PostgreSQL Source Code  git master
pathkeys.c File Reference
#include "postgres.h"
#include "miscadmin.h"
#include "access/stratnum.h"
#include "catalog/pg_opfamily.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "nodes/plannodes.h"
#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "partitioning/partbounds.h"
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
Include dependency graph for pathkeys.c:

Go to the source code of this file.

Data Structures

struct  PathkeyMutatorState
 
struct  PathkeySortCost
 

Typedefs

typedef struct PathkeyMutatorState PathkeyMutatorState
 
typedef struct PathkeySortCost PathkeySortCost
 

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)
 
static PathKeymake_pathkey_from_sortinfo (PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opfamily, Oid opcintype, Oid collation, bool reverse_sort, bool nulls_first, Index sortref, Relids rel, bool create_it)
 
static PathKeymake_pathkey_from_sortop (PlannerInfo *root, Expr *expr, Relids nullable_relids, 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)
 
int group_keys_reorder_by_pathkeys (List *pathkeys, List **group_pathkeys, List **group_clauses)
 
static void PathkeyMutatorInit (PathkeyMutatorState *state, List *elems, int start, int end)
 
static void PathkeyMutatorSwap (int *a, int i, int j)
 
static bool PathkeyMutatorNextSet (int *a, int n)
 
static ListPathkeyMutatorNext (PathkeyMutatorState *state)
 
static int pathkey_sort_cost_comparator (const void *_a, const void *_b)
 
static bool get_cheapest_group_keys_order (PlannerInfo *root, double nrows, List **group_pathkeys, List **group_clauses, int n_preordered)
 
Listget_useful_group_keys_orderings (PlannerInfo *root, double nrows, List *path_pathkeys, List *group_pathkeys, List *group_clauses)
 
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, Relids nullable_relids, 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)
 
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)
 
Listtruncate_useless_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 
bool has_useful_pathkeys (PlannerInfo *root, RelOptInfo *rel)
 

Variables

bool enable_group_by_reordering = true
 

Typedef Documentation

◆ PathkeyMutatorState

◆ PathkeySortCost

Function Documentation

◆ build_expression_pathkey()

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

Definition at line 1305 of file pathkeys.c.

1311 {
1312  List *pathkeys;
1313  Oid opfamily,
1314  opcintype;
1315  int16 strategy;
1316  PathKey *cpathkey;
1317 
1318  /* Find the operator in pg_amop --- failure shouldn't happen */
1319  if (!get_ordering_op_properties(opno,
1320  &opfamily, &opcintype, &strategy))
1321  elog(ERROR, "operator %u is not a valid ordering operator",
1322  opno);
1323 
1324  cpathkey = make_pathkey_from_sortinfo(root,
1325  expr,
1326  nullable_relids,
1327  opfamily,
1328  opcintype,
1329  exprCollation((Node *) expr),
1330  (strategy == BTGreaterStrategyNumber),
1331  (strategy == BTGreaterStrategyNumber),
1332  0,
1333  rel,
1334  create_it);
1335 
1336  if (cpathkey)
1337  pathkeys = list_make1(cpathkey);
1338  else
1339  pathkeys = NIL;
1340 
1341  return pathkeys;
1342 }
signed short int16
Definition: c.h:439
#define ERROR
Definition: elog.h:33
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, int16 *strategy)
Definition: lsyscache.c:205
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:788
static PathKey * make_pathkey_from_sortinfo(PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opfamily, Oid opcintype, Oid collation, bool reverse_sort, bool nulls_first, Index sortref, Relids rel, bool create_it)
Definition: pathkeys.c:182
#define NIL
Definition: pg_list.h:66
#define list_make1(x1)
Definition: pg_list.h:210
unsigned int Oid
Definition: postgres_ext.h:31
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Definition: pg_list.h:52
Definition: nodes.h:575

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

Referenced by set_function_pathlist().

◆ build_index_pathkeys()

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

Definition at line 1046 of file pathkeys.c.

