PostgreSQL Source Code  git master
paths.h File Reference
#include "nodes/pathnodes.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)
 
RelOptInfostandard_join_search (PlannerInfo *root, int levels_needed, List *initial_rels)
 
void generate_gather_paths (PlannerInfo *root, RelOptInfo *rel, bool override_rows)
 
void generate_useful_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 check_index_predicates (PlannerInfo *root, RelOptInfo *rel)
 
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 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)
 
Exprfind_em_expr_for_rel (EquivalenceClass *ec, RelOptInfo *rel)
 
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)
 
void add_child_join_rel_equivalences (PlannerInfo *root, int nappinfos, AppendRelInfo **appinfos, 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)
 
bool is_redundant_with_indexclauses (RestrictInfo *rinfo, List *indexclauses)
 
PathKeysComparison compare_pathkeys (List *keys1, List *keys2)
 
bool pathkeys_contained_in (List *keys1, List *keys2)
 
bool pathkeys_count_contained_in (List *keys1, List *keys2, int *n_common)
 
Pathget_cheapest_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
 
Pathget_cheapest_fractional_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, double fraction)
 
Pathget_cheapest_parallel_safe_total_inner (List *paths)
 
Listbuild_index_pathkeys (PlannerInfo *root, IndexOptInfo *index, ScanDirection scandir)
 
Listbuild_partition_pathkeys (PlannerInfo *root, RelOptInfo *partrel, ScanDirection scandir, bool *partialkeys)
 
Listbuild_expression_pathkey (PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opno, Relids rel, bool create_it)
 
Listconvert_subquery_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *subquery_pathkeys, List *subquery_tlist)
 
Listbuild_join_pathkeys (PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
 
Listmake_pathkeys_for_sortclauses (PlannerInfo *root, List *sortclauses, List *tlist)
 
void initialize_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
 
void update_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
 
Listfind_mergeclauses_for_outer_pathkeys (PlannerInfo *root, List *pathkeys, List *restrictinfos)
 
Listselect_outer_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
 
Listmake_inner_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
 
Listtrim_mergeclauses_for_inner_pathkeys (PlannerInfo *root, List *mergeclauses, List *pathkeys)
 
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 116 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 181 of file paths.h.

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

Function Documentation

◆ add_child_join_rel_equivalences()

void add_child_join_rel_equivalences ( PlannerInfo root,
int  nappinfos,
AppendRelInfo **  appinfos,
RelOptInfo parent_rel,
RelOptInfo child_rel 
)

Definition at line 2384 of file equivclass.c.

References add_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), adjust_child_relids_multilevel(), Assert, bms_add_members(), bms_difference(), bms_membership(), BMS_MULTIPLE, bms_next_member(), bms_overlap(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_nullable_relids, EquivalenceMember::em_relids, PlannerInfo::eq_classes, get_eclass_indexes_for_relids(), i, IS_JOIN_REL, list_length(), list_nth(), RelOptInfo::relids, RELOPT_JOINREL, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, and RelOptInfo::top_parent_relids.

Referenced by build_child_join_rel().

2388 {
2389  Relids top_parent_relids = child_joinrel->top_parent_relids;
2390  Relids child_relids = child_joinrel->relids;
2391  Bitmapset *matching_ecs;
2392  int i;
2393 
2394  Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
2395 
2396  /* We need consider only ECs that mention the parent joinrel */
2397  matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids);
2398 
2399  i = -1;
2400  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2401  {
2402  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2403  int num_members;
2404 
2405  /*
2406  * If this EC contains a volatile expression, then generating child
2407  * EMs would be downright dangerous, so skip it. We rely on a
2408  * volatile EC having only one EM.
2409  */
2410  if (cur_ec->ec_has_volatile)
2411  continue;
2412 
2413  /* Sanity check on get_eclass_indexes_for_relids result */
2414  Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
2415 
2416  /*
2417  * We don't use foreach() here because there's no point in scanning
2418  * newly-added child members, so we can stop after the last
2419  * pre-existing EC member.
2420  */
2421  num_members = list_length(cur_ec->ec_members);
2422  for (int pos = 0; pos < num_members; pos++)
2423  {
2424  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2425 
2426  if (cur_em->em_is_const)
2427  continue; /* ignore consts here */
2428 
2429  /*
2430  * We consider only original EC members here, not
2431  * already-transformed child members.
2432  */
2433  if (cur_em->em_is_child)
2434  continue; /* ignore children here */
2435 
2436  /*
2437  * We may ignore expressions that reference a single baserel,
2438  * because add_child_rel_equivalences should have handled them.
2439  */
2440  if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
2441  continue;
2442 
2443  /* Does this member reference child's topmost parent rel? */
2444  if (bms_overlap(cur_em->em_relids, top_parent_relids))
2445  {
2446  /* Yes, generate transformed child version */
2447  Expr *child_expr;
2448  Relids new_relids;
2449  Relids new_nullable_relids;
2450 
2451  if (parent_joinrel->reloptkind == RELOPT_JOINREL)
2452  {
2453  /* Simple single-level transformation */
2454  child_expr = (Expr *)
2456  (Node *) cur_em->em_expr,
2457  nappinfos, appinfos);
2458  }
2459  else
2460  {
2461  /* Must do multi-level transformation */
2462  Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
2463  child_expr = (Expr *)
2465  (Node *) cur_em->em_expr,
2466  child_relids,
2467  top_parent_relids);
2468  }
2469 
2470  /*
2471  * Transform em_relids to match. Note we do *not* do
2472  * pull_varnos(child_expr) here, as for example the
2473  * transformation might have substituted a constant, but we
2474  * don't want the child member to be marked as constant.
2475  */
2476  new_relids = bms_difference(cur_em->em_relids,
2477  top_parent_relids);
2478  new_relids = bms_add_members(new_relids, child_relids);
2479 
2480  /*
2481  * For nullable_relids, we must selectively replace parent
2482  * nullable relids with child ones.
2483  */
2484  new_nullable_relids = cur_em->em_nullable_relids;
2485  if (bms_overlap(new_nullable_relids, top_parent_relids))
2486  new_nullable_relids =
2488  new_nullable_relids,
2489  child_relids,
2490  top_parent_relids);
2491 
2492  (void) add_eq_member(cur_ec, child_expr,
2493  new_relids, new_nullable_relids,
2494  true, cur_em->em_datatype);
2495  }
2496  }
2497  }
2498 }
Relids em_nullable_relids
Definition: pathnodes.h:1014
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:291
Definition: nodes.h:529
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:643
Relids adjust_child_relids_multilevel(PlannerInfo *root, Relids relids, Relids child_relids, Relids top_parent_relids)
Definition: appendinfo.c:576
Node * adjust_appendrel_attrs_multilevel(PlannerInfo *root, Node *node, Relids child_relids, Relids top_parent_relids)
Definition: appendinfo.c:502
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:2887
Relids ec_relids
Definition: pathnodes.h:967
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:672
#define Assert(condition)
Definition: c.h:738
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:169
bool ec_has_volatile
Definition: pathnodes.h:970
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
int i
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, Relids nullable_relids, bool is_child, Oid datatype)
Definition: equivclass.c:549
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:793
List * ec_members
Definition: pathnodes.h:964
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, int nappinfos, AppendRelInfo **appinfos)
Definition: appendinfo.c:194

◆ add_child_rel_equivalences()

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

Definition at line 2256 of file equivclass.c.

References add_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), Assert, bms_add_member(), bms_add_members(), bms_difference(), bms_is_subset(), bms_next_member(), bms_overlap(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, PlannerInfo::ec_merging_done, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_nullable_relids, EquivalenceMember::em_relids, PlannerInfo::eq_classes, i, IS_SIMPLE_REL, list_length(), list_nth(), RelOptInfo::relids, RELOPT_BASEREL, RelOptInfo::reloptkind, and RelOptInfo::top_parent_relids.

Referenced by set_append_rel_size().

2260 {
2261  Relids top_parent_relids = child_rel->top_parent_relids;
2262  Relids child_relids = child_rel->relids;
2263  int i;
2264 
2265  /*
2266  * EC merging should be complete already, so we can use the parent rel's
2267  * eclass_indexes to avoid searching all of root->eq_classes.
2268  */
2269  Assert(root->ec_merging_done);
2270  Assert(IS_SIMPLE_REL(parent_rel));
2271 
2272  i = -1;
2273  while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
2274  {
2275  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2276  int num_members;
2277 
2278  /*
2279  * If this EC contains a volatile expression, then generating child
2280  * EMs would be downright dangerous, so skip it. We rely on a
2281  * volatile EC having only one EM.
2282  */
2283  if (cur_ec->ec_has_volatile)
2284  continue;
2285 
2286  /* Sanity check eclass_indexes only contain ECs for parent_rel */
2287  Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
2288 
2289  /*
2290  * We don't use foreach() here because there's no point in scanning
2291  * newly-added child members, so we can stop after the last
2292  * pre-existing EC member.
2293  */
2294  num_members = list_length(cur_ec->ec_members);
2295  for (int pos = 0; pos < num_members; pos++)
2296  {
2297  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2298 
2299  if (cur_em->em_is_const)
2300  continue; /* ignore consts here */
2301 
2302  /*
2303  * We consider only original EC members here, not
2304  * already-transformed child members. Otherwise, if some original
2305  * member expression references more than one appendrel, we'd get
2306  * an O(N^2) explosion of useless derived expressions for
2307  * combinations of children. (But add_child_join_rel_equivalences
2308  * may add targeted combinations for partitionwise-join purposes.)
2309  */
2310  if (cur_em->em_is_child)
2311  continue; /* ignore children here */
2312 
2313  /* Does this member reference child's topmost parent rel? */
2314  if (bms_overlap(cur_em->em_relids, top_parent_relids))
2315  {
2316  /* Yes, generate transformed child version */
2317  Expr *child_expr;
2318  Relids new_relids;
2319  Relids new_nullable_relids;
2320 
2321  if (parent_rel->reloptkind == RELOPT_BASEREL)
2322  {
2323  /* Simple single-level transformation */
2324  child_expr = (Expr *)
2326  (Node *) cur_em->em_expr,
2327  1, &appinfo);
2328  }
2329  else
2330  {
2331  /* Must do multi-level transformation */
2332  child_expr = (Expr *)
2334  (Node *) cur_em->em_expr,
2335  child_relids,
2336  top_parent_relids);
2337  }
2338 
2339  /*
2340  * Transform em_relids to match. Note we do *not* do
2341  * pull_varnos(child_expr) here, as for example the
2342  * transformation might have substituted a constant, but we
2343  * don't want the child member to be marked as constant.
2344  */
2345  new_relids = bms_difference(cur_em->em_relids,
2346  top_parent_relids);
2347  new_relids = bms_add_members(new_relids, child_relids);
2348 
2349  /*
2350  * And likewise for nullable_relids. Note this code assumes
2351  * parent and child relids are singletons.
2352  */
2353  new_nullable_relids = cur_em->em_nullable_relids;
2354  if (bms_overlap(new_nullable_relids, top_parent_relids))
2355  {
2356  new_nullable_relids = bms_difference(new_nullable_relids,
2357  top_parent_relids);
2358  new_nullable_relids = bms_add_members(new_nullable_relids,
2359  child_relids);
2360  }
2361 
2362  (void) add_eq_member(cur_ec, child_expr,
2363  new_relids, new_nullable_relids,
2364  true, cur_em->em_datatype);
2365 
2366  /* Record this EC index for the child rel */
2367  child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
2368  }
2369  }
2370  }
2371 }
RelOptKind reloptkind
Definition: pathnodes.h:662
bool ec_merging_done
Definition: pathnodes.h:268
Relids em_nullable_relids
Definition: pathnodes.h:1014
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:291
Definition: nodes.h:529
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:638
Node * adjust_appendrel_attrs_multilevel(PlannerInfo *root, Node *node, Relids child_relids, Relids top_parent_relids)
Definition: appendinfo.c:502
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
Relids ec_relids
Definition: pathnodes.h:967
Relids relids
Definition: pathnodes.h:665
#define Assert(condition)
Definition: c.h:738
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:169
bool ec_has_volatile
Definition: pathnodes.h:970
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:736
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
int i
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, Relids nullable_relids, bool is_child, Oid datatype)
Definition: equivclass.c:549
Bitmapset * eclass_indexes
Definition: pathnodes.h:707
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:793
List * ec_members
Definition: pathnodes.h:964
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, int nappinfos, AppendRelInfo **appinfos)
Definition: appendinfo.c:194
Relids top_parent_relids
Definition: pathnodes.h:738

◆ add_paths_to_append_rel()

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

Definition at line 1297 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(), RelOptInfo::consider_parallel, create_append_path(), enable_parallel_append, fls(), generate_orderedappend_paths(), get_cheapest_parallel_safe_total_inner(), get_cheapest_parameterized_child_path(), IS_JOIN_REL, IS_SIMPLE_REL, lappend(), lfirst, linitial, list_concat(), list_length(), list_make1, 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().

