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)
 
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 have_partkey_equi_join (RelOptInfo *joinrel, RelOptInfo *rel1, RelOptInfo *rel2, JoinType jointype, List *restrictlist)
 
bool process_equivalence (PlannerInfo *root, RestrictInfo **p_restrictinfo, bool below_outer_join)
 
Exprcanonicalize_ec_expression (Expr *expr, Oid req_type, Oid req_collation)
 
void reconsider_outer_join_clauses (PlannerInfo *root)
 
EquivalenceClassget_eclass_for_sort_expr (PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
 
void generate_base_implied_equalities (PlannerInfo *root)
 
Listgenerate_join_implied_equalities (PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
 
Listgenerate_join_implied_equalities_for_ecs (PlannerInfo *root, List *eclasses, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
 
bool exprs_known_equal (PlannerInfo *root, Node *item1, Node *item2)
 
EquivalenceClassmatch_eclasses_to_foreign_key_col (PlannerInfo *root, ForeignKeyOptInfo *fkinfo, int colno)
 
void add_child_rel_equivalences (PlannerInfo *root, AppendRelInfo *appinfo, RelOptInfo *parent_rel, RelOptInfo *child_rel)
 
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)
 
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 117 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 2356 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().

2360 {
2361  Relids top_parent_relids = child_joinrel->top_parent_relids;
2362  Relids child_relids = child_joinrel->relids;
2363  Bitmapset *matching_ecs;
2364  int i;
2365 
2366  Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
2367 
2368  /* We need consider only ECs that mention the parent joinrel */
2369  matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids);
2370 
2371  i = -1;
2372  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2373  {
2374  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2375  int num_members;
2376 
2377  /*
2378  * If this EC contains a volatile expression, then generating child
2379  * EMs would be downright dangerous, so skip it. We rely on a
2380  * volatile EC having only one EM.
2381  */
2382  if (cur_ec->ec_has_volatile)
2383  continue;
2384 
2385  /* Sanity check on get_eclass_indexes_for_relids result */
2386  Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
2387 
2388  /*
2389  * We don't use foreach() here because there's no point in scanning
2390  * newly-added child members, so we can stop after the last
2391  * pre-existing EC member.
2392  */
2393  num_members = list_length(cur_ec->ec_members);
2394  for (int pos = 0; pos < num_members; pos++)
2395  {
2396  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2397 
2398  if (cur_em->em_is_const)
2399  continue; /* ignore consts here */
2400 
2401  /*
2402  * We consider only original EC members here, not
2403  * already-transformed child members.
2404  */
2405  if (cur_em->em_is_child)
2406  continue; /* ignore children here */
2407 
2408  /*
2409  * We may ignore expressions that reference a single baserel,
2410  * because add_child_rel_equivalences should have handled them.
2411  */
2412  if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
2413  continue;
2414 
2415  /* Does this member reference child's topmost parent rel? */
2416  if (bms_overlap(cur_em->em_relids, top_parent_relids))
2417  {
2418  /* Yes, generate transformed child version */
2419  Expr *child_expr;
2420  Relids new_relids;
2421  Relids new_nullable_relids;
2422 
2423  if (parent_joinrel->reloptkind == RELOPT_JOINREL)
2424  {
2425  /* Simple single-level transformation */
2426  child_expr = (Expr *)
2428  (Node *) cur_em->em_expr,
2429  nappinfos, appinfos);
2430  }
2431  else
2432  {
2433  /* Must do multi-level transformation */
2434  Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
2435  child_expr = (Expr *)
2437  (Node *) cur_em->em_expr,
2438  child_relids,
2439  top_parent_relids);
2440  }
2441 
2442  /*
2443  * Transform em_relids to match. Note we do *not* do
2444  * pull_varnos(child_expr) here, as for example the
2445  * transformation might have substituted a constant, but we
2446  * don't want the child member to be marked as constant.
2447  */
2448  new_relids = bms_difference(cur_em->em_relids,
2449  top_parent_relids);
2450  new_relids = bms_add_members(new_relids, child_relids);
2451 
2452  /*
2453  * For nullable_relids, we must selectively replace parent
2454  * nullable relids with child ones.
2455  */
2456  new_nullable_relids = cur_em->em_nullable_relids;
2457  if (bms_overlap(new_nullable_relids, top_parent_relids))
2458  new_nullable_relids =
2460  new_nullable_relids,
2461  child_relids,
2462  top_parent_relids);
2463 
2464  (void) add_eq_member(cur_ec, child_expr,
2465  new_relids, new_nullable_relids,
2466  true, cur_em->em_datatype);
2467  }
2468  }
2469  }
2470 }
Relids em_nullable_relids
Definition: pathnodes.h:986
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:525
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:621
Relids adjust_child_relids_multilevel(PlannerInfo *root, Relids relids, Relids child_relids, Relids top_parent_relids)
Definition: appendinfo.c:571
Node * adjust_appendrel_attrs_multilevel(PlannerInfo *root, Node *node, Relids child_relids, Relids top_parent_relids)
Definition: appendinfo.c:497
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:2859
Relids ec_relids
Definition: pathnodes.h:939
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:672
#define Assert(condition)
Definition: c.h:739
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:169
bool ec_has_volatile
Definition: pathnodes.h:942
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
int i
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, Relids nullable_relids, bool is_child, Oid datatype)
Definition: equivclass.c:549
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:793
List * ec_members
Definition: pathnodes.h:936
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 2228 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().

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

◆ add_paths_to_append_rel()

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

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

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

734 {
735  List *pathkeys;
736  Oid opfamily,
737  opcintype;
738  int16 strategy;
739  PathKey *cpathkey;
740 
741  /* Find the operator in pg_amop --- failure shouldn't happen */
742  if (!get_ordering_op_properties(opno,
743  &opfamily, &opcintype, &strategy))
744  elog(ERROR, "operator %u is not a valid ordering operator",
745  opno);
746 
747  cpathkey = make_pathkey_from_sortinfo(root,
748  expr,
749  nullable_relids,
750  opfamily,
751  opcintype,
752  exprCollation((Node *) expr),
753  (strategy == BTGreaterStrategyNumber),
754  (strategy == BTGreaterStrategyNumber),
755  0,
756  rel,
757  create_it);
758 
759  if (cpathkey)
760  pathkeys = list_make1(cpathkey);
761  else
762  pathkeys = NIL;
763 
764  return pathkeys;
765 }
signed short int16
Definition: c.h:346
#define NIL
Definition: pg_list.h:65
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Definition: nodes.h:525
unsigned int Oid
Definition: postgres_ext.h:31
#define list_make1(x1)
Definition: pg_list.h:227
#define ERROR
Definition: elog.h:43
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, int16 *strategy)
Definition: lsyscache.c:204
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:719
#define elog(elevel,...)
Definition: elog.h:228
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 469 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().