1049 {
1050  List *retval = NIL;
1051  ListCell *lc;
1052  int i;
1053 
1054  if (index->sortopfamily == NULL)
1055  return NIL; /* non-orderable index */
1056 
1057  i = 0;
1058  foreach(lc, index->indextlist)
1059  {
1060  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
1061  Expr *indexkey;
1062  bool reverse_sort;
1063  bool nulls_first;
1064  PathKey *cpathkey;
1065 
1066  /*
1067  * INCLUDE columns are stored in index unordered, so they don't
1068  * support ordered index scan.
1069  */
1070  if (i >= index->nkeycolumns)
1071  break;
1072 
1073  /* We assume we don't need to make a copy of the tlist item */
1074  indexkey = indextle->expr;
1075 
1076  if (ScanDirectionIsBackward(scandir))
1077  {
1078  reverse_sort = !index->reverse_sort[i];
1079  nulls_first = !index->nulls_first[i];
1080  }
1081  else
1082  {
1083  reverse_sort = index->reverse_sort[i];
1084  nulls_first = index->nulls_first[i];
1085  }
1086 
1087  /*
1088  * OK, try to make a canonical pathkey for this sort key. Note we're
1089  * underneath any outer joins, so nullable_relids should be NULL.
1090  */
1091  cpathkey = make_pathkey_from_sortinfo(root,
1092  indexkey,
1093  NULL,
1094  index->sortopfamily[i],
1095  index->opcintype[i],
1096  index->indexcollations[i],
1097  reverse_sort,
1098  nulls_first,
1099  0,
1100  index->rel->relids,
1101  false);
1102 
1103  if (cpathkey)
1104  {
1105  /*
1106  * We found the sort key in an EquivalenceClass, so it's relevant
1107  * for this query. Add it to list, unless it's redundant.
1108  */
1109  if (!pathkey_is_redundant(cpathkey, retval))
1110  retval = lappend(retval, cpathkey);
1111  }
1112  else
1113  {
1114  /*
1115  * Boolean index keys might be redundant even if they do not
1116  * appear in an EquivalenceClass, because of our special treatment
1117  * of boolean equality conditions --- see the comment for
1118  * indexcol_is_bool_constant_for_query(). If that applies, we can
1119  * continue to examine lower-order index columns. Otherwise, the
1120  * sort key is not an interesting sort order for this query, so we
1121  * should stop considering index columns; any lower-order sort
1122  * keys won't be useful either.
1123  */
1125  break;
1126  }
1127 
1128  i++;
1129  }
1130 
1131  return retval;
1132 }
bool indexcol_is_bool_constant_for_query(PlannerInfo *root, IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3669
int i
Definition: isn.c:73
List * lappend(List *list, void *datum)
Definition: list.c:338
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:140
#define lfirst(lc)
Definition: pg_list.h:170
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
Expr * expr
Definition: primnodes.h:1828
Definition: type.h:90

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

Referenced by build_index_paths().

◆ build_join_pathkeys()

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

Definition at line 1605 of file pathkeys.c.

1609 {
1610  if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
1611  return NIL;
1612 
1613  /*
1614  * This used to be quite a complex bit of code, but now that all pathkey
1615  * sublists start out life canonicalized, we don't have to do a darn thing
1616  * here!
1617  *
1618  * We do, however, need to truncate the pathkeys list, since it may
1619  * contain pathkeys that were useful for forming this joinrel but are
1620  * uninteresting to higher levels.
1621  */
1622  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1623 }
@ JOIN_FULL
Definition: nodes.h:752
@ JOIN_RIGHT
Definition: nodes.h:753
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2441

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

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

◆ build_partition_pathkeys()

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

Definition at line 1222 of file pathkeys.c.

1224 {
1225  List *retval = NIL;
1226  PartitionScheme partscheme = partrel->part_scheme;
1227  int i;
1228 
1229  Assert(partscheme != NULL);
1230  Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
1231  /* For now, we can only cope with baserels */
1232  Assert(IS_SIMPLE_REL(partrel));
1233 
1234  for (i = 0; i < partscheme->partnatts; i++)
1235  {
1236  PathKey *cpathkey;
1237  Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
1238 
1239  /*
1240  * Try to make a canonical pathkey for this partkey.
1241  *
1242  * We're considering a baserel scan, so nullable_relids should be
1243  * NULL. Also, we assume the PartitionDesc lists any NULL partition
1244  * last, so we treat the scan like a NULLS LAST index: we have
1245  * nulls_first for backwards scan only.
1246  */
1247  cpathkey = make_pathkey_from_sortinfo(root,
1248  keyCol,
1249  NULL,
1250  partscheme->partopfamily[i],
1251  partscheme->partopcintype[i],
1252  partscheme->partcollation[i],
1253  ScanDirectionIsBackward(scandir),
1254  ScanDirectionIsBackward(scandir),
1255  0,
1256  partrel->relids,
1257  false);
1258 
1259 
1260  if (cpathkey)
1261  {
1262  /*
1263  * We found the sort key in an EquivalenceClass, so it's relevant
1264  * for this query. Add it to list, unless it's redundant.
1265  */
1266  if (!pathkey_is_redundant(cpathkey, retval))
1267  retval = lappend(retval, cpathkey);
1268  }
1269  else
1270  {
1271  /*
1272  * Boolean partition keys might be redundant even if they do not
1273  * appear in an EquivalenceClass, because of our special treatment
1274  * of boolean equality conditions --- see the comment for
1275  * partkey_is_bool_constant_for_query(). If that applies, we can
1276  * continue to examine lower-order partition keys. Otherwise, the
1277  * sort key is not an interesting sort order for this query, so we
1278  * should stop considering partition columns; any lower-order sort
1279  * keys won't be useful either.
1280  */
1281  if (!partkey_is_bool_constant_for_query(partrel, i))
1282  {
1283  *partialkeys = true;
1284  return retval;
1285  }
1286  }
1287  }
1288 
1289  *partialkeys = false;
1290  return retval;
1291 }
Assert(fmt[strlen(fmt) - 1] !='\n')
bool partitions_are_ordered(PartitionBoundInfo boundinfo, Bitmapset *live_parts)
Definition: partbounds.c:2863
static bool partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:1152
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:663
#define linitial(l)
Definition: pg_list.h:176
List ** partexprs
Definition: pathnodes.h:851
Relids relids
Definition: pathnodes.h:693
struct PartitionBoundInfoData * boundinfo
Definition: pathnodes.h:832
PartitionScheme part_scheme
Definition: pathnodes.h:824
Bitmapset * live_parts
Definition: pathnodes.h:847

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

Referenced by generate_orderedappend_paths().

◆ compare_pathkeys()

PathKeysComparison compare_pathkeys ( List keys1,
List keys2 
)

Definition at line 290 of file pathkeys.c.

291 {
292  ListCell *key1,
293  *key2;
294 
295  /*
296  * Fall out quickly if we are passed two identical lists. This mostly
297  * catches the case where both are NIL, but that's common enough to
298  * warrant the test.
299  */
300  if (keys1 == keys2)
301  return PATHKEYS_EQUAL;
302 
303  forboth(key1, keys1, key2, keys2)
304  {
305  PathKey *pathkey1 = (PathKey *) lfirst(key1);
306  PathKey *pathkey2 = (PathKey *) lfirst(key2);
307 
308  if (pathkey1 != pathkey2)
309  return PATHKEYS_DIFFERENT; /* no need to keep looking */
310  }
311 
312  /*
313  * If we reached the end of only one list, the other is longer and
314  * therefore not a subset.
315  */
316  if (key1 != NULL)
317  return PATHKEYS_BETTER1; /* key1 is longer */
318  if (key2 != NULL)
319  return PATHKEYS_BETTER2; /* key2 is longer */
320  return PATHKEYS_EQUAL;
321 }
@ PATHKEYS_BETTER2
Definition: paths.h:199
@ PATHKEYS_BETTER1
Definition: paths.h:198
@ PATHKEYS_DIFFERENT
Definition: paths.h:200
@ PATHKEYS_EQUAL
Definition: paths.h:197
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:465

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

1364 {
1365  List *retval = NIL;
1366  int retvallen = 0;
1367  int outer_query_keys = list_length(root->query_pathkeys);
1368  ListCell *i;
1369 
1370  foreach(i, subquery_pathkeys)
1371  {
1372  PathKey *sub_pathkey = (PathKey *) lfirst(i);
1373  EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
1374  PathKey *best_pathkey = NULL;
1375 
1376  if (sub_eclass->ec_has_volatile)
1377  {
1378  /*
1379  * If the sub_pathkey's EquivalenceClass is volatile, then it must
1380  * have come from an ORDER BY clause, and we have to match it to
1381  * that same targetlist entry.
1382  */
1383  TargetEntry *tle;
1384  Var *outer_var;
1385 
1386  if (sub_eclass->ec_sortref == 0) /* can't happen */
1387  elog(ERROR, "volatile EquivalenceClass has no sortref");
1388  tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
1389  Assert(tle);
1390  /* Is TLE actually available to the outer query? */
1391  outer_var = find_var_for_subquery_tle(rel, tle);
1392  if (outer_var)
1393  {
1394  /* We can represent this sub_pathkey */
1395  EquivalenceMember *sub_member;
1396  EquivalenceClass *outer_ec;
1397 
1398  Assert(list_length(sub_eclass->ec_members) == 1);
1399  sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
1400 
1401  /*
1402  * Note: it might look funny to be setting sortref = 0 for a
1403  * reference to a volatile sub_eclass. However, the
1404  * expression is *not* volatile in the outer query: it's just
1405  * a Var referencing whatever the subquery emitted. (IOW, the
1406  * outer query isn't going to re-execute the volatile
1407  * expression itself.) So this is okay. Likewise, it's
1408  * correct to pass nullable_relids = NULL, because we're
1409  * underneath any outer joins appearing in the outer query.
1410  */
1411  outer_ec =
1413  (Expr *) outer_var,
1414  NULL,
1415  sub_eclass->ec_opfamilies,
1416  sub_member->em_datatype,
1417  sub_eclass->ec_collation,
1418  0,
1419  rel->relids,
1420  false);
1421 
1422  /*
1423  * If we don't find a matching EC, sub-pathkey isn't
1424  * interesting to the outer query
1425  */
1426  if (outer_ec)
1427  best_pathkey =
1429  outer_ec,
1430  sub_pathkey->pk_opfamily,
1431  sub_pathkey->pk_strategy,
1432  sub_pathkey->pk_nulls_first);
1433  }
1434  }
1435  else
1436  {
1437  /*
1438  * Otherwise, the sub_pathkey's EquivalenceClass could contain
1439  * multiple elements (representing knowledge that multiple items
1440  * are effectively equal). Each element might match none, one, or
1441  * more of the output columns that are visible to the outer query.
1442  * This means we may have multiple possible representations of the
1443  * sub_pathkey in the context of the outer query. Ideally we
1444  * would generate them all and put them all into an EC of the
1445  * outer query, thereby propagating equality knowledge up to the
1446  * outer query. Right now we cannot do so, because the outer
1447  * query's EquivalenceClasses are already frozen when this is
1448  * called. Instead we prefer the one that has the highest "score"
1449  * (number of EC peers, plus one if it matches the outer
1450  * query_pathkeys). This is the most likely to be useful in the
1451  * outer query.
1452  */
1453  int best_score = -1;
1454  ListCell *j;
1455 
1456  foreach(j, sub_eclass->ec_members)
1457  {
1458  EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
1459  Expr *sub_expr = sub_member->em_expr;
1460  Oid sub_expr_type = sub_member->em_datatype;
1461  Oid sub_expr_coll = sub_eclass->ec_collation;
1462  ListCell *k;
1463 
1464  if (sub_member->em_is_child)
1465  continue; /* ignore children here */
1466 
1467  foreach(k, subquery_tlist)
1468  {
1469  TargetEntry *tle = (TargetEntry *) lfirst(k);
1470  Var *outer_var;
1471  Expr *tle_expr;
1472  EquivalenceClass *outer_ec;
1473  PathKey *outer_pk;
1474  int score;
1475 
1476  /* Is TLE actually available to the outer query? */
1477  outer_var = find_var_for_subquery_tle(rel, tle);
1478  if (!outer_var)
1479  continue;
1480 
1481  /*
1482  * The targetlist entry is considered to match if it
1483  * matches after sort-key canonicalization. That is
1484  * needed since the sub_expr has been through the same
1485  * process.
1486  */
1487  tle_expr = canonicalize_ec_expression(tle->expr,
1488  sub_expr_type,
1489  sub_expr_coll);
1490  if (!equal(tle_expr, sub_expr))
1491  continue;
1492 
1493  /* See if we have a matching EC for the TLE */
1494  outer_ec = get_eclass_for_sort_expr(root,
1495  (Expr *) outer_var,
1496  NULL,
1497  sub_eclass->ec_opfamilies,
1498  sub_expr_type,
1499  sub_expr_coll,
1500  0,
1501  rel->relids,
1502  false);
1503 
1504  /*
1505  * If we don't find a matching EC, this sub-pathkey isn't
1506  * interesting to the outer query
1507  */
1508  if (!outer_ec)
1509  continue;
1510 
1511  outer_pk = make_canonical_pathkey(root,
1512  outer_ec,
1513  sub_pathkey->pk_opfamily,
1514  sub_pathkey->pk_strategy,
1515  sub_pathkey->pk_nulls_first);
1516  /* score = # of equivalence peers */
1517  score = list_length(outer_ec->ec_members) - 1;
1518  /* +1 if it matches the proper query_pathkeys item */
1519  if (retvallen < outer_query_keys &&
1520  list_nth(root->query_pathkeys, retvallen) == outer_pk)
1521  score++;
1522  if (score > best_score)
1523  {
1524  best_pathkey = outer_pk;
1525  best_score = score;
1526  }
1527  }
1528  }
1529  }
1530 
1531  /*
1532  * If we couldn't find a representation of this sub_pathkey, we're
1533  * done (we can't use the ones to its right, either).
1534  */
1535  if (!best_pathkey)
1536  break;
1537 
1538  /*
1539  * Eliminate redundant ordering info; could happen if outer query
1540  * equivalences subquery keys...
1541  */
1542  if (!pathkey_is_redundant(best_pathkey, retval))
1543  {
1544  retval = lappend(retval, best_pathkey);
1545  retvallen++;
1546  }
1547  }
1548 
1549  return retval;
1550 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3580
EquivalenceClass * get_eclass_for_sort_expr(PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
Definition: equivclass.c:621
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:500
int j
Definition: isn.c:74
static Var * find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
Definition: pathkeys.c:1562
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:59
static int list_length(const List *l)
Definition: pg_list.h:150
static void * list_nth(const List *list, int n)
Definition: pg_list.h:297
List * ec_opfamilies
Definition: pathnodes.h:1130
bool pk_nulls_first
Definition: pathnodes.h:1212
int pk_strategy
Definition: pathnodes.h:1211
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1209
Oid pk_opfamily
Definition: pathnodes.h:1210
List * query_pathkeys
Definition: pathnodes.h:295
Definition: primnodes.h:209
TargetEntry * get_sortgroupref_tle(Index sortref, List *targetList)
Definition: tlist.c:334

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_eclass, PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, PlannerInfo::query_pathkeys, and RelOptInfo::relids.

Referenced by set_subquery_pathlist().

◆ find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1785 of file pathkeys.c.

1788 {
1789  List *mergeclauses = NIL;
1790  ListCell *i;
1791 
1792  /* make sure we have eclasses cached in the clauses */
1793  foreach(i, restrictinfos)
1794  {
1795  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1796 
1797  update_mergeclause_eclasses(root, rinfo);
1798  }
1799 
1800  foreach(i, pathkeys)
1801  {
1802  PathKey *pathkey = (PathKey *) lfirst(i);
1803  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1804  List *matched_restrictinfos = NIL;
1805  ListCell *j;
1806 
1807  /*----------
1808  * A mergejoin clause matches a pathkey if it has the same EC.
1809  * If there are multiple matching clauses, take them all. In plain
1810  * inner-join scenarios we expect only one match, because
1811  * equivalence-class processing will have removed any redundant
1812  * mergeclauses. However, in outer-join scenarios there might be
1813  * multiple matches. An example is
1814  *
1815  * select * from a full join b
1816  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1817  *
1818  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1819  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1820  * we *must* do so or we will be unable to form a valid plan.
1821  *
1822  * We expect that the given pathkeys list is canonical, which means
1823  * no two members have the same EC, so it's not possible for this
1824  * code to enter the same mergeclause into the result list twice.
1825  *
1826  * It's possible that multiple matching clauses might have different
1827  * ECs on the other side, in which case the order we put them into our
1828  * result makes a difference in the pathkeys required for the inner
1829  * input rel. However this routine hasn't got any info about which
1830  * order would be best, so we don't worry about that.
1831  *
1832  * It's also possible that the selected mergejoin clauses produce
1833  * a noncanonical ordering of pathkeys for the inner side, ie, we
1834  * might select clauses that reference b.v1, b.v2, b.v1 in that
1835  * order. This is not harmful in itself, though it suggests that
1836  * the clauses are partially redundant. Since the alternative is
1837  * to omit mergejoin clauses and thereby possibly fail to generate a
1838  * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1839  * has to delete duplicates when it constructs the inner pathkeys
1840  * list, and we also have to deal with such cases specially in
1841  * create_mergejoin_plan().
1842  *----------
1843  */
1844  foreach(j, restrictinfos)
1845  {
1846  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1847  EquivalenceClass *clause_ec;
1848 
1849  clause_ec = rinfo->outer_is_left ?
1850  rinfo->left_ec : rinfo->right_ec;
1851  if (clause_ec == pathkey_ec)
1852  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1853  }
1854 
1855  /*
1856  * If we didn't find a mergeclause, we're done --- any additional
1857  * sort-key positions in the pathkeys are useless. (But we can still
1858  * mergejoin if we found at least one mergeclause.)
1859  */
1860  if (matched_restrictinfos == NIL)
1861  break;
1862 
1863  /*
1864  * If we did find usable mergeclause(s) for this sort-key position,
1865  * add them to result list.
1866  */
1867  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1868  }
1869 
1870  return mergeclauses;
1871 }
List * list_concat(List *list1, const List *list2)
Definition: list.c:560
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1751
EquivalenceClass * left_ec
Definition: pathnodes.h:2314
bool outer_is_left
Definition: pathnodes.h:2328
EquivalenceClass * right_ec
Definition: pathnodes.h:2316

References i, j, lappend(), RestrictInfo::left_ec, lfirst, list_concat(), NIL, RestrictInfo::outer_is_left, PathKey::pk_eclass, RestrictInfo::right_ec, 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 1562 of file pathkeys.c.

1563 {
1564  ListCell *lc;
1565 
1566  /* If the TLE is resjunk, it's certainly not visible to the outer query */
1567  if (tle->resjunk)
1568  return NULL;
1569 
1570  /* Search the rel's targetlist to see what it will return */
1571  foreach(lc, rel->reltarget->exprs)
1572  {
1573  Var *var = (Var *) lfirst(lc);
1574 
1575  /* Ignore placeholders */
1576  if (!IsA(var, Var))
1577  continue;
1578  Assert(var->varno == rel->relid);
1579 
1580  /* If we find a Var referencing this TLE, we're good */
1581  if (var->varattno == tle->resno)
1582  return copyObject(var); /* Make a copy for safety */
1583  }
1584  return NULL;
1585 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:625
#define copyObject(obj)
Definition: nodes.h:690
List * exprs
Definition: pathnodes.h:1265
struct PathTarget * reltarget
Definition: pathnodes.h:715
Index relid
Definition: pathnodes.h:740
AttrNumber resno
Definition: primnodes.h:1829
bool resjunk
Definition: primnodes.h:1835
AttrNumber varattno
Definition: primnodes.h:221
int varno
Definition: primnodes.h:216

References Assert(), copyObject, PathTarget::exprs, IsA, lfirst, RelOptInfo::relid, RelOptInfo::reltarget, TargetEntry::resjunk, 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 972 of file pathkeys.c.

976 {
977  Path *matched_path = NULL;
978  ListCell *l;
979 
980  foreach(l, paths)
981  {
982  Path *path = (Path *) lfirst(l);
983 
984  /*
985  * Since cost comparison is a lot cheaper than pathkey comparison, do
986  * that first. (XXX is that still true?)
987  */
988  if (matched_path != NULL &&
989  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
990  continue;
991 
992  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
993  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
994  matched_path = path;
995  }
996  return matched_path;
997 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:329
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:117
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1371
List * pathkeys
Definition: pathnodes.h:1367

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

static bool get_cheapest_group_keys_order ( PlannerInfo root,
double  nrows,
List **  group_pathkeys,
List **  group_clauses,
int  n_preordered 
)
static

Definition at line 584 of file pathkeys.c.

587 {
588  List *new_group_pathkeys = NIL,
589  *new_group_clauses = NIL,
590  *var_group_pathkeys;
591 
592  ListCell *cell;
593  PathkeyMutatorState mstate;
594  double cheapest_sort_cost = -1.0;
595 
596  int nFreeKeys;
597  int nToPermute;
598 
599  /* If there are less than 2 unsorted pathkeys, we're done. */
600  if (list_length(*group_pathkeys) - n_preordered < 2)
601  return false;
602 
603  /*
604  * We could exhaustively cost all possible orderings of the pathkeys, but
605  * for a large number of pathkeys it might be prohibitively expensive. So
606  * we try to apply simple cheap heuristics first - we sort the pathkeys by
607  * sort cost (as if the pathkey was sorted independently) and then check
608  * only the four cheapest pathkeys. The remaining pathkeys are kept
609  * ordered by cost.
610  *
611  * XXX This is a very simple heuristics, but likely to work fine for most
612  * cases (because the number of GROUP BY clauses tends to be lower than
613  * 4). But it ignores how the number of distinct values in each pathkey
614  * affects the following steps. It might be better to use "more expensive"
615  * pathkey first if it has many distinct values, because it then limits
616  * the number of comparisons for the remaining pathkeys. But evaluating
617  * that is likely quite the expensive.
618  */
619  nFreeKeys = list_length(*group_pathkeys) - n_preordered;
620  nToPermute = 4;
621  if (nFreeKeys > nToPermute)
622  {
623  int i;
624  PathkeySortCost *costs = palloc(sizeof(PathkeySortCost) * nFreeKeys);
625 
626  /* skip the pre-ordered pathkeys */
627  cell = list_nth_cell(*group_pathkeys, n_preordered);
628 
629  /* estimate cost for sorting individual pathkeys */
630  for (i = 0; cell != NULL; i++, (cell = lnext(*group_pathkeys, cell)))
631  {
632  List *to_cost = list_make1(lfirst(cell));
633 
634  Assert(i < nFreeKeys);
635 
636  costs[i].pathkey = lfirst(cell);
637  costs[i].cost = cost_sort_estimate(root, to_cost, 0, nrows);
638 
639  pfree(to_cost);
640  }
641 
642  /* sort the pathkeys by sort cost in ascending order */
643  qsort(costs, nFreeKeys, sizeof(*costs), pathkey_sort_cost_comparator);
644 
645  /*
646  * Rebuild the list of pathkeys - first the preordered ones, then the
647  * rest ordered by cost.
648  */
649  new_group_pathkeys = list_truncate(list_copy(*group_pathkeys), n_preordered);
650 
651  for (i = 0; i < nFreeKeys; i++)
652  new_group_pathkeys = lappend(new_group_pathkeys, costs[i].pathkey);
653 
654  pfree(costs);
655  }
656  else
657  {
658  /* Copy the list, so that we can free the new list by list_free. */
659  new_group_pathkeys = list_copy(*group_pathkeys);
660  nToPermute = nFreeKeys;
661  }
662 
663  Assert(list_length(new_group_pathkeys) == list_length(*group_pathkeys));
664 
665  /*
666  * Generate pathkey lists with permutations of the first nToPermute
667  * pathkeys.
668  *
669  * XXX We simply calculate sort cost for each individual pathkey list, but
670  * there's room for two dynamic programming optimizations here. Firstly,
671  * we may pass the current "best" cost to cost_sort_estimate so that it
672  * can "abort" if the estimated pathkeys list exceeds it. Secondly, it
673  * could pass the return information about the position when it exceeded
674  * the cost, and we could skip all permutations with the same prefix.
675  *
676  * Imagine we've already found ordering with cost C1, and we're evaluating
677  * another ordering - cost_sort_estimate() calculates cost by adding the
678  * pathkeys one by one (more or less), and the cost only grows. If at any
679  * point it exceeds C1, it can't possibly be "better" so we can discard
680  * it. But we also know that we can discard all ordering with the same
681  * prefix, because if we're estimating (a,b,c,d) and we exceed C1 at (a,b)
682  * then the same thing will happen for any ordering with this prefix.
683  */
684  PathkeyMutatorInit(&mstate, new_group_pathkeys, n_preordered, n_preordered + nToPermute);
685 
686  while ((var_group_pathkeys = PathkeyMutatorNext(&mstate)) != NIL)
687  {
688  Cost cost;
689 
690  cost = cost_sort_estimate(root, var_group_pathkeys, n_preordered, nrows);
691 
692  if (cost < cheapest_sort_cost || cheapest_sort_cost < 0)
693  {
694  list_free(new_group_pathkeys);
695  new_group_pathkeys = list_copy(var_group_pathkeys);
696  cheapest_sort_cost = cost;
697  }
698  }
699 
700  /* Reorder the group clauses according to the reordered pathkeys. */
701  foreach(cell, new_group_pathkeys)
702  {
703  PathKey *pathkey = (PathKey *) lfirst(cell);
704 
705  new_group_clauses = lappend(new_group_clauses,
707  *group_clauses));
708  }
709 
710  /* Just append the rest GROUP BY clauses */
711  new_group_clauses = list_concat_unique_ptr(new_group_clauses,
712  *group_clauses);
713 
714  *group_pathkeys = new_group_pathkeys;
715  *group_clauses = new_group_clauses;
716 
717  return true;
718 }
Cost cost_sort_estimate(PlannerInfo *root, List *pathkeys, int nPresortedKeys, double tuples)
Definition: costsize.c:2113
List * list_truncate(List *list, int new_size)
Definition: list.c:630
List * list_copy(const List *oldlist)
Definition: list.c:1572
List * list_concat_unique_ptr(List *list1, const List *list2)
Definition: list.c:1426
void list_free(List *list)
Definition: list.c:1545
void pfree(void *pointer)
Definition: mcxt.c:1175
void * palloc(Size size)
Definition: mcxt.c:1068
double Cost
Definition: nodes.h:708
static int pathkey_sort_cost_comparator(const void *_a, const void *_b)
Definition: pathkeys.c:552
static List * PathkeyMutatorNext(PathkeyMutatorState *state)
Definition: pathkeys.c:512
static void PathkeyMutatorInit(PathkeyMutatorState *state, List *elems, int start, int end)
Definition: pathkeys.c:430
static ListCell * list_nth_cell(const List *list, int n)
Definition: pg_list.h:275
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:341
#define qsort(a, b, c, d)
Definition: port.h:495
PathKey * pathkey
Definition: pathkeys.c:548
SortGroupClause * get_sortgroupref_clause(Index sortref, List *clauses)
Definition: tlist.c:411

References Assert(), PathkeySortCost::cost, cost_sort_estimate(), EquivalenceClass::ec_sortref, get_sortgroupref_clause(), i, lappend(), lfirst, list_concat_unique_ptr(), list_copy(), list_free(), list_length(), list_make1, list_nth_cell(), list_truncate(), lnext(), NIL, palloc(), PathkeySortCost::pathkey, pathkey_sort_cost_comparator(), PathkeyMutatorInit(), PathkeyMutatorNext(), pfree(), PathKey::pk_eclass, and qsort.

Referenced by get_useful_group_keys_orderings().

◆ get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner ( List paths)

Definition at line 1005 of file pathkeys.c.

1006 {
1007  ListCell *l;
1008 
1009  foreach(l, paths)
1010  {
1011  Path *innerpath = (Path *) lfirst(l);
1012 
1013  if (innerpath->parallel_safe &&
1014  bms_is_empty(PATH_REQ_OUTER(innerpath)))
1015  return innerpath;
1016  }
1017 
1018  return NULL;
1019 }
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:703
bool parallel_safe
Definition: pathnodes.h:1357

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

931 {
932  Path *matched_path = NULL;
933  ListCell *l;
934 
935  foreach(l, paths)
936  {
937  Path *path = (Path *) lfirst(l);
938 
939  /*
940  * Since cost comparison is a lot cheaper than pathkey comparison, do
941  * that first. (XXX is that still true?)
942  */
943  if (matched_path != NULL &&
944  compare_path_costs(matched_path, path, cost_criterion) <= 0)
945  continue;
946 
947  if (require_parallel_safe && !path->parallel_safe)
948  continue;
949 
950  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
951  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
952  matched_path = path;
953  }
954  return matched_path;
955 }
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:71

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

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

◆ get_useful_group_keys_orderings()

List* get_useful_group_keys_orderings ( PlannerInfo root,
double  nrows,
List path_pathkeys,
List group_pathkeys,
List group_clauses 
)

Definition at line 745 of file pathkeys.c.

748 {
749  Query *parse = root->parse;
750  List *infos = NIL;
751  PathKeyInfo *info;
752  int n_preordered = 0;
753 
754  List *pathkeys = group_pathkeys;
755  List *clauses = group_clauses;
756 
757  /* always return at least the original pathkeys/clauses */
758  info = makeNode(PathKeyInfo);
759  info->pathkeys = pathkeys;
760  info->clauses = clauses;
761 
762  infos = lappend(infos, info);
763 
764  /*
765  * Should we try generating alternative orderings of the group keys? If
766  * not, we produce only the order specified in the query, i.e. the
767  * optimization is effectively disabled.
768  */
770  return infos;
771 
772  /* for grouping sets we can't do any reordering */
773  if (parse->groupingSets)
774  return infos;
775 
776  /*
777  * Try reordering pathkeys to minimize the sort cost, ignoring both the
778  * target ordering (ORDER BY) and ordering of the input path.
779  */
780  if (get_cheapest_group_keys_order(root, nrows, &pathkeys, &clauses,
781  n_preordered))
782  {
783  info = makeNode(PathKeyInfo);
784  info->pathkeys = pathkeys;
785  info->clauses = clauses;
786 
787  infos = lappend(infos, info);
788  }
789 
790  /*
791  * If the path is sorted in some way, try reordering the group keys to
792  * match as much of the ordering as possible - we get this sort for free
793  * (mostly).
794  *
795  * We must not do this when there are no grouping sets, because those use
796  * more complex logic to decide the ordering.
797  *
798  * XXX Isn't this somewhat redundant with presorted_keys? Actually, it's
799  * more a complement, because it allows benefiting from incremental sort
800  * as much as possible.
801  *
802  * XXX This does nothing if (n_preordered == 0). We shouldn't create the
803  * info in this case.
804  */
805  if (path_pathkeys)
806  {
807  n_preordered = group_keys_reorder_by_pathkeys(path_pathkeys,
808  &pathkeys,
809  &clauses);
810 
811  /* reorder the tail to minimize sort cost */
812  get_cheapest_group_keys_order(root, nrows, &pathkeys, &clauses,
813  n_preordered);
814 
815  /*
816  * reorder the tail to minimize sort cost
817  *
818  * XXX Ignore the return value - there may be nothing to reorder, in
819  * which case get_cheapest_group_keys_order returns false. But we
820  * still want to keep the keys reordered to path_pathkeys.
821  */
822  info = makeNode(PathKeyInfo);
823  info->pathkeys = pathkeys;
824  info->clauses = clauses;
825 
826  infos = lappend(infos, info);
827  }
828 
829  /*
830  * Try reordering pathkeys to minimize the sort cost (this time consider
831  * the ORDER BY clause, but only if set debug_group_by_match_order_by).
832  */
833  if (root->sort_pathkeys)
834  {
835  n_preordered = group_keys_reorder_by_pathkeys(root->sort_pathkeys,
836  &pathkeys,
837  &clauses);
838 
839  /*
840  * reorder the tail to minimize sort cost
841  *
842  * XXX Ignore the return value - there may be nothing to reorder, in
843  * which case get_cheapest_group_keys_order returns false. But we
844  * still want to keep the keys reordered to sort_pathkeys.
845  */
846  get_cheapest_group_keys_order(root, nrows, &pathkeys, &clauses,
847  n_preordered);
848 
849  /* keep the group keys reordered to match ordering of input path */
850  info = makeNode(PathKeyInfo);
851  info->pathkeys = pathkeys;
852  info->clauses = clauses;
853 
854  infos = lappend(infos, info);
855  }
856 
857  return infos;
858 }
#define makeNode(_type_)
Definition: nodes.h:622
static bool get_cheapest_group_keys_order(PlannerInfo *root, double nrows, List **group_pathkeys, List **group_clauses, int n_preordered)
Definition: pathkeys.c:584
bool enable_group_by_reordering
Definition: pathkeys.c:35
int group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys, List **group_clauses)
Definition: pathkeys.c:352
static struct subre * parse(struct vars *, int, int, struct state *, struct state *)
Definition: regcomp.c:673
List * pathkeys
Definition: pathnodes.h:1221
List * clauses
Definition: pathnodes.h:1222
List * sort_pathkeys
Definition: pathnodes.h:300
Query * parse
Definition: pathnodes.h:162

References PathKeyInfo::clauses, enable_group_by_reordering, get_cheapest_group_keys_order(), group_keys_reorder_by_pathkeys(), lappend(), makeNode, NIL, parse(), PlannerInfo::parse, PathKeyInfo::pathkeys, and PlannerInfo::sort_pathkeys.

Referenced by add_paths_to_grouping_rel(), and create_partial_grouping_paths().

◆ group_keys_reorder_by_pathkeys()

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

Definition at line 352 of file pathkeys.c.

354 {
355  List *new_group_pathkeys = NIL,
356  *new_group_clauses = NIL;
357  ListCell *lc;
358  int n;
359 
360  if (pathkeys == NIL || *group_pathkeys == NIL)
361  return 0;
362 
363  /*
364  * Walk the pathkeys (determining ordering of the input path) and see if
365  * there's a matching GROUP BY key. If we find one, we append it to the
366  * list, and do the same for the clauses.
367  *
368  * Once we find the first pathkey without a matching GROUP BY key, the
369  * rest of the pathkeys are useless and can't be used to evaluate the
370  * grouping, so we abort the loop and ignore the remaining pathkeys.
371  *
372  * XXX Pathkeys are built in a way to allow simply comparing pointers.
373  */
374  foreach(lc, pathkeys)
375  {
376  PathKey *pathkey = (PathKey *) lfirst(lc);
377  SortGroupClause *sgc;
378 
379  /* abort on first mismatch */
380  if (!list_member_ptr(*group_pathkeys, pathkey))
381  break;
382 
383  new_group_pathkeys = lappend(new_group_pathkeys, pathkey);
384 
386  *group_clauses);
387 
388  new_group_clauses = lappend(new_group_clauses, sgc);
389  }
390 
391  /* remember the number of pathkeys with a matching GROUP BY key */
392  n = list_length(new_group_pathkeys);
393 
394  /* append the remaining group pathkeys (will be treated as not sorted) */
395  *group_pathkeys = list_concat_unique_ptr(new_group_pathkeys,
396  *group_pathkeys);
397  *group_clauses = list_concat_unique_ptr(new_group_clauses,
398  *group_clauses);
399 
400  return n;
401 }
bool list_member_ptr(const List *list, const void *datum)
Definition: list.c:681

References EquivalenceClass::ec_sortref, get_sortgroupref_clause(), lappend(), lfirst, list_concat_unique_ptr(), list_length(), list_member_ptr(), NIL, and PathKey::pk_eclass.

Referenced by get_useful_group_keys_orderings().

◆ has_useful_pathkeys()

bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 2484 of file pathkeys.c.

2485 {
2486  if (rel->joininfo != NIL || rel->has_eclass_joins)
2487  return true; /* might be able to use pathkeys for merging */
2488  if (root->group_pathkeys != NIL)
2489  return true; /* might be able to use pathkeys for grouping */
2490  if (root->query_pathkeys != NIL)
2491  return true; /* might be able to use them for ordering */
2492  return false; /* definitely useless */
2493 }
List * group_pathkeys
Definition: pathnodes.h:297
List * joininfo
Definition: pathnodes.h:808
bool has_eclass_joins
Definition: pathnodes.h:810

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

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

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1702 of file pathkeys.c.

1703 {
1704  Expr *clause = restrictinfo->clause;
1705  Oid lefttype,
1706  righttype;
1707 
1708  /* Should be a mergeclause ... */
1709  Assert(restrictinfo->mergeopfamilies != NIL);
1710  /* ... with links not yet set */
1711  Assert(restrictinfo->left_ec == NULL);
1712  Assert(restrictinfo->right_ec == NULL);
1713 
1714  /* Need the declared input types of the operator */
1715  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1716 
1717  /* Find or create a matching EquivalenceClass for each side */
1718  restrictinfo->left_ec =
1720  (Expr *) get_leftop(clause),
1721  restrictinfo->nullable_relids,
1722  restrictinfo->mergeopfamilies,
1723  lefttype,
1724  ((OpExpr *) clause)->inputcollid,
1725  0,
1726  NULL,
1727  true);
1728  restrictinfo->right_ec =
1730  (Expr *) get_rightop(clause),
1731  restrictinfo->nullable_relids,
1732  restrictinfo->mergeopfamilies,
1733  righttype,
1734  ((OpExpr *) clause)->inputcollid,
1735  0,
1736  NULL,
1737  true);
1738 }
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1339
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:83
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:71
Relids nullable_relids
Definition: pathnodes.h:2267
Expr * clause
Definition: pathnodes.h:2234
List * mergeopfamilies
Definition: pathnodes.h:2307