1299 {
1300  List *subpaths = NIL;
1301  bool subpaths_valid = true;
1302  List *partial_subpaths = NIL;
1303  List *pa_partial_subpaths = NIL;
1304  List *pa_nonpartial_subpaths = NIL;
1305  bool partial_subpaths_valid = true;
1306  bool pa_subpaths_valid;
1307  List *all_child_pathkeys = NIL;
1308  List *all_child_outers = NIL;
1309  ListCell *l;
1310  List *partitioned_rels = NIL;
1311  double partial_rows = -1;
1312 
1313  /* If appropriate, consider parallel append */
1314  pa_subpaths_valid = enable_parallel_append && rel->consider_parallel;
1315 
1316  /*
1317  * AppendPath generated for partitioned tables must record the RT indexes
1318  * of partitioned tables that are direct or indirect children of this
1319  * Append rel.
1320  *
1321  * AppendPath may be for a sub-query RTE (UNION ALL), in which case, 'rel'
1322  * itself does not represent a partitioned relation, but the child sub-
1323  * queries may contain references to partitioned relations. The loop
1324  * below will look for such children and collect them in a list to be
1325  * passed to the path creation function. (This assumes that we don't need
1326  * to look through multiple levels of subquery RTEs; if we ever do, we
1327  * could consider stuffing the list we generate here into sub-query RTE's
1328  * RelOptInfo, just like we do for partitioned rels, which would be used
1329  * when populating our parent rel with paths. For the present, that
1330  * appears to be unnecessary.)
1331  */
1332  if (rel->part_scheme != NULL)
1333  {
1334  if (IS_SIMPLE_REL(rel))
1335  partitioned_rels = list_make1(rel->partitioned_child_rels);
1336  else if (IS_JOIN_REL(rel))
1337  {
1338  int relid = -1;
1339  List *partrels = NIL;
1340 
1341  /*
1342  * For a partitioned joinrel, concatenate the component rels'
1343  * partitioned_child_rels lists.
1344  */
1345  while ((relid = bms_next_member(rel->relids, relid)) >= 0)
1346  {
1347  RelOptInfo *component;
1348 
1349  Assert(relid >= 1 && relid < root->simple_rel_array_size);
1350  component = root->simple_rel_array[relid];
1351  Assert(component->part_scheme != NULL);
1352  Assert(list_length(component->partitioned_child_rels) >= 1);
1353  partrels = list_concat(partrels,
1354  component->partitioned_child_rels);
1355  }
1356 
1357  partitioned_rels = list_make1(partrels);
1358  }
1359 
1360  Assert(list_length(partitioned_rels) >= 1);
1361  }
1362 
1363  /*
1364  * For every non-dummy child, remember the cheapest path. Also, identify
1365  * all pathkeys (orderings) and parameterizations (required_outer sets)
1366  * available for the non-dummy member relations.
1367  */
1368  foreach(l, live_childrels)
1369  {
1370  RelOptInfo *childrel = lfirst(l);
1371  ListCell *lcp;
1372  Path *cheapest_partial_path = NULL;
1373 
1374  /*
1375  * For UNION ALLs with non-empty partitioned_child_rels, accumulate
1376  * the Lists of child relations.
1377  */
1378  if (rel->rtekind == RTE_SUBQUERY && childrel->partitioned_child_rels != NIL)
1379  partitioned_rels = lappend(partitioned_rels,
1380  childrel->partitioned_child_rels);
1381 
1382  /*
1383  * If child has an unparameterized cheapest-total path, add that to
1384  * the unparameterized Append path we are constructing for the parent.
1385  * If not, there's no workable unparameterized path.
1386  *
1387  * With partitionwise aggregates, the child rel's pathlist may be
1388  * empty, so don't assume that a path exists here.
1389  */
1390  if (childrel->pathlist != NIL &&
1391  childrel->cheapest_total_path->param_info == NULL)
1393  &subpaths, NULL);
1394  else
1395  subpaths_valid = false;
1396 
1397  /* Same idea, but for a partial plan. */
1398  if (childrel->partial_pathlist != NIL)
1399  {
1400  cheapest_partial_path = linitial(childrel->partial_pathlist);
1401  accumulate_append_subpath(cheapest_partial_path,
1402  &partial_subpaths, NULL);
1403  }
1404  else
1405  partial_subpaths_valid = false;
1406 
1407  /*
1408  * Same idea, but for a parallel append mixing partial and non-partial
1409  * paths.
1410  */
1411  if (pa_subpaths_valid)
1412  {
1413  Path *nppath = NULL;
1414 
1415  nppath =
1417 
1418  if (cheapest_partial_path == NULL && nppath == NULL)
1419  {
1420  /* Neither a partial nor a parallel-safe path? Forget it. */
1421  pa_subpaths_valid = false;
1422  }
1423  else if (nppath == NULL ||
1424  (cheapest_partial_path != NULL &&
1425  cheapest_partial_path->total_cost < nppath->total_cost))
1426  {
1427  /* Partial path is cheaper or the only option. */
1428  Assert(cheapest_partial_path != NULL);
1429  accumulate_append_subpath(cheapest_partial_path,
1430  &pa_partial_subpaths,
1431  &pa_nonpartial_subpaths);
1432 
1433  }
1434  else
1435  {
1436  /*
1437  * Either we've got only a non-partial path, or we think that
1438  * a single backend can execute the best non-partial path
1439  * faster than all the parallel backends working together can
1440  * execute the best partial path.
1441  *
1442  * It might make sense to be more aggressive here. Even if
1443  * the best non-partial path is more expensive than the best
1444  * partial path, it could still be better to choose the
1445  * non-partial path if there are several such paths that can
1446  * be given to different workers. For now, we don't try to
1447  * figure that out.
1448  */
1450  &pa_nonpartial_subpaths,
1451  NULL);
1452  }
1453  }
1454 
1455  /*
1456  * Collect lists of all the available path orderings and
1457  * parameterizations for all the children. We use these as a
1458  * heuristic to indicate which sort orderings and parameterizations we
1459  * should build Append and MergeAppend paths for.
1460  */
1461  foreach(lcp, childrel->pathlist)
1462  {
1463  Path *childpath = (Path *) lfirst(lcp);
1464  List *childkeys = childpath->pathkeys;
1465  Relids childouter = PATH_REQ_OUTER(childpath);
1466 
1467  /* Unsorted paths don't contribute to pathkey list */
1468  if (childkeys != NIL)
1469  {
1470  ListCell *lpk;
1471  bool found = false;
1472 
1473  /* Have we already seen this ordering? */
1474  foreach(lpk, all_child_pathkeys)
1475  {
1476  List *existing_pathkeys = (List *) lfirst(lpk);
1477 
1478  if (compare_pathkeys(existing_pathkeys,
1479  childkeys) == PATHKEYS_EQUAL)
1480  {
1481  found = true;
1482  break;
1483  }
1484  }
1485  if (!found)
1486  {
1487  /* No, so add it to all_child_pathkeys */
1488  all_child_pathkeys = lappend(all_child_pathkeys,
1489  childkeys);
1490  }
1491  }
1492 
1493  /* Unparameterized paths don't contribute to param-set list */
1494  if (childouter)
1495  {
1496  ListCell *lco;
1497  bool found = false;
1498 
1499  /* Have we already seen this param set? */
1500  foreach(lco, all_child_outers)
1501  {
1502  Relids existing_outers = (Relids) lfirst(lco);
1503 
1504  if (bms_equal(existing_outers, childouter))
1505  {
1506  found = true;
1507  break;
1508  }
1509  }
1510  if (!found)
1511  {
1512  /* No, so add it to all_child_outers */
1513  all_child_outers = lappend(all_child_outers,
1514  childouter);
1515  }
1516  }
1517  }
1518  }
1519 
1520  /*
1521  * If we found unparameterized paths for all children, build an unordered,
1522  * unparameterized Append path for the rel. (Note: this is correct even
1523  * if we have zero or one live subpath due to constraint exclusion.)
1524  */
1525  if (subpaths_valid)
1526  add_path(rel, (Path *) create_append_path(root, rel, subpaths, NIL,
1527  NIL, NULL, 0, false,
1528  partitioned_rels, -1));
1529 
1530  /*
1531  * Consider an append of unordered, unparameterized partial paths. Make
1532  * it parallel-aware if possible.
1533  */
1534  if (partial_subpaths_valid && partial_subpaths != NIL)
1535  {
1536  AppendPath *appendpath;
1537  ListCell *lc;
1538  int parallel_workers = 0;
1539 
1540  /* Find the highest number of workers requested for any subpath. */
1541  foreach(lc, partial_subpaths)
1542  {
1543  Path *path = lfirst(lc);
1544 
1545  parallel_workers = Max(parallel_workers, path->parallel_workers);
1546  }
1547  Assert(parallel_workers > 0);
1548 
1549  /*
1550  * If the use of parallel append is permitted, always request at least
1551  * log2(# of children) workers. We assume it can be useful to have
1552  * extra workers in this case because they will be spread out across
1553  * the children. The precise formula is just a guess, but we don't
1554  * want to end up with a radically different answer for a table with N
1555  * partitions vs. an unpartitioned table with the same data, so the
1556  * use of some kind of log-scaling here seems to make some sense.
1557  */
1559  {
1560  parallel_workers = Max(parallel_workers,
1561  fls(list_length(live_childrels)));
1562  parallel_workers = Min(parallel_workers,
1564  }
1565  Assert(parallel_workers > 0);
1566 
1567  /* Generate a partial append path. */
1568  appendpath = create_append_path(root, rel, NIL, partial_subpaths,
1569  NIL, NULL, parallel_workers,
1571  partitioned_rels, -1);
1572 
1573  /*
1574  * Make sure any subsequent partial paths use the same row count
1575  * estimate.
1576  */
1577  partial_rows = appendpath->path.rows;
1578 
1579  /* Add the path. */
1580  add_partial_path(rel, (Path *) appendpath);
1581  }
1582 
1583  /*
1584  * Consider a parallel-aware append using a mix of partial and non-partial
1585  * paths. (This only makes sense if there's at least one child which has
1586  * a non-partial path that is substantially cheaper than any partial path;
1587  * otherwise, we should use the append path added in the previous step.)
1588  */
1589  if (pa_subpaths_valid && pa_nonpartial_subpaths != NIL)
1590  {
1591  AppendPath *appendpath;
1592  ListCell *lc;
1593  int parallel_workers = 0;
1594 
1595  /*
1596  * Find the highest number of workers requested for any partial
1597  * subpath.
1598  */
1599  foreach(lc, pa_partial_subpaths)
1600  {
1601  Path *path = lfirst(lc);
1602 
1603  parallel_workers = Max(parallel_workers, path->parallel_workers);
1604  }
1605 
1606  /*
1607  * Same formula here as above. It's even more important in this
1608  * instance because the non-partial paths won't contribute anything to
1609  * the planned number of parallel workers.
1610  */
1611  parallel_workers = Max(parallel_workers,
1612  fls(list_length(live_childrels)));
1613  parallel_workers = Min(parallel_workers,
1615  Assert(parallel_workers > 0);
1616 
1617  appendpath = create_append_path(root, rel, pa_nonpartial_subpaths,
1618  pa_partial_subpaths,
1619  NIL, NULL, parallel_workers, true,
1620  partitioned_rels, partial_rows);
1621  add_partial_path(rel, (Path *) appendpath);
1622  }
1623 
1624  /*
1625  * Also build unparameterized ordered append paths based on the collected
1626  * list of child pathkeys.
1627  */
1628  if (subpaths_valid)
1629  generate_orderedappend_paths(root, rel, live_childrels,
1630  all_child_pathkeys,
1631  partitioned_rels);
1632 
1633  /*
1634  * Build Append paths for each parameterization seen among the child rels.
1635  * (This may look pretty expensive, but in most cases of practical
1636  * interest, the child rels will expose mostly the same parameterizations,
1637  * so that not that many cases actually get considered here.)
1638  *
1639  * The Append node itself cannot enforce quals, so all qual checking must
1640  * be done in the child paths. This means that to have a parameterized
1641  * Append path, we must have the exact same parameterization for each
1642  * child path; otherwise some children might be failing to check the
1643  * moved-down quals. To make them match up, we can try to increase the
1644  * parameterization of lesser-parameterized paths.
1645  */
1646  foreach(l, all_child_outers)
1647  {
1648  Relids required_outer = (Relids) lfirst(l);
1649  ListCell *lcr;
1650 
1651  /* Select the child paths for an Append with this parameterization */
1652  subpaths = NIL;
1653  subpaths_valid = true;
1654  foreach(lcr, live_childrels)
1655  {
1656  RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
1657  Path *subpath;
1658 
1659  if (childrel->pathlist == NIL)
1660  {
1661  /* failed to make a suitable path for this child */
1662  subpaths_valid = false;
1663  break;
1664  }
1665 
1667  childrel,
1668  required_outer);
1669  if (subpath == NULL)
1670  {
1671  /* failed to make a suitable path for this child */
1672  subpaths_valid = false;
1673  break;
1674  }
1675  accumulate_append_subpath(subpath, &subpaths, NULL);
1676  }
1677 
1678  if (subpaths_valid)
1679  add_path(rel, (Path *)
1680  create_append_path(root, rel, subpaths, NIL,
1681  NIL, required_outer, 0, false,
1682  partitioned_rels, -1));
1683  }
1684 
1685  /*
1686  * When there is only a single child relation, the Append path can inherit
1687  * any ordering available for the child rel's path, so that it's useful to
1688  * consider ordered partial paths. Above we only considered the cheapest
1689  * partial path for each child, but let's also make paths using any
1690  * partial paths that have pathkeys.
1691  */
1692  if (list_length(live_childrels) == 1)
1693  {
1694  RelOptInfo *childrel = (RelOptInfo *) linitial(live_childrels);
1695 
1696  foreach(l, childrel->partial_pathlist)
1697  {
1698  Path *path = (Path *) lfirst(l);
1699  AppendPath *appendpath;
1700 
1701  /*
1702  * Skip paths with no pathkeys. Also skip the cheapest partial
1703  * path, since we already used that above.
1704  */
1705  if (path->pathkeys == NIL ||
1706  path == linitial(childrel->partial_pathlist))
1707  continue;
1708 
1709  appendpath = create_append_path(root, rel, NIL, list_make1(path),
1710  NIL, NULL,
1711  path->parallel_workers, true,
1712  partitioned_rels, partial_rows);
1713  add_partial_path(rel, (Path *) appendpath);
1714  }
1715  }
1716 }
#define NIL
Definition: pg_list.h:65
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:1957
#define Min(x, y)
Definition: c.h:920
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
int parallel_workers
Definition: pathnodes.h:1151
ParamPathInfo * param_info
Definition: pathnodes.h:1147
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:643
List * list_concat(List *list1, const List *list2)
Definition: list.c:515
List * partial_pathlist
Definition: pathnodes.h:681
bool enable_parallel_append
Definition: costsize.c:141
PathKeysComparison compare_pathkeys(List *keys1, List *keys2)
Definition: pathkeys.c:285
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:638
int fls(int mask)
Definition: fls.c:55
struct RelOptInfo ** simple_rel_array
Definition: pathnodes.h:203
#define list_make1(x1)
Definition: pg_list.h:227
#define linitial(l)
Definition: pg_list.h:195
struct Path * cheapest_total_path
Definition: pathnodes.h:683
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1163
Relids relids
Definition: pathnodes.h:665
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:482
AppendPath * create_append_path(PlannerInfo *root, RelOptInfo *rel, List *subpaths, List *partial_subpaths, List *pathkeys, Relids required_outer, int parallel_workers, bool parallel_aware, List *partitioned_rels, double rows)
Definition: pathnode.c:1183
List * lappend(List *list, void *datum)
Definition: list.c:321
RTEKind rtekind
Definition: pathnodes.h:695
Cost total_cost
Definition: pathnodes.h:1156
List * pathkeys
Definition: pathnodes.h:1158
#define Max(x, y)
Definition: c.h:914
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
double rows
Definition: pathnodes.h:1154
static int list_length(const List *l)
Definition: pg_list.h:169
bool consider_parallel
Definition: pathnodes.h:673
Bitmapset * Relids
Definition: pathnodes.h:28
List * partitioned_child_rels
Definition: pathnodes.h:755
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:749
PartitionScheme part_scheme
Definition: pathnodes.h:742
List * pathlist
Definition: pathnodes.h:679
static void generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel, List *live_childrels, List *all_child_pathkeys, List *partitioned_rels)
Definition: allpaths.c:1746
static void accumulate_append_subpath(Path *path, List **subpaths, List **special_subpaths)
Definition: allpaths.c:2045
int max_parallel_workers_per_gather
Definition: costsize.c:123
Definition: pg_list.h:50
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:241
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:94

