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, double heap_pages, double index_pages)
 
void create_partial_bitmap_paths (PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
 
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, bool require_parallel_safe)
 
Pathget_cheapest_fractional_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, double fraction)
 
Pathget_cheapest_parallel_safe_total_inner (List *paths)
 
Listbuild_index_pathkeys (PlannerInfo *root, IndexOptInfo *index, ScanDirection scandir)
 
Listbuild_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 119 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 175 of file paths.h.

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

Function Documentation

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

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

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

Definition at line 107 of file joinpath.c.

References PlannerInfo::all_baserels, bms_add_members(), bms_difference(), bms_is_subset(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), enable_hashjoin, enable_mergejoin, RelOptInfo::fdwroutine, FdwRoutine::GetForeignJoinPaths, hash_inner_and_outer(), JoinPathExtraData::inner_unique, innerrel_is_unique(), JOIN_ANTI, JOIN_FULL, PlannerInfo::join_info_list, JOIN_INNER, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, SpecialJoinInfo::jointype, RelOptInfo::lateral_relids, lfirst, match_unsorted_outer(), JoinPathExtraData::mergeclause_list, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, 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 populate_joinrel_with_paths().

114 {
115  JoinPathExtraData extra;
116  bool mergejoin_allowed = true;
117  ListCell *lc;
118 
119  extra.restrictlist = restrictlist;
120  extra.mergeclause_list = NIL;
121  extra.sjinfo = sjinfo;
122  extra.param_source_rels = NULL;
123 
124  /*
125  * See if the inner relation is provably unique for this outer rel.
126  *
127  * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
128  * matter since the executor can make the equivalent optimization anyway;
129  * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
130  * must be considering a semijoin whose inner side is not provably unique
131  * (else reduce_unique_semijoins would've simplified it), so there's no
132  * point in calling innerrel_is_unique. However, if the LHS covers all of
133  * the semijoin's min_lefthand, then it's appropriate to set inner_unique
134  * because the path produced by create_unique_path will be unique relative
135  * to the LHS. (If we have an LHS that's only part of the min_lefthand,
136  * that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
137  * letting that value escape this module.
138  */
139  switch (jointype)
140  {
141  case JOIN_SEMI:
142  case JOIN_ANTI:
143  extra.inner_unique = false; /* well, unproven */
144  break;
145  case JOIN_UNIQUE_INNER:
146  extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
147  outerrel->relids);
148  break;
149  case JOIN_UNIQUE_OUTER:
150  extra.inner_unique = innerrel_is_unique(root,
151  outerrel->relids,
152  innerrel,
153  JOIN_INNER,
154  restrictlist,
155  false);
156  break;
157  default:
158  extra.inner_unique = innerrel_is_unique(root,
159  outerrel->relids,
160  innerrel,
161  jointype,
162  restrictlist,
163  false);
164  break;
165  }
166 
167  /*
168  * Find potential mergejoin clauses. We can skip this if we are not
169  * interested in doing a mergejoin. However, mergejoin may be our only
170  * way of implementing a full outer join, so override enable_mergejoin if
171  * it's a full join.
172  */
173  if (enable_mergejoin || jointype == JOIN_FULL)
175  joinrel,
176  outerrel,
177  innerrel,
178  restrictlist,
179  jointype,
180  &mergejoin_allowed);
181 
182  /*
183  * If it's SEMI, ANTI, or inner_unique join, compute correction factors
184  * for cost estimation. These will be the same for all paths.
185  */
186  if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique)
187  compute_semi_anti_join_factors(root, outerrel, innerrel,
188  jointype, sjinfo, restrictlist,
189  &extra.semifactors);
190 
191  /*
192  * Decide whether it's sensible to generate parameterized paths for this
193  * joinrel, and if so, which relations such paths should require. There
194  * is usually no need to create a parameterized result path unless there
195  * is a join order restriction that prevents joining one of our input rels
196  * directly to the parameter source rel instead of joining to the other
197  * input rel. (But see allow_star_schema_join().) This restriction
198  * reduces the number of parameterized paths we have to deal with at
199  * higher join levels, without compromising the quality of the resulting
200  * plan. We express the restriction as a Relids set that must overlap the
201  * parameterization of any proposed join path.
202  */
203  foreach(lc, root->join_info_list)
204  {
205  SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
206 
207  /*
208  * SJ is relevant to this join if we have some part of its RHS
209  * (possibly not all of it), and haven't yet joined to its LHS. (This
210  * test is pretty simplistic, but should be sufficient considering the
211  * join has already been proven legal.) If the SJ is relevant, it
212  * presents constraints for joining to anything not in its RHS.
213  */
214  if (bms_overlap(joinrel->relids, sjinfo2->min_righthand) &&
215  !bms_overlap(joinrel->relids, sjinfo2->min_lefthand))
218  sjinfo2->min_righthand));
219 
220  /* full joins constrain both sides symmetrically */
221  if (sjinfo2->jointype == JOIN_FULL &&
222  bms_overlap(joinrel->relids, sjinfo2->min_lefthand) &&
223  !bms_overlap(joinrel->relids, sjinfo2->min_righthand))
226  sjinfo2->min_lefthand));
227  }
228 
229  /*
230  * However, when a LATERAL subquery is involved, there will simply not be
231  * any paths for the joinrel that aren't parameterized by whatever the
232  * subquery is parameterized by, unless its parameterization is resolved
233  * within the joinrel. So we might as well allow additional dependencies
234  * on whatever residual lateral dependencies the joinrel will have.
235  */
237  joinrel->lateral_relids);
238 
239  /*
240  * 1. Consider mergejoin paths where both relations must be explicitly
241  * sorted. Skip this if we can't mergejoin.
242  */
243  if (mergejoin_allowed)
244  sort_inner_and_outer(root, joinrel, outerrel, innerrel,
245  jointype, &extra);
246 
247  /*
248  * 2. Consider paths where the outer relation need not be explicitly
249  * sorted. This includes both nestloops and mergejoins where the outer
250  * path is already ordered. Again, skip this if we can't mergejoin.
251  * (That's okay because we know that nestloop can't handle right/full
252  * joins at all, so it wouldn't work in the prohibited cases either.)
253  */
254  if (mergejoin_allowed)
255  match_unsorted_outer(root, joinrel, outerrel, innerrel,
256  jointype, &extra);
257 
258 #ifdef NOT_USED
259 
260  /*
261  * 3. Consider paths where the inner relation need not be explicitly
262  * sorted. This includes mergejoins only (nestloops were already built in
263  * match_unsorted_outer).
264  *
265  * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
266  * significant difference between the inner and outer side of a mergejoin,
267  * so match_unsorted_inner creates no paths that aren't equivalent to
268  * those made by match_unsorted_outer when add_paths_to_joinrel() is
269  * invoked with the two rels given in the other order.
270  */
271  if (mergejoin_allowed)
272  match_unsorted_inner(root, joinrel, outerrel, innerrel,
273  jointype, &extra);
274 #endif
275 
276  /*
277  * 4. Consider paths where both outer and inner relations must be hashed
278  * before being joined. As above, disregard enable_hashjoin for full
279  * joins, because there may be no other alternative.
280  */
281  if (enable_hashjoin || jointype == JOIN_FULL)
282  hash_inner_and_outer(root, joinrel, outerrel, innerrel,
283  jointype, &extra);
284 
285  /*
286  * 5. If inner and outer relations are foreign tables (or joins) belonging
287  * to the same server and assigned to the same user to check access
288  * permissions as, give the FDW a chance to push down joins.
289  */
290  if (joinrel->fdwroutine &&
292  joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
293  outerrel, innerrel,
294  jointype, &extra);
295 
296  /*
297  * 6. Finally, give extensions a chance to manipulate the path list.
298  */
300  set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
301  jointype, &extra);
302 }
#define NIL
Definition: pg_list.h:69
SemiAntiJoinFactors semifactors
Definition: relation.h:2184
List * join_info_list
Definition: relation.h:250
Relids min_righthand
Definition: relation.h:1918
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1583
Relids lateral_relids
Definition: relation.h:550
SpecialJoinInfo * sjinfo
Definition: relation.h:2183
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:785
Relids all_baserels
Definition: relation.h:196
GetForeignJoinPaths_function GetForeignJoinPaths
Definition: fdwapi.h:188
Relids param_source_rels
Definition: relation.h:2185
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:838
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
struct FdwRoutine * fdwroutine
Definition: relation.h:576
List * mergeclause_list
Definition: relation.h:2181
Relids relids
Definition: relation.h:525
bool innerrel_is_unique(PlannerInfo *root, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition: analyzejoins.c:962
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:1814
List * restrictlist
Definition: relation.h:2180
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:27
bool enable_mergejoin
Definition: costsize.c:127
#define NULL
Definition: c.h:229
#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:3755
JoinType jointype
Definition: relation.h:1921
bool enable_hashjoin
Definition: costsize.c:128
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
Relids min_lefthand
Definition: relation.h:1917
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:755
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1237
Expr* adjust_rowcompare_for_index ( RowCompareExpr clause,
IndexOptInfo index,
int  indexcol,
List **  indexcolnos,
bool var_on_left_p 
)

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

3829 {
3830  bool var_on_left;
3831  int op_strategy;
3832  Oid op_lefttype;
3833  Oid op_righttype;
3834  int matching_cols;
3835  Oid expr_op;
3836  List *opfamilies;
3837  List *lefttypes;
3838  List *righttypes;
3839  List *new_ops;
3840  ListCell *largs_cell;
3841  ListCell *rargs_cell;
3842  ListCell *opnos_cell;
3843  ListCell *collids_cell;
3844 
3845  /* We have to figure out (again) how the first col matches */
3846  var_on_left = match_index_to_operand((Node *) linitial(clause->largs),
3847  indexcol, index);
3848  Assert(var_on_left ||
3850  indexcol, index));
3851  *var_on_left_p = var_on_left;
3852 
3853  expr_op = linitial_oid(clause->opnos);
3854  if (!var_on_left)
3855  expr_op = get_commutator(expr_op);
3856  get_op_opfamily_properties(expr_op, index->opfamily[indexcol], false,
3857  &op_strategy,
3858  &op_lefttype,
3859  &op_righttype);
3860 
3861  /* Initialize returned list of which index columns are used */
3862  *indexcolnos = list_make1_int(indexcol);
3863 
3864  /* Build lists of the opfamilies and operator datatypes in case needed */
3865  opfamilies = list_make1_oid(index->opfamily[indexcol]);
3866  lefttypes = list_make1_oid(op_lefttype);
3867  righttypes = list_make1_oid(op_righttype);
3868 
3869  /*
3870  * See how many of the remaining columns match some index column in the
3871  * same way. As in match_clause_to_indexcol(), the "other" side of any
3872  * potential index condition is OK as long as it doesn't use Vars from the
3873  * indexed relation.
3874  */
3875  matching_cols = 1;
3876  largs_cell = lnext(list_head(clause->largs));
3877  rargs_cell = lnext(list_head(clause->rargs));
3878  opnos_cell = lnext(list_head(clause->opnos));
3879  collids_cell = lnext(list_head(clause->inputcollids));
3880 
3881  while (largs_cell != NULL)
3882  {
3883  Node *varop;
3884  Node *constop;
3885  int i;
3886 
3887  expr_op = lfirst_oid(opnos_cell);
3888  if (var_on_left)
3889  {
3890  varop = (Node *) lfirst(largs_cell);
3891  constop = (Node *) lfirst(rargs_cell);
3892  }
3893  else
3894  {
3895  varop = (Node *) lfirst(rargs_cell);
3896  constop = (Node *) lfirst(largs_cell);
3897  /* indexkey is on right, so commute the operator */
3898  expr_op = get_commutator(expr_op);
3899  if (expr_op == InvalidOid)
3900  break; /* operator is not usable */
3901  }
3902  if (bms_is_member(index->rel->relid, pull_varnos(constop)))
3903  break; /* no good, Var on wrong side */
3904  if (contain_volatile_functions(constop))
3905  break; /* no good, volatile comparison value */
3906 
3907  /*
3908  * The Var side can match any column of the index.
3909  */
3910  for (i = 0; i < index->ncolumns; i++)
3911  {
3912  if (match_index_to_operand(varop, i, index) &&
3913  get_op_opfamily_strategy(expr_op,
3914  index->opfamily[i]) == op_strategy &&
3916  lfirst_oid(collids_cell)))
3917  break;
3918  }
3919  if (i >= index->ncolumns)
3920  break; /* no match found */
3921 
3922  /* Add column number to returned list */
3923  *indexcolnos = lappend_int(*indexcolnos, i);
3924 
3925  /* Add opfamily and datatypes to lists */
3926  get_op_opfamily_properties(expr_op, index->opfamily[i], false,
3927  &op_strategy,
3928  &op_lefttype,
3929  &op_righttype);
3930  opfamilies = lappend_oid(opfamilies, index->opfamily[i]);
3931  lefttypes = lappend_oid(lefttypes, op_lefttype);
3932  righttypes = lappend_oid(righttypes, op_righttype);
3933 
3934  /* This column matches, keep scanning */
3935  matching_cols++;
3936  largs_cell = lnext(largs_cell);
3937  rargs_cell = lnext(rargs_cell);
3938  opnos_cell = lnext(opnos_cell);
3939  collids_cell = lnext(collids_cell);
3940  }
3941 
3942  /* Return clause as-is if it's all usable as index quals */
3943  if (matching_cols == list_length(clause->opnos))
3944  return (Expr *) clause;
3945 
3946  /*
3947  * We have to generate a subset rowcompare (possibly just one OpExpr). The
3948  * painful part of this is changing < to <= or > to >=, so deal with that
3949  * first.
3950  */
3951  if (op_strategy == BTLessEqualStrategyNumber ||
3952  op_strategy == BTGreaterEqualStrategyNumber)
3953  {
3954  /* easy, just use the same operators */
3955  new_ops = list_truncate(list_copy(clause->opnos), matching_cols);
3956  }
3957  else
3958  {
3959  ListCell *opfamilies_cell;
3960  ListCell *lefttypes_cell;
3961  ListCell *righttypes_cell;
3962 
3963  if (op_strategy == BTLessStrategyNumber)
3964  op_strategy = BTLessEqualStrategyNumber;
3965  else if (op_strategy == BTGreaterStrategyNumber)
3966  op_strategy = BTGreaterEqualStrategyNumber;
3967  else
3968  elog(ERROR, "unexpected strategy number %d", op_strategy);
3969  new_ops = NIL;
3970  lefttypes_cell = list_head(lefttypes);
3971  righttypes_cell = list_head(righttypes);
3972  foreach(opfamilies_cell, opfamilies)
3973  {
3974  Oid opfam = lfirst_oid(opfamilies_cell);
3975  Oid lefttype = lfirst_oid(lefttypes_cell);
3976  Oid righttype = lfirst_oid(righttypes_cell);
3977 
3978  expr_op = get_opfamily_member(opfam, lefttype, righttype,
3979  op_strategy);
3980  if (!OidIsValid(expr_op)) /* should not happen */
3981  elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
3982  op_strategy, lefttype, righttype, opfam);
3983  if (!var_on_left)
3984  {
3985  expr_op = get_commutator(expr_op);
3986  if (!OidIsValid(expr_op)) /* should not happen */
3987  elog(ERROR, "could not find commutator of operator %d(%u,%u) of opfamily %u",
3988  op_strategy, lefttype, righttype, opfam);
3989  }
3990  new_ops = lappend_oid(new_ops, expr_op);
3991  lefttypes_cell = lnext(lefttypes_cell);
3992  righttypes_cell = lnext(righttypes_cell);
3993  }
3994  }
3995 
3996  /* If we have more than one matching col, create a subset rowcompare */
3997  if (matching_cols > 1)
3998  {
4000 
4001  if (var_on_left)
4002  rc->rctype = (RowCompareType) op_strategy;
4003  else
4004  rc->rctype = (op_strategy == BTLessEqualStrategyNumber) ?
4006  rc->opnos = new_ops;
4008  matching_cols);
4010  matching_cols);
4011  rc->largs = list_truncate(copyObject(clause->largs),
4012  matching_cols);
4013  rc->rargs = list_truncate(copyObject(clause->rargs),
4014  matching_cols);
4015  return (Expr *) rc;
4016  }
4017  else
4018  {
4019  return make_opclause(linitial_oid(new_ops), BOOLOID, false,
4020  copyObject(linitial(clause->largs)),
4021  copyObject(linitial(clause->rargs)),
4022  InvalidOid,
4023  linitial_oid(clause->inputcollids));
4024  }
4025 }
#define NIL
Definition: pg_list.h:69
Oid get_commutator(Oid opno)
Definition: lsyscache.c:1313
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Oid * indexcollations
Definition: relation.h:643
bool match_index_to_operand(Node *operand, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:3180
RowCompareType rctype
Definition: primnodes.h:1031
List * opfamilies
Definition: primnodes.h:1033
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:509
Expr * make_opclause(Oid opno, Oid opresulttype, bool opretset, Expr *leftop, Expr *rightop, Oid opcollid, Oid inputcollid)
Definition: clauses.c:172
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:957
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:538
#define BTLessEqualStrategyNumber
Definition: stratnum.h:30
RelOptInfo * rel
Definition: relation.h:633
#define linitial(l)
Definition: pg_list.h:111
#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:145
int ncolumns
Definition: relation.h:641
#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:553
#define list_make1_oid(x1)
Definition: pg_list.h:151
#define InvalidOid
Definition: postgres_ext.h:36
RowCompareType
Definition: primnodes.h:1017
#define makeNode(_type_)
Definition: nodes.h:557
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
#define linitial_oid(l)
Definition: pg_list.h:113
static int list_length(const List *l)
Definition: pg_list.h:89
#define BOOLOID
Definition: pg_type.h:288
Oid * opfamily
Definition: relation.h:644
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
#define copyObject(obj)
Definition: nodes.h:622
List * inputcollids
Definition: primnodes.h:1034
#define BTLessStrategyNumber
Definition: stratnum.h:29
Definition: pg_list.h:45
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:420
#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 553 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().

559 {
560  List *pathkeys;
561  Oid opfamily,
562  opcintype;
563  int16 strategy;
564  PathKey *cpathkey;
565 
566  /* Find the operator in pg_amop --- failure shouldn't happen */
567  if (!get_ordering_op_properties(opno,
568  &opfamily, &opcintype, &strategy))
569  elog(ERROR, "operator %u is not a valid ordering operator",
570  opno);
571 
572  cpathkey = make_pathkey_from_sortinfo(root,
573  expr,
574  nullable_relids,
575  opfamily,
576  opcintype,
577  exprCollation((Node *) expr),
578  (strategy == BTGreaterStrategyNumber),
579  (strategy == BTGreaterStrategyNumber),
580  0,
581  rel,
582  create_it);
583 
584  if (cpathkey)
585  pathkeys = list_make1(cpathkey);
586  else
587  pathkeys = NIL;
588 
589  return pathkeys;
590 }
signed short int16
Definition: c.h:255
#define NIL
Definition: pg_list.h:69
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Definition: nodes.h:509
unsigned int Oid
Definition: postgres_ext.h:31
#define list_make1(x1)
Definition: pg_list.h:139
#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:720
#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 460 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().

463 {
464  List *retval = NIL;
465  ListCell *lc;
466  int i;
467 
468  if (index->sortopfamily == NULL)
469  return NIL; /* non-orderable index */
470 
471  i = 0;
472  foreach(lc, index->indextlist)
473  {
474  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
475  Expr *indexkey;
476  bool reverse_sort;
477  bool nulls_first;
478  PathKey *cpathkey;
479 
480  /* We assume we don't need to make a copy of the tlist item */
481  indexkey = indextle->expr;
482 
483  if (ScanDirectionIsBackward(scandir))
484  {
485  reverse_sort = !index->reverse_sort[i];
486  nulls_first = !index->nulls_first[i];
487  }
488  else
489  {
490  reverse_sort = index->reverse_sort[i];
491  nulls_first = index->nulls_first[i];
492  }
493 
494  /*
495  * OK, try to make a canonical pathkey for this sort key. Note we're
496  * underneath any outer joins, so nullable_relids should be NULL.
497  */
498  cpathkey = make_pathkey_from_sortinfo(root,
499  indexkey,
500  NULL,
501  index->sortopfamily[i],
502  index->opcintype[i],
503  index->indexcollations[i],
504  reverse_sort,
505  nulls_first,
506  0,
507  index->rel->relids,
508  false);
509 
510  if (cpathkey)
511  {
512  /*
513  * We found the sort key in an EquivalenceClass, so it's relevant
514  * for this query. Add it to list, unless it's redundant.
515  */
516  if (!pathkey_is_redundant(cpathkey, retval))
517  retval = lappend(retval, cpathkey);
518  }
519  else
520  {
521  /*
522  * Boolean index keys might be redundant even if they do not
523  * appear in an EquivalenceClass, because of our special treatment
524  * of boolean equality conditions --- see the comment for
525  * indexcol_is_bool_constant_for_query(). If that applies, we can
526  * continue to examine lower-order index columns. Otherwise, the
527  * sort key is not an interesting sort order for this query, so we
528  * should stop considering index columns; any lower-order sort
529  * keys won't be useful either.
530  */
532  break;
533  }
534 
535  i++;
536  }
537 
538  return retval;
539 }
#define NIL
Definition: pg_list.h:69
Oid * indexcollations
Definition: relation.h:643
List * indextlist
Definition: relation.h:656
Oid * sortopfamily
Definition: relation.h:646
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
RelOptInfo * rel
Definition: relation.h:633
Relids relids
Definition: relation.h:525
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:229
#define lfirst(lc)
Definition: pg_list.h:106
Expr * expr
Definition: primnodes.h:1368
Oid * opcintype
Definition: relation.h:645
bool indexcol_is_bool_constant_for_query(IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3131
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:648
bool * reverse_sort
Definition: relation.h:647
Definition: pg_list.h:45
List* build_join_pathkeys ( PlannerInfo root,
RelOptInfo joinrel,
JoinType  jointype,
List outer_pathkeys 
)

Definition at line 822 of file pathkeys.c.

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

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

826 {
827  if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
828  return NIL;
829 
830  /*
831  * This used to be quite a complex bit of code, but now that all pathkey
832  * sublists start out life canonicalized, we don't have to do a darn thing
833  * here!
834  *
835  * We do, however, need to truncate the pathkeys list, since it may
836  * contain pathkeys that were useful for forming this joinrel but are
837  * uninteresting to higher levels.
838  */
839  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
840 }
#define NIL
Definition: pg_list.h:69
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:1518
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:560
int32 exprTypmod(const Node *expr)
Definition: nodeFuncs.c:276
Definition: nodes.h:509
unsigned int Oid
Definition: postgres_ext.h:31
#define IsPolymorphicType(typid)
Definition: pg_type.h:745
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:720
void * arg
void check_index_predicates ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 2774 of file indxpath.c.

References PlannerInfo::all_baserels, Assert, RelOptInfo::baserestrictinfo, bms_difference(), bms_is_empty(), bms_union(), RestrictInfo::clause, contain_mutable_functions(), find_childrel_parents(), generate_join_implied_equalities(), get_plan_rowmark(), RelOptInfo::indexlist, IndexOptInfo::indpred, IndexOptInfo::indrestrictinfo, IS_SIMPLE_REL, join_clause_is_movable_to(), RelOptInfo::joininfo, lappend(), lfirst, list_concat(), list_copy(), list_make1, NIL, 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().

2775 {
2776  List *clauselist;
2777  bool have_partial;
2778  bool is_target_rel;
2779  Relids otherrels;
2780  ListCell *lc;
2781 
2782  /* Indexes are available only on base or "other" member relations. */
2783  Assert(IS_SIMPLE_REL(rel));
2784 
2785  /*
2786  * Initialize the indrestrictinfo lists to be identical to
2787  * baserestrictinfo, and check whether there are any partial indexes. If
2788  * not, this is all we need to do.
2789  */
2790  have_partial = false;
2791  foreach(lc, rel->indexlist)
2792  {
2794 
2795  index->indrestrictinfo = rel->baserestrictinfo;
2796  if (index->indpred)
2797  have_partial = true;
2798  }
2799  if (!have_partial)
2800  return;
2801 
2802  /*
2803  * Construct a list of clauses that we can assume true for the purpose of
2804  * proving the index(es) usable. Restriction clauses for the rel are
2805  * always usable, and so are any join clauses that are "movable to" this
2806  * rel. Also, we can consider any EC-derivable join clauses (which must
2807  * be "movable to" this rel, by definition).
2808  */
2809  clauselist = list_copy(rel->baserestrictinfo);
2810 
2811  /* Scan the rel's join clauses */
2812  foreach(lc, rel->joininfo)
2813  {
2814  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2815 
2816  /* Check if clause can be moved to this rel */
2817  if (!join_clause_is_movable_to(rinfo, rel))
2818  continue;
2819 
2820  clauselist = lappend(clauselist, rinfo);
2821  }
2822 
2823  /*
2824  * Add on any equivalence-derivable join clauses. Computing the correct
2825  * relid sets for generate_join_implied_equalities is slightly tricky
2826  * because the rel could be a child rel rather than a true baserel, and in
2827  * that case we must remove its parents' relid(s) from all_baserels.
2828  */
2829  if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
2830  otherrels = bms_difference(root->all_baserels,
2831  find_childrel_parents(root, rel));
2832  else
2833  otherrels = bms_difference(root->all_baserels, rel->relids);
2834 
2835  if (!bms_is_empty(otherrels))
2836  clauselist =
2837  list_concat(clauselist,
2839  bms_union(rel->relids,
2840  otherrels),
2841  otherrels,
2842  rel));
2843 
2844  /*
2845  * Normally we remove quals that are implied by a partial index's
2846  * predicate from indrestrictinfo, indicating that they need not be
2847  * checked explicitly by an indexscan plan using this index. However, if
2848  * the rel is a target relation of UPDATE/DELETE/SELECT FOR UPDATE, we
2849  * cannot remove such quals from the plan, because they need to be in the
2850  * plan so that they will be properly rechecked by EvalPlanQual testing.
2851  * Some day we might want to remove such quals from the main plan anyway
2852  * and pass them through to EvalPlanQual via a side channel; but for now,
2853  * we just don't remove implied quals at all for target relations.
2854  */
2855  is_target_rel = (rel->relid == root->parse->resultRelation ||
2856  get_plan_rowmark(root->rowMarks, rel->relid) != NULL);
2857 
2858  /*
2859  * Now try to prove each index predicate true, and compute the
2860  * indrestrictinfo lists for partial indexes. Note that we compute the
2861  * indrestrictinfo list even for non-predOK indexes; this might seem
2862  * wasteful, but we may be able to use such indexes in OR clauses, cf
2863  * generate_bitmap_or_paths().
2864  */
2865  foreach(lc, rel->indexlist)
2866  {
2867  IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
2868  ListCell *lcr;
2869 
2870  if (index->indpred == NIL)
2871  continue; /* ignore non-partial indexes here */
2872 
2873  if (!index->predOK) /* don't repeat work if already proven OK */
2874  index->predOK = predicate_implied_by(index->indpred, clauselist,
2875  false);
2876 
2877  /* If rel is an update target, leave indrestrictinfo as set above */
2878  if (is_target_rel)
2879  continue;
2880 
2881  /* Else compute indrestrictinfo as the non-implied quals */
2882  index->indrestrictinfo = NIL;
2883  foreach(lcr, rel->baserestrictinfo)
2884  {
2885  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
2886 
2887  /* predicate_implied_by() assumes first arg is immutable */
2888  if (contain_mutable_functions((Node *) rinfo->clause) ||
2890  index->indpred, false))
2891  index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
2892  }
2893  }
2894 }
#define NIL
Definition: pg_list.h:69
bool predicate_implied_by(List *predicate_list, List *clause_list, bool clause_is_check)
Definition: predtest.c:135
List * rowMarks
Definition: relation.h:256
Query * parse
Definition: relation.h:155
bool predOK
Definition: relation.h:664
RelOptKind reloptkind
Definition: relation.h:522
List * baserestrictinfo
Definition: relation.h:585
int resultRelation
Definition: parsenodes.h:120
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
List * list_copy(const List *oldlist)
Definition: list.c:1160
Definition: nodes.h:509
List * list_concat(List *list1, List *list2)
Definition: list.c:321
#define IS_SIMPLE_REL(rel)
Definition: relation.h:505
Definition: type.h:89
#define list_make1(x1)
Definition: pg_list.h:139
Relids all_baserels
Definition: relation.h:196
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:589
Relids relids
Definition: relation.h:525
Index relid
Definition: relation.h:553
List * lappend(List *list, void *datum)
Definition: list.c:128
Expr * clause
Definition: relation.h:1747
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
List * indrestrictinfo
Definition: relation.h:658
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1000
List * indexlist
Definition: relation.h:562
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:218
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:878
List * indpred
Definition: relation.h:654
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(), add_paths_to_append_rel(), pathkeys_contained_in(), 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:180
#define NULL
Definition: c.h:229
#define lfirst(lc)
Definition: pg_list.h:106
int compute_parallel_worker ( RelOptInfo rel,
double  heap_pages,
double  index_pages 
)

