geqo.h File Reference

#include "common/pg_prng.h"
#include "nodes/pathnodes.h"
#include "optimizer/geqo_gene.h"

Include dependency graph for geqo.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	GeqoPrivateData

Macros
#define	ERX
#define	DEFAULT_GEQO_EFFORT   5
#define	MIN_GEQO_EFFORT   1
#define	MAX_GEQO_EFFORT   10
#define	DEFAULT_GEQO_SELECTION_BIAS   2.0
#define	MIN_GEQO_SELECTION_BIAS   1.5
#define	MAX_GEQO_SELECTION_BIAS   2.0

Functions
RelOptInfo *	geqo (PlannerInfo *root, int number_of_rels, List *initial_rels)
Cost	geqo_eval (PlannerInfo *root, Gene *tour, int num_gene)
RelOptInfo *	gimme_tree (PlannerInfo *root, Gene *tour, int num_gene)

Variables
PGDLLIMPORT int	Geqo_effort
PGDLLIMPORT int	Geqo_pool_size
PGDLLIMPORT int	Geqo_generations
PGDLLIMPORT double	Geqo_selection_bias
PGDLLIMPORT double	Geqo_seed

Macro Definition Documentation

DEFAULT_GEQO_EFFORT

#define DEFAULT_GEQO_EFFORT   5

Definition at line 55 of file geqo.h.

DEFAULT_GEQO_SELECTION_BIAS

#define DEFAULT_GEQO_SELECTION_BIAS   2.0

Definition at line 65 of file geqo.h.

ERX

#define ERX

Definition at line 44 of file geqo.h.

MAX_GEQO_EFFORT

#define MAX_GEQO_EFFORT   10

Definition at line 57 of file geqo.h.

MAX_GEQO_SELECTION_BIAS

#define MAX_GEQO_SELECTION_BIAS   2.0

Definition at line 67 of file geqo.h.

MIN_GEQO_EFFORT

#define MIN_GEQO_EFFORT   1

Definition at line 56 of file geqo.h.

MIN_GEQO_SELECTION_BIAS

#define MIN_GEQO_SELECTION_BIAS   1.5

Definition at line 66 of file geqo.h.

Function Documentation

geqo()

RelOptInfo* geqo	(	PlannerInfo *	root,
		int	number_of_rels,
		List *	initial_rels
	)

Definition at line 67 of file geqo_main.c.

{
    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 = (void *) &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;
}

References alloc_chromo(), alloc_city_table(), alloc_edge_table(), alloc_pool(), cx(), Pool::data, DEBUG1, DEBUG2, elog(), ERROR, free_chromo(), free_city_table(), free_edge_table(), free_pool(), geqo_eval(), geqo_mutation(), Geqo_seed, geqo_selection(), Geqo_selection_bias, geqo_set_seed(), gimme_edge_table(), gimme_number_generations(), gimme_pool_size(), gimme_tour(), gimme_tree(), LOG, ox1(), ox2(), pmx(), px(), random_init_pool(), sort_pool(), spread_chromo(), generate_unaccent_rules::stdout, Chromosome::string, Pool::string_length, and Chromosome::worth.

Referenced by make_rel_from_joinlist().

geqo_eval()

Cost geqo_eval	(	PlannerInfo *	root,
		Gene *	tour,
		int	num_gene
	)

Definition at line 57 of file geqo_eval.c.

