viirya opened a new issue, #26088: URL: https://github.com/apache/datafusion/issues/26088
### Is your feature request related to a problem or challenge? A multi-column `(a, b) NOT IN (SELECT x, y ...)` (#25737, #19857) plans as a null-aware hash join that decides UNKNOWN per build row. Without correlation keys, every row with a NULL in any tuple element is paired with every row on the other side, and each pair is checked element by element for a definite mismatch. The cost grows with the product of the two sides. @comphead measured it in https://github.com/apache/datafusion/pull/19857#discussion_r4106477526, with equal row counts on both sides and no matches: | rows per side | nullable, no NULLs | 10% NULL in subquery | 10% NULL in outer | |---|---|---|---| | 20k | 1 ms | 96 ms | 68 ms | | 40k | 1 ms | 270 ms | 221 ms | | 80k | 2 ms | 1.27 s | 1.23 s | | 160k | 3 ms | 4.00 s | 5.15 s | ### Describe the solution you'd like A tuple element that is NOT NULL on both sides can never make the comparison UNKNOWN. Such an element could act as a correlation scope key instead of a value key, so the hash lookup on the scope keys narrows the candidate pairs, as it already does for correlated scalar `NOT IN`. For example, in `(a, b) NOT IN (SELECT x, y ...)` with `b` and `y` NOT NULL, a NULL `a` would only be paired with the subquery rows whose `y` equals its `b`. This needs the value keys reordered so that the NOT NULL elements follow the nullable ones (`HashJoinExec::null_aware_value_keys` counts only the leading value keys), or a way to mark individual keys as scope keys. ### Describe alternatives you've considered Building the join on the subquery side instead (see the related issue on a multi-key null-aware `RightAnti`), which also avoids keeping the outer side in memory. ### Additional context The `null_aware_join` benchmark suite has Q10 to Q12 for these shapes (no NULLs, NULLs in the subquery, NULLs in the outer side). -- 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]