References Assert(), RestrictInfo::clause, get_eclass_for_sort_expr(), get_leftop(), get_rightop(), RestrictInfo::left_ec, RestrictInfo::mergeopfamilies, NIL, RestrictInfo::nullable_relids, op_input_types(), and RestrictInfo::right_ec.

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

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

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

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

2073 {
2074  List *pathkeys = NIL;
2075  EquivalenceClass *lastoeclass;
2076  PathKey *opathkey;
2077  ListCell *lc;
2078  ListCell *lop;
2079 
2080  lastoeclass = NULL;
2081  opathkey = NULL;
2082  lop = list_head(outer_pathkeys);
2083 
2084  foreach(lc, mergeclauses)
2085  {
2086  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2087  EquivalenceClass *oeclass;
2088  EquivalenceClass *ieclass;
2089  PathKey *pathkey;
2090 
2091  update_mergeclause_eclasses(root, rinfo);
2092 
2093  if (rinfo->outer_is_left)
2094  {
2095  oeclass = rinfo->left_ec;
2096  ieclass = rinfo->right_ec;
2097  }
2098  else
2099  {
2100  oeclass = rinfo->right_ec;
2101  ieclass = rinfo->left_ec;
2102  }
2103 
2104  /* outer eclass should match current or next pathkeys */
2105  /* we check this carefully for debugging reasons */
2106  if (oeclass != lastoeclass)
2107  {
2108  if (!lop)
2109  elog(ERROR, "too few pathkeys for mergeclauses");
2110  opathkey = (PathKey *) lfirst(lop);
2111  lop = lnext(outer_pathkeys, lop);
2112  lastoeclass = opathkey->pk_eclass;
2113  if (oeclass != lastoeclass)
2114  elog(ERROR, "outer pathkeys do not match mergeclause");
2115  }
2116 
2117  /*
2118  * Often, we'll have same EC on both sides, in which case the outer
2119  * pathkey is also canonical for the inner side, and we can skip a
2120  * useless search.
2121  */
2122  if (ieclass == oeclass)
2123  pathkey = opathkey;
2124  else
2125  pathkey = make_canonical_pathkey(root,
2126  ieclass,
2127  opathkey->pk_opfamily,
2128  opathkey->pk_strategy,
2129  opathkey->pk_nulls_first);
2130 
2131  /*
2132  * Don't generate redundant pathkeys (which can happen if multiple
2133  * mergeclauses refer to the same EC). Because we do this, the output
2134  * pathkey list isn't necessarily ordered like the mergeclauses, which
2135  * complicates life for create_mergejoin_plan(). But if we didn't,
2136  * we'd have a noncanonical sort key list, which would be bad; for one
2137  * reason, it certainly wouldn't match any available sort order for
2138  * the input relation.
2139  */
2140  if (!pathkey_is_redundant(pathkey, pathkeys))
2141  pathkeys = lappend(pathkeys, pathkey);
2142  }
2143 
2144  return pathkeys;
2145 }
static ListCell * list_head(const List *l)
Definition: pg_list.h:126

