Skip to content

Commit 3931ab4

Browse files
Dandandanclaude
andauthored
feat: derive a distinct count from primary key and unique constraints (apache#24520)
## Which issue does this PR close? - Closes apache#24531 ## Rationale for this change From constraints on columns such as primary key / uniqueness we can derive distinct counts (number of rows = distinct counts). This helps making it more accurate in cases when filtering / joining on those columns. ## What changes are included in this PR? ## Are there any user-facing changes? --------- Co-authored-by: Claude Opus 5 <[email protected]>
1 parent 7b7a9e8 commit 3931ab4

2 files changed

Lines changed: 315 additions & 3 deletions

File tree

‎datafusion/datasource/src/file_scan_config/mod.rs‎

Lines changed: 141 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -39,7 +39,8 @@ use arrow::datatypes::{DataType, Schema, SchemaRef};
3939
use datafusion_common::config::ConfigOptions;
4040
use datafusion_common::tree_node::TreeNodeRecursion;
4141
use datafusion_common::{
42-
Constraints, Result, ScalarValue, Statistics, internal_datafusion_err, internal_err,
42+
Constraint, Constraints, Result, ScalarValue, Statistics, internal_datafusion_err,
43+
internal_err,
4344
};
4445
use datafusion_execution::{
4546
SendableRecordBatchStream, TaskContext, object_store::ObjectStoreUrl,
@@ -542,9 +543,10 @@ impl FileScanConfigBuilder {
542543
} = self;
543544

544545
let constraints = constraints.unwrap_or_default();
545-
let statistics = statistics.unwrap_or_else(|| {
546+
let mut statistics = statistics.unwrap_or_else(|| {
546547
Statistics::new_unknown(file_source.table_schema().table_schema())
547548
});
549+
add_key_distinct_counts(&constraints, &mut statistics);
548550
let file_compression_type =
549551
file_compression_type.unwrap_or(FileCompressionType::UNCOMPRESSED);
550552

@@ -568,6 +570,32 @@ impl FileScanConfigBuilder {
568570
}
569571
}
570572

573+
/// Records that a key column holds one distinct value per row, which no file format
574+
/// stores. Single-column keys only: a composite key says nothing about its columns.
575+
fn add_key_distinct_counts(constraints: &Constraints, statistics: &mut Statistics) {
576+
let num_rows = statistics.num_rows;
577+
for constraint in constraints.iter() {
578+
let (Constraint::PrimaryKey(indices) | Constraint::Unique(indices)) = constraint;
579+
let [index] = indices[..] else {
580+
continue;
581+
};
582+
let Some(column) = statistics.column_statistics.get_mut(index) else {
583+
continue;
584+
};
585+
if column.distinct_count != Precision::Absent {
586+
continue;
587+
}
588+
// A NULL is not a distinct value. A primary key has none; a unique column may
589+
// repeat them, so an unknown count leaves the result inexact.
590+
let nulls = match (constraint, column.null_count) {
591+
(Constraint::PrimaryKey(_), Precision::Absent) => Precision::Exact(0),
592+
(_, Precision::Absent) => Precision::Inexact(0),
593+
(_, nulls) => nulls,
594+
};
595+
column.distinct_count = num_rows.sub(&nulls);
596+
}
597+
}
598+
571599
impl From<FileScanConfig> for FileScanConfigBuilder {
572600
fn from(config: FileScanConfig) -> Self {
573601
Self {
@@ -2133,6 +2161,117 @@ mod tests {
21332161
}
21342162

21352163
// sets default for configs that play no role in projections
2164+
fn config_with_constraints(
2165+
table_schema: TableSchema,
2166+
statistics: Statistics,
2167+
constraints: Vec<Constraint>,
2168+
projection: Option<Vec<usize>>,
2169+
) -> FileScanConfig {
2170+
FileScanConfigBuilder::new(
2171+
ObjectStoreUrl::parse("test:///").unwrap(),
2172+
Arc::new(MockSource::new(table_schema)),
2173+
)
2174+
.with_statistics(statistics)
2175+
.with_constraints(Constraints::new_unverified(constraints))
2176+
.with_projection_indices(projection)
2177+
.unwrap()
2178+
.build()
2179+
}
2180+
2181+
/// A key column has one distinct value per row, which no file format records.
2182+
#[test]
2183+
fn key_columns_report_a_distinct_count() {
2184+
let file_schema = Arc::new(Schema::new(vec![
2185+
Field::new("id", DataType::Int32, false),
2186+
Field::new("part", DataType::Int32, false),
2187+
Field::new("code", DataType::Int32, true),
2188+
]));
2189+
let table_schema = TableSchema::builder(Arc::clone(&file_schema)).build();
2190+
let mut statistics = Statistics::new_unknown(&file_schema);
2191+
statistics.num_rows = Precision::Exact(100);
2192+
// A unique column may repeat NULL, which is not a distinct value.
2193+
statistics.column_statistics[2].null_count = Precision::Exact(10);
2194+
2195+
let stats = |constraints| {
2196+
config_with_constraints(
2197+
table_schema.clone(),
2198+
statistics.clone(),
2199+
constraints,
2200+
None,
2201+
)
2202+
.statistics()
2203+
};
2204+
2205+
// A primary key cannot be null, so the count is as exact as the row count.
2206+
let primary_key = stats(vec![Constraint::PrimaryKey(vec![0])]);
2207+
assert_eq!(
2208+
primary_key.column_statistics[0].distinct_count,
2209+
Precision::Exact(100)
2210+
);
2211+
assert_eq!(
2212+
primary_key.column_statistics[1].distinct_count,
2213+
Precision::Absent
2214+
);
2215+
2216+
// The nulls a unique column may repeat are known here, so this is exact too.
2217+
let unique = stats(vec![Constraint::Unique(vec![2])]);
2218+
assert_eq!(
2219+
unique.column_statistics[2].distinct_count,
2220+
Precision::Exact(90)
2221+
);
2222+
2223+
// With an unknown null count it is not exact.
2224+
let mut unknown_nulls = statistics.clone();
2225+
unknown_nulls.column_statistics[2].null_count = Precision::Absent;
2226+
let unique = config_with_constraints(
2227+
table_schema.clone(),
2228+
unknown_nulls,
2229+
vec![Constraint::Unique(vec![2])],
2230+
None,
2231+
)
2232+
.statistics();
2233+
assert_eq!(
2234+
unique.column_statistics[2].distinct_count,
2235+
Precision::Inexact(100)
2236+
);
2237+
2238+
// A composite key leaves its columns alone: only the combination is unique.
2239+
let composite = stats(vec![Constraint::PrimaryKey(vec![0, 1])]);
2240+
assert_eq!(
2241+
composite.column_statistics[0].distinct_count,
2242+
Precision::Absent
2243+
);
2244+
assert_eq!(
2245+
composite.column_statistics[1].distinct_count,
2246+
Precision::Absent
2247+
);
2248+
}
2249+
2250+
/// The count has to reach the plan, which reads statistics through the projection.
2251+
#[test]
2252+
fn a_projected_scan_keeps_the_key_distinct_count() {
2253+
let file_schema = Arc::new(Schema::new(vec![
2254+
Field::new("value", DataType::Int32, true),
2255+
Field::new("id", DataType::Int32, false),
2256+
]));
2257+
let table_schema = TableSchema::builder(Arc::clone(&file_schema)).build();
2258+
let mut statistics = Statistics::new_unknown(&file_schema);
2259+
statistics.num_rows = Precision::Exact(100);
2260+
2261+
let config = config_with_constraints(
2262+
table_schema,
2263+
statistics,
2264+
vec![Constraint::PrimaryKey(vec![1])],
2265+
Some(vec![1]),
2266+
);
2267+
2268+
let projected = config.partition_statistics(None).unwrap();
2269+
assert_eq!(
2270+
projected.column_statistics[0].distinct_count,
2271+
Precision::Exact(100)
2272+
);
2273+
}
2274+
21362275
fn config_for_projection(
21372276
file_schema: SchemaRef,
21382277
projection: Option<Vec<usize>>,

‎datafusion/physical-plan/src/filter.rs‎

Lines changed: 174 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -63,7 +63,7 @@ use datafusion_execution::TaskContext;
6363
use datafusion_expr::Operator;
6464
use datafusion_physical_expr::equivalence::ProjectionMapping;
6565
use datafusion_physical_expr::expressions::{
66-
BinaryExpr, Column, IsNotNullExpr, Literal, lit,
66+
BinaryExpr, Column, InListExpr, IsNotNullExpr, Literal, lit,
6767
};
6868
use datafusion_physical_expr::intervals::utils::check_support;
6969
use datafusion_physical_expr::utils::{collect_columns, reassign_expr_columns};
@@ -343,6 +343,11 @@ impl FilterExec {
343343
let input_num_rows = input_stats.num_rows;
344344
let input_total_byte_size = input_stats.total_byte_size;
345345

346+
// A column holding each of its values once, as a primary key or unique
347+
// constraint says, matches one row per value asked for. No selectivity
348+
// expresses that.
349+
let match_limit = unique_match_limit(predicate, &input_stats);
350+
346351
let (selectivity, num_rows, column_statistics) = if is_infeasible {
347352
// Contradictory predicate: no rows survive. Row-bounded counts are
348353
// zero; value statistics are undefined on an empty column.
@@ -406,6 +411,10 @@ impl FilterExec {
406411
}
407412
};
408413

414+
let num_rows = match (match_limit, num_rows.get_value()) {
415+
(Some(limit), Some(rows)) if *rows > limit => Precision::Inexact(limit),
416+
_ => num_rows,
417+
};
409418
let total_byte_size =
410419
scale_byte_size_at_rows(input_total_byte_size, selectivity, num_rows);
411420

@@ -972,6 +981,76 @@ impl EmbeddedProjection for FilterExec {
972981
}
973982
}
974983

984+
/// The most rows a filter can match, when it restricts a column holding each value
985+
/// once to a fixed set of values: one row per value.
986+
fn unique_match_limit(
987+
predicate: &Arc<dyn PhysicalExpr>,
988+
statistics: &Statistics,
989+
) -> Option<usize> {
990+
let mut limit: Option<usize> = None;
991+
for expr in split_conjunction(predicate) {
992+
let Some((index, values)) = restricted_column(expr) else {
993+
continue;
994+
};
995+
let holds_once = statistics
996+
.column_statistics
997+
.get(index)
998+
.is_some_and(|column| holds_each_value_once(column, &statistics.num_rows));
999+
if !holds_once {
1000+
continue;
1001+
}
1002+
limit = Some(limit.map_or(values, |limit: usize| limit.min(values)));
1003+
}
1004+
limit
1005+
}
1006+
1007+
/// The column an expression restricts to a fixed set of values, and how many values
1008+
/// that is. NULL is never one of them: it matches nothing.
1009+
fn restricted_column(expr: &Arc<dyn PhysicalExpr>) -> Option<(usize, usize)> {
1010+
if let Some(in_list) = expr.downcast_ref::<InListExpr>() {
1011+
if in_list.negated() {
1012+
return None;
1013+
}
1014+
let column = in_list.expr().downcast_ref::<Column>()?;
1015+
let mut values: Vec<&ScalarValue> = vec![];
1016+
for expr in in_list.list() {
1017+
let value = expr.downcast_ref::<Literal>()?.value();
1018+
if !value.is_null() && !values.contains(&value) {
1019+
values.push(value);
1020+
}
1021+
}
1022+
return Some((column.index(), values.len()));
1023+
}
1024+
1025+
let binary = expr.downcast_ref::<BinaryExpr>()?;
1026+
if *binary.op() != Operator::Eq {
1027+
return None;
1028+
}
1029+
let (column, literal) = match (
1030+
binary.left().downcast_ref::<Column>(),
1031+
binary.right().downcast_ref::<Column>(),
1032+
) {
1033+
(Some(column), None) => (column, binary.right()),
1034+
(None, Some(column)) => (column, binary.left()),
1035+
_ => return None,
1036+
};
1037+
let value = literal.downcast_ref::<Literal>()?.value();
1038+
(!value.is_null()).then_some((column.index(), 1))
1039+
}
1040+
1041+
/// Whether the column has as many distinct values as it has non-null rows, so each
1042+
/// value appears once.
1043+
fn holds_each_value_once(column: &ColumnStatistics, num_rows: &Precision<usize>) -> bool {
1044+
let (Some(rows), Some(distinct), Some(nulls)) = (
1045+
num_rows.get_value(),
1046+
column.distinct_count.get_value(),
1047+
column.null_count.get_value(),
1048+
) else {
1049+
return false;
1050+
};
1051+
distinct.saturating_add(*nulls) >= *rows
1052+
}
1053+
9751054
/// Collects column equality information from `col = literal` predicates in a
9761055
/// conjunction.
9771056
///
@@ -1486,6 +1565,100 @@ mod tests {
14861565
Ok(())
14871566
}
14881567

1568+
/// An equality on a column that holds each value once matches one row at most,
1569+
/// including on a type interval analysis cannot read, where the default
1570+
/// selectivity would otherwise apply.
1571+
#[tokio::test]
1572+
async fn test_filter_statistics_equality_on_a_unique_column() -> Result<()> {
1573+
let schema = Schema::new(vec![Field::new("id", DataType::Utf8, true)]);
1574+
let unique = ColumnStatistics {
1575+
null_count: Precision::Exact(0),
1576+
distinct_count: Precision::Exact(100),
1577+
..Default::default()
1578+
};
1579+
let rows = |column: ColumnStatistics| -> Result<Precision<usize>> {
1580+
let input = Arc::new(StatisticsExec::new(
1581+
Statistics {
1582+
num_rows: Precision::Exact(100),
1583+
total_byte_size: Precision::Exact(800),
1584+
column_statistics: vec![column],
1585+
},
1586+
schema.clone(),
1587+
));
1588+
let predicate =
1589+
binary(col("id", &schema)?, Operator::Eq, lit("seven"), &schema)?;
1590+
let filter: Arc<dyn ExecutionPlan> =
1591+
Arc::new(FilterExec::try_new(predicate, input)?);
1592+
Ok(StatisticsContext::new()
1593+
.compute(filter.as_ref(), &StatisticsArgs::new())?
1594+
.num_rows)
1595+
};
1596+
1597+
assert_eq!(rows(unique.clone())?, Precision::Inexact(1));
1598+
1599+
// The nulls a unique column may repeat do not make it hold a value twice.
1600+
assert_eq!(
1601+
rows(ColumnStatistics {
1602+
null_count: Precision::Exact(10),
1603+
distinct_count: Precision::Exact(90),
1604+
..unique.clone()
1605+
})?,
1606+
Precision::Inexact(1)
1607+
);
1608+
1609+
// Without a distinct count, the default selectivity applies as before.
1610+
assert_eq!(
1611+
rows(ColumnStatistics {
1612+
distinct_count: Precision::Absent,
1613+
..unique
1614+
})?,
1615+
Precision::Inexact(20)
1616+
);
1617+
1618+
Ok(())
1619+
}
1620+
1621+
/// Asking a unique column for three values matches three rows at most.
1622+
#[tokio::test]
1623+
async fn test_filter_statistics_in_list_on_a_unique_column() -> Result<()> {
1624+
use datafusion_physical_expr::expressions::in_list;
1625+
1626+
let schema = Schema::new(vec![Field::new("id", DataType::Utf8, true)]);
1627+
let rows = |list: Vec<&str>, negated: bool| -> Result<Precision<usize>> {
1628+
let input = Arc::new(StatisticsExec::new(
1629+
Statistics {
1630+
num_rows: Precision::Exact(100),
1631+
total_byte_size: Precision::Exact(800),
1632+
column_statistics: vec![ColumnStatistics {
1633+
null_count: Precision::Exact(0),
1634+
distinct_count: Precision::Exact(100),
1635+
..Default::default()
1636+
}],
1637+
},
1638+
schema.clone(),
1639+
));
1640+
let predicate = in_list(
1641+
col("id", &schema)?,
1642+
list.into_iter().map(|value| lit(value) as _).collect(),
1643+
&negated,
1644+
&schema,
1645+
)?;
1646+
let filter: Arc<dyn ExecutionPlan> =
1647+
Arc::new(FilterExec::try_new(predicate, input)?);
1648+
Ok(StatisticsContext::new()
1649+
.compute(filter.as_ref(), &StatisticsArgs::new())?
1650+
.num_rows)
1651+
};
1652+
1653+
assert_eq!(rows(vec!["a", "b", "c"], false)?, Precision::Inexact(3));
1654+
// Repeats ask for the same row twice.
1655+
assert_eq!(rows(vec!["a", "b", "a"], false)?, Precision::Inexact(2));
1656+
// `NOT IN` selects nearly everything, so the default applies.
1657+
assert_eq!(rows(vec!["a", "b", "c"], true)?, Precision::Inexact(20));
1658+
1659+
Ok(())
1660+
}
1661+
14891662
#[tokio::test]
14901663
async fn test_filter_statistics_basic_expr() -> Result<()> {
14911664
// Table:

0 commit comments

Comments
 (0)