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