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

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

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

◆ add_paths_to_append_rel()

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

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

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

References applyRelabelType(), COERCE_IMPLICIT_CAST, exprCollation(), exprType(), and exprTypmod().

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

496 {
497  Oid expr_type = exprType((Node *) expr);
498 
499  /*
500  * For a polymorphic-input-type opclass, just keep the same exposed type.
501  * RECORD opclasses work like polymorphic-type ones for this purpose.
502  */
503  if (IsPolymorphicType(req_type) || req_type == RECORDOID)
504  req_type = expr_type;
505 
506  /*
507  * No work if the expression exposes the right type/collation already.
508  */
509  if (expr_type != req_type ||
510  exprCollation((Node *) expr) != req_collation)
511  {
512  /*
513  * If we have to change the type of the expression, set typmod to -1,
514  * since the new type may not have the same typmod interpretation.
515  * When we only have to change collation, preserve the exposed typmod.
516  */
517  int32 req_typmod;
518 
519  if (expr_type != req_type)
520  req_typmod = -1;
521  else
522  req_typmod = exprTypmod((Node *) expr);
523 
524  /*
525  * Use applyRelabelType so that we preserve const-flatness. This is
526  * important since eval_const_expressions has already been applied.
527  */
528  expr = (Expr *) applyRelabelType((Node *) expr,
529  req_type, req_typmod, req_collation,
530  COERCE_IMPLICIT_CAST, -1, false);
531  }
532 
533  return expr;
534 }
Node * applyRelabelType(Node *arg, Oid rtype, int32 rtypmod, Oid rcollid, CoercionForm rformat, int rlocation, bool overwrite_ok)
Definition: nodeFuncs.c:591
int32 exprTypmod(const Node *expr)
Definition: nodeFuncs.c:275
Definition: nodes.h:528
unsigned int Oid
Definition: postgres_ext.h:31
signed int int32
Definition: c.h:362
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:41
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:768

◆ check_index_predicates()

void check_index_predicates ( PlannerInfo root,
RelOptInfo rel 
)

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

