geqo_eval.c File Reference

#include "postgres.h"
#include <float.h>
#include <limits.h>
#include <math.h>
#include "optimizer/geqo.h"
#include "optimizer/joininfo.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "utils/memutils.h"

Include dependency graph for geqo_eval.c:

Go to the source code of this file.

Data Structures
struct	Clump

Functions
static List *	merge_clump (PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene, bool force)
static bool	desirable_join (PlannerInfo *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel)
Cost	geqo_eval (PlannerInfo *root, Gene *tour, int num_gene)
RelOptInfo *	gimme_tree (PlannerInfo *root, Gene *tour, int num_gene)

Function Documentation

desirable_join()

static bool desirable_join ( PlannerInfo *  root, RelOptInfo *  outer_rel, RelOptInfo *  inner_rel  )

static

Definition at line 325 of file geqo_eval.c.

{
    /*
     * Join if there is an applicable join clause, or if there is a join order
     * restriction forcing these rels to be joined.
     */
    if (have_relevant_joinclause(root, outer_rel, inner_rel) ||
        have_join_order_restriction(root, outer_rel, inner_rel))
        return true;
 
    /* Otherwise postpone the join till later. */
    return false;
}

References have_join_order_restriction(), have_relevant_joinclause(), and root.

Referenced by merge_clump().

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(), list_length(), list_truncate(), MemoryContextDelete(), MemoryContextSwitchTo(), root, 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 for(), Clump::joinrel, lfirst, linitial, list_length(), list_nth(), merge_clump(), NIL, palloc(), root, and Clump::size.

Referenced by geqo(), and geqo_eval().

merge_clump()

static List * merge_clump ( PlannerInfo *  root, List *  clumps, Clump *  new_clump, int  num_gene, bool  force  )

static

Definition at line 238 of file geqo_eval.c.

{
    ListCell   *lc;
    int         pos;
 
    /* Look for a clump that new_clump can join to */
    foreach(lc, clumps)
    {
        Clump      *old_clump = (Clump *) lfirst(lc);
 
        if (force ||
            desirable_join(root, old_clump->joinrel, new_clump->joinrel))
        {
            RelOptInfo *joinrel;
 
            /*
             * Construct a RelOptInfo representing the join of these two input
             * relations.  Note that we expect the joinrel not to exist in
             * root->join_rel_list yet, and so the paths constructed for it
             * will only include the ones we want.
             */
            joinrel = make_join_rel(root,
                                    old_clump->joinrel,
                                    new_clump->joinrel);
 
            /* Keep searching if join order is not valid */
            if (joinrel)
            {
                /* Create paths for partitionwise joins. */
                generate_partitionwise_join_paths(root, joinrel);
 
                /*
                 * Except for the topmost scan/join rel, consider gathering
                 * partial paths.  We'll do the same for the topmost scan/join
                 * rel once we know the final targetlist (see
                 * grouping_planner).
                 */
                if (!bms_equal(joinrel->relids, root->all_query_rels))
                    generate_useful_gather_paths(root, joinrel, false);
 
                /* Find and save the cheapest paths for this joinrel */
                set_cheapest(joinrel);
 
                /* Absorb new clump into old */
                old_clump->joinrel = joinrel;
                old_clump->size += new_clump->size;
                pfree(new_clump);
 
                /* Remove old_clump from list */
                clumps = foreach_delete_current(clumps, lc);
 
                /*
                 * Recursively try to merge the enlarged old_clump with
                 * others.  When no further merge is possible, we'll reinsert
                 * it into the list.
                 */
                return merge_clump(root, clumps, old_clump, num_gene, force);
            }
        }
    }
 
    /*
     * No merging is possible, so add new_clump as an independent clump, in
     * proper order according to size.  We can be fast for the common case
     * where it has size 1 --- it should always go at the end.
     */
    if (clumps == NIL || new_clump->size == 1)
        return lappend(clumps, new_clump);
 
    /* Else search for the place to insert it */
    for (pos = 0; pos < list_length(clumps); pos++)
    {
        Clump      *old_clump = (Clump *) list_nth(clumps, pos);
 
        if (new_clump->size > old_clump->size)
            break;              /* new_clump belongs before old_clump */
    }
    clumps = list_insert_nth(clumps, pos, new_clump);
 
    return clumps;
}

References bms_equal(), desirable_join(), foreach_delete_current, generate_partitionwise_join_paths(), generate_useful_gather_paths(), Clump::joinrel, lappend(), lfirst, list_insert_nth(), list_length(), list_nth(), make_join_rel(), NIL, pfree(), RelOptInfo::relids, root, set_cheapest(), and Clump::size.

Referenced by gimme_tree().