References elog(), ERROR, lappend(), RestrictInfo::left_ec, lfirst, list_head(), lnext(), make_canonical_pathkey(), NIL, RestrictInfo::outer_is_left, pathkey_is_redundant(), PathKey::pk_eclass, PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, RestrictInfo::right_ec, 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,
Relids  nullable_relids,
Oid  opfamily,
Oid  opcintype,
Oid  collation,
bool  reverse_sort,
bool  nulls_first,
Index  sortref,
Relids  rel,
bool  create_it 
)
static

Definition at line 182 of file pathkeys.c.

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

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

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

◆ make_pathkey_from_sortop()

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

Definition at line 241 of file pathkeys.c.

248 {
249  Oid opfamily,
250  opcintype,
251  collation;
252  int16 strategy;
253 
254  /* Find the operator in pg_amop --- failure shouldn't happen */
255  if (!get_ordering_op_properties(ordering_op,
256  &opfamily, &opcintype, &strategy))
257  elog(ERROR, "operator %u is not a valid ordering operator",
258  ordering_op);
259 
260  /* Because SortGroupClause doesn't carry collation, consult the expr */
261  collation = exprCollation((Node *) expr);
262 
263  return make_pathkey_from_sortinfo(root,
264  expr,
265  nullable_relids,
266  opfamily,
267  opcintype,
268  collation,
269  (strategy == BTGreaterStrategyNumber),
270  nulls_first,
271  sortref,
272  NULL,
273  create_it);
274 }

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

