Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * pgpa_walker.c
4 : : * Main entrypoints for analyzing a plan to generate an advice string
5 : : *
6 : : * Copyright (c) 2016-2026, PostgreSQL Global Development Group
7 : : *
8 : : * contrib/pg_plan_advice/pgpa_walker.c
9 : : *
10 : : *-------------------------------------------------------------------------
11 : : */
12 : : #include "postgres.h"
13 : :
14 : : #include "pgpa_join.h"
15 : : #include "pgpa_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
3 rhaas@postgresql.org 71 :GNC 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 : : {
3 rhaas@postgresql.org 88 :UNC 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. */
3 rhaas@postgresql.org 95 [ + + + + :GNC 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 : : {
3 rhaas@postgresql.org 105 [ # # # # :UNC 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. */
3 rhaas@postgresql.org 120 [ - + ]:GNC 14 : if (dummy)
3 rhaas@postgresql.org 121 :UNC 0 : continue;
122 : :
123 : : /* Offset each entry from the original set. */
3 rhaas@postgresql.org 124 [ + + ]:GNC 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 : :
3 rhaas@postgresql.org 155 :UNC 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 : : */
3 rhaas@postgresql.org 174 [ + + ]:GNC 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
3 rhaas@postgresql.org 183 [ # # # # ]:UNC 0 : Assert(t == PGPAQF_GATHER || t == PGPAQF_GATHER_MERGE);
184 : : }
185 : :
3 rhaas@postgresql.org 186 :GNC 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 [ + + - + ]: 519 : 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)
3 rhaas@postgresql.org 285 :UNC 0 : elided_nodes = list_truncate(elided_nodes, num_elided_nodes - 1);
286 : :
287 : : /* Build scans for all (or the remaining) elided nodes. */
3 rhaas@postgresql.org 288 [ + - + + :GNC 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;
3 rhaas@postgresql.org 415 :UNC 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;
3 rhaas@postgresql.org 440 :GNC 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 [ - + ]: 87 : 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 [ - + ]: 112 : 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 : : {
3 rhaas@postgresql.org 524 [ # # ]:UNC 0 : if (n->plan_node_id == plan->plan_node_id)
525 : 0 : elided_node = n;
526 : : }
527 : :
3 rhaas@postgresql.org 528 :GNC 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))
3 rhaas@postgresql.org 540 :UNC 0 : return ((ForeignScan *) plan)->fs_relids;
3 rhaas@postgresql.org 541 [ + + ]:GNC 615 : else if (IsA(plan, Append))
542 : 22 : return ((Append *) plan)->apprelids;
543 [ - + ]: 593 : else if (IsA(plan, MergeAppend))
3 rhaas@postgresql.org 544 :UNC 0 : return ((MergeAppend *) plan)->apprelids;
545 : :
3 rhaas@postgresql.org 546 :GNC 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 : : {
3 rhaas@postgresql.org 640 :UNC 0 : qf->relids = bms_add_members(qf->relids, relids);
641 : : }
3 rhaas@postgresql.org 642 :GNC 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)
3 rhaas@postgresql.org 699 :UNC 0 : return false;
3 rhaas@postgresql.org 700 :GNC 87 : relids = bms_make_singleton(rti);
701 : : }
702 : : else
703 : : {
704 [ - + ]: 10 : Assert(target->ttype == PGPA_TARGET_ORDERED_LIST);
705 [ + - + + : 40 : foreach_ptr(pgpa_advice_target, child_target, target->children)
+ + ]
706 : : {
707 : : Index rti;
708 : :
709 [ - + ]: 20 : 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)
3 rhaas@postgresql.org 714 :UNC 0 : return false;
3 rhaas@postgresql.org 715 :GNC 20 : relids = bms_add_member(relids, rti);
716 : : }
717 : : }
718 : :
719 [ - + + + : 97 : switch (tag)
+ + + + +
+ + + + +
+ + + + +
- ]
720 : : {
3 rhaas@postgresql.org 721 :UNC 0 : case PGPA_TAG_JOIN_ORDER:
722 : : /* should have been handled above */
723 : 0 : pg_unreachable();
724 : : break;
3 rhaas@postgresql.org 725 :GNC 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 */
3 rhaas@postgresql.org 812 :UNC 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
3 rhaas@postgresql.org 823 :GNC 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
3 rhaas@postgresql.org 833 [ # # ]:UNC 0 : elog(ERROR, "unrecognized node type: %d", (int) nodeTag(plan));
834 : :
835 : : /* Check whether schema name matches, if specified in index target. */
3 rhaas@postgresql.org 836 [ + + ]:GNC 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 [ - + ]: 17 : 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)
3 rhaas@postgresql.org 867 :UNC 0 : return false;
868 : : }
869 : : else
870 : : {
3 rhaas@postgresql.org 871 [ - + ]:GNC 1 : if (nchildren != ujoin->ninner + 1)
3 rhaas@postgresql.org 872 :UNC 0 : return false;
873 : : }
874 : :
875 : : /* Outermost rel must match. */
3 rhaas@postgresql.org 876 [ + + ]:GNC 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 [ - + ]: 33 : Assert(member->scan != NULL);
920 [ - - + - ]: 33 : switch (target->ttype)
921 : : {
3 rhaas@postgresql.org 922 :UNC 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 : :
3 rhaas@postgresql.org 942 :GNC 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)
3 rhaas@postgresql.org 950 :UNC 0 : return false;
3 rhaas@postgresql.org 951 :GNC 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 : : }
|
