Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * pgpa_walker.c
4 : : * Main entrypoints for analyzing a plan to generate an advice string
5 : : *
6 : : * Copyright (c) 2016-2026, PostgreSQL Global Development Group
7 : : *
8 : : * contrib/pg_plan_advice/pgpa_walker.c
9 : : *
10 : : *-------------------------------------------------------------------------
11 : : */
12 : : #include "postgres.h"
13 : :
14 : : #include "pgpa_join.h"
15 : : #include "pgpa_planner.h"
16 : : #include "pgpa_scan.h"
17 : : #include "pgpa_walker.h"
18 : :
19 : : #include "access/tsmapi.h"
20 : : #include "miscadmin.h"
21 : : #include "nodes/plannodes.h"
22 : : #include "parser/parsetree.h"
23 : : #include "utils/lsyscache.h"
24 : :
25 : : static void pgpa_walk_recursively(pgpa_plan_walker_context *walker, Plan *plan,
26 : : bool within_setop,
27 : : bool within_join_problem,
28 : : pgpa_join_unroller *join_unroller,
29 : : List *active_query_features,
30 : : bool beneath_any_gather);
31 : : static Bitmapset *pgpa_process_unrolled_join(pgpa_plan_walker_context *walker,
32 : : pgpa_unrolled_join *ujoin);
33 : :
34 : : static pgpa_query_feature *pgpa_add_feature(pgpa_plan_walker_context *walker,
35 : : pgpa_qf_type type,
36 : : Plan *plan);
37 : :
38 : : static void pgpa_qf_add_rti(List *active_query_features, Index rti);
39 : : static void pgpa_qf_add_rtis(List *active_query_features, Bitmapset *relids);
40 : : static void pgpa_qf_add_plan_rtis(List *active_query_features, Plan *plan,
41 : : List *rtable);
42 : :
43 : : static unsigned pgpa_walker_join_order_matches(pgpa_unrolled_join *ujoin,
44 : : Index rtable_length,
45 : : pgpa_identifier *rt_identifiers,
46 : : pgpa_advice_target *target);
47 : : static bool pgpa_walker_join_order_matches_members(pgpa_unrolled_join *ujoin,
48 : : unsigned *match_position,
49 : : Index rtable_length,
50 : : pgpa_identifier *rt_identifiers,
51 : : pgpa_advice_target *target);
52 : : static Bitmapset *pgpa_walker_join_member_relids(pgpa_join_member *member);
53 : : static pgpa_scan *pgpa_walker_find_scan(pgpa_plan_walker_context *walker,
54 : : pgpa_scan_strategy strategy,
55 : : Bitmapset *relids);
56 : : static bool pgpa_walker_index_target_matches_plan(pgpa_index_target *itarget,
57 : : Plan *plan);
58 : : static bool pgpa_walker_contains_feature(pgpa_plan_walker_context *walker,
59 : : pgpa_qf_type type,
60 : : Bitmapset *relids);
61 : : static bool pgpa_walker_contains_join(pgpa_plan_walker_context *walker,
62 : : pgpa_join_strategy strategy,
63 : : Bitmapset *relids);
64 : : static bool pgpa_walker_contains_no_gather(pgpa_plan_walker_context *walker,
65 : : Bitmapset *relids);
66 : : static void pgpa_classify_alternative_subplans(pgpa_plan_walker_context *walker,
67 : : List *proots,
68 : : List **chosen_proots,
69 : : List **discarded_proots);
70 : :
71 : : /*
72 : : * Top-level entrypoint for the plan tree walk.
73 : : *
74 : : * Populates walker based on a traversal of the Plan trees in pstmt.
75 : : *
76 : : * proots is the list of pgpa_planner_info objects that were generated
77 : : * during planning.
78 : : */
79 : : void
238 rhaas@postgresql.org 80 :CBC 87304 : pgpa_plan_walker(pgpa_plan_walker_context *walker, PlannedStmt *pstmt,
81 : : List *proots)
82 : : {
83 : : ListCell *lc;
84 : 87304 : List *sj_unique_rtis = NULL;
85 : 87304 : List *sj_nonunique_qfs = NULL;
86 : : List *chosen_proots;
87 : : List *discarded_proots;
88 : :
89 : : /* Initialization. */
90 : 87304 : memset(walker, 0, sizeof(pgpa_plan_walker_context));
91 : 87304 : walker->pstmt = pstmt;
92 : :
93 : : /* Walk the main plan tree. */
7 94 : 87304 : pgpa_walk_recursively(walker, pstmt->planTree, false, false, NULL, NIL,
95 : : false);
96 : :
97 : : /* Main plan tree walk won't reach subplans, so walk those. */
238 98 [ + + + + : 96536 : foreach(lc, pstmt->subplans)
+ + ]
99 : : {
100 : 9232 : Plan *plan = lfirst(lc);
101 : :
102 [ + + ]: 9232 : if (plan != NULL)
7 103 : 8839 : pgpa_walk_recursively(walker, plan, false, false, NULL, NIL,
104 : : false);
105 : : }
106 : :
107 : : /* Adjust RTIs from sj_unique_rels for the flattened range table. */
224 108 [ + - + + : 279216 : foreach_ptr(pgpa_planner_info, proot, proots)
+ + ]
109 : : {
110 : : /* If there are no sj_unique_rels for this proot, we can skip it. */
111 [ + + ]: 104608 : if (proot->sj_unique_rels == NIL)
112 : 103321 : continue;
113 : :
114 : : /* If this is a subplan, find the range table offset. */
115 [ - + ]: 1287 : if (!proot->has_rtoffset)
224 rhaas@postgresql.org 116 [ # # ]:UBC 0 : elog(ERROR, "no rtoffset for plan %s", proot->plan_name);
117 : :
118 : : /* Offset each relid set by the proot's rtoffset. */
224 rhaas@postgresql.org 119 [ + - + + :CBC 4021 : foreach_node(Bitmapset, relids, proot->sj_unique_rels)
+ + ]
120 : : {
121 : 1447 : int rtindex = -1;
122 : 1447 : Bitmapset *flat_relids = NULL;
123 : :
124 [ + + ]: 2980 : while ((rtindex = bms_next_member(relids, rtindex)) >= 0)
125 : 1533 : flat_relids = bms_add_member(flat_relids,
126 : 1533 : rtindex + proot->rtoffset);
127 : :
128 : 1447 : sj_unique_rtis = lappend(sj_unique_rtis, flat_relids);
129 : : }
130 : : }
131 : :
132 : : /*
133 : : * Remove any non-unique semijoin query features for which making the rel
134 : : * unique wasn't considered.
135 : : */
238 136 [ + + + + : 175901 : foreach_ptr(pgpa_query_feature, qf,
+ + ]
137 : : walker->query_features[PGPAQF_SEMIJOIN_NON_UNIQUE])
138 : : {
139 [ + + ]: 1293 : if (list_member(sj_unique_rtis, qf->relids))
140 : 1239 : sj_nonunique_qfs = lappend(sj_nonunique_qfs, qf);
141 : : }
142 : 87304 : walker->query_features[PGPAQF_SEMIJOIN_NON_UNIQUE] = sj_nonunique_qfs;
143 : :
144 : : /*
145 : : * If we find any cases where analysis of the Plan tree shows that the
146 : : * semijoin was made unique but this possibility was never observed to be
147 : : * considered during planning, then we have a bug somewhere.
148 : : */
149 [ + + + + : 174768 : foreach_ptr(pgpa_query_feature, qf,
+ + ]
150 : : walker->query_features[PGPAQF_SEMIJOIN_UNIQUE])
151 : : {
152 [ - + ]: 160 : if (!list_member(sj_unique_rtis, qf->relids))
153 : : {
154 : : StringInfoData buf;
155 : :
238 rhaas@postgresql.org 156 :UBC 0 : initStringInfo(&buf);
157 : 0 : outBitmapset(&buf, qf->relids);
158 [ # # ]: 0 : elog(ERROR,
159 : : "unique semijoin found for relids %s but not observed during planning",
160 : : buf.data);
161 : : }
162 : : }
163 : :
164 : : /*
165 : : * It's possible for a Gather or Gather Merge query feature to find no
166 : : * RTIs when partitionwise aggregation is in use. We shouldn't emit
167 : : * something like GATHER_MERGE(()), so instead emit nothing. This means
168 : : * that we won't advise either GATHER or GATHER_MERGE or NO_GATHER in such
169 : : * cases, which might be something we want to improve in the future.
170 : : *
171 : : * The same thing happens when a Gather or Gather Merge node sits atop a
172 : : * set operation that was not flattened, because we decline to add RTIs
173 : : * from unflattened set operations to query features. In that case,
174 : : * there's no planner hook that would allow us to enforce the advice.
175 : : *
176 : : * (Should the Partial Aggregates in such a case be created in an
177 : : * UPPERREL_GROUP_AGG with a non-empty relid set? Right now that doesn't
178 : : * happen, but it seems like it would make life easier for us if it did.)
179 : : */
238 rhaas@postgresql.org 180 [ + + ]:CBC 436520 : for (int t = 0; t < NUM_PGPA_QF_TYPES; ++t)
181 : : {
182 : 349216 : List *query_features = NIL;
183 : :
184 [ + + + + : 700313 : foreach_ptr(pgpa_query_feature, qf, walker->query_features[t])
+ + ]
185 : : {
186 [ + + ]: 1881 : if (qf->relids != NULL)
187 : 1858 : query_features = lappend(query_features, qf);
188 : : else
189 [ + + - + ]: 23 : Assert(t == PGPAQF_GATHER || t == PGPAQF_GATHER_MERGE);
190 : : }
191 : :
192 : 349216 : walker->query_features[t] = query_features;
193 : : }
194 : :
195 : : /* Classify alternative subplans. */
224 196 : 87304 : pgpa_classify_alternative_subplans(walker, proots,
197 : : &chosen_proots, &discarded_proots);
198 : :
199 : : /*
200 : : * Figure out which of the discarded alternatives have a non-discarded
201 : : * alternative. Those are the ones for which we want to emit DO_NOT_SCAN
202 : : * advice. (If every alternative was discarded, then there's no point.)
203 : : */
204 [ + + + + : 175341 : foreach_ptr(pgpa_planner_info, discarded_proot, discarded_proots)
+ + ]
205 : : {
206 : 733 : bool some_alternative_chosen = false;
207 : :
208 [ + - + - : 1664 : foreach_ptr(pgpa_planner_info, chosen_proot, chosen_proots)
+ + ]
209 : : {
210 [ + + ]: 931 : if (strings_equal_or_both_null(discarded_proot->alternative_plan_name,
211 : 931 : chosen_proot->alternative_plan_name))
212 : : {
213 : 733 : some_alternative_chosen = true;
214 : 733 : break;
215 : : }
216 : : }
217 : :
218 [ + - ]: 733 : if (some_alternative_chosen)
219 : : {
220 [ + + ]: 6597 : for (int rti = 1; rti <= discarded_proot->rid_array_size; rti++)
221 : : {
222 : 5864 : pgpa_identifier *rid = &discarded_proot->rid_array[rti - 1];
223 : :
224 [ + + ]: 5864 : if (rid->alias_name != NULL)
225 : 863 : walker->do_not_scan_identifiers =
226 : 863 : lappend(walker->do_not_scan_identifiers, rid);
227 : : }
228 : : }
229 : : }
238 230 : 87304 : }
231 : :
232 : : /*
233 : : * Main workhorse for the plan tree walk.
234 : : *
235 : : * If within_setop is true, the portion of the plan tree in which this node
236 : : * occurs was generated while planning an unflattened set operation.
237 : : *
238 : : * If within_join_problem is true, we encountered a join at some higher level
239 : : * of the tree walk and haven't yet descended out of the portion of the plan
240 : : * tree that is part of that same join problem. We're no longer in the same
241 : : * join problem if (1) we cross into a different subquery or (2) we descend
242 : : * through an Append or MergeAppend node, below which any further joins would
243 : : * be partitionwise joins planned separately from the outer join problem.
244 : : *
245 : : * If join_unroller != NULL, the join unroller code expects us to find a join
246 : : * that should be unrolled into that object. This implies that we're within a
247 : : * join problem, but the reverse is not true: when we've traversed all the
248 : : * joins but are still looking for the scan that is the leaf of the join tree,
249 : : * join_unroller will be NULL but within_join_problem will be true.
250 : : *
251 : : * Each element of active_query_features corresponds to some item of advice
252 : : * that needs to enumerate all the relations it affects. We add RTIs we find
253 : : * during tree traversal to each of these query features.
254 : : *
255 : : * If beneath_any_gather == true, some higher level of the tree traversal found
256 : : * a Gather or Gather Merge node, except that we reset it for the non-partial
257 : : * children of a Parallel Append, for reasons explained in the comments below.
258 : : */
259 : : static void
260 : 250412 : pgpa_walk_recursively(pgpa_plan_walker_context *walker, Plan *plan,
261 : : bool within_setop,
262 : : bool within_join_problem,
263 : : pgpa_join_unroller *join_unroller,
264 : : List *active_query_features,
265 : : bool beneath_any_gather)
266 : : {
267 : 250412 : pgpa_join_unroller *outer_join_unroller = NULL;
268 : 250412 : pgpa_join_unroller *inner_join_unroller = NULL;
269 : 250412 : bool join_unroller_toplevel = false;
270 : : ListCell *lc;
271 : 250412 : List *extraplans = NIL;
8 272 : 250412 : int first_partial_plan = 0;
273 : :
238 274 [ + + - + ]: 250412 : Assert(within_join_problem || join_unroller == NULL);
275 : :
276 : : /*
277 : : * Check the future_query_features list to see whether this was previously
278 : : * identified as a plan node that needs to be treated as a query feature.
279 : : * We must do this before handling elided nodes, because if there's an
280 : : * elided node associated with a future query feature, the RTIs associated
281 : : * with the elided node should be the only ones attributed to the query
282 : : * feature.
283 : : */
284 [ + + + + : 502976 : foreach_ptr(pgpa_query_feature, qf, walker->future_query_features)
+ + ]
285 : : {
286 [ + + ]: 3605 : if (qf->plan == plan)
287 : : {
288 : 1453 : active_query_features = list_copy(active_query_features);
289 : 1453 : active_query_features = lappend(active_query_features, qf);
290 : 1453 : walker->future_query_features =
291 : 1453 : list_delete_ptr(walker->future_query_features, qf);
292 : 1453 : break;
293 : : }
294 : : }
295 : :
296 : : /*
297 : : * Process elided nodes that pertain to this Plan node. In the pstmt's
298 : : * list, the logically uppermost elided node appears last, so we walk the
299 : : * list in reverse order.
300 : : */
7 301 [ + + ]: 305525 : for (int n = list_length(walker->pstmt->elidedNodes) - 1; n >= 0; --n)
302 : : {
303 : 55113 : ElidedNode *elided_node = list_nth(walker->pstmt->elidedNodes, n);
304 : :
305 : : /* Ignore elided nodes that do not pertain to this plan node. */
306 [ + + ]: 55113 : if (elided_node->plan_node_id != plan->plan_node_id)
307 : 49510 : continue;
308 : :
309 : : /* Did an unflattened set operation produce this ElidedNode? */
310 [ + + ]: 5603 : if (!within_setop)
311 : 3291 : within_setop = pgpa_is_setop_parent(plan, elided_node,
312 : 3291 : walker->pstmt->rtable);
313 : :
314 : : /*
315 : : * Collect RTIs for any currently-active query features, unless we're
316 : : * within a set operation. There's no hook to enforce any advice
317 : : * pertaining to set operations, so we shouldn't generate any.
318 : : */
319 [ + + ]: 5603 : if (!within_setop)
320 : 3275 : pgpa_qf_add_rtis(active_query_features,
321 : : pgpa_filter_out_join_relids(elided_node->relids,
322 : 3275 : walker->pstmt->rtable));
323 : :
324 : : /* Sanity check. */
325 [ + + - + ]: 5603 : if (within_setop && within_join_problem)
7 rhaas@postgresql.org 326 [ # # ]:UBC 0 : elog(ERROR, "set operations cannot be part of a join problem");
327 : :
328 : : /*
329 : : * If we're within a join problem, the join unroller is responsible
330 : : * for building any required scan. If not, we do it here.
331 : : */
7 rhaas@postgresql.org 332 [ + + ]:CBC 5603 : if (!within_join_problem)
238 333 : 5041 : (void) pgpa_build_scan(walker, plan, elided_node,
7 334 [ + + + + ]: 5041 : !beneath_any_gather && !within_setop,
335 : 5041 : false);
336 : :
337 : : /* Set operations can't span a subquery boundary. */
338 [ + + ]: 5603 : if (elided_node->elided_type == T_SubqueryScan)
339 : 4437 : within_setop = false;
340 : :
341 : : /*
342 : : * Everything below an elided node is not part of the same join
343 : : * problem.
344 : : */
238 345 : 5603 : within_join_problem = false;
346 : 5603 : join_unroller = NULL;
347 : :
348 : : /* Elided nodes act as barriers to query features. */
7 349 : 5603 : active_query_features = NIL;
350 : : }
351 : :
352 : : /*
353 : : * If this is a Gather or Gather Merge node, directly add it to the list
354 : : * of currently-active query features. We must do this after handling
355 : : * elided nodes, since the Gather or Gather Merge node occurs logically
356 : : * beneath any associated elided nodes.
357 : : *
358 : : * Exception: We disregard any single_copy Gather nodes. These are created
359 : : * by debug_parallel_query, and having them affect the plan advice is
360 : : * counterproductive, as the result will be to advise the use of a real
361 : : * Gather node, rather than a single copy one.
362 : : */
238 363 [ + + + + ]: 250412 : if (IsA(plan, Gather) && !((Gather *) plan)->single_copy)
364 : : {
365 : : active_query_features =
366 : 354 : lappend(list_copy(active_query_features),
367 : 354 : pgpa_add_feature(walker, PGPAQF_GATHER, plan));
368 : 354 : beneath_any_gather = true;
369 : : }
370 [ + + ]: 250058 : else if (IsA(plan, GatherMerge))
371 : : {
372 : : active_query_features =
373 : 128 : lappend(list_copy(active_query_features),
374 : 128 : pgpa_add_feature(walker, PGPAQF_GATHER_MERGE, plan));
375 : 128 : beneath_any_gather = true;
376 : : }
377 : :
378 : : /* Did an unflattened set operation produce this Plan node? */
7 379 [ + + ]: 250412 : if (!within_setop)
380 : 248178 : within_setop = pgpa_is_setop_parent(plan, NULL, walker->pstmt->rtable);
381 : :
382 : : /* Sanity check. */
383 [ + + - + ]: 250412 : if (within_setop && within_join_problem)
7 rhaas@postgresql.org 384 [ # # ]:UBC 0 : elog(ERROR, "set operations cannot be part of a join problem");
385 : :
386 : : /*
387 : : * If we're within a join problem, the join unroller is responsible for
388 : : * building any required scan for this node. If not, we do it here.
389 : : */
238 rhaas@postgresql.org 390 [ + + ]:CBC 250412 : if (!within_join_problem)
7 391 : 176484 : (void) pgpa_build_scan(walker, plan, NULL,
392 [ + + + + ]: 176484 : !beneath_any_gather && !within_setop,
393 : 176484 : false);
394 : :
395 : : /*
396 : : * If this join needs to be unrolled but there's no join unroller already
397 : : * available, create one.
398 : : */
238 399 [ + + + + ]: 250412 : if (join_unroller == NULL && pgpa_is_join(plan))
400 : : {
401 : 22186 : join_unroller = pgpa_create_join_unroller();
402 : 22186 : join_unroller_toplevel = true;
403 : 22186 : within_join_problem = true;
404 : : }
405 : :
406 : : /*
407 : : * If this join is to be unrolled, pgpa_unroll_join() will return the join
408 : : * unroller object that should be passed down when we recurse into the
409 : : * outer and inner sides of the plan.
410 : : */
411 [ + + ]: 250412 : if (join_unroller != NULL)
412 : 31290 : pgpa_unroll_join(walker, plan, beneath_any_gather, join_unroller,
413 : : &outer_join_unroller, &inner_join_unroller);
414 : :
415 : : /*
416 : : * Collect RTIs for any currently-active query features, unless we're
417 : : * within a set operation. There's no hook to enforce any advice
418 : : * pertaining to set operations, so we shouldn't generate any.
419 : : */
7 420 [ + + ]: 250412 : if (!within_setop)
421 : 246518 : pgpa_qf_add_plan_rtis(active_query_features, plan,
422 : 246518 : walker->pstmt->rtable);
423 : :
424 : : /*
425 : : * Recurse into the outer and inner subtrees.
426 : : *
427 : : * As an exception, if this is a ForeignScan, don't recurse. postgres_fdw
428 : : * sometimes stores an EPQ recheck plan in plan->lefttree, but that's
429 : : * going to mention the same set of relations as the ForeignScan itself,
430 : : * and we have no way to emit advice targeting the EPQ case vs. the
431 : : * non-EPQ case. Moreover, it's not entirely clear what other FDWs might
432 : : * do with the left and right subtrees. Maybe some better handling is
433 : : * needed here, but for now, we just punt.
434 : : */
238 435 [ + + ]: 250412 : if (!IsA(plan, ForeignScan))
436 : : {
437 [ + + ]: 250410 : if (plan->lefttree != NULL)
7 438 : 104777 : pgpa_walk_recursively(walker, plan->lefttree, within_setop,
439 : : within_join_problem, outer_join_unroller,
440 : : active_query_features, beneath_any_gather);
238 441 [ + + ]: 250410 : if (plan->righttree != NULL)
7 442 : 30751 : pgpa_walk_recursively(walker, plan->righttree, within_setop,
443 : : within_join_problem, inner_join_unroller,
444 : : active_query_features, beneath_any_gather);
445 : : }
446 : :
447 : : /*
448 : : * If we created a join unroller up above, then it's also our join to use
449 : : * it to build the final pgpa_unrolled_join, and to destroy the object.
450 : : */
238 451 [ + + ]: 250412 : if (join_unroller_toplevel)
452 : : {
453 : : pgpa_unrolled_join *ujoin;
454 : :
455 : 22186 : ujoin = pgpa_build_unrolled_join(walker, join_unroller);
456 : 22186 : walker->toplevel_unrolled_joins =
457 : 22186 : lappend(walker->toplevel_unrolled_joins, ujoin);
458 : 22186 : pgpa_destroy_join_unroller(join_unroller);
459 : 22186 : (void) pgpa_process_unrolled_join(walker, ujoin);
460 : : }
461 : :
462 : : /*
463 : : * Some plan types can have additional children. Nodes like Append that
464 : : * can have any number of children store them in a List; a SubqueryScan
465 : : * just has a field for a single additional Plan.
466 : : */
467 [ + + + + : 250412 : switch (nodeTag(plan))
+ - + ]
468 : : {
469 : 5133 : case T_Append:
470 : : {
471 : 5133 : Append *aplan = (Append *) plan;
472 : :
473 : 5133 : extraplans = aplan->appendplans;
8 474 [ + + ]: 5133 : if (aplan->plan.parallel_aware)
475 : 86 : first_partial_plan = aplan->first_partial_plan;
476 : : }
238 477 : 5133 : break;
478 : 190 : case T_MergeAppend:
479 : : {
480 : 190 : MergeAppend *maplan = (MergeAppend *) plan;
481 : :
482 : 190 : extraplans = maplan->mergeplans;
483 : : }
484 : 190 : break;
485 : 34 : case T_BitmapAnd:
486 : 34 : extraplans = ((BitmapAnd *) plan)->bitmapplans;
487 : 34 : break;
488 : 66 : case T_BitmapOr:
489 : 66 : extraplans = ((BitmapOr *) plan)->bitmapplans;
490 : 66 : break;
491 : 3308 : case T_SubqueryScan:
492 : :
493 : : /*
494 : : * We don't pass down active_query_features across here, because
495 : : * those are specific to a subquery level.
496 : : */
497 : 3308 : pgpa_walk_recursively(walker, ((SubqueryScan *) plan)->subplan,
498 : : false, false, NULL, NIL, beneath_any_gather);
499 : 3308 : break;
238 rhaas@postgresql.org 500 :UBC 0 : case T_CustomScan:
501 : 0 : extraplans = ((CustomScan *) plan)->custom_plans;
502 : 0 : break;
238 rhaas@postgresql.org 503 :CBC 241681 : default:
504 : 241681 : break;
505 : : }
506 : :
507 : : /* If we found a list of extra children, iterate over it. */
508 [ + + + + : 265845 : foreach(lc, extraplans)
+ + ]
509 : : {
510 : 15433 : Plan *subplan = lfirst(lc);
8 511 : 15433 : bool child_beneath_any_gather = beneath_any_gather;
512 : :
513 : : /*
514 : : * NO_GATHER() is defined to both suppress placement of Gather and
515 : : * Gather Merge nodes within a join problem, and also to suppress
516 : : * generation of partial paths. For a non-partial child of a Parallel
517 : : * Append, both behaviors are appropriate, even though such a plan
518 : : * node is necessarily beneath a Gather or Gather Merge node. Hence,
519 : : * we fudge.
520 : : */
521 [ + + ]: 15433 : if (foreach_current_index(lc) < first_partial_plan)
522 : 103 : child_beneath_any_gather = false;
523 : :
7 524 : 15433 : pgpa_walk_recursively(walker, subplan, within_setop, false, NULL,
525 : : NIL, child_beneath_any_gather);
526 : : }
238 527 : 250412 : }
528 : :
529 : : /*
530 : : * Perform final processing of a newly-constructed pgpa_unrolled_join. This
531 : : * only needs to be called for toplevel pgpa_unrolled_join objects, since it
532 : : * recurses to sub-joins as needed.
533 : : *
534 : : * Our goal is to add the set of inner relids to the relevant join_strategies
535 : : * list, and to do the same for any sub-joins. To that end, the return value
536 : : * is the set of relids found beneath the join, but it is expected that
537 : : * the toplevel caller will ignore this.
538 : : */
539 : : static Bitmapset *
540 : 23360 : pgpa_process_unrolled_join(pgpa_plan_walker_context *walker,
541 : : pgpa_unrolled_join *ujoin)
542 : : {
543 : 23360 : Bitmapset *all_relids = bms_copy(ujoin->outer.scan->relids);
544 : :
545 : : /* If this fails, we didn't unroll properly. */
546 [ - + ]: 23360 : Assert(ujoin->outer.unrolled_join == NULL);
547 : :
117 peter@eisentraut.org 548 [ + + ]:GNC 53695 : for (unsigned k = 0; k < ujoin->ninner; ++k)
549 : : {
238 rhaas@postgresql.org 550 :CBC 30335 : pgpa_join_member *member = &ujoin->inner[k];
551 : : Bitmapset *relids;
552 : :
553 [ + + ]: 30335 : if (member->unrolled_join != NULL)
554 : 1174 : relids = pgpa_process_unrolled_join(walker,
555 : : member->unrolled_join);
556 : : else
557 : : {
558 [ - + ]: 29161 : Assert(member->scan != NULL);
559 : 29161 : relids = member->scan->relids;
560 : : }
561 : 60670 : walker->join_strategies[ujoin->strategy[k]] =
562 : 30335 : lappend(walker->join_strategies[ujoin->strategy[k]], relids);
563 : 30335 : all_relids = bms_add_members(all_relids, relids);
564 : : }
565 : :
566 : 23360 : return all_relids;
567 : : }
568 : :
569 : : /*
570 : : * Arrange for the given plan node to be treated as a query feature when the
571 : : * tree walk reaches it.
572 : : *
573 : : * Make sure to only use this for nodes that the tree walk can't have reached
574 : : * yet!
575 : : */
576 : : void
577 : 1453 : pgpa_add_future_feature(pgpa_plan_walker_context *walker,
578 : : pgpa_qf_type type, Plan *plan)
579 : : {
580 : 1453 : pgpa_query_feature *qf = pgpa_add_feature(walker, type, plan);
581 : :
582 : 1453 : walker->future_query_features =
583 : 1453 : lappend(walker->future_query_features, qf);
584 : 1453 : }
585 : :
586 : : /*
587 : : * Return the last of any elided nodes associated with this plan node ID.
588 : : *
589 : : * The last elided node is the one that would have been uppermost in the plan
590 : : * tree had it not been removed during setrefs processing.
591 : : */
592 : : ElidedNode *
593 : 73694 : pgpa_last_elided_node(PlannedStmt *pstmt, Plan *plan)
594 : : {
595 : 73694 : ElidedNode *elided_node = NULL;
596 : :
597 [ + + + + : 171088 : foreach_node(ElidedNode, n, pstmt->elidedNodes)
+ + ]
598 : : {
599 [ + + ]: 23700 : if (n->plan_node_id == plan->plan_node_id)
600 : 564 : elided_node = n;
601 : : }
602 : :
603 : 73694 : return elided_node;
604 : : }
605 : :
606 : : /*
607 : : * Certain plan nodes can refer to a set of RTIs. Extract and return the set.
608 : : */
609 : : Bitmapset *
610 : 378214 : pgpa_relids(Plan *plan)
611 : : {
612 [ + + ]: 378214 : if (IsA(plan, Result))
613 : 83389 : return ((Result *) plan)->relids;
614 [ + + ]: 294825 : else if (IsA(plan, ForeignScan))
615 : 4 : return ((ForeignScan *) plan)->fs_relids;
2 616 [ - + ]: 294821 : else if (IsA(plan, CustomScan))
2 rhaas@postgresql.org 617 :UBC 0 : return ((CustomScan *) plan)->custom_relids;
238 rhaas@postgresql.org 618 [ + + ]:CBC 294821 : else if (IsA(plan, Append))
619 : 14085 : return ((Append *) plan)->apprelids;
620 [ + + ]: 280736 : else if (IsA(plan, MergeAppend))
621 : 552 : return ((MergeAppend *) plan)->apprelids;
622 : :
623 : 280184 : return NULL;
624 : : }
625 : :
626 : : /*
627 : : * Extract the scanned RTI from a plan node.
628 : : *
629 : : * Returns 0 if there isn't one.
630 : : */
631 : : Index
632 : 433218 : pgpa_scanrelid(Plan *plan)
633 : : {
634 [ + + ]: 433218 : switch (nodeTag(plan))
635 : : {
636 : 202022 : case T_SeqScan:
637 : : case T_SampleScan:
638 : : case T_BitmapHeapScan:
639 : : case T_TidScan:
640 : : case T_TidRangeScan:
641 : : case T_SubqueryScan:
642 : : case T_FunctionScan:
643 : : case T_TableFuncScan:
644 : : case T_ValuesScan:
645 : : case T_CteScan:
646 : : case T_NamedTuplestoreScan:
647 : : case T_WorkTableScan:
648 : : case T_ForeignScan:
649 : : case T_CustomScan:
650 : : case T_IndexScan:
651 : : case T_IndexOnlyScan:
652 : 202022 : return ((Scan *) plan)->scanrelid;
653 : 231196 : default:
654 : 231196 : return 0;
655 : : }
656 : : }
657 : :
658 : : /*
659 : : * Check whether a plan node is a Material node that should be treated as
660 : : * a scan. Currently, this only happens when set_tablesample_rel_pathlist
661 : : * inserts a Material node to protect a SampleScan that uses a non-repeatable
662 : : * tablesample method.
663 : : *
664 : : * (Most Material nodes we're likely to encounter are actually part of the
665 : : * join strategy: nested loops and merge joins can choose to materialize the
666 : : * inner sides of the join. The cases identified here are the rare
667 : : * exceptions.)
668 : : */
669 : : bool
206 670 : 127581 : pgpa_is_scan_level_materialize(Plan *plan)
671 : : {
672 : : Plan *child;
673 : : SampleScan *sscan;
674 : : TsmRoutine *tsm;
675 : :
676 [ + + ]: 127581 : if (!IsA(plan, Material))
677 : 126350 : return false;
678 : 1231 : child = plan->lefttree;
679 [ + - + + ]: 1231 : if (child == NULL || !IsA(child, SampleScan))
680 : 1226 : return false;
681 : 5 : sscan = (SampleScan *) child;
682 : 5 : tsm = GetTsmRoutine(sscan->tablesample->tsmhandler);
683 : 5 : return !tsm->repeatable_across_scans;
684 : : }
685 : :
686 : : /*
687 : : * Construct a new Bitmapset containing non-RTE_JOIN members of 'relids'.
688 : : */
689 : : Bitmapset *
238 690 : 97833 : pgpa_filter_out_join_relids(Bitmapset *relids, List *rtable)
691 : : {
692 : 97833 : int rti = -1;
693 : 97833 : Bitmapset *result = NULL;
694 : :
695 [ + + ]: 200251 : while ((rti = bms_next_member(relids, rti)) >= 0)
696 : : {
697 : 102418 : RangeTblEntry *rte = rt_fetch(rti, rtable);
698 : :
699 [ + + ]: 102418 : if (rte->rtekind != RTE_JOIN)
700 : 101852 : result = bms_add_member(result, rti);
701 : : }
702 : :
703 : 97833 : return result;
704 : : }
705 : :
706 : : /*
707 : : * Create a pgpa_query_feature and add it to the list of all query features
708 : : * for this plan.
709 : : */
710 : : static pgpa_query_feature *
711 : 1935 : pgpa_add_feature(pgpa_plan_walker_context *walker,
712 : : pgpa_qf_type type, Plan *plan)
713 : : {
714 : 1935 : pgpa_query_feature *qf = palloc0_object(pgpa_query_feature);
715 : :
716 : 1935 : qf->type = type;
717 : 1935 : qf->plan = plan;
718 : :
719 : 3870 : walker->query_features[qf->type] =
720 : 1935 : lappend(walker->query_features[qf->type], qf);
721 : :
722 : 1935 : return qf;
723 : : }
724 : :
725 : : /*
726 : : * Add a single RTI to each active query feature.
727 : : */
728 : : static void
729 : 99957 : pgpa_qf_add_rti(List *active_query_features, Index rti)
730 : : {
731 [ + + + + : 200916 : foreach_ptr(pgpa_query_feature, qf, active_query_features)
+ + ]
732 : : {
733 : 1002 : qf->relids = bms_add_member(qf->relids, rti);
734 : : }
735 : 99957 : }
736 : :
737 : : /*
738 : : * Add a set of RTIs to each active query feature.
739 : : */
740 : : static void
741 : 45020 : pgpa_qf_add_rtis(List *active_query_features, Bitmapset *relids)
742 : : {
743 [ + + + + : 91172 : foreach_ptr(pgpa_query_feature, qf, active_query_features)
+ + ]
744 : : {
745 : 1132 : qf->relids = bms_add_members(qf->relids, relids);
746 : : }
747 : 45020 : }
748 : :
749 : : /*
750 : : * Add RTIs directly contained in a plan node to each active query feature,
751 : : * but filter out any join RTIs, since advice doesn't mention those.
752 : : */
753 : : static void
754 : 246518 : pgpa_qf_add_plan_rtis(List *active_query_features, Plan *plan, List *rtable)
755 : : {
756 : : Bitmapset *relids;
757 : : Index rti;
758 : :
759 [ + + ]: 246518 : if ((relids = pgpa_relids(plan)) != NULL)
760 : : {
761 : 41745 : relids = pgpa_filter_out_join_relids(relids, rtable);
762 : 41745 : pgpa_qf_add_rtis(active_query_features, relids);
763 : : }
764 [ + + ]: 204773 : else if ((rti = pgpa_scanrelid(plan)) != 0)
765 : 99957 : pgpa_qf_add_rti(active_query_features, rti);
766 : 246518 : }
767 : :
768 : : /*
769 : : * If we generated plan advice using the provided walker object and array
770 : : * of identifiers, would we generate the specified tag/target combination?
771 : : *
772 : : * If yes, the plan conforms to the advice; if no, it does not. Note that
773 : : * we have no way of knowing whether the planner was forced to emit a plan
774 : : * that conformed to the advice or just happened to do so.
775 : : */
776 : : bool
777 : 145501 : pgpa_walker_would_advise(pgpa_plan_walker_context *walker,
778 : : pgpa_identifier *rt_identifiers,
779 : : pgpa_advice_tag_type tag,
780 : : pgpa_advice_target *target)
781 : : {
782 : 145501 : Index rtable_length = list_length(walker->pstmt->rtable);
783 : 145501 : Bitmapset *relids = NULL;
784 : :
785 [ + + ]: 145501 : if (tag == PGPA_TAG_JOIN_ORDER)
786 : : {
787 [ + - + + : 15059 : foreach_ptr(pgpa_unrolled_join, ujoin, walker->toplevel_unrolled_joins)
+ + ]
788 : : {
789 : : /*
790 : : * The advice need not account for every member of the join, so
791 : : * any non-zero result is good enough.
792 : : */
793 [ + + ]: 15057 : if (pgpa_walker_join_order_matches(ujoin, rtable_length,
794 : : rt_identifiers, target) != 0)
795 : 11067 : return true;
796 : : }
797 : :
798 : 1 : return false;
799 : : }
800 : :
801 : : /*
802 : : * DO_NOT_SCAN advice targets rels that may not be in the flat range table
803 : : * (e.g. MinMaxAgg losers), so pgpa_compute_rti_from_identifier won't work
804 : : * here. Instead, check directly against the do_not_scan_identifiers list.
805 : : */
224 806 [ + + ]: 134433 : if (tag == PGPA_TAG_DO_NOT_SCAN)
807 : : {
808 [ - + ]: 434 : if (target->ttype != PGPA_TARGET_IDENTIFIER)
224 rhaas@postgresql.org 809 :UBC 0 : return false;
224 rhaas@postgresql.org 810 [ + + + - :CBC 755 : foreach_ptr(pgpa_identifier, rid, walker->do_not_scan_identifiers)
+ + ]
811 : : {
812 [ + + ]: 753 : if (strcmp(rid->alias_name, target->rid.alias_name) == 0 &&
813 [ + - + + ]: 1482 : rid->occurrence == target->rid.occurrence &&
814 : 741 : strings_equal_or_both_null(rid->partnsp,
815 [ + + ]: 669 : target->rid.partnsp) &&
816 : 669 : strings_equal_or_both_null(rid->partrel,
817 [ + + ]: 596 : target->rid.partrel) &&
818 : 596 : strings_equal_or_both_null(rid->plan_name,
819 : : target->rid.plan_name))
820 : 433 : return true;
821 : : }
822 : 1 : return false;
823 : : }
824 : :
238 825 [ + + ]: 133999 : if (target->ttype == PGPA_TARGET_IDENTIFIER)
826 : : {
827 : : Index rti;
828 : :
829 : 133087 : rti = pgpa_compute_rti_from_identifier(rtable_length, rt_identifiers,
830 : : &target->rid);
831 [ - + ]: 133087 : if (rti == 0)
238 rhaas@postgresql.org 832 :UBC 0 : return false;
238 rhaas@postgresql.org 833 :CBC 133087 : relids = bms_make_singleton(rti);
834 : : }
835 : : else
836 : : {
837 [ - + ]: 912 : Assert(target->ttype == PGPA_TARGET_ORDERED_LIST);
838 [ + - + + : 3828 : foreach_ptr(pgpa_advice_target, child_target, target->children)
+ + ]
839 : : {
840 : : Index rti;
841 : :
842 [ - + ]: 2004 : Assert(child_target->ttype == PGPA_TARGET_IDENTIFIER);
843 : 2004 : rti = pgpa_compute_rti_from_identifier(rtable_length,
844 : : rt_identifiers,
845 : : &child_target->rid);
846 [ - + ]: 2004 : if (rti == 0)
238 rhaas@postgresql.org 847 :UBC 0 : return false;
238 rhaas@postgresql.org 848 :CBC 2004 : relids = bms_add_member(relids, rti);
849 : : }
850 : : }
851 : :
852 [ - - + + : 133999 : switch (tag)
+ + + + +
+ + + + +
+ + + + +
+ - ]
853 : : {
238 rhaas@postgresql.org 854 :UBC 0 : case PGPA_TAG_JOIN_ORDER:
855 : : /* should have been handled above */
856 : 0 : pg_unreachable();
857 : : break;
224 858 : 0 : case PGPA_TAG_DO_NOT_SCAN:
859 : : /* should have been handled above */
860 : 0 : pg_unreachable();
861 : : break;
238 rhaas@postgresql.org 862 :CBC 2283 : case PGPA_TAG_BITMAP_HEAP_SCAN:
863 : 2283 : return pgpa_walker_find_scan(walker,
864 : : PGPA_SCAN_BITMAP_HEAP,
865 : 2283 : relids) != NULL;
866 : 1 : case PGPA_TAG_FOREIGN_JOIN:
867 : 1 : return pgpa_walker_find_scan(walker,
868 : : PGPA_SCAN_FOREIGN,
869 : 1 : relids) != NULL;
870 : 1688 : case PGPA_TAG_INDEX_ONLY_SCAN:
871 : : {
872 : : pgpa_scan *scan;
873 : :
874 : 1688 : scan = pgpa_walker_find_scan(walker, PGPA_SCAN_INDEX_ONLY,
875 : : relids);
876 [ + + ]: 1688 : if (scan == NULL)
877 : 3 : return false;
878 : :
879 : 1685 : return pgpa_walker_index_target_matches_plan(target->itarget, scan->plan);
880 : : }
881 : 13085 : case PGPA_TAG_INDEX_SCAN:
882 : : {
883 : : pgpa_scan *scan;
884 : :
885 : 13085 : scan = pgpa_walker_find_scan(walker, PGPA_SCAN_INDEX,
886 : : relids);
887 [ + + ]: 13085 : if (scan == NULL)
888 : 2 : return false;
889 : :
890 : 13083 : return pgpa_walker_index_target_matches_plan(target->itarget, scan->plan);
891 : : }
892 : 2251 : case PGPA_TAG_PARTITIONWISE:
893 : 2251 : return pgpa_walker_find_scan(walker,
894 : : PGPA_SCAN_PARTITIONWISE,
895 : 2251 : relids) != NULL;
896 : 26251 : case PGPA_TAG_SEQ_SCAN:
897 : 26251 : return pgpa_walker_find_scan(walker,
898 : : PGPA_SCAN_SEQ,
899 : 26251 : relids) != NULL;
900 : 420 : case PGPA_TAG_TID_SCAN:
901 : 420 : return pgpa_walker_find_scan(walker,
902 : : PGPA_SCAN_TID,
903 : 420 : relids) != NULL;
904 : 173 : case PGPA_TAG_GATHER:
905 : 173 : return pgpa_walker_contains_feature(walker,
906 : : PGPAQF_GATHER,
907 : : relids);
908 : 58 : case PGPA_TAG_GATHER_MERGE:
909 : 58 : return pgpa_walker_contains_feature(walker,
910 : : PGPAQF_GATHER_MERGE,
911 : : relids);
912 : 623 : case PGPA_TAG_SEMIJOIN_NON_UNIQUE:
913 : 623 : return pgpa_walker_contains_feature(walker,
914 : : PGPAQF_SEMIJOIN_NON_UNIQUE,
915 : : relids);
916 : 82 : case PGPA_TAG_SEMIJOIN_UNIQUE:
917 : 82 : return pgpa_walker_contains_feature(walker,
918 : : PGPAQF_SEMIJOIN_UNIQUE,
919 : : relids);
920 : 4432 : case PGPA_TAG_HASH_JOIN:
921 : 4432 : return pgpa_walker_contains_join(walker,
922 : : JSTRAT_HASH_JOIN,
923 : : relids);
924 : 31 : case PGPA_TAG_MERGE_JOIN_MATERIALIZE:
925 : 31 : return pgpa_walker_contains_join(walker,
926 : : JSTRAT_MERGE_JOIN_MATERIALIZE,
927 : : relids);
928 : 570 : case PGPA_TAG_MERGE_JOIN_PLAIN:
929 : 570 : return pgpa_walker_contains_join(walker,
930 : : JSTRAT_MERGE_JOIN_PLAIN,
931 : : relids);
932 : 566 : case PGPA_TAG_NESTED_LOOP_MATERIALIZE:
933 : 566 : return pgpa_walker_contains_join(walker,
934 : : JSTRAT_NESTED_LOOP_MATERIALIZE,
935 : : relids);
936 : 243 : case PGPA_TAG_NESTED_LOOP_MEMOIZE:
937 : 243 : return pgpa_walker_contains_join(walker,
938 : : JSTRAT_NESTED_LOOP_MEMOIZE,
939 : : relids);
940 : 9271 : case PGPA_TAG_NESTED_LOOP_PLAIN:
941 : 9271 : return pgpa_walker_contains_join(walker,
942 : : JSTRAT_NESTED_LOOP_PLAIN,
943 : : relids);
944 : 71971 : case PGPA_TAG_NO_GATHER:
945 : 71971 : return pgpa_walker_contains_no_gather(walker, relids);
946 : : }
947 : :
948 : : /* should not get here */
238 rhaas@postgresql.org 949 :UBC 0 : return false;
950 : : }
951 : :
952 : : /*
953 : : * Does the index target match the Plan?
954 : : *
955 : : * Should only be called when we know that itarget mandates an Index Scan or
956 : : * Index Only Scan and this corresponds to the type of Plan. Here, our job is
957 : : * just to check whether it's the same index.
958 : : */
959 : : static bool
238 rhaas@postgresql.org 960 :CBC 14768 : pgpa_walker_index_target_matches_plan(pgpa_index_target *itarget, Plan *plan)
961 : : {
962 : 14768 : Oid indexoid = InvalidOid;
963 : :
964 : : /* Retrieve the index OID from the plan. */
965 [ + + ]: 14768 : if (IsA(plan, IndexScan))
966 : 13083 : indexoid = ((IndexScan *) plan)->indexid;
967 [ + - ]: 1685 : else if (IsA(plan, IndexOnlyScan))
968 : 1685 : indexoid = ((IndexOnlyScan *) plan)->indexid;
969 : : else
238 rhaas@postgresql.org 970 [ # # ]:UBC 0 : elog(ERROR, "unrecognized node type: %d", (int) nodeTag(plan));
971 : :
972 : : /* Check whether schema name matches, if specified in index target. */
238 rhaas@postgresql.org 973 [ + + ]:CBC 14768 : if (itarget->indnamespace != NULL)
974 : : {
975 : 14757 : Oid nspoid = get_rel_namespace(indexoid);
976 : 14757 : char *relnamespace = get_namespace_name_or_temp(nspoid);
977 : :
978 [ + + ]: 14757 : if (strcmp(itarget->indnamespace, relnamespace) != 0)
979 : 1 : return false;
980 : : }
981 : :
982 : : /* Check whether relation name matches. */
983 : 14767 : return (strcmp(itarget->indname, get_rel_name(indexoid)) == 0);
984 : : }
985 : :
986 : : /*
987 : : * Does an unrolled join match the join order specified by an advice target?
988 : : *
989 : : * The return value is the number of join members matched, or 0 if they do not
990 : : * match. This allows the caller to distinguish between a complete match
991 : : * (where the return value will be ujoin->ninner + 1) and a partial match
992 : : * (where the return value will be some smaller positive integer), if desired.
993 : : */
994 : : static unsigned
995 : 15644 : pgpa_walker_join_order_matches(pgpa_unrolled_join *ujoin,
996 : : Index rtable_length,
997 : : pgpa_identifier *rt_identifiers,
998 : : pgpa_advice_target *target)
999 : : {
49 1000 : 15644 : unsigned match_position = 0;
1001 : :
238 1002 [ - + ]: 15644 : Assert(target->ttype == PGPA_TARGET_ORDERED_LIST);
1003 : :
49 1004 [ + - + + : 54079 : foreach_ptr(pgpa_advice_target, child_target, target->children)
+ + ]
1005 : : {
1006 [ - + ]: 30771 : if (match_position > ujoin->ninner)
1007 : 3990 : return 0;
1008 [ + + ]: 30771 : if (!pgpa_walker_join_order_matches_members(ujoin, &match_position,
1009 : : rtable_length,
1010 : : rt_identifiers,
1011 : : child_target))
1012 : 3990 : return 0;
1013 : : }
1014 : :
1015 : 11654 : return match_position;
1016 : : }
1017 : :
1018 : : /*
1019 : : * Does the specified portion of an unrolled join match an advice target?
1020 : : *
1021 : : * We'll look for a match within ujoin beginning at *match_position, where 0
1022 : : * means a match starting with the outer member, and a positive value of N
1023 : : * means a match starting with the inner member at index N - 1. If a match is
1024 : : * found, returns true and *match_position is incremented by the number of
1025 : : * pgpa_join_member objects consumed; if not, returns false and the value
1026 : : * of *match_position is undefined.
1027 : : */
1028 : : static bool
1029 : 30771 : pgpa_walker_join_order_matches_members(pgpa_unrolled_join *ujoin,
1030 : : unsigned *match_position,
1031 : : Index rtable_length,
1032 : : pgpa_identifier *rt_identifiers,
1033 : : pgpa_advice_target *target)
1034 : : {
1035 : : pgpa_join_member *member;
1036 : :
1037 : 30771 : check_stack_depth();
1038 : :
1039 : : /*
1040 : : * Find the pgpa_join_member to which *match_position refers.
1041 : : */
1042 [ + + ]: 30771 : if (*match_position == 0)
1043 : 15644 : member = &ujoin->outer;
1044 : : else
1045 : : {
1046 [ - + ]: 15127 : Assert(*match_position <= ujoin->ninner);
1047 : 15127 : member = &ujoin->inner[*match_position - 1];
1048 : : }
1049 : :
1050 : : /*
1051 : : * Single-element lists within a join order specification have no clear
1052 : : * meaning, since a join intrinsically involves at least two tables, but
1053 : : * enforcement treats them as if the extra list levels were not present.
1054 : : * That is, JOIN_ORDER((({a})) b) is elsewhere treated as synonymous with
1055 : : * JOIN_ORDER(a b), so we do that here as well.
1056 : : */
1057 [ + + + + ]: 31411 : while (target->ttype != PGPA_TARGET_IDENTIFIER &&
1058 : 635 : list_length(target->children) == 1)
1059 : 5 : target = linitial(target->children);
1060 : :
1061 : : /* Now do the real work. */
238 1062 [ + + + - ]: 30771 : switch (target->ttype)
1063 : : {
1064 : 587 : case PGPA_TARGET_ORDERED_LIST:
1065 : :
1066 : : /*
1067 : : * Since outer-deep joins are flattened, a sublist that begins at
1068 : : * the outer member describes the start of this unrolled join. For
1069 : : * instance, JOIN_ORDER((a b) c d) is a less-convenient but still
1070 : : * acceptable way of writing JOIN_ORDER(a b c d).
1071 : : */
49 1072 [ + + ]: 587 : if (*match_position == 0)
1073 : : {
1074 : : unsigned nmatched;
1075 : :
1076 : 2 : nmatched = pgpa_walker_join_order_matches(ujoin,
1077 : : rtable_length,
1078 : : rt_identifiers,
1079 : : target);
1080 [ - + ]: 2 : if (nmatched == 0)
49 rhaas@postgresql.org 1081 :UBC 0 : return false;
49 rhaas@postgresql.org 1082 :CBC 2 : *match_position += nmatched;
1083 : 2 : return true;
1084 : : }
1085 : :
1086 : : /*
1087 : : * In contrast, a sublist being matched to an inner member can
1088 : : * only ever match that one member, which must therefore be an
1089 : : * unrolled join.
1090 : : */
1091 [ + - ]: 585 : if (member->unrolled_join != NULL)
1092 : : {
1093 : 585 : pgpa_unrolled_join *nested = member->unrolled_join;
1094 : : unsigned nmatched;
1095 : :
1096 : 585 : nmatched = pgpa_walker_join_order_matches(nested,
1097 : : rtable_length,
1098 : : rt_identifiers,
1099 : : target);
1100 : :
1101 : : /*
1102 : : * Only a complete match suffices. Something like JOIN_ORDER(a
1103 : : * (b c d) e) still matches if, after those five tables are
1104 : : * joined as shown, there are additional joins to other
1105 : : * tables. But table a must be joined first to a three-way
1106 : : * join between exactly b, c, and d: no additional tables are
1107 : : * allowed beyond those named in the sublist.
1108 : : */
1109 [ + - ]: 585 : if (nmatched == nested->ninner + 1)
1110 : : {
1111 : 585 : *match_position += 1;
1112 : 585 : return true;
1113 : : }
1114 : : }
1115 : :
238 rhaas@postgresql.org 1116 :UBC 0 : return false;
1117 : :
238 rhaas@postgresql.org 1118 :CBC 43 : case PGPA_TARGET_UNORDERED_LIST:
1119 : : {
49 1120 : 43 : Bitmapset *relids = NULL;
1121 : : Bitmapset *member_relids;
1122 : : Bitmapset *accumulated_relids;
1123 : : BMS_Comparison comparison;
1124 : 43 : unsigned ninner = 0;
1125 : :
1126 : : /*
1127 : : * Convert this unordered sublist to a set of RTIs; but, if
1128 : : * any relation identifier can't be mapped to an RTI, then
1129 : : * there is no match.
1130 : : */
238 1131 [ + - + + : 183 : foreach_ptr(pgpa_advice_target, child_target, target->children)
+ + ]
1132 : : {
1133 : : Index rti;
1134 : :
1135 : 97 : rti = pgpa_compute_rti_from_identifier(rtable_length,
1136 : : rt_identifiers,
1137 : : &child_target->rid);
1138 [ - + ]: 97 : if (rti == 0)
238 rhaas@postgresql.org 1139 :UBC 0 : return false;
238 rhaas@postgresql.org 1140 :CBC 97 : relids = bms_add_member(relids, rti);
1141 : : }
1142 : :
1143 : : /* See whether it matches the set of RTIs for this member. */
49 1144 : 43 : member_relids = pgpa_walker_join_member_relids(member);
1145 : 43 : comparison = bms_subset_compare(member_relids, relids);
1146 [ + + ]: 43 : if (comparison == BMS_EQUAL)
1147 : : {
1148 : : /* Exact match: we're done! */
1149 : 20 : *match_position += 1;
1150 : 20 : return true;
1151 : : }
1152 : :
1153 : : /*
1154 : : * If we're matching this target against an inner member, the
1155 : : * target must match exactly one member, or else it's not a
1156 : : * match at all.
1157 : : */
1158 [ - + ]: 23 : if (*match_position != 0)
49 rhaas@postgresql.org 1159 :UBC 0 : return false;
1160 : :
1161 : : /*
1162 : : * Since outer-deep joins are flattened, a sublist that begins
1163 : : * at the outer member describes the start of this unrolled
1164 : : * join.
1165 : : *
1166 : : * For instance, JOIN_ORDER({a b} c d) allows for an unrolled
1167 : : * join with either a or b as the outer rel and the other as
1168 : : * the first inner rel.
1169 : : *
1170 : : * This means we need to iterate to figure out how many inner
1171 : : * members this advice target matches (or to discover that
1172 : : * there is no match).
1173 : : */
49 rhaas@postgresql.org 1174 :CBC 23 : accumulated_relids = bms_copy(member_relids);
1175 [ + + + - ]: 26 : while (comparison == BMS_SUBSET1 && ninner < ujoin->ninner)
1176 : : {
1177 : 3 : member = &ujoin->inner[ninner++];
1178 : 3 : member_relids = pgpa_walker_join_member_relids(member);
1179 : 3 : accumulated_relids = bms_add_members(accumulated_relids,
1180 : : member_relids);
1181 : 3 : comparison = bms_subset_compare(accumulated_relids,
1182 : : relids);
1183 : : }
1184 : :
1185 : : /*
1186 : : * If we found a number of inner members such that the union
1187 : : * of all their RTIs exactly matches the set that the advice
1188 : : * target must cover, then consume them all and return true.
1189 : : * If not, it's not a match, so return false.
1190 : : */
1191 [ + + ]: 23 : if (comparison == BMS_EQUAL)
1192 : : {
1193 : 2 : *match_position += 1 + ninner;
1194 : 2 : return true;
1195 : : }
1196 : 21 : return false;
1197 : : }
1198 : :
238 1199 : 30141 : case PGPA_TARGET_IDENTIFIER:
1200 : : {
1201 : : Index rti;
1202 : : int scan_rti;
1203 : :
1204 : : /* Could only match a scan */
49 1205 [ - + ]: 30141 : if (member->unrolled_join != NULL)
49 rhaas@postgresql.org 1206 :UBC 0 : return false;
1207 : :
238 rhaas@postgresql.org 1208 :CBC 30141 : rti = pgpa_compute_rti_from_identifier(rtable_length,
1209 : : rt_identifiers,
1210 : : &target->rid);
1211 [ - + ]: 30141 : if (rti == 0)
238 rhaas@postgresql.org 1212 :UBC 0 : return false;
1213 : :
49 rhaas@postgresql.org 1214 [ - + ]:CBC 30141 : if (!bms_get_singleton_member(member->scan->relids, &scan_rti))
49 rhaas@postgresql.org 1215 :UBC 0 : return false;
49 rhaas@postgresql.org 1216 [ + + ]:CBC 30141 : if (rti != (Index) scan_rti)
1217 : 3969 : return false;
1218 : :
1219 : 26172 : *match_position += 1;
1220 : 26172 : return true;
1221 : : }
1222 : : }
1223 : :
49 rhaas@postgresql.org 1224 :UBC 0 : pg_unreachable();
1225 : : return false;
1226 : : }
1227 : :
1228 : : /*
1229 : : * Compute the set of relations covered by one member of an unrolled join.
1230 : : */
1231 : : static Bitmapset *
49 rhaas@postgresql.org 1232 :CBC 48 : pgpa_walker_join_member_relids(pgpa_join_member *member)
1233 : : {
1234 : : pgpa_unrolled_join *ujoin;
1235 : : Bitmapset *all_relids;
1236 : :
1237 : 48 : check_stack_depth();
1238 : :
1239 : : /* If it's a scan, this is easy. */
1240 [ + + ]: 48 : if (member->scan != NULL)
1241 : 46 : return member->scan->relids;
1242 : :
1243 : : /* Otherwise, it's an unrolled join. */
1244 : 2 : ujoin = member->unrolled_join;
1245 [ - + ]: 2 : Assert(ujoin != NULL);
1246 : :
1247 : : /* Collect outer relids (which must be from a scan). */
1248 [ - + ]: 2 : Assert(ujoin->outer.unrolled_join == NULL);
1249 : 2 : all_relids = bms_copy(ujoin->outer.scan->relids);
1250 : :
1251 : : /* Collect each set of inner relids. */
1252 [ + + ]: 4 : for (unsigned k = 0; k < ujoin->ninner; ++k)
1253 : : all_relids =
1254 : 2 : bms_add_members(all_relids,
1255 : 2 : pgpa_walker_join_member_relids(&ujoin->inner[k]));
1256 : :
1257 : 2 : return all_relids;
1258 : : }
1259 : :
1260 : : /*
1261 : : * Find the scan where the walker says that the given scan strategy should be
1262 : : * used for the given relid set, if one exists.
1263 : : *
1264 : : * Returns the pgpa_scan object, or NULL if none was found.
1265 : : */
1266 : : static pgpa_scan *
238 1267 : 45979 : pgpa_walker_find_scan(pgpa_plan_walker_context *walker,
1268 : : pgpa_scan_strategy strategy,
1269 : : Bitmapset *relids)
1270 : : {
1271 : 45979 : List *scans = walker->scans[strategy];
1272 : :
1273 [ + + + + : 89570 : foreach_ptr(pgpa_scan, scan, scans)
+ + ]
1274 : : {
1275 [ + + ]: 89542 : if (bms_equal(scan->relids, relids))
1276 : 45965 : return scan;
1277 : : }
1278 : :
1279 : 14 : return NULL;
1280 : : }
1281 : :
1282 : : /*
1283 : : * Does this walker say that the given query feature applies to the given
1284 : : * relid set?
1285 : : */
1286 : : static bool
1287 : 936 : pgpa_walker_contains_feature(pgpa_plan_walker_context *walker,
1288 : : pgpa_qf_type type,
1289 : : Bitmapset *relids)
1290 : : {
1291 : 936 : List *query_features = walker->query_features[type];
1292 : :
1293 [ + + + + : 1058 : foreach_ptr(pgpa_query_feature, qf, query_features)
+ + ]
1294 : : {
1295 [ + + ]: 1046 : if (bms_equal(qf->relids, relids))
1296 : 930 : return true;
1297 : : }
1298 : :
1299 : 6 : return false;
1300 : : }
1301 : :
1302 : : /*
1303 : : * Does the walker say that the given join strategy should be used for the
1304 : : * given relid set?
1305 : : */
1306 : : static bool
1307 : 15113 : pgpa_walker_contains_join(pgpa_plan_walker_context *walker,
1308 : : pgpa_join_strategy strategy,
1309 : : Bitmapset *relids)
1310 : : {
1311 : 15113 : List *join_strategies = walker->join_strategies[strategy];
1312 : :
1313 [ + + + + : 25778 : foreach_ptr(Bitmapset, jsrelids, join_strategies)
+ + ]
1314 : : {
1315 [ + + ]: 25768 : if (bms_equal(jsrelids, relids))
1316 : 15108 : return true;
1317 : : }
1318 : :
1319 : 5 : return false;
1320 : : }
1321 : :
1322 : : /*
1323 : : * Does the walker say that the given relids should be marked as NO_GATHER?
1324 : : */
1325 : : static bool
1326 : 71971 : pgpa_walker_contains_no_gather(pgpa_plan_walker_context *walker,
1327 : : Bitmapset *relids)
1328 : : {
1329 : 71971 : return bms_is_subset(relids, walker->no_gather_scans);
1330 : : }
1331 : :
1332 : : /*
1333 : : * Classify alternative subplans as chosen or discarded.
1334 : : */
1335 : : static void
224 1336 : 87304 : pgpa_classify_alternative_subplans(pgpa_plan_walker_context *walker,
1337 : : List *proots,
1338 : : List **chosen_proots,
1339 : : List **discarded_proots)
1340 : : {
1341 : 87304 : Bitmapset *all_scan_rtis = NULL;
1342 : :
1343 : : /* Initialize both output lists to empty. */
1344 : 87304 : *chosen_proots = NIL;
1345 : 87304 : *discarded_proots = NIL;
1346 : :
1347 : : /* Collect all scan RTIs. */
1348 [ + + ]: 785736 : for (int s = 0; s < NUM_PGPA_SCAN_STRATEGY; s++)
1349 [ + + + + : 1548522 : foreach_ptr(pgpa_scan, scan, walker->scans[s])
+ + ]
1350 : 151658 : all_scan_rtis = bms_add_members(all_scan_rtis, scan->relids);
1351 : :
1352 : : /* Now classify each subplan. */
1353 [ + - + + : 279216 : foreach_ptr(pgpa_planner_info, proot, proots)
+ + ]
1354 : : {
1355 : 104608 : bool chosen = false;
1356 : :
1357 : : /*
1358 : : * We're only interested in classifying subplans for which there are
1359 : : * alternatives.
1360 : : */
1361 [ + + ]: 104608 : if (!proot->is_alternative_plan)
1362 : 103226 : continue;
1363 : :
1364 : : /*
1365 : : * A subplan has been chosen if any of its scan RTIs appear in the
1366 : : * final plan. This cannot be the case if it has no RT offset.
1367 : : */
1368 [ + + ]: 1382 : if (proot->has_rtoffset)
1369 : : {
1370 [ + + ]: 5176 : for (int rti = 1; rti <= proot->rid_array_size; rti++)
1371 : : {
1372 [ + + + + ]: 5905 : if (proot->rid_array[rti - 1].alias_name != NULL &&
1373 : 1232 : bms_is_member(proot->rtoffset + rti, all_scan_rtis))
1374 : : {
1375 : 649 : chosen = true;
1376 : 649 : break;
1377 : : }
1378 : : }
1379 : : }
1380 : :
1381 : : /* Add it to the correct list. */
1382 [ + + ]: 1382 : if (chosen)
1383 : 649 : *chosen_proots = lappend(*chosen_proots, proot);
1384 : : else
1385 : 733 : *discarded_proots = lappend(*discarded_proots, proot);
1386 : : }
1387 : 87304 : }
|
