DISJOIN breakpoint join is a quadratic HASH_JOIN + range filter (needs per-chromosome IEJoin)

[conradbzura]

Description

The DISJOIN breakpoint join scales quadratically. The __giql_dj_cuts CTE (src/giql/expanders/disjoin.py, _build_disjoin_sql) finds every reference breakpoint strictly inside each target interval with:

... FROM __giql_dj_tgt AS t JOIN __giql_dj_bp AS bp
    ON bp.chrom = t.chrom AND bp.pos > t.start AND bp.pos < t.end

DuckDB plans the chrom equality as a HASH_JOIN and applies the two position inequalities as a residual filter — effectively a nested loop within each chromosome bucket. This is the same pathology intersect had before #208, but DISJOIN is a separate expander and never received the IEJoin treatment. Because coverage-via-DISJOIN and subtract build on DISJOIN, they inherit the slowdown.

Measured (1 thread), found by the benchmark suite:

Query	1e5	1e6
DISJOIN(a) self-coverage	1.75 s	> 20 s (timeout)
DISJOIN(a, reference := b)	3.0 s	> 20 s (timeout)

Expected Behavior

DISJOIN should scale roughly log-linearly like the fixed intersect/count_overlaps paths, not quadratically.

Root Cause

DuckDB selects its fast IE_JOIN range-join operator only for INNER pure-inequality joins with no equality key. The breakpoint join carries the bp.chrom = t.chrom equality, so it falls to HASH_JOIN + filter.

Proposed fix

Partition the breakpoint join per chromosome so each partition is a pure-inequality INNER join DuckDB plans through IE_JOIN — the approach #208 used for column-to-column INTERSECTS. Validated prototype (per-chromosome UNION ALL of ... FROM (tgt WHERE chrom=c) t JOIN (bp WHERE chrom=c) bp ON bp.pos > t.start AND bp.pos < t.end):

	1e5	1e6
current	1.70 s	> 20 s
per-chrom IEJoin	0.067 s	0.58 s

Identical output (row counts match), EXPLAIN confirms IE_JOIN and no BLOCKWISE_NL_JOIN. Because GIQL does not know the data's chromosomes at transpile time, the per-chromosome UNION must be built at runtime (a string_agg over the distinct chromosomes, executed via a session-variable / query() indirection), which means DISJOIN's dialect="duckdb" output becomes a multi-statement form as the INTERSECTS override already is. Reusing the #208 per-chromosome machinery is the natural path.

[conradbzura]

Update: the proposed per-chromosome-IEJoin fix does not resolve the slowdown

Prototyping the full operator end-to-end (not just the isolated breakpoint join) shows the proposed fix does not make DISJOIN scale:

self-coverage DISJOIN(a) @1e6, 1 thread	result
current (single chrom-eq range join)	> 30 s (timeout)
per-chrom breakpoint join via getvariable	> 40 s (timeout), and slower than current at 1e5 (3.2 s vs 1.7 s)
per-chrom breakpoint join inlined statically (no getvariable)	> 50 s (timeout)

The isolated per-chromosome breakpoint join is fast (0.58 s @1e6, IE_JOIN), but once it feeds DISJOIN's downstream pipeline — the ~2.3M-row cut UNION, the LEAD window PARTITION BY (chrom, start, end), and the equi-join back to the target — the full operator stays quadratic/slow regardless. So the breakpoint join is not the (sole) bottleneck; the DISJOIN structure itself is. Reference-mode adds a second range join (the coverage EXISTS filter) on top.

Conclusion: the per-chromosome-IEJoin pattern that fixed #208/#209 does not transfer to DISJOIN. Making DISJOIN scale needs a rethink of the operator's algorithm (e.g. a global per-chromosome sweep that forms atomic segments once and assigns targets without a per-target range join, plus a sweep-based coverage filter), which is a larger, separate design effort with uncertain payoff — not the localized fix this issue proposed. Recommdending this issue be re-scoped to "investigate a sweep-based DISJOIN" rather than the IEJoin rewrite.