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)
 
Relids add_outer_joins_to_relids (PlannerInfo *root, Relids input_relids, SpecialJoinInfo *sjinfo, List **pushed_down_joins)
 
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)
 
void init_dummy_sjinfo (SpecialJoinInfo *sjinfo, Relids left_relids, Relids right_relids)
 
bool process_equivalence (PlannerInfo *root, RestrictInfo **p_restrictinfo, JoinDomain *jdomain)
 
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, 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)
 
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, SpecialJoinInfo *sjinfo)
 
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_joinrel, RelOptInfo *child_joinrel)
 
void add_setop_child_rel_equivalences (PlannerInfo *root, RelOptInfo *child_rel, List *child_tlist, List *setop_pathkeys)
 
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)
 
Listget_useful_group_keys_orderings (PlannerInfo *root, Path *path)
 
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, 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)
 
Listmake_pathkeys_for_sortclauses_extended (PlannerInfo *root, List **sortclauses, List *tlist, bool remove_redundant, bool *sortable)
 
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)
 
Listappend_pathkeys (List *target, List *source)
 
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 bool enable_group_by_reordering
 
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 119 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 46 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 37 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 30 of file paths.h.

Enumeration Type Documentation

◆ PathKeysComparison

Enumerator
PATHKEYS_EQUAL 
PATHKEYS_BETTER1 
PATHKEYS_BETTER2 
PATHKEYS_DIFFERENT 

Definition at line 200 of file paths.h.

201 {
202  PATHKEYS_EQUAL, /* pathkeys are identical */
203  PATHKEYS_BETTER1, /* pathkey 1 is a superset of pathkey 2 */
204  PATHKEYS_BETTER2, /* vice versa */
205  PATHKEYS_DIFFERENT, /* neither pathkey includes the other */
PathKeysComparison
Definition: paths.h:201
@ PATHKEYS_BETTER2
Definition: paths.h:204
@ PATHKEYS_BETTER1
Definition: paths.h:203
@ PATHKEYS_DIFFERENT
Definition: paths.h:205
@ PATHKEYS_EQUAL
Definition: paths.h:202

Function Documentation

◆ add_child_join_rel_equivalences()

void add_child_join_rel_equivalences ( PlannerInfo root,
int  nappinfos,
AppendRelInfo **  appinfos,
RelOptInfo parent_joinrel,
RelOptInfo child_joinrel 
)

Definition at line 2769 of file equivclass.c.

2773 {
2774  Relids top_parent_relids = child_joinrel->top_parent_relids;
2775  Relids child_relids = child_joinrel->relids;
2776  Bitmapset *matching_ecs;
2777  MemoryContext oldcontext;
2778  int i;
2779 
2780  Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
2781 
2782  /* We need consider only ECs that mention the parent joinrel */
2783  matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids);
2784 
2785  /*
2786  * If we're being called during GEQO join planning, we still have to
2787  * create any new EC members in the main planner context, to avoid having
2788  * a corrupt EC data structure after the GEQO context is reset. This is
2789  * problematic since we'll leak memory across repeated GEQO cycles. For
2790  * now, though, bloat is better than crash. If it becomes a real issue
2791  * we'll have to do something to avoid generating duplicate EC members.
2792  */
2793  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
2794 
2795  i = -1;
2796  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2797  {
2798  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2799  int num_members;
2800 
2801  /*
2802  * If this EC contains a volatile expression, then generating child
2803  * EMs would be downright dangerous, so skip it. We rely on a
2804  * volatile EC having only one EM.
2805  */
2806  if (cur_ec->ec_has_volatile)
2807  continue;
2808 
2809  /* Sanity check on get_eclass_indexes_for_relids result */
2810  Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
2811 
2812  /*
2813  * We don't use foreach() here because there's no point in scanning
2814  * newly-added child members, so we can stop after the last
2815  * pre-existing EC member.
2816  */
2817  num_members = list_length(cur_ec->ec_members);
2818  for (int pos = 0; pos < num_members; pos++)
2819  {
2820  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2821 
2822  if (cur_em->em_is_const)
2823  continue; /* ignore consts here */
2824 
2825  /*
2826  * We consider only original EC members here, not
2827  * already-transformed child members.
2828  */
2829  if (cur_em->em_is_child)
2830  continue; /* ignore children here */
2831 
2832  /*
2833  * We may ignore expressions that reference a single baserel,
2834  * because add_child_rel_equivalences should have handled them.
2835  */
2836  if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
2837  continue;
2838 
2839  /* Does this member reference child's topmost parent rel? */
2840  if (bms_overlap(cur_em->em_relids, top_parent_relids))
2841  {
2842  /* Yes, generate transformed child version */
2843  Expr *child_expr;
2844  Relids new_relids;
2845 
2846  if (parent_joinrel->reloptkind == RELOPT_JOINREL)
2847  {
2848  /* Simple single-level transformation */
2849  child_expr = (Expr *)
2851  (Node *) cur_em->em_expr,
2852  nappinfos, appinfos);
2853  }
2854  else
2855  {
2856  /* Must do multi-level transformation */
2857  Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
2858  child_expr = (Expr *)
2860  (Node *) cur_em->em_expr,
2861  child_joinrel,
2862  child_joinrel->top_parent);
2863  }
2864 
2865  /*
2866  * Transform em_relids to match. Note we do *not* do
2867  * pull_varnos(child_expr) here, as for example the
2868  * transformation might have substituted a constant, but we
2869  * don't want the child member to be marked as constant.
2870  */
2871  new_relids = bms_difference(cur_em->em_relids,
2872  top_parent_relids);
2873  new_relids = bms_add_members(new_relids, child_relids);
2874 
2875  (void) add_eq_member(cur_ec, child_expr, new_relids,
2876  cur_em->em_jdomain,
2877  cur_em, cur_em->em_datatype);
2878  }
2879  }
2880  }
2881 
2882  MemoryContextSwitchTo(oldcontext);
2883 }
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, int nappinfos, AppendRelInfo **appinfos)
Definition: appendinfo.c:196
Node * adjust_appendrel_attrs_multilevel(PlannerInfo *root, Node *node, RelOptInfo *childrel, RelOptInfo *parentrel)
Definition: appendinfo.c:521
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1306
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:346
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:917
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:781
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:582
@ BMS_MULTIPLE
Definition: bitmapset.h:73
#define Assert(condition)
Definition: c.h:858
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, JoinDomain *jdomain, EquivalenceMember *parent, Oid datatype)
Definition: equivclass.c:517
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:3344
int i
Definition: isn.c:73
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:834
@ RELOPT_JOINREL
Definition: pathnodes.h:818
@ RELOPT_OTHER_JOINREL
Definition: pathnodes.h:820
static int list_length(const List *l)
Definition: pg_list.h:152
static void * list_nth(const List *list, int n)
Definition: pg_list.h:299
MemoryContextSwitchTo(old_ctx)
tree ctl root
Definition: radixtree.h:1884
JoinDomain * em_jdomain
Definition: pathnodes.h:1435
Definition: nodes.h:129
Relids relids
Definition: pathnodes.h:861
Relids top_parent_relids
Definition: pathnodes.h:999
RelOptKind reloptkind
Definition: pathnodes.h:855

References add_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_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_jdomain, EquivalenceMember::em_relids, get_eclass_indexes_for_relids(), i, IS_JOIN_REL, list_length(), list_nth(), MemoryContextSwitchTo(), RelOptInfo::relids, RELOPT_JOINREL, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, root, and RelOptInfo::top_parent_relids.

Referenced by build_child_join_rel().

◆ add_child_rel_equivalences()

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

Definition at line 2647 of file equivclass.c.

2651 {
2652  Relids top_parent_relids = child_rel->top_parent_relids;
2653  Relids child_relids = child_rel->relids;
2654  int i;
2655 
2656  /*
2657  * EC merging should be complete already, so we can use the parent rel's
2658  * eclass_indexes to avoid searching all of root->eq_classes.
2659  */
2660  Assert(root->ec_merging_done);
2661  Assert(IS_SIMPLE_REL(parent_rel));
2662 
2663  i = -1;
2664  while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
2665  {
2666  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2667  int num_members;
2668 
2669  /*
2670  * If this EC contains a volatile expression, then generating child
2671  * EMs would be downright dangerous, so skip it. We rely on a
2672  * volatile EC having only one EM.
2673  */
2674  if (cur_ec->ec_has_volatile)
2675  continue;
2676 
2677  /* Sanity check eclass_indexes only contain ECs for parent_rel */
2678  Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
2679 
2680  /*
2681  * We don't use foreach() here because there's no point in scanning
2682  * newly-added child members, so we can stop after the last
2683  * pre-existing EC member.
2684  */
2685  num_members = list_length(cur_ec->ec_members);
2686  for (int pos = 0; pos < num_members; pos++)
2687  {
2688  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2689 
2690  if (cur_em->em_is_const)
2691  continue; /* ignore consts here */
2692 
2693  /*
2694  * We consider only original EC members here, not
2695  * already-transformed child members. Otherwise, if some original
2696  * member expression references more than one appendrel, we'd get
2697  * an O(N^2) explosion of useless derived expressions for
2698  * combinations of children. (But add_child_join_rel_equivalences
2699  * may add targeted combinations for partitionwise-join purposes.)
2700  */
2701  if (cur_em->em_is_child)
2702  continue; /* ignore children here */
2703 
2704  /*
2705  * Consider only members that reference and can be computed at
2706  * child's topmost parent rel. In particular we want to exclude
2707  * parent-rel Vars that have nonempty varnullingrels. Translating
2708  * those might fail, if the transformed expression wouldn't be a
2709  * simple Var; and in any case it wouldn't produce a member that
2710  * has any use in creating plans for the child rel.
2711  */
2712  if (bms_is_subset(cur_em->em_relids, top_parent_relids) &&
2713  !bms_is_empty(cur_em->em_relids))
2714  {
2715  /* OK, generate transformed child version */
2716  Expr *child_expr;
2717  Relids new_relids;
2718 
2719  if (parent_rel->reloptkind == RELOPT_BASEREL)
2720  {
2721  /* Simple single-level transformation */
2722  child_expr = (Expr *)
2724  (Node *) cur_em->em_expr,
2725  1, &appinfo);
2726  }
2727  else
2728  {
2729  /* Must do multi-level transformation */
2730  child_expr = (Expr *)
2732  (Node *) cur_em->em_expr,
2733  child_rel,
2734  child_rel->top_parent);
2735  }
2736 
2737  /*
2738  * Transform em_relids to match. Note we do *not* do
2739  * pull_varnos(child_expr) here, as for example the
2740  * transformation might have substituted a constant, but we
2741  * don't want the child member to be marked as constant.
2742  */
2743  new_relids = bms_difference(cur_em->em_relids,
2744  top_parent_relids);
2745  new_relids = bms_add_members(new_relids, child_relids);
2746 
2747  (void) add_eq_member(cur_ec, child_expr, new_relids,
2748  cur_em->em_jdomain,
2749  cur_em, cur_em->em_datatype);
2750 
2751  /* Record this EC index for the child rel */
2752  child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
2753  }
2754  }
2755  }
2756 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:412
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:815
#define bms_is_empty(a)
Definition: bitmapset.h:118
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:829
@ RELOPT_BASEREL
Definition: pathnodes.h:817
Bitmapset * eclass_indexes
Definition: pathnodes.h:942

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

Referenced by set_append_rel_size().

◆ add_outer_joins_to_relids()

Relids add_outer_joins_to_relids ( PlannerInfo root,
Relids  input_relids,
SpecialJoinInfo sjinfo,
List **  pushed_down_joins 
)

Definition at line 801 of file joinrels.c.

804 {
805  /* Nothing to do if this isn't an outer join with an assigned relid. */
806  if (sjinfo == NULL || sjinfo->ojrelid == 0)
807  return input_relids;
808 
809  /*
810  * If it's not a left join, we have no rules that would permit executing
811  * it in non-syntactic order, so just form the syntactic relid set. (This
812  * is just a quick-exit test; we'd come to the same conclusion anyway,
813  * since its commute_below_l and commute_above_l sets must be empty.)
814  */
815  if (sjinfo->jointype != JOIN_LEFT)
816  return bms_add_member(input_relids, sjinfo->ojrelid);
817 
818  /*
819  * We cannot add the OJ relid if this join has been pushed into the RHS of
820  * a syntactically-lower left join per OJ identity 3. (If it has, then we
821  * cannot claim that its outputs represent the final state of its RHS.)
822  * There will not be any other OJs that can be added either, so we're
823  * done.
824  */
825  if (!bms_is_subset(sjinfo->commute_below_l, input_relids))
826  return input_relids;
827 
828  /* OK to add OJ's own relid */
829  input_relids = bms_add_member(input_relids, sjinfo->ojrelid);
830 
831  /*
832  * Contrariwise, if we are now forming the final result of such a commuted
833  * pair of OJs, it's time to add the relid(s) of the pushed-down join(s).
834  * We can skip this if this join was never a candidate to be pushed up.
835  */
836  if (sjinfo->commute_above_l)
837  {
838  Relids commute_above_rels = bms_copy(sjinfo->commute_above_l);
839  ListCell *lc;
840 
841  /*
842  * The current join could complete the nulling of more than one
843  * pushed-down join, so we have to examine all the SpecialJoinInfos.
844  * Because join_info_list was built in bottom-up order, it's
845  * sufficient to traverse it once: an ojrelid we add in one loop
846  * iteration would not have affected decisions of earlier iterations.
847  */
848  foreach(lc, root->join_info_list)
849  {
850  SpecialJoinInfo *othersj = (SpecialJoinInfo *) lfirst(lc);
851 
852  if (othersj == sjinfo ||
853  othersj->ojrelid == 0 || othersj->jointype != JOIN_LEFT)
854  continue; /* definitely not interesting */
855 
856  if (!bms_is_member(othersj->ojrelid, commute_above_rels))
857  continue;
858 
859  /* Add it if not already present but conditions now satisfied */
860  if (!bms_is_member(othersj->ojrelid, input_relids) &&
861  bms_is_subset(othersj->min_lefthand, input_relids) &&
862  bms_is_subset(othersj->min_righthand, input_relids) &&
863  bms_is_subset(othersj->commute_below_l, input_relids))
864  {
865  input_relids = bms_add_member(input_relids, othersj->ojrelid);
866  /* report such pushed down outer joins, if asked */
867  if (pushed_down_joins != NULL)
868  *pushed_down_joins = lappend(*pushed_down_joins, othersj);
869 
870  /*
871  * We must also check any joins that othersj potentially
872  * commutes with. They likewise must appear later in
873  * join_info_list than othersj itself, so we can visit them
874  * later in this loop.
875  */
876  commute_above_rels = bms_add_members(commute_above_rels,
877  othersj->commute_above_l);
878  }
879  }
880  }
881 
882  return input_relids;
883 }
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:510
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:122
List * lappend(List *list, void *datum)
Definition: list.c:339
@ JOIN_LEFT
Definition: nodes.h:294
#define lfirst(lc)
Definition: pg_list.h:172
Relids min_righthand
Definition: pathnodes.h:2884
Relids commute_above_l
Definition: pathnodes.h:2889
JoinType jointype
Definition: pathnodes.h:2887
Relids commute_below_l
Definition: pathnodes.h:2891
Relids min_lefthand
Definition: pathnodes.h:2883

References bms_add_member(), bms_add_members(), bms_copy(), bms_is_member(), bms_is_subset(), SpecialJoinInfo::commute_above_l, SpecialJoinInfo::commute_below_l, JOIN_LEFT, SpecialJoinInfo::jointype, lappend(), lfirst, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, SpecialJoinInfo::ojrelid, and root.