472 {
473  List *retval = NIL;
474  ListCell *lc;
475  int i;
476 
477  if (index->sortopfamily == NULL)
478  return NIL; /* non-orderable index */
479 
480  i = 0;
481  foreach(lc, index->indextlist)
482  {
483  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
484  Expr *indexkey;
485  bool reverse_sort;
486  bool nulls_first;
487  PathKey *cpathkey;
488 
489  /*
490  * INCLUDE columns are stored in index unordered, so they don't
491  * support ordered index scan.
492  */
493  if (i >= index->nkeycolumns)
494  break;
495 
496  /* We assume we don't need to make a copy of the tlist item */
497  indexkey = indextle->expr;
498 
499  if (ScanDirectionIsBackward(scandir))
500  {
501  reverse_sort = !index->reverse_sort[i];
502  nulls_first = !index->nulls_first[i];
503  }
504  else
505  {
506  reverse_sort = index->reverse_sort[i];
507  nulls_first = index->nulls_first[i];
508  }
509 
510  /*
511  * OK, try to make a canonical pathkey for this sort key. Note we're
512  * underneath any outer joins, so nullable_relids should be NULL.
513  */
514  cpathkey = make_pathkey_from_sortinfo(root,
515  indexkey,
516  NULL,
517  index->sortopfamily[i],
518  index->opcintype[i],
519  index->indexcollations[i],
520  reverse_sort,
521  nulls_first,
522  0,
523  index->rel->relids,
524  false);
525 
526  if (cpathkey)
527  {
528  /*
529  * We found the sort key in an EquivalenceClass, so it's relevant
530  * for this query. Add it to list, unless it's redundant.
531  */
532  if (!pathkey_is_redundant(cpathkey, retval))
533  retval = lappend(retval, cpathkey);
534  }
535  else
536  {
537  /*
538  * Boolean index keys might be redundant even if they do not
539  * appear in an EquivalenceClass, because of our special treatment
540  * of boolean equality conditions --- see the comment for
541  * indexcol_is_bool_constant_for_query(). If that applies, we can
542  * continue to examine lower-order index columns. Otherwise, the
543  * sort key is not an interesting sort order for this query, so we
544  * should stop considering index columns; any lower-order sort
545  * keys won't be useful either.
546  */
548  break;
549  }
550 
551  i++;
552  }
553 
554  return retval;
555 }
#define NIL
Definition: pg_list.h:65
Oid * indexcollations
Definition: pathnodes.h:805
List * indextlist
Definition: pathnodes.h:818
Oid * sortopfamily
Definition: pathnodes.h:808
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
RelOptInfo * rel
Definition: pathnodes.h:793
Relids relids
Definition: pathnodes.h:643
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:322
#define lfirst(lc)
Definition: pg_list.h:190
Expr * expr
Definition: primnodes.h:1393
int nkeycolumns
Definition: pathnodes.h:802
Oid * opcintype
Definition: pathnodes.h:807
bool indexcol_is_bool_constant_for_query(IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3757
int i
static PathKey * make_pathkey_from_sortinfo(PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opfamily, Oid opcintype, Oid collation, bool reverse_sort, bool nulls_first, Index sortref, Relids rel, bool create_it)
Definition: pathkeys.c:177
bool * nulls_first
Definition: pathnodes.h:810
bool * reverse_sort
Definition: pathnodes.h:809
Definition: pg_list.h:50

◆ build_join_pathkeys()

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

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

1032 {
1033  if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
1034  return NIL;
1035 
1036  /*
1037  * This used to be quite a complex bit of code, but now that all pathkey
1038  * sublists start out life canonicalized, we don't have to do a darn thing
1039  * here!
1040  *
1041  * We do, however, need to truncate the pathkeys list, since it may
1042  * contain pathkeys that were useful for forming this joinrel but are
1043  * uninteresting to higher levels.
1044  */
1045  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1046 }
#define NIL
Definition: pg_list.h:65
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:1816

◆ build_partition_pathkeys()

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

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

647 {
648  List *retval = NIL;
649  PartitionScheme partscheme = partrel->part_scheme;
650  int i;
651 
652  Assert(partscheme != NULL);
653  Assert(partitions_are_ordered(partrel->boundinfo, partrel->nparts));
654  /* For now, we can only cope with baserels */
655  Assert(IS_SIMPLE_REL(partrel));
656 
657  for (i = 0; i < partscheme->partnatts; i++)
658  {
659  PathKey *cpathkey;
660  Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
661 
662  /*
663  * Try to make a canonical pathkey for this partkey.
664  *
665  * We're considering a baserel scan, so nullable_relids should be
666  * NULL. Also, we assume the PartitionDesc lists any NULL partition
667  * last, so we treat the scan like a NULLS LAST index: we have
668  * nulls_first for backwards scan only.
669  */
670  cpathkey = make_pathkey_from_sortinfo(root,
671  keyCol,
672  NULL,
673  partscheme->partopfamily[i],
674  partscheme->partopcintype[i],
675  partscheme->partcollation[i],
676  ScanDirectionIsBackward(scandir),
677  ScanDirectionIsBackward(scandir),
678  0,
679  partrel->relids,
680  false);
681 
682 
683  if (cpathkey)
684  {
685  /*
686  * We found the sort key in an EquivalenceClass, so it's relevant
687  * for this query. Add it to list, unless it's redundant.
688  */
689  if (!pathkey_is_redundant(cpathkey, retval))
690  retval = lappend(retval, cpathkey);
691  }
692  else
693  {
694  /*
695  * Boolean partition keys might be redundant even if they do not
696  * appear in an EquivalenceClass, because of our special treatment
697  * of boolean equality conditions --- see the comment for
698  * partkey_is_bool_constant_for_query(). If that applies, we can
699  * continue to examine lower-order partition keys. Otherwise, the
700  * sort key is not an interesting sort order for this query, so we
701  * should stop considering partition columns; any lower-order sort
702  * keys won't be useful either.
703  */
704  if (!partkey_is_bool_constant_for_query(partrel, i))
705  {
706  *partialkeys = true;
707  return retval;
708  }
709  }
710  }
711 
712  *partialkeys = false;
713  return retval;
714 }
#define NIL
Definition: pg_list.h:65
static bool partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:575
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:616
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
List ** partexprs
Definition: pathnodes.h:726
#define linitial(l)
Definition: pg_list.h:195
int nparts
Definition: pathnodes.h:721
Relids relids
Definition: pathnodes.h:643
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:322
struct PartitionBoundInfoData * boundinfo
Definition: pathnodes.h:722
bool partitions_are_ordered(PartitionBoundInfo boundinfo, int nparts)
Definition: partbounds.c:875
#define Assert(condition)
Definition: c.h:739
int i
PartitionScheme part_scheme
Definition: pathnodes.h:720
static PathKey * make_pathkey_from_sortinfo(PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opfamily, Oid opcintype, Oid collation, bool reverse_sort, bool nulls_first, Index sortref, Relids rel, bool create_it)
Definition: pathkeys.c:177
Definition: pg_list.h:50

◆ canonicalize_ec_expression()

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

Definition at line 499 of file equivclass.c.

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

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

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

◆ check_index_predicates()

void check_index_predicates ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 3395 of file indxpath.c.

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

Referenced by set_plain_rel_size(), and set_tablesample_rel_size().

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

◆ compare_pathkeys()

PathKeysComparison compare_pathkeys ( List keys1,
List keys2 
)

Definition at line 285 of file pathkeys.c.

References forboth, lfirst, PATHKEYS_BETTER1, PATHKEYS_BETTER2, PATHKEYS_DIFFERENT, and PATHKEYS_EQUAL.

Referenced by add_partial_path(), add_partial_path_precheck(), add_path(), add_path_precheck(), add_paths_to_append_rel(), pathkeys_contained_in(), and set_cheapest().

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

◆ compute_parallel_worker()

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

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

3577 {
3578  int parallel_workers = 0;
3579 
3580  /*
3581  * If the user has set the parallel_workers reloption, use that; otherwise
3582  * select a default number of workers.
3583  */
3584  if (rel->rel_parallel_workers != -1)
3585  parallel_workers = rel->rel_parallel_workers;
3586  else
3587  {
3588  /*
3589  * If the number of pages being scanned is insufficient to justify a
3590  * parallel scan, just return zero ... unless it's an inheritance
3591  * child. In that case, we want to generate a parallel path here
3592  * anyway. It might not be worthwhile just for this relation, but
3593  * when combined with all of its inheritance siblings it may well pay
3594  * off.
3595  */
3596  if (rel->reloptkind == RELOPT_BASEREL &&
3597  ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
3598  (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
3599  return 0;
3600 
3601  if (heap_pages >= 0)
3602  {
3603  int heap_parallel_threshold;
3604  int heap_parallel_workers = 1;
3605 
3606  /*
3607  * Select the number of workers based on the log of the size of
3608  * the relation. This probably needs to be a good deal more
3609  * sophisticated, but we need something here for now. Note that
3610  * the upper limit of the min_parallel_table_scan_size GUC is
3611  * chosen to prevent overflow here.
3612  */
3613  heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
3614  while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
3615  {
3616  heap_parallel_workers++;
3617  heap_parallel_threshold *= 3;
3618  if (heap_parallel_threshold > INT_MAX / 3)
3619  break; /* avoid overflow */
3620  }
3621 
3622  parallel_workers = heap_parallel_workers;
3623  }
3624 
3625  if (index_pages >= 0)
3626  {
3627  int index_parallel_workers = 1;
3628  int index_parallel_threshold;
3629 
3630  /* same calculation as for heap_pages above */
3631  index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
3632  while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
3633  {
3634  index_parallel_workers++;
3635  index_parallel_threshold *= 3;
3636  if (index_parallel_threshold > INT_MAX / 3)
3637  break; /* avoid overflow */
3638  }
3639 
3640  if (parallel_workers > 0)
3641  parallel_workers = Min(parallel_workers, index_parallel_workers);
3642  else
3643  parallel_workers = index_parallel_workers;
3644  }
3645  }
3646 
3647  /* In no case use more than caller supplied maximum number of workers */
3648  parallel_workers = Min(parallel_workers, max_workers);
3649 
3650  return parallel_workers;
3651 }
RelOptKind reloptkind
Definition: pathnodes.h:640
#define Min(x, y)
Definition: c.h:911
uint32 BlockNumber
Definition: block.h:31
int min_parallel_index_scan_size
Definition: allpaths.c:65
int rel_parallel_workers
Definition: pathnodes.h:689
#define Max(x, y)
Definition: c.h:905
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 784 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().

787 {
788  List *retval = NIL;
789  int retvallen = 0;
790  int outer_query_keys = list_length(root->query_pathkeys);
791  ListCell *i;
792 
793  foreach(i, subquery_pathkeys)
794  {
795  PathKey *sub_pathkey = (PathKey *) lfirst(i);
796  EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
797  PathKey *best_pathkey = NULL;
798 
799  if (sub_eclass->ec_has_volatile)
800  {
801  /*
802  * If the sub_pathkey's EquivalenceClass is volatile, then it must
803  * have come from an ORDER BY clause, and we have to match it to
804  * that same targetlist entry.
805  */
806  TargetEntry *tle;
807  Var *outer_var;
808 
809  if (sub_eclass->ec_sortref == 0) /* can't happen */
810  elog(ERROR, "volatile EquivalenceClass has no sortref");
811  tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
812  Assert(tle);
813  /* Is TLE actually available to the outer query? */
814  outer_var = find_var_for_subquery_tle(rel, tle);
815  if (outer_var)
816  {
817  /* We can represent this sub_pathkey */
818  EquivalenceMember *sub_member;
819  EquivalenceClass *outer_ec;
820 
821  Assert(list_length(sub_eclass->ec_members) == 1);
822  sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
823 
824  /*
825  * Note: it might look funny to be setting sortref = 0 for a
826  * reference to a volatile sub_eclass. However, the
827  * expression is *not* volatile in the outer query: it's just
828  * a Var referencing whatever the subquery emitted. (IOW, the
829  * outer query isn't going to re-execute the volatile
830  * expression itself.) So this is okay. Likewise, it's
831  * correct to pass nullable_relids = NULL, because we're
832  * underneath any outer joins appearing in the outer query.
833  */
834  outer_ec =
836  (Expr *) outer_var,
837  NULL,
838  sub_eclass->ec_opfamilies,
839  sub_member->em_datatype,
840  sub_eclass->ec_collation,
841  0,
842  rel->relids,
843  false);
844 
845  /*
846  * If we don't find a matching EC, sub-pathkey isn't
847  * interesting to the outer query
848  */
849  if (outer_ec)
850  best_pathkey =
852  outer_ec,
853  sub_pathkey->pk_opfamily,
854  sub_pathkey->pk_strategy,
855  sub_pathkey->pk_nulls_first);
856  }
857  }
858  else
859  {
860  /*
861  * Otherwise, the sub_pathkey's EquivalenceClass could contain
862  * multiple elements (representing knowledge that multiple items
863  * are effectively equal). Each element might match none, one, or
864  * more of the output columns that are visible to the outer query.
865  * This means we may have multiple possible representations of the
866  * sub_pathkey in the context of the outer query. Ideally we
867  * would generate them all and put them all into an EC of the
868  * outer query, thereby propagating equality knowledge up to the
869  * outer query. Right now we cannot do so, because the outer
870  * query's EquivalenceClasses are already frozen when this is
871  * called. Instead we prefer the one that has the highest "score"
872  * (number of EC peers, plus one if it matches the outer
873  * query_pathkeys). This is the most likely to be useful in the
874  * outer query.
875  */
876  int best_score = -1;
877  ListCell *j;
878 
879  foreach(j, sub_eclass->ec_members)
880  {
881  EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
882  Expr *sub_expr = sub_member->em_expr;
883  Oid sub_expr_type = sub_member->em_datatype;
884  Oid sub_expr_coll = sub_eclass->ec_collation;
885  ListCell *k;
886 
887  if (sub_member->em_is_child)
888  continue; /* ignore children here */
889 
890  foreach(k, subquery_tlist)
891  {
892  TargetEntry *tle = (TargetEntry *) lfirst(k);
893  Var *outer_var;
894  Expr *tle_expr;
895  EquivalenceClass *outer_ec;
896  PathKey *outer_pk;
897  int score;
898 
899  /* Is TLE actually available to the outer query? */
900  outer_var = find_var_for_subquery_tle(rel, tle);
901  if (!outer_var)
902  continue;
903 
904  /*
905  * The targetlist entry is considered to match if it
906  * matches after sort-key canonicalization. That is
907  * needed since the sub_expr has been through the same
908  * process.
909  */
910  tle_expr = canonicalize_ec_expression(tle->expr,
911  sub_expr_type,
912  sub_expr_coll);
913  if (!equal(tle_expr, sub_expr))
914  continue;
915 
916  /* See if we have a matching EC for the TLE */
917  outer_ec = get_eclass_for_sort_expr(root,
918  (Expr *) outer_var,
919  NULL,
920  sub_eclass->ec_opfamilies,
921  sub_expr_type,
922  sub_expr_coll,
923  0,
924  rel->relids,
925  false);
926 
927  /*
928  * If we don't find a matching EC, this sub-pathkey isn't
929  * interesting to the outer query
930  */
931  if (!outer_ec)
932  continue;
933 
934  outer_pk = make_canonical_pathkey(root,
935  outer_ec,
936  sub_pathkey->pk_opfamily,
937  sub_pathkey->pk_strategy,
938  sub_pathkey->pk_nulls_first);
939  /* score = # of equivalence peers */
940  score = list_length(outer_ec->ec_members) - 1;
941  /* +1 if it matches the proper query_pathkeys item */
942  if (retvallen < outer_query_keys &&
943  list_nth(root->query_pathkeys, retvallen) == outer_pk)
944  score++;
945  if (score > best_score)
946  {
947  best_pathkey = outer_pk;
948  best_score = score;
949  }
950  }
951  }
952  }
953 
954  /*
955  * If we couldn't find a representation of this sub_pathkey, we're
956  * done (we can't use the ones to its right, either).
957  */
958  if (!best_pathkey)
959  break;
960 
961  /*
962  * Eliminate redundant ordering info; could happen if outer query
963  * equivalences subquery keys...
964  */
965  if (!pathkey_is_redundant(best_pathkey, retval))
966  {
967  retval = lappend(retval, best_pathkey);
968  retvallen++;
969  }
970  }
971 
972  return retval;
973 }
#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:3011
EquivalenceClass * get_eclass_for_sort_expr(PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
Definition: equivclass.c:625
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:54
unsigned int Oid
Definition: postgres_ext.h:31
Definition: primnodes.h:167
int pk_strategy
Definition: pathnodes.h:1015
#define linitial(l)
Definition: pg_list.h:195
bool pk_nulls_first
Definition: pathnodes.h:1016
#define ERROR
Definition: elog.h:43
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:499
Relids relids
Definition: pathnodes.h:643
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:985
List * lappend(List *list, void *datum)
Definition: list.c:322
List * ec_opfamilies
Definition: pathnodes.h:934
#define Assert(condition)
Definition: c.h:739
#define lfirst(lc)
Definition: pg_list.h:190
Expr * expr
Definition: primnodes.h:1393
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1013
static int list_length(const List *l)
Definition: pg_list.h:169
bool ec_has_volatile
Definition: pathnodes.h:942
Oid pk_opfamily
Definition: pathnodes.h:1014
#define elog(elevel,...)
Definition: elog.h:228
int i
Definition: pg_list.h:50
List * ec_members
Definition: pathnodes.h:936

◆ create_index_paths()

void create_index_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 232 of file indxpath.c.

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

Referenced by set_plain_rel_pathlist().

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

◆ create_partial_bitmap_paths()

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

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

3541 {
3542  int parallel_workers;
3543  double pages_fetched;
3544 
3545  /* Compute heap pages for bitmap heap scan */
3546  pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
3547  NULL, NULL);
3548 
3549  parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
3551 
3552  if (parallel_workers <= 0)
3553  return;
3554 
3555  add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
3556  bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
3557 }
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:3575
Relids lateral_relids
Definition: pathnodes.h:668
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:749
int max_parallel_workers_per_gather
Definition: costsize.c:122
double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, int loop_count, Cost *cost, double *tuple)
Definition: costsize.c:5508
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:711
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
List * baserestrictinfo
Definition: pathnodes.h:705
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:668
static void BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
Definition: tidpath.c:313
List * joininfo
Definition: pathnodes.h:709
Relids lateral_referencers
Definition: pathnodes.h:679
static List * TidQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
Definition: tidpath.c:230
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1151
Definition: pg_list.h:50
List * generate_implied_equalities_for_column(PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
Definition: equivclass.c:2497

◆ eclass_useful_for_merging()

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

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

2741 {
2742  Relids relids;
2743  ListCell *lc;
2744 
2745  Assert(!eclass->ec_merged);
2746 
2747  /*
2748  * Won't generate joinclauses if const or single-member (the latter test
2749  * covers the volatile case too)
2750  */
2751  if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
2752  return false;
2753 
2754  /*
2755  * Note we don't test ec_broken; if we did, we'd need a separate code path
2756  * to look through ec_sources. Checking the members anyway is OK as a
2757  * possibly-overoptimistic heuristic.
2758  */
2759 
2760  /* If specified rel is a child, we must consider the topmost parent rel */
2761  if (IS_OTHER_REL(rel))
2762  {
2764  relids = rel->top_parent_relids;
2765  }
2766  else
2767  relids = rel->relids;
2768 
2769  /* If rel already includes all members of eclass, no point in searching */
2770  if (bms_is_subset(eclass->ec_relids, relids))
2771  return false;
2772 
2773  /* To join, we need a member not in the given rel */
2774  foreach(lc, eclass->ec_members)
2775  {
2776  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
2777 
2778  if (cur_em->em_is_child)
2779  continue; /* ignore children here */
2780 
2781  if (!bms_overlap(cur_em->em_relids, relids))
2782  return true;
2783  }
2784 
2785  return false;
2786 }
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:631
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
Relids ec_relids
Definition: pathnodes.h:939
Relids relids
Definition: pathnodes.h:643
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define Assert(condition)
Definition: c.h:739
#define lfirst(lc)
Definition: pg_list.h:190
static int list_length(const List *l)
Definition: pg_list.h:169
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:948
List * ec_members
Definition: pathnodes.h:936
Relids top_parent_relids
Definition: pathnodes.h:716

◆ exprs_known_equal()

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

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

2086 {
2087  ListCell *lc1;
2088 
2089  foreach(lc1, root->eq_classes)
2090  {
2091  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2092  bool item1member = false;
2093  bool item2member = false;
2094  ListCell *lc2;
2095 
2096  /* Never match to a volatile EC */
2097  if (ec->ec_has_volatile)
2098  continue;
2099 
2100  foreach(lc2, ec->ec_members)
2101  {
2103 
2104  if (em->em_is_child)
2105  continue; /* ignore children here */
2106  if (equal(item1, em->em_expr))
2107  item1member = true;
2108  else if (equal(item2, em->em_expr))
2109  item2member = true;
2110  /* Exit as soon as equality is proven */
2111  if (item1member && item2member)
2112  return true;
2113  }
2114  }
2115  return false;
2116 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3011
#define lfirst(lc)
Definition: pg_list.h:190
List * eq_classes
Definition: pathnodes.h:266
bool ec_has_volatile
Definition: pathnodes.h:942
List * ec_members
Definition: pathnodes.h:936

◆ find_mergeclauses_for_outer_pathkeys()

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

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

1211 {
1212  List *mergeclauses = NIL;
1213  ListCell *i;
1214 
1215  /* make sure we have eclasses cached in the clauses */
1216  foreach(i, restrictinfos)
1217  {
1218  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1219 
1220  update_mergeclause_eclasses(root, rinfo);
1221  }
1222 
1223  foreach(i, pathkeys)
1224  {
1225  PathKey *pathkey = (PathKey *) lfirst(i);
1226  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1227  List *matched_restrictinfos = NIL;
1228  ListCell *j;
1229 
1230  /*----------
1231  * A mergejoin clause matches a pathkey if it has the same EC.
1232  * If there are multiple matching clauses, take them all. In plain
1233  * inner-join scenarios we expect only one match, because
1234  * equivalence-class processing will have removed any redundant
1235  * mergeclauses. However, in outer-join scenarios there might be
1236  * multiple matches. An example is
1237  *
1238  * select * from a full join b
1239  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1240  *
1241  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1242  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1243  * we *must* do so or we will be unable to form a valid plan.
1244  *
1245  * We expect that the given pathkeys list is canonical, which means
1246  * no two members have the same EC, so it's not possible for this
1247  * code to enter the same mergeclause into the result list twice.
1248  *
1249  * It's possible that multiple matching clauses might have different
1250  * ECs on the other side, in which case the order we put them into our
1251  * result makes a difference in the pathkeys required for the inner
1252  * input rel. However this routine hasn't got any info about which
1253  * order would be best, so we don't worry about that.
1254  *
1255  * It's also possible that the selected mergejoin clauses produce
1256  * a noncanonical ordering of pathkeys for the inner side, ie, we
1257  * might select clauses that reference b.v1, b.v2, b.v1 in that
1258  * order. This is not harmful in itself, though it suggests that
1259  * the clauses are partially redundant. Since the alternative is
1260  * to omit mergejoin clauses and thereby possibly fail to generate a
1261  * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1262  * has to delete duplicates when it constructs the inner pathkeys
1263  * list, and we also have to deal with such cases specially in
1264  * create_mergejoin_plan().
1265  *----------
1266  */
1267  foreach(j, restrictinfos)
1268  {
1269  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1270  EquivalenceClass *clause_ec;
1271 
1272  clause_ec = rinfo->outer_is_left ?
1273  rinfo->left_ec : rinfo->right_ec;
1274  if (clause_ec == pathkey_ec)
1275  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1276  }
1277 
1278  /*
1279  * If we didn't find a mergeclause, we're done --- any additional
1280  * sort-key positions in the pathkeys are useless. (But we can still
1281  * mergejoin if we found at least one mergeclause.)
1282  */
1283  if (matched_restrictinfos == NIL)
1284  break;
1285 
1286  /*
1287  * If we did find usable mergeclause(s) for this sort-key position,
1288  * add them to result list.
1289  */
1290  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1291  }
1292 
1293  return mergeclauses;
1294 }
#define NIL
Definition: pg_list.h:65
List * list_concat(List *list1, const List *list2)
Definition: list.c:516
EquivalenceClass * right_ec
Definition: pathnodes.h:1994
bool outer_is_left
Definition: pathnodes.h:2000
List * lappend(List *list, void *datum)
Definition: list.c:322
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1013
EquivalenceClass * left_ec
Definition: pathnodes.h:1993
int i
Definition: pg_list.h:50
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1174

◆ generate_base_implied_equalities()

void generate_base_implied_equalities ( PlannerInfo root)

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

828 {
829  int ec_index;
830  ListCell *lc;
831 
832  /*
833  * At this point, we're done absorbing knowledge of equivalences in the
834  * query, so no further EC merging should happen, and ECs remaining in the
835  * eq_classes list can be considered canonical. (But note that it's still
836  * possible for new single-member ECs to be added through
837  * get_eclass_for_sort_expr().)
838  */
839  root->ec_merging_done = true;
840 
841  ec_index = 0;
842  foreach(lc, root->eq_classes)
843  {
845  bool can_generate_joinclause = false;
846  int i;
847 
848  Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
849  Assert(!ec->ec_broken); /* not yet anyway... */
850 
851  /*
852  * Generate implied equalities that are restriction clauses.
853  * Single-member ECs won't generate any deductions, either here or at
854  * the join level.
855  */
856  if (list_length(ec->ec_members) > 1)
857  {
858  if (ec->ec_has_const)
860  else
862 
863  /* Recover if we failed to generate required derived clauses */
864  if (ec->ec_broken)
866 
867  /* Detect whether this EC might generate join clauses */
868  can_generate_joinclause =
870  }
871 
872  /*
873  * Mark the base rels cited in each eclass (which should all exist by
874  * now) with the eq_classes indexes of all eclasses mentioning them.
875  * This will let us avoid searching in subsequent lookups. While
876  * we're at it, we can mark base rels that have pending eclass joins;
877  * this is a cheap version of has_relevant_eclass_joinclause().
878  */
879  i = -1;
880  while ((i = bms_next_member(ec->ec_relids, i)) > 0)
881  {
882  RelOptInfo *rel = root->simple_rel_array[i];
883 
885 
887  ec_index);
888 
889  if (can_generate_joinclause)
890  rel->has_eclass_joins = true;
891  }
892 
893  ec_index++;
894  }
895 }
bool has_eclass_joins
Definition: pathnodes.h:711
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:978
RelOptKind reloptkind
Definition: pathnodes.h:640
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:1069
struct RelOptInfo ** simple_rel_array
Definition: pathnodes.h:203
Relids ec_relids
Definition: pathnodes.h:939
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:672
#define Assert(condition)
Definition: c.h:739
#define lfirst(lc)
Definition: pg_list.h:190
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:169
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:736
int i
static void generate_base_implied_equalities_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:901
Bitmapset * eclass_indexes
Definition: pathnodes.h:685
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:948
List * ec_members
Definition: pathnodes.h:936

◆ generate_gather_paths()

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

Definition at line 2682 of file allpaths.c.

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

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

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

2502 {
2503  List *result = NIL;
2504  bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
2505  Relids parent_relids;
2506  int i;
2507 
2508  /* Should be OK to rely on eclass_indexes */
2509  Assert(root->ec_merging_done);
2510 
2511  /* Indexes are available only on base or "other" member relations. */
2512  Assert(IS_SIMPLE_REL(rel));
2513 
2514  /* If it's a child rel, we'll need to know what its parent(s) are */
2515  if (is_child_rel)
2516  parent_relids = find_childrel_parents(root, rel);
2517  else
2518  parent_relids = NULL; /* not used, but keep compiler quiet */
2519 
2520  i = -1;
2521  while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
2522  {
2523  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2524  EquivalenceMember *cur_em;
2525  ListCell *lc2;
2526 
2527  /* Sanity check eclass_indexes only contain ECs for rel */
2528  Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
2529 
2530  /*
2531  * Won't generate joinclauses if const or single-member (the latter
2532  * test covers the volatile case too)
2533  */
2534  if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
2535  continue;
2536 
2537  /*
2538  * Scan members, looking for a match to the target column. Note that
2539  * child EC members are considered, but only when they belong to the
2540  * target relation. (Unlike regular members, the same expression
2541  * could be a child member of more than one EC. Therefore, it's
2542  * potentially order-dependent which EC a child relation's target
2543  * column gets matched to. This is annoying but it only happens in
2544  * corner cases, so for now we live with just reporting the first
2545  * match. See also get_eclass_for_sort_expr.)
2546  */
2547  cur_em = NULL;
2548  foreach(lc2, cur_ec->ec_members)
2549  {
2550  cur_em = (EquivalenceMember *) lfirst(lc2);
2551  if (bms_equal(cur_em->em_relids, rel->relids) &&
2552  callback(root, rel, cur_ec, cur_em, callback_arg))
2553  break;
2554  cur_em = NULL;
2555  }
2556 
2557  if (!cur_em)
2558  continue;
2559 
2560  /*
2561  * Found our match. Scan the other EC members and attempt to generate
2562  * joinclauses.
2563  */
2564  foreach(lc2, cur_ec->ec_members)
2565  {
2566  EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
2567  Oid eq_op;
2568  RestrictInfo *rinfo;
2569 
2570  if (other_em->em_is_child)
2571  continue; /* ignore children here */
2572 
2573  /* Make sure it'll be a join to a different rel */
2574  if (other_em == cur_em ||
2575  bms_overlap(other_em->em_relids, rel->relids))
2576  continue;
2577 
2578  /* Forget it if caller doesn't want joins to this rel */
2579  if (bms_overlap(other_em->em_relids, prohibited_rels))
2580  continue;
2581 
2582  /*
2583  * Also, if this is a child rel, avoid generating a useless join
2584  * to its parent rel(s).
2585  */
2586  if (is_child_rel &&
2587  bms_overlap(parent_relids, other_em->em_relids))
2588  continue;
2589 
2590  eq_op = select_equality_operator(cur_ec,
2591  cur_em->em_datatype,
2592  other_em->em_datatype);
2593  if (!OidIsValid(eq_op))
2594  continue;
2595 
2596  /* set parent_ec to mark as redundant with other joinclauses */
2597  rinfo = create_join_clause(root, cur_ec, eq_op,
2598  cur_em, other_em,
2599  cur_ec);
2600 
2601  result = lappend(result, rinfo);
2602  }
2603 
2604  /*
2605  * If somehow we failed to create any join clauses, we might as well
2606  * keep scanning the ECs for another match. But if we did make any,
2607  * we're done, because we don't want to return non-redundant clauses.
2608  */
2609  if (result)
2610  break;
2611  }
2612 
2613  return result;
2614 }
#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:1535
RelOptKind reloptkind
Definition: pathnodes.h:640
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:645
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:616
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
static void callback(struct sockaddr *addr, struct sockaddr *mask, void *unused)
Definition: test_ifaddrs.c:48
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
static Oid select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
Definition: equivclass.c:1500
Relids ec_relids
Definition: pathnodes.h:939
Relids relids
Definition: pathnodes.h:643
List * lappend(List *list, void *datum)
Definition: list.c:322
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1228
#define Assert(condition)
Definition: c.h:739
#define lfirst(lc)
Definition: pg_list.h:190
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:169
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
int i
Definition: pg_list.h:50
Bitmapset * eclass_indexes
Definition: pathnodes.h:685
List * ec_members
Definition: pathnodes.h:936
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 1126 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().

1130 {
1131  List *result = NIL;
1132  Relids inner_relids = inner_rel->relids;
1133  Relids nominal_inner_relids;
1134  Relids nominal_join_relids;
1135  Bitmapset *matching_ecs;
1136  int i;
1137 
1138  /* If inner rel is a child, extra setup work is needed */
1139  if (IS_OTHER_REL(inner_rel))
1140  {
1141  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1142 
1143  /* Fetch relid set for the topmost parent rel */
1144  nominal_inner_relids = inner_rel->top_parent_relids;
1145  /* ECs will be marked with the parent's relid, not the child's */
1146  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1147  }
1148  else
1149  {
1150  nominal_inner_relids = inner_relids;
1151  nominal_join_relids = join_relids;
1152  }
1153 
1154  /*
1155  * Get all eclasses in common between inner_rel's relids and outer_relids
1156  */
1157  matching_ecs = get_common_eclass_indexes(root, inner_rel->relids,
1158  outer_relids);
1159 
1160  i = -1;
1161  while ((i = bms_next_member(matching_ecs, i)) >= 0)
1162  {
1164  List *sublist = NIL;
1165 
1166  /* ECs containing consts do not need any further enforcement */
1167  if (ec->ec_has_const)
1168  continue;
1169 
1170  /* Single-member ECs won't generate any deductions */
1171  if (list_length(ec->ec_members) <= 1)
1172  continue;
1173 
1174  /* Sanity check that this eclass overlaps the join */
1175  Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
1176 
1177  if (!ec->ec_broken)
1179  ec,
1180  join_relids,
1181  outer_relids,
1182  inner_relids);
1183 
1184  /* Recover if we failed to generate required derived clauses */
1185  if (ec->ec_broken)
1187  ec,
1188  nominal_join_relids,
1189  outer_relids,
1190  nominal_inner_relids,
1191  inner_rel);
1192 
1193  result = list_concat(result, sublist);
1194  }
1195 
1196  return result;
1197 }
#define NIL
Definition: pg_list.h:65
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:631
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
List * list_concat(List *list1, const List *list2)
Definition: list.c:516
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
static List * generate_join_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec, Relids nominal_join_relids, Relids outer_relids, Relids nominal_inner_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1451
Relids ec_relids
Definition: pathnodes.h:939
Relids relids
Definition: pathnodes.h:643
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1275
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:2883
#define Assert(condition)
Definition: c.h:739
List * eq_classes
Definition: pathnodes.h:266
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:225
static int list_length(const List *l)
Definition: pg_list.h:169
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
int i
Definition: pg_list.h:50
List * ec_members
Definition: pathnodes.h:936
Relids top_parent_relids
Definition: pathnodes.h:716

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