◆ 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:65
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:2428
RelOptKind reloptkind
Definition: pathnodes.h:662
List * join_info_list
Definition: pathnodes.h:283
Relids min_righthand
Definition: pathnodes.h:2176
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:291
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition: analyzejoins.c:964
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1676
Relids lateral_relids
Definition: pathnodes.h:690
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:2427
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: pathnodes.h:227
GetForeignJoinPaths_function GetForeignJoinPaths
Definition: fdwapi.h:202
Relids param_source_rels
Definition: pathnodes.h:2429
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:949
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
struct FdwRoutine * fdwroutine
Definition: pathnodes.h:718
List * mergeclause_list
Definition: pathnodes.h:2425
Relids relids
Definition: pathnodes.h:665
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:1931
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:27
bool enable_mergejoin
Definition: costsize.c:136
#define lfirst(lc)
Definition: pg_list.h:190
JoinType jointype
Definition: pathnodes.h:2179
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:4370
bool enable_hashjoin
Definition: costsize.c:137
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
Relids min_lefthand
Definition: pathnodes.h:2175
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:793
Relids top_parent_relids
Definition: pathnodes.h:738
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1331

◆ build_expression_pathkey()

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

Definition at line 782 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().

788 {
789  List *pathkeys;
790  Oid opfamily,
791  opcintype;
792  int16 strategy;
793  PathKey *cpathkey;
794 
795  /* Find the operator in pg_amop --- failure shouldn't happen */
796  if (!get_ordering_op_properties(opno,
797  &opfamily, &opcintype, &strategy))
798  elog(ERROR, "operator %u is not a valid ordering operator",
799  opno);
800 
801  cpathkey = make_pathkey_from_sortinfo(root,
802  expr,
803  nullable_relids,
804  opfamily,
805  opcintype,
806  exprCollation((Node *) expr),
807  (strategy == BTGreaterStrategyNumber),
808  (strategy == BTGreaterStrategyNumber),
809  0,
810  rel,
811  create_it);
812 
813  if (cpathkey)
814  pathkeys = list_make1(cpathkey);
815  else
816  pathkeys = NIL;
817 
818  return pathkeys;
819 }
signed short int16
Definition: c.h:354
#define NIL
Definition: pg_list.h:65
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Definition: nodes.h:529
unsigned int Oid
Definition: postgres_ext.h:31
#define list_make1(x1)
Definition: pg_list.h:227
#define ERROR
Definition: elog.h:43
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, int16 *strategy)
Definition: lsyscache.c:205
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:719
#define elog(elevel,...)
Definition: elog.h:214
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:177
Definition: pg_list.h:50

◆ build_index_pathkeys()

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

Definition at line 523 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().

526 {
527  List *retval = NIL;
528  ListCell *lc;
529  int i;
530 
531  if (index->sortopfamily == NULL)
532  return NIL; /* non-orderable index */
533 
534  i = 0;
535  foreach(lc, index->indextlist)
536  {
537  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
538  Expr *indexkey;
539  bool reverse_sort;
540  bool nulls_first;
541  PathKey *cpathkey;
542 
543  /*
544  * INCLUDE columns are stored in index unordered, so they don't
545  * support ordered index scan.
546  */
547  if (i >= index->nkeycolumns)
548  break;
549 
550  /* We assume we don't need to make a copy of the tlist item */
551  indexkey = indextle->expr;
552 
553  if (ScanDirectionIsBackward(scandir))
554  {
555  reverse_sort = !index->reverse_sort[i];
556  nulls_first = !index->nulls_first[i];
557  }
558  else
559  {
560  reverse_sort = index->reverse_sort[i];
561  nulls_first = index->nulls_first[i];
562  }
563 
564  /*
565  * OK, try to make a canonical pathkey for this sort key. Note we're
566  * underneath any outer joins, so nullable_relids should be NULL.
567  */
568  cpathkey = make_pathkey_from_sortinfo(root,
569  indexkey,
570  NULL,
571  index->sortopfamily[i],
572  index->opcintype[i],
573  index->indexcollations[i],
574  reverse_sort,
575  nulls_first,
576  0,
577  index->rel->relids,
578  false);
579 
580  if (cpathkey)
581  {
582  /*
583  * We found the sort key in an EquivalenceClass, so it's relevant
584  * for this query. Add it to list, unless it's redundant.
585  */
586  if (!pathkey_is_redundant(cpathkey, retval))
587  retval = lappend(retval, cpathkey);
588  }
589  else
590  {
591  /*
592  * Boolean index keys might be redundant even if they do not
593  * appear in an EquivalenceClass, because of our special treatment
594  * of boolean equality conditions --- see the comment for
595  * indexcol_is_bool_constant_for_query(). If that applies, we can
596  * continue to examine lower-order index columns. Otherwise, the
597  * sort key is not an interesting sort order for this query, so we
598  * should stop considering index columns; any lower-order sort
599  * keys won't be useful either.
600  */
602  break;
603  }
604 
605  i++;
606  }
607 
608  return retval;
609 }
#define NIL
Definition: pg_list.h:65
Oid * indexcollations
Definition: pathnodes.h:832
List * indextlist
Definition: pathnodes.h:846
Oid * sortopfamily
Definition: pathnodes.h:835
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
RelOptInfo * rel
Definition: pathnodes.h:820
Relids relids
Definition: pathnodes.h:665
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:321
#define lfirst(lc)
Definition: pg_list.h:190
Expr * expr
Definition: primnodes.h:1407
int nkeycolumns
Definition: pathnodes.h:829
Oid * opcintype
Definition: pathnodes.h:834
bool indexcol_is_bool_constant_for_query(IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3757
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:177
bool * nulls_first
Definition: pathnodes.h:837
bool * reverse_sort
Definition: pathnodes.h:836
Definition: pg_list.h:50

◆ build_join_pathkeys()

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

Definition at line 1082 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().

1086 {
1087  if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
1088  return NIL;
1089 
1090  /*
1091  * This used to be quite a complex bit of code, but now that all pathkey
1092  * sublists start out life canonicalized, we don't have to do a darn thing
1093  * here!
1094  *
1095  * We do, however, need to truncate the pathkeys list, since it may
1096  * contain pathkeys that were useful for forming this joinrel but are
1097  * uninteresting to higher levels.
1098  */
1099  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1100 }
#define NIL
Definition: pg_list.h:65
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:1870

◆ build_partition_pathkeys()

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

Definition at line 699 of file pathkeys.c.

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

Referenced by generate_orderedappend_paths().

701 {
702  List *retval = NIL;
703  PartitionScheme partscheme = partrel->part_scheme;
704  int i;
705 
706  Assert(partscheme != NULL);
707  Assert(partitions_are_ordered(partrel->boundinfo, partrel->nparts));
708  /* For now, we can only cope with baserels */
709  Assert(IS_SIMPLE_REL(partrel));
710 
711  for (i = 0; i < partscheme->partnatts; i++)
712  {
713  PathKey *cpathkey;
714  Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
715 
716  /*
717  * Try to make a canonical pathkey for this partkey.
718  *
719  * We're considering a baserel scan, so nullable_relids should be
720  * NULL. Also, we assume the PartitionDesc lists any NULL partition
721  * last, so we treat the scan like a NULLS LAST index: we have
722  * nulls_first for backwards scan only.
723  */
724  cpathkey = make_pathkey_from_sortinfo(root,
725  keyCol,
726  NULL,
727  partscheme->partopfamily[i],
728  partscheme->partopcintype[i],
729  partscheme->partcollation[i],
730  ScanDirectionIsBackward(scandir),
731  ScanDirectionIsBackward(scandir),
732  0,
733  partrel->relids,
734  false);
735 
736 
737  if (cpathkey)
738  {
739  /*
740  * We found the sort key in an EquivalenceClass, so it's relevant
741  * for this query. Add it to list, unless it's redundant.
742  */
743  if (!pathkey_is_redundant(cpathkey, retval))
744  retval = lappend(retval, cpathkey);
745  }
746  else
747  {
748  /*
749  * Boolean partition keys might be redundant even if they do not
750  * appear in an EquivalenceClass, because of our special treatment
751  * of boolean equality conditions --- see the comment for
752  * partkey_is_bool_constant_for_query(). If that applies, we can
753  * continue to examine lower-order partition keys. Otherwise, the
754  * sort key is not an interesting sort order for this query, so we
755  * should stop considering partition columns; any lower-order sort
756  * keys won't be useful either.
757  */
758  if (!partkey_is_bool_constant_for_query(partrel, i))
759  {
760  *partialkeys = true;
761  return retval;
762  }
763  }
764  }
765 
766  *partialkeys = false;
767  return retval;
768 }
#define NIL
Definition: pg_list.h:65
static bool partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:629
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:638
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
List ** partexprs
Definition: pathnodes.h:753
#define linitial(l)
Definition: pg_list.h:195
int nparts
Definition: pathnodes.h:743
Relids relids
Definition: pathnodes.h:665
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:321
struct PartitionBoundInfoData * boundinfo
Definition: pathnodes.h:746
bool partitions_are_ordered(PartitionBoundInfo boundinfo, int nparts)
Definition: partbounds.c:2750
#define Assert(condition)
Definition: c.h:738
int i
PartitionScheme part_scheme
Definition: pathnodes.h:742
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:177
Definition: pg_list.h:50

◆ canonicalize_ec_expression()

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

Definition at line 499 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().

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

◆ check_index_predicates()

void check_index_predicates ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 3395 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().

3396 {
3397  List *clauselist;
3398  bool have_partial;
3399  bool is_target_rel;
3400  Relids otherrels;
3401  ListCell *lc;
3402 
3403  /* Indexes are available only on base or "other" member relations. */
3404  Assert(IS_SIMPLE_REL(rel));
3405 
3406  /*
3407  * Initialize the indrestrictinfo lists to be identical to
3408  * baserestrictinfo, and check whether there are any partial indexes. If
3409  * not, this is all we need to do.
3410  */
3411  have_partial = false;
3412  foreach(lc, rel->indexlist)
3413  {
3415 
3416  index->indrestrictinfo = rel->baserestrictinfo;
3417  if (index->indpred)
3418  have_partial = true;
3419  }
3420  if (!have_partial)
3421  return;
3422 
3423  /*
3424  * Construct a list of clauses that we can assume true for the purpose of
3425  * proving the index(es) usable. Restriction clauses for the rel are
3426  * always usable, and so are any join clauses that are "movable to" this
3427  * rel. Also, we can consider any EC-derivable join clauses (which must
3428  * be "movable to" this rel, by definition).
3429  */
3430  clauselist = list_copy(rel->baserestrictinfo);
3431 
3432  /* Scan the rel's join clauses */
3433  foreach(lc, rel->joininfo)
3434  {
3435  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3436 
3437  /* Check if clause can be moved to this rel */
3438  if (!join_clause_is_movable_to(rinfo, rel))
3439  continue;
3440 
3441  clauselist = lappend(clauselist, rinfo);
3442  }
3443 
3444  /*
3445  * Add on any equivalence-derivable join clauses. Computing the correct
3446  * relid sets for generate_join_implied_equalities is slightly tricky
3447  * because the rel could be a child rel rather than a true baserel, and in
3448  * that case we must remove its parents' relid(s) from all_baserels.
3449  */
3450  if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
3451  otherrels = bms_difference(root->all_baserels,
3452  find_childrel_parents(root, rel));
3453  else
3454  otherrels = bms_difference(root->all_baserels, rel->relids);
3455 
3456  if (!bms_is_empty(otherrels))
3457  clauselist =
3458  list_concat(clauselist,
3460  bms_union(rel->relids,
3461  otherrels),
3462  otherrels,
3463  rel));
3464 
3465  /*
3466  * Normally we remove quals that are implied by a partial index's
3467  * predicate from indrestrictinfo, indicating that they need not be
3468  * checked explicitly by an indexscan plan using this index. However, if
3469  * the rel is a target relation of UPDATE/DELETE/SELECT FOR UPDATE, we
3470  * cannot remove such quals from the plan, because they need to be in the
3471  * plan so that they will be properly rechecked by EvalPlanQual testing.
3472  * Some day we might want to remove such quals from the main plan anyway
3473  * and pass them through to EvalPlanQual via a side channel; but for now,
3474  * we just don't remove implied quals at all for target relations.
3475  */
3476  is_target_rel = (rel->relid == root->parse->resultRelation ||
3477  get_plan_rowmark(root->rowMarks, rel->relid) != NULL);
3478 
3479  /*
3480  * Now try to prove each index predicate true, and compute the
3481  * indrestrictinfo lists for partial indexes. Note that we compute the
3482  * indrestrictinfo list even for non-predOK indexes; this might seem
3483  * wasteful, but we may be able to use such indexes in OR clauses, cf
3484  * generate_bitmap_or_paths().
3485  */
3486  foreach(lc, rel->indexlist)
3487  {
3488  IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
3489  ListCell *lcr;
3490 
3491  if (index->indpred == NIL)
3492  continue; /* ignore non-partial indexes here */
3493 
3494  if (!index->predOK) /* don't repeat work if already proven OK */
3495  index->predOK = predicate_implied_by(index->indpred, clauselist,
3496  false);
3497 
3498  /* If rel is an update target, leave indrestrictinfo as set above */
3499  if (is_target_rel)
3500  continue;
3501 
3502  /* Else compute indrestrictinfo as the non-implied quals */
3503  index->indrestrictinfo = NIL;
3504  foreach(lcr, rel->baserestrictinfo)
3505  {
3506  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
3507 
3508  /* predicate_implied_by() assumes first arg is immutable */
3509  if (contain_mutable_functions((Node *) rinfo->clause) ||
3511  index->indpred, false))
3512  index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
3513  }
3514  }
3515 }
#define NIL
Definition: pg_list.h:65
List * rowMarks
Definition: pathnodes.h:292
Query * parse
Definition: pathnodes.h:179
RelOptKind reloptkind
Definition: pathnodes.h:662
List * baserestrictinfo
Definition: pathnodes.h:727
int resultRelation
Definition: parsenodes.h:122
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:291
List * list_copy(const List *oldlist)
Definition: list.c:1403
Definition: nodes.h:529
List * list_concat(List *list1, const List *list2)
Definition: list.c:515
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:638
Definition: type.h:89
#define list_make1(x1)
Definition: pg_list.h:227
Relids all_baserels
Definition: pathnodes.h:227
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1154
List * joininfo
Definition: pathnodes.h:731
Relids relids
Definition: pathnodes.h:665
Index relid
Definition: pathnodes.h:693
List * lappend(List *list, void *datum)
Definition: list.c:321
Expr * clause
Definition: pathnodes.h:1985
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
List * indrestrictinfo
Definition: pathnodes.h:848
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1243
List * indexlist
Definition: pathnodes.h:702
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:225
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:504
PlanRowMark * get_plan_rowmark(List *rowmarks, Index rtindex)
Definition: preptlist.c:425
bool contain_mutable_functions(Node *clause)
Definition: clauses.c:647
List * indpred
Definition: pathnodes.h:844
bool predicate_implied_by(List *predicate_list, List *clause_list, bool weak)
Definition: predtest.c:151
Definition: pg_list.h:50

