PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
paths.h File Reference
#include "nodes/relation.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)
 
void set_dummy_rel_pathlist (RelOptInfo *rel)
 
RelOptInfostandard_join_search (PlannerInfo *root, int levels_needed, List *initial_rels)
 
void generate_gather_paths (PlannerInfo *root, RelOptInfo *rel)
 
int compute_parallel_worker (RelOptInfo *rel, BlockNumber heap_pages, BlockNumber index_pages)
 
void create_index_paths (PlannerInfo *root, RelOptInfo *rel)
 
bool relation_has_unique_index_for (PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist)
 
bool indexcol_is_bool_constant_for_query (IndexOptInfo *index, int indexcol)
 
bool match_index_to_operand (Node *operand, int indexcol, IndexOptInfo *index)
 
void expand_indexqual_conditions (IndexOptInfo *index, List *indexclauses, List *indexclausecols, List **indexquals_p, List **indexqualcols_p)
 
void check_index_predicates (PlannerInfo *root, RelOptInfo *rel)
 
Expradjust_rowcompare_for_index (RowCompareExpr *clause, IndexOptInfo *index, int indexcol, List **indexcolnos, bool *var_on_left_p)
 
void create_tidscan_paths (PlannerInfo *root, RelOptInfo *rel)
 
void add_paths_to_joinrel (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
 
void join_search_one_level (PlannerInfo *root, int level)
 
RelOptInfomake_join_rel (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
bool have_join_order_restriction (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
bool have_dangerous_phv (PlannerInfo *root, Relids outer_relids, Relids inner_params)
 
bool process_equivalence (PlannerInfo *root, RestrictInfo *restrictinfo, bool below_outer_join)
 
Exprcanonicalize_ec_expression (Expr *expr, Oid req_type, Oid req_collation)
 
void reconsider_outer_join_clauses (PlannerInfo *root)
 
EquivalenceClassget_eclass_for_sort_expr (PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
 
void generate_base_implied_equalities (PlannerInfo *root)
 
Listgenerate_join_implied_equalities (PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
 
Listgenerate_join_implied_equalities_for_ecs (PlannerInfo *root, List *eclasses, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
 
bool exprs_known_equal (PlannerInfo *root, Node *item1, Node *item2)
 
EquivalenceClassmatch_eclasses_to_foreign_key_col (PlannerInfo *root, ForeignKeyOptInfo *fkinfo, int colno)
 
void add_child_rel_equivalences (PlannerInfo *root, AppendRelInfo *appinfo, RelOptInfo *parent_rel, RelOptInfo *child_rel)
 
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)
 
PathKeysComparison compare_pathkeys (List *keys1, List *keys2)
 
bool pathkeys_contained_in (List *keys1, List *keys2)
 
Pathget_cheapest_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion)
 
Pathget_cheapest_fractional_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, double fraction)
 
Listbuild_index_pathkeys (PlannerInfo *root, IndexOptInfo *index, ScanDirection scandir)
 
Listbuild_expression_pathkey (PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opno, Relids rel, bool create_it)
 
Listconvert_subquery_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *subquery_pathkeys, List *subquery_tlist)
 
Listbuild_join_pathkeys (PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
 
Listmake_pathkeys_for_sortclauses (PlannerInfo *root, List *sortclauses, List *tlist)
 
void initialize_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
 
void update_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
 
Listfind_mergeclauses_for_pathkeys (PlannerInfo *root, List *pathkeys, bool outer_keys, 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)
 
Listtruncate_useless_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 
bool has_useful_pathkeys (PlannerInfo *root, RelOptInfo *rel)
 
PathKeymake_canonical_pathkey (PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
 

Variables

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

Typedef Documentation

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

Definition at line 117 of file paths.h.

typedef RelOptInfo*(* join_search_hook_type)(PlannerInfo *root, int levels_needed, List *initial_rels)

Definition at line 45 of file paths.h.

typedef void(* set_join_pathlist_hook_type)(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)

Definition at line 36 of file paths.h.

typedef void(* set_rel_pathlist_hook_type)(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte)

Definition at line 29 of file paths.h.

Enumeration Type Documentation

Enumerator
PATHKEYS_EQUAL 
PATHKEYS_BETTER1 
PATHKEYS_BETTER2 
PATHKEYS_DIFFERENT 

Definition at line 173 of file paths.h.

174 {
175  PATHKEYS_EQUAL, /* pathkeys are identical */
176  PATHKEYS_BETTER1, /* pathkey 1 is a superset of pathkey 2 */
177  PATHKEYS_BETTER2, /* vice versa */
178  PATHKEYS_DIFFERENT /* neither pathkey includes the other */
PathKeysComparison
Definition: paths.h:173

Function Documentation

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

Definition at line 2068 of file equivclass.c.

References add_eq_member(), adjust_appendrel_attrs(), bms_add_members(), bms_difference(), bms_is_subset(), bms_overlap(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_const, EquivalenceMember::em_nullable_relids, EquivalenceMember::em_relids, PlannerInfo::eq_classes, lfirst, RelOptInfo::relids, RELOPT_BASEREL, and RelOptInfo::reloptkind.

Referenced by set_append_rel_size().

2072 {
2073  ListCell *lc1;
2074 
2075  foreach(lc1, root->eq_classes)
2076  {
2077  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
2078  ListCell *lc2;
2079 
2080  /*
2081  * If this EC contains a volatile expression, then generating child
2082  * EMs would be downright dangerous, so skip it. We rely on a
2083  * volatile EC having only one EM.
2084  */
2085  if (cur_ec->ec_has_volatile)
2086  continue;
2087 
2088  /*
2089  * No point in searching if parent rel not mentioned in eclass; but we
2090  * can't tell that for sure if parent rel is itself a child.
2091  */
2092  if (parent_rel->reloptkind == RELOPT_BASEREL &&
2093  !bms_is_subset(parent_rel->relids, cur_ec->ec_relids))
2094  continue;
2095 
2096  foreach(lc2, cur_ec->ec_members)
2097  {
2098  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
2099 
2100  if (cur_em->em_is_const)
2101  continue; /* ignore consts here */
2102 
2103  /* Does it reference parent_rel? */
2104  if (bms_overlap(cur_em->em_relids, parent_rel->relids))
2105  {
2106  /* Yes, generate transformed child version */
2107  Expr *child_expr;
2108  Relids new_relids;
2109  Relids new_nullable_relids;
2110 
2111  child_expr = (Expr *)
2113  (Node *) cur_em->em_expr,
2114  appinfo);
2115 
2116  /*
2117  * Transform em_relids to match. Note we do *not* do
2118  * pull_varnos(child_expr) here, as for example the
2119  * transformation might have substituted a constant, but we
2120  * don't want the child member to be marked as constant.
2121  */
2122  new_relids = bms_difference(cur_em->em_relids,
2123  parent_rel->relids);
2124  new_relids = bms_add_members(new_relids, child_rel->relids);
2125 
2126  /*
2127  * And likewise for nullable_relids. Note this code assumes
2128  * parent and child relids are singletons.
2129  */
2130  new_nullable_relids = cur_em->em_nullable_relids;
2131  if (bms_overlap(new_nullable_relids, parent_rel->relids))
2132  {
2133  new_nullable_relids = bms_difference(new_nullable_relids,
2134  parent_rel->relids);
2135  new_nullable_relids = bms_add_members(new_nullable_relids,
2136  child_rel->relids);
2137  }
2138 
2139  (void) add_eq_member(cur_ec, child_expr,
2140  new_relids, new_nullable_relids,
2141  true, cur_em->em_datatype);
2142  }
2143  }
2144  }
2145 }
RelOptKind reloptkind
Definition: relation.h:487
Relids em_nullable_relids
Definition: relation.h:764
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:283
Definition: nodes.h:508
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, AppendRelInfo *appinfo)
Definition: prepunion.c:1733
Relids ec_relids
Definition: relation.h:717
Relids relids
Definition: relation.h:490
Relids em_relids
Definition: relation.h:763
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:232
bool ec_has_volatile
Definition: relation.h:720
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, Relids nullable_relids, bool is_child, Oid datatype)
Definition: equivclass.c:505
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:725
List * ec_members
Definition: relation.h:714
void add_paths_to_joinrel ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
SpecialJoinInfo sjinfo,
List restrictlist 
)

Definition at line 88 of file joinpath.c.

References PlannerInfo::all_baserels, bms_add_members(), bms_difference(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), enable_hashjoin, enable_mergejoin, RelOptInfo::fdwroutine, FdwRoutine::GetForeignJoinPaths, hash_inner_and_outer(), JOIN_ANTI, JOIN_FULL, PlannerInfo::join_info_list, JOIN_SEMI, SpecialJoinInfo::jointype, RelOptInfo::lateral_relids, lfirst, match_unsorted_outer(), JoinPathExtraData::mergeclause_list, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, NULL, JoinPathExtraData::param_source_rels, RelOptInfo::relids, JoinPathExtraData::restrictlist, select_mergejoin_clauses(), JoinPathExtraData::semifactors, set_join_pathlist_hook, JoinPathExtraData::sjinfo, and sort_inner_and_outer().

Referenced by make_join_rel().

95 {
96  JoinPathExtraData extra;
97  bool mergejoin_allowed = true;
98  ListCell *lc;
99 
100  extra.restrictlist = restrictlist;
101  extra.mergeclause_list = NIL;
102  extra.sjinfo = sjinfo;
103  extra.param_source_rels = NULL;
104 
105  /*
106  * Find potential mergejoin clauses. We can skip this if we are not
107  * interested in doing a mergejoin. However, mergejoin may be our only
108  * way of implementing a full outer join, so override enable_mergejoin if
109  * it's a full join.
110  */
111  if (enable_mergejoin || jointype == JOIN_FULL)
113  joinrel,
114  outerrel,
115  innerrel,
116  restrictlist,
117  jointype,
118  &mergejoin_allowed);
119 
120  /*
121  * If it's SEMI or ANTI join, compute correction factors for cost
122  * estimation. These will be the same for all paths.
123  */
124  if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
125  compute_semi_anti_join_factors(root, outerrel, innerrel,
126  jointype, sjinfo, restrictlist,
127  &extra.semifactors);
128 
129  /*
130  * Decide whether it's sensible to generate parameterized paths for this
131  * joinrel, and if so, which relations such paths should require. There
132  * is usually no need to create a parameterized result path unless there
133  * is a join order restriction that prevents joining one of our input rels
134  * directly to the parameter source rel instead of joining to the other
135  * input rel. (But see allow_star_schema_join().) This restriction
136  * reduces the number of parameterized paths we have to deal with at
137  * higher join levels, without compromising the quality of the resulting
138  * plan. We express the restriction as a Relids set that must overlap the
139  * parameterization of any proposed join path.
140  */
141  foreach(lc, root->join_info_list)
142  {
143  SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
144 
145  /*
146  * SJ is relevant to this join if we have some part of its RHS
147  * (possibly not all of it), and haven't yet joined to its LHS. (This
148  * test is pretty simplistic, but should be sufficient considering the
149  * join has already been proven legal.) If the SJ is relevant, it
150  * presents constraints for joining to anything not in its RHS.
151  */
152  if (bms_overlap(joinrel->relids, sjinfo2->min_righthand) &&
153  !bms_overlap(joinrel->relids, sjinfo2->min_lefthand))
156  sjinfo2->min_righthand));
157 
158  /* full joins constrain both sides symmetrically */
159  if (sjinfo2->jointype == JOIN_FULL &&
160  bms_overlap(joinrel->relids, sjinfo2->min_lefthand) &&
161  !bms_overlap(joinrel->relids, sjinfo2->min_righthand))
164  sjinfo2->min_lefthand));
165  }
166 
167  /*
168  * However, when a LATERAL subquery is involved, there will simply not be
169  * any paths for the joinrel that aren't parameterized by whatever the
170  * subquery is parameterized by, unless its parameterization is resolved
171  * within the joinrel. So we might as well allow additional dependencies
172  * on whatever residual lateral dependencies the joinrel will have.
173  */
175  joinrel->lateral_relids);
176 
177  /*
178  * 1. Consider mergejoin paths where both relations must be explicitly
179  * sorted. Skip this if we can't mergejoin.
180  */
181  if (mergejoin_allowed)
182  sort_inner_and_outer(root, joinrel, outerrel, innerrel,
183  jointype, &extra);
184 
185  /*
186  * 2. Consider paths where the outer relation need not be explicitly
187  * sorted. This includes both nestloops and mergejoins where the outer
188  * path is already ordered. Again, skip this if we can't mergejoin.
189  * (That's okay because we know that nestloop can't handle right/full
190  * joins at all, so it wouldn't work in the prohibited cases either.)
191  */
192  if (mergejoin_allowed)
193  match_unsorted_outer(root, joinrel, outerrel, innerrel,
194  jointype, &extra);
195 
196 #ifdef NOT_USED
197 
198  /*
199  * 3. Consider paths where the inner relation need not be explicitly
200  * sorted. This includes mergejoins only (nestloops were already built in
201  * match_unsorted_outer).
202  *
203  * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
204  * significant difference between the inner and outer side of a mergejoin,
205  * so match_unsorted_inner creates no paths that aren't equivalent to
206  * those made by match_unsorted_outer when add_paths_to_joinrel() is
207  * invoked with the two rels given in the other order.
208  */
209  if (mergejoin_allowed)
210  match_unsorted_inner(root, joinrel, outerrel, innerrel,
211  jointype, &extra);
212 #endif
213 
214  /*
215  * 4. Consider paths where both outer and inner relations must be hashed
216  * before being joined. As above, disregard enable_hashjoin for full
217  * joins, because there may be no other alternative.
218  */
219  if (enable_hashjoin || jointype == JOIN_FULL)
220  hash_inner_and_outer(root, joinrel, outerrel, innerrel,
221  jointype, &extra);
222 
223  /*
224  * 5. If inner and outer relations are foreign tables (or joins) belonging
225  * to the same server and assigned to the same user to check access
226  * permissions as, give the FDW a chance to push down joins.
227  */
228  if (joinrel->fdwroutine &&
230  joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
231  outerrel, innerrel,
232  jointype, &extra);
233 
234  /*
235  * 6. Finally, give extensions a chance to manipulate the path list.
236  */
238  set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
239  jointype, &extra);
240 }
#define NIL
Definition: pg_list.h:69
SemiAntiJoinFactors semifactors
Definition: relation.h:2052
List * join_info_list
Definition: relation.h:247
Relids min_righthand
Definition: relation.h:1808
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:283
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1324
Relids lateral_relids
Definition: relation.h:515
SpecialJoinInfo * sjinfo
Definition: relation.h:2051
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:645
Relids all_baserels
Definition: relation.h:193
GetForeignJoinPaths_function GetForeignJoinPaths
Definition: fdwapi.h:187
Relids param_source_rels
Definition: relation.h:2053
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:808
struct FdwRoutine * fdwroutine
Definition: relation.h:540
List * mergeclause_list
Definition: relation.h:2050
Relids relids
Definition: relation.h:490
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:1568
List * restrictlist
Definition: relation.h:2049
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:26
bool enable_mergejoin
Definition: costsize.c:127
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
void compute_semi_anti_join_factors(PlannerInfo *root, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist, SemiAntiJoinFactors *semifactors)
Definition: costsize.c:3506
JoinType jointype
Definition: relation.h:1811
bool enable_hashjoin
Definition: costsize.c:128
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
Relids min_lefthand
Definition: relation.h:1807
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:725
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1047
Expr* adjust_rowcompare_for_index ( RowCompareExpr clause,
IndexOptInfo index,
int  indexcol,
List **  indexcolnos,
bool var_on_left_p 
)

Definition at line 3805 of file indxpath.c.

References Assert, bms_is_member(), BOOLOID, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, contain_volatile_functions(), copyObject(), elog, ERROR, get_commutator(), get_op_opfamily_properties(), get_op_opfamily_strategy(), get_opfamily_member(), i, IndexOptInfo::indexcollations, IndexCollMatchesExprColl, RowCompareExpr::inputcollids, InvalidOid, lappend_int(), lappend_oid(), RowCompareExpr::largs, lfirst, lfirst_oid, linitial, linitial_oid, list_copy(), list_head(), list_length(), list_make1_int, list_make1_oid, list_truncate(), lnext, make_opclause(), makeNode, match_index_to_operand(), IndexOptInfo::ncolumns, NIL, NULL, OidIsValid, RowCompareExpr::opfamilies, IndexOptInfo::opfamily, RowCompareExpr::opnos, pull_varnos(), RowCompareExpr::rargs, RowCompareExpr::rctype, IndexOptInfo::rel, RelOptInfo::relid, ROWCOMPARE_GE, and ROWCOMPARE_LE.

Referenced by expand_indexqual_rowcompare(), and fix_indexqual_references().