3309 {
3310  List *clauselist;
3311  bool have_partial;
3312  bool is_target_rel;
3313  Relids otherrels;
3314  ListCell *lc;
3315 
3316  /* Indexes are available only on base or "other" member relations. */
3317  Assert(IS_SIMPLE_REL(rel));
3318 
3319  /*
3320  * Initialize the indrestrictinfo lists to be identical to
3321  * baserestrictinfo, and check whether there are any partial indexes. If
3322  * not, this is all we need to do.
3323  */
3324  have_partial = false;
3325  foreach(lc, rel->indexlist)
3326  {
3328 
3329  index->indrestrictinfo = rel->baserestrictinfo;
3330  if (index->indpred)
3331  have_partial = true;
3332  }
3333  if (!have_partial)
3334  return;
3335 
3336  /*
3337  * Construct a list of clauses that we can assume true for the purpose of
3338  * proving the index(es) usable. Restriction clauses for the rel are
3339  * always usable, and so are any join clauses that are "movable to" this
3340  * rel. Also, we can consider any EC-derivable join clauses (which must
3341  * be "movable to" this rel, by definition).
3342  */
3343  clauselist = list_copy(rel->baserestrictinfo);
3344 
3345  /* Scan the rel's join clauses */
3346  foreach(lc, rel->joininfo)
3347  {
3348  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3349 
3350  /* Check if clause can be moved to this rel */
3351  if (!join_clause_is_movable_to(rinfo, rel))
3352  continue;
3353 
3354  clauselist = lappend(clauselist, rinfo);
3355  }
3356 
3357  /*
3358  * Add on any equivalence-derivable join clauses. Computing the correct
3359  * relid sets for generate_join_implied_equalities is slightly tricky
3360  * because the rel could be a child rel rather than a true baserel, and in
3361  * that case we must remove its parents' relid(s) from all_baserels.
3362  */
3363  if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
3364  otherrels = bms_difference(root->all_baserels,
3365  find_childrel_parents(root, rel));
3366  else
3367  otherrels = bms_difference(root->all_baserels, rel->relids);
3368 
3369  if (!bms_is_empty(otherrels))
3370  clauselist =
3371  list_concat(clauselist,
3373  bms_union(rel->relids,
3374  otherrels),
3375  otherrels,
3376  rel));
3377 
3378  /*
3379  * Normally we remove quals that are implied by a partial index's
3380  * predicate from indrestrictinfo, indicating that they need not be
3381  * checked explicitly by an indexscan plan using this index. However, if
3382  * the rel is a target relation of UPDATE/DELETE/SELECT FOR UPDATE, we
3383  * cannot remove such quals from the plan, because they need to be in the
3384  * plan so that they will be properly rechecked by EvalPlanQual testing.
3385  * Some day we might want to remove such quals from the main plan anyway
3386  * and pass them through to EvalPlanQual via a side channel; but for now,
3387  * we just don't remove implied quals at all for target relations.
3388  */
3389  is_target_rel = (rel->relid == root->parse->resultRelation ||
3390  get_plan_rowmark(root->rowMarks, rel->relid) != NULL);
3391 
3392  /*
3393  * Now try to prove each index predicate true, and compute the
3394  * indrestrictinfo lists for partial indexes. Note that we compute the
3395  * indrestrictinfo list even for non-predOK indexes; this might seem
3396  * wasteful, but we may be able to use such indexes in OR clauses, cf
3397  * generate_bitmap_or_paths().
3398  */
3399  foreach(lc, rel->indexlist)
3400  {
3401  IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
3402  ListCell *lcr;
3403 
3404  if (index->indpred == NIL)
3405  continue; /* ignore non-partial indexes here */
3406 
3407  if (!index->predOK) /* don't repeat work if already proven OK */
3408  index->predOK = predicate_implied_by(index->indpred, clauselist,
3409  false);
3410 
3411  /* If rel is an update target, leave indrestrictinfo as set above */
3412  if (is_target_rel)
3413  continue;
3414 
3415  /* Else compute indrestrictinfo as the non-implied quals */
3416  index->indrestrictinfo = NIL;
3417  foreach(lcr, rel->baserestrictinfo)
3418  {
3419  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
3420 
3421  /* predicate_implied_by() assumes first arg is immutable */
3422  if (contain_mutable_functions((Node *) rinfo->clause) ||
3424  index->indpred, false))
3425  index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
3426  }
3427  }
3428 }
#define NIL
Definition: pg_list.h:65
List * rowMarks
Definition: pathnodes.h:292
Query * parse
Definition: pathnodes.h:179
RelOptKind reloptkind
Definition: pathnodes.h:663
List * baserestrictinfo
Definition: pathnodes.h:728
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:528
List * list_concat(List *list1, const List *list2)
Definition: list.c:515
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:639
Definition: type.h:89
#define list_make1(x1)
Definition: pg_list.h:206
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:1145
List * joininfo
Definition: pathnodes.h:732
Relids relids
Definition: pathnodes.h:666
Index relid
Definition: pathnodes.h:694
List * lappend(List *list, void *datum)
Definition: list.c:321
Expr * clause
Definition: pathnodes.h:1986
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
List * indrestrictinfo
Definition: pathnodes.h:849
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1243
List * indexlist
Definition: pathnodes.h:703
#define Assert(condition)
Definition: c.h:745
#define lfirst(lc)
Definition: pg_list.h:169
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:645
List * indpred
Definition: pathnodes.h:845
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:434
#define lfirst(lc)
Definition: pg_list.h:169

◆ compute_parallel_worker()

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

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

