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