3810 {
3811  bool var_on_left;
3812  int op_strategy;
3813  Oid op_lefttype;
3814  Oid op_righttype;
3815  int matching_cols;
3816  Oid expr_op;
3817  List *opfamilies;
3818  List *lefttypes;
3819  List *righttypes;
3820  List *new_ops;
3821  ListCell *largs_cell;
3822  ListCell *rargs_cell;
3823  ListCell *opnos_cell;
3824  ListCell *collids_cell;
3825 
3826  /* We have to figure out (again) how the first col matches */
3827  var_on_left = match_index_to_operand((Node *) linitial(clause->largs),
3828  indexcol, index);
3829  Assert(var_on_left ||
3831  indexcol, index));
3832  *var_on_left_p = var_on_left;
3833 
3834  expr_op = linitial_oid(clause->opnos);
3835  if (!var_on_left)
3836  expr_op = get_commutator(expr_op);
3837  get_op_opfamily_properties(expr_op, index->opfamily[indexcol], false,
3838  &op_strategy,
3839  &op_lefttype,
3840  &op_righttype);
3841 
3842  /* Initialize returned list of which index columns are used */
3843  *indexcolnos = list_make1_int(indexcol);
3844 
3845  /* Build lists of the opfamilies and operator datatypes in case needed */
3846  opfamilies = list_make1_oid(index->opfamily[indexcol]);
3847  lefttypes = list_make1_oid(op_lefttype);
3848  righttypes = list_make1_oid(op_righttype);
3849 
3850  /*
3851  * See how many of the remaining columns match some index column in the
3852  * same way. As in match_clause_to_indexcol(), the "other" side of any
3853  * potential index condition is OK as long as it doesn't use Vars from the
3854  * indexed relation.
3855  */
3856  matching_cols = 1;
3857  largs_cell = lnext(list_head(clause->largs));
3858  rargs_cell = lnext(list_head(clause->rargs));
3859  opnos_cell = lnext(list_head(clause->opnos));
3860  collids_cell = lnext(list_head(clause->inputcollids));
3861 
3862  while (largs_cell != NULL)
3863  {
3864  Node *varop;
3865  Node *constop;
3866  int i;
3867 
3868  expr_op = lfirst_oid(opnos_cell);
3869  if (var_on_left)
3870  {
3871  varop = (Node *) lfirst(largs_cell);
3872  constop = (Node *) lfirst(rargs_cell);
3873  }
3874  else
3875  {
3876  varop = (Node *) lfirst(rargs_cell);
3877  constop = (Node *) lfirst(largs_cell);
3878  /* indexkey is on right, so commute the operator */
3879  expr_op = get_commutator(expr_op);
3880  if (expr_op == InvalidOid)
3881  break; /* operator is not usable */
3882  }
3883  if (bms_is_member(index->rel->relid, pull_varnos(constop)))
3884  break; /* no good, Var on wrong side */
3885  if (contain_volatile_functions(constop))
3886  break; /* no good, volatile comparison value */
3887 
3888  /*
3889  * The Var side can match any column of the index.
3890  */
3891  for (i = 0; i < index->ncolumns; i++)
3892  {
3893  if (match_index_to_operand(varop, i, index) &&
3894  get_op_opfamily_strategy(expr_op,
3895  index->opfamily[i]) == op_strategy &&
3897  lfirst_oid(collids_cell)))
3898  break;
3899  }
3900  if (i >= index->ncolumns)
3901  break; /* no match found */
3902 
3903  /* Add column number to returned list */
3904  *indexcolnos = lappend_int(*indexcolnos, i);
3905 
3906  /* Add opfamily and datatypes to lists */
3907  get_op_opfamily_properties(expr_op, index->opfamily[i], false,
3908  &op_strategy,
3909  &op_lefttype,
3910  &op_righttype);
3911  opfamilies = lappend_oid(opfamilies, index->opfamily[i]);
3912  lefttypes = lappend_oid(lefttypes, op_lefttype);
3913  righttypes = lappend_oid(righttypes, op_righttype);
3914 
3915  /* This column matches, keep scanning */
3916  matching_cols++;
3917  largs_cell = lnext(largs_cell);
3918  rargs_cell = lnext(rargs_cell);
3919  opnos_cell = lnext(opnos_cell);
3920  collids_cell = lnext(collids_cell);
3921  }
3922 
3923  /* Return clause as-is if it's all usable as index quals */
3924  if (matching_cols == list_length(clause->opnos))
3925  return (Expr *) clause;
3926 
3927  /*
3928  * We have to generate a subset rowcompare (possibly just one OpExpr). The
3929  * painful part of this is changing < to <= or > to >=, so deal with that
3930  * first.
3931  */
3932  if (op_strategy == BTLessEqualStrategyNumber ||
3933  op_strategy == BTGreaterEqualStrategyNumber)
3934  {
3935  /* easy, just use the same operators */
3936  new_ops = list_truncate(list_copy(clause->opnos), matching_cols);
3937  }
3938  else
3939  {
3940  ListCell *opfamilies_cell;
3941  ListCell *lefttypes_cell;
3942  ListCell *righttypes_cell;
3943 
3944  if (op_strategy == BTLessStrategyNumber)
3945  op_strategy = BTLessEqualStrategyNumber;
3946  else if (op_strategy == BTGreaterStrategyNumber)
3947  op_strategy = BTGreaterEqualStrategyNumber;
3948  else
3949  elog(ERROR, "unexpected strategy number %d", op_strategy);
3950  new_ops = NIL;
3951  lefttypes_cell = list_head(lefttypes);
3952  righttypes_cell = list_head(righttypes);
3953  foreach(opfamilies_cell, opfamilies)
3954  {
3955  Oid opfam = lfirst_oid(opfamilies_cell);
3956  Oid lefttype = lfirst_oid(lefttypes_cell);
3957  Oid righttype = lfirst_oid(righttypes_cell);
3958 
3959  expr_op = get_opfamily_member(opfam, lefttype, righttype,
3960  op_strategy);
3961  if (!OidIsValid(expr_op)) /* should not happen */
3962  elog(ERROR, "could not find member %d(%u,%u) of opfamily %u",
3963  op_strategy, lefttype, righttype, opfam);
3964  if (!var_on_left)
3965  {
3966  expr_op = get_commutator(expr_op);
3967  if (!OidIsValid(expr_op)) /* should not happen */
3968  elog(ERROR, "could not find commutator of member %d(%u,%u) of opfamily %u",
3969  op_strategy, lefttype, righttype, opfam);
3970  }
3971  new_ops = lappend_oid(new_ops, expr_op);
3972  lefttypes_cell = lnext(lefttypes_cell);
3973  righttypes_cell = lnext(righttypes_cell);
3974  }
3975  }
3976 
3977  /* If we have more than one matching col, create a subset rowcompare */
3978  if (matching_cols > 1)
3979  {
3981 
3982  if (var_on_left)
3983  rc->rctype = (RowCompareType) op_strategy;
3984  else
3985  rc->rctype = (op_strategy == BTLessEqualStrategyNumber) ?
3987  rc->opnos = new_ops;
3989  matching_cols);
3991  matching_cols);
3992  rc->largs = list_truncate((List *) copyObject(clause->largs),
3993  matching_cols);
3994  rc->rargs = list_truncate((List *) copyObject(clause->rargs),
3995  matching_cols);
3996  return (Expr *) rc;
3997  }
3998  else
3999  {
4000  return make_opclause(linitial_oid(new_ops), BOOLOID, false,
4001  copyObject(linitial(clause->largs)),
4002  copyObject(linitial(clause->rargs)),
4003  InvalidOid,
4004  linitial_oid(clause->inputcollids));
4005  }
4006 }
#define NIL
Definition: pg_list.h:69
Oid get_commutator(Oid opno)
Definition: lsyscache.c:1281
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Oid * indexcollations
Definition: relation.h:600
bool match_index_to_operand(Node *operand, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:3161
RowCompareType rctype
Definition: primnodes.h:1007
List * opfamilies
Definition: primnodes.h:1009
List * list_truncate(List *list, int new_size)
Definition: list.c:350
List * list_copy(const List *oldlist)
Definition: list.c:1160
Definition: nodes.h:508
Expr * make_opclause(Oid opno, Oid opresulttype, bool opretset, Expr *leftop, Expr *rightop, Oid opcollid, Oid inputcollid)
Definition: clauses.c:171
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:950
unsigned int Oid
Definition: postgres_ext.h:31
List * lappend_oid(List *list, Oid datum)
Definition: list.c:164
#define OidIsValid(objectId)
Definition: c.h:534
#define BTLessEqualStrategyNumber
Definition: stratnum.h:30
void * copyObject(const void *from)
Definition: copyfuncs.c:4475
RelOptInfo * rel
Definition: relation.h:590
#define linitial(l)
Definition: pg_list.h:110
#define ERROR
Definition: elog.h:43
#define IndexCollMatchesExprColl(idxcollation, exprcollation)
Definition: indxpath.c:46
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:163
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
#define list_make1_int(x1)
Definition: pg_list.h:139
int ncolumns
Definition: relation.h:598
#define lnext(lc)
Definition: pg_list.h:105
Relids pull_varnos(Node *node)
Definition: var.c:95
List * lappend_int(List *list, int datum)
Definition: list.c:146
Index relid
Definition: relation.h:518
#define list_make1_oid(x1)
Definition: pg_list.h:145
#define InvalidOid
Definition: postgres_ext.h:36
RowCompareType
Definition: primnodes.h:993
#define makeNode(_type_)
Definition: nodes.h:556
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define lfirst(lc)
Definition: pg_list.h:106
#define linitial_oid(l)
Definition: pg_list.h:112
static int list_length(const List *l)
Definition: pg_list.h:89
#define BOOLOID
Definition: pg_type.h:288
Oid * opfamily
Definition: relation.h:601
int get_op_opfamily_strategy(Oid opno, Oid opfamily)
Definition: lsyscache.c:80
void get_op_opfamily_properties(Oid opno, Oid opfamily, bool ordering_op, int *strategy, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:133
int i
#define elog
Definition: elog.h:219
List * inputcollids
Definition: primnodes.h:1010
#define BTLessStrategyNumber
Definition: stratnum.h:29
Definition: pg_list.h:45
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:419
#define BTGreaterEqualStrategyNumber
Definition: stratnum.h:32
#define lfirst_oid(lc)
Definition: pg_list.h:108
List* build_expression_pathkey ( PlannerInfo root,
Expr expr,
Relids  nullable_relids,
Oid  opno,
Relids  rel,
bool  create_it 
)

Definition at line 526 of file pathkeys.c.

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

Referenced by set_function_pathlist().

532 {
533  List *pathkeys;
534  Oid opfamily,
535  opcintype;
536  int16 strategy;
537  PathKey *cpathkey;
538 
539  /* Find the operator in pg_amop --- failure shouldn't happen */
540  if (!get_ordering_op_properties(opno,
541  &opfamily, &opcintype, &strategy))
542  elog(ERROR, "operator %u is not a valid ordering operator",
543  opno);
544 
545  cpathkey = make_pathkey_from_sortinfo(root,
546  expr,
547  nullable_relids,
548  opfamily,
549  opcintype,
550  exprCollation((Node *) expr),
551  (strategy == BTGreaterStrategyNumber),
552  (strategy == BTGreaterStrategyNumber),
553  0,
554  rel,
555  create_it);
556 
557  if (cpathkey)
558  pathkeys = list_make1(cpathkey);
559  else
560  pathkeys = NIL;
561 
562  return pathkeys;
563 }
signed short int16
Definition: c.h:252
#define NIL
Definition: pg_list.h:69
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Definition: nodes.h:508
unsigned int Oid
Definition: postgres_ext.h:31
#define list_make1(x1)
Definition: pg_list.h:133
#define ERROR
Definition: elog.h:43
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, int16 *strategy)
Definition: lsyscache.c:204
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:745
#define elog
Definition: elog.h:219
static PathKey * make_pathkey_from_sortinfo(PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opfamily, Oid opcintype, Oid collation, bool reverse_sort, bool nulls_first, Index sortref, Relids rel, bool create_it)
Definition: pathkeys.c:170
Definition: pg_list.h:45
List* build_index_pathkeys ( PlannerInfo root,
IndexOptInfo index,
ScanDirection  scandir 
)

Definition at line 433 of file pathkeys.c.

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

Referenced by build_index_paths().

436 {
437  List *retval = NIL;
438  ListCell *lc;
439  int i;
440 
441  if (index->sortopfamily == NULL)
442  return NIL; /* non-orderable index */
443 
444  i = 0;
445  foreach(lc, index->indextlist)
446  {
447  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
448  Expr *indexkey;
449  bool reverse_sort;
450  bool nulls_first;
451  PathKey *cpathkey;
452 
453  /* We assume we don't need to make a copy of the tlist item */
454  indexkey = indextle->expr;
455 
456  if (ScanDirectionIsBackward(scandir))
457  {
458  reverse_sort = !index->reverse_sort[i];
459  nulls_first = !index->nulls_first[i];
460  }
461  else
462  {
463  reverse_sort = index->reverse_sort[i];
464  nulls_first = index->nulls_first[i];
465  }
466 
467  /*
468  * OK, try to make a canonical pathkey for this sort key. Note we're
469  * underneath any outer joins, so nullable_relids should be NULL.
470  */
471  cpathkey = make_pathkey_from_sortinfo(root,
472  indexkey,
473  NULL,
474  index->sortopfamily[i],
475  index->opcintype[i],
476  index->indexcollations[i],
477  reverse_sort,
478  nulls_first,
479  0,
480  index->rel->relids,
481  false);
482 
483  if (cpathkey)
484  {
485  /*
486  * We found the sort key in an EquivalenceClass, so it's relevant
487  * for this query. Add it to list, unless it's redundant.
488  */
489  if (!pathkey_is_redundant(cpathkey, retval))
490  retval = lappend(retval, cpathkey);
491  }
492  else
493  {
494  /*
495  * Boolean index keys might be redundant even if they do not
496  * appear in an EquivalenceClass, because of our special treatment
497  * of boolean equality conditions --- see the comment for
498  * indexcol_is_bool_constant_for_query(). If that applies, we can
499  * continue to examine lower-order index columns. Otherwise, the
500  * sort key is not an interesting sort order for this query, so we
501  * should stop considering index columns; any lower-order sort
502  * keys won't be useful either.
503  */
505  break;
506  }
507 
508  i++;
509  }
510 
511  return retval;
512 }
#define NIL
Definition: pg_list.h:69
Oid * indexcollations
Definition: relation.h:600
List * indextlist
Definition: relation.h:613
Oid * sortopfamily
Definition: relation.h:603
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
RelOptInfo * rel
Definition: relation.h:590
Relids relids
Definition: relation.h:490
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:128
List * lappend(List *list, void *datum)
Definition: list.c:128
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
Expr * expr
Definition: primnodes.h:1330
Oid * opcintype
Definition: relation.h:602
bool indexcol_is_bool_constant_for_query(IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3112
int i
static PathKey * make_pathkey_from_sortinfo(PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opfamily, Oid opcintype, Oid collation, bool reverse_sort, bool nulls_first, Index sortref, Relids rel, bool create_it)
Definition: pathkeys.c:170
bool * nulls_first
Definition: relation.h:605
bool * reverse_sort
Definition: relation.h:604
Definition: pg_list.h:45
List* build_join_pathkeys ( PlannerInfo root,
RelOptInfo joinrel,
JoinType  jointype,
List outer_pathkeys 
)

Definition at line 795 of file pathkeys.c.

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

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

799 {
800  if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
801  return NIL;
802 
803  /*
804  * This used to be quite a complex bit of code, but now that all pathkey
805  * sublists start out life canonicalized, we don't have to do a darn thing
806  * here!
807  *
808  * We do, however, need to truncate the pathkeys list, since it may
809  * contain pathkeys that were useful for forming this joinrel but are
810  * uninteresting to higher levels.
811  */
812  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
813 }
#define NIL
Definition: pg_list.h:69
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:1491
Expr* canonicalize_ec_expression ( Expr expr,
Oid  req_type,
Oid  req_collation 
)

Definition at line 456 of file equivclass.c.

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

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

457 {
458  Oid expr_type = exprType((Node *) expr);
459 
460  /*
461  * For a polymorphic-input-type opclass, just keep the same exposed type.
462  */
463  if (IsPolymorphicType(req_type))
464  req_type = expr_type;
465 
466  /*
467  * No work if the expression exposes the right type/collation already.
468  */
469  if (expr_type != req_type ||
470  exprCollation((Node *) expr) != req_collation)
471  {
472  /*
473  * Strip any existing RelabelType, then add a new one if needed. This
474  * is to preserve the invariant of no redundant RelabelTypes.
475  *
476  * If we have to change the exposed type of the stripped expression,
477  * set typmod to -1 (since the new type may not have the same typmod
478  * interpretation). If we only have to change collation, preserve the
479  * exposed typmod.
480  */
481  while (expr && IsA(expr, RelabelType))
482  expr = (Expr *) ((RelabelType *) expr)->arg;
483 
484  if (exprType((Node *) expr) != req_type)
485  expr = (Expr *) makeRelabelType(expr,
486  req_type,
487  -1,
488  req_collation,
490  else if (exprCollation((Node *) expr) != req_collation)
491  expr = (Expr *) makeRelabelType(expr,
492  req_type,
493  exprTypmod((Node *) expr),
494  req_collation,
496  }
497 
498  return expr;
499 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:559
int32 exprTypmod(const Node *expr)
Definition: nodeFuncs.c:273
Definition: nodes.h:508
unsigned int Oid
Definition: postgres_ext.h:31
#define IsPolymorphicType(typid)
Definition: pg_type.h:733
RelabelType * makeRelabelType(Expr *arg, Oid rtype, int32 rtypmod, Oid rcollid, CoercionForm rformat)
Definition: makefuncs.c:399
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:745
void * arg
void check_index_predicates ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 2759 of file indxpath.c.

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

Referenced by set_plain_rel_size(), and set_tablesample_rel_size().

2760 {
2761  List *clauselist;
2762  bool have_partial;
2763  bool is_target_rel;
2764  Relids otherrels;
2765  ListCell *lc;
2766 
2767  /*
2768  * Initialize the indrestrictinfo lists to be identical to
2769  * baserestrictinfo, and check whether there are any partial indexes. If
2770  * not, this is all we need to do.
2771  */
2772  have_partial = false;
2773  foreach(lc, rel->indexlist)
2774  {
2776 
2777  index->indrestrictinfo = rel->baserestrictinfo;
2778  if (index->indpred)
2779  have_partial = true;
2780  }
2781  if (!have_partial)
2782  return;
2783 
2784  /*
2785  * Construct a list of clauses that we can assume true for the purpose of
2786  * proving the index(es) usable. Restriction clauses for the rel are
2787  * always usable, and so are any join clauses that are "movable to" this
2788  * rel. Also, we can consider any EC-derivable join clauses (which must
2789  * be "movable to" this rel, by definition).
2790  */
2791  clauselist = list_copy(rel->baserestrictinfo);
2792 
2793  /* Scan the rel's join clauses */
2794  foreach(lc, rel->joininfo)
2795  {
2796  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2797 
2798  /* Check if clause can be moved to this rel */
2799  if (!join_clause_is_movable_to(rinfo, rel))
2800  continue;
2801 
2802  clauselist = lappend(clauselist, rinfo);
2803  }
2804 
2805  /*
2806  * Add on any equivalence-derivable join clauses. Computing the correct
2807  * relid sets for generate_join_implied_equalities is slightly tricky
2808  * because the rel could be a child rel rather than a true baserel, and in
2809  * that case we must remove its parents' relid(s) from all_baserels.
2810  */
2811  if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
2812  otherrels = bms_difference(root->all_baserels,
2813  find_childrel_parents(root, rel));
2814  else
2815  otherrels = bms_difference(root->all_baserels, rel->relids);
2816 
2817  if (!bms_is_empty(otherrels))
2818  clauselist =
2819  list_concat(clauselist,
2821  bms_union(rel->relids,
2822  otherrels),
2823  otherrels,
2824  rel));
2825 
2826  /*
2827  * Normally we remove quals that are implied by a partial index's
2828  * predicate from indrestrictinfo, indicating that they need not be
2829  * checked explicitly by an indexscan plan using this index. However, if
2830  * the rel is a target relation of UPDATE/DELETE/SELECT FOR UPDATE, we
2831  * cannot remove such quals from the plan, because they need to be in the
2832  * plan so that they will be properly rechecked by EvalPlanQual testing.
2833  * Some day we might want to remove such quals from the main plan anyway
2834  * and pass them through to EvalPlanQual via a side channel; but for now,
2835  * we just don't remove implied quals at all for target relations.
2836  */
2837  is_target_rel = (rel->relid == root->parse->resultRelation ||
2838  get_plan_rowmark(root->rowMarks, rel->relid) != NULL);
2839 
2840  /*
2841  * Now try to prove each index predicate true, and compute the
2842  * indrestrictinfo lists for partial indexes. Note that we compute the
2843  * indrestrictinfo list even for non-predOK indexes; this might seem
2844  * wasteful, but we may be able to use such indexes in OR clauses, cf
2845  * generate_bitmap_or_paths().
2846  */
2847  foreach(lc, rel->indexlist)
2848  {
2849  IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
2850  ListCell *lcr;
2851 
2852  if (index->indpred == NIL)
2853  continue; /* ignore non-partial indexes here */
2854 
2855  if (!index->predOK) /* don't repeat work if already proven OK */
2856  index->predOK = predicate_implied_by(index->indpred, clauselist);
2857 
2858  /* If rel is an update target, leave indrestrictinfo as set above */
2859  if (is_target_rel)
2860  continue;
2861 
2862  /* Else compute indrestrictinfo as the non-implied quals */
2863  index->indrestrictinfo = NIL;
2864  foreach(lcr, rel->baserestrictinfo)
2865  {
2866  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
2867 
2868  /* predicate_implied_by() assumes first arg is immutable */
2869  if (contain_mutable_functions((Node *) rinfo->clause) ||
2871  index->indpred))
2872  index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
2873  }
2874  }
2875 }
#define NIL
Definition: pg_list.h:69
List * rowMarks
Definition: relation.h:251
Query * parse
Definition: relation.h:152
bool predOK
Definition: relation.h:620
RelOptKind reloptkind
Definition: relation.h:487
bool predicate_implied_by(List *predicate_list, List *restrictinfo_list)
Definition: predtest.c:128
List * baserestrictinfo
Definition: relation.h:544
int resultRelation
Definition: parsenodes.h:113
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:283
List * list_copy(const List *oldlist)
Definition: list.c:1160
Definition: nodes.h:508
List * list_concat(List *list1, List *list2)
Definition: list.c:321
Definition: type.h:90
#define list_make1(x1)
Definition: pg_list.h:133
Relids all_baserels
Definition: relation.h:193
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1033
List * joininfo
Definition: relation.h:549
Relids relids
Definition: relation.h:490
Index relid
Definition: relation.h:518
List * lappend(List *list, void *datum)
Definition: list.c:128
Expr * clause
Definition: relation.h:1637
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:633
List * indrestrictinfo
Definition: relation.h:615
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:977
List * indexlist
Definition: relation.h:527
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:217
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:435
PlanRowMark * get_plan_rowmark(List *rowmarks, Index rtindex)
Definition: preptlist.c:401
bool contain_mutable_functions(Node *clause)
Definition: clauses.c:877
List * indpred
Definition: relation.h:611
Definition: pg_list.h:45
PathKeysComparison compare_pathkeys ( List keys1,
List keys2 
)

Definition at line 278 of file pathkeys.c.

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

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

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

Definition at line 2887 of file allpaths.c.

References Max, max_parallel_workers_per_gather, Min, min_parallel_index_scan_size, min_parallel_table_scan_size, RelOptInfo::rel_parallel_workers, RELOPT_BASEREL, and RelOptInfo::reloptkind.

Referenced by cost_index(), and create_plain_partial_paths().

2889 {
2890  int parallel_workers = 0;
2891  int heap_parallel_workers = 1;
2892  int index_parallel_workers = 1;
2893 
2894  /*
2895  * If the user has set the parallel_workers reloption, use that; otherwise
2896  * select a default number of workers.
2897  */
2898  if (rel->rel_parallel_workers != -1)
2899  parallel_workers = rel->rel_parallel_workers;
2900  else
2901  {
2902  int heap_parallel_threshold;
2903  int index_parallel_threshold;
2904 
2905  /*
2906  * If this relation is too small to be worth a parallel scan, just
2907  * return without doing anything ... unless it's an inheritance child.
2908  * In that case, we want to generate a parallel path here anyway. It
2909  * might not be worthwhile just for this relation, but when combined
2910  * with all of its inheritance siblings it may well pay off.
2911  */
2912  if (heap_pages < (BlockNumber) min_parallel_table_scan_size &&
2913  index_pages < (BlockNumber) min_parallel_index_scan_size &&
2914  rel->reloptkind == RELOPT_BASEREL)
2915  return 0;
2916 
2917  if (heap_pages > 0)
2918  {
2919  /*
2920  * Select the number of workers based on the log of the size of
2921  * the relation. This probably needs to be a good deal more
2922  * sophisticated, but we need something here for now. Note that
2923  * the upper limit of the min_parallel_table_scan_size GUC is
2924  * chosen to prevent overflow here.
2925  */
2926  heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
2927  while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
2928  {
2929  heap_parallel_workers++;
2930  heap_parallel_threshold *= 3;
2931  if (heap_parallel_threshold > INT_MAX / 3)
2932  break; /* avoid overflow */
2933  }
2934 
2935  parallel_workers = heap_parallel_workers;
2936  }
2937 
2938  if (index_pages > 0)
2939  {
2940  /* same calculation as for heap_pages above */
2941  index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
2942  while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
2943  {
2944  index_parallel_workers++;
2945  index_parallel_threshold *= 3;
2946  if (index_parallel_threshold > INT_MAX / 3)
2947  break; /* avoid overflow */
2948  }
2949 
2950  if (parallel_workers > 0)
2951  parallel_workers = Min(parallel_workers, index_parallel_workers);
2952  else
2953  parallel_workers = index_parallel_workers;
2954  }
2955  }
2956 
2957  /*
2958  * In no case use more than max_parallel_workers_per_gather workers.
2959  */
2960  parallel_workers = Min(parallel_workers, max_parallel_workers_per_gather);
2961 
2962  return parallel_workers;
2963 }
RelOptKind reloptkind
Definition: relation.h:487
#define Min(x, y)
Definition: c.h:802
uint32 BlockNumber
Definition: block.h:31
int min_parallel_index_scan_size
Definition: allpaths.c:61
int rel_parallel_workers
Definition: relation.h:533
#define Max(x, y)
Definition: c.h:796
int min_parallel_table_scan_size
Definition: allpaths.c:60
int max_parallel_workers_per_gather
Definition: costsize.c:116
List* convert_subquery_pathkeys ( PlannerInfo root,
RelOptInfo rel,
List subquery_pathkeys,
List subquery_tlist 
)

Definition at line 580 of file pathkeys.c.

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

Referenced by set_subquery_pathlist().

583 {
584  List *retval = NIL;
585  int retvallen = 0;
586  int outer_query_keys = list_length(root->query_pathkeys);
587  ListCell *i;
588 
589  foreach(i, subquery_pathkeys)
590  {
591  PathKey *sub_pathkey = (PathKey *) lfirst(i);
592  EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
593  PathKey *best_pathkey = NULL;
594 
595  if (sub_eclass->ec_has_volatile)
596  {
597  /*
598  * If the sub_pathkey's EquivalenceClass is volatile, then it must
599  * have come from an ORDER BY clause, and we have to match it to
600  * that same targetlist entry.
601  */
602  TargetEntry *tle;
603 
604  if (sub_eclass->ec_sortref == 0) /* can't happen */
605  elog(ERROR, "volatile EquivalenceClass has no sortref");
606  tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
607  Assert(tle);
608  /* resjunk items aren't visible to outer query */
609  if (!tle->resjunk)
610  {
611  /* We can represent this sub_pathkey */
612  EquivalenceMember *sub_member;
613  Expr *outer_expr;
614  EquivalenceClass *outer_ec;
615 
616  Assert(list_length(sub_eclass->ec_members) == 1);
617  sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
618  outer_expr = (Expr *) makeVarFromTargetEntry(rel->relid, tle);
619 
620  /*
621  * Note: it might look funny to be setting sortref = 0 for a
622  * reference to a volatile sub_eclass. However, the
623  * expression is *not* volatile in the outer query: it's just
624  * a Var referencing whatever the subquery emitted. (IOW, the
625  * outer query isn't going to re-execute the volatile
626  * expression itself.) So this is okay. Likewise, it's
627  * correct to pass nullable_relids = NULL, because we're
628  * underneath any outer joins appearing in the outer query.
629  */
630  outer_ec =
632  outer_expr,
633  NULL,
634  sub_eclass->ec_opfamilies,
635  sub_member->em_datatype,
636  sub_eclass->ec_collation,
637  0,
638  rel->relids,
639  false);
640 
641  /*
642  * If we don't find a matching EC, sub-pathkey isn't
643  * interesting to the outer query
644  */
645  if (outer_ec)
646  best_pathkey =
648  outer_ec,
649  sub_pathkey->pk_opfamily,
650  sub_pathkey->pk_strategy,
651  sub_pathkey->pk_nulls_first);
652  }
653  }
654  else
655  {
656  /*
657  * Otherwise, the sub_pathkey's EquivalenceClass could contain
658  * multiple elements (representing knowledge that multiple items
659  * are effectively equal). Each element might match none, one, or
660  * more of the output columns that are visible to the outer query.
661  * This means we may have multiple possible representations of the
662  * sub_pathkey in the context of the outer query. Ideally we
663  * would generate them all and put them all into an EC of the
664  * outer query, thereby propagating equality knowledge up to the
665  * outer query. Right now we cannot do so, because the outer
666  * query's EquivalenceClasses are already frozen when this is
667  * called. Instead we prefer the one that has the highest "score"
668  * (number of EC peers, plus one if it matches the outer
669  * query_pathkeys). This is the most likely to be useful in the
670  * outer query.
671  */
672  int best_score = -1;
673  ListCell *j;
674 
675  foreach(j, sub_eclass->ec_members)
676  {
677  EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
678  Expr *sub_expr = sub_member->em_expr;
679  Oid sub_expr_type = sub_member->em_datatype;
680  Oid sub_expr_coll = sub_eclass->ec_collation;
681  ListCell *k;
682 
683  if (sub_member->em_is_child)
684  continue; /* ignore children here */
685 
686  foreach(k, subquery_tlist)
687  {
688  TargetEntry *tle = (TargetEntry *) lfirst(k);
689  Expr *tle_expr;
690  Expr *outer_expr;
691  EquivalenceClass *outer_ec;
692  PathKey *outer_pk;
693  int score;
694 
695  /* resjunk items aren't visible to outer query */
696  if (tle->resjunk)
697  continue;
698 
699  /*
700  * The targetlist entry is considered to match if it
701  * matches after sort-key canonicalization. That is
702  * needed since the sub_expr has been through the same
703  * process.
704  */
705  tle_expr = canonicalize_ec_expression(tle->expr,
706  sub_expr_type,
707  sub_expr_coll);
708  if (!equal(tle_expr, sub_expr))
709  continue;
710 
711  /*
712  * Build a representation of this targetlist entry as an
713  * outer Var.
714  */
715  outer_expr = (Expr *) makeVarFromTargetEntry(rel->relid,
716  tle);
717 
718  /* See if we have a matching EC for that */
719  outer_ec = get_eclass_for_sort_expr(root,
720  outer_expr,
721  NULL,
722  sub_eclass->ec_opfamilies,
723  sub_expr_type,
724  sub_expr_coll,
725  0,
726  rel->relids,
727  false);
728 
729  /*
730  * If we don't find a matching EC, this sub-pathkey isn't
731  * interesting to the outer query
732  */
733  if (!outer_ec)
734  continue;
735 
736  outer_pk = make_canonical_pathkey(root,
737  outer_ec,
738  sub_pathkey->pk_opfamily,
739  sub_pathkey->pk_strategy,
740  sub_pathkey->pk_nulls_first);
741  /* score = # of equivalence peers */
742  score = list_length(outer_ec->ec_members) - 1;
743  /* +1 if it matches the proper query_pathkeys item */
744  if (retvallen < outer_query_keys &&
745  list_nth(root->query_pathkeys, retvallen) == outer_pk)
746  score++;
747  if (score > best_score)
748  {
749  best_pathkey = outer_pk;
750  best_score = score;
751  }
752  }
753  }
754  }
755 
756  /*
757  * If we couldn't find a representation of this sub_pathkey, we're
758  * done (we can't use the ones to its right, either).
759  */
760  if (!best_pathkey)
761  break;
762 
763  /*
764  * Eliminate redundant ordering info; could happen if outer query
765  * equivalences subquery keys...
766  */
767  if (!pathkey_is_redundant(best_pathkey, retval))
768  {
769  retval = lappend(retval, best_pathkey);
770  retvallen++;
771  }
772  }
773 
774  return retval;
775 }
#define NIL
Definition: pg_list.h:69
List * query_pathkeys
Definition: relation.h:257
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2870
EquivalenceClass * get_eclass_for_sort_expr(PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
Definition: equivclass.c:581
Var * makeVarFromTargetEntry(Index varno, TargetEntry *tle)
Definition: makefuncs.c:104
Index ec_sortref
Definition: relation.h:723
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:51
unsigned int Oid
Definition: postgres_ext.h:31
int pk_strategy
Definition: relation.h:793
bool resjunk
Definition: primnodes.h:1337
#define linitial(l)
Definition: pg_list.h:110
bool pk_nulls_first
Definition: relation.h:794
#define ERROR
Definition: elog.h:43
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:456
void * list_nth(const List *list, int n)
Definition: list.c:410
Relids relids
Definition: relation.h:490
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:128
TargetEntry * get_sortgroupref_tle(Index sortref, List *targetList)
Definition: tlist.c:348
Index relid
Definition: relation.h:518
List * lappend(List *list, void *datum)
Definition: list.c:128
List * ec_opfamilies
Definition: relation.h:712
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define lfirst(lc)
Definition: pg_list.h:106
Expr * expr
Definition: primnodes.h:1330
EquivalenceClass * pk_eclass
Definition: relation.h:791
static int list_length(const List *l)
Definition: pg_list.h:89
bool ec_has_volatile
Definition: relation.h:720
Oid pk_opfamily
Definition: relation.h:792
int i
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
List * ec_members
Definition: relation.h:714
void create_index_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 232 of file indxpath.c.

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

Referenced by set_plain_rel_pathlist().

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

Definition at line 253 of file tidpath.c.

References add_path(), create_tidscan_path(), RelOptInfo::lateral_relids, and TidQualFromBaseRestrictinfo().

Referenced by set_plain_rel_pathlist().

254 {
255  Relids required_outer;
256  List *tidquals;
257 
258  /*
259  * We don't support pushing join clauses into the quals of a tidscan, but
260  * it could still have required parameterization due to LATERAL refs in
261  * its tlist.
262  */
263  required_outer = rel->lateral_relids;
264 
265  tidquals = TidQualFromBaseRestrictinfo(rel);
266 
267  if (tidquals)
268  add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
269  required_outer));
270 }
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
static List * TidQualFromBaseRestrictinfo(RelOptInfo *rel)
Definition: tidpath.c:223
Relids lateral_relids
Definition: relation.h:515
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1171
Definition: pg_list.h:45
Definition: relation.h:888
bool eclass_useful_for_merging ( PlannerInfo root,
EquivalenceClass eclass,
RelOptInfo rel 
)