Referenced by generate_join_implied_equalities(), and make_join_rel().

◆ add_paths_to_append_rel()

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

Definition at line 1302 of file allpaths.c.

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

References accumulate_append_subpath(), add_partial_path(), add_path(), Assert, bms_equal(), RelOptInfo::cheapest_startup_path, RelOptInfo::cheapest_total_path, compare_pathkeys(), RelOptInfo::consider_parallel, RelOptInfo::consider_startup, create_append_path(), enable_parallel_append, 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, RelOptInfo::partial_pathlist, AppendPath::path, PATH_REQ_OUTER, Path::pathkeys, PATHKEYS_EQUAL, RelOptInfo::pathlist, pg_leftmost_one_pos32(), root, 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().

◆ 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 124 of file joinpath.c.

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

References bms_add_members(), bms_difference(), bms_is_subset(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), enable_hashjoin, enable_mergejoin, hash_inner_and_outer(), JoinPathExtraData::inner_unique, innerrel_is_unique(), JOIN_ANTI, JOIN_FULL, 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, root, 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().

◆ add_setop_child_rel_equivalences()

void add_setop_child_rel_equivalences ( PlannerInfo root,
RelOptInfo child_rel,
List child_tlist,
List setop_pathkeys 
)

Definition at line 2899 of file equivclass.c.

2901 {
2902  ListCell *lc;
2903  ListCell *lc2 = list_head(setop_pathkeys);
2904 
2905  foreach(lc, child_tlist)
2906  {
2907  TargetEntry *tle = lfirst_node(TargetEntry, lc);
2908  EquivalenceMember *parent_em;
2909  PathKey *pk;
2910 
2911  if (tle->resjunk)
2912  continue;
2913 
2914  if (lc2 == NULL)
2915  elog(ERROR, "too few pathkeys for set operation");
2916 
2917  pk = lfirst_node(PathKey, lc2);
2918  parent_em = linitial(pk->pk_eclass->ec_members);
2919 
2920  /*
2921  * We can safely pass the parent member as the first member in the
2922  * ec_members list as this is added first in generate_union_paths,
2923  * likewise, the JoinDomain can be that of the initial member of the
2924  * Pathkey's EquivalenceClass.
2925  */
2926  add_eq_member(pk->pk_eclass,
2927  tle->expr,
2928  child_rel->relids,
2929  parent_em->em_jdomain,
2930  parent_em,
2931  exprType((Node *) tle->expr));
2932 
2933  lc2 = lnext(setop_pathkeys, lc2);
2934  }
2935 
2936  /*
2937  * transformSetOperationStmt() ensures that the targetlist never contains
2938  * any resjunk columns, so all eclasses that exist in 'root' must have
2939  * received a new member in the loop above. Add them to the child_rel's
2940  * eclass_indexes.
2941  */
2942  child_rel->eclass_indexes = bms_add_range(child_rel->eclass_indexes, 0,
2943  list_length(root->eq_classes) - 1);
2944 }
Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper)
Definition: bitmapset.c:1019
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
#define lfirst_node(type, lc)
Definition: pg_list.h:176
static ListCell * list_head(const List *l)
Definition: pg_list.h:128
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:343
Expr * expr
Definition: primnodes.h:2192

References add_eq_member(), bms_add_range(), RelOptInfo::eclass_indexes, elog, EquivalenceMember::em_jdomain, ERROR, TargetEntry::expr, exprType(), lfirst_node, linitial, list_head(), list_length(), lnext(), RelOptInfo::relids, and root.

Referenced by build_setop_child_paths().

◆ append_pathkeys()

List* append_pathkeys ( List target,
List source 
)

Definition at line 106 of file pathkeys.c.

107 {
108  ListCell *lc;
109 
110  Assert(target != NIL);
111 
112  foreach(lc, source)
113  {
114  PathKey *pk = lfirst_node(PathKey, lc);
115 
116  if (!pathkey_is_redundant(pk, target))
117  target = lappend(target, pk);
118  }
119  return target;
120 }
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:158
static rewind_source * source
Definition: pg_rewind.c:89

References Assert, lappend(), lfirst_node, NIL, pathkey_is_redundant(), and source.

Referenced by adjust_group_pathkeys_for_groupagg(), and make_pathkeys_for_window().

◆ build_expression_pathkey()

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

Definition at line 1015 of file pathkeys.c.

1020 {
1021  List *pathkeys;
1022  Oid opfamily,
1023  opcintype;
1024  int16 strategy;
1025  PathKey *cpathkey;
1026 
1027  /* Find the operator in pg_amop --- failure shouldn't happen */
1028  if (!get_ordering_op_properties(opno,
1029  &opfamily, &opcintype, &strategy))
1030  elog(ERROR, "operator %u is not a valid ordering operator",
1031  opno);
1032 
1033  cpathkey = make_pathkey_from_sortinfo(root,
1034  expr,
1035  opfamily,
1036  opcintype,
1037  exprCollation((Node *) expr),
1038  (strategy == BTGreaterStrategyNumber),
1039  (strategy == BTGreaterStrategyNumber),
1040  0,
1041  rel,
1042  create_it);
1043 
1044  if (cpathkey)
1045  pathkeys = list_make1(cpathkey);
1046  else
1047  pathkeys = NIL;
1048 
1049  return pathkeys;
1050 }
signed short int16
Definition: c.h:493
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, int16 *strategy)
Definition: lsyscache.c:207
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:816
static PathKey * make_pathkey_from_sortinfo(PlannerInfo *root, Expr *expr, Oid opfamily, Oid opcintype, Oid collation, bool reverse_sort, bool nulls_first, Index sortref, Relids rel, bool create_it)
Definition: pathkeys.c:197
unsigned int Oid
Definition: postgres_ext.h:31
#define BTGreaterStrategyNumber
Definition: stratnum.h:33

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

Referenced by set_function_pathlist().

◆ build_index_pathkeys()

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

Definition at line 755 of file pathkeys.c.

758 {
759  List *retval = NIL;
760  ListCell *lc;
761  int i;
762 
763  if (index->sortopfamily == NULL)
764  return NIL; /* non-orderable index */
765 
766  i = 0;
767  foreach(lc, index->indextlist)
768  {
769  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
770  Expr *indexkey;
771  bool reverse_sort;
772  bool nulls_first;
773  PathKey *cpathkey;
774 
775  /*
776  * INCLUDE columns are stored in index unordered, so they don't
777  * support ordered index scan.
778  */
779  if (i >= index->nkeycolumns)
780  break;
781 
782  /* We assume we don't need to make a copy of the tlist item */
783  indexkey = indextle->expr;
784 
785  if (ScanDirectionIsBackward(scandir))
786  {
787  reverse_sort = !index->reverse_sort[i];
788  nulls_first = !index->nulls_first[i];
789  }
790  else
791  {
792  reverse_sort = index->reverse_sort[i];
793  nulls_first = index->nulls_first[i];
794  }
795 
796  /*
797  * OK, try to make a canonical pathkey for this sort key.
798  */
799  cpathkey = make_pathkey_from_sortinfo(root,
800  indexkey,
801  index->sortopfamily[i],
802  index->opcintype[i],
803  index->indexcollations[i],
804  reverse_sort,
805  nulls_first,
806  0,
807  index->rel->relids,
808  false);
809 
810  if (cpathkey)
811  {
812  /*
813  * We found the sort key in an EquivalenceClass, so it's relevant
814  * for this query. Add it to list, unless it's redundant.
815  */
816  if (!pathkey_is_redundant(cpathkey, retval))
817  retval = lappend(retval, cpathkey);
818  }
819  else
820  {
821  /*
822  * Boolean index keys might be redundant even if they do not
823  * appear in an EquivalenceClass, because of our special treatment
824  * of boolean equality conditions --- see the comment for
825  * indexcol_is_bool_constant_for_query(). If that applies, we can
826  * continue to examine lower-order index columns. Otherwise, the
827  * sort key is not an interesting sort order for this query, so we
828  * should stop considering index columns; any lower-order sort
829  * keys won't be useful either.
830  */
832  break;
833  }
834 
835  i++;
836  }
837 
838  return retval;
839 }
bool indexcol_is_bool_constant_for_query(PlannerInfo *root, IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3614
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:50
Definition: type.h:95

References TargetEntry::expr, i, indexcol_is_bool_constant_for_query(), lappend(), lfirst, make_pathkey_from_sortinfo(), NIL, pathkey_is_redundant(), root, and ScanDirectionIsBackward.

Referenced by build_index_paths().

◆ build_join_pathkeys()

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

Definition at line 1309 of file pathkeys.c.

1313 {
1314  if (jointype == JOIN_FULL ||
1315  jointype == JOIN_RIGHT ||
1316  jointype == JOIN_RIGHT_ANTI)
1317  return NIL;
1318 
1319  /*
1320  * This used to be quite a complex bit of code, but now that all pathkey
1321  * sublists start out life canonicalized, we don't have to do a darn thing
1322  * here!
1323  *
1324  * We do, however, need to truncate the pathkeys list, since it may
1325  * contain pathkeys that were useful for forming this joinrel but are
1326  * uninteresting to higher levels.
1327  */
1328  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1329 }
@ JOIN_RIGHT
Definition: nodes.h:296
@ JOIN_RIGHT_ANTI
Definition: nodes.h:309
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2215

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

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

◆ build_partition_pathkeys()

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

Definition at line 934 of file pathkeys.c.

936 {
937  List *retval = NIL;
938  PartitionScheme partscheme = partrel->part_scheme;
939  int i;
940 
941  Assert(partscheme != NULL);
942  Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
943  /* For now, we can only cope with baserels */
944  Assert(IS_SIMPLE_REL(partrel));
945 
946  for (i = 0; i < partscheme->partnatts; i++)
947  {
948  PathKey *cpathkey;
949  Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
950 
951  /*
952  * Try to make a canonical pathkey for this partkey.
953  *
954  * We assume the PartitionDesc lists any NULL partition last, so we
955  * treat the scan like a NULLS LAST index: we have nulls_first for
956  * backwards scan only.
957  */
958  cpathkey = make_pathkey_from_sortinfo(root,
959  keyCol,
960  partscheme->partopfamily[i],
961  partscheme->partopcintype[i],
962  partscheme->partcollation[i],
963  ScanDirectionIsBackward(scandir),
964  ScanDirectionIsBackward(scandir),
965  0,
966  partrel->relids,
967  false);
968 
969 
970  if (cpathkey)
971  {
972  /*
973  * We found the sort key in an EquivalenceClass, so it's relevant
974  * for this query. Add it to list, unless it's redundant.
975  */
976  if (!pathkey_is_redundant(cpathkey, retval))
977  retval = lappend(retval, cpathkey);
978  }
979  else
980  {
981  /*
982  * Boolean partition keys might be redundant even if they do not
983  * appear in an EquivalenceClass, because of our special treatment
984  * of boolean equality conditions --- see the comment for
985  * partkey_is_bool_constant_for_query(). If that applies, we can
986  * continue to examine lower-order partition keys. Otherwise, the
987  * sort key is not an interesting sort order for this query, so we
988  * should stop considering partition columns; any lower-order sort
989  * keys won't be useful either.
990  */
991  if (!partkey_is_bool_constant_for_query(partrel, i))
992  {
993  *partialkeys = true;
994  return retval;
995  }
996  }
997  }
998 
999  *partialkeys = false;
1000  return retval;
1001 }
bool partitions_are_ordered(PartitionBoundInfo boundinfo, Bitmapset *live_parts)
Definition: partbounds.c:2852
static bool partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:859
Bitmapset * live_parts
Definition: pathnodes.h:1029

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

Referenced by generate_orderedappend_paths().

◆ canonicalize_ec_expression()

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

Definition at line 472 of file equivclass.c.

473 {
474  Oid expr_type = exprType((Node *) expr);
475 
476  /*
477  * For a polymorphic-input-type opclass, just keep the same exposed type.
478  * RECORD opclasses work like polymorphic-type ones for this purpose.
479  */
480  if (IsPolymorphicType(req_type) || req_type == RECORDOID)
481  req_type = expr_type;
482 
483  /*
484  * No work if the expression exposes the right type/collation already.
485  */
486  if (expr_type != req_type ||
487  exprCollation((Node *) expr) != req_collation)
488  {
489  /*
490  * If we have to change the type of the expression, set typmod to -1,
491  * since the new type may not have the same typmod interpretation.
492  * When we only have to change collation, preserve the exposed typmod.
493  */
494  int32 req_typmod;
495 
496  if (expr_type != req_type)
497  req_typmod = -1;
498  else
499  req_typmod = exprTypmod((Node *) expr);
500 
501  /*
502  * Use applyRelabelType so that we preserve const-flatness. This is
503  * important since eval_const_expressions has already been applied.
504  */
505  expr = (Expr *) applyRelabelType((Node *) expr,
506  req_type, req_typmod, req_collation,
507  COERCE_IMPLICIT_CAST, -1, false);
508  }
509 
510  return expr;
511 }
signed int int32
Definition: c.h:494
int32 exprTypmod(const Node *expr)
Definition: nodeFuncs.c:298
Node * applyRelabelType(Node *arg, Oid rtype, int32 rtypmod, Oid rcollid, CoercionForm rformat, int rlocation, bool overwrite_ok)
Definition: nodeFuncs.c:631
@ COERCE_IMPLICIT_CAST
Definition: primnodes.h:736

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

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

◆ check_index_predicates()

void check_index_predicates ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 3244 of file indxpath.c.

3245 {
3246  List *clauselist;
3247  bool have_partial;
3248  bool is_target_rel;
3249  Relids otherrels;
3250  ListCell *lc;
3251 
3252  /* Indexes are available only on base or "other" member relations. */
3253  Assert(IS_SIMPLE_REL(rel));
3254 
3255  /*
3256  * Initialize the indrestrictinfo lists to be identical to
3257  * baserestrictinfo, and check whether there are any partial indexes. If
3258  * not, this is all we need to do.
3259  */
3260  have_partial = false;
3261  foreach(lc, rel->indexlist)
3262  {
3264 
3265  index->indrestrictinfo = rel->baserestrictinfo;
3266  if (index->indpred)
3267  have_partial = true;
3268  }
3269  if (!have_partial)
3270  return;
3271 
3272  /*
3273  * Construct a list of clauses that we can assume true for the purpose of
3274  * proving the index(es) usable. Restriction clauses for the rel are
3275  * always usable, and so are any join clauses that are "movable to" this
3276  * rel. Also, we can consider any EC-derivable join clauses (which must
3277  * be "movable to" this rel, by definition).
3278  */
3279  clauselist = list_copy(rel->baserestrictinfo);
3280 
3281  /* Scan the rel's join clauses */
3282  foreach(lc, rel->joininfo)
3283  {
3284  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3285 
3286  /* Check if clause can be moved to this rel */
3287  if (!join_clause_is_movable_to(rinfo, rel))
3288  continue;
3289 
3290  clauselist = lappend(clauselist, rinfo);
3291  }
3292 
3293  /*
3294  * Add on any equivalence-derivable join clauses. Computing the correct
3295  * relid sets for generate_join_implied_equalities is slightly tricky
3296  * because the rel could be a child rel rather than a true baserel, and in
3297  * that case we must subtract its parents' relid(s) from all_query_rels.
3298  * Additionally, we mustn't consider clauses that are only computable
3299  * after outer joins that can null the rel.
3300  */
3301  if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
3302  otherrels = bms_difference(root->all_query_rels,
3303  find_childrel_parents(root, rel));
3304  else
3305  otherrels = bms_difference(root->all_query_rels, rel->relids);
3306  otherrels = bms_del_members(otherrels, rel->nulling_relids);
3307 
3308  if (!bms_is_empty(otherrels))
3309  clauselist =
3310  list_concat(clauselist,
3312  bms_union(rel->relids,
3313  otherrels),
3314  otherrels,
3315  rel,
3316  NULL));
3317 
3318  /*
3319  * Normally we remove quals that are implied by a partial index's
3320  * predicate from indrestrictinfo, indicating that they need not be
3321  * checked explicitly by an indexscan plan using this index. However, if
3322  * the rel is a target relation of UPDATE/DELETE/MERGE/SELECT FOR UPDATE,
3323  * we cannot remove such quals from the plan, because they need to be in
3324  * the plan so that they will be properly rechecked by EvalPlanQual
3325  * testing. Some day we might want to remove such quals from the main
3326  * plan anyway and pass them through to EvalPlanQual via a side channel;
3327  * but for now, we just don't remove implied quals at all for target
3328  * relations.
3329  */
3330  is_target_rel = (bms_is_member(rel->relid, root->all_result_relids) ||
3331  get_plan_rowmark(root->rowMarks, rel->relid) != NULL);
3332 
3333  /*
3334  * Now try to prove each index predicate true, and compute the
3335  * indrestrictinfo lists for partial indexes. Note that we compute the
3336  * indrestrictinfo list even for non-predOK indexes; this might seem
3337  * wasteful, but we may be able to use such indexes in OR clauses, cf
3338  * generate_bitmap_or_paths().
3339  */
3340  foreach(lc, rel->indexlist)
3341  {
3343  ListCell *lcr;
3344 
3345  if (index->indpred == NIL)
3346  continue; /* ignore non-partial indexes here */
3347 
3348  if (!index->predOK) /* don't repeat work if already proven OK */
3349  index->predOK = predicate_implied_by(index->indpred, clauselist,
3350  false);
3351 
3352  /* If rel is an update target, leave indrestrictinfo as set above */
3353  if (is_target_rel)
3354  continue;
3355 
3356  /* Else compute indrestrictinfo as the non-implied quals */
3357  index->indrestrictinfo = NIL;
3358  foreach(lcr, rel->baserestrictinfo)
3359  {
3360  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
3361 
3362  /* predicate_implied_by() assumes first arg is immutable */
3363  if (contain_mutable_functions((Node *) rinfo->clause) ||
3365  index->indpred, false))
3366  index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
3367  }
3368  }
3369 }
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:251
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1161
bool contain_mutable_functions(Node *clause)
Definition: clauses.c:370
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
Definition: equivclass.c:1392
List * list_copy(const List *oldlist)
Definition: list.c:1573
List * list_concat(List *list1, const List *list2)
Definition: list.c:561
@ RELOPT_OTHER_MEMBER_REL
Definition: pathnodes.h:819
bool predicate_implied_by(List *predicate_list, List *clause_list, bool weak)
Definition: predtest.c:152
PlanRowMark * get_plan_rowmark(List *rowmarks, Index rtindex)
Definition: preptlist.c:509
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1521
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:584
List * baserestrictinfo
Definition: pathnodes.h:975
List * joininfo
Definition: pathnodes.h:981
Index relid
Definition: pathnodes.h:908
List * indexlist
Definition: pathnodes.h:934
Relids nulling_relids
Definition: pathnodes.h:928
Expr * clause
Definition: pathnodes.h:2553

