Re: [HACKERS] Improving GEQO
On Fri, May 29, 2015 at 12:59 AM, Merlin Moncure wrote: > On Wed, May 27, 2015 at 3:06 PM, boix wrote: > > Hello, my partner and me are working with the goal of improve the GEQO's > > performance, we tried with Ant Colony Optimization, but it does not > improve, > > actually we are trying with a new variant of Genetic Algorithm, > specifically > > Micro-GA. This algorithm finds a better solution than GEQO in less time, > > however the total query execution time is higher. The fitness is > calculated > > by geqo_eval function. Does anybody know why this happens? > > > > We attach the patch made with the changes in postgresql-9.2.0. > > can you submit more details? for example 'explain analyze' (perhaps > here: http://explain.depesz.com/) of the plans generated GEQO vs GA vs > stock? It sounds like you might be facing an estimation miss which is > not really an issue a better planner could solve. > > That said, assuming you're getting 'better' plans in less time suggest > you might be on to something. > > merlin > > What sort of tests are you running? I suspect that anything which is not too well thought out and tested might end up performing well only on small subset of tests. Also, what is the consistency of the plans generated? If you are only targeting planning time, I feel it might be of lesser value. However, if you can get large order joins to be executed in a near optimal (brute force) solution, you might be on to something. Something I would like to see done is remove the dead code that is present in existing GEQO. This might alone lead to lesser compilation times. -- Regards, Atri *l'apprenant*
Re: [HACKERS] Improving GEQO
On Wed, May 27, 2015 at 3:06 PM, boix wrote: > Hello, my partner and me are working with the goal of improve the GEQO's > performance, we tried with Ant Colony Optimization, but it does not improve, > actually we are trying with a new variant of Genetic Algorithm, specifically > Micro-GA. This algorithm finds a better solution than GEQO in less time, > however the total query execution time is higher. The fitness is calculated > by geqo_eval function. Does anybody know why this happens? > > We attach the patch made with the changes in postgresql-9.2.0. can you submit more details? for example 'explain analyze' (perhaps here: http://explain.depesz.com/) of the plans generated GEQO vs GA vs stock? It sounds like you might be facing an estimation miss which is not really an issue a better planner could solve. That said, assuming you're getting 'better' plans in less time suggest you might be on to something. merlin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Improving GEQO
We follow your advice, our goal is improve the quality of the solution
and we made it,however the total query execution time is higher.
Regards.
On 05/27/2015 04:36 PM, Tom Lane wrote:
boix writes:
Hello, my partner and me are working with the goal of improve the GEQO's
performance, we tried with Ant Colony Optimization, but it does not
improve, actually we are trying with a new variant of Genetic Algorithm,
specifically Micro-GA. This algorithm finds a better solution than GEQO
in less time, however the total query execution time is higher. The
fitness is calculated by geqo_eval function. Does anybody know why this
happens?
Well, for one thing, you can't just do this:
+ aux = aux1;
without totally confusing all your subsequent steps.
You'd want to copy the pointed-to data, likely, not the pointer.
regards, tom lane
diff --git a/contrib/Makefile b/contrib/Makefile
index d230451..df9ccef 100755
--- a/contrib/Makefile
+++ b/contrib/Makefile
@@ -26,6 +26,7 @@ SUBDIRS = \
isn \
lo \
ltree \
+ microg \
oid2name \
pageinspect \
passwordcheck \
diff --git a/contrib/microg/Makefile b/contrib/microg/Makefile
new file mode 100644
index 000..7597ede
--- /dev/null
+++ b/contrib/microg/Makefile
@@ -0,0 +1,25 @@
+#-
+#
+# Makefile--
+#Makefile for the genetic query optimizer module
+#
+# Copyright (c) 2015, Universidad Central Marta Abreu de Las Villas
+#
+# contrib/microg/Makefile
+#
+#-
+
+MODULE_big = microg
+OBJS = microg_main.o
+
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = contrib/microg
+top_builddir = ../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/contrib/microg/microg_main.c b/contrib/microg/microg_main.c
new file mode 100644
index 000..f71a0be
--- /dev/null
+++ b/contrib/microg/microg_main.c
@@ -0,0 +1,445 @@
+/*
+ *
+ * microg_main.c
+ * solution to the query optimization problem
+ * by means of a Micro Genetic Algorithm (micro-GA)
+ *
+ * Portions Copyright (c) 2014-2015, PostgreSQL Global Development Group
+ * Portions Copyright (c) 2015, Universidad Central de Las Villas
+ *
+ * contrib/microg_main.c
+ *
+ *-
+ */
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * ute...@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Laura Perez Triana
+ * Centro de Estudios Informaticos
+ *== Universidad Central de Las Villas =* ltri...@uclv.cu *Villa Clara, Cuba
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Alegandro G. Gomez Boix
+ * Centro de Estudios Informaticos
+ *== Universidad Central de Las Villas =* b...@uclv.cu *Villa Clara, Cuba
+ */
+
+/* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
+
+#include "postgres.h"
+
+#include
+
+#include "optimizer/geqo_misc.h"
+#include "optimizer/geqo_mutation.h"
+#include "optimizer/geqo_pool.h"
+#include "optimizer/geqo_random.h"
+#include "optimizer/geqo_selection.h"
+#include "optimizer/geqo_gene.h"
+#include "optimizer/paths.h"
+#include
+#include "fmgr.h"
+
+PG_MODULE_MAGIC
+;
+
+/*
+ * Configuration options
+ */
+int Geqo_effort;
+int Geqo_pool_size;
+int Geqo_generations;
+double Geqo_selection_bias;
+double Geqo_seed;
+
+join_search_hook_type join_search_hook = NULL;
+
+void _PG_init(void);
+void _PG_fini(void);
+
+/* new functions of microg */
+void random_init_poolMG(PlannerInfo *root, Pool *pool);
+int meanCommonEdgeInPool(Chromosome *pool, int pool_size, int number_of_rels);
+int existEdge(Gene a, Gene b, Gene* s2, int lenght);
+int commonEdge(Gene* s1, Gene* s2, int number_of_rels);
+Chromosome * localSerch2_opt(PlannerInfo *root, Gene* solution, int sizeProblem);
+RelOptInfo *microg(PlannerInfo *root, int number_of_rels, List *initial_rels);
+
+/* define edge recombination crossover [ERX] per default */
+#if !defined(ERX) && \
+ !defined(PMX) && \
+ !defined(CX) && \
+ !defined(PX) && \
+ !defined(OX1) && \
+ !defined(OX2)
+#define ERX
+#endif
+
+/*
+ * microg
+ * solution of the query optimization problem
+ * similar to a constrained Traveling Salesman Problem (TSP)
+ */
+
+RelOptInfo *
+microg(PlannerInfo *root, int number_of_rels, List *initial_rels) {
+ GeqoPrivateData private;
+ int generation;
+ Chromosome *momma;
+ Chromosome *daddy;
+ Chromosome *kid, *result;
+ Pool *pool;
+ int pool_size, number_generations;
+
+ struct ti
Re: [HACKERS] Improving GEQO
boix writes: > Hello, my partner and me are working with the goal of improve the GEQO's > performance, we tried with Ant Colony Optimization, but it does not > improve, actually we are trying with a new variant of Genetic Algorithm, > specifically Micro-GA. This algorithm finds a better solution than GEQO > in less time, however the total query execution time is higher. The > fitness is calculated by geqo_eval function. Does anybody know why this > happens? Well, for one thing, you can't just do this: + aux = aux1; without totally confusing all your subsequent steps. You'd want to copy the pointed-to data, likely, not the pointer. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] Improving GEQO
Hello, my partner and me are working with the goal of improve the GEQO's
performance, we tried with Ant Colony Optimization, but it does not
improve, actually we are trying with a new variant of Genetic Algorithm,
specifically Micro-GA. This algorithm finds a better solution than GEQO
in less time, however the total query execution time is higher. The
fitness is calculated by geqo_eval function. Does anybody know why this
happens?
We attach the patch made with the changes in postgresql-9.2.0.
Regards.
diff --git a/contrib/Makefile b/contrib/Makefile
index d230451..df9ccef 100755
--- a/contrib/Makefile
+++ b/contrib/Makefile
@@ -26,6 +26,7 @@ SUBDIRS = \
isn \
lo \
ltree \
+ microg \
oid2name \
pageinspect \
passwordcheck \
diff --git a/contrib/microg/Makefile b/contrib/microg/Makefile
new file mode 100644
index 000..7597ede
--- /dev/null
+++ b/contrib/microg/Makefile
@@ -0,0 +1,25 @@
+#-
+#
+# Makefile--
+#Makefile for the genetic query optimizer module
+#
+# Copyright (c) 2015, Universidad Central Marta Abreu de Las Villas
+#
+# contrib/microg/Makefile
+#
+#-
+
+MODULE_big = microg
+OBJS = microg_main.o
+
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = contrib/microg
+top_builddir = ../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/contrib/microg/microg_main.c b/contrib/microg/microg_main.c
new file mode 100644
index 000..0bd896d
--- /dev/null
+++ b/contrib/microg/microg_main.c
@@ -0,0 +1,451 @@
+/*
+ *
+ * microg_main.c
+ * solution to the query optimization problem
+ * by means of a Micro Genetic Algorithm (micro-GA)
+ *
+ * Portions Copyright (c) 2014-2015, PostgreSQL Global Development Group
+ * Portions Copyright (c) 2015, Universidad Central de Las Villas
+ *
+ * contrib/microg_main.c
+ *
+ *-
+ */
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * ute...@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+* Laura Perez Triana
+* Centro de Estudios Informaticos
+*== Universidad Central de Las Villas =* ltri...@uclv.cu *Villa Clara, Cuba
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+* Alejandro G. Gomez Boix
+* Centro de Estudios Informaticos
+*== Universidad Central de Las Villas =* b...@uclv.cu *Villa Clara, Cuba
+ */
+
+/* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
+
+#include "postgres.h"
+
+#include
+
+#include "optimizer/geqo_misc.h"
+#include "optimizer/geqo_mutation.h"
+#include "optimizer/geqo_pool.h"
+#include "optimizer/geqo_random.h"
+#include "optimizer/geqo_selection.h"
+#include "optimizer/geqo_gene.h"
+#include "optimizer/paths.h"
+#include
+#include "fmgr.h"
+
+PG_MODULE_MAGIC
+;
+
+/*
+ * Configuration options
+ */
+int Geqo_effort;
+int Geqo_pool_size;
+int Geqo_generations;
+double Geqo_selection_bias;
+double Geqo_seed;
+
+join_search_hook_type join_search_hook = NULL;
+
+void _PG_init(void);
+void _PG_fini(void);
+
+
+/* new functions of microg */
+void random_init_poolMG(PlannerInfo *root, Pool *pool);
+int meanCommonEdgeInPool(Chromosome *pool, int pool_size, int number_of_rels);
+int existEdge(Gene a, Gene b, Gene* s2, int lenght);
+int commonEdge(Gene* s1, Gene* s2, int number_of_rels);
+Chromosome * localSerch2_opt(PlannerInfo *root, Gene* solution, int sizeProblem);
+RelOptInfo *microg(PlannerInfo *root, int number_of_rels, List *initial_rels);
+
+
+/* define edge recombination crossover [ERX] per default */
+#if !defined(ERX) && \
+ !defined(PMX) && \
+ !defined(CX) && \
+ !defined(PX) && \
+ !defined(OX1) && \
+ !defined(OX2)
+#define ERX
+#endif
+
+/*
+ * microg
+ * solution of the query optimization problem
+ * similar to a constrained Traveling Salesman Problem (TSP)
+ */
+
+RelOptInfo *
+microg(PlannerInfo *root, int number_of_rels, List *initial_rels) {
+ GeqoPrivateData
+private;
+ int generation;
+ Chromosome *momma;
+ Chromosome *daddy;
+ Chromosome *kid, *result;
+ Pool *pool;
+ int pool_size, number_generations;
+
+ struct timeb seed;
+
+#ifdef GEQO_DEBUG
+ int status_interval;
+#endif
+
+ RelOptInfo *best_rel;
+
+#if defined(ERX)
+ Edge *edge_table; /* list of edges */
+ int edge_failures = 0;
+#endif
+#if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
+ City *city_table; /* list of cities */
+#endif
+#if defined(CX)
+ int cycle_diffs = 0;
+ int mutations = 0;
+#endif
+
+ /* set
Re: [HACKERS] Improving GEQO
On Wed, May 20, 2015 at 1:06 PM, alejandro wrote: > hello, my partner and me are working with the goal of improve the GEQO's > performance, we tried with Ant Colony Optimization, but it does not improve, > actually we are trying with a new variant of Genetic Algorithm, specifically > Micro-GA. This algorithm finds a better solution than GEQO in less time, > however the total query execution time is higher. The fitness is calculated > by geqo_eval function. Does anybody know why this happens? > It will be difficult for anyone here to figure out anything without the code to look at -- Jaime Casanova www.2ndQuadrant.com Professional PostgreSQL: Soporte 24x7 y capacitación -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] Improving GEQO
hello, my partner and me are working with the goal of improve the GEQO's performance, we tried with Ant Colony Optimization, but it does not improve, actually we are trying with a new variant of Genetic Algorithm, specifically Micro-GA. This algorithm finds a better solution than GEQO in less time, however the total query execution time is higher. The fitness is calculated by geqo_eval function. Does anybody know why this happens? Regards.