Definition at line 2393 of file equivclass.c.

References Assert, bms_is_subset(), bms_overlap(), EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_relids, EquivalenceMember::em_is_child, EquivalenceMember::em_relids, find_childrel_top_parent(), lfirst, list_length(), RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, and RelOptInfo::reloptkind.

Referenced by get_useful_ecs_for_relation(), and pathkeys_useful_for_merging().

2396 {
2397  Relids relids;
2398  ListCell *lc;
2399 
2400  Assert(!eclass->ec_merged);
2401 
2402  /*
2403  * Won't generate joinclauses if const or single-member (the latter test
2404  * covers the volatile case too)
2405  */
2406  if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
2407  return false;
2408 
2409  /*
2410  * Note we don't test ec_broken; if we did, we'd need a separate code path
2411  * to look through ec_sources. Checking the members anyway is OK as a
2412  * possibly-overoptimistic heuristic.
2413  */
2414 
2415  /* If specified rel is a child, we must consider the topmost parent rel */
2416  if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
2417  relids = find_childrel_top_parent(root, rel)->relids;
2418  else
2419  relids = rel->relids;
2420 
2421  /* If rel already includes all members of eclass, no point in searching */
2422  if (bms_is_subset(eclass->ec_relids, relids))
2423  return false;
2424 
2425  /* To join, we need a member not in the given rel */
2426  foreach(lc, eclass->ec_members)
2427  {
2428  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
2429 
2430  if (cur_em->em_is_child)
2431  continue; /* ignore children here */
2432 
2433  if (!bms_overlap(cur_em->em_relids, relids))
2434  return true;
2435  }
2436 
2437  return false;
2438 }
RelOptInfo * find_childrel_top_parent(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:951
RelOptKind reloptkind
Definition: relation.h:487
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
Relids ec_relids
Definition: relation.h:717
Relids relids
Definition: relation.h:490
Relids em_relids
Definition: relation.h:763
#define Assert(condition)
Definition: c.h:671
#define lfirst(lc)
Definition: pg_list.h:106
static int list_length(const List *l)
Definition: pg_list.h:89
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
struct EquivalenceClass * ec_merged
Definition: relation.h:726
List * ec_members
Definition: relation.h:714
void expand_indexqual_conditions ( IndexOptInfo index,
List indexclauses,
List indexclausecols,
List **  indexquals_p,
List **  indexqualcols_p 
)

Definition at line 3507 of file indxpath.c.

References IndexOptInfo::amsearchnulls, Assert, RestrictInfo::clause, elog, ERROR, expand_boolean_index_clause(), expand_indexqual_opclause(), expand_indexqual_rowcompare(), forboth, IndexOptInfo::indexcollations, is_opclause, IsA, IsBooleanOpfamily, lappend(), lappend_int(), lfirst, lfirst_int, list_concat(), list_length(), make_simple_restrictinfo, NIL, nodeTag, and IndexOptInfo::opfamily.

Referenced by create_index_path().

3510 {
3511  List *indexquals = NIL;
3512  List *indexqualcols = NIL;
3513  ListCell *lcc,
3514  *lci;
3515 
3516  forboth(lcc, indexclauses, lci, indexclausecols)
3517  {
3518  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcc);
3519  int indexcol = lfirst_int(lci);
3520  Expr *clause = rinfo->clause;
3521  Oid curFamily = index->opfamily[indexcol];
3522  Oid curCollation = index->indexcollations[indexcol];
3523 
3524  /* First check for boolean cases */
3525  if (IsBooleanOpfamily(curFamily))
3526  {
3527  Expr *boolqual;
3528 
3529  boolqual = expand_boolean_index_clause((Node *) clause,
3530  indexcol,
3531  index);
3532  if (boolqual)
3533  {
3534  indexquals = lappend(indexquals,
3535  make_simple_restrictinfo(boolqual));
3536  indexqualcols = lappend_int(indexqualcols, indexcol);
3537  continue;
3538  }
3539  }
3540 
3541  /*
3542  * Else it must be an opclause (usual case), ScalarArrayOp,
3543  * RowCompare, or NullTest
3544  */
3545  if (is_opclause(clause))
3546  {
3547  indexquals = list_concat(indexquals,
3549  curFamily,
3550  curCollation));
3551  /* expand_indexqual_opclause can produce multiple clauses */
3552  while (list_length(indexqualcols) < list_length(indexquals))
3553  indexqualcols = lappend_int(indexqualcols, indexcol);
3554  }
3555  else if (IsA(clause, ScalarArrayOpExpr))
3556  {
3557  /* no extra work at this time */
3558  indexquals = lappend(indexquals, rinfo);
3559  indexqualcols = lappend_int(indexqualcols, indexcol);
3560  }
3561  else if (IsA(clause, RowCompareExpr))
3562  {
3563  indexquals = lappend(indexquals,
3565  index,
3566  indexcol));
3567  indexqualcols = lappend_int(indexqualcols, indexcol);
3568  }
3569  else if (IsA(clause, NullTest))
3570  {
3571  Assert(index->amsearchnulls);
3572  indexquals = lappend(indexquals, rinfo);
3573  indexqualcols = lappend_int(indexqualcols, indexcol);
3574  }
3575  else
3576  elog(ERROR, "unsupported indexqual type: %d",
3577  (int) nodeTag(clause));
3578  }
3579 
3580  *indexquals_p = indexquals;
3581  *indexqualcols_p = indexqualcols;
3582 }
#define NIL
Definition: pg_list.h:69
#define IsBooleanOpfamily(opfamily)
Definition: indxpath.c:43
#define IsA(nodeptr, _type_)
Definition: nodes.h:559
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:174
Oid * indexcollations
Definition: relation.h:600
Definition: nodes.h:508
List * list_concat(List *list1, List *list2)
Definition: list.c:321
unsigned int Oid
Definition: postgres_ext.h:31
#define ERROR
Definition: elog.h:43
#define is_opclause(clause)
Definition: clauses.h:20
#define lfirst_int(lc)
Definition: pg_list.h:107
static Expr * expand_boolean_index_clause(Node *clause, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:3592
List * lappend_int(List *list, int datum)
Definition: list.c:146
List * lappend(List *list, void *datum)
Definition: list.c:128
Expr * clause
Definition: relation.h:1637
#define Assert(condition)
Definition: c.h:671
#define lfirst(lc)
Definition: pg_list.h:106
static RestrictInfo * expand_indexqual_rowcompare(RestrictInfo *rinfo, IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3752
static int list_length(const List *l)
Definition: pg_list.h:89
#define nodeTag(nodeptr)
Definition: nodes.h:513
Oid * opfamily
Definition: relation.h:601
#define elog
Definition: elog.h:219
bool amsearchnulls
Definition: relation.h:629
static List * expand_indexqual_opclause(RestrictInfo *rinfo, Oid opfamily, Oid idxcollation)
Definition: indxpath.c:3658
Definition: pg_list.h:45
#define make_simple_restrictinfo(clause)
Definition: restrictinfo.h:21
bool exprs_known_equal ( PlannerInfo root,
Node item1,
Node item2 
)

Definition at line 1943 of file equivclass.c.

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

Referenced by add_unique_group_var().

1944 {
1945  ListCell *lc1;
1946 
1947  foreach(lc1, root->eq_classes)
1948  {
1949  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
1950  bool item1member = false;
1951  bool item2member = false;
1952  ListCell *lc2;
1953 
1954  /* Never match to a volatile EC */
1955  if (ec->ec_has_volatile)
1956  continue;
1957 
1958  foreach(lc2, ec->ec_members)
1959  {
1961 
1962  if (em->em_is_child)
1963  continue; /* ignore children here */
1964  if (equal(item1, em->em_expr))
1965  item1member = true;
1966  else if (equal(item2, em->em_expr))
1967  item2member = true;
1968  /* Exit as soon as equality is proven */
1969  if (item1member && item2member)
1970  return true;
1971  }
1972  }
1973  return false;
1974 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2870
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:232
bool ec_has_volatile
Definition: relation.h:720
List * ec_members
Definition: relation.h:714
List* find_mergeclauses_for_pathkeys ( PlannerInfo root,
List pathkeys,
bool  outer_keys,
List restrictinfos 
)

Definition at line 976 of file pathkeys.c.

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

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

980 {
981  List *mergeclauses = NIL;
982  ListCell *i;
983 
984  /* make sure we have eclasses cached in the clauses */
985  foreach(i, restrictinfos)
986  {
987  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
988 
989  update_mergeclause_eclasses(root, rinfo);
990  }
991 
992  foreach(i, pathkeys)
993  {
994  PathKey *pathkey = (PathKey *) lfirst(i);
995  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
996  List *matched_restrictinfos = NIL;
997  ListCell *j;
998 
999  /*----------
1000  * A mergejoin clause matches a pathkey if it has the same EC.
1001  * If there are multiple matching clauses, take them all. In plain
1002  * inner-join scenarios we expect only one match, because
1003  * equivalence-class processing will have removed any redundant
1004  * mergeclauses. However, in outer-join scenarios there might be
1005  * multiple matches. An example is
1006  *
1007  * select * from a full join b
1008  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1009  *
1010  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1011  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1012  * we *must* do so or we will be unable to form a valid plan.
1013  *
1014  * We expect that the given pathkeys list is canonical, which means
1015  * no two members have the same EC, so it's not possible for this
1016  * code to enter the same mergeclause into the result list twice.
1017  *
1018  * It's possible that multiple matching clauses might have different
1019  * ECs on the other side, in which case the order we put them into our
1020  * result makes a difference in the pathkeys required for the other
1021  * input path. However this routine hasn't got any info about which
1022  * order would be best, so we don't worry about that.
1023  *
1024  * It's also possible that the selected mergejoin clauses produce
1025  * a noncanonical ordering of pathkeys for the other side, ie, we
1026  * might select clauses that reference b.v1, b.v2, b.v1 in that
1027  * order. This is not harmful in itself, though it suggests that
1028  * the clauses are partially redundant. Since it happens only with
1029  * redundant query conditions, we don't bother to eliminate it.
1030  * make_inner_pathkeys_for_merge() has to delete duplicates when
1031  * it constructs the canonical pathkeys list, and we also have to
1032  * deal with the case in create_mergejoin_plan().
1033  *----------
1034  */
1035  foreach(j, restrictinfos)
1036  {
1037  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1038  EquivalenceClass *clause_ec;
1039 
1040  if (outer_keys)
1041  clause_ec = rinfo->outer_is_left ?
1042  rinfo->left_ec : rinfo->right_ec;
1043  else
1044  clause_ec = rinfo->outer_is_left ?
1045  rinfo->right_ec : rinfo->left_ec;
1046  if (clause_ec == pathkey_ec)
1047  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1048  }
1049 
1050  /*
1051  * If we didn't find a mergeclause, we're done --- any additional
1052  * sort-key positions in the pathkeys are useless. (But we can still
1053  * mergejoin if we found at least one mergeclause.)
1054  */
1055  if (matched_restrictinfos == NIL)
1056  break;
1057 
1058  /*
1059  * If we did find usable mergeclause(s) for this sort-key position,
1060  * add them to result list.
1061  */
1062  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1063  }
1064 
1065  return mergeclauses;
1066 }
#define NIL
Definition: pg_list.h:69
List * list_concat(List *list1, List *list2)
Definition: list.c:321
EquivalenceClass * right_ec
Definition: relation.h:1686
bool outer_is_left
Definition: relation.h:1692
List * lappend(List *list, void *datum)
Definition: list.c:128
#define lfirst(lc)
Definition: pg_list.h:106
EquivalenceClass * pk_eclass
Definition: relation.h:791
EquivalenceClass * left_ec
Definition: relation.h:1685
int i
Definition: pg_list.h:45
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:941
void generate_base_implied_equalities ( PlannerInfo root)

Definition at line 762 of file equivclass.c.

References Assert, EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, PlannerInfo::eq_classes, generate_base_implied_equalities_broken(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), RelOptInfo::has_eclass_joins, has_relevant_eclass_joinclause(), lfirst, list_length(), NULL, PlannerInfo::simple_rel_array, and PlannerInfo::simple_rel_array_size.

Referenced by query_planner().

763 {
764  ListCell *lc;
765  Index rti;
766 
767  foreach(lc, root->eq_classes)
768  {
770 
771  Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
772  Assert(!ec->ec_broken); /* not yet anyway... */
773 
774  /* Single-member ECs won't generate any deductions */
775  if (list_length(ec->ec_members) <= 1)
776  continue;
777 
778  if (ec->ec_has_const)
780  else
782 
783  /* Recover if we failed to generate required derived clauses */
784  if (ec->ec_broken)
786  }
787 
788  /*
789  * This is also a handy place to mark base rels (which should all exist by
790  * now) with flags showing whether they have pending eclass joins.
791  */
792  for (rti = 1; rti < root->simple_rel_array_size; rti++)
793  {
794  RelOptInfo *brel = root->simple_rel_array[rti];
795 
796  if (brel == NULL)
797  continue;
798 
800  }
801 }
bool has_eclass_joins
Definition: relation.h:551
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:884
static void generate_base_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:976
struct RelOptInfo ** simple_rel_array
Definition: relation.h:176
bool has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
Definition: equivclass.c:2354
int simple_rel_array_size
Definition: relation.h:177
unsigned int Index
Definition: c.h:362
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:232
static int list_length(const List *l)
Definition: pg_list.h:89
static void generate_base_implied_equalities_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:807
struct EquivalenceClass * ec_merged
Definition: relation.h:726
List * ec_members
Definition: relation.h:714
void generate_gather_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 2058 of file allpaths.c.

References add_path(), create_gather_path(), linitial, NIL, NULL, RelOptInfo::partial_pathlist, and RelOptInfo::reltarget.

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

2059 {
2060  Path *cheapest_partial_path;
2061  Path *simple_gather_path;
2062 
2063  /* If there are no partial paths, there's nothing to do here. */
2064  if (rel->partial_pathlist == NIL)
2065  return;
2066 
2067  /*
2068  * The output of Gather is currently always unsorted, so there's only one
2069  * partial path of interest: the cheapest one. That will be the one at
2070  * the front of partial_pathlist because of the way add_partial_path
2071  * works.
2072  *
2073  * Eventually, we should have a Gather Merge operation that can merge
2074  * multiple tuple streams together while preserving their ordering. We
2075  * could usefully generate such a path from each partial path that has
2076  * non-NIL pathkeys.
2077  */
2078  cheapest_partial_path = linitial(rel->partial_pathlist);
2079  simple_gather_path = (Path *)
2080  create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
2081  NULL, NULL);
2082  add_path(rel, simple_gather_path);
2083 }
#define NIL
Definition: pg_list.h:69
GatherPath * create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, Relids required_outer, double *rows)
Definition: pathnode.c:1667
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
List * partial_pathlist
Definition: relation.h:506
#define linitial(l)
Definition: pg_list.h:110
#define NULL
Definition: c.h:226
struct PathTarget * reltarget
Definition: relation.h:501
Definition: relation.h:888
List* generate_implied_equalities_for_column ( PlannerInfo root,
RelOptInfo rel,
ec_matches_callback_type  callback,
void *  callback_arg,
Relids  prohibited_rels 
)

Definition at line 2172 of file equivclass.c.

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

Referenced by match_eclass_clauses_to_index(), and postgresGetForeignPaths().

2177 {
2178  List *result = NIL;
2179  bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
2180  Relids parent_relids;
2181  ListCell *lc1;
2182 
2183  /* If it's a child rel, we'll need to know what its parent(s) are */
2184  if (is_child_rel)
2185  parent_relids = find_childrel_parents(root, rel);
2186  else
2187  parent_relids = NULL; /* not used, but keep compiler quiet */
2188 
2189  foreach(lc1, root->eq_classes)
2190  {
2191  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
2192  EquivalenceMember *cur_em;
2193  ListCell *lc2;
2194 
2195  /*
2196  * Won't generate joinclauses if const or single-member (the latter
2197  * test covers the volatile case too)
2198  */
2199  if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
2200  continue;
2201 
2202  /*
2203  * No point in searching if rel not mentioned in eclass (but we can't
2204  * tell that for a child rel).
2205  */
2206  if (!is_child_rel &&
2207  !bms_is_subset(rel->relids, cur_ec->ec_relids))
2208  continue;
2209 
2210  /*
2211  * Scan members, looking for a match to the target column. Note that
2212  * child EC members are considered, but only when they belong to the
2213  * target relation. (Unlike regular members, the same expression
2214  * could be a child member of more than one EC. Therefore, it's
2215  * potentially order-dependent which EC a child relation's target
2216  * column gets matched to. This is annoying but it only happens in
2217  * corner cases, so for now we live with just reporting the first
2218  * match. See also get_eclass_for_sort_expr.)
2219  */
2220  cur_em = NULL;
2221  foreach(lc2, cur_ec->ec_members)
2222  {
2223  cur_em = (EquivalenceMember *) lfirst(lc2);
2224  if (bms_equal(cur_em->em_relids, rel->relids) &&
2225  callback(root, rel, cur_ec, cur_em, callback_arg))
2226  break;
2227  cur_em = NULL;
2228  }
2229 
2230  if (!cur_em)
2231  continue;
2232 
2233  /*
2234  * Found our match. Scan the other EC members and attempt to generate
2235  * joinclauses.
2236  */
2237  foreach(lc2, cur_ec->ec_members)
2238  {
2239  EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
2240  Oid eq_op;
2241  RestrictInfo *rinfo;
2242 
2243  if (other_em->em_is_child)
2244  continue; /* ignore children here */
2245 
2246  /* Make sure it'll be a join to a different rel */
2247  if (other_em == cur_em ||
2248  bms_overlap(other_em->em_relids, rel->relids))
2249  continue;
2250 
2251  /* Forget it if caller doesn't want joins to this rel */
2252  if (bms_overlap(other_em->em_relids, prohibited_rels))
2253  continue;
2254 
2255  /*
2256  * Also, if this is a child rel, avoid generating a useless join
2257  * to its parent rel(s).
2258  */
2259  if (is_child_rel &&
2260  bms_overlap(parent_relids, other_em->em_relids))
2261  continue;
2262 
2263  eq_op = select_equality_operator(cur_ec,
2264  cur_em->em_datatype,
2265  other_em->em_datatype);
2266  if (!OidIsValid(eq_op))
2267  continue;
2268 
2269  /* set parent_ec to mark as redundant with other joinclauses */
2270  rinfo = create_join_clause(root, cur_ec, eq_op,
2271  cur_em, other_em,
2272  cur_ec);
2273 
2274  result = lappend(result, rinfo);
2275  }
2276 
2277  /*
2278  * If somehow we failed to create any join clauses, we might as well
2279  * keep scanning the ECs for another match. But if we did make any,
2280  * we're done, because we don't want to return non-redundant clauses.
2281  */
2282  if (result)
2283  break;
2284  }
2285 
2286  return result;
2287 }
#define NIL
Definition: pg_list.h:69
static RestrictInfo * create_join_clause(PlannerInfo *root, EquivalenceClass *ec, Oid opno, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
Definition: equivclass.c:1379
RelOptKind reloptkind
Definition: relation.h:487
unsigned int Oid
Definition: postgres_ext.h:31
#define OidIsValid(objectId)
Definition: c.h:534
static void callback(struct sockaddr *addr, struct sockaddr *mask, void *unused)
Definition: test_ifaddrs.c:49
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
static Oid select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
Definition: equivclass.c:1344
Relids ec_relids
Definition: relation.h:717
Relids relids
Definition: relation.h:490
List * lappend(List *list, void *datum)
Definition: list.c:128
Relids em_relids
Definition: relation.h:763
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:977
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:232
static int list_length(const List *l)
Definition: pg_list.h:89
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
Definition: pg_list.h:45
List * ec_members
Definition: relation.h:714
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:130
List* generate_join_implied_equalities ( PlannerInfo root,
Relids  join_relids,
Relids  outer_relids,
RelOptInfo inner_rel 
)

Definition at line 1033 of file equivclass.c.

References PlannerInfo::eq_classes, and generate_join_implied_equalities_for_ecs().

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

1037 {
1039  root->eq_classes,
1040  join_relids,
1041  outer_relids,
1042  inner_rel);
1043 }
List * generate_join_implied_equalities_for_ecs(PlannerInfo *root, List *eclasses, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1050
List * eq_classes
Definition: relation.h:232
List* generate_join_implied_equalities_for_ecs ( PlannerInfo root,
List eclasses,
Relids  join_relids,
Relids  outer_relids,
RelOptInfo inner_rel 
)

Definition at line 1050 of file equivclass.c.

References bms_overlap(), bms_union(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, find_childrel_top_parent(), generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), lfirst, list_concat(), list_length(), NIL, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, and RelOptInfo::reloptkind.

Referenced by generate_join_implied_equalities(), and get_joinrel_parampathinfo().

1055 {
1056  List *result = NIL;
1057  Relids inner_relids = inner_rel->relids;
1058  Relids nominal_inner_relids;
1059  Relids nominal_join_relids;
1060  ListCell *lc;
1061 
1062  /* If inner rel is a child, extra setup work is needed */
1063  if (inner_rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
1064  {
1065  /* Fetch relid set for the topmost parent rel */
1066  nominal_inner_relids = find_childrel_top_parent(root, inner_rel)->relids;
1067  /* ECs will be marked with the parent's relid, not the child's */
1068  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1069  }
1070  else
1071  {
1072  nominal_inner_relids = inner_relids;
1073  nominal_join_relids = join_relids;
1074  }
1075 
1076  foreach(lc, eclasses)
1077  {
1079  List *sublist = NIL;
1080 
1081  /* ECs containing consts do not need any further enforcement */
1082  if (ec->ec_has_const)
1083  continue;
1084 
1085  /* Single-member ECs won't generate any deductions */
1086  if (list_length(ec->ec_members) <= 1)
1087  continue;
1088 
1089  /* We can quickly ignore any that don't overlap the join, too */
1090  if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1091  continue;
1092 
1093  if (!ec->ec_broken)
1095  ec,
1096  join_relids,
1097  outer_relids,
1098  inner_relids);
1099 
1100  /* Recover if we failed to generate required derived clauses */
1101  if (ec->ec_broken)
1103  ec,
1104  nominal_join_relids,
1105  outer_relids,
1106  nominal_inner_relids,
1107  inner_rel);
1108 
1109  result = list_concat(result, sublist);
1110  }
1111 
1112  return result;
1113 }
RelOptInfo * find_childrel_top_parent(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:951
#define NIL
Definition: pg_list.h:69
RelOptKind reloptkind
Definition: relation.h:487
List * list_concat(List *list1, List *list2)
Definition: list.c:321
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:1295
Relids ec_relids
Definition: relation.h:717
Relids relids
Definition: relation.h:490
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1119
#define lfirst(lc)
Definition: pg_list.h:106
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:217
static int list_length(const List *l)
Definition: pg_list.h:89
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
Definition: pg_list.h:45
List * ec_members
Definition: relation.h:714
Path* get_cheapest_fractional_path_for_pathkeys ( List paths,
List pathkeys,
Relids  required_outer,
double  fraction 
)

Definition at line 383 of file pathkeys.c.

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

Referenced by build_minmax_path().

387 {
388  Path *matched_path = NULL;
389  ListCell *l;
390 
391  foreach(l, paths)
392  {
393  Path *path = (Path *) lfirst(l);
394 
395  /*
396  * Since cost comparison is a lot cheaper than pathkey comparison, do
397  * that first. (XXX is that still true?)
398  */
399  if (matched_path != NULL &&
400  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
401  continue;
402 
403  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
404  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
405  matched_path = path;
406  }
407  return matched_path;
408 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:317
List * pathkeys
Definition: relation.h:909
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:107
#define PATH_REQ_OUTER(path)
Definition: relation.h:914
Definition: relation.h:888
Path* get_cheapest_path_for_pathkeys ( List paths,
List pathkeys,
Relids  required_outer,
CostSelector  cost_criterion 
)

Definition at line 342 of file pathkeys.c.

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

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

345 {
346  Path *matched_path = NULL;
347  ListCell *l;
348 
349  foreach(l, paths)
350  {
351  Path *path = (Path *) lfirst(l);
352 
353  /*
354  * Since cost comparison is a lot cheaper than pathkey comparison, do
355  * that first. (XXX is that still true?)
356  */
357  if (matched_path != NULL &&
358  compare_path_costs(matched_path, path, cost_criterion) <= 0)
359  continue;
360 
361  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
362  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
363  matched_path = path;
364  }
365  return matched_path;
366 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:61
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:317
List * pathkeys
Definition: relation.h:909
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
#define PATH_REQ_OUTER(path)
Definition: relation.h:914
Definition: relation.h:888
EquivalenceClass* get_eclass_for_sort_expr ( PlannerInfo root,
Expr expr,
Relids  nullable_relids,
List opfamilies,
Oid  opcintype,
Oid  collation,
Index  sortref,
Relids  rel,
bool  create_it 
)

Definition at line 581 of file equivclass.c.

References add_eq_member(), bms_equal(), bms_intersect(), canonicalize_ec_expression(), contain_agg_clause(), contain_volatile_functions(), contain_window_function(), copyObject(), EquivalenceClass::ec_below_outer_join, EquivalenceClass::ec_broken, EquivalenceClass::ec_collation, EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_max_security, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, PlannerInfo::eq_classes, equal(), ERROR, expression_returns_set(), lappend(), lfirst, list_copy(), makeNode, MemoryContextSwitchTo(), NIL, NULL, PlannerInfo::planner_cxt, and pull_varnos().

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

590 {
591  Relids expr_relids;
592  EquivalenceClass *newec;
593  EquivalenceMember *newem;
594  ListCell *lc1;
595  MemoryContext oldcontext;
596 
597  /*
598  * Ensure the expression exposes the correct type and collation.
599  */
600  expr = canonicalize_ec_expression(expr, opcintype, collation);
601 
602  /*
603  * Get the precise set of nullable relids appearing in the expression.
604  */
605  expr_relids = pull_varnos((Node *) expr);
606  nullable_relids = bms_intersect(nullable_relids, expr_relids);
607 
608  /*
609  * Scan through the existing EquivalenceClasses for a match
610  */
611  foreach(lc1, root->eq_classes)
612  {
613  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
614  ListCell *lc2;
615 
616  /*
617  * Never match to a volatile EC, except when we are looking at another
618  * reference to the same volatile SortGroupClause.
619  */
620  if (cur_ec->ec_has_volatile &&
621  (sortref == 0 || sortref != cur_ec->ec_sortref))
622  continue;
623 
624  if (collation != cur_ec->ec_collation)
625  continue;
626  if (!equal(opfamilies, cur_ec->ec_opfamilies))
627  continue;
628 
629  foreach(lc2, cur_ec->ec_members)
630  {
631  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
632 
633  /*
634  * Ignore child members unless they match the request.
635  */
636  if (cur_em->em_is_child &&
637  !bms_equal(cur_em->em_relids, rel))
638  continue;
639 
640  /*
641  * If below an outer join, don't match constants: they're not as
642  * constant as they look.
643  */
644  if (cur_ec->ec_below_outer_join &&
645  cur_em->em_is_const)
646  continue;
647 
648  if (opcintype == cur_em->em_datatype &&
649  equal(expr, cur_em->em_expr))
650  return cur_ec; /* Match! */
651  }
652  }
653 
654  /* No match; does caller want a NULL result? */
655  if (!create_it)
656  return NULL;
657 
658  /*
659  * OK, build a new single-member EC
660  *
661  * Here, we must be sure that we construct the EC in the right context.
662  */
663  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
664 
665  newec = makeNode(EquivalenceClass);
666  newec->ec_opfamilies = list_copy(opfamilies);
667  newec->ec_collation = collation;
668  newec->ec_members = NIL;
669  newec->ec_sources = NIL;
670  newec->ec_derives = NIL;
671  newec->ec_relids = NULL;
672  newec->ec_has_const = false;
674  newec->ec_below_outer_join = false;
675  newec->ec_broken = false;
676  newec->ec_sortref = sortref;
677  newec->ec_min_security = UINT_MAX;
678  newec->ec_max_security = 0;
679  newec->ec_merged = NULL;
680 
681  if (newec->ec_has_volatile && sortref == 0) /* should not happen */
682  elog(ERROR, "volatile EquivalenceClass has no sortref");
683 
684  newem = add_eq_member(newec, copyObject(expr), expr_relids,
685  nullable_relids, false, opcintype);
686 
687  /*
688  * add_eq_member doesn't check for volatile functions, set-returning
689  * functions, aggregates, or window functions, but such could appear in
690  * sort expressions; so we have to check whether its const-marking was
691  * correct.
692  */
693  if (newec->ec_has_const)
694  {
695  if (newec->ec_has_volatile ||
696  expression_returns_set((Node *) expr) ||
697  contain_agg_clause((Node *) expr) ||
698  contain_window_function((Node *) expr))
699  {
700  newec->ec_has_const = false;
701  newem->em_is_const = false;
702  }
703  }
704 
705  root->eq_classes = lappend(root->eq_classes, newec);
706 
707  MemoryContextSwitchTo(oldcontext);
708 
709  return newec;
710 }
#define NIL
Definition: pg_list.h:69
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2870
Index ec_min_security
Definition: relation.h:724
List * ec_derives
Definition: relation.h:716
bool expression_returns_set(Node *clause)
Definition: nodeFuncs.c:667
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
List * list_copy(const List *oldlist)
Definition: list.c:1160
Index ec_sortref
Definition: relation.h:723
Definition: nodes.h:508
bool ec_below_outer_join
Definition: relation.h:721
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:950
Index ec_max_security
Definition: relation.h:725
void * copyObject(const void *from)
Definition: copyfuncs.c:4475
#define ERROR
Definition: elog.h:43
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:456
List * ec_sources
Definition: relation.h:715
Relids ec_relids
Definition: relation.h:717
Relids pull_varnos(Node *node)
Definition: var.c:95
bool contain_window_function(Node *clause)
Definition: clauses.c:726
List * lappend(List *list, void *datum)
Definition: list.c:128
List * ec_opfamilies
Definition: relation.h:712
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:251
Relids em_relids
Definition: relation.h:763
#define makeNode(_type_)
Definition: nodes.h:556
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:232
bool ec_has_volatile
Definition: relation.h:720
bool contain_agg_clause(Node *clause)
Definition: clauses.c:416
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, Relids nullable_relids, bool is_child, Oid datatype)
Definition: equivclass.c:505
MemoryContext planner_cxt
Definition: relation.h:282
#define elog
Definition: elog.h:219
struct EquivalenceClass * ec_merged
Definition: relation.h:726
List * ec_members
Definition: relation.h:714
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:130
bool has_relevant_eclass_joinclause ( PlannerInfo root,
RelOptInfo rel1 
)

Definition at line 2354 of file equivclass.c.

References bms_is_subset(), bms_overlap(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, lfirst, list_length(), and RelOptInfo::relids.

Referenced by build_join_rel(), and generate_base_implied_equalities().

2355 {
2356  ListCell *lc1;
2357 
2358  foreach(lc1, root->eq_classes)
2359  {
2360  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2361 
2362  /*
2363  * Won't generate joinclauses if single-member (this test covers the
2364  * volatile case too)
2365  */
2366  if (list_length(ec->ec_members) <= 1)
2367  continue;
2368 
2369  /*
2370  * Per the comment in have_relevant_eclass_joinclause, it's sufficient
2371  * to find an EC that mentions both this rel and some other rel.
2372  */
2373  if (bms_overlap(rel1->relids, ec->ec_relids) &&
2374  !bms_is_subset(ec->ec_relids, rel1->relids))
2375  return true;
2376  }
2377 
2378  return false;
2379 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
Relids ec_relids
Definition: relation.h:717
Relids relids
Definition: relation.h:490
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:232
static int list_length(const List *l)
Definition: pg_list.h:89
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
List * ec_members
Definition: relation.h:714
bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 1531 of file pathkeys.c.

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

Referenced by build_index_paths(), and set_append_rel_size().

1532 {
1533  if (rel->joininfo != NIL || rel->has_eclass_joins)
1534  return true; /* might be able to use pathkeys for merging */
1535  if (root->query_pathkeys != NIL)
1536  return true; /* might be able to use them for ordering */
1537  return false; /* definitely useless */
1538 }
bool has_eclass_joins
Definition: relation.h:551
#define NIL
Definition: pg_list.h:69
List * query_pathkeys
Definition: relation.h:257
List * joininfo
Definition: relation.h:549
bool have_dangerous_phv ( PlannerInfo root,
Relids  outer_relids,
Relids  inner_params 
)

Definition at line 1132 of file joinrels.c.

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

Referenced by join_is_legal(), and try_nestloop_path().

1134 {
1135  ListCell *lc;
1136 
1137  foreach(lc, root->placeholder_list)
1138  {
1139  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1140 
1141  if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1142  continue; /* ignore, could not be a nestloop param */
1143  if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1144  continue; /* ignore, not relevant to this join */
1145  if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
1146  continue; /* safe, it can be eval'd within outerrel */
1147  /* Otherwise, it's potentially unsafe, so reject the join */
1148  return true;
1149  }
1150 
1151  /* OK to perform the join */
1152  return false;
1153 }
Relids ph_eval_at
Definition: relation.h:1935
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
#define lfirst(lc)
Definition: pg_list.h:106
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
List * placeholder_list
Definition: relation.h:253
bool have_join_order_restriction ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2 
)

Definition at line 899 of file joinrels.c.

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

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

901 {
902  bool result = false;
903  ListCell *l;
904 
905  /*
906  * If either side has a direct lateral reference to the other, attempt the
907  * join regardless of outer-join considerations.
908  */
909  if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) ||
911  return true;
912 
913  /*
914  * Likewise, if both rels are needed to compute some PlaceHolderVar,
915  * attempt the join regardless of outer-join considerations. (This is not
916  * very desirable, because a PHV with a large eval_at set will cause a lot
917  * of probably-useless joins to be considered, but failing to do this can
918  * cause us to fail to construct a plan at all.)
919  */
920  foreach(l, root->placeholder_list)
921  {
922  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
923 
924  if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) &&
925  bms_is_subset(rel2->relids, phinfo->ph_eval_at))
926  return true;
927  }
928 
929  /*
930  * It's possible that the rels correspond to the left and right sides of a
931  * degenerate outer join, that is, one with no joinclause mentioning the
932  * non-nullable side; in which case we should force the join to occur.
933  *
934  * Also, the two rels could represent a clauseless join that has to be
935  * completed to build up the LHS or RHS of an outer join.
936  */
937  foreach(l, root->join_info_list)
938  {
939  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
940 
941  /* ignore full joins --- other mechanisms handle them */
942  if (sjinfo->jointype == JOIN_FULL)
943  continue;
944 
945  /* Can we perform the SJ with these rels? */
946  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
947  bms_is_subset(sjinfo->min_righthand, rel2->relids))
948  {
949  result = true;
950  break;
951  }
952  if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
953  bms_is_subset(sjinfo->min_righthand, rel1->relids))
954  {
955  result = true;
956  break;
957  }
958 
959  /*
960  * Might we need to join these rels to complete the RHS? We have to
961  * use "overlap" tests since either rel might include a lower SJ that
962  * has been proven to commute with this one.
963  */
964  if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
965  bms_overlap(sjinfo->min_righthand, rel2->relids))
966  {
967  result = true;
968  break;
969  }
970 
971  /* Likewise for the LHS. */
972  if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
973  bms_overlap(sjinfo->min_lefthand, rel2->relids))
974  {
975  result = true;
976  break;
977  }
978  }
979 
980  /*
981  * We do not force the join to occur if either input rel can legally be
982  * joined to anything else using joinclauses. This essentially means that
983  * clauseless bushy joins are put off as long as possible. The reason is
984  * that when there is a join order restriction high up in the join tree
985  * (that is, with many rels inside the LHS or RHS), we would otherwise
986  * expend lots of effort considering very stupid join combinations within
987  * its LHS or RHS.
988  */
989  if (result)
990  {
991  if (has_legal_joinclause(root, rel1) ||
992  has_legal_joinclause(root, rel2))
993  result = false;
994  }
995 
996  return result;
997 }
Relids ph_eval_at
Definition: relation.h:1935
List * join_info_list
Definition: relation.h:247
Relids min_righthand
Definition: relation.h:1808
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1068
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
Relids relids
Definition: relation.h:490
Relids direct_lateral_relids
Definition: relation.h:514
#define lfirst(lc)
Definition: pg_list.h:106
JoinType jointype
Definition: relation.h:1811
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
List * placeholder_list
Definition: relation.h:253
Relids min_lefthand
Definition: relation.h:1807
bool have_relevant_eclass_joinclause ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2 
)