Referenced by make_pathkeys_for_sortclauses().

◆ make_pathkeys_for_sortclauses()

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

Definition at line 1648 of file pathkeys.c.

1651 {
1652  List *pathkeys = NIL;
1653  ListCell *l;
1654 
1655  foreach(l, sortclauses)
1656  {
1657  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1658  Expr *sortkey;
1659  PathKey *pathkey;
1660 
1661  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1662  Assert(OidIsValid(sortcl->sortop));
1663  pathkey = make_pathkey_from_sortop(root,
1664  sortkey,
1665  root->nullable_baserels,
1666  sortcl->sortop,
1667  sortcl->nulls_first,
1668  sortcl->tleSortGroupRef,
1669  true);
1670 
1671  /* Canonical form eliminates redundant ordering keys */
1672  if (!pathkey_is_redundant(pathkey, pathkeys))
1673  pathkeys = lappend(pathkeys, pathkey);
1674  }
1675  return pathkeys;
1676 }
static PathKey * make_pathkey_from_sortop(PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid ordering_op, bool nulls_first, Index sortref, bool create_it)
Definition: pathkeys.c:241
Relids nullable_baserels
Definition: pathnodes.h:218
Index tleSortGroupRef
Definition: parsenodes.h:1306
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:368

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

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

◆ matches_boolean_partition_clause()

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

