Skip to content

Commit f92731c

Browse files
hassaanch23Omega359
authored andcommitted
fix: account for every partition in local TopK and limit statistics (apache#25654)
## Which issue does this PR close? - Closes apache#25619. Part of apache#25610. ## Rationale for this change A TopK that preserves partitioning keeps up to `fetch` rows from **each** partition, but its overall row estimate is capped at one partition's `fetch`. In the issue's reproducer it is estimated at 10 rows and emits 40. The cause is shared by every operator that applies its fetch per partition. Each computes overall statistics as `with_fetch(self.fetch, 0, 1)` on the child's *overall* statistics: | Operator | Fetch applies to | Overall estimate on `main` | | --- | --- | --- | | `SortExec` TopK, `preserve_partitioning=[true]` | each partition | 1 × fetch | | `LocalLimitExec` | each partition | 1 × fetch, reported as **`Exact`** | | `HashJoinExec` with a fetch | each output partition | 1 × fetch | | `CoalesceBatchesExec` (deprecated) with a fetch | each partition | 1 × fetch | This predates the current statistics API. Before apache#11875, `LocalLimitExec` already reported `fetch` as exact (with a comment saying it *"is not actually exact, but will be when GlobalLimit is applied"*), and multiplied by the partition count only when the input had no row estimate. ## What changes are included in this PR? A crate-private helper, `with_per_partition_fetch` in `physical-plan/src/statistics.rs`, used by the four operators: - **One partition, or one output partition:** unchanged, it is `with_fetch(fetch, 0, 1)`. - **Overall, across `n` partitions:** estimates `min(input rows, fetch × n)`. - That count is **inexact** unless the fetch cannot drop any row (input ≤ fetch). How the input is spread over the partitions is unknown: 400 rows over 4 partitions under a limit of 10 gives 40 when spread evenly, and 10 when they all sit in one partition. I didn't reuse `with_fetch`'s `n_partitions` parameter. It treats `self` as *one partition's* statistics and multiplies them; given overall statistics it would report `Exact(40)` for a skewed split, and 40 rows out of a 25-row input. The merge above a per-partition TopK still caps the estimate at the global limit: `SortPreservingMergeExec` stays at 10 (see the `explain.slt` case). ### One trade-off to call out On `main`, `SELECT * FROM t LIMIT 5` over a two-partition table with exact statistics reports `Exact(5)` at the top. That exactness only came from `LocalLimitExec` claiming `Exact(5)` for output that is really 5–10 rows. With honest local estimates, the global limit reports **`Inexact(5)`**: the count is still right, but statistics can't express the lower bound needed to prove it exact. `custom_sources_cases::statistics::sql_limit` pinned the old value; I updated it with a comment. My reasoning is that an exact count should only be claimed when it's provable, since rules such as the `COUNT(*)`-from-statistics shortcut rely on it. If you'd rather keep `LocalLimitExec` as it is for now and scope this PR to TopK and joins, that's a one-line revert and I'm happy to make it. ## What is the testing strategy for this PR? - `statistics::tests::per_partition_fetch_counts_every_partition`: every branch of the helper. - `sorts::sort::tests::test_partitioned_topk_statistics_count_every_partition`: runs a per-partition TopK over 4 × 100 rows and checks the estimate against what it emits. - `joins::hash_join::exec::tests::join_fetch_statistics_count_every_output_partition`: a `CollectLeft` join with 4 output partitions and `fetch=10` emits 40 rows, and is now estimated at `Inexact(40)`. - `coalesce_batches::tests::fetch_statistics_count_every_partition`: the deprecated operator over 4 partitions with `fetch=10` emits 40 rows, and is now estimated at `Inexact(40)`. - `limit::tests::test_row_number_statistics_for_local_limit`: asserted `Exact(10)` for 4 partitions × 100 rows under a limit of 10; now `Inexact(40)`, plus the no-drop and single-partition cases. - `explain.slt`: the issue's plan shape (grouped aggregate → per-partition TopK → merge) with `show_statistics`. TopK is `Inexact(40)`, the merge is `Inexact(10)`. All of these fail on `main`: I checked by reverting only the helper's logic and keeping the tests. A note on the TopK test: `SortExec` with a fetch builds a dynamic filter that its partitions share, so a partition can stop short of `fetch` once another partition's heap is full. The test emits 37–40 rows depending on scheduling, so it checks that range rather than exactly 40. The estimate is an upper bound on it, and the issue's reproducer disables dynamic filtering for the same reason. Full runs pass: `datafusion-physical-plan` (with `test_utils`), `datafusion-physical-optimizer`, `datafusion`'s `core_integration` and `tpcds_planning`, and all 521 sqllogictest files. ## Are there any user-facing changes? Only statistics estimates: larger row estimates for per-partition TopK, local limits, and hash joins with a fetch, plus the `Exact` → `Inexact` change described above. No public API changes; the helper is `pub(crate)`.
1 parent c18a192 commit f92731c

7 files changed

Lines changed: 321 additions & 14 deletions

File tree

‎datafusion/core/tests/custom_sources_cases/statistics.rs‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -296,7 +296,10 @@ async fn sql_limit() -> Result<()> {
296296
// and cap NDV at the new row count
297297
let limit_stats = StatisticsContext::new()
298298
.compute(physical_plan.as_ref(), &StatisticsArgs::new())?;
299-
assert_eq!(limit_stats.num_rows, Precision::Exact(5));
299+
// Each of the table's two partitions is limited to 5 rows before the global
300+
// limit. How the 13 rows are split between the partitions is unknown, so the
301+
// local limits' output is only an estimate, and so is the global count.
302+
assert_eq!(limit_stats.num_rows, Precision::Inexact(5));
300303
// c1: NDV=2 stays at 2 (already below limit of 5)
301304
assert_eq!(
302305
limit_stats.column_statistics[0].distinct_count,

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

Lines changed: 50 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ use std::task::{Context, Poll};
2424
use super::metrics::{BaselineMetrics, ExecutionPlanMetricsSet, MetricsSet};
2525
use super::{DisplayAs, ExecutionPlanProperties, PlanProperties, Statistics};
2626
use crate::projection::ProjectionExec;
27-
use crate::statistics::{ChildStats, StatisticsArgs};
27+
use crate::statistics::{ChildStats, StatisticsArgs, with_per_partition_fetch};
2828
use crate::stream::EmptyRecordBatchStream;
2929
use crate::{
3030
ChildrenPropertiesMode, DisplayFormatType, ExecutionPlan, RecordBatchStream,
@@ -248,10 +248,15 @@ impl ExecutionPlan for CoalesceBatchesExec {
248248
fn statistics_from_inputs(
249249
&self,
250250
input_stats: &[Arc<Statistics>],
251-
_args: &StatisticsArgs,
251+
args: &StatisticsArgs,
252252
) -> Result<Arc<Statistics>> {
253253
let stats = input_stats[0].as_ref().clone();
254-
Ok(Arc::new(stats.with_fetch(self.fetch, 0, 1)?))
254+
Ok(Arc::new(with_per_partition_fetch(
255+
stats,
256+
self.fetch,
257+
self.properties().output_partitioning().partition_count(),
258+
args,
259+
)?))
255260
}
256261

257262
fn with_fetch(&self, limit: Option<usize>) -> Option<Arc<dyn ExecutionPlan>> {
@@ -493,3 +498,45 @@ impl RecordBatchStream for CoalesceBatchesStream {
493498
self.coalescer.schema()
494499
}
495500
}
501+
502+
#[cfg(test)]
503+
#[expect(deprecated)]
504+
mod tests {
505+
use super::*;
506+
use crate::collect;
507+
use crate::statistics::StatisticsContext;
508+
use crate::test::scan_partitioned;
509+
use datafusion_common::stats::Precision;
510+
use datafusion_execution::TaskContext;
511+
512+
/// `fetch` stops each partition separately, so the overall statistics must
513+
/// allow for the rows of every partition.
514+
#[tokio::test]
515+
async fn fetch_statistics_count_every_partition() -> Result<()> {
516+
// Four partitions of 100 rows each.
517+
let coalesce: Arc<dyn ExecutionPlan> = Arc::new(
518+
CoalesceBatchesExec::new(scan_partitioned(4), 8192).with_fetch(Some(10)),
519+
);
520+
let emitted: usize =
521+
collect(Arc::clone(&coalesce), Arc::new(TaskContext::default()))
522+
.await?
523+
.iter()
524+
.map(|batch| batch.num_rows())
525+
.sum();
526+
assert_eq!(emitted, 40);
527+
528+
let num_rows = |partition| {
529+
StatisticsContext::new()
530+
.compute(
531+
coalesce.as_ref(),
532+
&StatisticsArgs::new().with_partition(partition),
533+
)
534+
.map(|stats| stats.num_rows)
535+
};
536+
assert_eq!(num_rows(None)?, Precision::Inexact(40));
537+
// The scan has no statistics for a single partition, so there the fetch
538+
// alone bounds the estimate.
539+
assert_eq!(num_rows(Some(0))?, Precision::Inexact(10));
540+
Ok(())
541+
}
542+
}

‎datafusion/physical-plan/src/joins/hash_join/exec.rs‎

Lines changed: 55 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -51,7 +51,7 @@ use crate::projection::{
5151
try_pushdown_through_join_with_column_indices,
5252
};
5353
use crate::repartition::REPARTITION_RANDOM_STATE;
54-
use crate::statistics::{ChildStats, StatisticsArgs};
54+
use crate::statistics::{ChildStats, StatisticsArgs, with_per_partition_fetch};
5555
use crate::{
5656
ChildrenPropertiesMode, ExecutionPlanProperties, ReplaceChildrenOptions,
5757
validate_child_count,
@@ -1883,7 +1883,7 @@ impl ExecutionPlan for HashJoinExec {
18831883
fn statistics_from_inputs(
18841884
&self,
18851885
input_stats: &[Arc<Statistics>],
1886-
_args: &StatisticsArgs,
1886+
args: &StatisticsArgs,
18871887
) -> Result<Arc<Statistics>> {
18881888
let left_stats = if let Some(prepared) = &self.prepared_build {
18891889
// The declared left child supplies the schema but is never executed.
@@ -1903,8 +1903,13 @@ impl ExecutionPlan for HashJoinExec {
19031903
)?;
19041904
// Project statistics if there is a projection
19051905
let stats = stats.project(self.projection.as_ref());
1906-
// Apply fetch limit to statistics
1907-
Ok(Arc::new(stats.with_fetch(self.fetch, 0, 1)?))
1906+
// Apply the fetch, which limits each output partition separately
1907+
Ok(Arc::new(with_per_partition_fetch(
1908+
stats,
1909+
self.fetch,
1910+
self.properties().output_partitioning().partition_count(),
1911+
args,
1912+
)?))
19081913
}
19091914

19101915
/// Tries to push `projection` down through `hash_join`. If possible, performs the
@@ -3443,6 +3448,7 @@ mod tests {
34433448
use crate::execution_plan::Boundedness;
34443449
use crate::filter::FilterExecBuilder;
34453450
use crate::joins::hash_join::stream::lookup_join_hashmap;
3451+
use crate::statistics::StatisticsContext;
34463452
use crate::test::{TestMemoryExec, assert_join_metrics};
34473453
use crate::{ChildrenPropertiesMode, ReplaceChildrenOptions};
34483454
use crate::{
@@ -3458,6 +3464,7 @@ mod tests {
34583464
use arrow::buffer::NullBuffer;
34593465
use arrow::datatypes::{DataType, Field, Int32Type};
34603466
use datafusion_common::hash_utils::create_hashes;
3467+
use datafusion_common::stats::Precision;
34613468
use datafusion_common::test_util::{batches_to_sort_string, batches_to_string};
34623469
use datafusion_common::{
34633470
ScalarValue, assert_batches_eq, assert_batches_sorted_eq, assert_contains,
@@ -4854,6 +4861,50 @@ mod tests {
48544861
Ok(())
48554862
}
48564863

4864+
/// `fetch` stops each output partition separately, so the overall
4865+
/// statistics must allow for the rows of every partition.
4866+
#[tokio::test]
4867+
async fn join_fetch_statistics_count_every_output_partition() -> Result<()> {
4868+
let values: Vec<i32> = (0..100).collect();
4869+
let left = build_table(("a1", &values), ("b1", &values), ("c1", &values));
4870+
let batch = build_table_i32(("a2", &values), ("b2", &values), ("c2", &values));
4871+
let schema = batch.schema();
4872+
let right = TestMemoryExec::try_new_exec(&vec![vec![batch]; 4], schema, None)?;
4873+
let on = vec![(
4874+
Arc::new(Column::new_with_schema("b1", &left.schema())?) as _,
4875+
Arc::new(Column::new_with_schema("b2", &right.schema())?) as _,
4876+
)];
4877+
let join: Arc<dyn ExecutionPlan> = Arc::new(
4878+
HashJoinExecBuilder::new(left, right, on, JoinType::Inner)
4879+
.with_partition_mode(PartitionMode::CollectLeft)
4880+
.with_fetch(Some(10))
4881+
.build()?,
4882+
);
4883+
assert_eq!(join.properties().output_partitioning().partition_count(), 4);
4884+
4885+
// Each right row matches one left row, and each of the four output
4886+
// partitions stops after 10 rows.
4887+
let emitted: usize =
4888+
crate::collect(Arc::clone(&join), prepare_task_ctx(8192, false))
4889+
.await?
4890+
.iter()
4891+
.map(|batch| batch.num_rows())
4892+
.sum();
4893+
assert_eq!(emitted, 40);
4894+
4895+
let num_rows = |partition| {
4896+
StatisticsContext::new()
4897+
.compute(
4898+
join.as_ref(),
4899+
&StatisticsArgs::new().with_partition(partition),
4900+
)
4901+
.map(|stats| stats.num_rows)
4902+
};
4903+
assert_eq!(num_rows(None)?, Precision::Inexact(40));
4904+
assert_eq!(num_rows(Some(0))?, Precision::Inexact(10));
4905+
Ok(())
4906+
}
4907+
48574908
#[apply(hash_join_exec_configs)]
48584909
#[tokio::test]
48594910
async fn join_full_multi_batch(

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

Lines changed: 18 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,7 @@ use super::{
2727
SendableRecordBatchStream, Statistics,
2828
};
2929
use crate::execution_plan::{Boundedness, CardinalityEffect};
30-
use crate::statistics::{ChildStats, StatisticsArgs};
30+
use crate::statistics::{ChildStats, StatisticsArgs, with_per_partition_fetch};
3131
use crate::{
3232
ChildrenPropertiesMode, DisplayFormatType, Distribution, ExecutionPlan, Partitioning,
3333
ReplaceChildrenOptions, validate_child_count,
@@ -531,10 +531,15 @@ impl ExecutionPlan for LocalLimitExec {
531531
fn statistics_from_inputs(
532532
&self,
533533
input_stats: &[Arc<Statistics>],
534-
_args: &StatisticsArgs,
534+
args: &StatisticsArgs,
535535
) -> Result<Arc<Statistics>> {
536536
let stats = input_stats[0].as_ref().clone();
537-
Ok(Arc::new(stats.with_fetch(Some(self.fetch), 0, 1)?))
537+
Ok(Arc::new(with_per_partition_fetch(
538+
stats,
539+
Some(self.fetch),
540+
self.properties().output_partitioning().partition_count(),
541+
args,
542+
)?))
538543
}
539544

540545
fn fetch(&self) -> Option<usize> {
@@ -1040,7 +1045,17 @@ mod tests {
10401045

10411046
#[test]
10421047
fn test_row_number_statistics_for_local_limit() -> Result<()> {
1048+
// Each of four partitions of 100 rows keeps 10 of them. How the rows
1049+
// are spread over the partitions is unknown, so the count is inexact.
10431050
let row_count = row_number_statistics_for_local_limit(4, 10)?;
1051+
assert_eq!(row_count, Precision::Inexact(40));
1052+
1053+
// A limit as large as the whole input cannot drop any row.
1054+
let row_count = row_number_statistics_for_local_limit(4, 400)?;
1055+
assert_eq!(row_count, Precision::Exact(400));
1056+
1057+
// A single partition keeps exactly `fetch` rows.
1058+
let row_count = row_number_statistics_for_local_limit(1, 10)?;
10441059
assert_eq!(row_count, Precision::Exact(10));
10451060

10461061
Ok(())

‎datafusion/physical-plan/src/sorts/sort.rs‎

Lines changed: 58 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,7 @@ use crate::sorts::streaming_merge::{SortedSpillFile, StreamingMergeBuilder};
4646
use crate::spill::get_record_batch_memory_size;
4747
use crate::spill::in_progress_spill_file::InProgressSpillFile;
4848
use crate::spill::spill_manager::{GetSlicedSize, SpillManager};
49-
use crate::statistics::{ChildStats, StatisticsArgs};
49+
use crate::statistics::{ChildStats, StatisticsArgs, with_per_partition_fetch};
5050
use crate::stream::ReservationStream;
5151
use crate::stream::{ObservedStream, RecordBatchStreamAdapter};
5252
use crate::topk::TopK;
@@ -1559,10 +1559,16 @@ impl ExecutionPlan for SortExec {
15591559
fn statistics_from_inputs(
15601560
&self,
15611561
input_stats: &[Arc<Statistics>],
1562-
_args: &StatisticsArgs,
1562+
args: &StatisticsArgs,
15631563
) -> Result<Arc<Statistics>> {
15641564
let stats = input_stats[0].as_ref().clone();
1565-
Ok(Arc::new(stats.with_fetch(self.fetch, 0, 1)?))
1565+
// With `preserve_partitioning`, the fetch applies to each partition.
1566+
Ok(Arc::new(with_per_partition_fetch(
1567+
stats,
1568+
self.fetch,
1569+
self.properties().output_partitioning().partition_count(),
1570+
args,
1571+
)?))
15661572
}
15671573

15681574
fn with_fetch(&self, limit: Option<usize>) -> Option<Arc<dyn ExecutionPlan>> {
@@ -2168,6 +2174,7 @@ mod tests {
21682174
use crate::execution_plan::Boundedness;
21692175
use crate::expressions::col;
21702176
use crate::filter_pushdown::{FilterPushdownPhase, PushedDown};
2177+
use crate::statistics::StatisticsContext;
21712178
use crate::test;
21722179
use crate::test::TestMemoryExec;
21732180
use crate::test::exec::{BlockingExec, assert_strong_count_converges_to_zero};
@@ -2181,6 +2188,7 @@ mod tests {
21812188
use datafusion_common::ScalarValue;
21822189
use datafusion_common::cast::as_primitive_array;
21832190
use datafusion_common::config::ConfigOptions;
2191+
use datafusion_common::stats::Precision;
21842192
use datafusion_common::test_util::batches_to_string;
21852193
use datafusion_execution::RecordBatchStream;
21862194
use datafusion_execution::config::SessionConfig;
@@ -4233,4 +4241,51 @@ mod tests {
42334241
assert_eq!(desc.self_filters()[0].len(), 1);
42344242
Ok(())
42354243
}
4244+
4245+
/// A TopK that preserves partitioning keeps `fetch` rows from every
4246+
/// partition, so its overall statistics must count all of them.
4247+
#[tokio::test]
4248+
async fn test_partitioned_topk_statistics_count_every_partition() -> Result<()> {
4249+
// Four partitions of 100 rows each.
4250+
let input = test::scan_partitioned(4);
4251+
let ordering = LexOrdering::new(vec![PhysicalSortExpr {
4252+
expr: col("i", &input.schema())?,
4253+
options: SortOptions::default(),
4254+
}])
4255+
.unwrap();
4256+
let topk = |preserve_partitioning| -> Arc<dyn ExecutionPlan> {
4257+
Arc::new(
4258+
SortExec::new(ordering.clone(), Arc::clone(&input))
4259+
.with_fetch(Some(10))
4260+
.with_preserve_partitioning(preserve_partitioning),
4261+
)
4262+
};
4263+
let num_rows = |plan: &Arc<dyn ExecutionPlan>, partition| {
4264+
StatisticsContext::new()
4265+
.compute(
4266+
plan.as_ref(),
4267+
&StatisticsArgs::new().with_partition(partition),
4268+
)
4269+
.map(|stats| stats.num_rows)
4270+
};
4271+
4272+
let per_partition = topk(true);
4273+
let emitted: usize =
4274+
collect(Arc::clone(&per_partition), Arc::new(TaskContext::default()))
4275+
.await?
4276+
.iter()
4277+
.map(|batch| batch.num_rows())
4278+
.sum();
4279+
// The partitions share the TopK's dynamic filter, which can prune a few
4280+
// rows, but together they emit far more than one partition's 10.
4281+
assert!((11..=40).contains(&emitted), "emitted {emitted} rows");
4282+
assert_eq!(num_rows(&per_partition, None)?, Precision::Inexact(40));
4283+
// The scan has no statistics for a single partition, so there the fetch
4284+
// alone bounds the estimate.
4285+
assert_eq!(num_rows(&per_partition, Some(0))?, Precision::Inexact(10));
4286+
4287+
// Sorting the whole input keeps 10 rows in total.
4288+
assert_eq!(num_rows(&topk(false), None)?, Precision::Exact(10));
4289+
Ok(())
4290+
}
42364291
}

0 commit comments

Comments
 (0)