Definition at line 2300 of file equivclass.c.

References bms_overlap(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, lfirst, list_length(), and RelOptInfo::relids.

Referenced by have_relevant_joinclause().

2302 {
2303  ListCell *lc1;
2304 
2305  foreach(lc1, root->eq_classes)
2306  {
2307  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2308 
2309  /*
2310  * Won't generate joinclauses if single-member (this test covers the
2311  * volatile case too)
2312  */
2313  if (list_length(ec->ec_members) <= 1)
2314  continue;
2315 
2316  /*
2317  * We do not need to examine the individual members of the EC, because
2318  * all that we care about is whether each rel overlaps the relids of
2319  * at least one member, and a test on ec_relids is sufficient to prove
2320  * that. (As with have_relevant_joinclause(), it is not necessary
2321  * that the EC be able to form a joinclause relating exactly the two
2322  * given rels, only that it be able to form a joinclause mentioning
2323  * both, and this will surely be true if both of them overlap
2324  * ec_relids.)
2325  *
2326  * Note we don't test ec_broken; if we did, we'd need a separate code
2327  * path to look through ec_sources. Checking the membership anyway is
2328  * OK as a possibly-overoptimistic heuristic.
2329  *
2330  * We don't test ec_has_const either, even though a const eclass won't
2331  * generate real join clauses. This is because if we had "WHERE a.x =
2332  * b.y and a.x = 42", it is worth considering a join between a and b,
2333  * since the join result is likely to be small even though it'll end
2334  * up being an unqualified nestloop.
2335  */
2336  if (bms_overlap(rel1->relids, ec->ec_relids) &&
2337  bms_overlap(rel2->relids, ec->ec_relids))
2338  return true;
2339  }
2340 
2341  return false;
2342 }
Relids ec_relids
Definition: relation.h:717
Relids relids
Definition: relation.h:490
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:232
static int list_length(const List *l)
Definition: pg_list.h:89
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
List * ec_members
Definition: relation.h:714
bool indexcol_is_bool_constant_for_query ( IndexOptInfo index,
int  indexcol 
)

Definition at line 3112 of file indxpath.c.

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

Referenced by build_index_pathkeys().

3113 {
3114  ListCell *lc;
3115 
3116  /* If the index isn't boolean, we can't possibly get a match */
3117  if (!IsBooleanOpfamily(index->opfamily[indexcol]))
3118  return false;
3119 
3120  /* Check each restriction clause for the index's rel */
3121  foreach(lc, index->rel->baserestrictinfo)
3122  {
3123  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3124 
3125  /*
3126  * As in match_clause_to_indexcol, never match pseudoconstants to
3127  * indexes. (It might be semantically okay to do so here, but the
3128  * odds of getting a match are negligible, so don't waste the cycles.)
3129  */
3130  if (rinfo->pseudoconstant)
3131  continue;
3132 
3133  /* See if we can match the clause's expression to the index column */
3134  if (match_boolean_index_clause((Node *) rinfo->clause, indexcol, index))
3135  return true;
3136  }
3137 
3138  return false;
3139 }
#define IsBooleanOpfamily(opfamily)
Definition: indxpath.c:43
List * baserestrictinfo
Definition: relation.h:544
bool pseudoconstant
Definition: relation.h:1645
Definition: nodes.h:508
RelOptInfo * rel
Definition: relation.h:590
static bool match_boolean_index_clause(Node *clause, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:3287
Expr * clause
Definition: relation.h:1637
#define lfirst(lc)
Definition: pg_list.h:106
Oid * opfamily
Definition: relation.h:601
void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 892 of file pathkeys.c.

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

Referenced by distribute_qual_to_rels().

893 {
894  Expr *clause = restrictinfo->clause;
895  Oid lefttype,
896  righttype;
897 
898  /* Should be a mergeclause ... */
899  Assert(restrictinfo->mergeopfamilies != NIL);
900  /* ... with links not yet set */
901  Assert(restrictinfo->left_ec == NULL);
902  Assert(restrictinfo->right_ec == NULL);
903 
904  /* Need the declared input types of the operator */
905  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
906 
907  /* Find or create a matching EquivalenceClass for each side */
908  restrictinfo->left_ec =
910  (Expr *) get_leftop(clause),
911  restrictinfo->nullable_relids,
912  restrictinfo->mergeopfamilies,
913  lefttype,
914  ((OpExpr *) clause)->inputcollid,
915  0,
916  NULL,
917  true);
918  restrictinfo->right_ec =
920  (Expr *) get_rightop(clause),
921  restrictinfo->nullable_relids,
922  restrictinfo->mergeopfamilies,
923  righttype,
924  ((OpExpr *) clause)->inputcollid,
925  0,
926  NULL,
927  true);
928 }
#define NIL
Definition: pg_list.h:69
EquivalenceClass * get_eclass_for_sort_expr(PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
Definition: equivclass.c:581
EquivalenceClass * right_ec
Definition: relation.h:1686
unsigned int Oid
Definition: postgres_ext.h:31
List * mergeopfamilies
Definition: relation.h:1682
Node * get_leftop(const Expr *clause)
Definition: clauses.c:198
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1135
Expr * clause
Definition: relation.h:1637
Relids nullable_relids
Definition: relation.h:1661
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
Node * get_rightop(const Expr *clause)
Definition: clauses.c:215
EquivalenceClass * left_ec
Definition: relation.h:1685
bool is_redundant_derived_clause ( RestrictInfo rinfo,
List clauselist 
)

Definition at line 2448 of file equivclass.c.

References lfirst, NULL, and RestrictInfo::parent_ec.

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

2449 {
2450  EquivalenceClass *parent_ec = rinfo->parent_ec;
2451  ListCell *lc;
2452 
2453  /* Fail if it's not a potentially-redundant clause from some EC */
2454  if (parent_ec == NULL)
2455  return false;
2456 
2457  foreach(lc, clauselist)
2458  {
2459  RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
2460 
2461  if (otherrinfo->parent_ec == parent_ec)
2462  return true;
2463  }
2464 
2465  return false;
2466 }
EquivalenceClass * parent_ec
Definition: relation.h:1671
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
void join_search_one_level ( PlannerInfo root,
int  level 
)

Definition at line 51 of file joinrels.c.

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

Referenced by standard_join_search().

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

Definition at line 51 of file pathkeys.c.

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

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

54 {
55  PathKey *pk;
56  ListCell *lc;
57  MemoryContext oldcontext;
58 
59  /* The passed eclass might be non-canonical, so chase up to the top */
60  while (eclass->ec_merged)
61  eclass = eclass->ec_merged;
62 
63  foreach(lc, root->canon_pathkeys)
64  {
65  pk = (PathKey *) lfirst(lc);
66  if (eclass == pk->pk_eclass &&
67  opfamily == pk->pk_opfamily &&
68  strategy == pk->pk_strategy &&
69  nulls_first == pk->pk_nulls_first)
70  return pk;
71  }
72 
73  /*
74  * Be sure canonical pathkeys are allocated in the main planning context.
75  * Not an issue in normal planning, but it is for GEQO.
76  */
77  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
78 
79  pk = makeNode(PathKey);
80  pk->pk_eclass = eclass;
81  pk->pk_opfamily = opfamily;
82  pk->pk_strategy = strategy;
83  pk->pk_nulls_first = nulls_first;
84 
85  root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
86 
87  MemoryContextSwitchTo(oldcontext);
88 
89  return pk;
90 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int pk_strategy
Definition: relation.h:793
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:508
bool pk_nulls_first
Definition: relation.h:794
List * canon_pathkeys
Definition: relation.h:234
List * lappend(List *list, void *datum)
Definition: list.c:128
#define makeNode(_type_)
Definition: nodes.h:556
#define lfirst(lc)
Definition: pg_list.h:106
EquivalenceClass * pk_eclass
Definition: relation.h:791
Oid pk_opfamily
Definition: relation.h:792
MemoryContext planner_cxt
Definition: relation.h:282
struct EquivalenceClass * ec_merged
Definition: relation.h:726
List* make_inner_pathkeys_for_merge ( PlannerInfo root,
List mergeclauses,
List outer_pathkeys 
)

Definition at line 1265 of file pathkeys.c.

References elog, ERROR, lappend(), RestrictInfo::left_ec, lfirst, list_head(), lnext, make_canonical_pathkey(), NIL, NULL, RestrictInfo::outer_is_left, pathkey_is_redundant(), PathKey::pk_eclass, PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, RestrictInfo::right_ec, and update_mergeclause_eclasses().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

1268 {
1269  List *pathkeys = NIL;
1270  EquivalenceClass *lastoeclass;
1271  PathKey *opathkey;
1272  ListCell *lc;
1273  ListCell *lop;
1274 
1275  lastoeclass = NULL;
1276  opathkey = NULL;
1277  lop = list_head(outer_pathkeys);
1278 
1279  foreach(lc, mergeclauses)
1280  {
1281  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1282  EquivalenceClass *oeclass;
1283  EquivalenceClass *ieclass;
1284  PathKey *pathkey;
1285 
1286  update_mergeclause_eclasses(root, rinfo);
1287 
1288  if (rinfo->outer_is_left)
1289  {
1290  oeclass = rinfo->left_ec;
1291  ieclass = rinfo->right_ec;
1292  }
1293  else
1294  {
1295  oeclass = rinfo->right_ec;
1296  ieclass = rinfo->left_ec;
1297  }
1298 
1299  /* outer eclass should match current or next pathkeys */
1300  /* we check this carefully for debugging reasons */
1301  if (oeclass != lastoeclass)
1302  {
1303  if (!lop)
1304  elog(ERROR, "too few pathkeys for mergeclauses");
1305  opathkey = (PathKey *) lfirst(lop);
1306  lop = lnext(lop);
1307  lastoeclass = opathkey->pk_eclass;
1308  if (oeclass != lastoeclass)
1309  elog(ERROR, "outer pathkeys do not match mergeclause");
1310  }
1311 
1312  /*
1313  * Often, we'll have same EC on both sides, in which case the outer
1314  * pathkey is also canonical for the inner side, and we can skip a
1315  * useless search.
1316  */
1317  if (ieclass == oeclass)
1318  pathkey = opathkey;
1319  else
1320  pathkey = make_canonical_pathkey(root,
1321  ieclass,
1322  opathkey->pk_opfamily,
1323  opathkey->pk_strategy,
1324  opathkey->pk_nulls_first);
1325 
1326  /*
1327  * Don't generate redundant pathkeys (can happen if multiple
1328  * mergeclauses refer to same EC).
1329  */
1330  if (!pathkey_is_redundant(pathkey, pathkeys))
1331  pathkeys = lappend(pathkeys, pathkey);
1332  }
1333 
1334  return pathkeys;
1335 }
#define NIL
Definition: pg_list.h:69
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:51
EquivalenceClass * right_ec
Definition: relation.h:1686
int pk_strategy
Definition: relation.h:793
bool pk_nulls_first
Definition: relation.h:794
#define ERROR
Definition: elog.h:43
bool outer_is_left
Definition: relation.h:1692
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:128
#define lnext(lc)
Definition: pg_list.h:105
List * lappend(List *list, void *datum)
Definition: list.c:128
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
EquivalenceClass * pk_eclass
Definition: relation.h:791
Oid pk_opfamily
Definition: relation.h:792
EquivalenceClass * left_ec
Definition: relation.h:1685
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:941
RelOptInfo* make_join_rel ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2 
)

Definition at line 654 of file joinrels.c.

References add_paths_to_joinrel(), Assert, bms_equal(), bms_free(), bms_is_subset(), bms_overlap(), bms_union(), build_join_rel(), RelOptInfo::cheapest_total_path, create_unique_path(), SpecialJoinInfo::delay_upper_joins, elog, ereport, errcode(), errmsg(), ERROR, is_dummy_rel(), JOIN_ANTI, JOIN_FULL, JOIN_INNER, join_is_legal(), JOIN_LEFT, JOIN_RIGHT, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, SpecialJoinInfo::jointype, SpecialJoinInfo::lhs_strict, mark_dummy_rel(), SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, NULL, RelOptInfo::pathlist, RelOptInfo::relids, restriction_is_constant_false(), SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, SpecialJoinInfo::syn_righthand, T_SpecialJoinInfo, and SpecialJoinInfo::type.

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

655 {
656  Relids joinrelids;
657  SpecialJoinInfo *sjinfo;
658  bool reversed;
659  SpecialJoinInfo sjinfo_data;
660  RelOptInfo *joinrel;
661  List *restrictlist;
662 
663  /* We should never try to join two overlapping sets of rels. */
664  Assert(!bms_overlap(rel1->relids, rel2->relids));
665 
666  /* Construct Relids set that identifies the joinrel. */
667  joinrelids = bms_union(rel1->relids, rel2->relids);
668 
669  /* Check validity and determine join type. */
670  if (!join_is_legal(root, rel1, rel2, joinrelids,
671  &sjinfo, &reversed))
672  {
673  /* invalid join path */
674  bms_free(joinrelids);
675  return NULL;
676  }
677 
678  /* Swap rels if needed to match the join info. */
679  if (reversed)
680  {
681  RelOptInfo *trel = rel1;
682 
683  rel1 = rel2;
684  rel2 = trel;
685  }
686 
687  /*
688  * If it's a plain inner join, then we won't have found anything in
689  * join_info_list. Make up a SpecialJoinInfo so that selectivity
690  * estimation functions will know what's being joined.
691  */
692  if (sjinfo == NULL)
693  {
694  sjinfo = &sjinfo_data;
695  sjinfo->type = T_SpecialJoinInfo;
696  sjinfo->min_lefthand = rel1->relids;
697  sjinfo->min_righthand = rel2->relids;
698  sjinfo->syn_lefthand = rel1->relids;
699  sjinfo->syn_righthand = rel2->relids;
700  sjinfo->jointype = JOIN_INNER;
701  /* we don't bother trying to make the remaining fields valid */
702  sjinfo->lhs_strict = false;
703  sjinfo->delay_upper_joins = false;
704  sjinfo->semi_can_btree = false;
705  sjinfo->semi_can_hash = false;
706  sjinfo->semi_operators = NIL;
707  sjinfo->semi_rhs_exprs = NIL;
708  }
709 
710  /*
711  * Find or build the join RelOptInfo, and compute the restrictlist that
712  * goes with this particular joining.
713  */
714  joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
715  &restrictlist);
716 
717  /*
718  * If we've already proven this join is empty, we needn't consider any
719  * more paths for it.
720  */
721  if (is_dummy_rel(joinrel))
722  {
723  bms_free(joinrelids);
724  return joinrel;
725  }
726 
727  /*
728  * Consider paths using each rel as both outer and inner. Depending on
729  * the join type, a provably empty outer or inner rel might mean the join
730  * is provably empty too; in which case throw away any previously computed
731  * paths and mark the join as dummy. (We do it this way since it's
732  * conceivable that dummy-ness of a multi-element join might only be
733  * noticeable for certain construction paths.)
734  *
735  * Also, a provably constant-false join restriction typically means that
736  * we can skip evaluating one or both sides of the join. We do this by
737  * marking the appropriate rel as dummy. For outer joins, a
738  * constant-false restriction that is pushed down still means the whole
739  * join is dummy, while a non-pushed-down one means that no inner rows
740  * will join so we can treat the inner rel as dummy.
741  *
742  * We need only consider the jointypes that appear in join_info_list, plus
743  * JOIN_INNER.
744  */
745  switch (sjinfo->jointype)
746  {
747  case JOIN_INNER:
748  if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
749  restriction_is_constant_false(restrictlist, false))
750  {
751  mark_dummy_rel(joinrel);
752  break;
753  }
754  add_paths_to_joinrel(root, joinrel, rel1, rel2,
755  JOIN_INNER, sjinfo,
756  restrictlist);
757  add_paths_to_joinrel(root, joinrel, rel2, rel1,
758  JOIN_INNER, sjinfo,
759  restrictlist);
760  break;
761  case JOIN_LEFT:
762  if (is_dummy_rel(rel1) ||
763  restriction_is_constant_false(restrictlist, true))
764  {
765  mark_dummy_rel(joinrel);
766  break;
767  }
768  if (restriction_is_constant_false(restrictlist, false) &&
769  bms_is_subset(rel2->relids, sjinfo->syn_righthand))
770  mark_dummy_rel(rel2);
771  add_paths_to_joinrel(root, joinrel, rel1, rel2,
772  JOIN_LEFT, sjinfo,
773  restrictlist);
774  add_paths_to_joinrel(root, joinrel, rel2, rel1,
775  JOIN_RIGHT, sjinfo,
776  restrictlist);
777  break;
778  case JOIN_FULL:
779  if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) ||
780  restriction_is_constant_false(restrictlist, true))
781  {
782  mark_dummy_rel(joinrel);
783  break;
784  }
785  add_paths_to_joinrel(root, joinrel, rel1, rel2,
786  JOIN_FULL, sjinfo,
787  restrictlist);
788  add_paths_to_joinrel(root, joinrel, rel2, rel1,
789  JOIN_FULL, sjinfo,
790  restrictlist);
791 
792  /*
793  * If there are join quals that aren't mergeable or hashable, we
794  * may not be able to build any valid plan. Complain here so that
795  * we can give a somewhat-useful error message. (Since we have no
796  * flexibility of planning for a full join, there's no chance of
797  * succeeding later with another pair of input rels.)
798  */
799  if (joinrel->pathlist == NIL)
800  ereport(ERROR,
801  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
802  errmsg("FULL JOIN is only supported with merge-joinable or hash-joinable join conditions")));
803  break;
804  case JOIN_SEMI:
805 
806  /*
807  * We might have a normal semijoin, or a case where we don't have
808  * enough rels to do the semijoin but can unique-ify the RHS and
809  * then do an innerjoin (see comments in join_is_legal). In the
810  * latter case we can't apply JOIN_SEMI joining.
811  */
812  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
813  bms_is_subset(sjinfo->min_righthand, rel2->relids))
814  {
815  if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
816  restriction_is_constant_false(restrictlist, false))
817  {
818  mark_dummy_rel(joinrel);
819  break;
820  }
821  add_paths_to_joinrel(root, joinrel, rel1, rel2,
822  JOIN_SEMI, sjinfo,
823  restrictlist);
824  }
825 
826  /*
827  * If we know how to unique-ify the RHS and one input rel is
828  * exactly the RHS (not a superset) we can consider unique-ifying
829  * it and then doing a regular join. (The create_unique_path
830  * check here is probably redundant with what join_is_legal did,
831  * but if so the check is cheap because it's cached. So test
832  * anyway to be sure.)
833  */
834  if (bms_equal(sjinfo->syn_righthand, rel2->relids) &&
835  create_unique_path(root, rel2, rel2->cheapest_total_path,
836  sjinfo) != NULL)
837  {
838  if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
839  restriction_is_constant_false(restrictlist, false))
840  {
841  mark_dummy_rel(joinrel);
842  break;
843  }
844  add_paths_to_joinrel(root, joinrel, rel1, rel2,
845  JOIN_UNIQUE_INNER, sjinfo,
846  restrictlist);
847  add_paths_to_joinrel(root, joinrel, rel2, rel1,
848  JOIN_UNIQUE_OUTER, sjinfo,
849  restrictlist);
850  }
851  break;
852  case JOIN_ANTI:
853  if (is_dummy_rel(rel1) ||
854  restriction_is_constant_false(restrictlist, true))
855  {
856  mark_dummy_rel(joinrel);
857  break;
858  }
859  if (restriction_is_constant_false(restrictlist, false) &&
860  bms_is_subset(rel2->relids, sjinfo->syn_righthand))
861  mark_dummy_rel(rel2);
862  add_paths_to_joinrel(root, joinrel, rel1, rel2,
863  JOIN_ANTI, sjinfo,
864  restrictlist);
865  break;
866  default:
867  /* other values not expected here */
868  elog(ERROR, "unrecognized join type: %d", (int) sjinfo->jointype);
869  break;
870  }
871 
872  bms_free(joinrelids);
873 
874  return joinrel;
875 }
#define NIL
Definition: pg_list.h:69
static bool is_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1160
bool semi_can_btree
Definition: relation.h:1815
static bool restriction_is_constant_false(List *restrictlist, bool only_pushed_down)
Definition: joinrels.c:1221
Relids min_righthand
Definition: relation.h:1808
NodeTag type
Definition: relation.h:1806
static void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1181
int errcode(int sqlerrcode)
Definition: elog.c:575
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1424
Relids syn_lefthand
Definition: relation.h:1809
Relids syn_righthand
Definition: relation.h:1810
#define ERROR
Definition: elog.h:43
List * semi_rhs_exprs
Definition: relation.h:1818
bool semi_can_hash
Definition: relation.h:1816
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
static bool join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
Definition: joinrels.c:327
struct Path * cheapest_total_path
Definition: relation.h:508
Relids relids
Definition: relation.h:490
#define ereport(elevel, rest)
Definition: elog.h:122
bool delay_upper_joins
Definition: relation.h:1813
RelOptInfo * build_join_rel(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, List **restrictlist_ptr)
Definition: relnode.c:346
void bms_free(Bitmapset *a)
Definition: bitmapset.c:200
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
JoinType jointype
Definition: relation.h:1811
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:217
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
int errmsg(const char *fmt,...)
Definition: elog.c:797
List * semi_operators
Definition: relation.h:1817
void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinpath.c:88
List * pathlist
Definition: relation.h:504
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
Relids min_lefthand
Definition: relation.h:1807
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:130
RelOptInfo* make_one_rel ( PlannerInfo root,
List joinlist 
)

