Skip to content

Commit 4048898

Browse files
authored
fix: preserve fetch across distribution reoptimization (#24809)
## Which issue does this PR close? - Closes #24807. ## Rationale for this change Reoptimizing an already optimized physical plan could silently remove a pushed-down `LIMIT` stored on `SortPreservingMergeExec` or `CoalescePartitionsExec`. This could make a query return more rows than requested. ## What changes are included in this PR? - Consume a removed `fetch` when a replacement merge operator is inserted. - Remember the outermost removed fetch-capable distribution operator and rebuild it around the optimized child when no replacement consumes its limit. - Preserve the minimum effective fetch across nested distribution operators. - Carry a fetched ordered merge's limit to a replacement sort when order-preserving variants are removed. ## What is the testing strategy for this PR? Added targeted physical optimizer regression tests covering: - reoptimizing a fetched `SortPreservingMergeExec`; - reoptimizing a fetched `CoalescePartitionsExec`; - moving a fetched ordered merge's limit to a replacement sort; - updating an existing fetched single-partition merge snapshot that previously encoded the incorrect removal of its limit. Validated with: ```text # Fails on e4cf35c (current main before this patch): both regression tests fail cargo test -p datafusion --test core_integration physical_optimizer::enforce_distribution::preserve_fetch_when_reoptimizing # Passes with this patch cargo test -p datafusion --test core_integration physical_optimizer::enforce_distribution::preserve_fetch_when_reoptimizing cargo test -p datafusion --test core_integration physical_optimizer::enforce_distribution::move_fetch_to_replacement_sort cargo test -p datafusion --test core_integration physical_optimizer::enforce_distribution::test_replace_order_preserving_variants_with_fetch cargo fmt --all -- --check cargo clippy --all-targets --all-features -- -D warnings RUST_BACKTRACE=1 cargo test --profile ci --exclude datafusion-examples --exclude datafusion-benchmarks --exclude datafusion-cli --workspace --lib --tests --bins --features avro,json,backtrace,extended_tests,recursive_protection,parquet_encryption ``` ## Are there any user-facing changes? Queries preserve their requested global limit when physical distribution requirements are optimized more than once. There are no changes to SQL behavior other than fixing the incorrect result, and no changes to documented public APIs.
1 parent f8a4ac8 commit 4048898

6 files changed

Lines changed: 404 additions & 138 deletions

File tree

‎datafusion/core/tests/physical_optimizer/enforce_distribution.rs‎

Lines changed: 320 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,7 @@ use crate::physical_optimizer::test_utils::{
2626
sort_merge_join_exec, sort_preserving_merge_exec, union_exec,
2727
};
2828

29-
use arrow::array::{RecordBatch, UInt8Array, UInt64Array};
29+
use arrow::array::{Int64Array, RecordBatch, UInt8Array, UInt64Array};
3030
use arrow::compute::SortOptions;
3131
use arrow_schema::{DataType, Field, Schema, SchemaRef};
3232
use datafusion::config::ConfigOptions;
@@ -47,6 +47,7 @@ use datafusion_common::tree_node::{
4747
};
4848
use datafusion_datasource::file_groups::FileGroup;
4949
use datafusion_datasource::file_scan_config::FileScanConfigBuilder;
50+
use datafusion_datasource::memory::MemorySourceConfig;
5051
use datafusion_expr::{JoinType, Operator};
5152
use datafusion_functions_aggregate::count::count_udaf;
5253
use datafusion_physical_expr::aggregate::AggregateExprBuilder;
@@ -76,11 +77,12 @@ use datafusion_physical_plan::joins::utils::JoinOn;
7677
use datafusion_physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
7778
use datafusion_physical_plan::projection::{ProjectionExec, ProjectionExpr};
7879
use datafusion_physical_plan::repartition::RepartitionExec;
80+
use datafusion_physical_plan::sorts::sort::SortExec;
7981
use datafusion_physical_plan::sorts::sort_preserving_merge::SortPreservingMergeExec;
8082
use datafusion_physical_plan::union::{InterleaveExec, UnionExec};
8183
use datafusion_physical_plan::{
8284
ChildrenPropertiesMode, DisplayAs, DisplayFormatType, ExecutionPlanProperties,
83-
PlanProperties, ReplaceChildrenOptions, displayable,
85+
PlanProperties, ReplaceChildrenOptions, collect, displayable,
8486
};
8587
use insta::Settings;
8688

@@ -4844,11 +4846,12 @@ fn test_replace_order_preserving_variants_with_fetch() -> Result<()> {
48444846
// Apply the function
48454847
let result = replace_order_preserving_variants(dist_context)?;
48464848

4847-
// Verify the plan was transformed to CoalescePartitionsExec
4849+
// A fetched ordered merge must still select the TopK rows.
4850+
let result = check_integrity(result)?;
48484851
result
48494852
.plan
4850-
.downcast_ref::<CoalescePartitionsExec>()
4851-
.expect("Expected CoalescePartitionsExec");
4853+
.downcast_ref::<SortExec>()
4854+
.expect("Expected a TopK SortExec");
48524855

48534856
// Verify fetch was preserved
48544857
assert_eq!(
@@ -4860,6 +4863,318 @@ fn test_replace_order_preserving_variants_with_fetch() -> Result<()> {
48604863
Ok(())
48614864
}
48624865

4866+
#[test]
4867+
fn preserve_fetch_when_reoptimizing_ordered_merge() -> Result<()> {
4868+
let schema = schema();
4869+
let sort_key: LexOrdering =
4870+
[PhysicalSortExpr::new_default(col("c", &schema)?)].into();
4871+
let input = parquet_exec_multiple_sorted(vec![sort_key.clone()]);
4872+
let plan: Arc<dyn ExecutionPlan> =
4873+
Arc::new(SortPreservingMergeExec::new(sort_key, input).with_fetch(Some(5)));
4874+
4875+
let optimized =
4876+
EnsureRequirements::new().optimize(plan, &test_suite_default_config_options())?;
4877+
let plan = displayable(optimized.as_ref()).indent(true).to_string();
4878+
4879+
assert!(
4880+
plan.contains("SortPreservingMergeExec: [c@2 ASC], fetch=5"),
4881+
"expected the optimizer to preserve fetch:\n{plan}"
4882+
);
4883+
4884+
Ok(())
4885+
}
4886+
4887+
#[test]
4888+
fn preserve_fetch_when_reoptimizing_coalesce_partitions() -> Result<()> {
4889+
let input = parquet_exec_multiple();
4890+
let plan: Arc<dyn ExecutionPlan> =
4891+
Arc::new(CoalescePartitionsExec::new(input).with_fetch(Some(5)));
4892+
4893+
let optimized =
4894+
EnsureRequirements::new().optimize(plan, &test_suite_default_config_options())?;
4895+
4896+
assert_eq!(optimized.fetch(), Some(5));
4897+
optimized
4898+
.downcast_ref::<CoalescePartitionsExec>()
4899+
.expect("expected CoalescePartitionsExec");
4900+
4901+
Ok(())
4902+
}
4903+
4904+
#[tokio::test]
4905+
async fn move_fetch_to_replacement_sort() -> Result<()> {
4906+
for (options, partitions, expected) in [
4907+
(
4908+
SortOptions::default(),
4909+
[
4910+
vec![None, Some(1), Some(1), Some(6)],
4911+
vec![None, Some(1), Some(2), Some(7)],
4912+
],
4913+
vec![None, None, Some(1), Some(1), Some(1)],
4914+
),
4915+
(
4916+
SortOptions {
4917+
descending: true,
4918+
nulls_first: false,
4919+
},
4920+
[vec![Some(7), Some(1), None], vec![Some(6), Some(1), None]],
4921+
vec![Some(7), Some(6), Some(1), Some(1), None],
4922+
),
4923+
] {
4924+
let (input, sort_key) = sorted_memory_input(partitions, options)?;
4925+
let merge: Arc<dyn ExecutionPlan> = Arc::new(
4926+
SortPreservingMergeExec::new(sort_key.clone(), input).with_fetch(Some(5)),
4927+
);
4928+
assert_eq!(fetch_test_values(Arc::clone(&merge)).await?, expected);
4929+
let plan = sort_required_exec_with_req(merge, sort_key);
4930+
let optimized = ensure_distribution_helper(plan, 10, false)?;
4931+
let replacement = Arc::clone(optimized.children()[0]);
4932+
let sort = replacement
4933+
.downcast_ref::<SortExec>()
4934+
.expect("expected a replacement sort");
4935+
assert_eq!(sort.fetch(), Some(5));
4936+
assert_eq!(fetch_test_values(replacement).await?, expected);
4937+
}
4938+
Ok(())
4939+
}
4940+
4941+
#[tokio::test]
4942+
async fn preserve_fetch_in_nested_distribution_operators() -> Result<()> {
4943+
for outer_fetch in [0, 3, 10] {
4944+
let (input, sort_key) = sorted_memory_input(
4945+
[0, 1].map(|start| (start..10).step_by(2).map(Some).collect()),
4946+
SortOptions::default(),
4947+
)?;
4948+
let merge: Arc<dyn ExecutionPlan> =
4949+
Arc::new(SortPreservingMergeExec::new(sort_key, input).with_fetch(Some(5)));
4950+
let plan: Arc<dyn ExecutionPlan> =
4951+
Arc::new(CoalescePartitionsExec::new(merge).with_fetch(Some(outer_fetch)));
4952+
let expected = (0..outer_fetch.min(5))
4953+
.map(|value| Some(value as i64))
4954+
.collect::<Vec<_>>();
4955+
assert_reoptimized_fetch_values(plan, &expected).await?;
4956+
}
4957+
Ok(())
4958+
}
4959+
4960+
#[tokio::test]
4961+
async fn preserve_topk_when_parent_changes_ordering() -> Result<()> {
4962+
let (input, sort_key) = sorted_memory_input(
4963+
[0, 1].map(|start| (start..10).step_by(2).map(Some).collect()),
4964+
SortOptions::default(),
4965+
)?;
4966+
let descending = [PhysicalSortExpr::new(
4967+
col("c", &input.schema())?,
4968+
SortOptions {
4969+
descending: true,
4970+
nulls_first: false,
4971+
},
4972+
)]
4973+
.into();
4974+
let merge: Arc<dyn ExecutionPlan> =
4975+
Arc::new(SortPreservingMergeExec::new(sort_key, input).with_fetch(Some(5)));
4976+
let plan: Arc<dyn ExecutionPlan> = Arc::new(SortExec::new(descending, merge));
4977+
assert_reoptimized_fetch_values(plan, &[Some(4), Some(3), Some(2), Some(1), Some(0)])
4978+
.await
4979+
}
4980+
4981+
#[tokio::test]
4982+
async fn preserve_fetch_when_parallelizing_sort_above_filter() -> Result<()> {
4983+
let (input, sort_key) = sorted_memory_input(
4984+
[
4985+
vec![Some(-4), Some(-2), Some(2), Some(4), Some(6)],
4986+
vec![Some(-3), Some(-1), Some(3), Some(5), Some(7)],
4987+
],
4988+
SortOptions::default(),
4989+
)?;
4990+
let predicate = Arc::new(BinaryExpr::new(
4991+
col("c", &input.schema())?,
4992+
Operator::Gt,
4993+
lit(0_i64),
4994+
));
4995+
let coalesce: Arc<dyn ExecutionPlan> =
4996+
Arc::new(CoalescePartitionsExec::new(input).with_fetch(Some(5)));
4997+
let filter: Arc<dyn ExecutionPlan> =
4998+
Arc::new(FilterExec::try_new(predicate, coalesce)?);
4999+
let mut plan: Arc<dyn ExecutionPlan> = Arc::new(SortExec::new(sort_key, filter));
5000+
let mut config = test_suite_default_config_options();
5001+
config.optimizer.enable_round_robin_repartition = false;
5002+
config.optimizer.repartition_sorts = true;
5003+
for iteration in 0..3 {
5004+
if iteration > 0 {
5005+
plan = EnsureRequirements::new().optimize(plan, &config)?;
5006+
}
5007+
// Either input batch can arrive first. Both contain three positive
5008+
// rows, so keeping the limit below the filter always returns three.
5009+
assert_eq!(
5010+
fetch_test_values(Arc::clone(&plan)).await?.len(),
5011+
3,
5012+
"iteration {iteration}:\n{}",
5013+
displayable(plan.as_ref()).indent(true)
5014+
);
5015+
}
5016+
Ok(())
5017+
}
5018+
5019+
fn sorted_memory_input(
5020+
partitions: [Vec<Option<i64>>; 2],
5021+
options: SortOptions,
5022+
) -> Result<(Arc<dyn ExecutionPlan>, LexOrdering)> {
5023+
let schema = Arc::new(Schema::new(vec![Field::new("c", DataType::Int64, true)]));
5024+
let order: LexOrdering = [PhysicalSortExpr::new(col("c", &schema)?, options)].into();
5025+
let partitions = partitions
5026+
.into_iter()
5027+
.map(|values| {
5028+
RecordBatch::try_new(
5029+
Arc::clone(&schema),
5030+
vec![Arc::new(Int64Array::from(values))],
5031+
)
5032+
.map(|batch| vec![batch])
5033+
})
5034+
.collect::<std::result::Result<Vec<_>, _>>()?;
5035+
let source = MemorySourceConfig::try_new(&partitions, schema, None)?
5036+
.try_with_sort_information(vec![order.clone()])?;
5037+
Ok((DataSourceExec::from_data_source(source), order))
5038+
}
5039+
5040+
async fn fetch_test_values(plan: Arc<dyn ExecutionPlan>) -> Result<Vec<Option<i64>>> {
5041+
let batches = collect(plan, SessionContext::new().task_ctx()).await?;
5042+
Ok(batches
5043+
.iter()
5044+
.flat_map(|batch| {
5045+
batch
5046+
.column(0)
5047+
.as_any()
5048+
.downcast_ref::<Int64Array>()
5049+
.unwrap()
5050+
.iter()
5051+
})
5052+
.collect())
5053+
}
5054+
5055+
async fn assert_reoptimized_fetch_values(
5056+
plan: Arc<dyn ExecutionPlan>,
5057+
expected: &[Option<i64>],
5058+
) -> Result<()> {
5059+
for repartition_sorts in [false, true] {
5060+
let mut optimized = Arc::clone(&plan);
5061+
let mut config = test_suite_default_config_options();
5062+
config.optimizer.enable_round_robin_repartition = false;
5063+
config.optimizer.repartition_sorts = repartition_sorts;
5064+
for iteration in 0..3 {
5065+
if iteration > 0 {
5066+
let distribution =
5067+
DistributionContext::new_default(Arc::clone(&optimized))
5068+
.transform_up(|context| ensure_distribution(context, &config))?
5069+
.data;
5070+
check_integrity(distribution)?;
5071+
optimized = EnsureRequirements::new().optimize(optimized, &config)?;
5072+
}
5073+
assert_eq!(
5074+
fetch_test_values(Arc::clone(&optimized)).await?,
5075+
expected,
5076+
"iteration {iteration}, repartition_sorts={repartition_sorts}:\n{}",
5077+
displayable(optimized.as_ref()).indent(true)
5078+
);
5079+
}
5080+
}
5081+
Ok(())
5082+
}
5083+
5084+
#[tokio::test]
5085+
async fn preserve_fetch_below_filter_when_reoptimizing() -> Result<()> {
5086+
check_fetch_below_filter(
5087+
Operator::Gt,
5088+
[vec![-2, 0, 2, 4], vec![-1, 1, 3, 5]],
5089+
&[1, 2],
5090+
)
5091+
.await
5092+
}
5093+
5094+
#[tokio::test]
5095+
async fn preserve_fetch_below_filter_with_constant_ordering() -> Result<()> {
5096+
check_fetch_below_filter(
5097+
Operator::Eq,
5098+
[vec![-2, 0, 0, 0], vec![-1, 0, 0, 0]],
5099+
&[0, 0, 0],
5100+
)
5101+
.await
5102+
}
5103+
5104+
async fn check_fetch_below_filter(
5105+
op: Operator,
5106+
partitions: [Vec<i64>; 2],
5107+
expected: &[i64],
5108+
) -> Result<()> {
5109+
let schema = Arc::new(Schema::new(vec![Field::new("c", DataType::Int64, false)]));
5110+
let sort_key: LexOrdering =
5111+
[PhysicalSortExpr::new_default(col("c", &schema)?)].into();
5112+
let partitions = partitions
5113+
.into_iter()
5114+
.map(|values| {
5115+
RecordBatch::try_new(
5116+
Arc::clone(&schema),
5117+
vec![Arc::new(Int64Array::from(values))],
5118+
)
5119+
.map(|batch| vec![batch])
5120+
})
5121+
.collect::<std::result::Result<Vec<_>, _>>()?;
5122+
let source = MemorySourceConfig::try_new(&partitions, Arc::clone(&schema), None)?
5123+
.try_with_sort_information(vec![sort_key.clone()])?;
5124+
let merge: Arc<dyn ExecutionPlan> = Arc::new(
5125+
SortPreservingMergeExec::new(
5126+
sort_key.clone(),
5127+
DataSourceExec::from_data_source(source),
5128+
)
5129+
.with_fetch(Some(5)),
5130+
);
5131+
let predicate = Arc::new(BinaryExpr::new(col("c", &schema)?, op, lit(0_i64)));
5132+
let filter: Arc<dyn ExecutionPlan> = Arc::new(FilterExec::try_new(predicate, merge)?);
5133+
let mut plan = sort_required_exec_with_req(filter, sort_key);
5134+
let mut config = test_suite_default_config_options();
5135+
config.optimizer.enable_round_robin_repartition = false;
5136+
let task_context = SessionContext::new().task_ctx();
5137+
5138+
// The test operator only declares ordering requirements. Execute its child
5139+
// to compare query results before optimization and after repeated passes.
5140+
for iteration in 0..3 {
5141+
if iteration > 0 {
5142+
let distribution = DistributionContext::new_default(Arc::clone(&plan))
5143+
.transform_up(|context| ensure_distribution(context, &config))?
5144+
.data;
5145+
check_integrity(distribution)?;
5146+
plan = EnsureRequirements::new().optimize(plan, &config)?;
5147+
}
5148+
let input = Arc::clone(plan.children()[0]);
5149+
let batches = collect(input, Arc::clone(&task_context)).await?;
5150+
let values = batches
5151+
.iter()
5152+
.flat_map(|batch| {
5153+
batch
5154+
.column(0)
5155+
.as_any()
5156+
.downcast_ref::<Int64Array>()
5157+
.unwrap()
5158+
.values()
5159+
.iter()
5160+
.copied()
5161+
})
5162+
.collect::<Vec<_>>();
5163+
assert_eq!(
5164+
values,
5165+
expected,
5166+
"iteration {iteration}:\n{}",
5167+
displayable(plan.as_ref()).indent(true)
5168+
);
5169+
assert!(
5170+
plan.children()[0].is::<FilterExec>(),
5171+
"fetch must stay below the filter:\n{}",
5172+
displayable(plan.as_ref()).indent(true)
5173+
);
5174+
}
5175+
Ok(())
5176+
}
5177+
48635178
/// When a parent requires SinglePartition and maintains input order, order-preserving
48645179
/// variants (e.g. SortPreservingMergeExec) should be kept so that ordering can
48655180
/// propagate to ancestors. Replacing them with CoalescePartitionsExec would destroy

‎datafusion/core/tests/physical_optimizer/enforce_sorting.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2327,7 +2327,9 @@ async fn test_remove_unnecessary_spm2() -> Result<()> {
23272327
DataSourceExec: partitions=1, partition_sizes=[0]
23282328
23292329
Optimized Plan:
2330-
DataSourceExec: partitions=1, partition_sizes=[0]
2330+
LocalLimitExec: fetch=100
2331+
SortExec: expr=[non_nullable_col@1 ASC], preserve_partitioning=[false]
2332+
DataSourceExec: partitions=1, partition_sizes=[0]
23312333
");
23322334

23332335
Ok(())

0 commit comments

Comments
 (0)