References Assert, RelOptInfo::baserestrictinfo, bms_del_members(), 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, IS_SIMPLE_REL, join_clause_is_movable_to(), RelOptInfo::joininfo, lappend(), lfirst, list_concat(), list_copy(), list_make1, NIL, RelOptInfo::nulling_relids, predicate_implied_by(), RelOptInfo::relid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, and root.

Referenced by set_plain_rel_size(), and set_tablesample_rel_size().

◆ compare_pathkeys()

PathKeysComparison compare_pathkeys ( List keys1,
List keys2 
)

Definition at line 302 of file pathkeys.c.

303 {
304  ListCell *key1,
305  *key2;
306 
307  /*
308  * Fall out quickly if we are passed two identical lists. This mostly
309  * catches the case where both are NIL, but that's common enough to
310  * warrant the test.
311  */
312  if (keys1 == keys2)
313  return PATHKEYS_EQUAL;
314 
315  forboth(key1, keys1, key2, keys2)
316  {
317  PathKey *pathkey1 = (PathKey *) lfirst(key1);
318  PathKey *pathkey2 = (PathKey *) lfirst(key2);
319 
320  if (pathkey1 != pathkey2)
321  return PATHKEYS_DIFFERENT; /* no need to keep looking */
322  }
323 
324  /*
325  * If we reached the end of only one list, the other is longer and
326  * therefore not a subset.
327  */
328  if (key1 != NULL)
329  return PATHKEYS_BETTER1; /* key1 is longer */
330  if (key2 != NULL)
331  return PATHKEYS_BETTER2; /* key2 is longer */
332  return PATHKEYS_EQUAL;
333 }
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:518

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(), adjust_group_pathkeys_for_groupagg(), pathkeys_are_duplicate(), pathkeys_contained_in(), and set_cheapest().

◆ compute_parallel_worker()

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

Definition at line 4203 of file allpaths.c.

4205 {
4206  int parallel_workers = 0;
4207 
4208  /*
4209  * If the user has set the parallel_workers reloption, use that; otherwise
4210  * select a default number of workers.
4211  */
4212  if (rel->rel_parallel_workers != -1)
4213  parallel_workers = rel->rel_parallel_workers;
4214  else
4215  {
4216  /*
4217  * If the number of pages being scanned is insufficient to justify a
4218  * parallel scan, just return zero ... unless it's an inheritance
4219  * child. In that case, we want to generate a parallel path here
4220  * anyway. It might not be worthwhile just for this relation, but
4221  * when combined with all of its inheritance siblings it may well pay
4222  * off.
4223  */
4224  if (rel->reloptkind == RELOPT_BASEREL &&
4225  ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
4226  (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
4227  return 0;
4228 
4229  if (heap_pages >= 0)
4230  {
4231  int heap_parallel_threshold;
4232  int heap_parallel_workers = 1;
4233 
4234  /*
4235  * Select the number of workers based on the log of the size of
4236  * the relation. This probably needs to be a good deal more
4237  * sophisticated, but we need something here for now. Note that
4238  * the upper limit of the min_parallel_table_scan_size GUC is
4239  * chosen to prevent overflow here.
4240  */
4241  heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
4242  while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
4243  {
4244  heap_parallel_workers++;
4245  heap_parallel_threshold *= 3;
4246  if (heap_parallel_threshold > INT_MAX / 3)
4247  break; /* avoid overflow */
4248  }
4249 
4250  parallel_workers = heap_parallel_workers;
4251  }
4252 
4253  if (index_pages >= 0)
4254  {
4255  int index_parallel_workers = 1;
4256  int index_parallel_threshold;
4257 
4258  /* same calculation as for heap_pages above */
4259  index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
4260  while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
4261  {
4262  index_parallel_workers++;
4263  index_parallel_threshold *= 3;
4264  if (index_parallel_threshold > INT_MAX / 3)
4265  break; /* avoid overflow */
4266  }
4267 
4268  if (parallel_workers > 0)
4269  parallel_workers = Min(parallel_workers, index_parallel_workers);
4270  else
4271  parallel_workers = index_parallel_workers;
4272  }
4273  }
4274 
4275  /* In no case use more than caller supplied maximum number of workers */
4276  parallel_workers = Min(parallel_workers, max_workers);
4277 
4278  return parallel_workers;
4279 }
int min_parallel_index_scan_size
Definition: allpaths.c:82
int min_parallel_table_scan_size
Definition: allpaths.c:81
uint32 BlockNumber
Definition: block.h:31
int rel_parallel_workers
Definition: pathnodes.h:946

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

◆ convert_subquery_pathkeys()

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

Definition at line 1069 of file pathkeys.c.

1072 {
1073  List *retval = NIL;
1074  int retvallen = 0;
1075  int outer_query_keys = list_length(root->query_pathkeys);
1076  ListCell *i;
1077 
1078  foreach(i, subquery_pathkeys)
1079  {
1080  PathKey *sub_pathkey = (PathKey *) lfirst(i);
1081  EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
1082  PathKey *best_pathkey = NULL;
1083 
1084  if (sub_eclass->ec_has_volatile)
1085  {
1086  /*
1087  * If the sub_pathkey's EquivalenceClass is volatile, then it must
1088  * have come from an ORDER BY clause, and we have to match it to
1089  * that same targetlist entry.
1090  */
1091  TargetEntry *tle;
1092  Var *outer_var;
1093 
1094  if (sub_eclass->ec_sortref == 0) /* can't happen */
1095  elog(ERROR, "volatile EquivalenceClass has no sortref");
1096  tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
1097  Assert(tle);
1098  /* Is TLE actually available to the outer query? */
1099  outer_var = find_var_for_subquery_tle(rel, tle);
1100  if (outer_var)
1101  {
1102  /* We can represent this sub_pathkey */
1103  EquivalenceMember *sub_member;
1104  EquivalenceClass *outer_ec;
1105 
1106  Assert(list_length(sub_eclass->ec_members) == 1);
1107  sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
1108 
1109  /*
1110  * Note: it might look funny to be setting sortref = 0 for a
1111  * reference to a volatile sub_eclass. However, the
1112  * expression is *not* volatile in the outer query: it's just
1113  * a Var referencing whatever the subquery emitted. (IOW, the
1114  * outer query isn't going to re-execute the volatile
1115  * expression itself.) So this is okay.
1116  */
1117  outer_ec =
1119  (Expr *) outer_var,
1120  sub_eclass->ec_opfamilies,
1121  sub_member->em_datatype,
1122  sub_eclass->ec_collation,
1123  0,
1124  rel->relids,
1125  false);
1126 
1127  /*
1128  * If we don't find a matching EC, sub-pathkey isn't
1129  * interesting to the outer query
1130  */
1131  if (outer_ec)
1132  best_pathkey =
1134  outer_ec,
1135  sub_pathkey->pk_opfamily,
1136  sub_pathkey->pk_strategy,
1137  sub_pathkey->pk_nulls_first);
1138  }
1139  }
1140  else
1141  {
1142  /*
1143  * Otherwise, the sub_pathkey's EquivalenceClass could contain
1144  * multiple elements (representing knowledge that multiple items
1145  * are effectively equal). Each element might match none, one, or
1146  * more of the output columns that are visible to the outer query.
1147  * This means we may have multiple possible representations of the
1148  * sub_pathkey in the context of the outer query. Ideally we
1149  * would generate them all and put them all into an EC of the
1150  * outer query, thereby propagating equality knowledge up to the
1151  * outer query. Right now we cannot do so, because the outer
1152  * query's EquivalenceClasses are already frozen when this is
1153  * called. Instead we prefer the one that has the highest "score"
1154  * (number of EC peers, plus one if it matches the outer
1155  * query_pathkeys). This is the most likely to be useful in the
1156  * outer query.
1157  */
1158  int best_score = -1;
1159  ListCell *j;
1160 
1161  foreach(j, sub_eclass->ec_members)
1162  {
1163  EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
1164  Expr *sub_expr = sub_member->em_expr;
1165  Oid sub_expr_type = sub_member->em_datatype;
1166  Oid sub_expr_coll = sub_eclass->ec_collation;
1167  ListCell *k;
1168 
1169  if (sub_member->em_is_child)
1170  continue; /* ignore children here */
1171 
1172  foreach(k, subquery_tlist)
1173  {
1174  TargetEntry *tle = (TargetEntry *) lfirst(k);
1175  Var *outer_var;
1176  Expr *tle_expr;
1177  EquivalenceClass *outer_ec;
1178  PathKey *outer_pk;
1179  int score;
1180 
1181  /* Is TLE actually available to the outer query? */
1182  outer_var = find_var_for_subquery_tle(rel, tle);
1183  if (!outer_var)
1184  continue;
1185 
1186  /*
1187  * The targetlist entry is considered to match if it
1188  * matches after sort-key canonicalization. That is
1189  * needed since the sub_expr has been through the same
1190  * process.
1191  */
1192  tle_expr = canonicalize_ec_expression(tle->expr,
1193  sub_expr_type,
1194  sub_expr_coll);
1195  if (!equal(tle_expr, sub_expr))
1196  continue;
1197 
1198  /* See if we have a matching EC for the TLE */
1199  outer_ec = get_eclass_for_sort_expr(root,
1200  (Expr *) outer_var,
1201  sub_eclass->ec_opfamilies,
1202  sub_expr_type,
1203  sub_expr_coll,
1204  0,
1205  rel->relids,
1206  false);
1207 
1208  /*
1209  * If we don't find a matching EC, this sub-pathkey isn't
1210  * interesting to the outer query
1211  */
1212  if (!outer_ec)
1213  continue;
1214 
1215  outer_pk = make_canonical_pathkey(root,
1216  outer_ec,
1217  sub_pathkey->pk_opfamily,
1218  sub_pathkey->pk_strategy,
1219  sub_pathkey->pk_nulls_first);
1220  /* score = # of equivalence peers */
1221  score = list_length(outer_ec->ec_members) - 1;
1222  /* +1 if it matches the proper query_pathkeys item */
1223  if (retvallen < outer_query_keys &&
1224  list_nth(root->query_pathkeys, retvallen) == outer_pk)
1225  score++;
1226  if (score > best_score)
1227  {
1228  best_pathkey = outer_pk;
1229  best_score = score;
1230  }
1231  }
1232  }
1233  }
1234 
1235  /*
1236  * If we couldn't find a representation of this sub_pathkey, we're
1237  * done (we can't use the ones to its right, either).
1238  */
1239  if (!best_pathkey)
1240  break;
1241 
1242  /*
1243  * Eliminate redundant ordering info; could happen if outer query
1244  * equivalences subquery keys...
1245  */
1246  if (!pathkey_is_redundant(best_pathkey, retval))
1247  {
1248  retval = lappend(retval, best_pathkey);
1249  retvallen++;
1250  }
1251  }
1252 
1253  return retval;
1254 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:223
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:472
EquivalenceClass * get_eclass_for_sort_expr(PlannerInfo *root, Expr *expr, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
Definition: equivclass.c:587
int j
Definition: isn.c:74
static Var * find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
Definition: pathkeys.c:1266
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:55
List * ec_opfamilies
Definition: pathnodes.h:1379
bool pk_nulls_first
Definition: pathnodes.h:1467
int pk_strategy
Definition: pathnodes.h:1466
Oid pk_opfamily
Definition: pathnodes.h:1465
Definition: primnodes.h:248
TargetEntry * get_sortgroupref_tle(Index sortref, List *targetList)
Definition: tlist.c:345

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, j, lappend(), lfirst, linitial, list_length(), list_nth(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, RelOptInfo::relids, and root.

Referenced by build_setop_child_paths(), set_cte_pathlist(), and set_subquery_pathlist().

◆ create_index_paths()

void create_index_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 234 of file indxpath.c.

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

References add_path(), Assert, RelOptInfo::baserestrictinfo, 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, lappend(), RelOptInfo::lateral_relids, lfirst, list_append_unique(), list_concat(), match_eclass_clauses_to_index(), match_join_clauses_to_index(), match_restriction_clauses_to_index(), MemSet, NIL, IndexClauseSet::nonempty, PATH_REQ_OUTER, RelOptInfo::relid, and root.

Referenced by set_plain_rel_pathlist().

◆ create_partial_bitmap_paths()

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

Definition at line 4167 of file allpaths.c.

4169 {
4170  int parallel_workers;
4171  double pages_fetched;
4172 
4173  /* Compute heap pages for bitmap heap scan */
4174  pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
4175  NULL, NULL);
4176 
4177  parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
4179 
4180  if (parallel_workers <= 0)
4181  return;
4182 
4184  bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
4185 }
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:4203
double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, double loop_count, Cost *cost_p, double *tuples_p)
Definition: costsize.c:6403

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

Referenced by create_index_paths().

◆ create_tidscan_paths()

void create_tidscan_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 487 of file tidpath.c.

488 {
489  List *tidquals;
490  List *tidrangequals;
491 
492  /*
493  * If any suitable quals exist in the rel's baserestrict list, generate a
494  * plain (unparameterized) TidPath with them.
495  */
496  tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel);
497 
498  if (tidquals != NIL)
499  {
500  /*
501  * This path uses no join clauses, but it could still have required
502  * parameterization due to LATERAL refs in its tlist.
503  */
504  Relids required_outer = rel->lateral_relids;
505 
506  add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
507  required_outer));
508  }
509 
510  /*
511  * If there are range quals in the baserestrict list, generate a
512  * TidRangePath.
513  */
515  rel);
516 
517  if (tidrangequals != NIL)
518  {
519  /*
520  * This path uses no join clauses, but it could still have required
521  * parameterization due to LATERAL refs in its tlist.
522  */
523  Relids required_outer = rel->lateral_relids;
524 
526  tidrangequals,
527  required_outer));
528  }
529 
530  /*
531  * Try to generate parameterized TidPaths using equality clauses extracted
532  * from EquivalenceClasses. (This is important since simple "t1.ctid =
533  * t2.ctid" clauses will turn into ECs.)
534  */
535  if (rel->has_eclass_joins)
536  {
537  List *clauses;
538 
539  /* Generate clauses, skipping any that join to lateral_referencers */
541  rel,
543  NULL,
544  rel->lateral_referencers);
545 
546  /* Generate a path for each usable join clause */
547  BuildParameterizedTidPaths(root, rel, clauses);
548  }
549 
550  /*
551  * Also consider parameterized TidPaths using "loose" join quals. Quals
552  * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
553  * join quals, for example.
554  */
556 }
List * generate_implied_equalities_for_column(PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
Definition: equivclass.c:2971
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1179
TidRangePath * create_tidrangescan_path(PlannerInfo *root, RelOptInfo *rel, List *tidrangequals, Relids required_outer)
Definition: pathnode.c:1208
Relids lateral_referencers
Definition: pathnodes.h:932
bool has_eclass_joins
Definition: pathnodes.h:983
static void BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
Definition: tidpath.c:415
static List * TidQualFromRestrictInfoList(PlannerInfo *root, List *rlist, RelOptInfo *rel)
Definition: tidpath.c:280
static List * TidRangeQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
Definition: tidpath.c:387
static bool ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)
Definition: tidpath.c:470

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, root, TidQualFromRestrictInfoList(), and TidRangeQualFromRestrictInfoList().

