PostgreSQL Source Code  git master
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 Listmerge_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)
 
RelOptInfogimme_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.

References have_join_order_restriction(), and have_relevant_joinclause().

Referenced by merge_clump().

327 {
328  /*
329  * Join if there is an applicable join clause, or if there is a join order
330  * restriction forcing these rels to be joined.
331  */
332  if (have_relevant_joinclause(root, outer_rel, inner_rel) ||
333  have_join_order_restriction(root, outer_rel, inner_rel))
334  return true;
335 
336  /* Otherwise postpone the join till later. */
337  return false;
338 }
bool have_join_order_restriction(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:947
bool have_relevant_joinclause(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joininfo.c:36

◆ geqo_eval()

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

Definition at line 57 of file geqo_eval.c.

References ALLOCSET_DEFAULT_SIZES, 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(), and Path::total_cost.

Referenced by geqo(), and random_init_pool().

58 {
59  MemoryContext mycontext;
60  MemoryContext oldcxt;
61  RelOptInfo *joinrel;
62  Cost fitness;
63  int savelength;
64  struct HTAB *savehash;
65 
66  /*
67  * Create a private memory context that will hold all temp storage
68  * allocated inside gimme_tree().
69  *
70  * Since geqo_eval() will be called many times, we can't afford to let all
71  * that memory go unreclaimed until end of statement. Note we make the
72  * temp context a child of the planner's normal context, so that it will
73  * be freed even if we abort via ereport(ERROR).
74  */
76  "GEQO",
78  oldcxt = MemoryContextSwitchTo(mycontext);
79 
80  /*
81  * gimme_tree will add entries to root->join_rel_list, which may or may
82  * not already contain some entries. The newly added entries will be
83  * recycled by the MemoryContextDelete below, so we must ensure that the
84  * list is restored to its former state before exiting. We can do this by
85  * truncating the list to its original length. NOTE this assumes that any
86  * added entries are appended at the end!
87  *
88  * We also must take care not to mess up the outer join_rel_hash, if there
89  * is one. We can do this by just temporarily setting the link to NULL.
90  * (If we are dealing with enough join rels, which we very likely are, a
91  * new hash table will get built and used locally.)
92  *
93  * join_rel_level[] shouldn't be in use, so just Assert it isn't.
94  */
95  savelength = list_length(root->join_rel_list);
96  savehash = root->join_rel_hash;
97  Assert(root->join_rel_level == NULL);
98 
99  root->join_rel_hash = NULL;
100 
101  /* construct the best path for the given combination of relations */
102  joinrel = gimme_tree(root, tour, num_gene);
103 
104  /*
105  * compute fitness, if we found a valid join
106  *
107  * XXX geqo does not currently support optimization for partial result
108  * retrieval, nor do we take any cognizance of possible use of
109  * parameterized paths --- how to fix?
110  */
111  if (joinrel)
112  {
113  Path *best_path = joinrel->cheapest_total_path;
114 
115  fitness = best_path->total_cost;
116  }
117  else
118  fitness = DBL_MAX;
119 
120  /*
121  * Restore join_rel_list to its former state, and put back original
122  * hashtable if any.
123  */
125  savelength);
126  root->join_rel_hash = savehash;
127 
128  /* release all the memory acquired within gimme_tree */
129  MemoryContextSwitchTo(oldcxt);
130  MemoryContextDelete(mycontext);
131 
132  return fitness;
133 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:211
#define AllocSetContextCreate
Definition: memutils.h:170
RelOptInfo * gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
Definition: geqo_eval.c:163
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
List * list_truncate(List *list, int new_size)
Definition: list.c:586
List * join_rel_list
Definition: pathnodes.h:244
Definition: dynahash.c:208
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:192
struct Path * cheapest_total_path
Definition: pathnodes.h:659
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
Cost total_cost
Definition: pathnodes.h:1126
#define Assert(condition)
Definition: c.h:739
List ** join_rel_level
Definition: pathnodes.h:254
static int list_length(const List *l)
Definition: pg_list.h:169
struct HTAB * join_rel_hash
Definition: pathnodes.h:245
double Cost
Definition: nodes.h:659

◆ gimme_tree()

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

Definition at line 163 of file geqo_eval.c.

References 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().

164 {
166  List *clumps;
167  int rel_count;
168 
169  /*
170  * Sometimes, a relation can't yet be joined to others due to heuristics
171  * or actual semantic restrictions. We maintain a list of "clumps" of
172  * successfully joined relations, with larger clumps at the front. Each
173  * new relation from the tour is added to the first clump it can be joined
174  * to; if there is none then it becomes a new clump of its own. When we
175  * enlarge an existing clump we check to see if it can now be merged with
176  * any other clumps. After the tour is all scanned, we forget about the
177  * heuristics and try to forcibly join any remaining clumps. If we are
178  * unable to merge all the clumps into one, fail.
179  */
180  clumps = NIL;
181 
182  for (rel_count = 0; rel_count < num_gene; rel_count++)
183  {
184  int cur_rel_index;
185  RelOptInfo *cur_rel;
186  Clump *cur_clump;
187 
188  /* Get the next input relation */
189  cur_rel_index = (int) tour[rel_count];
190  cur_rel = (RelOptInfo *) list_nth(private->initial_rels,
191  cur_rel_index - 1);
192 
193  /* Make it into a single-rel clump */
194  cur_clump = (Clump *) palloc(sizeof(Clump));
195  cur_clump->joinrel = cur_rel;
196  cur_clump->size = 1;
197 
198  /* Merge it into the clumps list, using only desirable joins */
199  clumps = merge_clump(root, clumps, cur_clump, num_gene, false);
200  }
201 
202  if (list_length(clumps) > 1)
203  {
204  /* Force-join the remaining clumps in some legal order */
205  List *fclumps;
206  ListCell *lc;
207 
208  fclumps = NIL;
209  foreach(lc, clumps)
210  {
211  Clump *clump = (Clump *) lfirst(lc);
212 
213  fclumps = merge_clump(root, fclumps, clump, num_gene, true);
214  }
215  clumps = fclumps;
216  }
217 
218  /* Did we succeed in forming a single join relation? */
219  if (list_length(clumps) != 1)
220  return NULL;
221 
222  return ((Clump *) linitial(clumps))->joinrel;
223 }
#define NIL
Definition: pg_list.h:65
int size
Definition: geqo_eval.c:39
void * join_search_private
Definition: pathnodes.h:359
RelOptInfo * joinrel
Definition: geqo_eval.c:38
static List * merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene, bool force)
Definition: geqo_eval.c:238
#define linitial(l)
Definition: pg_list.h:195
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
#define lfirst(lc)
Definition: pg_list.h:190
static int list_length(const List *l)
Definition: pg_list.h:169
void * palloc(Size size)
Definition: mcxt.c:949
Definition: pg_list.h:50

◆ 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.

References desirable_join(), foreach_delete_current, generate_gather_paths(), generate_partitionwise_join_paths(), Clump::joinrel, lappend(), lfirst, list_insert_nth(), list_length(), list_nth(), make_join_rel(), NIL, pfree(), set_cheapest(), and Clump::size.

Referenced by gimme_tree().

240 {
241  ListCell *lc;
242  int pos;
243 
244  /* Look for a clump that new_clump can join to */
245  foreach(lc, clumps)
246  {
247  Clump *old_clump = (Clump *) lfirst(lc);
248 
249  if (force ||
250  desirable_join(root, old_clump->joinrel, new_clump->joinrel))
251  {
252  RelOptInfo *joinrel;
253 
254  /*
255  * Construct a RelOptInfo representing the join of these two input
256  * relations. Note that we expect the joinrel not to exist in
257  * root->join_rel_list yet, and so the paths constructed for it
258  * will only include the ones we want.
259  */
260  joinrel = make_join_rel(root,
261  old_clump->joinrel,
262  new_clump->joinrel);
263 
264  /* Keep searching if join order is not valid */
265  if (joinrel)
266  {
267  /* Create paths for partitionwise joins. */
268  generate_partitionwise_join_paths(root, joinrel);
269 
270  /*
271  * Except for the topmost scan/join rel, consider gathering
272  * partial paths. We'll do the same for the topmost scan/join
273  * rel once we know the final targetlist (see
274  * grouping_planner).
275  */
276  if (old_clump->size + new_clump->size < num_gene)
277  generate_gather_paths(root, joinrel, false);
278 
279  /* Find and save the cheapest paths for this joinrel */
280  set_cheapest(joinrel);
281 
282  /* Absorb new clump into old */
283  old_clump->joinrel = joinrel;
284  old_clump->size += new_clump->size;
285  pfree(new_clump);
286 
287  /* Remove old_clump from list */
288  clumps = foreach_delete_current(clumps, lc);
289 
290  /*
291  * Recursively try to merge the enlarged old_clump with
292  * others. When no further merge is possible, we'll reinsert
293  * it into the list.
294  */
295  return merge_clump(root, clumps, old_clump, num_gene, force);
296  }
297  }
298  }
299 
300  /*
301  * No merging is possible, so add new_clump as an independent clump, in
302  * proper order according to size. We can be fast for the common case
303  * where it has size 1 --- it should always go at the end.
304  */
305  if (clumps == NIL || new_clump->size == 1)
306  return lappend(clumps, new_clump);
307 
308  /* Else search for the place to insert it */
309  for (pos = 0; pos < list_length(clumps); pos++)
310  {
311  Clump *old_clump = (Clump *) list_nth(clumps, pos);
312 
313  if (new_clump->size > old_clump->size)
314  break; /* new_clump belongs before old_clump */
315  }
316  clumps = list_insert_nth(clumps, pos, new_clump);
317 
318  return clumps;
319 }
#define NIL
Definition: pg_list.h:65
int size
Definition: geqo_eval.c:39
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:3663
RelOptInfo * joinrel
Definition: geqo_eval.c:38
void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:2682
#define foreach_delete_current(lst, cell)
Definition: pg_list.h:368
List * list_insert_nth(List *list, int pos, void *datum)
Definition: list.c:401
void pfree(void *pointer)
Definition: mcxt.c:1056
static List * merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene, bool force)
Definition: geqo_eval.c:238
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
List * lappend(List *list, void *datum)
Definition: list.c:322
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:244
RelOptInfo * make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:682
#define lfirst(lc)
Definition: pg_list.h:190
static int list_length(const List *l)
Definition: pg_list.h:169
static bool desirable_join(PlannerInfo *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel)
Definition: geqo_eval.c:325