PostgreSQL Source Code  git master
paths.h File Reference
#include "nodes/relation.h"
Include dependency graph for paths.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs

typedef void(* set_rel_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte)
 
typedef void(* set_join_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
typedef RelOptInfo *(* join_search_hook_type) (PlannerInfo *root, int levels_needed, List *initial_rels)
 
typedef bool(* ec_matches_callback_type) (PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)
 

Enumerations

enum  PathKeysComparison { PATHKEYS_EQUAL, PATHKEYS_BETTER1, PATHKEYS_BETTER2, PATHKEYS_DIFFERENT }
 

Functions

RelOptInfomake_one_rel (PlannerInfo *root, List *joinlist)
 
void set_dummy_rel_pathlist (RelOptInfo *rel)
 
RelOptInfostandard_join_search (PlannerInfo *root, int levels_needed, List *initial_rels)
 
void generate_gather_paths (PlannerInfo *root, RelOptInfo *rel, bool override_rows)
 
int compute_parallel_worker (RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
 
void create_partial_bitmap_paths (PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
 
void generate_partitionwise_join_paths (PlannerInfo *root, RelOptInfo *rel)
 
void create_index_paths (PlannerInfo *root, RelOptInfo *rel)
 
bool relation_has_unique_index_for (PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist)
 
bool indexcol_is_bool_constant_for_query (IndexOptInfo *index, int indexcol)
 
bool match_index_to_operand (Node *operand, int indexcol, IndexOptInfo *index)
 
void expand_indexqual_conditions (IndexOptInfo *index, List *indexclauses, List *indexclausecols, List **indexquals_p, List **indexqualcols_p)
 
void check_index_predicates (PlannerInfo *root, RelOptInfo *rel)
 
Expradjust_rowcompare_for_index (RowCompareExpr *clause, IndexOptInfo *index, int indexcol, List **indexcolnos, bool *var_on_left_p)
 
void create_tidscan_paths (PlannerInfo *root, RelOptInfo *rel)
 
void add_paths_to_joinrel (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
 
void join_search_one_level (PlannerInfo *root, int level)
 
RelOptInfomake_join_rel (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
bool have_join_order_restriction (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
bool have_dangerous_phv (PlannerInfo *root, Relids outer_relids, Relids inner_params)
 
void mark_dummy_rel (RelOptInfo *rel)
 
bool have_partkey_equi_join (RelOptInfo *joinrel, RelOptInfo *rel1, RelOptInfo *rel2, JoinType jointype, List *restrictlist)
 
bool process_equivalence (PlannerInfo *root, RestrictInfo **p_restrictinfo, bool below_outer_join)
 
Exprcanonicalize_ec_expression (Expr *expr, Oid req_type, Oid req_collation)
 
void reconsider_outer_join_clauses (PlannerInfo *root)
 
EquivalenceClassget_eclass_for_sort_expr (PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
 
void generate_base_implied_equalities (PlannerInfo *root)
 
Listgenerate_join_implied_equalities (PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
 
Listgenerate_join_implied_equalities_for_ecs (PlannerInfo *root, List *eclasses, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
 
bool exprs_known_equal (PlannerInfo *root, Node *item1, Node *item2)
 
EquivalenceClassmatch_eclasses_to_foreign_key_col (PlannerInfo *root, ForeignKeyOptInfo *fkinfo, int colno)
 
void add_child_rel_equivalences (PlannerInfo *root, AppendRelInfo *appinfo, RelOptInfo *parent_rel, RelOptInfo *child_rel)
 
Listgenerate_implied_equalities_for_column (PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
 
bool have_relevant_eclass_joinclause (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
bool has_relevant_eclass_joinclause (PlannerInfo *root, RelOptInfo *rel1)
 
bool eclass_useful_for_merging (PlannerInfo *root, EquivalenceClass *eclass, RelOptInfo *rel)
 
bool is_redundant_derived_clause (RestrictInfo *rinfo, List *clauselist)
 
PathKeysComparison compare_pathkeys (List *keys1, List *keys2)
 
bool pathkeys_contained_in (List *keys1, List *keys2)
 
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)
 
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)
 
Listtruncate_useless_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 
bool has_useful_pathkeys (PlannerInfo *root, RelOptInfo *rel)
 
PathKeymake_canonical_pathkey (PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
 
void add_paths_to_append_rel (PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
 

Variables

PGDLLIMPORT bool enable_geqo
 
PGDLLIMPORT int geqo_threshold
 
PGDLLIMPORT int min_parallel_table_scan_size
 
PGDLLIMPORT int min_parallel_index_scan_size
 
PGDLLIMPORT set_rel_pathlist_hook_type set_rel_pathlist_hook
 
PGDLLIMPORT set_join_pathlist_hook_type set_join_pathlist_hook
 
PGDLLIMPORT join_search_hook_type join_search_hook
 

Typedef Documentation

◆ ec_matches_callback_type

typedef bool(* ec_matches_callback_type) (PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)

Definition at line 126 of file paths.h.

◆ join_search_hook_type

typedef RelOptInfo*(* join_search_hook_type) (PlannerInfo *root, int levels_needed, List *initial_rels)

Definition at line 45 of file paths.h.

◆ set_join_pathlist_hook_type

typedef void(* set_join_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)

Definition at line 36 of file paths.h.

◆ set_rel_pathlist_hook_type

typedef void(* set_rel_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte)

Definition at line 29 of file paths.h.

Enumeration Type Documentation

◆ PathKeysComparison

Enumerator
PATHKEYS_EQUAL 
PATHKEYS_BETTER1 
PATHKEYS_BETTER2 
PATHKEYS_DIFFERENT 

Definition at line 183 of file paths.h.

184 {
185  PATHKEYS_EQUAL, /* pathkeys are identical */
186  PATHKEYS_BETTER1, /* pathkey 1 is a superset of pathkey 2 */
187  PATHKEYS_BETTER2, /* vice versa */
188  PATHKEYS_DIFFERENT /* neither pathkey includes the other */
PathKeysComparison
Definition: paths.h:183

Function Documentation

◆ add_child_rel_equivalences()

void add_child_rel_equivalences ( PlannerInfo root,
AppendRelInfo appinfo,
RelOptInfo parent_rel,
RelOptInfo child_rel 
)

Definition at line 2108 of file equivclass.c.

References add_eq_member(), adjust_appendrel_attrs(), bms_add_members(), bms_difference(), bms_is_subset(), bms_overlap(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_const, EquivalenceMember::em_nullable_relids, EquivalenceMember::em_relids, PlannerInfo::eq_classes, lfirst, RelOptInfo::relids, RELOPT_BASEREL, and RelOptInfo::reloptkind.

Referenced by set_append_rel_size().

2112 {
2113  ListCell *lc1;
2114 
2115  foreach(lc1, root->eq_classes)
2116  {
2117  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
2118  ListCell *lc2;
2119 
2120  /*
2121  * If this EC contains a volatile expression, then generating child
2122  * EMs would be downright dangerous, so skip it. We rely on a
2123  * volatile EC having only one EM.
2124  */
2125  if (cur_ec->ec_has_volatile)
2126  continue;
2127 
2128  /*
2129  * No point in searching if parent rel not mentioned in eclass; but we
2130  * can't tell that for sure if parent rel is itself a child.
2131  */
2132  if (parent_rel->reloptkind == RELOPT_BASEREL &&
2133  !bms_is_subset(parent_rel->relids, cur_ec->ec_relids))
2134  continue;
2135 
2136  foreach(lc2, cur_ec->ec_members)
2137  {
2138  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
2139 
2140  if (cur_em->em_is_const)
2141  continue; /* ignore consts here */
2142 
2143  /* Does it reference parent_rel? */
2144  if (bms_overlap(cur_em->em_relids, parent_rel->relids))
2145  {
2146  /* Yes, generate transformed child version */
2147  Expr *child_expr;
2148  Relids new_relids;
2149  Relids new_nullable_relids;
2150 
2151  child_expr = (Expr *)
2153  (Node *) cur_em->em_expr,
2154  1, &appinfo);
2155 
2156  /*
2157  * Transform em_relids to match. Note we do *not* do
2158  * pull_varnos(child_expr) here, as for example the
2159  * transformation might have substituted a constant, but we
2160  * don't want the child member to be marked as constant.
2161  */
2162  new_relids = bms_difference(cur_em->em_relids,
2163  parent_rel->relids);
2164  new_relids = bms_add_members(new_relids, child_rel->relids);
2165 
2166  /*
2167  * And likewise for nullable_relids. Note this code assumes
2168  * parent and child relids are singletons.
2169  */
2170  new_nullable_relids = cur_em->em_nullable_relids;
2171  if (bms_overlap(new_nullable_relids, parent_rel->relids))
2172  {
2173  new_nullable_relids = bms_difference(new_nullable_relids,
2174  parent_rel->relids);
2175  new_nullable_relids = bms_add_members(new_nullable_relids,
2176  child_rel->relids);
2177  }
2178 
2179  (void) add_eq_member(cur_ec, child_expr,
2180  new_relids, new_nullable_relids,
2181  true, cur_em->em_datatype);
2182  }
2183  }
2184  }
2185 }
RelOptKind reloptkind
Definition: relation.h:609
Relids em_nullable_relids
Definition: relation.h:948
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:350
Definition: nodes.h:517
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:374
Relids ec_relids
Definition: relation.h:901
Relids relids
Definition: relation.h:612
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, int nappinfos, AppendRelInfo **appinfos)
Definition: prepunion.c:2046
Relids em_relids
Definition: relation.h:947
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:249
bool ec_has_volatile
Definition: relation.h:904
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:509
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, Relids nullable_relids, bool is_child, Oid datatype)
Definition: equivclass.c:543
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:821
List * ec_members
Definition: relation.h:898

◆ add_paths_to_append_rel()

void add_paths_to_append_rel ( PlannerInfo root,
RelOptInfo rel,
List live_childrels 
)

Definition at line 1377 of file allpaths.c.

References accumulate_append_subpath(), add_partial_path(), add_path(), Assert, bms_equal(), bms_next_member(), RelOptInfo::cheapest_total_path, compare_pathkeys(), create_append_path(), enable_parallel_append, fls(), generate_mergeappend_paths(), get_cheapest_parallel_safe_total_inner(), get_cheapest_parameterized_child_path(), IS_JOIN_REL, IS_SIMPLE_REL, lappend(), lfirst, linitial, list_concat(), list_copy(), list_length(), Max, max_parallel_workers_per_gather, Min, NIL, Path::parallel_workers, Path::param_info, RelOptInfo::part_scheme, RelOptInfo::partial_pathlist, RelOptInfo::partitioned_child_rels, AppendPath::path, PATH_REQ_OUTER, Path::pathkeys, PATHKEYS_EQUAL, RelOptInfo::pathlist, RelOptInfo::relids, Path::rows, RTE_SUBQUERY, RelOptInfo::rtekind, PlannerInfo::simple_rel_array, subpath(), and Path::total_cost.

Referenced by apply_scanjoin_target_to_paths(), create_partitionwise_grouping_paths(), generate_partitionwise_join_paths(), and set_append_rel_pathlist().

1379 {
1380  List *subpaths = NIL;
1381  bool subpaths_valid = true;
1382  List *partial_subpaths = NIL;
1383  List *pa_partial_subpaths = NIL;
1384  List *pa_nonpartial_subpaths = NIL;
1385  bool partial_subpaths_valid = true;
1386  bool pa_subpaths_valid = enable_parallel_append;
1387  List *all_child_pathkeys = NIL;
1388  List *all_child_outers = NIL;
1389  ListCell *l;
1390  List *partitioned_rels = NIL;
1391  bool build_partitioned_rels = false;
1392  double partial_rows = -1;
1393 
1394  /*
1395  * AppendPath generated for partitioned tables must record the RT indexes
1396  * of partitioned tables that are direct or indirect children of this
1397  * Append rel.
1398  *
1399  * AppendPath may be for a sub-query RTE (UNION ALL), in which case, 'rel'
1400  * itself does not represent a partitioned relation, but the child sub-
1401  * queries may contain references to partitioned relations. The loop
1402  * below will look for such children and collect them in a list to be
1403  * passed to the path creation function. (This assumes that we don't need
1404  * to look through multiple levels of subquery RTEs; if we ever do, we
1405  * could consider stuffing the list we generate here into sub-query RTE's
1406  * RelOptInfo, just like we do for partitioned rels, which would be used
1407  * when populating our parent rel with paths. For the present, that
1408  * appears to be unnecessary.)
1409  */
1410  if (rel->part_scheme != NULL)
1411  {
1412  if (IS_SIMPLE_REL(rel))
1413  partitioned_rels = rel->partitioned_child_rels;
1414  else if (IS_JOIN_REL(rel))
1415  {
1416  int relid = -1;
1417 
1418  /*
1419  * For a partitioned joinrel, concatenate the component rels'
1420  * partitioned_child_rels lists.
1421  */
1422  while ((relid = bms_next_member(rel->relids, relid)) >= 0)
1423  {
1424  RelOptInfo *component;
1425 
1426  Assert(relid >= 1 && relid < root->simple_rel_array_size);
1427  component = root->simple_rel_array[relid];
1428  Assert(component->part_scheme != NULL);
1429  Assert(list_length(component->partitioned_child_rels) >= 1);
1430  partitioned_rels =
1431  list_concat(partitioned_rels,
1432  list_copy(component->partitioned_child_rels));
1433  }
1434  }
1435 
1436  Assert(list_length(partitioned_rels) >= 1);
1437  }
1438  else if (rel->rtekind == RTE_SUBQUERY)
1439  build_partitioned_rels = true;
1440 
1441  /*
1442  * For every non-dummy child, remember the cheapest path. Also, identify
1443  * all pathkeys (orderings) and parameterizations (required_outer sets)
1444  * available for the non-dummy member relations.
1445  */
1446  foreach(l, live_childrels)
1447  {
1448  RelOptInfo *childrel = lfirst(l);
1449  ListCell *lcp;
1450  Path *cheapest_partial_path = NULL;
1451 
1452  /*
1453  * If we need to build partitioned_rels, accumulate the partitioned
1454  * rels for this child.
1455  */
1456  if (build_partitioned_rels)
1457  {
1458  List *cprels = childrel->partitioned_child_rels;
1459 
1460  partitioned_rels = list_concat(partitioned_rels,
1461  list_copy(cprels));
1462  }
1463 
1464  /*
1465  * If child has an unparameterized cheapest-total path, add that to
1466  * the unparameterized Append path we are constructing for the parent.
1467  * If not, there's no workable unparameterized path.
1468  *
1469  * With partitionwise aggregates, the child rel's pathlist may be
1470  * empty, so don't assume that a path exists here.
1471  */
1472  if (childrel->pathlist != NIL &&
1473  childrel->cheapest_total_path->param_info == NULL)
1475  &subpaths, NULL);
1476  else
1477  subpaths_valid = false;
1478 
1479  /* Same idea, but for a partial plan. */
1480  if (childrel->partial_pathlist != NIL)
1481  {
1482  cheapest_partial_path = linitial(childrel->partial_pathlist);
1483  accumulate_append_subpath(cheapest_partial_path,
1484  &partial_subpaths, NULL);
1485  }
1486  else
1487  partial_subpaths_valid = false;
1488 
1489  /*
1490  * Same idea, but for a parallel append mixing partial and non-partial
1491  * paths.
1492  */
1493  if (pa_subpaths_valid)
1494  {
1495  Path *nppath = NULL;
1496 
1497  nppath =
1499 
1500  if (cheapest_partial_path == NULL && nppath == NULL)
1501  {
1502  /* Neither a partial nor a parallel-safe path? Forget it. */
1503  pa_subpaths_valid = false;
1504  }
1505  else if (nppath == NULL ||
1506  (cheapest_partial_path != NULL &&
1507  cheapest_partial_path->total_cost < nppath->total_cost))
1508  {
1509  /* Partial path is cheaper or the only option. */
1510  Assert(cheapest_partial_path != NULL);
1511  accumulate_append_subpath(cheapest_partial_path,
1512  &pa_partial_subpaths,
1513  &pa_nonpartial_subpaths);
1514 
1515  }
1516  else
1517  {
1518  /*
1519  * Either we've got only a non-partial path, or we think that
1520  * a single backend can execute the best non-partial path
1521  * faster than all the parallel backends working together can
1522  * execute the best partial path.
1523  *
1524  * It might make sense to be more aggressive here. Even if
1525  * the best non-partial path is more expensive than the best
1526  * partial path, it could still be better to choose the
1527  * non-partial path if there are several such paths that can
1528  * be given to different workers. For now, we don't try to
1529  * figure that out.
1530  */
1532  &pa_nonpartial_subpaths,
1533  NULL);
1534  }
1535  }
1536 
1537  /*
1538  * Collect lists of all the available path orderings and
1539  * parameterizations for all the children. We use these as a
1540  * heuristic to indicate which sort orderings and parameterizations we
1541  * should build Append and MergeAppend paths for.
1542  */
1543  foreach(lcp, childrel->pathlist)
1544  {
1545  Path *childpath = (Path *) lfirst(lcp);
1546  List *childkeys = childpath->pathkeys;
1547  Relids childouter = PATH_REQ_OUTER(childpath);
1548 
1549  /* Unsorted paths don't contribute to pathkey list */
1550  if (childkeys != NIL)
1551  {
1552  ListCell *lpk;
1553  bool found = false;
1554 
1555  /* Have we already seen this ordering? */
1556  foreach(lpk, all_child_pathkeys)
1557  {
1558  List *existing_pathkeys = (List *) lfirst(lpk);
1559 
1560  if (compare_pathkeys(existing_pathkeys,
1561  childkeys) == PATHKEYS_EQUAL)
1562  {
1563  found = true;
1564  break;
1565  }
1566  }
1567  if (!found)
1568  {
1569  /* No, so add it to all_child_pathkeys */
1570  all_child_pathkeys = lappend(all_child_pathkeys,
1571  childkeys);
1572  }
1573  }
1574 
1575  /* Unparameterized paths don't contribute to param-set list */
1576  if (childouter)
1577  {
1578  ListCell *lco;
1579  bool found = false;
1580 
1581  /* Have we already seen this param set? */
1582  foreach(lco, all_child_outers)
1583  {
1584  Relids existing_outers = (Relids) lfirst(lco);
1585 
1586  if (bms_equal(existing_outers, childouter))
1587  {
1588  found = true;
1589  break;
1590  }
1591  }
1592  if (!found)
1593  {
1594  /* No, so add it to all_child_outers */
1595  all_child_outers = lappend(all_child_outers,
1596  childouter);
1597  }
1598  }
1599  }
1600  }
1601 
1602  /*
1603  * If we found unparameterized paths for all children, build an unordered,
1604  * unparameterized Append path for the rel. (Note: this is correct even
1605  * if we have zero or one live subpath due to constraint exclusion.)
1606  */
1607  if (subpaths_valid)
1608  add_path(rel, (Path *) create_append_path(root, rel, subpaths, NIL,
1609  NULL, 0, false,
1610  partitioned_rels, -1));
1611 
1612  /*
1613  * Consider an append of unordered, unparameterized partial paths. Make
1614  * it parallel-aware if possible.
1615  */
1616  if (partial_subpaths_valid)
1617  {
1618  AppendPath *appendpath;
1619  ListCell *lc;
1620  int parallel_workers = 0;
1621 
1622  /* Find the highest number of workers requested for any subpath. */
1623  foreach(lc, partial_subpaths)
1624  {
1625  Path *path = lfirst(lc);
1626 
1627  parallel_workers = Max(parallel_workers, path->parallel_workers);
1628  }
1629  Assert(parallel_workers > 0);
1630 
1631  /*
1632  * If the use of parallel append is permitted, always request at least
1633  * log2(# of children) workers. We assume it can be useful to have
1634  * extra workers in this case because they will be spread out across
1635  * the children. The precise formula is just a guess, but we don't
1636  * want to end up with a radically different answer for a table with N
1637  * partitions vs. an unpartitioned table with the same data, so the
1638  * use of some kind of log-scaling here seems to make some sense.
1639  */
1641  {
1642  parallel_workers = Max(parallel_workers,
1643  fls(list_length(live_childrels)));
1644  parallel_workers = Min(parallel_workers,
1646  }
1647  Assert(parallel_workers > 0);
1648 
1649  /* Generate a partial append path. */
1650  appendpath = create_append_path(root, rel, NIL, partial_subpaths,
1651  NULL, parallel_workers,
1653  partitioned_rels, -1);
1654 
1655  /*
1656  * Make sure any subsequent partial paths use the same row count
1657  * estimate.
1658  */
1659  partial_rows = appendpath->path.rows;
1660 
1661  /* Add the path. */
1662  add_partial_path(rel, (Path *) appendpath);
1663  }
1664 
1665  /*
1666  * Consider a parallel-aware append using a mix of partial and non-partial
1667  * paths. (This only makes sense if there's at least one child which has
1668  * a non-partial path that is substantially cheaper than any partial path;
1669  * otherwise, we should use the append path added in the previous step.)
1670  */
1671  if (pa_subpaths_valid && pa_nonpartial_subpaths != NIL)
1672  {
1673  AppendPath *appendpath;
1674  ListCell *lc;
1675  int parallel_workers = 0;
1676 
1677  /*
1678  * Find the highest number of workers requested for any partial
1679  * subpath.
1680  */
1681  foreach(lc, pa_partial_subpaths)
1682  {
1683  Path *path = lfirst(lc);
1684 
1685  parallel_workers = Max(parallel_workers, path->parallel_workers);
1686  }
1687 
1688  /*
1689  * Same formula here as above. It's even more important in this
1690  * instance because the non-partial paths won't contribute anything to
1691  * the planned number of parallel workers.
1692  */
1693  parallel_workers = Max(parallel_workers,
1694  fls(list_length(live_childrels)));
1695  parallel_workers = Min(parallel_workers,
1697  Assert(parallel_workers > 0);
1698 
1699  appendpath = create_append_path(root, rel, pa_nonpartial_subpaths,
1700  pa_partial_subpaths,
1701  NULL, parallel_workers, true,
1702  partitioned_rels, partial_rows);
1703  add_partial_path(rel, (Path *) appendpath);
1704  }
1705 
1706  /*
1707  * Also build unparameterized MergeAppend paths based on the collected
1708  * list of child pathkeys.
1709  */
1710  if (subpaths_valid)
1711  generate_mergeappend_paths(root, rel, live_childrels,
1712  all_child_pathkeys,
1713  partitioned_rels);
1714 
1715  /*
1716  * Build Append paths for each parameterization seen among the child rels.
1717  * (This may look pretty expensive, but in most cases of practical
1718  * interest, the child rels will expose mostly the same parameterizations,
1719  * so that not that many cases actually get considered here.)
1720  *
1721  * The Append node itself cannot enforce quals, so all qual checking must
1722  * be done in the child paths. This means that to have a parameterized
1723  * Append path, we must have the exact same parameterization for each
1724  * child path; otherwise some children might be failing to check the
1725  * moved-down quals. To make them match up, we can try to increase the
1726  * parameterization of lesser-parameterized paths.
1727  */
1728  foreach(l, all_child_outers)
1729  {
1730  Relids required_outer = (Relids) lfirst(l);
1731  ListCell *lcr;
1732 
1733  /* Select the child paths for an Append with this parameterization */
1734  subpaths = NIL;
1735  subpaths_valid = true;
1736  foreach(lcr, live_childrels)
1737  {
1738  RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
1739  Path *subpath;
1740 
1741  if (childrel->pathlist == NIL)
1742  {
1743  /* failed to make a suitable path for this child */
1744  subpaths_valid = false;
1745  break;
1746  }
1747 
1749  childrel,
1750  required_outer);
1751  if (subpath == NULL)
1752  {
1753  /* failed to make a suitable path for this child */
1754  subpaths_valid = false;
1755  break;
1756  }
1757  accumulate_append_subpath(subpath, &subpaths, NULL);
1758  }
1759 
1760  if (subpaths_valid)
1761  add_path(rel, (Path *)
1762  create_append_path(root, rel, subpaths, NIL,
1763  required_outer, 0, false,
1764  partitioned_rels, -1));
1765  }
1766 }
#define NIL
Definition: pg_list.h:69
AppendPath * create_append_path(PlannerInfo *root, RelOptInfo *rel, List *subpaths, List *partial_subpaths, Relids required_outer, int parallel_workers, bool parallel_aware, List *partitioned_rels, double rows)
Definition: pathnode.c:1213
static void generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel, List *live_childrels, List *all_child_pathkeys, List *partitioned_rels)
Definition: allpaths.c:1792
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
static Path * get_cheapest_parameterized_child_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
Definition: allpaths.c:1879
#define Min(x, y)
Definition: c.h:857
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1075
int parallel_workers
Definition: relation.h:1085
#define IS_JOIN_REL(rel)
Definition: relation.h:590
ParamPathInfo * param_info
Definition: relation.h:1081
List * list_copy(const List *oldlist)
Definition: list.c:1160
List * partial_pathlist
Definition: relation.h:628
List * list_concat(List *list1, List *list2)
Definition: list.c:321
bool enable_parallel_append
Definition: costsize.c:139
PathKeysComparison compare_pathkeys(List *keys1, List *keys2)
Definition: pathkeys.c:278
#define IS_SIMPLE_REL(rel)
Definition: relation.h:585
Path path
Definition: relation.h:1304
int fls(int mask)
Definition: fls.c:55
struct RelOptInfo ** simple_rel_array
Definition: relation.h:193
#define linitial(l)
Definition: pg_list.h:111
struct Path * cheapest_total_path
Definition: relation.h:630
Relids relids
Definition: relation.h:612
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:421
Bitmapset * Relids
Definition: relation.h:29
List * lappend(List *list, void *datum)
Definition: list.c:128
RTEKind rtekind
Definition: relation.h:642
Cost total_cost
Definition: relation.h:1090
List * pathkeys
Definition: relation.h:1092
#define Max(x, y)
Definition: c.h:851
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
double rows
Definition: relation.h:1088
#define PATH_REQ_OUTER(path)
Definition: relation.h:1097
static int list_length(const List *l)
Definition: pg_list.h:89
List * partitioned_child_rels
Definition: relation.h:692
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:762
PartitionScheme part_scheme
Definition: relation.h:684
List * pathlist
Definition: relation.h:626
static void accumulate_append_subpath(Path *path, List **subpaths, List **special_subpaths)
Definition: allpaths.c:1968
int max_parallel_workers_per_gather
Definition: costsize.c:123
Definition: pg_list.h:45
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:234
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:153

◆ add_paths_to_joinrel()

void add_paths_to_joinrel ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
SpecialJoinInfo sjinfo,
List restrictlist 
)

Definition at line 117 of file joinpath.c.

References PlannerInfo::all_baserels, bms_add_members(), bms_difference(), bms_is_subset(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), enable_hashjoin, enable_mergejoin, RelOptInfo::fdwroutine, FdwRoutine::GetForeignJoinPaths, hash_inner_and_outer(), JoinPathExtraData::inner_unique, innerrel_is_unique(), JOIN_ANTI, JOIN_FULL, PlannerInfo::join_info_list, JOIN_INNER, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, SpecialJoinInfo::jointype, RelOptInfo::lateral_relids, lfirst, match_unsorted_outer(), JoinPathExtraData::mergeclause_list, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, JoinPathExtraData::param_source_rels, RelOptInfo::relids, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, JoinPathExtraData::restrictlist, select_mergejoin_clauses(), JoinPathExtraData::semifactors, set_join_pathlist_hook, JoinPathExtraData::sjinfo, sort_inner_and_outer(), and RelOptInfo::top_parent_relids.

Referenced by populate_joinrel_with_paths().

124 {
125  JoinPathExtraData extra;
126  bool mergejoin_allowed = true;
127  ListCell *lc;
128  Relids joinrelids;
129 
130  /*
131  * PlannerInfo doesn't contain the SpecialJoinInfos created for joins
132  * between child relations, even if there is a SpecialJoinInfo node for
133  * the join between the topmost parents. So, while calculating Relids set
134  * representing the restriction, consider relids of topmost parent of
135  * partitions.
136  */
137  if (joinrel->reloptkind == RELOPT_OTHER_JOINREL)
138  joinrelids = joinrel->top_parent_relids;
139  else
140  joinrelids = joinrel->relids;
141 
142  extra.restrictlist = restrictlist;
143  extra.mergeclause_list = NIL;
144  extra.sjinfo = sjinfo;
145  extra.param_source_rels = NULL;
146 
147  /*
148  * See if the inner relation is provably unique for this outer rel.
149  *
150  * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
151  * matter since the executor can make the equivalent optimization anyway;
152  * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
153  * must be considering a semijoin whose inner side is not provably unique
154  * (else reduce_unique_semijoins would've simplified it), so there's no
155  * point in calling innerrel_is_unique. However, if the LHS covers all of
156  * the semijoin's min_lefthand, then it's appropriate to set inner_unique
157  * because the path produced by create_unique_path will be unique relative
158  * to the LHS. (If we have an LHS that's only part of the min_lefthand,
159  * that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
160  * letting that value escape this module.
161  */
162  switch (jointype)
163  {
164  case JOIN_SEMI:
165  case JOIN_ANTI:
166  extra.inner_unique = false; /* well, unproven */
167  break;
168  case JOIN_UNIQUE_INNER:
169  extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
170  outerrel->relids);
171  break;
172  case JOIN_UNIQUE_OUTER:
173  extra.inner_unique = innerrel_is_unique(root,
174  joinrel->relids,
175  outerrel->relids,
176  innerrel,
177  JOIN_INNER,
178  restrictlist,
179  false);
180  break;
181  default:
182  extra.inner_unique = innerrel_is_unique(root,
183  joinrel->relids,
184  outerrel->relids,
185  innerrel,
186  jointype,
187  restrictlist,
188  false);
189  break;
190  }
191 
192  /*
193  * Find potential mergejoin clauses. We can skip this if we are not
194  * interested in doing a mergejoin. However, mergejoin may be our only
195  * way of implementing a full outer join, so override enable_mergejoin if
196  * it's a full join.
197  */
198  if (enable_mergejoin || jointype == JOIN_FULL)
200  joinrel,
201  outerrel,
202  innerrel,
203  restrictlist,
204  jointype,
205  &mergejoin_allowed);
206 
207  /*
208  * If it's SEMI, ANTI, or inner_unique join, compute correction factors
209  * for cost estimation. These will be the same for all paths.
210  */
211  if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique)
212  compute_semi_anti_join_factors(root, joinrel, outerrel, innerrel,
213  jointype, sjinfo, restrictlist,
214  &extra.semifactors);
215 
216  /*
217  * Decide whether it's sensible to generate parameterized paths for this
218  * joinrel, and if so, which relations such paths should require. There
219  * is usually no need to create a parameterized result path unless there
220  * is a join order restriction that prevents joining one of our input rels
221  * directly to the parameter source rel instead of joining to the other
222  * input rel. (But see allow_star_schema_join().) This restriction
223  * reduces the number of parameterized paths we have to deal with at
224  * higher join levels, without compromising the quality of the resulting
225  * plan. We express the restriction as a Relids set that must overlap the
226  * parameterization of any proposed join path.
227  */
228  foreach(lc, root->join_info_list)
229  {
230  SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
231 
232  /*
233  * SJ is relevant to this join if we have some part of its RHS
234  * (possibly not all of it), and haven't yet joined to its LHS. (This
235  * test is pretty simplistic, but should be sufficient considering the
236  * join has already been proven legal.) If the SJ is relevant, it
237  * presents constraints for joining to anything not in its RHS.
238  */
239  if (bms_overlap(joinrelids, sjinfo2->min_righthand) &&
240  !bms_overlap(joinrelids, sjinfo2->min_lefthand))
243  sjinfo2->min_righthand));
244 
245  /* full joins constrain both sides symmetrically */
246  if (sjinfo2->jointype == JOIN_FULL &&
247  bms_overlap(joinrelids, sjinfo2->min_lefthand) &&
248  !bms_overlap(joinrelids, sjinfo2->min_righthand))
251  sjinfo2->min_lefthand));
252  }
253 
254  /*
255  * However, when a LATERAL subquery is involved, there will simply not be
256  * any paths for the joinrel that aren't parameterized by whatever the
257  * subquery is parameterized by, unless its parameterization is resolved
258  * within the joinrel. So we might as well allow additional dependencies
259  * on whatever residual lateral dependencies the joinrel will have.
260  */
262  joinrel->lateral_relids);
263 
264  /*
265  * 1. Consider mergejoin paths where both relations must be explicitly
266  * sorted. Skip this if we can't mergejoin.
267  */
268  if (mergejoin_allowed)
269  sort_inner_and_outer(root, joinrel, outerrel, innerrel,
270  jointype, &extra);
271 
272  /*
273  * 2. Consider paths where the outer relation need not be explicitly
274  * sorted. This includes both nestloops and mergejoins where the outer
275  * path is already ordered. Again, skip this if we can't mergejoin.
276  * (That's okay because we know that nestloop can't handle right/full
277  * joins at all, so it wouldn't work in the prohibited cases either.)
278  */
279  if (mergejoin_allowed)
280  match_unsorted_outer(root, joinrel, outerrel, innerrel,
281  jointype, &extra);
282 
283 #ifdef NOT_USED
284 
285  /*
286  * 3. Consider paths where the inner relation need not be explicitly
287  * sorted. This includes mergejoins only (nestloops were already built in
288  * match_unsorted_outer).
289  *
290  * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
291  * significant difference between the inner and outer side of a mergejoin,
292  * so match_unsorted_inner creates no paths that aren't equivalent to
293  * those made by match_unsorted_outer when add_paths_to_joinrel() is
294  * invoked with the two rels given in the other order.
295  */
296  if (mergejoin_allowed)
297  match_unsorted_inner(root, joinrel, outerrel, innerrel,
298  jointype, &extra);
299 #endif
300 
301  /*
302  * 4. Consider paths where both outer and inner relations must be hashed
303  * before being joined. As above, disregard enable_hashjoin for full
304  * joins, because there may be no other alternative.
305  */
306  if (enable_hashjoin || jointype == JOIN_FULL)
307  hash_inner_and_outer(root, joinrel, outerrel, innerrel,
308  jointype, &extra);
309 
310  /*
311  * 5. If inner and outer relations are foreign tables (or joins) belonging
312  * to the same server and assigned to the same user to check access
313  * permissions as, give the FDW a chance to push down joins.
314  */
315  if (joinrel->fdwroutine &&
317  joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
318  outerrel, innerrel,
319  jointype, &extra);
320 
321  /*
322  * 6. Finally, give extensions a chance to manipulate the path list.
323  */
325  set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
326  jointype, &extra);
327 }
#define NIL
Definition: pg_list.h:69
SemiAntiJoinFactors semifactors
Definition: relation.h:2314
RelOptKind reloptkind
Definition: relation.h:609
List * join_info_list
Definition: relation.h:264
Relids min_righthand
Definition: relation.h:2067
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:350
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition: analyzejoins.c:971
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1677
Relids lateral_relids
Definition: relation.h:637
SpecialJoinInfo * sjinfo
Definition: relation.h:2313
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:881
Relids all_baserels
Definition: relation.h:210
GetForeignJoinPaths_function GetForeignJoinPaths
Definition: fdwapi.h:201
Relids param_source_rels
Definition: relation.h:2315
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:976
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:374
struct FdwRoutine * fdwroutine
Definition: relation.h:663
List * mergeclause_list
Definition: relation.h:2311
Relids relids
Definition: relation.h:612
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:1929
List * restrictlist
Definition: relation.h:2310
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:27
bool enable_mergejoin
Definition: costsize.c:134
#define lfirst(lc)
Definition: pg_list.h:106
JoinType jointype
Definition: relation.h:2070
void compute_semi_anti_join_factors(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist, SemiAntiJoinFactors *semifactors)
Definition: costsize.c:4037
bool enable_hashjoin
Definition: costsize.c:135
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:509
Relids min_lefthand
Definition: relation.h:2066
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:821
Relids top_parent_relids
Definition: relation.h:681
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1331

