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

Go to the source code of this file.

Typedefs

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

Enumerations

enum  PathKeysComparison { PATHKEYS_EQUAL, PATHKEYS_BETTER1, PATHKEYS_BETTER2, PATHKEYS_DIFFERENT }
 

Functions

RelOptInfomake_one_rel (PlannerInfo *root, List *joinlist)
 
RelOptInfostandard_join_search (PlannerInfo *root, int levels_needed, List *initial_rels)
 
void generate_gather_paths (PlannerInfo *root, RelOptInfo *rel, bool override_rows)
 
void generate_useful_gather_paths (PlannerInfo *root, RelOptInfo *rel, bool override_rows)
 
int compute_parallel_worker (RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
 
void create_partial_bitmap_paths (PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
 
void generate_partitionwise_join_paths (PlannerInfo *root, RelOptInfo *rel)
 
void create_index_paths (PlannerInfo *root, RelOptInfo *rel)
 
bool relation_has_unique_index_for (PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist)
 
bool indexcol_is_bool_constant_for_query (PlannerInfo *root, IndexOptInfo *index, int indexcol)
 
bool match_index_to_operand (Node *operand, int indexcol, IndexOptInfo *index)
 
void check_index_predicates (PlannerInfo *root, RelOptInfo *rel)
 
void create_tidscan_paths (PlannerInfo *root, RelOptInfo *rel)
 
void add_paths_to_joinrel (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
 
void join_search_one_level (PlannerInfo *root, int level)
 
RelOptInfomake_join_rel (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
bool have_join_order_restriction (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
bool have_dangerous_phv (PlannerInfo *root, Relids outer_relids, Relids inner_params)
 
void mark_dummy_rel (RelOptInfo *rel)
 
bool process_equivalence (PlannerInfo *root, RestrictInfo **p_restrictinfo, bool below_outer_join)
 
Exprcanonicalize_ec_expression (Expr *expr, Oid req_type, Oid req_collation)
 
void reconsider_outer_join_clauses (PlannerInfo *root)
 
EquivalenceClassget_eclass_for_sort_expr (PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
 
EquivalenceMemberfind_ec_member_matching_expr (EquivalenceClass *ec, Expr *expr, Relids relids)
 
EquivalenceMemberfind_computable_ec_member (PlannerInfo *root, EquivalenceClass *ec, List *exprs, Relids relids, bool require_parallel_safe)
 
Exprfind_em_expr_for_rel (EquivalenceClass *ec, RelOptInfo *rel)
 
bool relation_can_be_sorted_early (PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, bool require_parallel_safe)
 
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)
 
RestrictInfofind_derived_clause_for_ec_member (EquivalenceClass *ec, EquivalenceMember *em)
 
void add_child_rel_equivalences (PlannerInfo *root, AppendRelInfo *appinfo, RelOptInfo *parent_rel, RelOptInfo *child_rel)
 
void add_child_join_rel_equivalences (PlannerInfo *root, int nappinfos, AppendRelInfo **appinfos, RelOptInfo *parent_rel, RelOptInfo *child_rel)
 
Listgenerate_implied_equalities_for_column (PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
 
bool have_relevant_eclass_joinclause (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
bool has_relevant_eclass_joinclause (PlannerInfo *root, RelOptInfo *rel1)
 
bool eclass_useful_for_merging (PlannerInfo *root, EquivalenceClass *eclass, RelOptInfo *rel)
 
bool is_redundant_derived_clause (RestrictInfo *rinfo, List *clauselist)
 
bool is_redundant_with_indexclauses (RestrictInfo *rinfo, List *indexclauses)
 
PathKeysComparison compare_pathkeys (List *keys1, List *keys2)
 
bool pathkeys_contained_in (List *keys1, List *keys2)
 
bool pathkeys_count_contained_in (List *keys1, List *keys2, int *n_common)
 
Pathget_cheapest_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
 
Pathget_cheapest_fractional_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, double fraction)
 
Pathget_cheapest_parallel_safe_total_inner (List *paths)
 
Listbuild_index_pathkeys (PlannerInfo *root, IndexOptInfo *index, ScanDirection scandir)
 
Listbuild_partition_pathkeys (PlannerInfo *root, RelOptInfo *partrel, ScanDirection scandir, bool *partialkeys)
 
Listbuild_expression_pathkey (PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opno, Relids rel, bool create_it)
 
Listconvert_subquery_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *subquery_pathkeys, List *subquery_tlist)
 
Listbuild_join_pathkeys (PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
 
Listmake_pathkeys_for_sortclauses (PlannerInfo *root, List *sortclauses, List *tlist)
 
void initialize_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
 
void update_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
 
Listfind_mergeclauses_for_outer_pathkeys (PlannerInfo *root, List *pathkeys, List *restrictinfos)
 
Listselect_outer_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
 
Listmake_inner_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
 
Listtrim_mergeclauses_for_inner_pathkeys (PlannerInfo *root, List *mergeclauses, List *pathkeys)
 
Listtruncate_useless_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 
bool has_useful_pathkeys (PlannerInfo *root, RelOptInfo *rel)
 
PathKeymake_canonical_pathkey (PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
 
void add_paths_to_append_rel (PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
 

Variables

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

Typedef Documentation

◆ ec_matches_callback_type

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

Definition at line 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 195 of file paths.h.

196 {
197  PATHKEYS_EQUAL, /* pathkeys are identical */
198  PATHKEYS_BETTER1, /* pathkey 1 is a superset of pathkey 2 */
199  PATHKEYS_BETTER2, /* vice versa */
200  PATHKEYS_DIFFERENT /* neither pathkey includes the other */
PathKeysComparison
Definition: paths.h:195

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 2696 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(), MemoryContextSwitchTo(), PlannerInfo::planner_cxt, RelOptInfo::relids, RELOPT_JOINREL, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, and RelOptInfo::top_parent_relids.

Referenced by build_child_join_rel().

2700 {
2701  Relids top_parent_relids = child_joinrel->top_parent_relids;
2702  Relids child_relids = child_joinrel->relids;
2703  Bitmapset *matching_ecs;
2704  MemoryContext oldcontext;
2705  int i;
2706 
2707  Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
2708 
2709  /* We need consider only ECs that mention the parent joinrel */
2710  matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids);
2711 
2712  /*
2713  * If we're being called during GEQO join planning, we still have to
2714  * create any new EC members in the main planner context, to avoid having
2715  * a corrupt EC data structure after the GEQO context is reset. This is
2716  * problematic since we'll leak memory across repeated GEQO cycles. For
2717  * now, though, bloat is better than crash. If it becomes a real issue
2718  * we'll have to do something to avoid generating duplicate EC members.
2719  */
2720  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
2721 
2722  i = -1;
2723  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2724  {
2725  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2726  int num_members;
2727 
2728  /*
2729  * If this EC contains a volatile expression, then generating child
2730  * EMs would be downright dangerous, so skip it. We rely on a
2731  * volatile EC having only one EM.
2732  */
2733  if (cur_ec->ec_has_volatile)
2734  continue;
2735 
2736  /* Sanity check on get_eclass_indexes_for_relids result */
2737  Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
2738 
2739  /*
2740  * We don't use foreach() here because there's no point in scanning
2741  * newly-added child members, so we can stop after the last
2742  * pre-existing EC member.
2743  */
2744  num_members = list_length(cur_ec->ec_members);
2745  for (int pos = 0; pos < num_members; pos++)
2746  {
2747  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2748 
2749  if (cur_em->em_is_const)
2750  continue; /* ignore consts here */
2751 
2752  /*
2753  * We consider only original EC members here, not
2754  * already-transformed child members.
2755  */
2756  if (cur_em->em_is_child)
2757  continue; /* ignore children here */
2758 
2759  /*
2760  * We may ignore expressions that reference a single baserel,
2761  * because add_child_rel_equivalences should have handled them.
2762  */
2763  if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
2764  continue;
2765 
2766  /* Does this member reference child's topmost parent rel? */
2767  if (bms_overlap(cur_em->em_relids, top_parent_relids))
2768  {
2769  /* Yes, generate transformed child version */
2770  Expr *child_expr;
2771  Relids new_relids;
2772  Relids new_nullable_relids;
2773 
2774  if (parent_joinrel->reloptkind == RELOPT_JOINREL)
2775  {
2776  /* Simple single-level transformation */
2777  child_expr = (Expr *)
2779  (Node *) cur_em->em_expr,
2780  nappinfos, appinfos);
2781  }
2782  else
2783  {
2784  /* Must do multi-level transformation */
2785  Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
2786  child_expr = (Expr *)
2788  (Node *) cur_em->em_expr,
2789  child_relids,
2790  top_parent_relids);
2791  }
2792 
2793  /*
2794  * Transform em_relids to match. Note we do *not* do
2795  * pull_varnos(child_expr) here, as for example the
2796  * transformation might have substituted a constant, but we
2797  * don't want the child member to be marked as constant.
2798  */
2799  new_relids = bms_difference(cur_em->em_relids,
2800  top_parent_relids);
2801  new_relids = bms_add_members(new_relids, child_relids);
2802 
2803  /*
2804  * For nullable_relids, we must selectively replace parent
2805  * nullable relids with child ones.
2806  */
2807  new_nullable_relids = cur_em->em_nullable_relids;
2808  if (bms_overlap(new_nullable_relids, top_parent_relids))
2809  new_nullable_relids =
2811  new_nullable_relids,
2812  child_relids,
2813  top_parent_relids);
2814 
2815  (void) add_eq_member(cur_ec, child_expr,
2816  new_relids, new_nullable_relids,
2817  true, cur_em->em_datatype);
2818  }
2819  }
2820  }
2821 
2822  MemoryContextSwitchTo(oldcontext);
2823 }
Relids em_nullable_relids
Definition: pathnodes.h:1031
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
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Definition: nodes.h:539
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:654
Relids adjust_child_relids_multilevel(PlannerInfo *root, Relids relids, Relids child_relids, Relids top_parent_relids)
Definition: appendinfo.c:562
Node * adjust_appendrel_attrs_multilevel(PlannerInfo *root, Node *node, Relids child_relids, Relids top_parent_relids)
Definition: appendinfo.c:488
static void * list_nth(const List *list, int n)
Definition: pg_list.h:278
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:3212
Relids ec_relids
Definition: pathnodes.h:984
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:672
#define Assert(condition)
Definition: c.h:804
List * eq_classes
Definition: pathnodes.h:248
static int list_length(const List *l)
Definition: pg_list.h:149
bool ec_has_volatile
Definition: pathnodes.h:987
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:545
MemoryContext planner_cxt
Definition: pathnodes.h:334
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:793
List * ec_members
Definition: pathnodes.h:981
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, int nappinfos, AppendRelInfo **appinfos)
Definition: appendinfo.c:195

◆ add_child_rel_equivalences()

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

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

2572 {
2573  Relids top_parent_relids = child_rel->top_parent_relids;
2574  Relids child_relids = child_rel->relids;
2575  int i;
2576 
2577  /*
2578  * EC merging should be complete already, so we can use the parent rel's
2579  * eclass_indexes to avoid searching all of root->eq_classes.
2580  */
2581  Assert(root->ec_merging_done);
2582  Assert(IS_SIMPLE_REL(parent_rel));
2583 
2584  i = -1;
2585  while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
2586  {
2587  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2588  int num_members;
2589 
2590  /*
2591  * If this EC contains a volatile expression, then generating child
2592  * EMs would be downright dangerous, so skip it. We rely on a
2593  * volatile EC having only one EM.
2594  */
2595  if (cur_ec->ec_has_volatile)
2596  continue;
2597 
2598  /* Sanity check eclass_indexes only contain ECs for parent_rel */
2599  Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
2600 
2601  /*
2602  * We don't use foreach() here because there's no point in scanning
2603  * newly-added child members, so we can stop after the last
2604  * pre-existing EC member.
2605  */
2606  num_members = list_length(cur_ec->ec_members);
2607  for (int pos = 0; pos < num_members; pos++)
2608  {
2609  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2610 
2611  if (cur_em->em_is_const)
2612  continue; /* ignore consts here */
2613 
2614  /*
2615  * We consider only original EC members here, not
2616  * already-transformed child members. Otherwise, if some original
2617  * member expression references more than one appendrel, we'd get
2618  * an O(N^2) explosion of useless derived expressions for
2619  * combinations of children. (But add_child_join_rel_equivalences
2620  * may add targeted combinations for partitionwise-join purposes.)
2621  */
2622  if (cur_em->em_is_child)
2623  continue; /* ignore children here */
2624 
2625  /* Does this member reference child's topmost parent rel? */
2626  if (bms_overlap(cur_em->em_relids, top_parent_relids))
2627  {
2628  /* Yes, generate transformed child version */
2629  Expr *child_expr;
2630  Relids new_relids;
2631  Relids new_nullable_relids;
2632 
2633  if (parent_rel->reloptkind == RELOPT_BASEREL)
2634  {
2635  /* Simple single-level transformation */
2636  child_expr = (Expr *)
2638  (Node *) cur_em->em_expr,
2639  1, &appinfo);
2640  }
2641  else
2642  {
2643  /* Must do multi-level transformation */
2644  child_expr = (Expr *)
2646  (Node *) cur_em->em_expr,
2647  child_relids,
2648  top_parent_relids);
2649  }
2650 
2651  /*
2652  * Transform em_relids to match. Note we do *not* do
2653  * pull_varnos(child_expr) here, as for example the
2654  * transformation might have substituted a constant, but we
2655  * don't want the child member to be marked as constant.
2656  */
2657  new_relids = bms_difference(cur_em->em_relids,
2658  top_parent_relids);
2659  new_relids = bms_add_members(new_relids, child_relids);
2660 
2661  /*
2662  * And likewise for nullable_relids. Note this code assumes
2663  * parent and child relids are singletons.
2664  */
2665  new_nullable_relids = cur_em->em_nullable_relids;
2666  if (bms_overlap(new_nullable_relids, top_parent_relids))
2667  {
2668  new_nullable_relids = bms_difference(new_nullable_relids,
2669  top_parent_relids);
2670  new_nullable_relids = bms_add_members(new_nullable_relids,
2671  child_relids);
2672  }
2673 
2674  (void) add_eq_member(cur_ec, child_expr,
2675  new_relids, new_nullable_relids,
2676  true, cur_em->em_datatype);
2677 
2678  /* Record this EC index for the child rel */
2679  child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
2680  }
2681  }
2682  }
2683 }
RelOptKind reloptkind
Definition: pathnodes.h:673
bool ec_merging_done
Definition: pathnodes.h:250
Relids em_nullable_relids
Definition: pathnodes.h:1031
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:539
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:649
Node * adjust_appendrel_attrs_multilevel(PlannerInfo *root, Node *node, Relids child_relids, Relids top_parent_relids)
Definition: appendinfo.c:488
static void * list_nth(const List *list, int n)
Definition: pg_list.h:278
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
Relids ec_relids
Definition: pathnodes.h:984
Relids relids
Definition: pathnodes.h:676
#define Assert(condition)
Definition: c.h:804
List * eq_classes
Definition: pathnodes.h:248
static int list_length(const List *l)
Definition: pg_list.h:149
bool ec_has_volatile
Definition: pathnodes.h:987
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:545
Bitmapset * eclass_indexes
Definition: pathnodes.h:718
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:793
List * ec_members
Definition: pathnodes.h:981
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, int nappinfos, AppendRelInfo **appinfos)
Definition: appendinfo.c:195
Relids top_parent_relids
Definition: pathnodes.h:751

◆ add_paths_to_append_rel()

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

Definition at line 1285 of file allpaths.c.

References accumulate_append_subpath(), add_partial_path(), add_path(), Assert, bms_equal(), RelOptInfo::cheapest_total_path, compare_pathkeys(), RelOptInfo::consider_parallel, create_append_path(), enable_parallel_append, fls(), for_each_from, generate_orderedappend_paths(), get_cheapest_parallel_safe_total_inner(), get_cheapest_parameterized_child_path(), lappend(), lfirst, linitial, list_length(), list_make1, Max, max_parallel_workers_per_gather, Min, NIL, Path::parallel_workers, Path::param_info, RelOptInfo::partial_pathlist, AppendPath::path, PATH_REQ_OUTER, Path::pathkeys, PATHKEYS_EQUAL, RelOptInfo::pathlist, Path::rows, 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().

1287 {
1288  List *subpaths = NIL;
1289  bool subpaths_valid = true;
1290  List *partial_subpaths = NIL;
1291  List *pa_partial_subpaths = NIL;
1292  List *pa_nonpartial_subpaths = NIL;
1293  bool partial_subpaths_valid = true;
1294  bool pa_subpaths_valid;
1295  List *all_child_pathkeys = NIL;
1296  List *all_child_outers = NIL;
1297  ListCell *l;
1298  double partial_rows = -1;
1299 
1300  /* If appropriate, consider parallel append */
1301  pa_subpaths_valid = enable_parallel_append && rel->consider_parallel;
1302 
1303  /*
1304  * For every non-dummy child, remember the cheapest path. Also, identify
1305  * all pathkeys (orderings) and parameterizations (required_outer sets)
1306  * available for the non-dummy member relations.
1307  */
1308  foreach(l, live_childrels)
1309  {
1310  RelOptInfo *childrel = lfirst(l);
1311  ListCell *lcp;
1312  Path *cheapest_partial_path = NULL;
1313 
1314  /*
1315  * If child has an unparameterized cheapest-total path, add that to
1316  * the unparameterized Append path we are constructing for the parent.
1317  * If not, there's no workable unparameterized path.
1318  *
1319  * With partitionwise aggregates, the child rel's pathlist may be
1320  * empty, so don't assume that a path exists here.
1321  */
1322  if (childrel->pathlist != NIL &&
1323  childrel->cheapest_total_path->param_info == NULL)
1325  &subpaths, NULL);
1326  else
1327  subpaths_valid = false;
1328 
1329  /* Same idea, but for a partial plan. */
1330  if (childrel->partial_pathlist != NIL)
1331  {
1332  cheapest_partial_path = linitial(childrel->partial_pathlist);
1333  accumulate_append_subpath(cheapest_partial_path,
1334  &partial_subpaths, NULL);
1335  }
1336  else
1337  partial_subpaths_valid = false;
1338 
1339  /*
1340  * Same idea, but for a parallel append mixing partial and non-partial
1341  * paths.
1342  */
1343  if (pa_subpaths_valid)
1344  {
1345  Path *nppath = NULL;
1346 
1347  nppath =
1349 
1350  if (cheapest_partial_path == NULL && nppath == NULL)
1351  {
1352  /* Neither a partial nor a parallel-safe path? Forget it. */
1353  pa_subpaths_valid = false;
1354  }
1355  else if (nppath == NULL ||
1356  (cheapest_partial_path != NULL &&
1357  cheapest_partial_path->total_cost < nppath->total_cost))
1358  {
1359  /* Partial path is cheaper or the only option. */
1360  Assert(cheapest_partial_path != NULL);
1361  accumulate_append_subpath(cheapest_partial_path,
1362  &pa_partial_subpaths,
1363  &pa_nonpartial_subpaths);
1364  }
1365  else
1366  {
1367  /*
1368  * Either we've got only a non-partial path, or we think that
1369  * a single backend can execute the best non-partial path
1370  * faster than all the parallel backends working together can
1371  * execute the best partial path.
1372  *
1373  * It might make sense to be more aggressive here. Even if
1374  * the best non-partial path is more expensive than the best
1375  * partial path, it could still be better to choose the
1376  * non-partial path if there are several such paths that can
1377  * be given to different workers. For now, we don't try to
1378  * figure that out.
1379  */
1381  &pa_nonpartial_subpaths,
1382  NULL);
1383  }
1384  }
1385 
1386  /*
1387  * Collect lists of all the available path orderings and
1388  * parameterizations for all the children. We use these as a
1389  * heuristic to indicate which sort orderings and parameterizations we
1390  * should build Append and MergeAppend paths for.
1391  */
1392  foreach(lcp, childrel->pathlist)
1393  {
1394  Path *childpath = (Path *) lfirst(lcp);
1395  List *childkeys = childpath->pathkeys;
1396  Relids childouter = PATH_REQ_OUTER(childpath);
1397 
1398  /* Unsorted paths don't contribute to pathkey list */
1399  if (childkeys != NIL)
1400  {
1401  ListCell *lpk;
1402  bool found = false;
1403 
1404  /* Have we already seen this ordering? */
1405  foreach(lpk, all_child_pathkeys)
1406  {
1407  List *existing_pathkeys = (List *) lfirst(lpk);
1408 
1409  if (compare_pathkeys(existing_pathkeys,
1410  childkeys) == PATHKEYS_EQUAL)
1411  {
1412  found = true;
1413  break;
1414  }
1415  }
1416  if (!found)
1417  {
1418  /* No, so add it to all_child_pathkeys */
1419  all_child_pathkeys = lappend(all_child_pathkeys,
1420  childkeys);
1421  }
1422  }
1423 
1424  /* Unparameterized paths don't contribute to param-set list */
1425  if (childouter)
1426  {
1427  ListCell *lco;
1428  bool found = false;
1429 
1430  /* Have we already seen this param set? */
1431  foreach(lco, all_child_outers)
1432  {
1433  Relids existing_outers = (Relids) lfirst(lco);
1434 
1435  if (bms_equal(existing_outers, childouter))
1436  {
1437  found = true;
1438  break;
1439  }
1440  }
1441  if (!found)
1442  {
1443  /* No, so add it to all_child_outers */
1444  all_child_outers = lappend(all_child_outers,
1445  childouter);
1446  }
1447  }
1448  }
1449  }
1450 
1451  /*
1452  * If we found unparameterized paths for all children, build an unordered,
1453  * unparameterized Append path for the rel. (Note: this is correct even
1454  * if we have zero or one live subpath due to constraint exclusion.)
1455  */
1456  if (subpaths_valid)
1457  add_path(rel, (Path *) create_append_path(root, rel, subpaths, NIL,
1458  NIL, NULL, 0, false,
1459  -1));
1460 
1461  /*
1462  * Consider an append of unordered, unparameterized partial paths. Make
1463  * it parallel-aware if possible.
1464  */
1465  if (partial_subpaths_valid && partial_subpaths != NIL)
1466  {
1467  AppendPath *appendpath;
1468  ListCell *lc;
1469  int parallel_workers = 0;
1470 
1471  /* Find the highest number of workers requested for any subpath. */
1472  foreach(lc, partial_subpaths)
1473  {
1474  Path *path = lfirst(lc);
1475 
1476  parallel_workers = Max(parallel_workers, path->parallel_workers);
1477  }
1478  Assert(parallel_workers > 0);
1479 
1480  /*
1481  * If the use of parallel append is permitted, always request at least
1482  * log2(# of children) workers. We assume it can be useful to have
1483  * extra workers in this case because they will be spread out across
1484  * the children. The precise formula is just a guess, but we don't
1485  * want to end up with a radically different answer for a table with N
1486  * partitions vs. an unpartitioned table with the same data, so the
1487  * use of some kind of log-scaling here seems to make some sense.
1488  */
1490  {
1491  parallel_workers = Max(parallel_workers,
1492  fls(list_length(live_childrels)));
1493  parallel_workers = Min(parallel_workers,
1495  }
1496  Assert(parallel_workers > 0);
1497 
1498  /* Generate a partial append path. */
1499  appendpath = create_append_path(root, rel, NIL, partial_subpaths,
1500  NIL, NULL, parallel_workers,
1502  -1);
1503 
1504  /*
1505  * Make sure any subsequent partial paths use the same row count
1506  * estimate.
1507  */
1508  partial_rows = appendpath->path.rows;
1509 
1510  /* Add the path. */
1511  add_partial_path(rel, (Path *) appendpath);
1512  }
1513 
1514  /*
1515  * Consider a parallel-aware append using a mix of partial and non-partial
1516  * paths. (This only makes sense if there's at least one child which has
1517  * a non-partial path that is substantially cheaper than any partial path;
1518  * otherwise, we should use the append path added in the previous step.)
1519  */
1520  if (pa_subpaths_valid && pa_nonpartial_subpaths != NIL)
1521  {
1522  AppendPath *appendpath;
1523  ListCell *lc;
1524  int parallel_workers = 0;
1525 
1526  /*
1527  * Find the highest number of workers requested for any partial
1528  * subpath.
1529  */
1530  foreach(lc, pa_partial_subpaths)
1531  {
1532  Path *path = lfirst(lc);
1533 
1534  parallel_workers = Max(parallel_workers, path->parallel_workers);
1535  }
1536 
1537  /*
1538  * Same formula here as above. It's even more important in this
1539  * instance because the non-partial paths won't contribute anything to
1540  * the planned number of parallel workers.
1541  */
1542  parallel_workers = Max(parallel_workers,
1543  fls(list_length(live_childrels)));
1544  parallel_workers = Min(parallel_workers,
1546  Assert(parallel_workers > 0);
1547 
1548  appendpath = create_append_path(root, rel, pa_nonpartial_subpaths,
1549  pa_partial_subpaths,
1550  NIL, NULL, parallel_workers, true,
1551  partial_rows);
1552  add_partial_path(rel, (Path *) appendpath);
1553  }
1554 
1555  /*
1556  * Also build unparameterized ordered append paths based on the collected
1557  * list of child pathkeys.
1558  */
1559  if (subpaths_valid)
1560  generate_orderedappend_paths(root, rel, live_childrels,
1561  all_child_pathkeys);
1562 
1563  /*
1564  * Build Append paths for each parameterization seen among the child rels.
1565  * (This may look pretty expensive, but in most cases of practical
1566  * interest, the child rels will expose mostly the same parameterizations,
1567  * so that not that many cases actually get considered here.)
1568  *
1569  * The Append node itself cannot enforce quals, so all qual checking must
1570  * be done in the child paths. This means that to have a parameterized
1571  * Append path, we must have the exact same parameterization for each
1572  * child path; otherwise some children might be failing to check the
1573  * moved-down quals. To make them match up, we can try to increase the
1574  * parameterization of lesser-parameterized paths.
1575  */
1576  foreach(l, all_child_outers)
1577  {
1578  Relids required_outer = (Relids) lfirst(l);
1579  ListCell *lcr;
1580 
1581  /* Select the child paths for an Append with this parameterization */
1582  subpaths = NIL;
1583  subpaths_valid = true;
1584  foreach(lcr, live_childrels)
1585  {
1586  RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
1587  Path *subpath;
1588 
1589  if (childrel->pathlist == NIL)
1590  {
1591  /* failed to make a suitable path for this child */
1592  subpaths_valid = false;
1593  break;
1594  }
1595 
1597  childrel,
1598  required_outer);
1599  if (subpath == NULL)
1600  {
1601  /* failed to make a suitable path for this child */
1602  subpaths_valid = false;
1603  break;
1604  }
1605  accumulate_append_subpath(subpath, &subpaths, NULL);
1606  }
1607 
1608  if (subpaths_valid)
1609  add_path(rel, (Path *)
1610  create_append_path(root, rel, subpaths, NIL,
1611  NIL, required_outer, 0, false,
1612  -1));
1613  }
1614 
1615  /*
1616  * When there is only a single child relation, the Append path can inherit
1617  * any ordering available for the child rel's path, so that it's useful to
1618  * consider ordered partial paths. Above we only considered the cheapest
1619  * partial path for each child, but let's also make paths using any
1620  * partial paths that have pathkeys.
1621  */
1622  if (list_length(live_childrels) == 1)
1623  {
1624  RelOptInfo *childrel = (RelOptInfo *) linitial(live_childrels);
1625 
1626  /* skip the cheapest partial path, since we already used that above */
1627  for_each_from(l, childrel->partial_pathlist, 1)
1628  {
1629  Path *path = (Path *) lfirst(l);
1630  AppendPath *appendpath;
1631 
1632  /* skip paths with no pathkeys. */
1633  if (path->pathkeys == NIL)
1634  continue;
1635 
1636  appendpath = create_append_path(root, rel, NIL, list_make1(path),
1637  NIL, NULL,
1638  path->parallel_workers, true,
1639  partial_rows);
1640  add_partial_path(rel, (Path *) appendpath);
1641  }
1642  }
1643 }
#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:1879
#define Min(x, y)
Definition: c.h:986
int parallel_workers
Definition: pathnodes.h:1181
ParamPathInfo * param_info
Definition: pathnodes.h:1177
List * partial_pathlist
Definition: pathnodes.h:692
bool enable_parallel_append
Definition: costsize.c:149
PathKeysComparison compare_pathkeys(List *keys1, List *keys2)
Definition: pathkeys.c:285
int fls(int mask)
Definition: fls.c:55
#define list_make1(x1)
Definition: pg_list.h:206
#define linitial(l)
Definition: pg_list.h:174
struct Path * cheapest_total_path
Definition: pathnodes.h:694
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1193
AppendPath * create_append_path(PlannerInfo *root, RelOptInfo *rel, List *subpaths, List *partial_subpaths, List *pathkeys, Relids required_outer, int parallel_workers, bool parallel_aware, double rows)
Definition: pathnode.c:1244
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:482
List * lappend(List *list, void *datum)
Definition: list.c:336
Cost total_cost
Definition: pathnodes.h:1186
List * pathkeys
Definition: pathnodes.h:1188
#define Max(x, y)
Definition: c.h:980
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
double rows
Definition: pathnodes.h:1184
static int list_length(const List *l)
Definition: pg_list.h:149
#define for_each_from(cell, lst, N)
Definition: pg_list.h:393
bool consider_parallel
Definition: pathnodes.h:684
Bitmapset * Relids
Definition: pathnodes.h:28
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:749
List * pathlist
Definition: pathnodes.h:690
static void generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel, List *live_childrels, List *all_child_pathkeys)
Definition: allpaths.c:1673
static void accumulate_append_subpath(Path *path, List **subpaths, List **special_subpaths)
Definition: allpaths.c:1967
int max_parallel_workers_per_gather
Definition: costsize.c:131
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 123 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().

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

