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