Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * pgpa_join.c
4 : : * analysis of joins in Plan trees
5 : : *
6 : : * Copyright (c) 2016-2026, PostgreSQL Global Development Group
7 : : *
8 : : * contrib/pg_plan_advice/pgpa_join.c
9 : : *
10 : : *-------------------------------------------------------------------------
11 : : */
12 : :
13 : : #include "postgres.h"
14 : :
15 : : #include "pgpa_join.h"
16 : : #include "pgpa_scan.h"
17 : : #include "pgpa_walker.h"
18 : :
19 : : #include "nodes/pathnodes.h"
20 : : #include "nodes/print.h"
21 : : #include "parser/parsetree.h"
22 : :
23 : : /*
24 : : * Temporary object used when unrolling a join tree.
25 : : */
26 : : struct pgpa_join_unroller
27 : : {
28 : : unsigned nallocated;
29 : : unsigned nused;
30 : : Plan *outer_subplan;
31 : : ElidedNode *outer_elided_node;
32 : : bool outer_beneath_any_gather;
33 : : pgpa_join_strategy *strategy;
34 : : Plan **inner_subplans;
35 : : ElidedNode **inner_elided_nodes;
36 : : pgpa_join_unroller **inner_unrollers;
37 : : bool *inner_beneath_any_gather;
38 : : };
39 : :
40 : : static pgpa_join_strategy pgpa_decompose_join(pgpa_plan_walker_context *walker,
41 : : Plan *plan,
42 : : Plan **realouter,
43 : : Plan **realinner,
44 : : ElidedNode **elidedrealouter,
45 : : ElidedNode **elidedrealinner,
46 : : bool *found_any_outer_gather,
47 : : bool *found_any_inner_gather);
48 : : static ElidedNode *pgpa_descend_node(PlannedStmt *pstmt, Plan **plan);
49 : : static ElidedNode *pgpa_descend_any_gather(PlannedStmt *pstmt, Plan **plan,
50 : : bool *found_any_gather);
51 : : static bool pgpa_descend_any_unique(PlannedStmt *pstmt, Plan **plan,
52 : : ElidedNode **elided_node);
53 : :
54 : : static bool is_result_node_with_child(Plan *plan);
55 : : static bool is_sorting_plan(Plan *plan);
56 : :
57 : : /*
58 : : * Create an initially-empty object for unrolling joins.
59 : : *
60 : : * This function creates a helper object that can later be used to create a
61 : : * pgpa_unrolled_join, after first calling pgpa_unroll_join one or more times.
62 : : */
63 : : pgpa_join_unroller *
64 : 23027 : pgpa_create_join_unroller(void)
65 : : {
66 : : pgpa_join_unroller *join_unroller;
67 : :
68 : 23027 : join_unroller = palloc0_object(pgpa_join_unroller);
69 : 23027 : join_unroller->nallocated = 4;
70 : 23027 : join_unroller->strategy =
71 : 23027 : palloc_array(pgpa_join_strategy, join_unroller->nallocated);
72 : 23027 : join_unroller->inner_subplans =
73 : 23027 : palloc_array(Plan *, join_unroller->nallocated);
74 : 23027 : join_unroller->inner_elided_nodes =
75 : 23027 : palloc_array(ElidedNode *, join_unroller->nallocated);
76 : 23027 : join_unroller->inner_unrollers =
77 : 23027 : palloc_array(pgpa_join_unroller *, join_unroller->nallocated);
78 : 23027 : join_unroller->inner_beneath_any_gather =
79 : 23027 : palloc_array(bool, join_unroller->nallocated);
80 : :
81 : 23027 : return join_unroller;
82 : : }
83 : :
84 : : /*
85 : : * Unroll one level of an unrollable join tree.
86 : : *
87 : : * Our basic goal here is to unroll join trees as they occur in the Plan
88 : : * tree into a simpler and more regular structure that we can more easily
89 : : * use for further processing. Unrolling is outer-deep, so if the plan tree
90 : : * has Join1(Join2(A,B),Join3(C,D)), the same join unroller object should be
91 : : * used for Join1 and Join2, but a different one will be needed for Join3,
92 : : * since that involves a join within the *inner* side of another join.
93 : : *
94 : : * pgpa_plan_walker creates a "top level" join unroller object when it
95 : : * encounters a join in a portion of the plan tree in which no join unroller
96 : : * is already active. From there, this function is responsible for determining
97 : : * to what portion of the plan tree that join unroller applies, and for
98 : : * creating any subordinate join unroller objects that are needed as a result
99 : : * of non-outer-deep join trees. We do this by returning the join unroller
100 : : * objects that should be used for further traversal of the outer and inner
101 : : * subtrees of the current plan node via *outer_join_unroller and
102 : : * *inner_join_unroller, respectively.
103 : : */
104 : : void
105 : 31115 : pgpa_unroll_join(pgpa_plan_walker_context *walker, Plan *plan,
106 : : bool beneath_any_gather,
107 : : pgpa_join_unroller *join_unroller,
108 : : pgpa_join_unroller **outer_join_unroller,
109 : : pgpa_join_unroller **inner_join_unroller)
110 : : {
111 : : pgpa_join_strategy strategy;
112 : : Plan *realinner,
113 : : *realouter;
114 : : ElidedNode *elidedinner,
115 : : *elidedouter;
116 : : int n;
117 : 31115 : bool found_any_outer_gather = false;
118 : 31115 : bool found_any_inner_gather = false;
119 : :
120 : : Assert(join_unroller != NULL);
121 : :
122 : : /*
123 : : * We need to pass the join_unroller object down through certain types of
124 : : * plan nodes -- anything that's considered part of the join strategy, and
125 : : * any other nodes that can occur in a join tree despite not being scans
126 : : * or joins.
127 : : *
128 : : * This includes:
129 : : *
130 : : * (1) Materialize, Memoize, and Hash nodes, which are part of the join
131 : : * strategy,
132 : : *
133 : : * (2) Gather and Gather Merge nodes, which can occur at any point in the
134 : : * join tree where the planner decided to initiate parallelism,
135 : : *
136 : : * (3) Sort and IncrementalSort nodes, which can occur beneath MergeJoin
137 : : * or GatherMerge,
138 : : *
139 : : * (4) Agg and Unique nodes, which can occur when we decide to make the
140 : : * nullable side of a semijoin unique and then join the result, and
141 : : *
142 : : * (5) Result nodes with children, which can be added either to project to
143 : : * enforce a one-time filter (but Result nodes without children are
144 : : * degenerate scans or joins).
145 : : */
146 [ + + + - : 31115 : if (IsA(plan, Material) || IsA(plan, Memoize) || IsA(plan, Hash)
+ + ]
147 [ + + + - ]: 30510 : || IsA(plan, Gather) || IsA(plan, GatherMerge)
148 [ + + + + : 30486 : || is_sorting_plan(plan) || IsA(plan, Agg) || IsA(plan, Unique)
+ + ]
149 [ + + ]: 30255 : || is_result_node_with_child(plan))
150 : : {
151 : 862 : *outer_join_unroller = join_unroller;
152 : 862 : return;
153 : : }
154 : :
155 : : /*
156 : : * Since we've already handled nodes that require pass-through treatment,
157 : : * this should be an unrollable join.
158 : : */
159 : 30253 : strategy = pgpa_decompose_join(walker, plan,
160 : : &realouter, &realinner,
161 : : &elidedouter, &elidedinner,
162 : : &found_any_outer_gather,
163 : : &found_any_inner_gather);
164 : :
165 : : /* If our workspace is full, expand it. */
166 [ + + ]: 30253 : if (join_unroller->nused >= join_unroller->nallocated)
167 : : {
168 : 64 : join_unroller->nallocated *= 2;
169 : 64 : join_unroller->strategy =
170 : 64 : repalloc_array(join_unroller->strategy,
171 : : pgpa_join_strategy,
172 : : join_unroller->nallocated);
173 : 64 : join_unroller->inner_subplans =
174 : 64 : repalloc_array(join_unroller->inner_subplans,
175 : : Plan *,
176 : : join_unroller->nallocated);
177 : 64 : join_unroller->inner_elided_nodes =
178 : 64 : repalloc_array(join_unroller->inner_elided_nodes,
179 : : ElidedNode *,
180 : : join_unroller->nallocated);
181 : 64 : join_unroller->inner_beneath_any_gather =
182 : 64 : repalloc_array(join_unroller->inner_beneath_any_gather,
183 : : bool,
184 : : join_unroller->nallocated);
185 : 64 : join_unroller->inner_unrollers =
186 : 64 : repalloc_array(join_unroller->inner_unrollers,
187 : : pgpa_join_unroller *,
188 : : join_unroller->nallocated);
189 : : }
190 : :
191 : : /*
192 : : * Since we're flattening outer-deep join trees, it follows that if the
193 : : * outer side is still an unrollable join, it should be unrolled into this
194 : : * same object. Otherwise, we've reached the limit of what we can unroll
195 : : * into this object and must remember the outer side as the final outer
196 : : * subplan.
197 : : */
198 [ + + + + ]: 30253 : if (elidedouter == NULL && pgpa_is_join(realouter))
199 : 7226 : *outer_join_unroller = join_unroller;
200 : : else
201 : : {
202 : 23027 : join_unroller->outer_subplan = realouter;
203 : 23027 : join_unroller->outer_elided_node = elidedouter;
204 : 23027 : join_unroller->outer_beneath_any_gather =
205 [ + + + + ]: 23027 : beneath_any_gather || found_any_outer_gather;
206 : : }
207 : :
208 : : /*
209 : : * Store the inner subplan. If it's an unrollable join, it needs to be
210 : : * flattened in turn, but into a new unroller object, not this one.
211 : : */
212 : 30253 : n = join_unroller->nused++;
213 : 30253 : join_unroller->strategy[n] = strategy;
214 : 30253 : join_unroller->inner_subplans[n] = realinner;
215 : 30253 : join_unroller->inner_elided_nodes[n] = elidedinner;
216 : 30253 : join_unroller->inner_beneath_any_gather[n] =
217 [ + + + + ]: 30253 : beneath_any_gather || found_any_inner_gather;
218 [ + + + + ]: 30253 : if (elidedinner == NULL && pgpa_is_join(realinner))
219 : 1057 : *inner_join_unroller = pgpa_create_join_unroller();
220 : : else
221 : 29196 : *inner_join_unroller = NULL;
222 : 30253 : join_unroller->inner_unrollers[n] = *inner_join_unroller;
223 : : }
224 : :
225 : : /*
226 : : * Use the data we've accumulated in a pgpa_join_unroller object to construct
227 : : * a pgpa_unrolled_join.
228 : : */
229 : : pgpa_unrolled_join *
230 : 23027 : pgpa_build_unrolled_join(pgpa_plan_walker_context *walker,
231 : : pgpa_join_unroller *join_unroller)
232 : : {
233 : : pgpa_unrolled_join *ujoin;
234 : :
235 : : /*
236 : : * We shouldn't have gone even so far as to create a join unroller unless
237 : : * we found at least one unrollable join.
238 : : */
239 : : Assert(join_unroller->nused > 0);
240 : :
241 : : /* Allocate result structures. */
242 : 23027 : ujoin = palloc0_object(pgpa_unrolled_join);
243 : 23027 : ujoin->ninner = join_unroller->nused;
244 : 23027 : ujoin->strategy = palloc0_array(pgpa_join_strategy, join_unroller->nused);
245 : 23027 : ujoin->inner = palloc0_array(pgpa_join_member, join_unroller->nused);
246 : :
247 : : /* Handle the outermost join. */
248 : 23027 : ujoin->outer.plan = join_unroller->outer_subplan;
249 : 23027 : ujoin->outer.elided_node = join_unroller->outer_elided_node;
250 : 23027 : ujoin->outer.scan =
251 : 23027 : pgpa_build_scan(walker, ujoin->outer.plan,
252 : : ujoin->outer.elided_node,
253 : 23027 : join_unroller->outer_beneath_any_gather,
254 : : true);
255 : :
256 : : /*
257 : : * We want the joins from the deepest part of the plan tree to appear
258 : : * first in the result object, but the join unroller adds them in exactly
259 : : * the reverse of that order, so we need to flip the order of the arrays
260 : : * when constructing the final result.
261 : : */
262 [ + + ]: 53280 : for (unsigned i = 0; i < join_unroller->nused; ++i)
263 : : {
264 : 30253 : int k = join_unroller->nused - i - 1;
265 : :
266 : : /* Copy strategy, Plan, and ElidedNode. */
267 : 30253 : ujoin->strategy[i] = join_unroller->strategy[k];
268 : 30253 : ujoin->inner[i].plan = join_unroller->inner_subplans[k];
269 : 30253 : ujoin->inner[i].elided_node = join_unroller->inner_elided_nodes[k];
270 : :
271 : : /*
272 : : * Fill in remaining details, using either the nested join unroller,
273 : : * or by deriving them from the plan and elided nodes.
274 : : */
275 [ + + ]: 30253 : if (join_unroller->inner_unrollers[k] != NULL)
276 : 1057 : ujoin->inner[i].unrolled_join =
277 : 1057 : pgpa_build_unrolled_join(walker,
278 : 1057 : join_unroller->inner_unrollers[k]);
279 : : else
280 : 29196 : ujoin->inner[i].scan =
281 : 29196 : pgpa_build_scan(walker, ujoin->inner[i].plan,
282 : 29196 : ujoin->inner[i].elided_node,
283 : 29196 : join_unroller->inner_beneath_any_gather[k],
284 : : true);
285 : : }
286 : :
287 : 23027 : return ujoin;
288 : : }
289 : :
290 : : /*
291 : : * Free memory allocated for pgpa_join_unroller.
292 : : */
293 : : void
294 : 21970 : pgpa_destroy_join_unroller(pgpa_join_unroller *join_unroller)
295 : : {
296 : 21970 : pfree(join_unroller->strategy);
297 : 21970 : pfree(join_unroller->inner_subplans);
298 : 21970 : pfree(join_unroller->inner_elided_nodes);
299 : 21970 : pfree(join_unroller->inner_unrollers);
300 : 21970 : pfree(join_unroller->inner_beneath_any_gather);
301 : 21970 : pfree(join_unroller);
302 : 21970 : }
303 : :
304 : : /*
305 : : * Identify the join strategy used by a join and the "real" inner and outer
306 : : * plans.
307 : : *
308 : : * For example, a Hash Join always has a Hash node on the inner side, but
309 : : * for all intents and purposes the real inner input is the Hash node's child,
310 : : * not the Hash node itself.
311 : : *
312 : : * Likewise, a Merge Join may have Sort node on the inner or outer side; if
313 : : * it does, the real input to the join is the Sort node's child, not the
314 : : * Sort node itself.
315 : : *
316 : : * In addition, with a Merge Join or a Nested Loop, the join planning code
317 : : * may add additional nodes such as Materialize or Memoize. We regard these
318 : : * as an aspect of the join strategy. As in the previous cases, the true input
319 : : * to the join is the underlying node.
320 : : *
321 : : * However, if any involved child node previously had a now-elided node stacked
322 : : * on top, then we can't "look through" that node -- indeed, what's going to be
323 : : * relevant for our purposes is the ElidedNode on top of that plan node, rather
324 : : * than the plan node itself.
325 : : *
326 : : * If there are multiple elided nodes, we want that one that would have been
327 : : * uppermost in the plan tree prior to setrefs processing; we expect to find
328 : : * that one last in the list of elided nodes.
329 : : *
330 : : * On return *realouter and *realinner will have been set to the real inner
331 : : * and real outer plans that we identified, and *elidedrealouter and
332 : : * *elidedrealinner to the last of any corresponding elided nodes.
333 : : * Additionally, *found_any_outer_gather and *found_any_inner_gather will
334 : : * be set to true if we looked through a Gather or Gather Merge node on
335 : : * that side of the join, and false otherwise.
336 : : */
337 : : static pgpa_join_strategy
338 : 30253 : pgpa_decompose_join(pgpa_plan_walker_context *walker, Plan *plan,
339 : : Plan **realouter, Plan **realinner,
340 : : ElidedNode **elidedrealouter, ElidedNode **elidedrealinner,
341 : : bool *found_any_outer_gather, bool *found_any_inner_gather)
342 : : {
343 : 30253 : PlannedStmt *pstmt = walker->pstmt;
344 : 30253 : JoinType jointype = ((Join *) plan)->jointype;
345 : 30253 : Plan *outerplan = plan->lefttree;
346 : 30253 : Plan *innerplan = plan->righttree;
347 : : ElidedNode *elidedouter;
348 : : ElidedNode *elidedinner;
349 : : pgpa_join_strategy strategy;
350 : : bool uniqueouter;
351 : : bool uniqueinner;
352 : :
353 : 30253 : elidedouter = pgpa_last_elided_node(pstmt, outerplan);
354 : 30253 : elidedinner = pgpa_last_elided_node(pstmt, innerplan);
355 : 30253 : *found_any_outer_gather = false;
356 : 30253 : *found_any_inner_gather = false;
357 : :
358 [ + + + - ]: 30253 : switch (nodeTag(plan))
359 : : {
360 : 1158 : case T_MergeJoin:
361 : :
362 : : /*
363 : : * The planner may have chosen to place a Material node on the
364 : : * inner side of the MergeJoin; if this is present, we record it
365 : : * as part of the join strategy. (However, scan-level Materialize
366 : : * nodes are an exception.)
367 : : */
368 [ + - + + ]: 1158 : if (elidedinner == NULL && IsA(innerplan, Material) &&
369 [ + - ]: 53 : !pgpa_is_scan_level_materialize(innerplan))
370 : : {
371 : 53 : elidedinner = pgpa_descend_node(pstmt, &innerplan);
372 : 53 : strategy = JSTRAT_MERGE_JOIN_MATERIALIZE;
373 : : }
374 : : else
375 : 1105 : strategy = JSTRAT_MERGE_JOIN_PLAIN;
376 : :
377 : : /*
378 : : * For a MergeJoin, either the outer or the inner subplan, or
379 : : * both, may have needed to be sorted; we must disregard any Sort
380 : : * or IncrementalSort node to find the real inner or outer
381 : : * subplan.
382 : : */
383 [ + + + + ]: 1158 : if (elidedouter == NULL && is_sorting_plan(outerplan))
384 : 817 : elidedouter = pgpa_descend_node(pstmt, &outerplan);
385 [ + + + + ]: 1158 : if (elidedinner == NULL && is_sorting_plan(innerplan))
386 : 1029 : elidedinner = pgpa_descend_node(pstmt, &innerplan);
387 : 1158 : break;
388 : :
389 : 19415 : case T_NestLoop:
390 : :
391 : : /*
392 : : * The planner may have chosen to place a Material or Memoize node
393 : : * on the inner side of the NestLoop; if this is present, we
394 : : * record it as part of the join strategy. (However, scan-level
395 : : * Materialize nodes are an exception.)
396 : : */
397 [ + + + + ]: 19415 : if (elidedinner == NULL && IsA(innerplan, Material) &&
398 [ + + ]: 1009 : !pgpa_is_scan_level_materialize(innerplan))
399 : : {
400 : 1008 : elidedinner = pgpa_descend_node(pstmt, &innerplan);
401 : 1008 : strategy = JSTRAT_NESTED_LOOP_MATERIALIZE;
402 : : }
403 [ + + + + ]: 18407 : else if (elidedinner == NULL && IsA(innerplan, Memoize))
404 : : {
405 : 418 : elidedinner = pgpa_descend_node(pstmt, &innerplan);
406 : 418 : strategy = JSTRAT_NESTED_LOOP_MEMOIZE;
407 : : }
408 : : else
409 : 17989 : strategy = JSTRAT_NESTED_LOOP_PLAIN;
410 : 19415 : break;
411 : :
412 : 9680 : case T_HashJoin:
413 : :
414 : : /*
415 : : * The inner subplan of a HashJoin is always a Hash node; the real
416 : : * inner subplan is the Hash node's child.
417 : : */
418 : : Assert(IsA(innerplan, Hash));
419 : : Assert(elidedinner == NULL);
420 : 9680 : elidedinner = pgpa_descend_node(pstmt, &innerplan);
421 : 9680 : strategy = JSTRAT_HASH_JOIN;
422 : 9680 : break;
423 : :
424 : 0 : default:
425 [ # # ]: 0 : elog(ERROR, "unrecognized node type: %d", (int) nodeTag(plan));
426 : : }
427 : :
428 : : /*
429 : : * The planner may have decided to implement a semijoin by first making
430 : : * the nullable side of the plan unique, and then performing a normal join
431 : : * against the result. Therefore, we might need to descend through a
432 : : * unique node on either side of the plan.
433 : : */
434 : 30253 : uniqueouter = pgpa_descend_any_unique(pstmt, &outerplan, &elidedouter);
435 : 30253 : uniqueinner = pgpa_descend_any_unique(pstmt, &innerplan, &elidedinner);
436 : :
437 : : /*
438 : : * Can we see a Result node here, to project above a Gather? So far I've
439 : : * found no example that behaves that way; rather, the Gather or Gather
440 : : * Merge is made to project. Hence, don't test is_result_node_with_child()
441 : : * at this point.
442 : : */
443 : :
444 : : /*
445 : : * The planner may have decided to parallelize part of the join tree, so
446 : : * we could find a Gather or Gather Merge node here. Note that, if
447 : : * present, this will appear below nodes we considered as part of the join
448 : : * strategy, but we could find another uniqueness-enforcing node below the
449 : : * Gather or Gather Merge, if present.
450 : : */
451 [ + + ]: 30253 : if (elidedouter == NULL)
452 : : {
453 : 30078 : elidedouter = pgpa_descend_any_gather(pstmt, &outerplan,
454 : : found_any_outer_gather);
455 [ + + + + ]: 30106 : if (*found_any_outer_gather &&
456 : 28 : pgpa_descend_any_unique(pstmt, &outerplan, &elidedouter))
457 : 2 : uniqueouter = true;
458 : : }
459 [ + + ]: 30253 : if (elidedinner == NULL)
460 : : {
461 : 29894 : elidedinner = pgpa_descend_any_gather(pstmt, &innerplan,
462 : : found_any_inner_gather);
463 [ + + - + ]: 29935 : if (*found_any_inner_gather &&
464 : 41 : pgpa_descend_any_unique(pstmt, &innerplan, &elidedinner))
465 : 0 : uniqueinner = true;
466 : : }
467 : :
468 : : /*
469 : : * It's possible that a Result node has been inserted either to project a
470 : : * target list or to implement a one-time filter. If so, we can descend
471 : : * through it. Note that a Result node without a child would be a
472 : : * degenerate scan or join, and not something we could descend through.
473 : : */
474 [ + + + + ]: 30253 : if (elidedouter == NULL && is_result_node_with_child(outerplan))
475 : 6 : elidedouter = pgpa_descend_node(pstmt, &outerplan);
476 [ + + + + ]: 30253 : if (elidedinner == NULL && is_result_node_with_child(innerplan))
477 : 6 : elidedinner = pgpa_descend_node(pstmt, &innerplan);
478 : :
479 : : /*
480 : : * If this is a semijoin that was converted to an inner join by making one
481 : : * side or the other unique, make a note that the inner or outer subplan,
482 : : * as appropriate, should be treated as a query plan feature when the main
483 : : * tree traversal reaches it.
484 : : *
485 : : * Conversely, if the planner could have made one side of the join unique
486 : : * and thereby converted it to an inner join, and chose not to do so, that
487 : : * is also worth noting.
488 : : *
489 : : * NB: This code could appear slightly higher up in this function, but
490 : : * none of the nodes through which we just descended should have
491 : : * associated RTIs.
492 : : *
493 : : * NB: This seems like a somewhat hacky way of passing information up to
494 : : * the main tree walk, but I don't currently have a better idea.
495 : : */
496 [ + + ]: 30253 : if (uniqueouter)
497 : 72 : pgpa_add_future_feature(walker, PGPAQF_SEMIJOIN_UNIQUE, outerplan);
498 [ + + ]: 30181 : else if (jointype == JOIN_RIGHT_SEMI)
499 : 83 : pgpa_add_future_feature(walker, PGPAQF_SEMIJOIN_NON_UNIQUE, outerplan);
500 [ + + ]: 30253 : if (uniqueinner)
501 : 82 : pgpa_add_future_feature(walker, PGPAQF_SEMIJOIN_UNIQUE, innerplan);
502 [ + + ]: 30171 : else if (jointype == JOIN_SEMI)
503 : 1218 : pgpa_add_future_feature(walker, PGPAQF_SEMIJOIN_NON_UNIQUE, innerplan);
504 : :
505 : : /* Set output parameters. */
506 : 30253 : *realouter = outerplan;
507 : 30253 : *realinner = innerplan;
508 : 30253 : *elidedrealouter = elidedouter;
509 : 30253 : *elidedrealinner = elidedinner;
510 : 30253 : return strategy;
511 : : }
512 : :
513 : : /*
514 : : * Descend through a Plan node in a join tree that the caller has determined
515 : : * to be irrelevant.
516 : : *
517 : : * Updates *plan, and returns the last of any elided nodes pertaining to the
518 : : * new plan node.
519 : : */
520 : : static ElidedNode *
521 : 13529 : pgpa_descend_node(PlannedStmt *pstmt, Plan **plan)
522 : : {
523 : 13529 : *plan = (*plan)->lefttree;
524 : 13529 : return pgpa_last_elided_node(pstmt, *plan);
525 : : }
526 : :
527 : : /*
528 : : * Descend through a Gather or Gather Merge node, if present, and any Sort
529 : : * or IncrementalSort node occurring under a Gather Merge.
530 : : *
531 : : * Caller should have verified that there is no ElidedNode pertaining to
532 : : * the initial value of *plan.
533 : : *
534 : : * Updates *plan, and returns the last of any elided nodes pertaining to the
535 : : * new plan node. Sets *found_any_gather = true if either Gather or
536 : : * Gather Merge was found, and otherwise leaves it unchanged.
537 : : */
538 : : static ElidedNode *
539 : 59972 : pgpa_descend_any_gather(PlannedStmt *pstmt, Plan **plan,
540 : : bool *found_any_gather)
541 : : {
542 [ + + ]: 59972 : if (IsA(*plan, Gather))
543 : : {
544 : 52 : *found_any_gather = true;
545 : 52 : return pgpa_descend_node(pstmt, plan);
546 : : }
547 : :
548 [ + + ]: 59920 : if (IsA(*plan, GatherMerge))
549 : : {
550 : 17 : ElidedNode *elided = pgpa_descend_node(pstmt, plan);
551 : :
552 [ + - + - ]: 17 : if (elided == NULL && is_sorting_plan(*plan))
553 : 17 : elided = pgpa_descend_node(pstmt, plan);
554 : :
555 : 17 : *found_any_gather = true;
556 : 17 : return elided;
557 : : }
558 : :
559 : 59903 : return NULL;
560 : : }
561 : :
562 : : /*
563 : : * If *plan is an Agg or Unique node, we want to descend through it, unless
564 : : * it has a corresponding elided node. If its immediate child is a Sort or
565 : : * IncrementalSort, we also want to descend through that, unless it has a
566 : : * corresponding elided node.
567 : : *
568 : : * On entry, *elided_node must be the last of any elided nodes corresponding
569 : : * to *plan; on exit, this will still be true, but *plan may have been updated.
570 : : *
571 : : * The reason we don't want to descend through elided nodes is that a single
572 : : * join tree can't cross through any sort of elided node: subqueries are
573 : : * planned separately, and planning inside an Append or MergeAppend is
574 : : * separate from planning outside of it.
575 : : *
576 : : * The return value is true if we descend through a node that we believe is
577 : : * making one side of a semijoin unique, and otherwise false.
578 : : */
579 : : static bool
580 : 60575 : pgpa_descend_any_unique(PlannedStmt *pstmt, Plan **plan,
581 : : ElidedNode **elided_node)
582 : : {
583 : 60575 : bool descend = false;
584 : 60575 : bool sjunique = false;
585 : :
586 [ + + ]: 60575 : if (*elided_node != NULL)
587 : 522 : return sjunique;
588 : :
589 [ + + ]: 60053 : if (IsA(*plan, Unique))
590 : : {
591 : 61 : descend = true;
592 : 61 : sjunique = true;
593 : : }
594 [ + + ]: 59992 : else if (IsA(*plan, Agg))
595 : : {
596 : : /*
597 : : * If this is a simple Agg node, then assume it's here to implement
598 : : * semijoin uniqueness. Otherwise, assume it's completing an eager
599 : : * aggregation or partitionwise aggregation operation that began at a
600 : : * higher level of the plan tree.
601 : : *
602 : : * (Note that when we're using an Agg node for uniqueness, there's no
603 : : * need for any case other than AGGSPLIT_SIMPLE, because there's no
604 : : * aggregated column being computed. However, the fact that
605 : : * AGGSPLIT_SIMPLE is in use doesn't prove that this Agg is here for
606 : : * the semijoin uniqueness. Maybe we should adjust an Agg node to
607 : : * carry a "purpose" field so that code like this can be more certain
608 : : * of its analysis.)
609 : : */
610 : 305 : descend = true;
611 : 305 : sjunique = (((Agg *) *plan)->aggsplit == AGGSPLIT_SIMPLE);
612 : : }
613 : :
614 [ + + ]: 60053 : if (descend)
615 : : {
616 : 366 : *elided_node = pgpa_descend_node(pstmt, plan);
617 : :
618 [ + + + + ]: 366 : if (*elided_node == NULL && is_sorting_plan(*plan))
619 : 60 : *elided_node = pgpa_descend_node(pstmt, plan);
620 : : }
621 : :
622 : 60053 : return sjunique;
623 : : }
624 : :
625 : : /*
626 : : * Is this a Result node that has a child?
627 : : */
628 : : static bool
629 : 90227 : is_result_node_with_child(Plan *plan)
630 : : {
631 [ + + + + ]: 90227 : return IsA(plan, Result) && plan->lefttree != NULL;
632 : : }
633 : :
634 : : /*
635 : : * Is this a Plan node whose purpose is to put the data in a certain order?
636 : : */
637 : : static bool
638 : 33155 : is_sorting_plan(Plan *plan)
639 : : {
640 [ + + + + ]: 33155 : return IsA(plan, Sort) || IsA(plan, IncrementalSort);
641 : : }
|
