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)
 
static int group_keys_reorder_by_pathkeys (List *pathkeys, List **group_pathkeys, List **group_clauses, int num_groupby_pathkeys)
 
static bool pathkeys_are_duplicate (List *infos, List *pathkeys)
 
Listget_useful_group_keys_orderings (PlannerInfo *root, Path *path)
 
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)
 
static int pathkeys_useful_for_grouping (PlannerInfo *root, List *pathkeys)
 
static int pathkeys_useful_for_setop (PlannerInfo *root, List *pathkeys)
 
Listtruncate_useless_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 
bool has_useful_pathkeys (PlannerInfo *root, RelOptInfo *rel)
 

Variables

bool enable_group_by_reordering = true
 

Function Documentation

◆ append_pathkeys()

List* append_pathkeys ( List target,
List source 
)

Definition at line 106 of file pathkeys.c.

107 {
108  ListCell *lc;
109 
110  Assert(target != NIL);
111 
112  foreach(lc, source)
113  {
114  PathKey *pk = lfirst_node(PathKey, lc);
115 
116  if (!pathkey_is_redundant(pk, target))
117  target = lappend(target, pk);
118  }
119  return target;
120 }
#define Assert(condition)
Definition: c.h:858
List * lappend(List *list, void *datum)
Definition: list.c:339
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:158
#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 1015 of file pathkeys.c.

1020 {
1021  List *pathkeys;
1022  Oid opfamily,
1023  opcintype;
1024  int16 strategy;
1025  PathKey *cpathkey;
1026 
1027  /* Find the operator in pg_amop --- failure shouldn't happen */
1028  if (!get_ordering_op_properties(opno,
1029  &opfamily, &opcintype, &strategy))
1030  elog(ERROR, "operator %u is not a valid ordering operator",
1031  opno);
1032 
1033  cpathkey = make_pathkey_from_sortinfo(root,
1034  expr,
1035  opfamily,
1036  opcintype,
1037  exprCollation((Node *) expr),
1038  (strategy == BTGreaterStrategyNumber),
1039  (strategy == BTGreaterStrategyNumber),
1040  0,
1041  rel,
1042  create_it);
1043 
1044  if (cpathkey)
1045  pathkeys = list_make1(cpathkey);
1046  else
1047  pathkeys = NIL;
1048 
1049  return pathkeys;
1050 }
signed short int16
Definition: c.h:493
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, int16 *strategy)
Definition: lsyscache.c:207
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:816
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:197
#define list_make1(x1)
Definition: pg_list.h:212
unsigned int Oid
Definition: postgres_ext.h:31
tree ctl root
Definition: radixtree.h:1880
#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(), NIL, and root.

Referenced by set_function_pathlist().

◆ build_index_pathkeys()

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

Definition at line 755 of file pathkeys.c.