◆ adjust_rowcompare_for_index()

Expr* adjust_rowcompare_for_index ( RowCompareExpr clause,
IndexOptInfo index,
int  indexcol,
List **  indexcolnos,
bool var_on_left_p 
)

Definition at line 3854 of file indxpath.c.

References Assert, bms_is_member(), BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, contain_volatile_functions(), copyObject, elog, ERROR, get_commutator(), get_op_opfamily_properties(), get_op_opfamily_strategy(), get_opfamily_member(), i, IndexOptInfo::indexcollations, IndexCollMatchesExprColl, RowCompareExpr::inputcollids, InvalidOid, lappend_int(), lappend_oid(), RowCompareExpr::largs, lfirst, lfirst_oid, linitial, linitial_oid, list_copy(), list_head(), list_length(), list_make1_int, list_make1_oid, list_truncate(), lnext, make_opclause(), makeNode, match_index_to_operand(), IndexOptInfo::ncolumns, NIL, IndexOptInfo::nkeycolumns, OidIsValid, RowCompareExpr::opfamilies, IndexOptInfo::opfamily, RowCompareExpr::opnos, pull_varnos(), RowCompareExpr::rargs, RowCompareExpr::rctype, IndexOptInfo::rel, RelOptInfo::relid, ROWCOMPARE_GE, and ROWCOMPARE_LE.

Referenced by expand_indexqual_rowcompare(), and fix_indexqual_references().