Referenced by set_plain_rel_pathlist().

◆ eclass_useful_for_merging()

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

Definition at line 3223 of file equivclass.c.

3226 {
3227  Relids relids;
3228  ListCell *lc;
3229 
3230  Assert(!eclass->ec_merged);
3231 
3232  /*
3233  * Won't generate joinclauses if const or single-member (the latter test
3234  * covers the volatile case too)
3235  */
3236  if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
3237  return false;
3238 
3239  /*
3240  * Note we don't test ec_broken; if we did, we'd need a separate code path
3241  * to look through ec_sources. Checking the members anyway is OK as a
3242  * possibly-overoptimistic heuristic.
3243  */
3244 
3245  /* If specified rel is a child, we must consider the topmost parent rel */
3246  if (IS_OTHER_REL(rel))
3247  {
3249  relids = rel->top_parent_relids;
3250  }
3251  else
3252  relids = rel->relids;
3253 
3254  /* If rel already includes all members of eclass, no point in searching */
3255  if (bms_is_subset(eclass->ec_relids, relids))
3256  return false;
3257 
3258  /* To join, we need a member not in the given rel */
3259  foreach(lc, eclass->ec_members)
3260  {
3261  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
3262 
3263  if (cur_em->em_is_child)
3264  continue; /* ignore children here */
3265 
3266  if (!bms_overlap(cur_em->em_relids, relids))
3267  return true;
3268  }
3269 
3270  return false;
3271 }
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:844
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:500

References Assert, bms_is_empty, bms_is_subset(), bms_overlap(), eclass(), 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().

◆ exprs_known_equal()

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

Definition at line 2465 of file equivclass.c.

2466 {
2467  ListCell *lc1;
2468 
2469  foreach(lc1, root->eq_classes)
2470  {
2471  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2472  bool item1member = false;
2473  bool item2member = false;
2474  ListCell *lc2;
2475 
2476  /* Never match to a volatile EC */
2477  if (ec->ec_has_volatile)
2478  continue;
2479 
2480  foreach(lc2, ec->ec_members)
2481  {
2483 
2484  if (em->em_is_child)
2485  continue; /* ignore children here */
2486  if (equal(item1, em->em_expr))
2487  item1member = true;
2488  else if (equal(item2, em->em_expr))
2489  item2member = true;
2490  /* Exit as soon as equality is proven */
2491  if (item1member && item2member)
2492  return true;
2493  }
2494  }
2495  return false;
2496 }

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

Referenced by add_unique_group_var().

◆ find_computable_ec_member()

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

Definition at line 836 of file equivclass.c.

841 {
842  ListCell *lc;
843 
844  foreach(lc, ec->ec_members)
845  {
847  List *exprvars;
848  ListCell *lc2;
849 
850  /*
851  * We shouldn't be trying to sort by an equivalence class that
852  * contains a constant, so no need to consider such cases any further.
853  */
854  if (em->em_is_const)
855  continue;
856 
857  /*
858  * Ignore child members unless they belong to the requested rel.
859  */
860  if (em->em_is_child &&
861  !bms_is_subset(em->em_relids, relids))
862  continue;
863 
864  /*
865  * Match if all Vars and quasi-Vars are available in "exprs".
866  */
867  exprvars = pull_var_clause((Node *) em->em_expr,
871  foreach(lc2, exprvars)
872  {
873  if (!is_exprlist_member(lfirst(lc2), exprs))
874  break;
875  }
876  list_free(exprvars);
877  if (lc2)
878  continue; /* we hit a non-available Var */
879 
880  /*
881  * If requested, reject expressions that are not parallel-safe. We
882  * check this last because it's a rather expensive test.
883  */
884  if (require_parallel_safe &&
885  !is_parallel_safe(root, (Node *) em->em_expr))
886  continue;
887 
888  return em; /* found usable expression */
889  }
890 
891  return NULL;
892 }
bool is_parallel_safe(PlannerInfo *root, Node *node)
Definition: clauses.c:753
static bool is_exprlist_member(Expr *node, List *exprs)
Definition: equivclass.c:902
void list_free(List *list)
Definition: list.c:1546
#define PVC_INCLUDE_WINDOWFUNCS
Definition: optimizer.h:188
#define PVC_INCLUDE_PLACEHOLDERS
Definition: optimizer.h:190
#define PVC_INCLUDE_AGGREGATES
Definition: optimizer.h:186
List * pull_var_clause(Node *node, int flags)
Definition: var.c:607

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, PVC_INCLUDE_WINDOWFUNCS, and root.

Referenced by prepare_sort_from_pathkeys(), and relation_can_be_sorted_early().

◆ find_derived_clause_for_ec_member()

RestrictInfo* find_derived_clause_for_ec_member ( EquivalenceClass ec,
EquivalenceMember em 
)

Definition at line 2607 of file equivclass.c.

2609 {
2610  ListCell *lc;
2611 
2612  Assert(ec->ec_has_const);
2613  Assert(!em->em_is_const);
2614  foreach(lc, ec->ec_derives)
2615  {
2616  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2617 
2618  /*
2619  * generate_base_implied_equalities_const will have put non-const
2620  * members on the left side of derived clauses.
2621  */
2622  if (rinfo->left_em == em)
2623  return rinfo;
2624  }
2625  return NULL;
2626 }

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

Referenced by get_foreign_key_join_selectivity().

◆ find_ec_member_matching_expr()

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

Definition at line 771 of file equivclass.c.

774 {
775  ListCell *lc;
776 
777  /* We ignore binary-compatible relabeling on both ends */
778  while (expr && IsA(expr, RelabelType))
779  expr = ((RelabelType *) expr)->arg;
780 
781  foreach(lc, ec->ec_members)
782  {
784  Expr *emexpr;
785 
786  /*
787  * We shouldn't be trying to sort by an equivalence class that
788  * contains a constant, so no need to consider such cases any further.
789  */
790  if (em->em_is_const)
791  continue;
792 
793  /*
794  * Ignore child members unless they belong to the requested rel.
795  */
796  if (em->em_is_child &&
797  !bms_is_subset(em->em_relids, relids))
798  continue;
799 
800  /*
801  * Match if same expression (after stripping relabel).
802  */
803  emexpr = em->em_expr;
804  while (emexpr && IsA(emexpr, RelabelType))
805  emexpr = ((RelabelType *) emexpr)->arg;
806 
807  if (equal(emexpr, expr))
808  return em;
809  }
810 
811  return NULL;
812 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
void * arg

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

◆ find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1527 of file pathkeys.c.

1530 {
1531  List *mergeclauses = NIL;
1532  ListCell *i;
1533 
1534  /* make sure we have eclasses cached in the clauses */
1535  foreach(i, restrictinfos)
1536  {
1537  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1538 
1540  }
1541 
1542  foreach(i, pathkeys)
1543  {
1544  PathKey *pathkey = (PathKey *) lfirst(i);
1545  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1546  List *matched_restrictinfos = NIL;
1547  ListCell *j;
1548 
1549  /*----------
1550  * A mergejoin clause matches a pathkey if it has the same EC.
1551  * If there are multiple matching clauses, take them all. In plain
1552  * inner-join scenarios we expect only one match, because
1553  * equivalence-class processing will have removed any redundant
1554  * mergeclauses. However, in outer-join scenarios there might be
1555  * multiple matches. An example is
1556  *
1557  * select * from a full join b
1558  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1559  *
1560  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1561  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1562  * we *must* do so or we will be unable to form a valid plan.
1563  *
1564  * We expect that the given pathkeys list is canonical, which means
1565  * no two members have the same EC, so it's not possible for this
1566  * code to enter the same mergeclause into the result list twice.
1567  *
1568  * It's possible that multiple matching clauses might have different
1569  * ECs on the other side, in which case the order we put them into our
1570  * result makes a difference in the pathkeys required for the inner
1571  * input rel. However this routine hasn't got any info about which
1572  * order would be best, so we don't worry about that.
1573  *
1574  * It's also possible that the selected mergejoin clauses produce
1575  * a noncanonical ordering of pathkeys for the inner side, ie, we
1576  * might select clauses that reference b.v1, b.v2, b.v1 in that
1577  * order. This is not harmful in itself, though it suggests that
1578  * the clauses are partially redundant. Since the alternative is
1579  * to omit mergejoin clauses and thereby possibly fail to generate a
1580  * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1581  * has to delete duplicates when it constructs the inner pathkeys
1582  * list, and we also have to deal with such cases specially in
1583  * create_mergejoin_plan().
1584  *----------
1585  */
1586  foreach(j, restrictinfos)
1587  {
1588  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1589  EquivalenceClass *clause_ec;
1590 
1591  clause_ec = rinfo->outer_is_left ?
1592  rinfo->left_ec : rinfo->right_ec;
1593  if (clause_ec == pathkey_ec)
1594  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1595  }
1596 
1597  /*
1598  * If we didn't find a mergeclause, we're done --- any additional
1599  * sort-key positions in the pathkeys are useless. (But we can still
1600  * mergejoin if we found at least one mergeclause.)
1601  */
1602  if (matched_restrictinfos == NIL)
1603  break;
1604 
1605  /*
1606  * If we did find usable mergeclause(s) for this sort-key position,
1607  * add them to result list.
1608  */
1609  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1610  }
1611 
1612  return mergeclauses;
1613 }
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1493

References i, j, lappend(), lfirst, list_concat(), NIL, root, and update_mergeclause_eclasses().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

◆ generate_base_implied_equalities()

void generate_base_implied_equalities ( PlannerInfo root)

Definition at line 1044 of file equivclass.c.

1045 {
1046  int ec_index;
1047  ListCell *lc;
1048 
1049  /*
1050  * At this point, we're done absorbing knowledge of equivalences in the
1051  * query, so no further EC merging should happen, and ECs remaining in the
1052  * eq_classes list can be considered canonical. (But note that it's still
1053  * possible for new single-member ECs to be added through
1054  * get_eclass_for_sort_expr().)
1055  */
1056  root->ec_merging_done = true;
1057 
1058  ec_index = 0;
1059  foreach(lc, root->eq_classes)
1060  {
1062  bool can_generate_joinclause = false;
1063  int i;
1064 
1065  Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
1066  Assert(!ec->ec_broken); /* not yet anyway... */
1067 
1068  /*
1069  * Generate implied equalities that are restriction clauses.
1070  * Single-member ECs won't generate any deductions, either here or at
1071  * the join level.
1072  */
1073  if (list_length(ec->ec_members) > 1)
1074  {
1075  if (ec->ec_has_const)
1077  else
1079 
1080  /* Recover if we failed to generate required derived clauses */
1081  if (ec->ec_broken)
1083 
1084  /* Detect whether this EC might generate join clauses */
1085  can_generate_joinclause =
1087  }
1088 
1089  /*
1090  * Mark the base rels cited in each eclass (which should all exist by
1091  * now) with the eq_classes indexes of all eclasses mentioning them.
1092  * This will let us avoid searching in subsequent lookups. While
1093  * we're at it, we can mark base rels that have pending eclass joins;
1094  * this is a cheap version of has_relevant_eclass_joinclause().
1095  */
1096  i = -1;
1097  while ((i = bms_next_member(ec->ec_relids, i)) > 0)
1098  {
1099  RelOptInfo *rel = root->simple_rel_array[i];
1100 
1101  if (rel == NULL) /* must be an outer join */
1102  {
1103  Assert(bms_is_member(i, root->outer_join_rels));
1104  continue;
1105  }
1106 
1107  Assert(rel->reloptkind == RELOPT_BASEREL);
1108 
1110  ec_index);
1111 
1112  if (can_generate_joinclause)
1113  rel->has_eclass_joins = true;
1114  }
1115 
1116  ec_index++;
1117  }
1118 }
static void generate_base_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1329
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1219
static void generate_base_implied_equalities_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1124
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:1392

References Assert, bms_add_member(), bms_is_member(), bms_membership(), BMS_MULTIPLE, bms_next_member(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, 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 root.

Referenced by query_planner().

◆ generate_gather_paths()

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

Definition at line 3052 of file allpaths.c.

3053 {
3054  Path *cheapest_partial_path;
3055  Path *simple_gather_path;
3056  ListCell *lc;
3057  double rows;
3058  double *rowsp = NULL;
3059 
3060  /* If there are no partial paths, there's nothing to do here. */
3061  if (rel->partial_pathlist == NIL)
3062  return;
3063 
3064  /* Should we override the rel's rowcount estimate? */
3065  if (override_rows)
3066  rowsp = &rows;
3067 
3068  /*
3069  * The output of Gather is always unsorted, so there's only one partial
3070  * path of interest: the cheapest one. That will be the one at the front
3071  * of partial_pathlist because of the way add_partial_path works.
3072  */
3073  cheapest_partial_path = linitial(rel->partial_pathlist);
3074  rows =
3075  cheapest_partial_path->rows * cheapest_partial_path->parallel_workers;
3076  simple_gather_path = (Path *)
3077  create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
3078  NULL, rowsp);
3079  add_path(rel, simple_gather_path);
3080 
3081  /*
3082  * For each useful ordering, we can consider an order-preserving Gather
3083  * Merge.
3084  */
3085  foreach(lc, rel->partial_pathlist)
3086  {
3087  Path *subpath = (Path *) lfirst(lc);
3088  GatherMergePath *path;
3089 
3090  if (subpath->pathkeys == NIL)
3091  continue;
3092 
3093  rows = subpath->rows * subpath->parallel_workers;
3094  path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
3095  subpath->pathkeys, NULL, rowsp);
3096  add_path(rel, &path->path);
3097  }
3098 }
GatherMergePath * create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, List *pathkeys, Relids required_outer, double *rows)
Definition: pathnode.c:1881
GatherPath * create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, Relids required_outer, double *rows)
Definition: pathnode.c:1972
struct PathTarget * reltarget
Definition: pathnodes.h:883

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

