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