758 {
759  List *retval = NIL;
760  ListCell *lc;
761  int i;
762 
763  if (index->sortopfamily == NULL)
764  return NIL; /* non-orderable index */
765 
766  i = 0;
767  foreach(lc, index->indextlist)
768  {
769  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
770  Expr *indexkey;
771  bool reverse_sort;
772  bool nulls_first;
773  PathKey *cpathkey;
774 
775  /*
776  * INCLUDE columns are stored in index unordered, so they don't
777  * support ordered index scan.
778  */
779  if (i >= index->nkeycolumns)
780  break;
781 
782  /* We assume we don't need to make a copy of the tlist item */
783  indexkey = indextle->expr;
784 
785  if (ScanDirectionIsBackward(scandir))
786  {
787  reverse_sort = !index->reverse_sort[i];
788  nulls_first = !index->nulls_first[i];
789  }
790  else
791  {
792  reverse_sort = index->reverse_sort[i];
793  nulls_first = index->nulls_first[i];
794  }
795 
796  /*
797  * OK, try to make a canonical pathkey for this sort key.
798  */
799  cpathkey = make_pathkey_from_sortinfo(root,
800  indexkey,
801  index->sortopfamily[i],
802  index->opcintype[i],
803  index->indexcollations[i],
804  reverse_sort,
805  nulls_first,
806  0,
807  index->rel->relids,
808  false);
809 
810  if (cpathkey)
811  {
812  /*
813  * We found the sort key in an EquivalenceClass, so it's relevant
814  * for this query. Add it to list, unless it's redundant.
815  */
816  if (!pathkey_is_redundant(cpathkey, retval))
817  retval = lappend(retval, cpathkey);
818  }
819  else
820  {
821  /*
822  * Boolean index keys might be redundant even if they do not
823  * appear in an EquivalenceClass, because of our special treatment
824  * of boolean equality conditions --- see the comment for
825  * indexcol_is_bool_constant_for_query(). If that applies, we can
826  * continue to examine lower-order index columns. Otherwise, the
827  * sort key is not an interesting sort order for this query, so we
828  * should stop considering index columns; any lower-order sort
829  * keys won't be useful either.
830  */
832  break;
833  }
834 
835  i++;
836  }
837 
838  return retval;
839 }
bool indexcol_is_bool_constant_for_query(PlannerInfo *root, IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3653
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:2157
Definition: type.h:95

References TargetEntry::expr, i, indexcol_is_bool_constant_for_query(), lappend(), lfirst, make_pathkey_from_sortinfo(), NIL, pathkey_is_redundant(), root, 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 1309 of file pathkeys.c.

1313 {
1314  if (jointype == JOIN_FULL ||
1315  jointype == JOIN_RIGHT ||
1316  jointype == JOIN_RIGHT_ANTI)
1317  return NIL;
1318 
1319  /*
1320  * This used to be quite a complex bit of code, but now that all pathkey
1321  * sublists start out life canonicalized, we don't have to do a darn thing
1322  * here!
1323  *
1324  * We do, however, need to truncate the pathkeys list, since it may
1325  * contain pathkeys that were useful for forming this joinrel but are
1326  * uninteresting to higher levels.
1327  */
1328  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1329 }
@ JOIN_FULL
Definition: nodes.h:295
@ JOIN_RIGHT
Definition: nodes.h:296
@ JOIN_RIGHT_ANTI
Definition: nodes.h:309
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2215

References JOIN_FULL, JOIN_RIGHT, JOIN_RIGHT_ANTI, NIL, root, 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 934 of file pathkeys.c.

936 {
937  List *retval = NIL;
938  PartitionScheme partscheme = partrel->part_scheme;
939  int i;
940 
941  Assert(partscheme != NULL);
942  Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
943  /* For now, we can only cope with baserels */
944  Assert(IS_SIMPLE_REL(partrel));
945 
946  for (i = 0; i < partscheme->partnatts; i++)
947  {
948  PathKey *cpathkey;
949  Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
950 
951  /*
952  * Try to make a canonical pathkey for this partkey.
953  *
954  * We assume the PartitionDesc lists any NULL partition last, so we
955  * treat the scan like a NULLS LAST index: we have nulls_first for
956  * backwards scan only.
957  */
958  cpathkey = make_pathkey_from_sortinfo(root,
959  keyCol,
960  partscheme->partopfamily[i],
961  partscheme->partopcintype[i],
962  partscheme->partcollation[i],
963  ScanDirectionIsBackward(scandir),
964  ScanDirectionIsBackward(scandir),
965  0,
966  partrel->relids,
967  false);
968 
969 
970  if (cpathkey)
971  {
972  /*
973  * We found the sort key in an EquivalenceClass, so it's relevant
974  * for this query. Add it to list, unless it's redundant.
975  */
976  if (!pathkey_is_redundant(cpathkey, retval))
977  retval = lappend(retval, cpathkey);
978  }
979  else
980  {
981  /*
982  * Boolean partition keys might be redundant even if they do not
983  * appear in an EquivalenceClass, because of our special treatment
984  * of boolean equality conditions --- see the comment for
985  * partkey_is_bool_constant_for_query(). If that applies, we can
986  * continue to examine lower-order partition keys. Otherwise, the
987  * sort key is not an interesting sort order for this query, so we
988  * should stop considering partition columns; any lower-order sort
989  * keys won't be useful either.
990  */
991  if (!partkey_is_bool_constant_for_query(partrel, i))
992  {
993  *partialkeys = true;
994  return retval;
995  }
996  }
997  }
998 
999  *partialkeys = false;
1000  return retval;
1001 }
bool partitions_are_ordered(PartitionBoundInfo boundinfo, Bitmapset *live_parts)
Definition: partbounds.c:2852
static bool partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:859
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:829
#define linitial(l)
Definition: pg_list.h:178
Relids relids
Definition: pathnodes.h:861
Bitmapset * live_parts
Definition: pathnodes.h:1029

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, root, and ScanDirectionIsBackward.

Referenced by generate_orderedappend_paths().

◆ compare_pathkeys()

PathKeysComparison compare_pathkeys ( List keys1,
List keys2 
)

Definition at line 302 of file pathkeys.c.

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

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_are_duplicate(), 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 1069 of file pathkeys.c.

1072 {
1073  List *retval = NIL;
1074  int retvallen = 0;
1075  int outer_query_keys = list_length(root->query_pathkeys);
1076  ListCell *i;
1077 
1078  foreach(i, subquery_pathkeys)
1079  {
1080  PathKey *sub_pathkey = (PathKey *) lfirst(i);
1081  EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
1082  PathKey *best_pathkey = NULL;
1083 
1084  if (sub_eclass->ec_has_volatile)
1085  {
1086  /*
1087  * If the sub_pathkey's EquivalenceClass is volatile, then it must
1088  * have come from an ORDER BY clause, and we have to match it to
1089  * that same targetlist entry.
1090  */
1091  TargetEntry *tle;
1092  Var *outer_var;
1093 
1094  if (sub_eclass->ec_sortref == 0) /* can't happen */
1095  elog(ERROR, "volatile EquivalenceClass has no sortref");
1096  tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
1097  Assert(tle);
1098  /* Is TLE actually available to the outer query? */
1099  outer_var = find_var_for_subquery_tle(rel, tle);
1100  if (outer_var)
1101  {
1102  /* We can represent this sub_pathkey */
1103  EquivalenceMember *sub_member;
1104  EquivalenceClass *outer_ec;
1105 
1106  Assert(list_length(sub_eclass->ec_members) == 1);
1107  sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
1108 
1109  /*
1110  * Note: it might look funny to be setting sortref = 0 for a
1111  * reference to a volatile sub_eclass. However, the
1112  * expression is *not* volatile in the outer query: it's just
1113  * a Var referencing whatever the subquery emitted. (IOW, the
1114  * outer query isn't going to re-execute the volatile
1115  * expression itself.) So this is okay.
1116  */
1117  outer_ec =
1119  (Expr *) outer_var,
1120  sub_eclass->ec_opfamilies,
1121  sub_member->em_datatype,
1122  sub_eclass->ec_collation,
1123  0,
1124  rel->relids,
1125  false);
1126 
1127  /*
1128  * If we don't find a matching EC, sub-pathkey isn't
1129  * interesting to the outer query
1130  */
1131  if (outer_ec)
1132  best_pathkey =
1134  outer_ec,
1135  sub_pathkey->pk_opfamily,
1136  sub_pathkey->pk_strategy,
1137  sub_pathkey->pk_nulls_first);
1138  }
1139  }
1140  else
1141  {
1142  /*
1143  * Otherwise, the sub_pathkey's EquivalenceClass could contain
1144  * multiple elements (representing knowledge that multiple items
1145  * are effectively equal). Each element might match none, one, or
1146  * more of the output columns that are visible to the outer query.
1147  * This means we may have multiple possible representations of the
1148  * sub_pathkey in the context of the outer query. Ideally we
1149  * would generate them all and put them all into an EC of the
1150  * outer query, thereby propagating equality knowledge up to the
1151  * outer query. Right now we cannot do so, because the outer
1152  * query's EquivalenceClasses are already frozen when this is
1153  * called. Instead we prefer the one that has the highest "score"
1154  * (number of EC peers, plus one if it matches the outer
1155  * query_pathkeys). This is the most likely to be useful in the
1156  * outer query.
1157  */
1158  int best_score = -1;
1159  ListCell *j;
1160 
1161  foreach(j, sub_eclass->ec_members)
1162  {
1163  EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
1164  Expr *sub_expr = sub_member->em_expr;
1165  Oid sub_expr_type = sub_member->em_datatype;
1166  Oid sub_expr_coll = sub_eclass->ec_collation;
1167  ListCell *k;
1168 
1169  if (sub_member->em_is_child)
1170  continue; /* ignore children here */
1171 
1172  foreach(k, subquery_tlist)
1173  {
1174  TargetEntry *tle = (TargetEntry *) lfirst(k);
1175  Var *outer_var;
1176  Expr *tle_expr;
1177  EquivalenceClass *outer_ec;
1178  PathKey *outer_pk;
1179  int score;
1180 
1181  /* Is TLE actually available to the outer query? */
1182  outer_var = find_var_for_subquery_tle(rel, tle);
1183  if (!outer_var)
1184  continue;
1185 
1186  /*
1187  * The targetlist entry is considered to match if it
1188  * matches after sort-key canonicalization. That is
1189  * needed since the sub_expr has been through the same
1190  * process.
1191  */
1192  tle_expr = canonicalize_ec_expression(tle->expr,
1193  sub_expr_type,
1194  sub_expr_coll);
1195  if (!equal(tle_expr, sub_expr))
1196  continue;
1197 
1198  /* See if we have a matching EC for the TLE */
1199  outer_ec = get_eclass_for_sort_expr(root,
1200  (Expr *) outer_var,
1201  sub_eclass->ec_opfamilies,
1202  sub_expr_type,
1203  sub_expr_coll,
1204  0,
1205  rel->relids,
1206  false);
1207 
1208  /*
1209  * If we don't find a matching EC, this sub-pathkey isn't
1210  * interesting to the outer query
1211  */
1212  if (!outer_ec)
1213  continue;
1214 
1215  outer_pk = make_canonical_pathkey(root,
1216  outer_ec,
1217  sub_pathkey->pk_opfamily,
1218  sub_pathkey->pk_strategy,
1219  sub_pathkey->pk_nulls_first);
1220  /* score = # of equivalence peers */
1221  score = list_length(outer_ec->ec_members) - 1;
1222  /* +1 if it matches the proper query_pathkeys item */
1223  if (retvallen < outer_query_keys &&
1224  list_nth(root->query_pathkeys, retvallen) == outer_pk)
1225  score++;
1226  if (score > best_score)
1227  {
1228  best_pathkey = outer_pk;
1229  best_score = score;
1230  }
1231  }
1232  }
1233  }
1234 
1235  /*
1236  * If we couldn't find a representation of this sub_pathkey, we're
1237  * done (we can't use the ones to its right, either).
1238  */
1239  if (!best_pathkey)
1240  break;
1241 
1242  /*
1243  * Eliminate redundant ordering info; could happen if outer query
1244  * equivalences subquery keys...
1245  */
1246  if (!pathkey_is_redundant(best_pathkey, retval))
1247  {
1248  retval = lappend(retval, best_pathkey);
1249  retvallen++;
1250  }
1251  }
1252 
1253  return retval;
1254 }
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:1266
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:55
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:1379
bool pk_nulls_first
Definition: pathnodes.h:1467
int pk_strategy
Definition: pathnodes.h:1466
Oid pk_opfamily
Definition: pathnodes.h:1465
Definition: primnodes.h:248
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, RelOptInfo::relids, and root.