3829 {
3830  int parallel_workers = 0;
3831 
3832  /*
3833  * If the user has set the parallel_workers reloption, use that; otherwise
3834  * select a default number of workers.
3835  */
3836  if (rel->rel_parallel_workers != -1)
3837  parallel_workers = rel->rel_parallel_workers;
3838  else
3839  {
3840  /*
3841  * If the number of pages being scanned is insufficient to justify a
3842  * parallel scan, just return zero ... unless it's an inheritance
3843  * child. In that case, we want to generate a parallel path here
3844  * anyway. It might not be worthwhile just for this relation, but
3845  * when combined with all of its inheritance siblings it may well pay
3846  * off.
3847  */
3848  if (rel->reloptkind == RELOPT_BASEREL &&
3849  ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
3850  (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
3851  return 0;
3852 
3853  if (heap_pages >= 0)
3854  {
3855  int heap_parallel_threshold;
3856  int heap_parallel_workers = 1;
3857 
3858  /*
3859  * Select the number of workers based on the log of the size of
3860  * the relation. This probably needs to be a good deal more
3861  * sophisticated, but we need something here for now. Note that
3862  * the upper limit of the min_parallel_table_scan_size GUC is
3863  * chosen to prevent overflow here.
3864  */
3865  heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
3866  while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
3867  {
3868  heap_parallel_workers++;
3869  heap_parallel_threshold *= 3;
3870  if (heap_parallel_threshold > INT_MAX / 3)
3871  break; /* avoid overflow */
3872  }
3873 
3874  parallel_workers = heap_parallel_workers;
3875  }
3876 
3877  if (index_pages >= 0)
3878  {
3879  int index_parallel_workers = 1;
3880  int index_parallel_threshold;
3881 
3882  /* same calculation as for heap_pages above */
3883  index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
3884  while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
3885  {
3886  index_parallel_workers++;
3887  index_parallel_threshold *= 3;
3888  if (index_parallel_threshold > INT_MAX / 3)
3889  break; /* avoid overflow */
3890  }
3891 
3892  if (parallel_workers > 0)
3893  parallel_workers = Min(parallel_workers, index_parallel_workers);
3894  else
3895  parallel_workers = index_parallel_workers;
3896  }
3897  }
3898 
3899  /* In no case use more than caller supplied maximum number of workers */
3900  parallel_workers = Min(parallel_workers, max_workers);
3901 
3902  return parallel_workers;
3903 }
RelOptKind reloptkind
Definition: pathnodes.h:663
#define Min(x, y)
Definition: c.h:927
uint32 BlockNumber
Definition: block.h:31
int min_parallel_index_scan_size
Definition: allpaths.c:65
int rel_parallel_workers
Definition: pathnodes.h:712
#define Max(x, y)
Definition: c.h:921
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:3032
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:616
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:1044
#define linitial(l)
Definition: pg_list.h:174
bool pk_nulls_first
Definition: pathnodes.h:1045
#define ERROR
Definition: elog.h:43
static void * list_nth(const List *list, int n)
Definition: pg_list.h:266
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:495
Relids relids
Definition: pathnodes.h:666
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:963
#define Assert(condition)
Definition: c.h:745
#define lfirst(lc)
Definition: pg_list.h:169
Expr * expr
Definition: primnodes.h:1410
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1042
static int list_length(const List *l)
Definition: pg_list.h:149
bool ec_has_volatile
Definition: pathnodes.h:971
Oid pk_opfamily
Definition: pathnodes.h:1043
#define elog(elevel,...)
Definition: elog.h:214
int i
Definition: pg_list.h:50
List * ec_members
Definition: pathnodes.h:965

◆ create_index_paths()

void create_index_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 231 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(), generate_bitmap_or_paths(), 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, PATH_REQ_OUTER, IndexOptInfo::predOK, and RelOptInfo::relid.

Referenced by set_plain_rel_pathlist().

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

◆ create_partial_bitmap_paths()

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

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

3793 {
3794  int parallel_workers;
3795  double pages_fetched;
3796 
3797  /* Compute heap pages for bitmap heap scan */
3798  pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
3799  NULL, NULL);
3800 
3801  parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
3803 
3804  if (parallel_workers <= 0)
3805  return;
3806 
3807  add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
3808  bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
3809 }
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:3827
Relids lateral_relids
Definition: pathnodes.h:691
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:5745
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:734
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
List * baserestrictinfo
Definition: pathnodes.h:728
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:691
static void BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
Definition: tidpath.c:313
List * joininfo
Definition: pathnodes.h:732
Relids lateral_referencers
Definition: pathnodes.h:702
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:1183
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:2516

◆ eclass_useful_for_merging()

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

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

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

◆ exprs_known_equal()

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

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

2105 {
2106  ListCell *lc1;
2107 
2108  foreach(lc1, root->eq_classes)
2109  {
2110  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2111  bool item1member = false;
2112  bool item2member = false;
2113  ListCell *lc2;
2114 
2115  /* Never match to a volatile EC */
2116  if (ec->ec_has_volatile)
2117  continue;
2118 
2119  foreach(lc2, ec->ec_members)
2120  {
2122 
2123  if (em->em_is_child)
2124  continue; /* ignore children here */
2125  if (equal(item1, em->em_expr))
2126  item1member = true;
2127  else if (equal(item2, em->em_expr))
2128  item2member = true;
2129  /* Exit as soon as equality is proven */
2130  if (item1member && item2member)
2131  return true;
2132  }
2133  }
2134  return false;
2135 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3032
#define lfirst(lc)
Definition: pg_list.h:169
List * eq_classes
Definition: pathnodes.h:266
bool ec_has_volatile
Definition: pathnodes.h:971
List * ec_members
Definition: pathnodes.h:965

◆ find_em_expr_for_rel()

Expr* find_em_expr_for_rel ( EquivalenceClass ec,
RelOptInfo rel 
)

Definition at line 773 of file equivclass.c.

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

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

◆ 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:2035
bool outer_is_left
Definition: pathnodes.h:2041
List * lappend(List *list, void *datum)
Definition: list.c:321
#define lfirst(lc)
Definition: pg_list.h:169
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1042
EquivalenceClass * left_ec
Definition: pathnodes.h:2034
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 846 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().

847 {
848  int ec_index;
849  ListCell *lc;
850 
851  /*
852  * At this point, we're done absorbing knowledge of equivalences in the
853  * query, so no further EC merging should happen, and ECs remaining in the
854  * eq_classes list can be considered canonical. (But note that it's still
855  * possible for new single-member ECs to be added through
856  * get_eclass_for_sort_expr().)
857  */
858  root->ec_merging_done = true;
859 
860  ec_index = 0;
861  foreach(lc, root->eq_classes)
862  {
864  bool can_generate_joinclause = false;
865  int i;
866 
867  Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
868  Assert(!ec->ec_broken); /* not yet anyway... */
869 
870  /*
871  * Generate implied equalities that are restriction clauses.
872  * Single-member ECs won't generate any deductions, either here or at
873  * the join level.
874  */
875  if (list_length(ec->ec_members) > 1)
876  {
877  if (ec->ec_has_const)
879  else
881 
882  /* Recover if we failed to generate required derived clauses */
883  if (ec->ec_broken)
885 
886  /* Detect whether this EC might generate join clauses */
887  can_generate_joinclause =
889  }
890 
891  /*
892  * Mark the base rels cited in each eclass (which should all exist by
893  * now) with the eq_classes indexes of all eclasses mentioning them.
894  * This will let us avoid searching in subsequent lookups. While
895  * we're at it, we can mark base rels that have pending eclass joins;
896  * this is a cheap version of has_relevant_eclass_joinclause().
897  */
898  i = -1;
899  while ((i = bms_next_member(ec->ec_relids, i)) > 0)
900  {
901  RelOptInfo *rel = root->simple_rel_array[i];
902 
904 
906  ec_index);
907 
908  if (can_generate_joinclause)
909  rel->has_eclass_joins = true;
910  }
911 
912  ec_index++;
913  }
914 }
bool has_eclass_joins
Definition: pathnodes.h:734
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:997
RelOptKind reloptkind
Definition: pathnodes.h:663
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:1088
struct RelOptInfo ** simple_rel_array
Definition: pathnodes.h:203
Relids ec_relids
Definition: pathnodes.h:968
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:672
#define Assert(condition)
Definition: c.h:745
#define lfirst(lc)
Definition: pg_list.h:169
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:149
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:920
Bitmapset * eclass_indexes
Definition: pathnodes.h:708
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:977
List * ec_members
Definition: pathnodes.h:965

◆ generate_gather_paths()

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

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

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

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

1149 {
1150  List *result = NIL;
1151  Relids inner_relids = inner_rel->relids;
1152  Relids nominal_inner_relids;
1153  Relids nominal_join_relids;
1154  Bitmapset *matching_ecs;
1155  int i;
1156 
1157  /* If inner rel is a child, extra setup work is needed */
1158  if (IS_OTHER_REL(inner_rel))
1159  {
1160  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1161 
1162  /* Fetch relid set for the topmost parent rel */
1163  nominal_inner_relids = inner_rel->top_parent_relids;
1164  /* ECs will be marked with the parent's relid, not the child's */
1165  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1166  }
1167  else
1168  {
1169  nominal_inner_relids = inner_relids;
1170  nominal_join_relids = join_relids;
1171  }
1172 
1173  /*
1174  * Get all eclasses in common between inner_rel's relids and outer_relids
1175  */
1176  matching_ecs = get_common_eclass_indexes(root, inner_rel->relids,
1177  outer_relids);
1178 
1179  i = -1;
1180  while ((i = bms_next_member(matching_ecs, i)) >= 0)
1181  {
1183  List *sublist = NIL;
1184 
1185  /* ECs containing consts do not need any further enforcement */
1186  if (ec->ec_has_const)
1187  continue;
1188 
1189  /* Single-member ECs won't generate any deductions */
1190  if (list_length(ec->ec_members) <= 1)
1191  continue;
1192 
1193  /* Sanity check that this eclass overlaps the join */
1194  Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
1195 
1196  if (!ec->ec_broken)
1198  ec,
1199  join_relids,
1200  outer_relids,
1201  inner_relids);
1202 
1203  /* Recover if we failed to generate required derived clauses */
1204  if (ec->ec_broken)
1206  ec,
1207  nominal_join_relids,
1208  outer_relids,
1209  nominal_inner_relids,
1210  inner_rel);
1211 
1212  result = list_concat(result, sublist);
1213  }
1214 
1215  return result;
1216 }
#define NIL
Definition: pg_list.h:65
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:654
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:266
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:1470
Relids ec_relids
Definition: pathnodes.h:968
Relids relids
Definition: pathnodes.h:666
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1294
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:2902
#define Assert(condition)
Definition: c.h:745
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:149
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:965
Relids top_parent_relids
Definition: pathnodes.h:739

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

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