3859 {
3860  bool var_on_left;
3861  int op_strategy;
3862  Oid op_lefttype;
3863  Oid op_righttype;
3864  int matching_cols;
3865  Oid expr_op;
3866  List *opfamilies;
3867  List *lefttypes;
3868  List *righttypes;
3869  List *new_ops;
3870  ListCell *largs_cell;
3871  ListCell *rargs_cell;
3872  ListCell *opnos_cell;
3873  ListCell *collids_cell;
3874 
3875  /* We have to figure out (again) how the first col matches */
3876  var_on_left = match_index_to_operand((Node *) linitial(clause->largs),
3877  indexcol, index);
3878  Assert(var_on_left ||
3880  indexcol, index));
3881  *var_on_left_p = var_on_left;
3882 
3883  expr_op = linitial_oid(clause->opnos);
3884  if (!var_on_left)
3885  expr_op = get_commutator(expr_op);
3886  get_op_opfamily_properties(expr_op, index->opfamily[indexcol], false,
3887  &op_strategy,
3888  &op_lefttype,
3889  &op_righttype);
3890 
3891  /* Initialize returned list of which index columns are used */
3892  *indexcolnos = list_make1_int(indexcol);
3893 
3894  /* Build lists of the opfamilies and operator datatypes in case needed */
3895  opfamilies = list_make1_oid(index->opfamily[indexcol]);
3896  lefttypes = list_make1_oid(op_lefttype);
3897  righttypes = list_make1_oid(op_righttype);
3898 
3899  /*
3900  * See how many of the remaining columns match some index column in the
3901  * same way. As in match_clause_to_indexcol(), the "other" side of any
3902  * potential index condition is OK as long as it doesn't use Vars from the
3903  * indexed relation.
3904  */
3905  matching_cols = 1;
3906  largs_cell = lnext(list_head(clause->largs));
3907  rargs_cell = lnext(list_head(clause->rargs));
3908  opnos_cell = lnext(list_head(clause->opnos));
3909  collids_cell = lnext(list_head(clause->inputcollids));
3910 
3911  while (largs_cell != NULL)
3912  {
3913  Node *varop;
3914  Node *constop;
3915  int i;
3916 
3917  expr_op = lfirst_oid(opnos_cell);
3918  if (var_on_left)
3919  {
3920  varop = (Node *) lfirst(largs_cell);
3921  constop = (Node *) lfirst(rargs_cell);
3922  }
3923  else
3924  {
3925  varop = (Node *) lfirst(rargs_cell);
3926  constop = (Node *) lfirst(largs_cell);
3927  /* indexkey is on right, so commute the operator */
3928  expr_op = get_commutator(expr_op);
3929  if (expr_op == InvalidOid)
3930  break; /* operator is not usable */
3931  }
3932  if (bms_is_member(index->rel->relid, pull_varnos(constop)))
3933  break; /* no good, Var on wrong side */
3934  if (contain_volatile_functions(constop))
3935  break; /* no good, volatile comparison value */
3936 
3937  /*
3938  * The Var side can match any column of the index.
3939  */
3940  for (i = 0; i < index->nkeycolumns; i++)
3941  {
3942  if (match_index_to_operand(varop, i, index) &&
3943  get_op_opfamily_strategy(expr_op,
3944  index->opfamily[i]) == op_strategy &&
3946  lfirst_oid(collids_cell)))
3947 
3948  break;
3949  }
3950  if (i >= index->ncolumns)
3951  break; /* no match found */
3952 
3953  /* Add column number to returned list */
3954  *indexcolnos = lappend_int(*indexcolnos, i);
3955 
3956  /* Add opfamily and datatypes to lists */
3957  get_op_opfamily_properties(expr_op, index->opfamily[i], false,
3958  &op_strategy,
3959  &op_lefttype,
3960  &op_righttype);
3961  opfamilies = lappend_oid(opfamilies, index->opfamily[i]);
3962  lefttypes = lappend_oid(lefttypes, op_lefttype);
3963  righttypes = lappend_oid(righttypes, op_righttype);
3964 
3965  /* This column matches, keep scanning */
3966  matching_cols++;
3967  largs_cell = lnext(largs_cell);
3968  rargs_cell = lnext(rargs_cell);
3969  opnos_cell = lnext(opnos_cell);
3970  collids_cell = lnext(collids_cell);
3971  }
3972 
3973  /* Return clause as-is if it's all usable as index quals */
3974  if (matching_cols == list_length(clause->opnos))
3975  return (Expr *) clause;
3976 
3977  /*
3978  * We have to generate a subset rowcompare (possibly just one OpExpr). The
3979  * painful part of this is changing < to <= or > to >=, so deal with that
3980  * first.
3981  */
3982  if (op_strategy == BTLessEqualStrategyNumber ||
3983  op_strategy == BTGreaterEqualStrategyNumber)
3984  {
3985  /* easy, just use the same operators */
3986  new_ops = list_truncate(list_copy(clause->opnos), matching_cols);
3987  }
3988  else
3989  {
3990  ListCell *opfamilies_cell;
3991  ListCell *lefttypes_cell;
3992  ListCell *righttypes_cell;
3993 
3994  if (op_strategy == BTLessStrategyNumber)
3995  op_strategy = BTLessEqualStrategyNumber;
3996  else if (op_strategy == BTGreaterStrategyNumber)
3997  op_strategy = BTGreaterEqualStrategyNumber;
3998  else
3999  elog(ERROR, "unexpected strategy number %d", op_strategy);
4000  new_ops = NIL;
4001  lefttypes_cell = list_head(lefttypes);
4002  righttypes_cell = list_head(righttypes);
4003  foreach(opfamilies_cell, opfamilies)
4004  {
4005  Oid opfam = lfirst_oid(opfamilies_cell);
4006  Oid lefttype = lfirst_oid(lefttypes_cell);
4007  Oid righttype = lfirst_oid(righttypes_cell);
4008 
4009  expr_op = get_opfamily_member(opfam, lefttype, righttype,
4010  op_strategy);
4011  if (!OidIsValid(expr_op)) /* should not happen */
4012  elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
4013  op_strategy, lefttype, righttype, opfam);
4014  if (!var_on_left)
4015  {
4016  expr_op = get_commutator(expr_op);
4017  if (!OidIsValid(expr_op)) /* should not happen */
4018  elog(ERROR, "could not find commutator of operator %d(%u,%u) of opfamily %u",
4019  op_strategy, lefttype, righttype, opfam);
4020  }
4021  new_ops = lappend_oid(new_ops, expr_op);
4022  lefttypes_cell = lnext(lefttypes_cell);
4023  righttypes_cell = lnext(righttypes_cell);
4024  }
4025  }
4026 
4027  /* If we have more than one matching col, create a subset rowcompare */
4028  if (matching_cols > 1)
4029  {
4031 
4032  if (var_on_left)
4033  rc->rctype = (RowCompareType) op_strategy;
4034  else
4035  rc->rctype = (op_strategy == BTLessEqualStrategyNumber) ?
4037  rc->opnos = new_ops;
4039  matching_cols);
4041  matching_cols);
4042  rc->largs = list_truncate(copyObject(clause->largs),
4043  matching_cols);
4044  rc->rargs = list_truncate(copyObject(clause->rargs),
4045  matching_cols);
4046  return (Expr *) rc;
4047  }
4048  else
4049  {
4050  return make_opclause(linitial_oid(new_ops), BOOLOID, false,
4051  copyObject(linitial(clause->largs)),
4052  copyObject(linitial(clause->rargs)),
4053  InvalidOid,
4054  linitial_oid(clause->inputcollids));
4055  }
4056 }
#define NIL
Definition: pg_list.h:69
Oid get_commutator(Oid opno)
Definition: lsyscache.c:1298
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Oid * indexcollations
Definition: relation.h:767
bool match_index_to_operand(Node *operand, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:3205
RowCompareType rctype
Definition: primnodes.h:1039
List * opfamilies
Definition: primnodes.h:1041
List * list_truncate(List *list, int new_size)
Definition: list.c:350
List * list_copy(const List *oldlist)
Definition: list.c:1160
Definition: nodes.h:517
Expr * make_opclause(Oid opno, Oid opresulttype, bool opretset, Expr *leftop, Expr *rightop, Oid opcollid, Oid inputcollid)
Definition: clauses.c:173
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:958
unsigned int Oid
Definition: postgres_ext.h:31
List * lappend_oid(List *list, Oid datum)
Definition: list.c:164
#define OidIsValid(objectId)
Definition: c.h:605
#define BTLessEqualStrategyNumber
Definition: stratnum.h:30
RelOptInfo * rel
Definition: relation.h:755
#define linitial(l)
Definition: pg_list.h:111
#define ERROR
Definition: elog.h:43
#define IndexCollMatchesExprColl(idxcollation, exprcollation)
Definition: indxpath.c:44
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:163
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
#define list_make1_int(x1)
Definition: pg_list.h:145
int ncolumns
Definition: relation.h:763
#define lnext(lc)
Definition: pg_list.h:105
Relids pull_varnos(Node *node)
Definition: var.c:95
List * lappend_int(List *list, int datum)
Definition: list.c:146
Index relid
Definition: relation.h:640
#define list_make1_oid(x1)
Definition: pg_list.h:151
#define InvalidOid
Definition: postgres_ext.h:36
RowCompareType
Definition: primnodes.h:1025
#define makeNode(_type_)
Definition: nodes.h:565
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
#define linitial_oid(l)
Definition: pg_list.h:113
static int list_length(const List *l)
Definition: pg_list.h:89
int nkeycolumns
Definition: relation.h:764
Oid * opfamily
Definition: relation.h:768
int get_op_opfamily_strategy(Oid opno, Oid opfamily)
Definition: lsyscache.c:80
void get_op_opfamily_properties(Oid opno, Oid opfamily, bool ordering_op, int *strategy, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:133
int i
#define elog
Definition: elog.h:219
#define copyObject(obj)
Definition: nodes.h:630
List * inputcollids
Definition: primnodes.h:1042
#define BTLessStrategyNumber
Definition: stratnum.h:29
Definition: pg_list.h:45
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:486
#define BTGreaterEqualStrategyNumber
Definition: stratnum.h:32
#define lfirst_oid(lc)
Definition: pg_list.h:108

◆ build_expression_pathkey()

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

Definition at line 562 of file pathkeys.c.

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

Referenced by set_function_pathlist().

568 {
569  List *pathkeys;
570  Oid opfamily,
571  opcintype;
572  int16 strategy;
573  PathKey *cpathkey;
574 
575  /* Find the operator in pg_amop --- failure shouldn't happen */
576  if (!get_ordering_op_properties(opno,
577  &opfamily, &opcintype, &strategy))
578  elog(ERROR, "operator %u is not a valid ordering operator",
579  opno);
580 
581  cpathkey = make_pathkey_from_sortinfo(root,
582  expr,
583  nullable_relids,
584  opfamily,
585  opcintype,
586  exprCollation((Node *) expr),
587  (strategy == BTGreaterStrategyNumber),
588  (strategy == BTGreaterStrategyNumber),
589  0,
590  rel,
591  create_it);
592 
593  if (cpathkey)
594  pathkeys = list_make1(cpathkey);
595  else
596  pathkeys = NIL;
597 
598  return pathkeys;
599 }
signed short int16
Definition: c.h:312
#define NIL
Definition: pg_list.h:69
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Definition: nodes.h:517
unsigned int Oid
Definition: postgres_ext.h:31
#define list_make1(x1)
Definition: pg_list.h:139
#define ERROR
Definition: elog.h:43
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, int16 *strategy)
Definition: lsyscache.c:204
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:720
#define elog
Definition: elog.h:219
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:170
Definition: pg_list.h:45

◆ build_index_pathkeys()

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

Definition at line 462 of file pathkeys.c.

References TargetEntry::expr, i, indexcol_is_bool_constant_for_query(), IndexOptInfo::indexcollations, IndexOptInfo::indextlist, lappend(), lfirst, make_pathkey_from_sortinfo(), NIL, IndexOptInfo::nkeycolumns, IndexOptInfo::nulls_first, IndexOptInfo::opcintype, pathkey_is_redundant(), IndexOptInfo::rel, RelOptInfo::relids, IndexOptInfo::reverse_sort, ScanDirectionIsBackward, and IndexOptInfo::sortopfamily.

Referenced by build_index_paths().

465 {
466  List *retval = NIL;
467  ListCell *lc;
468  int i;
469 
470  if (index->sortopfamily == NULL)
471  return NIL; /* non-orderable index */
472 
473  i = 0;
474  foreach(lc, index->indextlist)
475  {
476  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
477  Expr *indexkey;
478  bool reverse_sort;
479  bool nulls_first;
480  PathKey *cpathkey;
481 
482  /*
483  * INCLUDE columns are stored in index unordered, so they don't
484  * support ordered index scan.
485  */
486  if (i >= index->nkeycolumns)
487  break;
488 
489  /* We assume we don't need to make a copy of the tlist item */
490  indexkey = indextle->expr;
491 
492  if (ScanDirectionIsBackward(scandir))
493  {
494  reverse_sort = !index->reverse_sort[i];
495  nulls_first = !index->nulls_first[i];
496  }
497  else
498  {
499  reverse_sort = index->reverse_sort[i];
500  nulls_first = index->nulls_first[i];
501  }
502 
503  /*
504  * OK, try to make a canonical pathkey for this sort key. Note we're
505  * underneath any outer joins, so nullable_relids should be NULL.
506  */
507  cpathkey = make_pathkey_from_sortinfo(root,
508  indexkey,
509  NULL,
510  index->sortopfamily[i],
511  index->opcintype[i],
512  index->indexcollations[i],
513  reverse_sort,
514  nulls_first,
515  0,
516  index->rel->relids,
517  false);
518 
519  if (cpathkey)
520  {
521  /*
522  * We found the sort key in an EquivalenceClass, so it's relevant
523  * for this query. Add it to list, unless it's redundant.
524  */
525  if (!pathkey_is_redundant(cpathkey, retval))
526  retval = lappend(retval, cpathkey);
527  }
528  else
529  {
530  /*
531  * Boolean index keys might be redundant even if they do not
532  * appear in an EquivalenceClass, because of our special treatment
533  * of boolean equality conditions --- see the comment for
534  * indexcol_is_bool_constant_for_query(). If that applies, we can
535  * continue to examine lower-order index columns. Otherwise, the
536  * sort key is not an interesting sort order for this query, so we
537  * should stop considering index columns; any lower-order sort
538  * keys won't be useful either.
539  */
541  break;
542  }
543 
544  i++;
545  }
546 
547  return retval;
548 }
#define NIL
Definition: pg_list.h:69
Oid * indexcollations
Definition: relation.h:767
List * indextlist
Definition: relation.h:780
Oid * sortopfamily
Definition: relation.h:770
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
RelOptInfo * rel
Definition: relation.h:755
Relids relids
Definition: relation.h:612
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:128
List * lappend(List *list, void *datum)
Definition: list.c:128
#define lfirst(lc)
Definition: pg_list.h:106
Expr * expr
Definition: primnodes.h:1376
int nkeycolumns
Definition: relation.h:764
Oid * opcintype
Definition: relation.h:769
bool indexcol_is_bool_constant_for_query(IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3156
int i
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:170
bool * nulls_first
Definition: relation.h:772
bool * reverse_sort
Definition: relation.h:771
Definition: pg_list.h:45

◆ build_join_pathkeys()

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

Definition at line 831 of file pathkeys.c.

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

835 {
836  if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
837  return NIL;
838 
839  /*
840  * This used to be quite a complex bit of code, but now that all pathkey
841  * sublists start out life canonicalized, we don't have to do a darn thing
842  * here!
843  *
844  * We do, however, need to truncate the pathkeys list, since it may
845  * contain pathkeys that were useful for forming this joinrel but are
846  * uninteresting to higher levels.
847  */
848  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
849 }
#define NIL
Definition: pg_list.h:69
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:1619

◆ canonicalize_ec_expression()

Expr* canonicalize_ec_expression ( Expr expr,
Oid  req_type,
Oid  req_collation 
)

Definition at line 494 of file equivclass.c.

References arg, COERCE_IMPLICIT_CAST, exprCollation(), exprType(), exprTypmod(), IsA, and makeRelabelType().

Referenced by convert_subquery_pathkeys(), get_eclass_for_sort_expr(), and process_equivalence().

495 {
496  Oid expr_type = exprType((Node *) expr);
497 
498  /*
499  * For a polymorphic-input-type opclass, just keep the same exposed type.
500  */
501  if (IsPolymorphicType(req_type))
502  req_type = expr_type;
503 
504  /*
505  * No work if the expression exposes the right type/collation already.
506  */
507  if (expr_type != req_type ||
508  exprCollation((Node *) expr) != req_collation)
509  {
510  /*
511  * Strip any existing RelabelType, then add a new one if needed. This
512  * is to preserve the invariant of no redundant RelabelTypes.
513  *
514  * If we have to change the exposed type of the stripped expression,
515  * set typmod to -1 (since the new type may not have the same typmod
516  * interpretation). If we only have to change collation, preserve the
517  * exposed typmod.
518  */
519  while (expr && IsA(expr, RelabelType))
520  expr = (Expr *) ((RelabelType *) expr)->arg;
521 
522  if (exprType((Node *) expr) != req_type)
523  expr = (Expr *) makeRelabelType(expr,
524  req_type,
525  -1,
526  req_collation,
528  else if (exprCollation((Node *) expr) != req_collation)
529  expr = (Expr *) makeRelabelType(expr,
530  req_type,
531  exprTypmod((Node *) expr),
532  req_collation,
534  }
535 
536  return expr;
537 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:568
int32 exprTypmod(const Node *expr)
Definition: nodeFuncs.c:276
Definition: nodes.h:517
unsigned int Oid
Definition: postgres_ext.h:31
RelabelType * makeRelabelType(Expr *arg, Oid rtype, int32 rtypmod, Oid rcollid, CoercionForm rformat)
Definition: makefuncs.c:401
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:720
void * arg

◆ check_index_predicates()

void check_index_predicates ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 2794 of file indxpath.c.

References PlannerInfo::all_baserels, Assert, RelOptInfo::baserestrictinfo, bms_difference(), bms_is_empty(), bms_union(), RestrictInfo::clause, contain_mutable_functions(), find_childrel_parents(), generate_join_implied_equalities(), get_plan_rowmark(), RelOptInfo::indexlist, IndexOptInfo::indpred, IndexOptInfo::indrestrictinfo, IS_SIMPLE_REL, join_clause_is_movable_to(), RelOptInfo::joininfo, lappend(), lfirst, list_concat(), list_copy(), list_make1, NIL, PlannerInfo::parse, predicate_implied_by(), IndexOptInfo::predOK, RelOptInfo::relid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, Query::resultRelation, and PlannerInfo::rowMarks.

Referenced by set_plain_rel_size(), and set_tablesample_rel_size().

2795 {
2796  List *clauselist;
2797  bool have_partial;
2798  bool is_target_rel;
2799  Relids otherrels;
2800  ListCell *lc;
2801 
2802  /* Indexes are available only on base or "other" member relations. */
2803  Assert(IS_SIMPLE_REL(rel));
2804 
2805  /*
2806  * Initialize the indrestrictinfo lists to be identical to
2807  * baserestrictinfo, and check whether there are any partial indexes. If
2808  * not, this is all we need to do.
2809  */
2810  have_partial = false;
2811  foreach(lc, rel->indexlist)
2812  {
2814 
2815  index->indrestrictinfo = rel->baserestrictinfo;
2816  if (index->indpred)
2817  have_partial = true;
2818  }
2819  if (!have_partial)
2820  return;
2821 
2822  /*
2823  * Construct a list of clauses that we can assume true for the purpose of
2824  * proving the index(es) usable. Restriction clauses for the rel are
2825  * always usable, and so are any join clauses that are "movable to" this
2826  * rel. Also, we can consider any EC-derivable join clauses (which must
2827  * be "movable to" this rel, by definition).
2828  */
2829  clauselist = list_copy(rel->baserestrictinfo);
2830 
2831  /* Scan the rel's join clauses */
2832  foreach(lc, rel->joininfo)
2833  {
2834  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2835 
2836  /* Check if clause can be moved to this rel */
2837  if (!join_clause_is_movable_to(rinfo, rel))
2838  continue;
2839 
2840  clauselist = lappend(clauselist, rinfo);
2841  }
2842 
2843  /*
2844  * Add on any equivalence-derivable join clauses. Computing the correct
2845  * relid sets for generate_join_implied_equalities is slightly tricky
2846  * because the rel could be a child rel rather than a true baserel, and in
2847  * that case we must remove its parents' relid(s) from all_baserels.
2848  */
2849  if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
2850  otherrels = bms_difference(root->all_baserels,
2851  find_childrel_parents(root, rel));
2852  else
2853  otherrels = bms_difference(root->all_baserels, rel->relids);
2854 
2855  if (!bms_is_empty(otherrels))
2856  clauselist =
2857  list_concat(clauselist,
2859  bms_union(rel->relids,
2860  otherrels),
2861  otherrels,
2862  rel));
2863 
2864  /*
2865  * Normally we remove quals that are implied by a partial index's
2866  * predicate from indrestrictinfo, indicating that they need not be
2867  * checked explicitly by an indexscan plan using this index. However, if
2868  * the rel is a target relation of UPDATE/DELETE/SELECT FOR UPDATE, we
2869  * cannot remove such quals from the plan, because they need to be in the
2870  * plan so that they will be properly rechecked by EvalPlanQual testing.
2871  * Some day we might want to remove such quals from the main plan anyway
2872  * and pass them through to EvalPlanQual via a side channel; but for now,
2873  * we just don't remove implied quals at all for target relations.
2874  */
2875  is_target_rel = (rel->relid == root->parse->resultRelation ||
2876  get_plan_rowmark(root->rowMarks, rel->relid) != NULL);
2877 
2878  /*
2879  * Now try to prove each index predicate true, and compute the
2880  * indrestrictinfo lists for partial indexes. Note that we compute the
2881  * indrestrictinfo list even for non-predOK indexes; this might seem
2882  * wasteful, but we may be able to use such indexes in OR clauses, cf
2883  * generate_bitmap_or_paths().
2884  */
2885  foreach(lc, rel->indexlist)
2886  {
2887  IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
2888  ListCell *lcr;
2889 
2890  if (index->indpred == NIL)
2891  continue; /* ignore non-partial indexes here */
2892 
2893  if (!index->predOK) /* don't repeat work if already proven OK */
2894  index->predOK = predicate_implied_by(index->indpred, clauselist,
2895  false);
2896 
2897  /* If rel is an update target, leave indrestrictinfo as set above */
2898  if (is_target_rel)
2899  continue;
2900 
2901  /* Else compute indrestrictinfo as the non-implied quals */
2902  index->indrestrictinfo = NIL;
2903  foreach(lcr, rel->baserestrictinfo)
2904  {
2905  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
2906 
2907  /* predicate_implied_by() assumes first arg is immutable */
2908  if (contain_mutable_functions((Node *) rinfo->clause) ||
2910  index->indpred, false))
2911  index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
2912  }
2913  }
2914 }
#define NIL
Definition: pg_list.h:69
List * rowMarks
Definition: relation.h:268
Query * parse
Definition: relation.h:169
bool predOK
Definition: relation.h:788
RelOptKind reloptkind
Definition: relation.h:609
List * baserestrictinfo
Definition: relation.h:672
int resultRelation
Definition: parsenodes.h:122
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:350
List * list_copy(const List *oldlist)
Definition: list.c:1160
Definition: nodes.h:517
List * list_concat(List *list1, List *list2)
Definition: list.c:321
#define IS_SIMPLE_REL(rel)
Definition: relation.h:585
Definition: type.h:89
#define list_make1(x1)
Definition: pg_list.h:139
Relids all_baserels
Definition: relation.h:210
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1071
List * joininfo
Definition: relation.h:676
Relids relids
Definition: relation.h:612
Index relid
Definition: relation.h:640
List * lappend(List *list, void *datum)
Definition: list.c:128
Expr * clause
Definition: relation.h:1880
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:729
List * indrestrictinfo
Definition: relation.h:782
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1226
List * indexlist
Definition: relation.h:649
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:438
PlanRowMark * get_plan_rowmark(List *rowmarks, Index rtindex)
Definition: preptlist.c:424
bool contain_mutable_functions(Node *clause)
Definition: clauses.c:879
List * indpred
Definition: relation.h:778
bool predicate_implied_by(List *predicate_list, List *clause_list, bool weak)
Definition: predtest.c:149
Definition: pg_list.h:45

◆ compare_pathkeys()

PathKeysComparison compare_pathkeys ( List keys1,
List keys2 
)

Definition at line 278 of file pathkeys.c.

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

279 {
280  ListCell *key1,
281  *key2;
282 
283  /*
284  * Fall out quickly if we are passed two identical lists. This mostly
285  * catches the case where both are NIL, but that's common enough to
286  * warrant the test.
287  */
288  if (keys1 == keys2)
289  return PATHKEYS_EQUAL;
290 
291  forboth(key1, keys1, key2, keys2)
292  {
293  PathKey *pathkey1 = (PathKey *) lfirst(key1);
294  PathKey *pathkey2 = (PathKey *) lfirst(key2);
295 
296  if (pathkey1 != pathkey2)
297  return PATHKEYS_DIFFERENT; /* no need to keep looking */
298  }
299 
300  /*
301  * If we reached the end of only one list, the other is longer and
302  * therefore not a subset.
303  */
304  if (key1 != NULL)
305  return PATHKEYS_BETTER1; /* key1 is longer */
306  if (key2 != NULL)
307  return PATHKEYS_BETTER2; /* key2 is longer */
308  return PATHKEYS_EQUAL;
309 }
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:180
#define lfirst(lc)
Definition: pg_list.h:106

◆ compute_parallel_worker()

int compute_parallel_worker ( RelOptInfo rel,
double  heap_pages,
double  index_pages,
int  max_workers 
)

Definition at line 3435 of file allpaths.c.

References Max, Min, min_parallel_index_scan_size, min_parallel_table_scan_size, RelOptInfo::rel_parallel_workers, RELOPT_BASEREL, and RelOptInfo::reloptkind.

Referenced by cost_index(), create_partial_bitmap_paths(), create_plain_partial_paths(), and plan_create_index_workers().

3437 {
3438  int parallel_workers = 0;
3439 
3440  /*
3441  * If the user has set the parallel_workers reloption, use that; otherwise
3442  * select a default number of workers.
3443  */
3444  if (rel->rel_parallel_workers != -1)
3445  parallel_workers = rel->rel_parallel_workers;
3446  else
3447  {
3448  /*
3449  * If the number of pages being scanned is insufficient to justify a
3450  * parallel scan, just return zero ... unless it's an inheritance
3451  * child. In that case, we want to generate a parallel path here
3452  * anyway. It might not be worthwhile just for this relation, but
3453  * when combined with all of its inheritance siblings it may well pay
3454  * off.
3455  */
3456  if (rel->reloptkind == RELOPT_BASEREL &&
3457  ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
3458  (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
3459  return 0;
3460 
3461  if (heap_pages >= 0)
3462  {
3463  int heap_parallel_threshold;
3464  int heap_parallel_workers = 1;
3465 
3466  /*
3467  * Select the number of workers based on the log of the size of
3468  * the relation. This probably needs to be a good deal more
3469  * sophisticated, but we need something here for now. Note that
3470  * the upper limit of the min_parallel_table_scan_size GUC is
3471  * chosen to prevent overflow here.
3472  */
3473  heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
3474  while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
3475  {
3476  heap_parallel_workers++;
3477  heap_parallel_threshold *= 3;
3478  if (heap_parallel_threshold > INT_MAX / 3)
3479  break; /* avoid overflow */
3480  }
3481 
3482  parallel_workers = heap_parallel_workers;
3483  }
3484 
3485  if (index_pages >= 0)
3486  {
3487  int index_parallel_workers = 1;
3488  int index_parallel_threshold;
3489 
3490  /* same calculation as for heap_pages above */
3491  index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
3492  while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
3493  {
3494  index_parallel_workers++;
3495  index_parallel_threshold *= 3;
3496  if (index_parallel_threshold > INT_MAX / 3)
3497  break; /* avoid overflow */
3498  }
3499 
3500  if (parallel_workers > 0)
3501  parallel_workers = Min(parallel_workers, index_parallel_workers);
3502  else
3503  parallel_workers = index_parallel_workers;
3504  }
3505  }
3506 
3507  /* In no case use more than caller supplied maximum number of workers */
3508  parallel_workers = Min(parallel_workers, max_workers);
3509 
3510  return parallel_workers;
3511 }
RelOptKind reloptkind
Definition: relation.h:609
#define Min(x, y)
Definition: c.h:857
uint32 BlockNumber
Definition: block.h:31
int min_parallel_index_scan_size
Definition: allpaths.c:63
int rel_parallel_workers
Definition: relation.h:656
#define Max(x, y)
Definition: c.h:851
int min_parallel_table_scan_size
Definition: allpaths.c:62

◆ convert_subquery_pathkeys()

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

Definition at line 616 of file pathkeys.c.

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, get_eclass_for_sort_expr(), get_sortgroupref_tle(), i, lappend(), lfirst, linitial, list_length(), list_nth(), make_canonical_pathkey(), makeVarFromTargetEntry(), NIL, pathkey_is_redundant(), PathKey::pk_eclass, PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, PlannerInfo::query_pathkeys, RelOptInfo::relid, RelOptInfo::relids, and TargetEntry::resjunk.

Referenced by set_subquery_pathlist().

619 {
620  List *retval = NIL;
621  int retvallen = 0;
622  int outer_query_keys = list_length(root->query_pathkeys);
623  ListCell *i;
624 
625  foreach(i, subquery_pathkeys)
626  {
627  PathKey *sub_pathkey = (PathKey *) lfirst(i);
628  EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
629  PathKey *best_pathkey = NULL;
630 
631  if (sub_eclass->ec_has_volatile)
632  {
633  /*
634  * If the sub_pathkey's EquivalenceClass is volatile, then it must
635  * have come from an ORDER BY clause, and we have to match it to
636  * that same targetlist entry.
637  */
638  TargetEntry *tle;
639 
640  if (sub_eclass->ec_sortref == 0) /* can't happen */
641  elog(ERROR, "volatile EquivalenceClass has no sortref");
642  tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
643  Assert(tle);
644  /* resjunk items aren't visible to outer query */
645  if (!tle->resjunk)
646  {
647  /* We can represent this sub_pathkey */
648  EquivalenceMember *sub_member;
649  Expr *outer_expr;
650  EquivalenceClass *outer_ec;
651 
652  Assert(list_length(sub_eclass->ec_members) == 1);
653  sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
654  outer_expr = (Expr *) makeVarFromTargetEntry(rel->relid, tle);
655 
656  /*
657  * Note: it might look funny to be setting sortref = 0 for a
658  * reference to a volatile sub_eclass. However, the
659  * expression is *not* volatile in the outer query: it's just
660  * a Var referencing whatever the subquery emitted. (IOW, the
661  * outer query isn't going to re-execute the volatile
662  * expression itself.) So this is okay. Likewise, it's
663  * correct to pass nullable_relids = NULL, because we're
664  * underneath any outer joins appearing in the outer query.
665  */
666  outer_ec =
668  outer_expr,
669  NULL,
670  sub_eclass->ec_opfamilies,
671  sub_member->em_datatype,
672  sub_eclass->ec_collation,
673  0,
674  rel->relids,
675  false);
676 
677  /*
678  * If we don't find a matching EC, sub-pathkey isn't
679  * interesting to the outer query
680  */
681  if (outer_ec)
682  best_pathkey =
684  outer_ec,
685  sub_pathkey->pk_opfamily,
686  sub_pathkey->pk_strategy,
687  sub_pathkey->pk_nulls_first);
688  }
689  }
690  else
691  {
692  /*
693  * Otherwise, the sub_pathkey's EquivalenceClass could contain
694  * multiple elements (representing knowledge that multiple items
695  * are effectively equal). Each element might match none, one, or
696  * more of the output columns that are visible to the outer query.
697  * This means we may have multiple possible representations of the
698  * sub_pathkey in the context of the outer query. Ideally we
699  * would generate them all and put them all into an EC of the
700  * outer query, thereby propagating equality knowledge up to the
701  * outer query. Right now we cannot do so, because the outer
702  * query's EquivalenceClasses are already frozen when this is
703  * called. Instead we prefer the one that has the highest "score"
704  * (number of EC peers, plus one if it matches the outer
705  * query_pathkeys). This is the most likely to be useful in the
706  * outer query.
707  */
708  int best_score = -1;
709  ListCell *j;
710 
711  foreach(j, sub_eclass->ec_members)
712  {
713  EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
714  Expr *sub_expr = sub_member->em_expr;
715  Oid sub_expr_type = sub_member->em_datatype;
716  Oid sub_expr_coll = sub_eclass->ec_collation;
717  ListCell *k;
718 
719  if (sub_member->em_is_child)
720  continue; /* ignore children here */
721 
722  foreach(k, subquery_tlist)
723  {
724  TargetEntry *tle = (TargetEntry *) lfirst(k);
725  Expr *tle_expr;
726  Expr *outer_expr;
727  EquivalenceClass *outer_ec;
728  PathKey *outer_pk;
729  int score;
730 
731  /* resjunk items aren't visible to outer query */
732  if (tle->resjunk)
733  continue;
734 
735  /*
736  * The targetlist entry is considered to match if it
737  * matches after sort-key canonicalization. That is
738  * needed since the sub_expr has been through the same
739  * process.
740  */
741  tle_expr = canonicalize_ec_expression(tle->expr,
742  sub_expr_type,
743  sub_expr_coll);
744  if (!equal(tle_expr, sub_expr))
745  continue;
746 
747  /*
748  * Build a representation of this targetlist entry as an
749  * outer Var.
750  */
751  outer_expr = (Expr *) makeVarFromTargetEntry(rel->relid,
752  tle);
753 
754  /* See if we have a matching EC for that */
755  outer_ec = get_eclass_for_sort_expr(root,
756  outer_expr,
757  NULL,
758  sub_eclass->ec_opfamilies,
759  sub_expr_type,
760  sub_expr_coll,
761  0,
762  rel->relids,
763  false);
764 
765  /*
766  * If we don't find a matching EC, this sub-pathkey isn't
767  * interesting to the outer query
768  */
769  if (!outer_ec)
770  continue;
771 
772  outer_pk = make_canonical_pathkey(root,
773  outer_ec,
774  sub_pathkey->pk_opfamily,
775  sub_pathkey->pk_strategy,
776  sub_pathkey->pk_nulls_first);
777  /* score = # of equivalence peers */
778  score = list_length(outer_ec->ec_members) - 1;
779  /* +1 if it matches the proper query_pathkeys item */
780  if (retvallen < outer_query_keys &&
781  list_nth(root->query_pathkeys, retvallen) == outer_pk)
782  score++;
783  if (score > best_score)
784  {
785  best_pathkey = outer_pk;
786  best_score = score;
787  }
788  }
789  }
790  }
791 
792  /*
793  * If we couldn't find a representation of this sub_pathkey, we're
794  * done (we can't use the ones to its right, either).
795  */
796  if (!best_pathkey)
797  break;
798 
799  /*
800  * Eliminate redundant ordering info; could happen if outer query
801  * equivalences subquery keys...
802  */
803  if (!pathkey_is_redundant(best_pathkey, retval))
804  {
805  retval = lappend(retval, best_pathkey);
806  retvallen++;
807  }
808  }
809 
810  return retval;
811 }
#define NIL
Definition: pg_list.h:69
List * query_pathkeys
Definition: relation.h:274
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2986
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:619
Var * makeVarFromTargetEntry(Index varno, TargetEntry *tle)
Definition: makefuncs.c:104
Index ec_sortref
Definition: relation.h:907
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:51
unsigned int Oid
Definition: postgres_ext.h:31
int pk_strategy
Definition: relation.h:977
bool resjunk
Definition: primnodes.h:1383
#define linitial(l)
Definition: pg_list.h:111
bool pk_nulls_first
Definition: relation.h:978
#define ERROR
Definition: elog.h:43
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:494
void * list_nth(const List *list, int n)
Definition: list.c:410
Relids relids
Definition: relation.h:612
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:128
TargetEntry * get_sortgroupref_tle(Index sortref, List *targetList)
Definition: tlist.c:348
Index relid
Definition: relation.h:640
List * lappend(List *list, void *datum)
Definition: list.c:128
List * ec_opfamilies
Definition: relation.h:896
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
Expr * expr
Definition: primnodes.h:1376
EquivalenceClass * pk_eclass
Definition: relation.h:975
static int list_length(const List *l)
Definition: pg_list.h:89
bool ec_has_volatile
Definition: relation.h:904
Oid pk_opfamily
Definition: relation.h:976
int i
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
List * ec_members
Definition: relation.h:898

◆ create_index_paths()

void create_index_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 230 of file indxpath.c.

References add_path(), Assert, RelOptInfo::baserestrictinfo, bms_equal_any(), bms_is_subset(), choose_bitmap_and(), consider_index_join_clauses(), RelOptInfo::consider_parallel, create_bitmap_heap_path(), create_partial_bitmap_paths(), forboth, generate_bitmap_or_paths(), get_bitmap_tree_required_outer(), get_index_paths(), get_loop_count(), INDEX_MAX_KEYS, RelOptInfo::indexlist, IndexOptInfo::indpred, lappend(), RelOptInfo::lateral_relids, lfirst, list_concat(), match_eclass_clauses_to_index(), match_join_clauses_to_index(), match_restriction_clauses_to_index(), MemSet, IndexOptInfo::ncolumns, NIL, IndexClauseSet::nonempty, IndexOptInfo::predOK, and RelOptInfo::relid.

Referenced by set_plain_rel_pathlist().

231 {
232  List *indexpaths;
233  List *bitindexpaths;
234  List *bitjoinpaths;
235  List *joinorclauses;
236  IndexClauseSet rclauseset;
237  IndexClauseSet jclauseset;
238  IndexClauseSet eclauseset;
239  ListCell *lc;
240 
241  /* Skip the whole mess if no indexes */
242  if (rel->indexlist == NIL)
243  return;
244 
245  /* Bitmap paths are collected and then dealt with at the end */
246  bitindexpaths = bitjoinpaths = joinorclauses = NIL;
247 
248  /* Examine each index in turn */
249  foreach(lc, rel->indexlist)
250  {
252 
253  /* Protect limited-size array in IndexClauseSets */
254  Assert(index->ncolumns <= INDEX_MAX_KEYS);
255 
256  /*
257  * Ignore partial indexes that do not match the query.
258  * (generate_bitmap_or_paths() might be able to do something with
259  * them, but that's of no concern here.)
260  */
261  if (index->indpred != NIL && !index->predOK)
262  continue;
263 
264  /*
265  * Identify the restriction clauses that can match the index.
266  */
267  MemSet(&rclauseset, 0, sizeof(rclauseset));
268  match_restriction_clauses_to_index(rel, index, &rclauseset);
269 
270  /*
271  * Build index paths from the restriction clauses. These will be
272  * non-parameterized paths. Plain paths go directly to add_path(),
273  * bitmap paths are added to bitindexpaths to be handled below.
274  */
275  get_index_paths(root, rel, index, &rclauseset,
276  &bitindexpaths);
277 
278  /*
279  * Identify the join clauses that can match the index. For the moment
280  * we keep them separate from the restriction clauses. Note that this
281  * step finds only "loose" join clauses that have not been merged into
282  * EquivalenceClasses. Also, collect join OR clauses for later.
283  */
284  MemSet(&jclauseset, 0, sizeof(jclauseset));
285  match_join_clauses_to_index(root, rel, index,
286  &jclauseset, &joinorclauses);
287 
288  /*
289  * Look for EquivalenceClasses that can generate joinclauses matching
290  * the index.
291  */
292  MemSet(&eclauseset, 0, sizeof(eclauseset));
293  match_eclass_clauses_to_index(root, index,
294  &eclauseset);
295 
296  /*
297  * If we found any plain or eclass join clauses, build parameterized
298  * index paths using them.
299  */
300  if (jclauseset.nonempty || eclauseset.nonempty)
301  consider_index_join_clauses(root, rel, index,
302  &rclauseset,
303  &jclauseset,
304  &eclauseset,
305  &bitjoinpaths);
306  }
307 
308  /*
309  * Generate BitmapOrPaths for any suitable OR-clauses present in the
310  * restriction list. Add these to bitindexpaths.
311  */
312  indexpaths = generate_bitmap_or_paths(root, rel,
313  rel->baserestrictinfo, NIL);
314  bitindexpaths = list_concat(bitindexpaths, indexpaths);
315 
316  /*
317  * Likewise, generate BitmapOrPaths for any suitable OR-clauses present in
318  * the joinclause list. Add these to bitjoinpaths.
319  */
320  indexpaths = generate_bitmap_or_paths(root, rel,
321  joinorclauses, rel->baserestrictinfo);
322  bitjoinpaths = list_concat(bitjoinpaths, indexpaths);
323 
324  /*
325  * If we found anything usable, generate a BitmapHeapPath for the most
326  * promising combination of restriction bitmap index paths. Note there
327  * will be only one such path no matter how many indexes exist. This
328  * should be sufficient since there's basically only one figure of merit
329  * (total cost) for such a path.
330  */
331  if (bitindexpaths != NIL)
332  {
333  Path *bitmapqual;
334  BitmapHeapPath *bpath;
335 
336  bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
337  bpath = create_bitmap_heap_path(root, rel, bitmapqual,
338  rel->lateral_relids, 1.0, 0);
339  add_path(rel, (Path *) bpath);
340 
341  /* create a partial bitmap heap path */
342  if (rel->consider_parallel && rel->lateral_relids == NULL)
343  create_partial_bitmap_paths(root, rel, bitmapqual);
344  }
345 
346  /*
347  * Likewise, if we found anything usable, generate BitmapHeapPaths for the
348  * most promising combinations of join bitmap index paths. Our strategy
349  * is to generate one such path for each distinct parameterization seen
350  * among the available bitmap index paths. This may look pretty
351  * expensive, but usually there won't be very many distinct
352  * parameterizations. (This logic is quite similar to that in
353  * consider_index_join_clauses, but we're working with whole paths not
354  * individual clauses.)
355  */
356  if (bitjoinpaths != NIL)
357  {
358  List *path_outer;
359  List *all_path_outers;
360  ListCell *lc;
361 
362  /*
363  * path_outer holds the parameterization of each path in bitjoinpaths
364  * (to save recalculating that several times), while all_path_outers
365  * holds all distinct parameterization sets.
366  */
367  path_outer = all_path_outers = NIL;
368  foreach(lc, bitjoinpaths)
369  {
370  Path *path = (Path *) lfirst(lc);
371  Relids required_outer;
372 
373  required_outer = get_bitmap_tree_required_outer(path);
374  path_outer = lappend(path_outer, required_outer);
375  if (!bms_equal_any(required_outer, all_path_outers))
376  all_path_outers = lappend(all_path_outers, required_outer);
377  }
378 
379  /* Now, for each distinct parameterization set ... */
380  foreach(lc, all_path_outers)
381  {
382  Relids max_outers = (Relids) lfirst(lc);
383  List *this_path_set;
384  Path *bitmapqual;
385  Relids required_outer;
386  double loop_count;
387  BitmapHeapPath *bpath;
388  ListCell *lcp;
389  ListCell *lco;
390 
391  /* Identify all the bitmap join paths needing no more than that */
392  this_path_set = NIL;
393  forboth(lcp, bitjoinpaths, lco, path_outer)
394  {
395  Path *path = (Path *) lfirst(lcp);
396  Relids p_outers = (Relids) lfirst(lco);
397 
398  if (bms_is_subset(p_outers, max_outers))
399  this_path_set = lappend(this_path_set, path);
400  }
401 
402  /*
403  * Add in restriction bitmap paths, since they can be used
404  * together with any join paths.
405  */
406  this_path_set = list_concat(this_path_set, bitindexpaths);
407 
408  /* Select best AND combination for this parameterization */
409  bitmapqual = choose_bitmap_and(root, rel, this_path_set);
410 
411  /* And push that path into the mix */
412  required_outer = get_bitmap_tree_required_outer(bitmapqual);
413  loop_count = get_loop_count(root, rel->relid, required_outer);
414  bpath = create_bitmap_heap_path(root, rel, bitmapqual,
415  required_outer, loop_count, 0);
416  add_path(rel, (Path *) bpath);
417  }
418  }
419 }
#define NIL
Definition: pg_list.h:69
bool predOK
Definition: relation.h:788
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:180
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
bool nonempty
Definition: indxpath.c:58
List * baserestrictinfo
Definition: relation.h:672
#define MemSet(start, val, len)
Definition: c.h:908
List * list_concat(List *list1, List *list2)
Definition: list.c:321
Definition: type.h:89
static bool bms_equal_any(Relids relids, List *relids_list)
Definition: indxpath.c:706
Relids lateral_relids
Definition: relation.h:637
static void match_eclass_clauses_to_index(PlannerInfo *root, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition: indxpath.c:2156
static void get_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauses, List **bitindexpaths)
Definition: indxpath.c:735
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:374
static Path * choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
Definition: indxpath.c:1370
int ncolumns
Definition: relation.h:763
Index relid
Definition: relation.h:640
Bitmapset * Relids
Definition: relation.h:29
List * lappend(List *list, void *datum)
Definition: list.c:128
static double get_loop_count(PlannerInfo *root, Index cur_relid, Relids outer_relids)
Definition: indxpath.c:1974
static void match_restriction_clauses_to_index(RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition: indxpath.c:2112
static List * generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel, List *clauses, List *other_clauses)
Definition: indxpath.c:1263
List * indexlist
Definition: relation.h:649
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
#define INDEX_MAX_KEYS
bool consider_parallel
Definition: relation.h:620
static void match_join_clauses_to_index(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauseset, List **joinorclauses)
Definition: indxpath.c:2126
static Relids get_bitmap_tree_required_outer(Path *bitmapqual)
Definition: indxpath.c:1747
List * indpred
Definition: relation.h:778
void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
Definition: allpaths.c:3399
Definition: pg_list.h:45
BitmapHeapPath * create_bitmap_heap_path(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual, Relids required_outer, double loop_count, int parallel_degree)
Definition: pathnode.c:1077
static void consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, IndexClauseSet *jclauseset, IndexClauseSet *eclauseset, List **bitindexpaths)
Definition: indxpath.c:437

◆ create_partial_bitmap_paths()

void create_partial_bitmap_paths ( PlannerInfo root,
RelOptInfo rel,
Path bitmapqual 
)

Definition at line 3399 of file allpaths.c.

References add_partial_path(), compute_bitmap_pages(), compute_parallel_worker(), create_bitmap_heap_path(), RelOptInfo::lateral_relids, and max_parallel_workers_per_gather.

Referenced by create_index_paths().

3401 {
3402  int parallel_workers;
3403  double pages_fetched;
3404 
3405  /* Compute heap pages for bitmap heap scan */
3406  pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
3407  NULL, NULL);
3408 
3409  parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
3411 
3412  if (parallel_workers <= 0)
3413  return;
3414 
3415  add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
3416  bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
3417 }
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:3435
Relids lateral_relids
Definition: relation.h:637
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:762
int max_parallel_workers_per_gather
Definition: costsize.c:123
double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, int loop_count, Cost *cost, double *tuple)
Definition: costsize.c:5383
BitmapHeapPath * create_bitmap_heap_path(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual, Relids required_outer, double loop_count, int parallel_degree)
Definition: pathnode.c:1077

