PostgreSQL Source Code  git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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 reverse_sort, 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)
 
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 remove_group_rtindex, bool *sortable, bool set_ec_sortref)
 
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 107 of file pathkeys.c.

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

1005 {
1006  List *pathkeys;
1007  Oid opfamily,
1008  opcintype;
1009  int16 strategy;
1010  PathKey *cpathkey;
1011 
1012  /* Find the operator in pg_amop --- failure shouldn't happen */
1013  if (!get_ordering_op_properties(opno,
1014  &opfamily, &opcintype, &strategy))
1015  elog(ERROR, "operator %u is not a valid ordering operator",
1016  opno);
1017 
1018  cpathkey = make_pathkey_from_sortinfo(root,
1019  expr,
1020  opfamily,
1021  opcintype,
1022  exprCollation((Node *) expr),
1023  (strategy == BTGreaterStrategyNumber),
1024  (strategy == BTGreaterStrategyNumber),
1025  0,
1026  rel,
1027  create_it);
1028 
1029  if (cpathkey)
1030  pathkeys = list_make1(cpathkey);
1031  else
1032  pathkeys = NIL;
1033 
1034  return pathkeys;
1035 }
signed short int16
Definition: c.h:507
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
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:198
#define list_make1(x1)
Definition: pg_list.h:212
unsigned int Oid
Definition: postgres_ext.h:31
tree ctl root
Definition: radixtree.h:1886
#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 740 of file pathkeys.c.

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

1298 {
1299  /* RIGHT_SEMI should not come here */
1300  Assert(jointype != JOIN_RIGHT_SEMI);
1301 
1302  if (jointype == JOIN_FULL ||
1303  jointype == JOIN_RIGHT ||
1304  jointype == JOIN_RIGHT_ANTI)
1305  return NIL;
1306 
1307  /*
1308  * This used to be quite a complex bit of code, but now that all pathkey
1309  * sublists start out life canonicalized, we don't have to do a darn thing
1310  * here!
1311  *
1312  * We do, however, need to truncate the pathkeys list, since it may
1313  * contain pathkeys that were useful for forming this joinrel but are
1314  * uninteresting to higher levels.
1315  */
1316  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1317 }
@ JOIN_FULL
Definition: nodes.h:295
@ JOIN_RIGHT
Definition: nodes.h:296
@ JOIN_RIGHT_SEMI
Definition: nodes.h:309
@ JOIN_RIGHT_ANTI
Definition: nodes.h:310
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2231

References Assert, JOIN_FULL, JOIN_RIGHT, JOIN_RIGHT_ANTI, JOIN_RIGHT_SEMI, 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 919 of file pathkeys.c.

921 {
922  List *retval = NIL;
923  PartitionScheme partscheme = partrel->part_scheme;
924  int i;
925 
926  Assert(partscheme != NULL);
927  Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
928  /* For now, we can only cope with baserels */
929  Assert(IS_SIMPLE_REL(partrel));
930 
931  for (i = 0; i < partscheme->partnatts; i++)
932  {
933  PathKey *cpathkey;
934  Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
935 
936  /*
937  * Try to make a canonical pathkey for this partkey.
938  *
939  * We assume the PartitionDesc lists any NULL partition last, so we
940  * treat the scan like a NULLS LAST index: we have nulls_first for
941  * backwards scan only.
942  */
943  cpathkey = make_pathkey_from_sortinfo(root,
944  keyCol,
945  partscheme->partopfamily[i],
946  partscheme->partopcintype[i],
947  partscheme->partcollation[i],
948  ScanDirectionIsBackward(scandir),
949  ScanDirectionIsBackward(scandir),
950  0,
951  partrel->relids,
952  false);
953 
954 
955  if (cpathkey)
956  {
957  /*
958  * We found the sort key in an EquivalenceClass, so it's relevant
959  * for this query. Add it to list, unless it's redundant.
960  */
961  if (!pathkey_is_redundant(cpathkey, retval))
962  retval = lappend(retval, cpathkey);
963  }
964  else
965  {
966  /*
967  * Boolean partition keys might be redundant even if they do not
968  * appear in an EquivalenceClass, because of our special treatment
969  * of boolean equality conditions --- see the comment for
970  * partkey_is_bool_constant_for_query(). If that applies, we can
971  * continue to examine lower-order partition keys. Otherwise, the
972  * sort key is not an interesting sort order for this query, so we
973  * should stop considering partition columns; any lower-order sort
974  * keys won't be useful either.
975  */
976  if (!partkey_is_bool_constant_for_query(partrel, i))
977  {
978  *partialkeys = true;
979  return retval;
980  }
981  }
982  }
983 
984  *partialkeys = false;
985  return retval;
986 }
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:844
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:839
#define linitial(l)
Definition: pg_list.h:178
Relids relids
Definition: pathnodes.h:871
Bitmapset * live_parts
Definition: pathnodes.h:1039

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

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

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

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

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