Definition at line 3067 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(), create_partial_bitmap_paths(), and create_plain_partial_paths().

3068 {
3069  int parallel_workers = 0;
3070 
3071  /*
3072  * If the user has set the parallel_workers reloption, use that; otherwise
3073  * select a default number of workers.
3074  */
3075  if (rel->rel_parallel_workers != -1)
3076  parallel_workers = rel->rel_parallel_workers;
3077  else
3078  {
3079  /*
3080  * If the number of pages being scanned is insufficient to justify a
3081  * parallel scan, just return zero ... unless it's an inheritance
3082  * child. In that case, we want to generate a parallel path here
3083  * anyway. It might not be worthwhile just for this relation, but
3084  * when combined with all of its inheritance siblings it may well pay
3085  * off.
3086  */
3087  if (rel->reloptkind == RELOPT_BASEREL &&
3088  ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
3089  (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
3090  return 0;
3091 
3092  if (heap_pages >= 0)
3093  {
3094  int heap_parallel_threshold;
3095  int heap_parallel_workers = 1;
3096 
3097  /*
3098  * Select the number of workers based on the log of the size of
3099  * the relation. This probably needs to be a good deal more
3100  * sophisticated, but we need something here for now. Note that
3101  * the upper limit of the min_parallel_table_scan_size GUC is
3102  * chosen to prevent overflow here.
3103  */
3104  heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
3105  while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
3106  {
3107  heap_parallel_workers++;
3108  heap_parallel_threshold *= 3;
3109  if (heap_parallel_threshold > INT_MAX / 3)
3110  break; /* avoid overflow */
3111  }
3112 
3113  parallel_workers = heap_parallel_workers;
3114  }
3115 
3116  if (index_pages >= 0)
3117  {
3118  int index_parallel_workers = 1;
3119  int index_parallel_threshold;
3120 
3121  /* same calculation as for heap_pages above */
3122  index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
3123  while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
3124  {
3125  index_parallel_workers++;
3126  index_parallel_threshold *= 3;
3127  if (index_parallel_threshold > INT_MAX / 3)
3128  break; /* avoid overflow */
3129  }
3130 
3131  if (parallel_workers > 0)
3132  parallel_workers = Min(parallel_workers, index_parallel_workers);
3133  else
3134  parallel_workers = index_parallel_workers;
3135  }
3136  }
3137 
3138  /*
3139  * In no case use more than max_parallel_workers_per_gather workers.
3140  */
3141  parallel_workers = Min(parallel_workers, max_parallel_workers_per_gather);
3142 
3143  return parallel_workers;
3144 }
RelOptKind reloptkind
Definition: relation.h:522
#define Min(x, y)
Definition: c.h:806
uint32 BlockNumber
Definition: block.h:31
int min_parallel_index_scan_size
Definition: allpaths.c:61
int rel_parallel_workers
Definition: relation.h:569
#define Max(x, y)
Definition: c.h:800
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 607 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().

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

Definition at line 232 of file indxpath.c.

References add_path(), Assert, RelOptInfo::baserestrictinfo, bms_equal_any(), bms_is_subset(), choose_bitmap_and(), consider_index_join_clauses(), RelOptInfo::consider_parallel, create_bitmap_heap_path(), create_partial_bitmap_paths(), forboth, generate_bitmap_or_paths(), get_bitmap_tree_required_outer(), get_index_paths(), get_loop_count(), INDEX_MAX_KEYS, RelOptInfo::indexlist, IndexOptInfo::indpred, lappend(), RelOptInfo::lateral_relids, lfirst, list_concat(), match_eclass_clauses_to_index(), match_join_clauses_to_index(), match_restriction_clauses_to_index(), MemSet, IndexOptInfo::ncolumns, NIL, IndexClauseSet::nonempty, NULL, 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, 0);
341  add_path(rel, (Path *) bpath);
342 
343  /* create a partial bitmap heap path */
344  if (rel->consider_parallel && rel->lateral_relids == NULL)
345  create_partial_bitmap_paths(root, rel, bitmapqual);
346  }
347 
348  /*
349  * Likewise, if we found anything usable, generate BitmapHeapPaths for the
350  * most promising combinations of join bitmap index paths. Our strategy
351  * is to generate one such path for each distinct parameterization seen
352  * among the available bitmap index paths. This may look pretty
353  * expensive, but usually there won't be very many distinct
354  * parameterizations. (This logic is quite similar to that in
355  * consider_index_join_clauses, but we're working with whole paths not
356  * individual clauses.)
357  */
358  if (bitjoinpaths != NIL)
359  {
360  List *path_outer;
361  List *all_path_outers;
362  ListCell *lc;
363 
364  /*
365  * path_outer holds the parameterization of each path in bitjoinpaths
366  * (to save recalculating that several times), while all_path_outers
367  * holds all distinct parameterization sets.
368  */
369  path_outer = all_path_outers = NIL;
370  foreach(lc, bitjoinpaths)
371  {
372  Path *path = (Path *) lfirst(lc);
373  Relids required_outer;
374 
375  required_outer = get_bitmap_tree_required_outer(path);
376  path_outer = lappend(path_outer, required_outer);
377  if (!bms_equal_any(required_outer, all_path_outers))
378  all_path_outers = lappend(all_path_outers, required_outer);
379  }
380 
381  /* Now, for each distinct parameterization set ... */
382  foreach(lc, all_path_outers)
383  {
384  Relids max_outers = (Relids) lfirst(lc);
385  List *this_path_set;
386  Path *bitmapqual;
387  Relids required_outer;
388  double loop_count;
389  BitmapHeapPath *bpath;
390  ListCell *lcp;
391  ListCell *lco;
392 
393  /* Identify all the bitmap join paths needing no more than that */
394  this_path_set = NIL;
395  forboth(lcp, bitjoinpaths, lco, path_outer)
396  {
397  Path *path = (Path *) lfirst(lcp);
398  Relids p_outers = (Relids) lfirst(lco);
399 
400  if (bms_is_subset(p_outers, max_outers))
401  this_path_set = lappend(this_path_set, path);
402  }
403 
404  /*
405  * Add in restriction bitmap paths, since they can be used
406  * together with any join paths.
407  */
408  this_path_set = list_concat(this_path_set, bitindexpaths);
409 
410  /* Select best AND combination for this parameterization */
411  bitmapqual = choose_bitmap_and(root, rel, this_path_set);
412 
413  /* And push that path into the mix */
414  required_outer = get_bitmap_tree_required_outer(bitmapqual);
415  loop_count = get_loop_count(root, rel->relid, required_outer);
416  bpath = create_bitmap_heap_path(root, rel, bitmapqual,
417  required_outer, loop_count, 0);
418  add_path(rel, (Path *) bpath);
419  }
420  }
421 }
#define NIL
Definition: pg_list.h:69
bool predOK
Definition: relation.h:664
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:180
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
bool nonempty
Definition: indxpath.c:60
List * baserestrictinfo
Definition: relation.h:585
#define MemSet(start, val, len)
Definition: c.h:857
List * list_concat(List *list1, List *list2)
Definition: list.c:321
Definition: type.h:89
static bool bms_equal_any(Relids relids, List *relids_list)
Definition: indxpath.c:708
Relids lateral_relids
Definition: relation.h:550
static void match_eclass_clauses_to_index(PlannerInfo *root, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition: indxpath.c:2145
static void get_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauses, List **bitindexpaths)
Definition: indxpath.c:737
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
static Path * choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
Definition: indxpath.c:1372
int ncolumns
Definition: relation.h:641
Index relid
Definition: relation.h:553
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:1963
static void match_restriction_clauses_to_index(RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition: indxpath.c:2101
static List * generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel, List *clauses, List *other_clauses)
Definition: indxpath.c:1265
List * indexlist
Definition: relation.h:562
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
#define INDEX_MAX_KEYS
bool consider_parallel
Definition: relation.h:533
static void match_join_clauses_to_index(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauseset, List **joinorclauses)
Definition: indxpath.c:2115
static Relids get_bitmap_tree_required_outer(Path *bitmapqual)
Definition: indxpath.c:1749
List * indpred
Definition: relation.h:654
void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
Definition: allpaths.c:3035
Definition: pg_list.h:45
Definition: relation.h:948
BitmapHeapPath * create_bitmap_heap_path(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual, Relids required_outer, double loop_count, int parallel_degree)
Definition: pathnode.c:1067
static void consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, IndexClauseSet *jclauseset, IndexClauseSet *eclauseset, List **bitindexpaths)
Definition: indxpath.c:439
void create_partial_bitmap_paths ( PlannerInfo root,
RelOptInfo rel,
Path bitmapqual 
)