◆ create_tidscan_paths()

void create_tidscan_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 253 of file tidpath.c.

References add_path(), create_tidscan_path(), RelOptInfo::lateral_relids, and TidQualFromBaseRestrictinfo().

Referenced by set_plain_rel_pathlist().

254 {
255  Relids required_outer;
256  List *tidquals;
257 
258  /*
259  * We don't support pushing join clauses into the quals of a tidscan, but
260  * it could still have required parameterization due to LATERAL refs in
261  * its tlist.
262  */
263  required_outer = rel->lateral_relids;
264 
265  tidquals = TidQualFromBaseRestrictinfo(rel);
266 
267  if (tidquals)
268  add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
269  required_outer));
270 }
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
static List * TidQualFromBaseRestrictinfo(RelOptInfo *rel)
Definition: tidpath.c:223
Relids lateral_relids
Definition: relation.h:637
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1182
Definition: pg_list.h:45

◆ eclass_useful_for_merging()

bool eclass_useful_for_merging ( PlannerInfo root,
EquivalenceClass eclass,
RelOptInfo rel 
)

Definition at line 2436 of file equivclass.c.

References Assert, bms_is_empty(), bms_is_subset(), bms_overlap(), EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_relids, EquivalenceMember::em_is_child, EquivalenceMember::em_relids, IS_OTHER_REL, lfirst, list_length(), RelOptInfo::relids, and RelOptInfo::top_parent_relids.