Referenced by build_setop_child_paths(), set_cte_pathlist(), and set_subquery_pathlist().

◆ find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1527 of file pathkeys.c.

1530 {
1531  List *mergeclauses = NIL;
1532  ListCell *i;
1533 
1534  /* make sure we have eclasses cached in the clauses */
1535  foreach(i, restrictinfos)
1536  {
1537  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1538 
1540  }
1541 
1542  foreach(i, pathkeys)
1543  {
1544  PathKey *pathkey = (PathKey *) lfirst(i);
1545  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1546  List *matched_restrictinfos = NIL;
1547  ListCell *j;
1548 
1549  /*----------
1550  * A mergejoin clause matches a pathkey if it has the same EC.
1551  * If there are multiple matching clauses, take them all. In plain
1552  * inner-join scenarios we expect only one match, because
1553  * equivalence-class processing will have removed any redundant
1554  * mergeclauses. However, in outer-join scenarios there might be
1555  * multiple matches. An example is
1556  *
1557  * select * from a full join b
1558  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1559  *
1560  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1561  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1562  * we *must* do so or we will be unable to form a valid plan.
1563  *
1564  * We expect that the given pathkeys list is canonical, which means
1565  * no two members have the same EC, so it's not possible for this
1566  * code to enter the same mergeclause into the result list twice.
1567  *
1568  * It's possible that multiple matching clauses might have different
1569  * ECs on the other side, in which case the order we put them into our
1570  * result makes a difference in the pathkeys required for the inner
1571  * input rel. However this routine hasn't got any info about which
1572  * order would be best, so we don't worry about that.
1573  *
1574  * It's also possible that the selected mergejoin clauses produce
1575  * a noncanonical ordering of pathkeys for the inner side, ie, we
1576  * might select clauses that reference b.v1, b.v2, b.v1 in that
1577  * order. This is not harmful in itself, though it suggests that
1578  * the clauses are partially redundant. Since the alternative is
1579  * to omit mergejoin clauses and thereby possibly fail to generate a
1580  * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1581  * has to delete duplicates when it constructs the inner pathkeys
1582  * list, and we also have to deal with such cases specially in
1583  * create_mergejoin_plan().
1584  *----------
1585  */
1586  foreach(j, restrictinfos)
1587  {
1588  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1589  EquivalenceClass *clause_ec;
1590 
1591  clause_ec = rinfo->outer_is_left ?
1592  rinfo->left_ec : rinfo->right_ec;
1593  if (clause_ec == pathkey_ec)
1594  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1595  }
1596 
1597  /*
1598  * If we didn't find a mergeclause, we're done --- any additional
1599  * sort-key positions in the pathkeys are useless. (But we can still
1600  * mergejoin if we found at least one mergeclause.)
1601  */
1602  if (matched_restrictinfos == NIL)
1603  break;
1604 
1605  /*
1606  * If we did find usable mergeclause(s) for this sort-key position,
1607  * add them to result list.
1608  */
1609  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1610  }
1611 
1612  return mergeclauses;
1613 }
List * list_concat(List *list1, const List *list2)
Definition: list.c:561
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1493

References i, j, lappend(), lfirst, list_concat(), NIL, root, 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 1266 of file pathkeys.c.