◆ build_expression_pathkey()

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

Definition at line 782 of file pathkeys.c.

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

Referenced by set_function_pathlist().

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

◆ build_index_pathkeys()

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

Definition at line 523 of file pathkeys.c.

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

Referenced by build_index_paths().

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

◆ build_join_pathkeys()

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

Definition at line 1082 of file pathkeys.c.

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

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

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

◆ build_partition_pathkeys()

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

Definition at line 699 of file pathkeys.c.

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

Referenced by generate_orderedappend_paths().

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

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

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

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

◆ check_index_predicates()

void check_index_predicates ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 3320 of file indxpath.c.

References PlannerInfo::all_baserels, PlannerInfo::all_result_relids, Assert, RelOptInfo::baserestrictinfo, bms_difference(), bms_is_empty(), bms_is_member(), 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, predicate_implied_by(), IndexOptInfo::predOK, RelOptInfo::relid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, and PlannerInfo::rowMarks.

Referenced by set_plain_rel_size(), and set_tablesample_rel_size().

3321 {
3322  List *clauselist;
3323  bool have_partial;
3324  bool is_target_rel;
3325  Relids otherrels;
3326  ListCell *lc;
3327 
3328  /* Indexes are available only on base or "other" member relations. */
3329  Assert(IS_SIMPLE_REL(rel));
3330 
3331  /*
3332  * Initialize the indrestrictinfo lists to be identical to
3333  * baserestrictinfo, and check whether there are any partial indexes. If
3334  * not, this is all we need to do.
3335  */
3336  have_partial = false;
3337  foreach(lc, rel->indexlist)
3338  {
3340 
3341  index->indrestrictinfo = rel->baserestrictinfo;
3342  if (index->indpred)
3343  have_partial = true;
3344  }
3345  if (!have_partial)
3346  return;
3347 
3348  /*
3349  * Construct a list of clauses that we can assume true for the purpose of
3350  * proving the index(es) usable. Restriction clauses for the rel are
3351  * always usable, and so are any join clauses that are "movable to" this
3352  * rel. Also, we can consider any EC-derivable join clauses (which must
3353  * be "movable to" this rel, by definition).
3354  */
3355  clauselist = list_copy(rel->baserestrictinfo);
3356 
3357  /* Scan the rel's join clauses */
3358  foreach(lc, rel->joininfo)
3359  {
3360  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3361 
3362  /* Check if clause can be moved to this rel */
3363  if (!join_clause_is_movable_to(rinfo, rel))
3364  continue;
3365 
3366  clauselist = lappend(clauselist, rinfo);
3367  }
3368 
3369  /*
3370  * Add on any equivalence-derivable join clauses. Computing the correct
3371  * relid sets for generate_join_implied_equalities is slightly tricky
3372  * because the rel could be a child rel rather than a true baserel, and in
3373  * that case we must remove its parents' relid(s) from all_baserels.
3374  */
3375  if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
3376  otherrels = bms_difference(root->all_baserels,
3377  find_childrel_parents(root, rel));
3378  else
3379  otherrels = bms_difference(root->all_baserels, rel->relids);
3380 
3381  if (!bms_is_empty(otherrels))
3382  clauselist =
3383  list_concat(clauselist,
3385  bms_union(rel->relids,
3386  otherrels),
3387  otherrels,
3388  rel));
3389 
3390  /*
3391  * Normally we remove quals that are implied by a partial index's
3392  * predicate from indrestrictinfo, indicating that they need not be
3393  * checked explicitly by an indexscan plan using this index. However, if
3394  * the rel is a target relation of UPDATE/DELETE/SELECT FOR UPDATE, we
3395  * cannot remove such quals from the plan, because they need to be in the
3396  * plan so that they will be properly rechecked by EvalPlanQual testing.
3397  * Some day we might want to remove such quals from the main plan anyway
3398  * and pass them through to EvalPlanQual via a side channel; but for now,
3399  * we just don't remove implied quals at all for target relations.
3400  */
3401  is_target_rel = (bms_is_member(rel->relid, root->all_result_relids) ||
3402  get_plan_rowmark(root->rowMarks, rel->relid) != NULL);
3403 
3404  /*
3405  * Now try to prove each index predicate true, and compute the
3406  * indrestrictinfo lists for partial indexes. Note that we compute the
3407  * indrestrictinfo list even for non-predOK indexes; this might seem
3408  * wasteful, but we may be able to use such indexes in OR clauses, cf
3409  * generate_bitmap_or_paths().
3410  */
3411  foreach(lc, rel->indexlist)
3412  {
3413  IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
3414  ListCell *lcr;
3415 
3416  if (index->indpred == NIL)
3417  continue; /* ignore non-partial indexes here */
3418 
3419  if (!index->predOK) /* don't repeat work if already proven OK */
3420  index->predOK = predicate_implied_by(index->indpred, clauselist,
3421  false);
3422 
3423  /* If rel is an update target, leave indrestrictinfo as set above */
3424  if (is_target_rel)
3425  continue;
3426 
3427  /* Else compute indrestrictinfo as the non-implied quals */
3428  index->indrestrictinfo = NIL;
3429  foreach(lcr, rel->baserestrictinfo)
3430  {
3431  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
3432 
3433  /* predicate_implied_by() assumes first arg is immutable */
3434  if (contain_mutable_functions((Node *) rinfo->clause) ||
3436  index->indpred, false))
3437  index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
3438  }
3439  }
3440 }
#define NIL
Definition: pg_list.h:65
List * rowMarks
Definition: pathnodes.h:287
Relids all_result_relids
Definition: pathnodes.h:275
RelOptKind reloptkind
Definition: pathnodes.h:673
List * baserestrictinfo
Definition: pathnodes.h:740
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:291
List * list_copy(const List *oldlist)
Definition: list.c:1418
Definition: nodes.h:539
List * list_concat(List *list1, const List *list2)
Definition: list.c:530
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:649
Definition: type.h:89
#define list_make1(x1)
Definition: pg_list.h:206
Relids all_baserels
Definition: pathnodes.h:209
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1421
List * joininfo
Definition: pathnodes.h:744
Relids relids
Definition: pathnodes.h:676
Index relid
Definition: pathnodes.h:704
List * lappend(List *list, void *datum)
Definition: list.c:336
Expr * clause
Definition: pathnodes.h:2045
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
List * indrestrictinfo
Definition: pathnodes.h:860
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1258
List * indexlist
Definition: pathnodes.h:713
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:225
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:525
PlanRowMark * get_plan_rowmark(List *rowmarks, Index rtindex)
Definition: preptlist.c:425
bool contain_mutable_functions(Node *clause)
Definition: clauses.c:362
List * indpred
Definition: pathnodes.h:856
bool predicate_implied_by(List *predicate_list, List *clause_list, bool weak)
Definition: predtest.c:151
Definition: pg_list.h:50
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:427

