Skip to content

Commit dc92a7f

Browse files
author
unknown
committed
perf: per-batch fast path for IS NOT NULL over null-free batches
Replace the build-time predicate simplification with a runtime fast path in FilterExecStream: when the predicate is exactly a bare 'col IS NOT NULL' and the batch's column reports null_count() == 0 (O(1) cached), skip mask evaluation and filter_record_batch and push the batch into the coalescer unchanged. The build-time approach regressed joins by ~45%: simplifying the predicate to lit(true) let FilterPushdown delete the FilterExec node, losing its implicit batch coalescing; HashJoin then received 2x more, 2x smaller batches. The fast path keeps the plan shape identical to main while still skipping evaluation on null-free data (measured ~20% on sum(id) WHERE id IS NOT NULL over 4M rows). Also restores predicates.slt to its main expectation (FilterExec remains in the physical plan) and adds unit tests for both paths.
1 parent 913eac0 commit dc92a7f

2 files changed

Lines changed: 73 additions & 207 deletions

File tree

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

Lines changed: 71 additions & 206 deletions
Original file line numberDiff line numberDiff line change
@@ -205,23 +205,16 @@ impl FilterExecBuilder {
205205
// Validate projection if provided
206206
can_project(&self.input.schema(), self.projection.as_deref())?;
207207

208-
// Simplify the predicate using input statistics: drop `col IS NOT NULL`
209-
// conjuncts for columns whose input null_count is provably zero. Such
210-
// conjuncts always evaluate to true, yet still cost a full evaluation
211-
// and batch copy per input batch (measured 100% selectivity on
212-
// join-key filters over NOT NULL data, e.g. TPC-H keys).
213-
let predicate = simplify_not_null_conjuncts(self.predicate, &self.input);
214-
215208
// Compute properties once with all parameters
216209
let cache = FilterExec::compute_properties(
217210
&self.input,
218-
&predicate,
211+
&self.predicate,
219212
self.default_selectivity,
220213
self.projection.as_deref(),
221214
)?;
222215

223216
Ok(FilterExec {
224-
predicate,
217+
predicate: self.predicate,
225218
input: self.input,
226219
metrics: ExecutionPlanMetricsSet::new(),
227220
default_selectivity: self.default_selectivity,
@@ -628,18 +621,6 @@ impl ExecutionPlan for FilterExec {
628621
context.session_id(),
629622
context.task_id()
630623
);
631-
// A predicate that is provably `true` (e.g. after statistics-driven
632-
// simplification dropped all conjuncts) makes this operator a
633-
// pass-through: hand back the input stream directly instead of
634-
// paying mask evaluation, `filter_record_batch`, coalescing and
635-
// metrics per batch. Only valid when no projection / fetch needs to
636-
// be applied on top of the input batches.
637-
if self.predicate.eq(&lit(true))
638-
&& self.fetch.is_none()
639-
&& self.projection.is_none()
640-
{
641-
return self.input.execute(partition, context);
642-
}
643624
let metrics = FilterExecMetrics::new(&self.metrics, partition);
644625
Ok(Box::pin(FilterExecStream {
645626
schema: self.schema(),
@@ -1150,67 +1131,19 @@ fn collect_equality_columns(predicate: &Arc<dyn PhysicalExpr>) -> (HashSet<usize
11501131
(eq_values.into_keys().collect(), infeasible)
11511132
}
11521133

1153-
/// Removes `col IS NOT NULL` conjuncts whose column is provably non-null in
1154-
/// the input statistics (`null_count == Exact(0)`). Returns the original
1155-
/// predicate (Arc clone) when nothing can be dropped.
1134+
/// If `predicate` is exactly `Column IS NOT NULL` (a single bare conjunct,
1135+
/// the shape `filter_null_join_keys` injects on join inputs), return the
1136+
/// column. Used by `FilterExecStream` to skip mask evaluation and
1137+
/// `filter_record_batch` for batches where the column is provably null-free
1138+
/// (`Array::null_count() == 0`, an O(1) cached value in arrow).
11561139
///
1157-
/// This is the statistics-driven inverse of the null-rejecting analysis in
1158-
/// `collect_null_rejecting_columns`: there, a surviving `IS NOT NULL` conjunct
1159-
/// *derives* `null_count = Exact(0)` for the output; here, an input that
1160-
/// already proves `Exact(0)` nulls makes the conjunct vacuously true, so
1161-
/// evaluating it per batch is pure overhead (measured: 100% selectivity
1162-
/// join-key filters over NOT NULL data still pay full evaluation + batch
1163-
/// copy per scan).
1164-
fn simplify_not_null_conjuncts(
1165-
predicate: Arc<dyn PhysicalExpr>,
1166-
input: &Arc<dyn ExecutionPlan>,
1167-
) -> Arc<dyn PhysicalExpr> {
1168-
// Only worth consulting statistics when the predicate has a bare
1169-
// `Column IS NOT NULL` conjunct to drop.
1170-
let conjuncts = split_conjunction(&predicate);
1171-
let has_bare_not_null = conjuncts.iter().any(|e| {
1172-
e.downcast_ref::<IsNotNullExpr>()
1173-
.and_then(|n| n.arg().downcast_ref::<Column>())
1174-
.is_some()
1175-
});
1176-
if !has_bare_not_null {
1177-
return predicate;
1178-
}
1179-
1180-
// Global (all-partitions) statistics; per-partition refinement is not
1181-
// needed for a proof that holds across every partition.
1182-
let Ok(stats) =
1183-
StatisticsContext::new().compute(input.as_ref(), &StatisticsArgs::new())
1184-
else {
1185-
return predicate;
1186-
};
1187-
// Use the column's schema index directly: `Column::name()` is for display
1188-
// only and is ambiguous when the input has duplicate field names (e.g.
1189-
// after a join); the predicate's `Column::index()` is what physical
1190-
// evaluation uses and what `column_statistics` is keyed by.
1191-
let provably_non_null = |col: &Column| {
1192-
stats
1193-
.column_statistics
1194-
.get(col.index())
1195-
.is_some_and(|cs| matches!(cs.null_count, Precision::Exact(0)))
1196-
};
1197-
1198-
let mut kept: Vec<Arc<dyn PhysicalExpr>> = Vec::with_capacity(conjuncts.len());
1199-
for expr in conjuncts {
1200-
let drop = expr
1201-
.downcast_ref::<IsNotNullExpr>()
1202-
.and_then(|n| n.arg().downcast_ref::<Column>())
1203-
.is_some_and(provably_non_null);
1204-
if !drop {
1205-
kept.push(Arc::clone(expr));
1206-
}
1207-
}
1208-
match kept.len() {
1209-
0 => Arc::new(Literal::new(ScalarValue::Boolean(Some(true)))),
1210-
// Single conjunct: no need to re-conjoin
1211-
1 => kept.pop().expect("len checked"),
1212-
_ => conjunction(kept),
1213-
}
1140+
/// Kept deliberately narrow: only a whole-predicate match. Dropping individual
1141+
/// conjuncts of a larger predicate here would duplicate what the logical
1142+
/// `SimplifyExpressions` rule already does with schema nullability.
1143+
fn as_bare_is_not_null(predicate: &Arc<dyn PhysicalExpr>) -> Option<&Column> {
1144+
predicate
1145+
.downcast_ref::<IsNotNullExpr>()
1146+
.and_then(|n| n.arg().downcast_ref::<Column>())
12141147
}
12151148

12161149
/// Collects columns that cannot be NULL in any surviving row.
@@ -1499,6 +1432,24 @@ impl Stream for FilterExecStream {
14991432
}
15001433
Some(Ok(batch)) => {
15011434
let timer = elapsed_compute.timer();
1435+
// Fast path for `col IS NOT NULL` predicates over a batch
1436+
// where the column holds no NULLs (`null_count()` is an
1437+
// O(1) cached value): the mask would be all-true, so skip
1438+
// predicate evaluation and `filter_record_batch`'s row
1439+
// selection entirely and feed the batch to the coalescer
1440+
// as-is. This is the common case for join-key filters
1441+
// injected by `filter_null_join_keys` over NOT NULL keys.
1442+
if self.projection.is_none() {
1443+
if let Some(col) = as_bare_is_not_null(&self.predicate) {
1444+
if col.index() < batch.num_columns()
1445+
&& batch.column(col.index()).null_count() == 0
1446+
{
1447+
drop(timer);
1448+
let state = self.batch_coalescer.push_batch(batch)?;
1449+
continue;
1450+
}
1451+
}
1452+
}
15021453
let status = self.predicate.as_ref()
15031454
.evaluate(&batch)
15041455
.and_then(|v| v.into_array(batch.num_rows()))
@@ -1626,149 +1577,62 @@ mod tests {
16261577
use crate::test::exec::StatisticsExec;
16271578
use arrow::datatypes::{Field, Schema, UnionFields, UnionMode};
16281579

1629-
fn stats_exec_with_null_count(
1630-
schema: &Schema,
1631-
null_counts: Vec<usize>,
1632-
) -> Arc<dyn ExecutionPlan> {
1633-
let stats = Statistics {
1634-
column_statistics: null_counts
1635-
.into_iter()
1636-
.map(|n| ColumnStatistics {
1637-
null_count: Precision::Exact(n),
1638-
..Default::default()
1639-
})
1640-
.collect(),
1641-
..Statistics::new_unknown(schema)
1642-
};
1643-
Arc::new(StatisticsExec::new(stats, schema.clone()))
1644-
}
1645-
1646-
#[test]
1647-
fn not_null_conjunct_dropped_when_null_count_exact_zero() -> Result<()> {
1648-
// a IS NOT NULL AND a > 5, with input proving a has zero NULLs:
1649-
// the IS NOT NULL conjunct is vacuously true and must be dropped.
1650-
let schema = Schema::new(vec![Field::new("a", DataType::Int64, true)]);
1651-
let input = stats_exec_with_null_count(&schema, vec![0]);
1652-
let predicate: Arc<dyn PhysicalExpr> = Arc::new(BinaryExpr::new(
1653-
Arc::new(IsNotNullExpr::new(col("a", &schema)?)),
1654-
Operator::And,
1655-
binary(col("a", &schema)?, Operator::Gt, lit(5i64), &schema)?,
1656-
));
1657-
let simplified = simplify_not_null_conjuncts(predicate, &input);
1658-
assert_eq!(
1659-
format!("{simplified}"),
1660-
"a@0 > 5",
1661-
"IS NOT NULL conjunct should be dropped, keeping the range predicate"
1662-
);
1663-
Ok(())
1664-
}
1580+
#[tokio::test]
1581+
async fn is_not_null_fast_path_null_free_batch() -> Result<()> {
1582+
// A bare predicate over a batch whose column holds
1583+
// no NULLs takes the per-batch fast path in FilterExecStream: rows
1584+
// pass through unfiltered (identical to evaluating an all-true mask).
1585+
use crate::test::exec::MockExec;
1586+
use arrow::array::{ArrayRef, Int64Array};
1587+
use futures::TryStreamExt;
16651588

1666-
#[test]
1667-
fn not_null_whole_predicate_becomes_true_when_all_dropped() -> Result<()> {
1668-
// a IS NOT NULL with input proving zero NULLs: nothing left to check.
1669-
let schema = Schema::new(vec![Field::new("a", DataType::Int64, true)]);
1670-
let input = stats_exec_with_null_count(&schema, vec![0]);
1671-
let predicate: Arc<dyn PhysicalExpr> =
1672-
Arc::new(IsNotNullExpr::new(col("a", &schema)?));
1673-
let simplified = simplify_not_null_conjuncts(predicate, &input);
1674-
// PhysicalExpr: Any(经裸 trait 对象直接 cast)
1675-
let any_ref = simplified.as_ref() as &dyn std::any::Any;
1676-
assert!(
1677-
any_ref.downcast_ref::<Literal>().is_some(),
1678-
"whole predicate should simplify to a literal (true), got {simplified}"
1589+
let batch = RecordBatch::try_from_iter(vec![(
1590+
"a",
1591+
Arc::new(Int64Array::from(vec![Some(1i64), Some(2), Some(3)])) as ArrayRef,
1592+
)])?;
1593+
let schema = batch.schema();
1594+
let input = Arc::new(
1595+
MockExec::new(vec![Ok(batch.clone())], Arc::clone(&schema))
1596+
.with_use_task(false),
16791597
);
1680-
Ok(())
1681-
}
1682-
1683-
#[test]
1684-
fn not_null_conjunct_kept_when_null_count_not_exact() -> Result<()> {
1685-
// null_count unknown/inexact: no proof, predicate must pass through.
1686-
let schema = Schema::new(vec![Field::new("a", DataType::Int64, true)]);
1687-
let stats = Statistics {
1688-
column_statistics: vec![ColumnStatistics {
1689-
null_count: Precision::Absent,
1690-
..Default::default()
1691-
}],
1692-
..Statistics::new_unknown(&schema)
1693-
};
1694-
let input = Arc::new(StatisticsExec::new(stats, schema.clone()))
1695-
as Arc<dyn ExecutionPlan>;
16961598
let predicate: Arc<dyn PhysicalExpr> =
16971599
Arc::new(IsNotNullExpr::new(col("a", &schema)?));
1698-
let simplified = simplify_not_null_conjuncts(Arc::clone(&predicate), &input);
1699-
assert!(simplified.eq(&predicate), "must keep predicate unchanged");
1700-
Ok(())
1701-
}
1702-
1703-
#[test]
1704-
fn not_null_conjunct_uses_column_index_with_duplicate_names() -> Result<()> {
1705-
// Regression for review feedback: after a join the input schema can
1706-
// contain duplicate field names. Statistics must be looked up by the
1707-
// column's schema index, not by name: here field 0 ("a") is provably
1708-
// non-null while the same-named field 1 ("a") contains NULLs. A
1709-
// conjunct on field 0 must be dropped and one on field 1 kept.
1710-
let schema = Schema::new(vec![
1711-
Field::new("a", DataType::Int64, true),
1712-
Field::new("a", DataType::Int64, true),
1713-
]);
1714-
// null_count: field 0 = 0 (proof), field 1 = 5 (NULLs present)
1715-
let input = stats_exec_with_null_count(&schema, vec![0, 5]);
1716-
1717-
let col0 = Column::new("a", 0);
1718-
let col1 = Column::new("a", 1);
1719-
assert_eq!(col0.name(), col1.name(), "same name, different index");
1720-
1721-
// IS NOT NULL on the provably non-null field 0: dropped.
1722-
let p0: Arc<dyn PhysicalExpr> = Arc::new(IsNotNullExpr::new(Arc::new(col0)));
1723-
let simplified = simplify_not_null_conjuncts(Arc::clone(&p0), &input);
1724-
assert!(
1725-
simplified.downcast_ref::<Literal>().is_some(),
1726-
"conjunct on provably non-null field 0 should drop to a literal, got {simplified}"
1727-
);
1600+
let filter = FilterExecBuilder::new(predicate, input).build()?;
17281601

1729-
// IS NOT NULL on the same-named field 1 which holds NULLs: kept.
1730-
let p1: Arc<dyn PhysicalExpr> = Arc::new(IsNotNullExpr::new(Arc::new(col1)));
1731-
let simplified = simplify_not_null_conjuncts(Arc::clone(&p1), &input);
1732-
assert!(
1733-
simplified.eq(&p1),
1734-
"conjunct on same-named field 1 with NULLs must be kept, got {simplified}"
1602+
let ctx = Arc::new(TaskContext::default());
1603+
let mut stream = filter.execute(0, ctx)?;
1604+
let mut collected = Vec::new();
1605+
while let Some(b) = stream.try_next().await? {
1606+
collected.push(b);
1607+
}
1608+
assert_eq!(collected.len(), 1, "should return single batch");
1609+
assert_eq!(
1610+
collected[0], batch,
1611+
"null-free batch must pass through unchanged"
17351612
);
17361613
Ok(())
17371614
}
17381615

17391616
#[tokio::test]
1740-
async fn lit_true_predicate_bypasses_filter_stream() -> Result<()> {
1741-
// Regression for review feedback: a predicate that simplified to
1742-
// `lit(true)` (all conjuncts dropped) makes FilterExec a
1743-
// pass-through — execute() must return the input stream without
1744-
// building a FilterExecStream (no mask evaluation / coalescing).
1617+
async fn is_not_null_slow_path_batch_with_nulls() -> Result<()> {
1618+
// The same predicate over a batch that actually contains NULLs must
1619+
// take the normal evaluation path and filter them out.
17451620
use crate::test::exec::MockExec;
1746-
use arrow::array::ArrayRef;
1621+
use arrow::array::{ArrayRef, Int64Array};
17471622
use futures::TryStreamExt;
17481623

17491624
let batch = RecordBatch::try_from_iter(vec![(
17501625
"a",
1751-
Arc::new(arrow::array::Int64Array::from(vec![1, 2, 3])) as ArrayRef,
1626+
Arc::new(Int64Array::from(vec![Some(1i64), None, Some(3)])) as ArrayRef,
17521627
)])?;
17531628
let schema = batch.schema();
1754-
// Build input that reports zero nulls so IS NOT NULL simplifies to lit(true)
1755-
let input = stats_exec_with_null_count(&schema, vec![0]);
1756-
1629+
let input = Arc::new(
1630+
MockExec::new(vec![Ok(batch)], Arc::clone(&schema))
1631+
.with_use_task(false),
1632+
);
17571633
let predicate: Arc<dyn PhysicalExpr> =
17581634
Arc::new(IsNotNullExpr::new(col("a", &schema)?));
17591635
let filter = FilterExecBuilder::new(predicate, input).build()?;
1760-
assert!(
1761-
filter.predicate().eq(&lit(true)),
1762-
"predicate should have simplified to lit(true)"
1763-
);
1764-
1765-
// execute() must bypass: create a MockExec that produces one batch,
1766-
// then verify the filter returns the *same* batch (unfiltered).
1767-
let mock_input = Arc::new(
1768-
MockExec::new(vec![Ok(batch.clone())], Arc::clone(&schema))
1769-
.with_use_task(false),
1770-
);
1771-
let filter = FilterExecBuilder::new(lit(true), mock_input).build()?;
17721636

17731637
let ctx = Arc::new(TaskContext::default());
17741638
let mut stream = filter.execute(0, ctx)?;
@@ -1778,8 +1642,9 @@ mod tests {
17781642
}
17791643
assert_eq!(collected.len(), 1, "should return single batch");
17801644
assert_eq!(
1781-
collected[0], batch,
1782-
"batch must pass through unchanged (no mask applied)"
1645+
collected[0].num_rows(),
1646+
2,
1647+
"row with NULL must be filtered out"
17831648
);
17841649
Ok(())
17851650
}

‎datafusion/sqllogictest/test_files/predicates.slt‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -989,7 +989,8 @@ logical_plan
989989
01)Filter: t.x IS NOT NULL
990990
02)--TableScan: t projection=[x]
991991
physical_plan
992-
01)DataSourceExec: partitions=1, partition_sizes=[1]
992+
01)FilterExec: x@0 IS NOT NULL
993+
02)--DataSourceExec: partitions=1, partition_sizes=[1]
993994

994995
query TT
995996
explain select x from t where x IN (1,2,3,4,5) AND x NOT IN (1,2,3,4);

0 commit comments

Comments
 (0)