1267 {
1268  ListCell *lc;
1269 
1270  /* If the TLE is resjunk, it's certainly not visible to the outer query */
1271  if (tle->resjunk)
1272  return NULL;
1273 
1274  /* Search the rel's targetlist to see what it will return */
1275  foreach(lc, rel->reltarget->exprs)
1276  {
1277  Var *var = (Var *) lfirst(lc);
1278 
1279  /* Ignore placeholders */
1280  if (!IsA(var, Var))
1281  continue;
1282  Assert(var->varno == rel->relid);
1283 
1284  /* If we find a Var referencing this TLE, we're good */
1285  if (var->varattno == tle->resno)
1286  return copyObject(var); /* Make a copy for safety */
1287  }
1288  return NULL;
1289 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
#define copyObject(obj)
Definition: nodes.h:224
List * exprs
Definition: pathnodes.h:1522
struct PathTarget * reltarget
Definition: pathnodes.h:883
Index relid
Definition: pathnodes.h:908
AttrNumber resno
Definition: primnodes.h:2159
AttrNumber varattno
Definition: primnodes.h:260
int varno
Definition: primnodes.h:255

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 681 of file pathkeys.c.

685 {
686  Path *matched_path = NULL;
687  ListCell *l;
688 
689  foreach(l, paths)
690  {
691  Path *path = (Path *) lfirst(l);
692 
693  /*
694  * Since cost comparison is a lot cheaper than pathkey comparison, do
695  * that first. (XXX is that still true?)
696  */
697  if (matched_path != NULL &&
698  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
699  continue;
700 
701  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
702  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
703  matched_path = path;
704  }
705  return matched_path;
706 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:412
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:341
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:115
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1658
List * pathkeys
Definition: pathnodes.h:1654

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 714 of file pathkeys.c.

715 {
716  ListCell *l;
717 
718  foreach(l, paths)
719  {
720  Path *innerpath = (Path *) lfirst(l);
721 
722  if (innerpath->parallel_safe &&
723  bms_is_empty(PATH_REQ_OUTER(innerpath)))
724  return innerpath;
725  }
726 
727  return NULL;
728 }
#define bms_is_empty(a)
Definition: bitmapset.h:118
bool parallel_safe
Definition: pathnodes.h:1644

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 635 of file pathkeys.c.

639 {
640  Path *matched_path = NULL;
641  ListCell *l;
642 
643  foreach(l, paths)
644  {
645  Path *path = (Path *) lfirst(l);
646 
647  /* If required, reject paths that are not parallel-safe */
648  if (require_parallel_safe && !path->parallel_safe)
649  continue;
650 
651  /*
652  * Since cost comparison is a lot cheaper than pathkey comparison, do
653  * that first. (XXX is that still true?)
654  */
655  if (matched_path != NULL &&
656  compare_path_costs(matched_path, path, cost_criterion) <= 0)
657  continue;
658 
659  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
660  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
661  matched_path = path;
662  }
663  return matched_path;
664 }
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:69

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(), generate_union_paths(), and get_cheapest_parameterized_child_path().

◆ get_useful_group_keys_orderings()

List* get_useful_group_keys_orderings ( PlannerInfo root,
Path path 
)

Definition at line 485 of file pathkeys.c.

486 {
487  Query *parse = root->parse;
488  List *infos = NIL;
489  PathKeyInfo *info;
490 
491  List *pathkeys = root->group_pathkeys;
492  List *clauses = root->processed_groupClause;
493 
494  /* always return at least the original pathkeys/clauses */
495  info = makeNode(PathKeyInfo);
496  info->pathkeys = pathkeys;
497  info->clauses = clauses;
498  infos = lappend(infos, info);
499 
500  /*
501  * Should we try generating alternative orderings of the group keys? If
502  * not, we produce only the order specified in the query, i.e. the
503  * optimization is effectively disabled.
504  */
506  return infos;
507 
508  /*
509  * Grouping sets have own and more complex logic to decide the ordering.
510  */
511  if (parse->groupingSets)
512  return infos;
513 
514  /*
515  * If the path is sorted in some way, try reordering the group keys to
516  * match the path as much of the ordering as possible. Then thanks to
517  * incremental sort we would get this sort as cheap as possible.
518  */
519  if (path->pathkeys &&
520  !pathkeys_contained_in(path->pathkeys, root->group_pathkeys))
521  {
522  int n;
523 
524  n = group_keys_reorder_by_pathkeys(path->pathkeys, &pathkeys, &clauses,
525  root->num_groupby_pathkeys);
526 
527  if (n > 0 &&
528  (enable_incremental_sort || n == root->num_groupby_pathkeys) &&
529  !pathkeys_are_duplicate(infos, pathkeys))
530  {
531  info = makeNode(PathKeyInfo);
532  info->pathkeys = pathkeys;
533  info->clauses = clauses;
534 
535  infos = lappend(infos, info);
536  }
537  }
538 
539  /*
540  * Try reordering pathkeys to minimize the sort cost (this time consider
541  * the ORDER BY clause).
542  */
543  if (root->sort_pathkeys &&
544  !pathkeys_contained_in(root->sort_pathkeys, root->group_pathkeys))
545  {
546  int n;
547 
548  n = group_keys_reorder_by_pathkeys(root->sort_pathkeys, &pathkeys,
549  &clauses,
550  root->num_groupby_pathkeys);
551 
552  if (n > 0 &&
553  (enable_incremental_sort || n == list_length(root->sort_pathkeys)) &&
554  !pathkeys_are_duplicate(infos, pathkeys))
555  {
556  info = makeNode(PathKeyInfo);
557  info->pathkeys = pathkeys;
558  info->clauses = clauses;
559 
560  infos = lappend(infos, info);
561  }
562  }
563 
564  return infos;
565 }
bool enable_incremental_sort
Definition: costsize.c:140
#define makeNode(_type_)
Definition: nodes.h:155
static int group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys, List **group_clauses, int num_groupby_pathkeys)
Definition: pathkeys.c:368
bool enable_group_by_reordering
Definition: pathkeys.c:31
static bool pathkeys_are_duplicate(List *infos, List *pathkeys)
Definition: pathkeys.c:456
static struct subre * parse(struct vars *v, int stopper, int type, struct state *init, struct state *final)
Definition: regcomp.c:715
List * pathkeys
Definition: pathnodes.h:1476
List * clauses
Definition: pathnodes.h:1477

References PathKeyInfo::clauses, enable_group_by_reordering, enable_incremental_sort, group_keys_reorder_by_pathkeys(), lappend(), list_length(), makeNode, NIL, parse(), PathKeyInfo::pathkeys, Path::pathkeys, pathkeys_are_duplicate(), pathkeys_contained_in(), and root.

Referenced by add_paths_to_grouping_rel(), and create_partial_grouping_paths().

◆ group_keys_reorder_by_pathkeys()

static int group_keys_reorder_by_pathkeys ( List pathkeys,
List **  group_pathkeys,
List **  group_clauses,
int  num_groupby_pathkeys 
)
static

Definition at line 368 of file pathkeys.c.

371 {
372  List *new_group_pathkeys = NIL,
373  *new_group_clauses = NIL;
374  List *grouping_pathkeys;
375  ListCell *lc;
376  int n;
377 
378  if (pathkeys == NIL || *group_pathkeys == NIL)
379  return 0;
380 
381  /*
382  * We're going to search within just the first num_groupby_pathkeys of
383  * *group_pathkeys. The thing is that root->group_pathkeys is passed as
384  * *group_pathkeys containing grouping pathkeys altogether with aggregate
385  * pathkeys. If we process aggregate pathkeys we could get an invalid
386  * result of get_sortgroupref_clause_noerr(), because their
387  * pathkey->pk_eclass->ec_sortref doesn't referece query targetlist. So,
388  * we allocate a separate list of pathkeys for lookups.
389  */
390  grouping_pathkeys = list_copy_head(*group_pathkeys, num_groupby_pathkeys);
391 
392  /*
393  * Walk the pathkeys (determining ordering of the input path) and see if
394  * there's a matching GROUP BY key. If we find one, we append it to the
395  * list, and do the same for the clauses.
396  *
397  * Once we find the first pathkey without a matching GROUP BY key, the
398  * rest of the pathkeys are useless and can't be used to evaluate the
399  * grouping, so we abort the loop and ignore the remaining pathkeys.
400  */
401  foreach(lc, pathkeys)
402  {
403  PathKey *pathkey = (PathKey *) lfirst(lc);
404  SortGroupClause *sgc;
405 
406  /*
407  * Pathkeys are built in a way that allows simply comparing pointers.
408  * Give up if we can't find the matching pointer. Also give up if
409  * there is no sortclause reference for some reason.
410  */
411  if (foreach_current_index(lc) >= num_groupby_pathkeys ||
412  !list_member_ptr(grouping_pathkeys, pathkey) ||
413  pathkey->pk_eclass->ec_sortref == 0)
414  break;
415 
416  /*
417  * Since 1349d27 pathkey coming from underlying node can be in the
418  * root->group_pathkeys but not in the processed_groupClause. So, we
419  * should be careful here.
420  */
421  sgc = get_sortgroupref_clause_noerr(pathkey->pk_eclass->ec_sortref,
422  *group_clauses);
423  if (!sgc)
424  /* The grouping clause does not cover this pathkey */
425  break;
426 
427  /*
428  * Sort group clause should have an ordering operator as long as there
429  * is an associated pathkey.
430  */
431  Assert(OidIsValid(sgc->sortop));
432 
433  new_group_pathkeys = lappend(new_group_pathkeys, pathkey);
434  new_group_clauses = lappend(new_group_clauses, sgc);
435  }
436 
437  /* remember the number of pathkeys with a matching GROUP BY key */
438  n = list_length(new_group_pathkeys);
439 
440  /* append the remaining group pathkeys (will be treated as not sorted) */
441  *group_pathkeys = list_concat_unique_ptr(new_group_pathkeys,
442  *group_pathkeys);
443  *group_clauses = list_concat_unique_ptr(new_group_clauses,
444  *group_clauses);
445 
446  list_free(grouping_pathkeys);
447  return n;
448 }
#define OidIsValid(objectId)
Definition: c.h:775
List * list_copy_head(const List *oldlist, int len)
Definition: list.c:1593
bool list_member_ptr(const List *list, const void *datum)
Definition: list.c:682
List * list_concat_unique_ptr(List *list1, const List *list2)
Definition: list.c:1427
void list_free(List *list)
Definition: list.c:1546
#define foreach_current_index(var_or_cell)
Definition: pg_list.h:403
SortGroupClause * get_sortgroupref_clause_noerr(Index sortref, List *clauses)
Definition: tlist.c:443

References Assert, foreach_current_index, get_sortgroupref_clause_noerr(), lappend(), lfirst, list_concat_unique_ptr(), list_copy_head(), list_free(), list_length(), list_member_ptr(), NIL, OidIsValid, and SortGroupClause::sortop.

Referenced by get_useful_group_keys_orderings().

◆ has_useful_pathkeys()

bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 2261 of file pathkeys.c.

2262 {
2263  if (rel->joininfo != NIL || rel->has_eclass_joins)
2264  return true; /* might be able to use pathkeys for merging */
2265  if (root->group_pathkeys != NIL)
2266  return true; /* might be able to use pathkeys for grouping */
2267  if (root->query_pathkeys != NIL)
2268  return true; /* might be able to use them for ordering */
2269  return false; /* definitely useless */
2270 }
List * joininfo
Definition: pathnodes.h:981
bool has_eclass_joins
Definition: pathnodes.h:983

References RelOptInfo::has_eclass_joins, RelOptInfo::joininfo, NIL, and root.

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 1446 of file pathkeys.c.

1447 {
1448  Expr *clause = restrictinfo->clause;
1449  Oid lefttype,
1450  righttype;
1451 
1452  /* Should be a mergeclause ... */
1453  Assert(restrictinfo->mergeopfamilies != NIL);
1454  /* ... with links not yet set */
1455  Assert(restrictinfo->left_ec == NULL);
1456  Assert(restrictinfo->right_ec == NULL);
1457 
1458  /* Need the declared input types of the operator */
1459  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1460 
1461  /* Find or create a matching EquivalenceClass for each side */
1462  restrictinfo->left_ec =
1464  (Expr *) get_leftop(clause),
1465  restrictinfo->mergeopfamilies,
1466  lefttype,
1467  ((OpExpr *) clause)->inputcollid,
1468  0,
1469  NULL,
1470  true);
1471  restrictinfo->right_ec =
1473  (Expr *) get_rightop(clause),
1474  restrictinfo->mergeopfamilies,
1475  righttype,
1476  ((OpExpr *) clause)->inputcollid,
1477  0,
1478  NULL,
1479  true);
1480 }
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1336
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:2552

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

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 55 of file pathkeys.c.

