PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
joinpath.c File Reference
#include "postgres.h"
#include <math.h>
#include "executor/executor.h"
#include "foreign/fdwapi.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/placeholder.h"
#include "optimizer/planmain.h"
#include "optimizer/restrictinfo.h"
#include "utils/lsyscache.h"
#include "utils/typcache.h"
Include dependency graph for joinpath.c:

Go to the source code of this file.

Macros

#define PATH_PARAM_BY_PARENT(path, rel)
 
#define PATH_PARAM_BY_REL_SELF(path, rel)    ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids))
 
#define PATH_PARAM_BY_REL(path, rel)    (PATH_PARAM_BY_REL_SELF(path, rel) || PATH_PARAM_BY_PARENT(path, rel))
 

Functions

static void try_partial_mergejoin_path (PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys, JoinType jointype, JoinPathExtraData *extra)
 
static void sort_inner_and_outer (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
static void match_unsorted_outer (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
static void consider_parallel_nestloop (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
static void consider_parallel_mergejoin (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
 
static void hash_inner_and_outer (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
static Listselect_mergejoin_clauses (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
 
static void generate_mergejoin_paths (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *innerrel, Path *outerpath, JoinType jointype, JoinPathExtraData *extra, bool useallclauses, Path *inner_cheapest_total, List *merge_pathkeys, bool is_partial)
 
void add_paths_to_joinrel (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
 
static bool allow_star_schema_join (PlannerInfo *root, Relids outerrelids, Relids inner_paramrels)
 
static bool paraminfo_get_equal_hashops (PlannerInfo *root, ParamPathInfo *param_info, RelOptInfo *outerrel, RelOptInfo *innerrel, List *ph_lateral_vars, List **param_exprs, List **operators, bool *binary_mode)
 
static Listextract_lateral_vars_from_PHVs (PlannerInfo *root, Relids innerrelids)
 
static Pathget_memoize_path (PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
 
static void try_nestloop_path (PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
 
static void try_partial_nestloop_path (PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
 
static void try_mergejoin_path (PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys, JoinType jointype, JoinPathExtraData *extra, bool is_partial)
 
static void try_hashjoin_path (PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
 
static void try_partial_hashjoin_path (PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra, bool parallel_hash)
 

Variables

set_join_pathlist_hook_type set_join_pathlist_hook = NULL
 

Macro Definition Documentation

◆ PATH_PARAM_BY_PARENT

#define PATH_PARAM_BY_PARENT (   path,
  rel 
)
Value:
((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), \
(rel)->top_parent_relids))
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:582
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1806

Definition at line 40 of file joinpath.c.

◆ PATH_PARAM_BY_REL

#define PATH_PARAM_BY_REL (   path,
  rel 
)     (PATH_PARAM_BY_REL_SELF(path, rel) || PATH_PARAM_BY_PARENT(path, rel))

Definition at line 46 of file joinpath.c.

◆ PATH_PARAM_BY_REL_SELF

#define PATH_PARAM_BY_REL_SELF (   path,
  rel 
)     ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids))

Definition at line 43 of file joinpath.c.

Function Documentation

◆ add_paths_to_joinrel()

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

Definition at line 124 of file joinpath.c.

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

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

Referenced by populate_joinrel_with_paths().

◆ allow_star_schema_join()

static bool allow_star_schema_join ( PlannerInfo root,
Relids  outerrelids,
Relids  inner_paramrels 
)
inlinestatic

Definition at line 363 of file joinpath.c.

366{
367 /*
368 * It's a star-schema case if the outer rel provides some but not all of
369 * the inner rel's parameterization.
370 */
371 return (bms_overlap(inner_paramrels, outerrelids) &&
372 bms_nonempty_difference(inner_paramrels, outerrelids));
373}
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:641

References bms_nonempty_difference(), and bms_overlap().

Referenced by try_nestloop_path().

◆ consider_parallel_mergejoin()

static void consider_parallel_mergejoin ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra,
Path inner_cheapest_total 
)
static

Definition at line 2054 of file joinpath.c.

2061{
2062 ListCell *lc1;
2063
2064 /* generate merge join path for each partial outer path */
2065 foreach(lc1, outerrel->partial_pathlist)
2066 {
2067 Path *outerpath = (Path *) lfirst(lc1);
2068 List *merge_pathkeys;
2069
2070 /*
2071 * Figure out what useful ordering any paths we create will have.
2072 */
2073 merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
2074 outerpath->pathkeys);
2075
2076 generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
2077 extra, false, inner_cheapest_total,
2078 merge_pathkeys, true);
2079 }
2080}
static void generate_mergejoin_paths(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *innerrel, Path *outerpath, JoinType jointype, JoinPathExtraData *extra, bool useallclauses, Path *inner_cheapest_total, List *merge_pathkeys, bool is_partial)
Definition: joinpath.c:1547
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:1295
Definition: pg_list.h:54
List * pathkeys
Definition: pathnodes.h:1802
List * partial_pathlist
Definition: pathnodes.h:927

References build_join_pathkeys(), generate_mergejoin_paths(), lfirst, RelOptInfo::partial_pathlist, Path::pathkeys, and root.

Referenced by match_unsorted_outer().

◆ consider_parallel_nestloop()

static void consider_parallel_nestloop ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 2094 of file joinpath.c.

2100{
2101 JoinType save_jointype = jointype;
2102 Path *inner_cheapest_total = innerrel->cheapest_total_path;
2103 Path *matpath = NULL;
2104 ListCell *lc1;
2105
2106 if (jointype == JOIN_UNIQUE_INNER)
2107 jointype = JOIN_INNER;
2108
2109 /*
2110 * Consider materializing the cheapest inner path, unless: 1) we're doing
2111 * JOIN_UNIQUE_INNER, because in this case we have to unique-ify the
2112 * cheapest inner path, 2) enable_material is off, 3) the cheapest inner
2113 * path is not parallel-safe, 4) the cheapest inner path is parameterized
2114 * by the outer rel, or 5) the cheapest inner path materializes its output
2115 * anyway.
2116 */
2117 if (save_jointype != JOIN_UNIQUE_INNER &&
2118 enable_material && inner_cheapest_total->parallel_safe &&
2119 !PATH_PARAM_BY_REL(inner_cheapest_total, outerrel) &&
2120 !ExecMaterializesOutput(inner_cheapest_total->pathtype))
2121 {
2122 matpath = (Path *)
2123 create_material_path(innerrel, inner_cheapest_total);
2124 Assert(matpath->parallel_safe);
2125 }
2126
2127 foreach(lc1, outerrel->partial_pathlist)
2128 {
2129 Path *outerpath = (Path *) lfirst(lc1);
2130 List *pathkeys;
2131 ListCell *lc2;
2132
2133 /* Figure out what useful ordering any paths we create will have. */
2134 pathkeys = build_join_pathkeys(root, joinrel, jointype,
2135 outerpath->pathkeys);
2136
2137 /*
2138 * Try the cheapest parameterized paths; only those which will produce
2139 * an unparameterized path when joined to this outerrel will survive
2140 * try_partial_nestloop_path. The cheapest unparameterized path is
2141 * also in this list.
2142 */
2143 foreach(lc2, innerrel->cheapest_parameterized_paths)
2144 {
2145 Path *innerpath = (Path *) lfirst(lc2);
2146 Path *mpath;
2147
2148 /* Can't join to an inner path that is not parallel-safe */
2149 if (!innerpath->parallel_safe)
2150 continue;
2151
2152 /*
2153 * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
2154 * cheapest_total_path, and we have to unique-ify it. (We might
2155 * be able to relax this to allow other safe, unparameterized
2156 * inner paths, but right now create_unique_path is not on board
2157 * with that.)
2158 */
2159 if (save_jointype == JOIN_UNIQUE_INNER)
2160 {
2161 if (innerpath != innerrel->cheapest_total_path)
2162 continue;
2163 innerpath = (Path *) create_unique_path(root, innerrel,
2164 innerpath,
2165 extra->sjinfo);
2166 Assert(innerpath);
2167 }
2168
2169 try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
2170 pathkeys, jointype, extra);
2171
2172 /*
2173 * Try generating a memoize path and see if that makes the nested
2174 * loop any cheaper.
2175 */
2176 mpath = get_memoize_path(root, innerrel, outerrel,
2177 innerpath, outerpath, jointype,
2178 extra);
2179 if (mpath != NULL)
2180 try_partial_nestloop_path(root, joinrel, outerpath, mpath,
2181 pathkeys, jointype, extra);
2182 }
2183
2184 /* Also consider materialized form of the cheapest inner path */
2185 if (matpath != NULL)
2186 try_partial_nestloop_path(root, joinrel, outerpath, matpath,
2187 pathkeys, jointype, extra);
2188 }
2189}
bool enable_material
Definition: costsize.c:154
bool ExecMaterializesOutput(NodeTag plantype)
Definition: execAmi.c:636
Assert(PointerIsAligned(start, uint64))
static Path * get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:675
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:46
static void try_partial_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:953
JoinType
Definition: nodes.h:294
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1727
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath)
Definition: pathnode.c:1634
NodeTag pathtype
Definition: pathnodes.h:1762
bool parallel_safe
Definition: pathnodes.h:1791
List * cheapest_parameterized_paths
Definition: pathnodes.h:931
struct Path * cheapest_total_path
Definition: pathnodes.h:929