1209 {
1210  List *result = NIL;
1211  Relids inner_relids = inner_rel->relids;
1212  Relids nominal_inner_relids;
1213  Relids nominal_join_relids;
1214  ListCell *lc;
1215 
1216  /* If inner rel is a child, extra setup work is needed */
1217  if (IS_OTHER_REL(inner_rel))
1218  {
1219  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1220 
1221  /* Fetch relid set for the topmost parent rel */
1222  nominal_inner_relids = inner_rel->top_parent_relids;
1223  /* ECs will be marked with the parent's relid, not the child's */
1224  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1225  }
1226  else
1227  {
1228  nominal_inner_relids = inner_relids;
1229  nominal_join_relids = join_relids;
1230  }
1231 
1232  foreach(lc, eclasses)
1233  {
1235  List *sublist = NIL;
1236 
1237  /* ECs containing consts do not need any further enforcement */
1238  if (ec->ec_has_const)
1239  continue;
1240 
1241  /* Single-member ECs won't generate any deductions */
1242  if (list_length(ec->ec_members) <= 1)
1243  continue;
1244 
1245  /* We can quickly ignore any that don't overlap the join, too */
1246  if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1247  continue;
1248 
1249  if (!ec->ec_broken)
1251  ec,
1252  join_relids,
1253  outer_relids,
1254  inner_relids);
1255 
1256  /* Recover if we failed to generate required derived clauses */
1257  if (ec->ec_broken)
1259  ec,
1260  nominal_join_relids,
1261  outer_relids,
1262  nominal_inner_relids,
1263  inner_rel);
1264 
1265  result = list_concat(result, sublist);
1266  }
1267 
1268  return result;
1269 }
#define NIL
Definition: pg_list.h:65
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:631
List * list_concat(List *list1, const List *list2)
Definition: list.c:516
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:1451
Relids ec_relids
Definition: pathnodes.h:939
Relids relids
Definition: pathnodes.h:643
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1275
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define Assert(condition)
Definition: c.h:739
#define lfirst(lc)
Definition: pg_list.h:190
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:225
static int list_length(const List *l)
Definition: pg_list.h:169
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
Definition: pg_list.h:50
List * ec_members
Definition: pathnodes.h:936
Relids top_parent_relids
Definition: pathnodes.h:716