58 {
59  PathKey *pk;
60  ListCell *lc;
61  MemoryContext oldcontext;
62 
63  /* Can't make canonical pathkeys if the set of ECs might still change */
64  if (!root->ec_merging_done)
65  elog(ERROR, "too soon to build canonical pathkeys");
66 
67  /* The passed eclass might be non-canonical, so chase up to the top */
68  while (eclass->ec_merged)
69  eclass = eclass->ec_merged;
70 
71  foreach(lc, root->canon_pathkeys)
72  {
73  pk = (PathKey *) lfirst(lc);
74  if (eclass == pk->pk_eclass &&
75  opfamily == pk->pk_opfamily &&
76  strategy == pk->pk_strategy &&
77  nulls_first == pk->pk_nulls_first)
78  return pk;
79  }
80 
81  /*
82  * Be sure canonical pathkeys are allocated in the main planning context.
83  * Not an issue in normal planning, but it is for GEQO.
84  */
85  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
86 
87  pk = makeNode(PathKey);
88  pk->pk_eclass = eclass;
89  pk->pk_opfamily = opfamily;
90  pk->pk_strategy = strategy;
91  pk->pk_nulls_first = nulls_first;
92 
93  root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
94 
95  MemoryContextSwitchTo(oldcontext);
96 
97  return pk;
98 }
MemoryContextSwitchTo(old_ctx)
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:500

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

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 1838 of file pathkeys.c.

1841 {
1842  List *pathkeys = NIL;
1843  EquivalenceClass *lastoeclass;
1844  PathKey *opathkey;
1845  ListCell *lc;
1846  ListCell *lop;
1847 
1848  lastoeclass = NULL;
1849  opathkey = NULL;
1850  lop = list_head(outer_pathkeys);
1851 
1852  foreach(lc, mergeclauses)
1853  {
1854  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1855  EquivalenceClass *oeclass;
1856  EquivalenceClass *ieclass;
1857  PathKey *pathkey;
1858 
1860 
1861  if (rinfo->outer_is_left)
1862  {
1863  oeclass = rinfo->left_ec;
1864  ieclass = rinfo->right_ec;
1865  }
1866  else
1867  {
1868  oeclass = rinfo->right_ec;
1869  ieclass = rinfo->left_ec;
1870  }
1871 
1872  /* outer eclass should match current or next pathkeys */
1873  /* we check this carefully for debugging reasons */
1874  if (oeclass != lastoeclass)
1875  {
1876  if (!lop)
1877  elog(ERROR, "too few pathkeys for mergeclauses");
1878  opathkey = (PathKey *) lfirst(lop);
1879  lop = lnext(outer_pathkeys, lop);
1880  lastoeclass = opathkey->pk_eclass;
1881  if (oeclass != lastoeclass)
1882  elog(ERROR, "outer pathkeys do not match mergeclause");
1883  }
1884 
1885  /*
1886  * Often, we'll have same EC on both sides, in which case the outer
1887  * pathkey is also canonical for the inner side, and we can skip a
1888  * useless search.
1889  */
1890  if (ieclass == oeclass)
1891  pathkey = opathkey;
1892  else
1893  pathkey = make_canonical_pathkey(root,
1894  ieclass,
1895  opathkey->pk_opfamily,
1896  opathkey->pk_strategy,
1897  opathkey->pk_nulls_first);
1898 
1899  /*
1900  * Don't generate redundant pathkeys (which can happen if multiple
1901  * mergeclauses refer to the same EC). Because we do this, the output
1902  * pathkey list isn't necessarily ordered like the mergeclauses, which
1903  * complicates life for create_mergejoin_plan(). But if we didn't,
1904  * we'd have a noncanonical sort key list, which would be bad; for one
1905  * reason, it certainly wouldn't match any available sort order for
1906  * the input relation.
1907  */
1908  if (!pathkey_is_redundant(pathkey, pathkeys))
1909  pathkeys = lappend(pathkeys, pathkey);
1910  }
1911 
1912  return pathkeys;
1913 }
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, root, 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 197 of file pathkeys.c.

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

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 255 of file pathkeys.c.

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

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

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 1347 of file pathkeys.c.