◆ compare_pathkeys()

PathKeysComparison compare_pathkeys ( List keys1,
List keys2 
)

Definition at line 285 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().

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

◆ compute_parallel_worker()

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

Definition at line 3794 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().

3796 {
3797  int parallel_workers = 0;
3798 
3799  /*
3800  * If the user has set the parallel_workers reloption, use that; otherwise
3801  * select a default number of workers.
3802  */
3803  if (rel->rel_parallel_workers != -1)
3804  parallel_workers = rel->rel_parallel_workers;
3805  else
3806  {
3807  /*
3808  * If the number of pages being scanned is insufficient to justify a
3809  * parallel scan, just return zero ... unless it's an inheritance
3810  * child. In that case, we want to generate a parallel path here
3811  * anyway. It might not be worthwhile just for this relation, but
3812  * when combined with all of its inheritance siblings it may well pay
3813  * off.
3814  */
3815  if (rel->reloptkind == RELOPT_BASEREL &&
3816  ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
3817  (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
3818  return 0;
3819 
3820  if (heap_pages >= 0)
3821  {
3822  int heap_parallel_threshold;
3823  int heap_parallel_workers = 1;
3824 
3825  /*
3826  * Select the number of workers based on the log of the size of
3827  * the relation. This probably needs to be a good deal more
3828  * sophisticated, but we need something here for now. Note that
3829  * the upper limit of the min_parallel_table_scan_size GUC is
3830  * chosen to prevent overflow here.
3831  */
3832  heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
3833  while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
3834  {
3835  heap_parallel_workers++;
3836  heap_parallel_threshold *= 3;
3837  if (heap_parallel_threshold > INT_MAX / 3)
3838  break; /* avoid overflow */
3839  }
3840 
3841  parallel_workers = heap_parallel_workers;
3842  }
3843 
3844  if (index_pages >= 0)
3845  {
3846  int index_parallel_workers = 1;
3847  int index_parallel_threshold;
3848 
3849  /* same calculation as for heap_pages above */
3850  index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
3851  while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
3852  {
3853  index_parallel_workers++;
3854  index_parallel_threshold *= 3;
3855  if (index_parallel_threshold > INT_MAX / 3)
3856  break; /* avoid overflow */
3857  }
3858 
3859  if (parallel_workers > 0)
3860  parallel_workers = Min(parallel_workers, index_parallel_workers);
3861  else
3862  parallel_workers = index_parallel_workers;
3863  }
3864  }
3865 
3866  /* In no case use more than caller supplied maximum number of workers */
3867  parallel_workers = Min(parallel_workers, max_workers);
3868 
3869  return parallel_workers;
3870 }
RelOptKind reloptkind
Definition: pathnodes.h:662
#define Min(x, y)
Definition: c.h:920
uint32 BlockNumber
Definition: block.h:31
int min_parallel_index_scan_size
Definition: allpaths.c:65
int rel_parallel_workers
Definition: pathnodes.h:711
#define Max(x, y)
Definition: c.h:914
int min_parallel_table_scan_size
Definition: allpaths.c:64

◆ convert_subquery_pathkeys()

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

Definition at line 838 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, find_var_for_subquery_tle(), get_eclass_for_sort_expr(), get_sortgroupref_tle(), i, lappend(), lfirst, linitial, list_length(), list_nth(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_eclass, PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, PlannerInfo::query_pathkeys, and RelOptInfo::relids.

Referenced by set_subquery_pathlist().

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

◆ create_index_paths()

void create_index_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 232 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, NIL, IndexOptInfo::nkeycolumns, IndexClauseSet::nonempty, IndexOptInfo::predOK, and RelOptInfo::relid.

Referenced by set_plain_rel_pathlist().

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

◆ create_partial_bitmap_paths()

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

Definition at line 3758 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().

3760 {
3761  int parallel_workers;
3762  double pages_fetched;
3763 
3764  /* Compute heap pages for bitmap heap scan */
3765  pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
3766  NULL, NULL);
3767 
3768  parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
3770 
3771  if (parallel_workers <= 0)
3772  return;
3773 
3774  add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
3775  bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
3776 }
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:3794
Relids lateral_relids
Definition: pathnodes.h:690
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:749
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:5731
BitmapHeapPath * create_bitmap_heap_path(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual, Relids required_outer, double loop_count, int parallel_degree)
Definition: pathnode.c:1046

◆ create_tidscan_paths()

void create_tidscan_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 385 of file tidpath.c.

References add_path(), RelOptInfo::baserestrictinfo, BuildParameterizedTidPaths(), create_tidscan_path(), ec_member_matches_ctid(), generate_implied_equalities_for_column(), RelOptInfo::has_eclass_joins, RelOptInfo::joininfo, RelOptInfo::lateral_referencers, RelOptInfo::lateral_relids, and TidQualFromRestrictInfoList().

Referenced by set_plain_rel_pathlist().

386 {
387  List *tidquals;
388 
389  /*
390  * If any suitable quals exist in the rel's baserestrict list, generate a
391  * plain (unparameterized) TidPath with them.
392  */
393  tidquals = TidQualFromRestrictInfoList(rel->baserestrictinfo, rel);
394 
395  if (tidquals)
396  {
397  /*
398  * This path uses no join clauses, but it could still have required
399  * parameterization due to LATERAL refs in its tlist.
400  */
401  Relids required_outer = rel->lateral_relids;
402 
403  add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
404  required_outer));
405  }
406 
407  /*
408  * Try to generate parameterized TidPaths using equality clauses extracted
409  * from EquivalenceClasses. (This is important since simple "t1.ctid =
410  * t2.ctid" clauses will turn into ECs.)
411  */
412  if (rel->has_eclass_joins)
413  {
414  List *clauses;
415 
416  /* Generate clauses, skipping any that join to lateral_referencers */
418  rel,
420  NULL,
421  rel->lateral_referencers);
422 
423  /* Generate a path for each usable join clause */
424  BuildParameterizedTidPaths(root, rel, clauses);
425  }
426 
427  /*
428  * Also consider parameterized TidPaths using "loose" join quals. Quals
429  * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
430  * join quals, for example.
431  */
432  BuildParameterizedTidPaths(root, rel, rel->joininfo);
433 }
bool has_eclass_joins
Definition: pathnodes.h:733
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
List * baserestrictinfo
Definition: pathnodes.h:727
static bool ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)
Definition: tidpath.c:368
Relids lateral_relids
Definition: pathnodes.h:690
static void BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
Definition: tidpath.c:313
List * joininfo
Definition: pathnodes.h:731
Relids lateral_referencers
Definition: pathnodes.h:701
static List * TidQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
Definition: tidpath.c:230
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1151
Definition: pg_list.h:50
List * generate_implied_equalities_for_column(PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
Definition: equivclass.c:2525

◆ eclass_useful_for_merging()

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

Definition at line 2766 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().

2769 {
2770  Relids relids;
2771  ListCell *lc;
2772 
2773  Assert(!eclass->ec_merged);
2774 
2775  /*
2776  * Won't generate joinclauses if const or single-member (the latter test
2777  * covers the volatile case too)
2778  */
2779  if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
2780  return false;
2781 
2782  /*
2783  * Note we don't test ec_broken; if we did, we'd need a separate code path
2784  * to look through ec_sources. Checking the members anyway is OK as a
2785  * possibly-overoptimistic heuristic.
2786  */
2787 
2788  /* If specified rel is a child, we must consider the topmost parent rel */
2789  if (IS_OTHER_REL(rel))
2790  {
2792  relids = rel->top_parent_relids;
2793  }
2794  else
2795  relids = rel->relids;
2796 
2797  /* If rel already includes all members of eclass, no point in searching */
2798  if (bms_is_subset(eclass->ec_relids, relids))
2799  return false;
2800 
2801  /* To join, we need a member not in the given rel */
2802  foreach(lc, eclass->ec_members)
2803  {
2804  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
2805 
2806  if (cur_em->em_is_child)
2807  continue; /* ignore children here */
2808 
2809  if (!bms_overlap(cur_em->em_relids, relids))
2810  return true;
2811  }
2812 
2813  return false;
2814 }
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:653
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
Relids ec_relids
Definition: pathnodes.h:967
Relids relids
Definition: pathnodes.h:665
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
static int list_length(const List *l)
Definition: pg_list.h:169
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:976
List * ec_members
Definition: pathnodes.h:964
Relids top_parent_relids
Definition: pathnodes.h:738

◆ exprs_known_equal()

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

Definition at line 2113 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().

2114 {
2115  ListCell *lc1;
2116 
2117  foreach(lc1, root->eq_classes)
2118  {
2119  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2120  bool item1member = false;
2121  bool item2member = false;
2122  ListCell *lc2;
2123 
2124  /* Never match to a volatile EC */
2125  if (ec->ec_has_volatile)
2126  continue;
2127 
2128  foreach(lc2, ec->ec_members)
2129  {
2131 
2132  if (em->em_is_child)
2133  continue; /* ignore children here */
2134  if (equal(item1, em->em_expr))
2135  item1member = true;
2136  else if (equal(item2, em->em_expr))
2137  item2member = true;
2138  /* Exit as soon as equality is proven */
2139  if (item1member && item2member)
2140  return true;
2141  }
2142  }
2143  return false;
2144 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3033
#define lfirst(lc)
Definition: pg_list.h:190
List * eq_classes
Definition: pathnodes.h:266
bool ec_has_volatile
Definition: pathnodes.h:970
List * ec_members
Definition: pathnodes.h:964

◆ find_em_expr_for_rel()

Expr* find_em_expr_for_rel ( EquivalenceClass ec,
RelOptInfo rel 
)

Definition at line 782 of file equivclass.c.

References bms_is_empty(), bms_is_subset(), EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_relids, lfirst, and RelOptInfo::relids.

783 {
784  ListCell *lc_em;
785 
786  foreach(lc_em, ec->ec_members)
787  {
788  EquivalenceMember *em = lfirst(lc_em);
789 
790  if (bms_is_subset(em->em_relids, rel->relids) &&
791  !bms_is_empty(em->em_relids))
792  {
793  /*
794  * If there is more than one equivalence member whose Vars are
795  * taken entirely from this relation, we'll be content to choose
796  * any one of those.
797  */
798  return em->em_expr;
799  }
800  }
801 
802  /* We didn't find any suitable equivalence class expression */
803  return NULL;
804 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
Relids relids
Definition: pathnodes.h:665
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define lfirst(lc)
Definition: pg_list.h:190
List * ec_members
Definition: pathnodes.h:964

◆ find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1262 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().

1265 {
1266  List *mergeclauses = NIL;
1267  ListCell *i;
1268 
1269  /* make sure we have eclasses cached in the clauses */
1270  foreach(i, restrictinfos)
1271  {
1272  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1273 
1274  update_mergeclause_eclasses(root, rinfo);
1275  }
1276 
1277  foreach(i, pathkeys)
1278  {
1279  PathKey *pathkey = (PathKey *) lfirst(i);
1280  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1281  List *matched_restrictinfos = NIL;
1282  ListCell *j;
1283 
1284  /*----------
1285  * A mergejoin clause matches a pathkey if it has the same EC.
1286  * If there are multiple matching clauses, take them all. In plain
1287  * inner-join scenarios we expect only one match, because
1288  * equivalence-class processing will have removed any redundant
1289  * mergeclauses. However, in outer-join scenarios there might be
1290  * multiple matches. An example is
1291  *
1292  * select * from a full join b
1293  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1294  *
1295  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1296  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1297  * we *must* do so or we will be unable to form a valid plan.
1298  *
1299  * We expect that the given pathkeys list is canonical, which means
1300  * no two members have the same EC, so it's not possible for this
1301  * code to enter the same mergeclause into the result list twice.
1302  *
1303  * It's possible that multiple matching clauses might have different
1304  * ECs on the other side, in which case the order we put them into our
1305  * result makes a difference in the pathkeys required for the inner
1306  * input rel. However this routine hasn't got any info about which
1307  * order would be best, so we don't worry about that.
1308  *
1309  * It's also possible that the selected mergejoin clauses produce
1310  * a noncanonical ordering of pathkeys for the inner side, ie, we
1311  * might select clauses that reference b.v1, b.v2, b.v1 in that
1312  * order. This is not harmful in itself, though it suggests that
1313  * the clauses are partially redundant. Since the alternative is
1314  * to omit mergejoin clauses and thereby possibly fail to generate a
1315  * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1316  * has to delete duplicates when it constructs the inner pathkeys
1317  * list, and we also have to deal with such cases specially in
1318  * create_mergejoin_plan().
1319  *----------
1320  */
1321  foreach(j, restrictinfos)
1322  {
1323  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1324  EquivalenceClass *clause_ec;
1325 
1326  clause_ec = rinfo->outer_is_left ?
1327  rinfo->left_ec : rinfo->right_ec;
1328  if (clause_ec == pathkey_ec)
1329  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1330  }
1331 
1332  /*
1333  * If we didn't find a mergeclause, we're done --- any additional
1334  * sort-key positions in the pathkeys are useless. (But we can still
1335  * mergejoin if we found at least one mergeclause.)
1336  */
1337  if (matched_restrictinfos == NIL)
1338  break;
1339 
1340  /*
1341  * If we did find usable mergeclause(s) for this sort-key position,
1342  * add them to result list.
1343  */
1344  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1345  }
1346 
1347  return mergeclauses;
1348 }
#define NIL
Definition: pg_list.h:65
List * list_concat(List *list1, const List *list2)
Definition: list.c:515
EquivalenceClass * right_ec
Definition: pathnodes.h:2034
bool outer_is_left
Definition: pathnodes.h:2040
List * lappend(List *list, void *datum)
Definition: list.c:321
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041
EquivalenceClass * left_ec
Definition: pathnodes.h:2033
int i
Definition: pg_list.h:50
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1228

◆ generate_base_implied_equalities()

void generate_base_implied_equalities ( PlannerInfo root)

Definition at line 855 of file equivclass.c.

References Assert, bms_add_member(), bms_membership(), BMS_MULTIPLE, bms_next_member(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, PlannerInfo::ec_merging_done, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, PlannerInfo::eq_classes, generate_base_implied_equalities_broken(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), RelOptInfo::has_eclass_joins, i, lfirst, list_length(), RELOPT_BASEREL, RelOptInfo::reloptkind, and PlannerInfo::simple_rel_array.

Referenced by query_planner().

856 {
857  int ec_index;
858  ListCell *lc;
859 
860  /*
861  * At this point, we're done absorbing knowledge of equivalences in the
862  * query, so no further EC merging should happen, and ECs remaining in the
863  * eq_classes list can be considered canonical. (But note that it's still
864  * possible for new single-member ECs to be added through
865  * get_eclass_for_sort_expr().)
866  */
867  root->ec_merging_done = true;
868 
869  ec_index = 0;
870  foreach(lc, root->eq_classes)
871  {
873  bool can_generate_joinclause = false;
874  int i;
875 
876  Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
877  Assert(!ec->ec_broken); /* not yet anyway... */
878 
879  /*
880  * Generate implied equalities that are restriction clauses.
881  * Single-member ECs won't generate any deductions, either here or at
882  * the join level.
883  */
884  if (list_length(ec->ec_members) > 1)
885  {
886  if (ec->ec_has_const)
888  else
890 
891  /* Recover if we failed to generate required derived clauses */
892  if (ec->ec_broken)
894 
895  /* Detect whether this EC might generate join clauses */
896  can_generate_joinclause =
898  }
899 
900  /*
901  * Mark the base rels cited in each eclass (which should all exist by
902  * now) with the eq_classes indexes of all eclasses mentioning them.
903  * This will let us avoid searching in subsequent lookups. While
904  * we're at it, we can mark base rels that have pending eclass joins;
905  * this is a cheap version of has_relevant_eclass_joinclause().
906  */
907  i = -1;
908  while ((i = bms_next_member(ec->ec_relids, i)) > 0)
909  {
910  RelOptInfo *rel = root->simple_rel_array[i];
911 
913 
915  ec_index);
916 
917  if (can_generate_joinclause)
918  rel->has_eclass_joins = true;
919  }
920 
921  ec_index++;
922  }
923 }
bool has_eclass_joins
Definition: pathnodes.h:733
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1006
RelOptKind reloptkind
Definition: pathnodes.h:662
bool ec_merging_done
Definition: pathnodes.h:268
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
static void generate_base_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1097
struct RelOptInfo ** simple_rel_array
Definition: pathnodes.h:203
Relids ec_relids
Definition: pathnodes.h:967
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:672
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:169
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:736
int i
static void generate_base_implied_equalities_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:929
Bitmapset * eclass_indexes
Definition: pathnodes.h:707
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:976
List * ec_members
Definition: pathnodes.h:964

◆ generate_gather_paths()

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

Definition at line 2685 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 generate_useful_gather_paths().

2686 {
2687  Path *cheapest_partial_path;
2688  Path *simple_gather_path;
2689  ListCell *lc;
2690  double rows;
2691  double *rowsp = NULL;
2692 
2693  /* If there are no partial paths, there's nothing to do here. */
2694  if (rel->partial_pathlist == NIL)
2695  return;
2696 
2697  /* Should we override the rel's rowcount estimate? */
2698  if (override_rows)
2699  rowsp = &rows;
2700 
2701  /*
2702  * The output of Gather is always unsorted, so there's only one partial
2703  * path of interest: the cheapest one. That will be the one at the front
2704  * of partial_pathlist because of the way add_partial_path works.
2705  */
2706  cheapest_partial_path = linitial(rel->partial_pathlist);
2707  rows =
2708  cheapest_partial_path->rows * cheapest_partial_path->parallel_workers;
2709  simple_gather_path = (Path *)
2710  create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
2711  NULL, rowsp);
2712  add_path(rel, simple_gather_path);
2713 
2714  /*
2715  * For each useful ordering, we can consider an order-preserving Gather
2716  * Merge.
2717  */
2718  foreach(lc, rel->partial_pathlist)
2719  {
2720  Path *subpath = (Path *) lfirst(lc);
2721  GatherMergePath *path;
2722 
2723  if (subpath->pathkeys == NIL)
2724  continue;
2725 
2726  rows = subpath->rows * subpath->parallel_workers;
2727  path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
2728  subpath->pathkeys, NULL, rowsp);
2729  add_path(rel, &path->path);
2730  }
2731 }
#define NIL
Definition: pg_list.h:65
GatherPath * create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, Relids required_outer, double *rows)
Definition: pathnode.c:1845
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
int parallel_workers
Definition: pathnodes.h:1151
List * partial_pathlist
Definition: pathnodes.h:681
#define linitial(l)
Definition: pg_list.h:195
GatherMergePath * create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, List *pathkeys, Relids required_outer, double *rows)
Definition: pathnode.c:1754
List * pathkeys
Definition: pathnodes.h:1158
#define lfirst(lc)
Definition: pg_list.h:190
double rows
Definition: pathnodes.h:1154
struct PathTarget * reltarget
Definition: pathnodes.h:676
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:241