{
    MemoryContext mycontext;
    MemoryContext oldcxt;
    RelOptInfo *joinrel;
    Cost        fitness;
    int         savelength;
    struct HTAB *savehash;
 
    /*
     * Create a private memory context that will hold all temp storage
     * allocated inside gimme_tree().
     *
     * Since geqo_eval() will be called many times, we can't afford to let all
     * that memory go unreclaimed until end of statement.  Note we make the
     * temp context a child of the planner's normal context, so that it will
     * be freed even if we abort via ereport(ERROR).
     */
    mycontext = AllocSetContextCreate(CurrentMemoryContext,
                                      "GEQO",
                                      ALLOCSET_DEFAULT_SIZES);
    oldcxt = MemoryContextSwitchTo(mycontext);
 
    /*
     * gimme_tree will add entries to root->join_rel_list, which may or may
     * not already contain some entries.  The newly added entries will be
     * recycled by the MemoryContextDelete below, so we must ensure that the
     * list is restored to its former state before exiting.  We can do this by
     * truncating the list to its original length.  NOTE this assumes that any
     * added entries are appended at the end!
     *
     * We also must take care not to mess up the outer join_rel_hash, if there
     * is one.  We can do this by just temporarily setting the link to NULL.
     * (If we are dealing with enough join rels, which we very likely are, a
     * new hash table will get built and used locally.)
     *
     * join_rel_level[] shouldn't be in use, so just Assert it isn't.
     */
    savelength = list_length(root->join_rel_list);
    savehash = root->join_rel_hash;
    Assert(root->join_rel_level == NULL);
 
    root->join_rel_hash = NULL;
 
    /* construct the best path for the given combination of relations */
    joinrel = gimme_tree(root, tour, num_gene);
 
    /*
     * compute fitness, if we found a valid join
     *
     * XXX geqo does not currently support optimization for partial result
     * retrieval, nor do we take any cognizance of possible use of
     * parameterized paths --- how to fix?
     */
    if (joinrel)
    {
        Path       *best_path = joinrel->cheapest_total_path;
 
        fitness = best_path->total_cost;
    }
    else
        fitness = DBL_MAX;
 
    /*
     * Restore join_rel_list to its former state, and put back original
     * hashtable if any.
     */
    root->join_rel_list = list_truncate(root->join_rel_list,
                                        savelength);
    root->join_rel_hash = savehash;
 
    /* release all the memory acquired within gimme_tree */
    MemoryContextSwitchTo(oldcxt);
    MemoryContextDelete(mycontext);
 
    return fitness;
}

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Assert(), RelOptInfo::cheapest_total_path, CurrentMemoryContext, gimme_tree(), PlannerInfo::join_rel_list, list_length(), list_truncate(), MemoryContextDelete(), MemoryContextSwitchTo(), and Path::total_cost.

Referenced by geqo(), and random_init_pool().

gimme_tree()

RelOptInfo* gimme_tree	(	PlannerInfo *	root,
		Gene *	tour,
		int	num_gene
	)

Definition at line 163 of file geqo_eval.c.

{
    GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private;
    List       *clumps;
    int         rel_count;
 
    /*
     * Sometimes, a relation can't yet be joined to others due to heuristics
     * or actual semantic restrictions.  We maintain a list of "clumps" of
     * successfully joined relations, with larger clumps at the front. Each
     * new relation from the tour is added to the first clump it can be joined
     * to; if there is none then it becomes a new clump of its own. When we
     * enlarge an existing clump we check to see if it can now be merged with
     * any other clumps.  After the tour is all scanned, we forget about the
     * heuristics and try to forcibly join any remaining clumps.  If we are
     * unable to merge all the clumps into one, fail.
     */
    clumps = NIL;
 
    for (rel_count = 0; rel_count < num_gene; rel_count++)
    {
        int         cur_rel_index;
        RelOptInfo *cur_rel;
        Clump      *cur_clump;
 
        /* Get the next input relation */
        cur_rel_index = (int) tour[rel_count];
        cur_rel = (RelOptInfo *) list_nth(private->initial_rels,
                                          cur_rel_index - 1);
 
        /* Make it into a single-rel clump */
        cur_clump = (Clump *) palloc(sizeof(Clump));
        cur_clump->joinrel = cur_rel;
        cur_clump->size = 1;
 
        /* Merge it into the clumps list, using only desirable joins */
        clumps = merge_clump(root, clumps, cur_clump, num_gene, false);
    }
 
    if (list_length(clumps) > 1)
    {
        /* Force-join the remaining clumps in some legal order */
        List       *fclumps;
        ListCell   *lc;
 
        fclumps = NIL;
        foreach(lc, clumps)
        {
            Clump      *clump = (Clump *) lfirst(lc);
 
            fclumps = merge_clump(root, fclumps, clump, num_gene, true);
        }
        clumps = fclumps;
    }
 
    /* Did we succeed in forming a single join relation? */
    if (list_length(clumps) != 1)
        return NULL;
 
    return ((Clump *) linitial(clumps))->joinrel;
}

References Clump::joinrel, lfirst, linitial, list_length(), list_nth(), merge_clump(), NIL, palloc(), and Clump::size.

Referenced by geqo(), and geqo_eval().

Variable Documentation

Geqo_effort

PGDLLIMPORT int Geqo_effort

extern

Definition at line 39 of file geqo_main.c.

Referenced by gimme_pool_size().

Geqo_generations

PGDLLIMPORT int Geqo_generations

extern

Definition at line 41 of file geqo_main.c.

Referenced by gimme_number_generations().

Geqo_pool_size

PGDLLIMPORT int Geqo_pool_size

extern

Definition at line 40 of file geqo_main.c.

Referenced by gimme_pool_size().

Geqo_seed

PGDLLIMPORT double Geqo_seed

extern

Definition at line 43 of file geqo_main.c.

Referenced by geqo().

Geqo_selection_bias

PGDLLIMPORT double Geqo_selection_bias

extern

Definition at line 42 of file geqo_main.c.

Referenced by geqo().