◆ 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:446
#define lfirst(lc)
Definition: pg_list.h:169

◆ compute_parallel_worker()

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

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

3751 {
3752  int parallel_workers = 0;
3753 
3754  /*
3755  * If the user has set the parallel_workers reloption, use that; otherwise
3756  * select a default number of workers.
3757  */
3758  if (rel->rel_parallel_workers != -1)
3759  parallel_workers = rel->rel_parallel_workers;
3760  else
3761  {
3762  /*
3763  * If the number of pages being scanned is insufficient to justify a
3764  * parallel scan, just return zero ... unless it's an inheritance
3765  * child. In that case, we want to generate a parallel path here
3766  * anyway. It might not be worthwhile just for this relation, but
3767  * when combined with all of its inheritance siblings it may well pay
3768  * off.
3769  */
3770  if (rel->reloptkind == RELOPT_BASEREL &&
3771  ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
3772  (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
3773  return 0;
3774 
3775  if (heap_pages >= 0)
3776  {
3777  int heap_parallel_threshold;
3778  int heap_parallel_workers = 1;
3779 
3780  /*
3781  * Select the number of workers based on the log of the size of
3782  * the relation. This probably needs to be a good deal more
3783  * sophisticated, but we need something here for now. Note that
3784  * the upper limit of the min_parallel_table_scan_size GUC is
3785  * chosen to prevent overflow here.
3786  */
3787  heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
3788  while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
3789  {
3790  heap_parallel_workers++;
3791  heap_parallel_threshold *= 3;
3792  if (heap_parallel_threshold > INT_MAX / 3)
3793  break; /* avoid overflow */
3794  }
3795 
3796  parallel_workers = heap_parallel_workers;
3797  }
3798 
3799  if (index_pages >= 0)
3800  {
3801  int index_parallel_workers = 1;
3802  int index_parallel_threshold;
3803 
3804  /* same calculation as for heap_pages above */
3805  index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
3806  while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
3807  {
3808  index_parallel_workers++;
3809  index_parallel_threshold *= 3;
3810  if (index_parallel_threshold > INT_MAX / 3)
3811  break; /* avoid overflow */
3812  }
3813 
3814  if (parallel_workers > 0)
3815  parallel_workers = Min(parallel_workers, index_parallel_workers);
3816  else
3817  parallel_workers = index_parallel_workers;
3818  }
3819  }
3820 
3821  /* In no case use more than caller supplied maximum number of workers */
3822  parallel_workers = Min(parallel_workers, max_workers);
3823 
3824  return parallel_workers;
3825 }
RelOptKind reloptkind
Definition: pathnodes.h:673
#define Min(x, y)
Definition: c.h:986
uint32 BlockNumber
Definition: block.h:31
int min_parallel_index_scan_size
Definition: allpaths.c:65
int rel_parallel_workers
Definition: pathnodes.h:722
#define Max(x, y)
Definition: c.h:980
int min_parallel_table_scan_size
Definition: allpaths.c:64

◆ convert_subquery_pathkeys()

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

Definition at line 838 of file pathkeys.c.

References Assert, canonicalize_ec_expression(), EquivalenceClass::ec_collation, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_sortref, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, equal(), ERROR, TargetEntry::expr, find_var_for_subquery_tle(), get_eclass_for_sort_expr(), get_sortgroupref_tle(), i, lappend(), lfirst, linitial, list_length(), list_nth(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_eclass, PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, PlannerInfo::query_pathkeys, and RelOptInfo::relids.

Referenced by set_subquery_pathlist().

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

◆ create_index_paths()

void create_index_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 235 of file indxpath.c.

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

Referenced by set_plain_rel_pathlist().

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

◆ create_partial_bitmap_paths()

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

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

3715 {
3716  int parallel_workers;
3717  double pages_fetched;
3718 
3719  /* Compute heap pages for bitmap heap scan */
3720  pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
3721  NULL, NULL);
3722 
3723  parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
3725 
3726  if (parallel_workers <= 0)
3727  return;
3728 
3729  add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
3730  bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
3731 }
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:3749
Relids lateral_relids
Definition: pathnodes.h:701
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:749
int max_parallel_workers_per_gather
Definition: costsize.c:131
double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, int loop_count, Cost *cost, double *tuple)
Definition: costsize.c:6073
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 459 of file tidpath.c.

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

Referenced by set_plain_rel_pathlist().

460 {
461  List *tidquals;
462  List *tidrangequals;
463 
464  /*
465  * If any suitable quals exist in the rel's baserestrict list, generate a
466  * plain (unparameterized) TidPath with them.
467  */
468  tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel);
469 
470  if (tidquals != NIL)
471  {
472  /*
473  * This path uses no join clauses, but it could still have required
474  * parameterization due to LATERAL refs in its tlist.
475  */
476  Relids required_outer = rel->lateral_relids;
477 
478  add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
479  required_outer));
480  }
481 
482  /*
483  * If there are range quals in the baserestrict list, generate a
484  * TidRangePath.
485  */
487  rel);
488 
489  if (tidrangequals != NIL)
490  {
491  /*
492  * This path uses no join clauses, but it could still have required
493  * parameterization due to LATERAL refs in its tlist.
494  */
495  Relids required_outer = rel->lateral_relids;
496 
497  add_path(rel, (Path *) create_tidrangescan_path(root, rel,
498  tidrangequals,
499  required_outer));
500  }
501 
502  /*
503  * Try to generate parameterized TidPaths using equality clauses extracted
504  * from EquivalenceClasses. (This is important since simple "t1.ctid =
505  * t2.ctid" clauses will turn into ECs.)
506  */
507  if (rel->has_eclass_joins)
508  {
509  List *clauses;
510 
511  /* Generate clauses, skipping any that join to lateral_referencers */
513  rel,
515  NULL,
516  rel->lateral_referencers);
517 
518  /* Generate a path for each usable join clause */
519  BuildParameterizedTidPaths(root, rel, clauses);
520  }
521 
522  /*
523  * Also consider parameterized TidPaths using "loose" join quals. Quals
524  * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
525  * join quals, for example.
526  */
527  BuildParameterizedTidPaths(root, rel, rel->joininfo);
528 }
bool has_eclass_joins
Definition: pathnodes.h:746
#define NIL
Definition: pg_list.h:65
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
TidRangePath * create_tidrangescan_path(PlannerInfo *root, RelOptInfo *rel, List *tidrangequals, Relids required_outer)
Definition: pathnode.c:1212
List * baserestrictinfo
Definition: pathnodes.h:740
static List * TidRangeQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
Definition: tidpath.c:359
static bool ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)
Definition: tidpath.c:442
Relids lateral_relids
Definition: pathnodes.h:701
static void BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
Definition: tidpath.c:387
List * joininfo
Definition: pathnodes.h:744
Relids lateral_referencers
Definition: pathnodes.h:712
static List * TidQualFromRestrictInfoList(PlannerInfo *root, List *rlist, RelOptInfo *rel)
Definition: tidpath.c:276
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1183
Definition: pg_list.h:50
List * generate_implied_equalities_for_column(PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
Definition: equivclass.c:2850

◆ eclass_useful_for_merging()

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

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

3094 {
3095  Relids relids;
3096  ListCell *lc;
3097 
3098  Assert(!eclass->ec_merged);
3099 
3100  /*
3101  * Won't generate joinclauses if const or single-member (the latter test
3102  * covers the volatile case too)
3103  */
3104  if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
3105  return false;
3106 
3107  /*
3108  * Note we don't test ec_broken; if we did, we'd need a separate code path
3109  * to look through ec_sources. Checking the members anyway is OK as a
3110  * possibly-overoptimistic heuristic.
3111  */
3112 
3113  /* If specified rel is a child, we must consider the topmost parent rel */
3114  if (IS_OTHER_REL(rel))
3115  {
3117  relids = rel->top_parent_relids;
3118  }
3119  else
3120  relids = rel->relids;
3121 
3122  /* If rel already includes all members of eclass, no point in searching */
3123  if (bms_is_subset(eclass->ec_relids, relids))
3124  return false;
3125 
3126  /* To join, we need a member not in the given rel */
3127  foreach(lc, eclass->ec_members)
3128  {
3129  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
3130 
3131  if (cur_em->em_is_child)
3132  continue; /* ignore children here */
3133 
3134  if (!bms_overlap(cur_em->em_relids, relids))
3135  return true;
3136  }
3137 
3138  return false;
3139 }
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:664
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
Relids ec_relids
Definition: pathnodes.h:984
Relids relids
Definition: pathnodes.h:676
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
static int list_length(const List *l)
Definition: pg_list.h:149
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:993
List * ec_members
Definition: pathnodes.h:981
Relids top_parent_relids
Definition: pathnodes.h:751

◆ exprs_known_equal()

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

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

2387 {
2388  ListCell *lc1;
2389 
2390  foreach(lc1, root->eq_classes)
2391  {
2392  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2393  bool item1member = false;
2394  bool item2member = false;
2395  ListCell *lc2;
2396 
2397  /* Never match to a volatile EC */
2398  if (ec->ec_has_volatile)
2399  continue;
2400 
2401  foreach(lc2, ec->ec_members)
2402  {
2404 
2405  if (em->em_is_child)
2406  continue; /* ignore children here */
2407  if (equal(item1, em->em_expr))
2408  item1member = true;
2409  else if (equal(item2, em->em_expr))
2410  item2member = true;
2411  /* Exit as soon as equality is proven */
2412  if (item1member && item2member)
2413  return true;
2414  }
2415  }
2416  return false;
2417 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3122
#define lfirst(lc)
Definition: pg_list.h:169
List * eq_classes
Definition: pathnodes.h:248
bool ec_has_volatile
Definition: pathnodes.h:987
List * ec_members
Definition: pathnodes.h:981

◆ find_computable_ec_member()

EquivalenceMember* find_computable_ec_member ( PlannerInfo root,
EquivalenceClass ec,
List exprs,
Relids  relids,
bool  require_parallel_safe 
)

Definition at line 851 of file equivclass.c.

References bms_is_subset(), EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, is_exprlist_member(), is_parallel_safe(), lfirst, list_free(), pull_var_clause(), PVC_INCLUDE_AGGREGATES, PVC_INCLUDE_PLACEHOLDERS, and PVC_INCLUDE_WINDOWFUNCS.

Referenced by prepare_sort_from_pathkeys(), and relation_can_be_sorted_early().

856 {
857  ListCell *lc;
858 
859  foreach(lc, ec->ec_members)
860  {
862  List *exprvars;
863  ListCell *lc2;
864 
865  /*
866  * We shouldn't be trying to sort by an equivalence class that
867  * contains a constant, so no need to consider such cases any further.
868  */
869  if (em->em_is_const)
870  continue;
871 
872  /*
873  * Ignore child members unless they belong to the requested rel.
874  */
875  if (em->em_is_child &&
876  !bms_is_subset(em->em_relids, relids))
877  continue;
878 
879  /*
880  * Match if all Vars and quasi-Vars are available in "exprs".
881  */
882  exprvars = pull_var_clause((Node *) em->em_expr,
886  foreach(lc2, exprvars)
887  {
888  if (!is_exprlist_member(lfirst(lc2), exprs))
889  break;
890  }
891  list_free(exprvars);
892  if (lc2)
893  continue; /* we hit a non-available Var */
894 
895  /*
896  * If requested, reject expressions that are not parallel-safe. We
897  * check this last because it's a rather expensive test.
898  */
899  if (require_parallel_safe &&
900  !is_parallel_safe(root, (Node *) em->em_expr))
901  continue;
902 
903  return em; /* found usable expression */
904  }
905 
906  return NULL;
907 }
Definition: nodes.h:539
List * pull_var_clause(Node *node, int flags)
Definition: var.c:562
#define PVC_INCLUDE_AGGREGATES
Definition: optimizer.h:186
#define PVC_INCLUDE_WINDOWFUNCS
Definition: optimizer.h:188
bool is_parallel_safe(PlannerInfo *root, Node *node)
Definition: clauses.c:638
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
static bool is_exprlist_member(Expr *node, List *exprs)
Definition: equivclass.c:917
#define PVC_INCLUDE_PLACEHOLDERS
Definition: optimizer.h:190
#define lfirst(lc)
Definition: pg_list.h:169
void list_free(List *list)
Definition: list.c:1391
Definition: pg_list.h:50
List * ec_members
Definition: pathnodes.h:981

◆ find_derived_clause_for_ec_member()

RestrictInfo* find_derived_clause_for_ec_member ( EquivalenceClass ec,
EquivalenceMember em 
)

Definition at line 2528 of file equivclass.c.

References Assert, EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceMember::em_is_const, RestrictInfo::left_em, and lfirst.

Referenced by get_foreign_key_join_selectivity().

2530 {
2531  ListCell *lc;
2532 
2533  Assert(ec->ec_has_const);
2534  Assert(!em->em_is_const);
2535  foreach(lc, ec->ec_derives)
2536  {
2537  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2538 
2539  /*
2540  * generate_base_implied_equalities_const will have put non-const
2541  * members on the left side of derived clauses.
2542  */
2543  if (rinfo->left_em == em)
2544  return rinfo;
2545  }
2546  return NULL;
2547 }
List * ec_derives
Definition: pathnodes.h:983
EquivalenceMember * left_em
Definition: pathnodes.h:2098
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169

◆ find_ec_member_matching_expr()

EquivalenceMember* find_ec_member_matching_expr ( EquivalenceClass ec,
Expr expr,
Relids  relids 
)

Definition at line 786 of file equivclass.c.

References arg, bms_is_subset(), EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, equal(), IsA, and lfirst.

Referenced by make_unique_from_pathkeys(), prepare_sort_from_pathkeys(), and relation_can_be_sorted_early().

789 {
790  ListCell *lc;
791 
792  /* We ignore binary-compatible relabeling on both ends */
793  while (expr && IsA(expr, RelabelType))
794  expr = ((RelabelType *) expr)->arg;
795 
796  foreach(lc, ec->ec_members)
797  {
799  Expr *emexpr;
800 
801  /*
802  * We shouldn't be trying to sort by an equivalence class that
803  * contains a constant, so no need to consider such cases any further.
804  */
805  if (em->em_is_const)
806  continue;
807 
808  /*
809  * Ignore child members unless they belong to the requested rel.
810  */
811  if (em->em_is_child &&
812  !bms_is_subset(em->em_relids, relids))
813  continue;
814 
815  /*
816  * Match if same expression (after stripping relabel).
817  */
818  emexpr = em->em_expr;
819  while (emexpr && IsA(emexpr, RelabelType))
820  emexpr = ((RelabelType *) emexpr)->arg;
821 
822  if (equal(emexpr, expr))
823  return em;
824  }
825 
826  return NULL;
827 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:590
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3122
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
#define lfirst(lc)
Definition: pg_list.h:169
void * arg
List * ec_members
Definition: pathnodes.h:981

◆ find_em_expr_for_rel()

Expr* find_em_expr_for_rel ( EquivalenceClass ec,
RelOptInfo rel 
)

Definition at line 939 of file equivclass.c.

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

940 {
941  ListCell *lc_em;
942 
943  foreach(lc_em, ec->ec_members)
944  {
945  EquivalenceMember *em = lfirst(lc_em);
946 
947  if (bms_is_subset(em->em_relids, rel->relids) &&
948  !bms_is_empty(em->em_relids))
949  {
950  /*
951  * If there is more than one equivalence member whose Vars are
952  * taken entirely from this relation, we'll be content to choose
953  * any one of those.
954  */
955  return em->em_expr;
956  }
957  }
958 
959  /* We didn't find any suitable equivalence class expression */
960  return NULL;
961 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
Relids relids
Definition: pathnodes.h:676
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define lfirst(lc)
Definition: pg_list.h:169
List * ec_members
Definition: pathnodes.h:981

◆ find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1262 of file pathkeys.c.

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

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

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

◆ generate_base_implied_equalities()

void generate_base_implied_equalities ( PlannerInfo root)

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

1089 {
1090  int ec_index;
1091  ListCell *lc;
1092 
1093  /*
1094  * At this point, we're done absorbing knowledge of equivalences in the
1095  * query, so no further EC merging should happen, and ECs remaining in the
1096  * eq_classes list can be considered canonical. (But note that it's still
1097  * possible for new single-member ECs to be added through
1098  * get_eclass_for_sort_expr().)
1099  */
1100  root->ec_merging_done = true;
1101 
1102  ec_index = 0;
1103  foreach(lc, root->eq_classes)
1104  {
1106  bool can_generate_joinclause = false;
1107  int i;
1108 
1109  Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
1110  Assert(!ec->ec_broken); /* not yet anyway... */
1111 
1112  /*
1113  * Generate implied equalities that are restriction clauses.
1114  * Single-member ECs won't generate any deductions, either here or at
1115  * the join level.
1116  */
1117  if (list_length(ec->ec_members) > 1)
1118  {
1119  if (ec->ec_has_const)
1121  else
1123 
1124  /* Recover if we failed to generate required derived clauses */
1125  if (ec->ec_broken)
1127 
1128  /* Detect whether this EC might generate join clauses */
1129  can_generate_joinclause =
1131  }
1132 
1133  /*
1134  * Mark the base rels cited in each eclass (which should all exist by
1135  * now) with the eq_classes indexes of all eclasses mentioning them.
1136  * This will let us avoid searching in subsequent lookups. While
1137  * we're at it, we can mark base rels that have pending eclass joins;
1138  * this is a cheap version of has_relevant_eclass_joinclause().
1139  */
1140  i = -1;
1141  while ((i = bms_next_member(ec->ec_relids, i)) > 0)
1142  {
1143  RelOptInfo *rel = root->simple_rel_array[i];
1144 
1145  Assert(rel->reloptkind == RELOPT_BASEREL);
1146 
1148  ec_index);
1149 
1150  if (can_generate_joinclause)
1151  rel->has_eclass_joins = true;
1152  }
1153 
1154  ec_index++;
1155  }
1156 }
bool has_eclass_joins
Definition: pathnodes.h:746
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1257
RelOptKind reloptkind
Definition: pathnodes.h:673
bool ec_merging_done
Definition: pathnodes.h:250
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:1364
struct RelOptInfo ** simple_rel_array
Definition: pathnodes.h:185
Relids ec_relids
Definition: pathnodes.h:984
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:672
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
List * eq_classes
Definition: pathnodes.h:248
static int list_length(const List *l)
Definition: pg_list.h:149
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:736
int i
static void generate_base_implied_equalities_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1162
Bitmapset * eclass_indexes
Definition: pathnodes.h:718
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:993
List * ec_members
Definition: pathnodes.h:981

◆ generate_gather_paths()

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

Definition at line 2608 of file allpaths.c.

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

Referenced by generate_useful_gather_paths().

2609 {
2610  Path *cheapest_partial_path;
2611  Path *simple_gather_path;
2612  ListCell *lc;
2613  double rows;
2614  double *rowsp = NULL;
2615 
2616  /* If there are no partial paths, there's nothing to do here. */
2617  if (rel->partial_pathlist == NIL)
2618  return;
2619 
2620  /* Should we override the rel's rowcount estimate? */
2621  if (override_rows)
2622  rowsp = &rows;
2623 
2624  /*
2625  * The output of Gather is always unsorted, so there's only one partial
2626  * path of interest: the cheapest one. That will be the one at the front
2627  * of partial_pathlist because of the way add_partial_path works.
2628  */
2629  cheapest_partial_path = linitial(rel->partial_pathlist);
2630  rows =
2631  cheapest_partial_path->rows * cheapest_partial_path->parallel_workers;
2632  simple_gather_path = (Path *)
2633  create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
2634  NULL, rowsp);
2635  add_path(rel, simple_gather_path);
2636 
2637  /*
2638  * For each useful ordering, we can consider an order-preserving Gather
2639  * Merge.
2640  */
2641  foreach(lc, rel->partial_pathlist)
2642  {
2643  Path *subpath = (Path *) lfirst(lc);
2644  GatherMergePath *path;
2645 
2646  if (subpath->pathkeys == NIL)
2647  continue;
2648 
2649  rows = subpath->rows * subpath->parallel_workers;
2650  path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
2651  subpath->pathkeys, NULL, rowsp);
2652  add_path(rel, &path->path);
2653  }
2654 }
#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:1951
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
int parallel_workers
Definition: pathnodes.h:1181
List * partial_pathlist
Definition: pathnodes.h:692
#define linitial(l)
Definition: pg_list.h:174
GatherMergePath * create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, List *pathkeys, Relids required_outer, double *rows)
Definition: pathnode.c:1860
List * pathkeys
Definition: pathnodes.h:1188
#define lfirst(lc)
Definition: pg_list.h:169
double rows
Definition: pathnodes.h:1184
struct PathTarget * reltarget
Definition: pathnodes.h:687
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 2850 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().

2855 {
2856  List *result = NIL;
2857  bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
2858  Relids parent_relids;
2859  int i;
2860 
2861  /* Should be OK to rely on eclass_indexes */
2862  Assert(root->ec_merging_done);
2863 
2864  /* Indexes are available only on base or "other" member relations. */
2865  Assert(IS_SIMPLE_REL(rel));
2866 
2867  /* If it's a child rel, we'll need to know what its parent(s) are */
2868  if (is_child_rel)
2869  parent_relids = find_childrel_parents(root, rel);
2870  else
2871  parent_relids = NULL; /* not used, but keep compiler quiet */
2872 
2873  i = -1;
2874  while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
2875  {
2876  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2877  EquivalenceMember *cur_em;
2878  ListCell *lc2;
2879 
2880  /* Sanity check eclass_indexes only contain ECs for rel */
2881  Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
2882 
2883  /*
2884  * Won't generate joinclauses if const or single-member (the latter
2885  * test covers the volatile case too)
2886  */
2887  if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
2888  continue;
2889 
2890  /*
2891  * Scan members, looking for a match to the target column. Note that
2892  * child EC members are considered, but only when they belong to the
2893  * target relation. (Unlike regular members, the same expression
2894  * could be a child member of more than one EC. Therefore, it's
2895  * potentially order-dependent which EC a child relation's target
2896  * column gets matched to. This is annoying but it only happens in
2897  * corner cases, so for now we live with just reporting the first
2898  * match. See also get_eclass_for_sort_expr.)
2899  */
2900  cur_em = NULL;
2901  foreach(lc2, cur_ec->ec_members)
2902  {
2903  cur_em = (EquivalenceMember *) lfirst(lc2);
2904  if (bms_equal(cur_em->em_relids, rel->relids) &&
2905  callback(root, rel, cur_ec, cur_em, callback_arg))
2906  break;
2907  cur_em = NULL;
2908  }
2909 
2910  if (!cur_em)
2911  continue;
2912 
2913  /*
2914  * Found our match. Scan the other EC members and attempt to generate
2915  * joinclauses.
2916  */
2917  foreach(lc2, cur_ec->ec_members)
2918  {
2919  EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
2920  Oid eq_op;
2921  RestrictInfo *rinfo;
2922 
2923  if (other_em->em_is_child)
2924  continue; /* ignore children here */
2925 
2926  /* Make sure it'll be a join to a different rel */
2927  if (other_em == cur_em ||
2928  bms_overlap(other_em->em_relids, rel->relids))
2929  continue;
2930 
2931  /* Forget it if caller doesn't want joins to this rel */
2932  if (bms_overlap(other_em->em_relids, prohibited_rels))
2933  continue;
2934 
2935  /*
2936  * Also, if this is a child rel, avoid generating a useless join
2937  * to its parent rel(s).
2938  */
2939  if (is_child_rel &&
2940  bms_overlap(parent_relids, other_em->em_relids))
2941  continue;
2942 
2943  eq_op = select_equality_operator(cur_ec,
2944  cur_em->em_datatype,
2945  other_em->em_datatype);
2946  if (!OidIsValid(eq_op))
2947  continue;
2948 
2949  /* set parent_ec to mark as redundant with other joinclauses */
2950  rinfo = create_join_clause(root, cur_ec, eq_op,
2951  cur_em, other_em,
2952  cur_ec);
2953 
2954  result = lappend(result, rinfo);
2955  }
2956 
2957  /*
2958  * If somehow we failed to create any join clauses, we might as well
2959  * keep scanning the ECs for another match. But if we did make any,
2960  * we're done, because we don't want to return non-redundant clauses.
2961  */
2962  if (result)
2963  break;
2964  }
2965 
2966  return result;
2967 }
#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:1830
RelOptKind reloptkind
Definition: pathnodes.h:673
bool ec_merging_done
Definition: pathnodes.h:250
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:710
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:649
static void * list_nth(const List *list, int n)
Definition: pg_list.h:278
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:1795
Relids ec_relids
Definition: pathnodes.h:984
Relids relids
Definition: pathnodes.h:676
List * lappend(List *list, void *datum)
Definition: list.c:336
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1258
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
List * eq_classes
Definition: pathnodes.h:248
static int list_length(const List *l)
Definition: pg_list.h:149
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
int i
Definition: pg_list.h:50
Bitmapset * eclass_indexes
Definition: pathnodes.h:718
List * ec_members
Definition: pathnodes.h:981
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 1421 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().

1425 {
1426  List *result = NIL;
1427  Relids inner_relids = inner_rel->relids;
1428  Relids nominal_inner_relids;
1429  Relids nominal_join_relids;
1430  Bitmapset *matching_ecs;
1431  int i;
1432 
1433  /* If inner rel is a child, extra setup work is needed */
1434  if (IS_OTHER_REL(inner_rel))
1435  {
1436  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1437 
1438  /* Fetch relid set for the topmost parent rel */
1439  nominal_inner_relids = inner_rel->top_parent_relids;
1440  /* ECs will be marked with the parent's relid, not the child's */
1441  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1442  }
1443  else
1444  {
1445  nominal_inner_relids = inner_relids;
1446  nominal_join_relids = join_relids;
1447  }
1448 
1449  /*
1450  * Get all eclasses that mention both inner and outer sides of the join
1451  */
1452  matching_ecs = get_common_eclass_indexes(root, nominal_inner_relids,
1453  outer_relids);
1454 
1455  i = -1;
1456  while ((i = bms_next_member(matching_ecs, i)) >= 0)
1457  {
1459  List *sublist = NIL;
1460 
1461  /* ECs containing consts do not need any further enforcement */
1462  if (ec->ec_has_const)
1463  continue;
1464 
1465  /* Single-member ECs won't generate any deductions */
1466  if (list_length(ec->ec_members) <= 1)
1467  continue;
1468 
1469  /* Sanity check that this eclass overlaps the join */
1470  Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
1471 
1472  if (!ec->ec_broken)
1474  ec,
1475  join_relids,
1476  outer_relids,
1477  inner_relids);
1478 
1479  /* Recover if we failed to generate required derived clauses */
1480  if (ec->ec_broken)
1482  ec,
1483  nominal_join_relids,
1484  outer_relids,
1485  nominal_inner_relids,
1486  inner_rel);
1487 
1488  result = list_concat(result, sublist);
1489  }
1490 
1491  return result;
1492 }
#define NIL
Definition: pg_list.h:65
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:664
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
List * list_concat(List *list1, const List *list2)
Definition: list.c:530
static void * list_nth(const List *list, int n)
Definition: pg_list.h:278
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:1746
Relids ec_relids
Definition: pathnodes.h:984
Relids relids
Definition: pathnodes.h:676
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1570
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:3236
#define Assert(condition)
Definition: c.h:804
List * eq_classes
Definition: pathnodes.h:248
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:225
static int list_length(const List *l)
Definition: pg_list.h:149
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
int i
Definition: pg_list.h:50
List * ec_members
Definition: pathnodes.h:981
Relids top_parent_relids
Definition: pathnodes.h:751

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

