PostgreSQL Source Code  git master
pathkeys.c File Reference
Include dependency graph for pathkeys.c:

Go to the source code of this file.

Functions

static bool pathkey_is_redundant (PathKey *new_pathkey, List *pathkeys)
 
static bool matches_boolean_partition_clause (RestrictInfo *rinfo, RelOptInfo *partrel, int partkeycol)
 
static Varfind_var_for_subquery_tle (RelOptInfo *rel, TargetEntry *tle)
 
static bool right_merge_direction (PlannerInfo *root, PathKey *pathkey)
 
PathKeymake_canonical_pathkey (PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
 
Listappend_pathkeys (List *target, List *source)
 
static PathKeymake_pathkey_from_sortinfo (PlannerInfo *root, Expr *expr, Oid opfamily, Oid opcintype, Oid collation, bool reverse_sort, bool nulls_first, Index sortref, Relids rel, bool create_it)
 
static PathKeymake_pathkey_from_sortop (PlannerInfo *root, Expr *expr, Oid ordering_op, bool nulls_first, Index sortref, bool create_it)
 
PathKeysComparison compare_pathkeys (List *keys1, List *keys2)
 
bool pathkeys_contained_in (List *keys1, List *keys2)
 
bool pathkeys_count_contained_in (List *keys1, List *keys2, int *n_common)
 
Pathget_cheapest_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
 
Pathget_cheapest_fractional_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, double fraction)
 
Pathget_cheapest_parallel_safe_total_inner (List *paths)
 
Listbuild_index_pathkeys (PlannerInfo *root, IndexOptInfo *index, ScanDirection scandir)
 
static bool partkey_is_bool_constant_for_query (RelOptInfo *partrel, int partkeycol)
 
Listbuild_partition_pathkeys (PlannerInfo *root, RelOptInfo *partrel, ScanDirection scandir, bool *partialkeys)
 
Listbuild_expression_pathkey (PlannerInfo *root, Expr *expr, Oid opno, Relids rel, bool create_it)
 
Listconvert_subquery_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *subquery_pathkeys, List *subquery_tlist)
 