Referenced by get_useful_ecs_for_relation(), and pathkeys_useful_for_merging().

2439 {
2440  Relids relids;
2441  ListCell *lc;
2442 
2443  Assert(!eclass->ec_merged);
2444 
2445  /*
2446  * Won't generate joinclauses if const or single-member (the latter test
2447  * covers the volatile case too)
2448  */
2449  if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
2450  return false;
2451 
2452  /*
2453  * Note we don't test ec_broken; if we did, we'd need a separate code path
2454  * to look through ec_sources. Checking the members anyway is OK as a
2455  * possibly-overoptimistic heuristic.
2456  */
2457 
2458  /* If specified rel is a child, we must consider the topmost parent rel */
2459  if (IS_OTHER_REL(rel))
2460  {
2462  relids = rel->top_parent_relids;
2463  }
2464  else
2465  relids = rel->relids;
2466 
2467  /* If rel already includes all members of eclass, no point in searching */
2468  if (bms_is_subset(eclass->ec_relids, relids))
2469  return false;
2470 
2471  /* To join, we need a member not in the given rel */
2472  foreach(lc, eclass->ec_members)
2473  {
2474  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
2475 
2476  if (cur_em->em_is_child)
2477  continue; /* ignore children here */
2478 
2479  if (!bms_overlap(cur_em->em_relids, relids))
2480  return true;
2481  }
2482 
2483  return false;
2484 }
#define IS_OTHER_REL(rel)
Definition: relation.h:600
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:374
Relids ec_relids
Definition: relation.h:901
Relids relids
Definition: relation.h:612
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:729
Relids em_relids
Definition: relation.h:947
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
static int list_length(const List *l)
Definition: pg_list.h:89
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:509
struct EquivalenceClass * ec_merged
Definition: relation.h:910
List * ec_members
Definition: relation.h:898
Relids top_parent_relids
Definition: relation.h:681

◆ expand_indexqual_conditions()

void expand_indexqual_conditions ( IndexOptInfo index,
List indexclauses,
List indexclausecols,
List **  indexquals_p,
List **  indexqualcols_p 
)

Definition at line 3551 of file indxpath.c.

References IndexOptInfo::amsearchnulls, Assert, RestrictInfo::clause, elog, ERROR, expand_boolean_index_clause(), expand_indexqual_opclause(), expand_indexqual_rowcompare(), forboth, IndexOptInfo::indexcollations, is_opclause, IsA, lappend(), lappend_int(), lfirst, lfirst_int, list_concat(), list_length(), make_simple_restrictinfo, NIL, nodeTag, and IndexOptInfo::opfamily.

Referenced by create_index_path().

3554 {
3555  List *indexquals = NIL;
3556  List *indexqualcols = NIL;
3557  ListCell *lcc,
3558  *lci;
3559 
3560  forboth(lcc, indexclauses, lci, indexclausecols)
3561  {
3562  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcc);
3563  int indexcol = lfirst_int(lci);
3564  Expr *clause = rinfo->clause;
3565  Oid curFamily;
3566  Oid curCollation;
3567 
3568  Assert(indexcol < index->nkeycolumns);
3569 
3570  curFamily = index->opfamily[indexcol];
3571  curCollation = index->indexcollations[indexcol];
3572 
3573  /* First check for boolean cases */
3574  if (IsBooleanOpfamily(curFamily))
3575  {
3576  Expr *boolqual;
3577 
3578  boolqual = expand_boolean_index_clause((Node *) clause,
3579  indexcol,
3580  index);
3581  if (boolqual)
3582  {
3583  indexquals = lappend(indexquals,
3584  make_simple_restrictinfo(boolqual));
3585  indexqualcols = lappend_int(indexqualcols, indexcol);
3586  continue;
3587  }
3588  }
3589 
3590  /*
3591  * Else it must be an opclause (usual case), ScalarArrayOp,
3592  * RowCompare, or NullTest
3593  */
3594  if (is_opclause(clause))
3595  {
3596  indexquals = list_concat(indexquals,
3598  curFamily,
3599  curCollation));
3600  /* expand_indexqual_opclause can produce multiple clauses */
3601  while (list_length(indexqualcols) < list_length(indexquals))
3602  indexqualcols = lappend_int(indexqualcols, indexcol);
3603  }
3604  else if (IsA(clause, ScalarArrayOpExpr))
3605  {
3606  /* no extra work at this time */
3607  indexquals = lappend(indexquals, rinfo);
3608  indexqualcols = lappend_int(indexqualcols, indexcol);
3609  }
3610  else if (IsA(clause, RowCompareExpr))
3611  {
3612  indexquals = lappend(indexquals,
3614  index,
3615  indexcol));
3616  indexqualcols = lappend_int(indexqualcols, indexcol);
3617  }
3618  else if (IsA(clause, NullTest))
3619  {
3620  Assert(index->amsearchnulls);
3621  indexquals = lappend(indexquals, rinfo);
3622  indexqualcols = lappend_int(indexqualcols, indexcol);
3623  }
3624  else
3625  elog(ERROR, "unsupported indexqual type: %d",
3626  (int) nodeTag(clause));
3627  }
3628 
3629  *indexquals_p = indexquals;
3630  *indexqualcols_p = indexqualcols;
3631 }
#define NIL
Definition: pg_list.h:69
#define IsA(nodeptr, _type_)
Definition: nodes.h:568
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:180
Oid * indexcollations
Definition: relation.h:767
Definition: nodes.h:517
List * list_concat(List *list1, List *list2)
Definition: list.c:321
unsigned int Oid
Definition: postgres_ext.h:31
#define ERROR
Definition: elog.h:43
#define is_opclause(clause)
Definition: clauses.h:20
#define lfirst_int(lc)
Definition: pg_list.h:107
static Expr * expand_boolean_index_clause(Node *clause, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:3641
List * lappend_int(List *list, int datum)
Definition: list.c:146
List * lappend(List *list, void *datum)
Definition: list.c:128
Expr * clause
Definition: relation.h:1880
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
static RestrictInfo * expand_indexqual_rowcompare(RestrictInfo *rinfo, IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3801
static int list_length(const List *l)
Definition: pg_list.h:89
#define nodeTag(nodeptr)
Definition: nodes.h:522
Oid * opfamily
Definition: relation.h:768
#define elog
Definition: elog.h:219
bool amsearchnulls
Definition: relation.h:797
static List * expand_indexqual_opclause(RestrictInfo *rinfo, Oid opfamily, Oid idxcollation)
Definition: indxpath.c:3707
Definition: pg_list.h:45
#define make_simple_restrictinfo(clause)
Definition: restrictinfo.h:21

◆ exprs_known_equal()

bool exprs_known_equal ( PlannerInfo root,
Node item1,
Node item2 
)

Definition at line 1983 of file equivclass.c.

References EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, PlannerInfo::eq_classes, equal(), and lfirst.

Referenced by add_unique_group_var().

1984 {
1985  ListCell *lc1;
1986 
1987  foreach(lc1, root->eq_classes)
1988  {
1989  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
1990  bool item1member = false;
1991  bool item2member = false;
1992  ListCell *lc2;
1993 
1994  /* Never match to a volatile EC */
1995  if (ec->ec_has_volatile)
1996  continue;
1997 
1998  foreach(lc2, ec->ec_members)
1999  {
2001 
2002  if (em->em_is_child)
2003  continue; /* ignore children here */
2004  if (equal(item1, em->em_expr))
2005  item1member = true;
2006  else if (equal(item2, em->em_expr))
2007  item2member = true;
2008  /* Exit as soon as equality is proven */
2009  if (item1member && item2member)
2010  return true;
2011  }
2012  }
2013  return false;
2014 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2986
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:249
bool ec_has_volatile
Definition: relation.h:904
List * ec_members
Definition: relation.h:898

◆ find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1011 of file pathkeys.c.

References i, 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().

1014 {
1015  List *mergeclauses = NIL;
1016  ListCell *i;
1017 
1018  /* make sure we have eclasses cached in the clauses */
1019  foreach(i, restrictinfos)
1020  {
1021  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1022 
1023  update_mergeclause_eclasses(root, rinfo);
1024  }
1025 
1026  foreach(i, pathkeys)
1027  {
1028  PathKey *pathkey = (PathKey *) lfirst(i);
1029  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1030  List *matched_restrictinfos = NIL;
1031  ListCell *j;
1032 
1033  /*----------
1034  * A mergejoin clause matches a pathkey if it has the same EC.
1035  * If there are multiple matching clauses, take them all. In plain
1036  * inner-join scenarios we expect only one match, because
1037  * equivalence-class processing will have removed any redundant
1038  * mergeclauses. However, in outer-join scenarios there might be
1039  * multiple matches. An example is
1040  *
1041  * select * from a full join b
1042  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1043  *
1044  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1045  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1046  * we *must* do so or we will be unable to form a valid plan.
1047  *
1048  * We expect that the given pathkeys list is canonical, which means
1049  * no two members have the same EC, so it's not possible for this
1050  * code to enter the same mergeclause into the result list twice.
1051  *
1052  * It's possible that multiple matching clauses might have different
1053  * ECs on the other side, in which case the order we put them into our
1054  * result makes a difference in the pathkeys required for the inner
1055  * input rel. However this routine hasn't got any info about which
1056  * order would be best, so we don't worry about that.
1057  *
1058  * It's also possible that the selected mergejoin clauses produce
1059  * a noncanonical ordering of pathkeys for the inner side, ie, we
1060  * might select clauses that reference b.v1, b.v2, b.v1 in that
1061  * order. This is not harmful in itself, though it suggests that
1062  * the clauses are partially redundant. Since the alternative is
1063  * to omit mergejoin clauses and thereby possibly fail to generate a
1064  * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1065  * has to delete duplicates when it constructs the inner pathkeys
1066  * list, and we also have to deal with such cases specially in
1067  * create_mergejoin_plan().
1068  *----------
1069  */
1070  foreach(j, restrictinfos)
1071  {
1072  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1073  EquivalenceClass *clause_ec;
1074 
1075  clause_ec = rinfo->outer_is_left ?
1076  rinfo->left_ec : rinfo->right_ec;
1077  if (clause_ec == pathkey_ec)
1078  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1079  }
1080 
1081  /*
1082  * If we didn't find a mergeclause, we're done --- any additional
1083  * sort-key positions in the pathkeys are useless. (But we can still
1084  * mergejoin if we found at least one mergeclause.)
1085  */
1086  if (matched_restrictinfos == NIL)
1087  break;
1088 
1089  /*
1090  * If we did find usable mergeclause(s) for this sort-key position,
1091  * add them to result list.
1092  */
1093  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1094  }
1095 
1096  return mergeclauses;
1097 }
#define NIL
Definition: pg_list.h:69
List * list_concat(List *list1, List *list2)
Definition: list.c:321
EquivalenceClass * right_ec
Definition: relation.h:1929
bool outer_is_left
Definition: relation.h:1935
List * lappend(List *list, void *datum)
Definition: list.c:128
#define lfirst(lc)
Definition: pg_list.h:106
EquivalenceClass * pk_eclass
Definition: relation.h:975
EquivalenceClass * left_ec
Definition: relation.h:1928
int i
Definition: pg_list.h:45
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:977

◆ generate_base_implied_equalities()

void generate_base_implied_equalities ( PlannerInfo root)

Definition at line 800 of file equivclass.c.

References Assert, EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, PlannerInfo::eq_classes, generate_base_implied_equalities_broken(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), RelOptInfo::has_eclass_joins, has_relevant_eclass_joinclause(), lfirst, list_length(), PlannerInfo::simple_rel_array, and PlannerInfo::simple_rel_array_size.

Referenced by query_planner().

801 {
802  ListCell *lc;
803  Index rti;
804 
805  foreach(lc, root->eq_classes)
806  {
808 
809  Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
810  Assert(!ec->ec_broken); /* not yet anyway... */
811 
812  /* Single-member ECs won't generate any deductions */
813  if (list_length(ec->ec_members) <= 1)
814  continue;
815 
816  if (ec->ec_has_const)
818  else
820 
821  /* Recover if we failed to generate required derived clauses */
822  if (ec->ec_broken)
824  }
825 
826  /*
827  * This is also a handy place to mark base rels (which should all exist by
828  * now) with flags showing whether they have pending eclass joins.
829  */
830  for (rti = 1; rti < root->simple_rel_array_size; rti++)
831  {
832  RelOptInfo *brel = root->simple_rel_array[rti];
833 
834  if (brel == NULL)
835  continue;
836 
838  }
839 }
bool has_eclass_joins
Definition: relation.h:678
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:922
static void generate_base_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1014
struct RelOptInfo ** simple_rel_array
Definition: relation.h:193
bool has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
Definition: equivclass.c:2397
int simple_rel_array_size
Definition: relation.h:194
unsigned int Index
Definition: c.h:442
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:249
static int list_length(const List *l)
Definition: pg_list.h:89
static void generate_base_implied_equalities_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:845
struct EquivalenceClass * ec_merged
Definition: relation.h:910
List * ec_members
Definition: relation.h:898

◆ generate_gather_paths()

void generate_gather_paths ( PlannerInfo root,
RelOptInfo rel,
bool  override_rows 
)

Definition at line 2541 of file allpaths.c.

References add_path(), create_gather_merge_path(), create_gather_path(), lfirst, linitial, NIL, Path::parallel_workers, RelOptInfo::partial_pathlist, GatherMergePath::path, Path::pathkeys, RelOptInfo::reltarget, Path::rows, and subpath().

Referenced by apply_scanjoin_target_to_paths(), gather_grouping_paths(), merge_clump(), set_rel_pathlist(), and standard_join_search().

2542 {
2543  Path *cheapest_partial_path;
2544  Path *simple_gather_path;
2545  ListCell *lc;
2546  double rows;
2547  double *rowsp = NULL;
2548 
2549  /* If there are no partial paths, there's nothing to do here. */
2550  if (rel->partial_pathlist == NIL)
2551  return;
2552 
2553  /* Should we override the rel's rowcount estimate? */
2554  if (override_rows)
2555  rowsp = &rows;
2556 
2557  /*
2558  * The output of Gather is always unsorted, so there's only one partial
2559  * path of interest: the cheapest one. That will be the one at the front
2560  * of partial_pathlist because of the way add_partial_path works.
2561  */
2562  cheapest_partial_path = linitial(rel->partial_pathlist);
2563  rows =
2564  cheapest_partial_path->rows * cheapest_partial_path->parallel_workers;
2565  simple_gather_path = (Path *)
2566  create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
2567  NULL, rowsp);
2568  add_path(rel, simple_gather_path);
2569 
2570  /*
2571  * For each useful ordering, we can consider an order-preserving Gather
2572  * Merge.
2573  */
2574  foreach(lc, rel->partial_pathlist)
2575  {
2576  Path *subpath = (Path *) lfirst(lc);
2577  GatherMergePath *path;
2578 
2579  if (subpath->pathkeys == NIL)
2580  continue;
2581 
2582  rows = subpath->rows * subpath->parallel_workers;
2583  path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
2584  subpath->pathkeys, NULL, rowsp);
2585  add_path(rel, &path->path);
2586  }
2587 }
#define NIL
Definition: pg_list.h:69
GatherPath * create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, Relids required_outer, double *rows)
Definition: pathnode.c:1826
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
int parallel_workers
Definition: relation.h:1085
List * partial_pathlist
Definition: relation.h:628
#define linitial(l)
Definition: pg_list.h:111
GatherMergePath * create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, List *pathkeys, Relids required_outer, double *rows)
Definition: pathnode.c:1735
List * pathkeys
Definition: relation.h:1092
#define lfirst(lc)
Definition: pg_list.h:106
double rows
Definition: relation.h:1088
struct PathTarget * reltarget
Definition: relation.h:623
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:234

◆ generate_implied_equalities_for_column()

List* generate_implied_equalities_for_column ( PlannerInfo root,
RelOptInfo rel,
ec_matches_callback_type  callback,
void *  callback_arg,
Relids  prohibited_rels 
)

Definition at line 2212 of file equivclass.c.

References Assert, bms_equal(), bms_is_subset(), bms_overlap(), callback(), create_join_clause(), EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceMember::em_datatype, EquivalenceMember::em_is_child, EquivalenceMember::em_relids, PlannerInfo::eq_classes, find_childrel_parents(), IS_SIMPLE_REL, lappend(), lfirst, list_length(), NIL, OidIsValid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, and select_equality_operator().

Referenced by match_eclass_clauses_to_index(), and postgresGetForeignPaths().