1504 {
1505  List *result = NIL;
1506  Relids inner_relids = inner_rel->relids;
1507  Relids nominal_inner_relids;
1508  Relids nominal_join_relids;
1509  ListCell *lc;
1510 
1511  /* If inner rel is a child, extra setup work is needed */
1512  if (IS_OTHER_REL(inner_rel))
1513  {
1514  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1515 
1516  /* Fetch relid set for the topmost parent rel */
1517  nominal_inner_relids = inner_rel->top_parent_relids;
1518  /* ECs will be marked with the parent's relid, not the child's */
1519  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1520  }
1521  else
1522  {
1523  nominal_inner_relids = inner_relids;
1524  nominal_join_relids = join_relids;
1525  }
1526 
1527  foreach(lc, eclasses)
1528  {
1530  List *sublist = NIL;
1531 
1532  /* ECs containing consts do not need any further enforcement */
1533  if (ec->ec_has_const)
1534  continue;
1535 
1536  /* Single-member ECs won't generate any deductions */
1537  if (list_length(ec->ec_members) <= 1)
1538  continue;
1539 
1540  /* We can quickly ignore any that don't overlap the join, too */
1541  if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1542  continue;
1543 
1544  if (!ec->ec_broken)
1546  ec,
1547  join_relids,
1548  outer_relids,
1549  inner_relids);
1550 
1551  /* Recover if we failed to generate required derived clauses */
1552  if (ec->ec_broken)
1554  ec,
1555  nominal_join_relids,
1556  outer_relids,
1557  nominal_inner_relids,
1558  inner_rel);
1559 
1560  result = list_concat(result, sublist);
1561  }
1562 
1563  return result;
1564 }
#define NIL
Definition: pg_list.h:65
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:664
List * list_concat(List *list1, const List *list2)
Definition: list.c:530
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:1746
Relids ec_relids
Definition: pathnodes.h:984
Relids relids
Definition: pathnodes.h:676
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1570
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:225
static int list_length(const List *l)
Definition: pg_list.h:149
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
Definition: pg_list.h:50
List * ec_members
Definition: pathnodes.h:981
Relids top_parent_relids
Definition: pathnodes.h:751