◆ generate_partitionwise_join_paths()

void generate_partitionwise_join_paths ( PlannerInfo root,
RelOptInfo rel 
)

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

3664 {
3665  List *live_children = NIL;
3666  int cnt_parts;
3667  int num_parts;
3668  RelOptInfo **part_rels;
3669 
3670  /* Handle only join relations here. */
3671  if (!IS_JOIN_REL(rel))
3672  return;
3673 
3674  /* We've nothing to do if the relation is not partitioned. */
3675  if (!IS_PARTITIONED_REL(rel))
3676  return;
3677 
3678  /* The relation should have consider_partitionwise_join set. */
3680 
3681  /* Guard against stack overflow due to overly deep partition hierarchy. */
3683 
3684  num_parts = rel->nparts;
3685  part_rels = rel->part_rels;
3686 
3687  /* Collect non-dummy child-joins. */
3688  for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
3689  {
3690  RelOptInfo *child_rel = part_rels[cnt_parts];
3691 
3692  /* If it's been pruned entirely, it's certainly dummy. */
3693  if (child_rel == NULL)
3694  continue;
3695 
3696  /* Add partitionwise join paths for partitioned child-joins. */
3697  generate_partitionwise_join_paths(root, child_rel);
3698 
3699  set_cheapest(child_rel);
3700 
3701  /* Dummy children will not be scanned, so ignore those. */
3702  if (IS_DUMMY_REL(child_rel))
3703  continue;
3704 
3705 #ifdef OPTIMIZER_DEBUG
3706  debug_print_rel(root, child_rel);
3707 #endif
3708 
3709  live_children = lappend(live_children, child_rel);
3710  }
3711 
3712  /* If all child-joins are dummy, parent join is also dummy. */
3713  if (!live_children)
3714  {
3715  mark_dummy_rel(rel);
3716  return;
3717  }
3718 
3719  /* Build additional paths for this rel from child-join paths. */
3720  add_paths_to_append_rel(root, rel, live_children);
3721  list_free(live_children);
3722 }
#define NIL
Definition: pg_list.h:65
void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
Definition: allpaths.c:1294
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:3663
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:621
#define IS_DUMMY_REL(r)
Definition: pathnodes.h:1390
void check_stack_depth(void)
Definition: postgres.c:3302
int nparts
Definition: pathnodes.h:721
List * lappend(List *list, void *datum)
Definition: list.c:322
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:244
bool consider_partitionwise_join
Definition: pathnodes.h:714
void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1257
#define Assert(condition)
Definition: c.h:739
struct RelOptInfo ** part_rels
Definition: pathnodes.h:724
#define IS_PARTITIONED_REL(rel)
Definition: pathnodes.h:739
void list_free(List *list)
Definition: list.c:1377
Definition: pg_list.h:50

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

