viirya commented on code in PR #26214:
URL: https://github.com/apache/datafusion/pull/26214#discussion_r4418716218
##########
datafusion/optimizer/src/decorrelate_predicate_subquery.rs:
##########
@@ -929,6 +934,38 @@ fn build_join(
}
let left = projected_left.as_ref().unwrap_or(left);
+ // The first `V` keys of a null-aware join are its `NOT IN` value keys.
+ //
+ // A tuple element that cannot be NULL in scope on either side never makes
+ // the tuple comparison UNKNOWN: compared with a definite value it is
either
+ // equal, which leaves the other elements to decide, or a definite
mismatch,
+ // which makes the comparison FALSE whatever the other elements are. It
+ // therefore only selects which subquery rows a NULL in another element is
+ // compared with, which is what a correlation scope key does. Moving such
+ // elements after the ones that can be NULL turns them into scope keys, so
+ // the hash join finds the rows a NULL-valued row is compared with through
a
+ // hash lookup instead of pairing it with every row of the other side
+ // (<https://github.com/apache/datafusion/issues/26088>).
+ //
+ // A null-aware tuple has at least one element that can be NULL, so `V` is
+ // at least one. With exactly one, the join is a scalar `NOT IN` on that
+ // element, correlated by the other elements.
+ let null_aware_value_keys = if null_aware && in_values.len() > 1 {
+ let (nullable, non_nullable): (Vec<_>, Vec<_>) = in_values
+ .into_iter()
+ .zip(elements_may_be_null)
+ .partition(|(_, may_be_null)| *may_be_null);
+ let null_aware_value_keys = nullable.len();
Review Comment:
Thanks again for catching this. #25679 has now merged, and this PR is
updated on top of it. I also added Q13 to the `null_aware_join` benchmark to
cover the low-cardinality scope-key case you raised: `(o.id_n50, o.k) NOT IN
(...)`, where `k` is NOT NULL with 16 distinct values. On 10k / 20k rows it now
runs in 0.80 / 0.99 ms. Before #25679, the same shape on this branch took 20.5
/ 41.3 ms, and the value-key path on main takes 78.8 / 162 ms. Your 8192×8192
repro also now finishes in about 1 ms on every plan shape (RightAnti, LeftMark
and correlated scalar). Could you take another look when you have time?
##########
datafusion/optimizer/src/decorrelate_predicate_subquery.rs:
##########
@@ -1037,6 +1042,38 @@ fn build_join(
}
let left = projected_left.as_ref().unwrap_or(left);
+ // The first `V` keys of a null-aware join are its `NOT IN` value keys.
+ //
+ // A tuple element that cannot be NULL in scope on either side never makes
+ // the tuple comparison UNKNOWN: compared with a definite value it is
either
+ // equal, which leaves the other elements to decide, or a definite
mismatch,
+ // which makes the comparison FALSE whatever the other elements are. It
+ // therefore only selects which subquery rows a NULL in another element is
+ // compared with, which is what a correlation scope key does. Moving such
+ // elements after the ones that can be NULL turns them into scope keys, so
+ // the hash join finds the rows a NULL-valued row is compared with through
a
+ // hash lookup instead of pairing it with every row of the other side
+ // (<https://github.com/apache/datafusion/issues/26088>).
+ //
+ // A null-aware tuple has at least one element that can be NULL, so `V` is
+ // at least one. With exactly one, the join is a scalar `NOT IN` on that
+ // element, correlated by the other elements.
+ let null_aware_value_keys = if null_aware && in_values.len() > 1 {
Review Comment:
Thanks for measuring this, agreed. The scope map is now built on the first
probe row with a NULL value key that is in some scope, instead of in
`collect_left_input`, and is charged to the build reservation at that point
(a60e1af38). A NULL-free probe side no longer builds it, and a unit test checks
that through `build_mem_used`. On the `null_aware_join` benchmark, Q10
(nullable keys holding no NULL) is now at parity with main (0.34 / 0.38 ms vs
0.32 / 0.38 ms on 10k / 20k rows), while Q11–Q13 keep their gains.
##########
datafusion/sqllogictest/test_files/null_aware_multi_column.slt:
##########
@@ -546,6 +546,167 @@ z
statement ok
DEALLOCATE mc_tuple_qualified;
+#############
+## NOT NULL tuple elements
Review Comment:
Added in 865e3cd91, both as the mark projection and as the anti join filter.
`b = y` is planned as a scope key there, so the rows with a NULL `b` reach the
join with a NULL scope key. Thanks for the case and the expected results.
##########
datafusion/optimizer/src/decorrelate_predicate_subquery.rs:
##########
@@ -953,16 +955,19 @@ fn build_join(
None => vec![],
};
- // True if an `IN` value or the subquery column it is compared with can be
- // NULL inside the scope of an outer row.
- let mut value_may_be_null = false;
- for in_value in &in_values {
- value_may_be_null |= in_value.may_be_null_in_scope(
- left.schema(),
- sub_query_alias.schema(),
- &pull_up.correlated_filters,
- )?;
- }
+ // For each `IN` value, true if it or the subquery column it is compared
+ // with can be NULL inside the scope of an outer row.
+ let elements_may_be_null = in_values
+ .iter()
+ .map(|in_value| {
+ in_value.may_be_null_in_scope(
+ left.schema(),
+ sub_query_alias.schema(),
+ &pull_up.correlated_filters,
+ )
+ })
+ .collect::<Result<Vec<_>>>()?;
+ let value_may_be_null = elements_may_be_null.iter().any(|may_be_null|
*may_be_null);
Review Comment:
Done in 865e3cd91, thanks.
--
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]