◆ 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 2525 of file equivclass.c.

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

Referenced by create_tidscan_paths(), match_eclass_clauses_to_index(), and postgresGetForeignPaths().

2530 {
2531  List *result = NIL;
2532  bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
2533  Relids parent_relids;
2534  int i;
2535 
2536  /* Should be OK to rely on eclass_indexes */
2537  Assert(root->ec_merging_done);
2538 
2539  /* Indexes are available only on base or "other" member relations. */
2540  Assert(IS_SIMPLE_REL(rel));
2541 
2542  /* If it's a child rel, we'll need to know what its parent(s) are */
2543  if (is_child_rel)
2544  parent_relids = find_childrel_parents(root, rel);
2545  else
2546  parent_relids = NULL; /* not used, but keep compiler quiet */
2547 
2548  i = -1;
2549  while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
2550  {
2551  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2552  EquivalenceMember *cur_em;
2553  ListCell *lc2;
2554 
2555  /* Sanity check eclass_indexes only contain ECs for rel */
2556  Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
2557 
2558  /*
2559  * Won't generate joinclauses if const or single-member (the latter
2560  * test covers the volatile case too)
2561  */
2562  if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
2563  continue;
2564 
2565  /*
2566  * Scan members, looking for a match to the target column. Note that
2567  * child EC members are considered, but only when they belong to the
2568  * target relation. (Unlike regular members, the same expression
2569  * could be a child member of more than one EC. Therefore, it's
2570  * potentially order-dependent which EC a child relation's target
2571  * column gets matched to. This is annoying but it only happens in
2572  * corner cases, so for now we live with just reporting the first
2573  * match. See also get_eclass_for_sort_expr.)
2574  */
2575  cur_em = NULL;
2576  foreach(lc2, cur_ec->ec_members)
2577  {
2578  cur_em = (EquivalenceMember *) lfirst(lc2);
2579  if (bms_equal(cur_em->em_relids, rel->relids) &&
2580  callback(root, rel, cur_ec, cur_em, callback_arg))
2581  break;
2582  cur_em = NULL;
2583  }
2584 
2585  if (!cur_em)
2586  continue;
2587 
2588  /*
2589  * Found our match. Scan the other EC members and attempt to generate
2590  * joinclauses.
2591  */
2592  foreach(lc2, cur_ec->ec_members)
2593  {
2594  EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
2595  Oid eq_op;
2596  RestrictInfo *rinfo;
2597 
2598  if (other_em->em_is_child)
2599  continue; /* ignore children here */
2600 
2601  /* Make sure it'll be a join to a different rel */
2602  if (other_em == cur_em ||
2603  bms_overlap(other_em->em_relids, rel->relids))
2604  continue;
2605 
2606  /* Forget it if caller doesn't want joins to this rel */
2607  if (bms_overlap(other_em->em_relids, prohibited_rels))
2608  continue;
2609 
2610  /*
2611  * Also, if this is a child rel, avoid generating a useless join
2612  * to its parent rel(s).
2613  */
2614  if (is_child_rel &&
2615  bms_overlap(parent_relids, other_em->em_relids))
2616  continue;
2617 
2618  eq_op = select_equality_operator(cur_ec,
2619  cur_em->em_datatype,
2620  other_em->em_datatype);
2621  if (!OidIsValid(eq_op))
2622  continue;
2623 
2624  /* set parent_ec to mark as redundant with other joinclauses */
2625  rinfo = create_join_clause(root, cur_ec, eq_op,
2626  cur_em, other_em,
2627  cur_ec);
2628 
2629  result = lappend(result, rinfo);
2630  }
2631 
2632  /*
2633  * If somehow we failed to create any join clauses, we might as well
2634  * keep scanning the ECs for another match. But if we did make any,
2635  * we're done, because we don't want to return non-redundant clauses.
2636  */
2637  if (result)
2638  break;
2639  }
2640 
2641  return result;
2642 }
#define NIL
Definition: pg_list.h:65
static RestrictInfo * create_join_clause(PlannerInfo *root, EquivalenceClass *ec, Oid opno, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
Definition: equivclass.c:1563
RelOptKind reloptkind
Definition: pathnodes.h:662
bool ec_merging_done
Definition: pathnodes.h:268
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
unsigned int Oid
Definition: postgres_ext.h:31
#define OidIsValid(objectId)
Definition: c.h:644
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:638
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
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:315
static Oid select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
Definition: equivclass.c:1528
Relids ec_relids
Definition: pathnodes.h:967
Relids relids
Definition: pathnodes.h:665
List * lappend(List *list, void *datum)
Definition: list.c:321
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1243
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:169
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
int i
Definition: pg_list.h:50
Bitmapset * eclass_indexes
Definition: pathnodes.h:707
List * ec_members
Definition: pathnodes.h:964
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:94

◆ generate_join_implied_equalities()

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

Definition at line 1154 of file equivclass.c.

References Assert, bms_is_empty(), bms_next_member(), bms_overlap(), bms_union(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), get_common_eclass_indexes(), i, IS_OTHER_REL, list_concat(), list_length(), list_nth(), NIL, RelOptInfo::relids, and RelOptInfo::top_parent_relids.

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

1158 {
1159  List *result = NIL;
1160  Relids inner_relids = inner_rel->relids;
1161  Relids nominal_inner_relids;
1162  Relids nominal_join_relids;
1163  Bitmapset *matching_ecs;
1164  int i;
1165 
1166  /* If inner rel is a child, extra setup work is needed */
1167  if (IS_OTHER_REL(inner_rel))
1168  {
1169  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1170 
1171  /* Fetch relid set for the topmost parent rel */
1172  nominal_inner_relids = inner_rel->top_parent_relids;
1173  /* ECs will be marked with the parent's relid, not the child's */
1174  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1175  }
1176  else
1177  {
1178  nominal_inner_relids = inner_relids;
1179  nominal_join_relids = join_relids;
1180  }
1181 
1182  /*
1183  * Get all eclasses in common between inner_rel's relids and outer_relids
1184  */
1185  matching_ecs = get_common_eclass_indexes(root, inner_rel->relids,
1186  outer_relids);
1187 
1188  i = -1;
1189  while ((i = bms_next_member(matching_ecs, i)) >= 0)
1190  {
1192  List *sublist = NIL;
1193 
1194  /* ECs containing consts do not need any further enforcement */
1195  if (ec->ec_has_const)
1196  continue;
1197 
1198  /* Single-member ECs won't generate any deductions */
1199  if (list_length(ec->ec_members) <= 1)
1200  continue;
1201 
1202  /* Sanity check that this eclass overlaps the join */
1203  Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
1204 
1205  if (!ec->ec_broken)
1207  ec,
1208  join_relids,
1209  outer_relids,
1210  inner_relids);
1211 
1212  /* Recover if we failed to generate required derived clauses */
1213  if (ec->ec_broken)
1215  ec,
1216  nominal_join_relids,
1217  outer_relids,
1218  nominal_inner_relids,
1219  inner_rel);
1220 
1221  result = list_concat(result, sublist);
1222  }
1223 
1224  return result;
1225 }
#define NIL
Definition: pg_list.h:65
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:653
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
List * list_concat(List *list1, const List *list2)
Definition: list.c:515
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
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:1479
Relids ec_relids
Definition: pathnodes.h:967
Relids relids
Definition: pathnodes.h:665
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1303
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
static Bitmapset * get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
Definition: equivclass.c:2911
#define Assert(condition)
Definition: c.h:738
List * eq_classes
Definition: pathnodes.h:266
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:225
static int list_length(const List *l)
Definition: pg_list.h:169
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
int i
Definition: pg_list.h:50
List * ec_members
Definition: pathnodes.h:964
Relids top_parent_relids
Definition: pathnodes.h:738

