PostgreSQL Source Code  git master
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 generate_partition_wise_join_paths (PlannerInfo *root, RelOptInfo *rel)
 
void create_index_paths (PlannerInfo *root, RelOptInfo *rel)
 
bool relation_has_unique_index_for (PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist)
 
bool indexcol_is_bool_constant_for_query (IndexOptInfo *index, int indexcol)
 
bool match_index_to_operand (Node *operand, int indexcol, IndexOptInfo *index)
 
void 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)
 
void mark_dummy_rel (RelOptInfo *rel)
 
bool have_partkey_equi_join (RelOptInfo *rel1, RelOptInfo *rel2, JoinType jointype, List *restrictlist)
 
bool process_equivalence (PlannerInfo *root, RestrictInfo **p_restrictinfo, bool below_outer_join)
 
Exprcanonicalize_ec_expression (Expr *expr, Oid req_type, Oid req_collation)
 
void reconsider_outer_join_clauses (PlannerInfo *root)
 
EquivalenceClassget_eclass_for_sort_expr (PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
 
void generate_base_implied_equalities (PlannerInfo *root)
 
Listgenerate_join_implied_equalities (PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
 
Listgenerate_join_implied_equalities_for_ecs (PlannerInfo *root, List *eclasses, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
 
bool exprs_known_equal (PlannerInfo *root, Node *item1, Node *item2)
 
EquivalenceClassmatch_eclasses_to_foreign_key_col (PlannerInfo *root, ForeignKeyOptInfo *fkinfo, int colno)
 
void add_child_rel_equivalences (PlannerInfo *root, AppendRelInfo *appinfo, RelOptInfo *parent_rel, RelOptInfo *child_rel)
 
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

◆ ec_matches_callback_type

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

Definition at line 124 of file paths.h.

◆ join_search_hook_type

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

Definition at line 45 of file paths.h.

◆ set_join_pathlist_hook_type

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

Definition at line 36 of file paths.h.

◆ set_rel_pathlist_hook_type

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

Definition at line 29 of file paths.h.

Enumeration Type Documentation

◆ PathKeysComparison

Enumerator
PATHKEYS_EQUAL 
PATHKEYS_BETTER1 
PATHKEYS_BETTER2 
PATHKEYS_DIFFERENT 

Definition at line 181 of file paths.h.

182 {
183  PATHKEYS_EQUAL, /* pathkeys are identical */
184  PATHKEYS_BETTER1, /* pathkey 1 is a superset of pathkey 2 */
185  PATHKEYS_BETTER2, /* vice versa */
186  PATHKEYS_DIFFERENT /* neither pathkey includes the other */
PathKeysComparison
Definition: paths.h:181

Function Documentation

◆ add_child_rel_equivalences()

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

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

2112 {
2113  ListCell *lc1;
2114 
2115  foreach(lc1, root->eq_classes)
2116  {
2117  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
2118  ListCell *lc2;
2119 
2120  /*
2121  * If this EC contains a volatile expression, then generating child
2122  * EMs would be downright dangerous, so skip it. We rely on a
2123  * volatile EC having only one EM.
2124  */
2125  if (cur_ec->ec_has_volatile)
2126  continue;
2127 
2128  /*
2129  * No point in searching if parent rel not mentioned in eclass; but we
2130  * can't tell that for sure if parent rel is itself a child.
2131  */
2132  if (parent_rel->reloptkind == RELOPT_BASEREL &&
2133  !bms_is_subset(parent_rel->relids, cur_ec->ec_relids))
2134  continue;
2135 
2136  foreach(lc2, cur_ec->ec_members)
2137  {
2138  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
2139 
2140  if (cur_em->em_is_const)
2141  continue; /* ignore consts here */
2142 
2143  /* Does it reference parent_rel? */
2144  if (bms_overlap(cur_em->em_relids, parent_rel->relids))
2145  {
2146  /* Yes, generate transformed child version */
2147  Expr *child_expr;
2148  Relids new_relids;
2149  Relids new_nullable_relids;
2150 
2151  child_expr = (Expr *)
2153  (Node *) cur_em->em_expr,
2154  1, &appinfo);
2155 
2156  /*
2157  * Transform em_relids to match. Note we do *not* do
2158  * pull_varnos(child_expr) here, as for example the
2159  * transformation might have substituted a constant, but we
2160  * don't want the child member to be marked as constant.
2161  */
2162  new_relids = bms_difference(cur_em->em_relids,
2163  parent_rel->relids);
2164  new_relids = bms_add_members(new_relids, child_rel->relids);
2165 
2166  /*
2167  * And likewise for nullable_relids. Note this code assumes
2168  * parent and child relids are singletons.
2169  */
2170  new_nullable_relids = cur_em->em_nullable_relids;
2171  if (bms_overlap(new_nullable_relids, parent_rel->relids))
2172  {
2173  new_nullable_relids = bms_difference(new_nullable_relids,
2174  parent_rel->relids);
2175  new_nullable_relids = bms_add_members(new_nullable_relids,
2176  child_rel->relids);
2177  }
2178 
2179  (void) add_eq_member(cur_ec, child_expr,
2180  new_relids, new_nullable_relids,
2181  true, cur_em->em_datatype);
2182  }
2183  }
2184  }
2185 }
RelOptKind reloptkind
Definition: relation.h:582
Relids em_nullable_relids
Definition: relation.h:912
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
Definition: nodes.h:510
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
Relids ec_relids
Definition: relation.h:865
Relids relids
Definition: relation.h:585
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, int nappinfos, AppendRelInfo **appinfos)
Definition: prepunion.c:1945
Relids em_relids
Definition: relation.h:911
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:235
bool ec_has_volatile
Definition: relation.h:868
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:543
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:755
List * ec_members
Definition: relation.h:862

◆ add_paths_to_joinrel()

void add_paths_to_joinrel ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
SpecialJoinInfo sjinfo,
List restrictlist 
)

Definition at line 117 of file joinpath.c.

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

Referenced by populate_joinrel_with_paths().

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

◆ adjust_rowcompare_for_index()

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, 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:731
bool match_index_to_operand(Node *operand, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:3180
RowCompareType rctype
Definition: primnodes.h:1038
List * opfamilies
Definition: primnodes.h:1040
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:510
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:576
#define BTLessEqualStrategyNumber
Definition: stratnum.h:30
RelOptInfo * rel
Definition: relation.h:721
#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:729
#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:613
#define list_make1_oid(x1)
Definition: pg_list.h:151
#define InvalidOid
Definition: postgres_ext.h:36
RowCompareType
Definition: primnodes.h:1024
#define makeNode(_type_)
Definition: nodes.h:558
#define Assert(condition)
Definition: c.h:670
#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:732
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:623
List * inputcollids
Definition: primnodes.h:1041
#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

◆ build_expression_pathkey()

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:283
#define NIL
Definition: pg_list.h:69
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Definition: nodes.h:510
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

◆ build_index_pathkeys()

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, 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:731
List * indextlist
Definition: relation.h:744
Oid * sortopfamily
Definition: relation.h:734
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
RelOptInfo * rel
Definition: relation.h:721
Relids relids
Definition: relation.h:585
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 lfirst(lc)
Definition: pg_list.h:106
Expr * expr
Definition: primnodes.h:1375
Oid * opcintype
Definition: relation.h:733
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:736
bool * reverse_sort
Definition: relation.h:735
Definition: pg_list.h:45

◆ build_join_pathkeys()

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

◆ canonicalize_ec_expression()

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

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

495 {
496  Oid expr_type = exprType((Node *) expr);
497 
498  /*
499  * For a polymorphic-input-type opclass, just keep the same exposed type.
500  */
501  if (IsPolymorphicType(req_type))
502  req_type = expr_type;
503 
504  /*
505  * No work if the expression exposes the right type/collation already.
506  */
507  if (expr_type != req_type ||
508  exprCollation((Node *) expr) != req_collation)
509  {
510  /*
511  * Strip any existing RelabelType, then add a new one if needed. This
512  * is to preserve the invariant of no redundant RelabelTypes.
513  *
514  * If we have to change the exposed type of the stripped expression,
515  * set typmod to -1 (since the new type may not have the same typmod
516  * interpretation). If we only have to change collation, preserve the
517  * exposed typmod.
518  */
519  while (expr && IsA(expr, RelabelType))
520  expr = (Expr *) ((RelabelType *) expr)->arg;
521 
522  if (exprType((Node *) expr) != req_type)
523  expr = (Expr *) makeRelabelType(expr,
524  req_type,
525  -1,
526  req_collation,
528  else if (exprCollation((Node *) expr) != req_collation)
529  expr = (Expr *) makeRelabelType(expr,
530  req_type,
531  exprTypmod((Node *) expr),
532  req_collation,
534  }
535 
536  return expr;
537 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:561
int32 exprTypmod(const Node *expr)
Definition: nodeFuncs.c:276
Definition: nodes.h:510
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:401
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:720
void * arg

◆ check_index_predicates()

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, 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:752
RelOptKind reloptkind
Definition: relation.h:582
List * baserestrictinfo
Definition: relation.h:645
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:510
List * list_concat(List *list1, List *list2)
Definition: list.c:321
#define IS_SIMPLE_REL(rel)
Definition: relation.h:561
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:1071
List * joininfo
Definition: relation.h:649
Relids relids
Definition: relation.h:585
Index relid
Definition: relation.h:613
List * lappend(List *list, void *datum)
Definition: list.c:128
Expr * clause
Definition: relation.h:1835
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
List * indrestrictinfo
Definition: relation.h:746
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1218
List * indexlist
Definition: relation.h:622
#define Assert(condition)
Definition: c.h:670
#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:437
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:742
Definition: pg_list.h:45

◆ compare_pathkeys()

PathKeysComparison compare_pathkeys ( List keys1,
List keys2 
)

Definition at line 278 of file pathkeys.c.

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

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

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 lfirst(lc)
Definition: pg_list.h:106

◆ compute_parallel_worker()

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

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

3170 {
3171  int parallel_workers = 0;
3172 
3173  /*
3174  * If the user has set the parallel_workers reloption, use that; otherwise
3175  * select a default number of workers.
3176  */
3177  if (rel->rel_parallel_workers != -1)
3178  parallel_workers = rel->rel_parallel_workers;
3179  else
3180  {
3181  /*
3182  * If the number of pages being scanned is insufficient to justify a
3183  * parallel scan, just return zero ... unless it's an inheritance
3184  * child. In that case, we want to generate a parallel path here
3185  * anyway. It might not be worthwhile just for this relation, but
3186  * when combined with all of its inheritance siblings it may well pay
3187  * off.
3188  */
3189  if (rel->reloptkind == RELOPT_BASEREL &&
3190  ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
3191  (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
3192  return 0;
3193 
3194  if (heap_pages >= 0)
3195  {
3196  int heap_parallel_threshold;
3197  int heap_parallel_workers = 1;
3198 
3199  /*
3200  * Select the number of workers based on the log of the size of
3201  * the relation. This probably needs to be a good deal more
3202  * sophisticated, but we need something here for now. Note that
3203  * the upper limit of the min_parallel_table_scan_size GUC is
3204  * chosen to prevent overflow here.
3205  */
3206  heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
3207  while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
3208  {
3209  heap_parallel_workers++;
3210  heap_parallel_threshold *= 3;
3211  if (heap_parallel_threshold > INT_MAX / 3)
3212  break; /* avoid overflow */
3213  }
3214 
3215  parallel_workers = heap_parallel_workers;
3216  }
3217 
3218  if (index_pages >= 0)
3219  {
3220  int index_parallel_workers = 1;
3221  int index_parallel_threshold;
3222 
3223  /* same calculation as for heap_pages above */
3224  index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
3225  while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
3226  {
3227  index_parallel_workers++;
3228  index_parallel_threshold *= 3;
3229  if (index_parallel_threshold > INT_MAX / 3)
3230  break; /* avoid overflow */
3231  }
3232 
3233  if (parallel_workers > 0)
3234  parallel_workers = Min(parallel_workers, index_parallel_workers);
3235  else
3236  parallel_workers = index_parallel_workers;
3237  }
3238  }
3239 
3240  /*
3241  * In no case use more than max_parallel_workers_per_gather workers.
3242  */
3243  parallel_workers = Min(parallel_workers, max_parallel_workers_per_gather);
3244 
3245  return parallel_workers;
3246 }
RelOptKind reloptkind
Definition: relation.h:582
#define Min(x, y)
Definition: c.h:802
uint32 BlockNumber
Definition: block.h:31
int min_parallel_index_scan_size
Definition: allpaths.c:62
int rel_parallel_workers
Definition: relation.h:629
#define Max(x, y)
Definition: c.h:796
int min_parallel_table_scan_size
Definition: allpaths.c:61
int max_parallel_workers_per_gather
Definition: costsize.c:116

◆ convert_subquery_pathkeys()

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, 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:2974
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:619
Var * makeVarFromTargetEntry(Index varno, TargetEntry *tle)
Definition: makefuncs.c:104
Index ec_sortref
Definition: relation.h:871
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:941
bool resjunk
Definition: primnodes.h:1382
#define linitial(l)
Definition: pg_list.h:111
bool pk_nulls_first
Definition: relation.h:942
#define ERROR
Definition: elog.h:43
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:494
void * list_nth(const List *list, int n)
Definition: list.c:410
Relids relids
Definition: relation.h:585
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:613
List * lappend(List *list, void *datum)
Definition: list.c:128
List * ec_opfamilies
Definition: relation.h:860
#define Assert(condition)
Definition: c.h:670
#define lfirst(lc)
Definition: pg_list.h:106
Expr * expr
Definition: primnodes.h:1375
EquivalenceClass * pk_eclass
Definition: relation.h:939
static int list_length(const List *l)
Definition: pg_list.h:89
bool ec_has_volatile
Definition: relation.h:868
Oid pk_opfamily
Definition: relation.h:940
int i
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
List * ec_members
Definition: relation.h:862

◆ create_index_paths()

void create_index_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 232 of file indxpath.c.

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

Referenced by set_plain_rel_pathlist().

233 {
234  List *indexpaths;
235  List *bitindexpaths;
236  List *bitjoinpaths;
237  List *joinorclauses;
238  IndexClauseSet rclauseset;
239  IndexClauseSet jclauseset;
240  IndexClauseSet eclauseset;
241  ListCell *lc;
242 
243  /* Skip the whole mess if no indexes */
244  if (rel->indexlist == NIL)
245  return;
246 
247  /* Bitmap paths are collected and then dealt with at the end */
248  bitindexpaths = bitjoinpaths = joinorclauses = NIL;
249 
250  /* Examine each index in turn */
251  foreach(lc, rel->indexlist)
252  {
254 
255  /* Protect limited-size array in IndexClauseSets */
256  Assert(index->ncolumns <= INDEX_MAX_KEYS);
257 
258  /*
259  * Ignore partial indexes that do not match the query.
260  * (generate_bitmap_or_paths() might be able to do something with
261  * them, but that's of no concern here.)
262  */
263  if (index->indpred != NIL && !index->predOK)
264  continue;
265 
266  /*
267  * Identify the restriction clauses that can match the index.
268  */
269  MemSet(&rclauseset, 0, sizeof(rclauseset));
270  match_restriction_clauses_to_index(rel, index, &rclauseset);
271 
272  /*
273  * Build index paths from the restriction clauses. These will be
274  * non-parameterized paths. Plain paths go directly to add_path(),
275  * bitmap paths are added to bitindexpaths to be handled below.
276  */
277  get_index_paths(root, rel, index, &rclauseset,
278  &bitindexpaths);
279 
280  /*
281  * Identify the join clauses that can match the index. For the moment
282  * we keep them separate from the restriction clauses. Note that this
283  * step finds only "loose" join clauses that have not been merged into
284  * EquivalenceClasses. Also, collect join OR clauses for later.
285  */
286  MemSet(&jclauseset, 0, sizeof(jclauseset));
287  match_join_clauses_to_index(root, rel, index,
288  &jclauseset, &joinorclauses);
289 
290  /*
291  * Look for EquivalenceClasses that can generate joinclauses matching
292  * the index.
293  */
294  MemSet(&eclauseset, 0, sizeof(eclauseset));
295  match_eclass_clauses_to_index(root, index,
296  &eclauseset);
297 
298  /*
299  * If we found any plain or eclass join clauses, build parameterized
300  * index paths using them.
301  */
302  if (jclauseset.nonempty || eclauseset.nonempty)
303  consider_index_join_clauses(root, rel, index,
304  &rclauseset,
305  &jclauseset,
306  &eclauseset,
307  &bitjoinpaths);
308  }
309 
310  /*
311  * Generate BitmapOrPaths for any suitable OR-clauses present in the
312  * restriction list. Add these to bitindexpaths.
313  */
314  indexpaths = generate_bitmap_or_paths(root, rel,
315  rel->baserestrictinfo, NIL);
316  bitindexpaths = list_concat(bitindexpaths, indexpaths);
317 
318  /*
319  * Likewise, generate BitmapOrPaths for any suitable OR-clauses present in
320  * the joinclause list. Add these to bitjoinpaths.
321  */
322  indexpaths = generate_bitmap_or_paths(root, rel,
323  joinorclauses, rel->baserestrictinfo);
324  bitjoinpaths = list_concat(bitjoinpaths, indexpaths);
325 
326  /*
327  * If we found anything usable, generate a BitmapHeapPath for the most
328  * promising combination of restriction bitmap index paths. Note there
329  * will be only one such path no matter how many indexes exist. This
330  * should be sufficient since there's basically only one figure of merit
331  * (total cost) for such a path.
332  */
333  if (bitindexpaths != NIL)
334  {
335  Path *bitmapqual;
336  BitmapHeapPath *bpath;
337 
338  bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
339  bpath = create_bitmap_heap_path(root, rel, bitmapqual,
340  rel->lateral_relids, 1.0, 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:752
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:180
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:420
bool nonempty
Definition: indxpath.c:60
List * baserestrictinfo
Definition: relation.h:645
#define MemSet(start, val, len)
Definition: c.h:853
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:610
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:729
Index relid
Definition: relation.h:613
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:622
#define Assert(condition)
Definition: c.h:670
#define lfirst(lc)
Definition: pg_list.h:106
#define INDEX_MAX_KEYS
bool consider_parallel
Definition: relation.h:593
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:742
void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
Definition: allpaths.c:3137
Definition: pg_list.h:45
BitmapHeapPath * create_bitmap_heap_path(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual, Relids required_outer, double loop_count, int parallel_degree)
Definition: pathnode.c:1075
static void consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, IndexClauseSet *jclauseset, IndexClauseSet *eclauseset, List **bitindexpaths)
Definition: indxpath.c:439

◆ create_partial_bitmap_paths()

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

Definition at line 3137 of file allpaths.c.

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

Referenced by create_index_paths().

3139 {
3140  int parallel_workers;
3141  double pages_fetched;
3142 
3143  /* Compute heap pages for bitmap heap scan */
3144  pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
3145  NULL, NULL);
3146 
3147  parallel_workers = compute_parallel_worker(rel, pages_fetched, -1);
3148 
3149  if (parallel_workers <= 0)
3150  return;
3151 
3152  add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
3153  bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
3154 }
Relids lateral_relids
Definition: relation.h:610
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages)
Definition: allpaths.c:3169
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:760
double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, int loop_count, Cost *cost, double *tuple)
Definition: costsize.c:5170
BitmapHeapPath * create_bitmap_heap_path(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual, Relids required_outer, double loop_count, int parallel_degree)
Definition: pathnode.c:1075

◆ create_tidscan_paths()

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:420
static List * TidQualFromBaseRestrictinfo(RelOptInfo *rel)
Definition: tidpath.c:223
Relids lateral_relids
Definition: relation.h:610
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1180
Definition: pg_list.h:45

◆ eclass_useful_for_merging()

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

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

2439 {
2440  Relids relids;
2441  ListCell *lc;
2442 
2443  Assert(!eclass->ec_merged);
2444 
2445  /*
2446  * Won't generate joinclauses if const or single-member (the latter test
2447  * covers the volatile case too)
2448  */
2449  if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
2450  return false;
2451 
2452  /*
2453  * Note we don't test ec_broken; if we did, we'd need a separate code path
2454  * to look through ec_sources. Checking the members anyway is OK as a
2455  * possibly-overoptimistic heuristic.
2456  */
2457 
2458  /* If specified rel is a child, we must consider the topmost parent rel */
2459  if (IS_OTHER_REL(rel))
2460  {
2462  relids = rel->top_parent_relids;
2463  }
2464  else
2465  relids = rel->relids;
2466 
2467  /* If rel already includes all members of eclass, no point in searching */
2468  if (bms_is_subset(eclass->ec_relids, relids))
2469  return false;
2470 
2471  /* To join, we need a member not in the given rel */
2472  foreach(lc, eclass->ec_members)
2473  {
2474  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
2475 
2476  if (cur_em->em_is_child)
2477  continue; /* ignore children here */
2478 
2479  if (!bms_overlap(cur_em->em_relids, relids))
2480  return true;
2481  }
2482 
2483  return false;
2484 }
#define IS_OTHER_REL(rel)
Definition: relation.h:574
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
Relids ec_relids
Definition: relation.h:865
Relids relids
Definition: relation.h:585
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
Relids em_relids
Definition: relation.h:911
#define Assert(condition)
Definition: c.h:670
#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:874
List * ec_members
Definition: relation.h:862
Relids top_parent_relids
Definition: relation.h:654

◆ expand_indexqual_conditions()

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:561
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:180
Oid * indexcollations
Definition: relation.h:731
Definition: nodes.h:510
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:1835
#define Assert(condition)
Definition: c.h:670
#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:515
Oid * opfamily
Definition: relation.h:732
#define elog
Definition: elog.h:219
bool amsearchnulls
Definition: relation.h:761
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

◆ exprs_known_equal()

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

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

1984 {
1985  ListCell *lc1;
1986 
1987  foreach(lc1, root->eq_classes)
1988  {
1989  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
1990  bool item1member = false;
1991  bool item2member = false;
1992  ListCell *lc2;
1993 
1994  /* Never match to a volatile EC */
1995  if (ec->ec_has_volatile)
1996  continue;
1997 
1998  foreach(lc2, ec->ec_members)
1999  {
2001 
2002  if (em->em_is_child)
2003  continue; /* ignore children here */
2004  if (equal(item1, em->em_expr))
2005  item1member = true;
2006  else if (equal(item2, em->em_expr))
2007  item2member = true;
2008  /* Exit as soon as equality is proven */
2009  if (item1member && item2member)
2010  return true;
2011  }
2012  }
2013  return false;
2014 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2974
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:235
bool ec_has_volatile
Definition: relation.h:868
List * ec_members
Definition: relation.h:862

◆ find_mergeclauses_for_pathkeys()

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:1884
bool outer_is_left
Definition: relation.h:1890
List * lappend(List *list, void *datum)
Definition: list.c:128
#define lfirst(lc)
Definition: pg_list.h:106
EquivalenceClass * pk_eclass
Definition: relation.h:939
EquivalenceClass * left_ec
Definition: relation.h:1883
int i
Definition: pg_list.h:45
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:968

◆ generate_base_implied_equalities()

void generate_base_implied_equalities ( PlannerInfo root)

Definition at line 800 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(), PlannerInfo::simple_rel_array, and PlannerInfo::simple_rel_array_size.

Referenced by query_planner().

801 {
802  ListCell *lc;
803  Index rti;
804 
805  foreach(lc, root->eq_classes)
806  {
808 
809  Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
810  Assert(!ec->ec_broken); /* not yet anyway... */
811 
812  /* Single-member ECs won't generate any deductions */
813  if (list_length(ec->ec_members) <= 1)
814  continue;
815 
816  if (ec->ec_has_const)
818  else
820 
821  /* Recover if we failed to generate required derived clauses */
822  if (ec->ec_broken)
824  }
825 
826  /*
827  * This is also a handy place to mark base rels (which should all exist by
828  * now) with flags showing whether they have pending eclass joins.
829  */
830  for (rti = 1; rti < root->simple_rel_array_size; rti++)
831  {
832  RelOptInfo *brel = root->simple_rel_array[rti];
833 
834  if (brel == NULL)
835  continue;
836 
838  }
839 }
bool has_eclass_joins
Definition: relation.h:651
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:922
static void generate_base_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1014
struct RelOptInfo ** simple_rel_array
Definition: relation.h:179
bool has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
Definition: equivclass.c:2397
int simple_rel_array_size
Definition: relation.h:180
unsigned int Index
Definition: c.h:413
#define Assert(condition)
Definition: c.h:670
#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:845
struct EquivalenceClass * ec_merged
Definition: relation.h:874
List * ec_members
Definition: relation.h:862

◆ generate_gather_paths()

void generate_gather_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 2295 of file allpaths.c.

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

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

2296 {
2297  Path *cheapest_partial_path;
2298  Path *simple_gather_path;
2299  ListCell *lc;
2300 
2301  /* If there are no partial paths, there's nothing to do here. */
2302  if (rel->partial_pathlist == NIL)
2303  return;
2304 
2305  /*
2306  * The output of Gather is always unsorted, so there's only one partial
2307  * path of interest: the cheapest one. That will be the one at the front
2308  * of partial_pathlist because of the way add_partial_path works.
2309  */
2310  cheapest_partial_path = linitial(rel->partial_pathlist);
2311  simple_gather_path = (Path *)
2312  create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
2313  NULL, NULL);
2314  add_path(rel, simple_gather_path);
2315 
2316  /*
2317  * For each useful ordering, we can consider an order-preserving Gather
2318  * Merge.
2319  */
2320  foreach(lc, rel->partial_pathlist)
2321  {
2322  Path *subpath = (Path *) lfirst(lc);
2323  GatherMergePath *path;
2324 
2325  if (subpath->pathkeys == NIL)
2326  continue;
2327 
2328  path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
2329  subpath->pathkeys, NULL, NULL);
2330  add_path(rel, &path->path);
2331  }
2332 }
#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:1744
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:420
List * partial_pathlist
Definition: relation.h:601
#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:1653
List * pathkeys
Definition: relation.h:1056
#define lfirst(lc)
Definition: pg_list.h:106
struct PathTarget * reltarget
Definition: relation.h:596
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:234

◆ generate_implied_equalities_for_column()

List* generate_implied_equalities_for_column ( PlannerInfo root,
RelOptInfo rel,
ec_matches_callback_type  callback,
void *  callback_arg,
Relids  prohibited_rels 
)

Definition at line 2212 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, OidIsValid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, and select_equality_operator().

Referenced by match_eclass_clauses_to_index(), and postgresGetForeignPaths().

2217 {
2218  List *result = NIL;
2219  bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
2220  Relids parent_relids;
2221  ListCell *lc1;
2222 
2223  /* Indexes are available only on base or "other" member relations. */
2224  Assert(IS_SIMPLE_REL(rel));
2225 
2226  /* If it's a child rel, we'll need to know what its parent(s) are */
2227  if (is_child_rel)
2228  parent_relids = find_childrel_parents(root, rel);
2229  else
2230  parent_relids = NULL; /* not used, but keep compiler quiet */
2231 
2232  foreach(lc1, root->eq_classes)
2233  {
2234  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
2235  EquivalenceMember *cur_em;
2236  ListCell *lc2;
2237 
2238  /*
2239  * Won't generate joinclauses if const or single-member (the latter
2240  * test covers the volatile case too)
2241  */
2242  if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
2243  continue;
2244 
2245  /*
2246  * No point in searching if rel not mentioned in eclass (but we can't
2247  * tell that for a child rel).
2248  */
2249  if (!is_child_rel &&
2250  !bms_is_subset(rel->relids, cur_ec->ec_relids))
2251  continue;
2252 
2253  /*
2254  * Scan members, looking for a match to the target column. Note that
2255  * child EC members are considered, but only when they belong to the
2256  * target relation. (Unlike regular members, the same expression
2257  * could be a child member of more than one EC. Therefore, it's
2258  * potentially order-dependent which EC a child relation's target
2259  * column gets matched to. This is annoying but it only happens in
2260  * corner cases, so for now we live with just reporting the first
2261  * match. See also get_eclass_for_sort_expr.)
2262  */
2263  cur_em = NULL;
2264  foreach(lc2, cur_ec->ec_members)
2265  {
2266  cur_em = (EquivalenceMember *) lfirst(lc2);
2267  if (bms_equal(cur_em->em_relids, rel->relids) &&
2268  callback(root, rel, cur_ec, cur_em, callback_arg))
2269  break;
2270  cur_em = NULL;
2271  }
2272 
2273  if (!cur_em)
2274  continue;
2275 
2276  /*
2277  * Found our match. Scan the other EC members and attempt to generate
2278  * joinclauses.
2279  */
2280  foreach(lc2, cur_ec->ec_members)
2281  {
2282  EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
2283  Oid eq_op;
2284  RestrictInfo *rinfo;
2285 
2286  if (other_em->em_is_child)
2287  continue; /* ignore children here */
2288 
2289  /* Make sure it'll be a join to a different rel */
2290  if (other_em == cur_em ||
2291  bms_overlap(other_em->em_relids, rel->relids))
2292  continue;
2293 
2294  /* Forget it if caller doesn't want joins to this rel */
2295  if (bms_overlap(other_em->em_relids, prohibited_rels))
2296  continue;
2297 
2298  /*
2299  * Also, if this is a child rel, avoid generating a useless join
2300  * to its parent rel(s).
2301  */
2302  if (is_child_rel &&
2303  bms_overlap(parent_relids, other_em->em_relids))
2304  continue;
2305 
2306  eq_op = select_equality_operator(cur_ec,
2307  cur_em->em_datatype,
2308  other_em->em_datatype);
2309  if (!OidIsValid(eq_op))
2310  continue;
2311 
2312  /* set parent_ec to mark as redundant with other joinclauses */
2313  rinfo = create_join_clause(root, cur_ec, eq_op,
2314  cur_em, other_em,
2315  cur_ec);
2316 
2317  result = lappend(result, rinfo);
2318  }
2319 
2320  /*
2321  * If somehow we failed to create any join clauses, we might as well
2322  * keep scanning the ECs for another match. But if we did make any,
2323  * we're done, because we don't want to return non-redundant clauses.
2324  */
2325  if (result)
2326  break;
2327  }
2328 
2329  return result;
2330 }
#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:1419
RelOptKind reloptkind
Definition: relation.h:582
unsigned int Oid
Definition: postgres_ext.h:31
#define OidIsValid(objectId)
Definition: c.h:576
#define IS_SIMPLE_REL(rel)
Definition: relation.h:561
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:1384
Relids ec_relids
Definition: relation.h:865
Relids relids
Definition: relation.h:585
List * lappend(List *list, void *datum)
Definition: list.c:128
Relids em_relids
Definition: relation.h:911
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1218
#define Assert(condition)
Definition: c.h:670
#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:862
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:131

◆ generate_join_implied_equalities()

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

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

1075 {
1077  root->eq_classes,
1078  join_relids,
1079  outer_relids,
1080  inner_rel);
1081 }
List * generate_join_implied_equalities_for_ecs(PlannerInfo *root, List *eclasses, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1088
List * eq_classes
Definition: relation.h:235

◆ generate_join_implied_equalities_for_ecs()

List* generate_join_implied_equalities_for_ecs ( PlannerInfo root,
List eclasses,
Relids  join_relids,
Relids  outer_relids,
RelOptInfo inner_rel 
)

Definition at line 1088 of file equivclass.c.

References Assert, bms_is_empty(), bms_overlap(), bms_union(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), IS_OTHER_REL, lfirst, list_concat(), list_length(), NIL, RelOptInfo::relids, and RelOptInfo::top_parent_relids.

Referenced by generate_join_implied_equalities(), and get_joinrel_parampathinfo().

1093 {
1094  List *result = NIL;
1095  Relids inner_relids = inner_rel->relids;
1096  Relids nominal_inner_relids;
1097  Relids nominal_join_relids;
1098  ListCell *lc;
1099 
1100  /* If inner rel is a child, extra setup work is needed */
1101  if (IS_OTHER_REL(inner_rel))
1102  {
1103  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1104 
1105  /* Fetch relid set for the topmost parent rel */
1106  nominal_inner_relids = inner_rel->top_parent_relids;
1107  /* ECs will be marked with the parent's relid, not the child's */
1108  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1109  }
1110  else
1111  {
1112  nominal_inner_relids = inner_relids;
1113  nominal_join_relids = join_relids;
1114  }
1115 
1116  foreach(lc, eclasses)
1117  {
1119  List *sublist = NIL;
1120 
1121  /* ECs containing consts do not need any further enforcement */
1122  if (ec->ec_has_const)
1123  continue;
1124 
1125  /* Single-member ECs won't generate any deductions */
1126  if (list_length(ec->ec_members) <= 1)
1127  continue;
1128 
1129  /* We can quickly ignore any that don't overlap the join, too */
1130  if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1131  continue;
1132 
1133  if (!ec->ec_broken)
1135  ec,
1136  join_relids,
1137  outer_relids,
1138  inner_relids);
1139 
1140  /* Recover if we failed to generate required derived clauses */
1141  if (ec->ec_broken)
1143  ec,
1144  nominal_join_relids,
1145  outer_relids,
1146  nominal_inner_relids,
1147  inner_rel);
1148 
1149  result = list_concat(result, sublist);
1150  }
1151 
1152  return result;
1153 }
#define NIL
Definition: pg_list.h:69
#define IS_OTHER_REL(rel)
Definition: relation.h:574
List * list_concat(List *list1, List *list2)
Definition: list.c:321
static List * generate_join_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec, Relids nominal_join_relids, Relids outer_relids, Relids nominal_inner_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1335
Relids ec_relids
Definition: relation.h:865
Relids relids
Definition: relation.h:585
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1159
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
#define Assert(condition)
Definition: c.h:670
#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:862
Relids top_parent_relids
Definition: relation.h:654

◆ generate_partition_wise_join_paths()

void generate_partition_wise_join_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 3258 of file allpaths.c.

References add_paths_to_append_rel(), Alias::aliasname, RelOptInfo::baserestrictinfo, bms_next_member(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_startup_path, RelOptInfo::cheapest_total_path, check_stack_depth(), RestrictInfo::clause, RangeTblEntry::eref, generate_partition_wise_join_paths(), i, JoinPath::innerjoinpath, MergePath::innersortkeys, IS_DUMMY_REL, IS_JOIN_REL, IsA, RelOptInfo::joininfo, JoinPath::joinrestrictinfo, lappend(), lfirst, list_free(), lnext, mark_dummy_rel(), MergePath::materialize_inner, NIL, nodeTag, RelOptInfo::nparts, JoinPath::outerjoinpath, MergePath::outersortkeys, Path::param_info, Path::parent, PlannerInfo::parse, RelOptInfo::part_rels, Path::pathkeys, RelOptInfo::pathlist, Path::pathtype, ParamPathInfo::ppi_req_outer, print_expr(), print_pathkeys(), RelOptInfo::relids, RelOptInfo::reltarget, RelOptInfo::rows, Path::rows, Query::rtable, set_cheapest(), PlannerInfo::simple_rte_array, Path::startup_cost, subpath(), T_AggPath, T_AppendPath, T_BitmapAndPath, T_BitmapHeapPath, T_BitmapOrPath, T_CteScan, T_ForeignPath, T_FunctionScan, T_GatherPath, T_GroupingSetsPath, T_GroupPath, T_HashPath, T_IndexPath, T_LimitPath, T_LockRowsPath, T_MaterialPath, T_MergeAppendPath, T_MergePath, T_MinMaxAggPath, T_ModifyTablePath, T_NestPath, T_Path, T_ProjectionPath, T_ProjectSetPath, T_RecursiveUnionPath, T_ResultPath, T_SampleScan, T_SeqScan, T_SetOpPath, T_SortPath, T_SubqueryScan, T_SubqueryScanPath, T_TableFuncScan, T_TidPath, T_UniquePath, T_UpperUniquePath, T_ValuesScan, T_WindowAggPath, T_WorkTableScan, Path::total_cost, and PathTarget::width.

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

3259 {
3260  List *live_children = NIL;
3261  int cnt_parts;
3262  int num_parts;
3263  RelOptInfo **part_rels;
3264 
3265  /* Handle only join relations here. */
3266  if (!IS_JOIN_REL(rel))
3267  return;
3268 
3269  /*
3270  * If we've already proven this join is empty, we needn't consider any
3271  * more paths for it.
3272  */
3273  if (IS_DUMMY_REL(rel))
3274  return;
3275 
3276  /*
3277  * We've nothing to do if the relation is not partitioned. An outer join
3278  * relation which had an empty inner relation in every pair will have the
3279  * rest of the partitioning properties set except the child-join
3280  * RelOptInfos. See try_partition_wise_join() for more details.
3281  */
3282  if (rel->nparts <= 0 || rel->part_rels == NULL)
3283  return;
3284 
3285  /* Guard against stack overflow due to overly deep partition hierarchy. */
3287 
3288  num_parts = rel->nparts;
3289  part_rels = rel->part_rels;
3290 
3291  /* Collect non-dummy child-joins. */
3292  for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
3293  {
3294  RelOptInfo *child_rel = part_rels[cnt_parts];
3295 
3296  /* Add partition-wise join paths for partitioned child-joins. */
3297  generate_partition_wise_join_paths(root, child_rel);
3298 
3299  /* Dummy children will not be scanned, so ignore those. */
3300  if (IS_DUMMY_REL(child_rel))
3301  continue;
3302 
3303  set_cheapest(child_rel);
3304 
3305 #ifdef OPTIMIZER_DEBUG
3306  debug_print_rel(root, rel);
3307 #endif
3308 
3309  live_children = lappend(live_children, child_rel);
3310  }
3311 
3312  /* If all child-joins are dummy, parent join is also dummy. */
3313  if (!live_children)
3314  {
3315  mark_dummy_rel(rel);
3316  return;
3317  }
3318 
3319  /* Build additional paths for this rel from child-join paths. */
3320  add_paths_to_append_rel(root, rel, live_children);
3321  list_free(live_children);
3322 }
#define NIL
Definition: pg_list.h:69
#define IS_JOIN_REL(rel)
Definition: relation.h:566
void generate_partition_wise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:3258
#define IS_DUMMY_REL(r)
Definition: relation.h:1275
void check_stack_depth(void)
Definition: postgres.c:3150
int nparts
Definition: relation.h:658
List * lappend(List *list, void *datum)
Definition: list.c:128
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:242
void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1216
struct RelOptInfo ** part_rels
Definition: relation.h:660
void list_free(List *list)
Definition: list.c:1133
static void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
Definition: allpaths.c:1328
Definition: pg_list.h:45

◆ get_cheapest_fractional_path_for_pathkeys()

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

Definition at line 388 of file pathkeys.c.

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

Referenced by build_minmax_path().

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:1056
#define lfirst(lc)
Definition: pg_list.h:106
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:115
#define PATH_REQ_OUTER(path)
Definition: relation.h:1061

◆ get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner ( List paths)

Definition at line 421 of file pathkeys.c.

References bms_is_empty(), lfirst, 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 lfirst(lc)
Definition: pg_list.h:106
bool parallel_safe
Definition: relation.h:1048
#define PATH_REQ_OUTER(path)
Definition: relation.h:1061

◆ get_cheapest_path_for_pathkeys()

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

Definition at line 343 of file pathkeys.c.

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

Referenced by generate_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:69
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:317
List * pathkeys
Definition: relation.h:1056
#define lfirst(lc)
Definition: pg_list.h:106
bool parallel_safe
Definition: relation.h:1048
#define PATH_REQ_OUTER(path)
Definition: relation.h:1061

◆ get_eclass_for_sort_expr()

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

Definition at line 619 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, PlannerInfo::planner_cxt, and pull_varnos().

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

628 {
629  Relids expr_relids;
630  EquivalenceClass *newec;
631  EquivalenceMember *newem;
632  ListCell *lc1;
633  MemoryContext oldcontext;
634 
635  /*
636  * Ensure the expression exposes the correct type and collation.
637  */
638  expr = canonicalize_ec_expression(expr, opcintype, collation);
639 
640  /*
641  * Get the precise set of nullable relids appearing in the expression.
642  */
643  expr_relids = pull_varnos((Node *) expr);
644  nullable_relids = bms_intersect(nullable_relids, expr_relids);
645 
646  /*
647  * Scan through the existing EquivalenceClasses for a match
648  */
649  foreach(lc1, root->eq_classes)
650  {
651  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
652  ListCell *lc2;
653 
654  /*
655  * Never match to a volatile EC, except when we are looking at another
656  * reference to the same volatile SortGroupClause.
657  */
658  if (cur_ec->ec_has_volatile &&
659  (sortref == 0 || sortref != cur_ec->ec_sortref))
660  continue;
661 
662  if (collation != cur_ec->ec_collation)
663  continue;
664  if (!equal(opfamilies, cur_ec->ec_opfamilies))
665  continue;
666 
667  foreach(lc2, cur_ec->ec_members)
668  {
669  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
670 
671  /*
672  * Ignore child members unless they match the request.
673  */
674  if (cur_em->em_is_child &&
675  !bms_equal(cur_em->em_relids, rel))
676  continue;
677 
678  /*
679  * If below an outer join, don't match constants: they're not as
680  * constant as they look.
681  */
682  if (cur_ec->ec_below_outer_join &&
683  cur_em->em_is_const)
684  continue;
685 
686  if (opcintype == cur_em->em_datatype &&
687  equal(expr, cur_em->em_expr))
688  return cur_ec; /* Match! */
689  }
690  }
691 
692  /* No match; does caller want a NULL result? */
693  if (!create_it)
694  return NULL;
695 
696  /*
697  * OK, build a new single-member EC
698  *
699  * Here, we must be sure that we construct the EC in the right context.
700  */
701  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
702 
703  newec = makeNode(EquivalenceClass);
704  newec->ec_opfamilies = list_copy(opfamilies);
705  newec->ec_collation = collation;
706  newec->ec_members = NIL;
707  newec->ec_sources = NIL;
708  newec->ec_derives = NIL;
709  newec->ec_relids = NULL;
710  newec->ec_has_const = false;
712  newec->ec_below_outer_join = false;
713  newec->ec_broken = false;
714  newec->ec_sortref = sortref;
715  newec->ec_min_security = UINT_MAX;
716  newec->ec_max_security = 0;
717  newec->ec_merged = NULL;
718 
719  if (newec->ec_has_volatile && sortref == 0) /* should not happen */
720  elog(ERROR, "volatile EquivalenceClass has no sortref");
721 
722  newem = add_eq_member(newec, copyObject(expr), expr_relids,
723  nullable_relids, false, opcintype);
724 
725  /*
726  * add_eq_member doesn't check for volatile functions, set-returning
727  * functions, aggregates, or window functions, but such could appear in
728  * sort expressions; so we have to check whether its const-marking was
729  * correct.
730  */
731  if (newec->ec_has_const)
732  {
733  if (newec->ec_has_volatile ||
734  expression_returns_set((Node *) expr) ||
735  contain_agg_clause((Node *) expr) ||
736  contain_window_function((Node *) expr))
737  {
738  newec->ec_has_const = false;
739  newem->em_is_const = false;
740  }
741  }
742 
743  root->eq_classes = lappend(root->eq_classes, newec);
744 
745  MemoryContextSwitchTo(oldcontext);
746 
747  return newec;
748 }
#define NIL
Definition: pg_list.h:69
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2974
Index ec_min_security
Definition: relation.h:872
List * ec_derives
Definition: relation.h:864
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:871
Definition: nodes.h:510
bool ec_below_outer_join
Definition: relation.h:869
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:957
Index ec_max_security
Definition: relation.h:873
#define ERROR
Definition: elog.h:43
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:494
List * ec_sources
Definition: relation.h:863
Relids ec_relids
Definition: relation.h:865
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:860
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:252
Relids em_relids
Definition: relation.h:911
#define makeNode(_type_)
Definition: nodes.h:558
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:235
bool ec_has_volatile
Definition: relation.h:868
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:543
MemoryContext planner_cxt
Definition: relation.h:290
#define elog
Definition: elog.h:219
#define copyObject(obj)
Definition: nodes.h:623
struct EquivalenceClass * ec_merged
Definition: relation.h:874
List * ec_members
Definition: relation.h:862
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:131

◆ has_relevant_eclass_joinclause()

bool has_relevant_eclass_joinclause ( PlannerInfo root,
RelOptInfo rel1 
)

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

2398 {
2399  ListCell *lc1;
2400 
2401  foreach(lc1, root->eq_classes)
2402  {
2403  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2404 
2405  /*
2406  * Won't generate joinclauses if single-member (this test covers the
2407  * volatile case too)
2408  */
2409  if (list_length(ec->ec_members) <= 1)
2410  continue;
2411 
2412  /*
2413  * Per the comment in have_relevant_eclass_joinclause, it's sufficient
2414  * to find an EC that mentions both this rel and some other rel.
2415  */
2416  if (bms_overlap(rel1->relids, ec->ec_relids) &&
2417  !bms_is_subset(ec->ec_relids, rel1->relids))
2418  return true;
2419  }
2420 
2421  return false;
2422 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
Relids ec_relids
Definition: relation.h:865
Relids relids
Definition: relation.h:585
#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:862

◆ has_useful_pathkeys()

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:651
#define NIL
Definition: pg_list.h:69
List * query_pathkeys
Definition: relation.h:262
List * joininfo
Definition: relation.h:649

◆ have_dangerous_phv()

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

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

1169 {
1170  ListCell *lc;
1171 
1172  foreach(lc, root->placeholder_list)
1173  {
1174  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1175 
1176  if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1177  continue; /* ignore, could not be a nestloop param */
1178  if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1179  continue; /* ignore, not relevant to this join */
1180  if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
1181  continue; /* safe, it can be eval'd within outerrel */
1182  /* Otherwise, it's potentially unsafe, so reject the join */
1183  return true;
1184  }
1185 
1186  /* OK to perform the join */
1187  return false;
1188 }
Relids ph_eval_at
Definition: relation.h:2154
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

◆ have_join_order_restriction()

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

Definition at line 934 of file joinrels.c.

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

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

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

◆ have_partkey_equi_join()

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

Definition at line 1431 of file joinrels.c.

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

Referenced by build_joinrel_partition_info().

1433 {
1434  PartitionScheme part_scheme = rel1->part_scheme;
1435  ListCell *lc;
1436  int cnt_pks;
1437  bool pk_has_clause[PARTITION_MAX_KEYS];
1438  bool strict_op;
1439 
1440  /*
1441  * This function should be called when the joining relations have same
1442  * partitioning scheme.
1443  */
1444  Assert(rel1->part_scheme == rel2->part_scheme);
1445  Assert(part_scheme);
1446 
1447  memset(pk_has_clause, 0, sizeof(pk_has_clause));
1448  foreach(lc, restrictlist)
1449  {
1450  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1451  OpExpr *opexpr;
1452  Expr *expr1;
1453  Expr *expr2;
1454  int ipk1;
1455  int ipk2;
1456 
1457  /* If processing an outer join, only use its own join clauses. */
1458  if (IS_OUTER_JOIN(jointype) && rinfo->is_pushed_down)
1459  continue;
1460 
1461  /* Skip clauses which can not be used for a join. */
1462  if (!rinfo->can_join)
1463  continue;
1464 
1465  /* Skip clauses which are not equality conditions. */
1466  if (!rinfo->mergeopfamilies && !OidIsValid(rinfo->hashjoinoperator))
1467  continue;
1468 
1469  opexpr = (OpExpr *) rinfo->clause;
1470  Assert(is_opclause(opexpr));
1471 
1472  /*
1473  * The equi-join between partition keys is strict if equi-join between
1474  * at least one partition key is using a strict operator. See
1475  * explanation about outer join reordering identity 3 in
1476  * optimizer/README
1477  */
1478  strict_op = op_strict(opexpr->opno);
1479 
1480  /* Match the operands to the relation. */
1481  if (bms_is_subset(rinfo->left_relids, rel1->relids) &&
1482  bms_is_subset(rinfo->right_relids, rel2->relids))
1483  {
1484  expr1 = linitial(opexpr->args);
1485  expr2 = lsecond(opexpr->args);
1486  }
1487  else if (bms_is_subset(rinfo->left_relids, rel2->relids) &&
1488  bms_is_subset(rinfo->right_relids, rel1->relids))
1489  {
1490  expr1 = lsecond(opexpr->args);
1491  expr2 = linitial(opexpr->args);
1492  }
1493  else
1494  continue;
1495 
1496  /*
1497  * Only clauses referencing the partition keys are useful for
1498  * partition-wise join.
1499  */
1500  ipk1 = match_expr_to_partition_keys(expr1, rel1, strict_op);
1501  if (ipk1 < 0)
1502  continue;
1503  ipk2 = match_expr_to_partition_keys(expr2, rel2, strict_op);
1504  if (ipk2 < 0)
1505  continue;
1506 
1507  /*
1508  * If the clause refers to keys at different ordinal positions, it can
1509  * not be used for partition-wise join.
1510  */
1511  if (ipk1 != ipk2)
1512  continue;
1513 
1514  /*
1515  * The clause allows partition-wise join if only it uses the same
1516  * operator family as that specified by the partition key.
1517  */
1519  {
1520  if (!op_in_opfamily(rinfo->hashjoinoperator,
1521  part_scheme->partopfamily[ipk1]))
1522  continue;
1523  }
1524  else if (!list_member_oid(rinfo->mergeopfamilies,
1525  part_scheme->partopfamily[ipk1]))
1526  continue;
1527 
1528  /* Mark the partition key as having an equi-join clause. */
1529  pk_has_clause[ipk1] = true;
1530  }
1531 
1532  /* Check whether every partition key has an equi-join condition. */
1533  for (cnt_pks = 0; cnt_pks < part_scheme->partnatts; cnt_pks++)
1534  {
1535  if (!pk_has_clause[cnt_pks])
1536  return false;
1537  }
1538 
1539  return true;
1540 }
bool op_in_opfamily(Oid opno, Oid opfamily)
Definition: lsyscache.c:63
bool op_strict(Oid opno)
Definition: lsyscache.c:1281
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:723
#define PARTITION_MAX_KEYS
Relids left_relids
Definition: relation.h:1862
#define OidIsValid(objectId)
Definition: c.h:576
List * mergeopfamilies
Definition: relation.h:1880
#define lsecond(l)
Definition: pg_list.h:116
#define linitial(l)
Definition: pg_list.h:111
#define is_opclause(clause)
Definition: clauses.h:20
bool can_join
Definition: relation.h:1841
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
#define lfirst_node(type, lc)
Definition: pg_list.h:109
static int match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, bool strict_op)
Definition: joinrels.c:1547
Relids relids
Definition: relation.h:585
Expr * clause
Definition: relation.h:1835
#define PARTITION_STRATEGY_HASH
Definition: parsenodes.h:787
bool is_pushed_down
Definition: relation.h:1837
Relids right_relids
Definition: relation.h:1863
bool list_member_oid(const List *list, Oid datum)
Definition: list.c:505
#define Assert(condition)
Definition: c.h:670
Oid hashjoinoperator
Definition: relation.h:1893
PartitionScheme part_scheme
Definition: relation.h:657
Oid opno
Definition: primnodes.h:496
List * args
Definition: primnodes.h:502

◆ have_relevant_eclass_joinclause()

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

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

2345 {
2346  ListCell *lc1;
2347 
2348  foreach(lc1, root->eq_classes)
2349  {
2350  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2351 
2352  /*
2353  * Won't generate joinclauses if single-member (this test covers the
2354  * volatile case too)
2355  */
2356  if (list_length(ec->ec_members) <= 1)
2357  continue;
2358 
2359  /*
2360  * We do not need to examine the individual members of the EC, because
2361  * all that we care about is whether each rel overlaps the relids of
2362  * at least one member, and a test on ec_relids is sufficient to prove
2363  * that. (As with have_relevant_joinclause(), it is not necessary
2364  * that the EC be able to form a joinclause relating exactly the two
2365  * given rels, only that it be able to form a joinclause mentioning
2366  * both, and this will surely be true if both of them overlap
2367  * ec_relids.)
2368  *
2369  * Note we don't test ec_broken; if we did, we'd need a separate code
2370  * path to look through ec_sources. Checking the membership anyway is
2371  * OK as a possibly-overoptimistic heuristic.
2372  *
2373  * We don't test ec_has_const either, even though a const eclass won't
2374  * generate real join clauses. This is because if we had "WHERE a.x =
2375  * b.y and a.x = 42", it is worth considering a join between a and b,
2376  * since the join result is likely to be small even though it'll end
2377  * up being an unqualified nestloop.
2378  */
2379  if (bms_overlap(rel1->relids, ec->ec_relids) &&
2380  bms_overlap(rel2->relids, ec->ec_relids))
2381  return true;
2382  }
2383 
2384  return false;
2385 }
Relids ec_relids
Definition: relation.h:865
Relids relids
Definition: relation.h:585
#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:862

◆ indexcol_is_bool_constant_for_query()

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:645
bool pseudoconstant
Definition: relation.h:1843
Definition: nodes.h:510
RelOptInfo * rel
Definition: relation.h:721
static bool match_boolean_index_clause(Node *clause, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:3306
Expr * clause
Definition: relation.h:1835
#define lfirst(lc)
Definition: pg_list.h:106
Oid * opfamily
Definition: relation.h:732

◆ initialize_mergeclause_eclasses()

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, 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:619
EquivalenceClass * right_ec
Definition: relation.h:1884
unsigned int Oid
Definition: postgres_ext.h:31
List * mergeopfamilies
Definition: relation.h:1880
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:1835
Relids nullable_relids
Definition: relation.h:1859
#define Assert(condition)
Definition: c.h:670
Node * get_rightop(const Expr *clause)
Definition: clauses.c:216
EquivalenceClass * left_ec
Definition: relation.h:1883

◆ is_redundant_derived_clause()

bool is_redundant_derived_clause ( RestrictInfo rinfo,
List clauselist 
)

Definition at line 2494 of file equivclass.c.

References lfirst, and RestrictInfo::parent_ec.

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

2495 {
2496  EquivalenceClass *parent_ec = rinfo->parent_ec;
2497  ListCell *lc;
2498 
2499  /* Fail if it's not a potentially-redundant clause from some EC */
2500  if (parent_ec == NULL)
2501  return false;
2502 
2503  foreach(lc, clauselist)
2504  {
2505  RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
2506 
2507  if (otherrinfo->parent_ec == parent_ec)
2508  return true;
2509  }
2510 
2511  return false;
2512 }
EquivalenceClass * parent_ec
Definition: relation.h:1869
#define lfirst(lc)
Definition: pg_list.h:106

◆ join_search_one_level()

void join_search_one_level ( PlannerInfo root,
int  level 
)

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

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

◆ make_canonical_pathkey()

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:941
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:508
bool pk_nulls_first
Definition: relation.h:942
List * canon_pathkeys
Definition: relation.h:237
List * lappend(List *list, void *datum)
Definition: list.c:128
#define makeNode(_type_)
Definition: nodes.h:558
#define lfirst(lc)
Definition: pg_list.h:106
EquivalenceClass * pk_eclass
Definition: relation.h:939
Oid pk_opfamily
Definition: relation.h:940
MemoryContext planner_cxt
Definition: relation.h:290
struct EquivalenceClass * ec_merged
Definition: relation.h:874

◆ make_inner_pathkeys_for_merge()

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, 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:1884
int pk_strategy
Definition: relation.h:941
bool pk_nulls_first
Definition: relation.h:942
#define ERROR
Definition: elog.h:43
bool outer_is_left
Definition: relation.h:1890
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 lfirst(lc)
Definition: pg_list.h:106
EquivalenceClass * pk_eclass
Definition: relation.h:939
Oid pk_opfamily
Definition: relation.h:940
EquivalenceClass * left_ec
Definition: relation.h:1883
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:968

◆ make_join_rel()

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

Definition at line 669 of file joinrels.c.

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

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

670 {
671  Relids joinrelids;
672  SpecialJoinInfo *sjinfo;
673  bool reversed;
674  SpecialJoinInfo sjinfo_data;
675  RelOptInfo *joinrel;
676  List *restrictlist;
677 
678  /* We should never try to join two overlapping sets of rels. */
679  Assert(!bms_overlap(rel1->relids, rel2->relids));
680 
681  /* Construct Relids set that identifies the joinrel. */
682  joinrelids = bms_union(rel1->relids, rel2->relids);
683 
684  /* Check validity and determine join type. */
685  if (!join_is_legal(root, rel1, rel2, joinrelids,
686  &sjinfo, &reversed))
687  {
688  /* invalid join path */
689  bms_free(joinrelids);
690  return NULL;
691  }
692 
693  /* Swap rels if needed to match the join info. */
694  if (reversed)
695  {
696  RelOptInfo *trel = rel1;
697 
698  rel1 = rel2;
699  rel2 = trel;
700  }
701 
702  /*
703  * If it's a plain inner join, then we won't have found anything in
704  * join_info_list. Make up a SpecialJoinInfo so that selectivity
705  * estimation functions will know what's being joined.
706  */
707  if (sjinfo == NULL)
708  {
709  sjinfo = &sjinfo_data;
710  sjinfo->type = T_SpecialJoinInfo;
711  sjinfo->min_lefthand = rel1->relids;
712  sjinfo->min_righthand = rel2->relids;
713  sjinfo->syn_lefthand = rel1->relids;
714  sjinfo->syn_righthand = rel2->relids;
715  sjinfo->jointype = JOIN_INNER;
716  /* we don't bother trying to make the remaining fields valid */
717  sjinfo->lhs_strict = false;
718  sjinfo->delay_upper_joins = false;
719  sjinfo->semi_can_btree = false;
720  sjinfo->semi_can_hash = false;
721  sjinfo->semi_operators = NIL;
722  sjinfo->semi_rhs_exprs = NIL;
723  }
724 
725  /*
726  * Find or build the join RelOptInfo, and compute the restrictlist that
727  * goes with this particular joining.
728  */
729  joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
730  &restrictlist);
731 
732  /*
733  * If we've already proven this join is empty, we needn't consider any
734  * more paths for it.
735  */
736  if (is_dummy_rel(joinrel))
737  {
738  bms_free(joinrelids);
739  return joinrel;
740  }
741 
742  /* Add paths to the join relation. */
743  populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
744  restrictlist);
745 
746  bms_free(joinrelids);
747 
748  return joinrel;
749 }
#define NIL
Definition: pg_list.h:69
static bool is_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1195
bool semi_can_btree
Definition: relation.h:2015
static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinrels.c:759
Relids min_righthand
Definition: relation.h:2008
NodeTag type
Definition: relation.h:2006
Relids syn_lefthand
Definition: relation.h:2009
Relids syn_righthand
Definition: relation.h:2010
List * semi_rhs_exprs
Definition: relation.h:2018
bool semi_can_hash
Definition: relation.h:2016
static bool join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
Definition: joinrels.c:342
Relids relids
Definition: relation.h:585
bool delay_upper_joins
Definition: relation.h:2013
RelOptInfo * build_join_rel(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, List **restrictlist_ptr)
Definition: relnode.c:480
void bms_free(Bitmapset *a)
Definition: bitmapset.c:201
#define Assert(condition)
Definition: c.h:670
JoinType jointype
Definition: relation.h:2011
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:2017
Definition: pg_list.h:45
Relids min_lefthand
Definition: relation.h:2007

◆ make_one_rel()

RelOptInfo* make_one_rel ( PlannerInfo root,
List joinlist 
)

Definition at line 146 of file allpaths.c.

References PlannerInfo::all_baserels, Assert, bms_add_member(), bms_equal(), make_rel_from_joinlist(), 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().

147 {
148  RelOptInfo *rel;
149  Index rti;
150 
151  /*
152  * Construct the all_baserels Relids set.
153  */
154  root->all_baserels = NULL;
155  for (rti = 1; rti < root->simple_rel_array_size; rti++)
156  {
157  RelOptInfo *brel = root->simple_rel_array[rti];
158 
159  /* there may be empty slots corresponding to non-baserel RTEs */
160  if (brel == NULL)
161  continue;
162 
163  Assert(brel->relid == rti); /* sanity check on array */
164 
165  /* ignore RTEs that are "other rels" */
166  if (brel->reloptkind != RELOPT_BASEREL)
167  continue;
168 
169  root->all_baserels = bms_add_member(root->all_baserels, brel->relid);
170  }
171 
172  /* Mark base rels as to whether we care about fast-start plans */
174 
175  /*
176  * Compute size estimates and consider_parallel flags for each base rel,
177  * then generate access paths.
178  */
179  set_base_rel_sizes(root);
181 
182  /*
183  * Generate access paths for the entire join tree.
184  */
185  rel = make_rel_from_joinlist(root, joinlist);
186 
187  /*
188  * The result should join all and only the query's base rels.
189  */
190  Assert(bms_equal(rel->relids, root->all_baserels));
191 
192  return rel;
193 }
RelOptKind reloptkind
Definition: relation.h:582
static void set_base_rel_sizes(PlannerInfo *root)
Definition: allpaths.c:249
static void set_base_rel_consider_startup(PlannerInfo *root)
Definition: allpaths.c:206
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:2342
Relids relids
Definition: relation.h:585
int simple_rel_array_size
Definition: relation.h:180
Index relid
Definition: relation.h:613
static void set_base_rel_pathlists(PlannerInfo *root)
Definition: allpaths.c:292
unsigned int Index
Definition: c.h:413
#define Assert(condition)
Definition: c.h:670
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

◆ make_pathkeys_for_sortclauses()

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:1196
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:382
#define OidIsValid(objectId)
Definition: c.h:576
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:670
#define lfirst(lc)
Definition: pg_list.h:106
Relids nullable_baserels
Definition: relation.h:204
Definition: pg_list.h:45

◆ mark_dummy_rel()

void mark_dummy_rel ( RelOptInfo rel)

Definition at line 1216 of file joinrels.c.

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

Referenced by generate_partition_wise_join_paths(), and populate_joinrel_with_paths().

1217 {
1218  MemoryContext oldcontext;
1219 
1220  /* Already marked? */
1221  if (is_dummy_rel(rel))
1222  return;
1223 
1224  /* No, so choose correct context to make the dummy path in */
1225  oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1226 
1227  /* Set dummy size estimate */
1228  rel->rows = 0;
1229 
1230  /* Evict any previously chosen paths */
1231  rel->pathlist = NIL;
1232  rel->partial_pathlist = NIL;
1233 
1234  /* Set up the dummy path */
1235  add_path(rel, (Path *) create_append_path(rel, NIL, NULL, 0, NIL));
1236 
1237  /* Set or update cheapest_total_path and related fields */
1238  set_cheapest(rel);
1239 
1240  MemoryContextSwitchTo(oldcontext);
1241 }
#define NIL
Definition: pg_list.h:69
static bool is_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1195
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:420
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
List * partial_pathlist
Definition: relation.h:601
AppendPath * create_append_path(RelOptInfo *rel, List *subpaths, Relids required_outer, int parallel_workers, List *partitioned_rels)
Definition: pathnode.c:1211
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:242
double rows
Definition: relation.h:588
List * pathlist
Definition: relation.h:599
static MemoryContext GetMemoryChunkContext(void *pointer)
Definition: memutils.h:107

◆ match_eclasses_to_foreign_key_col()

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

Definition at line 2030 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, ForeignKeyOptInfo::ref_relid, RangeQueryClause::var, Var::varattno, and Var::varno.

Referenced by match_foreign_keys_to_quals().

2033 {
2034  Index var1varno = fkinfo->con_relid;
2035  AttrNumber var1attno = fkinfo->conkey[colno];
2036  Index var2varno = fkinfo->ref_relid;
2037  AttrNumber var2attno = fkinfo->confkey[colno];
2038  Oid eqop = fkinfo->conpfeqop[colno];
2039  List *opfamilies = NIL; /* compute only if needed */
2040  ListCell *lc1;
2041 
2042  foreach(lc1, root->eq_classes)
2043  {
2044  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2045  bool item1member = false;
2046  bool item2member = false;
2047  ListCell *lc2;
2048 
2049  /* Never match to a volatile EC */
2050  if (ec->ec_has_volatile)
2051  continue;
2052  /* Note: it seems okay to match to "broken" eclasses here */
2053 
2054  foreach(lc2, ec->ec_members)
2055  {
2057  Var *var;
2058 
2059  if (em->em_is_child)
2060  continue; /* ignore children here */
2061 
2062  /* EM must be a Var, possibly with RelabelType */
2063  var = (Var *) em->em_expr;
2064  while (var && IsA(var, RelabelType))
2065  var = (Var *) ((RelabelType *) var)->arg;
2066  if (!(var && IsA(var, Var)))
2067  continue;
2068 
2069  /* Match? */
2070  if (var->varno == var1varno && var->varattno == var1attno)
2071  item1member = true;
2072  else if (var->varno == var2varno && var->varattno == var2attno)
2073  item2member = true;
2074 
2075  /* Have we found both PK and FK column in this EC? */
2076  if (item1member && item2member)
2077  {
2078  /*
2079  * Succeed if eqop matches EC's opfamilies. We could test
2080  * this before scanning the members, but it's probably cheaper
2081  * to test for member matches first.
2082  */
2083  if (opfamilies == NIL) /* compute if we didn't already */
2084  opfamilies = get_mergejoin_opfamilies(eqop);
2085  if (equal(opfamilies, ec->ec_opfamilies))
2086  return ec;
2087  /* Otherwise, done with this EC, move on to the next */
2088  break;
2089  }
2090  }
2091  }
2092  return NULL;
2093 }
#define NIL
Definition: pg_list.h:69
#define IsA(nodeptr, _type_)
Definition: nodes.h:561
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2974
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:787
Index varno
Definition: primnodes.h:166
List * ec_opfamilies
Definition: relation.h:860
AttrNumber conkey[INDEX_MAX_KEYS]
Definition: relation.h:785
unsigned int Index
Definition: c.h:413
#define lfirst(lc)
Definition: pg_list.h:106
List * eq_classes
Definition: relation.h:235
bool ec_has_volatile
Definition: relation.h:868
Definition: pg_list.h:45
AttrNumber confkey[INDEX_MAX_KEYS]
Definition: relation.h:786
int16 AttrNumber
Definition: attnum.h:21
List * ec_members
Definition: relation.h:862

◆ match_index_to_operand()

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, 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:561
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2974
Definition: nodes.h:510
Definition: primnodes.h:163
RelOptInfo * rel
Definition: relation.h:721
#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:613
#define lfirst(lc)
Definition: pg_list.h:106
int i
void * arg
int * indexkeys
Definition: relation.h:730
#define elog
Definition: elog.h:219
List * indexprs
Definition: relation.h:741

◆ pathkeys_contained_in()

◆ process_equivalence()

bool process_equivalence ( PlannerInfo root,
RestrictInfo **  p_restrictinfo,
bool  below_outer_join 
)

Definition at line 114 of file equivclass.c.

References add_eq_member(), NullTest::arg, NullTest::argisrow, 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(), func_strict(), get_leftop(), get_rightop(), IS_NOT_NULL, is_opclause, RestrictInfo::is_pushed_down, lappend(), RestrictInfo::leakproof, RestrictInfo::left_ec, RestrictInfo::left_em, RestrictInfo::left_relids, lfirst, list_concat(), list_delete_ptr(), list_make1, NullTest::location, make_restrictinfo(), makeNode, Max, RestrictInfo::mergeopfamilies, Min, NIL, RestrictInfo::nullable_relids, NullTest::nulltesttype, op_input_types(), RestrictInfo::outer_relids, RestrictInfo::outerjoin_delayed, RestrictInfo::pseudoconstant, RestrictInfo::right_ec, RestrictInfo::right_em, RestrictInfo::right_relids, RestrictInfo::security_level, and set_opfuncid().

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

117 {
118  RestrictInfo *restrictinfo = *p_restrictinfo;
119  Expr *clause = restrictinfo->clause;
120  Oid opno,
121  collation,
122  item1_type,
123  item2_type;
124  Expr *item1;
125  Expr *item2;
126  Relids item1_relids,
127  item2_relids,
128  item1_nullable_relids,
129  item2_nullable_relids;
130  List *opfamilies;
131  EquivalenceClass *ec1,
132  *ec2;
133  EquivalenceMember *em1,
134  *em2;
135  ListCell *lc1;
136 
137  /* Should not already be marked as having generated an eclass */
138  Assert(restrictinfo->left_ec == NULL);
139  Assert(restrictinfo->right_ec == NULL);
140 
141  /* Reject if it is potentially postponable by security considerations */
142  if (restrictinfo->security_level > 0 && !restrictinfo->leakproof)
143  return false;
144 
145  /* Extract info from given clause */
146  Assert(is_opclause(clause));
147  opno = ((OpExpr *) clause)->opno;
148  collation = ((OpExpr *) clause)->inputcollid;
149  item1 = (Expr *) get_leftop(clause);
150  item2 = (Expr *) get_rightop(clause);
151  item1_relids = restrictinfo->left_relids;
152  item2_relids = restrictinfo->right_relids;
153 
154  /*
155  * Ensure both input expressions expose the desired collation (their types
156  * should be OK already); see comments for canonicalize_ec_expression.
157  */
158  item1 = canonicalize_ec_expression(item1,
159  exprType((Node *) item1),
160  collation);
161  item2 = canonicalize_ec_expression(item2,
162  exprType((Node *) item2),
163  collation);
164 
165  /*
166  * Clauses of the form X=X cannot be translated into EquivalenceClasses.
167  * We'd either end up with a single-entry EC, losing the knowledge that
168  * the clause was present at all, or else make an EC with duplicate
169  * entries, causing other issues.
170  */
171  if (equal(item1, item2))
172  {
173  /*
174  * If the operator is strict, then the clause can be treated as just
175  * "X IS NOT NULL". (Since we know we are considering a top-level
176  * qual, we can ignore the difference between FALSE and NULL results.)
177  * It's worth making the conversion because we'll typically get a much
178  * better selectivity estimate than we would for X=X.
179  *
180  * If the operator is not strict, we can't be sure what it will do
181  * with NULLs, so don't attempt to optimize it.
182  */
183  set_opfuncid((OpExpr *) clause);
184  if (func_strict(((OpExpr *) clause)->opfuncid))
185  {
186  NullTest *ntest = makeNode(NullTest);
187 
188  ntest->arg = item1;
189  ntest->nulltesttype = IS_NOT_NULL;
190  ntest->argisrow = false; /* correct even if composite arg */
191  ntest->location = -1;
192 
193  *p_restrictinfo =
194  make_restrictinfo((Expr *) ntest,
195  restrictinfo->is_pushed_down,
196  restrictinfo->outerjoin_delayed,
197  restrictinfo->pseudoconstant,
198  restrictinfo->security_level,
199  NULL,
200  restrictinfo->outer_relids,
201  restrictinfo->nullable_relids);
202  }
203  return false;
204  }
205 
206  /*
207  * If below outer join, check for strictness, else reject.
208  */
209  if (below_outer_join)
210  {
211  if (!bms_is_empty(item1_relids) &&
213  return false; /* LHS is non-strict but not constant */
214  if (!bms_is_empty(item2_relids) &&
216  return false; /* RHS is non-strict but not constant */
217  }
218 
219  /* Calculate nullable-relid sets for each side of the clause */
220  item1_nullable_relids = bms_intersect(item1_relids,
221  restrictinfo->nullable_relids);
222  item2_nullable_relids = bms_intersect(item2_relids,
223  restrictinfo->nullable_relids);
224 
225  /*
226  * We use the declared input types of the operator, not exprType() of the
227  * inputs, as the nominal datatypes for opfamily lookup. This presumes
228  * that btree operators are always registered with amoplefttype and
229  * amoprighttype equal to their declared input types. We will need this
230  * info anyway to build EquivalenceMember nodes, and by extracting it now
231  * we can use type comparisons to short-circuit some equal() tests.
232  */
233  op_input_types(opno, &item1_type, &item2_type);
234 
235  opfamilies = restrictinfo->mergeopfamilies;
236 
237  /*
238  * Sweep through the existing EquivalenceClasses looking for matches to
239  * item1 and item2. These are the possible outcomes:
240  *
241  * 1. We find both in the same EC. The equivalence is already known, so
242  * there's nothing to do.
243  *
244  * 2. We find both in different ECs. Merge the two ECs together.
245  *
246  * 3. We find just one. Add the other to its EC.
247  *
248  * 4. We find neither. Make a new, two-entry EC.
249  *
250  * Note: since all ECs are built through this process or the similar
251  * search in get_eclass_for_sort_expr(), it's impossible that we'd match
252  * an item in more than one existing nonvolatile EC. So it's okay to stop
253  * at the first match.
254  */
255  ec1 = ec2 = NULL;
256  em1 = em2 = NULL;
257  foreach(lc1, root->eq_classes)
258  {
259  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
260  ListCell *lc2;
261 
262  /* Never match to a volatile EC */
263  if (cur_ec->ec_has_volatile)
264  continue;
265 
266  /*
267  * The collation has to match; check this first since it's cheaper
268  * than the opfamily comparison.
269  */
270  if (collation != cur_ec->ec_collation)
271  continue;
272 
273  /*
274  * A "match" requires matching sets of btree opfamilies. Use of
275  * equal() for this test has implications discussed in the comments
276  * for get_mergejoin_opfamilies().
277  */
278  if (!equal(opfamilies, cur_ec->ec_opfamilies))
279  continue;
280 
281  foreach(lc2, cur_ec->ec_members)
282  {
283  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
284 
285  Assert(!cur_em->em_is_child); /* no children yet */
286 
287  /*
288  * If below an outer join, don't match constants: they're not as
289  * constant as they look.
290  */
291  if ((below_outer_join || cur_ec->ec_below_outer_join) &&
292  cur_em->em_is_const)
293  continue;
294 
295  if (!ec1 &&
296  item1_type == cur_em->em_datatype &&
297  equal(item1, cur_em->em_expr))
298  {
299  ec1 = cur_ec;
300  em1 = cur_em;
301  if (ec2)
302  break;
303  }
304 
305  if (!