1252 {
1253  ListCell *lc;
1254 
1255  /* If the TLE is resjunk, it's certainly not visible to the outer query */
1256  if (tle->resjunk)
1257  return NULL;
1258 
1259  /* Search the rel's targetlist to see what it will return */
1260  foreach(lc, rel->reltarget->exprs)
1261  {
1262  Var *var = (Var *) lfirst(lc);
1263 
1264  /* Ignore placeholders */
1265  if (!IsA(var, Var))
1266  continue;
1267  Assert(var->varno == rel->relid);
1268 
1269  /* If we find a Var referencing this TLE, we're good */
1270  if (var->varattno == tle->resno)
1271  return copyObject(var); /* Make a copy for safety */
1272  }
1273  return NULL;
1274 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
#define copyObject(obj)
Definition: nodes.h:224
List * exprs
Definition: pathnodes.h:1542
struct PathTarget * reltarget
Definition: pathnodes.h:893
Index relid
Definition: pathnodes.h:918
AttrNumber resno
Definition: primnodes.h:2192
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 666 of file pathkeys.c.

670 {
671  Path *matched_path = NULL;
672  ListCell *l;
673 
674  foreach(l, paths)
675  {
676  Path *path = (Path *) lfirst(l);
677 
678  /*
679  * Since cost comparison is a lot cheaper than pathkey comparison, do
680  * that first. (XXX is that still true?)
681  */
682  if (matched_path != NULL &&
683  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
684  continue;
685 
686  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
687  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
688  matched_path = path;
689  }
690  return matched_path;
691 }
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:343
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:124
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1679
List * pathkeys
Definition: pathnodes.h:1675

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

700 {
701  ListCell *l;
702 
703  foreach(l, paths)
704  {
705  Path *innerpath = (Path *) lfirst(l);
706 
707  if (innerpath->parallel_safe &&
708  bms_is_empty(PATH_REQ_OUTER(innerpath)))
709  return innerpath;
710  }
711 
712  return NULL;
713 }
#define bms_is_empty(a)
Definition: bitmapset.h:118
bool parallel_safe
Definition: pathnodes.h:1664

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

624 {
625  Path *matched_path = NULL;
626  ListCell *l;
627 
628  foreach(l, paths)
629  {
630  Path *path = (Path *) lfirst(l);
631 
632  /* If required, reject paths that are not parallel-safe */
633  if (require_parallel_safe && !path->parallel_safe)
634  continue;
635 
636  /*
637  * Since cost comparison is a lot cheaper than pathkey comparison, do
638  * that first. (XXX is that still true?)
639  */
640  if (matched_path != NULL &&
641  compare_path_costs(matched_path, path, cost_criterion) <= 0)
642  continue;
643 
644  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
645  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
646  matched_path = path;
647  }
648  return matched_path;
649 }
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 467 of file pathkeys.c.

468 {
469  Query *parse = root->parse;
470  List *infos = NIL;
471  GroupByOrdering *info;
472 
473  List *pathkeys = root->group_pathkeys;
474  List *clauses = root->processed_groupClause;
475 
476  /* always return at least the original pathkeys/clauses */
477  info = makeNode(GroupByOrdering);
478  info->pathkeys = pathkeys;
479  info->clauses = clauses;
480  infos = lappend(infos, info);
481 
482  /*
483  * Should we try generating alternative orderings of the group keys? If
484  * not, we produce only the order specified in the query, i.e. the
485  * optimization is effectively disabled.
486  */
488  return infos;
489 
490  /*
491  * Grouping sets have own and more complex logic to decide the ordering.
492  */
493  if (parse->groupingSets)
494  return infos;
495 
496  /*
497  * If the path is sorted in some way, try reordering the group keys to
498  * match the path as much of the ordering as possible. Then thanks to
499  * incremental sort we would get this sort as cheap as possible.
500  */
501  if (path->pathkeys &&
502  !pathkeys_contained_in(path->pathkeys, root->group_pathkeys))
503  {
504  int n;
505 
506  n = group_keys_reorder_by_pathkeys(path->pathkeys, &pathkeys, &clauses,
507  root->num_groupby_pathkeys);
508 
509  if (n > 0 &&
510  (enable_incremental_sort || n == root->num_groupby_pathkeys) &&
511  compare_pathkeys(pathkeys, root->group_pathkeys) != PATHKEYS_EQUAL)
512  {
513  info = makeNode(GroupByOrdering);
514  info->pathkeys = pathkeys;
515  info->clauses = clauses;
516 
517  infos = lappend(infos, info);
518  }
519  }
520 
521 #ifdef USE_ASSERT_CHECKING
522  {
524  ListCell *lc;
525 
526  /* Test consistency of info structures */
527  for_each_from(lc, infos, 1)
528  {
529  ListCell *lc1,
530  *lc2;
531 
532  info = lfirst_node(GroupByOrdering, lc);
533 
534  Assert(list_length(info->clauses) == list_length(pinfo->clauses));
535  Assert(list_length(info->pathkeys) == list_length(pinfo->pathkeys));
536  Assert(list_difference(info->clauses, pinfo->clauses) == NIL);
537  Assert(list_difference_ptr(info->pathkeys, pinfo->pathkeys) == NIL);
538 
539  forboth(lc1, info->clauses, lc2, info->pathkeys)
540  {
542  PathKey *pk = lfirst_node(PathKey, lc2);
543 
544  Assert(pk->pk_eclass->ec_sortref == sgc->tleSortGroupRef);
545  }
546  }
547  }
548 #endif
549  return infos;
550 }
bool enable_incremental_sort
Definition: costsize.c:151
List * list_difference_ptr(const List *list1, const List *list2)
Definition: list.c:1263
List * list_difference(const List *list1, const List *list2)
Definition: list.c:1237
#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:370
bool enable_group_by_reordering
Definition: pathkeys.c:32
PathKeysComparison compare_pathkeys(List *keys1, List *keys2)
Definition: pathkeys.c:304
#define linitial_node(type, l)
Definition: pg_list.h:181
#define for_each_from(cell, lst, N)
Definition: pg_list.h:414
static struct subre * parse(struct vars *v, int stopper, int type, struct state *init, struct state *final)
Definition: regcomp.c:717
Index tleSortGroupRef
Definition: parsenodes.h:1438

References Assert, GroupByOrdering::clauses, compare_pathkeys(), enable_group_by_reordering, enable_incremental_sort, for_each_from, forboth, group_keys_reorder_by_pathkeys(), lappend(), lfirst_node, linitial_node, list_difference(), list_difference_ptr(), list_length(), makeNode, NIL, parse(), GroupByOrdering::pathkeys, Path::pathkeys, pathkeys_contained_in(), PATHKEYS_EQUAL, root, and SortGroupClause::tleSortGroupRef.

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

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

2278 {
2279  if (rel->joininfo != NIL || rel->has_eclass_joins)
2280  return true; /* might be able to use pathkeys for merging */
2281  if (root->group_pathkeys != NIL)
2282  return true; /* might be able to use pathkeys for grouping */
2283  if (root->query_pathkeys != NIL)
2284  return true; /* might be able to use them for ordering */
2285  return false; /* definitely useless */
2286 }
List * joininfo
Definition: pathnodes.h:991
bool has_eclass_joins
Definition: pathnodes.h:993

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

1463 {
1464  Expr *clause = restrictinfo->clause;
1465  Oid lefttype,
1466  righttype;
1467 
1468  /* Should be a mergeclause ... */
1469  Assert(restrictinfo->mergeopfamilies != NIL);
1470  /* ... with links not yet set */
1471  Assert(restrictinfo->left_ec == NULL);
1472  Assert(restrictinfo->right_ec == NULL);
1473 
1474  /* Need the declared input types of the operator */
1475  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1476 
1477  /* Find or create a matching EquivalenceClass for each side */
1478  restrictinfo->left_ec =
1480  (Expr *) get_leftop(clause),
1481  restrictinfo->mergeopfamilies,
1482  lefttype,
1483  ((OpExpr *) clause)->inputcollid,
1484  0,
1485  NULL,
1486  true);
1487  restrictinfo->right_ec =
1489  (Expr *) get_rightop(clause),
1490  restrictinfo->mergeopfamilies,
1491  righttype,
1492  ((OpExpr *) clause)->inputcollid,
1493  0,
1494  NULL,
1495  true);
1496 }
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1358
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:95
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:83
Expr * clause
Definition: pathnodes.h:2574

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

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

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

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