Definition at line 3035 of file allpaths.c.

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

Referenced by create_index_paths().

3037 {
3038  int parallel_workers;
3039  double pages_fetched;
3040 
3041  /* Compute heap pages for bitmap heap scan */
3042  pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
3043  NULL, NULL);
3044 
3045  parallel_workers = compute_parallel_worker(rel, pages_fetched, -1);
3046 
3047  if (parallel_workers <= 0)
3048  return;
3049 
3050  add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
3051  bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
3052 }
Relids lateral_relids
Definition: relation.h:550
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages)
Definition: allpaths.c:3067
#define NULL
Definition: c.h:229
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:752
Definition: relation.h:948
double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, int loop_count, Cost *cost, double *tuple)
Definition: costsize.c:5102
BitmapHeapPath * create_bitmap_heap_path(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual, Relids required_outer, double loop_count, int parallel_degree)
Definition: pathnode.c:1067
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:550
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1172
Definition: pg_list.h:45
Definition: relation.h:948
bool eclass_useful_for_merging ( PlannerInfo root,
EquivalenceClass eclass,
RelOptInfo rel 
)

Definition at line 2397 of file equivclass.c.

References Assert, bms_is_empty(), bms_is_subset(), bms_overlap(), EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_relids, EquivalenceMember::em_is_child, EquivalenceMember::em_relids, IS_OTHER_REL, lfirst, list_length(), RelOptInfo::relids, and RelOptInfo::top_parent_relids.

