Brief
The maintained non-Numba conditional-join path currently chooses the first eligible non-equality predicate as its anchor. Predicate order can therefore make equivalent joins differ substantially in runtime and peak memory when one predicate is much more selective than another.
A local benchmark with two equivalent less-than conditions and keep=first showed the broad-first ordering becoming increasingly expensive compared with selective-first ordering:
- 1,000 rows: about 2x slower
- 3,000 rows: about 8.8x slower
- 10,000 rows: about 77x slower (about 100 ms versus 1.3 ms)
Goal
Research and implement a readable predicate-selection strategy that chooses a useful anchor before materializing candidate pairs. Possible approaches include:
- cheap selectivity estimates from column min/max values and distributions;
- exact or sampled candidate-count estimates;
- a conservative optimization limited to keep=first and keep=last;
- early rejection of predicates that would produce very broad candidate sets.
Correctness constraint
Anchor choice can affect the ordering of matches returned by keep=all. Any optimizer must preserve current row ordering as well as values, indexes, dtypes, extension-array behavior, and null semantics. This ordering constraint is why the optimization should not be folded into the result-materialization work in #1632 / #1638.
Benchmark and acceptance matrix
Cover at least:
- two or more eligible non-equality predicates with different selectivities;
- operators <, <=, >, and >=;
- keep=all, keep=first, and keep=last;
- sorted and unsorted inputs;
- dense, sparse, zero-match, and full-match cases;
- nullable and extension dtypes where supported.
Acceptance requires exact behavioral parity, including output ordering, with measurable improvement on badly ordered predicates and no material regression on already selective-first inputs. The implementation should remain understandable without relying on the deprecated Numba path.
Related work
Brief
The maintained non-Numba conditional-join path currently chooses the first eligible non-equality predicate as its anchor. Predicate order can therefore make equivalent joins differ substantially in runtime and peak memory when one predicate is much more selective than another.
A local benchmark with two equivalent less-than conditions and keep=first showed the broad-first ordering becoming increasingly expensive compared with selective-first ordering:
Goal
Research and implement a readable predicate-selection strategy that chooses a useful anchor before materializing candidate pairs. Possible approaches include:
Correctness constraint
Anchor choice can affect the ordering of matches returned by keep=all. Any optimizer must preserve current row ordering as well as values, indexes, dtypes, extension-array behavior, and null semantics. This ordering constraint is why the optimization should not be folded into the result-materialization work in #1632 / #1638.
Benchmark and acceptance matrix
Cover at least:
Acceptance requires exact behavioral parity, including output ordering, with measurable improvement on badly ordered predicates and no material regression on already selective-first inputs. The implementation should remain understandable without relying on the deprecated Numba path.
Related work
conditional_joinperformance #1415first/lastinconditional_join#1382