Definition at line 256 of file pathkeys.c.

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

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

1338 {
1339  List *result;
1340  bool sortable;
1341 
1343  &sortclauses,
1344  tlist,
1345  false,
1346  false,
1347  &sortable,
1348  false);
1349  /* It's caller error if not all clauses were sortable */
1350  Assert(sortable);
1351  return result;
1352 }
List * make_pathkeys_for_sortclauses_extended(PlannerInfo *root, List **sortclauses, List *tlist, bool remove_redundant, bool remove_group_rtindex, bool *sortable, bool set_ec_sortref)
Definition: pathkeys.c:1380

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  remove_group_rtindex,
bool sortable,
bool  set_ec_sortref 
)

Definition at line 1380 of file pathkeys.c.

1387 {
1388  List *pathkeys = NIL;
1389  ListCell *l;
1390 
1391  *sortable = true;
1392  foreach(l, *sortclauses)
1393  {
1394  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1395  Expr *sortkey;
1396  PathKey *pathkey;
1397 
1398  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1399  if (!OidIsValid(sortcl->sortop))
1400  {
1401  *sortable = false;
1402  continue;
1403  }
1404  if (remove_group_rtindex)
1405  {
1406  Assert(root->group_rtindex > 0);
1407  sortkey = (Expr *)
1408  remove_nulling_relids((Node *) sortkey,
1409  bms_make_singleton(root->group_rtindex),
1410  NULL);
1411  }
1412  pathkey = make_pathkey_from_sortop(root,
1413  sortkey,
1414  sortcl->sortop,
1415  sortcl->reverse_sort,
1416  sortcl->nulls_first,
1417  sortcl->tleSortGroupRef,
1418  true);
1419  if (pathkey->pk_eclass->ec_sortref == 0 && set_ec_sortref)
1420  {
1421  /*
1422  * Copy the sortref if it hasn't been set yet. That may happen if
1423  * the EquivalenceClass was constructed from a WHERE clause, i.e.
1424  * it doesn't have a target reference at all.
1425  */
1426  pathkey->pk_eclass->ec_sortref = sortcl->tleSortGroupRef;
1427  }
1428 
1429  /* Canonical form eliminates redundant ordering keys */
1430  if (!pathkey_is_redundant(pathkey, pathkeys))
1431  pathkeys = lappend(pathkeys, pathkey);
1432  else if (remove_redundant)
1433  *sortclauses = foreach_delete_current(*sortclauses, l);
1434  }
1435  return pathkeys;
1436 }
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:216
static PathKey * make_pathkey_from_sortop(PlannerInfo *root, Expr *expr, Oid ordering_op, bool reverse_sort, bool nulls_first, Index sortref, bool create_it)
Definition: pathkeys.c:256
#define foreach_delete_current(lst, var_or_cell)
Definition: pg_list.h:391
Node * remove_nulling_relids(Node *node, const Bitmapset *removable_relids, const Bitmapset *except_relids)
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:379