Referenced by get_useful_ecs_for_relation(), and pathkeys_useful_for_merging().

2400 {
2401  Relids relids;
2402  ListCell *lc;
2403 
2404  Assert(!eclass->ec_merged);
2405 
2406  /*
2407  * Won't generate joinclauses if const or single-member (the latter test
2408  * covers the volatile case too)
2409  */
2410  if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
2411  return false;
2412 
2413  /*
2414  * Note we don't test ec_broken; if we did, we'd need a separate code path
2415  * to look through ec_sources. Checking the members anyway is OK as a
2416  * possibly-overoptimistic heuristic.
2417  */
2418 
2419  /* If specified rel is a child, we must consider the topmost parent rel */
2420  if (IS_OTHER_REL(rel))
2421  {
2423  relids = rel->top_parent_relids;
2424  }
2425  else
2426  relids = rel->relids;
2427 
2428  /* If rel already includes all members of eclass, no point in searching */
2429  if (bms_is_subset(eclass->ec_relids, relids))
2430  return false;
2431 
2432  /* To join, we need a member not in the given rel */
2433  foreach(lc, eclass->ec_members)
2434  {
2435  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
2436 
2437  if (cur_em->em_is_child)
2438  continue; /* ignore children here */
2439 
2440  if (!bms_overlap(cur_em->em_relids, relids))
2441  return true;
2442  }
2443 
2444  return false;
2445 }
#define IS_OTHER_REL(rel)
Definition: relation.h:516
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
Relids ec_relids
Definition: relation.h:777
Relids relids
Definition: relation.h:525
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
Relids em_relids
Definition: relation.h:823
#define Assert(condition)
Definition: c.h:675
#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:443
struct EquivalenceClass * ec_merged
Definition: relation.h:786
List * ec_members
Definition: relation.h:774
Relids top_parent_relids
Definition: relation.h:594
void expand_indexqual_conditions ( IndexOptInfo index,
List indexclauses,
List indexclausecols,
List **  indexquals_p,
List **  indexqualcols_p 
)

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

