You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/07/22 12:08:29 UTC
(datafusion) branch gh-readonly-queue/main/pr-23788-39e2f23a3fbeebf4eebc3160d91a29c6a7286be7 created (now 05b7e11c7e)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-23788-39e2f23a3fbeebf4eebc3160d91a29c6a7286be7
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at 05b7e11c7e fix: avoid overflow in join cardinality estimation (#23788)
This branch includes the following new commits:
new 05b7e11c7e fix: avoid overflow in join cardinality estimation (#23788)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: fix: avoid overflow in join cardinality estimation (#23788)
Posted by 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-39e2f23a3fbeebf4eebc3160d91a29c6a7286be7
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit 05b7e11c7e459b21510cb96c5d20654e34646cfc
Author: xudong.w <wx...@gmail.com>
AuthorDate: Wed Jul 22 20:08:04 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.
Co-authored-by: Qi Zhu <zh...@gmail.com>
---
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