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