Quelle  geqo_main.c

/*------------------------------------------------------------------------
 *
 * geqo_main.c
 *   solution to the query optimization problem
 *   by means of a Genetic Algorithm (GA)
 *
 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/backend/optimizer/geqo/geqo_main.c
 *
 *-------------------------------------------------------------------------
 */

/* contributed by:
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch     * Institute of Automatic Control    *
   =        = University of Mining and Technology =
   *  utesch@aut.tu-freiberg.de  * Freiberg, Germany       *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

/* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */

#include "postgres.h"

#include <math.h>

#include "optimizer/geqo.h"

#include "optimizer/geqo_misc.h"
#if defined(CX)
#include "optimizer/geqo_mutation.h"
#endif
#include "optimizer/geqo_pool.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"
#include "optimizer/geqo_selection.h"


/*
 * Configuration options
 */
int   Geqo_effort;
int   Geqo_pool_size;
int   Geqo_generations;
double  Geqo_selection_bias;
double  Geqo_seed;


static int gimme_pool_size(int nr_rel);
static int gimme_number_generations(int pool_size);

/* complain if no recombination mechanism is #define'd */
#if !defined(ERX) && \
 !defined(PMX) && \
 !defined(CX)  && \
 !defined(PX)  && \
 !defined(OX1) && \
 !defined(OX2)
#error "must choose one GEQO recombination mechanism in geqo.h"
#endif


/*
 * geqo
 *   solution of the query optimization problem
 *   similar to a constrained Traveling Salesman Problem (TSP)
 */