References Assert(), build_join_pathkeys(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_total_path, create_material_path(), create_unique_path(), enable_material, ExecMaterializesOutput(), get_memoize_path(), JOIN_INNER, JOIN_UNIQUE_INNER, lfirst, Path::parallel_safe, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, Path::pathkeys, Path::pathtype, root, JoinPathExtraData::sjinfo, and try_partial_nestloop_path().

Referenced by match_unsorted_outer().

◆ extract_lateral_vars_from_PHVs()

static List * extract_lateral_vars_from_PHVs ( PlannerInfo root,
Relids  innerrelids 
)
static

Definition at line 584 of file joinpath.c.

585{
586 List *ph_lateral_vars = NIL;
587 ListCell *lc;
588
589 /* Nothing would be found if the query contains no LATERAL RTEs */
590 if (!root->hasLateralRTEs)
591 return NIL;
592
593 /*
594 * No need to consider PHVs that are due to be evaluated at joinrels,
595 * since we do not add Memoize nodes on top of joinrel paths.
596 */
597 if (bms_membership(innerrelids) == BMS_MULTIPLE)
598 return NIL;
599
600 foreach(lc, root->placeholder_list)
601 {
602 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
603 List *vars;
604 ListCell *cell;
605
606 /* PHV is uninteresting if no lateral refs */
607 if (phinfo->ph_lateral == NULL)
608 continue;
609
610 /* PHV is uninteresting if not due to be evaluated at innerrelids */
611 if (!bms_equal(phinfo->ph_eval_at, innerrelids))
612 continue;
613
614 /*
615 * If the PHV does not reference any rels in innerrelids, use its
616 * contained expression as a cache key rather than extracting the
617 * Vars/PHVs from it and using those. This can be beneficial in cases
618 * where the expression results in fewer distinct values to cache
619 * tuples for.
620 */
621 if (!bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
622 innerrelids))
623 {
624 ph_lateral_vars = lappend(ph_lateral_vars, phinfo->ph_var->phexpr);
625 continue;
626 }
627
628 /* Fetch Vars and PHVs of lateral references within PlaceHolderVars */
629 vars = pull_vars_of_level((Node *) phinfo->ph_var->phexpr, 0);
630 foreach(cell, vars)
631 {
632 Node *node = (Node *) lfirst(cell);
633
634 if (IsA(node, Var))
635 {
636 Var *var = (Var *) node;
637
638 Assert(var->varlevelsup == 0);
639
640 if (bms_is_member(var->varno, phinfo->ph_lateral))
641 ph_lateral_vars = lappend(ph_lateral_vars, node);
642 }
643 else if (IsA(node, PlaceHolderVar))
644 {
645 PlaceHolderVar *phv = (PlaceHolderVar *) node;
646
647 Assert(phv->phlevelsup == 0);
648
649 if (bms_is_subset(find_placeholder_info(root, phv)->ph_eval_at,
650 phinfo->ph_lateral))
651 ph_lateral_vars = lappend(ph_lateral_vars, node);
652 }
653 else
654 Assert(false);
655 }
656
658 }
659
660 return ph_lateral_vars;
661}
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:142
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:510
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:781
@ BMS_MULTIPLE
Definition: bitmapset.h:73
List * lappend(List *list, void *datum)
Definition: list.c:339
void list_free(List *list)
Definition: list.c:1546
#define IsA(nodeptr, _type_)
Definition: nodes.h:164
PlaceHolderInfo * find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
Definition: placeholder.c:83
Definition: nodes.h:135
Relids ph_lateral
Definition: pathnodes.h:3227
Relids ph_eval_at
Definition: pathnodes.h:3224
PlaceHolderVar * ph_var
Definition: pathnodes.h:3221
Index phlevelsup
Definition: pathnodes.h:2933
Definition: primnodes.h:262
int varno
Definition: primnodes.h:269
Index varlevelsup
Definition: primnodes.h:294
Definition: regcomp.c:282
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:114
List * pull_vars_of_level(Node *node, int levelsup)
Definition: var.c:339

References Assert(), bms_equal(), bms_is_member(), bms_is_subset(), bms_membership(), BMS_MULTIPLE, bms_overlap(), find_placeholder_info(), IsA, lappend(), lfirst, list_free(), NIL, PlaceHolderInfo::ph_eval_at, PlaceHolderInfo::ph_lateral, PlaceHolderInfo::ph_var, PlaceHolderVar::phlevelsup, pull_varnos(), pull_vars_of_level(), root, Var::varlevelsup, and Var::varno.

Referenced by get_memoize_path().

◆ generate_mergejoin_paths()

static void generate_mergejoin_paths ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo innerrel,
Path outerpath,
JoinType  jointype,
JoinPathExtraData extra,
bool  useallclauses,
Path inner_cheapest_total,
List merge_pathkeys,
bool  is_partial 
)
static

Definition at line 1547 of file joinpath.c.

1557{
1558 List *mergeclauses;
1559 List *innersortkeys;
1560 List *trialsortkeys;
1561 Path *cheapest_startup_inner;
1562 Path *cheapest_total_inner;
1563 JoinType save_jointype = jointype;
1564 int num_sortkeys;
1565 int sortkeycnt;
1566
1567 if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)
1568 jointype = JOIN_INNER;
1569
1570 /* Look for useful mergeclauses (if any) */
1571 mergeclauses =
1573 outerpath->pathkeys,
1574 extra->mergeclause_list);
1575
1576 /*
1577 * Done with this outer path if no chance for a mergejoin.
1578 *
1579 * Special corner case: for "x FULL JOIN y ON true", there will be no join
1580 * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1581 * but since mergejoin is our only join type that supports FULL JOIN
1582 * without any join clauses, it's necessary to generate a clauseless
1583 * mergejoin path instead.
1584 */
1585 if (mergeclauses == NIL)
1586 {
1587 if (jointype == JOIN_FULL)
1588 /* okay to try for mergejoin */ ;
1589 else
1590 return;
1591 }
1592 if (useallclauses &&
1593 list_length(mergeclauses) != list_length(extra->mergeclause_list))
1594 return;
1595
1596 /* Compute the required ordering of the inner path */
1597 innersortkeys = make_inner_pathkeys_for_merge(root,
1598 mergeclauses,
1599 outerpath->pathkeys);
1600
1601 /*
1602 * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1603 * a sort will be needed, only cheapest total cost matters. (But
1604 * try_mergejoin_path will do the right thing if inner_cheapest_total is
1605 * already correctly sorted.)
1606 */
1608 joinrel,
1609 outerpath,
1610 inner_cheapest_total,
1611 merge_pathkeys,
1612 mergeclauses,
1613 NIL,
1614 innersortkeys,
1615 jointype,
1616 extra,
1617 is_partial);
1618
1619 /* Can't do anything else if inner path needs to be unique'd */
1620 if (save_jointype == JOIN_UNIQUE_INNER)
1621 return;
1622
1623 /*
1624 * Look for presorted inner paths that satisfy the innersortkey list ---
1625 * or any truncation thereof, if we are allowed to build a mergejoin using
1626 * a subset of the merge clauses. Here, we consider both cheap startup
1627 * cost and cheap total cost.
1628 *
1629 * Currently we do not consider parameterized inner paths here. This
1630 * interacts with decisions elsewhere that also discriminate against
1631 * mergejoins with parameterized inputs; see comments in
1632 * src/backend/optimizer/README.
1633 *
1634 * As we shorten the sortkey list, we should consider only paths that are
1635 * strictly cheaper than (in particular, not the same as) any path found
1636 * in an earlier iteration. Otherwise we'd be intentionally using fewer
1637 * merge keys than a given path allows (treating the rest as plain
1638 * joinquals), which is unlikely to be a good idea. Also, eliminating
1639 * paths here on the basis of compare_path_costs is a lot cheaper than
1640 * building the mergejoin path only to throw it away.
1641 *
1642 * If inner_cheapest_total is well enough sorted to have not required a
1643 * sort in the path made above, we shouldn't make a duplicate path with
1644 * it, either. We handle that case with the same logic that handles the
1645 * previous consideration, by initializing the variables that track
1646 * cheapest-so-far properly. Note that we do NOT reject
1647 * inner_cheapest_total if we find it matches some shorter set of
1648 * pathkeys. That case corresponds to using fewer mergekeys to avoid
1649 * sorting inner_cheapest_total, whereas we did sort it above, so the
1650 * plans being considered are different.
1651 */
1652 if (pathkeys_contained_in(innersortkeys,
1653 inner_cheapest_total->pathkeys))
1654 {
1655 /* inner_cheapest_total didn't require a sort */
1656 cheapest_startup_inner = inner_cheapest_total;
1657 cheapest_total_inner = inner_cheapest_total;
1658 }
1659 else
1660 {
1661 /* it did require a sort, at least for the full set of keys */
1662 cheapest_startup_inner = NULL;
1663 cheapest_total_inner = NULL;
1664 }
1665 num_sortkeys = list_length(innersortkeys);
1666 if (num_sortkeys > 1 && !useallclauses)
1667 trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */
1668 else
1669 trialsortkeys = innersortkeys; /* won't really truncate */
1670
1671 for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1672 {
1673 Path *innerpath;
1674 List *newclauses = NIL;
1675
1676 /*
1677 * Look for an inner path ordered well enough for the first
1678 * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1679 * destructively, which is why we made a copy...
1680 */
1681 trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
1682 innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1683 trialsortkeys,
1684 NULL,
1685 TOTAL_COST,
1686 is_partial);
1687 if (innerpath != NULL &&
1688 (cheapest_total_inner == NULL ||
1689 compare_path_costs(innerpath, cheapest_total_inner,
1690 TOTAL_COST) < 0))
1691 {
1692 /* Found a cheap (or even-cheaper) sorted path */
1693 /* Select the right mergeclauses, if we didn't already */
1694 if (sortkeycnt < num_sortkeys)
1695 {
1696 newclauses =
1698 mergeclauses,
1699 trialsortkeys);
1700 Assert(newclauses != NIL);
1701 }
1702 else
1703 newclauses = mergeclauses;
1705 joinrel,
1706 outerpath,
1707 innerpath,
1708 merge_pathkeys,
1709 newclauses,
1710 NIL,
1711 NIL,
1712 jointype,
1713 extra,
1714 is_partial);
1715 cheapest_total_inner = innerpath;
1716 }
1717 /* Same on the basis of cheapest startup cost ... */
1718 innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1719 trialsortkeys,
1720 NULL,
1722 is_partial);
1723 if (innerpath != NULL &&
1724 (cheapest_startup_inner == NULL ||
1725 compare_path_costs(innerpath, cheapest_startup_inner,
1726 STARTUP_COST) < 0))
1727 {
1728 /* Found a cheap (or even-cheaper) sorted path */
1729 if (innerpath != cheapest_total_inner)
1730 {
1731 /*
1732 * Avoid rebuilding clause list if we already made one; saves
1733 * memory in big join trees...
1734 */
1735 if (newclauses == NIL)
1736 {
1737 if (sortkeycnt < num_sortkeys)
1738 {
1739 newclauses =
1741 mergeclauses,
1742 trialsortkeys);
1743 Assert(newclauses != NIL);
1744 }
1745 else
1746 newclauses = mergeclauses;
1747 }
1749 joinrel,
1750 outerpath,
1751 innerpath,
1752 merge_pathkeys,
1753 newclauses,
1754 NIL,
1755 NIL,
1756 jointype,
1757 extra,
1758 is_partial);
1759 }
1760 cheapest_startup_inner = innerpath;
1761 }
1762
1763 /*
1764 * Don't consider truncated sortkeys if we need all clauses.
1765 */
1766 if (useallclauses)
1767 break;
1768 }
1769}
static void try_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys, JoinType jointype, JoinPathExtraData *extra, bool is_partial)
Definition: joinpath.c:1032
List * list_copy(const List *oldlist)
Definition: list.c:1573
List * list_truncate(List *list, int new_size)
Definition: list.c:631
Path * get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Definition: pathkeys.c:620
List * make_inner_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
Definition: pathkeys.c:1858
List * find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, List *pathkeys, List *restrictinfos)
Definition: pathkeys.c:1544
List * trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root, List *mergeclauses, List *pathkeys)
Definition: pathkeys.c:1961
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:343
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:69
@ TOTAL_COST
Definition: pathnodes.h:38
@ STARTUP_COST
Definition: pathnodes.h:38
static int list_length(const List *l)
Definition: pg_list.h:152
List * pathlist
Definition: pathnodes.h:925