◆ 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 1232 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 get_joinrel_parampathinfo().

1237 {
1238  List *result = NIL;
1239  Relids inner_relids = inner_rel->relids;
1240  Relids nominal_inner_relids;
1241  Relids nominal_join_relids;
1242  ListCell *lc;
1243 
1244  /* If inner rel is a child, extra setup work is needed */
1245  if (IS_OTHER_REL(inner_rel))
1246  {
1247  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1248 
1249  /* Fetch relid set for the topmost parent rel */
1250  nominal_inner_relids = inner_rel->top_parent_relids;
1251  /* ECs will be marked with the parent's relid, not the child's */
1252  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1253  }
1254  else
1255  {
1256  nominal_inner_relids = inner_relids;
1257  nominal_join_relids = join_relids;
1258  }
1259 
1260  foreach(lc, eclasses)
1261  {
1263  List *sublist = NIL;
1264 
1265  /* ECs containing consts do not need any further enforcement */
1266  if (ec->ec_has_const)
1267  continue;
1268 
1269  /* Single-member ECs won't generate any deductions */
1270  if (list_length(ec->ec_members) <= 1)
1271  continue;
1272 
1273  /* We can quickly ignore any that don't overlap the join, too */
1274  if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1275  continue;
1276 
1277  if (!ec->ec_broken)
1279  ec,
1280  join_relids,
1281  outer_relids,
1282  inner_relids);
1283 
1284  /* Recover if we failed to generate required derived clauses */
1285  if (ec->ec_broken)
1287  ec,
1288  nominal_join_relids,
1289  outer_relids,
1290  nominal_inner_relids,
1291  inner_rel);
1292 
1293  result = list_concat(result, sublist);
1294  }
1295 
1296  return result;
1297 }
#define NIL
Definition: pg_list.h:65
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:653
List * list_concat(List *list1, const List *list2)
Definition: list.c:515
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:1479
Relids ec_relids
Definition: pathnodes.h:967
Relids relids
Definition: pathnodes.h:665
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1303
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:225
static int list_length(const List *l)
Definition: pg_list.h:169
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
Definition: pg_list.h:50
List * ec_members
Definition: pathnodes.h:964
Relids top_parent_relids
Definition: pathnodes.h:738

◆ generate_partitionwise_join_paths()

void generate_partitionwise_join_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 3882 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, RelOptInfo::consider_partitionwise_join, 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(), printf, RelOptInfo::relids, RelOptInfo::reltarget, RelOptInfo::rows, Path::rows, Query::rtable, set_cheapest(), PlannerInfo::simple_rte_array, Path::startup_cost, generate_unaccent_rules::stdout, subpath(), T_AggPath, T_AppendPath, T_BitmapAndPath, T_BitmapHeapPath, T_BitmapOrPath, T_CteScan, T_CustomPath, T_ForeignPath, T_FunctionScan, T_GatherMergePath, T_GatherPath, T_GroupingSetsPath, T_GroupPath, T_GroupResultPath, T_HashPath, T_IncrementalSortPath, T_IndexPath, T_LimitPath, T_LockRowsPath, T_MaterialPath, T_MergeAppendPath, T_MergePath, T_MinMaxAggPath, T_ModifyTablePath, T_NamedTuplestoreScan, T_NestPath, T_Path, T_ProjectionPath, T_ProjectSetPath, T_RecursiveUnionPath, T_Result, T_SampleScan, T_SeqScan, T_SetOpPath, T_SortPath, 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().

3883 {
3884  List *live_children = NIL;
3885  int cnt_parts;
3886  int num_parts;
3887  RelOptInfo **part_rels;
3888 
3889  /* Handle only join relations here. */
3890  if (!IS_JOIN_REL(rel))
3891  return;
3892 
3893  /* We've nothing to do if the relation is not partitioned. */
3894  if (!IS_PARTITIONED_REL(rel))
3895  return;
3896 
3897  /* The relation should have consider_partitionwise_join set. */
3899 
3900  /* Guard against stack overflow due to overly deep partition hierarchy. */
3902 
3903  num_parts = rel->nparts;
3904  part_rels = rel->part_rels;
3905 
3906  /* Collect non-dummy child-joins. */
3907  for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
3908  {
3909  RelOptInfo *child_rel = part_rels[cnt_parts];
3910 
3911  /* If it's been pruned entirely, it's certainly dummy. */
3912  if (child_rel == NULL)
3913  continue;
3914 
3915  /* Add partitionwise join paths for partitioned child-joins. */
3916  generate_partitionwise_join_paths(root, child_rel);
3917 
3918  set_cheapest(child_rel);
3919 
3920  /* Dummy children will not be scanned, so ignore those. */
3921  if (IS_DUMMY_REL(child_rel))
3922  continue;
3923 
3924 #ifdef OPTIMIZER_DEBUG
3925  debug_print_rel(root, child_rel);
3926 #endif
3927 
3928  live_children = lappend(live_children, child_rel);
3929  }
3930 
3931  /* If all child-joins are dummy, parent join is also dummy. */
3932  if (!live_children)
3933  {
3934  mark_dummy_rel(rel);
3935  return;
3936  }
3937 
3938  /* Build additional paths for this rel from child-join paths. */
3939  add_paths_to_append_rel(root, rel, live_children);
3940  list_free(live_children);
3941 }
#define NIL
Definition: pg_list.h:65
void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
Definition: allpaths.c:1297
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:3882
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:643
#define IS_DUMMY_REL(r)
Definition: pathnodes.h:1418
void check_stack_depth(void)
Definition: postgres.c:3312
int nparts
Definition: pathnodes.h:743
List * lappend(List *list, void *datum)
Definition: list.c:321
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:244
bool consider_partitionwise_join
Definition: pathnodes.h:736
void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1261
#define Assert(condition)
Definition: c.h:738
struct RelOptInfo ** part_rels
Definition: pathnodes.h:750
#define IS_PARTITIONED_REL(rel)
Definition: pathnodes.h:766
void list_free(List *list)
Definition: list.c:1376
Definition: pg_list.h:50

◆ generate_useful_gather_paths()

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

Definition at line 2816 of file allpaths.c.

References add_path(), Assert, create_gather_merge_path(), create_incremental_sort_path(), create_sort_path(), enable_incremental_sort, generate_gather_paths(), get_useful_pathkeys_for_relation(), lfirst, linitial, list_length(), NIL, Path::parallel_workers, RelOptInfo::partial_pathlist, GatherMergePath::path, Path::pathkeys, pathkeys_count_contained_in(), 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().

2817 {
2818  ListCell *lc;
2819  double rows;
2820  double *rowsp = NULL;
2821  List *useful_pathkeys_list = NIL;
2822  Path *cheapest_partial_path = NULL;
2823 
2824  /* If there are no partial paths, there's nothing to do here. */
2825  if (rel->partial_pathlist == NIL)
2826  return;
2827 
2828  /* Should we override the rel's rowcount estimate? */
2829  if (override_rows)
2830  rowsp = &rows;
2831 
2832  /* generate the regular gather (merge) paths */
2833  generate_gather_paths(root, rel, override_rows);
2834 
2835  /* consider incremental sort for interesting orderings */
2836  useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel);
2837 
2838  /* used for explicit (full) sort paths */
2839  cheapest_partial_path = linitial(rel->partial_pathlist);
2840 
2841  /*
2842  * Consider incremental sort paths for each interesting ordering.
2843  */
2844  foreach(lc, useful_pathkeys_list)
2845  {
2846  List *useful_pathkeys = lfirst(lc);
2847  ListCell *lc2;
2848  bool is_sorted;
2849  int presorted_keys;
2850 
2851  foreach(lc2, rel->partial_pathlist)
2852  {
2853  Path *subpath = (Path *) lfirst(lc2);
2854  GatherMergePath *path;
2855 
2856  /*
2857  * If the path has no ordering at all, then we can't use either
2858  * incremental sort or rely on implict sorting with a gather
2859  * merge.
2860  */
2861  if (subpath->pathkeys == NIL)
2862  continue;
2863 
2864  is_sorted = pathkeys_count_contained_in(useful_pathkeys,
2865  subpath->pathkeys,
2866  &presorted_keys);
2867 
2868  /*
2869  * We don't need to consider the case where a subpath is already
2870  * fully sorted because generate_gather_paths already creates a
2871  * gather merge path for every subpath that has pathkeys present.
2872  *
2873  * But since the subpath is already sorted, we know we don't need
2874  * to consider adding a sort (other either kind) on top of it, so
2875  * we can continue here.
2876  */
2877  if (is_sorted)
2878  continue;
2879 
2880  /*
2881  * Consider regular sort for the cheapest partial path (for each
2882  * useful pathkeys). We know the path is not sorted, because we'd
2883  * not get here otherwise.
2884  *
2885  * This is not redundant with the gather paths created in
2886  * generate_gather_paths, because that doesn't generate ordered
2887  * output. Here we add an explicit sort to match the useful
2888  * ordering.
2889  */
2890  if (cheapest_partial_path == subpath)
2891  {
2892  Path *tmp;
2893 
2894  tmp = (Path *) create_sort_path(root,
2895  rel,
2896  subpath,
2897  useful_pathkeys,
2898  -1.0);
2899 
2900  rows = tmp->rows * tmp->parallel_workers;
2901 
2902  path = create_gather_merge_path(root, rel,
2903  tmp,
2904  rel->reltarget,
2905  tmp->pathkeys,
2906  NULL,
2907  rowsp);
2908 
2909  add_path(rel, &path->path);
2910 
2911  /* Fall through */
2912  }
2913 
2914  /*
2915  * Consider incremental sort, but only when the subpath is already
2916  * partially sorted on a pathkey prefix.
2917  */
2918  if (enable_incremental_sort && presorted_keys > 0)
2919  {
2920  Path *tmp;
2921 
2922  /*
2923  * We should have already excluded pathkeys of length 1
2924  * because then presorted_keys > 0 would imply is_sorted was
2925  * true.
2926  */
2927  Assert(list_length(useful_pathkeys) != 1);
2928 
2929  tmp = (Path *) create_incremental_sort_path(root,
2930  rel,
2931  subpath,
2932  useful_pathkeys,
2933  presorted_keys,
2934  -1);
2935 
2936  path = create_gather_merge_path(root, rel,
2937  tmp,
2938  rel->reltarget,
2939  tmp->pathkeys,
2940  NULL,
2941  rowsp);
2942 
2943  add_path(rel, &path->path);
2944  }
2945  }
2946  }
2947 }
#define NIL
Definition: pg_list.h:65
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
bool enable_incremental_sort
Definition: costsize.c:131
SortPath * create_incremental_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, int presorted_keys, double limit_tuples)
Definition: pathnode.c:2769
int parallel_workers
Definition: pathnodes.h:1151
List * partial_pathlist
Definition: pathnodes.h:681
void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:2685
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:343
#define linitial(l)
Definition: pg_list.h:195
static List * get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:2752
GatherMergePath * create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, List *pathkeys, Relids required_outer, double *rows)
Definition: pathnode.c:1754
SortPath * create_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, double limit_tuples)
Definition: pathnode.c:2818
List * pathkeys
Definition: pathnodes.h:1158
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
double rows
Definition: pathnodes.h:1154
static int list_length(const List *l)
Definition: pg_list.h:169
Definition: pg_list.h:50
struct PathTarget * reltarget
Definition: pathnodes.h:676
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:241

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