Definition at line 138 of file allpaths.c.

References PlannerInfo::all_baserels, Assert, bms_add_member(), bms_equal(), make_rel_from_joinlist(), NULL, RelOptInfo::relid, RelOptInfo::relids, RELOPT_BASEREL, RelOptInfo::reloptkind, set_base_rel_consider_startup(), set_base_rel_pathlists(), set_base_rel_sizes(), PlannerInfo::simple_rel_array, and PlannerInfo::simple_rel_array_size.

Referenced by query_planner().

139 {
140  RelOptInfo *rel;
141  Index rti;
142 
143  /*
144  * Construct the all_baserels Relids set.
145  */
146  root->all_baserels = NULL;
147  for (rti = 1; rti < root->simple_rel_array_size; rti++)
148  {
149  RelOptInfo *brel = root->simple_rel_array[rti];
150 
151  /* there may be empty slots corresponding to non-baserel RTEs */
152  if (brel == NULL)
153  continue;
154 
155  Assert(brel->relid == rti); /* sanity check on array */
156 
157  /* ignore RTEs that are "other rels" */
158  if (brel->reloptkind != RELOPT_BASEREL)
159  continue;
160 
161  root->all_baserels = bms_add_member(root->all_baserels, brel->relid);
162  }
163 
164  /* Mark base rels as to whether we care about fast-start plans */
166 
167  /*
168  * Compute size estimates and consider_parallel flags for each base rel,
169  * then generate access paths.
170  */
171  set_base_rel_sizes(root);
173 
174  /*
175  * Generate access paths for the entire join tree.
176  */
177  rel = make_rel_from_joinlist(root, joinlist);
178 
179  /*
180  * The result should join all and only the query's base rels.
181  */
182  Assert(bms_equal(rel->relids, root->all_baserels));
183 
184  return rel;
185 }
RelOptKind reloptkind
Definition: relation.h:487
static void set_base_rel_sizes(PlannerInfo *root)
Definition: allpaths.c:241
static void set_base_rel_consider_startup(PlannerInfo *root)
Definition: allpaths.c:198
struct RelOptInfo ** simple_rel_array
Definition: relation.h:176
Relids all_baserels
Definition: relation.h:193
static RelOptInfo * make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
Definition: allpaths.c:2093
Relids relids
Definition: relation.h:490
int simple_rel_array_size
Definition: relation.h:177
Index relid
Definition: relation.h:518
static void set_base_rel_pathlists(PlannerInfo *root)
Definition: allpaths.c:284
unsigned int Index
Definition: c.h:362
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:668
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:130
List* make_pathkeys_for_sortclauses ( PlannerInfo root,
List sortclauses,
List tlist 
)