3529 {
3530  List *indexquals = NIL;
3531  List *indexqualcols = NIL;
3532  ListCell *lcc,
3533  *lci;
3534 
3535  forboth(lcc, indexclauses, lci, indexclausecols)
3536  {
3537  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcc);
3538  int indexcol = lfirst_int(lci);
3539  Expr *clause = rinfo->clause;
3540  Oid curFamily = index->opfamily[indexcol];
3541  Oid curCollation = index->indexcollations[indexcol];
3542 
3543  /* First check for boolean cases */
3544  if (IsBooleanOpfamily(curFamily))
3545  {
3546  Expr *boolqual;
3547 
3548  boolqual = expand_boolean_index_clause((Node *) clause,
3549  indexcol,
3550  index);
3551  if (boolqual)
3552  {
3553  indexquals = lappend(indexquals,
3554  make_simple_restrictinfo(boolqual));
3555  indexqualcols = lappend_int(indexqualcols, indexcol);
3556  continue;
3557  }
3558  }
3559 
3560  /*
3561  * Else it must be an opclause (usual case), ScalarArrayOp,
3562  * RowCompare, or NullTest
3563  */
3564  if (is_opclause(clause))
3565  {
3566  indexquals = list_concat(indexquals,
3568  curFamily,
3569  curCollation));
3570  /* expand_indexqual_opclause can produce multiple clauses */
3571  while (list_length(indexqualcols) < list_length(indexquals))
3572  indexqualcols = lappend_int(indexqualcols, indexcol);
3573  }
3574  else if (IsA(clause, ScalarArrayOpExpr))
3575  {
3576  /* no extra work at this time */
3577  indexquals = lappend(indexquals, rinfo);
3578  indexqualcols = lappend_int(indexqualcols, indexcol);
3579  }
3580  else if (IsA(clause, RowCompareExpr))
3581  {
3582  indexquals = lappend(indexquals,
3584  index,
3585  indexcol));
3586  indexqualcols = lappend_int(indexqualcols, indexcol);
3587  }
3588  else if (IsA(clause, NullTest))
3589  {
3590  Assert(index->amsearchnulls);
3591  indexquals = lappend(indexquals, rinfo);
3592  indexqualcols = lappend_int(indexqualcols, indexcol);
3593  }
3594  else
3595  elog(ERROR, "unsupported indexqual type: %d",
3596  (int) nodeTag(clause));
3597  }
3598 
3599  *indexquals_p = indexquals;
3600  *indexqualcols_p = indexqualcols;
3601 }
#define NIL
Definition: pg_list.h:69
#define IsBooleanOpfamily(opfamily)
Definition: indxpath.c:43
#define IsA(nodeptr, _type_)
Definition: nodes.h:560
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:180
Oid * indexcollations
Definition: relation.h:643
Definition: nodes.h:509
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:3611
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:1747
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
static RestrictInfo * expand_indexqual_rowcompare(RestrictInfo *rinfo, IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3771
static int list_length(const List *l)
Definition: pg_list.h:89
#define nodeTag(nodeptr)
Definition: nodes.h:514
Oid * opfamily
Definition: relation.h:644
#define elog
Definition: elog.h:219
bool amsearchnulls
Definition: relation.h:673
static List * expand_indexqual_opclause(RestrictInfo *rinfo, Oid opfamily, Oid idxcollation)
Definition: indxpath.c:3677
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 1944 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().

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

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

1007 {
1008  List *mergeclauses = NIL;
1009  ListCell *i;
1010 
1011  /* make sure we have eclasses cached in the clauses */
1012  foreach(i, restrictinfos)
1013  {
1014  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1015 
1016  update_mergeclause_eclasses(root, rinfo);
1017  }
1018 
1019  foreach(i, pathkeys)
1020  {
1021  PathKey *pathkey = (PathKey *) lfirst(i);
1022  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1023  List *matched_restrictinfos = NIL;
1024  ListCell *j;
1025 
1026  /*----------
1027  * A mergejoin clause matches a pathkey if it has the same EC.
1028  * If there are multiple matching clauses, take them all. In plain
1029  * inner-join scenarios we expect only one match, because
1030  * equivalence-class processing will have removed any redundant
1031  * mergeclauses. However, in outer-join scenarios there might be
1032  * multiple matches. An example is
1033  *
1034  * select * from a full join b
1035  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1036  *
1037  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1038  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1039  * we *must* do so or we will be unable to form a valid plan.
1040  *
1041  * We expect that the given pathkeys list is canonical, which means
1042  * no two members have the same EC, so it's not possible for this
1043  * code to enter the same mergeclause into the result list twice.
1044  *
1045  * It's possible that multiple matching clauses might have different
1046  * ECs on the other side, in which case the order we put them into our
1047  * result makes a difference in the pathkeys required for the other
1048  * input path. However this routine hasn't got any info about which
1049  * order would be best, so we don't worry about that.
1050  *
1051  * It's also possible that the selected mergejoin clauses produce
1052  * a noncanonical ordering of pathkeys for the other side, ie, we
1053  * might select clauses that reference b.v1, b.v2, b.v1 in that
1054  * order. This is not harmful in itself, though it suggests that
1055  * the clauses are partially redundant. Since it happens only with
1056  * redundant query conditions, we don't bother to eliminate it.
1057  * make_inner_pathkeys_for_merge() has to delete duplicates when
1058  * it constructs the canonical pathkeys list, and we also have to
1059  * deal with the case in create_mergejoin_plan().
1060  *----------
1061  */
1062  foreach(j, restrictinfos)
1063  {
1064  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1065  EquivalenceClass *clause_ec;
1066 
1067  if (outer_keys)
1068  clause_ec = rinfo->outer_is_left ?
1069  rinfo->left_ec : rinfo->right_ec;
1070  else
1071  clause_ec = rinfo->outer_is_left ?
1072  rinfo->right_ec : rinfo->left_ec;
1073  if (clause_ec == pathkey_ec)
1074  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1075  }
1076 
1077  /*
1078  * If we didn't find a mergeclause, we're done --- any additional
1079  * sort-key positions in the pathkeys are useless. (But we can still
1080  * mergejoin if we found at least one mergeclause.)
1081  */
1082  if (matched_restrictinfos == NIL)
1083  break;
1084 
1085  /*
1086  * If we did find usable mergeclause(s) for this sort-key position,
1087  * add them to result list.
1088  */
1089  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1090  }
1091 
1092  return mergeclauses;
1093 }
#define NIL
Definition: pg_list.h:69
List * list_concat(List *list1, List *list2)
Definition: list.c:321
EquivalenceClass * right_ec
Definition: relation.h:1796
bool outer_is_left
Definition: relation.h:1802
List * lappend(List *list, void *datum)
Definition: list.c:128
#define lfirst(lc)
Definition: pg_list.h:106
EquivalenceClass * pk_eclass
Definition: relation.h:851
EquivalenceClass * left_ec
Definition: relation.h:1795
int i
Definition: pg_list.h:45
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:968
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:591
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:179
bool has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
Definition: equivclass.c:2358
int simple_rel_array_size
Definition: relation.h:180
unsigned int Index
Definition: c.h:365
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:235
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:786
List * ec_members
Definition: relation.h:774
void generate_gather_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 2199 of file allpaths.c.

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

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

2200 {
2201  Path *cheapest_partial_path;
2202  Path *simple_gather_path;
2203  ListCell *lc;
2204 
2205  /* If there are no partial paths, there's nothing to do here. */
2206  if (rel->partial_pathlist == NIL)
2207  return;
2208 
2209  /*
2210  * The output of Gather is always unsorted, so there's only one partial
2211  * path of interest: the cheapest one. That will be the one at the front
2212  * of partial_pathlist because of the way add_partial_path works.
2213  */
2214  cheapest_partial_path = linitial(rel->partial_pathlist);
2215  simple_gather_path = (Path *)
2216  create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
2217  NULL, NULL);
2218  add_path(rel, simple_gather_path);
2219 
2220  /*
2221  * For each useful ordering, we can consider an order-preserving Gather
2222  * Merge.
2223  */
2224  foreach(lc, rel->partial_pathlist)
2225  {
2226  Path *subpath = (Path *) lfirst(lc);
2227  GatherMergePath *path;
2228 
2229  if (subpath->pathkeys == NIL)
2230  continue;
2231 
2232  path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
2233  subpath->pathkeys, NULL, NULL);
2234  add_path(rel, &path->path);
2235  }
2236 }
#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:1730
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
List * partial_pathlist
Definition: relation.h:541
#define linitial(l)
Definition: pg_list.h:111
GatherMergePath * create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, List *pathkeys, Relids required_outer, double *rows)
Definition: pathnode.c:1639
List * pathkeys
Definition: relation.h:968
#define NULL
Definition: c.h:229
#define lfirst(lc)
Definition: pg_list.h:106
struct PathTarget * reltarget
Definition: relation.h:536
Definition: relation.h:948
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:234
List* generate_implied_equalities_for_column ( PlannerInfo root,
RelOptInfo rel,
ec_matches_callback_type  callback,
void *  callback_arg,
Relids  prohibited_rels 
)