Referenced by generate_useful_gather_paths().

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

2976 {
2977  List *result = NIL;
2978  bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
2979  Relids parent_relids;
2980  int i;
2981 
2982  /* Should be OK to rely on eclass_indexes */
2983  Assert(root->ec_merging_done);
2984 
2985  /* Indexes are available only on base or "other" member relations. */
2986  Assert(IS_SIMPLE_REL(rel));
2987 
2988  /* If it's a child rel, we'll need to know what its parent(s) are */
2989  if (is_child_rel)
2990  parent_relids = find_childrel_parents(root, rel);
2991  else
2992  parent_relids = NULL; /* not used, but keep compiler quiet */
2993 
2994  i = -1;
2995  while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
2996  {
2997  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2998  EquivalenceMember *cur_em;
2999  ListCell *lc2;
3000 
3001  /* Sanity check eclass_indexes only contain ECs for rel */
3002  Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
3003 
3004  /*
3005  * Won't generate joinclauses if const or single-member (the latter
3006  * test covers the volatile case too)
3007  */
3008  if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
3009  continue;
3010 
3011  /*
3012  * Scan members, looking for a match to the target column. Note that
3013  * child EC members are considered, but only when they belong to the
3014  * target relation. (Unlike regular members, the same expression
3015  * could be a child member of more than one EC. Therefore, it's
3016  * potentially order-dependent which EC a child relation's target
3017  * column gets matched to. This is annoying but it only happens in
3018  * corner cases, so for now we live with just reporting the first
3019  * match. See also get_eclass_for_sort_expr.)
3020  */
3021  cur_em = NULL;
3022  foreach(lc2, cur_ec->ec_members)
3023  {
3024  cur_em = (EquivalenceMember *) lfirst(lc2);
3025  if (bms_equal(cur_em->em_relids, rel->relids) &&
3026  callback(root, rel, cur_ec, cur_em, callback_arg))
3027  break;
3028  cur_em = NULL;
3029  }
3030 
3031  if (!cur_em)
3032  continue;
3033 
3034  /*
3035  * Found our match. Scan the other EC members and attempt to generate
3036  * joinclauses.
3037  */
3038  foreach(lc2, cur_ec->ec_members)
3039  {
3040  EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
3041  Oid eq_op;
3042  RestrictInfo *rinfo;
3043 
3044  if (other_em->em_is_child)
3045  continue; /* ignore children here */
3046 
3047  /* Make sure it'll be a join to a different rel */
3048  if (other_em == cur_em ||
3049  bms_overlap(other_em->em_relids, rel->relids))
3050  continue;
3051 
3052  /* Forget it if caller doesn't want joins to this rel */
3053  if (bms_overlap(other_em->em_relids, prohibited_rels))
3054  continue;
3055 
3056  /*
3057  * Also, if this is a child rel, avoid generating a useless join
3058  * to its parent rel(s).
3059  */
3060  if (is_child_rel &&
3061  bms_overlap(parent_relids, other_em->em_relids))
3062  continue;
3063 
3064  eq_op = select_equality_operator(cur_ec,
3065  cur_em->em_datatype,
3066  other_em->em_datatype);
3067  if (!OidIsValid(eq_op))
3068  continue;
3069 
3070  /* set parent_ec to mark as redundant with other joinclauses */
3071  rinfo = create_join_clause(root, cur_ec, eq_op,
3072  cur_em, other_em,
3073  cur_ec);
3074 
3075  result = lappend(result, rinfo);
3076  }
3077 
3078  /*
3079  * If somehow we failed to create any join clauses, we might as well
3080  * keep scanning the ECs for another match. But if we did make any,
3081  * we're done, because we don't want to return non-redundant clauses.
3082  */
3083  if (result)
3084  break;
3085  }
3086 
3087  return result;
3088 }
#define OidIsValid(objectId)
Definition: c.h:775
static RestrictInfo * create_join_clause(PlannerInfo *root, EquivalenceClass *ec, Oid opno, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
Definition: equivclass.c:1824
static Oid select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
Definition: equivclass.c:1788
static void callback(struct sockaddr *addr, struct sockaddr *mask, void *unused)
Definition: test_ifaddrs.c:46

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

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

◆ generate_join_implied_equalities()

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

Definition at line 1392 of file equivclass.c.

1397 {
1398  List *result = NIL;
1399  Relids inner_relids = inner_rel->relids;
1400  Relids nominal_inner_relids;
1401  Relids nominal_join_relids;
1402  Bitmapset *matching_ecs;
1403  int i;
1404 
1405  /* If inner rel is a child, extra setup work is needed */
1406  if (IS_OTHER_REL(inner_rel))
1407  {
1408  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1409 
1410  /* Fetch relid set for the topmost parent rel */
1411  nominal_inner_relids = inner_rel->top_parent_relids;
1412  /* ECs will be marked with the parent's relid, not the child's */
1413  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1414  nominal_join_relids = add_outer_joins_to_relids(root,
1415  nominal_join_relids,
1416  sjinfo,
1417  NULL);
1418  }
1419  else
1420  {
1421  nominal_inner_relids = inner_relids;
1422  nominal_join_relids = join_relids;
1423  }
1424 
1425  /*
1426  * Examine all potentially-relevant eclasses.
1427  *
1428  * If we are considering an outer join, we must include "join" clauses
1429  * that mention either input rel plus the outer join's relid; these
1430  * represent post-join filter clauses that have to be applied at this
1431  * join. We don't have infrastructure that would let us identify such
1432  * eclasses cheaply, so just fall back to considering all eclasses
1433  * mentioning anything in nominal_join_relids.
1434  *
1435  * At inner joins, we can be smarter: only consider eclasses mentioning
1436  * both input rels.
1437  */
1438  if (sjinfo && sjinfo->ojrelid != 0)
1439  matching_ecs = get_eclass_indexes_for_relids(root, nominal_join_relids);
1440  else
1441  matching_ecs = get_common_eclass_indexes(root, nominal_inner_relids,
1442  outer_relids);
1443 
1444  i = -1;
1445  while ((i = bms_next_member(matching_ecs, i)) >= 0)
1446  {
1447  EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
1448  List *sublist = NIL;
1449 
1450  /* ECs containing consts do not need any further enforcement */
1451  if (ec->ec_has_const)
1452  continue;
1453 
1454  /* Single-member ECs won't generate any deductions */
1455  if (list_length(ec->ec_members) <= 1)
1456  continue;
1457 
1458  /* Sanity check that this eclass overlaps the join */
1459  Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
1460 
1461  if (!ec->ec_broken)
1463  ec,
1464  join_relids,
1465  outer_relids,
1466  inner_relids);
1467 
1468  /* Recover if we failed to generate required derived clauses */
1469  if (ec->ec_broken)
1471  ec,
1472  nominal_join_relids,
1473  outer_relids,
1474  nominal_inner_relids,
1475  inner_rel);
1476 
1477  result = list_concat(result, sublist);
1478  }
1479 
1480  return result;
1481 }
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1563
static Bitmapset * get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
Definition: equivclass.c:3374
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:1739
Relids add_outer_joins_to_relids(PlannerInfo *root, Relids input_relids, SpecialJoinInfo *sjinfo, List **pushed_down_joins)
Definition: joinrels.c:801

References add_outer_joins_to_relids(), Assert, bms_is_empty, bms_next_member(), 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(), get_common_eclass_indexes(), get_eclass_indexes_for_relids(), i, IS_OTHER_REL, list_concat(), list_length(), list_nth(), NIL, SpecialJoinInfo::ojrelid, RelOptInfo::relids, root, and RelOptInfo::top_parent_relids.

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

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

1497 {
1498  List *result = NIL;
1499  Relids inner_relids = inner_rel->relids;
1500  Relids nominal_inner_relids;
1501  Relids nominal_join_relids;
1502  ListCell *lc;
1503 
1504  /* If inner rel is a child, extra setup work is needed */
1505  if (IS_OTHER_REL(inner_rel))
1506  {
1507  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1508 
1509  /* Fetch relid set for the topmost parent rel */
1510  nominal_inner_relids = inner_rel->top_parent_relids;
1511  /* ECs will be marked with the parent's relid, not the child's */
1512  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1513  }
1514  else
1515  {
1516  nominal_inner_relids = inner_relids;
1517  nominal_join_relids = join_relids;
1518  }
1519 
1520  foreach(lc, eclasses)
1521  {
1523  List *sublist = NIL;
1524 
1525  /* ECs containing consts do not need any further enforcement */
1526  if (ec->ec_has_const)
1527  continue;
1528 
1529  /* Single-member ECs won't generate any deductions */
1530  if (list_length(ec->ec_members) <= 1)
1531  continue;
1532 
1533  /* We can quickly ignore any that don't overlap the join, too */
1534  if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1535  continue;
1536 
1537  if (!ec->ec_broken)
1539  ec,
1540  join_relids,
1541  outer_relids,
1542  inner_relids);
1543 
1544  /* Recover if we failed to generate required derived clauses */
1545  if (ec->ec_broken)
1547  ec,
1548  nominal_join_relids,
1549  outer_relids,
1550  nominal_inner_relids,
1551  inner_rel);
1552 
1553  result = list_concat(result, sublist);
1554  }
1555 
1556  return result;
1557 }

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, root, and RelOptInfo::top_parent_relids.

Referenced by get_joinrel_parampathinfo().

◆ generate_partitionwise_join_paths()

void generate_partitionwise_join_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 4291 of file allpaths.c.

4292 {
4293  List *live_children = NIL;
4294  int cnt_parts;
4295  int num_parts;
4296  RelOptInfo **part_rels;
4297 
4298  /* Handle only join relations here. */
4299  if (!IS_JOIN_REL(rel))
4300  return;
4301 
4302  /* We've nothing to do if the relation is not partitioned. */
4303  if (!IS_PARTITIONED_REL(rel))
4304  return;
4305 
4306  /* The relation should have consider_partitionwise_join set. */
4308 
4309  /* Guard against stack overflow due to overly deep partition hierarchy. */
4311 
4312  num_parts = rel->nparts;
4313  part_rels = rel->part_rels;
4314 
4315  /* Collect non-dummy child-joins. */
4316  for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
4317  {
4318  RelOptInfo *child_rel = part_rels[cnt_parts];
4319 
4320  /* If it's been pruned entirely, it's certainly dummy. */
4321  if (child_rel == NULL)
4322  continue;
4323 
4324  /* Make partitionwise join paths for this partitioned child-join. */
4326 
4327  /* If we failed to make any path for this child, we must give up. */
4328  if (child_rel->pathlist == NIL)
4329  {
4330  /*
4331  * Mark the parent joinrel as unpartitioned so that later
4332  * functions treat it correctly.
4333  */
4334  rel->nparts = 0;
4335  return;
4336  }
4337 
4338  /* Else, identify the cheapest path for it. */
4339  set_cheapest(child_rel);
4340 
4341  /* Dummy children need not be scanned, so ignore those. */
4342  if (IS_DUMMY_REL(child_rel))
4343  continue;
4344 
4345 #ifdef OPTIMIZER_DEBUG
4346  pprint(child_rel);
4347 #endif
4348 
4349  live_children = lappend(live_children, child_rel);
4350  }
4351 
4352  /* If all child-joins are dummy, parent join is also dummy. */
4353  if (!live_children)
4354  {
4355  mark_dummy_rel(rel);
4356  return;
4357  }
4358 
4359  /* Build additional paths for this rel from child-join paths. */
4360  add_paths_to_append_rel(root, rel, live_children);
4361  list_free(live_children);
4362 }
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:4291
void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
Definition: allpaths.c:1302
void pprint(const void *obj)
Definition: print.c:54
void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1381
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:242
#define IS_DUMMY_REL(r)
Definition: pathnodes.h:1935
#define IS_PARTITIONED_REL(rel)
Definition: pathnodes.h:1052
void check_stack_depth(void)
Definition: postgres.c:3531
bool consider_partitionwise_join
Definition: pathnodes.h:989

References add_paths_to_append_rel(), Assert, check_stack_depth(), RelOptInfo::consider_partitionwise_join, IS_DUMMY_REL, IS_JOIN_REL, IS_PARTITIONED_REL, lappend(), list_free(), mark_dummy_rel(), NIL, RelOptInfo::nparts, RelOptInfo::pathlist, pprint(), root, and set_cheapest().

Referenced by merge_clump(), and standard_join_search().

◆ generate_useful_gather_paths()

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

Definition at line 3190 of file allpaths.c.

3191 {
3192  ListCell *lc;
3193  double rows;
3194  double *rowsp = NULL;
3195  List *useful_pathkeys_list = NIL;
3196  Path *cheapest_partial_path = NULL;
3197 
3198  /* If there are no partial paths, there's nothing to do here. */
3199  if (rel->partial_pathlist == NIL)
3200  return;
3201 
3202  /* Should we override the rel's rowcount estimate? */
3203  if (override_rows)
3204  rowsp = &rows;
3205 
3206  /* generate the regular gather (merge) paths */
3207  generate_gather_paths(root, rel, override_rows);
3208 
3209  /* consider incremental sort for interesting orderings */
3210  useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
3211 
3212  /* used for explicit (full) sort paths */
3213  cheapest_partial_path = linitial(rel->partial_pathlist);
3214 
3215  /*
3216  * Consider sorted paths for each interesting ordering. We generate both
3217  * incremental and full sort.
3218  */
3219  foreach(lc, useful_pathkeys_list)
3220  {
3221  List *useful_pathkeys = lfirst(lc);
3222  ListCell *lc2;
3223  bool is_sorted;
3224  int presorted_keys;
3225 
3226  foreach(lc2, rel->partial_pathlist)
3227  {
3228  Path *subpath = (Path *) lfirst(lc2);
3229  GatherMergePath *path;
3230 
3231  is_sorted = pathkeys_count_contained_in(useful_pathkeys,
3232  subpath->pathkeys,
3233  &presorted_keys);
3234 
3235  /*
3236  * We don't need to consider the case where a subpath is already
3237  * fully sorted because generate_gather_paths already creates a
3238  * gather merge path for every subpath that has pathkeys present.
3239  *
3240  * But since the subpath is already sorted, we know we don't need
3241  * to consider adding a sort (full or incremental) on top of it,
3242  * so we can continue here.
3243  */
3244  if (is_sorted)
3245  continue;
3246 
3247  /*
3248  * Try at least sorting the cheapest path and also try
3249  * incrementally sorting any path which is partially sorted
3250  * already (no need to deal with paths which have presorted keys
3251  * when incremental sort is disabled unless it's the cheapest
3252  * input path).
3253  */
3254  if (subpath != cheapest_partial_path &&
3255  (presorted_keys == 0 || !enable_incremental_sort))
3256  continue;
3257 
3258  /*
3259  * Consider regular sort for any path that's not presorted or if
3260  * incremental sort is disabled. We've no need to consider both
3261  * sort and incremental sort on the same path. We assume that
3262  * incremental sort is always faster when there are presorted
3263  * keys.
3264  *
3265  * This is not redundant with the gather paths created in
3266  * generate_gather_paths, because that doesn't generate ordered
3267  * output. Here we add an explicit sort to match the useful
3268  * ordering.
3269  */
3270  if (presorted_keys == 0 || !enable_incremental_sort)
3271  {
3273  rel,
3274  subpath,
3275  useful_pathkeys,
3276  -1.0);
3277  rows = subpath->rows * subpath->parallel_workers;
3278  }
3279  else
3281  rel,
3282  subpath,
3283  useful_pathkeys,
3284  presorted_keys,
3285  -1);
3286  path = create_gather_merge_path(root, rel,
3287  subpath,
3288  rel->reltarget,
3289  subpath->pathkeys,
3290  NULL,
3291  rowsp);
3292 
3293  add_path(rel, &path->path);
3294  }
3295  }
3296 }
void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:3052
static List * get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel, bool require_parallel_safe)
Definition: allpaths.c:3122
bool enable_incremental_sort
Definition: costsize.c:140
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:573
SortPath * create_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, double limit_tuples)
Definition: pathnode.c:3000
IncrementalSortPath * create_incremental_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, int presorted_keys, double limit_tuples)
Definition: pathnode.c:2951