1350 {
1351  List *result;
1352  bool sortable;
1353 
1355  &sortclauses,
1356  tlist,
1357  false,
1358  &sortable);
1359  /* It's caller error if not all clauses were sortable */
1360  Assert(sortable);
1361  return result;
1362 }
List * make_pathkeys_for_sortclauses_extended(PlannerInfo *root, List **sortclauses, List *tlist, bool remove_redundant, bool *sortable)
Definition: pathkeys.c:1384

References Assert, make_pathkeys_for_sortclauses_extended(), and root.

Referenced by adjust_group_pathkeys_for_groupagg(), generate_nonunion_paths(), generate_union_paths(), grouping_planner(), make_pathkeys_for_window(), 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 1384 of file pathkeys.c.

1389 {
1390  List *pathkeys = NIL;
1391  ListCell *l;
1392 
1393  *sortable = true;
1394  foreach(l, *sortclauses)
1395  {
1396  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1397  Expr *sortkey;
1398  PathKey *pathkey;
1399 
1400  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1401  if (!OidIsValid(sortcl->sortop))
1402  {
1403  *sortable = false;
1404  continue;
1405  }
1406  pathkey = make_pathkey_from_sortop(root,
1407  sortkey,
1408  sortcl->sortop,
1409  sortcl->nulls_first,
1410  sortcl->tleSortGroupRef,
1411  true);
1412 
1413  /* Canonical form eliminates redundant ordering keys */
1414  if (!pathkey_is_redundant(pathkey, pathkeys))
1415  pathkeys = lappend(pathkeys, pathkey);
1416  else if (remove_redundant)
1417  *sortclauses = foreach_delete_current(*sortclauses, l);
1418  }
1419  return pathkeys;
1420 }
static PathKey * make_pathkey_from_sortop(PlannerInfo *root, Expr *expr, Oid ordering_op, bool nulls_first, Index sortref, bool create_it)
Definition: pathkeys.c:255
#define foreach_delete_current(lst, var_or_cell)
Definition: pg_list.h:391
Index tleSortGroupRef
Definition: parsenodes.h:1442
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(), root, 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 899 of file pathkeys.c.

901 {
902  Node *clause = (Node *) rinfo->clause;
903  Node *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
904 
905  /* Direct match? */
906  if (equal(partexpr, clause))
907  return true;
908  /* NOT clause? */
909  else if (is_notclause(clause))
910  {
911  Node *arg = (Node *) get_notclausearg((Expr *) clause);
912 
913  if (equal(partexpr, arg))
914  return true;
915  }
916 
917  return false;
918 }
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 859 of file pathkeys.c.

860 {
861  PartitionScheme partscheme = partrel->part_scheme;
862  ListCell *lc;
863 
864  /*
865  * If the partkey isn't boolean, we can't possibly get a match.
866  *
867  * Partitioning currently can only use built-in AMs, so checking for
868  * built-in boolean opfamilies is good enough.
869  */
870  if (!IsBuiltinBooleanOpfamily(partscheme->partopfamily[partkeycol]))
871  return false;
872 
873  /* Check each restriction clause for the partitioned rel */
874  foreach(lc, partrel->baserestrictinfo)
875  {
876  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
877 
878  /* Ignore pseudoconstant quals, they won't match */
879  if (rinfo->pseudoconstant)
880  continue;
881 
882  /* See if we can match the clause's expression to the partkey column */
883  if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
884  return true;
885  }
886 
887  return false;
888 }
static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:899
List * baserestrictinfo
Definition: pathnodes.h:975

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 158 of file pathkeys.c.

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

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_are_duplicate()

static bool pathkeys_are_duplicate ( List infos,
List pathkeys 
)
static

Definition at line 456 of file pathkeys.c.

457 {
458  ListCell *lc;
459 
460  foreach(lc, infos)
461  {
462  PathKeyInfo *info = lfirst_node(PathKeyInfo, lc);
463 
464  if (compare_pathkeys(pathkeys, info->pathkeys) == PATHKEYS_EQUAL)
465  return true;
466  }
467  return false;
468 }
PathKeysComparison compare_pathkeys(List *keys1, List *keys2)
Definition: pathkeys.c:302

References compare_pathkeys(), lfirst_node, PathKeyInfo::pathkeys, and PATHKEYS_EQUAL.

Referenced by get_useful_group_keys_orderings().

◆ pathkeys_contained_in()

◆ pathkeys_count_contained_in()

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

Definition at line 573 of file pathkeys.c.

574 {
575  int n = 0;
576  ListCell *key1,
577  *key2;
578 
579  /*
580  * See if we can avoiding looping through both lists. This optimization
581  * gains us several percent in planning time in a worst-case test.
582  */
583  if (keys1 == keys2)
584  {
585  *n_common = list_length(keys1);
586  return true;
587  }
588  else if (keys1 == NIL)
589  {
590  *n_common = 0;
591  return true;
592  }
593  else if (keys2 == NIL)
594  {
595  *n_common = 0;
596  return false;
597  }
598 
599  /*
600  * If both lists are non-empty, iterate through both to find out how many
601  * items are shared.
602  */
603  forboth(key1, keys1, key2, keys2)
604  {
605  PathKey *pathkey1 = (PathKey *) lfirst(key1);
606  PathKey *pathkey2 = (PathKey *) lfirst(key2);
607 
608  if (pathkey1 != pathkey2)
609  {
610  *n_common = n;
611  return false;
612  }
613  n++;
614  }
615 
616  /* If we ended with a null value, then we've processed the whole list. */
617  *n_common = n;
618  return (key1 == NULL);
619 }

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

Referenced by build_setop_child_paths(), create_final_distinct_paths(), create_one_window_path(), create_ordered_paths(), create_partial_distinct_paths(), create_window_paths(), gather_grouping_paths(), generate_useful_gather_paths(), make_ordered_path(), pathkeys_useful_for_ordering(), and pathkeys_useful_for_setop().

◆ pathkeys_useful_for_grouping()

static int pathkeys_useful_for_grouping ( PlannerInfo root,
List pathkeys 
)
static

Definition at line 2170 of file pathkeys.c.