RelOptInfo *
geqo(PlannerInfo *root, int number_of_rels, List *initial_rels)
{
 GeqoPrivateData private;
 int   generation;
 Chromosome *momma;
 Chromosome *daddy;
 Chromosome *kid;
 Pool    *pool;
 int   pool_size,
    number_generations;

#ifdef GEQO_DEBUG
 int   status_interval;
#endif
 Gene    *best_tour;
 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 up private information */
 root->join_search_private = &private;
 private.initial_rels = initial_rels;

/* initialize private number generator */
 geqo_set_seed(root, Geqo_seed);

/* set GA parameters */
 pool_size = gimme_pool_size(number_of_rels);
 number_generations = gimme_number_generations(pool_size);
#ifdef GEQO_DEBUG
 status_interval = 10;
#endif

/* allocate genetic pool memory */
 pool = alloc_pool(root, pool_size, number_of_rels);

/* random initialization of the pool */
 random_init_pool(root, pool);

/* sort the pool according to cheapest path as fitness */
 sort_pool(root, pool);  /* we have to do it only one time, since all
         * kids replace the worst individuals in
 * future (-> geqo_pool.c:spread_chromo ) */

#ifdef GEQO_DEBUG
 elog(DEBUG1, "GEQO selected %d pool entries, best %.2f, worst %.2f",
   pool_size,
   pool->data[0].worth,
   pool->data[pool_size - 1].worth);
#endif

/* allocate chromosome momma and daddy memory */
 momma = alloc_chromo(root, pool->string_length);
 daddy = alloc_chromo(root, pool->string_length);

#if defined (ERX)
#ifdef GEQO_DEBUG
 elog(DEBUG2, "using edge recombination crossover [ERX]");
#endif
/* allocate edge table memory */
 edge_table = alloc_edge_table(root, pool->string_length);
#elif defined(PMX)
#ifdef GEQO_DEBUG
 elog(DEBUG2, "using partially matched crossover [PMX]");
#endif
/* allocate chromosome kid memory */
 kid = alloc_chromo(root, pool->string_length);
#elif defined(CX)
#ifdef GEQO_DEBUG
 elog(DEBUG2, "using cycle crossover [CX]");
#endif
/* allocate city table memory */
 kid = alloc_chromo(root, pool->string_length);
 city_table = alloc_city_table(root, pool->string_length);
#elif defined(PX)
#ifdef GEQO_DEBUG
 elog(DEBUG2, "using position crossover [PX]");
#endif
/* allocate city table memory */
 kid = alloc_chromo(root, pool->string_length);
 city_table = alloc_city_table(root, pool->string_length);
#elif defined(OX1)
#ifdef GEQO_DEBUG
 elog(DEBUG2, "using order crossover [OX1]");
#endif
/* allocate city table memory */
 kid = alloc_chromo(root, pool->string_length);
 city_table = alloc_city_table(root, pool->string_length);
#elif defined(OX2)
#ifdef GEQO_DEBUG
 elog(DEBUG2, "using order crossover [OX2]");
#endif
/* allocate city table memory */
 kid = alloc_chromo(root, pool->string_length);
 city_table = alloc_city_table(root, pool->string_length);
#endif


/* my pain main part: */
/* iterative optimization */

 for (generation = 0; generation < number_generations; generation++)
 {
  /* SELECTION: using linear bias function */
  geqo_selection(root, momma, daddy, pool, Geqo_selection_bias);

#if defined (ERX)
  /* EDGE RECOMBINATION CROSSOVER */
  gimme_edge_table(root, momma->string, daddy->string, pool->string_length, edge_table);

  kid = momma;

  /* are there any edge failures ? */
  edge_failures += gimme_tour(root, edge_table, kid->string, pool->string_length);
#elif defined(PMX)
  /* PARTIALLY MATCHED CROSSOVER */
  pmx(root, momma->string, daddy->string, kid->string, pool->string_length);
#elif defined(CX)
  /* CYCLE CROSSOVER */
  cycle_diffs = cx(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
  /* mutate the child */
  if (cycle_diffs == 0)
  {
   mutations++;
   geqo_mutation(root, kid->string, pool->string_length);
  }
#elif defined(PX)
  /* POSITION CROSSOVER */
  px(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
#elif defined(OX1)
  /* ORDER CROSSOVER */
  ox1(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
#elif defined(OX2)
  /* ORDER CROSSOVER */
  ox2(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
#endif


  /* EVALUATE FITNESS */
  kid->worth = geqo_eval(root, kid->string, pool->string_length);

  /* push the kid into the wilderness of life according to its worth */
  spread_chromo(root, kid, pool);


#ifdef GEQO_DEBUG
  if (status_interval && !(generation % status_interval))
   print_gen(stdout, pool, generation);
#endif

 }


#if defined(ERX)
#if defined(GEQO_DEBUG)
 if (edge_failures != 0)
  elog(LOG, "[GEQO] failures: %d, average: %d",
    edge_failures, (int) number_generations / edge_failures);
 else
  elog(LOG, "[GEQO] no edge failures detected");
#else
 /* suppress variable-set-but-not-used warnings from some compilers */
 (void) edge_failures;
#endif
#endif

#if defined(CX) && defined(GEQO_DEBUG)
 if (mutations != 0)
  elog(LOG, "[GEQO] mutations: %d, generations: %d",
    mutations, number_generations);
 else
  elog(LOG, "[GEQO] no mutations processed");
#endif

#ifdef GEQO_DEBUG
 print_pool(stdout, pool, 0, pool_size - 1);
#endif

#ifdef GEQO_DEBUG
 elog(DEBUG1, "GEQO best is %.2f after %d generations",
   pool->data[0].worth, number_generations);
#endif


 /*
  * got the cheapest query tree processed by geqo; first element of the
  * population indicates the best query tree
 */
 best_tour = (Gene *) pool->data[0].string;

 best_rel = gimme_tree(root, best_tour, pool->string_length);

 if (best_rel == NULL)
  elog(ERROR, "geqo failed to make a valid plan");

 /* DBG: show the query plan */
#ifdef NOT_USED
 print_plan(best_plan, root);
#endif

 /* ... free memory stuff */
 free_chromo(root, momma);
 free_chromo(root, daddy);

#if defined (ERX)
 free_edge_table(root, edge_table);
#elif defined(PMX)
 free_chromo(root, kid);
#elif defined(CX)
 free_chromo(root, kid);
 free_city_table(root, city_table);
#elif defined(PX)
 free_chromo(root, kid);
 free_city_table(root, city_table);
#elif defined(OX1)
 free_chromo(root, kid);
 free_city_table(root, city_table);
#elif defined(OX2)
 free_chromo(root, kid);
 free_city_table(root, city_table);
#endif

 free_pool(root, pool);

 /* ... clear root pointer to our private storage */
 root->join_search_private = NULL;

 return best_rel;
}


/*
 * Return either configured pool size or a good default
 *
 * The default is based on query size (no. of relations) = 2^(QS+1),
 * but constrained to a range based on the effort value.
 */
static int
gimme_pool_size(int nr_rel)
{
 double  size;
 int   minsize;
 int   maxsize;

 /* Legal pool size *must* be at least 2, so ignore attempt to select 1 */
 if (Geqo_pool_size >= 2)
  return Geqo_pool_size;

 size = pow(2.0, nr_rel + 1.0);

 maxsize = 50 * Geqo_effort; /* 50 to 500 individuals */
 if (size > maxsize)
  return maxsize;

 minsize = 10 * Geqo_effort; /* 10 to 100 individuals */
 if (size < minsize)
  return minsize;

 return (int) ceil(size);
}


/*
 * Return either configured number of generations or a good default
 *
 * The default is the same as the pool size, which allows us to be
 * sure that less-fit individuals get pushed out of the breeding
 * population before the run finishes.
 */
static int
gimme_number_generations(int pool_size)
{
 if (Geqo_generations > 0)
  return Geqo_generations;

 return pool_size;
}