◆ generate_partitionwise_join_paths()

void generate_partitionwise_join_paths ( PlannerInfo root,
RelOptInfo rel 
)

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

3916 {
3917  List *live_children = NIL;
3918  int cnt_parts;
3919  int num_parts;
3920  RelOptInfo **part_rels;
3921 
3922  /* Handle only join relations here. */
3923  if (!IS_JOIN_REL(rel))
3924  return;
3925 
3926  /* We've nothing to do if the relation is not partitioned. */
3927  if (!IS_PARTITIONED_REL(rel))
3928  return;
3929 
3930  /* The relation should have consider_partitionwise_join set. */
3932 
3933  /* Guard against stack overflow due to overly deep partition hierarchy. */
3935 
3936  num_parts = rel->nparts;
3937  part_rels = rel->part_rels;
3938 
3939  /* Collect non-dummy child-joins. */
3940  for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
3941  {
3942  RelOptInfo *child_rel = part_rels[cnt_parts];
3943 
3944  /* If it's been pruned entirely, it's certainly dummy. */
3945  if (child_rel == NULL)
3946  continue;
3947 
3948  /* Add partitionwise join paths for partitioned child-joins. */
3949  generate_partitionwise_join_paths(root, child_rel);
3950 
3951  set_cheapest(child_rel);
3952 
3953  /* Dummy children will not be scanned, so ignore those. */
3954  if (IS_DUMMY_REL(child_rel))
3955  continue;
3956 
3957 #ifdef OPTIMIZER_DEBUG
3958  debug_print_rel(root, child_rel);
3959 #endif
3960 
3961  live_children = lappend(live_children, child_rel);
3962  }
3963 
3964  /* If all child-joins are dummy, parent join is also dummy. */
3965  if (!live_children)
3966  {
3967  mark_dummy_rel(rel);
3968  return;
3969  }
3970 
3971  /* Build additional paths for this rel from child-join paths. */
3972  add_paths_to_append_rel(root, rel, live_children);
3973  list_free(live_children);
3974 }
#define NIL
Definition: pg_list.h:65
void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
Definition: allpaths.c:1301
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:3915
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:644
#define IS_DUMMY_REL(r)
Definition: pathnodes.h:1419
void check_stack_depth(void)
Definition: postgres.c:3312
int nparts
Definition: pathnodes.h:744
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:737
void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1261
#define Assert(condition)
Definition: c.h:745
struct RelOptInfo ** part_rels
Definition: pathnodes.h:751
#define IS_PARTITIONED_REL(rel)
Definition: pathnodes.h:767
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 2820 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().

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