References add_path(), create_gather_merge_path(), create_incremental_sort_path(), create_sort_path(), enable_incremental_sort, generate_gather_paths(), get_useful_pathkeys_for_relation(), lfirst, linitial, NIL, RelOptInfo::partial_pathlist, GatherMergePath::path, pathkeys_count_contained_in(), RelOptInfo::reltarget, root, and subpath().

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

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

685 {
686  Path *matched_path = NULL;
687  ListCell *l;
688 
689  foreach(l, paths)
690  {
691  Path *path = (Path *) lfirst(l);
692 
693  /*
694  * Since cost comparison is a lot cheaper than pathkey comparison, do
695  * that first. (XXX is that still true?)
696  */
697  if (matched_path != NULL &&
698  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
699  continue;
700 
701  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
702  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
703  matched_path = path;
704  }
705  return matched_path;
706 }
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:341
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:115

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

Referenced by build_minmax_path(), and generate_orderedappend_paths().

◆ get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner ( List paths)

Definition at line 714 of file pathkeys.c.

715 {
716  ListCell *l;
717 
718  foreach(l, paths)
719  {
720  Path *innerpath = (Path *) lfirst(l);
721 
722  if (innerpath->parallel_safe &&
723  bms_is_empty(PATH_REQ_OUTER(innerpath)))
724  return innerpath;
725  }
726 
727  return NULL;
728 }
bool parallel_safe
Definition: pathnodes.h:1644

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

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

639 {
640  Path *matched_path = NULL;
641  ListCell *l;
642 
643  foreach(l, paths)
644  {
645  Path *path = (Path *) lfirst(l);
646 
647  /* If required, reject paths that are not parallel-safe */
648  if (require_parallel_safe && !path->parallel_safe)
649  continue;
650 
651  /*
652  * Since cost comparison is a lot cheaper than pathkey comparison, do
653  * that first. (XXX is that still true?)
654  */
655  if (matched_path != NULL &&
656  compare_path_costs(matched_path, path, cost_criterion) <= 0)
657  continue;
658 
659  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
660  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
661  matched_path = path;
662  }
663  return matched_path;
664 }
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:69

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(), generate_union_paths(), and get_cheapest_parameterized_child_path().

◆ get_eclass_for_sort_expr()

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

Definition at line 587 of file equivclass.c.

595 {
596  JoinDomain *jdomain;
597  Relids expr_relids;
598  EquivalenceClass *newec;
599  EquivalenceMember *newem;
600  ListCell *lc1;
601  MemoryContext oldcontext;
602 
603  /*
604  * Ensure the expression exposes the correct type and collation.
605  */
606  expr = canonicalize_ec_expression(expr, opcintype, collation);
607 
608  /*
609  * Since SortGroupClause nodes are top-level expressions (GROUP BY, ORDER
610  * BY, etc), they can be presumed to belong to the top JoinDomain.
611  */
612  jdomain = linitial_node(JoinDomain, root->join_domains);
613 
614  /*
615  * Scan through the existing EquivalenceClasses for a match
616  */
617  foreach(lc1, root->eq_classes)
618  {
619  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
620  ListCell *lc2;
621 
622  /*
623  * Never match to a volatile EC, except when we are looking at another
624  * reference to the same volatile SortGroupClause.
625  */
626  if (cur_ec->ec_has_volatile &&
627  (sortref == 0 || sortref != cur_ec->ec_sortref))
628  continue;
629 
630  if (collation != cur_ec->ec_collation)
631  continue;
632  if (!equal(opfamilies, cur_ec->ec_opfamilies))
633  continue;
634 
635  foreach(lc2, cur_ec->ec_members)
636  {
637  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
638 
639  /*
640  * Ignore child members unless they match the request.
641  */
642  if (cur_em->em_is_child &&
643  !bms_equal(cur_em->em_relids, rel))
644  continue;
645 
646  /*
647  * Match constants only within the same JoinDomain (see
648  * optimizer/README).
649  */
650  if (cur_em->em_is_const && cur_em->em_jdomain != jdomain)
651  continue;
652 
653  if (opcintype == cur_em->em_datatype &&
654  equal(expr, cur_em->em_expr))
655  {
656  /*
657  * Match!
658  *
659  * Copy the sortref if it wasn't set yet. That may happen if
660  * the ec was constructed from a WHERE clause, i.e. it doesn't
661  * have a target reference at all.
662  */
663  if (cur_ec->ec_sortref == 0 && sortref > 0)
664  cur_ec->ec_sortref = sortref;
665  return cur_ec;
666  }
667  }
668  }
669 
670  /* No match; does caller want a NULL result? */
671  if (!create_it)
672  return NULL;
673 
674  /*
675  * OK, build a new single-member EC
676  *
677  * Here, we must be sure that we construct the EC in the right context.
678  */
679  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
680 
681  newec = makeNode(EquivalenceClass);
682  newec->ec_opfamilies = list_copy(opfamilies);
683  newec->ec_collation = collation;
684  newec->ec_members = NIL;
685  newec->ec_sources = NIL;
686  newec->ec_derives = NIL;
687  newec->ec_relids = NULL;
688  newec->ec_has_const = false;
690  newec->ec_broken = false;
691  newec->ec_sortref = sortref;
692  newec->ec_min_security = UINT_MAX;
693  newec->ec_max_security = 0;
694  newec->ec_merged = NULL;
695 
696  if (newec->ec_has_volatile && sortref == 0) /* should not happen */
697  elog(ERROR, "volatile EquivalenceClass has no sortref");
698 
699  /*
700  * Get the precise set of relids appearing in the expression.
701  */
702  expr_relids = pull_varnos(root, (Node *) expr);
703 
704  newem = add_eq_member(newec, copyObject(expr), expr_relids,
705  jdomain, NULL, opcintype);
706 
707  /*
708  * add_eq_member doesn't check for volatile functions, set-returning
709  * functions, aggregates, or window functions, but such could appear in
710  * sort expressions; so we have to check whether its const-marking was
711  * correct.
712  */
713  if (newec->ec_has_const)
714  {
715  if (newec->ec_has_volatile ||
716  expression_returns_set((Node *) expr) ||
717  contain_agg_clause((Node *) expr) ||
718  contain_window_function((Node *) expr))
719  {
720  newec->ec_has_const = false;
721  newem->em_is_const = false;
722  }
723  }
724 
725  root->eq_classes = lappend(root->eq_classes, newec);
726 
727  /*
728  * If EC merging is already complete, we have to mop up by adding the new
729  * EC to the eclass_indexes of the relation(s) mentioned in it.
730  */
731  if (root->ec_merging_done)
732  {
733  int ec_index = list_length(root->eq_classes) - 1;
734  int i = -1;
735 
736  while ((i = bms_next_member(newec->ec_relids, i)) > 0)
737  {
738  RelOptInfo *rel = root->simple_rel_array[i];
739 
740  if (rel == NULL) /* must be an outer join */
741  {
742  Assert(bms_is_member(i, root->outer_join_rels));
743  continue;
744  }
745 
747 
749  ec_index);
750  }
751  }
752 
753  MemoryContextSwitchTo(oldcontext);
754 
755  return newec;
756 }
bool contain_agg_clause(Node *clause)
Definition: clauses.c:177
bool contain_window_function(Node *clause)
Definition: clauses.c:214
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:538
bool expression_returns_set(Node *clause)
Definition: nodeFuncs.c:758
#define copyObject(obj)
Definition: nodes.h:224
#define makeNode(_type_)
Definition: nodes.h:155
#define linitial_node(type, l)
Definition: pg_list.h:181
Index ec_min_security
Definition: pathnodes.h:1390
Index ec_max_security
Definition: pathnodes.h:1391
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:108

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

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

◆ get_useful_group_keys_orderings()

List* get_useful_group_keys_orderings ( PlannerInfo root,
Path path 
)

Definition at line 485 of file pathkeys.c.

486 {
487  Query *parse = root->parse;
488  List *infos = NIL;
489  PathKeyInfo *info;
490 
491  List *pathkeys = root->group_pathkeys;
492  List *clauses = root->processed_groupClause;
493 
494  /* always return at least the original pathkeys/clauses */
495  info = makeNode(PathKeyInfo);
496  info->pathkeys = pathkeys;
497  info->clauses = clauses;
498  infos = lappend(infos, info);
499 
500  /*
501  * Should we try generating alternative orderings of the group keys? If
502  * not, we produce only the order specified in the query, i.e. the
503  * optimization is effectively disabled.
504  */
506  return infos;
507 
508  /*
509  * Grouping sets have own and more complex logic to decide the ordering.
510  */
511  if (parse->groupingSets)
512  return infos;
513 
514  /*
515  * If the path is sorted in some way, try reordering the group keys to
516  * match the path as much of the ordering as possible. Then thanks to
517  * incremental sort we would get this sort as cheap as possible.
518  */
519  if (path->pathkeys &&
520  !pathkeys_contained_in(path->pathkeys, root->group_pathkeys))
521  {
522  int n;
523 
524  n = group_keys_reorder_by_pathkeys(path->pathkeys, &pathkeys, &clauses,
525  root->num_groupby_pathkeys);
526 
527  if (n > 0 &&
528  (enable_incremental_sort || n == root->num_groupby_pathkeys) &&
529  !pathkeys_are_duplicate(infos, pathkeys))
530  {
531  info = makeNode(PathKeyInfo);
532  info->pathkeys = pathkeys;
533  info->clauses = clauses;
534 
535  infos = lappend(infos, info);
536  }
537  }
538 
539  /*
540  * Try reordering pathkeys to minimize the sort cost (this time consider
541  * the ORDER BY clause).
542  */
543  if (root->sort_pathkeys &&
544  !pathkeys_contained_in(root->sort_pathkeys, root->group_pathkeys))
545  {
546  int n;
547 
548  n = group_keys_reorder_by_pathkeys(root->sort_pathkeys, &pathkeys,
549  &clauses,
550  root->num_groupby_pathkeys);
551 
552  if (n > 0 &&
553  (enable_incremental_sort || n == list_length(root->sort_pathkeys)) &&
554  !pathkeys_are_duplicate(infos, pathkeys))
555  {
556  info = makeNode(PathKeyInfo);
557  info->pathkeys = pathkeys;
558  info->clauses = clauses;
559 
560  infos = lappend(infos, info);
561  }
562  }
563 
564  return infos;
565 }
static int group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys, List **group_clauses, int num_groupby_pathkeys)
Definition: pathkeys.c:368
bool enable_group_by_reordering
Definition: pathkeys.c:31
static bool pathkeys_are_duplicate(List *infos, List *pathkeys)
Definition: pathkeys.c:456
static struct subre * parse(struct vars *v, int stopper, int type, struct state *init, struct state *final)
Definition: regcomp.c:715
List * pathkeys
Definition: pathnodes.h:1476
List * clauses
Definition: pathnodes.h:1477

References PathKeyInfo::clauses, enable_group_by_reordering, enable_incremental_sort, group_keys_reorder_by_pathkeys(), lappend(), list_length(), makeNode, NIL, parse(), PathKeyInfo::pathkeys, Path::pathkeys, pathkeys_are_duplicate(), pathkeys_contained_in(), and root.

Referenced by add_paths_to_grouping_rel(), and create_partial_grouping_paths().

◆ has_relevant_eclass_joinclause()

bool has_relevant_eclass_joinclause ( PlannerInfo root,
RelOptInfo rel1 
)

Definition at line 3179 of file equivclass.c.

3180 {
3181  Bitmapset *matched_ecs;
3182  int i;
3183 
3184  /* Examine only eclasses mentioning rel1 */
3185  matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
3186 
3187  i = -1;
3188  while ((i = bms_next_member(matched_ecs, i)) >= 0)
3189  {
3190  EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
3191  i);
3192 
3193  /*
3194  * Won't generate joinclauses if single-member (this test covers the
3195  * volatile case too)
3196  */
3197  if (list_length(ec->ec_members) <= 1)
3198  continue;
3199 
3200  /*
3201  * Per the comment in have_relevant_eclass_joinclause, it's sufficient
3202  * to find an EC that mentions both this rel and some other rel.
3203  */
3204  if (!bms_is_subset(ec->ec_relids, rel1->relids))
3205  return true;
3206  }
3207 
3208  return false;
3209 }

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

Referenced by build_join_rel().

◆ has_useful_pathkeys()

bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 2261 of file pathkeys.c.

2262 {
2263  if (rel->joininfo != NIL || rel->has_eclass_joins)
2264  return true; /* might be able to use pathkeys for merging */
2265  if (root->group_pathkeys != NIL)
2266  return true; /* might be able to use pathkeys for grouping */
2267  if (root->query_pathkeys != NIL)
2268  return true; /* might be able to use them for ordering */
2269  return false; /* definitely useless */
2270 }

References RelOptInfo::has_eclass_joins, RelOptInfo::joininfo, NIL, and root.

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

◆ have_dangerous_phv()

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

Definition at line 1304 of file joinrels.c.

1306 {
1307  ListCell *lc;
1308 
1309  foreach(lc, root->placeholder_list)
1310  {
1311  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1312 
1313  if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1314  continue; /* ignore, could not be a nestloop param */
1315  if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1316  continue; /* ignore, not relevant to this join */
1317  if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
1318  continue; /* safe, it can be eval'd within outerrel */
1319  /* Otherwise, it's potentially unsafe, so reject the join */
1320  return true;
1321  }
1322 
1323  /* OK to perform the join */
1324  return false;
1325 }
Relids ph_eval_at
Definition: pathnodes.h:3077

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

Referenced by join_is_legal(), and try_nestloop_path().

◆ have_join_order_restriction()

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

Definition at line 1071 of file joinrels.c.