453 {
454  Path *matched_path = NULL;
455  ListCell *l;
456 
457  foreach(l, paths)
458  {
459  Path *path = (Path *) lfirst(l);
460 
461  /*
462  * Since cost comparison is a lot cheaper than pathkey comparison, do
463  * that first. (XXX is that still true?)
464  */
465  if (matched_path != NULL &&
466  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
467  continue;
468 
469  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
470  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
471  matched_path = path;
472  }
473  return matched_path;
474 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1163
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
List * pathkeys
Definition: pathnodes.h:1158
#define lfirst(lc)
Definition: pg_list.h:190
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:117

◆ get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner ( List paths)

Definition at line 482 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().

483 {
484  ListCell *l;
485 
486  foreach(l, paths)
487  {
488  Path *innerpath = (Path *) lfirst(l);
489 
490  if (innerpath->parallel_safe &&
491  bms_is_empty(PATH_REQ_OUTER(innerpath)))
492  return innerpath;
493  }
494 
495  return NULL;
496 }
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1163
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define lfirst(lc)
Definition: pg_list.h:190
bool parallel_safe
Definition: pathnodes.h:1150

◆ 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 404 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_mergejoin_paths(), generate_orderedappend_paths(), and get_cheapest_parameterized_child_path().

408 {
409  Path *matched_path = NULL;
410  ListCell *l;
411 
412  foreach(l, paths)
413  {
414  Path *path = (Path *) lfirst(l);
415 
416  /*
417  * Since cost comparison is a lot cheaper than pathkey comparison, do
418  * that first. (XXX is that still true?)
419  */
420  if (matched_path != NULL &&
421  compare_path_costs(matched_path, path, cost_criterion) <= 0)
422  continue;
423 
424  if (require_parallel_safe && !path->parallel_safe)
425  continue;
426 
427  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
428  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
429  matched_path = path;
430  }
431  return matched_path;
432 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:71
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1163
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
List * pathkeys
Definition: pathnodes.h:1158
#define lfirst(lc)
Definition: pg_list.h:190
bool parallel_safe
Definition: pathnodes.h:1150

◆ 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 625 of file equivclass.c.

References add_eq_member(), Assert, bms_add_member(), bms_equal(), bms_intersect(), bms_next_member(), 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, PlannerInfo::ec_merging_done, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, RelOptInfo::eclass_indexes, 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(), i, lappend(), lfirst, list_copy(), list_length(), makeNode, MemoryContextSwitchTo(), NIL, PlannerInfo::planner_cxt, pull_varnos(), RELOPT_BASEREL, RELOPT_DEADREL, RelOptInfo::reloptkind, and PlannerInfo::simple_rel_array.

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

634 {
635  Relids expr_relids;
636  EquivalenceClass *newec;
637  EquivalenceMember *newem;
638  ListCell *lc1;
639  MemoryContext oldcontext;
640 
641  /*
642  * Ensure the expression exposes the correct type and collation.
643  */
644  expr = canonicalize_ec_expression(expr, opcintype, collation);
645 
646  /*
647  * Get the precise set of nullable relids appearing in the expression.
648  */
649  expr_relids = pull_varnos((Node *) expr);
650  nullable_relids = bms_intersect(nullable_relids, expr_relids);
651 
652  /*
653  * Scan through the existing EquivalenceClasses for a match
654  */
655  foreach(lc1, root->eq_classes)
656  {
657  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
658  ListCell *lc2;
659 
660  /*
661  * Never match to a volatile EC, except when we are looking at another
662  * reference to the same volatile SortGroupClause.
663  */
664  if (cur_ec->ec_has_volatile &&
665  (sortref == 0 || sortref != cur_ec->ec_sortref))
666  continue;
667 
668  if (collation != cur_ec->ec_collation)
669  continue;
670  if (!equal(opfamilies, cur_ec->ec_opfamilies))
671  continue;
672 
673  foreach(lc2, cur_ec->ec_members)
674  {
675  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
676 
677  /*
678  * Ignore child members unless they match the request.
679  */
680  if (cur_em->em_is_child &&
681  !bms_equal(cur_em->em_relids, rel))
682  continue;
683 
684  /*
685  * If below an outer join, don't match constants: they're not as
686  * constant as they look.
687  */
688  if (cur_ec->ec_below_outer_join &&
689  cur_em->em_is_const)
690  continue;
691 
692  if (opcintype == cur_em->em_datatype &&
693  equal(expr, cur_em->em_expr))
694  return cur_ec; /* Match! */
695  }
696  }
697 
698  /* No match; does caller want a NULL result? */
699  if (!create_it)
700  return NULL;
701 
702  /*
703  * OK, build a new single-member EC
704  *
705  * Here, we must be sure that we construct the EC in the right context.
706  */
707  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
708 
709  newec = makeNode(EquivalenceClass);
710  newec->ec_opfamilies = list_copy(opfamilies);
711  newec->ec_collation = collation;
712  newec->ec_members = NIL;
713  newec->ec_sources = NIL;
714  newec->ec_derives = NIL;
715  newec->ec_relids = NULL;
716  newec->ec_has_const = false;
718  newec->ec_below_outer_join = false;
719  newec->ec_broken = false;
720  newec->ec_sortref = sortref;
721  newec->ec_min_security = UINT_MAX;
722  newec->ec_max_security = 0;
723  newec->ec_merged = NULL;
724 
725  if (newec->ec_has_volatile && sortref == 0) /* should not happen */
726  elog(ERROR, "volatile EquivalenceClass has no sortref");
727 
728  newem = add_eq_member(newec, copyObject(expr), expr_relids,
729  nullable_relids, false, opcintype);
730 
731  /*
732  * add_eq_member doesn't check for volatile functions, set-returning
733  * functions, aggregates, or window functions, but such could appear in
734  * sort expressions; so we have to check whether its const-marking was
735  * correct.
736  */
737  if (newec->ec_has_const)
738  {
739  if (newec->ec_has_volatile ||
740  expression_returns_set((Node *) expr) ||
741  contain_agg_clause((Node *) expr) ||
742  contain_window_function((Node *) expr))
743  {
744  newec->ec_has_const = false;
745  newem->em_is_const = false;
746  }
747  }
748 
749  root->eq_classes = lappend(root->eq_classes, newec);
750 
751  /*
752  * If EC merging is already complete, we have to mop up by adding the new
753  * EC to the eclass_indexes of the relation(s) mentioned in it.
754  */
755  if (root->ec_merging_done)
756  {
757  int ec_index = list_length(root->eq_classes) - 1;
758  int i = -1;
759 
760  while ((i = bms_next_member(newec->ec_relids, i)) > 0)
761  {
762  RelOptInfo *rel = root->simple_rel_array[i];
763 
764  Assert(rel->reloptkind == RELOPT_BASEREL ||
765  rel->reloptkind == RELOPT_DEADREL);
766 
768  ec_index);
769  }
770  }
771 
772  MemoryContextSwitchTo(oldcontext);
773 
774  return newec;
775 }
#define NIL
Definition: pg_list.h:65
RelOptKind reloptkind
Definition: pathnodes.h:662
bool ec_merging_done
Definition: pathnodes.h:268
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3033
Index ec_min_security
Definition: pathnodes.h:974
List * ec_derives
Definition: pathnodes.h:966
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
bool expression_returns_set(Node *clause)
Definition: nodeFuncs.c:669
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
List * list_copy(const List *oldlist)
Definition: list.c:1403
Definition: nodes.h:529
bool ec_below_outer_join
Definition: pathnodes.h:971
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:726
Index ec_max_security
Definition: pathnodes.h:975
struct RelOptInfo ** simple_rel_array
Definition: pathnodes.h:203
#define ERROR
Definition: elog.h:43
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:499
List * ec_sources
Definition: pathnodes.h:965
Relids ec_relids
Definition: pathnodes.h:967
Relids pull_varnos(Node *node)
Definition: var.c:95
bool contain_window_function(Node *clause)
Definition: clauses.c:496
List * lappend(List *list, void *datum)
Definition: list.c:321
List * ec_opfamilies
Definition: pathnodes.h:962
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:259
#define makeNode(_type_)
Definition: nodes.h:577
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:169
bool ec_has_volatile
Definition: pathnodes.h:970
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:736
bool contain_agg_clause(Node *clause)
Definition: clauses.c:181
#define elog(elevel,...)
Definition: elog.h:214
int i
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, Relids nullable_relids, bool is_child, Oid datatype)
Definition: equivclass.c:549
MemoryContext planner_cxt
Definition: pathnodes.h:331
#define copyObject(obj)
Definition: nodes.h:645
Bitmapset * eclass_indexes
Definition: pathnodes.h:707
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:976
List * ec_members
Definition: pathnodes.h:964
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:94

◆ has_relevant_eclass_joinclause()

bool has_relevant_eclass_joinclause ( PlannerInfo root,
RelOptInfo rel1 
)

Definition at line 2722 of file equivclass.c.

References bms_is_subset(), bms_next_member(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, get_eclass_indexes_for_relids(), i, list_length(), list_nth(), and RelOptInfo::relids.

Referenced by build_join_rel().

2723 {
2724  Bitmapset *matched_ecs;
2725  int i;
2726 
2727  /* Examine only eclasses mentioning rel1 */
2728  matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
2729 
2730  i = -1;
2731  while ((i = bms_next_member(matched_ecs, i)) >= 0)
2732  {
2734  i);
2735 
2736  /*
2737  * Won't generate joinclauses if single-member (this test covers the
2738  * volatile case too)
2739  */
2740  if (list_length(ec->ec_members) <= 1)
2741  continue;
2742 
2743  /*
2744  * Per the comment in have_relevant_eclass_joinclause, it's sufficient
2745  * to find an EC that mentions both this rel and some other rel.
2746  */
2747  if (!bms_is_subset(ec->ec_relids, rel1->relids))
2748  return true;
2749  }
2750 
2751  return false;
2752 }
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:2887
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
Relids ec_relids
Definition: pathnodes.h:967
Relids relids
Definition: pathnodes.h:665
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:169
int i
List * ec_members
Definition: pathnodes.h:964

◆ has_useful_pathkeys()

bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 1910 of file pathkeys.c.

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

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

1911 {
1912  if (rel->joininfo != NIL || rel->has_eclass_joins)
1913  return true; /* might be able to use pathkeys for merging */
1914  if (root->query_pathkeys != NIL)
1915  return true; /* might be able to use them for ordering */
1916  return false; /* definitely useless */
1917 }
bool has_eclass_joins
Definition: pathnodes.h:733
#define NIL
Definition: pg_list.h:65
List * query_pathkeys
Definition: pathnodes.h:298
List * joininfo
Definition: pathnodes.h:731

◆ have_dangerous_phv()

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

Definition at line 1184 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().

1186 {
1187  ListCell *lc;
1188 
1189  foreach(lc, root->placeholder_list)
1190  {
1191  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1192 
1193  if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1194  continue; /* ignore, could not be a nestloop param */
1195  if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1196  continue; /* ignore, not relevant to this join */
1197  if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
1198  continue; /* safe, it can be eval'd within outerrel */
1199  /* Otherwise, it's potentially unsafe, so reject the join */
1200  return true;
1201  }
1202 
1203  /* OK to perform the join */
1204  return false;
1205 }
Relids ph_eval_at
Definition: pathnodes.h:2308
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
#define lfirst(lc)
Definition: pg_list.h:190
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
List * placeholder_list
Definition: pathnodes.h:294

◆ have_join_order_restriction()

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

Definition at line 951 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().

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

◆ have_relevant_eclass_joinclause()

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

Definition at line 2655 of file equivclass.c.

References Assert, bms_next_member(), bms_overlap(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, get_common_eclass_indexes(), i, list_length(), list_nth(), and RelOptInfo::relids.

Referenced by have_relevant_joinclause().

2657 {
2658  Bitmapset *matching_ecs;
2659  int i;
2660 
2661  /* Examine only eclasses mentioning both rel1 and rel2 */
2662  matching_ecs = get_common_eclass_indexes(root, rel1->relids,
2663  rel2->relids);
2664 
2665  i = -1;
2666  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2667  {
2669  i);
2670 
2671  /*
2672  * Sanity check that get_common_eclass_indexes gave only ECs
2673  * containing both rels.
2674  */
2675  Assert(bms_overlap(rel1->relids, ec->ec_relids));
2676  Assert(bms_overlap(rel2->relids, ec->ec_relids));
2677 
2678  /*
2679  * Won't generate joinclauses if single-member (this test covers the
2680  * volatile case too)
2681  */
2682  if (list_length(ec->ec_members) <= 1)
2683  continue;
2684 
2685  /*
2686  * We do not need to examine the individual members of the EC, because
2687  * all that we care about is whether each rel overlaps the relids of
2688  * at least one member, and get_common_eclass_indexes() and the single
2689  * member check above are sufficient to prove that. (As with
2690  * have_relevant_joinclause(), it is not necessary that the EC be able
2691  * to form a joinclause relating exactly the two given rels, only that
2692  * it be able to form a joinclause mentioning both, and this will
2693  * surely be true if both of them overlap ec_relids.)
2694  *
2695  * Note we don't test ec_broken; if we did, we'd need a separate code
2696  * path to look through ec_sources. Checking the membership anyway is
2697  * OK as a possibly-overoptimistic heuristic.
2698  *
2699  * We don't test ec_has_const either, even though a const eclass won't
2700  * generate real join clauses. This is because if we had "WHERE a.x =
2701  * b.y and a.x = 42", it is worth considering a join between a and b,
2702  * since the join result is likely to be small even though it'll end
2703  * up being an unqualified nestloop.
2704  */
2705 
2706  return true;
2707  }
2708 
2709  return false;
2710 }
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
Relids ec_relids
Definition: pathnodes.h:967
Relids relids
Definition: pathnodes.h:665
static Bitmapset * get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
Definition: equivclass.c:2911
#define Assert(condition)
Definition: c.h:738
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:169
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
int i
List * ec_members
Definition: pathnodes.h:964

◆ indexcol_is_bool_constant_for_query()

bool indexcol_is_bool_constant_for_query ( IndexOptInfo index,
int  indexcol 
)

Definition at line 3757 of file indxpath.c.

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

Referenced by build_index_pathkeys().

3758 {
3759  ListCell *lc;
3760 
3761  /* If the index isn't boolean, we can't possibly get a match */
3762  if (!IsBooleanOpfamily(index->opfamily[indexcol]))
3763  return false;
3764 
3765  /* Check each restriction clause for the index's rel */
3766  foreach(lc, index->rel->baserestrictinfo)
3767  {
3768  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3769 
3770  /*
3771  * As in match_clause_to_indexcol, never match pseudoconstants to
3772  * indexes. (It might be semantically okay to do so here, but the
3773  * odds of getting a match are negligible, so don't waste the cycles.)
3774  */
3775  if (rinfo->pseudoconstant)
3776  continue;
3777 
3778  /* See if we can match the clause's expression to the index column */
3779  if (match_boolean_index_clause(rinfo, indexcol, index))
3780  return true;
3781  }
3782 
3783  return false;
3784 }
static IndexClause * match_boolean_index_clause(RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:2458
List * baserestrictinfo
Definition: pathnodes.h:727
bool pseudoconstant
Definition: pathnodes.h:1993
RelOptInfo * rel
Definition: pathnodes.h:820
#define lfirst(lc)
Definition: pg_list.h:190
Oid * opfamily
Definition: pathnodes.h:833

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1179 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().

1180 {
1181  Expr *clause = restrictinfo->clause;
1182  Oid lefttype,
1183  righttype;
1184 
1185  /* Should be a mergeclause ... */
1186  Assert(restrictinfo->mergeopfamilies != NIL);
1187  /* ... with links not yet set */
1188  Assert(restrictinfo->left_ec == NULL);
1189  Assert(restrictinfo->right_ec == NULL);
1190 
1191  /* Need the declared input types of the operator */
1192  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1193 
1194  /* Find or create a matching EquivalenceClass for each side */
1195  restrictinfo->left_ec =
1197  (Expr *) get_leftop(clause),
1198  restrictinfo->nullable_relids,
1199  restrictinfo->mergeopfamilies,
1200  lefttype,
1201  ((OpExpr *) clause)->inputcollid,
1202  0,
1203  NULL,
1204  true);
1205  restrictinfo->right_ec =
1207  (Expr *) get_rightop(clause),
1208  restrictinfo->nullable_relids,
1209  restrictinfo->mergeopfamilies,
1210  righttype,
1211  ((OpExpr *) clause)->inputcollid,
1212  0,
1213  NULL,
1214  true);
1215 }
#define NIL
Definition: pg_list.h:65
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:625
EquivalenceClass * right_ec
Definition: pathnodes.h:2034
unsigned int Oid
Definition: postgres_ext.h:31
List * mergeopfamilies
Definition: pathnodes.h:2030
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1275
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:70
Expr * clause
Definition: pathnodes.h:1985
Relids nullable_relids
Definition: pathnodes.h:2009
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:82
#define Assert(condition)
Definition: c.h:738
EquivalenceClass * left_ec
Definition: pathnodes.h:2033