References Assert, bms_make_singleton(), foreach_delete_current, get_sortgroupclause_expr(), lappend(), lfirst, make_pathkey_from_sortop(), NIL, SortGroupClause::nulls_first, OidIsValid, pathkey_is_redundant(), remove_nulling_relids(), SortGroupClause::reverse_sort, 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 884 of file pathkeys.c.

886 {
887  Node *clause = (Node *) rinfo->clause;
888  Node *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
889 
890  /* Direct match? */
891  if (equal(partexpr, clause))
892  return true;
893  /* NOT clause? */
894  else if (is_notclause(clause))
895  {
896  Node *arg = (Node *) get_notclausearg((Expr *) clause);
897 
898  if (equal(partexpr, arg))
899  return true;
900  }
901 
902  return false;
903 }
static Expr * get_notclausearg(const void *notclause)
Definition: nodeFuncs.h:134
static bool is_notclause(const void *clause)
Definition: nodeFuncs.h:125
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 844 of file pathkeys.c.

845 {
846  PartitionScheme partscheme = partrel->part_scheme;
847  ListCell *lc;
848 
849  /*
850  * If the partkey isn't boolean, we can't possibly get a match.
851  *
852  * Partitioning currently can only use built-in AMs, so checking for
853  * built-in boolean opfamilies is good enough.
854  */
855  if (!IsBuiltinBooleanOpfamily(partscheme->partopfamily[partkeycol]))
856  return false;
857 
858  /* Check each restriction clause for the partitioned rel */
859  foreach(lc, partrel->baserestrictinfo)
860  {
861  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
862 
863  /* Ignore pseudoconstant quals, they won't match */
864  if (rinfo->pseudoconstant)
865  continue;
866 
867  /* See if we can match the clause's expression to the partkey column */
868  if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
869  return true;
870  }
871 
872  return false;
873 }
static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:884
List * baserestrictinfo
Definition: pathnodes.h:985

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

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

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