◆ generate_partitionwise_join_paths()

void generate_partitionwise_join_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 3837 of file allpaths.c.

References add_paths_to_append_rel(), Alias::aliasname, Assert, RelOptInfo::baserestrictinfo, bms_next_member(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_startup_path, RelOptInfo::cheapest_total_path, check_stack_depth(), RestrictInfo::clause, RelOptInfo::consider_partitionwise_join, RangeTblEntry::eref, generate_partitionwise_join_paths(), i, JoinPath::innerjoinpath, MergePath::innersortkeys, IS_DUMMY_REL, IS_JOIN_REL, IS_PARTITIONED_REL, IsA, RelOptInfo::joininfo, JoinPath::joinrestrictinfo, lappend(), lfirst, list_free(), lnext(), mark_dummy_rel(), MergePath::materialize_inner, NIL, nodeTag, RelOptInfo::nparts, JoinPath::outerjoinpath, MergePath::outersortkeys, Path::param_info, Path::parent, PlannerInfo::parse, RelOptInfo::part_rels, Path::pathkeys, RelOptInfo::pathlist, Path::pathtype, ParamPathInfo::ppi_req_outer, print_expr(), print_pathkeys(), printf, RelOptInfo::relids, RelOptInfo::reltarget, RelOptInfo::rows, Path::rows, Query::rtable, set_cheapest(), PlannerInfo::simple_rte_array, Path::startup_cost, generate_unaccent_rules::stdout, subpath(), T_AggPath, T_AppendPath, T_BitmapAndPath, T_BitmapHeapPath, T_BitmapOrPath, T_CteScan, T_CustomPath, T_ForeignPath, T_FunctionScan, T_GatherMergePath, T_GatherPath, T_GroupingSetsPath, T_GroupPath, T_GroupResultPath, T_HashPath, T_IncrementalSortPath, T_IndexPath, T_LimitPath, T_LockRowsPath, T_MaterialPath, T_MemoizePath, 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().

3838 {
3839  List *live_children = NIL;
3840  int cnt_parts;
3841  int num_parts;
3842  RelOptInfo **part_rels;
3843 
3844  /* Handle only join relations here. */
3845  if (!IS_JOIN_REL(rel))
3846  return;
3847 
3848  /* We've nothing to do if the relation is not partitioned. */
3849  if (!IS_PARTITIONED_REL(rel))
3850  return;
3851 
3852  /* The relation should have consider_partitionwise_join set. */
3854 
3855  /* Guard against stack overflow due to overly deep partition hierarchy. */
3857 
3858  num_parts = rel->nparts;
3859  part_rels = rel->part_rels;
3860 
3861  /* Collect non-dummy child-joins. */
3862  for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
3863  {
3864  RelOptInfo *child_rel = part_rels[cnt_parts];
3865 
3866  /* If it's been pruned entirely, it's certainly dummy. */
3867  if (child_rel == NULL)
3868  continue;
3869 
3870  /* Add partitionwise join paths for partitioned child-joins. */
3871  generate_partitionwise_join_paths(root, child_rel);
3872 
3873  set_cheapest(child_rel);
3874 
3875  /* Dummy children will not be scanned, so ignore those. */
3876  if (IS_DUMMY_REL(child_rel))
3877  continue;
3878 
3879 #ifdef OPTIMIZER_DEBUG
3880  debug_print_rel(root, child_rel);
3881 #endif
3882 
3883  live_children = lappend(live_children, child_rel);
3884  }
3885 
3886  /* If all child-joins are dummy, parent join is also dummy. */
3887  if (!live_children)
3888  {
3889  mark_dummy_rel(rel);
3890  return;
3891  }
3892 
3893  /* Build additional paths for this rel from child-join paths. */
3894  add_paths_to_append_rel(root, rel, live_children);
3895  list_free(live_children);
3896 }
#define NIL
Definition: pg_list.h:65
void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
Definition: allpaths.c:1285
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:3837
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:654
#define IS_DUMMY_REL(r)
Definition: pathnodes.h:1458
void check_stack_depth(void)
Definition: postgres.c:3469
int nparts
Definition: pathnodes.h:756
List * lappend(List *list, void *datum)
Definition: list.c:336
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:244
bool consider_partitionwise_join
Definition: pathnodes.h:749
void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1261
#define Assert(condition)
Definition: c.h:804
struct RelOptInfo ** part_rels
Definition: pathnodes.h:763
#define IS_PARTITIONED_REL(rel)
Definition: pathnodes.h:778
void list_free(List *list)
Definition: list.c:1391
Definition: pg_list.h:50

◆ generate_useful_gather_paths()

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

Definition at line 2746 of file allpaths.c.

References add_path(), Assert, create_gather_merge_path(), create_incremental_sort_path(), create_sort_path(), enable_incremental_sort, generate_gather_paths(), get_useful_pathkeys_for_relation(), lfirst, linitial, list_length(), NIL, Path::parallel_workers, RelOptInfo::partial_pathlist, GatherMergePath::path, Path::pathkeys, pathkeys_count_contained_in(), RelOptInfo::reltarget, Path::rows, and subpath().

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

2747 {
2748  ListCell *lc;
2749  double rows;
2750  double *rowsp = NULL;
2751  List *useful_pathkeys_list = NIL;
2752  Path *cheapest_partial_path = NULL;
2753 
2754  /* If there are no partial paths, there's nothing to do here. */
2755  if (rel->partial_pathlist == NIL)
2756  return;
2757 
2758  /* Should we override the rel's rowcount estimate? */
2759  if (override_rows)
2760  rowsp = &rows;
2761 
2762  /* generate the regular gather (merge) paths */
2763  generate_gather_paths(root, rel, override_rows);
2764 
2765  /* consider incremental sort for interesting orderings */
2766  useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
2767 
2768  /* used for explicit (full) sort paths */
2769  cheapest_partial_path = linitial(rel->partial_pathlist);
2770 
2771  /*
2772  * Consider sorted paths for each interesting ordering. We generate both
2773  * incremental and full sort.
2774  */
2775  foreach(lc, useful_pathkeys_list)
2776  {
2777  List *useful_pathkeys = lfirst(lc);
2778  ListCell *lc2;
2779  bool is_sorted;
2780  int presorted_keys;
2781 
2782  foreach(lc2, rel->partial_pathlist)
2783  {
2784  Path *subpath = (Path *) lfirst(lc2);
2785  GatherMergePath *path;
2786 
2787  is_sorted = pathkeys_count_contained_in(useful_pathkeys,
2788  subpath->pathkeys,
2789  &presorted_keys);
2790 
2791  /*
2792  * We don't need to consider the case where a subpath is already
2793  * fully sorted because generate_gather_paths already creates a
2794  * gather merge path for every subpath that has pathkeys present.
2795  *
2796  * But since the subpath is already sorted, we know we don't need
2797  * to consider adding a sort (full or incremental) on top of it,
2798  * so we can continue here.
2799  */
2800  if (is_sorted)
2801  continue;
2802 
2803  /*
2804  * Consider regular sort for the cheapest partial path (for each
2805  * useful pathkeys). We know the path is not sorted, because we'd
2806  * not get here otherwise.
2807  *
2808  * This is not redundant with the gather paths created in
2809  * generate_gather_paths, because that doesn't generate ordered
2810  * output. Here we add an explicit sort to match the useful
2811  * ordering.
2812  */
2813  if (cheapest_partial_path == subpath)
2814  {
2815  Path *tmp;
2816 
2817  tmp = (Path *) create_sort_path(root,
2818  rel,
2819  subpath,
2820  useful_pathkeys,
2821  -1.0);
2822 
2823  rows = tmp->rows * tmp->parallel_workers;
2824 
2825  path = create_gather_merge_path(root, rel,
2826  tmp,
2827  rel->reltarget,
2828  tmp->pathkeys,
2829  NULL,
2830  rowsp);
2831 
2832  add_path(rel, &path->path);
2833 
2834  /* Fall through */
2835  }
2836 
2837  /*
2838  * Consider incremental sort, but only when the subpath is already
2839  * partially sorted on a pathkey prefix.
2840  */
2841  if (enable_incremental_sort && presorted_keys > 0)
2842  {
2843  Path *tmp;
2844 
2845  /*
2846  * We should have already excluded pathkeys of length 1
2847  * because then presorted_keys > 0 would imply is_sorted was
2848  * true.
2849  */
2850  Assert(list_length(useful_pathkeys) != 1);
2851 
2852  tmp = (Path *) create_incremental_sort_path(root,
2853  rel,
2854  subpath,
2855  useful_pathkeys,
2856  presorted_keys,
2857  -1);
2858 
2859  path = create_gather_merge_path(root, rel,
2860  tmp,
2861  rel->reltarget,
2862  tmp->pathkeys,
2863  NULL,
2864  rowsp);
2865 
2866  add_path(rel, &path->path);
2867  }
2868  }
2869  }
2870 }
#define NIL
Definition: pg_list.h:65
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
bool enable_incremental_sort
Definition: costsize.c:139
int parallel_workers
Definition: pathnodes.h:1181
List * partial_pathlist
Definition: pathnodes.h:692
void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:2608
IncrementalSortPath * create_incremental_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, int presorted_keys, double limit_tuples)
Definition: pathnode.c:2892
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:343
#define linitial(l)
Definition: pg_list.h:174
GatherMergePath * create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, List *pathkeys, Relids required_outer, double *rows)
Definition: pathnode.c:1860
SortPath * create_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, double limit_tuples)
Definition: pathnode.c:2941
List * pathkeys
Definition: pathnodes.h:1188
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
double rows
Definition: pathnodes.h:1184
static int list_length(const List *l)
Definition: pg_list.h:149
static List * get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel, bool require_parallel_safe)
Definition: allpaths.c:2678
Definition: pg_list.h:50
struct PathTarget * reltarget
Definition: pathnodes.h:687
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:241