References Assert(), compare_path_costs(), find_mergeclauses_for_outer_pathkeys(), get_cheapest_path_for_pathkeys(), JOIN_FULL, JOIN_INNER, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, list_copy(), list_length(), list_truncate(), make_inner_pathkeys_for_merge(), JoinPathExtraData::mergeclause_list, NIL, Path::pathkeys, pathkeys_contained_in(), RelOptInfo::pathlist, root, STARTUP_COST, TOTAL_COST, trim_mergeclauses_for_inner_pathkeys(), and try_mergejoin_path().

Referenced by consider_parallel_mergejoin(), and match_unsorted_outer().

◆ get_memoize_path()

static Path * get_memoize_path ( PlannerInfo root,
RelOptInfo innerrel,
RelOptInfo outerrel,
Path inner_path,
Path outer_path,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 675 of file joinpath.c.

679{
680 List *param_exprs;
681 List *hash_operators;
682 ListCell *lc;
683 bool binary_mode;
684 List *ph_lateral_vars;
685
686 /* Obviously not if it's disabled */
687 if (!enable_memoize)
688 return NULL;
689
690 /*
691 * We can safely not bother with all this unless we expect to perform more
692 * than one inner scan. The first scan is always going to be a cache
693 * miss. This would likely fail later anyway based on costs, so this is
694 * really just to save some wasted effort.
695 */
696 if (outer_path->parent->rows < 2)
697 return NULL;
698
699 /*
700 * Extract lateral Vars/PHVs within PlaceHolderVars that are due to be
701 * evaluated at innerrel. These lateral Vars/PHVs could be used as
702 * memoize cache keys.
703 */
704 ph_lateral_vars = extract_lateral_vars_from_PHVs(root, innerrel->relids);
705
706 /*
707 * We can only have a memoize node when there's some kind of cache key,
708 * either parameterized path clauses or lateral Vars. No cache key sounds
709 * more like something a Materialize node might be more useful for.
710 */
711 if ((inner_path->param_info == NULL ||
712 inner_path->param_info->ppi_clauses == NIL) &&
713 innerrel->lateral_vars == NIL &&
714 ph_lateral_vars == NIL)
715 return NULL;
716
717 /*
718 * Currently we don't do this for SEMI and ANTI joins unless they're
719 * marked as inner_unique. This is because nested loop SEMI/ANTI joins
720 * don't scan the inner node to completion, which will mean memoize cannot
721 * mark the cache entry as complete.
722 *
723 * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
724 * = true. Should we? See add_paths_to_joinrel()
725 */
726 if (!extra->inner_unique && (jointype == JOIN_SEMI ||
727 jointype == JOIN_ANTI))
728 return NULL;
729
730 /*
731 * Memoize normally marks cache entries as complete when it runs out of
732 * tuples to read from its subplan. However, with unique joins, Nested
733 * Loop will skip to the next outer tuple after finding the first matching
734 * inner tuple. This means that we may not read the inner side of the
735 * join to completion which leaves no opportunity to mark the cache entry
736 * as complete. To work around that, when the join is unique we
737 * automatically mark cache entries as complete after fetching the first
738 * tuple. This works when the entire join condition is parameterized.
739 * Otherwise, when the parameterization is only a subset of the join
740 * condition, we can't be sure which part of it causes the join to be
741 * unique. This means there are no guarantees that only 1 tuple will be
742 * read. We cannot mark the cache entry as complete after reading the
743 * first tuple without that guarantee. This means the scope of Memoize
744 * node's usefulness is limited to only outer rows that have no join
745 * partner as this is the only case where Nested Loop would exhaust the
746 * inner scan of a unique join. Since the scope is limited to that, we
747 * just don't bother making a memoize path in this case.
748 *
749 * Lateral vars needn't be considered here as they're not considered when
750 * determining if the join is unique.
751 */
752 if (extra->inner_unique)
753 {
754 Bitmapset *ppi_serials;
755
756 if (inner_path->param_info == NULL)
757 return NULL;
758
759 ppi_serials = inner_path->param_info->ppi_serials;
760
762 {
763 if (!bms_is_member(rinfo->rinfo_serial, ppi_serials))
764 return NULL;
765 }
766 }
767
768 /*
769 * We can't use a memoize node if there are volatile functions in the
770 * inner rel's target list or restrict list. A cache hit could reduce the
771 * number of calls to these functions.
772 */
773 if (contain_volatile_functions((Node *) innerrel->reltarget))
774 return NULL;
775
776 foreach(lc, innerrel->baserestrictinfo)
777 {
778 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
779
780 if (contain_volatile_functions((Node *) rinfo))
781 return NULL;
782 }
783
784 /*
785 * Also check the parameterized path restrictinfos for volatile functions.
786 * Indexed functions must be immutable so shouldn't have any volatile
787 * functions, however, with a lateral join the inner scan may not be an
788 * index scan.
789 */
790 if (inner_path->param_info != NULL)
791 {
792 foreach(lc, inner_path->param_info->ppi_clauses)
793 {
794 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
795
796 if (contain_volatile_functions((Node *) rinfo))
797 return NULL;
798 }
799 }
800
801 /* Check if we have hash ops for each parameter to the path */
803 inner_path->param_info,
804 outerrel->top_parent ?
805 outerrel->top_parent : outerrel,
806 innerrel,
807 ph_lateral_vars,
808 &param_exprs,
809 &hash_operators,
810 &binary_mode))
811 {
812 return (Path *) create_memoize_path(root,
813 innerrel,
814 inner_path,
815 param_exprs,
816 hash_operators,
817 extra->inner_unique,
818 binary_mode,
819 outer_path->rows);
820 }
821
822 return NULL;
823}
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:539
bool enable_memoize
Definition: costsize.c:155
static List * extract_lateral_vars_from_PHVs(PlannerInfo *root, Relids innerrelids)
Definition: joinpath.c:584
static bool paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info, RelOptInfo *outerrel, RelOptInfo *innerrel, List *ph_lateral_vars, List **param_exprs, List **operators, bool *binary_mode)
Definition: joinpath.c:439
MemoizePath * create_memoize_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *param_exprs, List *hash_operators, bool singlerow, bool binary_mode, double calls)
Definition: pathnode.c:1667
#define foreach_node(type, var, lst)
Definition: pg_list.h:496
Cardinality rows
Definition: pathnodes.h:1796
List * baserestrictinfo
Definition: pathnodes.h:1012
struct PathTarget * reltarget
Definition: pathnodes.h:920
List * lateral_vars
Definition: pathnodes.h:967

References RelOptInfo::baserestrictinfo, bms_is_member(), contain_volatile_functions(), create_memoize_path(), enable_memoize, extract_lateral_vars_from_PHVs(), foreach_node, JoinPathExtraData::inner_unique, JOIN_ANTI, JOIN_SEMI, RelOptInfo::lateral_vars, lfirst, NIL, paraminfo_get_equal_hashops(), RelOptInfo::relids, RelOptInfo::reltarget, JoinPathExtraData::restrictlist, root, and Path::rows.

Referenced by consider_parallel_nestloop(), and match_unsorted_outer().

◆ hash_inner_and_outer()

static void hash_inner_and_outer ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 2203 of file joinpath.c.