Definition at line 1187 of file pathkeys.c.

1189 {
1190  Node *clause = (Node *) rinfo->clause;
1191  Node *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
1192 
1193  /* Direct match? */
1194  if (equal(partexpr, clause))
1195  return true;
1196  /* NOT clause? */
1197  else if (is_notclause(clause))
1198  {
1199  Node *arg = (Node *) get_notclausearg((Expr *) clause);
1200 
1201  if (equal(partexpr, arg))
1202  return true;
1203  }
1204 
1205  return false;
1206 }
static Expr * get_notclausearg(const void *notclause)
Definition: nodeFuncs.h:122
static bool is_notclause(const void *clause)
Definition: nodeFuncs.h:113
void * arg

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

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

1153 {
1154  PartitionScheme partscheme = partrel->part_scheme;
1155  ListCell *lc;
1156 
1157  /* If the partkey isn't boolean, we can't possibly get a match */
1158  if (!IsBooleanOpfamily(partscheme->partopfamily[partkeycol]))
1159  return false;
1160 
1161  /* Check each restriction clause for the partitioned rel */
1162  foreach(lc, partrel->baserestrictinfo)
1163  {
1164  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1165 
1166  /* Ignore pseudoconstant quals, they won't match */
1167  if (rinfo->pseudoconstant)
1168  continue;
1169 
1170  /* See if we can match the clause's expression to the partkey column */
1171  if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
1172  return true;
1173  }
1174 
1175  return false;
1176 }
static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:1187
List * baserestrictinfo
Definition: pathnodes.h:802
bool pseudoconstant
Definition: pathnodes.h:2246

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

Referenced by build_partition_pathkeys().

◆ pathkey_is_redundant()

static bool pathkey_is_redundant ( PathKey new_pathkey,
List pathkeys 
)
static

Definition at line 140 of file pathkeys.c.

141 {
142  EquivalenceClass *new_ec = new_pathkey->pk_eclass;
143  ListCell *lc;
144 
145  /* Check for EC containing a constant --- unconditionally redundant */
146  if (EC_MUST_BE_REDUNDANT(new_ec))
147  return true;
148 
149  /* If same EC already used in list, then redundant */
150  foreach(lc, pathkeys)
151  {
152  PathKey *old_pathkey = (PathKey *) lfirst(lc);
153 
154  if (new_ec == old_pathkey->pk_eclass)
155  return true;
156  }
157 
158  return false;
159 }
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: pathnodes.h:1151

References EC_MUST_BE_REDUNDANT, lfirst, and PathKey::pk_eclass.

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

◆ pathkey_sort_cost_comparator()

static int pathkey_sort_cost_comparator ( const void *  _a,
const void *  _b 
)
static

Definition at line 552 of file pathkeys.c.

553 {
554  const PathkeySortCost *a = (PathkeySortCost *) _a;
555  const PathkeySortCost *b = (PathkeySortCost *) _b;
556 
557  if (a->cost < b->cost)
558  return -1;
559  else if (a->cost == b->cost)
560  return 0;
561  return 1;
562 }
int b
Definition: isn.c:70
int a
Definition: isn.c:69

References a, and b.

Referenced by get_cheapest_group_keys_order().

◆ PathkeyMutatorInit()

static void PathkeyMutatorInit ( PathkeyMutatorState state,
List elems,
int  start,
int  end 
)
static

Definition at line 430 of file pathkeys.c.

431 {
432  int i;
433  int n = end - start;
434  ListCell *lc;
435 
436  memset(state, 0, sizeof(*state));
437 
438  state->mutatorNColumns = n;
439 
440  state->elemsList = list_copy(elems);
441 
442  state->elems = palloc(sizeof(void *) * n);
443  state->elemCells = palloc(sizeof(ListCell *) * n);
444  state->positions = palloc(sizeof(int) * n);
445 
446  i = 0;
447  for_each_cell(lc, state->elemsList, list_nth_cell(state->elemsList, start))
448  {
449  state->elemCells[i] = lc;
450  state->elems[i] = lfirst(lc);
451  state->positions[i] = i + 1;
452  i++;
453 
454  if (i >= n)
455  break;
456  }
457 }
#define for_each_cell(cell, lst, initcell)
Definition: pg_list.h:436
Definition: regguts.h:318

References for_each_cell, i, lfirst, list_copy(), list_nth_cell(), and palloc().

Referenced by get_cheapest_group_keys_order().

◆ PathkeyMutatorNext()

static List* PathkeyMutatorNext ( PathkeyMutatorState state)
static

Definition at line 512 of file pathkeys.c.

