Extending EXISTS Sublink Pull-up to Handle JoinExpr Quals

The Core Problem

PostgreSQL's convert_EXISTS_sublink_to_join() (in subselect.c, invoked from pull_up_sublinks_qual_recurse()) transforms correlated EXISTS (SELECT ... WHERE ...) subqueries into semi-joins, which is one of the planner's most impactful sublink flattening transformations. It enables the whole join search space — including hash/merge semi-joins, join reordering, and index-driven parameterized nested loops — rather than re-executing the subplan per outer tuple.

The transformation hinges on extracting the correlating qual (a qual in the subquery that references varlevelsup = 1 vars) so it can be lifted into the parent query's jointree as the semi-join's ON condition. Historically, this extraction has looked only at subselect->jointree->quals — i.e., the top-level WHERE clause of the subquery. That is a syntactic, not semantic, limitation: the comment in the function explicitly acknowledges this:

"We could theoretically also remove top-level plain JOIN/ON clauses, but it's probably not worth the trouble."

Alena Rybakina's thread directly challenges that "not worth the trouble" assumption. The motivating asymmetry is:

-- Pulls up to a Semi Join (correlation is in WHERE):
SELECT * FROM ta WHERE EXISTS (SELECT * FROM tb, tc WHERE ta.id = tb.id);

-- Does NOT pull up (correlation is in ON-clause of an explicit JOIN):
SELECT * FROM ta WHERE EXISTS (SELECT * FROM tb JOIN tc ON ta.id = tb.id);

The two are semantically equivalent (both are inner joins with a Cartesian shape once ta.id = tb.id is factored out), but only the first benefits from the semi-join transformation. The second falls back to a correlated SubPlan executed per outer tuple — a potentially large performance cliff.

Why This Is Architecturally Tricky

Lifting quals out of a JoinExpr->quals (as opposed to FromExpr->quals at top level) is not free:

1. Outer-join null-extension semantics. A qual sitting on a LEFT JOIN's ON-clause cannot in general be hoisted to WHERE: it can produce nulls rather than eliminate rows. The same applies to nullable sides of RIGHT/FULL joins. Any candidate qual must be shown to reside on a non-nullable side relative to every outer join above it in the subquery's jointree. This is analogous to the reduce_outer_joins/pull_up_sublinks invariants already maintained elsewhere in the planner.

2. Reference classification. Quals may reference (a) only outer-query vars (varlevelsup = 1), (b) only subquery vars, or (c) both. Only those that touch outer-query vars are candidates for lifting into the semi-join's condition; purely-inner quals must stay on the JoinExpr where they belong; mixed quals are the interesting case that drive the transformation (they become the join condition of the new semi-join).

3. preprocess_expression staging. convert_EXISTS_sublink_to_join is called mid-way through the parent's preprocess_expression() pass. Pulled-up expressions must be retro-fitted through the preprocessing steps that the outer query has already completed (constant folding, canonicalization, etc.), while the subquery-local parts need their varlevelsup decremented because the subquery is about to be flattened. Alena explicitly called this out in the 2025-02-09 message.

4. Safety predicates: volatility, SRFs, sublinks-within-quals, aggregates, window functions, CASE/OR expressions whose selectivity behavior changes under join-reordering — all of these are potential correctness or regression hazards (Ilya Evdokimov raised OR/CASE/nested-sublink concerns in April 2025).

Evolution of the Approach

The patch went through at least four distinct designs:

V1 (December 2024). Minimal extension: collect quals from both jointree->quals and jointree->fromlist (descending into JoinExprs), AND them together, and feed them into the existing pull-up path. Immediately surfaced bugs: constant quals on inner tables (tc.aid = 1) caused wrong results because contain_vars_of_level(whereClause, 1) returned false for them, but they still needed to remain as filters on the inner side rather than be silently dropped.

V2 (January–February 2025). Split quals into "parent-referencing" vs "subquery-local" sets, handle vars differently per set (decrement varlevelsup for inner vars, prepare outer vars for RTE-lifting), and introduce a newWhere for ambiguous expressions. This broke postgres_fdw tests — foreign-table LIMIT handling is sensitive to subquery shape.

V3 (April 2025). Additional failures on ANY-array quals, boolean columns (tb.is_active), and IS NULL/IS NOT NULL predicates exposed that the safety walker needed to be comprehensive (volatility, supported node types) rather than enumerating what to pull. Alena decided to introduce an expression-tree walker dedicated to "is this safely hoistable?" gating.

V4 (September 2025). Ilya Evdokimov proposed a structural refactor: rather than bolting more branches onto convert_EXISTS_sublink_to_join, introduce a parallel convert_EXISTS_sublink_to_lateral_join modeled on convert_ANY_sublink_to_join. This separates the two pull-up strategies and keeps each function focused. Alena pivoted to a mutator-based implementation.