Definition at line 2173 of file equivclass.c.

References Assert, 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(), IS_SIMPLE_REL, lappend(), lfirst, list_length(), NIL, NULL, OidIsValid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, result, and select_equality_operator().

Referenced by match_eclass_clauses_to_index(), and postgresGetForeignPaths().

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

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:235
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 Assert, bms_is_empty(), bms_overlap(), bms_union(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), IS_OTHER_REL, lfirst, list_concat(), list_length(), NIL, RelOptInfo::relids, result, and RelOptInfo::top_parent_relids.

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 (IS_OTHER_REL(inner_rel))
1064  {
1065  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1066 
1067  /* Fetch relid set for the topmost parent rel */
1068  nominal_inner_relids = inner_rel->top_parent_relids;
1069  /* ECs will be marked with the parent's relid, not the child's */
1070  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1071  }
1072  else
1073  {
1074  nominal_inner_relids = inner_relids;
1075  nominal_join_relids = join_relids;
1076  }
1077 
1078  foreach(lc, eclasses)
1079  {
1081  List *sublist = NIL;
1082 
1083  /* ECs containing consts do not need any further enforcement */
1084  if (ec->ec_has_const)
1085  continue;
1086 
1087  /* Single-member ECs won't generate any deductions */
1088  if (list_length(ec->ec_members) <= 1)
1089  continue;
1090 
1091  /* We can quickly ignore any that don't overlap the join, too */
1092  if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1093  continue;
1094 
1095  if (!ec->ec_broken)
1097  ec,
1098  join_relids,
1099  outer_relids,
1100  inner_relids);
1101 
1102  /* Recover if we failed to generate required derived clauses */
1103  if (ec->ec_broken)
1105  ec,
1106  nominal_join_relids,
1107  outer_relids,
1108  nominal_inner_relids,
1109  inner_rel);
1110 
1111  result = list_concat(result, sublist);
1112  }
1113 
1114  return result;
1115 }
#define NIL
Definition: pg_list.h:69
#define IS_OTHER_REL(rel)
Definition: relation.h:516
List * list_concat(List *list1, List *list2)
Definition: list.c:321
return result
Definition: formatting.c:1633
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:1297
Relids ec_relids
Definition: relation.h:777
Relids relids
Definition: relation.h:525
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1121
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:218
static int list_length(const List *l)
Definition: pg_list.h:89
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
Definition: pg_list.h:45
List * ec_members
Definition: relation.h:774
Relids top_parent_relids
Definition: relation.h:594
Path* get_cheapest_fractional_path_for_pathkeys ( List paths,
List pathkeys,
Relids  required_outer,
double  fraction 
)

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