513 {
514  int i;
515 
516  state->count++;
517 
518  /* first permutation is original list */
519  if (state->count == 1)
520  return state->elemsList;
521 
522  /* when there are no more permutations, return NIL */
523  if (!PathkeyMutatorNextSet(state->positions, state->mutatorNColumns))
524  {
525  pfree(state->elems);
526  pfree(state->elemCells);
527  pfree(state->positions);
528 
529  list_free(state->elemsList);
530 
531  return NIL;
532  }
533 
534  /* update the list cells to point to the right elements */
535  for (i = 0; i < state->mutatorNColumns; i++)
536  lfirst(state->elemCells[i]) =
537  (void *) state->elems[state->positions[i] - 1];
538 
539  return state->elemsList;
540 }
static bool PathkeyMutatorNextSet(int *a, int n)
Definition: pathkeys.c:473

References i, lfirst, list_free(), NIL, PathkeyMutatorNextSet(), and pfree().

Referenced by get_cheapest_group_keys_order().

◆ PathkeyMutatorNextSet()

static bool PathkeyMutatorNextSet ( int *  a,
int  n 
)
static

Definition at line 473 of file pathkeys.c.

474 {
475  int j,
476  k,
477  l,
478  r;
479 
480  j = n - 2;
481 
482  while (j >= 0 && a[j] >= a[j + 1])
483  j--;
484 
485  if (j < 0)
486  return false;
487 
488  k = n - 1;
489 
490  while (k >= 0 && a[j] >= a[k])
491  k--;
492 
493  PathkeyMutatorSwap(a, j, k);
494 
495  l = j + 1;
496  r = n - 1;
497 
498  while (l < r)
499  PathkeyMutatorSwap(a, l++, r--);
500 
501  return true;
502 }
static void PathkeyMutatorSwap(int *a, int i, int j)
Definition: pathkeys.c:461

References a, j, and PathkeyMutatorSwap().

Referenced by PathkeyMutatorNext().

◆ PathkeyMutatorSwap()

static void PathkeyMutatorSwap ( int *  a,
int  i,
int  j 
)
static

Definition at line 461 of file pathkeys.c.

462 {
463  int s = a[i];
464 
465  a[i] = a[j];
466  a[j] = s;
467 }

References a, i, and j.

Referenced by PathkeyMutatorNextSet().

◆ pathkeys_contained_in()

◆ pathkeys_count_contained_in()

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

Definition at line 866 of file pathkeys.c.

867 {
868  int n = 0;
869  ListCell *key1,
870  *key2;
871 
872  /*
873  * See if we can avoiding looping through both lists. This optimization
874  * gains us several percent in planning time in a worst-case test.
875  */
876  if (keys1 == keys2)
877  {
878  *n_common = list_length(keys1);
879  return true;
880  }
881  else if (keys1 == NIL)
882  {
883  *n_common = 0;
884  return true;
885  }
886  else if (keys2 == NIL)
887  {
888  *n_common = 0;
889  return false;
890  }
891 
892  /*
893  * If both lists are non-empty, iterate through both to find out how many
894  * items are shared.
895  */
896  forboth(key1, keys1, key2, keys2)
897  {
898  PathKey *pathkey1 = (PathKey *) lfirst(key1);
899  PathKey *pathkey2 = (PathKey *) lfirst(key2);
900 
901  if (pathkey1 != pathkey2)
902  {
903  *n_common = n;
904  return false;
905  }
906  n++;
907  }
908 
909  /* If we ended with a null value, then we've processed the whole list. */
910  *n_common = n;
911  return (key1 == NULL);
912 }

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

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

◆ pathkeys_useful_for_grouping()

static int pathkeys_useful_for_grouping ( PlannerInfo root,
List pathkeys 
)
static

Definition at line 2408 of file pathkeys.c.

2409 {
2410  ListCell *key;
2411  int n = 0;
2412 
2413  /* no special ordering requested for grouping */
2414  if (root->group_pathkeys == NIL)
2415  return 0;
2416 
2417  /* unordered path */
2418  if (pathkeys == NIL)
2419  return 0;
2420 
2421  /* walk the pathkeys and search for matching group key */
2422  foreach(key, pathkeys)
2423  {
2424  PathKey *pathkey = (PathKey *) lfirst(key);
2425 
2426  /* no matching group key, we're done */
2427  if (!list_member_ptr(root->group_pathkeys, pathkey))
2428  break;
2429 
2430  n++;
2431  }
2432 
2433  return n;
2434 }

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

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

2269 {
2270  int useful = 0;
2271  ListCell *i;
2272 
2273  foreach(i, pathkeys)
2274  {
2275  PathKey *pathkey = (PathKey *) lfirst(i);
2276  bool matched = false;
2277  ListCell *j;
2278 
2279  /* If "wrong" direction, not useful for merging */
2280  if (!right_merge_direction(root, pathkey))
2281  break;
2282 
2283  /*
2284  * First look into the EquivalenceClass of the pathkey, to see if
2285  * there are any members not yet joined to the rel. If so, it's
2286  * surely possible to generate a mergejoin clause using them.
2287  */
2288  if (rel->has_eclass_joins &&
2289  eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
2290  matched = true;
2291  else
2292  {
2293  /*
2294  * Otherwise search the rel's joininfo list, which contains
2295  * non-EquivalenceClass-derivable join clauses that might
2296  * nonetheless be mergejoinable.
2297  */
2298  foreach(j, rel->joininfo)
2299  {
2300  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
2301 
2302  if (restrictinfo->mergeopfamilies == NIL)
2303  continue;
2304  update_mergeclause_eclasses(root, restrictinfo);
2305 
2306  if (pathkey->pk_eclass == restrictinfo->left_ec ||
2307  pathkey->pk_eclass == restrictinfo->right_ec)
2308  {
2309  matched = true;
2310  break;
2311  }
2312  }
2313  }
2314 
2315  /*
2316  * If we didn't find a mergeclause, we're done --- any additional
2317  * sort-key positions in the pathkeys are useless. (But we can still
2318  * mergejoin if we found at least one mergeclause.)
2319  */
2320  if (matched)
2321  useful++;
2322  else
2323  break;
2324  }
2325 
2326  return useful;
2327 }
bool eclass_useful_for_merging(PlannerInfo *root, EquivalenceClass *eclass, RelOptInfo *rel)
Definition: equivclass.c:3073
static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey)
Definition: pathkeys.c:2335

References eclass_useful_for_merging(), RelOptInfo::has_eclass_joins, i, j, RelOptInfo::joininfo, RestrictInfo::left_ec, lfirst, RestrictInfo::mergeopfamilies, NIL, PathKey::pk_eclass, RestrictInfo::right_ec, right_merge_direction(), and update_mergeclause_eclasses().

Referenced by truncate_useless_pathkeys().

◆ pathkeys_useful_for_ordering()

static int pathkeys_useful_for_ordering ( PlannerInfo root,
List pathkeys 
)
static

Definition at line 2372 of file pathkeys.c.

2373 {
2374  int n_common_pathkeys;
2375 
2376  if (root->query_pathkeys == NIL)
2377  return 0; /* no special ordering requested */
2378 
2379  if (pathkeys == NIL)
2380  return 0; /* unordered path */
2381 
2382  (void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys,
2383  &n_common_pathkeys);
2384 
2385  return n_common_pathkeys;
2386 }
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:866

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

Referenced by truncate_useless_pathkeys().

◆ right_merge_direction()

static bool right_merge_direction ( PlannerInfo root,
PathKey pathkey 
)
static

Definition at line 2335 of file pathkeys.c.

2336 {
2337  ListCell *l;
2338 
2339  foreach(l, root->query_pathkeys)
2340  {
2341  PathKey *query_pathkey = (PathKey *) lfirst(l);
2342 
2343  if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
2344  pathkey->pk_opfamily == query_pathkey->pk_opfamily)
2345  {
2346  /*
2347  * Found a matching query sort column. Prefer this pathkey's
2348  * direction iff it matches. Note that we ignore pk_nulls_first,
2349  * which means that a sort might be needed anyway ... but we still
2350  * want to prefer only one of the two possible directions, and we
2351  * might as well use this one.
2352  */
2353  return (pathkey->pk_strategy == query_pathkey->pk_strategy);
2354  }
2355  }
2356 
2357  /* If no matching ORDER BY request, prefer the ASC direction */
2358  return (pathkey->pk_strategy == BTLessStrategyNumber);
2359 }

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

Referenced by pathkeys_useful_for_merging().

◆ select_outer_pathkeys_for_merge()

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

Definition at line 1898 of file pathkeys.c.

