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