◆ get_cheapest_fractional_path_for_pathkeys()

Path* get_cheapest_fractional_path_for_pathkeys ( List paths,
List pathkeys,
Relids  required_outer,
double  fraction 
)

Definition at line 449 of file pathkeys.c.

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

Referenced by build_minmax_path().

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

◆ get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner ( List paths)

Definition at line 482 of file pathkeys.c.

References bms_is_empty(), lfirst, Path::parallel_safe, and PATH_REQ_OUTER.

Referenced by add_paths_to_append_rel(), hash_inner_and_outer(), match_unsorted_outer(), and sort_inner_and_outer().

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

◆ get_cheapest_path_for_pathkeys()

Path* get_cheapest_path_for_pathkeys ( List paths,
List pathkeys,
Relids  required_outer,
CostSelector  cost_criterion,
bool  require_parallel_safe 
)

Definition at line 404 of file pathkeys.c.

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

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

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

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

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

3048 {
3049  Bitmapset *matched_ecs;
3050  int i;
3051 
3052  /* Examine only eclasses mentioning rel1 */
3053  matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
3054 
3055  i = -1;
3056  while ((i = bms_next_member(matched_ecs, i)) >= 0)
3057  {
3059  i);
3060 
3061  /*
3062  * Won't generate joinclauses if single-member (this test covers the
3063  * volatile case too)
3064  */
3065  if (list_length(ec->ec_members) <= 1)
3066  continue;
3067 
3068  /*
3069  * Per the comment in have_relevant_eclass_joinclause, it's sufficient
3070  * to find an EC that mentions both this rel and some other rel.
3071  */
3072  if (!bms_is_subset(ec->ec_relids, rel1->relids))
3073  return true;
3074  }
3075 
3076  return false;
3077 }
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:278
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:3212
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
Relids ec_relids
Definition: pathnodes.h:984
Relids relids
Definition: pathnodes.h:676
List * eq_classes
Definition: pathnodes.h:248
static int list_length(const List *l)
Definition: pg_list.h:149
int i
List * ec_members
Definition: pathnodes.h:981

