Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * pathkeys.c
4 : * Utilities for matching and building path keys
5 : *
6 : * See src/backend/optimizer/README for a great deal of information about
7 : * the nature and use of path keys.
8 : *
9 : *
10 : * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
11 : * Portions Copyright (c) 1994, Regents of the University of California
12 : *
13 : * IDENTIFICATION
14 : * src/backend/optimizer/path/pathkeys.c
15 : *
16 : *-------------------------------------------------------------------------
17 : */
18 : #include "postgres.h"
19 :
20 : #include "access/stratnum.h"
21 : #include "catalog/pg_opfamily.h"
22 : #include "nodes/nodeFuncs.h"
23 : #include "optimizer/cost.h"
24 : #include "optimizer/optimizer.h"
25 : #include "optimizer/pathnode.h"
26 : #include "optimizer/paths.h"
27 : #include "partitioning/partbounds.h"
28 : #include "rewrite/rewriteManip.h"
29 : #include "utils/lsyscache.h"
30 :
31 : /* Consider reordering of GROUP BY keys? */
32 : bool enable_group_by_reordering = true;
33 :
34 : static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
35 : static bool matches_boolean_partition_clause(RestrictInfo *rinfo,
36 : RelOptInfo *partrel,
37 : int partkeycol);
38 : static Var *find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle);
39 : static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
40 :
41 :
42 : /****************************************************************************
43 : * PATHKEY CONSTRUCTION AND REDUNDANCY TESTING
44 : ****************************************************************************/
45 :
46 : /*
47 : * make_canonical_pathkey
48 : * Given the parameters for a PathKey, find any pre-existing matching
49 : * pathkey in the query's list of "canonical" pathkeys. Make a new
50 : * entry if there's not one already.
51 : *
52 : * Note that this function must not be used until after we have completed
53 : * merging EquivalenceClasses.
54 : */
55 : PathKey *
56 2100720 : make_canonical_pathkey(PlannerInfo *root,
57 : EquivalenceClass *eclass, Oid opfamily,
58 : int strategy, bool nulls_first)
59 : {
60 : PathKey *pk;
61 : ListCell *lc;
62 : MemoryContext oldcontext;
63 :
64 : /* Can't make canonical pathkeys if the set of ECs might still change */
65 2100720 : if (!root->ec_merging_done)
66 0 : elog(ERROR, "too soon to build canonical pathkeys");
67 :
68 : /* The passed eclass might be non-canonical, so chase up to the top */
69 2100720 : while (eclass->ec_merged)
70 0 : eclass = eclass->ec_merged;
71 :
72 10518426 : foreach(lc, root->canon_pathkeys)
73 : {
74 9902712 : pk = (PathKey *) lfirst(lc);
75 9902712 : if (eclass == pk->pk_eclass &&
76 1991954 : opfamily == pk->pk_opfamily &&
77 1991954 : strategy == pk->pk_strategy &&
78 1485054 : nulls_first == pk->pk_nulls_first)
79 1485006 : return pk;
80 : }
81 :
82 : /*
83 : * Be sure canonical pathkeys are allocated in the main planning context.
84 : * Not an issue in normal planning, but it is for GEQO.
85 : */
86 615714 : oldcontext = MemoryContextSwitchTo(root->planner_cxt);
87 :
88 615714 : pk = makeNode(PathKey);
89 615714 : pk->pk_eclass = eclass;
90 615714 : pk->pk_opfamily = opfamily;
91 615714 : pk->pk_strategy = strategy;
92 615714 : pk->pk_nulls_first = nulls_first;
93 :
94 615714 : root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
95 :
96 615714 : MemoryContextSwitchTo(oldcontext);
97 :
98 615714 : return pk;
99 : }
100 :
101 : /*
102 : * append_pathkeys
103 : * Append all non-redundant PathKeys in 'source' onto 'target' and
104 : * returns the updated 'target' list.
105 : */
106 : List *
107 1510 : append_pathkeys(List *target, List *source)
108 : {
109 : ListCell *lc;
110 :
111 : Assert(target != NIL);
112 :
113 3086 : foreach(lc, source)
114 : {
115 1576 : PathKey *pk = lfirst_node(PathKey, lc);
116 :
117 1576 : if (!pathkey_is_redundant(pk, target))
118 1402 : target = lappend(target, pk);
119 : }
120 1510 : return target;
121 : }
122 :
123 : /*
124 : * pathkey_is_redundant
125 : * Is a pathkey redundant with one already in the given list?
126 : *
127 : * We detect two cases:
128 : *
129 : * 1. If the new pathkey's equivalence class contains a constant, and isn't
130 : * below an outer join, then we can disregard it as a sort key. An example:
131 : * SELECT ... WHERE x = 42 ORDER BY x, y;
132 : * We may as well just sort by y. Note that because of opfamily matching,
133 : * this is semantically correct: we know that the equality constraint is one
134 : * that actually binds the variable to a single value in the terms of any
135 : * ordering operator that might go with the eclass. This rule not only lets
136 : * us simplify (or even skip) explicit sorts, but also allows matching index
137 : * sort orders to a query when there are don't-care index columns.
138 : *
139 : * 2. If the new pathkey's equivalence class is the same as that of any
140 : * existing member of the pathkey list, then it is redundant. Some examples:
141 : * SELECT ... ORDER BY x, x;
142 : * SELECT ... ORDER BY x, x DESC;
143 : * SELECT ... WHERE x = y ORDER BY x, y;
144 : * In all these cases the second sort key cannot distinguish values that are
145 : * considered equal by the first, and so there's no point in using it.
146 : * Note in particular that we need not compare opfamily (all the opfamilies
147 : * of the EC have the same notion of equality) nor sort direction.
148 : *
149 : * Both the given pathkey and the list members must be canonical for this
150 : * to work properly, but that's okay since we no longer ever construct any
151 : * non-canonical pathkeys. (Note: the notion of a pathkey *list* being
152 : * canonical includes the additional requirement of no redundant entries,
153 : * which is exactly what we are checking for here.)
154 : *
155 : * Because the equivclass.c machinery forms only one copy of any EC per query,
156 : * pointer comparison is enough to decide whether canonical ECs are the same.
157 : */
158 : static bool
159 2344644 : pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
160 : {
161 2344644 : EquivalenceClass *new_ec = new_pathkey->pk_eclass;
162 : ListCell *lc;
163 :
164 : /* Check for EC containing a constant --- unconditionally redundant */
165 2344644 : if (EC_MUST_BE_REDUNDANT(new_ec))
166 309424 : return true;
167 :
168 : /* If same EC already used in list, then redundant */
169 2462594 : foreach(lc, pathkeys)
170 : {
171 428140 : PathKey *old_pathkey = (PathKey *) lfirst(lc);
172 :
173 428140 : if (new_ec == old_pathkey->pk_eclass)
174 766 : return true;
175 : }
176 :
177 2034454 : return false;
178 : }
179 :
180 : /*
181 : * make_pathkey_from_sortinfo
182 : * Given an expression and sort-order information, create a PathKey.
183 : * The result is always a "canonical" PathKey, but it might be redundant.
184 : *
185 : * If the PathKey is being generated from a SortGroupClause, sortref should be
186 : * the SortGroupClause's SortGroupRef; otherwise zero.
187 : *
188 : * If rel is not NULL, it identifies a specific relation we're considering
189 : * a path for, and indicates that child EC members for that relation can be
190 : * considered. Otherwise child members are ignored. (See the comments for
191 : * get_eclass_for_sort_expr.)
192 : *
193 : * create_it is true if we should create any missing EquivalenceClass
194 : * needed to represent the sort key. If it's false, we return NULL if the
195 : * sort key isn't already present in any EquivalenceClass.
196 : */
197 : static PathKey *
198 1780168 : make_pathkey_from_sortinfo(PlannerInfo *root,
199 : Expr *expr,
200 : Oid opfamily,
201 : Oid opcintype,
202 : Oid collation,
203 : bool reverse_sort,
204 : bool nulls_first,
205 : Index sortref,
206 : Relids rel,
207 : bool create_it)
208 : {
209 : int16 strategy;
210 : Oid equality_op;
211 : List *opfamilies;
212 : EquivalenceClass *eclass;
213 :
214 1780168 : strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
215 :
216 : /*
217 : * EquivalenceClasses need to contain opfamily lists based on the family
218 : * membership of mergejoinable equality operators, which could belong to
219 : * more than one opfamily. So we have to look up the opfamily's equality
220 : * operator and get its membership.
221 : */
222 1780168 : equality_op = get_opfamily_member(opfamily,
223 : opcintype,
224 : opcintype,
225 : BTEqualStrategyNumber);
226 1780168 : if (!OidIsValid(equality_op)) /* shouldn't happen */
227 0 : elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
228 : BTEqualStrategyNumber, opcintype, opcintype, opfamily);
229 1780168 : opfamilies = get_mergejoin_opfamilies(equality_op);
230 1780168 : if (!opfamilies) /* certainly should find some */
231 0 : elog(ERROR, "could not find opfamilies for equality operator %u",
232 : equality_op);
233 :
234 : /* Now find or (optionally) create a matching EquivalenceClass */
235 1780168 : eclass = get_eclass_for_sort_expr(root, expr,
236 : opfamilies, opcintype, collation,
237 : sortref, rel, create_it);
238 :
239 : /* Fail if no EC and !create_it */
240 1780168 : if (!eclass)
241 589184 : return NULL;
242 :
243 : /* And finally we can find or create a PathKey node */
244 1190984 : return make_canonical_pathkey(root, eclass, opfamily,
245 : strategy, nulls_first);
246 : }
247 :
248 : /*
249 : * make_pathkey_from_sortop
250 : * Like make_pathkey_from_sortinfo, but work from a sort operator.
251 : *
252 : * This should eventually go away, but we need to restructure SortGroupClause
253 : * first.
254 : */
255 : static PathKey *
256 177292 : make_pathkey_from_sortop(PlannerInfo *root,
257 : Expr *expr,
258 : Oid ordering_op,
259 : bool reverse_sort,
260 : bool nulls_first,
261 : Index sortref,
262 : bool create_it)
263 : {
264 : Oid opfamily,
265 : opcintype,
266 : collation;
267 : int16 strategy;
268 :
269 : /* Find the operator in pg_amop --- failure shouldn't happen */
270 177292 : if (!get_ordering_op_properties(ordering_op,
271 : &opfamily, &opcintype, &strategy))
272 0 : elog(ERROR, "operator %u is not a valid ordering operator",
273 : ordering_op);
274 :
275 : /* Because SortGroupClause doesn't carry collation, consult the expr */
276 177292 : collation = exprCollation((Node *) expr);
277 :
278 177292 : return make_pathkey_from_sortinfo(root,
279 : expr,
280 : opfamily,
281 : opcintype,
282 : collation,
283 : reverse_sort,
284 : nulls_first,
285 : sortref,
286 : NULL,
287 : create_it);
288 : }
289 :
290 :
291 : /****************************************************************************
292 : * PATHKEY COMPARISONS
293 : ****************************************************************************/
294 :
295 : /*
296 : * compare_pathkeys
297 : * Compare two pathkeys to see if they are equivalent, and if not whether
298 : * one is "better" than the other.
299 : *
300 : * We assume the pathkeys are canonical, and so they can be checked for
301 : * equality by simple pointer comparison.
302 : */
303 : PathKeysComparison
304 11857898 : compare_pathkeys(List *keys1, List *keys2)
305 : {
306 : ListCell *key1,
307 : *key2;
308 :
309 : /*
310 : * Fall out quickly if we are passed two identical lists. This mostly
311 : * catches the case where both are NIL, but that's common enough to
312 : * warrant the test.
313 : */
314 11857898 : if (keys1 == keys2)
315 4329656 : return PATHKEYS_EQUAL;
316 :
317 9503682 : forboth(key1, keys1, key2, keys2)
318 : {
319 2829140 : PathKey *pathkey1 = (PathKey *) lfirst(key1);
320 2829140 : PathKey *pathkey2 = (PathKey *) lfirst(key2);
321 :
322 2829140 : if (pathkey1 != pathkey2)
323 853700 : return PATHKEYS_DIFFERENT; /* no need to keep looking */
324 : }
325 :
326 : /*
327 : * If we reached the end of only one list, the other is longer and
328 : * therefore not a subset.
329 : */
330 6674542 : if (key1 != NULL)
331 4420810 : return PATHKEYS_BETTER1; /* key1 is longer */
332 2253732 : if (key2 != NULL)
333 792194 : return PATHKEYS_BETTER2; /* key2 is longer */
334 1461538 : return PATHKEYS_EQUAL;
335 : }
336 :
337 : /*
338 : * pathkeys_contained_in
339 : * Common special case of compare_pathkeys: we just want to know
340 : * if keys2 are at least as well sorted as keys1.
341 : */
342 : bool
343 4276954 : pathkeys_contained_in(List *keys1, List *keys2)
344 : {
345 4276954 : switch (compare_pathkeys(keys1, keys2))
346 : {
347 1171834 : case PATHKEYS_EQUAL:
348 : case PATHKEYS_BETTER2:
349 1171834 : return true;
350 3105120 : default:
351 3105120 : break;
352 : }
353 3105120 : return false;
354 : }
355 :
356 : /*
357 : * group_keys_reorder_by_pathkeys
358 : * Reorder GROUP BY pathkeys and clauses to match the input pathkeys.
359 : *
360 : * 'pathkeys' is an input list of pathkeys
361 : * '*group_pathkeys' and '*group_clauses' are pathkeys and clauses lists to
362 : * reorder. The pointers are redirected to new lists, original lists
363 : * stay untouched.
364 : * 'num_groupby_pathkeys' is the number of first '*group_pathkeys' items to
365 : * search matching pathkeys.
366 : *
367 : * Returns the number of GROUP BY keys with a matching pathkey.
368 : */
369 : static int
370 164 : group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
371 : List **group_clauses,
372 : int num_groupby_pathkeys)
373 : {
374 164 : List *new_group_pathkeys = NIL,
375 164 : *new_group_clauses = NIL;
376 : List *grouping_pathkeys;
377 : ListCell *lc;
378 : int n;
379 :
380 164 : if (pathkeys == NIL || *group_pathkeys == NIL)
381 0 : return 0;
382 :
383 : /*
384 : * We're going to search within just the first num_groupby_pathkeys of
385 : * *group_pathkeys. The thing is that root->group_pathkeys is passed as
386 : * *group_pathkeys containing grouping pathkeys altogether with aggregate
387 : * pathkeys. If we process aggregate pathkeys we could get an invalid
388 : * result of get_sortgroupref_clause_noerr(), because their
389 : * pathkey->pk_eclass->ec_sortref doesn't reference query targetlist. So,
390 : * we allocate a separate list of pathkeys for lookups.
391 : */
392 164 : grouping_pathkeys = list_copy_head(*group_pathkeys, num_groupby_pathkeys);
393 :
394 : /*
395 : * Walk the pathkeys (determining ordering of the input path) and see if
396 : * there's a matching GROUP BY key. If we find one, we append it to the
397 : * list, and do the same for the clauses.
398 : *
399 : * Once we find the first pathkey without a matching GROUP BY key, the
400 : * rest of the pathkeys are useless and can't be used to evaluate the
401 : * grouping, so we abort the loop and ignore the remaining pathkeys.
402 : */
403 398 : foreach(lc, pathkeys)
404 : {
405 260 : PathKey *pathkey = (PathKey *) lfirst(lc);
406 : SortGroupClause *sgc;
407 :
408 : /*
409 : * Pathkeys are built in a way that allows simply comparing pointers.
410 : * Give up if we can't find the matching pointer. Also give up if
411 : * there is no sortclause reference for some reason.
412 : */
413 260 : if (foreach_current_index(lc) >= num_groupby_pathkeys ||
414 254 : !list_member_ptr(grouping_pathkeys, pathkey) ||
415 234 : pathkey->pk_eclass->ec_sortref == 0)
416 : break;
417 :
418 : /*
419 : * Since 1349d27 pathkey coming from underlying node can be in the
420 : * root->group_pathkeys but not in the processed_groupClause. So, we
421 : * should be careful here.
422 : */
423 234 : sgc = get_sortgroupref_clause_noerr(pathkey->pk_eclass->ec_sortref,
424 : *group_clauses);
425 234 : if (!sgc)
426 : /* The grouping clause does not cover this pathkey */
427 0 : break;
428 :
429 : /*
430 : * Sort group clause should have an ordering operator as long as there
431 : * is an associated pathkey.
432 : */
433 : Assert(OidIsValid(sgc->sortop));
434 :
435 234 : new_group_pathkeys = lappend(new_group_pathkeys, pathkey);
436 234 : new_group_clauses = lappend(new_group_clauses, sgc);
437 : }
438 :
439 : /* remember the number of pathkeys with a matching GROUP BY key */
440 164 : n = list_length(new_group_pathkeys);
441 :
442 : /* append the remaining group pathkeys (will be treated as not sorted) */
443 164 : *group_pathkeys = list_concat_unique_ptr(new_group_pathkeys,
444 : *group_pathkeys);
445 164 : *group_clauses = list_concat_unique_ptr(new_group_clauses,
446 : *group_clauses);
447 :
448 164 : list_free(grouping_pathkeys);
449 164 : return n;
450 : }
451 :
452 : /*
453 : * get_useful_group_keys_orderings
454 : * Determine which orderings of GROUP BY keys are potentially interesting.
455 : *
456 : * Returns a list of GroupByOrdering items, each representing an interesting
457 : * ordering of GROUP BY keys. Each item stores pathkeys and clauses in the
458 : * matching order.
459 : *
460 : * The function considers (and keeps) following GROUP BY orderings:
461 : *
462 : * - GROUP BY keys as ordered by preprocess_groupclause() to match target
463 : * ORDER BY clause (as much as possible),
464 : * - GROUP BY keys reordered to match 'path' ordering (as much as possible).
465 : */
466 : List *
467 49120 : get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
468 : {
469 49120 : Query *parse = root->parse;
470 49120 : List *infos = NIL;
471 : GroupByOrdering *info;
472 :
473 49120 : List *pathkeys = root->group_pathkeys;
474 49120 : List *clauses = root->processed_groupClause;
475 :
476 : /* always return at least the original pathkeys/clauses */
477 49120 : info = makeNode(GroupByOrdering);
478 49120 : info->pathkeys = pathkeys;
479 49120 : info->clauses = clauses;
480 49120 : infos = lappend(infos, info);
481 :
482 : /*
483 : * Should we try generating alternative orderings of the group keys? If
484 : * not, we produce only the order specified in the query, i.e. the
485 : * optimization is effectively disabled.
486 : */
487 49120 : if (!enable_group_by_reordering)
488 0 : return infos;
489 :
490 : /*
491 : * Grouping sets have own and more complex logic to decide the ordering.
492 : */
493 49120 : if (parse->groupingSets)
494 944 : return infos;
495 :
496 : /*
497 : * If the path is sorted in some way, try reordering the group keys to
498 : * match the path as much of the ordering as possible. Then thanks to
499 : * incremental sort we would get this sort as cheap as possible.
500 : */
501 48176 : if (path->pathkeys &&
502 3748 : !pathkeys_contained_in(path->pathkeys, root->group_pathkeys))
503 : {
504 : int n;
505 :
506 164 : n = group_keys_reorder_by_pathkeys(path->pathkeys, &pathkeys, &clauses,
507 : root->num_groupby_pathkeys);
508 :
509 164 : if (n > 0 &&
510 288 : (enable_incremental_sort || n == root->num_groupby_pathkeys) &&
511 144 : compare_pathkeys(pathkeys, root->group_pathkeys) != PATHKEYS_EQUAL)
512 : {
513 144 : info = makeNode(GroupByOrdering);
514 144 : info->pathkeys = pathkeys;
515 144 : info->clauses = clauses;
516 :
517 144 : infos = lappend(infos, info);
518 : }
519 : }
520 :
521 : #ifdef USE_ASSERT_CHECKING
522 : {
523 : GroupByOrdering *pinfo = linitial_node(GroupByOrdering, infos);
524 : ListCell *lc;
525 :
526 : /* Test consistency of info structures */
527 : for_each_from(lc, infos, 1)
528 : {
529 : ListCell *lc1,
530 : *lc2;
531 :
532 : info = lfirst_node(GroupByOrdering, lc);
533 :
534 : Assert(list_length(info->clauses) == list_length(pinfo->clauses));
535 : Assert(list_length(info->pathkeys) == list_length(pinfo->pathkeys));
536 : Assert(list_difference(info->clauses, pinfo->clauses) == NIL);
537 : Assert(list_difference_ptr(info->pathkeys, pinfo->pathkeys) == NIL);
538 :
539 : forboth(lc1, info->clauses, lc2, info->pathkeys)
540 : {
541 : SortGroupClause *sgc = lfirst_node(SortGroupClause, lc1);
542 : PathKey *pk = lfirst_node(PathKey, lc2);
543 :
544 : Assert(pk->pk_eclass->ec_sortref == sgc->tleSortGroupRef);
545 : }
546 : }
547 : }
548 : #endif
549 48176 : return infos;
550 : }
551 :
552 : /*
553 : * pathkeys_count_contained_in
554 : * Same as pathkeys_contained_in, but also sets length of longest
555 : * common prefix of keys1 and keys2.
556 : */
557 : bool
558 6201740 : pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
559 : {
560 6201740 : int n = 0;
561 : ListCell *key1,
562 : *key2;
563 :
564 : /*
565 : * See if we can avoiding looping through both lists. This optimization
566 : * gains us several percent in planning time in a worst-case test.
567 : */
568 6201740 : if (keys1 == keys2)
569 : {
570 1472532 : *n_common = list_length(keys1);
571 1472532 : return true;
572 : }
573 4729208 : else if (keys1 == NIL)
574 : {
575 1978212 : *n_common = 0;
576 1978212 : return true;
577 : }
578 2750996 : else if (keys2 == NIL)
579 : {
580 1369924 : *n_common = 0;
581 1369924 : return false;
582 : }
583 :
584 : /*
585 : * If both lists are non-empty, iterate through both to find out how many
586 : * items are shared.
587 : */
588 1732386 : forboth(key1, keys1, key2, keys2)
589 : {
590 1413480 : PathKey *pathkey1 = (PathKey *) lfirst(key1);
591 1413480 : PathKey *pathkey2 = (PathKey *) lfirst(key2);
592 :
593 1413480 : if (pathkey1 != pathkey2)
594 : {
595 1062166 : *n_common = n;
596 1062166 : return false;
597 : }
598 351314 : n++;
599 : }
600 :
601 : /* If we ended with a null value, then we've processed the whole list. */
602 318906 : *n_common = n;
603 318906 : return (key1 == NULL);
604 : }
605 :
606 : /*
607 : * get_cheapest_path_for_pathkeys
608 : * Find the cheapest path (according to the specified criterion) that
609 : * satisfies the given pathkeys and parameterization, and is parallel-safe
610 : * if required.
611 : * Return NULL if no such path.
612 : *
613 : * 'paths' is a list of possible paths that all generate the same relation
614 : * 'pathkeys' represents a required ordering (in canonical form!)
615 : * 'required_outer' denotes allowable outer relations for parameterized paths
616 : * 'cost_criterion' is STARTUP_COST or TOTAL_COST
617 : * 'require_parallel_safe' causes us to consider only parallel-safe paths
618 : */
619 : Path *
620 897128 : get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
621 : Relids required_outer,
622 : CostSelector cost_criterion,
623 : bool require_parallel_safe)
624 : {
625 897128 : Path *matched_path = NULL;
626 : ListCell *l;
627 :
628 3290330 : foreach(l, paths)
629 : {
630 2393202 : Path *path = (Path *) lfirst(l);
631 :
632 : /* If required, reject paths that are not parallel-safe */
633 2393202 : if (require_parallel_safe && !path->parallel_safe)
634 264 : continue;
635 :
636 : /*
637 : * Since cost comparison is a lot cheaper than pathkey comparison, do
638 : * that first. (XXX is that still true?)
639 : */
640 2516582 : if (matched_path != NULL &&
641 123644 : compare_path_costs(matched_path, path, cost_criterion) <= 0)
642 101878 : continue;
643 :
644 3333686 : if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
645 1042626 : bms_is_subset(PATH_REQ_OUTER(path), required_outer))
646 621612 : matched_path = path;
647 : }
648 897128 : return matched_path;
649 : }
650 :
651 : /*
652 : * get_cheapest_fractional_path_for_pathkeys
653 : * Find the cheapest path (for retrieving a specified fraction of all
654 : * the tuples) that satisfies the given pathkeys and parameterization.
655 : * Return NULL if no such path.
656 : *
657 : * See compare_fractional_path_costs() for the interpretation of the fraction
658 : * parameter.
659 : *
660 : * 'paths' is a list of possible paths that all generate the same relation
661 : * 'pathkeys' represents a required ordering (in canonical form!)
662 : * 'required_outer' denotes allowable outer relations for parameterized paths
663 : * 'fraction' is the fraction of the total tuples expected to be retrieved
664 : */
665 : Path *
666 1882 : get_cheapest_fractional_path_for_pathkeys(List *paths,
667 : List *pathkeys,
668 : Relids required_outer,
669 : double fraction)
670 : {
671 1882 : Path *matched_path = NULL;
672 : ListCell *l;
673 :
674 5286 : foreach(l, paths)
675 : {
676 3404 : Path *path = (Path *) lfirst(l);
677 :
678 : /*
679 : * Since cost comparison is a lot cheaper than pathkey comparison, do
680 : * that first. (XXX is that still true?)
681 : */
682 3786 : if (matched_path != NULL &&
683 382 : compare_fractional_path_costs(matched_path, path, fraction) <= 0)
684 196 : continue;
685 :
686 4642 : if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
687 1434 : bms_is_subset(PATH_REQ_OUTER(path), required_outer))
688 1250 : matched_path = path;
689 : }
690 1882 : return matched_path;
691 : }
692 :
693 :
694 : /*
695 : * get_cheapest_parallel_safe_total_inner
696 : * Find the unparameterized parallel-safe path with the least total cost.
697 : */
698 : Path *
699 51238 : get_cheapest_parallel_safe_total_inner(List *paths)
700 : {
701 : ListCell *l;
702 :
703 57980 : foreach(l, paths)
704 : {
705 56808 : Path *innerpath = (Path *) lfirst(l);
706 :
707 56808 : if (innerpath->parallel_safe &&
708 55084 : bms_is_empty(PATH_REQ_OUTER(innerpath)))
709 50066 : return innerpath;
710 : }
711 :
712 1172 : return NULL;
713 : }
714 :
715 : /****************************************************************************
716 : * NEW PATHKEY FORMATION
717 : ****************************************************************************/
718 :
719 : /*
720 : * build_index_pathkeys
721 : * Build a pathkeys list that describes the ordering induced by an index
722 : * scan using the given index. (Note that an unordered index doesn't
723 : * induce any ordering, so we return NIL.)
724 : *
725 : * If 'scandir' is BackwardScanDirection, build pathkeys representing a
726 : * backwards scan of the index.
727 : *
728 : * We iterate only key columns of covering indexes, since non-key columns
729 : * don't influence index ordering. The result is canonical, meaning that
730 : * redundant pathkeys are removed; it may therefore have fewer entries than
731 : * there are key columns in the index.
732 : *
733 : * Another reason for stopping early is that we may be able to tell that
734 : * an index column's sort order is uninteresting for this query. However,
735 : * that test is just based on the existence of an EquivalenceClass and not
736 : * on position in pathkey lists, so it's not complete. Caller should call
737 : * truncate_useless_pathkeys() to possibly remove more pathkeys.
738 : */
739 : List *
740 1197000 : build_index_pathkeys(PlannerInfo *root,
741 : IndexOptInfo *index,
742 : ScanDirection scandir)
743 : {
744 1197000 : List *retval = NIL;
745 : ListCell *lc;
746 : int i;
747 :
748 1197000 : if (index->sortopfamily == NULL)
749 0 : return NIL; /* non-orderable index */
750 :
751 1197000 : i = 0;
752 2179544 : foreach(lc, index->indextlist)
753 : {
754 1554908 : TargetEntry *indextle = (TargetEntry *) lfirst(lc);
755 : Expr *indexkey;
756 : bool reverse_sort;
757 : bool nulls_first;
758 : PathKey *cpathkey;
759 :
760 : /*
761 : * INCLUDE columns are stored in index unordered, so they don't
762 : * support ordered index scan.
763 : */
764 1554908 : if (i >= index->nkeycolumns)
765 0 : break;
766 :
767 : /* We assume we don't need to make a copy of the tlist item */
768 1554908 : indexkey = indextle->expr;
769 :
770 1554908 : if (ScanDirectionIsBackward(scandir))
771 : {
772 777454 : reverse_sort = !index->reverse_sort[i];
773 777454 : nulls_first = !index->nulls_first[i];
774 : }
775 : else
776 : {
777 777454 : reverse_sort = index->reverse_sort[i];
778 777454 : nulls_first = index->nulls_first[i];
779 : }
780 :
781 : /*
782 : * OK, try to make a canonical pathkey for this sort key.
783 : */
784 1554908 : cpathkey = make_pathkey_from_sortinfo(root,
785 : indexkey,
786 1554908 : index->sortopfamily[i],
787 1554908 : index->opcintype[i],
788 1554908 : index->indexcollations[i],
789 : reverse_sort,
790 : nulls_first,
791 : 0,
792 1554908 : index->rel->relids,
793 : false);
794 :
795 1554908 : if (cpathkey)
796 : {
797 : /*
798 : * We found the sort key in an EquivalenceClass, so it's relevant
799 : * for this query. Add it to list, unless it's redundant.
800 : */
801 981320 : if (!pathkey_is_redundant(cpathkey, retval))
802 706668 : retval = lappend(retval, cpathkey);
803 : }
804 : else
805 : {
806 : /*
807 : * Boolean index keys might be redundant even if they do not
808 : * appear in an EquivalenceClass, because of our special treatment
809 : * of boolean equality conditions --- see the comment for
810 : * indexcol_is_bool_constant_for_query(). If that applies, we can
811 : * continue to examine lower-order index columns. Otherwise, the
812 : * sort key is not an interesting sort order for this query, so we
813 : * should stop considering index columns; any lower-order sort
814 : * keys won't be useful either.
815 : */
816 573588 : if (!indexcol_is_bool_constant_for_query(root, index, i))
817 572364 : break;
818 : }
819 :
820 982544 : i++;
821 : }
822 :
823 1197000 : return retval;
824 : }
825 :
826 : /*
827 : * partkey_is_bool_constant_for_query
828 : *
829 : * If a partition key column is constrained to have a constant value by the
830 : * query's WHERE conditions, then it's irrelevant for sort-order
831 : * considerations. Usually that means we have a restriction clause
832 : * WHERE partkeycol = constant, which gets turned into an EquivalenceClass
833 : * containing a constant, which is recognized as redundant by
834 : * build_partition_pathkeys(). But if the partition key column is a
835 : * boolean variable (or expression), then we are not going to see such a
836 : * WHERE clause, because expression preprocessing will have simplified it
837 : * to "WHERE partkeycol" or "WHERE NOT partkeycol". So we are not going
838 : * to have a matching EquivalenceClass (unless the query also contains
839 : * "ORDER BY partkeycol"). To allow such cases to work the same as they would
840 : * for non-boolean values, this function is provided to detect whether the
841 : * specified partition key column matches a boolean restriction clause.
842 : */
843 : static bool
844 15236 : partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
845 : {
846 15236 : PartitionScheme partscheme = partrel->part_scheme;
847 : ListCell *lc;
848 :
849 : /*
850 : * If the partkey isn't boolean, we can't possibly get a match.
851 : *
852 : * Partitioning currently can only use built-in AMs, so checking for
853 : * built-in boolean opfamilies is good enough.
854 : */
855 15236 : if (!IsBuiltinBooleanOpfamily(partscheme->partopfamily[partkeycol]))
856 14756 : return false;
857 :
858 : /* Check each restriction clause for the partitioned rel */
859 792 : foreach(lc, partrel->baserestrictinfo)
860 : {
861 552 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
862 :
863 : /* Ignore pseudoconstant quals, they won't match */
864 552 : if (rinfo->pseudoconstant)
865 0 : continue;
866 :
867 : /* See if we can match the clause's expression to the partkey column */
868 552 : if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
869 240 : return true;
870 : }
871 :
872 240 : return false;
873 : }
874 :
875 : /*
876 : * matches_boolean_partition_clause
877 : * Determine if the boolean clause described by rinfo matches
878 : * partrel's partkeycol-th partition key column.
879 : *
880 : * "Matches" can be either an exact match (equivalent to partkey = true),
881 : * or a NOT above an exact match (equivalent to partkey = false).
882 : */
883 : static bool
884 552 : matches_boolean_partition_clause(RestrictInfo *rinfo,
885 : RelOptInfo *partrel, int partkeycol)
886 : {
887 552 : Node *clause = (Node *) rinfo->clause;
888 552 : Node *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
889 :
890 : /* Direct match? */
891 552 : if (equal(partexpr, clause))
892 120 : return true;
893 : /* NOT clause? */
894 432 : else if (is_notclause(clause))
895 : {
896 144 : Node *arg = (Node *) get_notclausearg((Expr *) clause);
897 :
898 144 : if (equal(partexpr, arg))
899 120 : return true;
900 : }
901 :
902 312 : return false;
903 : }
904 :
905 : /*
906 : * build_partition_pathkeys
907 : * Build a pathkeys list that describes the ordering induced by the
908 : * partitions of partrel, under either forward or backward scan
909 : * as per scandir.
910 : *
911 : * Caller must have checked that the partitions are properly ordered,
912 : * as detected by partitions_are_ordered().
913 : *
914 : * Sets *partialkeys to true if pathkeys were only built for a prefix of the
915 : * partition key, or false if the pathkeys include all columns of the
916 : * partition key.
917 : */
918 : List *
919 45440 : build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
920 : ScanDirection scandir, bool *partialkeys)
921 : {
922 45440 : List *retval = NIL;
923 45440 : PartitionScheme partscheme = partrel->part_scheme;
924 : int i;
925 :
926 : Assert(partscheme != NULL);
927 : Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
928 : /* For now, we can only cope with baserels */
929 : Assert(IS_SIMPLE_REL(partrel));
930 :
931 77720 : for (i = 0; i < partscheme->partnatts; i++)
932 : {
933 : PathKey *cpathkey;
934 47276 : Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
935 :
936 : /*
937 : * Try to make a canonical pathkey for this partkey.
938 : *
939 : * We assume the PartitionDesc lists any NULL partition last, so we
940 : * treat the scan like a NULLS LAST index: we have nulls_first for
941 : * backwards scan only.
942 : */
943 47276 : cpathkey = make_pathkey_from_sortinfo(root,
944 : keyCol,
945 47276 : partscheme->partopfamily[i],
946 47276 : partscheme->partopcintype[i],
947 47276 : partscheme->partcollation[i],
948 : ScanDirectionIsBackward(scandir),
949 : ScanDirectionIsBackward(scandir),
950 : 0,
951 : partrel->relids,
952 : false);
953 :
954 :
955 47276 : if (cpathkey)
956 : {
957 : /*
958 : * We found the sort key in an EquivalenceClass, so it's relevant
959 : * for this query. Add it to list, unless it's redundant.
960 : */
961 32040 : if (!pathkey_is_redundant(cpathkey, retval))
962 11992 : retval = lappend(retval, cpathkey);
963 : }
964 : else
965 : {
966 : /*
967 : * Boolean partition keys might be redundant even if they do not
968 : * appear in an EquivalenceClass, because of our special treatment
969 : * of boolean equality conditions --- see the comment for
970 : * partkey_is_bool_constant_for_query(). If that applies, we can
971 : * continue to examine lower-order partition keys. Otherwise, the
972 : * sort key is not an interesting sort order for this query, so we
973 : * should stop considering partition columns; any lower-order sort
974 : * keys won't be useful either.
975 : */
976 15236 : if (!partkey_is_bool_constant_for_query(partrel, i))
977 : {
978 14996 : *partialkeys = true;
979 14996 : return retval;
980 : }
981 : }
982 : }
983 :
984 30444 : *partialkeys = false;
985 30444 : return retval;
986 : }
987 :
988 : /*
989 : * build_expression_pathkey
990 : * Build a pathkeys list that describes an ordering by a single expression
991 : * using the given sort operator.
992 : *
993 : * expr and rel are as for make_pathkey_from_sortinfo.
994 : * We induce the other arguments assuming default sort order for the operator.
995 : *
996 : * Similarly to make_pathkey_from_sortinfo, the result is NIL if create_it
997 : * is false and the expression isn't already in some EquivalenceClass.
998 : */
999 : List *
1000 692 : build_expression_pathkey(PlannerInfo *root,
1001 : Expr *expr,
1002 : Oid opno,
1003 : Relids rel,
1004 : bool create_it)
1005 : {
1006 : List *pathkeys;
1007 : Oid opfamily,
1008 : opcintype;
1009 : int16 strategy;
1010 : PathKey *cpathkey;
1011 :
1012 : /* Find the operator in pg_amop --- failure shouldn't happen */
1013 692 : if (!get_ordering_op_properties(opno,
1014 : &opfamily, &opcintype, &strategy))
1015 0 : elog(ERROR, "operator %u is not a valid ordering operator",
1016 : opno);
1017 :
1018 692 : cpathkey = make_pathkey_from_sortinfo(root,
1019 : expr,
1020 : opfamily,
1021 : opcintype,
1022 : exprCollation((Node *) expr),
1023 : (strategy == BTGreaterStrategyNumber),
1024 : (strategy == BTGreaterStrategyNumber),
1025 : 0,
1026 : rel,
1027 : create_it);
1028 :
1029 692 : if (cpathkey)
1030 332 : pathkeys = list_make1(cpathkey);
1031 : else
1032 360 : pathkeys = NIL;
1033 :
1034 692 : return pathkeys;
1035 : }
1036 :
1037 : /*
1038 : * convert_subquery_pathkeys
1039 : * Build a pathkeys list that describes the ordering of a subquery's
1040 : * result, in the terms of the outer query. This is essentially a
1041 : * task of conversion.
1042 : *
1043 : * 'rel': outer query's RelOptInfo for the subquery relation.
1044 : * 'subquery_pathkeys': the subquery's output pathkeys, in its terms.
1045 : * 'subquery_tlist': the subquery's output targetlist, in its terms.
1046 : *
1047 : * We intentionally don't do truncate_useless_pathkeys() here, because there
1048 : * are situations where seeing the raw ordering of the subquery is helpful.
1049 : * For example, if it returns ORDER BY x DESC, that may prompt us to
1050 : * construct a mergejoin using DESC order rather than ASC order; but the
1051 : * right_merge_direction heuristic would have us throw the knowledge away.
1052 : */
1053 : List *
1054 49510 : convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
1055 : List *subquery_pathkeys,
1056 : List *subquery_tlist)
1057 : {
1058 49510 : List *retval = NIL;
1059 49510 : int retvallen = 0;
1060 49510 : int outer_query_keys = list_length(root->query_pathkeys);
1061 : ListCell *i;
1062 :
1063 85878 : foreach(i, subquery_pathkeys)
1064 : {
1065 38844 : PathKey *sub_pathkey = (PathKey *) lfirst(i);
1066 38844 : EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
1067 38844 : PathKey *best_pathkey = NULL;
1068 :
1069 38844 : if (sub_eclass->ec_has_volatile)
1070 : {
1071 : /*
1072 : * If the sub_pathkey's EquivalenceClass is volatile, then it must
1073 : * have come from an ORDER BY clause, and we have to match it to
1074 : * that same targetlist entry.
1075 : */
1076 : TargetEntry *tle;
1077 : Var *outer_var;
1078 :
1079 86 : if (sub_eclass->ec_sortref == 0) /* can't happen */
1080 0 : elog(ERROR, "volatile EquivalenceClass has no sortref");
1081 86 : tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
1082 : Assert(tle);
1083 : /* Is TLE actually available to the outer query? */
1084 86 : outer_var = find_var_for_subquery_tle(rel, tle);
1085 86 : if (outer_var)
1086 : {
1087 : /* We can represent this sub_pathkey */
1088 : EquivalenceMember *sub_member;
1089 : EquivalenceClass *outer_ec;
1090 :
1091 : Assert(list_length(sub_eclass->ec_members) == 1);
1092 60 : sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
1093 :
1094 : /*
1095 : * Note: it might look funny to be setting sortref = 0 for a
1096 : * reference to a volatile sub_eclass. However, the
1097 : * expression is *not* volatile in the outer query: it's just
1098 : * a Var referencing whatever the subquery emitted. (IOW, the
1099 : * outer query isn't going to re-execute the volatile
1100 : * expression itself.) So this is okay.
1101 : */
1102 : outer_ec =
1103 60 : get_eclass_for_sort_expr(root,
1104 : (Expr *) outer_var,
1105 : sub_eclass->ec_opfamilies,
1106 : sub_member->em_datatype,
1107 : sub_eclass->ec_collation,
1108 : 0,
1109 : rel->relids,
1110 : false);
1111 :
1112 : /*
1113 : * If we don't find a matching EC, sub-pathkey isn't
1114 : * interesting to the outer query
1115 : */
1116 60 : if (outer_ec)
1117 : best_pathkey =
1118 12 : make_canonical_pathkey(root,
1119 : outer_ec,
1120 : sub_pathkey->pk_opfamily,
1121 : sub_pathkey->pk_strategy,
1122 12 : sub_pathkey->pk_nulls_first);
1123 : }
1124 : }
1125 : else
1126 : {
1127 : /*
1128 : * Otherwise, the sub_pathkey's EquivalenceClass could contain
1129 : * multiple elements (representing knowledge that multiple items
1130 : * are effectively equal). Each element might match none, one, or
1131 : * more of the output columns that are visible to the outer query.
1132 : * This means we may have multiple possible representations of the
1133 : * sub_pathkey in the context of the outer query. Ideally we
1134 : * would generate them all and put them all into an EC of the
1135 : * outer query, thereby propagating equality knowledge up to the
1136 : * outer query. Right now we cannot do so, because the outer
1137 : * query's EquivalenceClasses are already frozen when this is
1138 : * called. Instead we prefer the one that has the highest "score"
1139 : * (number of EC peers, plus one if it matches the outer
1140 : * query_pathkeys). This is the most likely to be useful in the
1141 : * outer query.
1142 : */
1143 38758 : int best_score = -1;
1144 : ListCell *j;
1145 :
1146 78788 : foreach(j, sub_eclass->ec_members)
1147 : {
1148 40030 : EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
1149 40030 : Expr *sub_expr = sub_member->em_expr;
1150 40030 : Oid sub_expr_type = sub_member->em_datatype;
1151 40030 : Oid sub_expr_coll = sub_eclass->ec_collation;
1152 : ListCell *k;
1153 :
1154 40030 : if (sub_member->em_is_child)
1155 1204 : continue; /* ignore children here */
1156 :
1157 221676 : foreach(k, subquery_tlist)
1158 : {
1159 182850 : TargetEntry *tle = (TargetEntry *) lfirst(k);
1160 : Var *outer_var;
1161 : Expr *tle_expr;
1162 : EquivalenceClass *outer_ec;
1163 : PathKey *outer_pk;
1164 : int score;
1165 :
1166 : /* Is TLE actually available to the outer query? */
1167 182850 : outer_var = find_var_for_subquery_tle(rel, tle);
1168 182850 : if (!outer_var)
1169 38148 : continue;
1170 :
1171 : /*
1172 : * The targetlist entry is considered to match if it
1173 : * matches after sort-key canonicalization. That is
1174 : * needed since the sub_expr has been through the same
1175 : * process.
1176 : */
1177 144702 : tle_expr = canonicalize_ec_expression(tle->expr,
1178 : sub_expr_type,
1179 : sub_expr_coll);
1180 144702 : if (!equal(tle_expr, sub_expr))
1181 107080 : continue;
1182 :
1183 : /* See if we have a matching EC for the TLE */
1184 37622 : outer_ec = get_eclass_for_sort_expr(root,
1185 : (Expr *) outer_var,
1186 : sub_eclass->ec_opfamilies,
1187 : sub_expr_type,
1188 : sub_expr_coll,
1189 : 0,
1190 : rel->relids,
1191 : false);
1192 :
1193 : /*
1194 : * If we don't find a matching EC, this sub-pathkey isn't
1195 : * interesting to the outer query
1196 : */
1197 37622 : if (!outer_ec)
1198 1250 : continue;
1199 :
1200 36372 : outer_pk = make_canonical_pathkey(root,
1201 : outer_ec,
1202 : sub_pathkey->pk_opfamily,
1203 : sub_pathkey->pk_strategy,
1204 36372 : sub_pathkey->pk_nulls_first);
1205 : /* score = # of equivalence peers */
1206 36372 : score = list_length(outer_ec->ec_members) - 1;
1207 : /* +1 if it matches the proper query_pathkeys item */
1208 72464 : if (retvallen < outer_query_keys &&
1209 36092 : list_nth(root->query_pathkeys, retvallen) == outer_pk)
1210 34410 : score++;
1211 36372 : if (score > best_score)
1212 : {
1213 36356 : best_pathkey = outer_pk;
1214 36356 : best_score = score;
1215 : }
1216 : }
1217 : }
1218 : }
1219 :
1220 : /*
1221 : * If we couldn't find a representation of this sub_pathkey, we're
1222 : * done (we can't use the ones to its right, either).
1223 : */
1224 38844 : if (!best_pathkey)
1225 2476 : break;
1226 :
1227 : /*
1228 : * Eliminate redundant ordering info; could happen if outer query
1229 : * equivalences subquery keys...
1230 : */
1231 36368 : if (!pathkey_is_redundant(best_pathkey, retval))
1232 : {
1233 36356 : retval = lappend(retval, best_pathkey);
1234 36356 : retvallen++;
1235 : }
1236 : }
1237 :
1238 49510 : return retval;
1239 : }
1240 :
1241 : /*
1242 : * find_var_for_subquery_tle
1243 : *
1244 : * If the given subquery tlist entry is due to be emitted by the subquery's
1245 : * scan node, return a Var for it, else return NULL.
1246 : *
1247 : * We need this to ensure that we don't return pathkeys describing values
1248 : * that are unavailable above the level of the subquery scan.
1249 : */
1250 : static Var *
1251 182936 : find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
1252 : {
1253 : ListCell *lc;
1254 :
1255 : /* If the TLE is resjunk, it's certainly not visible to the outer query */
1256 182936 : if (tle->resjunk)
1257 0 : return NULL;
1258 :
1259 : /* Search the rel's targetlist to see what it will return */
1260 1113978 : foreach(lc, rel->reltarget->exprs)
1261 : {
1262 1075804 : Var *var = (Var *) lfirst(lc);
1263 :
1264 : /* Ignore placeholders */
1265 1075804 : if (!IsA(var, Var))
1266 53276 : continue;
1267 : Assert(var->varno == rel->relid);
1268 :
1269 : /* If we find a Var referencing this TLE, we're good */
1270 1022528 : if (var->varattno == tle->resno)
1271 144762 : return copyObject(var); /* Make a copy for safety */
1272 : }
1273 38174 : return NULL;
1274 : }
1275 :
1276 : /*
1277 : * build_join_pathkeys
1278 : * Build the path keys for a join relation constructed by mergejoin or
1279 : * nestloop join. This is normally the same as the outer path's keys.
1280 : *
1281 : * EXCEPTION: in a FULL, RIGHT or RIGHT_ANTI join, we cannot treat the
1282 : * result as having the outer path's path keys, because null lefthand rows
1283 : * may be inserted at random points. It must be treated as unsorted.
1284 : *
1285 : * We truncate away any pathkeys that are uninteresting for higher joins.
1286 : *
1287 : * 'joinrel' is the join relation that paths are being formed for
1288 : * 'jointype' is the join type (inner, left, full, etc)
1289 : * 'outer_pathkeys' is the list of the current outer path's path keys
1290 : *
1291 : * Returns the list of new path keys.
1292 : */
1293 : List *
1294 1795344 : build_join_pathkeys(PlannerInfo *root,
1295 : RelOptInfo *joinrel,
1296 : JoinType jointype,
1297 : List *outer_pathkeys)
1298 : {
1299 : /* RIGHT_SEMI should not come here */
1300 : Assert(jointype != JOIN_RIGHT_SEMI);
1301 :
1302 1795344 : if (jointype == JOIN_FULL ||
1303 1547404 : jointype == JOIN_RIGHT ||
1304 : jointype == JOIN_RIGHT_ANTI)
1305 263640 : return NIL;
1306 :
1307 : /*
1308 : * This used to be quite a complex bit of code, but now that all pathkey
1309 : * sublists start out life canonicalized, we don't have to do a darn thing
1310 : * here!
1311 : *
1312 : * We do, however, need to truncate the pathkeys list, since it may
1313 : * contain pathkeys that were useful for forming this joinrel but are
1314 : * uninteresting to higher levels.
1315 : */
1316 1531704 : return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1317 : }
1318 :
1319 : /****************************************************************************
1320 : * PATHKEYS AND SORT CLAUSES
1321 : ****************************************************************************/
1322 :
1323 : /*
1324 : * make_pathkeys_for_sortclauses
1325 : * Generate a pathkeys list that represents the sort order specified
1326 : * by a list of SortGroupClauses
1327 : *
1328 : * The resulting PathKeys are always in canonical form. (Actually, there
1329 : * is no longer any code anywhere that creates non-canonical PathKeys.)
1330 : *
1331 : * 'sortclauses' is a list of SortGroupClause nodes
1332 : * 'tlist' is the targetlist to find the referenced tlist entries in
1333 : */
1334 : List *
1335 553766 : make_pathkeys_for_sortclauses(PlannerInfo *root,
1336 : List *sortclauses,
1337 : List *tlist)
1338 : {
1339 : List *result;
1340 : bool sortable;
1341 :
1342 553766 : result = make_pathkeys_for_sortclauses_extended(root,
1343 : &sortclauses,
1344 : tlist,
1345 : false,
1346 : false,
1347 : &sortable,
1348 : false);
1349 : /* It's caller error if not all clauses were sortable */
1350 : Assert(sortable);
1351 553766 : return result;
1352 : }
1353 :
1354 : /*
1355 : * make_pathkeys_for_sortclauses_extended
1356 : * Generate a pathkeys list that represents the sort order specified
1357 : * by a list of SortGroupClauses
1358 : *
1359 : * The comments for make_pathkeys_for_sortclauses apply here too. In addition:
1360 : *
1361 : * If remove_redundant is true, then any sort clauses that are found to
1362 : * give rise to redundant pathkeys are removed from the sortclauses list
1363 : * (which therefore must be pass-by-reference in this version).
1364 : *
1365 : * If remove_group_rtindex is true, then we need to remove the RT index of the
1366 : * grouping step from the sort expressions before we make PathKeys for them.
1367 : *
1368 : * *sortable is set to true if all the sort clauses are in fact sortable.
1369 : * If any are not, they are ignored except for setting *sortable false.
1370 : * (In that case, the output pathkey list isn't really useful. However,
1371 : * we process the whole sortclauses list anyway, because it's still valid
1372 : * to remove any clauses that can be proven redundant via the eclass logic.
1373 : * Even though we'll have to hash in that case, we might as well not hash
1374 : * redundant columns.)
1375 : *
1376 : * If set_ec_sortref is true then sets the value of the pathkey's
1377 : * EquivalenceClass unless it's already initialized.
1378 : */
1379 : List *
1380 576292 : make_pathkeys_for_sortclauses_extended(PlannerInfo *root,
1381 : List **sortclauses,
1382 : List *tlist,
1383 : bool remove_redundant,
1384 : bool remove_group_rtindex,
1385 : bool *sortable,
1386 : bool set_ec_sortref)
1387 : {
1388 576292 : List *pathkeys = NIL;
1389 : ListCell *l;
1390 :
1391 576292 : *sortable = true;
1392 753774 : foreach(l, *sortclauses)
1393 : {
1394 177482 : SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1395 : Expr *sortkey;
1396 : PathKey *pathkey;
1397 :
1398 177482 : sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1399 177482 : if (!OidIsValid(sortcl->sortop))
1400 : {
1401 190 : *sortable = false;
1402 190 : continue;
1403 : }
1404 177292 : if (remove_group_rtindex)
1405 : {
1406 : Assert(root->group_rtindex > 0);
1407 : sortkey = (Expr *)
1408 1412 : remove_nulling_relids((Node *) sortkey,
1409 1412 : bms_make_singleton(root->group_rtindex),
1410 : NULL);
1411 : }
1412 177292 : pathkey = make_pathkey_from_sortop(root,
1413 : sortkey,
1414 : sortcl->sortop,
1415 177292 : sortcl->reverse_sort,
1416 177292 : sortcl->nulls_first,
1417 : sortcl->tleSortGroupRef,
1418 : true);
1419 177292 : if (pathkey->pk_eclass->ec_sortref == 0 && set_ec_sortref)
1420 : {
1421 : /*
1422 : * Copy the sortref if it hasn't been set yet. That may happen if
1423 : * the EquivalenceClass was constructed from a WHERE clause, i.e.
1424 : * it doesn't have a target reference at all.
1425 : */
1426 554 : pathkey->pk_eclass->ec_sortref = sortcl->tleSortGroupRef;
1427 : }
1428 :
1429 : /* Canonical form eliminates redundant ordering keys */
1430 177292 : if (!pathkey_is_redundant(pathkey, pathkeys))
1431 162150 : pathkeys = lappend(pathkeys, pathkey);
1432 15142 : else if (remove_redundant)
1433 660 : *sortclauses = foreach_delete_current(*sortclauses, l);
1434 : }
1435 576292 : return pathkeys;
1436 : }
1437 :
1438 : /****************************************************************************
1439 : * PATHKEYS AND MERGECLAUSES
1440 : ****************************************************************************/
1441 :
1442 : /*
1443 : * initialize_mergeclause_eclasses
1444 : * Set the EquivalenceClass links in a mergeclause restrictinfo.
1445 : *
1446 : * RestrictInfo contains fields in which we may cache pointers to
1447 : * EquivalenceClasses for the left and right inputs of the mergeclause.
1448 : * (If the mergeclause is a true equivalence clause these will be the
1449 : * same EquivalenceClass, otherwise not.) If the mergeclause is either
1450 : * used to generate an EquivalenceClass, or derived from an EquivalenceClass,
1451 : * then it's easy to set up the left_ec and right_ec members --- otherwise,
1452 : * this function should be called to set them up. We will generate new
1453 : * EquivalenceClauses if necessary to represent the mergeclause's left and
1454 : * right sides.
1455 : *
1456 : * Note this is called before EC merging is complete, so the links won't
1457 : * necessarily point to canonical ECs. Before they are actually used for
1458 : * anything, update_mergeclause_eclasses must be called to ensure that
1459 : * they've been updated to point to canonical ECs.
1460 : */
1461 : void
1462 54240 : initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
1463 : {
1464 54240 : Expr *clause = restrictinfo->clause;
1465 : Oid lefttype,
1466 : righttype;
1467 :
1468 : /* Should be a mergeclause ... */
1469 : Assert(restrictinfo->mergeopfamilies != NIL);
1470 : /* ... with links not yet set */
1471 : Assert(restrictinfo->left_ec == NULL);
1472 : Assert(restrictinfo->right_ec == NULL);
1473 :
1474 : /* Need the declared input types of the operator */
1475 54240 : op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1476 :
1477 : /* Find or create a matching EquivalenceClass for each side */
1478 54240 : restrictinfo->left_ec =
1479 54240 : get_eclass_for_sort_expr(root,
1480 54240 : (Expr *) get_leftop(clause),
1481 : restrictinfo->mergeopfamilies,
1482 : lefttype,
1483 : ((OpExpr *) clause)->inputcollid,
1484 : 0,
1485 : NULL,
1486 : true);
1487 54240 : restrictinfo->right_ec =
1488 54240 : get_eclass_for_sort_expr(root,
1489 54240 : (Expr *) get_rightop(clause),
1490 : restrictinfo->mergeopfamilies,
1491 : righttype,
1492 : ((OpExpr *) clause)->inputcollid,
1493 : 0,
1494 : NULL,
1495 : true);
1496 54240 : }
1497 :
1498 : /*
1499 : * update_mergeclause_eclasses
1500 : * Make the cached EquivalenceClass links valid in a mergeclause
1501 : * restrictinfo.
1502 : *
1503 : * These pointers should have been set by process_equivalence or
1504 : * initialize_mergeclause_eclasses, but they might have been set to
1505 : * non-canonical ECs that got merged later. Chase up to the canonical
1506 : * merged parent if so.
1507 : */
1508 : void
1509 4643482 : update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
1510 : {
1511 : /* Should be a merge clause ... */
1512 : Assert(restrictinfo->mergeopfamilies != NIL);
1513 : /* ... with pointers already set */
1514 : Assert(restrictinfo->left_ec != NULL);
1515 : Assert(restrictinfo->right_ec != NULL);
1516 :
1517 : /* Chase up to the top as needed */
1518 4643482 : while (restrictinfo->left_ec->ec_merged)
1519 0 : restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
1520 4643482 : while (restrictinfo->right_ec->ec_merged)
1521 0 : restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
1522 4643482 : }
1523 :
1524 : /*
1525 : * find_mergeclauses_for_outer_pathkeys
1526 : * This routine attempts to find a list of mergeclauses that can be
1527 : * used with a specified ordering for the join's outer relation.
1528 : * If successful, it returns a list of mergeclauses.
1529 : *
1530 : * 'pathkeys' is a pathkeys list showing the ordering of an outer-rel path.
1531 : * 'restrictinfos' is a list of mergejoinable restriction clauses for the
1532 : * join relation being formed, in no particular order.
1533 : *
1534 : * The restrictinfos must be marked (via outer_is_left) to show which side
1535 : * of each clause is associated with the current outer path. (See
1536 : * select_mergejoin_clauses())
1537 : *
1538 : * The result is NIL if no merge can be done, else a maximal list of
1539 : * usable mergeclauses (represented as a list of their restrictinfo nodes).
1540 : * The list is ordered to match the pathkeys, as required for execution.
1541 : */
1542 : List *
1543 1762836 : find_mergeclauses_for_outer_pathkeys(PlannerInfo *root,
1544 : List *pathkeys,
1545 : List *restrictinfos)
1546 : {
1547 1762836 : List *mergeclauses = NIL;
1548 : ListCell *i;
1549 :
1550 : /* make sure we have eclasses cached in the clauses */
1551 3670464 : foreach(i, restrictinfos)
1552 : {
1553 1907628 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1554 :
1555 1907628 : update_mergeclause_eclasses(root, rinfo);
1556 : }
1557 :
1558 2887302 : foreach(i, pathkeys)
1559 : {
1560 1363818 : PathKey *pathkey = (PathKey *) lfirst(i);
1561 1363818 : EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1562 1363818 : List *matched_restrictinfos = NIL;
1563 : ListCell *j;
1564 :
1565 : /*----------
1566 : * A mergejoin clause matches a pathkey if it has the same EC.
1567 : * If there are multiple matching clauses, take them all. In plain
1568 : * inner-join scenarios we expect only one match, because
1569 : * equivalence-class processing will have removed any redundant
1570 : * mergeclauses. However, in outer-join scenarios there might be
1571 : * multiple matches. An example is
1572 : *
1573 : * select * from a full join b
1574 : * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1575 : *
1576 : * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1577 : * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1578 : * we *must* do so or we will be unable to form a valid plan.
1579 : *
1580 : * We expect that the given pathkeys list is canonical, which means
1581 : * no two members have the same EC, so it's not possible for this
1582 : * code to enter the same mergeclause into the result list twice.
1583 : *
1584 : * It's possible that multiple matching clauses might have different
1585 : * ECs on the other side, in which case the order we put them into our
1586 : * result makes a difference in the pathkeys required for the inner
1587 : * input rel. However this routine hasn't got any info about which
1588 : * order would be best, so we don't worry about that.
1589 : *
1590 : * It's also possible that the selected mergejoin clauses produce
1591 : * a noncanonical ordering of pathkeys for the inner side, ie, we
1592 : * might select clauses that reference b.v1, b.v2, b.v1 in that
1593 : * order. This is not harmful in itself, though it suggests that
1594 : * the clauses are partially redundant. Since the alternative is
1595 : * to omit mergejoin clauses and thereby possibly fail to generate a
1596 : * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1597 : * has to delete duplicates when it constructs the inner pathkeys
1598 : * list, and we also have to deal with such cases specially in
1599 : * create_mergejoin_plan().
1600 : *----------
1601 : */
1602 3080108 : foreach(j, restrictinfos)
1603 : {
1604 1716290 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1605 : EquivalenceClass *clause_ec;
1606 :
1607 3432580 : clause_ec = rinfo->outer_is_left ?
1608 1716290 : rinfo->left_ec : rinfo->right_ec;
1609 1716290 : if (clause_ec == pathkey_ec)
1610 1124580 : matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1611 : }
1612 :
1613 : /*
1614 : * If we didn't find a mergeclause, we're done --- any additional
1615 : * sort-key positions in the pathkeys are useless. (But we can still
1616 : * mergejoin if we found at least one mergeclause.)
1617 : */
1618 1363818 : if (matched_restrictinfos == NIL)
1619 239352 : break;
1620 :
1621 : /*
1622 : * If we did find usable mergeclause(s) for this sort-key position,
1623 : * add them to result list.
1624 : */
1625 1124466 : mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1626 : }
1627 :
1628 1762836 : return mergeclauses;
1629 : }
1630 :
1631 : /*
1632 : * select_outer_pathkeys_for_merge
1633 : * Builds a pathkey list representing a possible sort ordering
1634 : * that can be used with the given mergeclauses.
1635 : *
1636 : * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
1637 : * that will be used in a merge join.
1638 : * 'joinrel' is the join relation we are trying to construct.
1639 : *
1640 : * The restrictinfos must be marked (via outer_is_left) to show which side
1641 : * of each clause is associated with the current outer path. (See
1642 : * select_mergejoin_clauses())
1643 : *
1644 : * Returns a pathkeys list that can be applied to the outer relation.
1645 : *
1646 : * Since we assume here that a sort is required, there is no particular use
1647 : * in matching any available ordering of the outerrel. (joinpath.c has an
1648 : * entirely separate code path for considering sort-free mergejoins.) Rather,
1649 : * it's interesting to try to match, or match a prefix of the requested
1650 : * query_pathkeys so that a second output sort may be avoided or an
1651 : * incremental sort may be done instead. We can get away with just a prefix
1652 : * of the query_pathkeys when that prefix covers the entire join condition.
1653 : * Failing that, we try to list "more popular" keys (those with the most
1654 : * unmatched EquivalenceClass peers) earlier, in hopes of making the resulting
1655 : * ordering useful for as many higher-level mergejoins as possible.
1656 : */
1657 : List *
1658 505360 : select_outer_pathkeys_for_merge(PlannerInfo *root,
1659 : List *mergeclauses,
1660 : RelOptInfo *joinrel)
1661 : {
1662 505360 : List *pathkeys = NIL;
1663 505360 : int nClauses = list_length(mergeclauses);
1664 : EquivalenceClass **ecs;
1665 : int *scores;
1666 : int necs;
1667 : ListCell *lc;
1668 : int j;
1669 :
1670 : /* Might have no mergeclauses */
1671 505360 : if (nClauses == 0)
1672 0 : return NIL;
1673 :
1674 : /*
1675 : * Make arrays of the ECs used by the mergeclauses (dropping any
1676 : * duplicates) and their "popularity" scores.
1677 : */
1678 505360 : ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
1679 505360 : scores = (int *) palloc(nClauses * sizeof(int));
1680 505360 : necs = 0;
1681 :
1682 1069074 : foreach(lc, mergeclauses)
1683 : {
1684 563714 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1685 : EquivalenceClass *oeclass;
1686 : int score;
1687 : ListCell *lc2;
1688 :
1689 : /* get the outer eclass */
1690 563714 : update_mergeclause_eclasses(root, rinfo);
1691 :
1692 563714 : if (rinfo->outer_is_left)
1693 283988 : oeclass = rinfo->left_ec;
1694 : else
1695 279726 : oeclass = rinfo->right_ec;
1696 :
1697 : /* reject duplicates */
1698 624842 : for (j = 0; j < necs; j++)
1699 : {
1700 61194 : if (ecs[j] == oeclass)
1701 66 : break;
1702 : }
1703 563714 : if (j < necs)
1704 66 : continue;
1705 :
1706 : /* compute score */
1707 563648 : score = 0;
1708 1762180 : foreach(lc2, oeclass->ec_members)
1709 : {
1710 1198532 : EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
1711 :
1712 : /* Potential future join partner? */
1713 1198532 : if (!em->em_is_const && !em->em_is_child &&
1714 1058882 : !bms_overlap(em->em_relids, joinrel->relids))
1715 82290 : score++;
1716 : }
1717 :
1718 563648 : ecs[necs] = oeclass;
1719 563648 : scores[necs] = score;
1720 563648 : necs++;
1721 : }
1722 :
1723 : /*
1724 : * Find out if we have all the ECs mentioned in query_pathkeys; if so we
1725 : * can generate a sort order that's also useful for final output. If we
1726 : * only have a prefix of the query_pathkeys, and that prefix is the entire
1727 : * join condition, then it's useful to use the prefix as the pathkeys as
1728 : * this increases the chances that an incremental sort will be able to be
1729 : * used by the upper planner.
1730 : */
1731 505360 : if (root->query_pathkeys)
1732 : {
1733 319542 : int matches = 0;
1734 :
1735 379782 : foreach(lc, root->query_pathkeys)
1736 : {
1737 364574 : PathKey *query_pathkey = (PathKey *) lfirst(lc);
1738 364574 : EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1739 :
1740 703182 : for (j = 0; j < necs; j++)
1741 : {
1742 398848 : if (ecs[j] == query_ec)
1743 60240 : break; /* found match */
1744 : }
1745 364574 : if (j >= necs)
1746 304334 : break; /* didn't find match */
1747 :
1748 60240 : matches++;
1749 : }
1750 : /* if we got to the end of the list, we have them all */
1751 319542 : if (lc == NULL)
1752 : {
1753 : /* copy query_pathkeys as starting point for our output */
1754 15208 : pathkeys = list_copy(root->query_pathkeys);
1755 : /* mark their ECs as already-emitted */
1756 31174 : foreach(lc, root->query_pathkeys)
1757 : {
1758 15966 : PathKey *query_pathkey = (PathKey *) lfirst(lc);
1759 15966 : EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1760 :
1761 16850 : for (j = 0; j < necs; j++)
1762 : {
1763 16850 : if (ecs[j] == query_ec)
1764 : {
1765 15966 : scores[j] = -1;
1766 15966 : break;
1767 : }
1768 : }
1769 : }
1770 : }
1771 :
1772 : /*
1773 : * If we didn't match to all of the query_pathkeys, but did match to
1774 : * all of the join clauses then we'll make use of these as partially
1775 : * sorted input is better than nothing for the upper planner as it may
1776 : * lead to incremental sorts instead of full sorts.
1777 : */
1778 304334 : else if (matches == nClauses)
1779 : {
1780 36440 : pathkeys = list_copy_head(root->query_pathkeys, matches);
1781 :
1782 : /* we have all of the join pathkeys, so nothing more to do */
1783 36440 : pfree(ecs);
1784 36440 : pfree(scores);
1785 :
1786 36440 : return pathkeys;
1787 : }
1788 : }
1789 :
1790 : /*
1791 : * Add remaining ECs to the list in popularity order, using a default sort
1792 : * ordering. (We could use qsort() here, but the list length is usually
1793 : * so small it's not worth it.)
1794 : */
1795 : for (;;)
1796 511230 : {
1797 : int best_j;
1798 : int best_score;
1799 : EquivalenceClass *ec;
1800 : PathKey *pathkey;
1801 :
1802 980150 : best_j = 0;
1803 980150 : best_score = scores[0];
1804 1156298 : for (j = 1; j < necs; j++)
1805 : {
1806 176148 : if (scores[j] > best_score)
1807 : {
1808 57410 : best_j = j;
1809 57410 : best_score = scores[j];
1810 : }
1811 : }
1812 980150 : if (best_score < 0)
1813 468920 : break; /* all done */
1814 511230 : ec = ecs[best_j];
1815 511230 : scores[best_j] = -1;
1816 511230 : pathkey = make_canonical_pathkey(root,
1817 : ec,
1818 511230 : linitial_oid(ec->ec_opfamilies),
1819 : BTLessStrategyNumber,
1820 : false);
1821 : /* can't be redundant because no duplicate ECs */
1822 : Assert(!pathkey_is_redundant(pathkey, pathkeys));
1823 511230 : pathkeys = lappend(pathkeys, pathkey);
1824 : }
1825 :
1826 468920 : pfree(ecs);
1827 468920 : pfree(scores);
1828 :
1829 468920 : return pathkeys;
1830 : }
1831 :
1832 : /*
1833 : * make_inner_pathkeys_for_merge
1834 : * Builds a pathkey list representing the explicit sort order that
1835 : * must be applied to an inner path to make it usable with the
1836 : * given mergeclauses.
1837 : *
1838 : * 'mergeclauses' is a list of RestrictInfos for the mergejoin clauses
1839 : * that will be used in a merge join, in order.
1840 : * 'outer_pathkeys' are the already-known canonical pathkeys for the outer
1841 : * side of the join.
1842 : *
1843 : * The restrictinfos must be marked (via outer_is_left) to show which side
1844 : * of each clause is associated with the current outer path. (See
1845 : * select_mergejoin_clauses())
1846 : *
1847 : * Returns a pathkeys list that can be applied to the inner relation.
1848 : *
1849 : * Note that it is not this routine's job to decide whether sorting is
1850 : * actually needed for a particular input path. Assume a sort is necessary;
1851 : * just make the keys, eh?
1852 : */
1853 : List *
1854 968824 : make_inner_pathkeys_for_merge(PlannerInfo *root,
1855 : List *mergeclauses,
1856 : List *outer_pathkeys)
1857 : {
1858 968824 : List *pathkeys = NIL;
1859 : EquivalenceClass *lastoeclass;
1860 : PathKey *opathkey;
1861 : ListCell *lc;
1862 : ListCell *lop;
1863 :
1864 968824 : lastoeclass = NULL;
1865 968824 : opathkey = NULL;
1866 968824 : lop = list_head(outer_pathkeys);
1867 :
1868 2084872 : foreach(lc, mergeclauses)
1869 : {
1870 1116048 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1871 : EquivalenceClass *oeclass;
1872 : EquivalenceClass *ieclass;
1873 : PathKey *pathkey;
1874 :
1875 1116048 : update_mergeclause_eclasses(root, rinfo);
1876 :
1877 1116048 : if (rinfo->outer_is_left)
1878 : {
1879 590736 : oeclass = rinfo->left_ec;
1880 590736 : ieclass = rinfo->right_ec;
1881 : }
1882 : else
1883 : {
1884 525312 : oeclass = rinfo->right_ec;
1885 525312 : ieclass = rinfo->left_ec;
1886 : }
1887 :
1888 : /* outer eclass should match current or next pathkeys */
1889 : /* we check this carefully for debugging reasons */
1890 1116048 : if (oeclass != lastoeclass)
1891 : {
1892 1115946 : if (!lop)
1893 0 : elog(ERROR, "too few pathkeys for mergeclauses");
1894 1115946 : opathkey = (PathKey *) lfirst(lop);
1895 1115946 : lop = lnext(outer_pathkeys, lop);
1896 1115946 : lastoeclass = opathkey->pk_eclass;
1897 1115946 : if (oeclass != lastoeclass)
1898 0 : elog(ERROR, "outer pathkeys do not match mergeclause");
1899 : }
1900 :
1901 : /*
1902 : * Often, we'll have same EC on both sides, in which case the outer
1903 : * pathkey is also canonical for the inner side, and we can skip a
1904 : * useless search.
1905 : */
1906 1116048 : if (ieclass == oeclass)
1907 754564 : pathkey = opathkey;
1908 : else
1909 361484 : pathkey = make_canonical_pathkey(root,
1910 : ieclass,
1911 : opathkey->pk_opfamily,
1912 : opathkey->pk_strategy,
1913 361484 : opathkey->pk_nulls_first);
1914 :
1915 : /*
1916 : * Don't generate redundant pathkeys (which can happen if multiple
1917 : * mergeclauses refer to the same EC). Because we do this, the output
1918 : * pathkey list isn't necessarily ordered like the mergeclauses, which
1919 : * complicates life for create_mergejoin_plan(). But if we didn't,
1920 : * we'd have a noncanonical sort key list, which would be bad; for one
1921 : * reason, it certainly wouldn't match any available sort order for
1922 : * the input relation.
1923 : */
1924 1116048 : if (!pathkey_is_redundant(pathkey, pathkeys))
1925 1115886 : pathkeys = lappend(pathkeys, pathkey);
1926 : }
1927 :
1928 968824 : return pathkeys;
1929 : }
1930 :
1931 : /*
1932 : * trim_mergeclauses_for_inner_pathkeys
1933 : * This routine trims a list of mergeclauses to include just those that
1934 : * work with a specified ordering for the join's inner relation.
1935 : *
1936 : * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses for the
1937 : * join relation being formed, in an order known to work for the
1938 : * currently-considered sort ordering of the join's outer rel.
1939 : * 'pathkeys' is a pathkeys list showing the ordering of an inner-rel path;
1940 : * it should be equal to, or a truncation of, the result of
1941 : * make_inner_pathkeys_for_merge for these mergeclauses.
1942 : *
1943 : * What we return will be a prefix of the given mergeclauses list.
1944 : *
1945 : * We need this logic because make_inner_pathkeys_for_merge's result isn't
1946 : * necessarily in the same order as the mergeclauses. That means that if we
1947 : * consider an inner-rel pathkey list that is a truncation of that result,
1948 : * we might need to drop mergeclauses even though they match a surviving inner
1949 : * pathkey. This happens when they are to the right of a mergeclause that
1950 : * matches a removed inner pathkey.
1951 : *
1952 : * The mergeclauses must be marked (via outer_is_left) to show which side
1953 : * of each clause is associated with the current outer path. (See
1954 : * select_mergejoin_clauses())
1955 : */
1956 : List *
1957 8578 : trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root,
1958 : List *mergeclauses,
1959 : List *pathkeys)
1960 : {
1961 8578 : List *new_mergeclauses = NIL;
1962 : PathKey *pathkey;
1963 : EquivalenceClass *pathkey_ec;
1964 : bool matched_pathkey;
1965 : ListCell *lip;
1966 : ListCell *i;
1967 :
1968 : /* No pathkeys => no mergeclauses (though we don't expect this case) */
1969 8578 : if (pathkeys == NIL)
1970 0 : return NIL;
1971 : /* Initialize to consider first pathkey */
1972 8578 : lip = list_head(pathkeys);
1973 8578 : pathkey = (PathKey *) lfirst(lip);
1974 8578 : pathkey_ec = pathkey->pk_eclass;
1975 8578 : lip = lnext(pathkeys, lip);
1976 8578 : matched_pathkey = false;
1977 :
1978 : /* Scan mergeclauses to see how many we can use */
1979 17156 : foreach(i, mergeclauses)
1980 : {
1981 17156 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1982 : EquivalenceClass *clause_ec;
1983 :
1984 : /* Assume we needn't do update_mergeclause_eclasses again here */
1985 :
1986 : /* Check clause's inner-rel EC against current pathkey */
1987 34312 : clause_ec = rinfo->outer_is_left ?
1988 17156 : rinfo->right_ec : rinfo->left_ec;
1989 :
1990 : /* If we don't have a match, attempt to advance to next pathkey */
1991 17156 : if (clause_ec != pathkey_ec)
1992 : {
1993 : /* If we had no clauses matching this inner pathkey, must stop */
1994 8578 : if (!matched_pathkey)
1995 0 : break;
1996 :
1997 : /* Advance to next inner pathkey, if any */
1998 8578 : if (lip == NULL)
1999 8578 : break;
2000 0 : pathkey = (PathKey *) lfirst(lip);
2001 0 : pathkey_ec = pathkey->pk_eclass;
2002 0 : lip = lnext(pathkeys, lip);
2003 0 : matched_pathkey = false;
2004 : }
2005 :
2006 : /* If mergeclause matches current inner pathkey, we can use it */
2007 8578 : if (clause_ec == pathkey_ec)
2008 : {
2009 8578 : new_mergeclauses = lappend(new_mergeclauses, rinfo);
2010 8578 : matched_pathkey = true;
2011 : }
2012 : else
2013 : {
2014 : /* Else, no hope of adding any more mergeclauses */
2015 0 : break;
2016 : }
2017 : }
2018 :
2019 8578 : return new_mergeclauses;
2020 : }
2021 :
2022 :
2023 : /****************************************************************************
2024 : * PATHKEY USEFULNESS CHECKS
2025 : *
2026 : * We only want to remember as many of the pathkeys of a path as have some
2027 : * potential use, either for subsequent mergejoins or for meeting the query's
2028 : * requested output ordering. This ensures that add_path() won't consider
2029 : * a path to have a usefully different ordering unless it really is useful.
2030 : * These routines check for usefulness of given pathkeys.
2031 : ****************************************************************************/
2032 :
2033 : /*
2034 : * pathkeys_useful_for_merging
2035 : * Count the number of pathkeys that may be useful for mergejoins
2036 : * above the given relation.
2037 : *
2038 : * We consider a pathkey potentially useful if it corresponds to the merge
2039 : * ordering of either side of any joinclause for the rel. This might be
2040 : * overoptimistic, since joinclauses that require different other relations
2041 : * might never be usable at the same time, but trying to be exact is likely
2042 : * to be more trouble than it's worth.
2043 : *
2044 : * To avoid doubling the number of mergejoin paths considered, we would like
2045 : * to consider only one of the two scan directions (ASC or DESC) as useful
2046 : * for merging for any given target column. The choice is arbitrary unless
2047 : * one of the directions happens to match an ORDER BY key, in which case
2048 : * that direction should be preferred, in hopes of avoiding a final sort step.
2049 : * right_merge_direction() implements this heuristic.
2050 : */
2051 : static int
2052 2728704 : pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
2053 : {
2054 2728704 : int useful = 0;
2055 : ListCell *i;
2056 :
2057 3387198 : foreach(i, pathkeys)
2058 : {
2059 1741510 : PathKey *pathkey = (PathKey *) lfirst(i);
2060 1741510 : bool matched = false;
2061 : ListCell *j;
2062 :
2063 : /* If "wrong" direction, not useful for merging */
2064 1741510 : if (!right_merge_direction(root, pathkey))
2065 316120 : break;
2066 :
2067 : /*
2068 : * First look into the EquivalenceClass of the pathkey, to see if
2069 : * there are any members not yet joined to the rel. If so, it's
2070 : * surely possible to generate a mergejoin clause using them.
2071 : */
2072 2248946 : if (rel->has_eclass_joins &&
2073 823556 : eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
2074 474630 : matched = true;
2075 : else
2076 : {
2077 : /*
2078 : * Otherwise search the rel's joininfo list, which contains
2079 : * non-EquivalenceClass-derivable join clauses that might
2080 : * nonetheless be mergejoinable.
2081 : */
2082 1412482 : foreach(j, rel->joininfo)
2083 : {
2084 645586 : RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
2085 :
2086 645586 : if (restrictinfo->mergeopfamilies == NIL)
2087 163204 : continue;
2088 482382 : update_mergeclause_eclasses(root, restrictinfo);
2089 :
2090 482382 : if (pathkey->pk_eclass == restrictinfo->left_ec ||
2091 384894 : pathkey->pk_eclass == restrictinfo->right_ec)
2092 : {
2093 183864 : matched = true;
2094 183864 : break;
2095 : }
2096 : }
2097 : }
2098 :
2099 : /*
2100 : * If we didn't find a mergeclause, we're done --- any additional
2101 : * sort-key positions in the pathkeys are useless. (But we can still
2102 : * mergejoin if we found at least one mergeclause.)
2103 : */
2104 1425390 : if (matched)
2105 658494 : useful++;
2106 : else
2107 766896 : break;
2108 : }
2109 :
2110 2728704 : return useful;
2111 : }
2112 :
2113 : /*
2114 : * right_merge_direction
2115 : * Check whether the pathkey embodies the preferred sort direction
2116 : * for merging its target column.
2117 : */
2118 : static bool
2119 1741510 : right_merge_direction(PlannerInfo *root, PathKey *pathkey)
2120 : {
2121 : ListCell *l;
2122 :
2123 3217746 : foreach(l, root->query_pathkeys)
2124 : {
2125 1829970 : PathKey *query_pathkey = (PathKey *) lfirst(l);
2126 :
2127 1829970 : if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
2128 353734 : pathkey->pk_opfamily == query_pathkey->pk_opfamily)
2129 : {
2130 : /*
2131 : * Found a matching query sort column. Prefer this pathkey's
2132 : * direction iff it matches. Note that we ignore pk_nulls_first,
2133 : * which means that a sort might be needed anyway ... but we still
2134 : * want to prefer only one of the two possible directions, and we
2135 : * might as well use this one.
2136 : */
2137 353734 : return (pathkey->pk_strategy == query_pathkey->pk_strategy);
2138 : }
2139 : }
2140 :
2141 : /* If no matching ORDER BY request, prefer the ASC direction */
2142 1387776 : return (pathkey->pk_strategy == BTLessStrategyNumber);
2143 : }
2144 :
2145 : /*
2146 : * pathkeys_useful_for_ordering
2147 : * Count the number of pathkeys that are useful for meeting the
2148 : * query's requested output ordering.
2149 : *
2150 : * Because we the have the possibility of incremental sort, a prefix list of
2151 : * keys is potentially useful for improving the performance of the requested
2152 : * ordering. Thus we return 0, if no valuable keys are found, or the number
2153 : * of leading keys shared by the list and the requested ordering..
2154 : */
2155 : static int
2156 2728704 : pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
2157 : {
2158 : int n_common_pathkeys;
2159 :
2160 2728704 : (void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys,
2161 : &n_common_pathkeys);
2162 :
2163 2728704 : return n_common_pathkeys;
2164 : }
2165 :
2166 : /*
2167 : * pathkeys_useful_for_grouping
2168 : * Count the number of pathkeys that are useful for grouping (instead of
2169 : * explicit sort)
2170 : *
2171 : * Group pathkeys could be reordered to benefit from the ordering. The
2172 : * ordering may not be "complete" and may require incremental sort, but that's
2173 : * fine. So we simply count prefix pathkeys with a matching group key, and
2174 : * stop once we find the first pathkey without a match.
2175 : *
2176 : * So e.g. with pathkeys (a,b,c) and group keys (a,b,e) this determines (a,b)
2177 : * pathkeys are useful for grouping, and we might do incremental sort to get
2178 : * path ordered by (a,b,e).
2179 : *
2180 : * This logic is necessary to retain paths with ordering not matching grouping
2181 : * keys directly, without the reordering.
2182 : *
2183 : * Returns the length of pathkey prefix with matching group keys.
2184 : */
2185 : static int
2186 2728704 : pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
2187 : {
2188 : ListCell *key;
2189 2728704 : int n = 0;
2190 :
2191 : /* no special ordering requested for grouping */
2192 2728704 : if (root->group_pathkeys == NIL)
2193 2701978 : return 0;
2194 :
2195 : /* walk the pathkeys and search for matching group key */
2196 33182 : foreach(key, pathkeys)
2197 : {
2198 13260 : PathKey *pathkey = (PathKey *) lfirst(key);
2199 :
2200 : /* no matching group key, we're done */
2201 13260 : if (!list_member_ptr(root->group_pathkeys, pathkey))
2202 6804 : break;
2203 :
2204 6456 : n++;
2205 : }
2206 :
2207 26726 : return n;
2208 : }
2209 :
2210 : /*
2211 : * pathkeys_useful_for_distinct
2212 : * Count the number of pathkeys that are useful for DISTINCT or DISTINCT
2213 : * ON clause.
2214 : *
2215 : * DISTINCT keys could be reordered to benefit from the given pathkey list. As
2216 : * with pathkeys_useful_for_grouping, we return the number of leading keys in
2217 : * the list that are shared by the distinctClause pathkeys.
2218 : */
2219 : static int
2220 2728704 : pathkeys_useful_for_distinct(PlannerInfo *root, List *pathkeys)
2221 : {
2222 : int n_common_pathkeys;
2223 :
2224 : /*
2225 : * distinct_pathkeys may have become empty if all of the pathkeys were
2226 : * determined to be redundant. Return 0 in this case.
2227 : */
2228 2728704 : if (root->distinct_pathkeys == NIL)
2229 2666562 : return 0;
2230 :
2231 : /* walk the pathkeys and search for matching DISTINCT key */
2232 62142 : n_common_pathkeys = 0;
2233 132128 : foreach_node(PathKey, pathkey, pathkeys)
2234 : {
2235 : /* no matching DISTINCT key, we're done */
2236 42182 : if (!list_member_ptr(root->distinct_pathkeys, pathkey))
2237 34338 : break;
2238 :
2239 7844 : n_common_pathkeys++;
2240 : }
2241 :
2242 62142 : return n_common_pathkeys;
2243 : }
2244 :
2245 : /*
2246 : * pathkeys_useful_for_setop
2247 : * Count the number of leading common pathkeys root's 'setop_pathkeys' in
2248 : * 'pathkeys'.
2249 : */
2250 : static int
2251 2728704 : pathkeys_useful_for_setop(PlannerInfo *root, List *pathkeys)
2252 : {
2253 : int n_common_pathkeys;
2254 :
2255 2728704 : (void) pathkeys_count_contained_in(root->setop_pathkeys, pathkeys,
2256 : &n_common_pathkeys);
2257 :
2258 2728704 : return n_common_pathkeys;
2259 : }
2260 :
2261 : /*
2262 : * truncate_useless_pathkeys
2263 : * Shorten the given pathkey list to just the useful pathkeys.
2264 : */
2265 : List *
2266 2728704 : truncate_useless_pathkeys(PlannerInfo *root,
2267 : RelOptInfo *rel,
2268 : List *pathkeys)
2269 : {
2270 : int nuseful;
2271 : int nuseful2;
2272 :
2273 2728704 : nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
2274 2728704 : nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
2275 2728704 : if (nuseful2 > nuseful)
2276 160426 : nuseful = nuseful2;
2277 2728704 : nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
2278 2728704 : if (nuseful2 > nuseful)
2279 416 : nuseful = nuseful2;
2280 2728704 : nuseful2 = pathkeys_useful_for_distinct(root, pathkeys);
2281 2728704 : if (nuseful2 > nuseful)
2282 3288 : nuseful = nuseful2;
2283 2728704 : nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
2284 2728704 : if (nuseful2 > nuseful)
2285 0 : nuseful = nuseful2;
2286 :
2287 : /*
2288 : * Note: not safe to modify input list destructively, but we can avoid
2289 : * copying the list if we're not actually going to change it
2290 : */
2291 2728704 : if (nuseful == 0)
2292 1976456 : return NIL;
2293 752248 : else if (nuseful == list_length(pathkeys))
2294 714600 : return pathkeys;
2295 : else
2296 37648 : return list_copy_head(pathkeys, nuseful);
2297 : }
2298 :
2299 : /*
2300 : * has_useful_pathkeys
2301 : * Detect whether the specified rel could have any pathkeys that are
2302 : * useful according to truncate_useless_pathkeys().
2303 : *
2304 : * This is a cheap test that lets us skip building pathkeys at all in very
2305 : * simple queries. It's OK to err in the direction of returning "true" when
2306 : * there really aren't any usable pathkeys, but erring in the other direction
2307 : * is bad --- so keep this in sync with the routines above!
2308 : *
2309 : * We could make the test more complex, for example checking to see if any of
2310 : * the joinclauses are really mergejoinable, but that likely wouldn't win
2311 : * often enough to repay the extra cycles. Queries with neither a join nor
2312 : * a sort are reasonably common, though, so this much work seems worthwhile.
2313 : */
2314 : bool
2315 845402 : has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel)
2316 : {
2317 845402 : if (rel->joininfo != NIL || rel->has_eclass_joins)
2318 532056 : return true; /* might be able to use pathkeys for merging */
2319 313346 : if (root->group_pathkeys != NIL)
2320 6726 : return true; /* might be able to use pathkeys for grouping */
2321 306620 : if (root->query_pathkeys != NIL)
2322 78258 : return true; /* might be able to use them for ordering */
2323 228362 : return false; /* definitely useless */
2324 : }
|
