Skip to content

Commit 05b7e11

Browse files
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. Co-authored-by: Qi Zhu <[email protected]>
1 parent 39e2f23 commit 05b7e11

1 file changed

Lines changed: 55 additions & 8 deletions

File tree

  • datafusion/physical-plan/src/joins

‎datafusion/physical-plan/src/joins/utils.rs‎

Lines changed: 55 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -846,15 +846,22 @@ fn estimate_inner_join_cardinality(
846846
// With the assumption that the smaller input's domain is generally represented in the bigger
847847
// input's domain, we can estimate the inner join's cardinality by taking the cartesian product
848848
// of the two inputs and normalizing it by the selectivity factor.
849-
let left_num_rows = left_stats.num_rows.get_value()?;
850-
let right_num_rows = right_stats.num_rows.get_value()?;
849+
let left_num_rows = *left_stats.num_rows.get_value()?;
850+
let right_num_rows = *right_stats.num_rows.get_value()?;
851+
// Widen before multiplying so the intermediate Cartesian product does not
852+
// overflow when the normalized cardinality is still representable as usize.
853+
let cartesian_product = (left_num_rows as u128) * (right_num_rows as u128);
854+
let normalized_cardinality =
855+
|value: usize| usize::try_from(cartesian_product / value as u128);
851856
match join_selectivity {
852-
Precision::Exact(value) if value > 0 => {
853-
Some(Precision::Exact((left_num_rows * right_num_rows) / value))
854-
}
855-
Precision::Inexact(value) if value > 0 => {
856-
Some(Precision::Inexact((left_num_rows * right_num_rows) / value))
857-
}
857+
Precision::Exact(value) if value > 0 => Some(
858+
normalized_cardinality(value)
859+
.map(Precision::Exact)
860+
.unwrap_or(Precision::Inexact(usize::MAX)),
861+
),
862+
Precision::Inexact(value) if value > 0 => Some(Precision::Inexact(
863+
normalized_cardinality(value).unwrap_or(usize::MAX),
864+
)),
858865
// Since we don't have any information about the selectivity (which is derived
859866
// from the number of distinct rows information) we can give up here for now.
860867
// And let other passes handle this (otherwise we would need to produce an
@@ -3071,6 +3078,46 @@ mod tests {
30713078
Ok(())
30723079
}
30733080

3081+
#[test]
3082+
fn test_inner_join_cardinality_multiplication_overflow() {
3083+
let statistics = |num_rows, distinct_count| Statistics {
3084+
num_rows,
3085+
total_byte_size: Absent,
3086+
column_statistics: vec![ColumnStatistics {
3087+
distinct_count,
3088+
..Default::default()
3089+
}],
3090+
};
3091+
let large_row_count = usize::MAX / 2 + 1;
3092+
3093+
// The Cartesian product overflows usize, but applying the NDV divisor
3094+
// produces a representable cardinality.
3095+
assert_eq!(
3096+
estimate_inner_join_cardinality(
3097+
statistics(Inexact(large_row_count), Inexact(1)),
3098+
statistics(Inexact(3), Inexact(3)),
3099+
),
3100+
Some(Inexact(large_row_count))
3101+
);
3102+
assert_eq!(
3103+
estimate_inner_join_cardinality(
3104+
statistics(Exact(large_row_count), Exact(1)),
3105+
statistics(Exact(3), Exact(3)),
3106+
),
3107+
Some(Exact(large_row_count))
3108+
);
3109+
3110+
// If the normalized result itself cannot fit in usize, cap the
3111+
// estimate and mark it as inexact.
3112+
assert_eq!(
3113+
estimate_inner_join_cardinality(
3114+
statistics(Exact(usize::MAX), Exact(1)),
3115+
statistics(Exact(2), Exact(1)),
3116+
),
3117+
Some(Inexact(usize::MAX))
3118+
);
3119+
}
3120+
30743121
#[test]
30753122
fn test_inner_join_cardinality_multiple_column() -> Result<()> {
30763123
let left_col_stats = vec![

0 commit comments

Comments
 (0)