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