Definition at line 838 of file pathkeys.c.

References Assert, get_sortgroupclause_expr(), lappend(), lfirst, make_pathkey_from_sortop(), NIL, PlannerInfo::nullable_baserels, SortGroupClause::nulls_first, OidIsValid, pathkey_is_redundant(), SortGroupClause::sortop, and SortGroupClause::tleSortGroupRef.

Referenced by generate_nonunion_path(), get_column_info_for_window(), grouping_planner(), make_pathkeys_for_window(), make_union_unique(), minmax_qp_callback(), and standard_qp_callback().

841 {
842  List *pathkeys = NIL;
843  ListCell *l;
844 
845  foreach(l, sortclauses)
846  {
847  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
848  Expr *sortkey;
849  PathKey *pathkey;
850 
851  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
852  Assert(OidIsValid(sortcl->sortop));
853  pathkey = make_pathkey_from_sortop(root,
854  sortkey,
855  root->nullable_baserels,
856  sortcl->sortop,
857  sortcl->nulls_first,
858  sortcl->tleSortGroupRef,
859  true);
860 
861  /* Canonical form eliminates redundant ordering keys */
862  if (!pathkey_is_redundant(pathkey, pathkeys))
863  pathkeys = lappend(pathkeys, pathkey);
864  }
865  return pathkeys;
866 }
#define NIL
Definition: pg_list.h:69
static PathKey * make_pathkey_from_sortop(PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid ordering_op, bool nulls_first, Index sortref, bool create_it)
Definition: pathkeys.c:229
Index tleSortGroupRef
Definition: parsenodes.h:1102
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:382
#define OidIsValid(objectId)
Definition: c.h:534
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:128
List * lappend(List *list, void *datum)
Definition: list.c:128
#define Assert(condition)
Definition: c.h:671
#define lfirst(lc)
Definition: pg_list.h:106
Relids nullable_baserels
Definition: relation.h:201
Definition: pg_list.h:45
EquivalenceClass* match_eclasses_to_foreign_key_col ( PlannerInfo root,
ForeignKeyOptInfo fkinfo,
int  colno 
)