◆ 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:1164
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
List * pathkeys
Definition: pathnodes.h:1159
#define lfirst(lc)
Definition: pg_list.h:169
bool parallel_safe
Definition: pathnodes.h:1151

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

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

2714 {
2715  Bitmapset *matched_ecs;
2716  int i;
2717 
2718  /* Examine only eclasses mentioning rel1 */
2719  matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
2720 
2721  i = -1;
2722  while ((i = bms_next_member(matched_ecs, i)) >= 0)
2723  {
2725  i);
2726 
2727  /*
2728  * Won't generate joinclauses if single-member (this test covers the
2729  * volatile case too)
2730  */
2731  if (list_length(ec->ec_members) <= 1)
2732  continue;
2733 
2734  /*
2735  * Per the comment in have_relevant_eclass_joinclause, it's sufficient
2736  * to find an EC that mentions both this rel and some other rel.
2737  */
2738  if (!bms_is_subset(ec->ec_relids, rel1->relids))
2739  return true;
2740  }
2741 
2742  return false;
2743 }
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:266
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:2878
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
Relids ec_relids
Definition: pathnodes.h:968
Relids relids
Definition: pathnodes.h:666
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:149
int i
List * ec_members
Definition: pathnodes.h:965

◆ 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:734
#define NIL
Definition: pg_list.h:65
List * query_pathkeys
Definition: pathnodes.h:298
List * joininfo
Definition: pathnodes.h:732

