Skip to content

Commit 6145a09

Browse files
feat: estimate Decimal filter selectivity with interval analysis (#25790)
## Which issue does this PR close? - Closes #25613. ## Rationale for this change Decimal columns were excluded from interval analysis, so any filter touching one fell back to the default 20% selectivity. For the Q6-style predicate in the issue, that meant estimating ~1.2M rows when only ~114K match. ## What changes are included in this PR? - `FilterExec` statistics use a new `check_statistics_support`, which also accepts Decimal32/64/128/256. - `next_value` / `prev_value` handle decimals, so strict comparisons get tight bounds (`x < 24.00` becomes `x <= 23.99`). At the limit of a decimal's precision the bound becomes unbounded instead of overflowing. - `get_extreme_value!` supports Decimal32/64, which previously hit `unreachable!()`. - `CastExpr` now propagates constraints back through lossless decimal widening casts. Without this, a literal with a different scale than the column (e.g. `a >= 0.055` on `Decimal(15, 2)`, coerced to `Decimal128(30, 15)`) left the column range untouched and the estimate at 100%. - Decimal arithmetic (`+ - * / %`) is not analyzed: it changes the precision and scale of its operands, so those predicates keep the default selectivity. `check_support` and `is_datatype_supported` are unchanged, so symmetric hash join pruning behaves as before. Decimal support there could be a follow-up. ## What is the testing strategy for this PR? - Unit tests for decimal next/prev values across all four widths, including precision boundaries like 9.99 / -9.99 for `Decimal(3, 2)`, plus strict comparison bounds and Decimal32/64 overflow handling. - `test_filter_statistics_decimal_expr` and `test_filter_statistics_decimal_mixed_scale_expr` check row estimates and tightened min/max for same-scale and mixed-scale predicates. The mixed-scale test mirrors the plan the SQL planner produces. - `test_filter_statistics_decimal_arithmetic_expr` checks that decimal multiplication and subtraction predicates use the default selectivity and keep the column's own type. - `filter_statistics_decimal.slt` runs Q6-style ranges with fractional literals on a parquet table with min/max stats, checking EXPLAIN estimates and query results, including a mixed-scale literal and decimal arithmetic. - New cases in `test_cast_constraint_propagation`, plus boundary checks that propagating through a decimal widening cast never excludes a valid input, covering cross-width casts, a negative scale and the precision limits. - `test_custom_filter_selectivity` relied on decimals being unsupported, so I switched it to `Utf8`. - No existing sqllogictest or TPC-H/TPC-DS plan outputs changed. Reproducer from the issue (TPC-H SF1, current main): | SELECT | Before | After | Actual | | ------------------------- | --------: | ------: | ------: | | Date range | 869,535 | 869,535 | 909,455 | | Date + Decimal conditions | 1,200,243 | 111,291 | 114,160 | Worth a closer look in review: - The cast change extends the allowlist added in #25531. Decimal widening is lossless and order-preserving, and casting bounds back rounds to a neighboring value, which only widens the range. That reasoning is what makes it safe, so I'd appreciate a second opinion on it. - A decimal column with no min/max stats now gets selectivity 1.0 instead of the default, which matches how integer columns already behave. ## Are there any user-facing changes? Better row estimates for filters on decimal columns, which may change some plan choices. One new public function, `check_statistics_support`; no breaking changes.
1 parent 2bb383e commit 6145a09

5 files changed

Lines changed: 744 additions & 19 deletions

File tree

‎datafusion/expr-common/src/interval_arithmetic.rs‎

Lines changed: 237 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -27,8 +27,10 @@ use crate::type_coercion::binary::{BinaryTypeCoercer, comparison_coercion};
2727
use arrow::compute::{CastOptions, cast_with_options};
2828
use arrow::datatypes::{
2929
DataType, IntervalDayTime, IntervalMonthDayNano, IntervalUnit,
30+
MAX_DECIMAL32_FOR_EACH_PRECISION, MAX_DECIMAL64_FOR_EACH_PRECISION,
3031
MAX_DECIMAL128_FOR_EACH_PRECISION, MAX_DECIMAL256_FOR_EACH_PRECISION,
31-
MIN_DECIMAL128_FOR_EACH_PRECISION, MIN_DECIMAL256_FOR_EACH_PRECISION, TimeUnit,
32+
MIN_DECIMAL32_FOR_EACH_PRECISION, MIN_DECIMAL64_FOR_EACH_PRECISION,
33+
MIN_DECIMAL128_FOR_EACH_PRECISION, MIN_DECIMAL256_FOR_EACH_PRECISION, TimeUnit, i256,
3234
};
3335
use datafusion_common::rounding::{alter_fp_rounding_mode, next_down, next_up};
3436
use datafusion_common::{
@@ -37,7 +39,14 @@ use datafusion_common::{
3739
};
3840

3941
macro_rules! get_extreme_value {
40-
($extreme:ident, $DECIMAL128_ARRAY:ident, $DECIMAL256_ARRAY:ident, $value:expr) => {
42+
(
43+
$extreme:ident,
44+
$DECIMAL32_ARRAY:ident,
45+
$DECIMAL64_ARRAY:ident,
46+
$DECIMAL128_ARRAY:ident,
47+
$DECIMAL256_ARRAY:ident,
48+
$value:expr
49+
) => {
4150
match $value {
4251
DataType::UInt8 => ScalarValue::UInt8(Some(u8::$extreme)),
4352
DataType::UInt16 => ScalarValue::UInt16(Some(u16::$extreme)),
@@ -84,6 +93,16 @@ macro_rules! get_extreme_value {
8493
DataType::Interval(IntervalUnit::MonthDayNano) => {
8594
ScalarValue::IntervalMonthDayNano(Some(IntervalMonthDayNano::$extreme))
8695
}
96+
DataType::Decimal32(precision, scale) => ScalarValue::Decimal32(
97+
Some($DECIMAL32_ARRAY[*precision as usize]),
98+
*precision,
99+
*scale,
100+
),
101+
DataType::Decimal64(precision, scale) => ScalarValue::Decimal64(
102+
Some($DECIMAL64_ARRAY[*precision as usize]),
103+
*precision,
104+
*scale,
105+
),
87106
DataType::Decimal128(precision, scale) => ScalarValue::Decimal128(
88107
Some($DECIMAL128_ARRAY[*precision as usize]),
89108
*precision,
@@ -100,7 +119,15 @@ macro_rules! get_extreme_value {
100119
}
101120

102121
macro_rules! value_transition {
103-
($bound:ident, $direction:expr, $value:expr) => {
122+
(
123+
$bound:ident,
124+
$direction:expr,
125+
$DECIMAL32_ARRAY:ident,
126+
$DECIMAL64_ARRAY:ident,
127+
$DECIMAL128_ARRAY:ident,
128+
$DECIMAL256_ARRAY:ident,
129+
$value:expr
130+
) => {
104131
match $value {
105132
UInt8(Some(value)) if value == u8::$bound => UInt8(None),
106133
UInt16(Some(value)) if value == u16::$bound => UInt16(None),
@@ -147,6 +174,28 @@ macro_rules! value_transition {
147174
{
148175
IntervalMonthDayNano(None)
149176
}
177+
// Decimals saturate at the extreme value of their precision, not of
178+
// the underlying integer type:
179+
Decimal32(Some(value), precision, scale)
180+
if value == $DECIMAL32_ARRAY[precision as usize] =>
181+
{
182+
Decimal32(None, precision, scale)
183+
}
184+
Decimal64(Some(value), precision, scale)
185+
if value == $DECIMAL64_ARRAY[precision as usize] =>
186+
{
187+
Decimal64(None, precision, scale)
188+
}
189+
Decimal128(Some(value), precision, scale)
190+
if value == $DECIMAL128_ARRAY[precision as usize] =>
191+
{
192+
Decimal128(None, precision, scale)
193+
}
194+
Decimal256(Some(value), precision, scale)
195+
if value == $DECIMAL256_ARRAY[precision as usize] =>
196+
{
197+
Decimal256(None, precision, scale)
198+
}
150199
_ => next_value_helper::<$direction>($value),
151200
}
152201
};
@@ -1208,6 +1257,8 @@ fn handle_overflow<const UPPER: bool>(
12081257
(true, false) => {
12091258
get_extreme_value!(
12101259
MIN,
1260+
MIN_DECIMAL32_FOR_EACH_PRECISION,
1261+
MIN_DECIMAL64_FOR_EACH_PRECISION,
12111262
MIN_DECIMAL128_FOR_EACH_PRECISION,
12121263
MIN_DECIMAL256_FOR_EACH_PRECISION,
12131264
dt
@@ -1216,6 +1267,8 @@ fn handle_overflow<const UPPER: bool>(
12161267
(false, true) => {
12171268
get_extreme_value!(
12181269
MAX,
1270+
MAX_DECIMAL32_FOR_EACH_PRECISION,
1271+
MAX_DECIMAL64_FOR_EACH_PRECISION,
12191272
MAX_DECIMAL128_FOR_EACH_PRECISION,
12201273
MAX_DECIMAL256_FOR_EACH_PRECISION,
12211274
dt
@@ -1228,14 +1281,30 @@ fn handle_overflow<const UPPER: bool>(
12281281
// used without caution.
12291282
fn next_value(value: ScalarValue) -> ScalarValue {
12301283
use ScalarValue::*;
1231-
value_transition!(MAX, true, value)
1284+
value_transition!(
1285+
MAX,
1286+
true,
1287+
MAX_DECIMAL32_FOR_EACH_PRECISION,
1288+
MAX_DECIMAL64_FOR_EACH_PRECISION,
1289+
MAX_DECIMAL128_FOR_EACH_PRECISION,
1290+
MAX_DECIMAL256_FOR_EACH_PRECISION,
1291+
value
1292+
)
12321293
}
12331294

12341295
// This function should remain private since it may corrupt the an interval if
12351296
// used without caution.
12361297
fn prev_value(value: ScalarValue) -> ScalarValue {
12371298
use ScalarValue::*;
1238-
value_transition!(MIN, false, value)
1299+
value_transition!(
1300+
MIN,
1301+
false,
1302+
MIN_DECIMAL32_FOR_EACH_PRECISION,
1303+
MIN_DECIMAL64_FOR_EACH_PRECISION,
1304+
MIN_DECIMAL128_FOR_EACH_PRECISION,
1305+
MIN_DECIMAL256_FOR_EACH_PRECISION,
1306+
value
1307+
)
12391308
}
12401309

12411310
trait OneTrait: Sized + std::ops::Add + std::ops::Sub {
@@ -1246,6 +1315,12 @@ macro_rules! impl_OneTrait{
12461315
}
12471316
impl_OneTrait! {u8, u16, u32, u64, i8, i16, i32, i64, i128}
12481317

1318+
impl OneTrait for i256 {
1319+
fn one() -> Self {
1320+
i256::ONE
1321+
}
1322+
}
1323+
12491324
impl OneTrait for IntervalDayTime {
12501325
fn one() -> Self {
12511326
IntervalDayTime {
@@ -1300,6 +1375,23 @@ fn next_value_helper<const INC: bool>(value: ScalarValue) -> ScalarValue {
13001375
UInt16(Some(val)) => UInt16(Some(increment_decrement::<INC, u16>(val))),
13011376
UInt32(Some(val)) => UInt32(Some(increment_decrement::<INC, u32>(val))),
13021377
UInt64(Some(val)) => UInt64(Some(increment_decrement::<INC, u64>(val))),
1378+
// Decimals step by one unit in the last place, keeping precision and scale:
1379+
Decimal32(Some(val), precision, scale) => {
1380+
Decimal32(Some(increment_decrement::<INC, i32>(val)), precision, scale)
1381+
}
1382+
Decimal64(Some(val), precision, scale) => {
1383+
Decimal64(Some(increment_decrement::<INC, i64>(val)), precision, scale)
1384+
}
1385+
Decimal128(Some(val), precision, scale) => Decimal128(
1386+
Some(increment_decrement::<INC, i128>(val)),
1387+
precision,
1388+
scale,
1389+
),
1390+
Decimal256(Some(val), precision, scale) => Decimal256(
1391+
Some(increment_decrement::<INC, i256>(val)),
1392+
precision,
1393+
scale,
1394+
),
13031395
DurationSecond(Some(val)) => {
13041396
DurationSecond(Some(increment_decrement::<INC, i64>(val)))
13051397
}
@@ -2281,7 +2373,10 @@ mod tests {
22812373

22822374
use crate::interval_arithmetic::NullableInterval;
22832375
use arrow::compute::CastOptions;
2284-
use arrow::datatypes::DataType;
2376+
use arrow::datatypes::{
2377+
DataType, MAX_DECIMAL128_FOR_EACH_PRECISION, MIN_DECIMAL128_FOR_EACH_PRECISION,
2378+
i256,
2379+
};
22852380
use datafusion_common::rounding::{next_down, next_up};
22862381
use datafusion_common::{Result, ScalarValue};
22872382

@@ -2594,6 +2689,124 @@ mod tests {
25942689
Ok(())
25952690
}
25962691

2692+
#[test]
2693+
fn test_next_prev_value_decimal() {
2694+
use ScalarValue::*;
2695+
2696+
// Decimals step by one unit in the last place, keeping precision and scale:
2697+
let cases = vec![
2698+
(Decimal32(Some(2400), 9, 2), Decimal32(Some(2401), 9, 2)),
2699+
(Decimal64(Some(2400), 18, 2), Decimal64(Some(2401), 18, 2)),
2700+
(Decimal128(Some(2400), 15, 2), Decimal128(Some(2401), 15, 2)),
2701+
(
2702+
Decimal256(Some(i256::from(2400)), 40, 2),
2703+
Decimal256(Some(i256::from(2401)), 40, 2),
2704+
),
2705+
(Decimal128(Some(-1), 3, 2), Decimal128(Some(0), 3, 2)),
2706+
];
2707+
for (value, next) in cases {
2708+
assert_eq!(next_value(value.clone()), next);
2709+
assert_eq!(prev_value(next), value);
2710+
}
2711+
2712+
// Values at the extremes of their precision (e.g. -9.99 and 9.99 for
2713+
// precision 3, scale 2) become unbounded:
2714+
let d128_max = MAX_DECIMAL128_FOR_EACH_PRECISION[38];
2715+
let d128_min = MIN_DECIMAL128_FOR_EACH_PRECISION[38];
2716+
let cases = vec![
2717+
(
2718+
Decimal32(Some(-999), 3, 2),
2719+
Decimal32(Some(999), 3, 2),
2720+
Decimal32(Some(-998), 3, 2),
2721+
Decimal32(Some(998), 3, 2),
2722+
Decimal32(None, 3, 2),
2723+
),
2724+
(
2725+
Decimal64(Some(-999), 3, 2),
2726+
Decimal64(Some(999), 3, 2),
2727+
Decimal64(Some(-998), 3, 2),
2728+
Decimal64(Some(998), 3, 2),
2729+
Decimal64(None, 3, 2),
2730+
),
2731+
(
2732+
Decimal128(Some(-999), 3, 2),
2733+
Decimal128(Some(999), 3, 2),
2734+
Decimal128(Some(-998), 3, 2),
2735+
Decimal128(Some(998), 3, 2),
2736+
Decimal128(None, 3, 2),
2737+
),
2738+
(
2739+
Decimal256(Some(i256::from(-999)), 3, 2),
2740+
Decimal256(Some(i256::from(999)), 3, 2),
2741+
Decimal256(Some(i256::from(-998)), 3, 2),
2742+
Decimal256(Some(i256::from(998)), 3, 2),
2743+
Decimal256(None, 3, 2),
2744+
),
2745+
(
2746+
Decimal128(Some(d128_min), 38, 0),
2747+
Decimal128(Some(d128_max), 38, 0),
2748+
Decimal128(Some(d128_min + 1), 38, 0),
2749+
Decimal128(Some(d128_max - 1), 38, 0),
2750+
Decimal128(None, 38, 0),
2751+
),
2752+
];
2753+
for (min, max, after_min, before_max, inf) in cases {
2754+
assert_eq!(next_value(max.clone()), inf);
2755+
assert_eq!(prev_value(max), before_max);
2756+
2757+
assert_eq!(prev_value(min.clone()), inf);
2758+
assert_eq!(next_value(min), after_min);
2759+
2760+
assert_eq!(next_value(inf.clone()), inf);
2761+
assert_eq!(prev_value(inf.clone()), inf);
2762+
}
2763+
}
2764+
2765+
#[test]
2766+
fn test_satisfy_strict_comparison_decimal() -> Result<()> {
2767+
use ScalarValue::*;
2768+
2769+
// x in [0.00, 50.00], constraint 24.00 > x tightens x to [0.00, 23.99]:
2770+
let x =
2771+
Interval::try_new(Decimal128(Some(0), 15, 2), Decimal128(Some(5000), 15, 2))?;
2772+
let literal = Interval::try_new(
2773+
Decimal128(Some(2400), 15, 2),
2774+
Decimal128(Some(2400), 15, 2),
2775+
)?;
2776+
let (_, x_lt) = satisfy_greater(&literal, &x, true)?.unwrap();
2777+
assert_eq!(
2778+
x_lt,
2779+
Interval::try_new(Decimal128(Some(0), 15, 2), Decimal128(Some(2399), 15, 2))?
2780+
);
2781+
2782+
// Constraint x > 24.00 tightens x to [24.01, 50.00]:
2783+
let (x_gt, _) = satisfy_greater(&x, &literal, true)?.unwrap();
2784+
assert_eq!(
2785+
x_gt,
2786+
Interval::try_new(
2787+
Decimal128(Some(2401), 15, 2),
2788+
Decimal128(Some(5000), 15, 2),
2789+
)?
2790+
);
2791+
2792+
// Non-strict comparisons keep the closed bound:
2793+
let (_, x_le) = satisfy_greater(&literal, &x, false)?.unwrap();
2794+
assert_eq!(
2795+
x_le,
2796+
Interval::try_new(Decimal128(Some(0), 15, 2), Decimal128(Some(2400), 15, 2))?
2797+
);
2798+
2799+
// A strict bound at the precision's extreme conservatively becomes
2800+
// unbounded instead of stepping past it (x > 9.99 for Decimal128(3, 2)):
2801+
let x = Interval::make_unbounded(&DataType::Decimal128(3, 2))?;
2802+
let max =
2803+
Interval::try_new(Decimal128(Some(999), 3, 2), Decimal128(Some(999), 3, 2))?;
2804+
let (x_gt, _) = satisfy_greater(&x, &max, true)?.unwrap();
2805+
assert_eq!(x_gt, Interval::make_unbounded(&DataType::Decimal128(3, 2))?);
2806+
2807+
Ok(())
2808+
}
2809+
25972810
#[test]
25982811
fn test_new_interval() -> Result<()> {
25992812
use ScalarValue::*;
@@ -4407,6 +4620,24 @@ mod tests {
44074620
ScalarValue::Decimal128(Some(99999999999999999999999999999999999999), 38, 35)
44084621
);
44094622

4623+
// Test Decimal32/Decimal64 underflow handling:
4624+
let op = Operator::Minus;
4625+
let dt = DataType::Decimal32(3, 2);
4626+
let lhs = ScalarValue::Decimal32(Some(-999), 3, 2);
4627+
let rhs = ScalarValue::Decimal32(Some(1), 3, 2);
4628+
let result = handle_overflow::<true>(&dt, op, &lhs, &rhs);
4629+
assert_eq!(result, ScalarValue::Decimal32(Some(-999), 3, 2));
4630+
let result = handle_overflow::<false>(&dt, op, &lhs, &rhs);
4631+
assert_eq!(result, ScalarValue::Decimal32(None, 3, 2));
4632+
4633+
let dt = DataType::Decimal64(3, 2);
4634+
let lhs = ScalarValue::Decimal64(Some(-999), 3, 2);
4635+
let rhs = ScalarValue::Decimal64(Some(1), 3, 2);
4636+
let result = handle_overflow::<true>(&dt, op, &lhs, &rhs);
4637+
assert_eq!(result, ScalarValue::Decimal64(Some(-999), 3, 2));
4638+
let result = handle_overflow::<false>(&dt, op, &lhs, &rhs);
4639+
assert_eq!(result, ScalarValue::Decimal64(None, 3, 2));
4640+
44104641
Ok(())
44114642
}
44124643

0 commit comments

Comments
 (0)