2217 {
2218  List *result = NIL;
2219  bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
2220  Relids parent_relids;
2221  ListCell *lc1;
2222 
2223  /* Indexes are available only on base or "other" member relations. */
2224  Assert(IS_SIMPLE_REL(rel));
2225 
2226  /* If it's a child rel, we'll need to know what its parent(s) are */
2227  if (is_child_rel)
2228  parent_relids = find_childrel_parents(root, rel);
2229  else
2230  parent_relids = NULL; /* not used, but keep compiler quiet */
2231 
2232  foreach(lc1, root->eq_classes)
2233  {
2234  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
2235  EquivalenceMember *cur_em;
2236  ListCell *lc2;
2237 
2238  /*
2239  * Won't generate joinclauses if const or single-member (the latter
2240  * test covers the volatile case too)
2241  */
2242  if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
2243  continue;
2244 
2245  /*
2246  * No point in searching if rel not mentioned in eclass (but we can't
2247  * tell that for a child rel).
2248  */
2249  if (!is_child_rel &&
2250  !bms_is_subset(rel->relids, cur_ec->ec_relids))
2251  continue;
2252 
2253  /*
2254  * Scan members, looking for a match to the target column. Note that
2255  * child EC members are considered, but only when they belong to the
2256  * target relation. (Unlike regular members, the same expression
2257  * could be a child member of more than one EC. Therefore, it's
2258  * potentially order-dependent which EC a child relation's target
2259  * column gets matched to. This is annoying but it only happens in
2260  * corner cases, so for now we live with just reporting the first
2261  * match. See also get_eclass_for_sort_expr.)
2262  */
2263  cur_em = NULL;
2264  foreach(lc2, cur_ec->ec_members)
2265  {
2266  cur_em = (EquivalenceMember *) lfirst(lc2);
2267  if (bms_equal(cur_em->em_relids, rel->relids) &&
2268  callback(root, rel, cur_ec, cur_em, callback_arg))
2269  break;
2270  cur_em = NULL;
2271  }
2272 
2273  if (!cur_em)
2274  continue;
2275 
2276  /*
2277  * Found our match. Scan the other EC members and attempt to generate
2278  * joinclauses.
2279  */
2280  foreach(lc2, cur_ec->ec_members)
2281  {
2282  EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
2283  Oid eq_op;
2284  RestrictInfo *rinfo;
2285 
2286  if (other_em->em_is_child)
2287  continue; /* ignore children here */
2288 
2289  /* Make sure it'll be a join to a different rel */
2290  if (other_em == cur_em ||
2291  bms_overlap(other_em->em_relids, rel->relids))
2292  continue;
2293 
2294  /* Forget it if caller doesn't want joins to this rel */
2295  if (bms_overlap(other_em->em_relids, prohibited_rels))
2296  continue;
2297 
2298  /*
2299  * Also, if this is a child rel, avoid generating a useless join
2300  * to its parent rel(s).
2301  */
2302  if (is_child_rel &&
2303  bms_overlap(parent_relids, other_em->em_relids))
2304  continue;
2305 
2306  eq_op = select_equality_operator(cur_ec,
2307  cur_em->em_datatype,
2308  other_em->em_datatype);
2309  if (!OidIsValid(eq_op))
2310  continue;
2311 
2312  /* set parent_ec to mark as redundant with other joinclauses */
2313  rinfo = create_join_clause(root, cur_ec, eq_op,
2314  cur_em, other_em,
2315  cur_ec);
2316 
2317  result = lappend(result, rinfo);
2318  }
2319 
2320  /*
2321  * If somehow we failed to create any join clauses, we might as well
2322  * keep scanning the ECs for another match. But if we did make any,
2323  * we're done, because we don't want to return non-redundant clauses.
2324  */
2325  if (result)
2326  break;
2327  }
2328 
2329  return result;
2330 }
#define NIL
Definition: pg_list.h:69
static RestrictInfo * create_join_clause(PlannerInfo *root, EquivalenceClass *ec, Oid opno, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
Definition: equivclass.c:1419
RelOptKind reloptkind
Definition: relation.h:609
unsigned int Oid
Definition: postgres_ext.h:31
#define OidIsValid(objectId)
Definition: c.h:605
#define IS_SIMPLE_REL(rel)
Definition: relation.h:585
static void callback(struct sockaddr *addr, struct sockaddr *mask, void *unused)
Definition: test_ifaddrs.c:48
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:374
static Oid select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
Definition: equivclass.c:1384
Relids ec_relids
Definition: relation.h:901
Relids relids
Definition: relation.h:612
List * lappend(List *list, void *datum)
Definition: list.c:128
Relids em_relids
Definition: relation.h:947
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1226
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:249
static int list_length(const List *l)
Definition: pg_list.h:89
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:509
Definition: pg_list.h:45
List * ec_members
Definition: relation.h:898
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:153

◆ generate_join_implied_equalities()

List* generate_join_implied_equalities ( PlannerInfo root,
Relids  join_relids,
Relids  outer_relids,
RelOptInfo inner_rel 
)

Definition at line 1071 of file equivclass.c.

References PlannerInfo::eq_classes, and generate_join_implied_equalities_for_ecs().

Referenced by build_joinrel_restrictlist(), check_index_predicates(), get_baserel_parampathinfo(), get_joinrel_parampathinfo(), and reduce_unique_semijoins().

1075 {
1077  root->eq_classes,
1078  join_relids,
1079  outer_relids,
1080  inner_rel);
1081 }
List * generate_join_implied_equalities_for_ecs(PlannerInfo *root, List *eclasses, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1088
List * eq_classes
Definition: relation.h:249

◆ generate_join_implied_equalities_for_ecs()

List* generate_join_implied_equalities_for_ecs ( PlannerInfo root,
List eclasses,
Relids  join_relids,
Relids  outer_relids,
RelOptInfo inner_rel 
)

Definition at line 1088 of file equivclass.c.

References Assert, bms_is_empty(), bms_overlap(), bms_union(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), IS_OTHER_REL, lfirst, list_concat(), list_length(), NIL, RelOptInfo::relids, and RelOptInfo::top_parent_relids.

Referenced by generate_join_implied_equalities(), and get_joinrel_parampathinfo().

1093 {
1094  List *result = NIL;
1095  Relids inner_relids = inner_rel->relids;
1096  Relids nominal_inner_relids;
1097  Relids nominal_join_relids;
1098  ListCell *lc;
1099 
1100  /* If inner rel is a child, extra setup work is needed */
1101  if (IS_OTHER_REL(inner_rel))
1102  {
1103  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1104 
1105  /* Fetch relid set for the topmost parent rel */
1106  nominal_inner_relids = inner_rel->top_parent_relids;
1107  /* ECs will be marked with the parent's relid, not the child's */
1108  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1109  }
1110  else
1111  {
1112  nominal_inner_relids = inner_relids;
1113  nominal_join_relids = join_relids;
1114  }
1115 
1116  foreach(lc, eclasses)
1117  {
1119  List *sublist = NIL;
1120 
1121  /* ECs containing consts do not need any further enforcement */
1122  if (ec->ec_has_const)
1123  continue;
1124 
1125  /* Single-member ECs won't generate any deductions */
1126  if (list_length(ec->ec_members) <= 1)
1127  continue;
1128 
1129  /* We can quickly ignore any that don't overlap the join, too */
1130  if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1131  continue;
1132 
1133  if (!ec->ec_broken)
1135  ec,
1136  join_relids,
1137  outer_relids,
1138  inner_relids);
1139 
1140  /* Recover if we failed to generate required derived clauses */
1141  if (ec->ec_broken)
1143  ec,
1144  nominal_join_relids,
1145  outer_relids,
1146  nominal_inner_relids,
1147  inner_rel);
1148 
1149  result = list_concat(result, sublist);
1150  }
1151 
1152  return result;
1153 }
#define NIL
Definition: pg_list.h:69
#define IS_OTHER_REL(rel)
Definition: relation.h:600
List * list_concat(List *list1, List *list2)
Definition: list.c:321
static List * generate_join_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec, Relids nominal_join_relids, Relids outer_relids, Relids nominal_inner_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1335
Relids ec_relids
Definition: relation.h:901
Relids relids
Definition: relation.h:612
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1159
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:729
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
static int list_length(const List *l)
Definition: pg_list.h:89
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:509
Definition: pg_list.h:45
List * ec_members
Definition: relation.h:898
Relids top_parent_relids
Definition: relation.h:681

◆ generate_partitionwise_join_paths()

void generate_partitionwise_join_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 3523 of file allpaths.c.

References add_paths_to_append_rel(), Alias::aliasname, Assert, RelOptInfo::baserestrictinfo, bms_next_member(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_startup_path, RelOptInfo::cheapest_total_path, check_stack_depth(), RestrictInfo::clause, RangeTblEntry::eref, generate_partitionwise_join_paths(), i, JoinPath::innerjoinpath, MergePath::innersortkeys, IS_DUMMY_REL, IS_JOIN_REL, IS_PARTITIONED_REL, IsA, RelOptInfo::joininfo, JoinPath::joinrestrictinfo, lappend(), lfirst, list_free(), lnext, mark_dummy_rel(), MergePath::materialize_inner, NIL, nodeTag, RelOptInfo::nparts, JoinPath::outerjoinpath, MergePath::outersortkeys, Path::param_info, Path::parent, PlannerInfo::parse, RelOptInfo::part_rels, Path::pathkeys, RelOptInfo::pathlist, Path::pathtype, ParamPathInfo::ppi_req_outer, print_expr(), print_pathkeys(), RelOptInfo::relids, RelOptInfo::reltarget, RelOptInfo::rows, Path::rows, Query::rtable, set_cheapest(), PlannerInfo::simple_rte_array, Path::startup_cost, subpath(), T_AggPath, T_AppendPath, T_BitmapAndPath, T_BitmapHeapPath, T_BitmapOrPath, T_CteScan, T_ForeignPath, T_FunctionScan, T_GatherPath, T_GroupingSetsPath, T_GroupPath, T_HashPath, T_IndexPath, T_LimitPath, T_LockRowsPath, T_MaterialPath, T_MergeAppendPath, T_MergePath, T_MinMaxAggPath, T_ModifyTablePath, T_NestPath, T_Path, T_ProjectionPath, T_ProjectSetPath, T_RecursiveUnionPath, T_ResultPath, T_SampleScan, T_SeqScan, T_SetOpPath, T_SortPath, T_SubqueryScan, T_SubqueryScanPath, T_TableFuncScan, T_TidPath, T_UniquePath, T_UpperUniquePath, T_ValuesScan, T_WindowAggPath, T_WorkTableScan, Path::total_cost, and PathTarget::width.

Referenced by generate_partitionwise_join_paths(), merge_clump(), and standard_join_search().

3524 {
3525  List *live_children = NIL;
3526  int cnt_parts;
3527  int num_parts;
3528  RelOptInfo **part_rels;
3529 
3530  /* Handle only join relations here. */
3531  if (!IS_JOIN_REL(rel))
3532  return;
3533 
3534  /* We've nothing to do if the relation is not partitioned. */
3535  if (!IS_PARTITIONED_REL(rel))
3536  return;
3537 
3538  /* Guard against stack overflow due to overly deep partition hierarchy. */
3540 
3541  num_parts = rel->nparts;
3542  part_rels = rel->part_rels;
3543 
3544  /* Collect non-dummy child-joins. */
3545  for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
3546  {
3547  RelOptInfo *child_rel = part_rels[cnt_parts];
3548 
3549  Assert(child_rel != NULL);
3550 
3551  /* Add partitionwise join paths for partitioned child-joins. */
3552  generate_partitionwise_join_paths(root, child_rel);
3553 
3554  /* Dummy children will not be scanned, so ignore those. */
3555  if (IS_DUMMY_REL(child_rel))
3556  continue;
3557 
3558  set_cheapest(child_rel);
3559 
3560 #ifdef OPTIMIZER_DEBUG
3561  debug_print_rel(root, child_rel);
3562 #endif
3563 
3564  live_children = lappend(live_children, child_rel);
3565  }
3566 
3567  /* If all child-joins are dummy, parent join is also dummy. */
3568  if (!live_children)
3569  {
3570  mark_dummy_rel(rel);
3571  return;
3572  }
3573 
3574  /* Build additional paths for this rel from child-join paths. */
3575  add_paths_to_append_rel(root, rel, live_children);
3576  list_free(live_children);
3577 }
#define NIL
Definition: pg_list.h:69
void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
Definition: allpaths.c:1377
#define IS_PARTITIONED_REL(rel)
Definition: relation.h:706
#define IS_JOIN_REL(rel)
Definition: relation.h:590
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:3523
#define IS_DUMMY_REL(r)
Definition: relation.h:1317
void check_stack_depth(void)
Definition: postgres.c:3155
int nparts
Definition: relation.h:685
List * lappend(List *list, void *datum)
Definition: list.c:128
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:244
void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1215
#define Assert(condition)
Definition: c.h:699
struct RelOptInfo ** part_rels
Definition: relation.h:688
void list_free(List *list)
Definition: list.c:1133
Definition: pg_list.h:45

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

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

Referenced by build_minmax_path().

392 {
393  Path *matched_path = NULL;
394  ListCell *l;
395 
396  foreach(l, paths)
397  {
398  Path *path = (Path *) lfirst(l);
399 
400  /*
401  * Since cost comparison is a lot cheaper than pathkey comparison, do
402  * that first. (XXX is that still true?)
403  */
404  if (matched_path != NULL &&
405  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
406  continue;
407 
408  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
409  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
410  matched_path = path;
411  }
412  return matched_path;
413 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:374
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:317
List * pathkeys
Definition: relation.h:1092
#define lfirst(lc)
Definition: pg_list.h:106
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:117
#define PATH_REQ_OUTER(path)
Definition: relation.h:1097

◆ get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner ( List paths)

Definition at line 421 of file pathkeys.c.

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

422 {
423  ListCell *l;
424 
425  foreach(l, paths)
426  {
427  Path *innerpath = (Path *) lfirst(l);
428 
429  if (innerpath->parallel_safe &&
430  bms_is_empty(PATH_REQ_OUTER(innerpath)))
431  return innerpath;
432  }
433 
434  return NULL;
435 }
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:729
#define lfirst(lc)
Definition: pg_list.h:106
bool parallel_safe
Definition: relation.h:1084
#define PATH_REQ_OUTER(path)
Definition: relation.h:1097

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

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

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

347 {
348  Path *matched_path = NULL;
349  ListCell *l;
350 
351  foreach(l, paths)
352  {
353  Path *path = (Path *) lfirst(l);
354 
355  /*
356  * Since cost comparison is a lot cheaper than pathkey comparison, do
357  * that first. (XXX is that still true?)
358  */
359  if (matched_path != NULL &&
360  compare_path_costs(matched_path, path, cost_criterion) <= 0)
361  continue;
362 
363  if (require_parallel_safe && !path->parallel_safe)
364  continue;
365 
366  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
367  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
368  matched_path = path;
369  }
370  return matched_path;
371 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:374
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:71
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:317
List * pathkeys
Definition: relation.h:1092
#define lfirst(lc)
Definition: pg_list.h:106
bool parallel_safe
Definition: relation.h:1084
#define PATH_REQ_OUTER(path)
Definition: relation.h:1097

◆ get_eclass_for_sort_expr()

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 at line 619 of file equivclass.c.

References add_eq_member(), bms_equal(), bms_intersect(), canonicalize_ec_expression(), contain_agg_clause(), contain_volatile_functions(), contain_window_function(), copyObject, EquivalenceClass::ec_below_outer_join, EquivalenceClass::ec_broken, EquivalenceClass::ec_collation, EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_max_security, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, PlannerInfo::eq_classes, equal(), ERROR, expression_returns_set(), lappend(), lfirst, list_copy(), makeNode, MemoryContextSwitchTo(), NIL, PlannerInfo::planner_cxt, and pull_varnos().

Referenced by convert_subquery_pathkeys(), initialize_mergeclause_eclasses(), and make_pathkey_from_sortinfo().

628 {
629  Relids expr_relids;
630  EquivalenceClass *newec;
631  EquivalenceMember *newem;
632  ListCell *lc1;
633  MemoryContext oldcontext;
634 
635  /*
636  * Ensure the expression exposes the correct type and collation.
637  */
638  expr = canonicalize_ec_expression(expr, opcintype, collation);
639 
640  /*
641  * Get the precise set of nullable relids appearing in the expression.
642  */
643  expr_relids = pull_varnos((Node *) expr);
644  nullable_relids = bms_intersect(nullable_relids, expr_relids);
645 
646  /*
647  * Scan through the existing EquivalenceClasses for a match
648  */
649  foreach(lc1, root->eq_classes)
650  {
651  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
652  ListCell *lc2;
653 
654  /*
655  * Never match to a volatile EC, except when we are looking at another
656  * reference to the same volatile SortGroupClause.
657  */
658  if (cur_ec->ec_has_volatile &&
659  (sortref == 0 || sortref != cur_ec->ec_sortref))
660  continue;
661 
662  if (collation != cur_ec->ec_collation)
663  continue;
664  if (!equal(opfamilies, cur_ec->ec_opfamilies))
665  continue;
666 
667  foreach(lc2, cur_ec->ec_members)
668  {
669  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
670 
671  /*
672  * Ignore child members unless they match the request.
673  */
674  if (cur_em->em_is_child &&
675  !bms_equal(cur_em->em_relids, rel))
676  continue;
677 
678  /*
679  * If below an outer join, don't match constants: they're not as
680  * constant as they look.
681  */
682  if (cur_ec->ec_below_outer_join &&
683  cur_em->em_is_const)
684  continue;
685 
686  if (opcintype == cur_em->em_datatype &&
687  equal(expr, cur_em->em_expr))
688  return cur_ec; /* Match! */
689  }
690  }
691 
692  /* No match; does caller want a NULL result? */
693  if (!create_it)
694  return NULL;
695 
696  /*
697  * OK, build a new single-member EC
698  *
699  * Here, we must be sure that we construct the EC in the right context.
700  */
701  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
702 
703  newec = makeNode(EquivalenceClass);
704  newec->ec_opfamilies = list_copy(opfamilies);
705  newec->ec_collation = collation;
706  newec->ec_members = NIL;
707  newec->ec_sources = NIL;
708  newec->ec_derives = NIL;
709  newec->ec_relids = NULL;
710  newec->ec_has_const = false;
712  newec->ec_below_outer_join = false;
713  newec->ec_broken = false;
714  newec->ec_sortref = sortref;
715  newec->ec_min_security = UINT_MAX;
716  newec->ec_max_security = 0;
717  newec->ec_merged = NULL;
718 
719  if (newec->ec_has_volatile && sortref == 0) /* should not happen */
720  elog(ERROR, "volatile EquivalenceClass has no sortref");
721 
722  newem = add_eq_member(newec, copyObject(expr), expr_relids,
723  nullable_relids, false, opcintype);
724 
725  /*
726  * add_eq_member doesn't check for volatile functions, set-returning
727  * functions, aggregates, or window functions, but such could appear in
728  * sort expressions; so we have to check whether its const-marking was
729  * correct.
730  */
731  if (newec->ec_has_const)
732  {
733  if (newec->ec_has_volatile ||
734  expression_returns_set((Node *) expr) ||
735  contain_agg_clause((Node *) expr) ||
736  contain_window_function((Node *) expr))
737  {
738  newec->ec_has_const = false;
739  newem->em_is_const = false;
740  }
741  }
742 
743  root->eq_classes = lappend(root->eq_classes, newec);
744 
745  MemoryContextSwitchTo(oldcontext);
746 
747  return newec;
748 }
#define NIL
Definition: pg_list.h:69
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2986
Index ec_min_security
Definition: relation.h:908
List * ec_derives
Definition: relation.h:900
bool expression_returns_set(Node *clause)
Definition: nodeFuncs.c:670
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
List * list_copy(const List *oldlist)
Definition: list.c:1160
Index ec_sortref
Definition: relation.h:907
Definition: nodes.h:517
bool ec_below_outer_join
Definition: relation.h:905
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:958
Index ec_max_security
Definition: relation.h:909
#define ERROR
Definition: elog.h:43
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:494
List * ec_sources
Definition: relation.h:899
Relids ec_relids
Definition: relation.h:901
Relids pull_varnos(Node *node)
Definition: var.c:95
bool contain_window_function(Node *clause)
Definition: clauses.c:728
List * lappend(List *list, void *datum)
Definition: list.c:128
List * ec_opfamilies
Definition: relation.h:896
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:318
Relids em_relids
Definition: relation.h:947
#define makeNode(_type_)
Definition: nodes.h:565
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:249
bool ec_has_volatile
Definition: relation.h:904
bool contain_agg_clause(Node *clause)
Definition: clauses.c:418
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, Relids nullable_relids, bool is_child, Oid datatype)
Definition: equivclass.c:543
MemoryContext planner_cxt
Definition: relation.h:302
#define elog
Definition: elog.h:219
#define copyObject(obj)
Definition: nodes.h:630
struct EquivalenceClass * ec_merged
Definition: relation.h:910
List * ec_members
Definition: relation.h:898
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:153

◆ has_relevant_eclass_joinclause()

bool has_relevant_eclass_joinclause ( PlannerInfo root,
RelOptInfo rel1 
)

Definition at line 2397 of file equivclass.c.

References bms_is_subset(), bms_overlap(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, lfirst, list_length(), and RelOptInfo::relids.

Referenced by build_join_rel(), and generate_base_implied_equalities().

2398 {
2399  ListCell *lc1;
2400 
2401  foreach(lc1, root->eq_classes)
2402  {
2403  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2404 
2405  /*
2406  * Won't generate joinclauses if single-member (this test covers the
2407  * volatile case too)
2408  */
2409  if (list_length(ec->ec_members) <= 1)
2410  continue;
2411 
2412  /*
2413  * Per the comment in have_relevant_eclass_joinclause, it's sufficient
2414  * to find an EC that mentions both this rel and some other rel.
2415  */
2416  if (bms_overlap(rel1->relids, ec->ec_relids) &&
2417  !bms_is_subset(ec->ec_relids, rel1->relids))
2418  return true;
2419  }
2420 
2421  return false;
2422 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:374
Relids ec_relids
Definition: relation.h:901
Relids relids
Definition: relation.h:612
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:249
static int list_length(const List *l)
Definition: pg_list.h:89
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:509
List * ec_members
Definition: relation.h:898

◆ has_useful_pathkeys()

bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 1659 of file pathkeys.c.

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

Referenced by build_index_paths(), and set_append_rel_size().

1660 {
1661  if (rel->joininfo != NIL || rel->has_eclass_joins)
1662  return true; /* might be able to use pathkeys for merging */
1663  if (root->query_pathkeys != NIL)
1664  return true; /* might be able to use them for ordering */
1665  return false; /* definitely useless */
1666 }
bool has_eclass_joins
Definition: relation.h:678
#define NIL
Definition: pg_list.h:69
List * query_pathkeys
Definition: relation.h:274
List * joininfo
Definition: relation.h:676

◆ have_dangerous_phv()

bool have_dangerous_phv ( PlannerInfo root,
Relids  outer_relids,
Relids  inner_params 
)

Definition at line 1166 of file joinrels.c.

References bms_is_subset(), bms_overlap(), lfirst, PlaceHolderInfo::ph_eval_at, and PlannerInfo::placeholder_list.

Referenced by join_is_legal(), and try_nestloop_path().

1168 {
1169  ListCell *lc;
1170 
1171  foreach(lc, root->placeholder_list)
1172  {
1173  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1174 
1175  if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1176  continue; /* ignore, could not be a nestloop param */
1177  if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1178  continue; /* ignore, not relevant to this join */
1179  if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
1180  continue; /* safe, it can be eval'd within outerrel */
1181  /* Otherwise, it's potentially unsafe, so reject the join */
1182  return true;
1183  }
1184 
1185  /* OK to perform the join */
1186  return false;
1187 }
Relids ph_eval_at
Definition: relation.h:2194
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:374
#define lfirst(lc)
Definition: pg_list.h:106
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:509
List * placeholder_list
Definition: relation.h:270

◆ have_join_order_restriction()

bool have_join_order_restriction ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2 
)

Definition at line 933 of file joinrels.c.

References bms_is_subset(), bms_overlap(), RelOptInfo::direct_lateral_relids, has_legal_joinclause(), JOIN_FULL, PlannerInfo::join_info_list, SpecialJoinInfo::jointype, lfirst, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, PlaceHolderInfo::ph_eval_at, PlannerInfo::placeholder_list, and RelOptInfo::relids.

Referenced by desirable_join(), join_search_one_level(), and make_rels_by_clause_joins().

935 {
936  bool result = false;
937  ListCell *l;
938 
939  /*
940  * If either side has a direct lateral reference to the other, attempt the
941  * join regardless of outer-join considerations.
942  */
943  if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) ||
945  return true;
946 
947  /*
948  * Likewise, if both rels are needed to compute some PlaceHolderVar,
949  * attempt the join regardless of outer-join considerations. (This is not
950  * very desirable, because a PHV with a large eval_at set will cause a lot
951  * of probably-useless joins to be considered, but failing to do this can
952  * cause us to fail to construct a plan at all.)
953  */
954  foreach(l, root->placeholder_list)
955  {
956  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
957 
958  if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) &&
959  bms_is_subset(rel2->relids, phinfo->ph_eval_at))
960  return true;
961  }
962 
963  /*
964  * It's possible that the rels correspond to the left and right sides of a
965  * degenerate outer join, that is, one with no joinclause mentioning the
966  * non-nullable side; in which case we should force the join to occur.
967  *
968  * Also, the two rels could represent a clauseless join that has to be
969  * completed to build up the LHS or RHS of an outer join.
970  */
971  foreach(l, root->join_info_list)
972  {
973  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
974 
975  /* ignore full joins --- other mechanisms handle them */
976  if (sjinfo->jointype == JOIN_FULL)
977  continue;
978 
979  /* Can we perform the SJ with these rels? */
980  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
981  bms_is_subset(sjinfo->min_righthand, rel2->relids))
982  {
983  result = true;
984  break;
985  }
986  if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
987  bms_is_subset(sjinfo->min_righthand, rel1->relids))
988  {
989  result = true;
990  break;
991  }
992 
993  /*
994  * Might we need to join these rels to complete the RHS? We have to
995  * use "overlap" tests since either rel might include a lower SJ that
996  * has been proven to commute with this one.
997  */
998  if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
999  bms_overlap(sjinfo->min_righthand, rel2->relids))
1000  {
1001  result = true;
1002  break;
1003  }
1004 
1005  /* Likewise for the LHS. */
1006  if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
1007  bms_overlap(sjinfo->min_lefthand, rel2->relids))
1008  {
1009  result = true;
1010  break;
1011  }
1012  }
1013 
1014  /*
1015  * We do not force the join to occur if either input rel can legally be
1016  * joined to anything else using joinclauses. This essentially means that
1017  * clauseless bushy joins are put off as long as possible. The reason is
1018  * that when there is a join order restriction high up in the join tree
1019  * (that is, with many rels inside the LHS or RHS), we would otherwise
1020  * expend lots of effort considering very stupid join combinations within
1021  * its LHS or RHS.
1022  */
1023  if (result)
1024  {
1025  if (has_legal_joinclause(root, rel1) ||
1026  has_legal_joinclause(root, rel2))
1027  result = false;
1028  }
1029 
1030  return result;
1031 }
Relids ph_eval_at
Definition: relation.h:2194
List * join_info_list
Definition: relation.h:264
Relids min_righthand
Definition: relation.h:2067
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1102
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:374
Relids relids
Definition: relation.h:612
Relids direct_lateral_relids
Definition: relation.h:636
#define lfirst(lc)
Definition: pg_list.h:106
JoinType jointype
Definition: relation.h:2070
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:509
List * placeholder_list
Definition: relation.h:270
Relids min_lefthand
Definition: relation.h:2066