◆ 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:2309
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
#define lfirst(lc)
Definition: pg_list.h:169
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:2309
List * join_info_list
Definition: pathnodes.h:283
Relids min_righthand
Definition: pathnodes.h:2177
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:666
Relids direct_lateral_relids
Definition: pathnodes.h:690
#define lfirst(lc)
Definition: pg_list.h:169
JoinType jointype
Definition: pathnodes.h:2180
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:2176

◆ have_relevant_eclass_joinclause()

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

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

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

◆ indexcol_is_bool_constant_for_query()

bool indexcol_is_bool_constant_for_query ( IndexOptInfo index,
int  indexcol 
)

Definition at line 3670 of file indxpath.c.

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

Referenced by build_index_pathkeys().

3671 {
3672  ListCell *lc;
3673 
3674  /* If the index isn't boolean, we can't possibly get a match */
3675  if (!IsBooleanOpfamily(index->opfamily[indexcol]))
3676  return false;
3677 
3678  /* Check each restriction clause for the index's rel */
3679  foreach(lc, index->rel->baserestrictinfo)
3680  {
3681  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3682 
3683  /*
3684  * As in match_clause_to_indexcol, never match pseudoconstants to
3685  * indexes. (It might be semantically okay to do so here, but the
3686  * odds of getting a match are negligible, so don't waste the cycles.)
3687  */
3688  if (rinfo->pseudoconstant)
3689  continue;
3690 
3691  /* See if we can match the clause's expression to the index column */
3692  if (match_boolean_index_clause(rinfo, indexcol, index))
3693  return true;
3694  }
3695 
3696  return false;
3697 }
static IndexClause * match_boolean_index_clause(RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:2371
List * baserestrictinfo
Definition: pathnodes.h:728
bool pseudoconstant
Definition: pathnodes.h:1994
RelOptInfo * rel
Definition: pathnodes.h:821
#define lfirst(lc)
Definition: pg_list.h:169
Oid * opfamily
Definition: pathnodes.h:834

◆ 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:616
EquivalenceClass * right_ec
Definition: pathnodes.h:2035
unsigned int Oid
Definition: postgres_ext.h:31
List * mergeopfamilies
Definition: pathnodes.h:2031
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1275
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:73
Expr * clause
Definition: pathnodes.h:1986
Relids nullable_relids
Definition: pathnodes.h:2010
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:85
#define Assert(condition)
Definition: c.h:745
EquivalenceClass * left_ec
Definition: pathnodes.h:2034

◆ is_redundant_derived_clause()

bool is_redundant_derived_clause ( RestrictInfo rinfo,
List clauselist 
)

Definition at line 2815 of file equivclass.c.

References lfirst, and RestrictInfo::parent_ec.

Referenced by create_tidscan_plan().

2816 {
2817  EquivalenceClass *parent_ec = rinfo->parent_ec;
2818  ListCell *lc;
2819 
2820  /* Fail if it's not a potentially-redundant clause from some EC */
2821  if (parent_ec == NULL)
2822  return false;
2823 
2824  foreach(lc, clauselist)
2825  {
2826  RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
2827 
2828  if (otherrinfo->parent_ec == parent_ec)
2829  return true;
2830  }
2831 
2832  return false;
2833 }
EquivalenceClass * parent_ec
Definition: pathnodes.h:2020
#define lfirst(lc)
Definition: pg_list.h:169

◆ is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses ( RestrictInfo rinfo,
List indexclauses 
)

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

2843 {
2844  EquivalenceClass *parent_ec = rinfo->parent_ec;
2845  ListCell *lc;
2846 
2847  foreach(lc, indexclauses)
2848  {
2849  IndexClause *iclause = lfirst_node(IndexClause, lc);
2850  RestrictInfo *otherrinfo = iclause->rinfo;
2851 
2852  /* If indexclause is lossy, it won't enforce the condition exactly */
2853  if (iclause->lossy)
2854  continue;
2855 
2856  /* Match if it's same clause (pointer equality should be enough) */
2857  if (rinfo == otherrinfo)
2858  return true;
2859  /* Match if derived from same EC */
2860  if (parent_ec && otherrinfo->parent_ec == parent_ec)
2861  return true;
2862 
2863  /*
2864  * No need to look at the derived clauses in iclause->indexquals; they
2865  * couldn't match if the parent clause didn't.
2866  */
2867  }
2868 
2869  return false;
2870 }
EquivalenceClass * parent_ec
Definition: pathnodes.h:2020
#define lfirst_node(type, lc)
Definition: pg_list.h:172
struct RestrictInfo * rinfo
Definition: pathnodes.h:1254

◆ 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:734
#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:310
#define for_each_cell(cell, lst, initcell)
Definition: pg_list.h:405
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:732
static ListCell * list_head(const List *l)
Definition: pg_list.h:125
Relids relids
Definition: pathnodes.h:666
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:745
#define lfirst(lc)
Definition: pg_list.h:169
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:1044
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:508
bool pk_nulls_first
Definition: pathnodes.h:1045
#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:576
#define lfirst(lc)
Definition: pg_list.h:169
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1042
Oid pk_opfamily
Definition: pathnodes.h:1043
#define elog(elevel,...)
Definition: elog.h:214
MemoryContext planner_cxt
Definition: pathnodes.h:331
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:977

◆ 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:310
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:2035
int pk_strategy
Definition: pathnodes.h:1044
bool pk_nulls_first
Definition: pathnodes.h:1045
#define ERROR
Definition: elog.h:43
bool outer_is_left
Definition: pathnodes.h:2041
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:169
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1042
Oid pk_opfamily
Definition: pathnodes.h:1043
EquivalenceClass * left_ec
Definition: pathnodes.h:2034
#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()