399 {
400  Path *matched_path = NULL;
401  ListCell *l;
402 
403  foreach(l, paths)
404  {
405  Path *path = (Path *) lfirst(l);
406 
407  /*
408  * Since cost comparison is a lot cheaper than pathkey comparison, do
409  * that first. (XXX is that still true?)
410  */
411  if (matched_path != NULL &&
412  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
413  continue;
414 
415  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
416  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
417  matched_path = path;
418  }
419  return matched_path;
420 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1135
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
List * pathkeys
Definition: pathnodes.h:1130
#define lfirst(lc)
Definition: pg_list.h:190
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:117

◆ get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner ( List paths)

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

429 {
430  ListCell *l;
431 
432  foreach(l, paths)
433  {
434  Path *innerpath = (Path *) lfirst(l);
435 
436  if (innerpath->parallel_safe &&
437  bms_is_empty(PATH_REQ_OUTER(innerpath)))
438  return innerpath;
439  }
440 
441  return NULL;
442 }
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1135
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define lfirst(lc)
Definition: pg_list.h:190
bool parallel_safe
Definition: pathnodes.h:1122

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

354 {
355  Path *matched_path = NULL;
356  ListCell *l;
357 
358  foreach(l, paths)
359  {
360  Path *path = (Path *) lfirst(l);
361 
362  /*
363  * Since cost comparison is a lot cheaper than pathkey comparison, do
364  * that first. (XXX is that still true?)
365  */
366  if (matched_path != NULL &&
367  compare_path_costs(matched_path, path, cost_criterion) <= 0)
368  continue;
369 
370  if (require_parallel_safe && !path->parallel_safe)
371  continue;
372 
373  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
374  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
375  matched_path = path;
376  }
377  return matched_path;
378 }
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:1135
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
List * pathkeys
Definition: pathnodes.h:1130
#define lfirst(lc)
Definition: pg_list.h:190
bool parallel_safe
Definition: pathnodes.h:1122

◆ get_eclass_for_sort_expr()

EquivalenceClass* get_eclass_for_sort_expr ( PlannerInfo root,
Expr expr,
Relids  nullable_relids,
List opfamilies,
Oid  opcintype,
Oid  collation,
Index  sortref,
Relids  rel,
bool  create_it 
)

Definition at line 625 of file equivclass.c.

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

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

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

2695 {
2696  Bitmapset *matched_ecs;
2697  int i;
2698 
2699  /* Examine only eclasses mentioning rel1 */
2700  matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
2701 
2702  i = -1;
2703  while ((i = bms_next_member(matched_ecs, i)) >= 0)
2704  {
2706  i);
2707 
2708  /*
2709  * Won't generate joinclauses if single-member (this test covers the
2710  * volatile case too)
2711  */
2712  if (list_length(ec->ec_members) <= 1)
2713  continue;
2714 
2715  /*
2716  * Per the comment in have_relevant_eclass_joinclause, it's sufficient
2717  * to find an EC that mentions both this rel and some other rel.
2718  */
2719  if (!bms_is_subset(ec->ec_relids, rel1->relids))
2720  return true;
2721  }
2722 
2723  return false;
2724 }
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:2859
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
Relids ec_relids
Definition: pathnodes.h:939
Relids relids
Definition: pathnodes.h:643
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:169
int i
List * ec_members
Definition: pathnodes.h:936

◆ has_useful_pathkeys()

bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

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

1857 {
1858  if (rel->joininfo != NIL || rel->has_eclass_joins)
1859  return true; /* might be able to use pathkeys for merging */
1860  if (root->query_pathkeys != NIL)
1861  return true; /* might be able to use them for ordering */
1862  return false; /* definitely useless */
1863 }
bool has_eclass_joins
Definition: pathnodes.h:711
#define NIL
Definition: pg_list.h:65
List * query_pathkeys
Definition: pathnodes.h:298
List * joininfo
Definition: pathnodes.h:709

◆ have_dangerous_phv()

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

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

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

◆ have_join_order_restriction()

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

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

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

◆ have_partkey_equi_join()

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

Definition at line 1582 of file joinrels.c.

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

Referenced by build_joinrel_partition_info().

1585 {
1586  PartitionScheme part_scheme = rel1->part_scheme;
1587  ListCell *lc;
1588  int cnt_pks;
1589  bool pk_has_clause[PARTITION_MAX_KEYS];
1590  bool strict_op;
1591 
1592  /*
1593  * This function should be called when the joining relations have same
1594  * partitioning scheme.
1595  */
1596  Assert(rel1->part_scheme == rel2->part_scheme);
1597  Assert(part_scheme);
1598 
1599  memset(pk_has_clause, 0, sizeof(pk_has_clause));
1600  foreach(lc, restrictlist)
1601  {
1602  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1603  OpExpr *opexpr;
1604  Expr *expr1;
1605  Expr *expr2;
1606  int ipk1;
1607  int ipk2;
1608 
1609  /* If processing an outer join, only use its own join clauses. */
1610  if (IS_OUTER_JOIN(jointype) &&
1611  RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
1612  continue;
1613 
1614  /* Skip clauses which can not be used for a join. */
1615  if (!rinfo->can_join)
1616  continue;
1617 
1618  /* Skip clauses which are not equality conditions. */
1619  if (!rinfo->mergeopfamilies && !OidIsValid(rinfo->hashjoinoperator))
1620  continue;
1621 
1622  opexpr = castNode(OpExpr, rinfo->clause);
1623 
1624  /*
1625  * The equi-join between partition keys is strict if equi-join between
1626  * at least one partition key is using a strict operator. See
1627  * explanation about outer join reordering identity 3 in
1628  * optimizer/README
1629  */
1630  strict_op = op_strict(opexpr->opno);
1631 
1632  /* Match the operands to the relation. */
1633  if (bms_is_subset(rinfo->left_relids, rel1->relids) &&
1634  bms_is_subset(rinfo->right_relids, rel2->relids))
1635  {
1636  expr1 = linitial(opexpr->args);
1637  expr2 = lsecond(opexpr->args);
1638  }
1639  else if (bms_is_subset(rinfo->left_relids, rel2->relids) &&
1640  bms_is_subset(rinfo->right_relids, rel1->relids))
1641  {
1642  expr1 = lsecond(opexpr->args);
1643  expr2 = linitial(opexpr->args);
1644  }
1645  else
1646  continue;
1647 
1648  /*
1649  * Only clauses referencing the partition keys are useful for
1650  * partitionwise join.
1651  */
1652  ipk1 = match_expr_to_partition_keys(expr1, rel1, strict_op);
1653  if (ipk1 < 0)
1654  continue;
1655  ipk2 = match_expr_to_partition_keys(expr2, rel2, strict_op);
1656  if (ipk2 < 0)
1657  continue;
1658 
1659  /*
1660  * If the clause refers to keys at different ordinal positions, it can
1661  * not be used for partitionwise join.
1662  */
1663  if (ipk1 != ipk2)
1664  continue;
1665 
1666  /*
1667  * The clause allows partitionwise join if only it uses the same
1668  * operator family as that specified by the partition key.
1669  */
1671  {
1672  if (!op_in_opfamily(rinfo->hashjoinoperator,
1673  part_scheme->partopfamily[ipk1]))
1674  continue;
1675  }
1676  else if (!list_member_oid(rinfo->mergeopfamilies,
1677  part_scheme->partopfamily[ipk1]))
1678  continue;
1679 
1680  /* Mark the partition key as having an equi-join clause. */
1681  pk_has_clause[ipk1] = true;
1682  }
1683 
1684  /* Check whether every partition key has an equi-join condition. */
1685  for (cnt_pks = 0; cnt_pks < part_scheme->partnatts; cnt_pks++)
1686  {
1687  if (!pk_has_clause[cnt_pks])
1688  return false;
1689  }
1690 
1691  return true;
1692 }
bool op_in_opfamily(Oid opno, Oid opfamily)
Definition: lsyscache.c:63
bool op_strict(Oid opno)
Definition: lsyscache.c:1279
#define castNode(_type_, nodeptr)
Definition: nodes.h:594
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:741
#define PARTITION_MAX_KEYS
Relids left_relids
Definition: pathnodes.h:1972
#define OidIsValid(objectId)
Definition: c.h:645
List * mergeopfamilies
Definition: pathnodes.h:1990
#define lsecond(l)
Definition: pg_list.h:200
#define linitial(l)
Definition: pg_list.h:195
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
#define lfirst_node(type, lc)
Definition: pg_list.h:193
static int match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, bool strict_op)
Definition: joinrels.c:1699
Relids relids
Definition: pathnodes.h:643
Expr * clause
Definition: pathnodes.h:1945
#define PARTITION_STRATEGY_HASH
Definition: parsenodes.h:798
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2022
Relids right_relids
Definition: pathnodes.h:1973
bool list_member_oid(const List *list, Oid datum)
Definition: list.c:675
#define Assert(condition)
Definition: c.h:739
Oid hashjoinoperator
Definition: pathnodes.h:2003
PartitionScheme part_scheme
Definition: pathnodes.h:720
Oid opno
Definition: primnodes.h:502
List * args
Definition: primnodes.h:508

◆ have_relevant_eclass_joinclause()

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

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

2629 {
2630  Bitmapset *matching_ecs;
2631  int i;
2632 
2633  /* Examine only eclasses mentioning both rel1 and rel2 */
2634  matching_ecs = get_common_eclass_indexes(root, rel1->relids,
2635  rel2->relids);
2636 
2637  i = -1;
2638  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2639  {
2641  i);
2642 
2643  /*
2644  * Sanity check that get_common_eclass_indexes gave only ECs
2645  * containing both rels.
2646  */
2647  Assert(bms_overlap(rel1->relids, ec->ec_relids));
2648  Assert(bms_overlap(rel2->relids, ec->ec_relids));
2649 
2650  /*
2651  * Won't generate joinclauses if single-member (this test covers the
2652  * volatile case too)
2653  */
2654  if (list_length(ec->ec_members) <= 1)
2655  continue;
2656 
2657  /*
2658  * We do not need to examine the individual members of the EC, because
2659  * all that we care about is whether each rel overlaps the relids of
2660  * at least one member, and get_common_eclass_indexes() and the single
2661  * member check above are sufficient to prove that. (As with
2662  * have_relevant_joinclause(), it is not necessary that the EC be able
2663  * to form a joinclause relating exactly the two given rels, only that
2664  * it be able to form a joinclause mentioning both, and this will
2665  * surely be true if both of them overlap ec_relids.)
2666  *
2667  * Note we don't test ec_broken; if we did, we'd need a separate code
2668  * path to look through ec_sources. Checking the membership anyway is
2669  * OK as a possibly-overoptimistic heuristic.
2670  *
2671  * We don't test ec_has_const either, even though a const eclass won't
2672  * generate real join clauses. This is because if we had "WHERE a.x =
2673  * b.y and a.x = 42", it is worth considering a join between a and b,
2674  * since the join result is likely to be small even though it'll end
2675  * up being an unqualified nestloop.
2676  */
2677 
2678  return true;
2679  }
2680 
2681  return false;
2682 }
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
static void * list_nth(const List *list, int n)
Definition: pg_list.h:277
Relids ec_relids
Definition: pathnodes.h:939
Relids relids
Definition: pathnodes.h:643
static Bitmapset * get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
Definition: equivclass.c:2883
#define Assert(condition)
Definition: c.h:739
List * eq_classes
Definition: pathnodes.h:266
static int list_length(const List *l)
Definition: pg_list.h:169
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
int i
List * ec_members
Definition: pathnodes.h:936