2209{
2210 JoinType save_jointype = jointype;
2211 bool isouterjoin = IS_OUTER_JOIN(jointype);
2212 List *hashclauses;
2213 ListCell *l;
2214
2215 /*
2216 * We need to build only one hashclauses list for any given pair of outer
2217 * and inner relations; all of the hashable clauses will be used as keys.
2218 *
2219 * Scan the join's restrictinfo list to find hashjoinable clauses that are
2220 * usable with this pair of sub-relations.
2221 */
2222 hashclauses = NIL;
2223 foreach(l, extra->restrictlist)
2224 {
2225 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2226
2227 /*
2228 * If processing an outer join, only use its own join clauses for
2229 * hashing. For inner joins we need not be so picky.
2230 */
2231 if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2232 continue;
2233
2234 if (!restrictinfo->can_join ||
2235 restrictinfo->hashjoinoperator == InvalidOid)
2236 continue; /* not hashjoinable */
2237
2238 /*
2239 * Check if clause has the form "outer op inner" or "inner op outer".
2240 */
2241 if (!clause_sides_match_join(restrictinfo, outerrel->relids,
2242 innerrel->relids))
2243 continue; /* no good for these input relations */
2244
2245 /*
2246 * If clause has the form "inner op outer", check if its operator has
2247 * valid commutator. This is necessary because hashclauses in this
2248 * form will get commuted in createplan.c to put the outer var on the
2249 * left (see get_switched_clauses). This probably shouldn't ever
2250 * fail, since hashable operators ought to have commutators, but be
2251 * paranoid.
2252 *
2253 * The clause being hashjoinable indicates that it's an OpExpr.
2254 */
2255 if (!restrictinfo->outer_is_left &&
2256 !OidIsValid(get_commutator(castNode(OpExpr, restrictinfo->clause)->opno)))
2257 continue;
2258
2259 hashclauses = lappend(hashclauses, restrictinfo);
2260 }
2261
2262 /* If we found any usable hashclauses, make paths */
2263 if (hashclauses)
2264 {
2265 /*
2266 * We consider both the cheapest-total-cost and cheapest-startup-cost
2267 * outer paths. There's no need to consider any but the
2268 * cheapest-total-cost inner path, however.
2269 */
2270 Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
2271 Path *cheapest_total_outer = outerrel->cheapest_total_path;
2272 Path *cheapest_total_inner = innerrel->cheapest_total_path;
2273
2274 /*
2275 * If either cheapest-total path is parameterized by the other rel, we
2276 * can't use a hashjoin. (There's no use looking for alternative
2277 * input paths, since these should already be the least-parameterized
2278 * available paths.)
2279 */
2280 if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
2281 PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
2282 return;
2283
2284 /* Unique-ify if need be; we ignore parameterized possibilities */
2285 if (jointype == JOIN_UNIQUE_OUTER)
2286 {
2287 cheapest_total_outer = (Path *)
2288 create_unique_path(root, outerrel,
2289 cheapest_total_outer, extra->sjinfo);
2290 Assert(cheapest_total_outer);
2291 jointype = JOIN_INNER;
2293 joinrel,
2294 cheapest_total_outer,
2295 cheapest_total_inner,
2296 hashclauses,
2297 jointype,
2298 extra);
2299 /* no possibility of cheap startup here */
2300 }
2301 else if (jointype == JOIN_UNIQUE_INNER)
2302 {
2303 cheapest_total_inner = (Path *)
2304 create_unique_path(root, innerrel,
2305 cheapest_total_inner, extra->sjinfo);
2306 Assert(cheapest_total_inner);
2307 jointype = JOIN_INNER;
2309 joinrel,
2310 cheapest_total_outer,
2311 cheapest_total_inner,
2312 hashclauses,
2313 jointype,
2314 extra);
2315 if (cheapest_startup_outer != NULL &&
2316 cheapest_startup_outer != cheapest_total_outer)
2318 joinrel,
2319 cheapest_startup_outer,
2320 cheapest_total_inner,
2321 hashclauses,
2322 jointype,
2323 extra);
2324 }
2325 else
2326 {
2327 /*
2328 * For other jointypes, we consider the cheapest startup outer
2329 * together with the cheapest total inner, and then consider
2330 * pairings of cheapest-total paths including parameterized ones.
2331 * There is no use in generating parameterized paths on the basis
2332 * of possibly cheap startup cost, so this is sufficient.
2333 */
2334 ListCell *lc1;
2335 ListCell *lc2;
2336
2337 if (cheapest_startup_outer != NULL)
2339 joinrel,
2340 cheapest_startup_outer,
2341 cheapest_total_inner,
2342 hashclauses,
2343 jointype,
2344 extra);
2345
2346 foreach(lc1, outerrel->cheapest_parameterized_paths)
2347 {
2348 Path *outerpath = (Path *) lfirst(lc1);
2349
2350 /*
2351 * We cannot use an outer path that is parameterized by the
2352 * inner rel.
2353 */
2354 if (PATH_PARAM_BY_REL(outerpath, innerrel))
2355 continue;
2356
2357 foreach(lc2, innerrel->cheapest_parameterized_paths)
2358 {
2359 Path *innerpath = (Path *) lfirst(lc2);
2360
2361 /*
2362 * We cannot use an inner path that is parameterized by
2363 * the outer rel, either.
2364 */
2365 if (PATH_PARAM_BY_REL(innerpath, outerrel))
2366 continue;
2367
2368 if (outerpath == cheapest_startup_outer &&
2369 innerpath == cheapest_total_inner)
2370 continue; /* already tried it */
2371
2373 joinrel,
2374 outerpath,
2375 innerpath,
2376 hashclauses,
2377 jointype,
2378 extra);
2379 }
2380 }
2381 }
2382
2383 /*
2384 * If the joinrel is parallel-safe, we may be able to consider a
2385 * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER,
2386 * because the outer path will be partial, and therefore we won't be
2387 * able to properly guarantee uniqueness. Also, the resulting path
2388 * must not be parameterized.
2389 */
2390 if (joinrel->consider_parallel &&
2391 save_jointype != JOIN_UNIQUE_OUTER &&
2392 outerrel->partial_pathlist != NIL &&
2393 bms_is_empty(joinrel->lateral_relids))
2394 {
2395 Path *cheapest_partial_outer;
2396 Path *cheapest_partial_inner = NULL;
2397 Path *cheapest_safe_inner = NULL;
2398
2399 cheapest_partial_outer =
2400 (Path *) linitial(outerrel->partial_pathlist);
2401
2402 /*
2403 * Can we use a partial inner plan too, so that we can build a
2404 * shared hash table in parallel? We can't handle
2405 * JOIN_UNIQUE_INNER because we can't guarantee uniqueness.
2406 */
2407 if (innerrel->partial_pathlist != NIL &&
2408 save_jointype != JOIN_UNIQUE_INNER &&
2410 {
2411 cheapest_partial_inner =
2412 (Path *) linitial(innerrel->partial_pathlist);
2414 cheapest_partial_outer,
2415 cheapest_partial_inner,
2416 hashclauses, jointype, extra,
2417 true /* parallel_hash */ );
2418 }
2419
2420 /*
2421 * Normally, given that the joinrel is parallel-safe, the cheapest
2422 * total inner path will also be parallel-safe, but if not, we'll
2423 * have to search for the cheapest safe, unparameterized inner
2424 * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
2425 * inner path. If full, right, right-semi or right-anti join, we
2426 * can't use parallelism (building the hash table in each backend)
2427 * because no one process has all the match bits.
2428 */
2429 if (save_jointype == JOIN_FULL ||
2430 save_jointype == JOIN_RIGHT ||
2431 save_jointype == JOIN_RIGHT_SEMI ||
2432 save_jointype == JOIN_RIGHT_ANTI)
2433 cheapest_safe_inner = NULL;
2434 else if (cheapest_total_inner->parallel_safe)
2435 cheapest_safe_inner = cheapest_total_inner;
2436 else if (save_jointype != JOIN_UNIQUE_INNER)
2437 cheapest_safe_inner =
2439
2440 if (cheapest_safe_inner != NULL)
2442 cheapest_partial_outer,
2443 cheapest_safe_inner,
2444 hashclauses, jointype, extra,
2445 false /* parallel_hash */ );
2446 }
2447 }
2448}
#define bms_is_empty(a)
Definition: bitmapset.h:118
#define OidIsValid(objectId)
Definition: c.h:746
bool enable_parallel_hash
Definition: costsize.c:162
static void try_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1205
static void try_partial_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra, bool parallel_hash)
Definition: joinpath.c:1282
Oid get_commutator(Oid opno)
Definition: lsyscache.c:1649
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:344
#define castNode(_type_, nodeptr)
Definition: nodes.h:182
@ JOIN_RIGHT
Definition: nodes.h:302
@ JOIN_RIGHT_SEMI
Definition: nodes.h:315
@ JOIN_RIGHT_ANTI
Definition: nodes.h:316
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:699
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2857
#define linitial(l)
Definition: pg_list.h:178
#define InvalidOid
Definition: postgres_ext.h:35
static bool clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
Definition: restrictinfo.h:73
bool consider_parallel
Definition: pathnodes.h:914
struct Path * cheapest_startup_path
Definition: pathnodes.h:928
Expr * clause
Definition: pathnodes.h:2700

References Assert(), bms_is_empty, castNode, RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_startup_path, RelOptInfo::cheapest_total_path, RestrictInfo::clause, clause_sides_match_join(), RelOptInfo::consider_parallel, create_unique_path(), enable_parallel_hash, get_cheapest_parallel_safe_total_inner(), get_commutator(), InvalidOid, IS_OUTER_JOIN, JOIN_FULL, JOIN_INNER, JOIN_RIGHT, JOIN_RIGHT_ANTI, JOIN_RIGHT_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, lappend(), RelOptInfo::lateral_relids, lfirst, linitial, NIL, OidIsValid, Path::parallel_safe, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, RelOptInfo::pathlist, RelOptInfo::relids, JoinPathExtraData::restrictlist, RINFO_IS_PUSHED_DOWN, root, JoinPathExtraData::sjinfo, try_hashjoin_path(), and try_partial_hashjoin_path().

Referenced by add_paths_to_joinrel().

◆ match_unsorted_outer()

static void match_unsorted_outer ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1795 of file joinpath.c.