◆ has_useful_pathkeys()

bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 1910 of file pathkeys.c.

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

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

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

◆ have_dangerous_phv()

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

Definition at line 1184 of file joinrels.c.

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

Referenced by join_is_legal(), and try_nestloop_path().

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

◆ have_join_order_restriction()

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

Definition at line 951 of file joinrels.c.

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

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

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

◆ have_relevant_eclass_joinclause()

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

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

2982 {
2983  Bitmapset *matching_ecs;
2984  int i;
2985 
2986  /* Examine only eclasses mentioning both rel1 and rel2 */
2987  matching_ecs = get_common_eclass_indexes(root, rel1->relids,
2988  rel2->relids);
2989 
2990  i = -1;
2991  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2992  {
2994  i);
2995 
2996  /*
2997  * Sanity check that get_common_eclass_indexes gave only ECs
2998  * containing both rels.
2999  */
3000  Assert(bms_overlap(rel1->relids, ec->ec_relids));
3001  Assert(bms_overlap(rel2->relids, ec->ec_relids));
3002 
3003  /*
3004  * Won't generate joinclauses if single-member (this test covers the
3005  * volatile case too)
3006  */
3007  if (list_length(ec->ec_members) <= 1)
3008  continue;
3009 
3010  /*
3011  * We do not need to examine the individual members of the EC, because
3012  * all that we care about is whether each rel overlaps the relids of
3013  * at least one member, and get_common_eclass_indexes() and the single
3014  * member check above are sufficient to prove that. (As with
3015  * have_relevant_joinclause(), it is not necessary that the EC be able
3016  * to form a joinclause relating exactly the two given rels, only that
3017  * it be able to form a joinclause mentioning both, and this will
3018  * surely be true if both of them overlap ec_relids.)
3019  *
3020  * Note we don't test ec_broken; if we did, we'd need a separate code
3021  * path to look through ec_sources. Checking the membership anyway is
3022  * OK as a possibly-overoptimistic heuristic.
3023  *
3024  * We don't test ec_has_const either, even though a const eclass won't
3025  * generate real join clauses. This is because if we had "WHERE a.x =
3026  * b.y and a.x = 42", it is worth considering a join between a and b,
3027  * since the join result is likely to be small even though it'll end
3028  * up being an unqualified nestloop.
3029  */
3030 
3031  return true;
3032  }
3033 
3034  return false;
3035 }
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:278
Relids ec_relids
Definition: pathnodes.h:984
Relids relids
Definition: pathnodes.h:676
static Bitmapset * get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
Definition: equivclass.c:3236
#define Assert(condition)
Definition: c.h:804
List * eq_classes
Definition: pathnodes.h:248
static int list_length(const List *l)
Definition: pg_list.h:149
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
int i
List * ec_members
Definition: pathnodes.h:981

