Skip to content

Commit 4042812

Browse files
fix: consider nulls_first when propagating ordered SortProperties (apache#24206)
## Which issue does this PR close? <!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes apache#123` indicates that this PR will close issue apache#123. --> - Closes apache#11596. ## Rationale for this change <!-- Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed. Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes. Please explain the problem you are trying to solve in terms of the user-visible behavior, rather than the implementation. For example, "The code in `foo.rs` doesn't handle nulls" is a symptom of the implementation. "COUNT(DISTINCT) returns wrong results when the column contains nulls" is the user-visible problem. --> In the original implementation, cases where `null_first` is not same were not correctly handled and were still treated as `ordered`. Example: `a` sorted `ASC NULLS FIRST`, `b` sorted `ASC NULLS LAST`: | a | b | a + b | | ---- | ---- | ----- | | NULL | 1 | NULL | | 1 | 2 | 3 | | 2 | 4 | 6 | | 3 | NULL | NULL | Since `a + b` is `NULL` wherever either input is, the result has nulls at both ends. The previous code returned `Ordered(ASC, nulls_first: true)` for this case; it now returns `Unordered`. ## What changes are included in this PR? <!-- There is no need to duplicate the description in the issue here, but it is sometimes worth providing a summary of the individual changes in this PR. --> Unit Tests were added and issues were fixed. Additional processing was performed on `and_or` (see apache#11596 (comment) ) SortProperties::{add, sub, gt_or_gteq, and_or} now propagate an Ordered result only when both operands agree on nulls_first; otherwise they return Unordered. This is conservative. If one input were known to be non-null the old result could be valid. But SortProperties carries no nullability information, so Unordered is the only sound answer at this layer. ## Are these changes tested? <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 2. Serve as another way to document the expected behavior of the code If tests are not included in your PR, please explain why (for example, are they covered by existing tests)? --> Yes. ## Are there any user-facing changes? <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. If there are any breaking changes to public APIs, please add the `api change` label. --> No.
1 parent 2da78d6 commit 4042812

4 files changed

Lines changed: 344 additions & 9 deletions

File tree

‎Cargo.lock‎

Lines changed: 1 addition & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎datafusion/expr-common/Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -48,3 +48,4 @@ itertools = { workspace = true }
4848

4949
[dev-dependencies]
5050
insta = { workspace = true }
51+
rstest = { workspace = true }

‎datafusion/expr-common/src/sort_properties.rs‎

Lines changed: 260 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -50,11 +50,12 @@ impl SortProperties {
5050
(Self::Singleton, _) => *rhs,
5151
(_, Self::Singleton) => *self,
5252
(Self::Ordered(lhs), Self::Ordered(rhs))
53-
if lhs.descending == rhs.descending =>
53+
if lhs.descending == rhs.descending
54+
&& lhs.nulls_first == rhs.nulls_first =>
5455
{
5556
Self::Ordered(SortOptions {
5657
descending: lhs.descending,
57-
nulls_first: lhs.nulls_first || rhs.nulls_first,
58+
nulls_first: lhs.nulls_first,
5859
})
5960
}
6061
_ => Self::Unordered,
@@ -70,11 +71,12 @@ impl SortProperties {
7071
}),
7172
(_, Self::Singleton) => *self,
7273
(Self::Ordered(lhs), Self::Ordered(rhs))
73-
if lhs.descending != rhs.descending =>
74+
if lhs.descending != rhs.descending
75+
&& lhs.nulls_first == rhs.nulls_first =>
7476
{
7577
Self::Ordered(SortOptions {
7678
descending: lhs.descending,
77-
nulls_first: lhs.nulls_first || rhs.nulls_first,
79+
nulls_first: lhs.nulls_first,
7880
})
7981
}
8082
_ => Self::Unordered,
@@ -89,7 +91,8 @@ impl SortProperties {
8991
}),
9092
(_, Self::Singleton) => *self,
9193
(Self::Ordered(lhs), Self::Ordered(rhs))
92-
if lhs.descending != rhs.descending =>
94+
if lhs.descending != rhs.descending
95+
&& lhs.nulls_first == rhs.nulls_first =>
9396
{
9497
*self
9598
}
@@ -100,11 +103,12 @@ impl SortProperties {
100103
pub fn and_or(&self, rhs: &Self) -> Self {
101104
match (self, rhs) {
102105
(Self::Ordered(lhs), Self::Ordered(rhs))
103-
if lhs.descending == rhs.descending =>
106+
if lhs.descending == rhs.descending
107+
&& lhs.nulls_first == rhs.nulls_first =>
104108
{
105109
Self::Ordered(SortOptions {
106110
descending: lhs.descending,
107-
nulls_first: lhs.nulls_first || rhs.nulls_first,
111+
nulls_first: lhs.nulls_first,
108112
})
109113
}
110114
(Self::Ordered(opt), Self::Singleton)
@@ -118,6 +122,255 @@ impl SortProperties {
118122
}
119123
}
120124

125+
#[cfg(test)]
126+
mod sort_properties_test {
127+
use super::{SortOptions, SortProperties};
128+
use rstest::rstest;
129+
130+
const fn ordered(descending: bool, nulls_first: bool) -> SortProperties {
131+
SortProperties::Ordered(SortOptions {
132+
descending,
133+
nulls_first,
134+
})
135+
}
136+
137+
const ASC_NF: SortProperties = ordered(false, true);
138+
const ASC_NL: SortProperties = ordered(false, false);
139+
const DESC_NF: SortProperties = ordered(true, true);
140+
const DESC_NL: SortProperties = ordered(true, false);
141+
const UNORDERED: SortProperties = SortProperties::Unordered;
142+
const SINGLETON: SortProperties = SortProperties::Singleton;
143+
144+
type BinOp = fn(&SortProperties, &SortProperties) -> SortProperties;
145+
146+
/// Each method's direction rule and its `Singleton` arms.
147+
///
148+
/// Operands that *disagree* on null placement are deliberately absent:
149+
/// that half is covered exhaustively by
150+
/// [`conflicting_null_placement_is_never_ordered`].
151+
#[test]
152+
fn ordering_propagation() {
153+
let cases: &[(&str, BinOp, SortProperties, SortProperties, SortProperties)] = &[
154+
// `add` preserves ordering when both operands run in the same
155+
// direction. It is commutative, so one argument order suffices.
156+
(
157+
"add: same direction is preserved",
158+
SortProperties::add,
159+
ASC_NF,
160+
ASC_NF,
161+
ASC_NF,
162+
),
163+
(
164+
"add: nulls_last placement is preserved",
165+
SortProperties::add,
166+
ASC_NL,
167+
ASC_NL,
168+
ASC_NL,
169+
),
170+
(
171+
"add: opposing directions are unordered",
172+
SortProperties::add,
173+
ASC_NF,
174+
DESC_NF,
175+
UNORDERED,
176+
),
177+
(
178+
"add: literal with ordered",
179+
SortProperties::add,
180+
SINGLETON,
181+
ASC_NF,
182+
ASC_NF,
183+
),
184+
(
185+
"add: two literals stay a literal",
186+
SortProperties::add,
187+
SINGLETON,
188+
SINGLETON,
189+
SINGLETON,
190+
),
191+
// `and_or` backs both `AND` and `OR`, whose rules coincide. Same
192+
// shape as `add`, and likewise commutative.
193+
(
194+
"and_or: same direction is preserved",
195+
SortProperties::and_or,
196+
ASC_NF,
197+
ASC_NF,
198+
ASC_NF,
199+
),
200+
(
201+
"and_or: nulls_last placement is preserved",
202+
SortProperties::and_or,
203+
DESC_NL,
204+
DESC_NL,
205+
DESC_NL,
206+
),
207+
(
208+
"and_or: opposing directions are unordered",
209+
SortProperties::and_or,
210+
ASC_NF,
211+
DESC_NF,
212+
UNORDERED,
213+
),
214+
(
215+
"and_or: literal with ordered",
216+
SortProperties::and_or,
217+
SINGLETON,
218+
ASC_NF,
219+
ASC_NF,
220+
),
221+
(
222+
"and_or: two literals stay a literal",
223+
SortProperties::and_or,
224+
SINGLETON,
225+
SINGLETON,
226+
SINGLETON,
227+
),
228+
// `sub` needs the *opposite* rule: an ascending column minus a
229+
// descending one still ascends. It is not commutative
230+
(
231+
"sub: opposing directions are preserved",
232+
SortProperties::sub,
233+
ASC_NF,
234+
DESC_NF,
235+
ASC_NF,
236+
),
237+
(
238+
"sub: result follows the left operand",
239+
SortProperties::sub,
240+
DESC_NF,
241+
ASC_NF,
242+
DESC_NF,
243+
),
244+
(
245+
"sub: nulls_last placement is preserved",
246+
SortProperties::sub,
247+
ASC_NL,
248+
DESC_NL,
249+
ASC_NL,
250+
),
251+
(
252+
"sub: same direction is unordered",
253+
SortProperties::sub,
254+
ASC_NF,
255+
ASC_NF,
256+
UNORDERED,
257+
),
258+
(
259+
"sub: literal minus ordered flips the direction",
260+
SortProperties::sub,
261+
SINGLETON,
262+
ASC_NF,
263+
DESC_NF,
264+
),
265+
(
266+
"sub: ordered minus literal keeps the direction",
267+
SortProperties::sub,
268+
ASC_NF,
269+
SINGLETON,
270+
ASC_NF,
271+
),
272+
(
273+
"sub: two literals stay a literal",
274+
SortProperties::sub,
275+
SINGLETON,
276+
SINGLETON,
277+
SINGLETON,
278+
),
279+
// `gt_or_gteq` compares into a boolean column, which is ordered by
280+
// `false < true`. Same direction rule as `sub`, also asymmetric.
281+
(
282+
"gt_or_gteq: opposing directions are preserved",
283+
SortProperties::gt_or_gteq,
284+
ASC_NF,
285+
DESC_NF,
286+
ASC_NF,
287+
),
288+
(
289+
"gt_or_gteq: result follows the left operand",
290+
SortProperties::gt_or_gteq,
291+
DESC_NF,
292+
ASC_NF,
293+
DESC_NF,
294+
),
295+
(
296+
"gt_or_gteq: nulls_last placement is preserved",
297+
SortProperties::gt_or_gteq,
298+
DESC_NL,
299+
ASC_NL,
300+
DESC_NL,
301+
),
302+
(
303+
"gt_or_gteq: same direction is unordered",
304+
SortProperties::gt_or_gteq,
305+
ASC_NF,
306+
ASC_NF,
307+
UNORDERED,
308+
),
309+
(
310+
"gt_or_gteq: literal on the left flips the direction",
311+
SortProperties::gt_or_gteq,
312+
SINGLETON,
313+
ASC_NF,
314+
DESC_NF,
315+
),
316+
(
317+
"gt_or_gteq: literal on the right keeps the direction",
318+
SortProperties::gt_or_gteq,
319+
ASC_NF,
320+
SINGLETON,
321+
ASC_NF,
322+
),
323+
(
324+
"gt_or_gteq: two literals stay a literal",
325+
SortProperties::gt_or_gteq,
326+
SINGLETON,
327+
SINGLETON,
328+
SINGLETON,
329+
),
330+
];
331+
332+
for &(name, op, lhs, rhs, expected) in cases {
333+
assert_eq!(op(&lhs, &rhs), expected, "case: {name}");
334+
}
335+
336+
// `add` and `and_or` are commutative, which is what lets the table
337+
// above cover only one argument order for them.
338+
for (lhs, rhs) in [(ASC_NF, DESC_NL), (ASC_NF, SINGLETON), (ASC_NL, DESC_NF)] {
339+
assert_eq!(lhs.add(&rhs), rhs.add(&lhs), "add is commutative");
340+
assert_eq!(lhs.and_or(&rhs), rhs.and_or(&lhs), "and_or is commutative");
341+
}
342+
}
343+
344+
/// If two ordered operands disagree on null placement, the result is
345+
/// always Unordered, no matter which operator or direction is used.
346+
/// Checked below for every combination.
347+
///
348+
/// Nulls propagate: the result is null wherever either operand is
349+
/// null. `nulls_first` treats those rows as a prefix, `nulls_last` as
350+
/// a suffix. A set that's both can't be described by any `SortOptions`.
351+
///
352+
/// The assertion only checks "not Ordered", not which ordering
353+
/// results. That keeps the test from just repeating the logic it's
354+
/// checking.
355+
#[rstest]
356+
#[case::add("add", SortProperties::add)]
357+
#[case::sub("sub", SortProperties::sub)]
358+
#[case::gt_or_gteq("gt_or_gteq", SortProperties::gt_or_gteq)]
359+
#[case::and_or("and_or", SortProperties::and_or)]
360+
fn conflicting_null_placement_is_never_ordered(
361+
#[values(false, true)] l_descending: bool,
362+
#[values(false, true)] r_descending: bool,
363+
#[values(false, true)] l_nulls_first: bool,
364+
#[case] op_name: &str,
365+
#[case] op: BinOp,
366+
) {
367+
// Negating `l_nulls_first` makes the operands disagree by construction.
368+
let lhs = ordered(l_descending, l_nulls_first);
369+
let rhs = ordered(r_descending, !l_nulls_first);
370+
assert_eq!(op(&lhs, &rhs), UNORDERED, "{op_name}: {lhs:?} and {rhs:?}");
371+
}
372+
}
373+
121374
impl Neg for SortProperties {
122375
type Output = Self;
123376

0 commit comments

Comments
 (0)