2171 {
2172  ListCell *key;
2173  int n = 0;
2174 
2175  /* no special ordering requested for grouping */
2176  if (root->group_pathkeys == NIL)
2177  return 0;
2178 
2179  /* walk the pathkeys and search for matching group key */
2180  foreach(key, pathkeys)
2181  {
2182  PathKey *pathkey = (PathKey *) lfirst(key);
2183 
2184  /* no matching group key, we're done */
2185  if (!list_member_ptr(root->group_pathkeys, pathkey))
2186  break;
2187 
2188  n++;
2189  }
2190 
2191  return n;
2192 }

References sort-test::key, lfirst, list_member_ptr(), NIL, and root.

Referenced by truncate_useless_pathkeys().

◆ pathkeys_useful_for_merging()

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

Definition at line 2036 of file pathkeys.c.

2037 {
2038  int useful = 0;
2039  ListCell *i;
2040 
2041  foreach(i, pathkeys)
2042  {
2043  PathKey *pathkey = (PathKey *) lfirst(i);
2044  bool matched = false;
2045  ListCell *j;
2046 
2047  /* If "wrong" direction, not useful for merging */
2048  if (!right_merge_direction(root, pathkey))
2049  break;
2050 
2051  /*
2052  * First look into the EquivalenceClass of the pathkey, to see if
2053  * there are any members not yet joined to the rel. If so, it's
2054  * surely possible to generate a mergejoin clause using them.
2055  */
2056  if (rel->has_eclass_joins &&
2057  eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
2058  matched = true;
2059  else
2060  {
2061  /*
2062  * Otherwise search the rel's joininfo list, which contains
2063  * non-EquivalenceClass-derivable join clauses that might
2064  * nonetheless be mergejoinable.
2065  */
2066  foreach(j, rel->joininfo)
2067  {
2068  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
2069 
2070  if (restrictinfo->mergeopfamilies == NIL)
2071  continue;
2072  update_mergeclause_eclasses(root, restrictinfo);
2073 
2074  if (pathkey->pk_eclass == restrictinfo->left_ec ||
2075  pathkey->pk_eclass == restrictinfo->right_ec)
2076  {
2077  matched = true;
2078  break;
2079  }
2080  }
2081  }
2082 
2083  /*
2084  * If we didn't find a mergeclause, we're done --- any additional
2085  * sort-key positions in the pathkeys are useless. (But we can still
2086  * mergejoin if we found at least one mergeclause.)
2087  */
2088  if (matched)
2089  useful++;
2090  else
2091  break;
2092  }
2093 
2094  return useful;
2095 }
bool eclass_useful_for_merging(PlannerInfo *root, EquivalenceClass *eclass, RelOptInfo *rel)
Definition: equivclass.c:3208
static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey)
Definition: pathkeys.c:2103

References eclass_useful_for_merging(), RelOptInfo::has_eclass_joins, i, j, RelOptInfo::joininfo, lfirst, NIL, right_merge_direction(), root, 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 2140 of file pathkeys.c.

2141 {
2142  int n_common_pathkeys;
2143 
2144  (void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys,
2145  &n_common_pathkeys);
2146 
2147  return n_common_pathkeys;
2148 }
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:573

References pathkeys_count_contained_in(), and root.

Referenced by truncate_useless_pathkeys().

◆ pathkeys_useful_for_setop()

static int pathkeys_useful_for_setop ( PlannerInfo root,
List pathkeys 
)
static

Definition at line 2200 of file pathkeys.c.

2201 {
2202  int n_common_pathkeys;
2203 
2204  (void) pathkeys_count_contained_in(root->setop_pathkeys, pathkeys,
2205  &n_common_pathkeys);
2206 
2207  return n_common_pathkeys;
2208 }

References pathkeys_count_contained_in(), and root.

Referenced by truncate_useless_pathkeys().

◆ right_merge_direction()

static bool right_merge_direction ( PlannerInfo root,
PathKey pathkey 
)
static

Definition at line 2103 of file pathkeys.c.

2104 {
2105  ListCell *l;
2106 
2107  foreach(l, root->query_pathkeys)
2108  {
2109  PathKey *query_pathkey = (PathKey *) lfirst(l);
2110 
2111  if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
2112  pathkey->pk_opfamily == query_pathkey->pk_opfamily)
2113  {
2114  /*
2115  * Found a matching query sort column. Prefer this pathkey's
2116  * direction iff it matches. Note that we ignore pk_nulls_first,
2117  * which means that a sort might be needed anyway ... but we still
2118  * want to prefer only one of the two possible directions, and we
2119  * might as well use this one.
2120  */
2121  return (pathkey->pk_strategy == query_pathkey->pk_strategy);
2122  }
2123  }
2124 
2125  /* If no matching ORDER BY request, prefer the ASC direction */
2126  return (pathkey->pk_strategy == BTLessStrategyNumber);
2127 }

References BTLessStrategyNumber, lfirst, PathKey::pk_opfamily, PathKey::pk_strategy, and root.

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 1642 of file pathkeys.c.