Definition at line 1990 of file equivclass.c.

References ForeignKeyOptInfo::con_relid, ForeignKeyOptInfo::confkey, ForeignKeyOptInfo::conkey, ForeignKeyOptInfo::conpfeqop, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, PlannerInfo::eq_classes, equal(), get_mergejoin_opfamilies(), IsA, lfirst, NIL, NULL, ForeignKeyOptInfo::ref_relid, RangeQueryClause::var, Var::varattno, and Var::varno.

Referenced by match_foreign_keys_to_quals().

1993 {
1994  Index var1varno = fkinfo->con_relid;
1995  AttrNumber var1attno = fkinfo->conkey[colno];
1996  Index var2varno = fkinfo->ref_relid;
1997  AttrNumber var2attno = fkinfo->confkey[colno];
1998  Oid eqop = fkinfo->conpfeqop[colno];
1999  List *opfamilies = NIL; /* compute only if needed */
2000  ListCell *lc1;
2001 
2002  foreach(lc1, root->eq_classes)
2003  {
2004  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2005  bool item1member = false;
2006  bool item2member = false;
2007  ListCell *lc2;
2008 
2009  /* Never match to a volatile EC */
2010  if (ec->ec_has_volatile)
2011  continue;
2012  /* Note: it seems okay to match to "broken" eclasses here */
2013 
2014  foreach(lc2, ec->ec_members)
2015  {
2017  Var *var;
2018 
2019  if (em->em_is_child)
2020  continue; /* ignore children here */
2021 
2022  /* EM must be a Var, possibly with RelabelType */
2023  var = (Var *) em->em_expr;
2024  while (var && IsA(var, RelabelType))
2025  var = (Var *) ((RelabelType *) var)->arg;
2026  if (!(var && IsA(var, Var)))
2027  continue;
2028 
2029  /* Match? */
2030  if (var->varno == var1varno && var->varattno == var1attno)
2031  item1member = true;
2032  else if (var->varno == var2varno && var->varattno == var2attno)
2033  item2member = true;
2034 
2035  /* Have we found both PK and FK column in this EC? */
2036  if (item1member && item2member)
2037  {
2038  /*
2039  * Succeed if eqop matches EC's opfamilies. We could test
2040  * this before scanning the members, but it's probably cheaper
2041  * to test for member matches first.
2042  */
2043  if (opfamilies == NIL) /* compute if we didn't already */
2044  opfamilies = get_mergejoin_opfamilies(eqop);
2045  if (equal(opfamilies, ec->ec_opfamilies))
2046  return ec;
2047  /* Otherwise, done with this EC, move on to the next */
2048  break;
2049  }
2050  }
2051  }
2052  return NULL;
2053 }
#define NIL
Definition: pg_list.h:69
#define IsA(nodeptr, _type_)
Definition: nodes.h:559
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2870
List * get_mergejoin_opfamilies(Oid opno)
Definition: lsyscache.c:363
AttrNumber varattno
Definition: primnodes.h:146
unsigned int Oid
Definition: postgres_ext.h:31
Definition: primnodes.h:141
Oid conpfeqop[INDEX_MAX_KEYS]
Definition: relation.h:655
Index varno
Definition: primnodes.h:144
List * ec_opfamilies
Definition: relation.h:712
AttrNumber conkey[INDEX_MAX_KEYS]
Definition: relation.h:653
unsigned int Index
Definition: c.h:362
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:232
bool ec_has_volatile
Definition: relation.h:720
Definition: pg_list.h:45
AttrNumber confkey[INDEX_MAX_KEYS]
Definition: relation.h:654
int16 AttrNumber
Definition: attnum.h:21
List * ec_members
Definition: relation.h:714
bool match_index_to_operand ( Node operand,
int  indexcol,
IndexOptInfo index 
)

Definition at line 3161 of file indxpath.c.

References arg, elog, equal(), ERROR, i, IndexOptInfo::indexkeys, IndexOptInfo::indexprs, IsA, lfirst, list_head(), lnext, NULL, IndexOptInfo::rel, and RelOptInfo::relid.

Referenced by adjust_rowcompare_for_index(), deconstruct_indexquals(), ec_member_matches_indexcol(), expand_boolean_index_clause(), get_actual_variable_range(), match_boolean_index_clause(), match_clause_to_indexcol(), match_clause_to_ordering_op(), match_rowcompare_to_indexcol(), and relation_has_unique_index_for().