1073 {
1074  bool result = false;
1075  ListCell *l;
1076 
1077  /*
1078  * If either side has a direct lateral reference to the other, attempt the
1079  * join regardless of outer-join considerations.
1080  */
1081  if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) ||
1083  return true;
1084 
1085  /*
1086  * Likewise, if both rels are needed to compute some PlaceHolderVar,
1087  * attempt the join regardless of outer-join considerations. (This is not
1088  * very desirable, because a PHV with a large eval_at set will cause a lot
1089  * of probably-useless joins to be considered, but failing to do this can
1090  * cause us to fail to construct a plan at all.)
1091  */
1092  foreach(l, root->placeholder_list)
1093  {
1094  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
1095 
1096  if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) &&
1097  bms_is_subset(rel2->relids, phinfo->ph_eval_at))
1098  return true;
1099  }
1100 
1101  /*
1102  * It's possible that the rels correspond to the left and right sides of a
1103  * degenerate outer join, that is, one with no joinclause mentioning the
1104  * non-nullable side; in which case we should force the join to occur.
1105  *
1106  * Also, the two rels could represent a clauseless join that has to be
1107  * completed to build up the LHS or RHS of an outer join.
1108  */
1109  foreach(l, root->join_info_list)
1110  {
1111  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1112 
1113  /* ignore full joins --- other mechanisms handle them */
1114  if (sjinfo->jointype == JOIN_FULL)
1115  continue;
1116 
1117  /* Can we perform the SJ with these rels? */
1118  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
1119  bms_is_subset(sjinfo->min_righthand, rel2->relids))
1120  {
1121  result = true;
1122  break;
1123  }
1124  if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
1125  bms_is_subset(sjinfo->min_righthand, rel1->relids))
1126  {
1127  result = true;
1128  break;
1129  }
1130 
1131  /*
1132  * Might we need to join these rels to complete the RHS? We have to
1133  * use "overlap" tests since either rel might include a lower SJ that
1134  * has been proven to commute with this one.
1135  */
1136  if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
1137  bms_overlap(sjinfo->min_righthand, rel2->relids))
1138  {
1139  result = true;
1140  break;
1141  }
1142 
1143  /* Likewise for the LHS. */
1144  if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
1145  bms_overlap(sjinfo->min_lefthand, rel2->relids))
1146  {
1147  result = true;
1148  break;
1149  }
1150  }
1151 
1152  /*
1153  * We do not force the join to occur if either input rel can legally be
1154  * joined to anything else using joinclauses. This essentially means that
1155  * clauseless bushy joins are put off as long as possible. The reason is
1156  * that when there is a join order restriction high up in the join tree
1157  * (that is, with many rels inside the LHS or RHS), we would otherwise
1158  * expend lots of effort considering very stupid join combinations within
1159  * its LHS or RHS.
1160  */
1161  if (result)
1162  {
1163  if (has_legal_joinclause(root, rel1) ||
1164  has_legal_joinclause(root, rel2))
1165  result = false;
1166  }
1167 
1168  return result;
1169 }
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1240
Relids direct_lateral_relids
Definition: pathnodes.h:901

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

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

◆ have_relevant_eclass_joinclause()

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

Definition at line 3103 of file equivclass.c.

3105 {
3106  Bitmapset *matching_ecs;
3107  int i;
3108 
3109  /*
3110  * Examine only eclasses mentioning both rel1 and rel2.
3111  *
3112  * Note that we do not consider the possibility of an eclass generating
3113  * "join" clauses that mention just one of the rels plus an outer join
3114  * that could be formed from them. Although such clauses must be
3115  * correctly enforced when we form the outer join, they don't seem like
3116  * sufficient reason to prioritize this join over other ones. The join
3117  * ordering rules will force the join to be made when necessary.
3118  */
3119  matching_ecs = get_common_eclass_indexes(root, rel1->relids,
3120  rel2->relids);
3121 
3122  i = -1;
3123  while ((i = bms_next_member(matching_ecs, i)) >= 0)
3124  {
3125  EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
3126  i);
3127 
3128  /*
3129  * Sanity check that get_common_eclass_indexes gave only ECs
3130  * containing both rels.
3131  */
3132  Assert(bms_overlap(rel1->relids, ec->ec_relids));
3133  Assert(bms_overlap(rel2->relids, ec->ec_relids));
3134 
3135  /*
3136  * Won't generate joinclauses if single-member (this test covers the
3137  * volatile case too)
3138  */
3139  if (list_length(ec->ec_members) <= 1)
3140  continue;
3141 
3142  /*
3143  * We do not need to examine the individual members of the EC, because
3144  * all that we care about is whether each rel overlaps the relids of
3145  * at least one member, and get_common_eclass_indexes() and the single
3146  * member check above are sufficient to prove that. (As with
3147  * have_relevant_joinclause(), it is not necessary that the EC be able
3148  * to form a joinclause relating exactly the two given rels, only that
3149  * it be able to form a joinclause mentioning both, and this will
3150  * surely be true if both of them overlap ec_relids.)
3151  *
3152  * Note we don't test ec_broken; if we did, we'd need a separate code
3153  * path to look through ec_sources. Checking the membership anyway is
3154  * OK as a possibly-overoptimistic heuristic.
3155  *
3156  * We don't test ec_has_const either, even though a const eclass won't
3157  * generate real join clauses. This is because if we had "WHERE a.x =
3158  * b.y and a.x = 42", it is worth considering a join between a and b,
3159  * since the join result is likely to be small even though it'll end
3160  * up being an unqualified nestloop.
3161  */
3162 
3163  return true;
3164  }
3165 
3166  return false;
3167 }

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

Referenced by have_relevant_joinclause().

◆ indexcol_is_bool_constant_for_query()

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

Definition at line 3614 of file indxpath.c.

3617 {
3618  ListCell *lc;
3619 
3620  /* If the index isn't boolean, we can't possibly get a match */
3621  if (!IsBooleanOpfamily(index->opfamily[indexcol]))
3622  return false;
3623 
3624  /* Check each restriction clause for the index's rel */
3625  foreach(lc, index->rel->baserestrictinfo)
3626  {
3627  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3628 
3629  /*
3630  * As in match_clause_to_indexcol, never match pseudoconstants to
3631  * indexes. (It might be semantically okay to do so here, but the
3632  * odds of getting a match are negligible, so don't waste the cycles.)
3633  */
3634  if (rinfo->pseudoconstant)
3635  continue;
3636 
3637  /* See if we can match the clause's expression to the index column */
3638  if (match_boolean_index_clause(root, rinfo, indexcol, index))
3639  return true;
3640  }
3641 
3642  return false;
3643 }
static bool IsBooleanOpfamily(Oid opfamily)
Definition: indxpath.c:2280
static IndexClause * match_boolean_index_clause(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:2305

References IsBooleanOpfamily(), lfirst, match_boolean_index_clause(), and root.

Referenced by build_index_pathkeys().

◆ init_dummy_sjinfo()

void init_dummy_sjinfo ( SpecialJoinInfo sjinfo,
Relids  left_relids,
Relids  right_relids 
)

Definition at line 669 of file joinrels.c.

671 {
672  sjinfo->type = T_SpecialJoinInfo;
673  sjinfo->min_lefthand = left_relids;
674  sjinfo->min_righthand = right_relids;
675  sjinfo->syn_lefthand = left_relids;
676  sjinfo->syn_righthand = right_relids;
677  sjinfo->jointype = JOIN_INNER;
678  sjinfo->ojrelid = 0;
679  sjinfo->commute_above_l = NULL;
680  sjinfo->commute_above_r = NULL;
681  sjinfo->commute_below_l = NULL;
682  sjinfo->commute_below_r = NULL;
683  /* we don't bother trying to make the remaining fields valid */
684  sjinfo->lhs_strict = false;
685  sjinfo->semi_can_btree = false;
686  sjinfo->semi_can_hash = false;
687  sjinfo->semi_operators = NIL;
688  sjinfo->semi_rhs_exprs = NIL;
689 }
Relids commute_above_r
Definition: pathnodes.h:2890
Relids syn_lefthand
Definition: pathnodes.h:2885
List * semi_rhs_exprs
Definition: pathnodes.h:2898
Relids syn_righthand
Definition: pathnodes.h:2886
Relids commute_below_r
Definition: pathnodes.h:2892
List * semi_operators
Definition: pathnodes.h:2897

References SpecialJoinInfo::commute_above_l, SpecialJoinInfo::commute_above_r, SpecialJoinInfo::commute_below_l, SpecialJoinInfo::commute_below_r, JOIN_INNER, SpecialJoinInfo::jointype, SpecialJoinInfo::lhs_strict, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, SpecialJoinInfo::ojrelid, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, and SpecialJoinInfo::syn_righthand.

Referenced by approx_tuple_count(), build_child_join_sjinfo(), compute_semi_anti_join_factors(), consider_new_or_clause(), and make_join_rel().

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1446 of file pathkeys.c.

1447 {
1448  Expr *clause = restrictinfo->clause;
1449  Oid lefttype,
1450  righttype;
1451 
1452  /* Should be a mergeclause ... */
1453  Assert(restrictinfo->mergeopfamilies != NIL);
1454  /* ... with links not yet set */
1455  Assert(restrictinfo->left_ec == NULL);
1456  Assert(restrictinfo->right_ec == NULL);
1457 
1458  /* Need the declared input types of the operator */
1459  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1460 
1461  /* Find or create a matching EquivalenceClass for each side */
1462  restrictinfo->left_ec =
1464  (Expr *) get_leftop(clause),
1465  restrictinfo->mergeopfamilies,
1466  lefttype,
1467  ((OpExpr *) clause)->inputcollid,
1468  0,
1469  NULL,
1470  true);
1471  restrictinfo->right_ec =
1473  (Expr *) get_rightop(clause),
1474  restrictinfo->mergeopfamilies,
1475  righttype,
1476  ((OpExpr *) clause)->inputcollid,
1477  0,
1478  NULL,
1479  true);
1480 }
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1358
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:93
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:81

References Assert, RestrictInfo::clause, get_eclass_for_sort_expr(), get_leftop(), get_rightop(), NIL, op_input_types(), and root.

Referenced by distribute_qual_to_rels().

◆ is_redundant_derived_clause()

bool is_redundant_derived_clause ( RestrictInfo rinfo,
List clauselist 
)

Definition at line 3281 of file equivclass.c.

3282 {
3283  EquivalenceClass *parent_ec = rinfo->parent_ec;
3284  ListCell *lc;
3285 
3286  /* Fail if it's not a potentially-redundant clause from some EC */
3287  if (parent_ec == NULL)
3288  return false;
3289 
3290  foreach(lc, clauselist)
3291  {
3292  RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
3293 
3294  if (otherrinfo->parent_ec == parent_ec)
3295  return true;
3296  }
3297 
3298  return false;
3299 }

References lfirst.

Referenced by create_tidscan_plan().

◆ is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses ( RestrictInfo rinfo,
List indexclauses 
)

Definition at line 3308 of file equivclass.c.

3309 {
3310  EquivalenceClass *parent_ec = rinfo->parent_ec;
3311  ListCell *lc;
3312 
3313  foreach(lc, indexclauses)
3314  {
3315  IndexClause *iclause = lfirst_node(IndexClause, lc);
3316  RestrictInfo *otherrinfo = iclause->rinfo;
3317 
3318  /* If indexclause is lossy, it won't enforce the condition exactly */
3319  if (iclause->lossy)
3320  continue;
3321 
3322  /* Match if it's same clause (pointer equality should be enough) */
3323  if (rinfo == otherrinfo)
3324  return true;
3325  /* Match if derived from same EC */
3326  if (parent_ec && otherrinfo->parent_ec == parent_ec)
3327  return true;
3328 
3329  /*
3330  * No need to look at the derived clauses in iclause->indexquals; they
3331  * couldn't match if the parent clause didn't.
3332  */
3333  }
3334 
3335  return false;
3336 }
struct RestrictInfo * rinfo
Definition: pathnodes.h:1747

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

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

◆ join_search_one_level()

void join_search_one_level ( PlannerInfo root,
int  level 
)

Definition at line 72 of file joinrels.c.

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

References Assert, bms_overlap(), elog, ERROR, for_each_from, foreach_current_index, RelOptInfo::has_eclass_joins, has_join_restriction(), have_join_order_restriction(), have_relevant_joinclause(), RelOptInfo::joininfo, lfirst, make_join_rel(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), NIL, RelOptInfo::relids, and root.

Referenced by standard_join_search().

◆ make_canonical_pathkey()

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

Definition at line 55 of file pathkeys.c.

58 {
59  PathKey *pk;
60  ListCell *lc;
61  MemoryContext oldcontext;
62 
63  /* Can't make canonical pathkeys if the set of ECs might still change */
64  if (!root->ec_merging_done)
65  elog(ERROR, "too soon to build canonical pathkeys");
66 
67  /* The passed eclass might be non-canonical, so chase up to the top */
68  while (eclass->ec_merged)
69  eclass = eclass->ec_merged;
70 
71  foreach(lc, root->canon_pathkeys)
72  {
73  pk = (PathKey *) lfirst(lc);
74  if (eclass == pk->pk_eclass &&
75  opfamily == pk->pk_opfamily &&
76  strategy == pk->pk_strategy &&
77  nulls_first == pk->pk_nulls_first)
78  return pk;
79  }
80 
81  /*
82  * Be sure canonical pathkeys are allocated in the main planning context.
83  * Not an issue in normal planning, but it is for GEQO.
84  */
85  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
86 
87  pk = makeNode(PathKey);
88  pk->pk_eclass = eclass;
89  pk->pk_opfamily = opfamily;
90  pk->pk_strategy = strategy;
91  pk->pk_nulls_first = nulls_first;
92 
93  root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
94 
95  MemoryContextSwitchTo(oldcontext);
96 
97  return pk;
98 }

References eclass(), elog, ERROR, lappend(), lfirst, makeNode, MemoryContextSwitchTo(), PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, and root.

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

◆ make_inner_pathkeys_for_merge()

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

Definition at line 1838 of file pathkeys.c.

1841 {
1842  List *pathkeys = NIL;
1843  EquivalenceClass *lastoeclass;
1844  PathKey *opathkey;
1845  ListCell *lc;
1846  ListCell *lop;
1847 
1848  lastoeclass = NULL;
1849  opathkey = NULL;
1850  lop = list_head(outer_pathkeys);
1851 
1852  foreach(lc, mergeclauses)
1853  {
1854  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1855  EquivalenceClass *oeclass;
1856  EquivalenceClass *ieclass;
1857  PathKey *pathkey;
1858 
1860 
1861  if (rinfo->outer_is_left)
1862  {
1863  oeclass = rinfo->left_ec;
1864  ieclass = rinfo->right_ec;
1865  }
1866  else
1867  {
1868  oeclass = rinfo->right_ec;
1869  ieclass = rinfo->left_ec;
1870  }
1871 
1872  /* outer eclass should match current or next pathkeys */
1873  /* we check this carefully for debugging reasons */
1874  if (oeclass != lastoeclass)
1875  {
1876  if (!lop)
1877  elog(ERROR, "too few pathkeys for mergeclauses");
1878  opathkey = (PathKey *) lfirst(lop);
1879  lop = lnext(outer_pathkeys, lop);
1880  lastoeclass = opathkey->pk_eclass;
1881  if (oeclass != lastoeclass)
1882  elog(ERROR, "outer pathkeys do not match mergeclause");
1883  }
1884 
1885  /*
1886  * Often, we'll have same EC on both sides, in which case the outer
1887  * pathkey is also canonical for the inner side, and we can skip a
1888  * useless search.
1889  */
1890  if (ieclass == oeclass)
1891  pathkey = opathkey;
1892  else
1893  pathkey = make_canonical_pathkey(root,
1894  ieclass,
1895  opathkey->pk_opfamily,
1896  opathkey->pk_strategy,
1897  opathkey->pk_nulls_first);
1898 
1899  /*
1900  * Don't generate redundant pathkeys (which can happen if multiple
1901  * mergeclauses refer to the same EC). Because we do this, the output
1902  * pathkey list isn't necessarily ordered like the mergeclauses, which
1903  * complicates life for create_mergejoin_plan(). But if we didn't,
1904  * we'd have a noncanonical sort key list, which would be bad; for one
1905  * reason, it certainly wouldn't match any available sort order for
1906  * the input relation.
1907  */
1908  if (!pathkey_is_redundant(pathkey, pathkeys))
1909  pathkeys = lappend(pathkeys, pathkey);
1910  }
1911 
1912  return pathkeys;
1913 }