392 {
393  Path *matched_path = NULL;
394  ListCell *l;
395 
396  foreach(l, paths)
397  {
398  Path *path = (Path *) lfirst(l);
399 
400  /*
401  * Since cost comparison is a lot cheaper than pathkey comparison, do
402  * that first. (XXX is that still true?)
403  */
404  if (matched_path != NULL &&
405  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
406  continue;
407 
408  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
409  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
410  matched_path = path;
411  }
412  return matched_path;
413 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:317
List * pathkeys
Definition: relation.h:968
#define NULL
Definition: c.h:229
#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:973
Definition: relation.h:948
Path* get_cheapest_parallel_safe_total_inner ( List paths)

Definition at line 421 of file pathkeys.c.

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

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

422 {
423  ListCell *l;
424 
425  foreach(l, paths)
426  {
427  Path *innerpath = (Path *) lfirst(l);
428 
429  if (innerpath->parallel_safe &&
430  bms_is_empty(PATH_REQ_OUTER(innerpath)))
431  return innerpath;
432  }
433 
434  return NULL;
435 }
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
#define NULL
Definition: c.h:229
#define lfirst(lc)
Definition: pg_list.h:106
bool parallel_safe
Definition: relation.h:960
#define PATH_REQ_OUTER(path)
Definition: relation.h:973
Definition: relation.h:948
Path* get_cheapest_path_for_pathkeys ( List paths,
List pathkeys,
Relids  required_outer,
CostSelector  cost_criterion,
bool  require_parallel_safe 
)

Definition at line 343 of file pathkeys.c.

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

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

347 {
348  Path *matched_path = NULL;
349  ListCell *l;
350 
351  foreach(l, paths)
352  {
353  Path *path = (Path *) lfirst(l);
354 
355  /*
356  * Since cost comparison is a lot cheaper than pathkey comparison, do
357  * that first. (XXX is that still true?)
358  */
359  if (matched_path != NULL &&
360  compare_path_costs(matched_path, path, cost_criterion) <= 0)
361  continue;
362 
363  if (require_parallel_safe && !path->parallel_safe)
364  continue;
365 
366  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
367  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
368  matched_path = path;
369  }
370  return matched_path;
371 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
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:968
#define NULL
Definition: c.h:229
#define lfirst(lc)
Definition: pg_list.h:106
bool parallel_safe
Definition: relation.h:960
#define PATH_REQ_OUTER(path)
Definition: relation.h:973
Definition: relation.h:948
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:2962
Index ec_min_security
Definition: relation.h:784
List * ec_derives
Definition: relation.h:776
bool expression_returns_set(Node *clause)
Definition: nodeFuncs.c:670
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:783
Definition: nodes.h:509
bool ec_below_outer_join
Definition: relation.h:781
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:957
Index ec_max_security
Definition: relation.h:785
#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:775
Relids ec_relids
Definition: relation.h:777
Relids pull_varnos(Node *node)
Definition: var.c:95
bool contain_window_function(Node *clause)
Definition: clauses.c:727
List * lappend(List *list, void *datum)
Definition: list.c:128
List * ec_opfamilies
Definition: relation.h:772
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:252
Relids em_relids
Definition: relation.h:823
#define makeNode(_type_)
Definition: nodes.h:557
#define NULL
Definition: c.h:229
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:235
bool ec_has_volatile
Definition: relation.h:780
bool contain_agg_clause(Node *clause)
Definition: clauses.c:417
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:287
#define elog
Definition: elog.h:219
#define copyObject(obj)
Definition: nodes.h:622
struct EquivalenceClass * ec_merged
Definition: relation.h:786
List * ec_members
Definition: relation.h:774
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:131
bool has_relevant_eclass_joinclause ( PlannerInfo root,
RelOptInfo rel1 
)

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

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

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

1559 {
1560  if (rel->joininfo != NIL || rel->has_eclass_joins)
1561  return true; /* might be able to use pathkeys for merging */
1562  if (root->query_pathkeys != NIL)
1563  return true; /* might be able to use them for ordering */
1564  return false; /* definitely useless */
1565 }
bool has_eclass_joins
Definition: relation.h:591
#define NIL
Definition: pg_list.h:69
List * query_pathkeys
Definition: relation.h:262
List * joininfo
Definition: relation.h:589
bool have_dangerous_phv ( PlannerInfo root,
Relids  outer_relids,
Relids  inner_params 
)

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

1154 {
1155  ListCell *lc;
1156 
1157  foreach(lc, root->placeholder_list)
1158  {
1159  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1160 
1161  if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1162  continue; /* ignore, could not be a nestloop param */
1163  if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1164  continue; /* ignore, not relevant to this join */
1165  if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
1166  continue; /* safe, it can be eval'd within outerrel */
1167  /* Otherwise, it's potentially unsafe, so reject the join */
1168  return true;
1169  }
1170 
1171  /* OK to perform the join */
1172  return false;
1173 }
Relids ph_eval_at
Definition: relation.h:2064
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
#define lfirst(lc)
Definition: pg_list.h:106
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
List * placeholder_list
Definition: relation.h:258
bool have_join_order_restriction ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2 
)

Definition at line 919 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, RelOptInfo::relids, and result.

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

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

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

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

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

3132 {
3133  ListCell *lc;
3134 
3135  /* If the index isn't boolean, we can't possibly get a match */
3136  if (!IsBooleanOpfamily(index->opfamily[indexcol]))
3137  return false;
3138 
3139  /* Check each restriction clause for the index's rel */
3140  foreach(lc, index->rel->baserestrictinfo)
3141  {
3142  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3143 
3144  /*
3145  * As in match_clause_to_indexcol, never match pseudoconstants to
3146  * indexes. (It might be semantically okay to do so here, but the
3147  * odds of getting a match are negligible, so don't waste the cycles.)
3148  */
3149  if (rinfo->pseudoconstant)
3150  continue;
3151 
3152  /* See if we can match the clause's expression to the index column */
3153  if (match_boolean_index_clause((Node *) rinfo->clause, indexcol, index))
3154  return true;
3155  }
3156 
3157  return false;
3158 }
#define IsBooleanOpfamily(opfamily)
Definition: indxpath.c:43
List * baserestrictinfo
Definition: relation.h:585
bool pseudoconstant
Definition: relation.h:1755
Definition: nodes.h:509
RelOptInfo * rel
Definition: relation.h:633
static bool match_boolean_index_clause(Node *clause, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:3306
Expr * clause
Definition: relation.h:1747
#define lfirst(lc)
Definition: pg_list.h:106
Oid * opfamily
Definition: relation.h:644
void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

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

920 {
921  Expr *clause = restrictinfo->clause;
922  Oid lefttype,
923  righttype;
924 
925  /* Should be a mergeclause ... */
926  Assert(restrictinfo->mergeopfamilies != NIL);
927  /* ... with links not yet set */
928  Assert(restrictinfo->left_ec == NULL);
929  Assert(restrictinfo->right_ec == NULL);
930 
931  /* Need the declared input types of the operator */
932  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
933 
934  /* Find or create a matching EquivalenceClass for each side */
935  restrictinfo->left_ec =
937  (Expr *) get_leftop(clause),
938  restrictinfo->nullable_relids,
939  restrictinfo->mergeopfamilies,
940  lefttype,
941  ((OpExpr *) clause)->inputcollid,
942  0,
943  NULL,
944  true);
945  restrictinfo->right_ec =
947  (Expr *) get_rightop(clause),
948  restrictinfo->nullable_relids,
949  restrictinfo->mergeopfamilies,
950  righttype,
951  ((OpExpr *) clause)->inputcollid,
952  0,
953  NULL,
954  true);
955 }
#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:1796
unsigned int Oid
Definition: postgres_ext.h:31
List * mergeopfamilies
Definition: relation.h:1792
Node * get_leftop(const Expr *clause)
Definition: clauses.c:199
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1167
Expr * clause
Definition: relation.h:1747
Relids nullable_relids
Definition: relation.h:1771
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
Node * get_rightop(const Expr *clause)
Definition: clauses.c:216
EquivalenceClass * left_ec
Definition: relation.h:1795
bool is_redundant_derived_clause ( RestrictInfo rinfo,
List clauselist 
)

Definition at line 2455 of file equivclass.c.

References lfirst, NULL, and RestrictInfo::parent_ec.

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

2456 {
2457  EquivalenceClass *parent_ec = rinfo->parent_ec;
2458  ListCell *lc;
2459 
2460  /* Fail if it's not a potentially-redundant clause from some EC */
2461  if (parent_ec == NULL)
2462  return false;
2463 
2464  foreach(lc, clauselist)
2465  {
2466  RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
2467 
2468  if (otherrinfo->parent_ec == parent_ec)
2469  return true;
2470  }
2471 
2472  return false;
2473 }
EquivalenceClass * parent_ec
Definition: relation.h:1781
#define NULL
Definition: c.h:229
#define lfirst(lc)
Definition: pg_list.h:106
void join_search_one_level ( PlannerInfo root,
int  level 
)

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

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

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

1295 {
1296  List *pathkeys = NIL;
1297  EquivalenceClass *lastoeclass;
1298  PathKey *opathkey;
1299  ListCell *lc;
1300  ListCell *lop;
1301 
1302  lastoeclass = NULL;
1303  opathkey = NULL;
1304  lop = list_head(outer_pathkeys);
1305 
1306  foreach(lc, mergeclauses)
1307  {
1308  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1309  EquivalenceClass *oeclass;
1310  EquivalenceClass *ieclass;
1311  PathKey *pathkey;
1312 
1313  update_mergeclause_eclasses(root, rinfo);
1314 
1315  if (rinfo->outer_is_left)
1316  {
1317  oeclass = rinfo->left_ec;
1318  ieclass = rinfo->right_ec;
1319  }
1320  else
1321  {
1322  oeclass = rinfo->right_ec;
1323  ieclass = rinfo->left_ec;
1324  }
1325 
1326  /* outer eclass should match current or next pathkeys */
1327  /* we check this carefully for debugging reasons */
1328  if (oeclass != lastoeclass)
1329  {
1330  if (!lop)
1331  elog(ERROR, "too few pathkeys for mergeclauses");
1332  opathkey = (PathKey *) lfirst(lop);
1333  lop = lnext(lop);
1334  lastoeclass = opathkey->pk_eclass;
1335  if (oeclass != lastoeclass)
1336  elog(ERROR, "outer pathkeys do not match mergeclause");
1337  }
1338 
1339  /*
1340  * Often, we'll have same EC on both sides, in which case the outer
1341  * pathkey is also canonical for the inner side, and we can skip a
1342  * useless search.
1343  */
1344  if (ieclass == oeclass)
1345  pathkey = opathkey;
1346  else
1347  pathkey = make_canonical_pathkey(root,
1348  ieclass,
1349  opathkey->pk_opfamily,
1350  opathkey->pk_strategy,
1351  opathkey->pk_nulls_first);
1352 
1353  /*
1354  * Don't generate redundant pathkeys (can happen if multiple
1355  * mergeclauses refer to same EC).
1356  */
1357  if (!pathkey_is_redundant(pathkey, pathkeys))
1358  pathkeys = lappend(pathkeys, pathkey);
1359  }
1360 
1361  return pathkeys;
1362 }
#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:1796
int pk_strategy
Definition: relation.h:853
bool pk_nulls_first
Definition: relation.h:854
#define ERROR
Definition: elog.h:43
bool outer_is_left
Definition: relation.h:1802
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:229
#define lfirst(lc)
Definition: pg_list.h:106
EquivalenceClass * pk_eclass
Definition: relation.h:851
Oid pk_opfamily
Definition: relation.h:852
EquivalenceClass * left_ec
Definition: relation.h:1795
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:968
RelOptInfo* make_join_rel ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2 
)