1801{
1802 JoinType save_jointype = jointype;
1803 bool nestjoinOK;
1804 bool useallclauses;
1805 Path *inner_cheapest_total = innerrel->cheapest_total_path;
1806 Path *matpath = NULL;
1807 ListCell *lc1;
1808
1809 /*
1810 * For now we do not support RIGHT_SEMI join in mergejoin or nestloop
1811 * join.
1812 */
1813 if (jointype == JOIN_RIGHT_SEMI)
1814 return;
1815
1816 /*
1817 * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1818 * are doing a right, right-anti or full mergejoin, we must use *all* the
1819 * mergeclauses as join clauses, else we will not have a valid plan.
1820 * (Although these two flags are currently inverses, keep them separate
1821 * for clarity and possible future changes.)
1822 */
1823 switch (jointype)
1824 {
1825 case JOIN_INNER:
1826 case JOIN_LEFT:
1827 case JOIN_SEMI:
1828 case JOIN_ANTI:
1829 nestjoinOK = true;
1830 useallclauses = false;
1831 break;
1832 case JOIN_RIGHT:
1833 case JOIN_RIGHT_ANTI:
1834 case JOIN_FULL:
1835 nestjoinOK = false;
1836 useallclauses = true;
1837 break;
1838 case JOIN_UNIQUE_OUTER:
1839 case JOIN_UNIQUE_INNER:
1840 jointype = JOIN_INNER;
1841 nestjoinOK = true;
1842 useallclauses = false;
1843 break;
1844 default:
1845 elog(ERROR, "unrecognized join type: %d",
1846 (int) jointype);
1847 nestjoinOK = false; /* keep compiler quiet */
1848 useallclauses = false;
1849 break;
1850 }
1851
1852 /*
1853 * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1854 * we will consider it below as a member of cheapest_parameterized_paths,
1855 * but the other possibilities considered in this routine aren't usable.
1856 */
1857 if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1858 inner_cheapest_total = NULL;
1859
1860 /*
1861 * If we need to unique-ify the inner path, we will consider only the
1862 * cheapest-total inner.
1863 */
1864 if (save_jointype == JOIN_UNIQUE_INNER)
1865 {
1866 /* No way to do this with an inner path parameterized by outer rel */
1867 if (inner_cheapest_total == NULL)
1868 return;
1869 inner_cheapest_total = (Path *)
1870 create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1871 Assert(inner_cheapest_total);
1872 }
1873 else if (nestjoinOK)
1874 {
1875 /*
1876 * Consider materializing the cheapest inner path, unless
1877 * enable_material is off or the path in question materializes its
1878 * output anyway.
1879 */
1880 if (enable_material && inner_cheapest_total != NULL &&
1881 !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1882 matpath = (Path *)
1883 create_material_path(innerrel, inner_cheapest_total);
1884 }
1885
1886 foreach(lc1, outerrel->pathlist)
1887 {
1888 Path *outerpath = (Path *) lfirst(lc1);
1889 List *merge_pathkeys;
1890
1891 /*
1892 * We cannot use an outer path that is parameterized by the inner rel.
1893 */
1894 if (PATH_PARAM_BY_REL(outerpath, innerrel))
1895 continue;
1896
1897 /*
1898 * If we need to unique-ify the outer path, it's pointless to consider
1899 * any but the cheapest outer. (XXX we don't consider parameterized
1900 * outers, nor inners, for unique-ified cases. Should we?)
1901 */
1902 if (save_jointype == JOIN_UNIQUE_OUTER)
1903 {
1904 if (outerpath != outerrel->cheapest_total_path)
1905 continue;
1906 outerpath = (Path *) create_unique_path(root, outerrel,
1907 outerpath, extra->sjinfo);
1908 Assert(outerpath);
1909 }
1910
1911 /*
1912 * The result will have this sort order (even if it is implemented as
1913 * a nestloop, and even if some of the mergeclauses are implemented by
1914 * qpquals rather than as true mergeclauses):
1915 */
1916 merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1917 outerpath->pathkeys);
1918
1919 if (save_jointype == JOIN_UNIQUE_INNER)
1920 {
1921 /*
1922 * Consider nestloop join, but only with the unique-ified cheapest
1923 * inner path
1924 */
1926 joinrel,
1927 outerpath,
1928 inner_cheapest_total,
1929 merge_pathkeys,
1930 jointype,
1931 extra);
1932 }
1933 else if (nestjoinOK)
1934 {
1935 /*
1936 * Consider nestloop joins using this outer path and various
1937 * available paths for the inner relation. We consider the
1938 * cheapest-total paths for each available parameterization of the
1939 * inner relation, including the unparameterized case.
1940 */
1941 ListCell *lc2;
1942
1943 foreach(lc2, innerrel->cheapest_parameterized_paths)
1944 {
1945 Path *innerpath = (Path *) lfirst(lc2);
1946 Path *mpath;
1947
1949 joinrel,
1950 outerpath,
1951 innerpath,
1952 merge_pathkeys,
1953 jointype,
1954 extra);
1955
1956 /*
1957 * Try generating a memoize path and see if that makes the
1958 * nested loop any cheaper.
1959 */
1960 mpath = get_memoize_path(root, innerrel, outerrel,
1961 innerpath, outerpath, jointype,
1962 extra);
1963 if (mpath != NULL)
1965 joinrel,
1966 outerpath,
1967 mpath,
1968 merge_pathkeys,
1969 jointype,
1970 extra);
1971 }
1972
1973 /* Also consider materialized form of the cheapest inner path */
1974 if (matpath != NULL)
1976 joinrel,
1977 outerpath,
1978 matpath,
1979 merge_pathkeys,
1980 jointype,
1981 extra);
1982 }
1983
1984 /* Can't do anything else if outer path needs to be unique'd */
1985 if (save_jointype == JOIN_UNIQUE_OUTER)
1986 continue;
1987
1988 /* Can't do anything else if inner rel is parameterized by outer */
1989 if (inner_cheapest_total == NULL)
1990 continue;
1991
1992 /* Generate merge join paths */
1993 generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
1994 save_jointype, extra, useallclauses,
1995 inner_cheapest_total, merge_pathkeys,
1996 false);
1997 }
1998
1999 /*
2000 * Consider partial nestloop and mergejoin plan if outerrel has any
2001 * partial path and the joinrel is parallel-safe. However, we can't
2002 * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
2003 * therefore we won't be able to properly guarantee uniqueness. Nor can
2004 * we handle joins needing lateral rels, since partial paths must not be
2005 * parameterized. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT and
2006 * JOIN_RIGHT_ANTI, because they can produce false null extended rows.
2007 */
2008 if (joinrel->consider_parallel &&
2009 save_jointype != JOIN_UNIQUE_OUTER &&
2010 save_jointype != JOIN_FULL &&
2011 save_jointype != JOIN_RIGHT &&
2012 save_jointype != JOIN_RIGHT_ANTI &&
2013 outerrel->partial_pathlist != NIL &&
2014 bms_is_empty(joinrel->lateral_relids))
2015 {
2016 if (nestjoinOK)
2017 consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
2018 save_jointype, extra);
2019
2020 /*
2021 * If inner_cheapest_total is NULL or non parallel-safe then find the
2022 * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
2023 * can't use any alternative inner path.
2024 */
2025 if (inner_cheapest_total == NULL ||
2026 !inner_cheapest_total->parallel_safe)
2027 {
2028 if (save_jointype == JOIN_UNIQUE_INNER)
2029 return;
2030
2031 inner_cheapest_total = get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
2032 }
2033
2034 if (inner_cheapest_total)
2035 consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
2036 save_jointype, extra,
2037 inner_cheapest_total);
2038 }
2039}
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:226
static void try_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:831
static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:2094
static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
Definition: joinpath.c:2054
@ JOIN_LEFT
Definition: nodes.h:300

References Assert(), bms_is_empty, build_join_pathkeys(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_total_path, RelOptInfo::consider_parallel, consider_parallel_mergejoin(), consider_parallel_nestloop(), create_material_path(), create_unique_path(), elog, enable_material, ERROR, ExecMaterializesOutput(), generate_mergejoin_paths(), get_cheapest_parallel_safe_total_inner(), get_memoize_path(), JOIN_ANTI, JOIN_FULL, JOIN_INNER, JOIN_LEFT, JOIN_RIGHT, JOIN_RIGHT_ANTI, JOIN_RIGHT_SEMI, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, RelOptInfo::lateral_relids, lfirst, NIL, Path::parallel_safe, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, Path::pathkeys, RelOptInfo::pathlist, Path::pathtype, root, JoinPathExtraData::sjinfo, and try_nestloop_path().

Referenced by add_paths_to_joinrel().

◆ paraminfo_get_equal_hashops()

static bool paraminfo_get_equal_hashops ( PlannerInfo root,
ParamPathInfo param_info,
RelOptInfo outerrel,
RelOptInfo innerrel,
List ph_lateral_vars,
List **  param_exprs,
List **  operators,
bool *  binary_mode 
)
static

Definition at line 439 of file joinpath.c.

444{
445 List *lateral_vars;
446 ListCell *lc;
447
448 *param_exprs = NIL;
449 *operators = NIL;
450 *binary_mode = false;
451
452 /* Add join clauses from param_info to the hash key */
453 if (param_info != NULL)
454 {
455 List *clauses = param_info->ppi_clauses;
456
457 foreach(lc, clauses)
458 {
459 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
460 OpExpr *opexpr;
461 Node *expr;
462 Oid hasheqoperator;
463
464 opexpr = (OpExpr *) rinfo->clause;
465
466 /*
467 * Bail if the rinfo is not compatible. We need a join OpExpr
468 * with 2 args.
469 */
470 if (!IsA(opexpr, OpExpr) || list_length(opexpr->args) != 2 ||
471 !clause_sides_match_join(rinfo, outerrel->relids,
472 innerrel->relids))
473 {
474 list_free(*operators);
475 list_free(*param_exprs);
476 return false;
477 }
478
479 if (rinfo->outer_is_left)
480 {
481 expr = (Node *) linitial(opexpr->args);
482 hasheqoperator = rinfo->left_hasheqoperator;
483 }
484 else
485 {
486 expr = (Node *) lsecond(opexpr->args);
487 hasheqoperator = rinfo->right_hasheqoperator;
488 }
489
490 /* can't do memoize if we can't hash the outer type */
491 if (!OidIsValid(hasheqoperator))
492 {
493 list_free(*operators);
494 list_free(*param_exprs);
495 return false;
496 }
497
498 /*
499 * 'expr' may already exist as a parameter from a previous item in
500 * ppi_clauses. No need to include it again, however we'd better
501 * ensure we do switch into binary mode if required. See below.
502 */
503 if (!list_member(*param_exprs, expr))
504 {
505 *operators = lappend_oid(*operators, hasheqoperator);
506 *param_exprs = lappend(*param_exprs, expr);
507 }
508
509 /*
510 * When the join operator is not hashable then it's possible that
511 * the operator will be able to distinguish something that the
512 * hash equality operator could not. For example with floating
513 * point types -0.0 and +0.0 are classed as equal by the hash
514 * function and equality function, but some other operator may be
515 * able to tell those values apart. This means that we must put
516 * memoize into binary comparison mode so that it does bit-by-bit
517 * comparisons rather than a "logical" comparison as it would
518 * using the hash equality operator.
519 */
520 if (!OidIsValid(rinfo->hashjoinoperator))
521 *binary_mode = true;
522 }
523 }
524
525 /* Now add any lateral vars to the cache key too */
526 lateral_vars = list_concat(ph_lateral_vars, innerrel->lateral_vars);
527 foreach(lc, lateral_vars)
528 {
529 Node *expr = (Node *) lfirst(lc);
530 TypeCacheEntry *typentry;
531
532 /* Reject if there are any volatile functions in lateral vars */
534 {
535 list_free(*operators);
536 list_free(*param_exprs);
537 return false;
538 }
539
540 typentry = lookup_type_cache(exprType(expr),
542
543 /* can't use memoize without a valid hash proc and equals operator */
544 if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr))
545 {
546 list_free(*operators);
547 list_free(*param_exprs);
548 return false;
549 }
550
551 /*
552 * 'expr' may already exist as a parameter from the ppi_clauses. No
553 * need to include it again, however we'd better ensure we do switch
554 * into binary mode.
555 */
556 if (!list_member(*param_exprs, expr))
557 {
558 *operators = lappend_oid(*operators, typentry->eq_opr);
559 *param_exprs = lappend(*param_exprs, expr);
560 }
561
562 /*
563 * We must go into binary mode as we don't have too much of an idea of
564 * how these lateral Vars are being used. See comment above when we
565 * set *binary_mode for the non-lateral Var case. This could be
566 * relaxed a bit if we had the RestrictInfos and knew the operators
567 * being used, however for cases like Vars that are arguments to
568 * functions we must operate in binary mode as we don't have
569 * visibility into what the function is doing with the Vars.
570 */
571 *binary_mode = true;
572 }
573
574 /* We're okay to use memoize */
575 return true;
576}
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:81
List * list_concat(List *list1, const List *list2)
Definition: list.c:561
List * lappend_oid(List *list, Oid datum)
Definition: list.c:375
bool list_member(const List *list, const void *datum)
Definition: list.c:661
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
#define lsecond(l)
Definition: pg_list.h:183
unsigned int Oid
Definition: postgres_ext.h:30
List * args
Definition: primnodes.h:853
List * ppi_clauses
Definition: pathnodes.h:1717
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:386
#define TYPECACHE_EQ_OPR
Definition: typcache.h:138
#define TYPECACHE_HASH_PROC
Definition: typcache.h:142