References elog, ERROR, lappend(), lfirst, list_head(), lnext(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, root, and update_mergeclause_eclasses().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

◆ make_join_rel()

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

Definition at line 704 of file joinrels.c.

705 {
706  Relids joinrelids;
707  SpecialJoinInfo *sjinfo;
708  bool reversed;
709  List *pushed_down_joins = NIL;
710  SpecialJoinInfo sjinfo_data;
711  RelOptInfo *joinrel;
712  List *restrictlist;
713 
714  /* We should never try to join two overlapping sets of rels. */
715  Assert(!bms_overlap(rel1->relids, rel2->relids));
716 
717  /* Construct Relids set that identifies the joinrel (without OJ as yet). */
718  joinrelids = bms_union(rel1->relids, rel2->relids);
719 
720  /* Check validity and determine join type. */
721  if (!join_is_legal(root, rel1, rel2, joinrelids,
722  &sjinfo, &reversed))
723  {
724  /* invalid join path */
725  bms_free(joinrelids);
726  return NULL;
727  }
728 
729  /*
730  * Add outer join relid(s) to form the canonical relids. Any added outer
731  * joins besides sjinfo itself are appended to pushed_down_joins.
732  */
733  joinrelids = add_outer_joins_to_relids(root, joinrelids, sjinfo,
734  &pushed_down_joins);
735 
736  /* Swap rels if needed to match the join info. */
737  if (reversed)
738  {
739  RelOptInfo *trel = rel1;
740 
741  rel1 = rel2;
742  rel2 = trel;
743  }
744 
745  /*
746  * If it's a plain inner join, then we won't have found anything in
747  * join_info_list. Make up a SpecialJoinInfo so that selectivity
748  * estimation functions will know what's being joined.
749  */
750  if (sjinfo == NULL)
751  {
752  sjinfo = &sjinfo_data;
753  init_dummy_sjinfo(sjinfo, rel1->relids, rel2->relids);
754  }
755 
756  /*
757  * Find or build the join RelOptInfo, and compute the restrictlist that
758  * goes with this particular joining.
759  */
760  joinrel = build_join_rel(root, joinrelids, rel1, rel2,
761  sjinfo, pushed_down_joins,
762  &restrictlist);
763 
764  /*
765  * If we've already proven this join is empty, we needn't consider any
766  * more paths for it.
767  */
768  if (is_dummy_rel(joinrel))
769  {
770  bms_free(joinrelids);
771  return joinrel;
772  }
773 
774  /* Add paths to the join relation. */
775  populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
776  restrictlist);
777 
778  bms_free(joinrelids);
779 
780  return joinrel;
781 }
void bms_free(Bitmapset *a)
Definition: bitmapset.c:239
static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinrels.c:893
bool is_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1332
void init_dummy_sjinfo(SpecialJoinInfo *sjinfo, Relids left_relids, Relids right_relids)
Definition: joinrels.c:669
static bool join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
Definition: joinrels.c:349
RelOptInfo * build_join_rel(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, List *pushed_down_joins, List **restrictlist_ptr)
Definition: relnode.c:665

References add_outer_joins_to_relids(), Assert, bms_free(), bms_overlap(), bms_union(), build_join_rel(), init_dummy_sjinfo(), is_dummy_rel(), join_is_legal(), NIL, populate_joinrel_with_paths(), RelOptInfo::relids, and root.

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

◆ make_one_rel()

RelOptInfo* make_one_rel ( PlannerInfo root,
List joinlist 
)

Definition at line 171 of file allpaths.c.

172 {
173  RelOptInfo *rel;
174  Index rti;
175  double total_pages;
176 
177  /* Mark base rels as to whether we care about fast-start plans */
179 
180  /*
181  * Compute size estimates and consider_parallel flags for each base rel.
182  */
184 
185  /*
186  * We should now have size estimates for every actual table involved in
187  * the query, and we also know which if any have been deleted from the
188  * query by join removal, pruned by partition pruning, or eliminated by
189  * constraint exclusion. So we can now compute total_table_pages.
190  *
191  * Note that appendrels are not double-counted here, even though we don't
192  * bother to distinguish RelOptInfos for appendrel parents, because the
193  * parents will have pages = 0.
194  *
195  * XXX if a table is self-joined, we will count it once per appearance,
196  * which perhaps is the wrong thing ... but that's not completely clear,
197  * and detecting self-joins here is difficult, so ignore it for now.
198  */
199  total_pages = 0;
200  for (rti = 1; rti < root->simple_rel_array_size; rti++)
201  {
202  RelOptInfo *brel = root->simple_rel_array[rti];
203 
204  /* there may be empty slots corresponding to non-baserel RTEs */
205  if (brel == NULL)
206  continue;
207 
208  Assert(brel->relid == rti); /* sanity check on array */
209 
210  if (IS_DUMMY_REL(brel))
211  continue;
212 
213  if (IS_SIMPLE_REL(brel))
214  total_pages += (double) brel->pages;
215  }
216  root->total_table_pages = total_pages;
217 
218  /*
219  * Generate access paths for each base rel.
220  */
222 
223  /*
224  * Generate access paths for the entire join tree.
225  */
226  rel = make_rel_from_joinlist(root, joinlist);
227 
228  /*
229  * The result should join all and only the query's base + outer-join rels.
230  */
231  Assert(bms_equal(rel->relids, root->all_query_rels));
232 
233  return rel;
234 }
static void set_base_rel_sizes(PlannerInfo *root)
Definition: allpaths.c:290
static void set_base_rel_consider_startup(PlannerInfo *root)
Definition: allpaths.c:247
static void set_base_rel_pathlists(PlannerInfo *root)
Definition: allpaths.c:333
static RelOptInfo * make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
Definition: allpaths.c:3306
unsigned int Index
Definition: c.h:614
BlockNumber pages
Definition: pathnodes.h:938

References Assert, bms_equal(), IS_DUMMY_REL, IS_SIMPLE_REL, make_rel_from_joinlist(), RelOptInfo::pages, RelOptInfo::relid, RelOptInfo::relids, root, set_base_rel_consider_startup(), set_base_rel_pathlists(), and set_base_rel_sizes().

Referenced by query_planner().

◆ make_pathkeys_for_sortclauses()

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

Definition at line 1347 of file pathkeys.c.

1350 {
1351  List *result;
1352  bool sortable;
1353 
1355  &sortclauses,
1356  tlist,
1357  false,
1358  &sortable);
1359  /* It's caller error if not all clauses were sortable */
1360  Assert(sortable);
1361  return result;
1362 }
List * make_pathkeys_for_sortclauses_extended(PlannerInfo *root, List **sortclauses, List *tlist, bool remove_redundant, bool *sortable)
Definition: pathkeys.c:1384

References Assert, make_pathkeys_for_sortclauses_extended(), and root.

Referenced by adjust_group_pathkeys_for_groupagg(), generate_nonunion_paths(), generate_union_paths(), grouping_planner(), make_pathkeys_for_window(), minmax_qp_callback(), and standard_qp_callback().

◆ make_pathkeys_for_sortclauses_extended()

List* make_pathkeys_for_sortclauses_extended ( PlannerInfo root,
List **  sortclauses,
List tlist,
bool  remove_redundant,
bool sortable 
)

Definition at line 1384 of file pathkeys.c.

1389 {
1390  List *pathkeys = NIL;
1391  ListCell *l;
1392 
1393  *sortable = true;
1394  foreach(l, *sortclauses)
1395  {
1396  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1397  Expr *sortkey;
1398  PathKey *pathkey;
1399 
1400  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1401  if (!OidIsValid(sortcl->sortop))
1402  {
1403  *sortable = false;
1404  continue;
1405  }
1406  pathkey = make_pathkey_from_sortop(root,
1407  sortkey,
1408  sortcl->sortop,
1409  sortcl->nulls_first,
1410  sortcl->tleSortGroupRef,
1411  true);
1412 
1413  /* Canonical form eliminates redundant ordering keys */
1414  if (!pathkey_is_redundant(pathkey, pathkeys))
1415  pathkeys = lappend(pathkeys, pathkey);
1416  else if (remove_redundant)
1417  *sortclauses = foreach_delete_current(*sortclauses, l);
1418  }
1419  return pathkeys;
1420 }
static PathKey * make_pathkey_from_sortop(PlannerInfo *root, Expr *expr, Oid ordering_op, bool nulls_first, Index sortref, bool create_it)
Definition: pathkeys.c:255
#define foreach_delete_current(lst, var_or_cell)
Definition: pg_list.h:391
Index tleSortGroupRef
Definition: parsenodes.h:1442
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:379

References foreach_delete_current, get_sortgroupclause_expr(), lappend(), lfirst, make_pathkey_from_sortop(), NIL, SortGroupClause::nulls_first, OidIsValid, pathkey_is_redundant(), root, SortGroupClause::sortop, and SortGroupClause::tleSortGroupRef.

Referenced by make_pathkeys_for_sortclauses(), make_pathkeys_for_window(), and standard_qp_callback().

◆ mark_dummy_rel()

void mark_dummy_rel ( RelOptInfo rel)

Definition at line 1381 of file joinrels.c.

1382 {
1383  MemoryContext oldcontext;
1384 
1385  /* Already marked? */
1386  if (is_dummy_rel(rel))
1387  return;
1388 
1389  /* No, so choose correct context to make the dummy path in */
1390  oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1391 
1392  /* Set dummy size estimate */
1393  rel->rows = 0;
1394 
1395  /* Evict any previously chosen paths */
1396  rel->pathlist = NIL;
1397  rel->partial_pathlist = NIL;
1398 
1399  /* Set up the dummy path */
1400  add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL,
1401  NIL, rel->lateral_relids,
1402  0, false, -1));
1403 
1404  /* Set or update cheapest_total_path and related fields */
1405  set_cheapest(rel);
1406 
1407  MemoryContextSwitchTo(oldcontext);
1408 }
MemoryContext GetMemoryChunkContext(void *pointer)
Definition: mcxt.c:707
Cardinality rows
Definition: pathnodes.h:867

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

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

◆ match_eclasses_to_foreign_key_col()

EquivalenceClass* match_eclasses_to_foreign_key_col ( PlannerInfo root,
ForeignKeyOptInfo fkinfo,
int  colno 
)

Definition at line 2516 of file equivclass.c.

2519 {
2520  Index var1varno = fkinfo->con_relid;
2521  AttrNumber var1attno = fkinfo->conkey[colno];
2522  Index var2varno = fkinfo->ref_relid;
2523  AttrNumber var2attno = fkinfo->confkey[colno];
2524  Oid eqop = fkinfo->conpfeqop[colno];
2525  RelOptInfo *rel1 = root->simple_rel_array[var1varno];
2526  RelOptInfo *rel2 = root->simple_rel_array[var2varno];
2527  List *opfamilies = NIL; /* compute only if needed */
2528  Bitmapset *matching_ecs;
2529  int i;
2530 
2531  /* Consider only eclasses mentioning both relations */
2532  Assert(root->ec_merging_done);
2533  Assert(IS_SIMPLE_REL(rel1));
2534  Assert(IS_SIMPLE_REL(rel2));
2535  matching_ecs = bms_intersect(rel1->eclass_indexes,
2536  rel2->eclass_indexes);
2537 
2538  i = -1;
2539  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2540  {
2541  EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
2542  i);
2543  EquivalenceMember *item1_em = NULL;
2544  EquivalenceMember *item2_em = NULL;
2545  ListCell *lc2;
2546 
2547  /* Never match to a volatile EC */
2548  if (ec->ec_has_volatile)
2549  continue;
2550  /* Note: it seems okay to match to "broken" eclasses here */
2551 
2552  foreach(lc2, ec->ec_members)
2553  {
2555  Var *var;
2556 
2557  if (em->em_is_child)
2558  continue; /* ignore children here */
2559 
2560  /* EM must be a Var, possibly with RelabelType */
2561  var = (Var *) em->em_expr;
2562  while (var && IsA(var, RelabelType))
2563  var = (Var *) ((RelabelType *) var)->arg;
2564  if (!(var && IsA(var, Var)))
2565  continue;
2566 
2567  /* Match? */
2568  if (var->varno == var1varno && var->varattno == var1attno)
2569  item1_em = em;
2570  else if (var->varno == var2varno && var->varattno == var2attno)
2571  item2_em = em;
2572 
2573  /* Have we found both PK and FK column in this EC? */
2574  if (item1_em && item2_em)
2575  {
2576  /*
2577  * Succeed if eqop matches EC's opfamilies. We could test
2578  * this before scanning the members, but it's probably cheaper
2579  * to test for member matches first.
2580  */
2581  if (opfamilies == NIL) /* compute if we didn't already */
2582  opfamilies = get_mergejoin_opfamilies(eqop);
2583  if (equal(opfamilies, ec->ec_opfamilies))
2584  {
2585  fkinfo->eclass[colno] = ec;
2586  fkinfo->fk_eclass_member[colno] = item2_em;
2587  return ec;
2588  }
2589  /* Otherwise, done with this EC, move on to the next */
2590  break;
2591  }
2592  }
2593  }
2594  return NULL;
2595 }
int16 AttrNumber
Definition: attnum.h:21
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:292
List * get_mergejoin_opfamilies(Oid opno)
Definition: lsyscache.c:366
while(p+4<=pend)
struct EquivalenceClass * eclass[INDEX_MAX_KEYS]
Definition: pathnodes.h:1246
struct EquivalenceMember * fk_eclass_member[INDEX_MAX_KEYS]
Definition: pathnodes.h:1248
AttrNumber varattno
Definition: primnodes.h:260
int varno
Definition: primnodes.h:255

References Assert, bms_intersect(), bms_next_member(), ForeignKeyOptInfo::con_relid, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, ForeignKeyOptInfo::eclass, RelOptInfo::eclass_indexes, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, equal(), ForeignKeyOptInfo::fk_eclass_member, get_mergejoin_opfamilies(), i, IS_SIMPLE_REL, IsA, lfirst, list_nth(), NIL, ForeignKeyOptInfo::ref_relid, root, Var::varattno, Var::varno, and while().

Referenced by match_foreign_keys_to_quals().

◆ match_index_to_operand()

bool match_index_to_operand ( Node operand,
int  indexcol,
IndexOptInfo index 
)

Definition at line 3665 of file indxpath.c.

3668 {
3669  int indkey;
3670 
3671  /*
3672  * Ignore any RelabelType node above the operand. This is needed to be
3673  * able to apply indexscanning in binary-compatible-operator cases. Note:
3674  * we can assume there is at most one RelabelType node;
3675  * eval_const_expressions() will have simplified if more than one.
3676  */
3677  if (operand && IsA(operand, RelabelType))
3678  operand = (Node *) ((RelabelType *) operand)->arg;
3679 
3680  indkey = index->indexkeys[indexcol];
3681  if (indkey != 0)
3682  {
3683  /*
3684  * Simple index column; operand must be a matching Var.
3685  */
3686  if (operand && IsA(operand, Var) &&
3687  index->rel->relid == ((Var *) operand)->varno &&
3688  indkey == ((Var *) operand)->varattno &&