◆ indexcol_is_bool_constant_for_query()

bool indexcol_is_bool_constant_for_query ( PlannerInfo root,
IndexOptInfo index,
int  indexcol 
)

Definition at line 3682 of file indxpath.c.

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

Referenced by build_index_pathkeys().

3685 {
3686  ListCell *lc;
3687 
3688  /* If the index isn't boolean, we can't possibly get a match */
3689  if (!IsBooleanOpfamily(index->opfamily[indexcol]))
3690  return false;
3691 
3692  /* Check each restriction clause for the index's rel */
3693  foreach(lc, index->rel->baserestrictinfo)
3694  {
3695  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3696 
3697  /*
3698  * As in match_clause_to_indexcol, never match pseudoconstants to
3699  * indexes. (It might be semantically okay to do so here, but the
3700  * odds of getting a match are negligible, so don't waste the cycles.)
3701  */
3702  if (rinfo->pseudoconstant)
3703  continue;
3704 
3705  /* See if we can match the clause's expression to the index column */
3706  if (match_boolean_index_clause(root, rinfo, indexcol, index))
3707  return true;
3708  }
3709 
3710  return false;
3711 }
List * baserestrictinfo
Definition: pathnodes.h:740
bool pseudoconstant
Definition: pathnodes.h:2053
static IndexClause * match_boolean_index_clause(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:2376
RelOptInfo * rel
Definition: pathnodes.h:832
#define lfirst(lc)
Definition: pg_list.h:169
Oid * opfamily
Definition: pathnodes.h:845

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1179 of file pathkeys.c.

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

Referenced by distribute_qual_to_rels().

1180 {
1181  Expr *clause = restrictinfo->clause;
1182  Oid lefttype,
1183  righttype;
1184 
1185  /* Should be a mergeclause ... */
1186  Assert(restrictinfo->mergeopfamilies != NIL);
1187  /* ... with links not yet set */
1188  Assert(restrictinfo->left_ec == NULL);
1189  Assert(restrictinfo->right_ec == NULL);
1190 
1191  /* Need the declared input types of the operator */
1192  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1193 
1194  /* Find or create a matching EquivalenceClass for each side */
1195  restrictinfo->left_ec =
1197  (Expr *) get_leftop(clause),
1198  restrictinfo->nullable_relids,
1199  restrictinfo->mergeopfamilies,
1200  lefttype,
1201  ((OpExpr *) clause)->inputcollid,
1202  0,
1203  NULL,
1204  true);
1205  restrictinfo->right_ec =
1207  (Expr *) get_rightop(clause),
1208  restrictinfo->nullable_relids,
1209  restrictinfo->mergeopfamilies,
1210  righttype,
1211  ((OpExpr *) clause)->inputcollid,
1212  0,
1213  NULL,
1214  true);
1215 }
#define NIL
Definition: pg_list.h:65
EquivalenceClass * get_eclass_for_sort_expr(PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
Definition: equivclass.c:621
EquivalenceClass * right_ec
Definition: pathnodes.h:2097
unsigned int Oid
Definition: postgres_ext.h:31
List * mergeopfamilies
Definition: pathnodes.h:2093
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1329
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:73
Expr * clause
Definition: pathnodes.h:2045
Relids nullable_relids
Definition: pathnodes.h:2072
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:85
#define Assert(condition)
Definition: c.h:804
EquivalenceClass * left_ec
Definition: pathnodes.h:2096

◆ is_redundant_derived_clause()

bool is_redundant_derived_clause ( RestrictInfo rinfo,
List clauselist 
)

Definition at line 3149 of file equivclass.c.

References lfirst, and RestrictInfo::parent_ec.

Referenced by create_tidscan_plan().

3150 {
3151  EquivalenceClass *parent_ec = rinfo->parent_ec;
3152  ListCell *lc;
3153 
3154  /* Fail if it's not a potentially-redundant clause from some EC */
3155  if (parent_ec == NULL)
3156  return false;
3157 
3158  foreach(lc, clauselist)
3159  {
3160  RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
3161 
3162  if (otherrinfo->parent_ec == parent_ec)
3163  return true;
3164  }
3165 
3166  return false;
3167 }
EquivalenceClass * parent_ec
Definition: pathnodes.h:2082
#define lfirst(lc)
Definition: pg_list.h:169

◆ is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses ( RestrictInfo rinfo,
List indexclauses 
)

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

3177 {
3178  EquivalenceClass *parent_ec = rinfo->parent_ec;
3179  ListCell *lc;
3180 
3181  foreach(lc, indexclauses)
3182  {
3183  IndexClause *iclause = lfirst_node(IndexClause, lc);
3184  RestrictInfo *otherrinfo = iclause->rinfo;
3185 
3186  /* If indexclause is lossy, it won't enforce the condition exactly */
3187  if (iclause->lossy)
3188  continue;
3189 
3190  /* Match if it's same clause (pointer equality should be enough) */
3191  if (rinfo == otherrinfo)
3192  return true;
3193  /* Match if derived from same EC */
3194  if (parent_ec && otherrinfo->parent_ec == parent_ec)
3195  return true;
3196 
3197  /*
3198  * No need to look at the derived clauses in iclause->indexquals; they
3199  * couldn't match if the parent clause didn't.
3200  */
3201  }
3202 
3203  return false;
3204 }
EquivalenceClass * parent_ec
Definition: pathnodes.h:2082
#define lfirst_node(type, lc)
Definition: pg_list.h:172
struct RestrictInfo * rinfo
Definition: pathnodes.h:1283

◆ join_search_one_level()

void join_search_one_level ( PlannerInfo root,
int  level 
)

Definition at line 71 of file joinrels.c.

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

Referenced by standard_join_search().

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