References OpExpr::args, RestrictInfo::clause, clause_sides_match_join(), contain_volatile_functions(), TypeCacheEntry::eq_opr, exprType(), TypeCacheEntry::hash_proc, if(), IsA, lappend(), lappend_oid(), RelOptInfo::lateral_vars, lfirst, linitial, list_concat(), list_free(), list_length(), list_member(), lookup_type_cache(), lsecond, NIL, OidIsValid, ParamPathInfo::ppi_clauses, RelOptInfo::relids, TYPECACHE_EQ_OPR, and TYPECACHE_HASH_PROC.

Referenced by get_memoize_path().

◆ select_mergejoin_clauses()

static List * select_mergejoin_clauses ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
List restrictlist,
JoinType  jointype,
bool *  mergejoin_allowed 
)
static

Definition at line 2473 of file joinpath.c.

2480{
2481 List *result_list = NIL;
2482 bool isouterjoin = IS_OUTER_JOIN(jointype);
2483 bool have_nonmergeable_joinclause = false;
2484 ListCell *l;
2485
2486 /*
2487 * For now we do not support RIGHT_SEMI join in mergejoin: the benefit of
2488 * swapping inputs tends to be small here.
2489 */
2490 if (jointype == JOIN_RIGHT_SEMI)
2491 {
2492 *mergejoin_allowed = false;
2493 return NIL;
2494 }
2495
2496 foreach(l, restrictlist)
2497 {
2498 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2499
2500 /*
2501 * If processing an outer join, only use its own join clauses in the
2502 * merge. For inner joins we can use pushed-down clauses too. (Note:
2503 * we don't set have_nonmergeable_joinclause here because pushed-down
2504 * clauses will become otherquals not joinquals.)
2505 */
2506 if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2507 continue;
2508
2509 /* Check that clause is a mergeable operator clause */
2510 if (!restrictinfo->can_join ||
2511 restrictinfo->mergeopfamilies == NIL)
2512 {
2513 /*
2514 * The executor can handle extra joinquals that are constants, but
2515 * not anything else, when doing right/right-anti/full merge join.
2516 * (The reason to support constants is so we can do FULL JOIN ON
2517 * FALSE.)
2518 */
2519 if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
2520 have_nonmergeable_joinclause = true;
2521 continue; /* not mergejoinable */
2522 }
2523
2524 /*
2525 * Check if clause has the form "outer op inner" or "inner op outer".
2526 */
2527 if (!clause_sides_match_join(restrictinfo, outerrel->relids,
2528 innerrel->relids))
2529 {
2530 have_nonmergeable_joinclause = true;
2531 continue; /* no good for these input relations */
2532 }
2533
2534 /*
2535 * If clause has the form "inner op outer", check if its operator has
2536 * valid commutator. This is necessary because mergejoin clauses in
2537 * this form will get commuted in createplan.c to put the outer var on
2538 * the left (see get_switched_clauses). This probably shouldn't ever
2539 * fail, since mergejoinable operators ought to have commutators, but
2540 * be paranoid.
2541 *
2542 * The clause being mergejoinable indicates that it's an OpExpr.
2543 */
2544 if (!restrictinfo->outer_is_left &&
2545 !OidIsValid(get_commutator(castNode(OpExpr, restrictinfo->clause)->opno)))
2546 {
2547 have_nonmergeable_joinclause = true;
2548 continue;
2549 }
2550
2551 /*
2552 * Insist that each side have a non-redundant eclass. This
2553 * restriction is needed because various bits of the planner expect
2554 * that each clause in a merge be associable with some pathkey in a
2555 * canonical pathkey list, but redundant eclasses can't appear in
2556 * canonical sort orderings. (XXX it might be worth relaxing this,
2557 * but not enough time to address it for 8.3.)
2558 */
2559 update_mergeclause_eclasses(root, restrictinfo);
2560
2561 if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
2562 EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
2563 {
2564 have_nonmergeable_joinclause = true;
2565 continue; /* can't handle redundant eclasses */
2566 }
2567
2568 result_list = lappend(result_list, restrictinfo);
2569 }
2570
2571 /*
2572 * Report whether mergejoin is allowed (see comment at top of function).
2573 */
2574 switch (jointype)
2575 {
2576 case JOIN_RIGHT:
2577 case JOIN_RIGHT_ANTI:
2578 case JOIN_FULL:
2579 *mergejoin_allowed = !have_nonmergeable_joinclause;
2580 break;
2581 default:
2582 *mergejoin_allowed = true;
2583 break;
2584 }
2585
2586 return result_list;
2587}
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1510
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: pathnodes.h:1475

References castNode, RestrictInfo::clause, clause_sides_match_join(), EC_MUST_BE_REDUNDANT, get_commutator(), IS_OUTER_JOIN, IsA, JOIN_FULL, JOIN_RIGHT, JOIN_RIGHT_ANTI, JOIN_RIGHT_SEMI, lappend(), lfirst, NIL, OidIsValid, RelOptInfo::relids, RINFO_IS_PUSHED_DOWN, root, and update_mergeclause_eclasses().

Referenced by add_paths_to_joinrel().

◆ sort_inner_and_outer()

static void sort_inner_and_outer ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1340 of file joinpath.c.

1346{
1347 JoinType save_jointype = jointype;
1348 Path *outer_path;
1349 Path *inner_path;
1350 Path *cheapest_partial_outer = NULL;
1351 Path *cheapest_safe_inner = NULL;
1352 List *all_pathkeys;
1353 ListCell *l;
1354
1355 /* Nothing to do if there are no available mergejoin clauses */
1356 if (extra->mergeclause_list == NIL)
1357 return;
1358
1359 /*
1360 * We only consider the cheapest-total-cost input paths, since we are
1361 * assuming here that a sort is required. We will consider
1362 * cheapest-startup-cost input paths later, and only if they don't need a
1363 * sort.
1364 *
1365 * This function intentionally does not consider parameterized input
1366 * paths, except when the cheapest-total is parameterized. If we did so,
1367 * we'd have a combinatorial explosion of mergejoin paths of dubious
1368 * value. This interacts with decisions elsewhere that also discriminate
1369 * against mergejoins with parameterized inputs; see comments in
1370 * src/backend/optimizer/README.
1371 */
1372 outer_path = outerrel->cheapest_total_path;
1373 inner_path = innerrel->cheapest_total_path;
1374
1375 /*
1376 * If either cheapest-total path is parameterized by the other rel, we
1377 * can't use a mergejoin. (There's no use looking for alternative input
1378 * paths, since these should already be the least-parameterized available
1379 * paths.)
1380 */
1381 if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
1382 PATH_PARAM_BY_REL(inner_path, outerrel))
1383 return;
1384
1385 /*
1386 * If unique-ification is requested, do it and then handle as a plain
1387 * inner join.
1388 */
1389 if (jointype == JOIN_UNIQUE_OUTER)
1390 {
1391 outer_path = (Path *) create_unique_path(root, outerrel,
1392 outer_path, extra->sjinfo);
1393 Assert(outer_path);
1394 jointype = JOIN_INNER;
1395 }
1396 else if (jointype == JOIN_UNIQUE_INNER)
1397 {
1398 inner_path = (Path *) create_unique_path(root, innerrel,
1399 inner_path, extra->sjinfo);
1400 Assert(inner_path);
1401 jointype = JOIN_INNER;
1402 }
1403
1404 /*
1405 * If the joinrel is parallel-safe, we may be able to consider a partial
1406 * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
1407 * outer path will be partial, and therefore we won't be able to properly
1408 * guarantee uniqueness. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT
1409 * and JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1410 * Also, the resulting path must not be parameterized.
1411 */
1412 if (joinrel->consider_parallel &&
1413 save_jointype != JOIN_UNIQUE_OUTER &&
1414 save_jointype != JOIN_FULL &&
1415 save_jointype != JOIN_RIGHT &&
1416 save_jointype != JOIN_RIGHT_ANTI &&
1417 outerrel->partial_pathlist != NIL &&
1418 bms_is_empty(joinrel->lateral_relids))
1419 {
1420 cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
1421
1422 if (inner_path->parallel_safe)
1423 cheapest_safe_inner = inner_path;
1424 else if (save_jointype != JOIN_UNIQUE_INNER)
1425 cheapest_safe_inner =
1427 }
1428
1429 /*
1430 * Each possible ordering of the available mergejoin clauses will generate
1431 * a differently-sorted result path at essentially the same cost. We have
1432 * no basis for choosing one over another at this level of joining, but
1433 * some sort orders may be more useful than others for higher-level
1434 * mergejoins, so it's worth considering multiple orderings.
1435 *
1436 * Actually, it's not quite true that every mergeclause ordering will
1437 * generate a different path order, because some of the clauses may be
1438 * partially redundant (refer to the same EquivalenceClasses). Therefore,
1439 * what we do is convert the mergeclause list to a list of canonical
1440 * pathkeys, and then consider different orderings of the pathkeys.
1441 *
1442 * Generating a path for *every* permutation of the pathkeys doesn't seem
1443 * like a winning strategy; the cost in planning time is too high. For
1444 * now, we generate one path for each pathkey, listing that pathkey first
1445 * and the rest in random order. This should allow at least a one-clause
1446 * mergejoin without re-sorting against any other possible mergejoin
1447 * partner path. But if we've not guessed the right ordering of secondary
1448 * keys, we may end up evaluating clauses as qpquals when they could have
1449 * been done as mergeclauses. (In practice, it's rare that there's more
1450 * than two or three mergeclauses, so expending a huge amount of thought
1451 * on that is probably not worth it.)
1452 *
1453 * The pathkey order returned by select_outer_pathkeys_for_merge() has
1454 * some heuristics behind it (see that function), so be sure to try it
1455 * exactly as-is as well as making variants.
1456 */
1458 extra->mergeclause_list,
1459 joinrel);
1460
1461 foreach(l, all_pathkeys)
1462 {
1463 PathKey *front_pathkey = (PathKey *) lfirst(l);
1464 List *cur_mergeclauses;
1465 List *outerkeys;
1466 List *innerkeys;
1467 List *merge_pathkeys;
1468
1469 /* Make a pathkey list with this guy first */
1470 if (l != list_head(all_pathkeys))
1471 outerkeys = lcons(front_pathkey,
1472 list_delete_nth_cell(list_copy(all_pathkeys),
1474 else
1475 outerkeys = all_pathkeys; /* no work at first one... */
1476
1477 /* Sort the mergeclauses into the corresponding ordering */
1478 cur_mergeclauses =
1480 outerkeys,
1481 extra->mergeclause_list);
1482
1483 /* Should have used them all... */
1484 Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
1485
1486 /* Build sort pathkeys for the inner side */
1488 cur_mergeclauses,
1489 outerkeys);
1490
1491 /* Build pathkeys representing output sort order */
1492 merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1493 outerkeys);
1494
1495 /*
1496 * And now we can make the path.
1497 *
1498 * Note: it's possible that the cheapest paths will already be sorted
1499 * properly. try_mergejoin_path will detect that case and suppress an
1500 * explicit sort step, so we needn't do so here.
1501 */
1503 joinrel,
1504 outer_path,
1505 inner_path,
1506 merge_pathkeys,
1507 cur_mergeclauses,
1508 outerkeys,
1509 innerkeys,
1510 jointype,
1511 extra,
1512 false);
1513
1514 /*
1515 * If we have partial outer and parallel safe inner path then try
1516 * partial mergejoin path.
1517 */
1518 if (cheapest_partial_outer && cheapest_safe_inner)
1520 joinrel,
1521 cheapest_partial_outer,
1522 cheapest_safe_inner,
1523 merge_pathkeys,
1524 cur_mergeclauses,
1525 outerkeys,
1526 innerkeys,
1527 jointype,
1528 extra);
1529 }
1530}
static void try_partial_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1138
List * list_delete_nth_cell(List *list, int n)
Definition: list.c:767
List * lcons(void *datum, List *list)
Definition: list.c:495
List * select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
Definition: pathkeys.c:1659
#define foreach_current_index(var_or_cell)
Definition: pg_list.h:403
static ListCell * list_head(const List *l)
Definition: pg_list.h:128