◆ have_partkey_equi_join()

bool have_partkey_equi_join ( RelOptInfo joinrel,
RelOptInfo rel1,
RelOptInfo rel2,
JoinType  jointype,
List restrictlist 
)

Definition at line 1418 of file joinrels.c.

References OpExpr::args, Assert, bms_is_subset(), RestrictInfo::can_join, RestrictInfo::clause, RestrictInfo::hashjoinoperator, is_opclause, IS_OUTER_JOIN, RestrictInfo::left_relids, lfirst_node, linitial, list_member_oid(), lsecond, match_expr_to_partition_keys(), RestrictInfo::mergeopfamilies, OidIsValid, op_in_opfamily(), op_strict(), OpExpr::opno, RelOptInfo::part_scheme, PARTITION_MAX_KEYS, PARTITION_STRATEGY_HASH, PartitionSchemeData::partnatts, PartitionSchemeData::partopfamily, RelOptInfo::relids, RestrictInfo::right_relids, RINFO_IS_PUSHED_DOWN, and PartitionSchemeData::strategy.

Referenced by build_joinrel_partition_info().

1421 {
1422  PartitionScheme part_scheme = rel1->part_scheme;
1423  ListCell *lc;
1424  int cnt_pks;
1425  bool pk_has_clause[PARTITION_MAX_KEYS];
1426  bool strict_op;
1427 
1428  /*
1429  * This function should be called when the joining relations have same
1430  * partitioning scheme.
1431  */
1432  Assert(rel1->part_scheme == rel2->part_scheme);
1433  Assert(part_scheme);
1434 
1435  memset(pk_has_clause, 0, sizeof(pk_has_clause));
1436  foreach(lc, restrictlist)
1437  {
1438  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1439  OpExpr *opexpr;
1440  Expr *expr1;
1441  Expr *expr2;
1442  int ipk1;
1443  int ipk2;
1444 
1445  /* If processing an outer join, only use its own join clauses. */
1446  if (IS_OUTER_JOIN(jointype) &&
1447  RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
1448  continue;
1449 
1450  /* Skip clauses which can not be used for a join. */
1451  if (!rinfo->can_join)
1452  continue;
1453 
1454  /* Skip clauses which are not equality conditions. */
1455  if (!rinfo->mergeopfamilies && !OidIsValid(rinfo->hashjoinoperator))
1456  continue;
1457 
1458  opexpr = (OpExpr *) rinfo->clause;
1459  Assert(is_opclause(opexpr));
1460 
1461  /*
1462  * The equi-join between partition keys is strict if equi-join between
1463  * at least one partition key is using a strict operator. See
1464  * explanation about outer join reordering identity 3 in
1465  * optimizer/README
1466  */
1467  strict_op = op_strict(opexpr->opno);
1468 
1469  /* Match the operands to the relation. */
1470  if (bms_is_subset(rinfo->left_relids, rel1->relids) &&
1471  bms_is_subset(rinfo->right_relids, rel2->relids))
1472  {
1473  expr1 = linitial(opexpr->args);
1474  expr2 = lsecond(opexpr->args);
1475  }
1476  else if (bms_is_subset(rinfo->left_relids, rel2->relids) &&
1477  bms_is_subset(rinfo->right_relids, rel1->relids))
1478  {
1479  expr1 = lsecond(opexpr->args);
1480  expr2 = linitial(opexpr->args);
1481  }
1482  else
1483  continue;
1484 
1485  /*
1486  * Only clauses referencing the partition keys are useful for
1487  * partitionwise join.
1488  */
1489  ipk1 = match_expr_to_partition_keys(expr1, rel1, strict_op);
1490  if (ipk1 < 0)
1491  continue;
1492  ipk2 = match_expr_to_partition_keys(expr2, rel2, strict_op);
1493  if (ipk2 < 0)
1494  continue;
1495 
1496  /*
1497  * If the clause refers to keys at different ordinal positions, it can
1498  * not be used for partitionwise join.
1499  */
1500  if (ipk1 != ipk2)
1501  continue;
1502 
1503  /*
1504  * The clause allows partitionwise join if only it uses the same
1505  * operator family as that specified by the partition key.
1506  */
1508  {
1509  if (!op_in_opfamily(rinfo->hashjoinoperator,
1510  part_scheme->partopfamily[ipk1]))
1511  continue;
1512  }
1513  else if (!list_member_oid(rinfo->mergeopfamilies,
1514  part_scheme->partopfamily[ipk1]))
1515  continue;
1516 
1517  /* Mark the partition key as having an equi-join clause. */
1518  pk_has_clause[ipk1] = true;
1519  }
1520 
1521  /* Check whether every partition key has an equi-join condition. */
1522  for (cnt_pks = 0; cnt_pks < part_scheme->partnatts; cnt_pks++)
1523  {
1524  if (!pk_has_clause[cnt_pks])
1525  return false;
1526  }
1527 
1528  return true;
1529 }
bool op_in_opfamily(Oid opno, Oid opfamily)
Definition: lsyscache.c:63
bool op_strict(Oid opno)
Definition: lsyscache.c:1266
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:730
#define PARTITION_MAX_KEYS
Relids left_relids
Definition: relation.h:1907
#define OidIsValid(objectId)
Definition: c.h:605
List * mergeopfamilies
Definition: relation.h:1925
#define lsecond(l)
Definition: pg_list.h:116
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: relation.h:1957
#define linitial(l)
Definition: pg_list.h:111
#define is_opclause(clause)
Definition: clauses.h:20
bool can_join
Definition: relation.h:1886
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:374
#define lfirst_node(type, lc)
Definition: pg_list.h:109
static int match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, bool strict_op)
Definition: joinrels.c:1536
Relids relids
Definition: relation.h:612
Expr * clause
Definition: relation.h:1880
#define PARTITION_STRATEGY_HASH
Definition: parsenodes.h:798
Relids right_relids
Definition: relation.h:1908
bool list_member_oid(const List *list, Oid datum)
Definition: list.c:505
#define Assert(condition)
Definition: c.h:699
Oid hashjoinoperator
Definition: relation.h:1938
PartitionScheme part_scheme
Definition: relation.h:684
Oid opno
Definition: primnodes.h:497
List * args
Definition: primnodes.h:503

◆ have_relevant_eclass_joinclause()

bool have_relevant_eclass_joinclause ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2 
)

Definition at line 2343 of file equivclass.c.

References bms_overlap(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, lfirst, list_length(), and RelOptInfo::relids.

Referenced by have_relevant_joinclause().

2345 {
2346  ListCell *lc1;
2347 
2348  foreach(lc1, root->eq_classes)
2349  {
2350  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2351 
2352  /*
2353  * Won't generate joinclauses if single-member (this test covers the
2354  * volatile case too)
2355  */
2356  if (list_length(ec->ec_members) <= 1)
2357  continue;
2358 
2359  /*
2360  * We do not need to examine the individual members of the EC, because
2361  * all that we care about is whether each rel overlaps the relids of
2362  * at least one member, and a test on ec_relids is sufficient to prove
2363  * that. (As with have_relevant_joinclause(), it is not necessary
2364  * that the EC be able to form a joinclause relating exactly the two
2365  * given rels, only that it be able to form a joinclause mentioning
2366  * both, and this will surely be true if both of them overlap
2367  * ec_relids.)
2368  *
2369  * Note we don't test ec_broken; if we did, we'd need a separate code
2370  * path to look through ec_sources. Checking the membership anyway is
2371  * OK as a possibly-overoptimistic heuristic.
2372  *
2373  * We don't test ec_has_const either, even though a const eclass won't
2374  * generate real join clauses. This is because if we had "WHERE a.x =
2375  * b.y and a.x = 42", it is worth considering a join between a and b,
2376  * since the join result is likely to be small even though it'll end
2377  * up being an unqualified nestloop.
2378  */
2379  if (bms_overlap(rel1->relids, ec->ec_relids) &&
2380  bms_overlap(rel2->relids, ec->ec_relids))
2381  return true;
2382  }
2383 
2384  return false;
2385 }
Relids ec_relids
Definition: relation.h:901
Relids relids
Definition: relation.h:612
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:249
static int list_length(const List *l)
Definition: pg_list.h:89
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:509
List * ec_members
Definition: relation.h:898

◆ indexcol_is_bool_constant_for_query()

bool indexcol_is_bool_constant_for_query ( IndexOptInfo index,
int  indexcol 
)

Definition at line 3156 of file indxpath.c.

References RelOptInfo::baserestrictinfo, RestrictInfo::clause, lfirst, match_boolean_index_clause(), IndexOptInfo::opfamily, RestrictInfo::pseudoconstant, and IndexOptInfo::rel.

Referenced by build_index_pathkeys().

3157 {
3158  ListCell *lc;
3159 
3160  /* If the index isn't boolean, we can't possibly get a match */
3161  if (!IsBooleanOpfamily(index->opfamily[indexcol]))
3162  return false;
3163 
3164  /* Check each restriction clause for the index's rel */
3165  foreach(lc, index->rel->baserestrictinfo)
3166  {
3167  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3168 
3169  /*
3170  * As in match_clause_to_indexcol, never match pseudoconstants to
3171  * indexes. (It might be semantically okay to do so here, but the
3172  * odds of getting a match are negligible, so don't waste the cycles.)
3173  */
3174  if (rinfo->pseudoconstant)
3175  continue;
3176 
3177  /* See if we can match the clause's expression to the index column */
3178  if (match_boolean_index_clause((Node *) rinfo->clause, indexcol, index))
3179  return true;
3180  }
3181 
3182  return false;
3183 }
List * baserestrictinfo
Definition: relation.h:672
bool pseudoconstant
Definition: relation.h:1888
Definition: nodes.h:517
RelOptInfo * rel
Definition: relation.h:755
static bool match_boolean_index_clause(Node *clause, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:3331
Expr * clause
Definition: relation.h:1880
#define lfirst(lc)
Definition: pg_list.h:106
Oid * opfamily
Definition: relation.h:768

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 928 of file pathkeys.c.

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

929 {
930  Expr *clause = restrictinfo->clause;
931  Oid lefttype,
932  righttype;
933 
934  /* Should be a mergeclause ... */
935  Assert(restrictinfo->mergeopfamilies != NIL);
936  /* ... with links not yet set */
937  Assert(restrictinfo->left_ec == NULL);
938  Assert(restrictinfo->right_ec == NULL);
939 
940  /* Need the declared input types of the operator */
941  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
942 
943  /* Find or create a matching EquivalenceClass for each side */
944  restrictinfo->left_ec =
946  (Expr *) get_leftop(clause),
947  restrictinfo->nullable_relids,
948  restrictinfo->mergeopfamilies,
949  lefttype,
950  ((OpExpr *) clause)->inputcollid,
951  0,
952  NULL,
953  true);
954  restrictinfo->right_ec =
956  (Expr *) get_rightop(clause),
957  restrictinfo->nullable_relids,
958  restrictinfo->mergeopfamilies,
959  righttype,
960  ((OpExpr *) clause)->inputcollid,
961  0,
962  NULL,
963  true);
964 }
#define NIL
Definition: pg_list.h:69
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:619
EquivalenceClass * right_ec
Definition: relation.h:1929
unsigned int Oid
Definition: postgres_ext.h:31
List * mergeopfamilies
Definition: relation.h:1925
Node * get_leftop(const Expr *clause)
Definition: clauses.c:200
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1152
Expr * clause
Definition: relation.h:1880
Relids nullable_relids
Definition: relation.h:1904
#define Assert(condition)
Definition: c.h:699
Node * get_rightop(const Expr *clause)
Definition: clauses.c:217
EquivalenceClass * left_ec
Definition: relation.h:1928

◆ is_redundant_derived_clause()

bool is_redundant_derived_clause ( RestrictInfo rinfo,
List clauselist 
)

Definition at line 2494 of file equivclass.c.

References lfirst, and RestrictInfo::parent_ec.

Referenced by create_indexscan_plan(), extract_nonindex_conditions(), and has_indexed_join_quals().

2495 {
2496  EquivalenceClass *parent_ec = rinfo->parent_ec;
2497  ListCell *lc;
2498 
2499  /* Fail if it's not a potentially-redundant clause from some EC */
2500  if (parent_ec == NULL)
2501  return false;
2502 
2503  foreach(lc, clauselist)
2504  {
2505  RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
2506 
2507  if (otherrinfo->parent_ec == parent_ec)
2508  return true;
2509  }
2510 
2511  return false;
2512 }
EquivalenceClass * parent_ec
Definition: relation.h:1914
#define lfirst(lc)
Definition: pg_list.h:106

◆ join_search_one_level()

void join_search_one_level ( PlannerInfo root,
int  level 
)

Definition at line 65 of file joinrels.c.

References Assert, bms_overlap(), elog, ERROR, for_each_cell, RelOptInfo::has_eclass_joins, has_join_restriction(), PlannerInfo::hasLateralRTEs, have_join_order_restriction(), have_relevant_joinclause(), PlannerInfo::join_cur_level, PlannerInfo::join_info_list, PlannerInfo::join_rel_level, RelOptInfo::joininfo, lfirst, list_head(), lnext, make_join_rel(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), NIL, and RelOptInfo::relids.

Referenced by standard_join_search().

