(datafusion) 01/01: fix: avoid overflow in join cardinality estimation (#23788)

[gi...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-23788-dfe0f26b5f944c2ca7dfa748313f8eac00232775
in repository https://gitbox.apache.org/repos/asf/datafusion.git

commit 9f3f98f0d46fb8c4720a4ce39c9bb6213f4fb2e2
Author: xudong.w <wx...@gmail.com>
AuthorDate: Wed Jul 22 18:25:54 2026 +0800

    fix: avoid overflow in join cardinality estimation (#23788)
    
    ## Which issue does this PR close?
    
    - Closes #23787.
    
    ## Rationale for this change
    
    Join cardinality estimation multiplies two `usize` row counts before
    applying the join-key NDV divisor. A large Cartesian-product
    intermediate can therefore overflow and panic even when the normalized
    cardinality is representable. Saturating the product before division
    would avoid the panic but produce an inaccurate estimate.
    
    ## What changes are included in this PR?
    
    - Compute the Cartesian-product intermediate with `u128` before applying
    the NDV divisor.
    - Preserve exact estimates when the normalized result fits in `usize`.
    - Cap an unrepresentable final result at `usize::MAX` and mark it
    inexact, consistent with existing statistics arithmetic.
    - Add regression coverage for exact and inexact statistics and for
    final-result overflow.
    
    ## Are these changes tested?
    
    Yes.
    ## Are there any user-facing changes?
    
    Queries with very large join statistics no longer panic during
    cardinality estimation. There are no public API changes.
---
 datafusion/physical-plan/src/joins/utils.rs | 63 +++++++++++++++++++++++++----
 1 file changed, 55 insertions(+), 8 deletions(-)

diff --git a/datafusion/physical-plan/src/joins/utils.rs b/datafusion/physical-plan/src/joins/utils.rs
index 90b39f7ada..654d873ae1 100644
--- a/datafusion/physical-plan/src/joins/utils.rs
+++ b/datafusion/physical-plan/src/joins/utils.rs
@@ -846,15 +846,22 @@ fn estimate_inner_join_cardinality(
     // With the assumption that the smaller input's domain is generally represented in the bigger
     // input's domain, we can estimate the inner join's cardinality by taking the cartesian product
     // of the two inputs and normalizing it by the selectivity factor.
-    let left_num_rows = left_stats.num_rows.get_value()?;
-    let right_num_rows = right_stats.num_rows.get_value()?;
+    let left_num_rows = *left_stats.num_rows.get_value()?;
+    let right_num_rows = *right_stats.num_rows.get_value()?;
+    // Widen before multiplying so the intermediate Cartesian product does not
+    // overflow when the normalized cardinality is still representable as usize.
+    let cartesian_product = (left_num_rows as u128) * (right_num_rows as u128);
+    let normalized_cardinality =
+        |value: usize| usize::try_from(cartesian_product / value as u128);
     match join_selectivity {
-        Precision::Exact(value) if value > 0 => {
-            Some(Precision::Exact((left_num_rows * right_num_rows) / value))
-        }
-        Precision::Inexact(value) if value > 0 => {
-            Some(Precision::Inexact((left_num_rows * right_num_rows) / value))
-        }
+        Precision::Exact(value) if value > 0 => Some(
+            normalized_cardinality(value)
+                .map(Precision::Exact)
+                .unwrap_or(Precision::Inexact(usize::MAX)),
+        ),
+        Precision::Inexact(value) if value > 0 => Some(Precision::Inexact(
+            normalized_cardinality(value).unwrap_or(usize::MAX),
+        )),
         // Since we don't have any information about the selectivity (which is derived
         // from the number of distinct rows information) we can give up here for now.
         // And let other passes handle this (otherwise we would need to produce an
@@ -3071,6 +3078,46 @@ mod tests {
         Ok(())
     }
 
+    #[test]
+    fn test_inner_join_cardinality_multiplication_overflow() {
+        let statistics = |num_rows, distinct_count| Statistics {
+            num_rows,
+            total_byte_size: Absent,
+            column_statistics: vec![ColumnStatistics {
+                distinct_count,
+                ..Default::default()
+            }],
+        };
+        let large_row_count = usize::MAX / 2 + 1;
+
+        // The Cartesian product overflows usize, but applying the NDV divisor
+        // produces a representable cardinality.
+        assert_eq!(
+            estimate_inner_join_cardinality(
+                statistics(Inexact(large_row_count), Inexact(1)),
+                statistics(Inexact(3), Inexact(3)),
+            ),
+            Some(Inexact(large_row_count))
+        );
+        assert_eq!(
+            estimate_inner_join_cardinality(
+                statistics(Exact(large_row_count), Exact(1)),
+                statistics(Exact(3), Exact(3)),
+            ),
+            Some(Exact(large_row_count))
+        );
+
+        // If the normalized result itself cannot fit in usize, cap the
+        // estimate and mark it as inexact.
+        assert_eq!(
+            estimate_inner_join_cardinality(
+                statistics(Exact(usize::MAX), Exact(1)),
+                statistics(Exact(2), Exact(1)),
+            ),
+            Some(Inexact(usize::MAX))
+        );
+    }
+
     #[test]
     fn test_inner_join_cardinality_multiple_column() -> Result<()> {
         let left_col_stats = vec![


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