3164 {
3165  int indkey;
3166 
3167  /*
3168  * Ignore any RelabelType node above the operand. This is needed to be
3169  * able to apply indexscanning in binary-compatible-operator cases. Note:
3170  * we can assume there is at most one RelabelType node;
3171  * eval_const_expressions() will have simplified if more than one.
3172  */
3173  if (operand && IsA(operand, RelabelType))
3174  operand = (Node *) ((RelabelType *) operand)->arg;
3175 
3176  indkey = index->indexkeys[indexcol];
3177  if (indkey != 0)
3178  {
3179  /*
3180  * Simple index column; operand must be a matching Var.
3181  */
3182  if (operand && IsA(operand, Var) &&
3183  index->rel->relid == ((Var *) operand)->varno &&
3184  indkey == ((Var *) operand)->varattno)
3185  return true;
3186  }
3187  else
3188  {
3189  /*
3190  * Index expression; find the correct expression. (This search could
3191  * be avoided, at the cost of complicating all the callers of this
3192  * routine; doesn't seem worth it.)
3193  */
3194  ListCell *indexpr_item;
3195  int i;
3196  Node *indexkey;
3197 
3198  indexpr_item = list_head(index->indexprs);
3199  for (i = 0; i < indexcol; i++)
3200  {
3201  if (index->indexkeys[i] == 0)
3202  {
3203  if (indexpr_item == NULL)
3204  elog(ERROR, "wrong number of index expressions");
3205  indexpr_item = lnext(indexpr_item);
3206  }
3207  }
3208  if (indexpr_item == NULL)
3209  elog(ERROR, "wrong number of index expressions");
3210  indexkey = (Node *) lfirst(indexpr_item);
3211 
3212  /*
3213  * Does it match the operand? Again, strip any relabeling.
3214  */
3215  if (indexkey && IsA(indexkey, RelabelType))
3216  indexkey = (Node *) ((RelabelType *) indexkey)->arg;
3217 
3218  if (equal(indexkey, operand))
3219  return true;
3220  }
3221 
3222  return false;
3223 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:559
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2870
Definition: nodes.h:508
Definition: primnodes.h:141
RelOptInfo * rel
Definition: relation.h:590
#define ERROR
Definition: elog.h:43
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
#define lnext(lc)
Definition: pg_list.h:105
Index relid
Definition: relation.h:518
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
int i
void * arg
int * indexkeys
Definition: relation.h:599
#define elog
Definition: elog.h:219
List * indexprs
Definition: relation.h:610
bool pathkeys_contained_in ( List keys1,
List keys2 
)

Definition at line 317 of file pathkeys.c.

References compare_pathkeys(), PATHKEYS_BETTER2, and PATHKEYS_EQUAL.

Referenced by create_distinct_paths(), create_grouping_paths(), create_merge_append_path(), create_merge_append_plan(), create_one_window_path(), create_ordered_paths(), create_window_paths(), generate_mergejoin_paths(), get_cheapest_fractional_path_for_pathkeys(), get_cheapest_path_for_pathkeys(), pathkeys_useful_for_ordering(), and try_mergejoin_path().

318 {
319  switch (compare_pathkeys(keys1, keys2))
320  {
321  case PATHKEYS_EQUAL:
322  case PATHKEYS_BETTER2:
323  return true;
324  default:
325  break;
326  }
327  return false;
328 }
PathKeysComparison compare_pathkeys(List *keys1, List *keys2)
Definition: pathkeys.c:278
bool process_equivalence ( PlannerInfo root,
RestrictInfo restrictinfo,
bool  below_outer_join 
)

Definition at line 107 of file equivclass.c.

References add_eq_member(), Assert, bms_intersect(), bms_is_empty(), bms_join(), PlannerInfo::canon_pathkeys, canonicalize_ec_expression(), RestrictInfo::clause, contain_nonstrict_functions(), EquivalenceClass::ec_below_outer_join, EquivalenceClass::ec_broken, EquivalenceClass::ec_collation, EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_max_security, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, PlannerInfo::eq_classes, equal(), ERROR, exprType(), get_leftop(), get_rightop(), is_opclause, lappend(), RestrictInfo::leakproof, RestrictInfo::left_ec, RestrictInfo::left_em, RestrictInfo::left_relids, lfirst, list_concat(), list_delete_ptr(), list_make1, makeNode, Max, RestrictInfo::mergeopfamilies, Min, NIL, NULL, RestrictInfo::nullable_relids, op_input_types(), RestrictInfo::right_ec, RestrictInfo::right_em, RestrictInfo::right_relids, and RestrictInfo::security_level.

Referenced by distribute_qual_to_rels(), reconsider_full_join_clause(), and reconsider_outer_join_clause().

109 {
110  Expr *clause = restrictinfo->clause;
111  Oid opno,
112  collation,
113  item1_type,
114  item2_type;
115  Expr *item1;
116  Expr *item2;
117  Relids item1_relids,
118  item2_relids,
119  item1_nullable_relids,
120  item2_nullable_relids;
121  List *opfamilies;
122  EquivalenceClass *ec1,
123  *ec2;
124  EquivalenceMember *em1,
125  *em2;
126  ListCell *lc1;
127 
128  /* Should not already be marked as having generated an eclass */
129  Assert(restrictinfo->left_ec == NULL);
130  Assert(restrictinfo->right_ec == NULL);
131 
132  /* Reject if it is potentially postponable by security considerations */
133  if (restrictinfo->security_level > 0 && !restrictinfo->leakproof)
134  return false;
135 
136  /* Extract info from given clause */
137  Assert(is_opclause(clause));
138  opno = ((OpExpr *) clause)->opno;
139  collation = ((OpExpr *) clause)->inputcollid;
140  item1 = (Expr *) get_leftop(clause);
141  item2 = (Expr *) get_rightop(clause);
142  item1_relids = restrictinfo->left_relids;
143  item2_relids = restrictinfo->right_relids;
144 
145  /*
146  * Ensure both input expressions expose the desired collation (their types
147  * should be OK already); see comments for canonicalize_ec_expression.
148  */
149  item1 = canonicalize_ec_expression(item1,
150  exprType((Node *) item1),
151  collation);
152  item2 = canonicalize_ec_expression(item2,
153  exprType((Node *) item2),
154  collation);
155 
156  /*
157  * Reject clauses of the form X=X. These are not as redundant as they
158  * might seem at first glance: assuming the operator is strict, this is
159  * really an expensive way to write X IS NOT NULL. So we must not risk
160  * just losing the clause, which would be possible if there is already a
161  * single-element EquivalenceClass containing X. The case is not common
162  * enough to be worth contorting the EC machinery for, so just reject the
163  * clause and let it be processed as a normal restriction clause.
164  */
165  if (equal(item1, item2))
166  return false; /* X=X is not a useful equivalence */
167 
168  /*
169  * If below outer join, check for strictness, else reject.
170  */
171  if (below_outer_join)
172  {
173  if (!bms_is_empty(item1_relids) &&
175  return false; /* LHS is non-strict but not constant */
176  if (!bms_is_empty(item2_relids) &&
178  return false; /* RHS is non-strict but not constant */
179  }
180 
181  /* Calculate nullable-relid sets for each side of the clause */
182  item1_nullable_relids = bms_intersect(item1_relids,
183  restrictinfo->nullable_relids);
184  item2_nullable_relids = bms_intersect(item2_relids,
185  restrictinfo->nullable_relids);
186 
187  /*
188  * We use the declared input types of the operator, not exprType() of the
189  * inputs, as the nominal datatypes for opfamily lookup. This presumes
190  * that btree operators are always registered with amoplefttype and
191  * amoprighttype equal to their declared input types. We will need this
192  * info anyway to build EquivalenceMember nodes, and by extracting it now
193  * we can use type comparisons to short-circuit some equal() tests.
194  */
195  op_input_types(opno, &item1_type, &item2_type);
196 
197  opfamilies = restrictinfo->mergeopfamilies;
198 
199  /*
200  * Sweep through the existing EquivalenceClasses looking for matches to
201  * item1 and item2. These are the possible outcomes:
202  *
203  * 1. We find both in the same EC. The equivalence is already known, so
204  * there's nothing to do.
205  *
206  * 2. We find both in different ECs. Merge the two ECs together.
207  *
208  * 3. We find just one. Add the other to its EC.
209  *
210  * 4. We find neither. Make a new, two-entry EC.
211  *
212  * Note: since all ECs are built through this process or the similar
213  * search in get_eclass_for_sort_expr(), it's impossible that we'd match
214  * an item in more than one existing nonvolatile EC. So it's okay to stop
215  * at the first match.
216  */
217  ec1 = ec2 = NULL;
218  em1 = em2 = NULL;
219  foreach(lc1, root->eq_classes)
220  {
221  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
222  ListCell *lc2;
223 
224  /* Never match to a volatile EC */
225  if (cur_ec->ec_has_volatile)
226  continue;
227 
228  /*
229  * The collation has to match; check this first since it's cheaper
230  * than the opfamily comparison.
231  */
232  if (collation != cur_ec->ec_collation)
233  continue;
234 
235  /*
236  * A "match" requires matching sets of btree opfamilies. Use of
237  * equal() for this test has implications discussed in the comments
238  * for get_mergejoin_opfamilies().
239  */
240  if (!equal(opfamilies, cur_ec->ec_opfamilies))
241  continue;
242 
243  foreach(lc2, cur_ec->ec_members)
244  {
245  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
246 
247  Assert(!cur_em->em_is_child); /* no children yet */
248 
249  /*
250  * If below an outer join, don't match constants: they're not as
251  * constant as they look.
252  */
253  if ((below_outer_join || cur_ec->ec_below_outer_join) &&
254  cur_em->em_is_const)
255  continue;
256 
257  if (!ec1 &&
258  item1_type == cur_em->em_datatype &&
259  equal(item1, cur_em->em_expr))
260  {
261  ec1 = cur_ec;
262  em1 = cur_em;
263  if (ec2)
264  break;
265  }
266 
267  if (!ec2 &&
268  item2_type == cur_em->em_datatype &&
269  equal(item2, cur_em->em_expr))
270  {
271  ec2 = cur_ec;
272  em2 = cur_em;
273  if (ec1)
274  break;
275  }
276  }
277 
278  if (ec1 && ec2)
279  break;
280  }
281 
282  /* Sweep finished, what did we find? */
283 
284  if (ec1 && ec2)
285  {
286  /* If case 1, nothing to do, except add to sources */
287  if (ec1 == ec2)
288  {
289  ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
290  ec1->ec_below_outer_join |= below_outer_join;
291  ec1->ec_min_security = Min(ec1->ec_min_security,
292  restrictinfo->security_level);
293  ec1->ec_max_security = Max(ec1->ec_max_security,
294  restrictinfo->security_level);
295  /* mark the RI as associated with this eclass */
296  restrictinfo->left_ec = ec1;
297  restrictinfo->right_ec = ec1;
298  /* mark the RI as usable with this pair of EMs */
299  restrictinfo->left_em = em1;
300  restrictinfo->right_em = em2;
301  return true;
302  }
303 
304  /*
305  * Case 2: need to merge ec1 and ec2. This should never happen after
306  * we've built any canonical pathkeys; if it did, those pathkeys might
307  * be rendered non-canonical by the merge.
308  */
309  if (root->canon_pathkeys != NIL)
310  elog(ERROR, "too late to merge equivalence classes");
311 
312  /*
313  * We add ec2's items to ec1, then set ec2's ec_merged link to point
314  * to ec1 and remove ec2 from the eq_classes list. We cannot simply
315  * delete ec2 because that could leave dangling pointers in existing
316  * PathKeys. We leave it behind with a link so that the merged EC can
317  * be found.
318  */
319  ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
320  ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
321  ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
322  ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
323  ec1->ec_has_const |= ec2->ec_has_const;
324  /* can't need to set has_volatile */
326  ec1->ec_min_security = Min(ec1->ec_min_security,
327  ec2->ec_min_security);
328  ec1->ec_max_security = Max(ec1->ec_max_security,
329  ec2->ec_max_security);
330  ec2->ec_merged = ec1;
331  root->eq_classes = list_delete_ptr(root->eq_classes, ec2);
332  /* just to avoid debugging confusion w/ dangling pointers: */
333  ec2->ec_members = NIL;
334  ec2->ec_sources = NIL;
335  ec2->ec_derives = NIL;
336  ec2->ec_relids = NULL;
337  ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
338  ec1->ec_below_outer_join |= below_outer_join;
339  ec1->ec_min_security = Min(ec1->ec_min_security,
340  restrictinfo->security_level);
341  ec1->ec_max_security = Max(ec1->ec_max_security,
342  restrictinfo->security_level);
343  /* mark the RI as associated with this eclass */
344  restrictinfo->left_ec = ec1;
345  restrictinfo->right_ec = ec1;
346  /* mark the RI as usable with this pair of EMs */
347  restrictinfo->left_em = em1;
348  restrictinfo->right_em = em2;
349  }
350  else if (ec1)
351  {
352  /* Case 3: add item2 to ec1 */
353  em2 = add_eq_member(ec1, item2, item2_relids, item2_nullable_relids,
354  false, item2_type);
355  ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
356  ec1->ec_below_outer_join |= below_outer_join;
357  ec1->ec_min_security = Min(ec1->ec_min_security,
358  restrictinfo->security_level);
359  ec1->ec_max_security = Max(ec1->ec_max_security,
360  restrictinfo->security_level);
361  /* mark the RI as associated with this eclass */
362  restrictinfo->left_ec = ec1;
363  restrictinfo->right_ec = ec1;
364  /* mark the RI as usable with this pair of EMs */
365  restrictinfo->left_em = em1;
366  restrictinfo->right_em = em2;
367  }
368  else if (ec2)
369  {
370  /* Case 3: add item1 to ec2 */
371  em1 = add_eq_member(ec2, item1, item1_relids, item1_nullable_relids,
372  false, item1_type);
373  ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
374  ec2->ec_below_outer_join |= below_outer_join;
375  ec2->ec_min_security = Min(ec2->ec_min_security,
376  restrictinfo->security_level);
377  ec2->ec_max_security = Max(ec2->ec_max_security,
378  restrictinfo->security_level);
379  /* mark the RI as associated with this eclass */
380  restrictinfo->left_ec = ec2;
381  restrictinfo->right_ec = ec2;
382  /* mark the RI as usable with this pair of EMs */
383  restrictinfo->left_em = em1;
384  restrictinfo->right_em = em2;
385  }
386  else
387  {
388  /* Case 4: make a new, two-entry EC */
390 
391  ec->ec_opfamilies = opfamilies;
392  ec->ec_collation = collation;
393  ec->ec_members = NIL;
394  ec->ec_sources = list_make1(restrictinfo);
395  ec->ec_derives = NIL;
396  ec->ec_relids = NULL;
397  ec->ec_has_const = false;
398  ec->ec_has_volatile = false;
399  ec->ec_below_outer_join = below_outer_join;
400  ec->ec_broken = false;
401  ec->ec_sortref = 0;
402  ec->ec_min_security = restrictinfo->security_level;
403  ec->ec_max_security = restrictinfo->security_level;
404  ec->ec_merged = NULL;
405  em1 = add_eq_member(ec, item1, item1_relids, item1_nullable_relids,
406  false, item1_type);
407  em2 = add_eq_member(ec, item2, item2_relids, item2_nullable_relids,
408  false, item2_type);
409 
410  root->eq_classes = lappend(root->eq_classes, ec);
411 
412  /* mark the RI as associated with this eclass */
413  restrictinfo->left_ec = ec;
414  restrictinfo->right_ec = ec;
415  /* mark the RI as usable with this pair of EMs */
416  restrictinfo->left_em = em1;
417  restrictinfo->right_em = em2;
418  }
419 
420  return true;
421 }
#define NIL
Definition: pg_list.h:69
Index security_level
Definition: relation.h:1649
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2870
bool leakproof
Definition: relation.h:1647
Index ec_min_security
Definition: relation.h:724
List * ec_derives
Definition: relation.h:716
#define Min(x, y)
Definition: c.h:802
Index ec_sortref
Definition: relation.h:723
Definition: nodes.h:508
Relids left_relids
Definition: relation.h:1664
List * list_concat(List *list1, List *list2)
Definition: list.c:321
bool ec_below_outer_join
Definition: relation.h:721
EquivalenceClass * right_ec
Definition: relation.h:1686
Index ec_max_security
Definition: relation.h:725
List * list_delete_ptr(List *list, void *datum)
Definition: list.c:590
unsigned int Oid
Definition: postgres_ext.h:31
List * mergeopfamilies
Definition: relation.h:1682
#define list_make1(x1)
Definition: pg_list.h:133
#define ERROR
Definition: elog.h:43
#define is_opclause(clause)
Definition: clauses.h:20
EquivalenceMember * left_em
Definition: relation.h:1687
Node * get_leftop(const Expr *clause)
Definition: clauses.c:198
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:808
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:456
List * ec_sources
Definition: relation.h:715
Relids ec_relids
Definition: relation.h:717
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1135
List * canon_pathkeys
Definition: relation.h:234
List * lappend(List *list, void *datum)
Definition: list.c:128
EquivalenceMember * right_em
Definition: relation.h:1688
Expr * clause
Definition: relation.h:1637
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:633
List * ec_opfamilies
Definition: relation.h:712
Relids nullable_relids
Definition: relation.h:1661
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:251
#define Max(x, y)
Definition: c.h:796
#define makeNode(_type_)
Definition: nodes.h:556
Relids right_relids
Definition: relation.h:1665
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:232
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
bool ec_has_volatile
Definition: relation.h:720
Node * get_rightop(const Expr *clause)
Definition: clauses.c:215
EquivalenceClass * left_ec
Definition: relation.h:1685
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, Relids nullable_relids, bool is_child, Oid datatype)
Definition: equivclass.c:505
#define elog
Definition: elog.h:219
bool contain_nonstrict_functions(Node *clause)
Definition: clauses.c:1234
Definition: pg_list.h:45
struct EquivalenceClass * ec_merged
Definition: relation.h:726
List * ec_members
Definition: relation.h:714
void reconsider_outer_join_clauses ( PlannerInfo root)

Definition at line 1532 of file equivclass.c.

References distribute_restrictinfo_to_rels(), PlannerInfo::full_join_clauses, PlannerInfo::left_join_clauses, lfirst, list_delete_cell(), list_head(), lnext, next, RestrictInfo::norm_selec, NULL, RestrictInfo::outer_selec, reconsider_full_join_clause(), reconsider_outer_join_clause(), and PlannerInfo::right_join_clauses.

Referenced by query_planner().

1533 {
1534  bool found;
1535  ListCell *cell;
1536  ListCell *prev;
1537  ListCell *next;
1538 
1539  /* Outer loop repeats until we find no more deductions */
1540  do
1541  {
1542  found = false;
1543 
1544  /* Process the LEFT JOIN clauses */
1545  prev = NULL;
1546  for (cell = list_head(root->left_join_clauses); cell; cell = next)
1547  {
1548  RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1549 
1550  next = lnext(cell);
1551  if (reconsider_outer_join_clause(root, rinfo, true))
1552  {
1553  found = true;
1554  /* remove it from the list */
1555  root->left_join_clauses =
1556  list_delete_cell(root->left_join_clauses, cell, prev);
1557  /* we throw it back anyway (see notes above) */
1558  /* but the thrown-back clause has no extra selectivity */
1559  rinfo->norm_selec = 2.0;
1560  rinfo->outer_selec = 1.0;
1561  distribute_restrictinfo_to_rels(root, rinfo);
1562  }
1563  else
1564  prev = cell;
1565  }
1566 
1567  /* Process the RIGHT JOIN clauses */
1568  prev = NULL;
1569  for (cell = list_head(root->right_join_clauses); cell; cell = next)
1570  {
1571  RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1572 
1573  next = lnext(cell);
1574  if (reconsider_outer_join_clause(root, rinfo, false))
1575  {
1576  found = true;
1577  /* remove it from the list */
1578  root->right_join_clauses =
1579  list_delete_cell(root->right_join_clauses, cell, prev);
1580  /* we throw it back anyway (see notes above) */
1581  /* but the thrown-back clause has no extra selectivity */
1582  rinfo->norm_selec = 2.0;
1583  rinfo->outer_selec = 1.0;
1584  distribute_restrictinfo_to_rels(root, rinfo);
1585  }
1586  else
1587  prev = cell;
1588  }
1589 
1590  /* Process the FULL JOIN clauses */
1591  prev = NULL;
1592  for (cell = list_head(root->full_join_clauses); cell; cell = next)
1593  {
1594  RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1595 
1596  next = lnext(cell);
1597  if (reconsider_full_join_clause(root, rinfo))
1598  {
1599  found = true;
1600  /* remove it from the list */
1601  root->full_join_clauses =
1602  list_delete_cell(root->full_join_clauses, cell, prev);
1603  /* we throw it back anyway (see notes above) */
1604  /* but the thrown-back clause has no extra selectivity */
1605  rinfo->norm_selec = 2.0;
1606  rinfo->outer_selec = 1.0;
1607  distribute_restrictinfo_to_rels(root, rinfo);
1608  }
1609  else
1610  prev = cell;
1611  }
1612  } while (found);
1613 
1614  /* Now, any remaining clauses have to be thrown back */
1615  foreach(cell, root->left_join_clauses)
1616  {
1617  RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1618 
161