559 {
560  int n = 0;
561  ListCell *key1,
562  *key2;
563 
564  /*
565  * See if we can avoiding looping through both lists. This optimization
566  * gains us several percent in planning time in a worst-case test.
567  */
568  if (keys1 == keys2)
569  {
570  *n_common = list_length(keys1);
571  return true;
572  }
573  else if (keys1 == NIL)
574  {
575  *n_common = 0;
576  return true;
577  }
578  else if (keys2 == NIL)
579  {
580  *n_common = 0;
581  return false;
582  }
583 
584  /*
585  * If both lists are non-empty, iterate through both to find out how many
586  * items are shared.
587  */
588  forboth(key1, keys1, key2, keys2)
589  {
590  PathKey *pathkey1 = (PathKey *) lfirst(key1);
591  PathKey *pathkey2 = (PathKey *) lfirst(key2);
592 
593  if (pathkey1 != pathkey2)
594  {
595  *n_common = n;
596  return false;
597  }
598  n++;
599  }
600 
601  /* If we ended with a null value, then we've processed the whole list. */
602  *n_common = n;
603  return (key1 == NULL);
604 }

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

Referenced by build_setop_child_paths(), create_final_distinct_paths(), create_mergejoin_plan(), create_one_window_path(), create_ordered_paths(), create_partial_distinct_paths(), create_window_paths(), gather_grouping_paths(), generate_useful_gather_paths(), initial_cost_mergejoin(), 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 2186 of file pathkeys.c.

