You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "jonathanc-n (via GitHub)" <gi...@apache.org> on 2025/05/29 18:10:43 UTC

[PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

jonathanc-n opened a new pull request, #16210:
URL: https://github.com/apache/datafusion/pull/16210

   ## Which issue does this PR close?
   
   <!--
   We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
   -->
   
   - Closes #16051 .
   
   ## Rationale for this change
   Supporting null aware loop join in the case that cost is cheaper than Hash join.
   <!--
    Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
    Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.  
   -->
   
   ## What changes are included in this PR?
   Added support for null aware + equijoins for nested loop join
   <!--
   There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
   -->
   
   ## Are these changes tested?
   Yes
   <!--
   We typically require tests for all PRs in order to:
   1. Prevent the code from being accidentally broken by subsequent changes
   2. Serve as another way to document the expected behavior of the code
   
   If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
   -->
   


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2125235875


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -810,6 +871,123 @@ fn build_join_indices(
     }
 }
 
+// Find matching indices based on join `on` predicates
+fn get_equijoin_match(
+    left_indices: UInt64Array,
+    right_indices: UInt32Array,
+    left_batch: &RecordBatch,
+    right_batch: &RecordBatch,
+    on: &Vec<(PhysicalExprRef, PhysicalExprRef)>,
+    null_equals_null: bool,
+) -> Result<(UInt64Array, UInt32Array)> {
+    // Create the different `ArrayRef`s holding the values that were evaluated
+    // against each expression in the `on` predicate
+    let left_arrays: Vec<ArrayRef> = on
+        .iter()
+        .map(|(l, _)| l.evaluate(left_batch))
+        .collect::<Result<Vec<ColumnarValue>>>()?
+        .into_iter()
+        .map(|cv| cv.into_array(left_batch.num_rows()).unwrap())
+        .collect();
+    let right_arrays: Vec<ArrayRef> = on
+        .iter()
+        .map(|(_, r)| r.evaluate(right_batch))
+        .collect::<Result<Vec<ColumnarValue>>>()?
+        .into_iter()
+        .map(|cv| cv.into_array(right_batch.num_rows()).unwrap())
+        .collect();
+
+    let mut out_l = UInt64Builder::new();
+    let mut out_r = UInt32Builder::new();
+
+    // Goes through both left and right indices and compares the values
+    for (l_idx, r_idx) in left_indices.values().iter().zip(right_indices.values()) {
+        if compare_arrays(
+            &left_arrays,
+            *l_idx as usize,
+            &right_arrays,
+            *r_idx as usize,
+            null_equals_null,
+        )? {
+            out_l.append_value(*l_idx);
+            out_r.append_value(*r_idx);
+        }
+    }
+
+    Ok((out_l.finish(), out_r.finish()))
+}
+
+// Compares values in the array, returns true if match, false otherwise
+fn compare_arrays(
+    left_arrays: &[ArrayRef],
+    left: usize,

Review Comment:
   this reminds me of SMJ, the similar mechanism, probably we can factor it out?



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "UBarney (via GitHub)" <gi...@apache.org>.
UBarney commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2144201354


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   I missed that we may convert EXCEPT to a null aware join. Sorry for that.
   If null_equal_null is true, we can replace `=` in the ON clause with `<=>` and merge it into the filter in the planner. Otherwise, we merge the ON clause into the filter directly.
   
   > how were you able to have the query use a nested loop join with a on condition?
   
   There's **no equal join condition in `on`,** so the planner choose nlj
   
   https://github.com/apache/datafusion/blob/e5f596b59ece71329635d41fd7f147d1d702e49e/datafusion/core/src/physical_planner.rs#L1104-L1111



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n closed pull request #16210: feat: Support null aware + equijoins for `NestedLoopJoin`
URL: https://github.com/apache/datafusion/pull/16210


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#issuecomment-2924177927

   This feature is intended purely for performance, right? Not because there are cases that can only be run with NLJ.
   If that's the case, I suggest to do some benchmarks upfront to justify the additional complexity.


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2141190301


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   > Maybe we can change type to `Vec<(PhysicalExprRef, PhysicalExprRef)>` . `on.is_empty() == true` mean no equijoin columns.
   Because nested loop joins exclusively take in filter clauses more often than not, I decided it'd be easier to check if `on.is_some()`. Currently the physical planner doesnt take in nested loop join for equijoins on purpose, this will be added in another pr.
   
   > If we can merge `on` condition into `filter`, we can remove this field and reuse existing filter logic. For example: `filter: t1.a < t2.a, on: t1.c = t2.c` -> `filter: t1.a < t2.a and t1.c = t2.c`
   I separated merging the filter + on condition to make sure that we can do the null_equals_null check (this is how it is implemented for the other joins as well).



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "UBarney (via GitHub)" <gi...@apache.org>.
UBarney commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2144121144


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   Let's just skip `ExtractEquijoinPredicate` if we prefer NLJ.
   https://github.com/apache/datafusion/blob/8d79bddeda71bc415ba9bf85e77476ab1784c665/datafusion/optimizer/src/extract_equijoin_predicate.rs#L30-L43
   
   
   I assume we achieve the behavior of `null_equals_null` by using `<=>`. For example: `select t1.value from range(6) t1 join range(6) t2 on t1.value <=> t2.value;`. The current spaceship operator can already handle this.
   
   https://github.com/apache/datafusion/blob/916ccc39f2af1aa3fb01f1c7e406fbcdbc03cc13/datafusion/sqllogictest/test_files/expr.slt#L1595-L1612
   



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2144167426


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   Oh yeah that makes sense, just have it be merged in the join filter. :facepalm: Thanks for finding this πŸ˜„. I think I'll just put out a pull request removing the todo statement, that statement led me to think that null aware wasn't supported yet.



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "UBarney (via GitHub)" <gi...@apache.org>.
UBarney commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2140090439


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   Maybe we can change type to `Vec<(PhysicalExprRef, PhysicalExprRef)>` . `on.is_empty() == true` mean no equijoin columns.
   



##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   If we can merge `on` condition into `filter`, we can remove this field and reuse existing filter logic.
   For example: `filter: t1.a < t2.a, on: t1.c = t2.c` -> `filter:  t1.a < t2.a and t1.c = t2.c`



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#issuecomment-2945598547

   @2010YOUY01 I was doing some benchmarks on NLJs vs. HJs and it looked bad even for cases where one table is very small which is what NLJs should excel at. One thing is to note that it does seem slightly faster when both tables are very small, especially in the case when the outer table is the larger table (makes sense due to hashing the build side, I should probably test this with SMJ cases). Duckdb has something interesting where if one of the tables have a certain row threshold (5), they choose to use a nested loop join for `on.is_some()` cases: [threshold](https://github.com/duckdb/duckdb/blob/a8a377580cc5d26ae90f16b41affad24ac6ee833/src/include/duckdb/main/client_config.hpp#L102) (we could probably do this as well when performance is better).
   
   ### Benchmarks
   Here is some experiment benchmarks that I had run if curious (one thing to note is that these benchmarks are just simulated on created row batches and are not read from disk + they are called directly from physical plan and not passed into the optimizer -- the batch sides would have been swapped): 
   <details>
     <summary>Benchmark</summary>
     Benchmarking joins/HashJoin/l=5_r=10165536: Collecting 100 samples in estimated 7.3643 s (300 ite
   joins/HashJoin/l=5_r=10165536
                           time:   [24.433 ms 24.499 ms 24.567 ms]
                           change: [-26.227% -21.563% -17.138%] (p = 0.00 < 0.05)
                           Performance has improved.
   Found 5 outliers among 100 measurements (5.00%)
     5 (5.00%) high mild
   Benchmarking joins/NestedLoopJoin/l=5_r=10165536: Warming up for 3.0000 s
   Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 40.0s, or reduce sample count to 10.
   Benchmarking joins/NestedLoopJoin/l=5_r=10165536: Collecting 100 samples in estimated 40.016 s (1
   joins/NestedLoopJoin/l=5_r=10165536
                           time:   [399.05 ms 400.87 ms 403.07 ms]
                           change: [+0.2540% +0.7221% +1.3508%] (p = 0.00 < 0.05)
                           Change within noise threshold.
   Found 10 outliers among 100 measurements (10.00%)
     3 (3.00%) high mild
     7 (7.00%) high severe
   Benchmarking joins/HashJoin/l=5_r=1165536: Collecting 100 samples in estimated 5.0385 s (2000 ite
   joins/HashJoin/l=5_r=1165536
                           time:   [2.4954 ms 2.5147 ms 2.5488 ms]
                           change: [+0.3564% +1.1539% +2.5753%] (p = 0.03 < 0.05)
                           Change within noise threshold.
   Found 6 outliers among 100 measurements (6.00%)
     2 (2.00%) high mild
     4 (4.00%) high severe
   Benchmarking joins/NestedLoopJoin/l=5_r=1165536: Collecting 100 samples in estimated 8.8061 s (20
   joins/NestedLoopJoin/l=5_r=1165536
                           time:   [43.398 ms 43.540 ms 43.721 ms]
                           change: [-3.4531% -2.3846% -1.4403%] (p = 0.00 < 0.05)
                           Performance has improved.
   Found 8 outliers among 100 measurements (8.00%)
     4 (4.00%) high mild
     4 (4.00%) high severe
   Benchmarking joins/HashJoin/l=5_r=536: Collecting 100 samples in estimated 5.0472 s (510k iterati
   joins/HashJoin/l=5_r=536
                           time:   [9.9513 Β΅s 10.019 Β΅s 10.090 Β΅s]
                           change: [-0.8239% -0.0294% +0.8130%] (p = 0.95 > 0.05)
                           No change in performance detected.
   Found 2 outliers among 100 measurements (2.00%)
     1 (1.00%) high mild
     1 (1.00%) high severe
   Benchmarking joins/NestedLoopJoin/l=5_r=536: Collecting 100 samples in estimated 5.0749 s (202k i
   joins/NestedLoopJoin/l=5_r=536
                           time:   [25.074 Β΅s 25.114 Β΅s 25.160 Β΅s]
                           change: [-79.602% -79.115% -78.699%] (p = 0.00 < 0.05)
                           Performance has improved.
   Found 4 outliers among 100 measurements (4.00%)
     1 (1.00%) high mild
     3 (3.00%) high severe
   Benchmarking joins/HashJoin/l=5_r=36: Collecting 100 samples in estimated 5.0396 s (556k iteratio
   joins/HashJoin/l=5_r=36 time:   [9.1466 Β΅s 9.2176 Β΅s 9.2864 Β΅s]
                           change: [+0.5504% +2.4160% +5.0403%] (p = 0.02 < 0.05)
                           Change within noise threshold.
   Found 3 outliers among 100 measurements (3.00%)
     1 (1.00%) high mild
     2 (2.00%) high severe
   Benchmarking joins/NestedLoopJoin/l=5_r=36: Collecting 100 samples in estimated 5.0394 s (641k it
   joins/NestedLoopJoin/l=5_r=36
                           time:   [7.7842 Β΅s 7.8208 Β΅s 7.8561 Β΅s]
                           change: [-92.509% -92.452% -92.375%] (p = 0.00 < 0.05)
                           Performance has improved.
   Found 4 outliers among 100 measurements (4.00%)
     1 (1.00%) low mild
     2 (2.00%) high mild
     1 (1.00%) high severe
   Benchmarking joins/HashJoin/l=1_r=10165536: Collecting 100 samples in estimated 6.5938 s (300 ite
   joins/HashJoin/l=1_r=10165536
                           time:   [21.778 ms 21.825 ms 21.875 ms]
                           change: [-0.7761% -0.2678% +0.1717%] (p = 0.28 > 0.05)
                           No change in performance detected.
   Found 4 outliers among 100 measurements (4.00%)
     3 (3.00%) high mild
     1 (1.00%) high severe
   Benchmarking joins/NestedLoopJoin/l=1_r=10165536: Warming up for 3.0000 s
   Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 7.7s, or reduce sample count to 60.
   Benchmarking joins/NestedLoopJoin/l=1_r=10165536: Collecting 100 samples in estimated 7.7104 s (1
   joins/NestedLoopJoin/l=1_r=10165536
                           time:   [76.483 ms 76.543 ms 76.607 ms]
                           change: [-0.8023% -0.6128% -0.4446%] (p = 0.00 < 0.05)
                           Change within noise threshold.
   Found 3 outliers among 100 measurements (3.00%)
     3 (3.00%) high mild
   Benchmarking joins/HashJoin/l=1_r=1165536: Collecting 100 samples in estimated 5.0671 s (2300 ite
   joins/HashJoin/l=1_r=1165536
                           time:   [2.2005 ms 2.2029 ms 2.2057 ms]
                           change: [+0.4246% +0.5813% +0.7394%] (p = 0.00 < 0.05)
                           Change within noise threshold.
   Found 1 outliers among 100 measurements (1.00%)
     1 (1.00%) high severe
   Benchmarking joins/NestedLoopJoin/l=1_r=1165536: Collecting 100 samples in estimated 5.8078 s (70
   joins/NestedLoopJoin/l=1_r=1165536
                           time:   [8.2899 ms 8.3103 ms 8.3466 ms]
                           change: [-7.8900% -5.3165% -3.4247%] (p = 0.00 < 0.05)
                           Performance has improved.
   Found 4 outliers among 100 measurements (4.00%)
     1 (1.00%) high mild
     3 (3.00%) high severe
   Benchmarking joins/HashJoin/l=1_r=536: Collecting 100 samples in estimated 5.0210 s (545k iterati
   joins/HashJoin/l=1_r=536
                           time:   [9.2227 Β΅s 9.2730 Β΅s 9.3264 Β΅s]
                           change: [-0.9104% -0.0683% +0.6914%] (p = 0.86 > 0.05)
                           No change in performance detected.
   Benchmarking joins/NestedLoopJoin/l=1_r=536: Collecting 100 samples in estimated 5.0185 s (515k i
   joins/NestedLoopJoin/l=1_r=536
                           time:   [9.6997 Β΅s 9.7260 Β΅s 9.7531 Β΅s]
                           change: [-91.393% -91.304% -91.222%] (p = 0.00 < 0.05)
                           Performance has improved.
   Found 2 outliers among 100 measurements (2.00%)
     1 (1.00%) high mild
     1 (1.00%) high severe
   Benchmarking joins/HashJoin/l=1_r=36: Collecting 100 samples in estimated 5.0175 s (606k iteratio
   joins/HashJoin/l=1_r=36 time:   [8.3172 Β΅s 8.3724 Β΅s 8.4360 Β΅s]
                           change: [-4.5295% -2.7882% -1.4567%] (p = 0.00 < 0.05)
                           Performance has improved.
   Found 2 outliers among 100 measurements (2.00%)
     1 (1.00%) high mild
     1 (1.00%) high severe
   Benchmarking joins/NestedLoopJoin/l=1_r=36: Collecting 100 samples in estimated 5.0127 s (803k it
   joins/NestedLoopJoin/l=1_r=36
                           time:   [6.1413 Β΅s 6.1649 Β΅s 6.1893 Β΅s]
                           change: [-95.940% -95.689% -95.431%] (p = 0.00 < 0.05)
                           Performance has improved.
   Found 2 outliers among 100 measurements (2.00%)
     1 (1.00%) low mild
     1 (1.00%) high mild
   Benchmarking joins/HashJoin/l=10165536_r=5: Warming up for 3.0000 s
   Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 14.2s, or reduce sample count to 30.
   Benchmarking joins/HashJoin/l=10165536_r=5: Collecting 100 samples in estimated 14.174 s (100 ite
   joins/HashJoin/l=10165536_r=5
                           time:   [139.17 ms 141.39 ms 144.00 ms]
                           change: [-9.4179% -7.2756% -4.9624%] (p = 0.00 < 0.05)
                           Performance has improved.
   Found 11 outliers among 100 measurements (11.00%)
     7 (7.00%) high mild
     4 (4.00%) high severe
   Benchmarking joins/NestedLoopJoin/l=10165536_r=5: Warming up for 3.0000 s
   Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 39.7s, or reduce sample count to 10.
   Benchmarking joins/NestedLoopJoin/l=10165536_r=5: Collecting 100 samples in estimated 39.689 s (1
   joins/NestedLoopJoin/l=10165536_r=5
                           time:   [397.64 ms 399.12 ms 400.92 ms]
                           change: [-2.0605% -0.9166% -0.0093%] (p = 0.08 > 0.05)
                           No change in performance detected.
   Found 10 outliers among 100 measurements (10.00%)
     2 (2.00%) high mild
     8 (8.00%) high severe
   Benchmarking joins/HashJoin/l=1165536_r=5: Collecting 100 samples in estimated 5.3484 s (600 iter
   joins/HashJoin/l=1165536_r=5
                           time:   [8.5434 ms 8.7560 ms 9.0212 ms]
                           change: [-5.8975% -3.1249% -0.3413%] (p = 0.04 < 0.05)
                           Change within noise threshold.
   Found 7 outliers among 100 measurements (7.00%)
     3 (3.00%) high mild
     4 (4.00%) high severe
   Benchmarking joins/NestedLoopJoin/l=1165536_r=5: Collecting 100 samples in estimated 8.5975 s (20
   joins/NestedLoopJoin/l=1165536_r=5
                           time:   [43.161 ms 43.425 ms 43.768 ms]
                           change: [-0.8075% -0.2119% +0.5729%] (p = 0.60 > 0.05)
                           No change in performance detected.
   Found 8 outliers among 100 measurements (8.00%)
     5 (5.00%) high mild
     3 (3.00%) high severe
   Benchmarking joins/HashJoin/l=536_r=5: Collecting 100 samples in estimated 5.0214 s (460k iterati
   joins/HashJoin/l=536_r=5
                           time:   [11.736 Β΅s 12.520 Β΅s 13.378 Β΅s]
                           change: [+7.4909% +12.306% +17.627%] (p = 0.00 < 0.05)
                           Performance has regressed.
   Found 7 outliers among 100 measurements (7.00%)
     5 (5.00%) high mild
     2 (2.00%) high severe
   Benchmarking joins/NestedLoopJoin/l=536_r=5: Collecting 100 samples in estimated 5.0127 s (197k i
   joins/NestedLoopJoin/l=536_r=5
                           time:   [25.173 Β΅s 25.299 Β΅s 25.448 Β΅s]
                           change: [-1.5034% -0.4593% +0.3076%] (p = 0.38 > 0.05)
                           No change in performance detected.
   Found 12 outliers among 100 measurements (12.00%)
     2 (2.00%) low mild
     1 (1.00%) high mild
     9 (9.00%) high severe
   Benchmarking joins/HashJoin/l=36_r=5: Collecting 100 samples in estimated 5.0086 s (561k iteratio
   joins/HashJoin/l=36_r=5 time:   [9.0865 Β΅s 9.1404 Β΅s 9.2022 Β΅s]
                           change: [+0.5672% +2.5431% +3.9872%] (p = 0.00 < 0.05)
                           Change within noise threshold.
   Found 4 outliers among 100 measurements (4.00%)
     4 (4.00%) high mild
   Benchmarking joins/NestedLoopJoin/l=36_r=5: Collecting 100 samples in estimated 5.0098 s (667k it
   joins/NestedLoopJoin/l=36_r=5
                           time:   [7.9047 Β΅s 7.9530 Β΅s 7.9958 Β΅s]
                           change: [+1.7475% +2.8065% +3.8190%] (p = 0.00 < 0.05)
                           Performance has regressed.
   Found 2 outliers among 100 measurements (2.00%)
     1 (1.00%) low mild
     1 (1.00%) high severe
   Benchmarking joins/HashJoin/l=10165536_r=1: Warming up for 3.0000 s
   Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 16.4s, or reduce sample count to 30.
   Benchmarking joins/HashJoin/l=10165536_r=1: Collecting 100 samples in estimated 16.431 s (100 ite
   joins/HashJoin/l=10165536_r=1
                           time:   [170.17 ms 181.86 ms 194.52 ms]
                           change: [+17.971% +27.731% +36.798%] (p = 0.00 < 0.05)
                           Performance has regressed.
   Found 9 outliers among 100 measurements (9.00%)
     7 (7.00%) high mild
     2 (2.00%) high severe
   Benchmarking joins/NestedLoopJoin/l=10165536_r=1: Warming up for 3.0000 s
   Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 7.8s, or reduce sample count to 60.
   Benchmarking joins/NestedLoopJoin/l=10165536_r=1: Collecting 100 samples in estimated 7.8403 s (1
   joins/NestedLoopJoin/l=10165536_r=1
                           time:   [80.408 ms 81.251 ms 82.168 ms]
                           change: [+5.9184% +6.9256% +8.1615%] (p = 0.00 < 0.05)
                           Performance has regressed.
   Found 8 outliers among 100 measurements (8.00%)
     5 (5.00%) high mild
     3 (3.00%) high severe
   Benchmarking joins/HashJoin/l=1165536_r=1: Collecting 100 samples in estimated 5.6164 s (600 iter
   joins/HashJoin/l=1165536_r=1
                           time:   [10.917 ms 11.369 ms 11.918 ms]
                           change: [+24.789% +29.850% +37.372%] (p = 0.00 < 0.05)
                           Performance has regressed.
   Found 6 outliers among 100 measurements (6.00%)
     4 (4.00%) high mild
     2 (2.00%) high severe
   Benchmarking joins/NestedLoopJoin/l=1165536_r=1: Collecting 100 samples in estimated 5.0288 s (50
   joins/NestedLoopJoin/l=1165536_r=1
                           time:   [9.6901 ms 9.9011 ms 10.182 ms]
                           change: [+13.021% +15.449% +18.574%] (p = 0.00 < 0.05)
                           Performance has regressed.
   Found 12 outliers among 100 measurements (12.00%)
     8 (8.00%) high mild
     4 (4.00%) high severe
   Benchmarking joins/HashJoin/l=536_r=1: Collecting 100 samples in estimated 5.0044 s (480k iterati
   joins/HashJoin/l=536_r=1
                           time:   [10.219 Β΅s 10.340 Β΅s 10.447 Β΅s]
                           change: [-3.4348% -2.5041% -1.5280%] (p = 0.00 < 0.05)
                           Performance has improved.
   Benchmarking joins/NestedLoopJoin/l=536_r=1: Collecting 100 samples in estimated 5.0492 s (510k i
   joins/NestedLoopJoin/l=536_r=1
                           time:   [9.8366 Β΅s 9.8801 Β΅s 9.9240 Β΅s]
                           change: [+0.4580% +1.1528% +2.0755%] (p = 0.00 < 0.05)
                           Change within noise threshold.
   Found 3 outliers among 100 measurements (3.00%)
     2 (2.00%) low mild
     1 (1.00%) high severe
   Benchmarking joins/HashJoin/l=36_r=1: Collecting 100 samples in estimated 5.0406 s (596k iteratio
   joins/HashJoin/l=36_r=1 time:   [8.9515 Β΅s 9.4730 Β΅s 10.132 Β΅s]
                           change: [-0.6109% +4.0642% +10.933%] (p = 0.18 > 0.05)
                           No change in performance detected.
   Found 10 outliers among 100 measurements (10.00%)
     2 (2.00%) high mild
     8 (8.00%) high severe
   Benchmarking joins/NestedLoopJoin/l=36_r=1: Collecting 100 samples in estimated 5.0112 s (798k it
   joins/NestedLoopJoin/l=36_r=1
                           time:   [6.2231 Β΅s 6.3843 Β΅s 6.6209 Β΅s]
                           change: [-1.2056% +0.5125% +2.7669%] (p = 0.63 > 0.05)
                           No change in performance detected.
   Found 6 outliers among 100 measurements (6.00%)
     2 (2.00%) high mild
     4 (4.00%) high severe
   </details>
   
   The tests seem to be a bit inconsistent when I run locally so if someone would like to run it on their computer, here is the code (make a file in `datafusion/physical_plan/benches`):
   <details>
     <summary>Code</summary>
   ```
   use std::sync::Arc;
   
   use arrow::array::{Date32Builder, Decimal128Builder, Int32Builder, RecordBatch, StringBuilder};
   use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
   use criterion::{criterion_group, criterion_main, BatchSize, BenchmarkId, Criterion};
   use datafusion_common::{Result};
   use datafusion_execution::TaskContext;
   use datafusion_expr::JoinType;
   use datafusion_physical_expr::expressions::Column;
   
   use datafusion_physical_plan::{collect, ExecutionPlan};
   use tokio::runtime::Runtime;
   use datafusion_physical_plan::joins::{HashJoinExec, NestedLoopJoinExec, PartitionMode};
   use datafusion_physical_plan::test::TestMemoryExec;
   
   //
   pub fn create_batch(num_rows: usize, allow_nulls: bool) -> RecordBatch {
       let schema = Arc::new(Schema::new(vec![
           Field::new("c0", DataType::Int32, true),
           Field::new("c1", DataType::Utf8, true),
           Field::new("c2", DataType::Date32, true),
           Field::new("c3", DataType::Decimal128(11, 2), true),
       ]));
   
       let mut a = Int32Builder::new();
       let mut b = StringBuilder::new();
       let mut c = Date32Builder::new();
       let mut d = Decimal128Builder::new().with_precision_and_scale(11, 2).unwrap();
   
       for i in 0..num_rows {
           a.append_value(i as i32);
           c.append_value(i as i32);
           d.append_value((i as i128) * 1_000_000);
   
           if allow_nulls && i % 10 == 0 {
               b.append_null();
           } else {
               b.append_value(format!("string_{i}"));
           }
       }
   
       let a = Arc::new(a.finish());
       let b = Arc::new(b.finish());
       let c = Arc::new(c.finish());
       let d = Arc::new(d.finish());
   
       RecordBatch::try_new(
           schema.clone(),
           vec![a as _, b as _, c as _, d as _],
       )
       .unwrap()
   }
   
   fn make_memory_execs(
       left_rows: usize,
       right_rows: usize,
   ) -> (Arc<dyn ExecutionPlan>, Arc<dyn ExecutionPlan>, SchemaRef) {
       let left_batch = create_batch(left_rows, true);
       let schema = left_batch.schema();
       let left_partitions = vec![vec![left_batch]];
   
       let right_batch = create_batch(right_rows, true);
       let right_partitions = vec![vec![right_batch]];
   
       let left_mem = TestMemoryExec::try_new_exec(&left_partitions, schema.clone(), None).unwrap();
       let right_mem = TestMemoryExec::try_new_exec(&right_partitions, schema.clone(), None).unwrap();
   
       (left_mem, right_mem, schema)
   }
   
   
   fn build_two_joins(
       left: Arc<dyn ExecutionPlan>,
       right: Arc<dyn ExecutionPlan>,
   ) -> Result<(
       Arc<dyn ExecutionPlan>, // hj
       Arc<dyn ExecutionPlan>, // nlj
   )> {
       let hj = HashJoinExec::try_new(
           left.clone(),
           right.clone(),
   
           vec![(Arc::new(Column::new("c0", 0)), Arc::new(Column::new("c0", 0)))],
           None,              
           &JoinType::Inner,     
           None,                 
           PartitionMode::Partitioned,
           false, // null_aware = false
       )?;
   
       let nlj = NestedLoopJoinExec::try_new(
           left,
           right,
           None,                
           &JoinType::Inner,
           None,               
           false, // null_aware = false
           Some(vec![(Arc::new(Column::new("c0", 0)), Arc::new(Column::new("c0", 0)))]),
       )?;
   
       Ok((Arc::new(hj), Arc::new(nlj)))
   }
   
   
   fn bench_joins(c: &mut Criterion) {
       let rt = Runtime::new().unwrap();
       let mut group = c.benchmark_group("joins");
   
       // row pairs for each side in benchmarks
       let size_pairs = &[
           (5, 10_165_536),
           (5, 1_165_536), 
           (5, 536),
           (5, 36),
           (1, 10_165_536),
           (1, 1_165_536), 
           (1, 536),
           (1, 36),
           (10_165_536, 5),
           (1_165_536, 5),
           (536, 5),
           (36, 5),
           (10_165_536, 1),
           (1_165_536, 1),
           (536, 1),
           (36, 1),
       ];
   
       for &(left_rows, right_rows) in size_pairs.iter() {
           let (left_mem, right_mem, _schema) = make_memory_execs(left_rows, right_rows);
   
           let (hash_join, nested_loop_join) =
               build_two_joins(left_mem.clone(), right_mem.clone()).unwrap();
   
           group.bench_with_input(
               BenchmarkId::new(
                   "HashJoin",
                   format!("l={}_r={}", left_rows, right_rows),
               ),
               &hash_join,
               |b, plan| {
                   b.iter_batched(
                       || (),
                       |_setup| {
                           let ctx = TaskContext::default();
                           let fut = collect(plan.clone(), Arc::new(ctx));
                           rt.block_on(async {
                               let _ = fut.await.unwrap();
                           });
                       },
                       BatchSize::SmallInput,
                   )
               },
           );
   
           group.bench_with_input(
               BenchmarkId::new(
                   "NestedLoopJoin",
                   format!("l={}_r={}", left_rows, right_rows),
               ),
               &nested_loop_join,
               |b, plan| {
                   b.iter_batched(
                       || (),
                       |_setup| {
                           let ctx = TaskContext::default();
                           let fut = collect(plan.clone(), Arc::new(ctx));
                           rt.block_on(async {
                               let _ = fut.await.unwrap();
                           });
                       },
                       BatchSize::SmallInput,
                   )
               },
           );
       }
   
       group.finish();
   }
   
   criterion_group!(benches, bench_joins);
   criterion_main!(benches);
   ```
   </details>
   I think this code should be run with different batches though.
   
   ### Consensus
   I think we can either add this to Datafusion more as an feature users can experiment with (users can pass a flag and experiment -- `datafusion.optimizer.use_nested_loop_join`)  -> then we refactor for performance for NLJ equijoin cases. This seems to be fine as the current implementation doesnt affect existing performance but I'm not sure if Datafusion supports features that are purely for user experiments (@alamb would you be willing to fact check me on this?)
   
   


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2144282145


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   > If null_equal_null is true, we can replace = in the ON clause with <=> and merge it into the filter in the planner
   
   This seems slower, we should just pass this to smj or hj. I can play around with the threshold logic that duckdb has for smaller tables where nljs may be faster. 
   
   > There's **no equal(`=` not `<=>`) join condition in `on`,** so the planner choose nlj
   
   Since hash join and smj are usually faster for this equi conditions, instead of passing in <=> into the join filter we can flip the null equals null bit to true and run the <=> in the `on` clause; but this would clash with a `=` if null_equals_null is false. The solution I was thinking of is these cases:
   - `null_equals_null` equals true + `<=>` condition +  `=` condition -> we pass the `<=>` expressions into the `on` clause
   - `null_equals_null` equals false +  `<=>` condition +  `=` condition -> `<=>` stays in join filter 
   - `null_equals_null` equals false + `<=>` condition + no `=` condition -> we flip the `null_equals_null` to true and pass the `<=>` expressions into the `on` clause
   
   WDYT @UBarney 
   
   
   



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2114981517


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -810,6 +871,123 @@ fn build_join_indices(
     }
 }
 
+// Find matching indices based on join `on` predicates

Review Comment:
   Not sure if this is the most efficient way? I tried to add comments wherever possible to make the review process easier, and the logic is straight forward (should be simple to review πŸ˜„ ). 



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "UBarney (via GitHub)" <gi...@apache.org>.
UBarney commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2142968386


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   > we can do the null_equals_null check
   
   We can do this by merging on condition into filter.
   For example: filter: `t1.a < t2.a, on: t1.c = t2.c` -> `filter:  t1.a < t2.a and (t1.c = t2.c or (is_null(t1.c) and (is_null(t2.c))))`
   
   > this is how it is implemented for the other joins as well
   
   Hash Joins and Sort-Merge Joins are fundamentally reliant on equality conditions. Their high-speed mechanisms (hashing, merging) are impossible without them.
   But for nlj separating equality conditions doesn't improve performance



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "UBarney (via GitHub)" <gi...@apache.org>.
UBarney commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2144121144


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   Let's just skip ExtractEquijoinPredicate if we prefer NLJ.
   https://github.com/apache/datafusion/blob/8d79bddeda71bc415ba9bf85e77476ab1784c665/datafusion/optimizer/src/extract_equijoin_predicate.rs#L30-L43
   
   
   I assume we can achieve the behavior of `null_equals_null` by using `<=>`. For example: `select t1.value from range(6) t1 join range(6) t2 on t1.value <=> t2.value;`. The current spaceship operator can already handle this.
   
   https://github.com/apache/datafusion/blob/916ccc39f2af1aa3fb01f1c7e406fbcdbc03cc13/datafusion/sqllogictest/test_files/expr.slt#L1595-L1612
   



##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   Let's just skip `ExtractEquijoinPredicate` if we prefer NLJ.
   https://github.com/apache/datafusion/blob/8d79bddeda71bc415ba9bf85e77476ab1784c665/datafusion/optimizer/src/extract_equijoin_predicate.rs#L30-L43
   
   
   I assume we can achieve the behavior of `null_equals_null` by using `<=>`. For example: `select t1.value from range(6) t1 join range(6) t2 on t1.value <=> t2.value;`. The current spaceship operator can already handle this.
   
   https://github.com/apache/datafusion/blob/916ccc39f2af1aa3fb01f1c7e406fbcdbc03cc13/datafusion/sqllogictest/test_files/expr.slt#L1595-L1612
   



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n closed pull request #16210: feat: Support null aware + equijoins for `NestedLoopJoin`
URL: https://github.com/apache/datafusion/pull/16210


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#issuecomment-2954336669

   @comphead Pointers have been resolved, good for another review. 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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2125246086


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -1129,6 +1316,95 @@ pub(crate) mod tests {
         )
     }
 
+    fn build_left_table_equijoin() -> Arc<dyn ExecutionPlan> {
+        build_table(
+            ("a1", &vec![12, 2, 11]),
+            ("b1", &vec![2, 2, 8]),
+            ("c1", &vec![50, 90, 110]),
+            None,
+            Vec::new(),
+        )
+    }
+
+    fn build_right_table_equijoin() -> Arc<dyn ExecutionPlan> {
+        build_table(
+            ("a2", &vec![12, 2, 10]),
+            ("b2", &vec![10, 2, 10]),
+            ("c2", &vec![40, 80, 100]),
+            None,
+            Vec::new(),
+        )
+    }
+
+    /// This builds table with nullable values (uses same logic as `build_table` above)
+    fn build_table_null(
+        a: (&str, &Vec<Option<i32>>),
+        b: (&str, &Vec<Option<i32>>),
+        c: (&str, &Vec<Option<i32>>),
+        batch_size: Option<usize>,
+        sorted_column_names: Vec<&str>,
+    ) -> Arc<dyn ExecutionPlan> {
+        // build 0 or more sliced RecordBatches with nullable values
+        let batch = build_table_i32_null(a, b, c);
+        let schema = batch.schema();
+
+        let batches = if let Some(batch_size) = batch_size {
+            let num_batches = batch.num_rows().div_ceil(batch_size);
+            (0..num_batches)
+                .map(|i| {
+                    let start = i * batch_size;
+                    let remaining_rows = batch.num_rows() - start;
+                    batch.slice(start, batch_size.min(remaining_rows))
+                })
+                .collect::<Vec<_>>()
+        } else {
+            vec![batch]
+        };
+
+        // create the in‑memory source
+        let mut source =
+            TestMemoryExec::try_new(&[batches], Arc::clone(&schema), None).unwrap();
+
+        // attach sort information if requested
+        if !sorted_column_names.is_empty() {
+            let mut sort_info = LexOrdering::default();
+            for name in sorted_column_names {
+                let idx = schema.index_of(name).unwrap();
+                sort_info.push(PhysicalSortExpr {
+                    expr: Arc::new(Column::new(name, idx)),
+                    options: SortOptions {
+                        descending: false,
+                        nulls_first: false,
+                    },
+                });
+            }
+            source = source.try_with_sort_information(vec![sort_info]).unwrap();
+        }
+
+        // wrap in cache and return
+        Arc::new(TestMemoryExec::update_cache(Arc::new(source)))
+    }
+
+    fn build_left_table_null() -> Arc<dyn ExecutionPlan> {

Review Comment:
   a nit: but I think it would be easier to show the table contents in the content. 
   The table can be built in text format like here https://www.tablesgenerator.com/text_tables



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "UBarney (via GitHub)" <gi...@apache.org>.
UBarney commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2144201354


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   I missed that we may convert EXCEPT to a null aware join. Sorry for that.
   If null_equal_null is true, we can replace `=` in the ON clause with `<=>` and merge it into the filter in the planner. Otherwise, we merge the ON clause into the filter directly.
   
   > how were you able to have the query use a nested loop join with a on condition?
   
   There's **no equal(`=`) join condition in `on`,** so the planner choose nlj
   
   https://github.com/apache/datafusion/blob/e5f596b59ece71329635d41fd7f147d1d702e49e/datafusion/core/src/physical_planner.rs#L1104-L1111



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2144282145


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   Ok this sounds like a good plan, I think I will try to reiterate and run some benchmarks to see if it is worth it. 
   
   > If null_equal_null is true, we can replace = in the ON clause with <=> and merge it into the filter in the planner
   This seems slower, we should just pass this to smj or hj. I can play around with the threshold logic that duckdb has for smaller tables where nljs may be faster. 
   
   > There's **no equal(`=` not `<=>`) join condition in `on`,** so the planner choose nlj
   This is interesting because how will sort merge join + hash join when to treat . And since hash join and smj are usually faster for this equi conditions, instead of passing in <=> into the join filter we can flip the null equals null bit to true and run the <=> in the `on` clause; but this would clash with a `=` if null_equals_null is false. The solution I was thinking of is these cases:
   - `null_equals_null` equals true + `<=>` condition +  `=` condition -> we pass the `<=>` expressions into the `on` clause
   - `null_equals_null` equals false +  `<=>` condition +  `=` condition -> `<=>` stays in join filter 
   - `null_equals_null` equals false + `<=>` condition + no `=` condition -> we flip the `null_equals_null` to true and pass the `<=>` expressions into the `on` clause
   
   
   
   



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#issuecomment-2922765656

   I believe a follow up pull request can be made to actually have this be used in the physical plan based on some statistics. @comphead Does this look fine for now?


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "UBarney (via GitHub)" <gi...@apache.org>.
UBarney commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2142968386


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   > to make sure that we can do the null_equals_null check
   
   We can also do this by merging on condition into filter.
   For example: filter: `t1.a < t2.a, on: t1.c = t2.c` -> `filter:  t1.a < t2.a and (t1.c = t2.c or (is_null(t1.c) and (is_null(t2.c))))`
   
   > this is how it is implemented for the other joins as well
   
   Hash Joins and Sort-Merge Joins are fundamentally reliant on equality conditions. Their high-speed mechanisms (hashing, merging) are impossible without them.
   But for nlj separating equality conditions doesn't improve performance



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "UBarney (via GitHub)" <gi...@apache.org>.
UBarney commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2144133973


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   Looks like current nlj already supports null_equal_null πŸ˜‚
   
   
   
   ```
   > explain SELECT
       *
   FROM
       (VALUES (1, 'Apple'), (2, 'Banana'), (NULL, 'Cherry')) AS i(id, name)
   JOIN
       (VALUES (1, 'Fruit'), (3, 'Vegetable'), (NULL, 'Unknown')) AS c(id, category)
   ON
       i.id <=> c.id;
   
   +---------------+------------------------------------------------------------+
   | plan_type     | plan                                                       |
   +---------------+------------------------------------------------------------+
   | physical_plan | β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”                              |
   |               | β”‚     NestedLoopJoinExec    β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”               |
   |               | β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜              β”‚               |
   |               | β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β” |
   |               | β”‚       ProjectionExec      β”‚β”‚       ProjectionExec      β”‚ |
   |               | β”‚    --------------------   β”‚β”‚    --------------------   β”‚ |
   |               | β”‚        id: column1        β”‚β”‚     category: column2     β”‚ |
   |               | β”‚       name: column2       β”‚β”‚        id: column1        β”‚ |
   |               | β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜ |
   |               | β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β” |
   |               | β”‚       DataSourceExec      β”‚β”‚       DataSourceExec      β”‚ |
   |               | β”‚    --------------------   β”‚β”‚    --------------------   β”‚ |
   |               | β”‚        bytes: 1400        β”‚β”‚        bytes: 1400        β”‚ |
   |               | β”‚       format: memory      β”‚β”‚       format: memory      β”‚ |
   |               | β”‚          rows: 1          β”‚β”‚          rows: 1          β”‚ |
   |               | β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜ |
   |               |                                                            |
   +---------------+------------------------------------------------------------+
   1 row(s) fetched.
   Elapsed 0.001 seconds.
   
   
   > SELECT
       *
   FROM
       (VALUES (1, 'Apple'), (2, 'Banana'), (NULL, 'Cherry')) AS i(id, name)
   JOIN
       (VALUES (1, 'Fruit'), (3, 'Vegetable'), (NULL, 'Unknown')) AS c(id, category)
   ON
       i.id <=> c.id;
   
   +------+--------+------+----------+
   | id   | name   | id   | category |
   +------+--------+------+----------+
   | 1    | Apple  | 1    | Fruit    |
   | NULL | Cherry | NULL | Unknown  |
   +------+--------+------+----------+
   2 row(s) fetched.
   Elapsed 0.001 seconds.
   ```



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "UBarney (via GitHub)" <gi...@apache.org>.
UBarney commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2144201354


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   I missed that we may **convert EXCEPT to a null aware join**. Sorry for that.
   If null_equal_null is true, we can replace `=` in the ON clause with `<=>` and merge it into the filter in the planner. Otherwise, we merge the ON clause into the filter directly.
   
   > how were you able to have the query use a nested loop join with a on condition?
   
   There's **no equal(`=` not `<=>`) join condition in `on`,** so the planner choose nlj
   
   https://github.com/apache/datafusion/blob/e5f596b59ece71329635d41fd7f147d1d702e49e/datafusion/core/src/physical_planner.rs#L1104-L1111



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "UBarney (via GitHub)" <gi...@apache.org>.
UBarney commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2147410263


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   > > If null_equal_null is true, we can replace = in the ON clause with <=> and merge it into the filter in the planner
   > 
   > This seems slower, we should just pass this to smj or hj. I can play around with the threshold logic that duckdb has for smaller tables where nljs may be faster.
   > 
   > >
   
   Under the premise that we prefer NLJ
   
   Rest lgtm
   
   null_equals_null equals true  + <=> condition -> we can always pass the <=> expressions into the on clause
   



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#issuecomment-2945916745

   There's an interesting implementation of index joins [here](https://github.com/duckdb/duckdb/pull/1008), but this would involve creating indexes. What are the thoughts on supporting `CREATE INDEX`?
   


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2141190301


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   > Maybe we can change type to `Vec<(PhysicalExprRef, PhysicalExprRef)>` . `on.is_empty() == true` mean no equijoin columns.
   
   Because nested loop joins exclusively take in filter clauses more often than not, I decided it'd be easier to check if `on.is_some()`. Currently the physical planner doesnt take in nested loop join for equijoins on purpose, this will be added in another pr.
   
   > If we can merge `on` condition into `filter`, we can remove this field and reuse existing filter logic. For example: `filter: t1.a < t2.a, on: t1.c = t2.c` -> `filter: t1.a < t2.a and t1.c = t2.c`
   I separated merging the filter + on condition to make sure that we can do the null_equals_null check (this is how it is implemented for the other joins as well).



##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   > Maybe we can change type to `Vec<(PhysicalExprRef, PhysicalExprRef)>` . `on.is_empty() == true` mean no equijoin columns.
   
   Because nested loop joins exclusively take in filter clauses more often than not, I decided it'd be easier to check if `on.is_some()`. Currently the physical planner doesnt take in nested loop join for equijoins on purpose, this will be added in another pr.
   
   > If we can merge `on` condition into `filter`, we can remove this field and reuse existing filter logic. For example: `filter: t1.a < t2.a, on: t1.c = t2.c` -> `filter: t1.a < t2.a and t1.c = t2.c`
   
   I separated merging the filter + on condition to make sure that we can do the null_equals_null check (this is how it is implemented for the other joins as well).



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "UBarney (via GitHub)" <gi...@apache.org>.
UBarney commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2140108914


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   If we can merge `on` condition into `filter`, we can remove this field and reuse current existing filter logic.
   For example: `filter: t1.a < t2.a, on: t1.c = t2.c` -> `filter:  t1.a < t2.a and t1.c = t2.c`



##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   Maybe we can change type to `Vec<(PhysicalExprRef, PhysicalExprRef)>` . `if on.is_empty()` mean no equijoin columns.
   



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2143227797


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   But how would you suggest doing the null_equal_null check. I do think that it willl probably be faster to merge the two.



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2144169706


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   I am curious though, how were you able to have the query use a nested loop join with a `on` condition?



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org

Re: [PR] feat: Support null aware + equijoins for `NestedLoopJoin` [datafusion]

Posted by "UBarney (via GitHub)" <gi...@apache.org>.
UBarney commented on code in PR #16210:
URL: https://github.com/apache/datafusion/pull/16210#discussion_r2144201354


##########
datafusion/physical-plan/src/joins/nested_loop_join.rs:
##########
@@ -178,6 +187,18 @@ pub struct NestedLoopJoinExec {
     metrics: ExecutionPlanMetricsSet,
     /// Cache holding plan properties like equivalences, output partitioning etc.
     cache: PlanProperties,
+    /// Null matching behavior: If `null_equals_null` is true, rows that have
+    /// `null`s in both left and right equijoin columns will be matched.
+    /// Otherwise, rows that have `null`s in the join columns will not be
+    /// matched and thus will not appear in the output.
+    null_equals_null: bool,
+    /// Set of equijoin columns from the relations: `(left_col, right_col)`
+    ///
+    /// This is optional as a nested loop join can be passed a 'on' clause
+    /// in the case that a Hash Join cost is more expensive than a
+    /// nested loop join or when a user would like to pick nested loop
+    /// join by hint
+    on: Option<Vec<(PhysicalExprRef, PhysicalExprRef)>>,

Review Comment:
   I missed that we may convert EXCEPT to a null aware join. Sorry for that.
   If null_equal_null is true, we can replace `=` in the ON clause with `<=>` and merge it into the filter in the planner. Otherwise, we merge the ON clause into the filter directly.
   
   > how were you able to have the query use a nested loop join with a on condition?
   
   There's **no equal(`=` not `<=>`) join condition in `on`,** so the planner choose nlj
   
   https://github.com/apache/datafusion/blob/e5f596b59ece71329635d41fd7f147d1d702e49e/datafusion/core/src/physical_planner.rs#L1104-L1111



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org