References Assert(), bms_is_empty, build_join_pathkeys(), RelOptInfo::cheapest_total_path, RelOptInfo::consider_parallel, create_unique_path(), find_mergeclauses_for_outer_pathkeys(), foreach_current_index, get_cheapest_parallel_safe_total_inner(), JOIN_FULL, JOIN_INNER, JOIN_RIGHT, JOIN_RIGHT_ANTI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, RelOptInfo::lateral_relids, lcons(), lfirst, linitial, list_copy(), list_delete_nth_cell(), list_head(), list_length(), make_inner_pathkeys_for_merge(), JoinPathExtraData::mergeclause_list, NIL, Path::parallel_safe, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, RelOptInfo::pathlist, root, select_outer_pathkeys_for_merge(), JoinPathExtraData::sjinfo, try_mergejoin_path(), and try_partial_mergejoin_path().

Referenced by add_paths_to_joinrel().

◆ try_hashjoin_path()

static void try_hashjoin_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List hashclauses,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1205 of file joinpath.c.

1212{
1213 Relids required_outer;
1214 JoinCostWorkspace workspace;
1215
1216 /*
1217 * If we are forming an outer join at this join, it's nonsensical to use
1218 * an input path that uses the outer join as part of its parameterization.
1219 * (This can happen despite our join order restrictions, since those apply
1220 * to what is in an input relation not what its parameters are.)
1221 */
1222 if (extra->sjinfo->ojrelid != 0 &&
1223 (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) ||
1224 bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path))))
1225 return;
1226
1227 /*
1228 * Check to see if proposed path is still parameterized, and reject if the
1229 * parameterization wouldn't be sensible.
1230 */
1231 required_outer = calc_non_nestloop_required_outer(outer_path,
1232 inner_path);
1233 if (required_outer &&
1234 !bms_overlap(required_outer, extra->param_source_rels))
1235 {
1236 /* Waste no memory when we reject a path here */
1237 bms_free(required_outer);
1238 return;
1239 }
1240
1241 /*
1242 * See comments in try_nestloop_path(). Also note that hashjoin paths
1243 * never have any output pathkeys, per comments in create_hashjoin_path.
1244 */
1245 initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1246 outer_path, inner_path, extra, false);
1247
1248 if (add_path_precheck(joinrel, workspace.disabled_nodes,
1249 workspace.startup_cost, workspace.total_cost,
1250 NIL, required_outer))
1251 {
1252 add_path(joinrel, (Path *)
1254 joinrel,
1255 jointype,
1256 &workspace,
1257 extra,
1258 outer_path,
1259 inner_path,
1260 false, /* parallel_hash */
1261 extra->restrictlist,
1262 required_outer,
1263 hashclauses));
1264 }
1265 else
1266 {
1267 /* Waste no memory when we reject a path here */
1268 bms_free(required_outer);
1269 }
1270}
void bms_free(Bitmapset *a)
Definition: bitmapset.c:239
void initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *hashclauses, Path *outer_path, Path *inner_path, JoinPathExtraData *extra, bool parallel_hash)
Definition: costsize.c:4159
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:2483
HashPath * create_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, bool parallel_hash, List *restrict_clauses, Relids required_outer, List *hashclauses)
Definition: pathnode.c:2697
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:461
bool add_path_precheck(RelOptInfo *parent_rel, int disabled_nodes, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:688

References add_path(), add_path_precheck(), bms_free(), bms_is_member(), bms_overlap(), calc_non_nestloop_required_outer(), create_hashjoin_path(), JoinCostWorkspace::disabled_nodes, initial_cost_hashjoin(), NIL, SpecialJoinInfo::ojrelid, JoinPathExtraData::param_source_rels, PATH_REQ_OUTER, JoinPathExtraData::restrictlist, root, JoinPathExtraData::sjinfo, JoinCostWorkspace::startup_cost, and JoinCostWorkspace::total_cost.

Referenced by hash_inner_and_outer().

◆ try_mergejoin_path()

static void try_mergejoin_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List pathkeys,
List mergeclauses,
List outersortkeys,
List innersortkeys,
JoinType  jointype,
JoinPathExtraData extra,
bool  is_partial 
)
static

Definition at line 1032 of file joinpath.c.

1043{
1044 Relids required_outer;
1045 JoinCostWorkspace workspace;
1046
1047 if (is_partial)
1048 {
1050 joinrel,
1051 outer_path,
1052 inner_path,
1053 pathkeys,
1054 mergeclauses,
1055 outersortkeys,
1056 innersortkeys,
1057 jointype,
1058 extra);
1059 return;
1060 }
1061
1062 /*
1063 * If we are forming an outer join at this join, it's nonsensical to use
1064 * an input path that uses the outer join as part of its parameterization.
1065 * (This can happen despite our join order restrictions, since those apply
1066 * to what is in an input relation not what its parameters are.)
1067 */
1068 if (extra->sjinfo->ojrelid != 0 &&
1069 (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) ||
1070 bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path))))
1071 return;
1072
1073 /*
1074 * Check to see if proposed path is still parameterized, and reject if the
1075 * parameterization wouldn't be sensible.
1076 */
1077 required_outer = calc_non_nestloop_required_outer(outer_path,
1078 inner_path);
1079 if (required_outer &&
1080 !bms_overlap(required_outer, extra->param_source_rels))
1081 {
1082 /* Waste no memory when we reject a path here */
1083 bms_free(required_outer);
1084 return;
1085 }
1086
1087 /*
1088 * If the given paths are already well enough ordered, we can skip doing
1089 * an explicit sort.
1090 */
1091 if (outersortkeys &&
1092 pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
1093 outersortkeys = NIL;
1094 if (innersortkeys &&
1095 pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
1096 innersortkeys = NIL;
1097
1098 /*
1099 * See comments in try_nestloop_path().
1100 */
1101 initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
1102 outer_path, inner_path,
1103 outersortkeys, innersortkeys,
1104 extra);
1105
1106 if (add_path_precheck(joinrel, workspace.disabled_nodes,
1107 workspace.startup_cost, workspace.total_cost,
1108 pathkeys, required_outer))
1109 {
1110 add_path(joinrel, (Path *)
1112 joinrel,
1113 jointype,
1114 &workspace,
1115 extra,
1116 outer_path,
1117 inner_path,
1118 extra->restrictlist,
1119 pathkeys,
1120 required_outer,
1121 mergeclauses,
1122 outersortkeys,
1123 innersortkeys));
1124 }
1125 else
1126 {
1127 /* Waste no memory when we reject a path here */
1128 bms_free(required_outer);
1129 }
1130}
void initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *mergeclauses, Path *outer_path, Path *inner_path, List *outersortkeys, List *innersortkeys, JoinPathExtraData *extra)
Definition: costsize.c:3551
MergePath * create_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, List *restrict_clauses, List *pathkeys, Relids required_outer, List *mergeclauses, List *outersortkeys, List *innersortkeys)
Definition: pathnode.c:2631

References add_path(), add_path_precheck(), bms_free(), bms_is_member(), bms_overlap(), calc_non_nestloop_required_outer(), create_mergejoin_path(), JoinCostWorkspace::disabled_nodes, initial_cost_mergejoin(), NIL, SpecialJoinInfo::ojrelid, JoinPathExtraData::param_source_rels, PATH_REQ_OUTER, Path::pathkeys, pathkeys_contained_in(), JoinPathExtraData::restrictlist, root, JoinPathExtraData::sjinfo, JoinCostWorkspace::startup_cost, JoinCostWorkspace::total_cost, and try_partial_mergejoin_path().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

◆ try_nestloop_path()

static void try_nestloop_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List pathkeys,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 831 of file joinpath.c.

