adriangb opened a new issue, #25438: URL: https://github.com/apache/datafusion/issues/25438
### Is your feature request related to a problem or challenge? A correlated `NOT IN` whose correlation includes an equality is slower than the same query without that equality, and its cost grows with the square of the table size. An equality correlation gives the null-aware hash join a correlation scope key. The key should make the query cheaper, because the candidate (build row x probe row) pairs then come from a hash lookup instead of the full cross product. Today it makes the query more expensive. **How to reproduce** (`datafusion-cli`, release, after https://github.com/apache/datafusion/pull/25339): ```sql CREATE TABLE outer_t AS SELECT value AS id, CASE WHEN value % 2 = 0 THEN NULL ELSE value END AS id_n50, value % 1000 AS z, value % 16 AS k FROM range(0, 100000); CREATE TABLE inner_t AS SELECT value * 2 AS id_n0, value % 1000 AS z, value % 16 AS k FROM range(0, 100000); -- (a) non-equality correlation only SELECT count(*) FROM outer_t o WHERE o.id_n50 NOT IN (SELECT i.id_n0 FROM inner_t i WHERE i.z < o.z); -- (b) the same, plus an equality correlation on k SELECT count(*) FROM outer_t o WHERE o.z > 900 OR o.id_n50 NOT IN (SELECT i.id_n0 FROM inner_t i WHERE i.k = o.k AND i.z < o.z); ``` Query (a) takes 24 ms. Query (b), which has 16 times less work to do, takes 412 ms. This is the `null_aware_join` benchmark suite (#25386), Q06 and Q08, at three sizes. Apple M4 Pro, median of 3 runs. DuckDB 1.5.2 on the same tables is given for scale. Both engines return the same results. | `NAJ_ROWS` | DF Q06 | DF Q08 | DF Q08/Q06 | DuckDB Q06 | DuckDB Q08 | DuckDB Q08/Q06 | |---|---|---|---|---|---|---| | 10,000 | 1 ms | 12 ms | 12x | 114 ms | 22 ms | 0.19x | | 30,000 | 1 ms | 38.5 ms | 38x | 329 ms | 49.7 ms | 0.15x | | 100,000 | 13 ms | 418.5 ms | 32x | 1110 ms | 147 ms | 0.13x | The equality correlation makes the query about 7 times cheaper in DuckDB. In DataFusion it makes the query more than 10 times more expensive. DataFusion is much faster than DuckDB for all other queries of this suite, but it is slower for this one from about 100,000 rows. ### Describe the solution you'd like A correlated null-aware join marks a build row UNKNOWN when a candidate pair passes the join filter, and the row stays UNKNOWN. The join can thus ignore the build rows that are already marked. https://github.com/apache/datafusion/pull/25339 does this for the path that has no scope key: it drops the marked build rows after each chunk of pairs and stops the pairing when no unmarked build row is left. At the default benchmark sizes, this takes Q06 from 20.6M candidate pairs to 240K. The scope-key path does not get this. It removes the marked build rows only after the hash lookup produced the pairs, so the enumeration still costs the same. At the default sizes, Q08 enumerates 6.25M pairs and keeps 86K of them. The fix is to narrow the lookup itself with the UNKNOWN bitmap, so that a marked build row does not produce candidate pairs at all. ### Describe alternatives you've considered For each probe batch, compare the number of unmarked build rows with the expected number of lookup pairs, and pair through the cross product when the unmarked rows are few. That path already stops early. It would then have to apply the scope-key equality itself, because the equality is a join key and not part of the join filter. ### Additional context The behavior is in `mark_null_candidates_for_probe_batch` in `datafusion/physical-plan/src/joins/hash_join/stream.rs`. The gap is not new. It became visible because #25339 makes the other correlated shapes fast. This issue tracks the follow-up that the review of that PR asked about. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
