This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datafusion.git
The following commit(s) were added to refs/heads/main by this push:
new 4042812a86 fix: consider nulls_first when propagating ordered
SortProperties (#24206)
4042812a86 is described below
commit 4042812a86f4a753c4b717ecbe12dbc928957254
Author: Nagato Yuzuru <[email protected]>
AuthorDate: Sun Aug 16 02:31:43 2026 +0000
fix: consider nulls_first when propagating ordered SortProperties (#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 #123` indicates that this PR will close issue #123.
-->
- Closes #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
https://github.com/apache/datafusion/issues/11596#issuecomment-5232788766
)
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.
---
Cargo.lock | 1 +
datafusion/expr-common/Cargo.toml | 1 +
datafusion/expr-common/src/sort_properties.rs | 267 +++++++++++++++++++++++++-
datafusion/sqllogictest/test_files/order.slt | 84 +++++++-
4 files changed, 344 insertions(+), 9 deletions(-)
diff --git a/Cargo.lock b/Cargo.lock
index d7576659f0..cca0d1fdbf 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -2196,6 +2196,7 @@ dependencies = [
"indexmap 2.14.0",
"insta",
"itertools 0.15.0",
+ "rstest",
]
[[package]]
diff --git a/datafusion/expr-common/Cargo.toml
b/datafusion/expr-common/Cargo.toml
index 072c8f14da..026c1e0bc3 100644
--- a/datafusion/expr-common/Cargo.toml
+++ b/datafusion/expr-common/Cargo.toml
@@ -48,3 +48,4 @@ itertools = { workspace = true }
[dev-dependencies]
insta = { workspace = true }
+rstest = { workspace = true }
diff --git a/datafusion/expr-common/src/sort_properties.rs
b/datafusion/expr-common/src/sort_properties.rs
index 74d644f79f..6f18a8a46a 100644
--- a/datafusion/expr-common/src/sort_properties.rs
+++ b/datafusion/expr-common/src/sort_properties.rs
@@ -50,11 +50,12 @@ impl SortProperties {
(Self::Singleton, _) => *rhs,
(_, Self::Singleton) => *self,
(Self::Ordered(lhs), Self::Ordered(rhs))
- if lhs.descending == rhs.descending =>
+ if lhs.descending == rhs.descending
+ && lhs.nulls_first == rhs.nulls_first =>
{
Self::Ordered(SortOptions {
descending: lhs.descending,
- nulls_first: lhs.nulls_first || rhs.nulls_first,
+ nulls_first: lhs.nulls_first,
})
}
_ => Self::Unordered,
@@ -70,11 +71,12 @@ impl SortProperties {
}),
(_, Self::Singleton) => *self,
(Self::Ordered(lhs), Self::Ordered(rhs))
- if lhs.descending != rhs.descending =>
+ if lhs.descending != rhs.descending
+ && lhs.nulls_first == rhs.nulls_first =>
{
Self::Ordered(SortOptions {
descending: lhs.descending,
- nulls_first: lhs.nulls_first || rhs.nulls_first,
+ nulls_first: lhs.nulls_first,
})
}
_ => Self::Unordered,
@@ -89,7 +91,8 @@ impl SortProperties {
}),
(_, Self::Singleton) => *self,
(Self::Ordered(lhs), Self::Ordered(rhs))
- if lhs.descending != rhs.descending =>
+ if lhs.descending != rhs.descending
+ && lhs.nulls_first == rhs.nulls_first =>
{
*self
}
@@ -100,11 +103,12 @@ impl SortProperties {
pub fn and_or(&self, rhs: &Self) -> Self {
match (self, rhs) {
(Self::Ordered(lhs), Self::Ordered(rhs))
- if lhs.descending == rhs.descending =>
+ if lhs.descending == rhs.descending
+ && lhs.nulls_first == rhs.nulls_first =>
{
Self::Ordered(SortOptions {
descending: lhs.descending,
- nulls_first: lhs.nulls_first || rhs.nulls_first,
+ nulls_first: lhs.nulls_first,
})
}
(Self::Ordered(opt), Self::Singleton)
@@ -118,6 +122,255 @@ impl SortProperties {
}
}
+#[cfg(test)]
+mod sort_properties_test {
+ use super::{SortOptions, SortProperties};
+ use rstest::rstest;
+
+ const fn ordered(descending: bool, nulls_first: bool) -> SortProperties {
+ SortProperties::Ordered(SortOptions {
+ descending,
+ nulls_first,
+ })
+ }
+
+ const ASC_NF: SortProperties = ordered(false, true);
+ const ASC_NL: SortProperties = ordered(false, false);
+ const DESC_NF: SortProperties = ordered(true, true);
+ const DESC_NL: SortProperties = ordered(true, false);
+ const UNORDERED: SortProperties = SortProperties::Unordered;
+ const SINGLETON: SortProperties = SortProperties::Singleton;
+
+ type BinOp = fn(&SortProperties, &SortProperties) -> SortProperties;
+
+ /// Each method's direction rule and its `Singleton` arms.
+ ///
+ /// Operands that *disagree* on null placement are deliberately absent:
+ /// that half is covered exhaustively by
+ /// [`conflicting_null_placement_is_never_ordered`].
+ #[test]
+ fn ordering_propagation() {
+ let cases: &[(&str, BinOp, SortProperties, SortProperties,
SortProperties)] = &[
+ // `add` preserves ordering when both operands run in the same
+ // direction. It is commutative, so one argument order suffices.
+ (
+ "add: same direction is preserved",
+ SortProperties::add,
+ ASC_NF,
+ ASC_NF,
+ ASC_NF,
+ ),
+ (
+ "add: nulls_last placement is preserved",
+ SortProperties::add,
+ ASC_NL,
+ ASC_NL,
+ ASC_NL,
+ ),
+ (
+ "add: opposing directions are unordered",
+ SortProperties::add,
+ ASC_NF,
+ DESC_NF,
+ UNORDERED,
+ ),
+ (
+ "add: literal with ordered",
+ SortProperties::add,
+ SINGLETON,
+ ASC_NF,
+ ASC_NF,
+ ),
+ (
+ "add: two literals stay a literal",
+ SortProperties::add,
+ SINGLETON,
+ SINGLETON,
+ SINGLETON,
+ ),
+ // `and_or` backs both `AND` and `OR`, whose rules coincide. Same
+ // shape as `add`, and likewise commutative.
+ (
+ "and_or: same direction is preserved",
+ SortProperties::and_or,
+ ASC_NF,
+ ASC_NF,
+ ASC_NF,
+ ),
+ (
+ "and_or: nulls_last placement is preserved",
+ SortProperties::and_or,
+ DESC_NL,
+ DESC_NL,
+ DESC_NL,
+ ),
+ (
+ "and_or: opposing directions are unordered",
+ SortProperties::and_or,
+ ASC_NF,
+ DESC_NF,
+ UNORDERED,
+ ),
+ (
+ "and_or: literal with ordered",
+ SortProperties::and_or,
+ SINGLETON,
+ ASC_NF,
+ ASC_NF,
+ ),
+ (
+ "and_or: two literals stay a literal",
+ SortProperties::and_or,
+ SINGLETON,
+ SINGLETON,
+ SINGLETON,
+ ),
+ // `sub` needs the *opposite* rule: an ascending column minus a
+ // descending one still ascends. It is not commutative
+ (
+ "sub: opposing directions are preserved",
+ SortProperties::sub,
+ ASC_NF,
+ DESC_NF,
+ ASC_NF,
+ ),
+ (
+ "sub: result follows the left operand",
+ SortProperties::sub,
+ DESC_NF,
+ ASC_NF,
+ DESC_NF,
+ ),
+ (
+ "sub: nulls_last placement is preserved",
+ SortProperties::sub,
+ ASC_NL,
+ DESC_NL,
+ ASC_NL,
+ ),
+ (
+ "sub: same direction is unordered",
+ SortProperties::sub,
+ ASC_NF,
+ ASC_NF,
+ UNORDERED,
+ ),
+ (
+ "sub: literal minus ordered flips the direction",
+ SortProperties::sub,
+ SINGLETON,
+ ASC_NF,
+ DESC_NF,
+ ),
+ (
+ "sub: ordered minus literal keeps the direction",
+ SortProperties::sub,
+ ASC_NF,
+ SINGLETON,
+ ASC_NF,
+ ),
+ (
+ "sub: two literals stay a literal",
+ SortProperties::sub,
+ SINGLETON,
+ SINGLETON,
+ SINGLETON,
+ ),
+ // `gt_or_gteq` compares into a boolean column, which is ordered by
+ // `false < true`. Same direction rule as `sub`, also asymmetric.
+ (
+ "gt_or_gteq: opposing directions are preserved",
+ SortProperties::gt_or_gteq,
+ ASC_NF,
+ DESC_NF,
+ ASC_NF,
+ ),
+ (
+ "gt_or_gteq: result follows the left operand",
+ SortProperties::gt_or_gteq,
+ DESC_NF,
+ ASC_NF,
+ DESC_NF,
+ ),
+ (
+ "gt_or_gteq: nulls_last placement is preserved",
+ SortProperties::gt_or_gteq,
+ DESC_NL,
+ ASC_NL,
+ DESC_NL,
+ ),
+ (
+ "gt_or_gteq: same direction is unordered",
+ SortProperties::gt_or_gteq,
+ ASC_NF,
+ ASC_NF,
+ UNORDERED,
+ ),
+ (
+ "gt_or_gteq: literal on the left flips the direction",
+ SortProperties::gt_or_gteq,
+ SINGLETON,
+ ASC_NF,
+ DESC_NF,
+ ),
+ (
+ "gt_or_gteq: literal on the right keeps the direction",
+ SortProperties::gt_or_gteq,
+ ASC_NF,
+ SINGLETON,
+ ASC_NF,
+ ),
+ (
+ "gt_or_gteq: two literals stay a literal",
+ SortProperties::gt_or_gteq,
+ SINGLETON,
+ SINGLETON,
+ SINGLETON,
+ ),
+ ];
+
+ for &(name, op, lhs, rhs, expected) in cases {
+ assert_eq!(op(&lhs, &rhs), expected, "case: {name}");
+ }
+
+ // `add` and `and_or` are commutative, which is what lets the table
+ // above cover only one argument order for them.
+ for (lhs, rhs) in [(ASC_NF, DESC_NL), (ASC_NF, SINGLETON), (ASC_NL,
DESC_NF)] {
+ assert_eq!(lhs.add(&rhs), rhs.add(&lhs), "add is commutative");
+ assert_eq!(lhs.and_or(&rhs), rhs.and_or(&lhs), "and_or is
commutative");
+ }
+ }
+
+ /// If two ordered operands disagree on null placement, the result is
+ /// always Unordered, no matter which operator or direction is used.
+ /// Checked below for every combination.
+ ///
+ /// Nulls propagate: the result is null wherever either operand is
+ /// null. `nulls_first` treats those rows as a prefix, `nulls_last` as
+ /// a suffix. A set that's both can't be described by any `SortOptions`.
+ ///
+ /// The assertion only checks "not Ordered", not which ordering
+ /// results. That keeps the test from just repeating the logic it's
+ /// checking.
+ #[rstest]
+ #[case::add("add", SortProperties::add)]
+ #[case::sub("sub", SortProperties::sub)]
+ #[case::gt_or_gteq("gt_or_gteq", SortProperties::gt_or_gteq)]
+ #[case::and_or("and_or", SortProperties::and_or)]
+ fn conflicting_null_placement_is_never_ordered(
+ #[values(false, true)] l_descending: bool,
+ #[values(false, true)] r_descending: bool,
+ #[values(false, true)] l_nulls_first: bool,
+ #[case] op_name: &str,
+ #[case] op: BinOp,
+ ) {
+ // Negating `l_nulls_first` makes the operands disagree by
construction.
+ let lhs = ordered(l_descending, l_nulls_first);
+ let rhs = ordered(r_descending, !l_nulls_first);
+ assert_eq!(op(&lhs, &rhs), UNORDERED, "{op_name}: {lhs:?} and
{rhs:?}");
+ }
+}
+
impl Neg for SortProperties {
type Output = Self;
diff --git a/datafusion/sqllogictest/test_files/order.slt
b/datafusion/sqllogictest/test_files/order.slt
index 4b136d24b0..dfe5c0faab 100644
--- a/datafusion/sqllogictest/test_files/order.slt
+++ b/datafusion/sqllogictest/test_files/order.slt
@@ -1485,7 +1485,9 @@ physical_plan
03)----RepartitionExec: partitioning=RoundRobinBatch(2), input_partitions=1,
maintains_sort_order=true
04)------DataSourceExec: file_groups={1 group:
[[WORKSPACE_ROOT/datafusion/core/tests/data/window_2.csv]]}, projection=[c],
output_ordering=[c@0 ASC NULLS LAST], file_type=csv, has_header=true
-# Boolean to integer casts preserve the order.
+# The cast preserves the order, but the comparison does not: `inc_col` is
+# ASC NULLS LAST while `desc_col` is DESC NULLS FIRST, so `inc_col > desc_col`
+# is null at both ends and the sort has to stay.
statement ok
CREATE EXTERNAL TABLE annotated_data_finite (
ts INTEGER,
@@ -1507,9 +1509,87 @@ logical_plan
03)----TableScan: annotated_data_finite projection=[inc_col, desc_col]
physical_plan
01)SortPreservingMergeExec: [c@0 ASC NULLS LAST]
+02)--SortExec: expr=[c@0 ASC NULLS LAST], preserve_partitioning=[true]
+03)----ProjectionExec: expr=[CAST(inc_col@0 > desc_col@1 AS Int32) as c]
+04)------RepartitionExec: partitioning=RoundRobinBatch(2), input_partitions=1,
maintains_sort_order=true
+05)--------DataSourceExec: file_groups={1 group:
[[WORKSPACE_ROOT/datafusion/core/tests/data/window_1.csv]]},
projection=[inc_col, desc_col], output_orderings=[[inc_col@0 ASC NULLS LAST],
[desc_col@1 DESC]], file_type=csv, has_header=true
+
+# With matching null placement the comparison keeps its order: no sort needed.
+statement ok
+CREATE EXTERNAL TABLE annotated_data_finite_nulls_last (
+ ts INTEGER,
+ inc_col INTEGER,
+ desc_col INTEGER,
+)
+STORED AS CSV
+WITH ORDER (inc_col ASC NULLS LAST)
+WITH ORDER (desc_col DESC NULLS LAST)
+LOCATION '../core/tests/data/window_1.csv'
+OPTIONS ('format.has_header' 'true');
+
+query TT
+EXPLAIN SELECT CAST((inc_col>desc_col) as integer) as c from
annotated_data_finite_nulls_last order by c;
+----
+logical_plan
+01)Sort: c ASC NULLS LAST
+02)--Projection: CAST(annotated_data_finite_nulls_last.inc_col >
annotated_data_finite_nulls_last.desc_col AS Int32) AS c
+03)----TableScan: annotated_data_finite_nulls_last projection=[inc_col,
desc_col]
+physical_plan
+01)SortPreservingMergeExec: [c@0 ASC NULLS LAST]
02)--ProjectionExec: expr=[CAST(inc_col@0 > desc_col@1 AS Int32) as c]
03)----RepartitionExec: partitioning=RoundRobinBatch(2), input_partitions=1,
maintains_sort_order=true
-04)------DataSourceExec: file_groups={1 group:
[[WORKSPACE_ROOT/datafusion/core/tests/data/window_1.csv]]},
projection=[inc_col, desc_col], output_orderings=[[inc_col@0 ASC NULLS LAST],
[desc_col@1 DESC]], file_type=csv, has_header=true
+04)------DataSourceExec: file_groups={1 group:
[[WORKSPACE_ROOT/datafusion/core/tests/data/window_1.csv]]},
projection=[inc_col, desc_col], output_orderings=[[inc_col@0 ASC NULLS LAST],
[desc_col@1 DESC NULLS LAST]], file_type=csv, has_header=true
+
+# Regression test for #11596. `a` is ASC NULLS FIRST and `b` is ASC NULLS LAST,
+# so `a + b` is null at both ends of the scan: (NULL, 3, 6, NULL). No nulls
+# placement describes that.
+query I
+COPY (VALUES (NULL, 1), (1, 2), (2, 4), (3, NULL))
+TO 'test_files/scratch/order/mixed_null_placement.csv'
+OPTIONS ('format.has_header' 'true');
+----
+4
+
+statement ok
+CREATE EXTERNAL TABLE mixed_null_placement (
+ a BIGINT,
+ b BIGINT
+)
+STORED AS CSV
+WITH ORDER (a ASC NULLS FIRST)
+WITH ORDER (b ASC NULLS LAST)
+LOCATION 'test_files/scratch/order/mixed_null_placement.csv'
+OPTIONS ('format.has_header' 'true');
+
+# The sort has to happen. Without it, this comes back in scan order.
+query I
+SELECT a + b AS s FROM mixed_null_placement ORDER BY s;
+----
+3
+6
+NULL
+NULL
+
+# Same at the plan level. Two separate things keep this sort: `add()` won't
+# merge mismatched `nulls_first`, and `arithmetic_sort_properties` gives up on
+# any `col + col` with unbounded ranges, which is every column read from a
+# file. The second masks the first today.
+query TT
+EXPLAIN SELECT a + b AS s FROM mixed_null_placement ORDER BY s;
+----
+logical_plan
+01)Sort: s ASC NULLS LAST
+02)--Projection: mixed_null_placement.a + mixed_null_placement.b AS s
+03)----TableScan: mixed_null_placement projection=[a, b]
+physical_plan
+01)SortPreservingMergeExec: [s@0 ASC NULLS LAST]
+02)--SortExec: expr=[s@0 ASC NULLS LAST], preserve_partitioning=[true]
+03)----ProjectionExec: expr=[a@0 + b@1 as s]
+04)------RepartitionExec: partitioning=RoundRobinBatch(2), input_partitions=1,
maintains_sort_order=true
+05)--------DataSourceExec: file_groups={1 group:
[[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/order/mixed_null_placement.csv]]},
projection=[a, b], output_orderings=[[a@0 ASC], [b@1 ASC NULLS LAST]],
file_type=csv, has_header=true
+
+statement ok
+DROP TABLE mixed_null_placement;
# Union a query with the actual data and one with a constant
query I
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