838{
839 Relids required_outer;
840 JoinCostWorkspace workspace;
841 RelOptInfo *innerrel = inner_path->parent;
842 RelOptInfo *outerrel = outer_path->parent;
843 Relids innerrelids;
844 Relids outerrelids;
845 Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
846 Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
847
848 /*
849 * If we are forming an outer join at this join, it's nonsensical to use
850 * an input path that uses the outer join as part of its parameterization.
851 * (This can happen despite our join order restrictions, since those apply
852 * to what is in an input relation not what its parameters are.)
853 */
854 if (extra->sjinfo->ojrelid != 0 &&
855 (bms_is_member(extra->sjinfo->ojrelid, inner_paramrels) ||
856 bms_is_member(extra->sjinfo->ojrelid, outer_paramrels)))
857 return;
858
859 /*
860 * Any parameterization of the input paths refers to topmost parents of
861 * the relevant relations, because reparameterize_path_by_child() hasn't
862 * been called yet. So we must consider topmost parents of the relations
863 * being joined, too, while determining parameterization of the result and
864 * checking for disallowed parameterization cases.
865 */
866 if (innerrel->top_parent_relids)
867 innerrelids = innerrel->top_parent_relids;
868 else
869 innerrelids = innerrel->relids;
870
871 if (outerrel->top_parent_relids)
872 outerrelids = outerrel->top_parent_relids;
873 else
874 outerrelids = outerrel->relids;
875
876 /*
877 * Check to see if proposed path is still parameterized, and reject if the
878 * parameterization wouldn't be sensible --- unless allow_star_schema_join
879 * says to allow it anyway. Also, we must reject if have_dangerous_phv
880 * doesn't like the look of it, which could only happen if the nestloop is
881 * still parameterized.
882 */
883 required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels,
884 innerrelids, inner_paramrels);
885 if (required_outer &&
886 ((!bms_overlap(required_outer, extra->param_source_rels) &&
887 !allow_star_schema_join(root, outerrelids, inner_paramrels)) ||
888 have_dangerous_phv(root, outerrelids, inner_paramrels)))
889 {
890 /* Waste no memory when we reject a path here */
891 bms_free(required_outer);
892 return;
893 }
894
895 /* If we got past that, we shouldn't have any unsafe outer-join refs */
896 Assert(!have_unsafe_outer_join_ref(root, outerrelids, inner_paramrels));
897
898 /*
899 * If the inner path is parameterized, it is parameterized by the topmost
900 * parent of the outer rel, not the outer rel itself. We will need to
901 * translate the parameterization, if this path is chosen, during
902 * create_plan(). Here we just check whether we will be able to perform
903 * the translation, and if not avoid creating a nestloop path.
904 */
905 if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent) &&
906 !path_is_reparameterizable_by_child(inner_path, outer_path->parent))
907 {
908 bms_free(required_outer);
909 return;
910 }
911
912 /*
913 * Do a precheck to quickly eliminate obviously-inferior paths. We
914 * calculate a cheap lower bound on the path's cost and then use
915 * add_path_precheck() to see if the path is clearly going to be dominated
916 * by some existing path for the joinrel. If not, do the full pushup with
917 * creating a fully valid path structure and submitting it to add_path().
918 * The latter two steps are expensive enough to make this two-phase
919 * methodology worthwhile.
920 */
921 initial_cost_nestloop(root, &workspace, jointype,
922 outer_path, inner_path, extra);
923
924 if (add_path_precheck(joinrel, workspace.disabled_nodes,
925 workspace.startup_cost, workspace.total_cost,
926 pathkeys, required_outer))
927 {
928 add_path(joinrel, (Path *)
930 joinrel,
931 jointype,
932 &workspace,
933 extra,
934 outer_path,
935 inner_path,
936 extra->restrictlist,
937 pathkeys,
938 required_outer));
939 }
940 else
941 {
942 /* Waste no memory when we reject a path here */
943 bms_free(required_outer);
944 }
945}
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:3267
#define PATH_PARAM_BY_PARENT(path, rel)
Definition: joinpath.c:40
static bool allow_star_schema_join(PlannerInfo *root, Relids outerrelids, Relids inner_paramrels)
Definition: joinpath.c:363
bool have_dangerous_phv(PlannerInfo *root, Relids outer_relids, Relids inner_params)
Definition: joinrels.c:1308
bool path_is_reparameterizable_by_child(Path *path, RelOptInfo *child_rel)
Definition: pathnode.c:4565
Relids calc_nestloop_required_outer(Relids outerrelids, Relids outer_paramrels, Relids innerrelids, Relids inner_paramrels)
Definition: pathnode.c:2456
NestPath * create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, List *restrict_clauses, List *pathkeys, Relids required_outer)
Definition: pathnode.c:2535

References add_path(), add_path_precheck(), allow_star_schema_join(), Assert(), bms_free(), bms_is_member(), bms_overlap(), calc_nestloop_required_outer(), create_nestloop_path(), JoinCostWorkspace::disabled_nodes, have_dangerous_phv(), initial_cost_nestloop(), SpecialJoinInfo::ojrelid, JoinPathExtraData::param_source_rels, path_is_reparameterizable_by_child(), PATH_PARAM_BY_PARENT, PATH_REQ_OUTER, RelOptInfo::relids, JoinPathExtraData::restrictlist, root, JoinPathExtraData::sjinfo, JoinCostWorkspace::startup_cost, RelOptInfo::top_parent_relids, and JoinCostWorkspace::total_cost.

Referenced by match_unsorted_outer().

◆ try_partial_hashjoin_path()

static void try_partial_hashjoin_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List hashclauses,
JoinType  jointype,
JoinPathExtraData extra,
bool  parallel_hash 
)
static

Definition at line 1282 of file joinpath.c.

1290{
1291 JoinCostWorkspace workspace;
1292
1293 /*
1294 * If the inner path is parameterized, we can't use a partial hashjoin.
1295 * Parameterized partial paths are not supported. The caller should
1296 * already have verified that no lateral rels are required here.
1297 */
1299 Assert(bms_is_empty(PATH_REQ_OUTER(outer_path)));
1300 if (!bms_is_empty(PATH_REQ_OUTER(inner_path)))
1301 return;
1302
1303 /*
1304 * Before creating a path, get a quick lower bound on what it is likely to
1305 * cost. Bail out right away if it looks terrible.
1306 */
1307 initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1308 outer_path, inner_path, extra, parallel_hash);
1309 if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,
1310 workspace.total_cost, NIL))
1311 return;
1312
1313 /* Might be good enough to be worth trying, so let's try it. */
1314 add_partial_path(joinrel, (Path *)
1316 joinrel,
1317 jointype,
1318 &workspace,
1319 extra,
1320 outer_path,
1321 inner_path,
1322 parallel_hash,
1323 extra->restrictlist,
1324 NULL,
1325 hashclauses));
1326}
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:795
bool add_partial_path_precheck(RelOptInfo *parent_rel, int disabled_nodes, Cost total_cost, List *pathkeys)
Definition: pathnode.c:921

References add_partial_path(), add_partial_path_precheck(), Assert(), bms_is_empty, create_hashjoin_path(), JoinCostWorkspace::disabled_nodes, initial_cost_hashjoin(), RelOptInfo::lateral_relids, NIL, PATH_REQ_OUTER, JoinPathExtraData::restrictlist, root, and JoinCostWorkspace::total_cost.

Referenced by hash_inner_and_outer().

◆ try_partial_mergejoin_path()

static void try_partial_mergejoin_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List pathkeys,
List mergeclauses,
List outersortkeys,
List innersortkeys,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1138 of file joinpath.c.

1148{
1149 JoinCostWorkspace workspace;
1150
1151 /*
1152 * See comments in try_partial_hashjoin_path().
1153 */
1155 Assert(bms_is_empty(PATH_REQ_OUTER(outer_path)));
1156 if (!bms_is_empty(PATH_REQ_OUTER(inner_path)))
1157 return;
1158
1159 /*
1160 * If the given paths are already well enough ordered, we can skip doing
1161 * an explicit sort.
1162 */
1163 if (outersortkeys &&
1164 pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
1165 outersortkeys = NIL;
1166 if (innersortkeys &&
1167 pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
1168 innersortkeys = NIL;
1169
1170 /*
1171 * See comments in try_partial_nestloop_path().
1172 */
1173 initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
1174 outer_path, inner_path,
1175 outersortkeys, innersortkeys,
1176 extra);
1177
1178 if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,
1179 workspace.total_cost, pathkeys))
1180 return;
1181
1182 /* Might be good enough to be worth trying, so let's try it. */
1183 add_partial_path(joinrel, (Path *)
1185 joinrel,
1186 jointype,
1187 &workspace,
1188 extra,
1189 outer_path,
1190 inner_path,
1191 extra->restrictlist,
1192 pathkeys,
1193 NULL,
1194 mergeclauses,
1195 outersortkeys,
1196 innersortkeys));
1197}

References add_partial_path(), add_partial_path_precheck(), Assert(), bms_is_empty, create_mergejoin_path(), JoinCostWorkspace::disabled_nodes, initial_cost_mergejoin(), RelOptInfo::lateral_relids, NIL, PATH_REQ_OUTER, Path::pathkeys, pathkeys_contained_in(), JoinPathExtraData::restrictlist, root, and JoinCostWorkspace::total_cost.

Referenced by sort_inner_and_outer(), and try_mergejoin_path().

◆ try_partial_nestloop_path()

static void try_partial_nestloop_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List pathkeys,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 953 of file joinpath.c.

960{
961 JoinCostWorkspace workspace;
962
963 /*
964 * If the inner path is parameterized, the parameterization must be fully
965 * satisfied by the proposed outer path. Parameterized partial paths are
966 * not supported. The caller should already have verified that no lateral
967 * rels are required here.
968 */
970 Assert(bms_is_empty(PATH_REQ_OUTER(outer_path)));
971 if (inner_path->param_info != NULL)
972 {
973 Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
974 RelOptInfo *outerrel = outer_path->parent;
975 Relids outerrelids;
976
977 /*
978 * The inner and outer paths are parameterized, if at all, by the top
979 * level parents, not the child relations, so we must use those relids
980 * for our parameterization tests.
981 */
982 if (outerrel->top_parent_relids)
983 outerrelids = outerrel->top_parent_relids;
984 else
985 outerrelids = outerrel->relids;
986
987 if (!bms_is_subset(inner_paramrels, outerrelids))
988 return;
989 }
990
991 /*
992 * If the inner path is parameterized, it is parameterized by the topmost
993 * parent of the outer rel, not the outer rel itself. We will need to
994 * translate the parameterization, if this path is chosen, during
995 * create_plan(). Here we just check whether we will be able to perform
996 * the translation, and if not avoid creating a nestloop path.
997 */
998 if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent) &&
999 !path_is_reparameterizable_by_child(inner_path, outer_path->parent))
1000 return;
1001
1002 /*
1003 * Before creating a path, get a quick lower bound on what it is likely to
1004 * cost. Bail out right away if it looks terrible.
1005 */
1006 initial_cost_nestloop(root, &workspace, jointype,
1007 outer_path, inner_path, extra);
1008 if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,
1009 workspace.total_cost, pathkeys))
1010 return;
1011
1012 /* Might be good enough to be worth trying, so let's try it. */
1013 add_partial_path(joinrel, (Path *)
1015 joinrel,
1016 jointype,
1017 &workspace,
1018 extra,
1019 outer_path,
1020 inner_path,
1021 extra->restrictlist,
1022 pathkeys,
1023 NULL));
1024}

References add_partial_path(), add_partial_path_precheck(), Assert(), bms_is_empty, bms_is_subset(), create_nestloop_path(), JoinCostWorkspace::disabled_nodes, initial_cost_nestloop(), RelOptInfo::lateral_relids, path_is_reparameterizable_by_child(), PATH_PARAM_BY_PARENT, PATH_REQ_OUTER, RelOptInfo::relids, JoinPathExtraData::restrictlist, root, RelOptInfo::top_parent_relids, and JoinCostWorkspace::total_cost.

Referenced by consider_parallel_nestloop().

Variable Documentation

◆ set_join_pathlist_hook

set_join_pathlist_hook_type set_join_pathlist_hook = NULL

Definition at line 33 of file joinpath.c.

Referenced by add_paths_to_joinrel().