Branch data Line data Source code
1 : : /*------------------------------------------------------------------------
2 : : *
3 : : * geqo_eval.c
4 : : * Routines to evaluate query trees
5 : : *
6 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
7 : : * Portions Copyright (c) 1994, Regents of the University of California
8 : : *
9 : : * src/backend/optimizer/geqo/geqo_eval.c
10 : : *
11 : : *-------------------------------------------------------------------------
12 : : */
13 : :
14 : : /*
15 : : * contributed by:
16 : : * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
17 : : * * Martin Utesch * Institute of Automatic Control *
18 : : * = = University of Mining and Technology =
19 : : * * utesch@aut.tu-freiberg.de * Freiberg, Germany *
20 : : * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
21 : : */
22 : :
23 : : #include "postgres.h"
24 : :
25 : : #include <float.h>
26 : : #include <limits.h>
27 : :
28 : : #include "optimizer/geqo.h"
29 : : #include "optimizer/joininfo.h"
30 : : #include "optimizer/pathnode.h"
31 : : #include "optimizer/paths.h"
32 : : #include "utils/memutils.h"
33 : :
34 : :
35 : : /* A "clump" of already-joined relations within gimme_tree */
36 : : typedef struct
37 : : {
38 : : RelOptInfo *joinrel; /* joinrel for the set of relations */
39 : : int size; /* number of input relations in clump */
40 : : } Clump;
41 : :
42 : : static List *merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump,
43 : : int num_gene, bool force);
44 : : static bool desirable_join(PlannerInfo *root,
45 : : RelOptInfo *outer_rel, RelOptInfo *inner_rel);
46 : :
47 : :
48 : : /*
49 : : * geqo_eval
50 : : *
51 : : * Returns the fitness of a query tree as an individual of the population.
52 : : *
53 : : * If no legal join order can be extracted from the proposed tour, returns
54 : : * the invalid fitness described in geqo_gene.h.
55 : : */
56 : : Fitness
57 : 3640 : geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
58 : : {
59 : : MemoryContext mycontext;
60 : : MemoryContext oldcxt;
61 : : RelOptInfo *joinrel;
62 : : Fitness 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 : : */
75 : 3640 : mycontext = AllocSetContextCreate(CurrentMemoryContext,
76 : : "GEQO",
77 : : ALLOCSET_DEFAULT_SIZES);
78 : 3640 : 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 : 3640 : savelength = list_length(root->join_rel_list);
96 : 3640 : savehash = root->join_rel_hash;
97 : : Assert(root->join_rel_level == NULL);
98 : :
99 : 3640 : root->join_rel_hash = NULL;
100 : :
101 : : /* construct the best path for the given combination of relations */
102 : 3640 : 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 [ + - ]: 3640 : if (joinrel)
112 : : {
113 : 3640 : Path *best_path = joinrel->cheapest_total_path;
114 : :
115 : 3640 : fitness.disabled_nodes = best_path->disabled_nodes;
116 : 3640 : fitness.cost = best_path->total_cost;
117 : : }
118 : : else
119 : : {
120 : 0 : fitness.disabled_nodes = INT_MAX;
121 : 0 : fitness.cost = DBL_MAX;
122 : : }
123 : :
124 : : /*
125 : : * Restore join_rel_list to its former state, and put back original
126 : : * hashtable if any.
127 : : */
128 : 3640 : root->join_rel_list = list_truncate(root->join_rel_list,
129 : : savelength);
130 : 3640 : root->join_rel_hash = savehash;
131 : :
132 : : /* release all the memory acquired within gimme_tree */
133 : 3640 : MemoryContextSwitchTo(oldcxt);
134 : 3640 : MemoryContextDelete(mycontext);
135 : :
136 : 3640 : return fitness;
137 : : }
138 : :
139 : : /*
140 : : * gimme_tree
141 : : * Form planner estimates for a join tree constructed in the specified
142 : : * order.
143 : : *
144 : : * 'tour' is the proposed join order, of length 'num_gene'
145 : : *
146 : : * Returns a new join relation whose cheapest path is the best plan for
147 : : * this join order. NB: will return NULL if join order is invalid and
148 : : * we can't modify it into a valid order.
149 : : *
150 : : * The original implementation of this routine always joined in the specified
151 : : * order, and so could only build left-sided plans (and right-sided and
152 : : * mixtures, as a byproduct of the fact that make_join_rel() is symmetric).
153 : : * It could never produce a "bushy" plan. This had a couple of big problems,
154 : : * of which the worst was that there are situations involving join order
155 : : * restrictions where the only valid plans are bushy.
156 : : *
157 : : * The present implementation takes the given tour as a guideline, but
158 : : * postpones joins that are illegal or seem unsuitable according to some
159 : : * heuristic rules. This allows correct bushy plans to be generated at need,
160 : : * and as a nice side-effect it seems to materially improve the quality of the
161 : : * generated plans. Note however that since it's just a heuristic, it can
162 : : * still fail in some cases. (In particular, we might clump together
163 : : * relations that actually mustn't be joined yet due to LATERAL restrictions;
164 : : * since there's no provision for un-clumping, this must lead to failure.)
165 : : */
166 : : RelOptInfo *
167 : 3675 : gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
168 : : {
169 : 3675 : GeqoPrivateData *private = GetGeqoPrivateData(root);
170 : : List *clumps;
171 : : int rel_count;
172 : :
173 : : /*
174 : : * Sometimes, a relation can't yet be joined to others due to heuristics
175 : : * or actual semantic restrictions. We maintain a list of "clumps" of
176 : : * successfully joined relations, with larger clumps at the front. Each
177 : : * new relation from the tour is added to the first clump it can be joined
178 : : * to; if there is none then it becomes a new clump of its own. When we
179 : : * enlarge an existing clump we check to see if it can now be merged with
180 : : * any other clumps. After the tour is all scanned, we forget about the
181 : : * heuristics and try to forcibly join any remaining clumps. If we are
182 : : * unable to merge all the clumps into one, fail.
183 : : */
184 : 3675 : clumps = NIL;
185 : :
186 [ + + ]: 12960 : for (rel_count = 0; rel_count < num_gene; rel_count++)
187 : : {
188 : : int cur_rel_index;
189 : : RelOptInfo *cur_rel;
190 : : Clump *cur_clump;
191 : :
192 : : /* Get the next input relation */
193 : 9285 : cur_rel_index = (int) tour[rel_count];
194 : 9285 : cur_rel = (RelOptInfo *) list_nth(private->initial_rels,
195 : : cur_rel_index - 1);
196 : :
197 : : /* Make it into a single-rel clump */
198 : 9285 : cur_clump = palloc_object(Clump);
199 : 9285 : cur_clump->joinrel = cur_rel;
200 : 9285 : cur_clump->size = 1;
201 : :
202 : : /* Merge it into the clumps list, using only desirable joins */
203 : 9285 : clumps = merge_clump(root, clumps, cur_clump, num_gene, false);
204 : : }
205 : :
206 [ - + ]: 3675 : if (list_length(clumps) > 1)
207 : : {
208 : : /* Force-join the remaining clumps in some legal order */
209 : : List *fclumps;
210 : : ListCell *lc;
211 : :
212 : 0 : fclumps = NIL;
213 [ # # # # : 0 : foreach(lc, clumps)
# # ]
214 : : {
215 : 0 : Clump *clump = (Clump *) lfirst(lc);
216 : :
217 : 0 : fclumps = merge_clump(root, fclumps, clump, num_gene, true);
218 : : }
219 : 0 : clumps = fclumps;
220 : : }
221 : :
222 : : /* Did we succeed in forming a single join relation? */
223 [ - + ]: 3675 : if (list_length(clumps) != 1)
224 : 0 : return NULL;
225 : :
226 : 3675 : return ((Clump *) linitial(clumps))->joinrel;
227 : : }
228 : :
229 : : /*
230 : : * Merge a "clump" into the list of existing clumps for gimme_tree.
231 : : *
232 : : * We try to merge the clump into some existing clump, and repeat if
233 : : * successful. When no more merging is possible, insert the clump
234 : : * into the list, preserving the list ordering rule (namely, that
235 : : * clumps of larger size appear earlier).
236 : : *
237 : : * If force is true, merge anywhere a join is legal, even if it causes
238 : : * a cartesian join to be performed. When force is false, do only
239 : : * "desirable" joins.
240 : : */
241 : : static List *
242 : 14895 : merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene,
243 : : bool force)
244 : : {
245 : : ListCell *lc;
246 : : int pos;
247 : :
248 : : /* Look for a clump that new_clump can join to */
249 [ + + + + : 18149 : foreach(lc, clumps)
+ + ]
250 : : {
251 : 8864 : Clump *old_clump = (Clump *) lfirst(lc);
252 : :
253 [ + - + + ]: 17728 : if (force ||
254 : 8864 : desirable_join(root, old_clump->joinrel, new_clump->joinrel))
255 : : {
256 : : RelOptInfo *joinrel;
257 : :
258 : : /*
259 : : * Construct a RelOptInfo representing the join of these two input
260 : : * relations. Note that we expect the joinrel not to exist in
261 : : * root->join_rel_list yet, and so the paths constructed for it
262 : : * will only include the ones we want.
263 : : */
264 : 6984 : joinrel = make_join_rel(root,
265 : : old_clump->joinrel,
266 : : new_clump->joinrel);
267 : :
268 : : /* Keep searching if join order is not valid */
269 [ + + ]: 6984 : if (joinrel)
270 : : {
271 : 5610 : bool is_top_rel = bms_equal(joinrel->relids,
272 : 5610 : root->all_query_rels);
273 : :
274 : : /* Create paths for partitionwise joins. */
275 : 5610 : generate_partitionwise_join_paths(root, joinrel);
276 : :
277 : : /*
278 : : * Except for the topmost scan/join rel, consider gathering
279 : : * partial paths. We'll do the same for the topmost scan/join
280 : : * rel once we know the final targetlist (see
281 : : * grouping_planner).
282 : : */
283 [ + + ]: 5610 : if (!is_top_rel)
284 : 1935 : generate_useful_gather_paths(root, joinrel, false);
285 : :
286 : : /* Find and save the cheapest paths for this joinrel */
287 : 5610 : set_cheapest(joinrel);
288 : :
289 : : /*
290 : : * Except for the topmost scan/join rel, consider generating
291 : : * partial aggregation paths for the grouped relation on top
292 : : * of the paths of this rel. After that, we're done creating
293 : : * paths for the grouped relation, so run set_cheapest().
294 : : */
295 [ + + - + ]: 5610 : if (joinrel->grouped_rel != NULL && !is_top_rel)
296 : : {
297 : 0 : RelOptInfo *grouped_rel = joinrel->grouped_rel;
298 : :
299 : : Assert(IS_GROUPED_REL(grouped_rel));
300 : :
301 : 0 : generate_grouped_paths(root, grouped_rel, joinrel);
302 : 0 : set_cheapest(grouped_rel);
303 : : }
304 : :
305 : : /* Absorb new clump into old */
306 : 5610 : old_clump->joinrel = joinrel;
307 : 5610 : old_clump->size += new_clump->size;
308 : 5610 : pfree(new_clump);
309 : :
310 : : /* Remove old_clump from list */
311 : 5610 : clumps = foreach_delete_current(clumps, lc);
312 : :
313 : : /*
314 : : * Recursively try to merge the enlarged old_clump with
315 : : * others. When no further merge is possible, we'll reinsert
316 : : * it into the list.
317 : : */
318 : 5610 : return merge_clump(root, clumps, old_clump, num_gene, force);
319 : : }
320 : : }
321 : : }
322 : :
323 : : /*
324 : : * No merging is possible, so add new_clump as an independent clump, in
325 : : * proper order according to size. We can be fast for the common case
326 : : * where it has size 1 --- it should always go at the end.
327 : : */
328 [ + + + + ]: 9285 : if (clumps == NIL || new_clump->size == 1)
329 : 8564 : return lappend(clumps, new_clump);
330 : :
331 : : /* Else search for the place to insert it */
332 [ + + ]: 850 : for (pos = 0; pos < list_length(clumps); pos++)
333 : : {
334 : 721 : Clump *old_clump = (Clump *) list_nth(clumps, pos);
335 : :
336 [ + + ]: 721 : if (new_clump->size > old_clump->size)
337 : 592 : break; /* new_clump belongs before old_clump */
338 : : }
339 : 721 : clumps = list_insert_nth(clumps, pos, new_clump);
340 : :
341 : 721 : return clumps;
342 : : }
343 : :
344 : : /*
345 : : * Heuristics for gimme_tree: do we want to join these two relations?
346 : : */
347 : : static bool
348 : 8864 : desirable_join(PlannerInfo *root,
349 : : RelOptInfo *outer_rel, RelOptInfo *inner_rel)
350 : : {
351 : : /*
352 : : * Join if there is an applicable join clause, or if there is a join order
353 : : * restriction forcing these rels to be joined.
354 : : */
355 [ + + - + ]: 10744 : if (have_relevant_joinclause(root, outer_rel, inner_rel) ||
356 : 1880 : have_join_order_restriction(root, outer_rel, inner_rel))
357 : 6984 : return true;
358 : :
359 : : /* Otherwise postpone the join till later. */
360 : 1880 : return false;
361 : : }
|
