Re: Performance improvement for joins where outer side is unique - Mailing list pgsql-hackers
| From | Tom Lane |
|---|---|
| Subject | Re: Performance improvement for joins where outer side is unique |
| Date | |
| Msg-id | 10298.1460073571@sss.pgh.pa.us Whole thread Raw |
| In response to | Re: Performance improvement for joins where outer side is unique (Tom Lane <tgl@sss.pgh.pa.us>) |
| Responses |
Re: Performance improvement for joins where outer side is unique
(Robert Haas <robertmhaas@gmail.com>)
Re: Performance improvement for joins where outer side is unique (David Rowley <david.rowley@2ndquadrant.com>) |
| List | pgsql-hackers |
I wrote: > Alvaro Herrera <alvherre@2ndquadrant.com> writes: >> FWIW the feature freeze rules state that it is allowed for a committer >> to request an extension to the feature freeze date for individual >> patches: >> https://www.postgresql.org/message-id/CA%2BTgmoY56w5FOzeEo%2Bi48qehL%2BBsVTwy-Q1M0xjUhUCwgGW7-Q%40mail.gmail.com >> It seems to me that the restrictions laid out there are well met for >> this patch, if you only need a couple of additional days for this patch >> to get in. > Hmm ... the changes I'm thinking about here are certainly pretty > mechanical, if tedious. The main question mark I have hanging over > this patch is whether the planning-time penalty is too large --- but > that's something that can be tested with the patch as it stands. > Let me go investigate that a bit before requesting an extension. I did some performance testing on the attached somewhat-cleaned-up patch, and convinced myself that the planning time penalty is fairly minimal: on the order of a couple percent in simple one-join queries, and less than that in very large queries. Oddly, it seems that the result cacheing done in get_optimal_jointype() is only barely worth the trouble in typical cases; though if you get a query large enough to require GEQO, it's a win because successive GEQO attempts can re-use cache entries made by earlier attempts. (This may indicate something wrong with my testing procedure? Seems like diking out the cache should have made more difference.) I did find by measurement that the negative-cache-entry code produces exactly zero hits unless you're in GEQO mode, which is not really surprising given the order in which the join search occurs. So in the attached patch I made the code not bother with making negative cache entries unless using GEQO, to hopefully save a few nanoseconds. I rebased over f338dd758, did a little bit of code cleanup and fixed some bugs in the uniqueness detection logic, but have not reviewed the rest of the patch since it's likely all gonna change if we reconsider the JoinType representation. Anyway, I think it would be reasonable to give this patch a few more days in view of David's being away through the weekend. But the RMT has final say on that. regards, tom lane diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out index 50f1261..f9df294 100644 *** a/contrib/postgres_fdw/expected/postgres_fdw.out --- b/contrib/postgres_fdw/expected/postgres_fdw.out *************** EXPLAIN (VERBOSE, COSTS false) *** 386,392 **** --------------------------------------------------------------------------------------- Limit Output: t1.c1, t2."C 1" ! -> Merge Join Output: t1.c1, t2."C 1" Merge Cond: (t1.c1 = t2."C 1") -> Foreign Scan on public.ft2 t1 --- 386,392 ---- --------------------------------------------------------------------------------------- Limit Output: t1.c1, t2."C 1" ! -> Merge Unique Inner Join Output: t1.c1, t2."C 1" Merge Cond: (t1.c1 = t2."C 1") -> Foreign Scan on public.ft2 t1 *************** EXPLAIN (VERBOSE, COSTS false) *** 419,425 **** --------------------------------------------------------------------------------------- Limit Output: t1.c1, t2."C 1" ! -> Merge Left Join Output: t1.c1, t2."C 1" Merge Cond: (t1.c1 = t2."C 1") -> Foreign Scan on public.ft2 t1 --- 419,425 ---- --------------------------------------------------------------------------------------- Limit Output: t1.c1, t2."C 1" ! -> Merge Unique Left Join Output: t1.c1, t2."C 1" Merge Cond: (t1.c1 = t2."C 1") -> Foreign Scan on public.ft2 t1 *************** explain (verbose, costs off) select * fr *** 2520,2526 **** where f.f3 = l.f3 COLLATE "POSIX" and l.f1 = 'foo'; QUERY PLAN ------------------------------------------------------------- ! Hash Join Output: f.f1, f.f2, f.f3, l.f1, l.f2, l.f3 Hash Cond: ((f.f3)::text = (l.f3)::text) -> Foreign Scan on public.ft3 f --- 2520,2526 ---- where f.f3 = l.f3 COLLATE "POSIX" and l.f1 = 'foo'; QUERY PLAN ------------------------------------------------------------- ! Hash Unique Inner Join Output: f.f1, f.f2, f.f3, l.f1, l.f2, l.f3 Hash Cond: ((f.f3)::text = (l.f3)::text) -> Foreign Scan on public.ft3 f diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c index ee0220a..59084c6 100644 *** a/contrib/postgres_fdw/postgres_fdw.c --- b/contrib/postgres_fdw/postgres_fdw.c *************** foreign_join_ok(PlannerInfo *root, RelOp *** 3923,3932 **** /* * We support pushing down INNER, LEFT, RIGHT and FULL OUTER joins. * Constructing queries representing SEMI and ANTI joins is hard, hence ! * not considered right now. */ if (jointype != JOIN_INNER && jointype != JOIN_LEFT && ! jointype != JOIN_RIGHT && jointype != JOIN_FULL) return false; /* --- 3923,3935 ---- /* * We support pushing down INNER, LEFT, RIGHT and FULL OUTER joins. * Constructing queries representing SEMI and ANTI joins is hard, hence ! * not considered right now. INNER_UNIQUE and LEFT_UNIQUE joins are ok ! * here, since they're merely an optimization their non-unique ! * counterparts. */ if (jointype != JOIN_INNER && jointype != JOIN_LEFT && ! jointype != JOIN_RIGHT && jointype != JOIN_FULL && ! jointype != JOIN_INNER_UNIQUE && jointype != JOIN_LEFT_UNIQUE) return false; /* *************** foreign_join_ok(PlannerInfo *root, RelOp *** 4052,4057 **** --- 4055,4061 ---- switch (jointype) { case JOIN_INNER: + case JOIN_INNER_UNIQUE: fpinfo->remote_conds = list_concat(fpinfo->remote_conds, list_copy(fpinfo_i->remote_conds)); fpinfo->remote_conds = list_concat(fpinfo->remote_conds, *************** foreign_join_ok(PlannerInfo *root, RelOp *** 4059,4064 **** --- 4063,4069 ---- break; case JOIN_LEFT: + case JOIN_LEFT_UNIQUE: fpinfo->joinclauses = list_concat(fpinfo->joinclauses, list_copy(fpinfo_i->remote_conds)); fpinfo->remote_conds = list_concat(fpinfo->remote_conds, diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c index 713cd0e..e05925b 100644 *** a/src/backend/commands/explain.c --- b/src/backend/commands/explain.c *************** ExplainNode(PlanState *planstate, List * *** 1118,1126 **** --- 1118,1132 ---- case JOIN_INNER: jointype = "Inner"; break; + case JOIN_INNER_UNIQUE: + jointype = "Unique Inner"; + break; case JOIN_LEFT: jointype = "Left"; break; + case JOIN_LEFT_UNIQUE: + jointype = "Unique Left"; + break; case JOIN_FULL: jointype = "Full"; break; diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c index 369e666..196a075 100644 *** a/src/backend/executor/nodeHashjoin.c --- b/src/backend/executor/nodeHashjoin.c *************** ExecHashJoin(HashJoinState *node) *** 306,315 **** } /* ! * In a semijoin, we'll consider returning the first ! * match, but after that we're done with this outer tuple. */ ! if (node->js.jointype == JOIN_SEMI) node->hj_JoinState = HJ_NEED_NEW_OUTER; if (otherqual == NIL || --- 306,318 ---- } /* ! * In an inner unique, left unique or semi join, we'll ! * consider returning the first match, but after that ! * we're done with this outer tuple. */ ! if (node->js.jointype == JOIN_INNER_UNIQUE || ! node->js.jointype == JOIN_LEFT_UNIQUE || ! node->js.jointype == JOIN_SEMI) node->hj_JoinState = HJ_NEED_NEW_OUTER; if (otherqual == NIL || *************** ExecInitHashJoin(HashJoin *node, EState *** 499,507 **** --- 502,512 ---- switch (node->join.jointype) { case JOIN_INNER: + case JOIN_INNER_UNIQUE: case JOIN_SEMI: break; case JOIN_LEFT: + case JOIN_LEFT_UNIQUE: case JOIN_ANTI: hjstate->hj_NullInnerTupleSlot = ExecInitNullTupleSlot(estate, diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c index 6db09b8..aa3e144 100644 *** a/src/backend/executor/nodeMergejoin.c --- b/src/backend/executor/nodeMergejoin.c *************** ExecMergeJoin(MergeJoinState *node) *** 840,849 **** } /* ! * In a semijoin, we'll consider returning the first ! * match, but after that we're done with this outer tuple. */ ! if (node->js.jointype == JOIN_SEMI) node->mj_JoinState = EXEC_MJ_NEXTOUTER; qualResult = (otherqual == NIL || --- 840,852 ---- } /* ! * In an inner unique, left unique or semi join, we'll ! * consider returning the first match, but after that ! * we're done with this outer tuple. */ ! if (node->js.jointype == JOIN_INNER_UNIQUE || ! node->js.jointype == JOIN_LEFT_UNIQUE || ! node->js.jointype == JOIN_SEMI) node->mj_JoinState = EXEC_MJ_NEXTOUTER; qualResult = (otherqual == NIL || *************** ExecInitMergeJoin(MergeJoin *node, EStat *** 1555,1564 **** --- 1558,1569 ---- { case JOIN_INNER: case JOIN_SEMI: + case JOIN_INNER_UNIQUE: mergestate->mj_FillOuter = false; mergestate->mj_FillInner = false; break; case JOIN_LEFT: + case JOIN_LEFT_UNIQUE: case JOIN_ANTI: mergestate->mj_FillOuter = true; mergestate->mj_FillInner = false; diff --git a/src/backend/executor/nodeNestloop.c b/src/backend/executor/nodeNestloop.c index 555fa09..0526170 100644 *** a/src/backend/executor/nodeNestloop.c --- b/src/backend/executor/nodeNestloop.c *************** ExecNestLoop(NestLoopState *node) *** 182,187 **** --- 182,188 ---- if (!node->nl_MatchedOuter && (node->js.jointype == JOIN_LEFT || + node->js.jointype == JOIN_LEFT_UNIQUE || node->js.jointype == JOIN_ANTI)) { /* *************** ExecNestLoop(NestLoopState *node) *** 247,256 **** } /* ! * In a semijoin, we'll consider returning the first match, but ! * after that we're done with this outer tuple. */ ! if (node->js.jointype == JOIN_SEMI) node->nl_NeedNewOuter = true; if (otherqual == NIL || ExecQual(otherqual, econtext, false)) --- 248,260 ---- } /* ! * In an inner unique, left unique or semi join, we'll consider ! * returning the first match, but after that we're done with this ! * outer tuple. */ ! if (node->js.jointype == JOIN_INNER_UNIQUE || ! node->js.jointype == JOIN_LEFT_UNIQUE || ! node->js.jointype == JOIN_SEMI) node->nl_NeedNewOuter = true; if (otherqual == NIL || ExecQual(otherqual, econtext, false)) *************** ExecInitNestLoop(NestLoop *node, EState *** 355,363 **** --- 359,369 ---- switch (node->join.jointype) { case JOIN_INNER: + case JOIN_INNER_UNIQUE: case JOIN_SEMI: break; case JOIN_LEFT: + case JOIN_LEFT_UNIQUE: case JOIN_ANTI: nlstate->nl_NullInnerTupleSlot = ExecInitNullTupleSlot(estate, diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c index a21928b..a2a91e5 100644 *** a/src/backend/nodes/copyfuncs.c --- b/src/backend/nodes/copyfuncs.c *************** _copySpecialJoinInfo(const SpecialJoinIn *** 2065,2070 **** --- 2065,2071 ---- COPY_BITMAPSET_FIELD(syn_lefthand); COPY_BITMAPSET_FIELD(syn_righthand); COPY_SCALAR_FIELD(jointype); + COPY_SCALAR_FIELD(optimal_jointype); COPY_SCALAR_FIELD(lhs_strict); COPY_SCALAR_FIELD(delay_upper_joins); COPY_SCALAR_FIELD(semi_can_btree); diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c index 3c6c567..3302a69 100644 *** a/src/backend/nodes/equalfuncs.c --- b/src/backend/nodes/equalfuncs.c *************** _equalSpecialJoinInfo(const SpecialJoinI *** 837,842 **** --- 837,843 ---- COMPARE_BITMAPSET_FIELD(syn_lefthand); COMPARE_BITMAPSET_FIELD(syn_righthand); COMPARE_SCALAR_FIELD(jointype); + COMPARE_SCALAR_FIELD(optimal_jointype); COMPARE_SCALAR_FIELD(lhs_strict); COMPARE_SCALAR_FIELD(delay_upper_joins); COMPARE_SCALAR_FIELD(semi_can_btree); diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index f783a49..06323d4 100644 *** a/src/backend/nodes/outfuncs.c --- b/src/backend/nodes/outfuncs.c *************** _outSpecialJoinInfo(StringInfo str, cons *** 2276,2281 **** --- 2276,2282 ---- WRITE_BITMAPSET_FIELD(syn_lefthand); WRITE_BITMAPSET_FIELD(syn_righthand); WRITE_ENUM_FIELD(jointype, JoinType); + WRITE_ENUM_FIELD(optimal_jointype, JoinType); WRITE_BOOL_FIELD(lhs_strict); WRITE_BOOL_FIELD(delay_upper_joins); WRITE_BOOL_FIELD(semi_can_btree); diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 70a4c27..e4d5cc9 100644 *** a/src/backend/optimizer/path/costsize.c --- b/src/backend/optimizer/path/costsize.c *************** cost_group(Path *path, PlannerInfo *root *** 1893,1900 **** * estimate and getting a tight lower bound. We choose to not examine the * join quals here, since that's by far the most expensive part of the * calculations. The end result is that CPU-cost considerations must be ! * left for the second phase; and for SEMI/ANTI joins, we must also postpone ! * incorporation of the inner path's run cost. * * 'workspace' is to be filled with startup_cost, total_cost, and perhaps * other data to be used by final_cost_nestloop --- 1893,1901 ---- * estimate and getting a tight lower bound. We choose to not examine the * join quals here, since that's by far the most expensive part of the * calculations. The end result is that CPU-cost considerations must be ! * left for the second phase; and for INNER_UNIQUE, LEFT_UNIQUE, SEMI, and ! * ANTI joins, we must also postpone incorporation of the inner path's run ! * cost. * * 'workspace' is to be filled with startup_cost, total_cost, and perhaps * other data to be used by final_cost_nestloop *************** cost_group(Path *path, PlannerInfo *root *** 1902,1908 **** * 'outer_path' is the outer input to the join * 'inner_path' is the inner input to the join * 'sjinfo' is extra info about the join for selectivity estimation ! * 'semifactors' contains valid data if jointype is SEMI or ANTI */ void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, --- 1903,1910 ---- * 'outer_path' is the outer input to the join * 'inner_path' is the inner input to the join * 'sjinfo' is extra info about the join for selectivity estimation ! * 'semifactors' contains valid data if jointype is INNER_UNIQUE, LEFT_UNIQUE, ! * SEMI, or ANTI */ void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, *************** initial_cost_nestloop(PlannerInfo *root, *** 1940,1949 **** inner_run_cost = inner_path->total_cost - inner_path->startup_cost; inner_rescan_run_cost = inner_rescan_total_cost - inner_rescan_start_cost; ! if (jointype == JOIN_SEMI || jointype == JOIN_ANTI) { /* ! * SEMI or ANTI join: executor will stop after first match. * * Getting decent estimates requires inspection of the join quals, * which we choose to postpone to final_cost_nestloop. --- 1942,1955 ---- inner_run_cost = inner_path->total_cost - inner_path->startup_cost; inner_rescan_run_cost = inner_rescan_total_cost - inner_rescan_start_cost; ! if (jointype == JOIN_INNER_UNIQUE || ! jointype == JOIN_LEFT_UNIQUE || ! jointype == JOIN_SEMI || ! jointype == JOIN_ANTI) { /* ! * INNER_UNIQUE, LEFT_UNIQUE, SEMI, or ANTI join: executor will stop ! * after first match. * * Getting decent estimates requires inspection of the join quals, * which we choose to postpone to final_cost_nestloop. *************** initial_cost_nestloop(PlannerInfo *root, *** 1977,1983 **** * 'path' is already filled in except for the rows and cost fields * 'workspace' is the result from initial_cost_nestloop * 'sjinfo' is extra info about the join for selectivity estimation ! * 'semifactors' contains valid data if path->jointype is SEMI or ANTI */ void final_cost_nestloop(PlannerInfo *root, NestPath *path, --- 1983,1990 ---- * 'path' is already filled in except for the rows and cost fields * 'workspace' is the result from initial_cost_nestloop * 'sjinfo' is extra info about the join for selectivity estimation ! * 'semifactors' contains valid data if jointype is INNER_UNIQUE, LEFT_UNIQUE, ! * SEMI, or ANTI */ void final_cost_nestloop(PlannerInfo *root, NestPath *path, *************** final_cost_nestloop(PlannerInfo *root, N *** 2017,2026 **** /* cost of inner-relation source data (we already dealt with outer rel) */ ! if (path->jointype == JOIN_SEMI || path->jointype == JOIN_ANTI) { /* ! * SEMI or ANTI join: executor will stop after first match. */ Cost inner_run_cost = workspace->inner_run_cost; Cost inner_rescan_run_cost = workspace->inner_rescan_run_cost; --- 2024,2037 ---- /* cost of inner-relation source data (we already dealt with outer rel) */ ! if (path->jointype == JOIN_INNER_UNIQUE || ! path->jointype == JOIN_LEFT_UNIQUE || ! path->jointype == JOIN_SEMI || ! path->jointype == JOIN_ANTI) { /* ! * INNER_UNIQUE, LEFT_UNIQUE, SEMI, or ANTI join: executor will stop ! * after first match. */ Cost inner_run_cost = workspace->inner_run_cost; Cost inner_rescan_run_cost = workspace->inner_rescan_run_cost; *************** initial_cost_mergejoin(PlannerInfo *root *** 2250,2255 **** --- 2261,2267 ---- innerendsel = cache->leftendsel; } if (jointype == JOIN_LEFT || + jointype == JOIN_LEFT_UNIQUE || jointype == JOIN_ANTI) { outerstartsel = 0.0; *************** initial_cost_hashjoin(PlannerInfo *root, *** 2773,2779 **** * num_batches * 'workspace' is the result from initial_cost_hashjoin * 'sjinfo' is extra info about the join for selectivity estimation ! * 'semifactors' contains valid data if path->jointype is SEMI or ANTI */ void final_cost_hashjoin(PlannerInfo *root, HashPath *path, --- 2785,2792 ---- * num_batches * 'workspace' is the result from initial_cost_hashjoin * 'sjinfo' is extra info about the join for selectivity estimation ! * 'semifactors' contains valid data if path->jointype is INNER_UNIQUE, ! * LEFT_UNIQUE, SEMI or ANTI */ void final_cost_hashjoin(PlannerInfo *root, HashPath *path, *************** final_cost_hashjoin(PlannerInfo *root, H *** 2896,2908 **** /* CPU costs */ ! if (path->jpath.jointype == JOIN_SEMI || path->jpath.jointype == JOIN_ANTI) { double outer_matched_rows; Selectivity inner_scan_frac; /* ! * SEMI or ANTI join: executor will stop after first match. * * For an outer-rel row that has at least one match, we can expect the * bucket scan to stop after a fraction 1/(match_count+1) of the --- 2909,2925 ---- /* CPU costs */ ! if (path->jpath.jointype == JOIN_INNER_UNIQUE || ! path->jpath.jointype == JOIN_LEFT_UNIQUE || ! path->jpath.jointype == JOIN_SEMI || ! path->jpath.jointype == JOIN_ANTI) { double outer_matched_rows; Selectivity inner_scan_frac; /* ! * INNER_UNIQUE, LEFT_UNIQUE, SEMI or ANTI join: executor will stop ! * after first match. * * For an outer-rel row that has at least one match, we can expect the * bucket scan to stop after a fraction 1/(match_count+1) of the *************** final_cost_hashjoin(PlannerInfo *root, H *** 2937,2946 **** clamp_row_est(inner_path_rows / virtualbuckets) * 0.05; /* Get # of tuples that will pass the basic join */ ! if (path->jpath.jointype == JOIN_SEMI) ! hashjointuples = outer_matched_rows; ! else hashjointuples = outer_path_rows - outer_matched_rows; } else { --- 2954,2963 ---- clamp_row_est(inner_path_rows / virtualbuckets) * 0.05; /* Get # of tuples that will pass the basic join */ ! if (path->jpath.jointype == JOIN_ANTI) hashjointuples = outer_path_rows - outer_matched_rows; + else + hashjointuples = outer_matched_rows; } else { *************** get_restriction_qual_cost(PlannerInfo *r *** 3469,3481 **** /* * compute_semi_anti_join_factors ! * Estimate how much of the inner input a SEMI or ANTI join ! * can be expected to scan. * ! * In a hash or nestloop SEMI/ANTI join, the executor will stop scanning ! * inner rows as soon as it finds a match to the current outer row. ! * We should therefore adjust some of the cost components for this effect. ! * This function computes some estimates needed for these adjustments. * These estimates will be the same regardless of the particular paths used * for the outer and inner relation, so we compute these once and then pass * them to all the join cost estimation functions. --- 3486,3498 ---- /* * compute_semi_anti_join_factors ! * Estimate how much of the inner input a INNER_UNIQUE, LEFT_UNIQUE, SEMI, ! * ANTI join can be expected to scan. * ! * In a hash or nestloop INNER_UNIQUE/LEFT_UNIQUE/SEMI/ANTI join, the executor ! * will stop scanning inner rows as soon as it finds a match to the current ! * outer row. We should therefore adjust some of the cost components for this ! * effect. This function computes some estimates needed for these adjustments. * These estimates will be the same regardless of the particular paths used * for the outer and inner relation, so we compute these once and then pass * them to all the join cost estimation functions. *************** get_restriction_qual_cost(PlannerInfo *r *** 3483,3489 **** * Input parameters: * outerrel: outer relation under consideration * innerrel: inner relation under consideration ! * jointype: must be JOIN_SEMI or JOIN_ANTI * sjinfo: SpecialJoinInfo relevant to this join * restrictlist: join quals * Output parameters: --- 3500,3507 ---- * Input parameters: * outerrel: outer relation under consideration * innerrel: inner relation under consideration ! * jointype: must be JOIN_INNER_UNIQUE, JOIN_LEFT_UNIQUE,JOIN_SEMI or ! * JOIN_ANTI * sjinfo: SpecialJoinInfo relevant to this join * restrictlist: join quals * Output parameters: *************** compute_semi_anti_join_factors(PlannerIn *** 3506,3512 **** ListCell *l; /* Should only be called in these cases */ ! Assert(jointype == JOIN_SEMI || jointype == JOIN_ANTI); /* * In an ANTI join, we must ignore clauses that are "pushed down", since --- 3524,3533 ---- ListCell *l; /* Should only be called in these cases */ ! Assert(jointype == JOIN_INNER_UNIQUE || ! jointype == JOIN_LEFT_UNIQUE || ! jointype == JOIN_SEMI || ! jointype == JOIN_ANTI); /* * In an ANTI join, we must ignore clauses that are "pushed down", since *************** compute_semi_anti_join_factors(PlannerIn *** 3530,3536 **** joinquals = restrictlist; /* ! * Get the JOIN_SEMI or JOIN_ANTI selectivity of the join clauses. */ jselec = clauselist_selectivity(root, joinquals, --- 3551,3558 ---- joinquals = restrictlist; /* ! * Get the JOIN_INNER_UNIQUE, JOIN_LEFT_UNIQUE, JOIN_SEMI or JOIN_ANTI ! * selectivity of the join clauses. */ jselec = clauselist_selectivity(root, joinquals, *************** calc_joinrel_size_estimate(PlannerInfo * *** 3967,3974 **** * pushed-down quals are applied after the outer join, so their * selectivity applies fully. * ! * For JOIN_SEMI and JOIN_ANTI, the selectivity is defined as the fraction ! * of LHS rows that have matches, and we apply that straightforwardly. */ switch (jointype) { --- 3989,4001 ---- * pushed-down quals are applied after the outer join, so their * selectivity applies fully. * ! * For JOIN_INNER_UNIQUE, JOIN_SEMI and JOIN_ANTI, the selectivity is ! * defined as the fraction of LHS rows that have matches, and we apply ! * that straightforwardly. ! * ! * For JOIN_SEMI_LEFT, the selectivity is defined as the fraction of the ! * LHS rows that have matches, although unlike JOIN_SEMI we must consider ! * NULL RHS rows, and take the higher estimate of the two. */ switch (jointype) { *************** calc_joinrel_size_estimate(PlannerInfo * *** 3990,3998 **** --- 4017,4032 ---- nrows *= pselec; break; case JOIN_SEMI: + case JOIN_INNER_UNIQUE: nrows = outer_rows * jselec; /* pselec not used */ break; + case JOIN_LEFT_UNIQUE: + nrows = outer_rows * jselec; + if (nrows < outer_rows) + nrows = outer_rows; + nrows *= pselec; + break; case JOIN_ANTI: nrows = outer_rows * (1.0 - jselec); nrows *= pselec; diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c index 41b60d0..c92f561 100644 *** a/src/backend/optimizer/path/joinpath.c --- b/src/backend/optimizer/path/joinpath.c *************** *** 19,24 **** --- 19,25 ---- #include "executor/executor.h" #include "foreign/fdwapi.h" #include "optimizer/cost.h" + #include "optimizer/planmain.h" #include "optimizer/pathnode.h" #include "optimizer/paths.h" *************** add_paths_to_joinrel(PlannerInfo *root, *** 88,93 **** --- 89,101 ---- bool mergejoin_allowed = true; ListCell *lc; + /* + * There may be a more optimal JoinType to use. Check for such cases + * first. + */ + jointype = get_optimal_jointype(root, outerrel, innerrel, jointype, sjinfo, + restrictlist); + extra.restrictlist = restrictlist; extra.mergeclause_list = NIL; extra.sjinfo = sjinfo; *************** add_paths_to_joinrel(PlannerInfo *root, *** 109,118 **** &mergejoin_allowed); /* ! * If it's SEMI or ANTI join, compute correction factors for cost ! * estimation. These will be the same for all paths. */ ! if (jointype == JOIN_SEMI || jointype == JOIN_ANTI) compute_semi_anti_join_factors(root, outerrel, innerrel, jointype, sjinfo, restrictlist, &extra.semifactors); --- 117,130 ---- &mergejoin_allowed); /* ! * If it's INNER_UNIQUE, LEFT_UNIQUE, SEMI or ANTI join, compute ! * correction factors for cost estimation. These will be the same for all ! * paths. */ ! if (jointype == JOIN_INNER_UNIQUE || ! jointype == JOIN_LEFT_UNIQUE || ! jointype == JOIN_SEMI || ! jointype == JOIN_ANTI) compute_semi_anti_join_factors(root, outerrel, innerrel, jointype, sjinfo, restrictlist, &extra.semifactors); *************** match_unsorted_outer(PlannerInfo *root, *** 827,842 **** ListCell *lc1; /* ! * Nestloop only supports inner, left, semi, and anti joins. Also, if we ! * are doing a right or full mergejoin, we must use *all* the mergeclauses ! * as join clauses, else we will not have a valid plan. (Although these ! * two flags are currently inverses, keep them separate for clarity and ! * possible future changes.) */ switch (jointype) { case JOIN_INNER: case JOIN_LEFT: case JOIN_SEMI: case JOIN_ANTI: nestjoinOK = true; --- 839,856 ---- ListCell *lc1; /* ! * Nestloop only supports inner, inner unique, left, left unique, semi, ! * and anti joins. Also, if we are doing a right or full mergejoin, we ! * must use *all* the mergeclauses as join clauses, else we will not have ! * a valid plan. (Although these two flags are currently inverses, keep ! * them separate for clarity and possible future changes.) */ switch (jointype) { case JOIN_INNER: + case JOIN_INNER_UNIQUE: case JOIN_LEFT: + case JOIN_LEFT_UNIQUE: case JOIN_SEMI: case JOIN_ANTI: nestjoinOK = true; diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c index 01d4fea..547d09d 100644 *** a/src/backend/optimizer/path/joinrels.c --- b/src/backend/optimizer/path/joinrels.c *************** join_is_legal(PlannerInfo *root, RelOptI *** 490,499 **** /* * The proposed join could still be legal, but only if we're * allowed to associate it into the RHS of this SJ. That means ! * this SJ must be a LEFT join (not SEMI or ANTI, and certainly ! * not FULL) and the proposed join must not overlap the LHS. */ ! if (sjinfo->jointype != JOIN_LEFT || bms_overlap(joinrelids, sjinfo->min_lefthand)) return false; /* invalid join path */ --- 490,501 ---- /* * The proposed join could still be legal, but only if we're * allowed to associate it into the RHS of this SJ. That means ! * this SJ must be a LEFT or LEFT_UNIQUE join (not SEMI or ANTI, ! * and certainly not FULL) and the proposed join must not overlap ! * the LHS. */ ! if ((sjinfo->jointype != JOIN_LEFT && ! sjinfo->jointype != JOIN_LEFT_UNIQUE) || bms_overlap(joinrelids, sjinfo->min_lefthand)) return false; /* invalid join path */ *************** join_is_legal(PlannerInfo *root, RelOptI *** 508,515 **** } /* ! * Fail if violated any SJ's RHS and didn't match to a LEFT SJ: the ! * proposed join can't associate into an SJ's RHS. * * Also, fail if the proposed join's predicate isn't strict; we're * essentially checking to see if we can apply outer-join identity 3, and --- 510,517 ---- } /* ! * Fail if violated any SJ's RHS and didn't match to a LEFT or LEFT_UNIQUE ! * SJ: the proposed join can't associate into an SJ's RHS. * * Also, fail if the proposed join's predicate isn't strict; we're * essentially checking to see if we can apply outer-join identity 3, and *************** join_is_legal(PlannerInfo *root, RelOptI *** 518,524 **** */ if (must_be_leftjoin && (match_sjinfo == NULL || ! match_sjinfo->jointype != JOIN_LEFT || !match_sjinfo->lhs_strict)) return false; /* invalid join path */ --- 520,527 ---- */ if (must_be_leftjoin && (match_sjinfo == NULL || ! (match_sjinfo->jointype != JOIN_LEFT && ! match_sjinfo->jointype != JOIN_LEFT_UNIQUE) || !match_sjinfo->lhs_strict)) return false; /* invalid join path */ *************** make_join_rel(PlannerInfo *root, RelOptI *** 698,703 **** --- 701,707 ---- sjinfo->syn_lefthand = rel1->relids; sjinfo->syn_righthand = rel2->relids; sjinfo->jointype = JOIN_INNER; + sjinfo->optimal_jointype = JOIN_INNER; /* we don't bother trying to make the remaining fields valid */ sjinfo->lhs_strict = false; sjinfo->delay_upper_joins = false; diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c index 3d305eb..f00d4a1 100644 *** a/src/backend/optimizer/plan/analyzejoins.c --- b/src/backend/optimizer/plan/analyzejoins.c *************** *** 34,39 **** --- 34,41 ---- /* local functions */ static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo); + static bool specialjoin_is_unique_join(PlannerInfo *root, + SpecialJoinInfo *sjinfo); static void remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids); static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved); *************** static bool rel_supports_distinctness(Pl *** 41,46 **** --- 43,80 ---- static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list); static Oid distinct_col_search(int colno, List *colnos, List *opids); + static bool is_innerrel_unique_for(PlannerInfo *root, + RelOptInfo *outerrel, + RelOptInfo *innerrel, + List *restrictlist); + + + /* + * optimize_outerjoin_types + * Determine the most optimal JoinType for each outer join, and update + * SpecialJoinInfo's optimal_jointype to that join type. + */ + void + optimize_outerjoin_types(PlannerInfo *root) + { + ListCell *lc; + + foreach(lc, root->join_info_list) + { + SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc); + + /* + * Currently we're only interested in LEFT JOINs. If we can prove + * these to have a unique inner side, based on the join condition then + * this can save the executor from having to attempt fruitless + * searches for subsequent matching outer tuples. + */ + if (sjinfo->jointype == JOIN_LEFT && + sjinfo->optimal_jointype != JOIN_LEFT_UNIQUE && + specialjoin_is_unique_join(root, sjinfo)) + sjinfo->optimal_jointype = JOIN_LEFT_UNIQUE; + } + } /* *************** restart: *** 95,100 **** --- 129,140 ---- root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo); /* + * We may now be able to optimize some joins which we could not + * optimize before. (XXX huh? how would that happen?) + */ + optimize_outerjoin_types(root); + + /* * Restart the scan. This is necessary to ensure we find all * removable joins independently of ordering of the join_info_list * (note that removal of attr_needed bits may make a join appear *************** join_is_removable(PlannerInfo *root, Spe *** 156,186 **** int innerrelid; RelOptInfo *innerrel; Relids joinrelids; - List *clause_list = NIL; - ListCell *l; int attroff; /* ! * Must be a non-delaying left join to a single baserel, else we aren't ! * going to be able to do anything with it. */ ! if (sjinfo->jointype != JOIN_LEFT || sjinfo->delay_upper_joins) return false; if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid)) ! return false; innerrel = find_base_rel(root, innerrelid); - /* - * Before we go to the effort of checking whether any innerrel variables - * are needed above the join, make a quick check to eliminate cases in - * which we will surely be unable to prove uniqueness of the innerrel. - */ - if (!rel_supports_distinctness(root, innerrel)) - return false; - /* Compute the relid set for the join we are considering */ joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); --- 196,219 ---- int innerrelid; RelOptInfo *innerrel; Relids joinrelids; int attroff; + ListCell *l; /* ! * Join must have a unique inner side and must be a non-delaying join to a ! * single baserel, else we aren't going to be able to do anything with it. */ ! if (sjinfo->optimal_jointype != JOIN_LEFT_UNIQUE || sjinfo->delay_upper_joins) return false; + /* Now we know specialjoin_is_unique_join() succeeded for this join */ + if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid)) ! return false; /* should not happen */ innerrel = find_base_rel(root, innerrelid); /* Compute the relid set for the join we are considering */ joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); *************** join_is_removable(PlannerInfo *root, Spe *** 190,196 **** * * Note that this test only detects use of inner-rel attributes in higher * join conditions and the target list. There might be such attributes in ! * pushed-down conditions at this join, too. We check that case below. * * As a micro-optimization, it seems better to start with max_attr and * count down rather than starting with min_attr and counting up, on the --- 223,230 ---- * * Note that this test only detects use of inner-rel attributes in higher * join conditions and the target list. There might be such attributes in ! * pushed-down conditions at this join, too, but in this case the join ! * would not have been optimized into a LEFT_UNIQUE join. * * As a micro-optimization, it seems better to start with max_attr and * count down rather than starting with min_attr and counting up, on the *************** join_is_removable(PlannerInfo *root, Spe *** 231,236 **** --- 265,305 ---- return false; /* it does reference innerrel */ } + return true; + } + + /* + * specialjoin_is_unique_join + * True if it can be proved that this special join can only ever match at + * most one inner row for any single outer row. False is returned if + * there's insufficient evidence to prove the join is unique. + */ + static bool + specialjoin_is_unique_join(PlannerInfo *root, SpecialJoinInfo *sjinfo) + { + int innerrelid; + RelOptInfo *innerrel; + Relids joinrelids; + List *clause_list = NIL; + ListCell *lc; + + /* if there's more than one relation involved, then punt */ + if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid)) + return false; + + innerrel = find_base_rel(root, innerrelid); + + /* + * Before we go to the effort of pulling out the join condition's columns, + * make a quick check to eliminate cases in which we will surely be unable + * to prove uniqueness of the innerrel. + */ + if (!rel_supports_distinctness(root, innerrel)) + return false; + + /* Compute the relid set for the join we are considering */ + joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); + /* * Search for mergejoinable clauses that constrain the inner rel against * either the outer rel or a pseudoconstant. If an operator is *************** join_is_removable(PlannerInfo *root, Spe *** 238,246 **** * it's what we want. The mergejoinability test also eliminates clauses * containing volatile functions, which we couldn't depend on. */ ! foreach(l, innerrel->joininfo) { ! RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l); /* * If it's not a join clause for this outer join, we can't use it. --- 307,315 ---- * it's what we want. The mergejoinability test also eliminates clauses * containing volatile functions, which we couldn't depend on. */ ! foreach(lc, innerrel->joininfo) { ! RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc); /* * If it's not a join clause for this outer join, we can't use it. *************** join_is_removable(PlannerInfo *root, Spe *** 252,261 **** !bms_equal(restrictinfo->required_relids, joinrelids)) { /* ! * If such a clause actually references the inner rel then join ! * removal has to be disallowed. We have to check this despite ! * the previous attr_needed checks because of the possibility of ! * pushed-down clauses referencing the rel. */ if (bms_is_member(innerrelid, restrictinfo->clause_relids)) return false; --- 321,331 ---- !bms_equal(restrictinfo->required_relids, joinrelids)) { /* ! * If such a clause actually references the inner rel then we ! * can't say we're unique. (XXX this is confusing conditions for ! * join removability with conditions for uniqueness, and could ! * probably stand to be improved. But for the moment, keep on ! * applying the stricter condition.) */ if (bms_is_member(innerrelid, restrictinfo->clause_relids)) return false; *************** distinct_col_search(int colno, List *col *** 837,839 **** --- 907,1074 ---- } return InvalidOid; } + + + /* + * is_innerrel_unique_for + * Determine if this innerrel can, at most, return a single tuple for each + * outer tuple, based on the 'restrictlist'. + */ + static bool + is_innerrel_unique_for(PlannerInfo *root, + RelOptInfo *outerrel, + RelOptInfo *innerrel, + List *restrictlist) + { + List *clause_list = NIL; + ListCell *lc; + + /* Fall out quickly if we certainly can't prove anything */ + if (restrictlist == NIL || + !rel_supports_distinctness(root, innerrel)) + return false; + + /* + * Search for mergejoinable clauses that constrain the inner rel against + * the outer rel. If an operator is mergejoinable then it behaves like + * equality for some btree opclass, so it's what we want. The + * mergejoinability test also eliminates clauses containing volatile + * functions, which we couldn't depend on. + */ + foreach(lc, restrictlist) + { + RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc); + + /* Ignore if it's not a mergejoinable clause */ + if (!restrictinfo->can_join || + restrictinfo->mergeopfamilies == NIL) + continue; /* not mergejoinable */ + + /* + * Check if clause has the form "outer op inner" or "inner op outer", + * and if so mark which side is inner. + */ + if (!clause_sides_match_join(restrictinfo, outerrel->relids, + innerrel->relids)) + continue; /* no good for these input relations */ + + /* OK, add to list */ + clause_list = lappend(clause_list, restrictinfo); + } + + /* Let rel_is_distinct_for() do the hard work */ + return rel_is_distinct_for(root, innerrel, clause_list); + } + + /* + * get_optimal_jointype + * We may be able to optimize some joins by converting the JoinType to one + * which the executor is able to run more efficiently. Here we look for + * such cases and if we find a better choice, then we'll return it, + * otherwise we'll return the original JoinType. + */ + JoinType + get_optimal_jointype(PlannerInfo *root, + RelOptInfo *outerrel, + RelOptInfo *innerrel, + JoinType jointype, + SpecialJoinInfo *sjinfo, + List *restrictlist) + { + int innerrelid; + + /* left joins were already optimized in optimize_outerjoin_types() */ + if (jointype == JOIN_LEFT) + return sjinfo->optimal_jointype; + + if (!bms_get_singleton_member(innerrel->relids, &innerrelid)) + return jointype; + + /* + * Any INNER JOINs which can be proven to return at most one inner tuple + * for each outer tuple can be converted in to a JOIN_SEMI. + */ + if (jointype == JOIN_INNER) + { + MemoryContext old_context; + ListCell *lc; + + /* can't optimize jointype with an empty restrictlist */ + if (restrictlist == NIL) + return jointype; + + /* + * First let's query the unique and non-unique caches to see if we've + * managed to prove that innerrel is unique for some subset of this + * outerrel. We don't need an exact match, as if we have any extra + * outerrels than were previously cached, then they can't make the + * innerrel any less unique. + */ + foreach(lc, root->unique_rels[innerrelid]) + { + Bitmapset *unique_rels = (Bitmapset *) lfirst(lc); + + if (bms_is_subset(unique_rels, outerrel->relids)) + return JOIN_INNER_UNIQUE; /* Success! */ + } + + /* + * We may have previously determined that this outerrel, or some + * superset thereof, cannot prove this innerrel to be unique. + */ + foreach(lc, root->non_unique_rels[innerrelid]) + { + Bitmapset *unique_rels = (Bitmapset *) lfirst(lc); + + if (bms_is_subset(outerrel->relids, unique_rels)) + return jointype; + } + + /* No cached information, so try to make the proof. */ + if (is_innerrel_unique_for(root, outerrel, innerrel, restrictlist)) + { + jointype = JOIN_INNER_UNIQUE; /* Success! */ + + /* + * Cache the positive result for future probes, being sure to keep + * it in the planner_cxt even if we are working in GEQO. + * + * Note: one might consider trying to isolate the minimal subset + * of the outerrels that proved the innerrel unique. But it's not + * worth the trouble, because the planner builds up joinrels + * incrementally and so we'll see the minimally sufficient + * outerrels before any supersets of them anyway. + */ + old_context = MemoryContextSwitchTo(root->planner_cxt); + root->unique_rels[innerrelid] = + lappend(root->unique_rels[innerrelid], + bms_copy(outerrel->relids)); + MemoryContextSwitchTo(old_context); + } + else + { + /* + * None of the join conditions for outerrel proved innerrel + * unique, so we can safely reject this outerrel or any subset of + * it in future checks. + * + * However, in normal planning mode, caching this knowledge is + * totally pointless; it won't be queried again, because we build + * up joinrels from smaller to larger. It is useful in GEQO mode, + * where the knowledge can be carried across successive planning + * attempts; and it's likely to be useful when using join-search + * plugins, too. Hence cache only when join_search_private is + * non-NULL. (Yeah, that's a hack, but it seems reasonable.) + */ + if (root->join_search_private) + { + old_context = MemoryContextSwitchTo(root->planner_cxt); + root->non_unique_rels[innerrelid] = + lappend(root->non_unique_rels[innerrelid], + bms_copy(outerrel->relids)); + MemoryContextSwitchTo(old_context); + } + } + } + return jointype; + } diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index 9999eea..a615680 100644 *** a/src/backend/optimizer/plan/initsplan.c --- b/src/backend/optimizer/plan/initsplan.c *************** make_outerjoininfo(PlannerInfo *root, *** 1128,1133 **** --- 1128,1135 ---- sjinfo->syn_lefthand = left_rels; sjinfo->syn_righthand = right_rels; sjinfo->jointype = jointype; + /* this may be changed later */ + sjinfo->optimal_jointype = jointype; /* this always starts out false */ sjinfo->delay_upper_joins = false; diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index edd95d8..690349d 100644 *** a/src/backend/optimizer/plan/planmain.c --- b/src/backend/optimizer/plan/planmain.c *************** query_planner(PlannerInfo *root, List *t *** 124,129 **** --- 124,132 ---- */ setup_simple_rel_arrays(root); + /* Allocate memory for caching which joins are unique. */ + setup_unique_join_caches(root); + /* * Construct RelOptInfo nodes for all base relations in query, and * indirectly for all appendrel member relations ("other rels"). This *************** query_planner(PlannerInfo *root, List *t *** 185,190 **** --- 188,196 ---- */ fix_placeholder_input_needed_levels(root); + /* Determine if there's a better JoinType for each outer join */ + optimize_outerjoin_types(root); + /* * Remove any useless outer joins. Ideally this would be done during * jointree preprocessing, but the necessary information isn't available diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index 5537c14..95c3a2f 100644 *** a/src/backend/optimizer/plan/setrefs.c --- b/src/backend/optimizer/plan/setrefs.c *************** set_join_references(PlannerInfo *root, J *** 1617,1622 **** --- 1617,1623 ---- switch (join->jointype) { case JOIN_LEFT: + case JOIN_LEFT_UNIQUE: case JOIN_SEMI: case JOIN_ANTI: inner_itlist->has_non_vars = false; diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 802eab3..c11769e 100644 *** a/src/backend/optimizer/util/relnode.c --- b/src/backend/optimizer/util/relnode.c *************** setup_simple_rel_arrays(PlannerInfo *roo *** 81,86 **** --- 81,102 ---- } /* + * setup_unique_join_caches + * Prepare the arrays we use for caching which joins are proved to be + * unique and non-unique. + */ + void + setup_unique_join_caches(PlannerInfo *root) + { + int size = list_length(root->parse->rtable) + 1; + + /* initialize the unique relation cache to all NULLs */ + root->unique_rels = (List **) palloc0(size * sizeof(List *)); + + root->non_unique_rels = (List **) palloc0(size * sizeof(List *)); + } + + /* * build_simple_rel * Construct a new RelOptInfo for a base relation or 'other' relation. */ diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c index 751de4b..66eb670 100644 *** a/src/backend/parser/parse_clause.c --- b/src/backend/parser/parse_clause.c *************** transformFromClauseItem(ParseState *psta *** 978,988 **** /* * Make the left-side RTEs available for LATERAL access within the * right side, by temporarily adding them to the pstate's namespace ! * list. Per SQL:2008, if the join type is not INNER or LEFT then the ! * left-side names must still be exposed, but it's an error to ! * reference them. (Stupid design, but that's what it says.) Hence, ! * we always push them into the namespace, but mark them as not ! * lateral_ok if the jointype is wrong. * * Notice that we don't require the merged namespace list to be * conflict-free. See the comments for scanNameSpaceForRefname(). --- 978,988 ---- /* * Make the left-side RTEs available for LATERAL access within the * right side, by temporarily adding them to the pstate's namespace ! * list. Per SQL:2008, if the join type is not INNER, INNER_UNIQUE, ! * LEFT or LEFT_UNIQUE then the left-side names must still be exposed, ! * but it's an error to reference them. (Stupid design, but that's ! * what it says.) Hence, we always push them into the namespace, but ! * mark them as not lateral_ok if the jointype is wrong. * * Notice that we don't require the merged namespace list to be * conflict-free. See the comments for scanNameSpaceForRefname(). *************** transformFromClauseItem(ParseState *psta *** 990,996 **** * NB: this coding relies on the fact that list_concat is not * destructive to its second argument. */ ! lateral_ok = (j->jointype == JOIN_INNER || j->jointype == JOIN_LEFT); setNamespaceLateralState(l_namespace, true, lateral_ok); sv_namespace_length = list_length(pstate->p_namespace); --- 990,999 ---- * NB: this coding relies on the fact that list_concat is not * destructive to its second argument. */ ! lateral_ok = (j->jointype == JOIN_INNER || ! j->jointype == JOIN_INNER_UNIQUE || ! j->jointype == JOIN_LEFT || ! j->jointype == JOIN_LEFT_UNIQUE); setNamespaceLateralState(l_namespace, true, lateral_ok); sv_namespace_length = list_length(pstate->p_namespace); diff --git a/src/backend/utils/adt/network_selfuncs.c b/src/backend/utils/adt/network_selfuncs.c index 2e39687..f14a3cb 100644 *** a/src/backend/utils/adt/network_selfuncs.c --- b/src/backend/utils/adt/network_selfuncs.c *************** networkjoinsel(PG_FUNCTION_ARGS) *** 215,221 **** --- 215,223 ---- switch (sjinfo->jointype) { case JOIN_INNER: + case JOIN_INNER_UNIQUE: case JOIN_LEFT: + case JOIN_LEFT_UNIQUE: case JOIN_FULL: /* diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index cc2a9a1..346952e 100644 *** a/src/backend/utils/adt/selfuncs.c --- b/src/backend/utils/adt/selfuncs.c *************** eqjoinsel(PG_FUNCTION_ARGS) *** 2202,2207 **** --- 2202,2208 ---- { case JOIN_INNER: case JOIN_LEFT: + case JOIN_LEFT_UNIQUE: case JOIN_FULL: selec = eqjoinsel_inner(operator, &vardata1, &vardata2); break; diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index 84efa8e..2ba7b07 100644 *** a/src/include/nodes/nodes.h --- b/src/include/nodes/nodes.h *************** typedef enum JoinType *** 640,645 **** --- 640,655 ---- JOIN_ANTI, /* 1 copy of each LHS row that has no match */ /* + * The following join types are a variants of JOIN_INNER and JOIN_LEFT for + * when the inner side of the join is known to be unique. This serves + * solely as an optimization to allow the executor to skip looking for + * another matching tuple in the inner side, when it's known that another + * cannot exist. + */ + JOIN_INNER_UNIQUE, + JOIN_LEFT_UNIQUE, + + /* * These codes are used internally in the planner, but are not supported * by the executor (nor, indeed, by most of the planner). */ *************** typedef enum JoinType *** 668,673 **** --- 678,684 ---- #define IS_OUTER_JOIN(jointype) \ (((1 << (jointype)) & \ ((1 << JOIN_LEFT) | \ + (1 << JOIN_LEFT_UNIQUE) | \ (1 << JOIN_FULL) | \ (1 << JOIN_RIGHT) | \ (1 << JOIN_ANTI))) != 0) diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index d430f6e..b00aba3 100644 *** a/src/include/nodes/relation.h --- b/src/include/nodes/relation.h *************** typedef struct PlannerInfo *** 221,226 **** --- 221,238 ---- List **join_rel_level; /* lists of join-relation RelOptInfos */ int join_cur_level; /* index of list being extended */ + /* + * During the join search we attempt to optimize joins to try to prove + * their inner side to be unique based on the join condition. This is a + * rather expensive thing to do as it requires checking each relations + * unique indexes to see if the relation can, at most, return one tuple + * for each outer tuple. We use this cache during the join search to + * record lists of the sets of relations which both prove, and disprove + * the uniqueness properties for the relid indexed by these arrays. + */ + List **unique_rels; /* cache for proven unique rels */ + List **non_unique_rels; /* cache for proven non-unique rels */ + List *init_plans; /* init SubPlans for query */ List *cte_plan_ids; /* per-CTE-item list of subplan IDs */ *************** typedef struct SpecialJoinInfo *** 1750,1755 **** --- 1762,1769 ---- Relids syn_lefthand; /* base relids syntactically within LHS */ Relids syn_righthand; /* base relids syntactically within RHS */ JoinType jointype; /* always INNER, LEFT, FULL, SEMI, or ANTI */ + JoinType optimal_jointype; /* as above but may also be + * INNER_UNIQUE or LEFT_UNIQUE */ bool lhs_strict; /* joinclause is strict for some LHS rel */ bool delay_upper_joins; /* can't commute with upper RHS */ /* Remaining fields are set only for JOIN_SEMI jointype: */ diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index acc827d..13b212f 100644 *** a/src/include/optimizer/pathnode.h --- b/src/include/optimizer/pathnode.h *************** extern Path *reparameterize_path(Planner *** 236,241 **** --- 236,242 ---- * prototypes for relnode.c */ extern void setup_simple_rel_arrays(PlannerInfo *root); + extern void setup_unique_join_caches(PlannerInfo *root); extern RelOptInfo *build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind); extern RelOptInfo *find_base_rel(PlannerInfo *root, int relid); diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h index da9c640..a10146c 100644 *** a/src/include/optimizer/planmain.h --- b/src/include/optimizer/planmain.h *************** extern RestrictInfo *build_implied_join_ *** 99,107 **** --- 99,114 ---- /* * prototypes for plan/analyzejoins.c */ + extern void optimize_outerjoin_types(PlannerInfo *root); extern List *remove_useless_joins(PlannerInfo *root, List *joinlist); extern bool query_supports_distinctness(Query *query); extern bool query_is_distinct_for(Query *query, List *colnos, List *opids); + extern JoinType get_optimal_jointype(PlannerInfo *root, + RelOptInfo *outerrel, + RelOptInfo *innerrel, + JoinType jointype, + SpecialJoinInfo *sjinfo, + List *restrictlist); /* * prototypes for plan/setrefs.c diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out index 3ff6691..691fa11 100644 *** a/src/test/regress/expected/aggregates.out --- b/src/test/regress/expected/aggregates.out *************** explain (costs off) select a,c from t1 g *** 880,908 **** explain (costs off) select * from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.y,t2.z; ! QUERY PLAN ! ------------------------------------------------------- ! Group Group Key: t1.a, t1.b, t2.x, t2.y ! -> Merge Join ! Merge Cond: ((t1.a = t2.x) AND (t1.b = t2.y)) ! -> Index Scan using t1_pkey on t1 ! -> Index Scan using t2_pkey on t2 ! (6 rows) -- Test case where t1 can be optimized but not t2 explain (costs off) select t1.*,t2.x,t2.z from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.z; ! QUERY PLAN ! ------------------------------------------------------- HashAggregate Group Key: t1.a, t1.b, t2.x, t2.z ! -> Merge Join ! Merge Cond: ((t1.a = t2.x) AND (t1.b = t2.y)) ! -> Index Scan using t1_pkey on t1 ! -> Index Scan using t2_pkey on t2 ! (6 rows) -- Cannot optimize when PK is deferrable explain (costs off) select * from t3 group by a,b,c; --- 880,910 ---- explain (costs off) select * from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.y,t2.z; ! QUERY PLAN ! ------------------------------------------------------ ! HashAggregate Group Key: t1.a, t1.b, t2.x, t2.y ! -> Hash Unique Inner Join ! Hash Cond: ((t2.x = t1.a) AND (t2.y = t1.b)) ! -> Seq Scan on t2 ! -> Hash ! -> Seq Scan on t1 ! (7 rows) -- Test case where t1 can be optimized but not t2 explain (costs off) select t1.*,t2.x,t2.z from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.z; ! QUERY PLAN ! ------------------------------------------------------ HashAggregate Group Key: t1.a, t1.b, t2.x, t2.z ! -> Hash Unique Inner Join ! Hash Cond: ((t2.x = t1.a) AND (t2.y = t1.b)) ! -> Seq Scan on t2 ! -> Hash ! -> Seq Scan on t1 ! (7 rows) -- Cannot optimize when PK is deferrable explain (costs off) select * from t3 group by a,b,c; diff --git a/src/test/regress/expected/equivclass.out b/src/test/regress/expected/equivclass.out index 0391b8e..f446284 100644 *** a/src/test/regress/expected/equivclass.out --- b/src/test/regress/expected/equivclass.out *************** explain (costs off) *** 186,192 **** select * from ec1, ec2 where ff = x1 and x1 = '42'::int8alias2; QUERY PLAN ----------------------------------------- ! Nested Loop -> Seq Scan on ec2 Filter: (x1 = '42'::int8alias2) -> Index Scan using ec1_pkey on ec1 --- 186,192 ---- select * from ec1, ec2 where ff = x1 and x1 = '42'::int8alias2; QUERY PLAN ----------------------------------------- ! Nested Loop Unique Inner Join -> Seq Scan on ec2 Filter: (x1 = '42'::int8alias2) -> Index Scan using ec1_pkey on ec1 *************** explain (costs off) *** 310,316 **** -> Index Scan using ec1_expr3 on ec1 ec1_5 -> Index Scan using ec1_expr4 on ec1 ec1_6 -> Materialize ! -> Merge Join Merge Cond: ((((ec1_1.ff + 2) + 1)) = ec1.f1) -> Merge Append Sort Key: (((ec1_1.ff + 2) + 1)) --- 310,316 ---- -> Index Scan using ec1_expr3 on ec1 ec1_5 -> Index Scan using ec1_expr4 on ec1 ec1_6 -> Materialize ! -> Merge Unique Inner Join Merge Cond: ((((ec1_1.ff + 2) + 1)) = ec1.f1) -> Merge Append Sort Key: (((ec1_1.ff + 2) + 1)) *************** explain (costs off) *** 365,371 **** where ss1.x = ec1.f1 and ec1.ff = 42::int8; QUERY PLAN ----------------------------------------------------- ! Merge Join Merge Cond: ((((ec1_1.ff + 2) + 1)) = ec1.f1) -> Merge Append Sort Key: (((ec1_1.ff + 2) + 1)) --- 365,371 ---- where ss1.x = ec1.f1 and ec1.ff = 42::int8; QUERY PLAN ----------------------------------------------------- ! Merge Unique Inner Join Merge Cond: ((((ec1_1.ff + 2) + 1)) = ec1.f1) -> Merge Append Sort Key: (((ec1_1.ff + 2) + 1)) diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index cafbc5e..7d0aaa7 100644 *** a/src/test/regress/expected/join.out --- b/src/test/regress/expected/join.out *************** from nt3 as nt3 *** 2756,2763 **** where nt3.id = 1 and ss2.b3; QUERY PLAN ----------------------------------------------- ! Nested Loop ! -> Nested Loop -> Index Scan using nt3_pkey on nt3 Index Cond: (id = 1) -> Index Scan using nt2_pkey on nt2 --- 2756,2763 ---- where nt3.id = 1 and ss2.b3; QUERY PLAN ----------------------------------------------- ! Nested Loop Unique Inner Join ! -> Nested Loop Unique Inner Join -> Index Scan using nt3_pkey on nt3 Index Cond: (id = 1) -> Index Scan using nt2_pkey on nt2 *************** explain (costs off) *** 4035,4041 **** on (p.k = ss.k); QUERY PLAN --------------------------------- ! Hash Left Join Hash Cond: (p.k = c.k) -> Seq Scan on parent p -> Hash --- 4035,4041 ---- on (p.k = ss.k); QUERY PLAN --------------------------------- ! Hash Unique Left Join Hash Cond: (p.k = c.k) -> Seq Scan on parent p -> Hash *************** ERROR: invalid reference to FROM-clause *** 5260,5262 **** --- 5260,5497 ---- LINE 1: ...xx1 using lateral (select * from int4_tbl where f1 = x1) ss; ^ HINT: There is an entry for table "xx1", but it cannot be referenced from this part of the query. + -- + -- test planner's ability to change joins into their appropriate semi join + -- type + -- + create table j1 (id int primary key); + create table j2 (id int primary key); + create table j3 (id int); + insert into j1 values(1),(2),(3); + insert into j2 values(1),(2),(3); + insert into j3 values(1),(1); + analyze j1; + analyze j2; + analyze j3; + -- ensure join is changed to a semi join + explain (verbose, costs off) + select * from j1 inner join j2 on j1.id = j2.id; + QUERY PLAN + ----------------------------------- + Hash Unique Inner Join + Output: j1.id, j2.id + Hash Cond: (j1.id = j2.id) + -> Seq Scan on public.j1 + Output: j1.id + -> Hash + Output: j2.id + -> Seq Scan on public.j2 + Output: j2.id + (9 rows) + + -- ensure join not changed when not an equi-join + explain (verbose, costs off) + select * from j1 inner join j2 on j1.id > j2.id; + QUERY PLAN + ----------------------------------- + Nested Loop + Output: j1.id, j2.id + Join Filter: (j1.id > j2.id) + -> Seq Scan on public.j1 + Output: j1.id + -> Materialize + Output: j2.id + -> Seq Scan on public.j2 + Output: j2.id + (9 rows) + + -- don't change, as j3 has no unique index or pk on id + explain (verbose, costs off) + select * from j1 inner join j3 on j1.id = j3.id; + QUERY PLAN + ----------------------------------- + Hash Unique Inner Join + Output: j1.id, j3.id + Hash Cond: (j3.id = j1.id) + -> Seq Scan on public.j3 + Output: j3.id + -> Hash + Output: j1.id + -> Seq Scan on public.j1 + Output: j1.id + (9 rows) + + -- ensure left join is converted to left semi join + explain (verbose, costs off) + select * from j1 left join j2 on j1.id = j2.id; + QUERY PLAN + ----------------------------------- + Hash Unique Left Join + Output: j1.id, j2.id + Hash Cond: (j1.id = j2.id) + -> Seq Scan on public.j1 + Output: j1.id + -> Hash + Output: j2.id + -> Seq Scan on public.j2 + Output: j2.id + (9 rows) + + -- ensure right join is converted too + explain (verbose, costs off) + select * from j1 right join j2 on j1.id = j2.id; + QUERY PLAN + ----------------------------------- + Hash Unique Left Join + Output: j1.id, j2.id + Hash Cond: (j2.id = j1.id) + -> Seq Scan on public.j2 + Output: j2.id + -> Hash + Output: j1.id + -> Seq Scan on public.j1 + Output: j1.id + (9 rows) + + -- a clauseless (cross) join can't be converted + explain (verbose, costs off) + select * from j1 cross join j2; + QUERY PLAN + ----------------------------------- + Nested Loop + Output: j1.id, j2.id + -> Seq Scan on public.j1 + Output: j1.id + -> Materialize + Output: j2.id + -> Seq Scan on public.j2 + Output: j2.id + (8 rows) + + -- ensure a natural join is converted to a semi join + explain (verbose, costs off) + select * from j1 natural join j2; + QUERY PLAN + ----------------------------------- + Hash Unique Inner Join + Output: j1.id + Hash Cond: (j1.id = j2.id) + -> Seq Scan on public.j1 + Output: j1.id + -> Hash + Output: j2.id + -> Seq Scan on public.j2 + Output: j2.id + (9 rows) + + -- ensure distinct clause allows the inner to become a semi join + explain (verbose, costs off) + select * from j1 + inner join (select distinct id from j3) j3 on j1.id = j3.id; + QUERY PLAN + ----------------------------------------------- + Nested Loop Unique Inner Join + Output: j1.id, j3.id + Join Filter: (j1.id = j3.id) + -> Seq Scan on public.j1 + Output: j1.id + -> Materialize + Output: j3.id + -> Unique + Output: j3.id + -> Sort + Output: j3.id + Sort Key: j3.id + -> Seq Scan on public.j3 + Output: j3.id + (14 rows) + + -- ensure group by clause allows the inner to become a semi join + explain (verbose, costs off) + select * from j1 + inner join (select id from j3 group by id) j3 on j1.id = j3.id; + QUERY PLAN + ----------------------------------------------- + Nested Loop Unique Inner Join + Output: j1.id, j3.id + Join Filter: (j1.id = j3.id) + -> Seq Scan on public.j1 + Output: j1.id + -> Materialize + Output: j3.id + -> Group + Output: j3.id + Group Key: j3.id + -> Sort + Output: j3.id + Sort Key: j3.id + -> Seq Scan on public.j3 + Output: j3.id + (15 rows) + + -- ensure a full join is not altered + explain (verbose, costs off) + select * from j1 full join j2 on j1.id = j2.id; + QUERY PLAN + ----------------------------------- + Hash Full Join + Output: j1.id, j2.id + Hash Cond: (j1.id = j2.id) + -> Seq Scan on public.j1 + Output: j1.id + -> Hash + Output: j2.id + -> Seq Scan on public.j2 + Output: j2.id + (9 rows) + + drop table j1; + drop table j2; + drop table j3; + -- test a more complex permutations of join conversions + create table j1 (id1 int, id2 int, primary key(id1,id2)); + create table j2 (id1 int, id2 int, primary key(id1,id2)); + create table j3 (id1 int, id2 int, primary key(id1,id2)); + insert into j1 values(1,1),(2,2); + insert into j2 values(1,1); + insert into j3 values(1,1); + analyze j1; + analyze j2; + analyze j3; + -- ensure there's no join conversion when not all columns which are part of + -- the unique index are part of the join clause + explain (verbose, costs off) + select * from j1 + inner join j2 on j1.id1 = j2.id1; + QUERY PLAN + ------------------------------------------ + Nested Loop + Output: j1.id1, j1.id2, j2.id1, j2.id2 + Join Filter: (j1.id1 = j2.id1) + -> Seq Scan on public.j2 + Output: j2.id1, j2.id2 + -> Seq Scan on public.j1 + Output: j1.id1, j1.id2 + (7 rows) + + -- ensure inner is converted to semi join when there's multiple columns in the + -- join condition + explain (verbose, costs off) + select * from j1 + inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2; + QUERY PLAN + ---------------------------------------------------------- + Nested Loop Unique Inner Join + Output: j1.id1, j1.id2, j2.id1, j2.id2 + Join Filter: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2)) + -> Seq Scan on public.j1 + Output: j1.id1, j1.id2 + -> Materialize + Output: j2.id1, j2.id2 + -> Seq Scan on public.j2 + Output: j2.id1, j2.id2 + (9 rows) + + drop table j1; + drop table j2; + drop table j3; diff --git a/src/test/regress/expected/rowsecurity.out b/src/test/regress/expected/rowsecurity.out index 067aa8d..9fdc695 100644 *** a/src/test/regress/expected/rowsecurity.out --- b/src/test/regress/expected/rowsecurity.out *************** EXPLAIN (COSTS OFF) SELECT * FROM docume *** 276,282 **** EXPLAIN (COSTS OFF) SELECT * FROM document NATURAL JOIN category WHERE f_leak(dtitle); QUERY PLAN ---------------------------------------------------- ! Nested Loop -> Subquery Scan on document Filter: f_leak(document.dtitle) -> Seq Scan on document document_1 --- 276,282 ---- EXPLAIN (COSTS OFF) SELECT * FROM document NATURAL JOIN category WHERE f_leak(dtitle); QUERY PLAN ---------------------------------------------------- ! Nested Loop Unique Inner Join -> Subquery Scan on document Filter: f_leak(document.dtitle) -> Seq Scan on document document_1 diff --git a/src/test/regress/expected/select_views.out b/src/test/regress/expected/select_views.out index 7f57526..2651ff8 100644 *** a/src/test/regress/expected/select_views.out --- b/src/test/regress/expected/select_views.out *************** NOTICE: f_leak => 9801-2345-6789-0123 *** 1411,1417 **** EXPLAIN (COSTS OFF) SELECT * FROM my_credit_card_normal WHERE f_leak(cnum); QUERY PLAN --------------------------------------------------------- ! Hash Join Hash Cond: (r.cid = l.cid) -> Seq Scan on credit_card r Filter: f_leak(cnum) --- 1411,1417 ---- EXPLAIN (COSTS OFF) SELECT * FROM my_credit_card_normal WHERE f_leak(cnum); QUERY PLAN --------------------------------------------------------- ! Hash Unique Inner Join Hash Cond: (r.cid = l.cid) -> Seq Scan on credit_card r Filter: f_leak(cnum) *************** EXPLAIN (COSTS OFF) SELECT * FROM my_cre *** 1432,1438 **** --------------------------------------------------------------- Subquery Scan on my_credit_card_secure Filter: f_leak(my_credit_card_secure.cnum) ! -> Hash Join Hash Cond: (r.cid = l.cid) -> Seq Scan on credit_card r -> Hash --- 1432,1438 ---- --------------------------------------------------------------- Subquery Scan on my_credit_card_secure Filter: f_leak(my_credit_card_secure.cnum) ! -> Hash Unique Inner Join Hash Cond: (r.cid = l.cid) -> Seq Scan on credit_card r -> Hash *************** EXPLAIN (COSTS OFF) SELECT * FROM my_cre *** 1466,1472 **** -> Materialize -> Subquery Scan on l Filter: f_leak(l.cnum) ! -> Hash Join Hash Cond: (r_1.cid = l_1.cid) -> Seq Scan on credit_card r_1 -> Hash --- 1466,1472 ---- -> Materialize -> Subquery Scan on l Filter: f_leak(l.cnum) ! -> Hash Unique Inner Join Hash Cond: (r_1.cid = l_1.cid) -> Seq Scan on credit_card r_1 -> Hash *************** EXPLAIN (COSTS OFF) SELECT * FROM my_cre *** 1497,1503 **** -> Seq Scan on credit_usage r Filter: ((ymd >= '10-01-2011'::date) AND (ymd < '11-01-2011'::date)) -> Materialize ! -> Hash Join Hash Cond: (r_1.cid = l.cid) -> Seq Scan on credit_card r_1 -> Hash --- 1497,1503 ---- -> Seq Scan on credit_usage r Filter: ((ymd >= '10-01-2011'::date) AND (ymd < '11-01-2011'::date)) -> Materialize ! -> Hash Unique Inner Join Hash Cond: (r_1.cid = l.cid) -> Seq Scan on credit_card r_1 -> Hash diff --git a/src/test/regress/expected/select_views_1.out b/src/test/regress/expected/select_views_1.out index 5275ef0..81795d8 100644 *** a/src/test/regress/expected/select_views_1.out --- b/src/test/regress/expected/select_views_1.out *************** NOTICE: f_leak => 9801-2345-6789-0123 *** 1411,1417 **** EXPLAIN (COSTS OFF) SELECT * FROM my_credit_card_normal WHERE f_leak(cnum); QUERY PLAN --------------------------------------------------------- ! Hash Join Hash Cond: (r.cid = l.cid) -> Seq Scan on credit_card r Filter: f_leak(cnum) --- 1411,1417 ---- EXPLAIN (COSTS OFF) SELECT * FROM my_credit_card_normal WHERE f_leak(cnum); QUERY PLAN --------------------------------------------------------- ! Hash Unique Inner Join Hash Cond: (r.cid = l.cid) -> Seq Scan on credit_card r Filter: f_leak(cnum) *************** EXPLAIN (COSTS OFF) SELECT * FROM my_cre *** 1432,1438 **** --------------------------------------------------------------- Subquery Scan on my_credit_card_secure Filter: f_leak(my_credit_card_secure.cnum) ! -> Hash Join Hash Cond: (r.cid = l.cid) -> Seq Scan on credit_card r -> Hash --- 1432,1438 ---- --------------------------------------------------------------- Subquery Scan on my_credit_card_secure Filter: f_leak(my_credit_card_secure.cnum) ! -> Hash Unique Inner Join Hash Cond: (r.cid = l.cid) -> Seq Scan on credit_card r -> Hash *************** EXPLAIN (COSTS OFF) SELECT * FROM my_cre *** 1466,1472 **** -> Materialize -> Subquery Scan on l Filter: f_leak(l.cnum) ! -> Hash Join Hash Cond: (r_1.cid = l_1.cid) -> Seq Scan on credit_card r_1 -> Hash --- 1466,1472 ---- -> Materialize -> Subquery Scan on l Filter: f_leak(l.cnum) ! -> Hash Unique Inner Join Hash Cond: (r_1.cid = l_1.cid) -> Seq Scan on credit_card r_1 -> Hash *************** EXPLAIN (COSTS OFF) SELECT * FROM my_cre *** 1497,1503 **** -> Seq Scan on credit_usage r Filter: ((ymd >= '10-01-2011'::date) AND (ymd < '11-01-2011'::date)) -> Materialize ! -> Hash Join Hash Cond: (r_1.cid = l.cid) -> Seq Scan on credit_card r_1 -> Hash --- 1497,1503 ---- -> Seq Scan on credit_usage r Filter: ((ymd >= '10-01-2011'::date) AND (ymd < '11-01-2011'::date)) -> Materialize ! -> Hash Unique Inner Join Hash Cond: (r_1.cid = l.cid) -> Seq Scan on credit_card r_1 -> Hash diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql index 3430f91..38cc39c 100644 *** a/src/test/regress/sql/join.sql --- b/src/test/regress/sql/join.sql *************** update xx1 set x2 = f1 from xx1, lateral *** 1696,1698 **** --- 1696,1791 ---- delete from xx1 using (select * from int4_tbl where f1 = x1) ss; delete from xx1 using (select * from int4_tbl where f1 = xx1.x1) ss; delete from xx1 using lateral (select * from int4_tbl where f1 = x1) ss; + + -- + -- test planner's ability to change joins into their appropriate semi join + -- type + -- + + create table j1 (id int primary key); + create table j2 (id int primary key); + create table j3 (id int); + + insert into j1 values(1),(2),(3); + insert into j2 values(1),(2),(3); + insert into j3 values(1),(1); + + analyze j1; + analyze j2; + analyze j3; + + -- ensure join is changed to a semi join + explain (verbose, costs off) + select * from j1 inner join j2 on j1.id = j2.id; + + -- ensure join not changed when not an equi-join + explain (verbose, costs off) + select * from j1 inner join j2 on j1.id > j2.id; + + -- don't change, as j3 has no unique index or pk on id + explain (verbose, costs off) + select * from j1 inner join j3 on j1.id = j3.id; + + -- ensure left join is converted to left semi join + explain (verbose, costs off) + select * from j1 left join j2 on j1.id = j2.id; + + -- ensure right join is converted too + explain (verbose, costs off) + select * from j1 right join j2 on j1.id = j2.id; + + -- a clauseless (cross) join can't be converted + explain (verbose, costs off) + select * from j1 cross join j2; + + -- ensure a natural join is converted to a semi join + explain (verbose, costs off) + select * from j1 natural join j2; + + -- ensure distinct clause allows the inner to become a semi join + explain (verbose, costs off) + select * from j1 + inner join (select distinct id from j3) j3 on j1.id = j3.id; + + -- ensure group by clause allows the inner to become a semi join + explain (verbose, costs off) + select * from j1 + inner join (select id from j3 group by id) j3 on j1.id = j3.id; + + -- ensure a full join is not altered + explain (verbose, costs off) + select * from j1 full join j2 on j1.id = j2.id; + + drop table j1; + drop table j2; + drop table j3; + + -- test a more complex permutations of join conversions + + create table j1 (id1 int, id2 int, primary key(id1,id2)); + create table j2 (id1 int, id2 int, primary key(id1,id2)); + create table j3 (id1 int, id2 int, primary key(id1,id2)); + + insert into j1 values(1,1),(2,2); + insert into j2 values(1,1); + insert into j3 values(1,1); + + analyze j1; + analyze j2; + analyze j3; + + -- ensure there's no join conversion when not all columns which are part of + -- the unique index are part of the join clause + explain (verbose, costs off) + select * from j1 + inner join j2 on j1.id1 = j2.id1; + + -- ensure inner is converted to semi join when there's multiple columns in the + -- join condition + explain (verbose, costs off) + select * from j1 + inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2; + + drop table j1; + drop table j2; + drop table j3;
pgsql-hackers by date: