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 "nodes/plannodes.h"
21 : #include "parser/parsetree.h"
22 : #include "utils/lsyscache.h"
23 :
24 : static void pgpa_walk_recursively(pgpa_plan_walker_context *walker, Plan *plan,
25 : bool within_join_problem,
26 : pgpa_join_unroller *join_unroller,
27 : List *active_query_features,
28 : bool beneath_any_gather);
29 : static Bitmapset *pgpa_process_unrolled_join(pgpa_plan_walker_context *walker,
30 : pgpa_unrolled_join *ujoin);
31 :
32 : static pgpa_query_feature *pgpa_add_feature(pgpa_plan_walker_context *walker,
33 : pgpa_qf_type type,
34 : Plan *plan);
35 :
36 : static void pgpa_qf_add_rti(List *active_query_features, Index rti);
37 : static void pgpa_qf_add_rtis(List *active_query_features, Bitmapset *relids);
38 : static void pgpa_qf_add_plan_rtis(List *active_query_features, Plan *plan,
39 : List *rtable);
40 :
41 : static bool pgpa_walker_join_order_matches(pgpa_unrolled_join *ujoin,
42 : Index rtable_length,
43 : pgpa_identifier *rt_identifiers,
44 : pgpa_advice_target *target,
45 : bool toplevel);
46 : static bool pgpa_walker_join_order_matches_member(pgpa_join_member *member,
47 : Index rtable_length,
48 : pgpa_identifier *rt_identifiers,
49 : pgpa_advice_target *target);
50 : static pgpa_scan *pgpa_walker_find_scan(pgpa_plan_walker_context *walker,
51 : pgpa_scan_strategy strategy,
52 : Bitmapset *relids);
53 : static bool pgpa_walker_index_target_matches_plan(pgpa_index_target *itarget,
54 : Plan *plan);
55 : static bool pgpa_walker_contains_feature(pgpa_plan_walker_context *walker,
56 : pgpa_qf_type type,
57 : Bitmapset *relids);
58 : static bool pgpa_walker_contains_join(pgpa_plan_walker_context *walker,
59 : pgpa_join_strategy strategy,
60 : Bitmapset *relids);
61 : static bool pgpa_walker_contains_no_gather(pgpa_plan_walker_context *walker,
62 : Bitmapset *relids);
63 : static void pgpa_classify_alternative_subplans(pgpa_plan_walker_context *walker,
64 : List *proots,
65 : List **chosen_proots,
66 : List **discarded_proots);
67 :
68 : /*
69 : * Top-level entrypoint for the plan tree walk.
70 : *
71 : * Populates walker based on a traversal of the Plan trees in pstmt.
72 : *
73 : * proots is the list of pgpa_planner_info objects that were generated
74 : * during planning.
75 : */
76 : void
77 87144 : pgpa_plan_walker(pgpa_plan_walker_context *walker, PlannedStmt *pstmt,
78 : List *proots)
79 : {
80 : ListCell *lc;
81 87144 : List *sj_unique_rtis = NULL;
82 87144 : List *sj_nonunique_qfs = NULL;
83 : List *chosen_proots;
84 : List *discarded_proots;
85 :
86 : /* Initialization. */
87 87144 : memset(walker, 0, sizeof(pgpa_plan_walker_context));
88 87144 : walker->pstmt = pstmt;
89 :
90 : /* Walk the main plan tree. */
91 87144 : pgpa_walk_recursively(walker, pstmt->planTree, false, NULL, NIL, false);
92 :
93 : /* Main plan tree walk won't reach subplans, so walk those. */
94 96276 : foreach(lc, pstmt->subplans)
95 : {
96 9132 : Plan *plan = lfirst(lc);
97 :
98 9132 : if (plan != NULL)
99 8743 : pgpa_walk_recursively(walker, plan, false, NULL, NIL, false);
100 : }
101 :
102 : /* Adjust RTIs from sj_unique_rels for the flattened range table. */
103 278568 : foreach_ptr(pgpa_planner_info, proot, proots)
104 : {
105 : /* If there are no sj_unique_rels for this proot, we can skip it. */
106 104280 : if (proot->sj_unique_rels == NIL)
107 102997 : continue;
108 :
109 : /* If this is a subplan, find the range table offset. */
110 1283 : if (!proot->has_rtoffset)
111 0 : elog(ERROR, "no rtoffset for plan %s", proot->plan_name);
112 :
113 : /* Offset each relid set by the proot's rtoffset. */
114 4009 : foreach_node(Bitmapset, relids, proot->sj_unique_rels)
115 : {
116 1443 : int rtindex = -1;
117 1443 : Bitmapset *flat_relids = NULL;
118 :
119 2972 : while ((rtindex = bms_next_member(relids, rtindex)) >= 0)
120 1529 : flat_relids = bms_add_member(flat_relids,
121 1529 : rtindex + proot->rtoffset);
122 :
123 1443 : sj_unique_rtis = lappend(sj_unique_rtis, flat_relids);
124 : }
125 : }
126 :
127 : /*
128 : * Remove any non-unique semijoin query features for which making the rel
129 : * unique wasn't considered.
130 : */
131 175583 : foreach_ptr(pgpa_query_feature, qf,
132 : walker->query_features[PGPAQF_SEMIJOIN_NON_UNIQUE])
133 : {
134 1295 : if (list_member(sj_unique_rtis, qf->relids))
135 1241 : sj_nonunique_qfs = lappend(sj_nonunique_qfs, qf);
136 : }
137 87144 : walker->query_features[PGPAQF_SEMIJOIN_NON_UNIQUE] = sj_nonunique_qfs;
138 :
139 : /*
140 : * If we find any cases where analysis of the Plan tree shows that the
141 : * semijoin was made unique but this possibility was never observed to be
142 : * considered during planning, then we have a bug somewhere.
143 : */
144 174442 : foreach_ptr(pgpa_query_feature, qf,
145 : walker->query_features[PGPAQF_SEMIJOIN_UNIQUE])
146 : {
147 154 : if (!list_member(sj_unique_rtis, qf->relids))
148 : {
149 : StringInfoData buf;
150 :
151 0 : initStringInfo(&buf);
152 0 : outBitmapset(&buf, qf->relids);
153 0 : elog(ERROR,
154 : "unique semijoin found for relids %s but not observed during planning",
155 : buf.data);
156 : }
157 : }
158 :
159 : /*
160 : * It's possible for a Gather or Gather Merge query feature to find no
161 : * RTIs when partitionwise aggregation is in use. We shouldn't emit
162 : * something like GATHER_MERGE(()), so instead emit nothing. This means
163 : * that we won't advise either GATHER or GATHER_MERGE or NO_GATHER in such
164 : * cases, which might be something we want to improve in the future.
165 : *
166 : * (Should the Partial Aggregates in such a case be created in an
167 : * UPPERREL_GROUP_AGG with a non-empty relid set? Right now that doesn't
168 : * happen, but it seems like it would make life easier for us if it did.)
169 : */
170 435720 : for (int t = 0; t < NUM_PGPA_QF_TYPES; ++t)
171 : {
172 348576 : List *query_features = NIL;
173 :
174 699024 : foreach_ptr(pgpa_query_feature, qf, walker->query_features[t])
175 : {
176 1872 : if (qf->relids != NULL)
177 1850 : query_features = lappend(query_features, qf);
178 : else
179 : Assert(t == PGPAQF_GATHER || t == PGPAQF_GATHER_MERGE);
180 : }
181 :
182 348576 : walker->query_features[t] = query_features;
183 : }
184 :
185 : /* Classify alternative subplans. */
186 87144 : pgpa_classify_alternative_subplans(walker, proots,
187 : &chosen_proots, &discarded_proots);
188 :
189 : /*
190 : * Figure out which of the discarded alternatives have a non-discarded
191 : * alternative. Those are the ones for which we want to emit DO_NOT_SCAN
192 : * advice. (If every alternative was discarded, then there's no point.)
193 : */
194 175013 : foreach_ptr(pgpa_planner_info, discarded_proot, discarded_proots)
195 : {
196 725 : bool some_alternative_chosen = false;
197 :
198 1646 : foreach_ptr(pgpa_planner_info, chosen_proot, chosen_proots)
199 : {
200 921 : if (strings_equal_or_both_null(discarded_proot->alternative_plan_name,
201 921 : chosen_proot->alternative_plan_name))
202 : {
203 725 : some_alternative_chosen = true;
204 725 : break;
205 : }
206 : }
207 :
208 725 : if (some_alternative_chosen)
209 : {
210 6525 : for (int rti = 1; rti <= discarded_proot->rid_array_size; rti++)
211 : {
212 5800 : pgpa_identifier *rid = &discarded_proot->rid_array[rti - 1];
213 :
214 5800 : if (rid->alias_name != NULL)
215 855 : walker->do_not_scan_identifiers =
216 855 : lappend(walker->do_not_scan_identifiers, rid);
217 : }
218 : }
219 : }
220 87144 : }
221 :
222 : /*
223 : * Main workhorse for the plan tree walk.
224 : *
225 : * If within_join_problem is true, we encountered a join at some higher level
226 : * of the tree walk and haven't yet descended out of the portion of the plan
227 : * tree that is part of that same join problem. We're no longer in the same
228 : * join problem if (1) we cross into a different subquery or (2) we descend
229 : * through an Append or MergeAppend node, below which any further joins would
230 : * be partitionwise joins planned separately from the outer join problem.
231 : *
232 : * If join_unroller != NULL, the join unroller code expects us to find a join
233 : * that should be unrolled into that object. This implies that we're within a
234 : * join problem, but the reverse is not true: when we've traversed all the
235 : * joins but are still looking for the scan that is the leaf of the join tree,
236 : * join_unroller will be NULL but within_join_problem will be true.
237 : *
238 : * Each element of active_query_features corresponds to some item of advice
239 : * that needs to enumerate all the relations it affects. We add RTIs we find
240 : * during tree traversal to each of these query features.
241 : *
242 : * If beneath_any_gather == true, some higher level of the tree traversal found
243 : * a Gather or Gather Merge node.
244 : */
245 : static void
246 249978 : pgpa_walk_recursively(pgpa_plan_walker_context *walker, Plan *plan,
247 : bool within_join_problem,
248 : pgpa_join_unroller *join_unroller,
249 : List *active_query_features,
250 : bool beneath_any_gather)
251 : {
252 249978 : pgpa_join_unroller *outer_join_unroller = NULL;
253 249978 : pgpa_join_unroller *inner_join_unroller = NULL;
254 249978 : bool join_unroller_toplevel = false;
255 : ListCell *lc;
256 249978 : List *extraplans = NIL;
257 249978 : List *elided_nodes = NIL;
258 :
259 : Assert(within_join_problem || join_unroller == NULL);
260 :
261 : /*
262 : * Check the future_query_features list to see whether this was previously
263 : * identified as a plan node that needs to be treated as a query feature.
264 : * We must do this before handling elided nodes, because if there's an
265 : * elided node associated with a future query feature, the RTIs associated
266 : * with the elided node should be the only ones attributed to the query
267 : * feature.
268 : */
269 501994 : foreach_ptr(pgpa_query_feature, qf, walker->future_query_features)
270 : {
271 3487 : if (qf->plan == plan)
272 : {
273 1449 : active_query_features = list_copy(active_query_features);
274 1449 : active_query_features = lappend(active_query_features, qf);
275 1449 : walker->future_query_features =
276 1449 : list_delete_ptr(walker->future_query_features, qf);
277 1449 : break;
278 : }
279 : }
280 :
281 : /*
282 : * Find all elided nodes for this Plan node.
283 : */
284 564792 : foreach_node(ElidedNode, n, walker->pstmt->elidedNodes)
285 : {
286 64836 : if (n->plan_node_id == plan->plan_node_id)
287 5630 : elided_nodes = lappend(elided_nodes, n);
288 : }
289 :
290 : /* If we found any elided_nodes, handle them. */
291 249978 : if (elided_nodes != NIL)
292 : {
293 5596 : int num_elided_nodes = list_length(elided_nodes);
294 : ElidedNode *last_elided_node;
295 :
296 : /*
297 : * RTIs for the final -- and thus logically uppermost -- elided node
298 : * should be collected for query features passed down by the caller.
299 : * However, elided nodes act as barriers to query features, which
300 : * means that (1) the remaining elided nodes, if any, should be
301 : * ignored for purposes of query features and (2) the list of active
302 : * query features should be reset to empty so that we do not add RTIs
303 : * from the plan node that is logically beneath the elided node to the
304 : * query features passed down from the caller.
305 : */
306 5596 : last_elided_node = list_nth(elided_nodes, num_elided_nodes - 1);
307 5596 : pgpa_qf_add_rtis(active_query_features,
308 : pgpa_filter_out_join_relids(last_elided_node->relids,
309 5596 : walker->pstmt->rtable));
310 5596 : active_query_features = NIL;
311 :
312 : /*
313 : * If we're within a join problem, the join_unroller is responsible
314 : * for building the scan for the final elided node, so throw it out.
315 : */
316 5596 : if (within_join_problem)
317 512 : elided_nodes = list_truncate(elided_nodes, num_elided_nodes - 1);
318 :
319 : /* Build scans for all (or the remaining) elided nodes. */
320 16310 : foreach_node(ElidedNode, elided_node, elided_nodes)
321 : {
322 5118 : (void) pgpa_build_scan(walker, plan, elided_node,
323 : beneath_any_gather, within_join_problem);
324 : }
325 :
326 : /*
327 : * If there were any elided nodes, then everything beneath those nodes
328 : * is not part of the same join problem.
329 : *
330 : * In more detail, if an Append or MergeAppend was elided, then a
331 : * partitionwise join was chosen and only a single child survived; if
332 : * a SubqueryScan was elided, the subquery was planned without
333 : * flattening it into the parent.
334 : */
335 5596 : within_join_problem = false;
336 5596 : join_unroller = NULL;
337 : }
338 :
339 : /*
340 : * If this is a Gather or Gather Merge node, directly add it to the list
341 : * of currently-active query features. We must do this after handling
342 : * elided nodes, since the Gather or Gather Merge node occurs logically
343 : * beneath any associated elided nodes.
344 : *
345 : * Exception: We disregard any single_copy Gather nodes. These are created
346 : * by debug_parallel_query, and having them affect the plan advice is
347 : * counterproductive, as the result will be to advise the use of a real
348 : * Gather node, rather than a single copy one.
349 : */
350 249978 : if (IsA(plan, Gather) && !((Gather *) plan)->single_copy)
351 : {
352 : active_query_features =
353 343 : lappend(list_copy(active_query_features),
354 343 : pgpa_add_feature(walker, PGPAQF_GATHER, plan));
355 343 : beneath_any_gather = true;
356 : }
357 249635 : else if (IsA(plan, GatherMerge))
358 : {
359 : active_query_features =
360 134 : lappend(list_copy(active_query_features),
361 134 : pgpa_add_feature(walker, PGPAQF_GATHER_MERGE, plan));
362 134 : beneath_any_gather = true;
363 : }
364 :
365 : /*
366 : * If we're within a join problem, the join unroller is responsible for
367 : * building any required scan for this node. If not, we do it here.
368 : */
369 249978 : if (!within_join_problem)
370 177637 : (void) pgpa_build_scan(walker, plan, NULL, beneath_any_gather, false);
371 :
372 : /*
373 : * If this join needs to be unrolled but there's no join unroller already
374 : * available, create one.
375 : */
376 249978 : if (join_unroller == NULL && pgpa_is_join(plan))
377 : {
378 22348 : join_unroller = pgpa_create_join_unroller();
379 22348 : join_unroller_toplevel = true;
380 22348 : within_join_problem = true;
381 : }
382 :
383 : /*
384 : * If this join is to be unrolled, pgpa_unroll_join() will return the join
385 : * unroller object that should be passed down when we recurse into the
386 : * outer and inner sides of the plan.
387 : */
388 249978 : if (join_unroller != NULL)
389 30581 : pgpa_unroll_join(walker, plan, beneath_any_gather, join_unroller,
390 : &outer_join_unroller, &inner_join_unroller);
391 :
392 : /* Add RTIs from the plan node to all active query features. */
393 249978 : pgpa_qf_add_plan_rtis(active_query_features, plan, walker->pstmt->rtable);
394 :
395 : /*
396 : * Recurse into the outer and inner subtrees.
397 : *
398 : * As an exception, if this is a ForeignScan, don't recurse. postgres_fdw
399 : * sometimes stores an EPQ recheck plan in plan->lefttree, but that's
400 : * going to mention the same set of relations as the ForeignScan itself,
401 : * and we have no way to emit advice targeting the EPQ case vs. the
402 : * non-EPQ case. Moreover, it's not entirely clear what other FDWs might
403 : * do with the left and right subtrees. Maybe some better handling is
404 : * needed here, but for now, we just punt.
405 : */
406 249978 : if (!IsA(plan, ForeignScan))
407 : {
408 249978 : if (plan->lefttree != NULL)
409 104832 : pgpa_walk_recursively(walker, plan->lefttree, within_join_problem,
410 : outer_join_unroller, active_query_features,
411 : beneath_any_gather);
412 249978 : if (plan->righttree != NULL)
413 30097 : pgpa_walk_recursively(walker, plan->righttree, within_join_problem,
414 : inner_join_unroller, active_query_features,
415 : beneath_any_gather);
416 : }
417 :
418 : /*
419 : * If we created a join unroller up above, then it's also our join to use
420 : * it to build the final pgpa_unrolled_join, and to destroy the object.
421 : */
422 249978 : if (join_unroller_toplevel)
423 : {
424 : pgpa_unrolled_join *ujoin;
425 :
426 22348 : ujoin = pgpa_build_unrolled_join(walker, join_unroller);
427 22348 : walker->toplevel_unrolled_joins =
428 22348 : lappend(walker->toplevel_unrolled_joins, ujoin);
429 22348 : pgpa_destroy_join_unroller(join_unroller);
430 22348 : (void) pgpa_process_unrolled_join(walker, ujoin);
431 : }
432 :
433 : /*
434 : * Some plan types can have additional children. Nodes like Append that
435 : * can have any number of children store them in a List; a SubqueryScan
436 : * just has a field for a single additional Plan.
437 : */
438 249978 : switch (nodeTag(plan))
439 : {
440 5241 : case T_Append:
441 : {
442 5241 : Append *aplan = (Append *) plan;
443 :
444 5241 : extraplans = aplan->appendplans;
445 : }
446 5241 : break;
447 186 : case T_MergeAppend:
448 : {
449 186 : MergeAppend *maplan = (MergeAppend *) plan;
450 :
451 186 : extraplans = maplan->mergeplans;
452 : }
453 186 : break;
454 34 : case T_BitmapAnd:
455 34 : extraplans = ((BitmapAnd *) plan)->bitmapplans;
456 34 : break;
457 66 : case T_BitmapOr:
458 66 : extraplans = ((BitmapOr *) plan)->bitmapplans;
459 66 : break;
460 3262 : case T_SubqueryScan:
461 :
462 : /*
463 : * We don't pass down active_query_features across here, because
464 : * those are specific to a subquery level.
465 : */
466 3262 : pgpa_walk_recursively(walker, ((SubqueryScan *) plan)->subplan,
467 : 0, NULL, NIL, beneath_any_gather);
468 3262 : break;
469 0 : case T_CustomScan:
470 0 : extraplans = ((CustomScan *) plan)->custom_plans;
471 0 : break;
472 241189 : default:
473 241189 : break;
474 : }
475 :
476 : /* If we found a list of extra children, iterate over it. */
477 265878 : foreach(lc, extraplans)
478 : {
479 15900 : Plan *subplan = lfirst(lc);
480 :
481 15900 : pgpa_walk_recursively(walker, subplan, false, NULL, NIL,
482 : beneath_any_gather);
483 : }
484 249978 : }
485 :
486 : /*
487 : * Perform final processing of a newly-constructed pgpa_unrolled_join. This
488 : * only needs to be called for toplevel pgpa_unrolled_join objects, since it
489 : * recurses to sub-joins as needed.
490 : *
491 : * Our goal is to add the set of inner relids to the relevant join_strategies
492 : * list, and to do the same for any sub-joins. To that end, the return value
493 : * is the set of relids found beneath the join, but it is expected that
494 : * the toplevel caller will ignore this.
495 : */
496 : static Bitmapset *
497 23411 : pgpa_process_unrolled_join(pgpa_plan_walker_context *walker,
498 : pgpa_unrolled_join *ujoin)
499 : {
500 23411 : Bitmapset *all_relids = bms_copy(ujoin->outer.scan->relids);
501 :
502 : /* If this fails, we didn't unroll properly. */
503 : Assert(ujoin->outer.unrolled_join == NULL);
504 :
505 53124 : for (int k = 0; k < ujoin->ninner; ++k)
506 : {
507 29713 : pgpa_join_member *member = &ujoin->inner[k];
508 : Bitmapset *relids;
509 :
510 29713 : if (member->unrolled_join != NULL)
511 1063 : relids = pgpa_process_unrolled_join(walker,
512 : member->unrolled_join);
513 : else
514 : {
515 : Assert(member->scan != NULL);
516 28650 : relids = member->scan->relids;
517 : }
518 59426 : walker->join_strategies[ujoin->strategy[k]] =
519 29713 : lappend(walker->join_strategies[ujoin->strategy[k]], relids);
520 29713 : all_relids = bms_add_members(all_relids, relids);
521 : }
522 :
523 23411 : return all_relids;
524 : }
525 :
526 : /*
527 : * Arrange for the given plan node to be treated as a query feature when the
528 : * tree walk reaches it.
529 : *
530 : * Make sure to only use this for nodes that the tree walk can't have reached
531 : * yet!
532 : */
533 : void
534 1449 : pgpa_add_future_feature(pgpa_plan_walker_context *walker,
535 : pgpa_qf_type type, Plan *plan)
536 : {
537 1449 : pgpa_query_feature *qf = pgpa_add_feature(walker, type, plan);
538 :
539 1449 : walker->future_query_features =
540 1449 : lappend(walker->future_query_features, qf);
541 1449 : }
542 :
543 : /*
544 : * Return the last of any elided nodes associated with this plan node ID.
545 : *
546 : * The last elided node is the one that would have been uppermost in the plan
547 : * tree had it not been removed during setrefs processing.
548 : */
549 : ElidedNode *
550 71997 : pgpa_last_elided_node(PlannedStmt *pstmt, Plan *plan)
551 : {
552 71997 : ElidedNode *elided_node = NULL;
553 :
554 176400 : foreach_node(ElidedNode, n, pstmt->elidedNodes)
555 : {
556 32406 : if (n->plan_node_id == plan->plan_node_id)
557 514 : elided_node = n;
558 : }
559 :
560 71997 : return elided_node;
561 : }
562 :
563 : /*
564 : * Certain plan nodes can refer to a set of RTIs. Extract and return the set.
565 : */
566 : Bitmapset *
567 377365 : pgpa_relids(Plan *plan)
568 : {
569 377365 : if (IsA(plan, Result))
570 82800 : return ((Result *) plan)->relids;
571 294565 : else if (IsA(plan, ForeignScan))
572 0 : return ((ForeignScan *) plan)->fs_relids;
573 294565 : else if (IsA(plan, Append))
574 10482 : return ((Append *) plan)->apprelids;
575 284083 : else if (IsA(plan, MergeAppend))
576 372 : return ((MergeAppend *) plan)->apprelids;
577 :
578 283711 : return NULL;
579 : }
580 :
581 : /*
582 : * Extract the scanned RTI from a plan node.
583 : *
584 : * Returns 0 if there isn't one.
585 : */
586 : Index
587 436324 : pgpa_scanrelid(Plan *plan)
588 : {
589 436324 : switch (nodeTag(plan))
590 : {
591 203598 : case T_SeqScan:
592 : case T_SampleScan:
593 : case T_BitmapHeapScan:
594 : case T_TidScan:
595 : case T_TidRangeScan:
596 : case T_SubqueryScan:
597 : case T_FunctionScan:
598 : case T_TableFuncScan:
599 : case T_ValuesScan:
600 : case T_CteScan:
601 : case T_NamedTuplestoreScan:
602 : case T_WorkTableScan:
603 : case T_ForeignScan:
604 : case T_CustomScan:
605 : case T_IndexScan:
606 : case T_IndexOnlyScan:
607 203598 : return ((Scan *) plan)->scanrelid;
608 232726 : default:
609 232726 : return 0;
610 : }
611 : }
612 :
613 : /*
614 : * Check whether a plan node is a Material node that should be treated as
615 : * a scan. Currently, this only happens when set_tablesample_rel_pathlist
616 : * inserts a Material node to protect a SampleScan that uses a non-repeatable
617 : * tablesample method.
618 : *
619 : * (Most Material nodes we're likely to encounter are actually part of the
620 : * join strategy: nested loops and merge joins can choose to materialize the
621 : * inner sides of the join. The cases identified here are the rare
622 : * exceptions.)
623 : */
624 : bool
625 128453 : pgpa_is_scan_level_materialize(Plan *plan)
626 : {
627 : Plan *child;
628 : SampleScan *sscan;
629 : TsmRoutine *tsm;
630 :
631 128453 : if (!IsA(plan, Material))
632 127359 : return false;
633 1094 : child = plan->lefttree;
634 1094 : if (child == NULL || !IsA(child, SampleScan))
635 1089 : return false;
636 5 : sscan = (SampleScan *) child;
637 5 : tsm = GetTsmRoutine(sscan->tablesample->tsmhandler);
638 5 : return !tsm->repeatable_across_scans;
639 : }
640 :
641 : /*
642 : * Construct a new Bitmapset containing non-RTE_JOIN members of 'relids'.
643 : */
644 : Bitmapset *
645 100852 : pgpa_filter_out_join_relids(Bitmapset *relids, List *rtable)
646 : {
647 100852 : int rti = -1;
648 100852 : Bitmapset *result = NULL;
649 :
650 208536 : while ((rti = bms_next_member(relids, rti)) >= 0)
651 : {
652 107684 : RangeTblEntry *rte = rt_fetch(rti, rtable);
653 :
654 107684 : if (rte->rtekind != RTE_JOIN)
655 107202 : result = bms_add_member(result, rti);
656 : }
657 :
658 100852 : return result;
659 : }
660 :
661 : /*
662 : * Create a pgpa_query_feature and add it to the list of all query features
663 : * for this plan.
664 : */
665 : static pgpa_query_feature *
666 1926 : pgpa_add_feature(pgpa_plan_walker_context *walker,
667 : pgpa_qf_type type, Plan *plan)
668 : {
669 1926 : pgpa_query_feature *qf = palloc0_object(pgpa_query_feature);
670 :
671 1926 : qf->type = type;
672 1926 : qf->plan = plan;
673 :
674 3852 : walker->query_features[qf->type] =
675 1926 : lappend(walker->query_features[qf->type], qf);
676 :
677 1926 : return qf;
678 : }
679 :
680 : /*
681 : * Add a single RTI to each active query feature.
682 : */
683 : static void
684 101799 : pgpa_qf_add_rti(List *active_query_features, Index rti)
685 : {
686 204569 : foreach_ptr(pgpa_query_feature, qf, active_query_features)
687 : {
688 971 : qf->relids = bms_add_member(qf->relids, rti);
689 : }
690 101799 : }
691 :
692 : /*
693 : * Add a set of RTIs to each active query feature.
694 : */
695 : static void
696 48438 : pgpa_qf_add_rtis(List *active_query_features, Bitmapset *relids)
697 : {
698 98039 : foreach_ptr(pgpa_query_feature, qf, active_query_features)
699 : {
700 1163 : qf->relids = bms_add_members(qf->relids, relids);
701 : }
702 48438 : }
703 :
704 : /*
705 : * Add RTIs directly contained in a plan node to each active query feature,
706 : * but filter out any join RTIs, since advice doesn't mention those.
707 : */
708 : static void
709 249978 : pgpa_qf_add_plan_rtis(List *active_query_features, Plan *plan, List *rtable)
710 : {
711 : Bitmapset *relids;
712 : Index rti;
713 :
714 249978 : if ((relids = pgpa_relids(plan)) != NULL)
715 : {
716 42842 : relids = pgpa_filter_out_join_relids(relids, rtable);
717 42842 : pgpa_qf_add_rtis(active_query_features, relids);
718 : }
719 207136 : else if ((rti = pgpa_scanrelid(plan)) != 0)
720 101799 : pgpa_qf_add_rti(active_query_features, rti);
721 249978 : }
722 :
723 : /*
724 : * If we generated plan advice using the provided walker object and array
725 : * of identifiers, would we generate the specified tag/target combination?
726 : *
727 : * If yes, the plan conforms to the advice; if no, it does not. Note that
728 : * we have no way of knowing whether the planner was forced to emit a plan
729 : * that conformed to the advice or just happened to do so.
730 : */
731 : bool
732 144305 : pgpa_walker_would_advise(pgpa_plan_walker_context *walker,
733 : pgpa_identifier *rt_identifiers,
734 : pgpa_advice_tag_type tag,
735 : pgpa_advice_target *target)
736 : {
737 144305 : Index rtable_length = list_length(walker->pstmt->rtable);
738 144305 : Bitmapset *relids = NULL;
739 :
740 144305 : if (tag == PGPA_TAG_JOIN_ORDER)
741 : {
742 15411 : foreach_ptr(pgpa_unrolled_join, ujoin, walker->toplevel_unrolled_joins)
743 : {
744 15407 : if (pgpa_walker_join_order_matches(ujoin, rtable_length,
745 : rt_identifiers, target, true))
746 11144 : return true;
747 : }
748 :
749 2 : return false;
750 : }
751 :
752 : /*
753 : * DO_NOT_SCAN advice targets rels that may not be in the flat range table
754 : * (e.g. MinMaxAgg losers), so pgpa_compute_rti_from_identifier won't work
755 : * here. Instead, check directly against the do_not_scan_identifiers list.
756 : */
757 133159 : if (tag == PGPA_TAG_DO_NOT_SCAN)
758 : {
759 430 : if (target->ttype != PGPA_TARGET_IDENTIFIER)
760 0 : return false;
761 749 : foreach_ptr(pgpa_identifier, rid, walker->do_not_scan_identifiers)
762 : {
763 747 : if (strcmp(rid->alias_name, target->rid.alias_name) == 0 &&
764 1470 : rid->occurrence == target->rid.occurrence &&
765 735 : strings_equal_or_both_null(rid->partnsp,
766 663 : target->rid.partnsp) &&
767 663 : strings_equal_or_both_null(rid->partrel,
768 590 : target->rid.partrel) &&
769 590 : strings_equal_or_both_null(rid->plan_name,
770 : target->rid.plan_name))
771 429 : return true;
772 : }
773 1 : return false;
774 : }
775 :
776 132729 : if (target->ttype == PGPA_TARGET_IDENTIFIER)
777 : {
778 : Index rti;
779 :
780 131882 : rti = pgpa_compute_rti_from_identifier(rtable_length, rt_identifiers,
781 : &target->rid);
782 131882 : if (rti == 0)
783 0 : return false;
784 131882 : relids = bms_make_singleton(rti);
785 : }
786 : else
787 : {
788 : Assert(target->ttype == PGPA_TARGET_ORDERED_LIST);
789 3601 : foreach_ptr(pgpa_advice_target, child_target, target->children)
790 : {
791 : Index rti;
792 :
793 : Assert(child_target->ttype == PGPA_TARGET_IDENTIFIER);
794 1907 : rti = pgpa_compute_rti_from_identifier(rtable_length,
795 : rt_identifiers,
796 : &child_target->rid);
797 1907 : if (rti == 0)
798 0 : return false;
799 1907 : relids = bms_add_member(relids, rti);
800 : }
801 : }
802 :
803 132729 : switch (tag)
804 : {
805 : case PGPA_TAG_JOIN_ORDER:
806 : /* should have been handled above */
807 : pg_unreachable();
808 : break;
809 : case PGPA_TAG_DO_NOT_SCAN:
810 : /* should have been handled above */
811 : pg_unreachable();
812 : break;
813 2664 : case PGPA_TAG_BITMAP_HEAP_SCAN:
814 2664 : return pgpa_walker_find_scan(walker,
815 : PGPA_SCAN_BITMAP_HEAP,
816 2664 : relids) != NULL;
817 1 : case PGPA_TAG_FOREIGN_JOIN:
818 1 : return pgpa_walker_find_scan(walker,
819 : PGPA_SCAN_FOREIGN,
820 1 : relids) != NULL;
821 1920 : case PGPA_TAG_INDEX_ONLY_SCAN:
822 : {
823 : pgpa_scan *scan;
824 :
825 1920 : scan = pgpa_walker_find_scan(walker, PGPA_SCAN_INDEX_ONLY,
826 : relids);
827 1920 : if (scan == NULL)
828 3 : return false;
829 :
830 1917 : return pgpa_walker_index_target_matches_plan(target->itarget, scan->plan);
831 : }
832 11795 : case PGPA_TAG_INDEX_SCAN:
833 : {
834 : pgpa_scan *scan;
835 :
836 11795 : scan = pgpa_walker_find_scan(walker, PGPA_SCAN_INDEX,
837 : relids);
838 11795 : if (scan == NULL)
839 2 : return false;
840 :
841 11793 : return pgpa_walker_index_target_matches_plan(target->itarget, scan->plan);
842 : }
843 2186 : case PGPA_TAG_PARTITIONWISE:
844 2186 : return pgpa_walker_find_scan(walker,
845 : PGPA_SCAN_PARTITIONWISE,
846 2186 : relids) != NULL;
847 26901 : case PGPA_TAG_SEQ_SCAN:
848 26901 : return pgpa_walker_find_scan(walker,
849 : PGPA_SCAN_SEQ,
850 26901 : relids) != NULL;
851 422 : case PGPA_TAG_TID_SCAN:
852 422 : return pgpa_walker_find_scan(walker,
853 : PGPA_SCAN_TID,
854 422 : relids) != NULL;
855 172 : case PGPA_TAG_GATHER:
856 172 : return pgpa_walker_contains_feature(walker,
857 : PGPAQF_GATHER,
858 : relids);
859 61 : case PGPA_TAG_GATHER_MERGE:
860 61 : return pgpa_walker_contains_feature(walker,
861 : PGPAQF_GATHER_MERGE,
862 : relids);
863 624 : case PGPA_TAG_SEMIJOIN_NON_UNIQUE:
864 624 : return pgpa_walker_contains_feature(walker,
865 : PGPAQF_SEMIJOIN_NON_UNIQUE,
866 : relids);
867 79 : case PGPA_TAG_SEMIJOIN_UNIQUE:
868 79 : return pgpa_walker_contains_feature(walker,
869 : PGPAQF_SEMIJOIN_UNIQUE,
870 : relids);
871 4308 : case PGPA_TAG_HASH_JOIN:
872 4308 : return pgpa_walker_contains_join(walker,
873 : JSTRAT_HASH_JOIN,
874 : relids);
875 27 : case PGPA_TAG_MERGE_JOIN_MATERIALIZE:
876 27 : return pgpa_walker_contains_join(walker,
877 : JSTRAT_MERGE_JOIN_MATERIALIZE,
878 : relids);
879 552 : case PGPA_TAG_MERGE_JOIN_PLAIN:
880 552 : return pgpa_walker_contains_join(walker,
881 : JSTRAT_MERGE_JOIN_PLAIN,
882 : relids);
883 503 : case PGPA_TAG_NESTED_LOOP_MATERIALIZE:
884 503 : return pgpa_walker_contains_join(walker,
885 : JSTRAT_NESTED_LOOP_MATERIALIZE,
886 : relids);
887 233 : case PGPA_TAG_NESTED_LOOP_MEMOIZE:
888 233 : return pgpa_walker_contains_join(walker,
889 : JSTRAT_NESTED_LOOP_MEMOIZE,
890 : relids);
891 9188 : case PGPA_TAG_NESTED_LOOP_PLAIN:
892 9188 : return pgpa_walker_contains_join(walker,
893 : JSTRAT_NESTED_LOOP_PLAIN,
894 : relids);
895 71093 : case PGPA_TAG_NO_GATHER:
896 71093 : return pgpa_walker_contains_no_gather(walker, relids);
897 : }
898 :
899 : /* should not get here */
900 0 : return false;
901 : }
902 :
903 : /*
904 : * Does the index target match the Plan?
905 : *
906 : * Should only be called when we know that itarget mandates an Index Scan or
907 : * Index Only Scan and this corresponds to the type of Plan. Here, our job is
908 : * just to check whether it's the same index.
909 : */
910 : static bool
911 13710 : pgpa_walker_index_target_matches_plan(pgpa_index_target *itarget, Plan *plan)
912 : {
913 13710 : Oid indexoid = InvalidOid;
914 :
915 : /* Retrieve the index OID from the plan. */
916 13710 : if (IsA(plan, IndexScan))
917 11793 : indexoid = ((IndexScan *) plan)->indexid;
918 1917 : else if (IsA(plan, IndexOnlyScan))
919 1917 : indexoid = ((IndexOnlyScan *) plan)->indexid;
920 : else
921 0 : elog(ERROR, "unrecognized node type: %d", (int) nodeTag(plan));
922 :
923 : /* Check whether schema name matches, if specified in index target. */
924 13710 : if (itarget->indnamespace != NULL)
925 : {
926 13699 : Oid nspoid = get_rel_namespace(indexoid);
927 13699 : char *relnamespace = get_namespace_name_or_temp(nspoid);
928 :
929 13699 : if (strcmp(itarget->indnamespace, relnamespace) != 0)
930 1 : return false;
931 : }
932 :
933 : /* Check whether relation name matches. */
934 13709 : return (strcmp(itarget->indname, get_rel_name(indexoid)) == 0);
935 : }
936 :
937 : /*
938 : * Does an unrolled join match the join order specified by an advice target?
939 : */
940 : static bool
941 15937 : pgpa_walker_join_order_matches(pgpa_unrolled_join *ujoin,
942 : Index rtable_length,
943 : pgpa_identifier *rt_identifiers,
944 : pgpa_advice_target *target,
945 : bool toplevel)
946 : {
947 15937 : int nchildren = list_length(target->children);
948 :
949 : Assert(target->ttype == PGPA_TARGET_ORDERED_LIST);
950 :
951 : /* At toplevel, we allow a prefix match. */
952 15937 : if (toplevel)
953 : {
954 15407 : if (nchildren > ujoin->ninner + 1)
955 111 : return false;
956 : }
957 : else
958 : {
959 530 : if (nchildren != ujoin->ninner + 1)
960 0 : return false;
961 : }
962 :
963 : /* Outermost rel must match. */
964 15826 : if (!pgpa_walker_join_order_matches_member(&ujoin->outer,
965 : rtable_length,
966 : rt_identifiers,
967 15826 : linitial(target->children)))
968 4151 : return false;
969 :
970 : /* Each inner rel must match. */
971 26486 : for (int n = 0; n < nchildren - 1; ++n)
972 : {
973 14812 : pgpa_advice_target *child_target = list_nth(target->children, n + 1);
974 :
975 14812 : if (!pgpa_walker_join_order_matches_member(&ujoin->inner[n],
976 : rtable_length,
977 : rt_identifiers,
978 : child_target))
979 1 : return false;
980 : }
981 :
982 11674 : return true;
983 : }
984 :
985 : /*
986 : * Does one member of an unrolled join match an advice target?
987 : */
988 : static bool
989 30638 : pgpa_walker_join_order_matches_member(pgpa_join_member *member,
990 : Index rtable_length,
991 : pgpa_identifier *rt_identifiers,
992 : pgpa_advice_target *target)
993 : {
994 30638 : Bitmapset *relids = NULL;
995 :
996 30638 : if (member->unrolled_join != NULL)
997 : {
998 531 : if (target->ttype != PGPA_TARGET_ORDERED_LIST)
999 1 : return false;
1000 530 : return pgpa_walker_join_order_matches(member->unrolled_join,
1001 : rtable_length,
1002 : rt_identifiers,
1003 : target,
1004 : false);
1005 : }
1006 :
1007 : Assert(member->scan != NULL);
1008 30107 : switch (target->ttype)
1009 : {
1010 0 : case PGPA_TARGET_ORDERED_LIST:
1011 : /* Could only match an unrolled join */
1012 0 : return false;
1013 :
1014 19 : case PGPA_TARGET_UNORDERED_LIST:
1015 : {
1016 86 : foreach_ptr(pgpa_advice_target, child_target, target->children)
1017 : {
1018 : Index rti;
1019 :
1020 48 : rti = pgpa_compute_rti_from_identifier(rtable_length,
1021 : rt_identifiers,
1022 : &child_target->rid);
1023 48 : if (rti == 0)
1024 0 : return false;
1025 48 : relids = bms_add_member(relids, rti);
1026 : }
1027 19 : break;
1028 : }
1029 :
1030 30088 : case PGPA_TARGET_IDENTIFIER:
1031 : {
1032 : Index rti;
1033 :
1034 30088 : rti = pgpa_compute_rti_from_identifier(rtable_length,
1035 : rt_identifiers,
1036 : &target->rid);
1037 30088 : if (rti == 0)
1038 0 : return false;
1039 30088 : relids = bms_make_singleton(rti);
1040 30088 : break;
1041 : }
1042 : }
1043 :
1044 30107 : return bms_equal(member->scan->relids, relids);
1045 : }
1046 :
1047 : /*
1048 : * Find the scan where the walker says that the given scan strategy should be
1049 : * used for the given relid set, if one exists.
1050 : *
1051 : * Returns the pgpa_scan object, or NULL if none was found.
1052 : */
1053 : static pgpa_scan *
1054 45889 : pgpa_walker_find_scan(pgpa_plan_walker_context *walker,
1055 : pgpa_scan_strategy strategy,
1056 : Bitmapset *relids)
1057 : {
1058 45889 : List *scans = walker->scans[strategy];
1059 :
1060 90485 : foreach_ptr(pgpa_scan, scan, scans)
1061 : {
1062 90461 : if (bms_equal(scan->relids, relids))
1063 45877 : return scan;
1064 : }
1065 :
1066 12 : return NULL;
1067 : }
1068 :
1069 : /*
1070 : * Does this walker say that the given query feature applies to the given
1071 : * relid set?
1072 : */
1073 : static bool
1074 936 : pgpa_walker_contains_feature(pgpa_plan_walker_context *walker,
1075 : pgpa_qf_type type,
1076 : Bitmapset *relids)
1077 : {
1078 936 : List *query_features = walker->query_features[type];
1079 :
1080 1058 : foreach_ptr(pgpa_query_feature, qf, query_features)
1081 : {
1082 1046 : if (bms_equal(qf->relids, relids))
1083 930 : return true;
1084 : }
1085 :
1086 6 : return false;
1087 : }
1088 :
1089 : /*
1090 : * Does the walker say that the given join strategy should be used for the
1091 : * given relid set?
1092 : */
1093 : static bool
1094 14811 : pgpa_walker_contains_join(pgpa_plan_walker_context *walker,
1095 : pgpa_join_strategy strategy,
1096 : Bitmapset *relids)
1097 : {
1098 14811 : List *join_strategies = walker->join_strategies[strategy];
1099 :
1100 25104 : foreach_ptr(Bitmapset, jsrelids, join_strategies)
1101 : {
1102 25094 : if (bms_equal(jsrelids, relids))
1103 14806 : return true;
1104 : }
1105 :
1106 5 : return false;
1107 : }
1108 :
1109 : /*
1110 : * Does the walker say that the given relids should be marked as NO_GATHER?
1111 : */
1112 : static bool
1113 71093 : pgpa_walker_contains_no_gather(pgpa_plan_walker_context *walker,
1114 : Bitmapset *relids)
1115 : {
1116 71093 : return bms_is_subset(relids, walker->no_gather_scans);
1117 : }
1118 :
1119 : /*
1120 : * Classify alternative subplans as chosen or discarded.
1121 : */
1122 : static void
1123 87144 : pgpa_classify_alternative_subplans(pgpa_plan_walker_context *walker,
1124 : List *proots,
1125 : List **chosen_proots,
1126 : List **discarded_proots)
1127 : {
1128 87144 : Bitmapset *all_scan_rtis = NULL;
1129 :
1130 : /* Initialize both output lists to empty. */
1131 87144 : *chosen_proots = NIL;
1132 87144 : *discarded_proots = NIL;
1133 :
1134 : /* Collect all scan RTIs. */
1135 784296 : for (int s = 0; s < NUM_PGPA_SCAN_STRATEGY; s++)
1136 1545315 : foreach_ptr(pgpa_scan, scan, walker->scans[s])
1137 151011 : all_scan_rtis = bms_add_members(all_scan_rtis, scan->relids);
1138 :
1139 : /* Now classify each subplan. */
1140 278568 : foreach_ptr(pgpa_planner_info, proot, proots)
1141 : {
1142 104280 : bool chosen = false;
1143 :
1144 : /*
1145 : * We're only interested in classifying subplans for which there are
1146 : * alternatives.
1147 : */
1148 104280 : if (!proot->is_alternative_plan)
1149 102912 : continue;
1150 :
1151 : /*
1152 : * A subplan has been chosen if any of its scan RTIs appear in the
1153 : * final plan. This cannot be the case if it has no RT offset.
1154 : */
1155 1368 : if (proot->has_rtoffset)
1156 : {
1157 5134 : for (int rti = 1; rti <= proot->rid_array_size; rti++)
1158 : {
1159 5857 : if (proot->rid_array[rti - 1].alias_name != NULL &&
1160 1222 : bms_is_member(proot->rtoffset + rti, all_scan_rtis))
1161 : {
1162 643 : chosen = true;
1163 643 : break;
1164 : }
1165 : }
1166 : }
1167 :
1168 : /* Add it to the correct list. */
1169 1368 : if (chosen)
1170 643 : *chosen_proots = lappend(*chosen_proots, proot);
1171 : else
1172 725 : *discarded_proots = lappend(*discarded_proots, proot);
1173 : }
1174 87144 : }
|