◆ indexcol_is_bool_constant_for_query()

bool indexcol_is_bool_constant_for_query ( IndexOptInfo index,
int  indexcol 
)

Definition at line 3757 of file indxpath.c.

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

Referenced by build_index_pathkeys().

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

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

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

1126 {
1127  Expr *clause = restrictinfo->clause;
1128  Oid lefttype,
1129  righttype;
1130 
1131  /* Should be a mergeclause ... */
1132  Assert(restrictinfo->mergeopfamilies != NIL);
1133  /* ... with links not yet set */
1134  Assert(restrictinfo->left_ec == NULL);
1135  Assert(restrictinfo->right_ec == NULL);
1136 
1137  /* Need the declared input types of the operator */
1138  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1139 
1140  /* Find or create a matching EquivalenceClass for each side */
1141  restrictinfo->left_ec =
1143  (Expr *) get_leftop(clause),
1144  restrictinfo->nullable_relids,
1145  restrictinfo->mergeopfamilies,
1146  lefttype,
1147  ((OpExpr *) clause)->inputcollid,
1148  0,
1149  NULL,
1150  true);
1151  restrictinfo->right_ec =
1153  (Expr *) get_rightop(clause),
1154  restrictinfo->nullable_relids,
1155  restrictinfo->mergeopfamilies,
1156  righttype,
1157  ((OpExpr *) clause)->inputcollid,
1158  0,
1159  NULL,
1160  true);
1161 }
#define NIL
Definition: pg_list.h:65
EquivalenceClass * get_eclass_for_sort_expr(PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
Definition: equivclass.c:625
EquivalenceClass * right_ec
Definition: pathnodes.h:1994
unsigned int Oid
Definition: postgres_ext.h:31
List * mergeopfamilies
Definition: pathnodes.h:1990
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1165
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:70
Expr * clause
Definition: pathnodes.h:1945
Relids nullable_relids
Definition: pathnodes.h:1969
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:82
#define Assert(condition)
Definition: c.h:739
EquivalenceClass * left_ec
Definition: pathnodes.h:1993

◆ is_redundant_derived_clause()

bool is_redundant_derived_clause ( RestrictInfo rinfo,
List clauselist 
)

Definition at line 2796 of file equivclass.c.

References lfirst, and RestrictInfo::parent_ec.

Referenced by create_tidscan_plan().

2797 {
2798  EquivalenceClass *parent_ec = rinfo->parent_ec;
2799  ListCell *lc;
2800 
2801  /* Fail if it's not a potentially-redundant clause from some EC */
2802  if (parent_ec == NULL)
2803  return false;
2804 
2805  foreach(lc, clauselist)
2806  {
2807  RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
2808 
2809  if (otherrinfo->parent_ec == parent_ec)
2810  return true;
2811  }
2812 
2813  return false;
2814 }
EquivalenceClass * parent_ec
Definition: pathnodes.h:1979
#define lfirst(lc)
Definition: pg_list.h:190

◆ is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses ( RestrictInfo rinfo,
List indexclauses 
)

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

2824 {
2825  EquivalenceClass *parent_ec = rinfo->parent_ec;
2826  ListCell *lc;
2827 
2828  foreach(lc, indexclauses)
2829  {
2830  IndexClause *iclause = lfirst_node(IndexClause, lc);
2831  RestrictInfo *otherrinfo = iclause->rinfo;
2832 
2833  /* If indexclause is lossy, it won't enforce the condition exactly */
2834  if (iclause->lossy)
2835  continue;
2836 
2837  /* Match if it's same clause (pointer equality should be enough) */
2838  if (rinfo == otherrinfo)
2839  return true;
2840  /* Match if derived from same EC */
2841  if (parent_ec && otherrinfo->parent_ec == parent_ec)
2842  return true;
2843 
2844  /*
2845  * No need to look at the derived clauses in iclause->indexquals; they
2846  * couldn't match if the parent clause didn't.
2847  */
2848  }
2849 
2850  return false;
2851 }
EquivalenceClass * parent_ec
Definition: pathnodes.h:1979
#define lfirst_node(type, lc)
Definition: pg_list.h:193
struct RestrictInfo * rinfo
Definition: pathnodes.h:1225

◆ join_search_one_level()

void join_search_one_level ( PlannerInfo root,
int  level 
)

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

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

◆ make_inner_pathkeys_for_merge()

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

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

1496 {
1497  List *pathkeys = NIL;
1498  EquivalenceClass *lastoeclass;
1499  PathKey *opathkey;
1500  ListCell *lc;
1501  ListCell *lop;
1502 
1503  lastoeclass = NULL;
1504  opathkey = NULL;
1505  lop = list_head(outer_pathkeys);
1506 
1507  foreach(lc, mergeclauses)
1508  {
1509  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1510  EquivalenceClass *oeclass;
1511  EquivalenceClass *ieclass;
1512  PathKey *pathkey;
1513 
1514  update_mergeclause_eclasses(root, rinfo);
1515 
1516  if (rinfo->outer_is_left)
1517  {
1518  oeclass = rinfo->left_ec;
1519  ieclass = rinfo->right_ec;
1520  }
1521  else
1522  {
1523  oeclass = rinfo->right_ec;
1524  ieclass = rinfo->left_ec;
1525  }
1526 
1527  /* outer eclass should match current or next pathkeys */
1528  /* we check this carefully for debugging reasons */
1529  if (oeclass != lastoeclass)
1530  {
1531  if (!lop)
1532  elog(ERROR, "too few pathkeys for mergeclauses");
1533  opathkey = (PathKey *) lfirst(lop);
1534  lop = lnext(outer_pathkeys, lop);
1535  lastoeclass = opathkey->pk_eclass;
1536  if (oeclass != lastoeclass)
1537  elog(ERROR, "outer pathkeys do not match mergeclause");
1538  }
1539 
1540  /*
1541  * Often, we'll have same EC on both sides, in which case the outer
1542  * pathkey is also canonical for the inner side, and we can skip a
1543  * useless search.
1544  */
1545  if (ieclass == oeclass)
1546  pathkey = opathkey;
1547  else
1548  pathkey = make_canonical_pathkey(root,
1549  ieclass,
1550  opathkey->pk_opfamily,
1551  opathkey->pk_strategy,
1552  opathkey->pk_nulls_first);
1553 
1554  /*
1555  * Don't generate redundant pathkeys (which can happen if multiple
1556  * mergeclauses refer to the same EC). Because we do this, the output
1557  * pathkey list isn't necessarily ordered like the mergeclauses, which
1558  * complicates life for create_mergejoin_plan(). But if we didn't,
1559  * we'd have a noncanonical sort key list, which would be bad; for one
1560  * reason, it certainly wouldn't match any available sort order for
1561  * the input relation.
1562  */
1563  if (!pathkey_is_redundant(pathkey, pathkeys))
1564  pathkeys = lappend(pathkeys, pathkey);
1565  }
1566 
1567  return pathkeys;
1568 }
#define NIL
Definition: pg_list.h:65
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:321
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:54
EquivalenceClass * right_ec
Definition: pathnodes.h:1994
int pk_strategy
Definition: pathnodes.h:1015
bool pk_nulls_first
Definition: pathnodes.h:1016
#define ERROR
Definition: elog.h:43
bool outer_is_left
Definition: pathnodes.h:2000
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:322
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1013
Oid pk_opfamily
Definition: pathnodes.h:1014
EquivalenceClass * left_ec
Definition: pathnodes.h:1993
#define elog(elevel,...)
Definition: elog.h:228
Definition: pg_list.h:50
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1174

◆ make_join_rel()

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

Definition at line 682 of file joinrels.c.

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

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

683 {
684  Relids joinrelids;
685  SpecialJoinInfo *sjinfo;
686  bool reversed;
687  SpecialJoinInfo sjinfo_data;
688  RelOptInfo *joinrel;
689  List *restrictlist;
690 
691  /* We should never try to join two overlapping sets of rels. */
692  Assert(!bms_overlap(rel1->relids, rel2->relids));
693 
694  /* Construct Relids set that identifies the joinrel. */
695  joinrelids = bms_union(rel1->relids, rel2->relids);
696 
697  /* Check validity and determine join type. */
698  if (!join_is_legal(root, rel1, rel2, joinrelids,
699  &sjinfo, &reversed))
700  {
701  /* invalid join path */
702  bms_free(joinrelids);
703  return NULL;
704  }
705 
706  /* Swap rels if needed to match the join info. */
707  if (reversed)
708  {
709  RelOptInfo *trel = rel1;
710 
711  rel1 = rel2;
712  rel2 = trel;