Header And Logo
|
#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"
Go to the source code of this file.
Data Structures | |
| struct | Clump |
Functions | |
| static List * | merge_clump (PlannerInfo *root, List *clumps, Clump *new_clump, 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) |
| static bool desirable_join | ( | PlannerInfo * | root, | |
| RelOptInfo * | outer_rel, | |||
| RelOptInfo * | inner_rel | |||
| ) | [static] |
Definition at line 311 of file geqo_eval.c.
References have_join_order_restriction(), and have_relevant_joinclause().
Referenced by merge_clump().
{
/*
* 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;
}
| Cost geqo_eval | ( | PlannerInfo * | root, | |
| Gene * | tour, | |||
| int | num_gene | |||
| ) |
Definition at line 54 of file geqo_eval.c.
References ALLOCSET_DEFAULT_INITSIZE, ALLOCSET_DEFAULT_MAXSIZE, ALLOCSET_DEFAULT_MINSIZE, AllocSetContextCreate(), Assert, RelOptInfo::cheapest_total_path, CurrentMemoryContext, gimme_tree(), PlannerInfo::join_rel_hash, PlannerInfo::join_rel_level, PlannerInfo::join_rel_list, list_length(), list_truncate(), MemoryContextDelete(), MemoryContextSwitchTo(), NULL, and Path::total_cost.
Referenced by geqo(), and random_init_pool().
{
MemoryContext mycontext;
MemoryContext oldcxt;
RelOptInfo *joinrel;
Path *best_path;
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_MINSIZE,
ALLOCSET_DEFAULT_INITSIZE,
ALLOCSET_DEFAULT_MAXSIZE);
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);
best_path = joinrel->cheapest_total_path;
/*
* compute fitness
*
* 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?
*/
fitness = best_path->total_cost;
/*
* 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;
}
| RelOptInfo* gimme_tree | ( | PlannerInfo * | root, | |
| Gene * | tour, | |||
| int | num_gene | |||
| ) |
Definition at line 153 of file geqo_eval.c.
References elog, ERROR, PlannerInfo::join_search_private, Clump::joinrel, lfirst, linitial, list_length(), list_nth(), merge_clump(), NIL, palloc(), and Clump::size.
Referenced by geqo(), and geqo_eval().
{
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. Some forced
* joins might still fail due to semantics, but we should always be able
* to find some join order that works.
*/
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, 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, true);
}
clumps = fclumps;
}
/* Did we succeed in forming a single join relation? */
if (list_length(clumps) != 1)
elog(ERROR, "failed to join all relations together");
return ((Clump *) linitial(clumps))->joinrel;
}
| static List * merge_clump | ( | PlannerInfo * | root, | |
| List * | clumps, | |||
| Clump * | new_clump, | |||
| bool | force | |||
| ) | [static] |
Definition at line 229 of file geqo_eval.c.
References desirable_join(), Clump::joinrel, lappend(), lappend_cell(), lcons(), lfirst, list_delete_cell(), list_head(), lnext, make_join_rel(), NIL, NULL, pfree(), set_cheapest(), and Clump::size.
Referenced by gimme_tree().
{
ListCell *prev;
ListCell *lc;
/* Look for a clump that new_clump can join to */
prev = NULL;
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)
{
/* 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 = list_delete_cell(clumps, lc, prev);
/*
* 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, force);
}
}
prev = lc;
}
/*
* 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);
/* Check if it belongs at the front */
lc = list_head(clumps);
if (new_clump->size > ((Clump *) lfirst(lc))->size)
return lcons(new_clump, clumps);
/* Else search for the place to insert it */
for (;;)
{
ListCell *nxt = lnext(lc);
if (nxt == NULL || new_clump->size > ((Clump *) lfirst(nxt))->size)
break; /* it belongs after 'lc', before 'nxt' */
lc = nxt;
}
lappend_cell(clumps, lc, new_clump);
return clumps;
}
1.7.1