Listbuild_join_pathkeys (PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
 
Listmake_pathkeys_for_sortclauses (PlannerInfo *root, List *sortclauses, List *tlist)
 
Listmake_pathkeys_for_sortclauses_extended (PlannerInfo *root, List **sortclauses, List *tlist, bool remove_redundant, bool *sortable)
 
void initialize_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
 
void update_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
 
Listfind_mergeclauses_for_outer_pathkeys (PlannerInfo *root, List *pathkeys, List *restrictinfos)
 
Listselect_outer_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
 
Listmake_inner_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
 
Listtrim_mergeclauses_for_inner_pathkeys (PlannerInfo *root, List *mergeclauses, List *pathkeys)
 
static int pathkeys_useful_for_merging (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 
static int pathkeys_useful_for_ordering (PlannerInfo *root, List *pathkeys)
 
Listtruncate_useless_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 
bool has_useful_pathkeys (PlannerInfo *root, RelOptInfo *rel)
 

Function Documentation

◆ append_pathkeys()

List* append_pathkeys ( List target,
List source 
)

Definition at line 105 of file pathkeys.c.

106 {
107  ListCell *lc;
108 
109  Assert(target != NIL);
110 
111  foreach(lc, source)
112  {
113  PathKey *pk = lfirst_node(PathKey, lc);
114 
115  if (!pathkey_is_redundant(pk, target))
116  target = lappend(target, pk);
117  }
118  return target;
119 }
Assert(fmt[strlen(fmt) - 1] !='\n')
List * lappend(List *list, void *datum)
Definition: list.c:338
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:157
#define lfirst_node(type, lc)
Definition: pg_list.h:176
#define NIL
Definition: pg_list.h:68
static rewind_source * source
Definition: pg_rewind.c:89

References Assert(), lappend(), lfirst_node, NIL, pathkey_is_redundant(), and source.

Referenced by adjust_group_pathkeys_for_groupagg(), and make_pathkeys_for_window().

◆ build_expression_pathkey()

List* build_expression_pathkey ( PlannerInfo root,
Expr expr,
Oid  opno,
Relids  rel,
bool  create_it 
)

Definition at line 801 of file pathkeys.c.

806 {
807  List *pathkeys;
808  Oid opfamily,
809  opcintype;
810  int16 strategy;
811  PathKey *cpathkey;
812 
813  /* Find the operator in pg_amop --- failure shouldn't happen */
814  if (!get_ordering_op_properties(opno,
815  &opfamily, &opcintype, &strategy))
816  elog(ERROR, "operator %u is not a valid ordering operator",
817  opno);
818 
819  cpathkey = make_pathkey_from_sortinfo(root,
820  expr,
821  opfamily,
822  opcintype,
823  exprCollation((Node *) expr),
824  (strategy == BTGreaterStrategyNumber),
825  (strategy == BTGreaterStrategyNumber),
826  0,
827  rel,
828  create_it);
829 
830  if (cpathkey)
831  pathkeys = list_make1(cpathkey);
832  else
833  pathkeys = NIL;
834 
835  return pathkeys;
836 }
signed short int16
Definition: c.h:482
#define ERROR
Definition: elog.h:39
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, int16 *strategy)
Definition: lsyscache.c:206
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:786
static PathKey * make_pathkey_from_sortinfo(PlannerInfo *root, Expr *expr, Oid opfamily, Oid opcintype, Oid collation, bool reverse_sort, bool nulls_first, Index sortref, Relids rel, bool create_it)
Definition: pathkeys.c:196
#define list_make1(x1)
Definition: pg_list.h:212
unsigned int Oid
Definition: postgres_ext.h:31
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Definition: pg_list.h:54
Definition: nodes.h:129

References BTGreaterStrategyNumber, elog(), ERROR, exprCollation(), get_ordering_op_properties(), list_make1, make_pathkey_from_sortinfo(), and NIL.

Referenced by set_function_pathlist().

◆ build_index_pathkeys()

List* build_index_pathkeys ( PlannerInfo root,
IndexOptInfo index,
ScanDirection  scandir 
)

Definition at line 541 of file pathkeys.c.

544 {
545  List *retval = NIL;
546  ListCell *lc;
547  int i;
548 
549  if (index->sortopfamily == NULL)
550  return NIL; /* non-orderable index */
551 
552  i = 0;
553  foreach(lc, index->indextlist)
554  {
555  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
556  Expr *indexkey;
557  bool reverse_sort;
558  bool nulls_first;
559  PathKey *cpathkey;
560 
561  /*
562  * INCLUDE columns are stored in index unordered, so they don't
563  * support ordered index scan.
564  */
565  if (i >= index->nkeycolumns)
566  break;
567 
568  /* We assume we don't need to make a copy of the tlist item */
569  indexkey = indextle->expr;
570 
571  if (ScanDirectionIsBackward(scandir))
572  {
573  reverse_sort = !index->reverse_sort[i];
574  nulls_first = !index->nulls_first[i];
575  }
576  else
577  {
578  reverse_sort = index->reverse_sort[i];
579  nulls_first = index->nulls_first[i];
580  }
581 
582  /*
583  * OK, try to make a canonical pathkey for this sort key.
584  */
585  cpathkey = make_pathkey_from_sortinfo(root,
586  indexkey,
587  index->sortopfamily[i],
588  index->opcintype[i],
589  index->indexcollations[i],
590  reverse_sort,
591  nulls_first,
592  0,
593  index->rel->relids,
594  false);
595 
596  if (cpathkey)
597  {
598  /*
599  * We found the sort key in an EquivalenceClass, so it's relevant
600  * for this query. Add it to list, unless it's redundant.
601  */
602  if (!pathkey_is_redundant(cpathkey, retval))
603  retval = lappend(retval, cpathkey);
604  }
605  else
606  {
607  /*
608  * Boolean index keys might be redundant even if they do not
609  * appear in an EquivalenceClass, because of our special treatment
610  * of boolean equality conditions --- see the comment for
611  * indexcol_is_bool_constant_for_query(). If that applies, we can
612  * continue to examine lower-order index columns. Otherwise, the
613  * sort key is not an interesting sort order for this query, so we
614  * should stop considering index columns; any lower-order sort
615  * keys won't be useful either.
616  */
618  break;
619  }
620 
621  i++;
622  }
623 
624  return retval;
625 }
bool indexcol_is_bool_constant_for_query(PlannerInfo *root, IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3668
int i
Definition: isn.c:73
#define lfirst(lc)
Definition: pg_list.h:172
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:50
Expr * expr
Definition: primnodes.h:1895
Definition: type.h:95

References TargetEntry::expr, i, indexcol_is_bool_constant_for_query(), lappend(), lfirst, make_pathkey_from_sortinfo(), NIL, pathkey_is_redundant(), and ScanDirectionIsBackward.

Referenced by build_index_paths().

◆ build_join_pathkeys()

List* build_join_pathkeys ( PlannerInfo root,
RelOptInfo joinrel,
JoinType  jointype,
List outer_pathkeys 
)

Definition at line 1095 of file pathkeys.c.

1099 {
1100  if (jointype == JOIN_FULL ||
1101  jointype == JOIN_RIGHT ||
1102  jointype == JOIN_RIGHT_ANTI)
1103  return NIL;
1104 
1105  /*
1106  * This used to be quite a complex bit of code, but now that all pathkey
1107  * sublists start out life canonicalized, we don't have to do a darn thing
1108  * here!
1109  *
1110  * We do, however, need to truncate the pathkeys list, since it may
1111  * contain pathkeys that were useful for forming this joinrel but are
1112  * uninteresting to higher levels.
1113  */
1114  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1115 }
@ JOIN_FULL
Definition: nodes.h:306
@ JOIN_RIGHT
Definition: nodes.h:307
@ JOIN_RIGHT_ANTI
Definition: nodes.h:320
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:1947

References JOIN_FULL, JOIN_RIGHT, JOIN_RIGHT_ANTI, NIL, and truncate_useless_pathkeys().

Referenced by consider_parallel_mergejoin(), consider_parallel_nestloop(), match_unsorted_outer(), and sort_inner_and_outer().

◆ build_partition_pathkeys()

List* build_partition_pathkeys ( PlannerInfo root,
RelOptInfo partrel,
ScanDirection  scandir,
bool partialkeys 
)

Definition at line 720 of file pathkeys.c.

722 {
723  List *retval = NIL;
724  PartitionScheme partscheme = partrel->part_scheme;
725  int i;
726 
727  Assert(partscheme != NULL);
728  Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
729  /* For now, we can only cope with baserels */
730  Assert(IS_SIMPLE_REL(partrel));
731 
732  for (i = 0; i < partscheme->partnatts; i++)
733  {
734  PathKey *cpathkey;
735  Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
736 
737  /*
738  * Try to make a canonical pathkey for this partkey.
739  *
740  * We assume the PartitionDesc lists any NULL partition last, so we
741  * treat the scan like a NULLS LAST index: we have nulls_first for
742  * backwards scan only.
743  */
744  cpathkey = make_pathkey_from_sortinfo(root,
745  keyCol,
746  partscheme->partopfamily[i],
747  partscheme->partopcintype[i],
748  partscheme->partcollation[i],
749  ScanDirectionIsBackward(scandir),
750  ScanDirectionIsBackward(scandir),
751  0,
752  partrel->relids,
753  false);
754 
755 
756  if (cpathkey)
757  {
758  /*
759  * We found the sort key in an EquivalenceClass, so it's relevant
760  * for this query. Add it to list, unless it's redundant.
761  */
762  if (!pathkey_is_redundant(cpathkey, retval))
763  retval = lappend(retval, cpathkey);
764  }
765  else
766  {
767  /*
768  * Boolean partition keys might be redundant even if they do not
769  * appear in an EquivalenceClass, because of our special treatment
770  * of boolean equality conditions --- see the comment for
771  * partkey_is_bool_constant_for_query(). If that applies, we can
772  * continue to examine lower-order partition keys. Otherwise, the
773  * sort key is not an interesting sort order for this query, so we
774  * should stop considering partition columns; any lower-order sort
775  * keys won't be useful either.
776  */
777  if (!partkey_is_bool_constant_for_query(partrel, i))
778  {
779  *partialkeys = true;
780  return retval;
781  }
782  }
783  }
784 
785  *partialkeys = false;
786  return retval;
787 }
bool partitions_are_ordered(PartitionBoundInfo boundinfo, Bitmapset *live_parts)
Definition: partbounds.c:2853
static bool partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:645
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:824
#define linitial(l)
Definition: pg_list.h:178
Relids relids
Definition: pathnodes.h:856
Bitmapset * live_parts
Definition: pathnodes.h:1018

References Assert(), i, IS_SIMPLE_REL, lappend(), linitial, RelOptInfo::live_parts, make_pathkey_from_sortinfo(), NIL, PartitionSchemeData::partcollation, partitions_are_ordered(), partkey_is_bool_constant_for_query(), PartitionSchemeData::partnatts, PartitionSchemeData::partopcintype, PartitionSchemeData::partopfamily, pathkey_is_redundant(), RelOptInfo::relids, and ScanDirectionIsBackward.

Referenced by generate_orderedappend_paths().

◆ compare_pathkeys()

PathKeysComparison compare_pathkeys ( List keys1,
List keys2 
)

Definition at line 301 of file pathkeys.c.

302 {
303  ListCell *key1,
304  *key2;
305 
306  /*
307  * Fall out quickly if we are passed two identical lists. This mostly
308  * catches the case where both are NIL, but that's common enough to
309  * warrant the test.
310  */
311  if (keys1 == keys2)
312  return PATHKEYS_EQUAL;
313 
314  forboth(key1, keys1, key2, keys2)
315  {
316  PathKey *pathkey1 = (PathKey *) lfirst(key1);
317  PathKey *pathkey2 = (PathKey *) lfirst(key2);
318 
319  if (pathkey1 != pathkey2)
320  return PATHKEYS_DIFFERENT; /* no need to keep looking */
321  }
322 
323  /*
324  * If we reached the end of only one list, the other is longer and
325  * therefore not a subset.
326  */
327  if (key1 != NULL)
328  return PATHKEYS_BETTER1; /* key1 is longer */
329  if (key2 != NULL)
330  return PATHKEYS_BETTER2; /* key2 is longer */
331  return PATHKEYS_EQUAL;
332 }
@ PATHKEYS_BETTER2
Definition: paths.h:201
@ PATHKEYS_BETTER1
Definition: paths.h:200
@ PATHKEYS_DIFFERENT
Definition: paths.h:202
@ PATHKEYS_EQUAL
Definition: paths.h:199
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:467

References forboth, lfirst, PATHKEYS_BETTER1, PATHKEYS_BETTER2, PATHKEYS_DIFFERENT, and PATHKEYS_EQUAL.

Referenced by add_partial_path(), add_partial_path_precheck(), add_path(), add_path_precheck(), add_paths_to_append_rel(), adjust_group_pathkeys_for_groupagg(), pathkeys_contained_in(), and set_cheapest().

◆ convert_subquery_pathkeys()

List* convert_subquery_pathkeys ( PlannerInfo root,
RelOptInfo rel,
List subquery_pathkeys,
List subquery_tlist 
)

Definition at line 855 of file pathkeys.c.

858 {
859  List *retval = NIL;
860  int retvallen = 0;
861  int outer_query_keys = list_length(root->query_pathkeys);
862  ListCell *i;
863 
864  foreach(i, subquery_pathkeys)
865  {
866  PathKey *sub_pathkey = (PathKey *) lfirst(i);
867  EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
868  PathKey *best_pathkey = NULL;
869 
870  if (sub_eclass->ec_has_volatile)
871  {
872  /*
873  * If the sub_pathkey's EquivalenceClass is volatile, then it must
874  * have come from an ORDER BY clause, and we have to match it to
875  * that same targetlist entry.
876  */
877  TargetEntry *tle;
878  Var *outer_var;
879 
880  if (sub_eclass->ec_sortref == 0) /* can't happen */
881  elog(ERROR, "volatile EquivalenceClass has no sortref");
882  tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
883  Assert(tle);
884  /* Is TLE actually available to the outer query? */
885  outer_var = find_var_for_subquery_tle(rel, tle);
886  if (outer_var)
887  {
888  /* We can represent this sub_pathkey */
889  EquivalenceMember *sub_member;
890  EquivalenceClass *outer_ec;
891 
892  Assert(list_length(sub_eclass->ec_members) == 1);
893  sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
894 
895  /*
896  * Note: it might look funny to be setting sortref = 0 for a
897  * reference to a volatile sub_eclass. However, the
898  * expression is *not* volatile in the outer query: it's just
899  * a Var referencing whatever the subquery emitted. (IOW, the
900  * outer query isn't going to re-execute the volatile
901  * expression itself.) So this is okay.
902  */
903  outer_ec =
905  (Expr *) outer_var,
906  sub_eclass->ec_opfamilies,
907  sub_member->em_datatype,
908  sub_eclass->ec_collation,
909  0,
910  rel->relids,
911  false);
912 
913  /*
914  * If we don't find a matching EC, sub-pathkey isn't
915  * interesting to the outer query
916  */
917  if (outer_ec)
918  best_pathkey =
920  outer_ec,
921  sub_pathkey->pk_opfamily,
922  sub_pathkey->pk_strategy,
923  sub_pathkey->pk_nulls_first);
924  }
925  }
926  else
927  {
928  /*
929  * Otherwise, the sub_pathkey's EquivalenceClass could contain
930  * multiple elements (representing knowledge that multiple items
931  * are effectively equal). Each element might match none, one, or
932  * more of the output columns that are visible to the outer query.
933  * This means we may have multiple possible representations of the
934  * sub_pathkey in the context of the outer query. Ideally we
935  * would generate them all and put them all into an EC of the
936  * outer query, thereby propagating equality knowledge up to the
937  * outer query. Right now we cannot do so, because the outer
938  * query's EquivalenceClasses are already frozen when this is
939  * called. Instead we prefer the one that has the highest "score"
940  * (number of EC peers, plus one if it matches the outer
941  * query_pathkeys). This is the most likely to be useful in the
942  * outer query.
943  */
944  int best_score = -1;
945  ListCell *j;
946 
947  foreach(j, sub_eclass->ec_members)
948  {
949  EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
950  Expr *sub_expr = sub_member->em_expr;
951  Oid sub_expr_type = sub_member->em_datatype;
952  Oid sub_expr_coll = sub_eclass->ec_collation;
953  ListCell *k;
954 
955  if (sub_member->em_is_child)
956  continue; /* ignore children here */
957 
958  foreach(k, subquery_tlist)
959  {
960  TargetEntry *tle = (TargetEntry *) lfirst(k);
961  Var *outer_var;
962  Expr *tle_expr;
963  EquivalenceClass *outer_ec;
964  PathKey *outer_pk;
965  int score;
966 
967  /* Is TLE actually available to the outer query? */
968  outer_var = find_var_for_subquery_tle(rel, tle);
969  if (!outer_var)
970  continue;
971 
972  /*
973  * The targetlist entry is considered to match if it
974  * matches after sort-key canonicalization. That is
975  * needed since the sub_expr has been through the same
976  * process.
977  */
978  tle_expr = canonicalize_ec_expression(tle->expr,
979  sub_expr_type,
980  sub_expr_coll);
981  if (!equal(tle_expr, sub_expr))
982  continue;
983 
984  /* See if we have a matching EC for the TLE */
985  outer_ec = get_eclass_for_sort_expr(root,
986  (Expr *) outer_var,
987  sub_eclass->ec_opfamilies,
988  sub_expr_type,
989  sub_expr_coll,
990  0,
991  rel->relids,
992  false);
993 
994  /*
995  * If we don't find a matching EC, this sub-pathkey isn't
996  * interesting to the outer query
997  */
998  if (!outer_ec)
999  continue;
1000 
1001  outer_pk = make_canonical_pathkey(root,
1002  outer_ec,
1003  sub_pathkey->pk_opfamily,
1004  sub_pathkey->pk_strategy,
1005  sub_pathkey->pk_nulls_first);
1006  /* score = # of equivalence peers */
1007  score = list_length(outer_ec->ec_members) - 1;
1008  /* +1 if it matches the proper query_pathkeys item */
1009  if (retvallen < outer_query_keys &&
1010  list_nth(root->query_pathkeys, retvallen) == outer_pk)
1011  score++;
1012  if (score > best_score)
1013  {
1014  best_pathkey = outer_pk;
1015  best_score = score;
1016  }
1017  }
1018  }
1019  }
1020 
1021  /*
1022  * If we couldn't find a representation of this sub_pathkey, we're
1023  * done (we can't use the ones to its right, either).
1024  */
1025  if (!best_pathkey)
1026  break;
1027 
1028  /*
1029  * Eliminate redundant ordering info; could happen if outer query
1030  * equivalences subquery keys...
1031  */
1032  if (!pathkey_is_redundant(best_pathkey, retval))
1033  {
1034  retval = lappend(retval, best_pathkey);
1035  retvallen++;
1036  }
1037  }
1038 
1039  return retval;
1040 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:223
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:472
EquivalenceClass * get_eclass_for_sort_expr(PlannerInfo *root, Expr *expr, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
Definition: equivclass.c:587
int j
Definition: isn.c:74
static Var * find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
Definition: pathkeys.c:1052
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:54
static int list_length(const List *l)
Definition: pg_list.h:152
static void * list_nth(const List *list, int n)
Definition: pg_list.h:299
List * ec_opfamilies
Definition: pathnodes.h:1368
bool pk_nulls_first
Definition: pathnodes.h:1456
int pk_strategy
Definition: pathnodes.h:1455
Oid pk_opfamily
Definition: pathnodes.h:1454
List * query_pathkeys
Definition: pathnodes.h:382
Definition: primnodes.h:226
TargetEntry * get_sortgroupref_tle(Index sortref, List *targetList)
Definition: tlist.c:345

References Assert(), canonicalize_ec_expression(), EquivalenceClass::ec_collation, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_sortref, elog(), EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, equal(), ERROR, TargetEntry::expr, find_var_for_subquery_tle(), get_eclass_for_sort_expr(), get_sortgroupref_tle(), i, j, lappend(), lfirst, linitial, list_length(), list_nth(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, PlannerInfo::query_pathkeys, and RelOptInfo::relids.

Referenced by set_subquery_pathlist().

◆ find_mergeclauses_for_outer_pathkeys()

List* find_mergeclauses_for_outer_pathkeys ( PlannerInfo root,
List pathkeys,
List restrictinfos 
)

Definition at line 1313 of file pathkeys.c.

1316 {
1317  List *mergeclauses = NIL;
1318  ListCell *i;
1319 
1320  /* make sure we have eclasses cached in the clauses */
1321  foreach(i, restrictinfos)
1322  {
1323  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1324 
1325  update_mergeclause_eclasses(root, rinfo);
1326  }
1327 
1328  foreach(i, pathkeys)
1329  {
1330  PathKey *pathkey = (PathKey *) lfirst(i);
1331  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1332  List *matched_restrictinfos = NIL;
1333  ListCell *j;
1334 
1335  /*----------
1336  * A mergejoin clause matches a pathkey if it has the same EC.
1337  * If there are multiple matching clauses, take them all. In plain
1338  * inner-join scenarios we expect only one match, because
1339  * equivalence-class processing will have removed any redundant
1340  * mergeclauses. However, in outer-join scenarios there might be
1341  * multiple matches. An example is
1342  *
1343  * select * from a full join b
1344  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1345  *
1346  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1347  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1348  * we *must* do so or we will be unable to form a valid plan.
1349  *
1350  * We expect that the given pathkeys list is canonical, which means
1351  * no two members have the same EC, so it's not possible for this
1352  * code to enter the same mergeclause into the result list twice.
1353  *
1354  * It's possible that multiple matching clauses might have different
1355  * ECs on the other side, in which case the order we put them into our
1356  * result makes a difference in the pathkeys required for the inner
1357  * input rel. However this routine hasn't got any info about which
1358  * order would be best, so we don't worry about that.
1359  *
1360  * It's also possible that the selected mergejoin clauses produce
1361  * a noncanonical ordering of pathkeys for the inner side, ie, we
1362  * might select clauses that reference b.v1, b.v2, b.v1 in that
1363  * order. This is not harmful in itself, though it suggests that
1364  * the clauses are partially redundant. Since the alternative is
1365  * to omit mergejoin clauses and thereby possibly fail to generate a
1366  * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1367  * has to delete duplicates when it constructs the inner pathkeys
1368  * list, and we also have to deal with such cases specially in
1369  * create_mergejoin_plan().
1370  *----------
1371  */
1372  foreach(j, restrictinfos)
1373  {
1374  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1375  EquivalenceClass *clause_ec;
1376 
1377  clause_ec = rinfo->outer_is_left ?
1378  rinfo->left_ec : rinfo->right_ec;
1379  if (clause_ec == pathkey_ec)
1380  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1381  }
1382 
1383  /*
1384  * If we didn't find a mergeclause, we're done --- any additional
1385  * sort-key positions in the pathkeys are useless. (But we can still
1386  * mergejoin if we found at least one mergeclause.)
1387  */
1388  if (matched_restrictinfos == NIL)
1389  break;
1390 
1391  /*
1392  * If we did find usable mergeclause(s) for this sort-key position,
1393  * add them to result list.
1394  */
1395  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1396  }
1397 
1398  return mergeclauses;
1399 }
List * list_concat(List *list1, const List *list2)
Definition: list.c:560
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1279

References i, j, lappend(), lfirst, list_concat(), NIL, and update_mergeclause_eclasses().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

◆ find_var_for_subquery_tle()

static Var * find_var_for_subquery_tle ( RelOptInfo rel,
TargetEntry tle 
)
static

Definition at line 1052 of file pathkeys.c.

1053 {
1054  ListCell *lc;
1055 
1056  /* If the TLE is resjunk, it's certainly not visible to the outer query */
1057  if (tle->resjunk)
1058  return NULL;
1059 
1060  /* Search the rel's targetlist to see what it will return */
1061  foreach(lc, rel->reltarget->exprs)
1062  {
1063  Var *var = (Var *) lfirst(lc);
1064 
1065  /* Ignore placeholders */
1066  if (!IsA(var, Var))
1067  continue;
1068  Assert(var->varno == rel->relid);
1069 
1070  /* If we find a Var referencing this TLE, we're good */
1071  if (var->varattno == tle->resno)
1072  return copyObject(var); /* Make a copy for safety */
1073  }
1074  return NULL;
1075 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:179
#define copyObject(obj)
Definition: nodes.h:244
List * exprs
Definition: pathnodes.h:1501
struct PathTarget * reltarget
Definition: pathnodes.h:878
Index relid
Definition: pathnodes.h:903
AttrNumber resno
Definition: primnodes.h:1897
AttrNumber varattno
Definition: primnodes.h:238
int varno
Definition: primnodes.h:233

References Assert(), copyObject, PathTarget::exprs, IsA, lfirst, RelOptInfo::relid, RelOptInfo::reltarget, TargetEntry::resno, Var::varattno, and Var::varno.

Referenced by convert_subquery_pathkeys().

◆ get_cheapest_fractional_path_for_pathkeys()

Path* get_cheapest_fractional_path_for_pathkeys ( List paths,
List pathkeys,
Relids  required_outer,
double  fraction 
)

Definition at line 467 of file pathkeys.c.

471 {
472  Path *matched_path = NULL;
473  ListCell *l;
474 
475  foreach(l, paths)
476  {
477  Path *path = (Path *) lfirst(l);
478 
479  /*
480  * Since cost comparison is a lot cheaper than pathkey comparison, do
481  * that first. (XXX is that still true?)
482  */
483  if (matched_path != NULL &&
484  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
485  continue;
486 
487  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
488  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
489  matched_path = path;
490  }
491  return matched_path;
492 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:363
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:340
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:117
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1637
List * pathkeys
Definition: pathnodes.h:1633

References bms_is_subset(), compare_fractional_path_costs(), lfirst, PATH_REQ_OUTER, Path::pathkeys, and pathkeys_contained_in().

Referenced by build_minmax_path(), and generate_orderedappend_paths().

◆ get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner ( List paths)

Definition at line 500 of file pathkeys.c.

501 {
502  ListCell *l;
503 
504  foreach(l, paths)
505  {
506  Path *innerpath = (Path *) lfirst(l);
507 
508  if (innerpath->parallel_safe &&
509  bms_is_empty(PATH_REQ_OUTER(innerpath)))
510  return innerpath;
511  }
512 
513  return NULL;
514 }
#define bms_is_empty(a)
Definition: bitmapset.h:105
bool parallel_safe
Definition: pathnodes.h:1623

References bms_is_empty, lfirst, Path::parallel_safe, and PATH_REQ_OUTER.

Referenced by add_paths_to_append_rel(), hash_inner_and_outer(), match_unsorted_outer(), and sort_inner_and_outer().

◆ get_cheapest_path_for_pathkeys()

Path* get_cheapest_path_for_pathkeys ( List paths,
List pathkeys,
Relids  required_outer,
CostSelector  cost_criterion,
bool  require_parallel_safe 
)

Definition at line 421 of file pathkeys.c.

425 {
426  Path *matched_path = NULL;
427  ListCell *l;
428 
429  foreach(l, paths)
430  {
431  Path *path = (Path *) lfirst(l);
432 
433  /* If required, reject paths that are not parallel-safe */
434  if (require_parallel_safe && !path->parallel_safe)
435  continue;
436 
437  /*
438  * Since cost comparison is a lot cheaper than pathkey comparison, do
439  * that first. (XXX is that still true?)
440  */
441  if (matched_path != NULL &&
442  compare_path_costs(matched_path, path, cost_criterion) <= 0)
443  continue;
444 
445  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
446  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
447  matched_path = path;
448  }
449  return matched_path;
450 }
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:71

References bms_is_subset(), compare_path_costs(), lfirst, Path::parallel_safe, PATH_REQ_OUTER, Path::pathkeys, and pathkeys_contained_in().

Referenced by generate_mergejoin_paths(), generate_orderedappend_paths(), and get_cheapest_parameterized_child_path().

◆ has_useful_pathkeys()

bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 1987 of file pathkeys.c.

1988 {
1989  if (rel->joininfo != NIL || rel->has_eclass_joins)
1990  return true; /* might be able to use pathkeys for merging */
1991  if (root->query_pathkeys != NIL)
1992  return true; /* might be able to use them for ordering */
1993  return false; /* definitely useless */
1994 }
List * joininfo
Definition: pathnodes.h:970
bool has_eclass_joins
Definition: pathnodes.h:972

References RelOptInfo::has_eclass_joins, RelOptInfo::joininfo, NIL, and PlannerInfo::query_pathkeys.

Referenced by build_child_join_rel(), build_index_paths(), and set_append_rel_size().

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1232 of file pathkeys.c.

1233 {
1234  Expr *clause = restrictinfo->clause;
1235  Oid lefttype,
1236  righttype;
1237 
1238  /* Should be a mergeclause ... */
1239  Assert(restrictinfo->mergeopfamilies != NIL);
1240  /* ... with links not yet set */
1241  Assert(restrictinfo->left_ec == NULL);
1242  Assert(restrictinfo->right_ec == NULL);
1243 
1244  /* Need the declared input types of the operator */
1245  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1246 
1247  /* Find or create a matching EquivalenceClass for each side */
1248  restrictinfo->left_ec =
1250  (Expr *) get_leftop(clause),
1251  restrictinfo->mergeopfamilies,
1252  lefttype,
1253  ((OpExpr *) clause)->inputcollid,
1254  0,
1255  NULL,
1256  true);
1257  restrictinfo->right_ec =
1259  (Expr *) get_rightop(clause),
1260  restrictinfo->mergeopfamilies,
1261  righttype,
1262  ((OpExpr *) clause)->inputcollid,
1263  0,
1264  NULL,
1265  true);
1266 }
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1362
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:93
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:81
Expr * clause
Definition: pathnodes.h:2529

References Assert(), RestrictInfo::clause, get_eclass_for_sort_expr(), get_leftop(), get_rightop(), NIL, and op_input_types().

Referenced by distribute_qual_to_rels().

◆ make_canonical_pathkey()

PathKey* make_canonical_pathkey ( PlannerInfo root,
EquivalenceClass eclass,
Oid  opfamily,
int  strategy,
bool  nulls_first 
)

Definition at line 54 of file pathkeys.c.

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 }
#define makeNode(_type_)
Definition: nodes.h:176
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:138
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:500
List * canon_pathkeys
Definition: pathnodes.h:317
bool ec_merging_done
Definition: pathnodes.h:314

References PlannerInfo::canon_pathkeys, PlannerInfo::ec_merging_done, eclass(), elog(), ERROR, lappend(), lfirst, makeNode, MemoryContextSwitchTo(), PathKey::pk_nulls_first, PathKey::pk_opfamily, and PathKey::pk_strategy.

Referenced by convert_subquery_pathkeys(), get_useful_pathkeys_for_relation(), make_inner_pathkeys_for_merge(), make_pathkey_from_sortinfo(), and select_outer_pathkeys_for_merge().

◆ make_inner_pathkeys_for_merge()

List* make_inner_pathkeys_for_merge ( PlannerInfo root,
List mergeclauses,
List outer_pathkeys 
)

Definition at line 1624 of file pathkeys.c.

1627 {
1628  List *pathkeys = NIL;
1629  EquivalenceClass *lastoeclass;
1630  PathKey *opathkey;
1631  ListCell *lc;
1632  ListCell *lop;
1633 
1634  lastoeclass = NULL;
1635  opathkey = NULL;
1636  lop = list_head(outer_pathkeys);
1637 
1638  foreach(lc, mergeclauses)
1639  {
1640  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1641  EquivalenceClass *oeclass;
1642  EquivalenceClass *ieclass;
1643  PathKey *pathkey;
1644 
1645  update_mergeclause_eclasses(root, rinfo);
1646 
1647  if (rinfo->outer_is_left)
1648  {
1649  oeclass = rinfo->left_ec;
1650  ieclass = rinfo->right_ec;
1651  }
1652  else
1653  {
1654  oeclass = rinfo->right_ec;
1655  ieclass = rinfo->left_ec;
1656  }
1657 
1658  /* outer eclass should match current or next pathkeys */
1659  /* we check this carefully for debugging reasons */
1660  if (oeclass != lastoeclass)
1661  {
1662  if (!lop)
1663  elog(ERROR, "too few pathkeys for mergeclauses");
1664  opathkey = (PathKey *) lfirst(lop);
1665  lop = lnext(outer_pathkeys, lop);
1666  lastoeclass = opathkey->pk_eclass;
1667  if (oeclass != lastoeclass)
1668  elog(ERROR, "outer pathkeys do not match mergeclause");
1669  }
1670 
1671  /*
1672  * Often, we'll have same EC on both sides, in which case the outer
1673  * pathkey is also canonical for the inner side, and we can skip a
1674  * useless search.
1675  */
1676  if (ieclass == oeclass)
1677  pathkey = opathkey;
1678  else
1679  pathkey = make_canonical_pathkey(root,
1680  ieclass,
1681  opathkey->pk_opfamily,
1682  opathkey->pk_strategy,
1683  opathkey->pk_nulls_first);
1684 
1685  /*
1686  * Don't generate redundant pathkeys (which can happen if multiple
1687  * mergeclauses refer to the same EC). Because we do this, the output
1688  * pathkey list isn't necessarily ordered like the mergeclauses, which
1689  * complicates life for create_mergejoin_plan(). But if we didn't,
1690  * we'd have a noncanonical sort key list, which would be bad; for one
1691  * reason, it certainly wouldn't match any available sort order for
1692  * the input relation.
1693  */
1694  if (!pathkey_is_redundant(pathkey, pathkeys))
1695  pathkeys = lappend(pathkeys, pathkey);
1696  }
1697 
1698  return pathkeys;
1699 }
static ListCell * list_head(const List *l)
Definition: pg_list.h:128
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:343

References elog(), ERROR, lappend(), lfirst, list_head(), lnext(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, and update_mergeclause_eclasses().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

◆ make_pathkey_from_sortinfo()

static PathKey* make_pathkey_from_sortinfo ( PlannerInfo root,
Expr expr,
Oid  opfamily,
Oid  opcintype,
Oid  collation,
bool  reverse_sort,
bool  nulls_first,
Index  sortref,
Relids  rel,
bool  create_it 
)
static

Definition at line 196 of file pathkeys.c.

206 {
207  int16 strategy;
208  Oid equality_op;
209  List *opfamilies;
211 
212  strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
213 
214  /*
215  * EquivalenceClasses need to contain opfamily lists based on the family
216  * membership of mergejoinable equality operators, which could belong to
217  * more than one opfamily. So we have to look up the opfamily's equality
218  * operator and get its membership.
219  */
220  equality_op = get_opfamily_member(opfamily,
221  opcintype,
222  opcintype,
224  if (!OidIsValid(equality_op)) /* shouldn't happen */
225  elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
226  BTEqualStrategyNumber, opcintype, opcintype, opfamily);
227  opfamilies = get_mergejoin_opfamilies(equality_op);
228  if (!opfamilies) /* certainly should find some */
229  elog(ERROR, "could not find opfamilies for equality operator %u",
230  equality_op);
231 
232  /* Now find or (optionally) create a matching EquivalenceClass */
233  eclass = get_eclass_for_sort_expr(root, expr,
234  opfamilies, opcintype, collation,
235  sortref, rel, create_it);
236 
237  /* Fail if no EC and !create_it */
238  if (!eclass)
239  return NULL;
240 
241  /* And finally we can find or create a PathKey node */
242  return make_canonical_pathkey(root, eclass, opfamily,
243  strategy, nulls_first);
244 }
#define OidIsValid(objectId)
Definition: c.h:764
List * get_mergejoin_opfamilies(Oid opno)
Definition: lsyscache.c:365
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:165
#define BTLessStrategyNumber
Definition: stratnum.h:29
#define BTEqualStrategyNumber
Definition: stratnum.h:31

References BTEqualStrategyNumber, BTGreaterStrategyNumber, BTLessStrategyNumber, eclass(), elog(), ERROR, get_eclass_for_sort_expr(), get_mergejoin_opfamilies(), get_opfamily_member(), make_canonical_pathkey(), and OidIsValid.

Referenced by build_expression_pathkey(), build_index_pathkeys(), build_partition_pathkeys(), and make_pathkey_from_sortop().

◆ make_pathkey_from_sortop()

static PathKey* make_pathkey_from_sortop ( PlannerInfo root,
Expr expr,
Oid  ordering_op,
bool  nulls_first,
Index  sortref,
bool  create_it 
)
static

Definition at line 254 of file pathkeys.c.

260 {
261  Oid opfamily,
262  opcintype,
263  collation;
264  int16 strategy;
265 
266  /* Find the operator in pg_amop --- failure shouldn't happen */
267  if (!get_ordering_op_properties(ordering_op,
268  &opfamily, &opcintype, &strategy))
269  elog(ERROR, "operator %u is not a valid ordering operator",
270  ordering_op);
271 
272  /* Because SortGroupClause doesn't carry collation, consult the expr */
273  collation = exprCollation((Node *) expr);
274 
275  return make_pathkey_from_sortinfo(root,
276  expr,
277  opfamily,
278  opcintype,
279  collation,
280  (strategy == BTGreaterStrategyNumber),
281  nulls_first,
282  sortref,
283  NULL,
284  create_it);
285 }

References BTGreaterStrategyNumber, elog(), ERROR, exprCollation(), get_ordering_op_properties(), and make_pathkey_from_sortinfo().

Referenced by make_pathkeys_for_sortclauses_extended().

◆ make_pathkeys_for_sortclauses()

List* make_pathkeys_for_sortclauses ( PlannerInfo root,
List sortclauses,
List tlist 
)

Definition at line 1133 of file pathkeys.c.

1136 {
1137  List *result;
1138  bool sortable;
1139 
1141  &sortclauses,
1142  tlist,
1143  false,
1144  &sortable);
1145  /* It's caller error if not all clauses were sortable */
1146  Assert(sortable);
1147  return result;
1148 }
List * make_pathkeys_for_sortclauses_extended(PlannerInfo *root, List **sortclauses, List *tlist, bool remove_redundant, bool *sortable)
Definition: pathkeys.c:1170

References Assert(), and make_pathkeys_for_sortclauses_extended().

Referenced by adjust_group_pathkeys_for_groupagg(), generate_nonunion_paths(), grouping_planner(), make_pathkeys_for_window(), make_union_unique(), minmax_qp_callback(), and standard_qp_callback().

◆ make_pathkeys_for_sortclauses_extended()

List* make_pathkeys_for_sortclauses_extended ( PlannerInfo root,
List **  sortclauses,
List tlist,
bool  remove_redundant,
bool sortable 
)

Definition at line 1170 of file pathkeys.c.

1175 {
1176  List *pathkeys = NIL;
1177  ListCell *l;
1178 
1179  *sortable = true;
1180  foreach(l, *sortclauses)
1181  {
1182  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1183  Expr *sortkey;
1184  PathKey *pathkey;
1185 
1186  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1187  if (!OidIsValid(sortcl->sortop))
1188  {
1189  *sortable = false;
1190  continue;
1191  }
1192  pathkey = make_pathkey_from_sortop(root,
1193  sortkey,
1194  sortcl->sortop,
1195  sortcl->nulls_first,
1196  sortcl->tleSortGroupRef,
1197  true);
1198 
1199  /* Canonical form eliminates redundant ordering keys */
1200  if (!pathkey_is_redundant(pathkey, pathkeys))
1201  pathkeys = lappend(pathkeys, pathkey);
1202  else if (remove_redundant)
1203  *sortclauses = foreach_delete_current(*sortclauses, l);
1204  }
1205  return pathkeys;
1206 }
static PathKey * make_pathkey_from_sortop(PlannerInfo *root, Expr *expr, Oid ordering_op, bool nulls_first, Index sortref, bool create_it)
Definition: pathkeys.c:254
#define foreach_delete_current(lst, cell)
Definition: pg_list.h:390
Index tleSortGroupRef
Definition: parsenodes.h:1392
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:379

References foreach_delete_current, get_sortgroupclause_expr(), lappend(), lfirst, make_pathkey_from_sortop(), NIL, SortGroupClause::nulls_first, OidIsValid, pathkey_is_redundant(), SortGroupClause::sortop, and SortGroupClause::tleSortGroupRef.

Referenced by make_pathkeys_for_sortclauses(), make_pathkeys_for_window(), and standard_qp_callback().

◆ matches_boolean_partition_clause()

static bool matches_boolean_partition_clause ( RestrictInfo rinfo,
RelOptInfo partrel,
int  partkeycol 
)
static

Definition at line 685 of file pathkeys.c.

687 {
688  Node *clause = (Node *) rinfo->clause;
689  Node *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
690 
691  /* Direct match? */
692  if (equal(partexpr, clause))
693  return true;
694  /* NOT clause? */
695  else if (is_notclause(clause))
696  {
697  Node *arg = (Node *) get_notclausearg((Expr *) clause);
698 
699  if (equal(partexpr, arg))
700  return true;
701  }
702 
703  return false;
704 }
static Expr * get_notclausearg(const void *notclause)
Definition: nodeFuncs.h:132
static bool is_notclause(const void *clause)
Definition: nodeFuncs.h:123
void * arg

References arg, RestrictInfo::clause, equal(), get_notclausearg(), is_notclause(), and linitial.

Referenced by partkey_is_bool_constant_for_query().

◆ partkey_is_bool_constant_for_query()

static bool partkey_is_bool_constant_for_query ( RelOptInfo partrel,
int  partkeycol 
)
static

Definition at line 645 of file pathkeys.c.

646 {
647  PartitionScheme partscheme = partrel->part_scheme;
648  ListCell *lc;
649 
650  /*
651  * If the partkey isn't boolean, we can't possibly get a match.
652  *
653  * Partitioning currently can only use built-in AMs, so checking for
654  * built-in boolean opfamilies is good enough.
655  */
656  if (!IsBuiltinBooleanOpfamily(partscheme->partopfamily[partkeycol]))
657  return false;
658 
659  /* Check each restriction clause for the partitioned rel */
660  foreach(lc, partrel->baserestrictinfo)
661  {
662  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
663 
664  /* Ignore pseudoconstant quals, they won't match */
665  if (rinfo->pseudoconstant)
666  continue;
667 
668  /* See if we can match the clause's expression to the partkey column */
669  if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
670  return true;
671  }
672 
673  return false;
674 }
static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:685
List * baserestrictinfo
Definition: pathnodes.h:964

References RelOptInfo::baserestrictinfo, lfirst, matches_boolean_partition_clause(), and PartitionSchemeData::partopfamily.

Referenced by build_partition_pathkeys().

◆ pathkey_is_redundant()

static bool pathkey_is_redundant ( PathKey new_pathkey,
List pathkeys 
)
static

Definition at line 157 of file pathkeys.c.

158 {
159  EquivalenceClass *new_ec = new_pathkey->pk_eclass;
160  ListCell *lc;
161 
162  /* Check for EC containing a constant --- unconditionally redundant */
163  if (EC_MUST_BE_REDUNDANT(new_ec))
164  return true;
165 
166  /* If same EC already used in list, then redundant */
167  foreach(lc, pathkeys)
168  {
169  PathKey *old_pathkey = (PathKey *) lfirst(lc);
170 
171  if (new_ec == old_pathkey->pk_eclass)
172  return true;
173  }
174 
175  return false;
176 }
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: pathnodes.h:1388

References EC_MUST_BE_REDUNDANT, and lfirst.

Referenced by append_pathkeys(), build_index_pathkeys(), build_partition_pathkeys(), convert_subquery_pathkeys(), make_inner_pathkeys_for_merge(), make_pathkeys_for_sortclauses_extended(), and select_outer_pathkeys_for_merge().

◆ pathkeys_contained_in()

◆ pathkeys_count_contained_in()

bool pathkeys_count_contained_in ( List keys1,
List keys2,
int *  n_common 
)

Definition at line 359 of file pathkeys.c.

360 {
361  int n = 0;
362  ListCell *key1,
363  *key2;
364 
365  /*
366  * See if we can avoiding looping through both lists. This optimization
367  * gains us several percent in planning time in a worst-case test.
368  */
369  if (keys1 == keys2)
370  {
371  *n_common = list_length(keys1);
372  return true;
373  }
374  else if (keys1 == NIL)
375  {
376  *n_common = 0;
377  return true;
378  }
379  else if (keys2 == NIL)
380  {
381  *n_common = 0;
382  return false;
383  }
384 
385  /*
386  * If both lists are non-empty, iterate through both to find out how many
387  * items are shared.
388  */
389  forboth(key1, keys1, key2, keys2)
390  {
391  PathKey *pathkey1 = (PathKey *) lfirst(key1);
392  PathKey *pathkey2 = (PathKey *) lfirst(key2);
393 
394  if (pathkey1 != pathkey2)
395  {
396  *n_common = n;
397  return false;
398  }
399  n++;
400  }
401 
402  /* If we ended with a null value, then we've processed the whole list. */
403  *n_common = n;
404  return (key1 == NULL);
405 }

References forboth, lfirst, list_length(), and NIL.

Referenced by add_paths_to_grouping_rel(), create_final_distinct_paths(), create_one_window_path(), create_ordered_paths(), create_partial_distinct_paths(), create_partial_grouping_paths(), create_window_paths(), gather_grouping_paths(), generate_useful_gather_paths(), and pathkeys_useful_for_ordering().

◆ pathkeys_useful_for_merging()

static int pathkeys_useful_for_merging ( PlannerInfo root,
RelOptInfo rel,
List pathkeys 
)
static

Definition at line 1822 of file pathkeys.c.

1823 {
1824  int useful = 0;
1825  ListCell *i;
1826 
1827  foreach(i, pathkeys)
1828  {
1829  PathKey *pathkey = (PathKey *) lfirst(i);
1830  bool matched = false;
1831  ListCell *j;
1832 
1833  /* If "wrong" direction, not useful for merging */
1834  if (!right_merge_direction(root, pathkey))
1835  break;
1836 
1837  /*
1838  * First look into the EquivalenceClass of the pathkey, to see if
1839  * there are any members not yet joined to the rel. If so, it's
1840  * surely possible to generate a mergejoin clause using them.
1841  */
1842  if (rel->has_eclass_joins &&
1843  eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
1844  matched = true;
1845  else
1846  {
1847  /*
1848  * Otherwise search the rel's joininfo list, which contains
1849  * non-EquivalenceClass-derivable join clauses that might
1850  * nonetheless be mergejoinable.
1851  */
1852  foreach(j, rel->joininfo)
1853  {
1854  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
1855 
1856  if (restrictinfo->mergeopfamilies == NIL)
1857  continue;
1858  update_mergeclause_eclasses(root, restrictinfo);
1859 
1860  if (pathkey->pk_eclass == restrictinfo->left_ec ||
1861  pathkey->pk_eclass == restrictinfo->right_ec)
1862  {
1863  matched = true;
1864  break;
1865  }
1866  }
1867  }
1868 
1869  /*
1870  * If we didn't find a mergeclause, we're done --- any additional
1871  * sort-key positions in the pathkeys are useless. (But we can still
1872  * mergejoin if we found at least one mergeclause.)
1873  */
1874  if (matched)
1875  useful++;
1876  else
1877  break;
1878  }
1879 
1880  return useful;
1881 }
bool eclass_useful_for_merging(PlannerInfo *root, EquivalenceClass *eclass, RelOptInfo *rel)
Definition: equivclass.c:3136
static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey)
Definition: pathkeys.c:1889

References eclass_useful_for_merging(), RelOptInfo::has_eclass_joins, i, j, RelOptInfo::joininfo, lfirst, NIL, right_merge_direction(), and update_mergeclause_eclasses().

Referenced by truncate_useless_pathkeys().

◆ pathkeys_useful_for_ordering()

static int pathkeys_useful_for_ordering ( PlannerInfo root,
List pathkeys 
)
static

Definition at line 1926 of file pathkeys.c.

1927 {
1928  int n_common_pathkeys;
1929 
1930  if (root->query_pathkeys == NIL)
1931  return 0; /* no special ordering requested */
1932 
1933  if (pathkeys == NIL)
1934  return 0; /* unordered path */
1935 
1936  (void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys,
1937  &n_common_pathkeys);
1938 
1939  return n_common_pathkeys;
1940 }
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:359

References NIL, pathkeys_count_contained_in(), and PlannerInfo::query_pathkeys.

Referenced by truncate_useless_pathkeys().

◆ right_merge_direction()

static bool right_merge_direction ( PlannerInfo root,
PathKey pathkey 
)
static

Definition at line 1889 of file pathkeys.c.

1890 {
1891  ListCell *l;
1892 
1893  foreach(l, root->query_pathkeys)
1894  {
1895  PathKey *query_pathkey = (PathKey *) lfirst(l);
1896 
1897  if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
1898  pathkey->pk_opfamily == query_pathkey->pk_opfamily)
1899  {
1900  /*
1901  * Found a matching query sort column. Prefer this pathkey's
1902  * direction iff it matches. Note that we ignore pk_nulls_first,
1903  * which means that a sort might be needed anyway ... but we still
1904  * want to prefer only one of the two possible directions, and we
1905  * might as well use this one.
1906  */
1907  return (pathkey->pk_strategy == query_pathkey->pk_strategy);
1908  }
1909  }
1910 
1911  /* If no matching ORDER BY request, prefer the ASC direction */
1912  return (pathkey->pk_strategy == BTLessStrategyNumber);
1913 }

References BTLessStrategyNumber, lfirst, PathKey::pk_opfamily, PathKey::pk_strategy, and PlannerInfo::query_pathkeys.

Referenced by pathkeys_useful_for_merging().

◆ select_outer_pathkeys_for_merge()

List* select_outer_pathkeys_for_merge ( PlannerInfo root,
List mergeclauses,
RelOptInfo joinrel 
)

Definition at line 1428 of file pathkeys.c.

1431 {
1432  List *pathkeys = NIL;
1433  int nClauses = list_length(mergeclauses);
1434  EquivalenceClass **ecs;
1435  int *scores;
1436  int necs;
1437  ListCell *lc;
1438  int j;
1439 
1440  /* Might have no mergeclauses */
1441  if (nClauses == 0)
1442  return NIL;
1443 
1444  /*
1445  * Make arrays of the ECs used by the mergeclauses (dropping any
1446  * duplicates) and their "popularity" scores.
1447  */
1448  ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
1449  scores = (int *) palloc(nClauses * sizeof(int));
1450  necs = 0;
1451 
1452  foreach(lc, mergeclauses)
1453  {
1454  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1455  EquivalenceClass *oeclass;
1456  int score;
1457  ListCell *lc2;
1458 
1459  /* get the outer eclass */
1460  update_mergeclause_eclasses(root, rinfo);
1461 
1462  if (rinfo->outer_is_left)
1463  oeclass = rinfo->left_ec;
1464  else
1465  oeclass = rinfo->right_ec;
1466 
1467  /* reject duplicates */
1468  for (j = 0; j < necs; j++)
1469  {
1470  if (ecs[j] == oeclass)
1471  break;
1472  }
1473  if (j < necs)
1474  continue;
1475 
1476  /* compute score */
1477  score = 0;
1478  foreach(lc2, oeclass->ec_members)
1479  {
1481 
1482  /* Potential future join partner? */
1483  if (!em->em_is_const && !em->em_is_child &&
1484  !bms_overlap(em->em_relids, joinrel->relids))
1485  score++;
1486  }
1487 
1488  ecs[necs] = oeclass;
1489  scores[necs] = score;
1490  necs++;
1491  }
1492 
1493  /*
1494  * Find out if we have all the ECs mentioned in query_pathkeys; if so we
1495  * can generate a sort order that's also useful for final output. If we
1496  * only have a prefix of the query_pathkeys, and that prefix is the entire
1497  * join condition, then it's useful to use the prefix as the pathkeys as
1498  * this increases the chances that an incremental sort will be able to be
1499  * used by the upper planner.
1500  */
1501  if (root->query_pathkeys)
1502  {
1503  int matches = 0;
1504 
1505  foreach(lc, root->query_pathkeys)
1506  {
1507  PathKey *query_pathkey = (PathKey *) lfirst(lc);
1508  EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1509 
1510  for (j = 0; j < necs; j++)
1511  {
1512  if (ecs[j] == query_ec)
1513  break; /* found match */
1514  }
1515  if (j >= necs)
1516  break; /* didn't find match */
1517 
1518  matches++;
1519  }
1520  /* if we got to the end of the list, we have them all */
1521  if (lc == NULL)
1522  {
1523  /* copy query_pathkeys as starting point for our output */
1524  pathkeys = list_copy(root->query_pathkeys);
1525  /* mark their ECs as already-emitted */
1526  foreach(lc, root->query_pathkeys)
1527  {
1528  PathKey *query_pathkey = (PathKey *) lfirst(lc);
1529  EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1530 
1531  for (j = 0; j < necs; j++)
1532  {
1533  if (ecs[j] == query_ec)
1534  {
1535  scores[j] = -1;
1536  break;
1537  }
1538  }
1539  }
1540  }
1541 
1542  /*
1543  * If we didn't match to all of the query_pathkeys, but did match to
1544  * all of the join clauses then we'll make use of these as partially
1545  * sorted input is better than nothing for the upper planner as it may
1546  * lead to incremental sorts instead of full sorts.
1547  */
1548  else if (matches == nClauses)
1549  {
1550  pathkeys = list_copy_head(root->query_pathkeys, matches);
1551 
1552  /* we have all of the join pathkeys, so nothing more to do */
1553  pfree(ecs);
1554  pfree(scores);
1555 
1556  return pathkeys;
1557  }
1558  }
1559 
1560  /*
1561  * Add remaining ECs to the list in popularity order, using a default sort
1562  * ordering. (We could use qsort() here, but the list length is usually
1563  * so small it's not worth it.)
1564  */
1565  for (;;)
1566  {
1567  int best_j;
1568  int best_score;
1569  EquivalenceClass *ec;
1570  PathKey *pathkey;
1571 
1572  best_j = 0;
1573  best_score = scores[0];
1574  for (j = 1; j < necs; j++)
1575  {
1576  if (scores[j] > best_score)
1577  {
1578  best_j = j;
1579  best_score = scores[j];
1580  }
1581  }
1582  if (best_score < 0)
1583  break; /* all done */
1584  ec = ecs[best_j];
1585  scores[best_j] = -1;
1586  pathkey = make_canonical_pathkey(root,
1587  ec,
1590  false);
1591  /* can't be redundant because no duplicate ECs */
1592  Assert(!pathkey_is_redundant(pathkey, pathkeys));
1593  pathkeys = lappend(pathkeys, pathkey);
1594  }
1595 
1596  pfree(ecs);
1597  pfree(scores);
1598 
1599  return pathkeys;
1600 }
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:527
List * list_copy_head(const List *oldlist, int len)
Definition: list.c:1592
List * list_copy(const List *oldlist)
Definition: list.c:1572
void pfree(void *pointer)
Definition: mcxt.c:1456
void * palloc(Size size)
Definition: mcxt.c:1226
#define linitial_oid(l)
Definition: pg_list.h:180

References Assert(), bms_overlap(), BTLessStrategyNumber, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, j, lappend(), lfirst, linitial_oid, list_copy(), list_copy_head(), list_length(), make_canonical_pathkey(), NIL, palloc(), pathkey_is_redundant(), pfree(), PlannerInfo::query_pathkeys, RelOptInfo::relids, and update_mergeclause_eclasses().

Referenced by sort_inner_and_outer().

◆ trim_mergeclauses_for_inner_pathkeys()

List* trim_mergeclauses_for_inner_pathkeys ( PlannerInfo root,
List mergeclauses,
List pathkeys 
)

Definition at line 1727 of file pathkeys.c.

1730 {
1731  List *new_mergeclauses = NIL;
1732  PathKey *pathkey;
1733  EquivalenceClass *pathkey_ec;
1734  bool matched_pathkey;
1735  ListCell *lip;
1736  ListCell *i;
1737 
1738  /* No pathkeys => no mergeclauses (though we don't expect this case) */
1739  if (pathkeys == NIL)
1740  return NIL;
1741  /* Initialize to consider first pathkey */
1742  lip = list_head(pathkeys);
1743  pathkey = (PathKey *) lfirst(lip);
1744  pathkey_ec = pathkey->pk_eclass;
1745  lip = lnext(pathkeys, lip);
1746  matched_pathkey = false;
1747 
1748  /* Scan mergeclauses to see how many we can use */
1749  foreach(i, mergeclauses)
1750  {
1751  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1752  EquivalenceClass *clause_ec;
1753 
1754  /* Assume we needn't do update_mergeclause_eclasses again here */
1755 
1756  /* Check clause's inner-rel EC against current pathkey */
1757  clause_ec = rinfo->outer_is_left ?
1758  rinfo->right_ec : rinfo->left_ec;
1759 
1760  /* If we don't have a match, attempt to advance to next pathkey */
1761  if (clause_ec != pathkey_ec)
1762  {
1763  /* If we had no clauses matching this inner pathkey, must stop */
1764  if (!matched_pathkey)
1765  break;
1766 
1767  /* Advance to next inner pathkey, if any */
1768  if (lip == NULL)
1769  break;
1770  pathkey = (PathKey *) lfirst(lip);
1771  pathkey_ec = pathkey->pk_eclass;
1772  lip = lnext(pathkeys, lip);
1773  matched_pathkey = false;
1774  }
1775 
1776  /* If mergeclause matches current inner pathkey, we can use it */
1777  if (clause_ec == pathkey_ec)
1778  {
1779  new_mergeclauses = lappend(new_mergeclauses, rinfo);
1780  matched_pathkey = true;
1781  }
1782  else
1783  {
1784  /* Else, no hope of adding any more mergeclauses */
1785  break;
1786  }
1787  }
1788 
1789  return new_mergeclauses;
1790 }

References i, lappend(), lfirst, list_head(), lnext(), and NIL.

Referenced by generate_mergejoin_paths().

◆ truncate_useless_pathkeys()

List* truncate_useless_pathkeys ( PlannerInfo root,
RelOptInfo rel,
List pathkeys 
)

Definition at line 1947 of file pathkeys.c.

1950 {
1951  int nuseful;
1952  int nuseful2;
1953 
1954  nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
1955  nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
1956  if (nuseful2 > nuseful)
1957  nuseful = nuseful2;
1958 
1959  /*
1960  * Note: not safe to modify input list destructively, but we can avoid
1961  * copying the list if we're not actually going to change it
1962  */
1963  if (nuseful == 0)
1964  return NIL;
1965  else if (nuseful == list_length(pathkeys))
1966  return pathkeys;
1967  else
1968  return list_copy_head(pathkeys, nuseful);
1969 }
static int pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:1926
static int pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:1822

References list_copy_head(), list_length(), NIL, pathkeys_useful_for_merging(), and pathkeys_useful_for_ordering().

Referenced by build_index_paths(), and build_join_pathkeys().

◆ update_mergeclause_eclasses()

void update_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1279 of file pathkeys.c.

1280 {
1281  /* Should be a merge clause ... */
1282  Assert(restrictinfo->mergeopfamilies != NIL);
1283  /* ... with pointers already set */
1284  Assert(restrictinfo->left_ec != NULL);
1285  Assert(restrictinfo->right_ec != NULL);
1286 
1287  /* Chase up to the top as needed */
1288  while (restrictinfo->left_ec->ec_merged)
1289  restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
1290  while (restrictinfo->right_ec->ec_merged)
1291  restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
1292 }

References Assert(), and NIL.

Referenced by find_mergeclauses_for_outer_pathkeys(), get_useful_ecs_for_relation(), make_inner_pathkeys_for_merge(), pathkeys_useful_for_merging(), select_mergejoin_clauses(), and select_outer_pathkeys_for_merge().