1645 {
1646  List *pathkeys = NIL;
1647  int nClauses = list_length(mergeclauses);
1648  EquivalenceClass **ecs;
1649  int *scores;
1650  int necs;
1651  ListCell *lc;
1652  int j;
1653 
1654  /* Might have no mergeclauses */
1655  if (nClauses == 0)
1656  return NIL;
1657 
1658  /*
1659  * Make arrays of the ECs used by the mergeclauses (dropping any
1660  * duplicates) and their "popularity" scores.
1661  */
1662  ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
1663  scores = (int *) palloc(nClauses * sizeof(int));
1664  necs = 0;
1665 
1666  foreach(lc, mergeclauses)
1667  {
1668  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1669  EquivalenceClass *oeclass;
1670  int score;
1671  ListCell *lc2;
1672 
1673  /* get the outer eclass */
1675 
1676  if (rinfo->outer_is_left)
1677  oeclass = rinfo->left_ec;
1678  else
1679  oeclass = rinfo->right_ec;
1680 
1681  /* reject duplicates */
1682  for (j = 0; j < necs; j++)
1683  {
1684  if (ecs[j] == oeclass)
1685  break;
1686  }
1687  if (j < necs)
1688  continue;
1689 
1690  /* compute score */
1691  score = 0;
1692  foreach(lc2, oeclass->ec_members)
1693  {
1695 
1696  /* Potential future join partner? */
1697  if (!em->em_is_const && !em->em_is_child &&
1698  !bms_overlap(em->em_relids, joinrel->relids))
1699  score++;
1700  }
1701 
1702  ecs[necs] = oeclass;
1703  scores[necs] = score;
1704  necs++;
1705  }
1706 
1707  /*
1708  * Find out if we have all the ECs mentioned in query_pathkeys; if so we
1709  * can generate a sort order that's also useful for final output. If we
1710  * only have a prefix of the query_pathkeys, and that prefix is the entire
1711  * join condition, then it's useful to use the prefix as the pathkeys as
1712  * this increases the chances that an incremental sort will be able to be
1713  * used by the upper planner.
1714  */
1715  if (root->query_pathkeys)
1716  {
1717  int matches = 0;
1718 
1719  foreach(lc, root->query_pathkeys)
1720  {
1721  PathKey *query_pathkey = (PathKey *) lfirst(lc);
1722  EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1723 
1724  for (j = 0; j < necs; j++)
1725  {
1726  if (ecs[j] == query_ec)
1727  break; /* found match */
1728  }
1729  if (j >= necs)
1730  break; /* didn't find match */
1731 
1732  matches++;
1733  }
1734  /* if we got to the end of the list, we have them all */
1735  if (lc == NULL)
1736  {
1737  /* copy query_pathkeys as starting point for our output */
1738  pathkeys = list_copy(root->query_pathkeys);
1739  /* mark their ECs as already-emitted */
1740  foreach(lc, root->query_pathkeys)
1741  {
1742  PathKey *query_pathkey = (PathKey *) lfirst(lc);
1743  EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1744 
1745  for (j = 0; j < necs; j++)
1746  {
1747  if (ecs[j] == query_ec)
1748  {
1749  scores[j] = -1;
1750  break;
1751  }
1752  }
1753  }
1754  }
1755 
1756  /*
1757  * If we didn't match to all of the query_pathkeys, but did match to
1758  * all of the join clauses then we'll make use of these as partially
1759  * sorted input is better than nothing for the upper planner as it may
1760  * lead to incremental sorts instead of full sorts.
1761  */
1762  else if (matches == nClauses)
1763  {
1764  pathkeys = list_copy_head(root->query_pathkeys, matches);
1765 
1766  /* we have all of the join pathkeys, so nothing more to do */
1767  pfree(ecs);
1768  pfree(scores);
1769 
1770  return pathkeys;
1771  }
1772  }
1773 
1774  /*
1775  * Add remaining ECs to the list in popularity order, using a default sort
1776  * ordering. (We could use qsort() here, but the list length is usually
1777  * so small it's not worth it.)
1778  */
1779  for (;;)
1780  {
1781  int best_j;
1782  int best_score;
1783  EquivalenceClass *ec;
1784  PathKey *pathkey;
1785 
1786  best_j = 0;
1787  best_score = scores[0];
1788  for (j = 1; j < necs; j++)
1789  {
1790  if (scores[j] > best_score)
1791  {
1792  best_j = j;
1793  best_score = scores[j];
1794  }
1795  }
1796  if (best_score < 0)
1797  break; /* all done */
1798  ec = ecs[best_j];
1799  scores[best_j] = -1;
1800  pathkey = make_canonical_pathkey(root,
1801  ec,
1804  false);
1805  /* can't be redundant because no duplicate ECs */
1806  Assert(!pathkey_is_redundant(pathkey, pathkeys));
1807  pathkeys = lappend(pathkeys, pathkey);
1808  }
1809 
1810  pfree(ecs);
1811  pfree(scores);
1812 
1813  return pathkeys;
1814 }
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:582
List * list_copy(const List *oldlist)
Definition: list.c:1573
void pfree(void *pointer)
Definition: mcxt.c:1520
void * palloc(Size size)
Definition: mcxt.c:1316
#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(), RelOptInfo::relids, root, 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 1941 of file pathkeys.c.

1944 {
1945  List *new_mergeclauses = NIL;
1946  PathKey *pathkey;
1947  EquivalenceClass *pathkey_ec;
1948  bool matched_pathkey;
1949  ListCell *lip;
1950  ListCell *i;
1951 
1952  /* No pathkeys => no mergeclauses (though we don't expect this case) */
1953  if (pathkeys == NIL)
1954  return NIL;
1955  /* Initialize to consider first pathkey */
1956  lip = list_head(pathkeys);
1957  pathkey = (PathKey *) lfirst(lip);
1958  pathkey_ec = pathkey->pk_eclass;
1959  lip = lnext(pathkeys, lip);
1960  matched_pathkey = false;
1961 
1962  /* Scan mergeclauses to see how many we can use */
1963  foreach(i, mergeclauses)
1964  {
1965  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1966  EquivalenceClass *clause_ec;
1967 
1968  /* Assume we needn't do update_mergeclause_eclasses again here */
1969 
1970  /* Check clause's inner-rel EC against current pathkey */
1971  clause_ec = rinfo->outer_is_left ?
1972  rinfo->right_ec : rinfo->left_ec;
1973 
1974  /* If we don't have a match, attempt to advance to next pathkey */
1975  if (clause_ec != pathkey_ec)
1976  {
1977  /* If we had no clauses matching this inner pathkey, must stop */
1978  if (!matched_pathkey)
1979  break;
1980 
1981  /* Advance to next inner pathkey, if any */
1982  if (lip == NULL)
1983  break;
1984  pathkey = (PathKey *) lfirst(lip);
1985  pathkey_ec = pathkey->pk_eclass;
1986  lip = lnext(pathkeys, lip);
1987  matched_pathkey = false;
1988  }
1989 
1990  /* If mergeclause matches current inner pathkey, we can use it */
1991  if (clause_ec == pathkey_ec)
1992  {
1993  new_mergeclauses = lappend(new_mergeclauses, rinfo);
1994  matched_pathkey = true;
1995  }
1996  else
1997  {
1998  /* Else, no hope of adding any more mergeclauses */
1999  break;
2000  }
2001  }
2002 
2003  return new_mergeclauses;
2004 }

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 2215 of file pathkeys.c.

2218 {
2219  int nuseful;
2220  int nuseful2;
2221 
2222  nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
2223  nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
2224  if (nuseful2 > nuseful)
2225  nuseful = nuseful2;
2226  nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
2227  if (nuseful2 > nuseful)
2228  nuseful = nuseful2;
2229  nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
2230  if (nuseful2 > nuseful)
2231  nuseful = nuseful2;
2232 
2233  /*
2234  * Note: not safe to modify input list destructively, but we can avoid
2235  * copying the list if we're not actually going to change it
2236  */
2237  if (nuseful == 0)
2238  return NIL;
2239  else if (nuseful == list_length(pathkeys))
2240  return pathkeys;
2241  else
2242  return list_copy_head(pathkeys, nuseful);
2243 }
static int pathkeys_useful_for_setop(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2200
static int pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2140
static int pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2170
static int pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2036

References list_copy_head(), list_length(), NIL, pathkeys_useful_for_grouping(), pathkeys_useful_for_merging(), pathkeys_useful_for_ordering(), pathkeys_useful_for_setop(), and root.

Referenced by build_index_paths(), and build_join_pathkeys().

◆ update_mergeclause_eclasses()

void update_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1493 of file pathkeys.c.

1494 {
1495  /* Should be a merge clause ... */
1496  Assert(restrictinfo->mergeopfamilies != NIL);
1497  /* ... with pointers already set */
1498  Assert(restrictinfo->left_ec != NULL);
1499  Assert(restrictinfo->right_ec != NULL);
1500 
1501  /* Chase up to the top as needed */
1502  while (restrictinfo->left_ec->ec_merged)
1503  restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
1504  while (restrictinfo->right_ec->ec_merged)
1505  restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
1506 }

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().

Variable Documentation

◆ enable_group_by_reordering

bool enable_group_by_reordering = true

Definition at line 31 of file pathkeys.c.

Referenced by get_useful_group_keys_orderings().