66 {
67  List **joinrels = root->join_rel_level;
68  ListCell *r;
69  int k;
70 
71  Assert(joinrels[level] == NIL);
72 
73  /* Set join_cur_level so that new joinrels are added to proper list */
74  root->join_cur_level = level;
75 
76  /*
77  * First, consider left-sided and right-sided plans, in which rels of
78  * exactly level-1 member relations are joined against initial relations.
79  * We prefer to join using join clauses, but if we find a rel of level-1
80  * members that has no join clauses, we will generate Cartesian-product
81  * joins against all initial rels not already contained in it.
82  */
83  foreach(r, joinrels[level - 1])
84  {
85  RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
86 
87  if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
88  has_join_restriction(root, old_rel))
89  {
90  /*
91  * There are join clauses or join order restrictions relevant to
92  * this rel, so consider joins between this rel and (only) those
93  * initial rels it is linked to by a clause or restriction.
94  *
95  * At level 2 this condition is symmetric, so there is no need to
96  * look at initial rels before this one in the list; we already
97  * considered such joins when we were at the earlier rel. (The
98  * mirror-image joins are handled automatically by make_join_rel.)
99  * In later passes (level > 2), we join rels of the previous level
100  * to each initial rel they don't already include but have a join
101  * clause or restriction with.
102  */
103  ListCell *other_rels;
104 
105  if (level == 2) /* consider remaining initial rels */
106  other_rels = lnext(r);
107  else /* consider all initial rels */
108  other_rels = list_head(joinrels[1]);
109 
111  old_rel,
112  other_rels);
113  }
114  else
115  {
116  /*
117  * Oops, we have a relation that is not joined to any other
118  * relation, either directly or by join-order restrictions.
119  * Cartesian product time.
120  *
121  * We consider a cartesian product with each not-already-included
122  * initial rel, whether it has other join clauses or not. At
123  * level 2, if there are two or more clauseless initial rels, we
124  * will redundantly consider joining them in both directions; but
125  * such cases aren't common enough to justify adding complexity to
126  * avoid the duplicated effort.
127  */
129  old_rel,
130  list_head(joinrels[1]));
131  }
132  }
133 
134  /*
135  * Now, consider "bushy plans" in which relations of k initial rels are
136  * joined to relations of level-k initial rels, for 2 <= k <= level-2.
137  *
138  * We only consider bushy-plan joins for pairs of rels where there is a
139  * suitable join clause (or join order restriction), in order to avoid
140  * unreasonable growth of planning time.
141  */
142  for (k = 2;; k++)
143  {
144  int other_level = level - k;
145 
146  /*
147  * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
148  * need to go as far as the halfway point.
149  */
150  if (k > other_level)
151  break;
152 
153  foreach(r, joinrels[k])
154  {
155  RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
156  ListCell *other_rels;
157  ListCell *r2;
158 
159  /*
160  * We can ignore relations without join clauses here, unless they
161  * participate in join-order restrictions --- then we might have
162  * to force a bushy join plan.
163  */
164  if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
165  !has_join_restriction(root, old_rel))
166  continue;
167 
168  if (k == other_level)
169  other_rels = lnext(r); /* only consider remaining rels */
170  else
171  other_rels = list_head(joinrels[other_level]);
172 
173  for_each_cell(r2, other_rels)
174  {
175  RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
176 
177  if (!bms_overlap(old_rel->relids, new_rel->relids))
178  {
179  /*
180  * OK, we can build a rel of the right level from this
181  * pair of rels. Do so if there is at least one relevant
182  * join clause or join order restriction.
183  */
184  if (have_relevant_joinclause(root, old_rel, new_rel) ||
185  have_join_order_restriction(root, old_rel, new_rel))
186  {
187  (void) make_join_rel(root, old_rel, new_rel);
188  }
189  }
190  }
191  }
192  }
193 
194  /*----------
195  * Last-ditch effort: if we failed to find any usable joins so far, force
196  * a set of cartesian-product joins to be generated. This handles the
197  * special case where all the available rels have join clauses but we
198  * cannot use any of those clauses yet. This can only happen when we are
199  * considering a join sub-problem (a sub-joinlist) and all the rels in the
200  * sub-problem have only join clauses with rels outside the sub-problem.
201  * An example is
202  *
203  * SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
204  * WHERE a.w = c.x and b.y = d.z;
205  *
206  * If the "a INNER JOIN b" sub-problem does not get flattened into the
207  * upper level, we must be willing to make a cartesian join of a and b;
208  * but the code above will not have done so, because it thought that both
209  * a and b have joinclauses. We consider only left-sided and right-sided
210  * cartesian joins in this case (no bushy).
211  *----------
212  */
213  if (joinrels[level] == NIL)
214  {
215  /*
216  * This loop is just like the first one, except we always call
217  * make_rels_by_clauseless_joins().
218  */
219  foreach(r, joinrels[level - 1])
220  {
221  RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
222 
224  old_rel,
225  list_head(joinrels[1]));
226  }
227 
228  /*----------
229  * When special joins are involved, there may be no legal way
230  * to make an N-way join for some values of N. For example consider
231  *
232  * SELECT ... FROM t1 WHERE
233  * x IN (SELECT ... FROM t2,t3 WHERE ...) AND
234  * y IN (SELECT ... FROM t4,t5 WHERE ...)
235  *
236  * We will flatten this query to a 5-way join problem, but there are
237  * no 4-way joins that join_is_legal() will consider legal. We have
238  * to accept failure at level 4 and go on to discover a workable
239  * bushy plan at level 5.
240  *
241  * However, if there are no special joins and no lateral references
242  * then join_is_legal() should never fail, and so the following sanity
243  * check is useful.
244  *----------
245  */
246  if (joinrels[level] == NIL &&
247  root->join_info_list == NIL &&
248  !root->hasLateralRTEs)
249  elog(ERROR, "failed to build any %d-way joins", level);
250  }
251 }
bool has_eclass_joins
Definition: relation.h:678
#define NIL
Definition: pg_list.h:69
int join_cur_level
Definition: relation.h:240
List * join_info_list
Definition: relation.h:264
static void make_rels_by_clauseless_joins(PlannerInfo *root, RelOptInfo *old_rel, ListCell *other_rels)
Definition: joinrels.c:308
bool have_join_order_restriction(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:933
static void make_rels_by_clause_joins(PlannerInfo *root, RelOptInfo *old_rel, ListCell *other_rels)
Definition: joinrels.c:274
#define ERROR
Definition: elog.h:43
static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1046
bool hasLateralRTEs
Definition: relation.h:316
List * joininfo
Definition: relation.h:676
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
Relids relids
Definition: relation.h:612
#define lnext(lc)
Definition: pg_list.h:105
RelOptInfo * make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:668
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
List ** join_rel_level
Definition: relation.h:239
#define for_each_cell(cell, initcell)
Definition: pg_list.h:169
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:509
bool have_relevant_joinclause(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joininfo.c:36
#define elog
Definition: elog.h:219
Definition: pg_list.h:45

◆ make_canonical_pathkey()

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

Definition at line 51 of file pathkeys.c.

References PlannerInfo::canon_pathkeys, EquivalenceClass::ec_merged, eclass(), 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().

54 {
55  PathKey *pk;
56  ListCell *lc;
57  MemoryContext oldcontext;
58 
59  /* The passed eclass might be non-canonical, so chase up to the top */
60  while (eclass->ec_merged)
61  eclass = eclass->ec_merged;
62 
63  foreach(lc, root->canon_pathkeys)
64  {
65  pk = (PathKey *) lfirst(lc);
66  if (eclass == pk->pk_eclass &&
67  opfamily == pk->pk_opfamily &&
68  strategy == pk->pk_strategy &&
69  nulls_first == pk->pk_nulls_first)
70  return pk;
71  }
72 
73  /*
74  * Be sure canonical pathkeys are allocated in the main planning context.
75  * Not an issue in normal planning, but it is for GEQO.
76  */
77  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
78 
79  pk = makeNode(PathKey);
80  pk->pk_eclass = eclass;
81  pk->pk_opfamily = opfamily;
82  pk->pk_strategy = strategy;
83  pk->pk_nulls_first = nulls_first;
84 
85  root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
86 
87  MemoryContextSwitchTo(oldcontext);
88 
89  return pk;
90 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int pk_strategy
Definition: relation.h:977
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:508
bool pk_nulls_first
Definition: relation.h:978
List * canon_pathkeys
Definition: relation.h:251
List * lappend(List *list, void *datum)
Definition: list.c:128
#define makeNode(_type_)
Definition: nodes.h:565
#define lfirst(lc)
Definition: pg_list.h:106
EquivalenceClass * pk_eclass
Definition: relation.h:975
Oid pk_opfamily
Definition: relation.h:976
MemoryContext planner_cxt
Definition: relation.h:302
struct EquivalenceClass * ec_merged
Definition: relation.h:910

◆ make_inner_pathkeys_for_merge()

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

Definition at line 1296 of file pathkeys.c.

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

1299 {
1300  List *pathkeys = NIL;
1301  EquivalenceClass *lastoeclass;
1302  PathKey *opathkey;
1303  ListCell *lc;
1304  ListCell *lop;
1305 
1306  lastoeclass = NULL;
1307  opathkey = NULL;
1308  lop = list_head(outer_pathkeys);
1309 
1310  foreach(lc, mergeclauses)
1311  {
1312  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1313  EquivalenceClass *oeclass;
1314  EquivalenceClass *ieclass;
1315  PathKey *pathkey;
1316 
1317  update_mergeclause_eclasses(root, rinfo);
1318 
1319  if (rinfo->outer_is_left)
1320  {
1321  oeclass = rinfo->left_ec;
1322  ieclass = rinfo->right_ec;
1323  }
1324  else
1325  {
1326  oeclass = rinfo->right_ec;
1327  ieclass = rinfo->left_ec;
1328  }
1329 
1330  /* outer eclass should match current or next pathkeys */
1331  /* we check this carefully for debugging reasons */
1332  if (oeclass != lastoeclass)
1333  {
1334  if (!lop)
1335  elog(ERROR, "too few pathkeys for mergeclauses");
1336  opathkey = (PathKey *) lfirst(lop);
1337  lop = lnext(lop);
1338  lastoeclass = opathkey->pk_eclass;
1339  if (oeclass != lastoeclass)
1340  elog(ERROR, "outer pathkeys do not match mergeclause");
1341  }
1342 
1343  /*
1344  * Often, we'll have same EC on both sides, in which case the outer
1345  * pathkey is also canonical for the inner side, and we can skip a
1346  * useless search.
1347  */
1348  if (ieclass == oeclass)
1349  pathkey = opathkey;
1350  else
1351  pathkey = make_canonical_pathkey(root,
1352  ieclass,
1353  opathkey->pk_opfamily,
1354  opathkey->pk_strategy,
1355  opathkey->pk_nulls_first);
1356 
1357  /*
1358  * Don't generate redundant pathkeys (which can happen if multiple
1359  * mergeclauses refer to the same EC). Because we do this, the output
1360  * pathkey list isn't necessarily ordered like the mergeclauses, which
1361  * complicates life for create_mergejoin_plan(). But if we didn't,
1362  * we'd have a noncanonical sort key list, which would be bad; for one
1363  * reason, it certainly wouldn't match any available sort order for
1364  * the input relation.
1365  */
1366  if (!pathkey_is_redundant(pathkey, pathkeys))
1367  pathkeys = lappend(pathkeys, pathkey);
1368  }
1369 
1370  return pathkeys;
1371 }
#define NIL
Definition: pg_list.h:69
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:51
EquivalenceClass * right_ec
Definition: relation.h:1929
int pk_strategy
Definition: relation.h:977
bool pk_nulls_first
Definition: relation.h:978
#define ERROR
Definition: elog.h:43
bool outer_is_left
Definition: relation.h:1935
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:128
#define lnext(lc)
Definition: pg_list.h:105
List * lappend(List *list, void *datum)
Definition: list.c:128
#define lfirst(lc)
Definition: pg_list.h:106
EquivalenceClass * pk_eclass
Definition: relation.h:975
Oid pk_opfamily
Definition: relation.h:976
EquivalenceClass * left_ec
Definition: relation.h:1928
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:977

◆ make_join_rel()

RelOptInfo* make_join_rel ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2 
)

Definition at line 668 of file joinrels.c.

References Assert, bms_free(), bms_overlap(), bms_union(), build_join_rel(), SpecialJoinInfo::delay_upper_joins, is_dummy_rel(), JOIN_INNER, join_is_legal(), SpecialJoinInfo::jointype, SpecialJoinInfo::lhs_strict, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, populate_joinrel_with_paths(), RelOptInfo::relids, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, SpecialJoinInfo::syn_righthand, T_SpecialJoinInfo, and SpecialJoinInfo::type.

Referenced by join_search_one_level(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), and merge_clump().

669 {
670  Relids joinrelids;
671  SpecialJoinInfo *sjinfo;
672  bool reversed;
673  SpecialJoinInfo sjinfo_data;
674  RelOptInfo *joinrel;
675  List *restrictlist;
676 
677  /* We should never try to join two overlapping sets of rels. */
678  Assert(!bms_overlap(rel1->relids, rel2->relids));
679 
680  /* Construct Relids set that identifies the joinrel. */
681  joinrelids = bms_union(rel1->relids, rel2->relids);
682 
683  /* Check validity and determine join type. */
684  if (!join_is_legal(root, rel1, rel2, joinrelids,
685  &sjinfo, &reversed))
686  {
687  /* invalid join path */
688  bms_free(joinrelids);
689  return NULL;
690  }
691 
692  /* Swap rels if needed to match the join info. */
693  if (reversed)
694  {
695  RelOptInfo *trel = rel1;
696 
697  rel1 = rel2;
698  rel2 = trel;
699  }
700 
701  /*
702  * If it's a plain inner join, then we won't have found anything in
703  * join_info_list. Make up a SpecialJoinInfo so that selectivity
704  * estimation functions will know what's being joined.
705  */
706  if (sjinfo == NULL)
707  {
708  sjinfo = &sjinfo_data;
709  sjinfo->type = T_SpecialJoinInfo;
710  sjinfo->min_lefthand = rel1->relids;
711  sjinfo->min_righthand = rel2->relids;
712  sjinfo->syn_lefthand = rel1->relids;
713  sjinfo->syn_righthand = rel2->relids;
714  sjinfo->jointype = JOIN_INNER;
715  /* we don't bother trying to make the remaining fields valid */
716  sjinfo->lhs_strict = false;
717  sjinfo->delay_upper_joins = false;
718  sjinfo->semi_can_btree = false;
719  sjinfo->semi_can_hash = false;
720  sjinfo->semi_operators = NIL;
721  sjinfo->semi_rhs_exprs = NIL;
722  }
723 
724  /*
725  * Find or build the join RelOptInfo, and compute the restrictlist that
726  * goes with this particular joining.
727  */
728  joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
729  &restrictlist);
730 
731  /*
732  * If we've already proven this join is empty, we needn't consider any
733  * more paths for it.
734  */
735  if (is_dummy_rel(joinrel))
736  {
737  bms_free(joinrelids);
738  return joinrel;
739  }
740 
741  /* Add paths to the join relation. */
742  populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
743  restrictlist);
744 
745  bms_free(joinrelids);
746 
747  return joinrel;
748 }
#define NIL
Definition: pg_list.h:69
static bool is_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1194
bool semi_can_btree
Definition: relation.h:2074
static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinrels.c:758
Relids min_righthand
Definition: relation.h:2067
NodeTag type
Definition: relation.h:2065
Relids syn_lefthand
Definition: relation.h:2068
Relids syn_righthand
Definition: relation.h:2069
List * semi_rhs_exprs
Definition: relation.h:2077
bool semi_can_hash
Definition: relation.h:2075
static bool join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
Definition: joinrels.c:341
Relids relids
Definition: relation.h:612
bool delay_upper_joins
Definition: relation.h:2072
RelOptInfo * build_join_rel(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, List **restrictlist_ptr)
Definition: relnode.c:482
void bms_free(Bitmapset *a)
Definition: bitmapset.c:267
#define Assert(condition)
Definition: c.h:699
JoinType jointype
Definition: relation.h:2070
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:509
List * semi_operators
Definition: relation.h:2076
Definition: pg_list.h:45
Relids min_lefthand
Definition: relation.h:2066

◆ make_one_rel()

RelOptInfo* make_one_rel ( PlannerInfo root,
List joinlist 
)

Definition at line 146 of file allpaths.c.

References PlannerInfo::all_baserels, Assert, bms_add_member(), bms_equal(), make_rel_from_joinlist(), RelOptInfo::relid, RelOptInfo::relids, RELOPT_BASEREL, RelOptInfo::reloptkind, set_base_rel_consider_startup(), set_base_rel_pathlists(), set_base_rel_sizes(), PlannerInfo::simple_rel_array, and PlannerInfo::simple_rel_array_size.

Referenced by query_planner().

147 {
148  RelOptInfo *rel;
149  Index rti;
150 
151  /*
152  * Construct the all_baserels Relids set.
153  */
154  root->all_baserels = NULL;
155  for (rti = 1; rti < root->simple_rel_array_size; rti++)
156  {
157  RelOptInfo *brel = root->simple_rel_array[rti];
158 
159  /* there may be empty slots corresponding to non-baserel RTEs */
160  if (brel == NULL)
161  continue;
162 
163  Assert(brel->relid == rti); /* sanity check on array */
164 
165  /* ignore RTEs that are "other rels" */
166  if (brel->reloptkind != RELOPT_BASEREL)
167  continue;
168 
169  root->all_baserels = bms_add_member(root->all_baserels, brel->relid);
170  }
171 
172  /* Mark base rels as to whether we care about fast-start plans */
174 
175  /*
176  * Compute size estimates and consider_parallel flags for each base rel,
177  * then generate access paths.
178  */
179  set_base_rel_sizes(root);
181 
182  /*
183  * Generate access paths for the entire join tree.
184  */
185  rel = make_rel_from_joinlist(root, joinlist);
186 
187  /*
188  * The result should join all and only the query's base rels.
189  */
190  Assert(bms_equal(rel->relids, root->all_baserels));
191 
192  return rel;
193 }
RelOptKind reloptkind
Definition: relation.h:609
static void set_base_rel_sizes(PlannerInfo *root)
Definition: allpaths.c:249
static void set_base_rel_consider_startup(PlannerInfo *root)
Definition: allpaths.c:206
struct RelOptInfo ** simple_rel_array
Definition: relation.h:193
Relids all_baserels
Definition: relation.h:210
static RelOptInfo * make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
Definition: allpaths.c:2597
Relids relids
Definition: relation.h:612
int simple_rel_array_size
Definition: relation.h:194
Index relid
Definition: relation.h:640
static void set_base_rel_pathlists(PlannerInfo *root)
Definition: allpaths.c:292
unsigned int Index
Definition: c.h:442
#define Assert(condition)
Definition: c.h:699
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:764
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:153

◆ make_pathkeys_for_sortclauses()

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

Definition at line 874 of file pathkeys.c.

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(), get_column_info_for_window(), grouping_planner(), make_pathkeys_for_window(), make_union_unique(), minmax_qp_callback(), and standard_qp_callback().

877 {
878  List *pathkeys = NIL;
879  ListCell *l;
880 
881  foreach(l, sortclauses)
882  {
883  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
884  Expr *sortkey;
885  PathKey *pathkey;
886 
887  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
888  Assert(OidIsValid(sortcl->sortop));
889  pathkey = make_pathkey_from_sortop(root,
890  sortkey,
891  root->nullable_baserels,
892  sortcl->sortop,
893  sortcl->nulls_first,
894  sortcl->tleSortGroupRef,
895  true);
896 
897  /* Canonical form eliminates redundant ordering keys */
898  if (!pathkey_is_redundant(pathkey, pathkeys))
899  pathkeys = lappend(pathkeys, pathkey);
900  }
901  return pathkeys;
902 }
#define NIL
Definition: pg_list.h:69
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:229
Index tleSortGroupRef
Definition: parsenodes.h:1207
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:382
#define OidIsValid(objectId)
Definition: c.h:605
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:128
List * lappend(List *list, void *datum)
Definition: list.c:128
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
Relids nullable_baserels
Definition: relation.h:218
Definition: pg_list.h:45

◆ mark_dummy_rel()

void mark_dummy_rel ( RelOptInfo rel)

Definition at line 1215 of file joinrels.c.

References add_path(), create_append_path(), GetMemoryChunkContext(), is_dummy_rel(), MemoryContextSwitchTo(), NIL, RelOptInfo::partial_pathlist, RelOptInfo::pathlist, RelOptInfo::rows, and set_cheapest().

Referenced by create_partitionwise_grouping_paths(), generate_partitionwise_join_paths(), and populate_joinrel_with_paths().

1216 {
1217  MemoryContext oldcontext;
1218 
1219  /* Already marked? */
1220  if (is_dummy_rel(rel))
1221  return;
1222 
1223  /* No, so choose correct context to make the dummy path in */
1224  oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1225 
1226  /* Set dummy size estimate */
1227  rel->rows = 0;
1228 
1229  /* Evict any previously chosen paths */
1230  rel->pathlist = NIL;
1231  rel->partial_pathlist = NIL;
1232 
1233  /* Set up the dummy path */
1234  add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL, NULL,
1235  0, false,