Route count_overlaps (LEFT JOIN + GROUP BY on INTERSECTS) through IE_JOIN with zero-fill

[conradbzura]

Description

A count_overlaps-style query — for each left interval, the count of overlapping right intervals, including zeros — is naturally written as a LEFT JOIN on INTERSECTS plus GROUP BY:

SELECT a.chrom, a.start, a."end", COUNT(b.chrom) AS n
FROM a LEFT JOIN b ON a.interval INTERSECTS b.interval
GROUP BY a.chrom, a.start, a."end"

The DuckDB IEJoin override (src/giql/expanders/intersects_duckdb.py) declines outer joins to the naive-predicate plan (_has_outer_join_intersects, ~line 503). The naive plan keeps the chrom = chrom equality, so DuckDB selects a HASH_JOIN on the 24-value chromosome key with the two inequalities as a post-filter — effectively a nested loop within each chromosome bucket, i.e. quadratic.

Measured (N = 1e6 per set, hg38 narrow peaks, single-threaded):

Plan	Operator	Time
current (LEFT JOIN + GROUP BY, naive)	HASH_JOIN + inequality filter	81 s
INNER IE_JOIN + GROUP BY + zero-fill	IE_JOIN	0.44 s
bioframe count_overlaps (reference)	—	0.67 s

Motivation

count_overlaps is one of the most common interval operations (it is bioframe's count_overlaps and bedtools coverage -counts). At scale it is ~180x slower than it needs to be and slower than the reference tools, purely because the zero-preserving LEFT join blocks the IEJoin path. This is the same underlying cause as the SEMI/ANTI slowdown tracked in #208 (DuckDB only picks IE_JOIN for INNER pure-inequality joins), split out per scope.

Expected Outcome

The LEFT-join-for-count pattern reaches IE_JOIN and is competitive with the reference tools. A viable rewrite: compute the per-chromosome INNER IE_JOIN, GROUP BY the left key to count matches, then LEFT JOIN that back onto the left table to zero-fill non-matching rows:

WITH hits AS (
  SELECT chrom, start, "end", count(*) AS n
  FROM (<per-chrom INNER IE_JOIN of a x b>) t
  GROUP BY 1, 2, 3
)
SELECT a.chrom, a.start, a."end", COALESCE(h.n, 0) AS n
FROM a LEFT JOIN hits h USING (chrom, start, "end")

Verified equivalent to the current plan's output (1,000,000 rows) at N = 1e6 in 0.44 s. Detecting this specific shape (LEFT join whose only use of the right side is inside COUNT/aggregates, with the left key in GROUP BY) and rewriting it is the main design question. Depends on / relates to #208.

Discovered by the benchmark suite (benchmarks/).