◆ is_redundant_derived_clause()

bool is_redundant_derived_clause ( RestrictInfo rinfo,
List clauselist 
)

Definition at line 2824 of file equivclass.c.

References lfirst, and RestrictInfo::parent_ec.

Referenced by create_tidscan_plan().

2825 {
2826  EquivalenceClass *parent_ec = rinfo->parent_ec;
2827  ListCell *lc;
2828 
2829  /* Fail if it's not a potentially-redundant clause from some EC */
2830  if (parent_ec == NULL)
2831  return false;
2832 
2833  foreach(lc, clauselist)
2834  {
2835  RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
2836 
2837  if (otherrinfo->parent_ec == parent_ec)
2838  return true;
2839  }
2840 
2841  return false;
2842 }
EquivalenceClass * parent_ec
Definition: pathnodes.h:2019
#define lfirst(lc)
Definition: pg_list.h:190

◆ is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses ( RestrictInfo rinfo,
List indexclauses 
)

Definition at line 2851 of file equivclass.c.

References lfirst_node, IndexClause::lossy, RestrictInfo::parent_ec, and IndexClause::rinfo.

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

2852 {
2853  EquivalenceClass *parent_ec = rinfo->parent_ec;
2854  ListCell *lc;
2855 
2856  foreach(lc, indexclauses)
2857  {
2858  IndexClause *iclause = lfirst_node(IndexClause, lc);
2859  RestrictInfo *otherrinfo = iclause->rinfo;
2860 
2861  /* If indexclause is lossy, it won't enforce the condition exactly */
2862  if (iclause->lossy)
2863  continue;
2864 
2865  /* Match if it's same clause (pointer equality should be enough) */
2866  if (rinfo == otherrinfo)
2867  return true;
2868  /* Match if derived from same EC */
2869  if (parent_ec && otherrinfo->parent_ec == parent_ec)
2870  return true;
2871 
2872  /*
2873  * No need to look at the derived clauses in iclause->indexquals; they
2874  * couldn't match if the parent clause didn't.
2875  */
2876  }
2877 
2878  return false;
2879 }
EquivalenceClass * parent_ec
Definition: pathnodes.h:2019
#define lfirst_node(type, lc)
Definition: pg_list.h:193
struct RestrictInfo * rinfo
Definition: pathnodes.h:1253

◆ join_search_one_level()

void join_search_one_level ( PlannerInfo root,
int  level 
)

Definition at line 71 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().

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

◆ make_canonical_pathkey()

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

Definition at line 54 of file pathkeys.c.

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

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

57 {
58  PathKey *pk;
59  ListCell *lc;
60  MemoryContext oldcontext;
61 
62  /* Can't make canonical pathkeys if the set of ECs might still change */
63  if (!root->ec_merging_done)
64  elog(ERROR, "too soon to build canonical pathkeys");
65 
66  /* The passed eclass might be non-canonical, so chase up to the top */
67  while (eclass->ec_merged)
68  eclass = eclass->ec_merged;
69 
70  foreach(lc, root->canon_pathkeys)
71  {
72  pk = (PathKey *) lfirst(lc);
73  if (eclass == pk->pk_eclass &&
74  opfamily == pk->pk_opfamily &&
75  strategy == pk->pk_strategy &&
76  nulls_first == pk->pk_nulls_first)
77  return pk;
78  }
79 
80  /*
81  * Be sure canonical pathkeys are allocated in the main planning context.
82  * Not an issue in normal planning, but it is for GEQO.
83  */
84  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
85 
86  pk = makeNode(PathKey);
87  pk->pk_eclass = eclass;
88  pk->pk_opfamily = opfamily;
89  pk->pk_strategy = strategy;
90  pk->pk_nulls_first = nulls_first;
91 
92  root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
93 
94  MemoryContextSwitchTo(oldcontext);
95 
96  return pk;
97 }
bool ec_merging_done
Definition: pathnodes.h:268
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int pk_strategy
Definition: pathnodes.h:1043
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:508
bool pk_nulls_first
Definition: pathnodes.h:1044
#define ERROR
Definition: elog.h:43
List * canon_pathkeys
Definition: pathnodes.h:270
List * lappend(List *list, void *datum)
Definition: list.c:321
#define makeNode(_type_)
Definition: nodes.h:577
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041
Oid pk_opfamily
Definition: pathnodes.h:1042
#define elog(elevel,...)
Definition: elog.h:214
MemoryContext planner_cxt
Definition: pathnodes.h:331
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:976

◆ make_inner_pathkeys_for_merge()

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

Definition at line 1547 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().

1550 {
1551  List *pathkeys = NIL;
1552  EquivalenceClass *lastoeclass;
1553  PathKey *opathkey;
1554  ListCell *lc;
1555  ListCell *lop;
1556 
1557  lastoeclass = NULL;
1558  opathkey = NULL;
1559  lop = list_head(outer_pathkeys);
1560 
1561  foreach(lc, mergeclauses)
1562  {
1563  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1564  EquivalenceClass *oeclass;
1565  EquivalenceClass *ieclass;
1566  PathKey *pathkey;
1567 
1568  update_mergeclause_eclasses(root, rinfo);
1569 
1570  if (rinfo->outer_is_left)
1571  {
1572  oeclass = rinfo->left_ec;
1573  ieclass = rinfo->right_ec;
1574  }
1575  else
1576  {
1577  oeclass = rinfo->right_ec;
1578  ieclass = rinfo->left_ec;
1579  }
1580 
1581  /* outer eclass should match current or next pathkeys */
1582  /* we check this carefully for debugging reasons */
1583  if (oeclass != lastoeclass)
1584  {
1585  if (!lop)
1586  elog(ERROR, "too few pathkeys for mergeclauses");
1587  opathkey = (PathKey *) lfirst(lop);
1588  lop = lnext(outer_pathkeys, lop);
1589  lastoeclass = opathkey->pk_eclass;
1590  if (oeclass != lastoeclass)
1591  elog(ERROR, "outer pathkeys do not match mergeclause");
1592  }
1593 
1594  /*
1595  * Often, we'll have same EC on both sides, in which case the outer
1596  * pathkey is also canonical for the inner side, and we can skip a
1597  * useless search.
1598  */
1599  if (ieclass == oeclass)
1600  pathkey = opathkey;
1601  else
1602  pathkey = make_canonical_pathkey(root,
1603  ieclass,
1604  opathkey->pk_opfamily,
1605  opathkey->pk_strategy,
1606  opathkey->pk_nulls_first);
1607 
1608  /*
1609  * Don't generate redundant pathkeys (which can happen if multiple
1610  * mergeclauses refer to the same EC). Because we do this, the output
1611  * pathkey list isn't necessarily ordered like the mergeclauses, which
1612  * complicates life for create_mergejoin_plan(). But if we didn't,
1613  * we'd have a noncanonical sort key list, which would be bad; for one
1614  * reason, it certainly wouldn't match any available sort order for
1615  * the input relation.
1616  */
1617  if (!pathkey_is_redundant(pathkey, pathkeys))
1618  pathkeys = lappend(pathkeys, pathkey);
1619  }
1620 
1621  return pathkeys;
1622 }
#define NIL
Definition: pg_list.h:65
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:321
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:54
EquivalenceClass * right_ec
Definition: pathnodes.h:2034
int pk_strategy
Definition: pathnodes.h:1043
bool pk_nulls_first
Definition: pathnodes.h:1044
#define ERROR
Definition: elog.h:43
bool outer_is_left
Definition: pathnodes.h:2040
static ListCell * list_head(const List *l)
Definition: pg_list.h:125
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:321
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041
Oid pk_opfamily
Definition: pathnodes.h:1042
EquivalenceClass * left_ec
Definition: pathnodes.h:2033
#define elog(elevel,...)
Definition: elog.h:214
Definition: pg_list.h:50
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1228

◆ make_join_rel()

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