Skip to content

Commit 7032b23

Browse files
cning112claudejayzhan211
authored
fix: keep per-partition constant sort keys in a partitioned TopK (apache#26455)
## Which issue does this PR close? - Closes apache#26454. ## Rationale for this change `ORDER BY ... LIMIT` over a `UNION ALL` returns wrong rows when a leading sort key is a constant with a different value in each arm: ```sql SELECT 5 AS c0, id AS c1 FROM t UNION ALL SELECT 1 AS c0, id AS c1 FROM t WHERE g = 0 ORDER BY c0, c1 LIMIT 2 -- returns (1, 0), (5, 0); expected (1, 0), (1, 1) ``` The optimizer plans a partitioned TopK under a `SortPreservingMergeExec` and drops `c0` from the TopK key, because `c0` is constant within each partition. All partitions of one `SortExec` share a single TopK dynamic filter threshold. The `c0 = 5` partition publishes a threshold on `c1` alone, and the `c0 = 1` partition then discards a row it needs. The issue has the full walk-through. ## What changes are included in this PR? `add_sort_above` and `add_sort_above_with_distribution` in `datafusion/physical-optimizer/src/utils.rs` both remove sort keys that are constant in the input. They now share one helper, `ordering_without_constants(plan, sort_requirements, keep_heterogeneous)`, which still removes them, except that a constant whose value differs between partitions (`AcrossPartitions::Heterogeneous`) is kept when `keep_heterogeneous` is set. Each caller sets it when an operator compares rows from different partitions on the new ordering: - **Partitioned TopK** (both helpers): the new `SortExec` has a `fetch` and its input has more than one partition. The shared threshold then compares the full key, which is comparable across partitions. - **Merge above the sort** (`add_sort_above_with_distribution` only): when the parent requires a single partition, the helper wraps the sort in a `SortPreservingMergeExec` built from the same ordering. That merge compares rows across partitions even without a fetch, and since it clears per-partition constants from its output, a shortened key would no longer guarantee the required ordering. The constant is now kept there too. The helper preserves these existing behaviors: - `Uniform` constants are still removed. - A partitioned sort without a `fetch` and without an added merge still removes `Heterogeneous` constants. Each partition sorts on its own, and any merge above it sorts on the full key. - With a single input partition nothing is compared across partitions. With the change, the plan for the query above is: ``` SortPreservingMergeExec: [c0@0 ASC NULLS LAST, c1@1 ASC NULLS LAST], fetch=2 SortExec: TopK(fetch=2), expr=[c0@0 ASC NULLS LAST, c1@1 ASC NULLS LAST], preserve_partitioning=[true], sort_prefix=[c0@0 ASC NULLS LAST] ``` The longer key gives the TopK a `sort_prefix` of `[c0]`, because each partition's input is trivially ordered by its constant `c0`. Why the fix lives here: `EXPLAIN VERBOSE` shows the shortened `SortExec: TopK(fetch=2), expr=[c1@1 ...]` already in the plan right after `EnsureRequirements`, with the fetch attached. No later rule changes it. A temporary print in the two helpers showed `parallelize_sorts` building it through `add_sort_above_with_check` → `add_sort_above`, and `pushdown_sorts` building it again through `add_sort_above_with_distribution`. Both calls had `fetch = Some(2)`, two input partitions, and `c0` reported as `Heterogeneous`. So both helpers need the change, and fixing only one would leave the bug. apache#23528 fixed the same `Uniform`/`Heterogeneous` confusion in `EquivalenceGroup`'s sort normalization. This PR applies it to the TopK key and to the merge that these two helpers build. Open PRs apache#25408 and apache#25065 change the callers of these helpers (`enforce_sorting/sort_pushdown.rs` and `enforce_sorting/mod.rs`) but not `utils.rs`. This PR should not conflict with them textually, but whichever merges second should re-run `topk.slt`. Two separate validation prerequisites are included: three narrowly scoped `mutable_key_type` Clippy annotations matching existing optimizer conventions, and lockfile patch updates for `rustls-webpki` (0.103.16) and `webpki-root-certs` (1.0.10). The exact all-features Clippy command failed on the unchanged base, and the security audit exposed RUSTSEC-2026-0382 / RUSTSEC-2026-0383 in the existing lockfile. Neither prerequisite changes the TopK implementation. ## What is the testing strategy for this PR? - **`topk.slt`**, on `VALUES` tables, each with an `EXPLAIN` that pins the TopK key and a result query: - the query above, and the same query without the filter; - `ORDER BY c0 DESC, c1`; - `ORDER BY c1, c0`, where the constant is not the leading key and only breaks ties on `c1`; - `LIMIT ... OFFSET`, where the TopK needs three rows from the `c0 = 1` arm; - a three-arm union, so two arms can publish a threshold that cuts the third; - controls: `LIMIT 3`, a `Uniform` constant (end-to-end control), and no `fetch` (sort pushed into the arms). Whether a result query fails without the fix depends on which arm publishes its threshold first (the `DESC` query never failed in 8 runs), so the `EXPLAIN`s are what catch a regression reliably. - **Unit tests in `utils.rs`**, one per branch: a partitioned TopK keeps a `Heterogeneous` constant; the added merge keeps it with and without a fetch; a partitioned sort without a fetch or merge drops it; a `Uniform` constant is always dropped. - **Unit tests in `topk/mod.rs`**: two TopKs share one `TopKDynamicFilters`, with key `[c0, c1]` and `sort_prefix` `[c0]`. Both feeding orders return the right top 2. A second test feeds several batches per partition and checks the early-exit state: the better partition keeps reading until it has `k` rows, and only then does the worse one finish. Ablation, with all tests in place: - Dropping `Heterogeneous` constants again in `ordering_without_constants` fails both `keep` unit tests in `utils.rs` and 10 `topk.slt` assertions, including every new `EXPLAIN`. - Removing only the merge part (`|| add_merge`) fails `merge_keeps_a_constant_that_differs_between_partitions` on its `fetch = None` case. No `.slt` test fails, see below. No existing `.slt` plan changes. Local validation on the final tree: formatting, `cargo clippy --all-targets --all-features -- -D warnings`, and `uv run ./dev/rust_lint.sh` pass. The required extended workspace test command passes with 12,733 Rust tests (8 ignored) and all 535 SQL files. Independent mutations also confirm the new TopK tests fail when the leading filter key is omitted, and the multi-batch test fails when the shared-prefix comparison is reversed. Benchmark datasets were unavailable; no performance claim is made. ## Are there any user-facing changes? The wrong results are fixed. Plans that hit this case now show the constant in the TopK `expr`. There are no API changes. ## Unknowns / assumptions - **Shared prefix threshold.** The new key gives the TopK a `sort_prefix` of `[c0]`. That enables the shared-prefix early exit from apache#22991 for these plans. It stays correct because it compares on the full key prefix, which now includes `c0`, and a threshold is only published once the publishing partition has `k` rows. The multi-batch TopK unit test exercises this directly; no `.slt` test forces a particular partition to finish first. - **No tested SQL reached the no-fetch merge branch.** I instrumented `add_sort_above_with_distribution` for `fetch = None` with a single-partition requirement and more than one input partition. It recorded no hits across the whole sqllogictest suite, for candidate queries (un-partitioned windows over union, filter, join, aggregate and distinct), or with `optimizer.repartition_sorts = false` / `optimizer.enable_sort_pushdown = false`. Distribution enforcement and `parallelize_sorts` build the merge with the full ordering before `pushdown_sorts` runs. That is an observation, not a proof, so that branch is covered by the unit test only. - **Fetch attached after key simplification (accepted risk; follow-up).** The helper decides whether to retain heterogeneous constants when it builds the sort. A partitioned sort without a fetch or helper-added merge may omit `c0`; if `LimitPushdown` or `LimitPushPastWindows` subsequently calls `SortExec::with_fetch`, that method enables shared TopK filtering without restoring `c0`. This PR does not guard that transition. No SQL query tried so far reaches the entire sequence under the current rule order: the tested shapes already have a fetch at construction, push sorts into individual union arms, retain the full key below a merge, hash-repartition first, or eliminate the inner sort. That evidence does not establish unreachability. The proposed follow-up is a hand-built plan regression plus an executor guard that isolates or disables unsafe shared filtering, including dynamic-filter pushdown. The reproduction is proposed, not yet executed. `preserve_fetch_above_ordered_plan` remains an additional path to audit. - **Alternative fix.** The other option is to stop sharing the TopK threshold across partitions when the input has a `Heterogeneous` constant. That would be a larger change inside TopK and would give up the shared filter. I went with the smaller planner change, but I am happy to switch if maintainers prefer it. --------- Co-authored-by: Claude Opus 5.5 <[email protected]> Co-authored-by: Jay Zhan <[email protected]>
1 parent a7787f4 commit 7032b23

3 files changed

Lines changed: 626 additions & 27 deletions

File tree

‎datafusion/physical-optimizer/src/utils.rs‎

Lines changed: 199 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,9 @@
1818
use std::sync::Arc;
1919

2020
use datafusion_common::Result;
21-
use datafusion_physical_expr::{Distribution, LexOrdering, LexRequirement};
21+
use datafusion_physical_expr::{
22+
AcrossPartitions, Distribution, LexOrdering, LexRequirement,
23+
};
2224
use datafusion_physical_plan::coalesce_partitions::CoalescePartitionsExec;
2325
use datafusion_physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
2426
use datafusion_physical_plan::repartition::RepartitionExec;
@@ -29,6 +31,35 @@ use datafusion_physical_plan::union::UnionExec;
2931
use datafusion_physical_plan::windows::{BoundedWindowAggExec, WindowAggExec};
3032
use datafusion_physical_plan::{ExecutionPlan, ExecutionPlanProperties};
3133

34+
/// Builds the ordering of a sort placed above `plan` from `sort_requirements`,
35+
/// leaving out the requirements whose expression is constant in `plan`'s
36+
/// output.
37+
///
38+
/// A constant with the same value in every partition
39+
/// ([`AcrossPartitions::Uniform`]) is always left out. A constant whose value
40+
/// differs between partitions ([`AcrossPartitions::Heterogeneous`]) is left out
41+
/// only when `keep_heterogeneous` is false. Callers set it when an operator
42+
/// compares rows from different partitions on this ordering, since there the
43+
/// constant still decides the order. `EquivalenceGroup::is_uniform_constant`
44+
/// makes the same distinction when it normalizes orderings (#23528).
45+
fn ordering_without_constants(
46+
plan: &dyn ExecutionPlan,
47+
sort_requirements: LexRequirement,
48+
keep_heterogeneous: bool,
49+
) -> Option<LexOrdering> {
50+
let eq_properties = plan.equivalence_properties();
51+
let sort_exprs = sort_requirements
52+
.into_iter()
53+
.filter(|req| match eq_properties.is_expr_constant(&req.expr) {
54+
None => true,
55+
Some(AcrossPartitions::Heterogeneous) => keep_heterogeneous,
56+
Some(AcrossPartitions::Uniform(_)) => false,
57+
})
58+
.map(Into::into)
59+
.collect::<Vec<_>>();
60+
LexOrdering::new(sort_exprs)
61+
}
62+
3263
/// This utility function adds a `SortExec` above an operator according to the
3364
/// given ordering requirements while preserving the original partitioning.
3465
///
@@ -40,19 +71,19 @@ pub fn add_sort_above<T: Clone + Default>(
4071
sort_requirements: LexRequirement,
4172
fetch: Option<usize>,
4273
) -> PlanContext<T> {
43-
let mut sort_reqs: Vec<_> = sort_requirements.into();
44-
sort_reqs.retain(|sort_expr| {
45-
node.plan
46-
.equivalence_properties()
47-
.is_expr_constant(&sort_expr.expr)
48-
.is_none()
49-
});
50-
let sort_exprs = sort_reqs.into_iter().map(Into::into).collect::<Vec<_>>();
51-
let Some(ordering) = LexOrdering::new(sort_exprs) else {
74+
let preserve_partitioning = node.plan.output_partitioning().partition_count() > 1;
75+
// The partitions of a `SortExec` with a fetch and `preserve_partitioning`
76+
// share one TopK threshold, which compares rows across partitions.
77+
let keep_heterogeneous = preserve_partitioning && fetch.is_some();
78+
let Some(ordering) = ordering_without_constants(
79+
node.plan.as_ref(),
80+
sort_requirements,
81+
keep_heterogeneous,
82+
) else {
5283
return node;
5384
};
5485
let mut new_sort = SortExec::new(ordering, Arc::clone(&node.plan)).with_fetch(fetch);
55-
if node.plan.output_partitioning().partition_count() > 1 {
86+
if preserve_partitioning {
5687
new_sort = new_sort.with_preserve_partitioning(true);
5788
}
5889
PlanContext::new(Arc::new(new_sort), T::default(), vec![node])
@@ -68,19 +99,22 @@ pub fn add_sort_above_with_distribution<T: Clone + Default>(
6899
fetch: Option<usize>,
69100
required_distribution: &Distribution,
70101
) -> PlanContext<T> {
71-
let mut sort_reqs: Vec<_> = sort_requirements.into();
72-
sort_reqs.retain(|sort_expr| {
73-
node.plan
74-
.equivalence_properties()
75-
.is_expr_constant(&sort_expr.expr)
76-
.is_none()
77-
});
78-
let sort_exprs = sort_reqs.into_iter().map(Into::into).collect::<Vec<_>>();
79-
let Some(ordering) = LexOrdering::new(sort_exprs) else {
80-
return node;
81-
};
82102
let input_has_multiple_partitions =
83103
node.plan.output_partitioning().partition_count() > 1;
104+
let add_merge = matches!(required_distribution, Distribution::SinglePartition)
105+
&& input_has_multiple_partitions;
106+
// A merge compares rows across partitions, and so do the partitions of a
107+
// `SortExec` with a fetch and `preserve_partitioning`, which share one TopK
108+
// threshold. Both use this ordering.
109+
let keep_heterogeneous =
110+
input_has_multiple_partitions && (fetch.is_some() || add_merge);
111+
let Some(ordering) = ordering_without_constants(
112+
node.plan.as_ref(),
113+
sort_requirements,
114+
keep_heterogeneous,
115+
) else {
116+
return node;
117+
};
84118

85119
let mut new_sort =
86120
SortExec::new(ordering.clone(), Arc::clone(&node.plan)).with_fetch(fetch);
@@ -92,9 +126,7 @@ pub fn add_sort_above_with_distribution<T: Clone + Default>(
92126

93127
// If the parent requires SinglePartition and the input has multiple partitions,
94128
// wrap the partition-preserving sort in SortPreservingMergeExec.
95-
if matches!(required_distribution, Distribution::SinglePartition)
96-
&& input_has_multiple_partitions
97-
{
129+
if add_merge {
98130
PlanContext::new(
99131
Arc::new(
100132
SortPreservingMergeExec::new(ordering, Arc::clone(&sort_node.plan))
@@ -163,3 +195,145 @@ pub fn is_repartition(plan: &Arc<dyn ExecutionPlan>) -> bool {
163195
pub fn is_limit(plan: &Arc<dyn ExecutionPlan>) -> bool {
164196
plan.is::<GlobalLimitExec>() || plan.is::<LocalLimitExec>()
165197
}
198+
199+
#[cfg(test)]
200+
mod tests {
201+
use super::*;
202+
203+
use arrow::datatypes::{DataType, Field, Schema};
204+
use datafusion_common::ScalarValue;
205+
use datafusion_physical_expr::PhysicalSortExpr;
206+
use datafusion_physical_expr::expressions::{col, lit};
207+
use datafusion_physical_plan::empty::EmptyExec;
208+
use datafusion_physical_plan::projection::ProjectionExec;
209+
210+
/// `UnionExec` of one `SELECT <c> AS c0, id AS c1` arm per constant, so
211+
/// `c0` is constant in every partition, and differs between them unless
212+
/// the constants are equal.
213+
fn union_of_constants(constants: &[i64]) -> Arc<dyn ExecutionPlan> {
214+
let schema =
215+
Arc::new(Schema::new(vec![Field::new("id", DataType::Int64, false)]));
216+
let arms = constants
217+
.iter()
218+
.map(|c| {
219+
let input = Arc::new(EmptyExec::new(Arc::clone(&schema)));
220+
let exprs = vec![
221+
(lit(ScalarValue::Int64(Some(*c))), "c0".to_string()),
222+
(col("id", &schema).unwrap(), "c1".to_string()),
223+
];
224+
Arc::new(ProjectionExec::try_new(exprs, input).unwrap())
225+
as Arc<dyn ExecutionPlan>
226+
})
227+
.collect();
228+
UnionExec::try_new(arms).unwrap()
229+
}
230+
231+
/// The requirement `c0 ASC, c1 ASC` on `plan`.
232+
fn c0_c1(plan: &Arc<dyn ExecutionPlan>) -> LexRequirement {
233+
let schema = plan.schema();
234+
LexRequirement::new(["c0", "c1"].map(|name| {
235+
PhysicalSortExpr::new_default(col(name, &schema).unwrap()).into()
236+
}))
237+
.unwrap()
238+
}
239+
240+
fn columns(ordering: &LexOrdering) -> Vec<String> {
241+
ordering.iter().map(|e| e.expr.to_string()).collect()
242+
}
243+
244+
/// The ordering of the `SortExec` and of the `SortPreservingMergeExec`, if
245+
/// any, at the top of `plan`.
246+
fn orderings(plan: &Arc<dyn ExecutionPlan>) -> (Vec<String>, Option<Vec<String>>) {
247+
if let Some(merge) = plan.downcast_ref::<SortPreservingMergeExec>() {
248+
let (sort, _) = orderings(merge.input());
249+
return (sort, Some(columns(merge.expr())));
250+
}
251+
let sort = plan.downcast_ref::<SortExec>().unwrap();
252+
(columns(sort.expr()), None)
253+
}
254+
255+
fn sort_above(
256+
plan: Arc<dyn ExecutionPlan>,
257+
fetch: Option<usize>,
258+
) -> Arc<dyn ExecutionPlan> {
259+
let reqs = c0_c1(&plan);
260+
add_sort_above(PlanContext::<()>::new_default(plan), reqs, fetch).plan
261+
}
262+
263+
fn sort_above_with_distribution(
264+
plan: Arc<dyn ExecutionPlan>,
265+
fetch: Option<usize>,
266+
distribution: Distribution,
267+
) -> Arc<dyn ExecutionPlan> {
268+
let reqs = c0_c1(&plan);
269+
let node = PlanContext::<()>::new_default(plan);
270+
add_sort_above_with_distribution(node, reqs, fetch, &distribution).plan
271+
}
272+
273+
#[test]
274+
fn partitioned_top_k_keeps_a_constant_that_differs_between_partitions() {
275+
let c0_c1 = vec!["c0@0".to_string(), "c1@1".to_string()];
276+
assert_eq!(
277+
orderings(&sort_above(union_of_constants(&[5, 1]), Some(2))),
278+
(c0_c1.clone(), None)
279+
);
280+
assert_eq!(
281+
orderings(&sort_above_with_distribution(
282+
union_of_constants(&[5, 1]),
283+
Some(2),
284+
Distribution::UnspecifiedDistribution,
285+
)),
286+
(c0_c1, None)
287+
);
288+
}
289+
290+
#[test]
291+
fn merge_keeps_a_constant_that_differs_between_partitions() {
292+
let c0_c1 = vec!["c0@0".to_string(), "c1@1".to_string()];
293+
for fetch in [None, Some(2)] {
294+
assert_eq!(
295+
orderings(&sort_above_with_distribution(
296+
union_of_constants(&[5, 1]),
297+
fetch,
298+
Distribution::SinglePartition,
299+
)),
300+
(c0_c1.clone(), Some(c0_c1.clone())),
301+
"fetch {fetch:?}"
302+
);
303+
}
304+
}
305+
306+
#[test]
307+
fn sort_without_fetch_or_merge_drops_a_constant_that_differs_between_partitions() {
308+
let c1 = vec!["c1@1".to_string()];
309+
assert_eq!(
310+
orderings(&sort_above(union_of_constants(&[5, 1]), None)),
311+
(c1.clone(), None)
312+
);
313+
assert_eq!(
314+
orderings(&sort_above_with_distribution(
315+
union_of_constants(&[5, 1]),
316+
None,
317+
Distribution::UnspecifiedDistribution,
318+
)),
319+
(c1, None)
320+
);
321+
}
322+
323+
#[test]
324+
fn sort_drops_a_constant_with_the_same_value_in_every_partition() {
325+
let c1 = vec!["c1@1".to_string()];
326+
assert_eq!(
327+
orderings(&sort_above(union_of_constants(&[1, 1]), Some(2))),
328+
(c1.clone(), None)
329+
);
330+
assert_eq!(
331+
orderings(&sort_above_with_distribution(
332+
union_of_constants(&[1, 1]),
333+
Some(2),
334+
Distribution::SinglePartition,
335+
)),
336+
(c1.clone(), Some(c1))
337+
);
338+
}
339+
}

0 commit comments

Comments
 (0)