DuckDB INTERSECTS SEMI/ANTI joins fall back to BLOCKWISE_NL_JOIN instead of IE_JOIN (~80x slowdown)

[conradbzura]

Description

The DuckDB IEJoin override (src/giql/expanders/intersects_duckdb.py) rewrites a column-to-column INTERSECTS join into a per-chromosome dynamic-SQL pattern, expecting DuckDB to plan each partition through its range-join family (IE_JOIN). This works for INNER joins but not for SEMI/ANTI joins: the per-chromosome template emits SEMI JOIN / ANTI JOIN (_build_sql, the join_keyword map ~line 1034), and DuckDB does not use IE_JOIN for semi/anti inequality joins — it plans them as BLOCKWISE_NL_JOIN (a nested loop), which is quadratic.

Measured on a synthetic narrow-peaks pair (N = 1e6 each, hg38, realized Jaccard ~0.17), single-threaded, DuckDB tables:

Query	Current plan	Current	Corrected plan	Corrected
intersect -u (SEMI)	BLOCKWISE_NL_JOIN	38 s	IE_JOIN via EXISTS	0.46 s
intersect -v (ANTI)	BLOCKWISE_NL_JOIN	~38 s	IE_JOIN via NOT EXISTS	0.48 s
intersect (INNER)	IE_JOIN (already correct)	0.48 s	—	—

For reference, bioframe does the same overlap in 0.46 s single-threaded; bedtools intersect -u in 0.71 s (E2E). The corrected GIQL plans are competitive single-threaded and faster multi-threaded (~0.18-0.20 s at 14 threads).

The analogous count_overlaps (LEFT JOIN ... GROUP BY) slowdown — declined to the naive plan and executed as a HASH_JOIN + inequality filter — shares the same root cause but is tracked separately as a follow-up (see linked issue).

Expected Behavior

INTERSECTS SEMI/ANTI joins should reach DuckDB's IE_JOIN operator and scale like the INNER path, rather than degrading to a nested loop. The class docstring's claim that "SEMI / ANTI engage DuckDB's IE_JOIN with the corresponding semi/anti semantics" (and the matching text in docs/transpilation/performance.rst) is currently inaccurate.

Root Cause

DuckDB's IE_JOIN (and PIECEWISE_MERGE_JOIN) operators are selected only for INNER joins with pure-inequality predicates. When the per-chromosome subquery uses SEMI JOIN / ANTI JOIN with a.start < b.end AND a.end > b.start, DuckDB's optimizer instead selects BLOCKWISE_NL_JOIN. Verified via EXPLAIN on a single chromosome (43k x 43k):

• SEMI JOIN -> BLOCKWISE_NL_JOIN (5.08 s)
• ANTI JOIN -> BLOCKWISE_NL_JOIN
• WHERE EXISTS (SELECT 1 FROM b WHERE <overlap>) -> IE_JOIN (0.034 s)
• WHERE NOT EXISTS (...) -> IE_JOIN (RIGHT_ANTI)
• INNER JOIN -> IE_JOIN

Proposed Fix

In the per-chromosome template (_build_sql), for the left-only shapes, emit a correlated subquery against b instead of a SEMI/ANTI join keyword:

• SEMI: SELECT <left cols> FROM (...WHERE chrom=<c>) a WHERE EXISTS (SELECT 1 FROM (...WHERE chrom=<c>) b WHERE a.start < b.end AND a.end > b.start [AND <residuals>])
• ANTI: the same with NOT EXISTS.

This preserves exact SEMI/ANTI semantics — one row per qualifying left row, no dedup-on-projection hazard — while reaching IE_JOIN. Verified at N = 1e6: SEMI via EXISTS = 535,768 rows in 0.46 s; ANTI via NOT EXISTS = 464,232 rows; the two partition |A| exactly (535,768 + 464,232 = 1,000,000). The existing ANTI left-distinct chromosome-partition logic and the WHERE-residual outer-filter handling (#200) compose unchanged. Update docs/transpilation/performance.rst and the class docstring to match.

Discovered by the benchmark suite (benchmarks/) on its first full scaling-ladder run.