1901 {
1902  List *pathkeys = NIL;
1903  int nClauses = list_length(mergeclauses);
1904  EquivalenceClass **ecs;
1905  int *scores;
1906  int necs;
1907  ListCell *lc;
1908  int j;
1909 
1910  /* Might have no mergeclauses */
1911  if (nClauses == 0)
1912  return NIL;
1913 
1914  /*
1915  * Make arrays of the ECs used by the mergeclauses (dropping any
1916  * duplicates) and their "popularity" scores.
1917  */
1918  ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
1919  scores = (int *) palloc(nClauses * sizeof(int));
1920  necs = 0;
1921 
1922  foreach(lc, mergeclauses)
1923  {
1924  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1925  EquivalenceClass *oeclass;
1926  int score;
1927  ListCell *lc2;
1928 
1929  /* get the outer eclass */
1930  update_mergeclause_eclasses(root, rinfo);
1931 
1932  if (rinfo->outer_is_left)
1933  oeclass = rinfo->left_ec;
1934  else
1935  oeclass = rinfo->right_ec;
1936 
1937  /* reject duplicates */
1938  for (j = 0; j < necs; j++)
1939  {
1940  if (ecs[j] == oeclass)
1941  break;
1942  }
1943  if (j < necs)
1944  continue;
1945 
1946  /* compute score */
1947  score = 0;
1948  foreach(lc2, oeclass->ec_members)
1949  {
1951 
1952  /* Potential future join partner? */
1953  if (!em->em_is_const && !em->em_is_child &&
1954  !bms_overlap(em->em_relids, joinrel->relids))
1955  score++;
1956  }
1957 
1958  ecs[necs] = oeclass;
1959  scores[necs] = score;
1960  necs++;
1961  }
1962 
1963  /*
1964  * Find out if we have all the ECs mentioned in query_pathkeys; if so we
1965  * can generate a sort order that's also useful for final output. There is
1966  * no percentage in a partial match, though, so we have to have 'em all.
1967  */
1968  if (root->query_pathkeys)
1969  {
1970  foreach(lc, root->query_pathkeys)
1971  {
1972  PathKey *query_pathkey = (PathKey *) lfirst(lc);
1973  EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1974 
1975  for (j = 0; j < necs; j++)
1976  {
1977  if (ecs[j] == query_ec)
1978  break; /* found match */
1979  }
1980  if (j >= necs)
1981  break; /* didn't find match */
1982  }
1983  /* if we got to the end of the list, we have them all */
1984  if (lc == NULL)
1985  {
1986  /* copy query_pathkeys as starting point for our output */
1987  pathkeys = list_copy(root->query_pathkeys);
1988  /* mark their ECs as already-emitted */
1989  foreach(lc, root->query_pathkeys)
1990  {
1991  PathKey *query_pathkey = (PathKey *) lfirst(lc);
1992  EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1993 
1994  for (j = 0; j < necs; j++)
1995  {
1996  if (ecs[j] == query_ec)
1997  {
1998  scores[j] = -1;
1999  break;
2000  }
2001  }
2002  }
2003  }
2004  }
2005 
2006  /*
2007  * Add remaining ECs to the list in popularity order, using a default sort
2008  * ordering. (We could use qsort() here, but the list length is usually
2009  * so small it's not worth it.)
2010  */
2011  for (;;)
2012  {
2013  int best_j;
2014  int best_score;
2015  EquivalenceClass *ec;
2016  PathKey *pathkey;
2017 
2018  best_j = 0;
2019  best_score = scores[0];
2020  for (j = 1; j < necs; j++)
2021  {
2022  if (scores[j] > best_score)
2023  {
2024  best_j = j;
2025  best_score = scores[j];
2026  }
2027  }
2028  if (best_score < 0)
2029  break; /* all done */
2030  ec = ecs[best_j];
2031  scores[best_j] = -1;
2032  pathkey = make_canonical_pathkey(root,
2033  ec,
2036  false);
2037  /* can't be redundant because no duplicate ECs */
2038  Assert(!pathkey_is_redundant(pathkey, pathkeys));
2039  pathkeys = lappend(pathkeys, pathkey);
2040  }
2041 
2042  pfree(ecs);
2043  pfree(scores);
2044 
2045  return pathkeys;
2046 }
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
#define linitial_oid(l)
Definition: pg_list.h:178

References Assert(), bms_overlap(), BTLessStrategyNumber, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, j, lappend(), RestrictInfo::left_ec, lfirst, linitial_oid, list_copy(), list_length(), make_canonical_pathkey(), NIL, RestrictInfo::outer_is_left, palloc(), pathkey_is_redundant(), pfree(), PathKey::pk_eclass, PlannerInfo::query_pathkeys, RelOptInfo::relids, RestrictInfo::right_ec, 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 2173 of file pathkeys.c.

2176 {
2177  List *new_mergeclauses = NIL;
2178  PathKey *pathkey;
2179  EquivalenceClass *pathkey_ec;
2180  bool matched_pathkey;
2181  ListCell *lip;
2182  ListCell *i;
2183 
2184  /* No pathkeys => no mergeclauses (though we don't expect this case) */
2185  if (pathkeys == NIL)
2186  return NIL;
2187  /* Initialize to consider first pathkey */
2188  lip = list_head(pathkeys);
2189  pathkey = (PathKey *) lfirst(lip);
2190  pathkey_ec = pathkey->pk_eclass;
2191  lip = lnext(pathkeys, lip);
2192  matched_pathkey = false;
2193 
2194  /* Scan mergeclauses to see how many we can use */
2195  foreach(i, mergeclauses)
2196  {
2197  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
2198  EquivalenceClass *clause_ec;
2199 
2200  /* Assume we needn't do update_mergeclause_eclasses again here */
2201 
2202  /* Check clause's inner-rel EC against current pathkey */
2203  clause_ec = rinfo->outer_is_left ?
2204  rinfo->right_ec : rinfo->left_ec;
2205 
2206  /* If we don't have a match, attempt to advance to next pathkey */
2207  if (clause_ec != pathkey_ec)
2208  {
2209  /* If we had no clauses matching this inner pathkey, must stop */
2210  if (!matched_pathkey)
2211  break;
2212 
2213  /* Advance to next inner pathkey, if any */
2214  if (lip == NULL)
2215  break;
2216  pathkey = (PathKey *) lfirst(lip);
2217  pathkey_ec = pathkey->pk_eclass;
2218  lip = lnext(pathkeys, lip);
2219  matched_pathkey = false;
2220  }
2221 
2222  /* If mergeclause matches current inner pathkey, we can use it */
2223  if (clause_ec == pathkey_ec)
2224  {
2225  new_mergeclauses = lappend(new_mergeclauses, rinfo);
2226  matched_pathkey = true;
2227  }
2228  else
2229  {
2230  /* Else, no hope of adding any more mergeclauses */
2231  break;
2232  }
2233  }
2234 
2235  return new_mergeclauses;
2236 }

References i, lappend(), RestrictInfo::left_ec, lfirst, list_head(), lnext(), NIL, RestrictInfo::outer_is_left, PathKey::pk_eclass, and RestrictInfo::right_ec.

Referenced by generate_mergejoin_paths().

◆ truncate_useless_pathkeys()

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

Definition at line 2441 of file pathkeys.c.

2444 {
2445  int nuseful;
2446  int nuseful2;
2447 
2448  nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
2449  nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
2450  if (nuseful2 > nuseful)
2451  nuseful = nuseful2;
2452  nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
2453  if (nuseful2 > nuseful)
2454  nuseful = nuseful2;
2455 
2456  /*
2457  * Note: not safe to modify input list destructively, but we can avoid
2458  * copying the list if we're not actually going to change it
2459  */
2460  if (nuseful == 0)
2461  return NIL;
2462  else if (nuseful == list_length(pathkeys))
2463  return pathkeys;
2464  else
2465  return list_truncate(list_copy(pathkeys), nuseful);
2466 }
static int pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2372
static int pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2408
static int pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2268

References list_copy(), list_length(), list_truncate(), NIL, pathkeys_useful_for_grouping(), pathkeys_useful_for_merging(), and pathkeys_useful_for_ordering().

Referenced by build_index_paths(), and build_join_pathkeys().

◆ update_mergeclause_eclasses()

void update_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1751 of file pathkeys.c.

1752 {
1753  /* Should be a merge clause ... */
1754  Assert(restrictinfo->mergeopfamilies != NIL);
1755  /* ... with pointers already set */
1756  Assert(restrictinfo->left_ec != NULL);
1757  Assert(restrictinfo->right_ec != NULL);
1758 
1759  /* Chase up to the top as needed */
1760  while (restrictinfo->left_ec->ec_merged)
1761  restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
1762  while (restrictinfo->right_ec->ec_merged)
1763  restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
1764 }
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:1144

References Assert(), EquivalenceClass::ec_merged, RestrictInfo::left_ec, RestrictInfo::mergeopfamilies, NIL, and RestrictInfo::right_ec.

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

Referenced by get_useful_group_keys_orderings().