V5 (October 2025 → 2026). Alena (writing now from lena.ribackina@yandex.ru) herself pushed back on the lateral-join approach: forming a LATERAL join effectively forces a nested-loop shape and forecloses hash/merge semi-join plans. Her test with enable_nestloop = off showed the planner could not switch strategies because lateral parameters preclude hash/merge. This is a significant observation — LATERAL is a correctness-preserving but plan-space-restricting transformation, and the whole point of semi-join flattening is to open plan space.

Peter Petrov's Review (May 2026) — The Current State of Criticism

Peter Petrov's review is the most architecturally incisive. Key points:

1. Cleaner separation of concerns. Detach jointree and whereClause from the subselect temporarily, run the hoistability checks, then re-attach. This avoids the "collect everything into a context, then decide" pattern.

2. Drop get_relids_in_jointree()/nullable_above bookkeeping. Since jointree traversal is top-down, nullability is a simple inherited boolean: rarg_is_nullable = is_nullable_side || type IN (FULL, LEFT), larg_is_nullable = is_nullable_side || type IN (FULL, RIGHT). He also suspects FULL JOIN is not correctly handled — a meaningful correctness concern.

3. "Mutator" is the wrong abstraction. expression_tree_mutator is for whole-expression rewriting including subquery descent. Here the patch only walks the top jointree of a single query level — a simple recursive traversal with three parameters (node, is_nullable_side, output list) is both adequate and clearer.

4. Don't call canonicalize_qual(). It will be invoked later in the normal preprocess_expression → canonicalize_qual → find_duplicate_ors path. Calling it early is both redundant and makes reasoning about invariants harder. This is a correct internals observation.

5. Unexplained plan change. A regression-test change from Merge Anti Join to Hash Anti Join on tt4x — this is the kind of "why did an unrelated plan flip?" signal that usually indicates either cost model perturbation from extra baserels being introduced, or accidental changes to outer-join reduction.

6. A remaining gap. EXISTS (SELECT ... FROM tenk2 B, (SELECT f.hundred FROM (SELECT A.hundred) AS f) AS v ...) does not pull up because the inner (SELECT A.hundred) RTE_SUBQUERY is not flattened before pull_up_sublinks() runs. Peter suggests this might be solvable in SS_process_sublinks() but explicitly defers it.

Key Technical Insights

Insight 1: The WHERE-vs-ON asymmetry is a syntactic artifact

Semantically, FROM a, b WHERE p and FROM a JOIN b ON p are identical for inner joins. The planner's sublink-flattening paths should be oblivious to which form the user wrote. This patch is essentially normalizing that syntactic distinction at the sublink-pull-up stage, on par with what reduce_outer_joins / inner-join flattening already does later in planning.

Insight 2: LATERAL is a plan-space hazard, not a solution

Ilya's suggestion to model the transformation on convert_ANY_sublink_to_join (which produces LATERAL semi-joins) is intuitive but wrong in the general case. Alena's October 2025 test demonstrates empirically that lateral parameterization blocks hash/merge semi-join — exactly the plans that make this transformation worthwhile for large inputs.

Insight 3: Null-extension safety requires side-aware traversal

Hoisting a qual from an outer-join's ON-clause is only safe when the qual's variables all sit on non-nullable sides relative to every enclosing outer join. Peter's observation that this collapses to two inherited booleans is correct and is the same machinery used in reduce_outer_joins style logic.

Insight 4: Do one thing, and let the rest of preprocess_expression run

Calling canonicalize_qual inside a sublink transformer couples the pass to downstream passes. The planner's preprocess phases are carefully ordered; short-circuiting them locally tends to produce subtle bugs (double-canonicalization, varlevelsup mismatches).

Insight 5: The real cost question is unsolved

Alena's own June 2025 example shows a case where the pulled-up plan is slower than the SubPlan: when the EXISTS subquery's inner join produces a huge intermediate that the outer filter would have short-circuited. There's no framework in the thread for deciding when to apply the transformation — it's treated as unconditionally beneficial. This remains an open design question.

Assessment

The feature is clearly desirable and fills a real optimization gap. After 1.5+ years and multiple rewrites, however, the patch has accumulated complexity (mutator + context struct + nullability tracking + safety walker + qual rewriting) disproportionate to its stated goal. Peter's review argues convincingly that a tighter design — simple top-down jointree traversal with inherited nullability, collecting hoistable JoinExpr/FromExpr nodes, replacing their quals with true, and folding the collected predicates into the WHERE — would be both shorter and easier to verify. The FULL JOIN concern and the unexplained Merge→Hash plan change are correctness issues that must be resolved before this is committable.