Definition at line 657 of file joinrels.c.

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

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

658 {
659  Relids joinrelids;
660  SpecialJoinInfo *sjinfo;
661  bool reversed;
662  SpecialJoinInfo sjinfo_data;
663  RelOptInfo *joinrel;
664  List *restrictlist;
665 
666  /* We should never try to join two overlapping sets of rels. */
667  Assert(!bms_overlap(rel1->relids, rel2->relids));
668 
669  /* Construct Relids set that identifies the joinrel. */
670  joinrelids = bms_union(rel1->relids, rel2->relids);
671 
672  /* Check validity and determine join type. */
673  if (!join_is_legal(root, rel1, rel2, joinrelids,
674  &sjinfo, &reversed))
675  {
676  /* invalid join path */
677  bms_free(joinrelids);
678  return NULL;
679  }
680 
681  /* Swap rels if needed to match the join info. */
682  if (reversed)
683  {
684  RelOptInfo *trel = rel1;
685 
686  rel1 = rel2;
687  rel2 = trel;
688  }
689 
690  /*
691  * If it's a plain inner join, then we won't have found anything in
692  * join_info_list. Make up a SpecialJoinInfo so that selectivity
693  * estimation functions will know what's being joined.
694  */
695  if (sjinfo == NULL)
696  {
697  sjinfo = &sjinfo_data;
698  sjinfo->type = T_SpecialJoinInfo;
699  sjinfo->min_lefthand = rel1->relids;
700  sjinfo->min_righthand = rel2->relids;
701  sjinfo->syn_lefthand = rel1->relids;
702  sjinfo->syn_righthand = rel2->relids;
703  sjinfo->jointype = JOIN_INNER;
704  /* we don't bother trying to make the remaining fields valid */
705  sjinfo->lhs_strict = false;
706  sjinfo->delay_upper_joins = false;
707  sjinfo->semi_can_btree = false;
708  sjinfo->semi_can_hash = false;
709  sjinfo->semi_operators = NIL;
710  sjinfo->semi_rhs_exprs = NIL;
711  }
712 
713  /*
714  * Find or build the join RelOptInfo, and compute the restrictlist that
715  * goes with this particular joining.
716  */
717  joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
718  &restrictlist);
719 
720  /*
721  * If we've already proven this join is empty, we needn't consider any
722  * more paths for it.
723  */
724  if (is_dummy_rel(joinrel))
725  {
726  bms_free(joinrelids);
727  return joinrel;
728  }
729 
730  /* Add paths to the join relation. */
731  populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
732  restrictlist);
733 
734  bms_free(joinrelids);
735 
736  return joinrel;
737 }
#define NIL
Definition: pg_list.h:69
static bool is_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1180
bool semi_can_btree
Definition: relation.h:1925
static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinrels.c:747
Relids min_righthand
Definition: relation.h:1918
NodeTag type
Definition: relation.h:1916
Relids syn_lefthand
Definition: relation.h:1919
Relids syn_righthand
Definition: relation.h:1920
List * semi_rhs_exprs
Definition: relation.h:1928
bool semi_can_hash
Definition: relation.h:1926
static bool join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
Definition: joinrels.c:330
Relids relids
Definition: relation.h:525
bool delay_upper_joins
Definition: relation.h:1923
RelOptInfo * build_join_rel(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, List **restrictlist_ptr)
Definition: relnode.c:446
void bms_free(Bitmapset *a)
Definition: bitmapset.c:201
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
JoinType jointype
Definition: relation.h:1921
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:218
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
List * semi_operators
Definition: relation.h:1927
Definition: pg_list.h:45
Relids min_lefthand
Definition: relation.h:1917
RelOptInfo* make_one_rel ( PlannerInfo root,
List joinlist 
)

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

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

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

868 {
869  List *pathkeys = NIL;
870  ListCell *l;
871 
872  foreach(l, sortclauses)
873  {
874  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
875  Expr *sortkey;
876  PathKey *pathkey;
877 
878  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
879  Assert(OidIsValid(sortcl->sortop));
880  pathkey = make_pathkey_from_sortop(root,
881  sortkey,
882  root->nullable_baserels,
883  sortcl->sortop,
884  sortcl->nulls_first,
885  sortcl->tleSortGroupRef,
886  true);
887 
888  /* Canonical form eliminates redundant ordering keys */
889  if (!pathkey_is_redundant(pathkey, pathkeys))
890  pathkeys = lappend(pathkeys, pathkey);
891  }
892  return pathkeys;
893 }
#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:1184
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:382
#define OidIsValid(objectId)
Definition: c.h:538
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:675
#define lfirst(lc)
Definition: pg_list.h:106
Relids nullable_baserels
Definition: relation.h:204
Definition: pg_list.h:45
EquivalenceClass* match_eclasses_to_foreign_key_col ( PlannerInfo root,
ForeignKeyOptInfo fkinfo,
int  colno 
)

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

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

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

3183 {
3184  int indkey;
3185 
3186  /*
3187  * Ignore any RelabelType node above the operand. This is needed to be
3188  * able to apply indexscanning in binary-compatible-operator cases. Note:
3189  * we can assume there is at most one RelabelType node;
3190  * eval_const_expressions() will have simplified if more than one.
3191  */
3192  if (operand && IsA(operand, RelabelType))
3193  operand = (Node *) ((RelabelType *) operand)->arg;
3194 
3195  indkey = index->indexkeys[indexcol];
3196  if (indkey != 0)
3197  {
3198  /*
3199  * Simple index column; operand must be a matching Var.
3200  */
3201  if (operand && IsA(operand, Var) &&
3202  index->rel->relid == ((Var *) operand)->varno &&
3203  indkey == ((Var *) operand)->varattno)
3204  return true;
3205  }
3206  else
3207  {
3208  /*
3209  * Index expression; find the correct expression. (This search could
3210  * be avoided, at the cost of complicating all the callers of this
3211  * routine; doesn't seem worth it.)
3212  */
3213  ListCell *indexpr_item;
3214  int i;
3215  Node *indexkey;
3216 
3217  indexpr_item = list_head(index->indexprs);
3218  for (i = 0; i < indexcol; i++)
3219  {
3220  if (index->indexkeys[i] == 0)
3221  {
3222  if (indexpr_item == NULL)
3223  elog(ERROR, "wrong number of index expressions");
3224  indexpr_item = lnext(indexpr_item);
3225  }
3226  }
3227  if (indexpr_item == NULL)
3228  elog(ERROR, "wrong number of index expressions");
3229  indexkey = (Node *) lfirst(indexpr_item);
3230 
3231  /*
3232  * Does it match the operand? Again, strip any relabeling.
3233  */
3234  if (indexkey && IsA(indexkey, RelabelType))
3235  indexkey = (Node *) ((RelabelType *) indexkey)->arg;
3236 
3237  if (equal(indexkey, operand))
3238  return true;
3239  }
3240 
3241  return false;
3242 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:560
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2962
Definition: nodes.h:509
Definition: primnodes.h:163
RelOptInfo * rel
Definition: relation.h:633
#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:553
#define NULL
Definition: c.h:229
#define lfirst(lc)
Definition: pg_list.h:106
int i
void * arg
int * indexkeys
Definition: relation.h:642
#define elog
Definition: elog.h:219
List * indexprs
Definition: relation.h:653
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:1759
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2962
bool leakproof
Definition: relation.h:1757
Index ec_min_security
Definition: relation.h:784
List * ec_derives
Definition: relation.h:776
#define Min(x, y)
Definition: c.h:806
Index ec_sortref
Definition: relation.h:783
Definition: nodes.h:509
Relids left_relids
Definition: relation.h:1774
List * list_concat(List *list1, List *list2)
Definition: list.c:321
bool ec_below_outer_join
Definition: relation.h:781
EquivalenceClass * right_ec
Definition: relation.h:1796
Index ec_max_security
Definition: relation.h:785
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:1792
#define list_make1(x1)
Definition: pg_list.h:139
#define ERROR
Definition: elog.h:43
#define is_opclause(clause)
Definition: clauses.h:20
EquivalenceMember * left_em
Definition: relation.h:1797
Node * get_leftop(const Expr *clause)
Definition: clauses.c:199
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:838
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:456
List * ec_sources
Definition: relation.h:775
Relids ec_relids
Definition: relation.h:777
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1167
List * canon_pathkeys
Definition: relation.h:237
List * lappend(List *list, void *datum)
Definition: list.c:128
EquivalenceMember * right_em
Definition: relation.h:1798
Expr * clause
Definition: relation.h:1747
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
List * ec_opfamilies
Definition: relation.h:772
Relids nullable_relids
Definition: relation.h:1771
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:252
#define Max(x, y)
Definition: c.h:800
#define makeNode(_type_)
Definition: nodes.h:557
Relids right_relids
Definition: relation.h:1775
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:235
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
bool ec_has_volatile
Definition: relation.h:780
Node * get_rightop(const Expr *clause)
Definition: clauses.c:216
EquivalenceClass * left_ec
Definition: relation.h:1795
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:1288
Definition: pg_list.h:45
struct EquivalenceClass * ec_merged
Definition: relation.h:786
List * ec_members
Definition: relation.h:774
void reconsider_outer_join_clauses ( PlannerInfo root)

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

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