2187 {
2188  ListCell *key;
2189  int n = 0;
2190 
2191  /* no special ordering requested for grouping */
2192  if (root->group_pathkeys == NIL)
2193  return 0;
2194 
2195  /* walk the pathkeys and search for matching group key */
2196  foreach(key, pathkeys)
2197  {
2198  PathKey *pathkey = (PathKey *) lfirst(key);
2199 
2200  /* no matching group key, we're done */
2201  if (!list_member_ptr(root->group_pathkeys, pathkey))
2202  break;
2203 
2204  n++;
2205  }
2206 
2207  return n;
2208 }

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

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

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

2157 {
2158  int n_common_pathkeys;
2159 
2160  (void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys,
2161  &n_common_pathkeys);
2162 
2163  return n_common_pathkeys;
2164 }
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:558

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

2217 {
2218  int n_common_pathkeys;
2219 
2220  (void) pathkeys_count_contained_in(root->setop_pathkeys, pathkeys,
2221  &n_common_pathkeys);
2222 
2223  return n_common_pathkeys;
2224 }

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

2120 {
2121  ListCell *l;
2122 
2123  foreach(l, root->query_pathkeys)
2124  {
2125  PathKey *query_pathkey = (PathKey *) lfirst(l);
2126 
2127  if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
2128  pathkey->pk_opfamily == query_pathkey->pk_opfamily)
2129  {
2130  /*
2131  * Found a matching query sort column. Prefer this pathkey's
2132  * direction iff it matches. Note that we ignore pk_nulls_first,
2133  * which means that a sort might be needed anyway ... but we still
2134  * want to prefer only one of the two possible directions, and we
2135  * might as well use this one.
2136  */
2137  return (pathkey->pk_strategy == query_pathkey->pk_strategy);
2138  }
2139  }
2140 
2141  /* If no matching ORDER BY request, prefer the ASC direction */
2142  return (pathkey->pk_strategy == BTLessStrategyNumber);
2143 }

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

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

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

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

2234 {
2235  int nuseful;
2236  int nuseful2;
2237 
2238  nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
2239  nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
2240  if (nuseful2 > nuseful)
2241  nuseful = nuseful2;
2242  nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
2243  if (nuseful2 > nuseful)
2244  nuseful = nuseful2;
2245  nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
2246  if (nuseful2 > nuseful)
2247  nuseful = nuseful2;
2248 
2249  /*
2250  * Note: not safe to modify input list destructively, but we can avoid
2251  * copying the list if we're not actually going to change it
2252  */
2253  if (nuseful == 0)
2254  return NIL;
2255  else if (nuseful == list_length(pathkeys))
2256  return pathkeys;
2257  else
2258  return list_copy_head(pathkeys, nuseful);
2259 }
static int pathkeys_useful_for_setop(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2216
static int pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2156
static int pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2186
static int pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2052

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

1510 {
1511  /* Should be a merge clause ... */
1512  Assert(restrictinfo->mergeopfamilies != NIL);
1513  /* ... with pointers already set */
1514  Assert(restrictinfo->left_ec != NULL);
1515  Assert(restrictinfo->right_ec != NULL);
1516 
1517  /* Chase up to the top as needed */
1518  while (restrictinfo->left_ec->ec_merged)
1519  restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
1520  while (restrictinfo->right_ec->ec_merged)
1521  restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
1522 }

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

Referenced by get_useful_group_keys_orderings().