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:1681

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:5090
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:2467
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1334
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:2197
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1789
@ JOIN_SEMI
Definition: nodes.h:307
@ JOIN_FULL
Definition: nodes.h:295
@ JOIN_INNER
Definition: nodes.h:293
@ JOIN_UNIQUE_OUTER
Definition: nodes.h:316
@ JOIN_UNIQUE_INNER
Definition: nodes.h:317
@ JOIN_ANTI
Definition: nodes.h:308
@ RELOPT_OTHER_JOINREL
Definition: pathnodes.h:830
#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:3242
Relids param_source_rels
Definition: pathnodes.h:3246
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:3245
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:3244
Relids relids
Definition: pathnodes.h:871
Relids top_parent_relids
Definition: pathnodes.h:1009
Relids lateral_relids
Definition: pathnodes.h:913
RelOptKind reloptkind
Definition: pathnodes.h:865
Relids min_righthand
Definition: pathnodes.h:2906
JoinType jointype
Definition: pathnodes.h:2909
Relids min_lefthand
Definition: pathnodes.h:2905

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

2055{
2056 ListCell *lc1;
2057
2058 /* generate merge join path for each partial outer path */
2059 foreach(lc1, outerrel->partial_pathlist)
2060 {
2061 Path *outerpath = (Path *) lfirst(lc1);
2062 List *merge_pathkeys;
2063
2064 /*
2065 * Figure out what useful ordering any paths we create will have.
2066 */
2067 merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
2068 outerpath->pathkeys);
2069
2070 generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
2071 extra, false, inner_cheapest_total,
2072 merge_pathkeys, true);
2073 }
2074}
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:1541
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:1294
Definition: pg_list.h:54
List * pathkeys
Definition: pathnodes.h:1677
List * partial_pathlist
Definition: pathnodes.h:900

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

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

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:158
PlaceHolderInfo * find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
Definition: placeholder.c:83
Definition: nodes.h:129
Relids ph_lateral
Definition: pathnodes.h:3102
Relids ph_eval_at
Definition: pathnodes.h:3099
PlaceHolderVar * ph_var
Definition: pathnodes.h:3096
Index phlevelsup
Definition: pathnodes.h:2808
Definition: primnodes.h:261
int varno
Definition: primnodes.h:268
Index varlevelsup
Definition: primnodes.h:293
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 1541 of file joinpath.c.

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

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 * XXX this could be enabled if the remaining join quals were made part of
753 * the inner scan's filter instead of the join filter. Maybe it's worth
754 * considering doing that?
755 */
756 if (extra->inner_unique &&
757 (inner_path->param_info == NULL ||
758 bms_num_members(inner_path->param_info->ppi_serials) <
759 list_length(extra->restrictlist)))
760 return NULL;
761
762 /*
763 * We can't use a memoize node if there are volatile functions in the
764 * inner rel's target list or restrict list. A cache hit could reduce the
765 * number of calls to these functions.
766 */
767 if (contain_volatile_functions((Node *) innerrel->reltarget))
768 return NULL;
769
770 foreach(lc, innerrel->baserestrictinfo)
771 {
772 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
773
774 if (contain_volatile_functions((Node *) rinfo))
775 return NULL;
776 }
777
778 /*
779 * Also check the parameterized path restrictinfos for volatile functions.
780 * Indexed functions must be immutable so shouldn't have any volatile
781 * functions, however, with a lateral join the inner scan may not be an
782 * index scan.
783 */
784 if (inner_path->param_info != NULL)
785 {
786 foreach(lc, inner_path->param_info->ppi_clauses)
787 {
788 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
789
790 if (contain_volatile_functions((Node *) rinfo))
791 return NULL;
792 }
793 }
794
795 /* Check if we have hash ops for each parameter to the path */
797 inner_path->param_info,
798 outerrel->top_parent ?
799 outerrel->top_parent : outerrel,
800 innerrel,
801 ph_lateral_vars,
802 &param_exprs,
803 &hash_operators,
804 &binary_mode))
805 {
806 return (Path *) create_memoize_path(root,
807 innerrel,
808 inner_path,
809 param_exprs,
810 hash_operators,
811 extra->inner_unique,
812 binary_mode,
813 outer_path->rows);
814 }
815
816 return NULL;
817}
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:751
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:537
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
Cardinality rows
Definition: pathnodes.h:1671
List * baserestrictinfo
Definition: pathnodes.h:985
struct PathTarget * reltarget
Definition: pathnodes.h:893
List * lateral_vars
Definition: pathnodes.h:940

