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