Discard ORDER BY/DISTINCT when an ANY/IN sublink is pulled up to a join
Hi,
When convert_ANY_sublink_to_join() turns an IN/ANY sublink -- or a
provably null-safe NOT IN, which becomes an anti join -- into a semi or
anti join, it currently leaves the sub-select's ORDER BY and DISTINCT
clauses in place. Neither can affect the result of a semi/anti join,
which depends only on whether a matching inner row exists, not on the
order of the inner rows or whether they are distinct.
simplify_EXISTS_query() already drops these clauses for EXISTS; the
ANY/IN path is just the one place that doesn't. The attached patch makes
it consistent: it discards ORDER BY and DISTINCT once we've committed to
the conversion.
if (subselect->limitOffset == NULL &&
subselect->limitCount == NULL &&
!subselect->hasDistinctOn)
{
subselect->distinctClause = NIL;
subselect->sortClause = NIL;
}
Besides saving a useless sort or de-duplication of the inner side, this
lets the sub-select become "simple" so that pull_up_subqueries() can
flatten it (see is_simple_subquery()) instead of leaving a separate
subquery. The effect is most visible for a correlated sub-select, e.g.
explain (costs off)
select * from tenk1 t
where t.hundred in (select b.ten from tenk2 b
where b.unique2 = t.unique1 order b
which today plans as a Nested Loop Semi Join over a Subquer
inner Sort is re-executed per outer row, and with the patch becomes a
plain Hash Semi Join.
The clauses are kept when the sub-select has LIMIT/OFFSET (
and DISTINCT do determine which rows are returned) or uses DISTINCT ON
(which selects particular rows in conjunction with ORDER BY
A semi/anti join's result is a function of the *set* of inn
(existence of a match), not their order or multiplicity. Removing
DISTINCT doesn't change that set or the presence of NULLs;
ORDER BY (absent LIMIT/OFFSET) doesn't change which rows are produced.
This holds regardless of how the inner rows are computed, s
safe with aggregates, window functions and set-returning functions in the
sub-select -- only the query-level sortClause is touched, n
own ORDER BY. The NOT IN -> anti join direction is reached only after the
existing nullability proofs, so it is unaffected. groupCla
alone on purpose, so no RTE_GROUP / hasGroupRTE cleanup is needed (unlike
simplify_EXISTS_query, which discards the whole targetlist)
Removing the clauses turns a forced de-duplication into a c
choice. For IN/semi joins the planner can still unique-ify the inner
(JOIN_UNIQUE_INNER) when that is cheaper, so the previous p
reachable; where it isn't (e.g. a semi join that short-circuits early)
the plan improves. For NOT IN/anti joins the planner adapt
shape (e.g. a Hash Right Anti Join) so the inner is not materialized into
a large hash, and dropping the forced dedup pass is typical
neutral-to-faster. As with any change that widens the plan space a
different plan could occasionally be cheaper -- anti joins
have no JOIN_UNIQUE-style inner-dedup fallback -- but I have not found a
case where the difference is more than marginal.
make check passes with no changes to existing expected outp
adds coverage to subselect.sql: that the DISTINCT and ORDER BY spellings
now plan like the plain ones, that LIMIT and DISTINCT ON ar
that aggregates and window functions are handled safely, and that both
the semi (IN) and anti (NOT IN) paths are exercised.
I searched the archives and didn't find a prior proposal fo
specific simplification; the closest related work is the general
subquery-unnesting discussion[1]/messages/by-id/67e353e8-c20e-7980-a282-538779edf25b@iki.fi, which is orthogonal to th
change.
Thoughts welcome.
Thanks,
Ewan Young
[1]: /messages/by-id/67e353e8-c20e-7980-a282-538779edf25b@iki.fi
Attachments:
v1-0001-Discard-ORDER-BY-and-DISTINCT-in-an-ANY-IN-sub-se.patchapplication/octet-stream; name=v1-0001-Discard-ORDER-BY-and-DISTINCT-in-an-ANY-IN-sub-se.patchDownload+319-1
Hello
I verified that the patch is generally faster in my benchmarks, with one exception:
anti joins with heavy duplication end up being significantly slower, for example:
create table ao (a int not null);
create table ai (k int not null);
insert into ao select g from generate_series(1,100000) g;
insert into ai select g % 50 from generate_series(1,2000000) g;
analyze ao;
analyze ai;
\timing on
explain (analyze, costs off, timing off, summary off)
select count(*) from ao where a not in (select distinct k from ai);
Which seems related to parallelization, as in these scenarios the patched version chooses a serial execution compared to the parallelized deduplication on master, and ends up being 2-4x slower. If I force it to use parallel workers, it ends up being faster even in these cases.
Thanks for benchmarking this, and for pinning down the anti-join case.
You're right. This is exactly the risk I flagged in the original mail --
that anti joins have no JOIN_UNIQUE-style inner-dedup fallback -- where I
said I hadn't yet found a case in which the difference was more than
marginal. You've found one. It comes down to an asymmetry between the
two join types: the simplification is reversible for a semijoin but not
for an antijoin.
v2 therefore restricts it to the semijoin (IN/ANY) path and leaves a
null-safe NOT IN -> antijoin completely untouched, so by construction
your
select count(*) from ao where a not in (select distinct k from ai);
plans exactly as on master -- the regression simply cannot arise. I
confirmed this directly: on the same data, v2 produces a plan identical
to master's for your query (the same parallel Unique over a
HashAggregate), so there is no performance change versus master. Only
the semijoin cases, where the consistent wins were, are changed from v1.
The reason for the asymmetry: a semijoin is algebraically equivalent to
an inner join whose inner side has been made unique on the join key,
A SEMI B == A JOIN unique(B)
and that equivalence is precisely what JOIN_UNIQUE_INNER implements. So
dropping the sub-select's DISTINCT in the semijoin case loses nothing:
the planner can reconstruct the de-duplication itself (by unique-ifying
the inner) whenever that is cheaper, so the removal just turns a forced
de-dup into a cost-based one.
An antijoin has no comparable equivalence -- "no matching row exists"
cannot be rephrased as an inner join over any transform of the inner
side -- which is exactly why there is no JOIN_UNIQUE path for it
(joinrels.c calls create_unique_paths() only for JOIN_SEMI). So once a
DISTINCT in a NOT IN sub-select is dropped, the de-duplication is gone
for good, and the planner is forced to push the full, heavily-duplicated
inner relation through the join -- which is where the parallel de-dup on
master was winning in your test.
The further point you raise -- that the serial-vs-parallel choice for
this antijoin looks suboptimal in its own right -- seems to me a
pre-existing parallel-costing matter independent of this patch, so I
haven't touched it here; might be worth a separate look.
v2 is attached. make check passes, and I extended the NOT IN coverage in
subselect.sql to pin down the new behavior directly: the DISTINCT/ORDER BY
spellings now keep their de-duplication/sort on the antijoin path rather
than being flattened like the IN spellings.
Happy to post the plan trees or before/after numbers for your 2M-row case
if that's useful.
Regards,
Ewan
Show quoted text
On Thu, Jun 11, 2026 at 6:33 AM Zsolt Parragi <zsolt.parragi@percona.com> wrote:
Hello
I verified that the patch is generally faster in my benchmarks, with
one exception:
anti joins with heavy duplication end up being significantly slower,
for example:create table ao (a int not null);
create table ai (k int not null);
insert into ao select g from generate_series(1,100000) g;
insert into ai select g % 50 from generate_series(1,2000000) g;
analyze ao;
analyze ai;
\timing on
explain (analyze, costs off, timing off, summary off)
select count(*) from ao where a not in (select distinct k from ai);Which seems related to parallelization, as in these scenarios the
patched version chooses a serial execution compared to the
parallelized deduplication on master, and ends up being 2-4x slower.
If I force it to use parallel workers, it ends up being faster even in
these cases.