Take the outer-join decomposition for expression projections by NULL-substituting the null side's leaf columns #243

Description

The outer-join decomposition (#95) declines any LEFT / RIGHT JOIN ... ON a.interval INTERSECTS b.interval whose SELECT list contains an expression. Every projection must be a bare qualified column. #109 taught the INNER path to rebuild scalar expressions, and the #223 PR body predicted that -wao "unblocks with #109". It does not. Measured on origin/main at 6bb3479, which includes both merges, and reproduced by three independent runs:

INNER + plain cols               vars=1  IEJoin
INNER + scalar expr (#109)       vars=1  IEJoin
INNER + CASE both sides          vars=1  IEJoin
LEFT  + plain cols (#95)         vars=2  IEJoin
LEFT  + expr on preserved only   vars=0  DECLINES     -- a.start + 1
LEFT  + expr on null side only   vars=0  DECLINES     -- b.start + 1
LEFT  + expr spanning sides      vars=0  DECLINES     -- GREATEST(a.start, b.start)
LEFT  + CASE (the -wao shape)    vars=0  DECLINES

vars counts SET VARIABLE __giql_iejoin_ statements in the transpiled output; the decomposition emits two, the INNER path one, the naive plan zero. Even an expression that touches only the preserved side declines.

The shape that matters is bedtools intersect -wao, one of the two benchmarked intersect modes that still do not reach IE_JOIN. The other, -u -s, engages the dialect but its equality residual collapses the inner join to HASH_JOIN, which is #98. This one never engages the dialect at all:

SELECT a.chrom, a.start, a."end", b.chrom, b.start, b."end",
       CASE WHEN b.chrom IS NULL THEN 0
            ELSE LEAST(a."end", b."end") - GREATEST(a.start, b.start) END AS ov
FROM a LEFT JOIN b ON a.interval INTERSECTS b.interval

On main this transpiles to the naive predicate and plans as HASH_JOIN on the chromosome key with the position inequalities as a residual filter, which is quadratic. The same query with the CASE removed takes the decomposition and reaches IE_JOIN in both halves.

There is no workaround spelling. Hoisting the CASE into an outer SELECT over a derived table or a CTE also declines — the dialect only fires on a top-level join, INNER included, so wrapping the LEFT JOIN loses the fast path before the projection is even considered (#110). A user has to choose between the fast path and the ov column.

Motivation

The decline is in _match_outer_join_decomposition, which classifies each SELECT item by hand rather than through the _classify_projection machinery #109 added:

if (not isinstance(target, exp.Column)
        or isinstance(target.this, exp.Star)
        or not target.table):
    return None

Letting expressions through the matcher is not the whole fix. The unmatched half and the NULL-chromosome branch in _build_outer_join_parts fill the null side by output position — NULL AS <output name> for every position attributed to the other side. That rule is correct for a bare column and wrong for an expression. CASE WHEN b.chrom IS NULL THEN 0 ... must produce 0 on an unmatched row, and positional fill produces NULL.

The general rule is to substitute NULL for each of the null side's leaf columns and let the expression evaluate. On a bare column the two rules coincide, so nothing that passes today changes. On -wao's CASE they diverge by exactly the value bedtools reports.

This is the intersection of the two families the laggard analysis identified — the join is already accelerated by #95 and the projection rebuild already exists from #109 — so it is smaller than either. It touches no partition machinery and adds no gate class.

Hand-written SQL for this decomposition, measured in July before either issue landed, ran -wao in 0.223s at 1e5 rows per side against 0.904s on the naive plan, and in 1.58s at 1e6 where the naive plan does not finish. Those are figures for the target shape, not for GIQL output; GIQL has never emitted it.

Expected outcome

• A LEFT / RIGHT outer-join INTERSECTS whose SELECT list contains a rebuildable scalar expression (per _is_rebuildable_scalar) takes the decomposition and returns the same rows, column names, and column types as the naive plan.
• In the unmatched half and the NULL-chromosome branch, every leaf column belonging to the null side is replaced by NULL and the expression is re-emitted around the substitution, rather than the output position being filled with NULL. The ANTI half projects the preserved side's leaf columns that the SELECT list references, not the expressions themselves.
• _match_outer_join_decomposition partitions SELECT items by leaf set: an item whose leaves are all preserved-side is a preserved item; an item touching any null-side leaf is a null-side item. _OuterJoinShape's two index tuples keep their meaning.
• A NULL-substituted expression evaluates to a narrower type than the matched half produces — COALESCE(NULL, 0) is INTEGER where COALESCE(b.start, 0) is BIGINT. DuckDB unifies UNION ALL branches to the widest type regardless of order, so this does not surface for any shape tested, but the differential comparison must cover result schema rather than rows alone so that it cannot surface silently. The existing _rows_and_schema helper already does.
• Whether substitution happens on the sqlglot tree or in the rendered string is stated and pinned. After substitution -wao's CASE reads CASE WHEN NULL IS NULL THEN 0 ..., which folds to a literal 0; that is correct, but a tree-level fold has to pass _renders_faithfully_for_duckdb, and a string-level one has to be produced by the same rewrite the INNER path uses.
• A bedtools intersect -wao oracle is added to tests/integration/bedtools/test_intersect.py — none exists today, though bedtools_wrapper.py already supports the flag — running against dialect="duckdb" and asserting sql.count("SET VARIABLE __giql_iejoin_") == 2, so it cannot pass on a silent fallback to the naive plan.
• The two tests that pin today's decline are inverted rather than left beside the new coverage: test_transpile_should_decline_outer_join_when_projection_is_expression (ids left_wao_case, left_arithmetic, right_greatest; full_arithmetic must keep declining) and test_query_should_match_naive_plan_when_declined_wao_expression_runs.
• Unit coverage for the three shapes in the table above that decline today, with the null-side-only case using an expression that is non-NULL under substitution (COALESCE(b.start, 0)), since that is the case positional fill gets wrong. The hypothesis draw in TestTranspileDuckDBIEJoinOuterJoinDecomposition projects bare columns only; it should draw from _expression_trees, which the INNER and SEMI / ANTI property tests already use.
• Aggregates, window functions, bare literals, and every other _classify_projection verdict other than "column" and "scalar" continue to decline the decomposition, with a test pinning that. This is about the decomposition's gate only: LEFT JOIN ... GROUP BY with a COUNT keeps taking the count_overlaps path, which dispatches first.
• The duplicate-name gate on preserved output names is restated for the new contract. The ANTI half re-projects preserved leaf columns rather than output names, so the collision that matters becomes a leaf-name collision across preserved items, still compared case-insensitively.
• Three documentation sites are corrected: the sentence at docs/transpilation/performance.rst:491 that says any outer join carrying an expression projection takes the naive plan, the _match_outer_join_decomposition docstring that names the -wao CASE as a shape that "still declines here", and the Support LEFT/RIGHT JOIN in the DuckDB IEJoin dialect by decomposing the outer join into INNER pairs plus unmatched rows — Closes #95 #223 description's claim that Keep the DuckDB IEJoin plan for scalar expression projections instead of declining to the naive plan #109 would unblock it. The migration recipe at docs/recipes/bedtools-migration.rst:242 spells -wao as SELECT a.*, b.*, which is a star projection and stays on the naive plan after this change; either rewrite it with explicit columns or say so beside it.

Additional context

Of the twelve benchmarked bedtools intersect modes, ten now reach IE_JOIN on main. The two that do not are this one and -u -s (#98). Closing both puts every mode on the fast path.

The INNER rebuild's leaf-substitution mechanism is the model: _resolve_projections already projects every leaf as a __giql_p<n> inner column and re-emits the tree on the outer SELECT, and the two replace() closures in _rewrite_refs_for_per_chrom_subquery and _rewrite_refs_for_wrapper_relation show the column-rewrite idiom. The unmatched half needs the same walk with a different substitution. The NULL-chromosome branch is the third site and the easiest to get wrong: it selects straight from the preserved base table and today renders each SELECT item's column directly, so an expression there must be re-emitted in full over the substituted leaves, not reduced to its leaf.

The outer-join matcher produced four defects in the review that preceded #95's merge (case-insensitive name collision, dropped QUALIFY, unparseable TABLESAMPLE, NULL-chromosome row loss), each documented in the #223 description and pinned in source comments. Widening it again should go through the same review rather than a quick relaxation.