Do not scan index in right table if condition for left join evaluates to false using columns in left table

First seen: 2024-12-07 18:30:46+00:00 · Messages: 16 · Participants: 5

Latest Update

2026-06-01 · claude-opus-4-6

Deep Technical Analysis: Optimizing Nested Loop Left Joins by Short-Circuiting Inner Scans

The Core Problem

When PostgreSQL executes a Nested Loop Left Join where the join condition (ON clause) contains predicates referencing only the outer (non-nullable) table, the executor unnecessarily scans the inner relation even when those predicates are guaranteed to evaluate to false for a given outer row.

Consider:

SELECT * FROM parent p LEFT JOIN child c ON p.id = c.id AND p.dtype = 'B' WHERE p.id = 1;

The predicate p.dtype = 'B' references only the outer table (parent). If the outer row has dtype = 'A', the join condition will inevitably fail regardless of what the inner scan returns. Yet PostgreSQL still performs the index scan on child — wasted I/O and CPU.

Why This Can't Simply Be Pushed Down

The critical semantic distinction that makes this non-trivial: this is NOT equivalent to moving the condition to WHERE. In a LEFT JOIN, when the ON condition fails, the outer row is still emitted with NULLs for the inner columns. Moving p.dtype = 'B' to WHERE would eliminate outer rows entirely — a semantic change. Tom Lane immediately identified this constraint, and Andres Freund acknowledged his initial suggestion of pushdown was incorrect.

The existing optimizer already handles the symmetric case: conditions in the ON clause that reference only the nullable (inner) side are recognized and pushed down (since they can safely filter inner rows without affecting outer row emission). But the non-nullable-side-only case was never implemented because it's semantically different — you can't filter outer rows, you can only skip the inner scan.

Real-World Prevalence

This pattern is not merely academic:

  1. Hibernate/JPA ORM — The treat() function for polymorphic queries with fetched associations generates exactly this pattern automatically
  2. Product catalog systems — Tables with category-specific detail tables joined conditionally (vehicles, phones, etc.)
  3. PostgreSQL's own codebase — psql's describeOneTableDetails() and pg_dump's getTables() contain similar patterns

Proposed Solutions

Approach 1: Executor-Level NestLoop Modification (Lepikhov/Petrov)

The initial patch by Andrei Lepikhov and Petr Petrov modifies the executor directly:

  1. Planning phase: In create_nestloop_path(), detect RestrictInfo clauses whose required relids only reference the outer side. Store these separately as rhs_joinrinfo.
  2. Plan creation: In make_nestloop(), remove these clauses from joinqual and store them in a new rhs_joinqual field.
  3. Execution: In ExecNestLoop(), evaluate rhs_joinqual after fetching the outer tuple but before fetching any inner tuple. If false, immediately emit the outer row with NULL inner columns, skipping the inner scan entirely.
  4. EXPLAIN: Introduces "Outer Tuple Filter" as a new filter type with a nunmatched counter in Instrumentation.

Tradeoffs: Touches multiple subsystems (planner, executor node, EXPLAIN). Adds new executor code paths specifically for outer joins in nestloop. Creates new node-level state that's only useful in this specific scenario.

Approach 2: Gating Result Node (Andres Freund's Suggestion, Lepikhov's 2026 Patch)

Instead of modifying the nestloop executor, inject a Result node with a One-Time Filter above the inner side of the parameterized nested loop:

Nested Loop Left Join
  ->  Seq Scan on products p
  ->  Result
        One-Time Filter: (p.type = 'v'::text)
        ->  Index Scan using vehicles_pkey on vehicles v
              Index Cond: (id = p.id)

The Result node evaluates the outer-only predicate first. When false, it returns no rows without ever invoking the child Index Scan. This leverages existing executor machinery — Result nodes with one-time filters are already implemented.

Tradeoffs:

Key Design Decisions and Disagreements

Applicability to Other Join Types

Lepikhov initially proposed handling this for Hash Join and Merge Join as well. This was firmly rejected by both Andres and Tom Lane:

Cost Model Implications

The 2026 patch from Lepikhov raises whether this should be integrated into the cost model via a new Path node. Currently, the Result node injection happens after path selection. If done at the Path level, the optimizer could cost-compare "gated nested loop" vs. other join strategies. Lepikhov prefers the simpler post-hoc approach unless evidence shows the Path-level change benefits other optimizations.

GUC Control

Lepikhov explicitly stated no GUC should be needed — the optimization should always be beneficial when applicable, as the Result node evaluation cost is negligible compared to an unnecessary index scan.

Architectural Implications

The "gating Result node" approach is architecturally elegant because it composes existing plan node semantics rather than adding special-case logic. It's analogous to how PostgreSQL already uses Result nodes for:

The key insight is that a parameterized inner path in a nested loop can be "gated" by predicates that only depend on parameters from the outer side. The Result node re-evaluates its One-Time Filter each time its parameters change (i.e., each new outer row), making it a natural fit for this per-outer-row gating behavior.

Current Status (as of May 2026)

Lepikhov's updated patch demonstrates the Result-node approach working correctly with significant scan reduction (from 10036 inner scans down to ~5000 in the benchmark case). Outstanding work includes: