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-2019, 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/makefuncs.h"
23#include "nodes/nodeFuncs.h"
24#include "nodes/plannodes.h"
25#include "optimizer/optimizer.h"
26#include "optimizer/pathnode.h"
27#include "optimizer/paths.h"
28#include "partitioning/partbounds.h"
29#include "utils/lsyscache.h"
30
31
32static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
33static bool matches_boolean_partition_clause(RestrictInfo *rinfo,
34 RelOptInfo *partrel,
35 int partkeycol);
36static Var *find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle);
37static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
38
39
40/****************************************************************************
41 * PATHKEY CONSTRUCTION AND REDUNDANCY TESTING
42 ****************************************************************************/
43
44/*
45 * make_canonical_pathkey
46 * Given the parameters for a PathKey, find any pre-existing matching
47 * pathkey in the query's list of "canonical" pathkeys. Make a new
48 * entry if there's not one already.
49 *
50 * Note that this function must not be used until after we have completed
51 * merging EquivalenceClasses. (We don't try to enforce that here; instead,
52 * equivclass.c will complain if a merge occurs after root->canon_pathkeys
53 * has become nonempty.)
54 */
55PathKey *
56make_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 /* The passed eclass might be non-canonical, so chase up to the top */
65 while (eclass->ec_merged)
66 eclass = eclass->ec_merged;
67
68 foreach(lc, root->canon_pathkeys)
69 {
70 pk = (PathKey *) lfirst(lc);
71 if (eclass == pk->pk_eclass &&
72 opfamily == pk->pk_opfamily &&
73 strategy == pk->pk_strategy &&
74 nulls_first == pk->pk_nulls_first)
75 return pk;
76 }
77
78 /*
79 * Be sure canonical pathkeys are allocated in the main planning context.
80 * Not an issue in normal planning, but it is for GEQO.
81 */
82 oldcontext = MemoryContextSwitchTo(root->planner_cxt);
83
84 pk = makeNode(PathKey);
85 pk->pk_eclass = eclass;
86 pk->pk_opfamily = opfamily;
87 pk->pk_strategy = strategy;
88 pk->pk_nulls_first = nulls_first;
89
90 root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
91
92 MemoryContextSwitchTo(oldcontext);
93
94 return pk;
95}
96
97/*
98 * pathkey_is_redundant
99 * Is a pathkey redundant with one already in the given list?
100 *
101 * We detect two cases:
102 *
103 * 1. If the new pathkey's equivalence class contains a constant, and isn't
104 * below an outer join, then we can disregard it as a sort key. An example:
105 * SELECT ... WHERE x = 42 ORDER BY x, y;
106 * We may as well just sort by y. Note that because of opfamily matching,
107 * this is semantically correct: we know that the equality constraint is one
108 * that actually binds the variable to a single value in the terms of any
109 * ordering operator that might go with the eclass. This rule not only lets
110 * us simplify (or even skip) explicit sorts, but also allows matching index
111 * sort orders to a query when there are don't-care index columns.
112 *
113 * 2. If the new pathkey's equivalence class is the same as that of any
114 * existing member of the pathkey list, then it is redundant. Some examples:
115 * SELECT ... ORDER BY x, x;
116 * SELECT ... ORDER BY x, x DESC;
117 * SELECT ... WHERE x = y ORDER BY x, y;
118 * In all these cases the second sort key cannot distinguish values that are
119 * considered equal by the first, and so there's no point in using it.
120 * Note in particular that we need not compare opfamily (all the opfamilies
121 * of the EC have the same notion of equality) nor sort direction.
122 *
123 * Both the given pathkey and the list members must be canonical for this
124 * to work properly, but that's okay since we no longer ever construct any
125 * non-canonical pathkeys. (Note: the notion of a pathkey *list* being
126 * canonical includes the additional requirement of no redundant entries,
127 * which is exactly what we are checking for here.)
128 *
129 * Because the equivclass.c machinery forms only one copy of any EC per query,
130 * pointer comparison is enough to decide whether canonical ECs are the same.
131 */
132static bool
133pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
134{
135 EquivalenceClass *new_ec = new_pathkey->pk_eclass;
136 ListCell *lc;
137
138 /* Check for EC containing a constant --- unconditionally redundant */
139 if (EC_MUST_BE_REDUNDANT(new_ec))
140 return true;
141
142 /* If same EC already used in list, then redundant */
143 foreach(lc, pathkeys)
144 {
145 PathKey *old_pathkey = (PathKey *) lfirst(lc);
146
147 if (new_ec == old_pathkey->pk_eclass)
148 return true;
149 }
150
151 return false;
152}
153
154/*
155 * make_pathkey_from_sortinfo
156 * Given an expression and sort-order information, create a PathKey.
157 * The result is always a "canonical" PathKey, but it might be redundant.
158 *
159 * expr is the expression, and nullable_relids is the set of base relids
160 * that are potentially nullable below it.
161 *
162 * If the PathKey is being generated from a SortGroupClause, sortref should be
163 * the SortGroupClause's SortGroupRef; otherwise zero.
164 *
165 * If rel is not NULL, it identifies a specific relation we're considering
166 * a path for, and indicates that child EC members for that relation can be
167 * considered. Otherwise child members are ignored. (See the comments for
168 * get_eclass_for_sort_expr.)
169 *
170 * create_it is true if we should create any missing EquivalenceClass
171 * needed to represent the sort key. If it's false, we return NULL if the
172 * sort key isn't already present in any EquivalenceClass.
173 */
174static PathKey *
175make_pathkey_from_sortinfo(PlannerInfo *root,
176 Expr *expr,
177 Relids nullable_relids,
178 Oid opfamily,
179 Oid opcintype,
180 Oid collation,
181 bool reverse_sort,
182 bool nulls_first,
183 Index sortref,
184 Relids rel,
185 bool create_it)
186{
187 int16 strategy;
188 Oid equality_op;
189 List *opfamilies;
190 EquivalenceClass *eclass;
191
192 strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
193
194 /*
195 * EquivalenceClasses need to contain opfamily lists based on the family
196 * membership of mergejoinable equality operators, which could belong to
197 * more than one opfamily. So we have to look up the opfamily's equality
198 * operator and get its membership.
199 */
200 equality_op = get_opfamily_member(opfamily,
201 opcintype,
202 opcintype,
203 BTEqualStrategyNumber);
204 if (!OidIsValid(equality_op)) /* shouldn't happen */
205 elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
206 BTEqualStrategyNumber, opcintype, opcintype, opfamily);
207 opfamilies = get_mergejoin_opfamilies(equality_op);
208 if (!opfamilies) /* certainly should find some */
209 elog(ERROR, "could not find opfamilies for equality operator %u",
210 equality_op);
211
212 /* Now find or (optionally) create a matching EquivalenceClass */
213 eclass = get_eclass_for_sort_expr(root, expr, nullable_relids,
214 opfamilies, opcintype, collation,
215 sortref, rel, create_it);
216
217 /* Fail if no EC and !create_it */
218 if (!eclass)
219 return NULL;
220
221 /* And finally we can find or create a PathKey node */
222 return make_canonical_pathkey(root, eclass, opfamily,
223 strategy, nulls_first);
224}
225
226/*
227 * make_pathkey_from_sortop
228 * Like make_pathkey_from_sortinfo, but work from a sort operator.
229 *
230 * This should eventually go away, but we need to restructure SortGroupClause
231 * first.
232 */
233static PathKey *
234make_pathkey_from_sortop(PlannerInfo *root,
235 Expr *expr,
236 Relids nullable_relids,
237 Oid ordering_op,
238 bool nulls_first,
239 Index sortref,
240 bool create_it)
241{
242 Oid opfamily,
243 opcintype,
244 collation;
245 int16 strategy;
246
247 /* Find the operator in pg_amop --- failure shouldn't happen */
248 if (!get_ordering_op_properties(ordering_op,
249 &opfamily, &opcintype, &strategy))
250 elog(ERROR, "operator %u is not a valid ordering operator",
251 ordering_op);
252
253 /* Because SortGroupClause doesn't carry collation, consult the expr */
254 collation = exprCollation((Node *) expr);
255
256 return make_pathkey_from_sortinfo(root,
257 expr,
258 nullable_relids,
259 opfamily,
260 opcintype,
261 collation,
262 (strategy == BTGreaterStrategyNumber),
263 nulls_first,
264 sortref,
265 NULL,
266 create_it);
267}
268
269
270/****************************************************************************
271 * PATHKEY COMPARISONS
272 ****************************************************************************/
273
274/*
275 * compare_pathkeys
276 * Compare two pathkeys to see if they are equivalent, and if not whether
277 * one is "better" than the other.
278 *
279 * We assume the pathkeys are canonical, and so they can be checked for
280 * equality by simple pointer comparison.
281 */
282PathKeysComparison
283compare_pathkeys(List *keys1, List *keys2)
284{
285 ListCell *key1,
286 *key2;
287
288 /*
289 * Fall out quickly if we are passed two identical lists. This mostly
290 * catches the case where both are NIL, but that's common enough to
291 * warrant the test.
292 */
293 if (keys1 == keys2)
294 return PATHKEYS_EQUAL;
295
296 forboth(key1, keys1, key2, keys2)
297 {
298 PathKey *pathkey1 = (PathKey *) lfirst(key1);
299 PathKey *pathkey2 = (PathKey *) lfirst(key2);
300
301 if (pathkey1 != pathkey2)
302 return PATHKEYS_DIFFERENT; /* no need to keep looking */
303 }
304
305 /*
306 * If we reached the end of only one list, the other is longer and
307 * therefore not a subset.
308 */
309 if (key1 != NULL)
310 return PATHKEYS_BETTER1; /* key1 is longer */
311 if (key2 != NULL)
312 return PATHKEYS_BETTER2; /* key2 is longer */
313 return PATHKEYS_EQUAL;
314}
315
316/*
317 * pathkeys_contained_in
318 * Common special case of compare_pathkeys: we just want to know
319 * if keys2 are at least as well sorted as keys1.
320 */
321bool
322pathkeys_contained_in(List *keys1, List *keys2)
323{
324 switch (compare_pathkeys(keys1, keys2))
325 {
326 case PATHKEYS_EQUAL:
327 case PATHKEYS_BETTER2:
328 return true;
329 default:
330 break;
331 }
332 return false;
333}
334
335/*
336 * get_cheapest_path_for_pathkeys
337 * Find the cheapest path (according to the specified criterion) that
338 * satisfies the given pathkeys and parameterization.
339 * Return NULL if no such path.
340 *
341 * 'paths' is a list of possible paths that all generate the same relation
342 * 'pathkeys' represents a required ordering (in canonical form!)
343 * 'required_outer' denotes allowable outer relations for parameterized paths
344 * 'cost_criterion' is STARTUP_COST or TOTAL_COST
345 * 'require_parallel_safe' causes us to consider only parallel-safe paths
346 */
347Path *
348get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
349 Relids required_outer,
350 CostSelector cost_criterion,
351 bool require_parallel_safe)
352{
353 Path *matched_path = NULL;
354 ListCell *l;
355
356 foreach(l, paths)
357 {
358 Path *path = (Path *) lfirst(l);
359
360 /*
361 * Since cost comparison is a lot cheaper than pathkey comparison, do
362 * that first. (XXX is that still true?)
363 */
364 if (matched_path != NULL &&
365 compare_path_costs(matched_path, path, cost_criterion) <= 0)
366 continue;
367
368 if (require_parallel_safe && !path->parallel_safe)
369 continue;
370
371 if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
372 bms_is_subset(PATH_REQ_OUTER(path), required_outer))
373 matched_path = path;
374 }
375 return matched_path;
376}
377
378/*
379 * get_cheapest_fractional_path_for_pathkeys
380 * Find the cheapest path (for retrieving a specified fraction of all
381 * the tuples) that satisfies the given pathkeys and parameterization.
382 * Return NULL if no such path.
383 *
384 * See compare_fractional_path_costs() for the interpretation of the fraction
385 * parameter.
386 *
387 * 'paths' is a list of possible paths that all generate the same relation
388 * 'pathkeys' represents a required ordering (in canonical form!)
389 * 'required_outer' denotes allowable outer relations for parameterized paths
390 * 'fraction' is the fraction of the total tuples expected to be retrieved
391 */
392Path *
393get_cheapest_fractional_path_for_pathkeys(List *paths,
394 List *pathkeys,
395 Relids required_outer,
396 double fraction)
397{
398 Path *matched_path = NULL;
399 ListCell *l;
400
401 foreach(l, paths)
402 {
403 Path *path = (Path *) lfirst(l);
404
405 /*
406 * Since cost comparison is a lot cheaper than pathkey comparison, do
407 * that first. (XXX is that still true?)
408 */
409 if (matched_path != NULL &&
410 compare_fractional_path_costs(matched_path, path, fraction) <= 0)
411 continue;
412
413 if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
414 bms_is_subset(PATH_REQ_OUTER(path), required_outer))
415 matched_path = path;
416 }
417 return matched_path;
418}
419
420
421/*
422 * get_cheapest_parallel_safe_total_inner
423 * Find the unparameterized parallel-safe path with the least total cost.
424 */
425Path *
426get_cheapest_parallel_safe_total_inner(List *paths)
427{
428 ListCell *l;
429
430 foreach(l, paths)
431 {
432 Path *innerpath = (Path *) lfirst(l);
433
434 if (innerpath->parallel_safe &&
435 bms_is_empty(PATH_REQ_OUTER(innerpath)))
436 return innerpath;
437 }
438
439 return NULL;
440}
441
442/****************************************************************************
443 * NEW PATHKEY FORMATION
444 ****************************************************************************/
445
446/*
447 * build_index_pathkeys
448 * Build a pathkeys list that describes the ordering induced by an index
449 * scan using the given index. (Note that an unordered index doesn't
450 * induce any ordering, so we return NIL.)
451 *
452 * If 'scandir' is BackwardScanDirection, build pathkeys representing a
453 * backwards scan of the index.
454 *
455 * We iterate only key columns of covering indexes, since non-key columns
456 * don't influence index ordering. The result is canonical, meaning that
457 * redundant pathkeys are removed; it may therefore have fewer entries than
458 * there are key columns in the index.
459 *
460 * Another reason for stopping early is that we may be able to tell that
461 * an index column's sort order is uninteresting for this query. However,
462 * that test is just based on the existence of an EquivalenceClass and not
463 * on position in pathkey lists, so it's not complete. Caller should call
464 * truncate_useless_pathkeys() to possibly remove more pathkeys.
465 */
466List *
467build_index_pathkeys(PlannerInfo *root,
468 IndexOptInfo *index,
469 ScanDirection scandir)
470{
471 List *retval = NIL;
472 ListCell *lc;
473 int i;
474
475 if (index->sortopfamily == NULL)
476 return NIL; /* non-orderable index */
477
478 i = 0;
479 foreach(lc, index->indextlist)
480 {
481 TargetEntry *indextle = (TargetEntry *) lfirst(lc);
482 Expr *indexkey;
483 bool reverse_sort;
484 bool nulls_first;
485 PathKey *cpathkey;
486
487 /*
488 * INCLUDE columns are stored in index unordered, so they don't
489 * support ordered index scan.
490 */
491 if (i >= index->nkeycolumns)
492 break;
493
494 /* We assume we don't need to make a copy of the tlist item */
495 indexkey = indextle->expr;
496
497 if (ScanDirectionIsBackward(scandir))
498 {
499 reverse_sort = !index->reverse_sort[i];
500 nulls_first = !index->nulls_first[i];
501 }
502 else
503 {
504 reverse_sort = index->reverse_sort[i];
505 nulls_first = index->nulls_first[i];
506 }
507
508 /*
509 * OK, try to make a canonical pathkey for this sort key. Note we're
510 * underneath any outer joins, so nullable_relids should be NULL.
511 */
512 cpathkey = make_pathkey_from_sortinfo(root,
513 indexkey,
514 NULL,
515 index->sortopfamily[i],
516 index->opcintype[i],
517 index->indexcollations[i],
518 reverse_sort,
519 nulls_first,
520 0,
521 index->rel->relids,
522 false);
523
524 if (cpathkey)
525 {
526 /*
527 * We found the sort key in an EquivalenceClass, so it's relevant
528 * for this query. Add it to list, unless it's redundant.
529 */
530 if (!pathkey_is_redundant(cpathkey, retval))
531 retval = lappend(retval, cpathkey);
532 }
533 else
534 {
535 /*
536 * Boolean index keys might be redundant even if they do not
537 * appear in an EquivalenceClass, because of our special treatment
538 * of boolean equality conditions --- see the comment for
539 * indexcol_is_bool_constant_for_query(). If that applies, we can
540 * continue to examine lower-order index columns. Otherwise, the
541 * sort key is not an interesting sort order for this query, so we
542 * should stop considering index columns; any lower-order sort
543 * keys won't be useful either.
544 */
545 if (!indexcol_is_bool_constant_for_query(index, i))
546 break;
547 }
548
549 i++;
550 }
551
552 return retval;
553}
554
555/*
556 * partkey_is_bool_constant_for_query
557 *
558 * If a partition key column is constrained to have a constant value by the
559 * query's WHERE conditions, then it's irrelevant for sort-order
560 * considerations. Usually that means we have a restriction clause
561 * WHERE partkeycol = constant, which gets turned into an EquivalenceClass
562 * containing a constant, which is recognized as redundant by
563 * build_partition_pathkeys(). But if the partition key column is a
564 * boolean variable (or expression), then we are not going to see such a
565 * WHERE clause, because expression preprocessing will have simplified it
566 * to "WHERE partkeycol" or "WHERE NOT partkeycol". So we are not going
567 * to have a matching EquivalenceClass (unless the query also contains
568 * "ORDER BY partkeycol"). To allow such cases to work the same as they would
569 * for non-boolean values, this function is provided to detect whether the
570 * specified partition key column matches a boolean restriction clause.
571 */
572static bool
573partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
574{
575 PartitionScheme partscheme = partrel->part_scheme;
576 ListCell *lc;
577
578 /* If the partkey isn't boolean, we can't possibly get a match */
579 if (!IsBooleanOpfamily(partscheme->partopfamily[partkeycol]))
580 return false;
581
582 /* Check each restriction clause for the partitioned rel */
583 foreach(lc, partrel->baserestrictinfo)
584 {
585 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
586
587 /* Ignore pseudoconstant quals, they won't match */
588 if (rinfo->pseudoconstant)
589 continue;
590
591 /* See if we can match the clause's expression to the partkey column */
592 if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
593 return true;
594 }
595
596 return false;
597}
598
599/*
600 * matches_boolean_partition_clause
601 * Determine if the boolean clause described by rinfo matches
602 * partrel's partkeycol-th partition key column.
603 *
604 * "Matches" can be either an exact match (equivalent to partkey = true),
605 * or a NOT above an exact match (equivalent to partkey = false).
606 */
607static bool
608matches_boolean_partition_clause(RestrictInfo *rinfo,
609 RelOptInfo *partrel, int partkeycol)
610{
611 Node *clause = (Node *) rinfo->clause;
612 Node *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
613
614 /* Direct match? */
615 if (equal(partexpr, clause))
616 return true;
617 /* NOT clause? */
618 else if (is_notclause(clause))
619 {
620 Node *arg = (Node *) get_notclausearg((Expr *) clause);
621
622 if (equal(partexpr, arg))
623 return true;
624 }
625
626 return false;
627}
628
629/*
630 * build_partition_pathkeys
631 * Build a pathkeys list that describes the ordering induced by the
632 * partitions of partrel, under either forward or backward scan
633 * as per scandir.
634 *
635 * Caller must have checked that the partitions are properly ordered,
636 * as detected by partitions_are_ordered().
637 *
638 * Sets *partialkeys to true if pathkeys were only built for a prefix of the
639 * partition key, or false if the pathkeys include all columns of the
640 * partition key.
641 */
642List *
643build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
644 ScanDirection scandir, bool *partialkeys)
645{
646 List *retval = NIL;
647 PartitionScheme partscheme = partrel->part_scheme;
648 int i;
649
650 Assert(partscheme != NULL);
651 Assert(partitions_are_ordered(partrel->boundinfo, partrel->nparts));
652 /* For now, we can only cope with baserels */
653 Assert(IS_SIMPLE_REL(partrel));
654
655 for (i = 0; i < partscheme->partnatts; i++)
656 {
657 PathKey *cpathkey;
658 Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
659
660 /*
661 * Try to make a canonical pathkey for this partkey.
662 *
663 * We're considering a baserel scan, so nullable_relids should be
664 * NULL. Also, we assume the PartitionDesc lists any NULL partition
665 * last, so we treat the scan like a NULLS LAST index: we have
666 * nulls_first for backwards scan only.
667 */
668 cpathkey = make_pathkey_from_sortinfo(root,
669 keyCol,
670 NULL,
671 partscheme->partopfamily[i],
672 partscheme->partopcintype[i],
673 partscheme->partcollation[i],
674 ScanDirectionIsBackward(scandir),
675 ScanDirectionIsBackward(scandir),
676 0,
677 partrel->relids,
678 false);
679
680
681 if (cpathkey)
682 {
683 /*
684 * We found the sort key in an EquivalenceClass, so it's relevant
685 * for this query. Add it to list, unless it's redundant.
686 */
687 if (!pathkey_is_redundant(cpathkey, retval))
688 retval = lappend(retval, cpathkey);
689 }
690 else
691 {
692 /*
693 * Boolean partition keys might be redundant even if they do not
694 * appear in an EquivalenceClass, because of our special treatment
695 * of boolean equality conditions --- see the comment for
696 * partkey_is_bool_constant_for_query(). If that applies, we can
697 * continue to examine lower-order partition keys. Otherwise, the
698 * sort key is not an interesting sort order for this query, so we
699 * should stop considering partition columns; any lower-order sort
700 * keys won't be useful either.
701 */
702 if (!partkey_is_bool_constant_for_query(partrel, i))
703 {
704 *partialkeys = true;
705 return retval;
706 }
707 }
708 }
709
710 *partialkeys = false;
711 return retval;
712}
713
714/*
715 * build_expression_pathkey
716 * Build a pathkeys list that describes an ordering by a single expression
717 * using the given sort operator.
718 *
719 * expr, nullable_relids, and rel are as for make_pathkey_from_sortinfo.
720 * We induce the other arguments assuming default sort order for the operator.
721 *
722 * Similarly to make_pathkey_from_sortinfo, the result is NIL if create_it
723 * is false and the expression isn't already in some EquivalenceClass.
724 */
725List *
726build_expression_pathkey(PlannerInfo *root,
727 Expr *expr,
728 Relids nullable_relids,
729 Oid opno,
730 Relids rel,
731 bool create_it)
732{
733 List *pathkeys;
734 Oid opfamily,
735 opcintype;
736 int16 strategy;
737 PathKey *cpathkey;
738
739 /* Find the operator in pg_amop --- failure shouldn't happen */
740 if (!get_ordering_op_properties(opno,
741 &opfamily, &opcintype, &strategy))
742 elog(ERROR, "operator %u is not a valid ordering operator",
743 opno);
744
745 cpathkey = make_pathkey_from_sortinfo(root,
746 expr,
747 nullable_relids,
748 opfamily,
749 opcintype,
750 exprCollation((Node *) expr),
751 (strategy == BTGreaterStrategyNumber),
752 (strategy == BTGreaterStrategyNumber),
753 0,
754 rel,
755 create_it);
756
757 if (cpathkey)
758 pathkeys = list_make1(cpathkey);
759 else
760 pathkeys = NIL;
761
762 return pathkeys;
763}
764
765/*
766 * convert_subquery_pathkeys
767 * Build a pathkeys list that describes the ordering of a subquery's
768 * result, in the terms of the outer query. This is essentially a
769 * task of conversion.
770 *
771 * 'rel': outer query's RelOptInfo for the subquery relation.
772 * 'subquery_pathkeys': the subquery's output pathkeys, in its terms.
773 * 'subquery_tlist': the subquery's output targetlist, in its terms.
774 *
775 * We intentionally don't do truncate_useless_pathkeys() here, because there
776 * are situations where seeing the raw ordering of the subquery is helpful.
777 * For example, if it returns ORDER BY x DESC, that may prompt us to
778 * construct a mergejoin using DESC order rather than ASC order; but the
779 * right_merge_direction heuristic would have us throw the knowledge away.
780 */
781List *
782convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
783 List *subquery_pathkeys,
784 List *subquery_tlist)
785{
786 List *retval = NIL;
787 int retvallen = 0;
788 int outer_query_keys = list_length(root->query_pathkeys);
789 ListCell *i;
790
791 foreach(i, subquery_pathkeys)
792 {
793 PathKey *sub_pathkey = (PathKey *) lfirst(i);
794 EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
795 PathKey *best_pathkey = NULL;
796
797 if (sub_eclass->ec_has_volatile)
798 {
799 /*
800 * If the sub_pathkey's EquivalenceClass is volatile, then it must
801 * have come from an ORDER BY clause, and we have to match it to
802 * that same targetlist entry.
803 */
804 TargetEntry *tle;
805 Var *outer_var;
806
807 if (sub_eclass->ec_sortref == 0) /* can't happen */
808 elog(ERROR, "volatile EquivalenceClass has no sortref");
809 tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
810 Assert(tle);
811 /* Is TLE actually available to the outer query? */
812 outer_var = find_var_for_subquery_tle(rel, tle);
813 if (outer_var)
814 {
815 /* We can represent this sub_pathkey */
816 EquivalenceMember *sub_member;
817 EquivalenceClass *outer_ec;
818
819 Assert(list_length(sub_eclass->ec_members) == 1);
820 sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
821
822 /*
823 * Note: it might look funny to be setting sortref = 0 for a
824 * reference to a volatile sub_eclass. However, the
825 * expression is *not* volatile in the outer query: it's just
826 * a Var referencing whatever the subquery emitted. (IOW, the
827 * outer query isn't going to re-execute the volatile
828 * expression itself.) So this is okay. Likewise, it's
829 * correct to pass nullable_relids = NULL, because we're
830 * underneath any outer joins appearing in the outer query.
831 */
832 outer_ec =
833 get_eclass_for_sort_expr(root,
834 (Expr *) outer_var,
835 NULL,
836 sub_eclass->ec_opfamilies,
837 sub_member->em_datatype,
838 sub_eclass->ec_collation,
839 0,
840 rel->relids,
841 false);
842
843 /*
844 * If we don't find a matching EC, sub-pathkey isn't
845 * interesting to the outer query
846 */
847 if (outer_ec)
848 best_pathkey =
849 make_canonical_pathkey(root,
850 outer_ec,
851 sub_pathkey->pk_opfamily,
852 sub_pathkey->pk_strategy,
853 sub_pathkey->pk_nulls_first);
854 }
855 }
856 else
857 {
858 /*
859 * Otherwise, the sub_pathkey's EquivalenceClass could contain
860 * multiple elements (representing knowledge that multiple items
861 * are effectively equal). Each element might match none, one, or
862 * more of the output columns that are visible to the outer query.
863 * This means we may have multiple possible representations of the
864 * sub_pathkey in the context of the outer query. Ideally we
865 * would generate them all and put them all into an EC of the
866 * outer query, thereby propagating equality knowledge up to the
867 * outer query. Right now we cannot do so, because the outer
868 * query's EquivalenceClasses are already frozen when this is
869 * called. Instead we prefer the one that has the highest "score"
870 * (number of EC peers, plus one if it matches the outer
871 * query_pathkeys). This is the most likely to be useful in the
872 * outer query.
873 */
874 int best_score = -1;
875 ListCell *j;
876
877 foreach(j, sub_eclass->ec_members)
878 {
879 EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
880 Expr *sub_expr = sub_member->em_expr;
881 Oid sub_expr_type = sub_member->em_datatype;
882 Oid sub_expr_coll = sub_eclass->ec_collation;
883 ListCell *k;
884
885 if (sub_member->em_is_child)
886 continue; /* ignore children here */
887
888 foreach(k, subquery_tlist)
889 {
890 TargetEntry *tle = (TargetEntry *) lfirst(k);
891 Var *outer_var;
892 Expr *tle_expr;
893 EquivalenceClass *outer_ec;
894 PathKey *outer_pk;
895 int score;
896
897 /* Is TLE actually available to the outer query? */
898 outer_var = find_var_for_subquery_tle(rel, tle);
899 if (!outer_var)
900 continue;
901
902 /*
903 * The targetlist entry is considered to match if it
904 * matches after sort-key canonicalization. That is
905 * needed since the sub_expr has been through the same
906 * process.
907 */
908 tle_expr = canonicalize_ec_expression(tle->expr,
909 sub_expr_type,
910 sub_expr_coll);
911 if (!equal(tle_expr, sub_expr))
912 continue;
913
914 /* See if we have a matching EC for the TLE */
915 outer_ec = get_eclass_for_sort_expr(root,
916 (Expr *) outer_var,
917 NULL,
918 sub_eclass->ec_opfamilies,
919 sub_expr_type,
920 sub_expr_coll,
921 0,
922 rel->relids,
923 false);
924
925 /*
926 * If we don't find a matching EC, this sub-pathkey isn't
927 * interesting to the outer query
928 */
929 if (!outer_ec)
930 continue;
931
932 outer_pk = make_canonical_pathkey(root,
933 outer_ec,
934 sub_pathkey->pk_opfamily,
935 sub_pathkey->pk_strategy,
936 sub_pathkey->pk_nulls_first);
937 /* score = # of equivalence peers */
938 score = list_length(outer_ec->ec_members) - 1;
939 /* +1 if it matches the proper query_pathkeys item */
940 if (retvallen < outer_query_keys &&
941 list_nth(root->query_pathkeys, retvallen) == outer_pk)
942 score++;
943 if (score > best_score)
944 {
945 best_pathkey = outer_pk;
946 best_score = score;
947 }
948 }
949 }
950 }
951
952 /*
953 * If we couldn't find a representation of this sub_pathkey, we're
954 * done (we can't use the ones to its right, either).
955 */
956 if (!best_pathkey)
957 break;
958
959 /*
960 * Eliminate redundant ordering info; could happen if outer query
961 * equivalences subquery keys...
962 */
963 if (!pathkey_is_redundant(best_pathkey, retval))
964 {
965 retval = lappend(retval, best_pathkey);
966 retvallen++;
967 }
968 }
969
970 return retval;
971}
972
973/*
974 * find_var_for_subquery_tle
975 *
976 * If the given subquery tlist entry is due to be emitted by the subquery's
977 * scan node, return a Var for it, else return NULL.
978 *
979 * We need this to ensure that we don't return pathkeys describing values
980 * that are unavailable above the level of the subquery scan.
981 */
982static Var *
983find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
984{
985 ListCell *lc;
986
987 /* If the TLE is resjunk, it's certainly not visible to the outer query */
988 if (tle->resjunk)
989 return NULL;
990
991 /* Search the rel's targetlist to see what it will return */
992 foreach(lc, rel->reltarget->exprs)
993 {
994 Var *var = (Var *) lfirst(lc);
995
996 /* Ignore placeholders */
997 if (!IsA(var, Var))
998 continue;
999 Assert(var->varno == rel->relid);
1000
1001 /* If we find a Var referencing this TLE, we're good */
1002 if (var->varattno == tle->resno)
1003 return copyObject(var); /* Make a copy for safety */
1004 }
1005 return NULL;
1006}
1007
1008/*
1009 * build_join_pathkeys
1010 * Build the path keys for a join relation constructed by mergejoin or
1011 * nestloop join. This is normally the same as the outer path's keys.
1012 *
1013 * EXCEPTION: in a FULL or RIGHT join, we cannot treat the result as
1014 * having the outer path's path keys, because null lefthand rows may be
1015 * inserted at random points. It must be treated as unsorted.
1016 *
1017 * We truncate away any pathkeys that are uninteresting for higher joins.
1018 *
1019 * 'joinrel' is the join relation that paths are being formed for
1020 * 'jointype' is the join type (inner, left, full, etc)
1021 * 'outer_pathkeys' is the list of the current outer path's path keys
1022 *
1023 * Returns the list of new path keys.
1024 */
1025List *
1026build_join_pathkeys(PlannerInfo *root,
1027 RelOptInfo *joinrel,
1028 JoinType jointype,
1029 List *outer_pathkeys)
1030{
1031 if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
1032 return NIL;
1033
1034 /*
1035 * This used to be quite a complex bit of code, but now that all pathkey
1036 * sublists start out life canonicalized, we don't have to do a darn thing
1037 * here!
1038 *
1039 * We do, however, need to truncate the pathkeys list, since it may
1040 * contain pathkeys that were useful for forming this joinrel but are
1041 * uninteresting to higher levels.
1042 */
1043 return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1044}
1045
1046/****************************************************************************
1047 * PATHKEYS AND SORT CLAUSES
1048 ****************************************************************************/
1049
1050/*
1051 * make_pathkeys_for_sortclauses
1052 * Generate a pathkeys list that represents the sort order specified
1053 * by a list of SortGroupClauses
1054 *
1055 * The resulting PathKeys are always in canonical form. (Actually, there
1056 * is no longer any code anywhere that creates non-canonical PathKeys.)
1057 *
1058 * We assume that root->nullable_baserels is the set of base relids that could
1059 * have gone to NULL below the SortGroupClause expressions. This is okay if
1060 * the expressions came from the query's top level (ORDER BY, DISTINCT, etc)
1061 * and if this function is only invoked after deconstruct_jointree. In the
1062 * future we might have to make callers pass in the appropriate
1063 * nullable-relids set, but for now it seems unnecessary.
1064 *
1065 * 'sortclauses' is a list of SortGroupClause nodes
1066 * 'tlist' is the targetlist to find the referenced tlist entries in
1067 */
1068List *
1069make_pathkeys_for_sortclauses(PlannerInfo *root,
1070 List *sortclauses,
1071 List *tlist)
1072{
1073 List *pathkeys = NIL;
1074 ListCell *l;
1075
1076 foreach(l, sortclauses)
1077 {
1078 SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1079 Expr *sortkey;
1080 PathKey *pathkey;
1081
1082 sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1083 Assert(OidIsValid(sortcl->sortop));
1084 pathkey = make_pathkey_from_sortop(root,
1085 sortkey,
1086 root->nullable_baserels,
1087 sortcl->sortop,
1088 sortcl->nulls_first,
1089 sortcl->tleSortGroupRef,
1090 true);
1091
1092 /* Canonical form eliminates redundant ordering keys */
1093 if (!pathkey_is_redundant(pathkey, pathkeys))
1094 pathkeys = lappend(pathkeys, pathkey);
1095 }
1096 return pathkeys;
1097}
1098
1099/****************************************************************************
1100 * PATHKEYS AND MERGECLAUSES
1101 ****************************************************************************/
1102
1103/*
1104 * initialize_mergeclause_eclasses
1105 * Set the EquivalenceClass links in a mergeclause restrictinfo.
1106 *
1107 * RestrictInfo contains fields in which we may cache pointers to
1108 * EquivalenceClasses for the left and right inputs of the mergeclause.
1109 * (If the mergeclause is a true equivalence clause these will be the
1110 * same EquivalenceClass, otherwise not.) If the mergeclause is either
1111 * used to generate an EquivalenceClass, or derived from an EquivalenceClass,
1112 * then it's easy to set up the left_ec and right_ec members --- otherwise,
1113 * this function should be called to set them up. We will generate new
1114 * EquivalenceClauses if necessary to represent the mergeclause's left and
1115 * right sides.
1116 *
1117 * Note this is called before EC merging is complete, so the links won't
1118 * necessarily point to canonical ECs. Before they are actually used for
1119 * anything, update_mergeclause_eclasses must be called to ensure that
1120 * they've been updated to point to canonical ECs.
1121 */
1122void
1123initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
1124{
1125 Expr *clause = restrictinfo->clause;
1126 Oid lefttype,
1127 righttype;
1128
1129 /* Should be a mergeclause ... */
1130 Assert(restrictinfo->mergeopfamilies != NIL);
1131 /* ... with links not yet set */
1132 Assert(restrictinfo->left_ec == NULL);
1133 Assert(restrictinfo->right_ec == NULL);
1134
1135 /* Need the declared input types of the operator */
1136 op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1137
1138 /* Find or create a matching EquivalenceClass for each side */
1139 restrictinfo->left_ec =
1140 get_eclass_for_sort_expr(root,
1141 (Expr *) get_leftop(clause),
1142 restrictinfo->nullable_relids,
1143 restrictinfo->mergeopfamilies,
1144 lefttype,
1145 ((OpExpr *) clause)->inputcollid,
1146 0,
1147 NULL,
1148 true);
1149 restrictinfo->right_ec =
1150 get_eclass_for_sort_expr(root,
1151 (Expr *) get_rightop(clause),
1152 restrictinfo->nullable_relids,
1153 restrictinfo->mergeopfamilies,
1154 righttype,
1155 ((OpExpr *) clause)->inputcollid,
1156 0,
1157 NULL,
1158 true);
1159}
1160
1161/*
1162 * update_mergeclause_eclasses
1163 * Make the cached EquivalenceClass links valid in a mergeclause
1164 * restrictinfo.
1165 *
1166 * These pointers should have been set by process_equivalence or
1167 * initialize_mergeclause_eclasses, but they might have been set to
1168 * non-canonical ECs that got merged later. Chase up to the canonical
1169 * merged parent if so.
1170 */
1171void
1172update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
1173{
1174 /* Should be a merge clause ... */
1175 Assert(restrictinfo->mergeopfamilies != NIL);
1176 /* ... with pointers already set */
1177 Assert(restrictinfo->left_ec != NULL);
1178 Assert(restrictinfo->right_ec != NULL);
1179
1180 /* Chase up to the top as needed */
1181 while (restrictinfo->left_ec->ec_merged)
1182 restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
1183 while (restrictinfo->right_ec->ec_merged)
1184 restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
1185}
1186
1187/*
1188 * find_mergeclauses_for_outer_pathkeys
1189 * This routine attempts to find a list of mergeclauses that can be
1190 * used with a specified ordering for the join's outer relation.
1191 * If successful, it returns a list of mergeclauses.
1192 *
1193 * 'pathkeys' is a pathkeys list showing the ordering of an outer-rel path.
1194 * 'restrictinfos' is a list of mergejoinable restriction clauses for the
1195 * join relation being formed, in no particular order.
1196 *
1197 * The restrictinfos must be marked (via outer_is_left) to show which side
1198 * of each clause is associated with the current outer path. (See
1199 * select_mergejoin_clauses())
1200 *
1201 * The result is NIL if no merge can be done, else a maximal list of
1202 * usable mergeclauses (represented as a list of their restrictinfo nodes).
1203 * The list is ordered to match the pathkeys, as required for execution.
1204 */
1205List *
1206find_mergeclauses_for_outer_pathkeys(PlannerInfo *root,
1207 List *pathkeys,
1208 List *restrictinfos)
1209{
1210 List *mergeclauses = NIL;
1211 ListCell *i;
1212
1213 /* make sure we have eclasses cached in the clauses */
1214 foreach(i, restrictinfos)
1215 {
1216 RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1217
1218 update_mergeclause_eclasses(root, rinfo);
1219 }
1220
1221 foreach(i, pathkeys)
1222 {
1223 PathKey *pathkey = (PathKey *) lfirst(i);
1224 EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1225 List *matched_restrictinfos = NIL;
1226 ListCell *j;
1227
1228 /*----------
1229 * A mergejoin clause matches a pathkey if it has the same EC.
1230 * If there are multiple matching clauses, take them all. In plain
1231 * inner-join scenarios we expect only one match, because
1232 * equivalence-class processing will have removed any redundant
1233 * mergeclauses. However, in outer-join scenarios there might be
1234 * multiple matches. An example is
1235 *
1236 * select * from a full join b
1237 * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1238 *
1239 * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1240 * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1241 * we *must* do so or we will be unable to form a valid plan.
1242 *
1243 * We expect that the given pathkeys list is canonical, which means
1244 * no two members have the same EC, so it's not possible for this
1245 * code to enter the same mergeclause into the result list twice.
1246 *
1247 * It's possible that multiple matching clauses might have different
1248 * ECs on the other side, in which case the order we put them into our
1249 * result makes a difference in the pathkeys required for the inner
1250 * input rel. However this routine hasn't got any info about which
1251 * order would be best, so we don't worry about that.
1252 *
1253 * It's also possible that the selected mergejoin clauses produce
1254 * a noncanonical ordering of pathkeys for the inner side, ie, we
1255 * might select clauses that reference b.v1, b.v2, b.v1 in that
1256 * order. This is not harmful in itself, though it suggests that
1257 * the clauses are partially redundant. Since the alternative is
1258 * to omit mergejoin clauses and thereby possibly fail to generate a
1259 * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1260 * has to delete duplicates when it constructs the inner pathkeys
1261 * list, and we also have to deal with such cases specially in
1262 * create_mergejoin_plan().
1263 *----------
1264 */
1265 foreach(j, restrictinfos)
1266 {
1267 RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1268 EquivalenceClass *clause_ec;
1269
1270 clause_ec = rinfo->outer_is_left ?
1271 rinfo->left_ec : rinfo->right_ec;
1272 if (clause_ec == pathkey_ec)
1273 matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1274 }
1275
1276 /*
1277 * If we didn't find a mergeclause, we're done --- any additional
1278 * sort-key positions in the pathkeys are useless. (But we can still
1279 * mergejoin if we found at least one mergeclause.)
1280 */
1281 if (matched_restrictinfos == NIL)
1282 break;
1283
1284 /*
1285 * If we did find usable mergeclause(s) for this sort-key position,
1286 * add them to result list.
1287 */
1288 mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1289 }
1290
1291 return mergeclauses;
1292}
1293
1294/*
1295 * select_outer_pathkeys_for_merge
1296 * Builds a pathkey list representing a possible sort ordering
1297 * that can be used with the given mergeclauses.
1298 *
1299 * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
1300 * that will be used in a merge join.
1301 * 'joinrel' is the join relation we are trying to construct.
1302 *
1303 * The restrictinfos must be marked (via outer_is_left) to show which side
1304 * of each clause is associated with the current outer path. (See
1305 * select_mergejoin_clauses())
1306 *
1307 * Returns a pathkeys list that can be applied to the outer relation.
1308 *
1309 * Since we assume here that a sort is required, there is no particular use
1310 * in matching any available ordering of the outerrel. (joinpath.c has an
1311 * entirely separate code path for considering sort-free mergejoins.) Rather,
1312 * it's interesting to try to match the requested query_pathkeys so that a
1313 * second output sort may be avoided; and failing that, we try to list "more
1314 * popular" keys (those with the most unmatched EquivalenceClass peers)
1315 * earlier, in hopes of making the resulting ordering useful for as many
1316 * higher-level mergejoins as possible.
1317 */
1318List *
1319select_outer_pathkeys_for_merge(PlannerInfo *root,
1320 List *mergeclauses,
1321 RelOptInfo *joinrel)
1322{
1323 List *pathkeys = NIL;
1324 int nClauses = list_length(mergeclauses);
1325 EquivalenceClass **ecs;
1326 int *scores;
1327 int necs;
1328 ListCell *lc;
1329 int j;
1330
1331 /* Might have no mergeclauses */
1332 if (nClauses == 0)
1333 return NIL;
1334
1335 /*
1336 * Make arrays of the ECs used by the mergeclauses (dropping any
1337 * duplicates) and their "popularity" scores.
1338 */
1339 ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
1340 scores = (int *) palloc(nClauses * sizeof(int));
1341 necs = 0;
1342
1343 foreach(lc, mergeclauses)
1344 {
1345 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1346 EquivalenceClass *oeclass;
1347 int score;
1348 ListCell *lc2;
1349
1350 /* get the outer eclass */
1351 update_mergeclause_eclasses(root, rinfo);
1352
1353 if (rinfo->outer_is_left)
1354 oeclass = rinfo->left_ec;
1355 else
1356 oeclass = rinfo->right_ec;
1357
1358 /* reject duplicates */
1359 for (j = 0; j < necs; j++)
1360 {
1361 if (ecs[j] == oeclass)
1362 break;
1363 }
1364 if (j < necs)
1365 continue;
1366
1367 /* compute score */
1368 score = 0;
1369 foreach(lc2, oeclass->ec_members)
1370 {
1371 EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
1372
1373 /* Potential future join partner? */
1374 if (!em->em_is_const && !em->em_is_child &&
1375 !bms_overlap(em->em_relids, joinrel->relids))
1376 score++;
1377 }
1378
1379 ecs[necs] = oeclass;
1380 scores[necs] = score;
1381 necs++;
1382 }
1383
1384 /*
1385 * Find out if we have all the ECs mentioned in query_pathkeys; if so we
1386 * can generate a sort order that's also useful for final output. There is
1387 * no percentage in a partial match, though, so we have to have 'em all.
1388 */
1389 if (root->query_pathkeys)
1390 {
1391 foreach(lc, root->query_pathkeys)
1392 {
1393 PathKey *query_pathkey = (PathKey *) lfirst(lc);
1394 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1395
1396 for (j = 0; j < necs; j++)
1397 {
1398 if (ecs[j] == query_ec)
1399 break; /* found match */
1400 }
1401 if (j >= necs)
1402 break; /* didn't find match */
1403 }
1404 /* if we got to the end of the list, we have them all */
1405 if (lc == NULL)
1406 {
1407 /* copy query_pathkeys as starting point for our output */
1408 pathkeys = list_copy(root->query_pathkeys);
1409 /* mark their ECs as already-emitted */
1410 foreach(lc, root->query_pathkeys)
1411 {
1412 PathKey *query_pathkey = (PathKey *) lfirst(lc);
1413 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1414
1415 for (j = 0; j < necs; j++)
1416 {
1417 if (ecs[j] == query_ec)
1418 {
1419 scores[j] = -1;
1420 break;
1421 }
1422 }
1423 }
1424 }
1425 }
1426
1427 /*
1428 * Add remaining ECs to the list in popularity order, using a default sort
1429 * ordering. (We could use qsort() here, but the list length is usually
1430 * so small it's not worth it.)
1431 */
1432 for (;;)
1433 {
1434 int best_j;
1435 int best_score;
1436 EquivalenceClass *ec;
1437 PathKey *pathkey;
1438
1439 best_j = 0;
1440 best_score = scores[0];
1441 for (j = 1; j < necs; j++)
1442 {
1443 if (scores[j] > best_score)
1444 {
1445 best_j = j;
1446 best_score = scores[j];
1447 }
1448 }
1449 if (best_score < 0)
1450 break; /* all done */
1451 ec = ecs[best_j];
1452 scores[best_j] = -1;
1453 pathkey = make_canonical_pathkey(root,
1454 ec,
1455 linitial_oid(ec->ec_opfamilies),
1456 BTLessStrategyNumber,
1457 false);
1458 /* can't be redundant because no duplicate ECs */
1459 Assert(!pathkey_is_redundant(pathkey, pathkeys));
1460 pathkeys = lappend(pathkeys, pathkey);
1461 }
1462
1463 pfree(ecs);
1464 pfree(scores);
1465
1466 return pathkeys;
1467}
1468
1469/*
1470 * make_inner_pathkeys_for_merge
1471 * Builds a pathkey list representing the explicit sort order that
1472 * must be applied to an inner path to make it usable with the
1473 * given mergeclauses.
1474 *
1475 * 'mergeclauses' is a list of RestrictInfos for the mergejoin clauses
1476 * that will be used in a merge join, in order.
1477 * 'outer_pathkeys' are the already-known canonical pathkeys for the outer
1478 * side of the join.
1479 *
1480 * The restrictinfos must be marked (via outer_is_left) to show which side
1481 * of each clause is associated with the current outer path. (See
1482 * select_mergejoin_clauses())
1483 *
1484 * Returns a pathkeys list that can be applied to the inner relation.
1485 *
1486 * Note that it is not this routine's job to decide whether sorting is
1487 * actually needed for a particular input path. Assume a sort is necessary;
1488 * just make the keys, eh?
1489 */
1490List *
1491make_inner_pathkeys_for_merge(PlannerInfo *root,
1492 List *mergeclauses,
1493 List *outer_pathkeys)
1494{
1495 List *pathkeys = NIL;
1496 EquivalenceClass *lastoeclass;
1497 PathKey *opathkey;
1498 ListCell *lc;
1499 ListCell *lop;
1500
1501 lastoeclass = NULL;
1502 opathkey = NULL;
1503 lop = list_head(outer_pathkeys);
1504
1505 foreach(lc, mergeclauses)
1506 {
1507 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1508 EquivalenceClass *oeclass;
1509 EquivalenceClass *ieclass;
1510 PathKey *pathkey;
1511
1512 update_mergeclause_eclasses(root, rinfo);
1513
1514 if (rinfo->outer_is_left)
1515 {
1516 oeclass = rinfo->left_ec;
1517 ieclass = rinfo->right_ec;
1518 }
1519 else
1520 {
1521 oeclass = rinfo->right_ec;
1522 ieclass = rinfo->left_ec;
1523 }
1524
1525 /* outer eclass should match current or next pathkeys */
1526 /* we check this carefully for debugging reasons */
1527 if (oeclass != lastoeclass)
1528 {
1529 if (!lop)
1530 elog(ERROR, "too few pathkeys for mergeclauses");
1531 opathkey = (PathKey *) lfirst(lop);
1532 lop = lnext(lop);
1533 lastoeclass = opathkey->pk_eclass;
1534 if (oeclass != lastoeclass)
1535 elog(ERROR, "outer pathkeys do not match mergeclause");
1536 }
1537
1538 /*
1539 * Often, we'll have same EC on both sides, in which case the outer
1540 * pathkey is also canonical for the inner side, and we can skip a
1541 * useless search.
1542 */
1543 if (ieclass == oeclass)
1544 pathkey = opathkey;
1545 else
1546 pathkey = make_canonical_pathkey(root,
1547 ieclass,
1548 opathkey->pk_opfamily,
1549 opathkey->pk_strategy,
1550 opathkey->pk_nulls_first);
1551
1552 /*
1553 * Don't generate redundant pathkeys (which can happen if multiple
1554 * mergeclauses refer to the same EC). Because we do this, the output
1555 * pathkey list isn't necessarily ordered like the mergeclauses, which
1556 * complicates life for create_mergejoin_plan(). But if we didn't,
1557 * we'd have a noncanonical sort key list, which would be bad; for one
1558 * reason, it certainly wouldn't match any available sort order for
1559 * the input relation.
1560 */
1561 if (!pathkey_is_redundant(pathkey, pathkeys))
1562 pathkeys = lappend(pathkeys, pathkey);
1563 }
1564
1565 return pathkeys;
1566}
1567
1568/*
1569 * trim_mergeclauses_for_inner_pathkeys
1570 * This routine trims a list of mergeclauses to include just those that
1571 * work with a specified ordering for the join's inner relation.
1572 *
1573 * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses for the
1574 * join relation being formed, in an order known to work for the
1575 * currently-considered sort ordering of the join's outer rel.
1576 * 'pathkeys' is a pathkeys list showing the ordering of an inner-rel path;
1577 * it should be equal to, or a truncation of, the result of
1578 * make_inner_pathkeys_for_merge for these mergeclauses.
1579 *
1580 * What we return will be a prefix of the given mergeclauses list.
1581 *
1582 * We need this logic because make_inner_pathkeys_for_merge's result isn't
1583 * necessarily in the same order as the mergeclauses. That means that if we
1584 * consider an inner-rel pathkey list that is a truncation of that result,
1585 * we might need to drop mergeclauses even though they match a surviving inner
1586 * pathkey. This happens when they are to the right of a mergeclause that
1587 * matches a removed inner pathkey.
1588 *
1589 * The mergeclauses must be marked (via outer_is_left) to show which side
1590 * of each clause is associated with the current outer path. (See
1591 * select_mergejoin_clauses())
1592 */
1593List *
1594trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root,
1595 List *mergeclauses,
1596 List *pathkeys)
1597{
1598 List *new_mergeclauses = NIL;
1599 PathKey *pathkey;
1600 EquivalenceClass *pathkey_ec;
1601 bool matched_pathkey;
1602 ListCell *lip;
1603 ListCell *i;
1604
1605 /* No pathkeys => no mergeclauses (though we don't expect this case) */
1606 if (pathkeys == NIL)
1607 return NIL;
1608 /* Initialize to consider first pathkey */
1609 lip = list_head(pathkeys);
1610 pathkey = (PathKey *) lfirst(lip);
1611 pathkey_ec = pathkey->pk_eclass;
1612 lip = lnext(lip);
1613 matched_pathkey = false;
1614
1615 /* Scan mergeclauses to see how many we can use */
1616 foreach(i, mergeclauses)
1617 {
1618 RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1619 EquivalenceClass *clause_ec;
1620
1621 /* Assume we needn't do update_mergeclause_eclasses again here */
1622
1623 /* Check clause's inner-rel EC against current pathkey */
1624 clause_ec = rinfo->outer_is_left ?
1625 rinfo->right_ec : rinfo->left_ec;
1626
1627 /* If we don't have a match, attempt to advance to next pathkey */
1628 if (clause_ec != pathkey_ec)
1629 {
1630 /* If we had no clauses matching this inner pathkey, must stop */
1631 if (!matched_pathkey)
1632 break;
1633
1634 /* Advance to next inner pathkey, if any */
1635 if (lip == NULL)
1636 break;
1637 pathkey = (PathKey *) lfirst(lip);
1638 pathkey_ec = pathkey->pk_eclass;
1639 lip = lnext(lip);
1640 matched_pathkey = false;
1641 }
1642
1643 /* If mergeclause matches current inner pathkey, we can use it */
1644 if (clause_ec == pathkey_ec)
1645 {
1646 new_mergeclauses = lappend(new_mergeclauses, rinfo);
1647 matched_pathkey = true;
1648 }
1649 else
1650 {
1651 /* Else, no hope of adding any more mergeclauses */
1652 break;
1653 }
1654 }
1655
1656 return new_mergeclauses;
1657}
1658
1659
1660/****************************************************************************
1661 * PATHKEY USEFULNESS CHECKS
1662 *
1663 * We only want to remember as many of the pathkeys of a path as have some
1664 * potential use, either for subsequent mergejoins or for meeting the query's
1665 * requested output ordering. This ensures that add_path() won't consider
1666 * a path to have a usefully different ordering unless it really is useful.
1667 * These routines check for usefulness of given pathkeys.
1668 ****************************************************************************/
1669
1670/*
1671 * pathkeys_useful_for_merging
1672 * Count the number of pathkeys that may be useful for mergejoins
1673 * above the given relation.
1674 *
1675 * We consider a pathkey potentially useful if it corresponds to the merge
1676 * ordering of either side of any joinclause for the rel. This might be
1677 * overoptimistic, since joinclauses that require different other relations
1678 * might never be usable at the same time, but trying to be exact is likely
1679 * to be more trouble than it's worth.
1680 *
1681 * To avoid doubling the number of mergejoin paths considered, we would like
1682 * to consider only one of the two scan directions (ASC or DESC) as useful
1683 * for merging for any given target column. The choice is arbitrary unless
1684 * one of the directions happens to match an ORDER BY key, in which case
1685 * that direction should be preferred, in hopes of avoiding a final sort step.
1686 * right_merge_direction() implements this heuristic.
1687 */
1688static int
1689pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
1690{
1691 int useful = 0;
1692 ListCell *i;
1693
1694 foreach(i, pathkeys)
1695 {
1696 PathKey *pathkey = (PathKey *) lfirst(i);
1697 bool matched = false;
1698 ListCell *j;
1699
1700 /* If "wrong" direction, not useful for merging */
1701 if (!right_merge_direction(root, pathkey))
1702 break;
1703
1704 /*
1705 * First look into the EquivalenceClass of the pathkey, to see if
1706 * there are any members not yet joined to the rel. If so, it's
1707 * surely possible to generate a mergejoin clause using them.
1708 */
1709 if (rel->has_eclass_joins &&
1710 eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
1711 matched = true;
1712 else
1713 {
1714 /*
1715 * Otherwise search the rel's joininfo list, which contains
1716 * non-EquivalenceClass-derivable join clauses that might
1717 * nonetheless be mergejoinable.
1718 */
1719 foreach(j, rel->joininfo)
1720 {
1721 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
1722
1723 if (restrictinfo->mergeopfamilies == NIL)
1724 continue;
1725 update_mergeclause_eclasses(root, restrictinfo);
1726
1727 if (pathkey->pk_eclass == restrictinfo->left_ec ||
1728 pathkey->pk_eclass == restrictinfo->right_ec)
1729 {
1730 matched = true;
1731 break;
1732 }
1733 }
1734 }
1735
1736 /*
1737 * If we didn't find a mergeclause, we're done --- any additional
1738 * sort-key positions in the pathkeys are useless. (But we can still
1739 * mergejoin if we found at least one mergeclause.)
1740 */
1741 if (matched)
1742 useful++;
1743 else
1744 break;
1745 }
1746
1747 return useful;
1748}
1749
1750/*
1751 * right_merge_direction
1752 * Check whether the pathkey embodies the preferred sort direction
1753 * for merging its target column.
1754 */
1755static bool
1756right_merge_direction(PlannerInfo *root, PathKey *pathkey)
1757{
1758 ListCell *l;
1759
1760 foreach(l, root->query_pathkeys)
1761 {
1762 PathKey *query_pathkey = (PathKey *) lfirst(l);
1763
1764 if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
1765 pathkey->pk_opfamily == query_pathkey->pk_opfamily)
1766 {
1767 /*
1768 * Found a matching query sort column. Prefer this pathkey's
1769 * direction iff it matches. Note that we ignore pk_nulls_first,
1770 * which means that a sort might be needed anyway ... but we still
1771 * want to prefer only one of the two possible directions, and we
1772 * might as well use this one.
1773 */
1774 return (pathkey->pk_strategy == query_pathkey->pk_strategy);
1775 }
1776 }
1777
1778 /* If no matching ORDER BY request, prefer the ASC direction */
1779 return (pathkey->pk_strategy == BTLessStrategyNumber);
1780}
1781
1782/*
1783 * pathkeys_useful_for_ordering
1784 * Count the number of pathkeys that are useful for meeting the
1785 * query's requested output ordering.
1786 *
1787 * Unlike merge pathkeys, this is an all-or-nothing affair: it does us
1788 * no good to order by just the first key(s) of the requested ordering.
1789 * So the result is always either 0 or list_length(root->query_pathkeys).
1790 */
1791static int
1792pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
1793{
1794 if (root->query_pathkeys == NIL)
1795 return 0; /* no special ordering requested */
1796
1797 if (pathkeys == NIL)
1798 return 0; /* unordered path */
1799
1800 if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
1801 {
1802 /* It's useful ... or at least the first N keys are */
1803 return list_length(root->query_pathkeys);
1804 }
1805
1806 return 0; /* path ordering not useful */
1807}
1808
1809/*
1810 * truncate_useless_pathkeys
1811 * Shorten the given pathkey list to just the useful pathkeys.
1812 */
1813List *
1814truncate_useless_pathkeys(PlannerInfo *root,
1815 RelOptInfo *rel,
1816 List *pathkeys)
1817{
1818 int nuseful;
1819 int nuseful2;
1820
1821 nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
1822 nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
1823 if (nuseful2 > nuseful)
1824 nuseful = nuseful2;
1825
1826 /*
1827 * Note: not safe to modify input list destructively, but we can avoid
1828 * copying the list if we're not actually going to change it
1829 */
1830 if (nuseful == 0)
1831 return NIL;
1832 else if (nuseful == list_length(pathkeys))
1833 return pathkeys;
1834 else
1835 return list_truncate(list_copy(pathkeys), nuseful);
1836}
1837
1838/*
1839 * has_useful_pathkeys
1840 * Detect whether the specified rel could have any pathkeys that are
1841 * useful according to truncate_useless_pathkeys().
1842 *
1843 * This is a cheap test that lets us skip building pathkeys at all in very
1844 * simple queries. It's OK to err in the direction of returning "true" when
1845 * there really aren't any usable pathkeys, but erring in the other direction
1846 * is bad --- so keep this in sync with the routines above!
1847 *
1848 * We could make the test more complex, for example checking to see if any of
1849 * the joinclauses are really mergejoinable, but that likely wouldn't win
1850 * often enough to repay the extra cycles. Queries with neither a join nor
1851 * a sort are reasonably common, though, so this much work seems worthwhile.
1852 */
1853bool
1854has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel)
1855{
1856 if (rel->joininfo != NIL || rel->has_eclass_joins)
1857 return true; /* might be able to use pathkeys for merging */
1858 if (root->query_pathkeys != NIL)
1859 return true; /* might be able to use them for ordering */
1860 return false; /* definitely useless */
1861}
1862