References RelOptInfo::baserestrictinfo, bms_num_members(), contain_volatile_functions(), create_memoize_path(), enable_memoize, extract_lateral_vars_from_PHVs(), JoinPathExtraData::inner_unique, JOIN_ANTI, JOIN_SEMI, RelOptInfo::lateral_vars, lfirst, list_length(), 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 2197 of file joinpath.c.

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

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

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

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:76
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:32
List * args
Definition: primnodes.h:852
List * ppi_clauses
Definition: pathnodes.h:1592
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:386
#define TYPECACHE_EQ_OPR
Definition: typcache.h:137
#define TYPECACHE_HASH_PROC
Definition: typcache.h:141

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

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

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

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

1206{
1207 Relids required_outer;
1208 JoinCostWorkspace workspace;
1209
1210 /*
1211 * If we are forming an outer join at this join, it's nonsensical to use
1212 * an input path that uses the outer join as part of its parameterization.
1213 * (This can happen despite our join order restrictions, since those apply
1214 * to what is in an input relation not what its parameters are.)
1215 */
1216 if (extra->sjinfo->ojrelid != 0 &&
1217 (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) ||
1218 bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path))))
1219 return;
1220
1221 /*
1222 * Check to see if proposed path is still parameterized, and reject if the
1223 * parameterization wouldn't be sensible.
1224 */
1225 required_outer = calc_non_nestloop_required_outer(outer_path,
1226 inner_path);
1227 if (required_outer &&
1228 !bms_overlap(required_outer, extra->param_source_rels))
1229 {
1230 /* Waste no memory when we reject a path here */
1231 bms_free(required_outer);
1232 return;
1233 }
1234
1235 /*
1236 * See comments in try_nestloop_path(). Also note that hashjoin paths
1237 * never have any output pathkeys, per comments in create_hashjoin_path.
1238 */
1239 initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1240 outer_path, inner_path, extra, false);
1241
1242 if (add_path_precheck(joinrel, workspace.disabled_nodes,
1243 workspace.startup_cost, workspace.total_cost,
1244 NIL, required_outer))
1245 {
1246 add_path(joinrel, (Path *)
1248 joinrel,
1249 jointype,
1250 &workspace,
1251 extra,
1252 outer_path,
1253 inner_path,
1254 false, /* parallel_hash */
1255 extra->restrictlist,
1256 required_outer,
1257 hashclauses));
1258 }
1259 else
1260 {
1261 /* Waste no memory when we reject a path here */
1262 bms_free(required_outer);
1263 }
1264}
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:4160
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 1026 of file joinpath.c.

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

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

1284{
1285 JoinCostWorkspace workspace;
1286
1287 /*
1288 * If the inner path is parameterized, we can't use a partial hashjoin.
1289 * Parameterized partial paths are not supported. The caller should
1290 * already have verified that no lateral rels are required here.
1291 */
1293 Assert(bms_is_empty(PATH_REQ_OUTER(outer_path)));
1294 if (!bms_is_empty(PATH_REQ_OUTER(inner_path)))
1295 return;
1296
1297 /*
1298 * Before creating a path, get a quick lower bound on what it is likely to
1299 * cost. Bail out right away if it looks terrible.
1300 */
1301 initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1302 outer_path, inner_path, extra, parallel_hash);
1303 if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,
1304 workspace.total_cost, NIL))
1305 return;
1306
1307 /* Might be good enough to be worth trying, so let's try it. */
1308 add_partial_path(joinrel, (Path *)
1310 joinrel,
1311 jointype,
1312 &workspace,
1313 extra,
1314 outer_path,
1315 inner_path,
1316 parallel_hash,
1317 extra->restrictlist,
1318 NULL,
1319 hashclauses));
1320}
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 1132 of file joinpath.c.

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

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

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

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