Skip to content

Commit ceaef16

Browse files
Split and deprecate and_or (apache#24276)
## 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#24208. ## 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. --> Under Kleene logic, the behavior of `and` and `or` is inconsistent with respect to transitivity of ordered. See apache#24208 for the counterexamples and the full rules. ## 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. --> - Split `SortProperties::and_or` into `and` / `or` . `BinaryExpr::get_properties` now calls the matching method per operator. - Deprecate `and_or` and narrow it to what `and` and `or` agree on (`Singleton`/`Singleton` → `Singleton`, everything else `Unordered`). A caller of `and_or` does not say which operator it means, so any stronger claim is wrong for one of them. The previous behavior is this bug. ## 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. --> Yes. Split and deprecate `and_or`
1 parent cd8cef9 commit ceaef16

4 files changed

Lines changed: 225 additions & 37 deletions

File tree

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

Lines changed: 130 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -100,23 +100,32 @@ impl SortProperties {
100100
}
101101
}
102102

103-
pub fn and_or(&self, rhs: &Self) -> Self {
103+
/// `AND` keeps an ordering only when nulls sort after `true`
104+
/// (`ASC NULLS LAST`, `DESC NULLS FIRST`).
105+
pub fn and(&self, rhs: &Self) -> Self {
106+
self.kleene(rhs, |opt| opt.descending == opt.nulls_first)
107+
}
108+
109+
/// `OR` keeps an ordering only when nulls sort before `false`
110+
/// (`ASC NULLS FIRST`, `DESC NULLS LAST`).
111+
pub fn or(&self, rhs: &Self) -> Self {
112+
self.kleene(rhs, |opt| opt.descending != opt.nulls_first)
113+
}
114+
115+
/// `preserves` reports whether the operator keeps data in that ordering.
116+
/// A `Singleton` may be a literal NULL, so it carries the same guard.
117+
fn kleene(&self, rhs: &Self, preserves: fn(&SortOptions) -> bool) -> Self {
104118
match (self, rhs) {
105-
(Self::Ordered(lhs), Self::Ordered(rhs))
106-
if lhs.descending == rhs.descending
107-
&& lhs.nulls_first == rhs.nulls_first =>
119+
(Self::Singleton, Self::Singleton) => Self::Singleton,
120+
(Self::Ordered(opt), Self::Singleton)
121+
| (Self::Singleton, Self::Ordered(opt))
122+
if preserves(opt) =>
108123
{
109-
Self::Ordered(SortOptions {
110-
descending: lhs.descending,
111-
nulls_first: lhs.nulls_first,
112-
})
124+
Self::Ordered(*opt)
125+
}
126+
(Self::Ordered(lhs), Self::Ordered(rhs)) if lhs == rhs && preserves(lhs) => {
127+
Self::Ordered(*lhs)
113128
}
114-
(Self::Ordered(opt), Self::Singleton)
115-
| (Self::Singleton, Self::Ordered(opt)) => Self::Ordered(SortOptions {
116-
descending: opt.descending,
117-
nulls_first: opt.nulls_first,
118-
}),
119-
(Self::Singleton, Self::Singleton) => Self::Singleton,
120129
_ => Self::Unordered,
121130
}
122131
}
@@ -188,39 +197,116 @@ mod sort_properties_test {
188197
SINGLETON,
189198
SINGLETON,
190199
),
191-
// `and_or` backs both `AND` and `OR`, whose rules coincide. Same
192-
// shape as `add`, and likewise commutative.
200+
// `and` keeps ASC NULLS LAST / DESC NULLS FIRST, `or` keeps ASC
201+
// NULLS FIRST / DESC NULLS LAST. Both are commutative.
202+
(
203+
"and: ASC NULLS LAST is preserved",
204+
SortProperties::and,
205+
ASC_NL,
206+
ASC_NL,
207+
ASC_NL,
208+
),
209+
(
210+
"and: DESC NULLS FIRST is preserved",
211+
SortProperties::and,
212+
DESC_NF,
213+
DESC_NF,
214+
DESC_NF,
215+
),
216+
(
217+
"and: ASC NULLS FIRST is unordered",
218+
SortProperties::and,
219+
ASC_NF,
220+
ASC_NF,
221+
UNORDERED,
222+
),
223+
(
224+
"and: DESC NULLS LAST is unordered",
225+
SortProperties::and,
226+
DESC_NL,
227+
DESC_NL,
228+
UNORDERED,
229+
),
230+
(
231+
"and: mixed directions are unordered",
232+
SortProperties::and,
233+
ASC_NL,
234+
DESC_NF,
235+
UNORDERED,
236+
),
237+
(
238+
"and: literal with ASC NULLS LAST",
239+
SortProperties::and,
240+
SINGLETON,
241+
ASC_NL,
242+
ASC_NL,
243+
),
244+
(
245+
"and: literal with ASC NULLS FIRST is unordered",
246+
SortProperties::and,
247+
SINGLETON,
248+
ASC_NF,
249+
UNORDERED,
250+
),
251+
(
252+
"and: two literals stay a literal",
253+
SortProperties::and,
254+
SINGLETON,
255+
SINGLETON,
256+
SINGLETON,
257+
),
193258
(
194-
"and_or: same direction is preserved",
195-
SortProperties::and_or,
259+
"or: ASC NULLS FIRST is preserved",
260+
SortProperties::or,
196261
ASC_NF,
197262
ASC_NF,
198263
ASC_NF,
199264
),
200265
(
201-
"and_or: nulls_last placement is preserved",
202-
SortProperties::and_or,
266+
"or: DESC NULLS LAST is preserved",
267+
SortProperties::or,
203268
DESC_NL,
204269
DESC_NL,
205270
DESC_NL,
206271
),
207272
(
208-
"and_or: opposing directions are unordered",
209-
SortProperties::and_or,
210-
ASC_NF,
273+
"or: ASC NULLS LAST is unordered",
274+
SortProperties::or,
275+
ASC_NL,
276+
ASC_NL,
277+
UNORDERED,
278+
),
279+
(
280+
"or: DESC NULLS FIRST is unordered",
281+
SortProperties::or,
211282
DESC_NF,
283+
DESC_NF,
284+
UNORDERED,
285+
),
286+
(
287+
"or: mixed directions are unordered",
288+
SortProperties::or,
289+
ASC_NF,
290+
DESC_NL,
212291
UNORDERED,
213292
),
214293
(
215-
"and_or: literal with ordered",
216-
SortProperties::and_or,
294+
"or: literal with ASC NULLS FIRST",
295+
SortProperties::or,
217296
SINGLETON,
218297
ASC_NF,
219298
ASC_NF,
220299
),
221300
(
222-
"and_or: two literals stay a literal",
223-
SortProperties::and_or,
301+
"or: literal with ASC NULLS LAST is unordered",
302+
SortProperties::or,
303+
SINGLETON,
304+
ASC_NL,
305+
UNORDERED,
306+
),
307+
(
308+
"or: two literals stay a literal",
309+
SortProperties::or,
224310
SINGLETON,
225311
SINGLETON,
226312
SINGLETON,
@@ -333,21 +419,29 @@ mod sort_properties_test {
333419
assert_eq!(op(&lhs, &rhs), expected, "case: {name}");
334420
}
335421

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)] {
422+
// `add`, `and` and `or` are commutative, so the table above covers
423+
// only one argument order.
424+
for (lhs, rhs) in [
425+
(ASC_NF, DESC_NL),
426+
(ASC_NF, SINGLETON),
427+
(ASC_NL, SINGLETON),
428+
(ASC_NL, DESC_NF),
429+
] {
339430
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");
431+
assert_eq!(lhs.and(&rhs), rhs.and(&lhs), "and is commutative");
432+
assert_eq!(lhs.or(&rhs), rhs.or(&lhs), "or is commutative");
341433
}
342434
}
343435

344436
/// If two ordered operands disagree on null placement, the result is
345437
/// always Unordered, no matter which operator or direction is used.
346438
/// Checked below for every combination.
347439
///
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`.
440+
/// Nulls propagate through the arithmetic and comparison operators: the
441+
/// result is null wherever either operand is null. `nulls_first` treats
442+
/// those rows as a prefix, `nulls_last` as a suffix. A set that's both
443+
/// can't be described by any `SortOptions`. `and`/`or` keep an ordering
444+
/// only when both operands already share it.
351445
///
352446
/// The assertion only checks "not Ordered", not which ordering
353447
/// results. That keeps the test from just repeating the logic it's
@@ -356,7 +450,8 @@ mod sort_properties_test {
356450
#[case::add("add", SortProperties::add)]
357451
#[case::sub("sub", SortProperties::sub)]
358452
#[case::gt_or_gteq("gt_or_gteq", SortProperties::gt_or_gteq)]
359-
#[case::and_or("and_or", SortProperties::and_or)]
453+
#[case::and("and", SortProperties::and)]
454+
#[case::or("or", SortProperties::or)]
360455
fn conflicting_null_placement_is_never_ordered(
361456
#[values(false, true)] l_descending: bool,
362457
#[values(false, true)] r_descending: bool,

‎datafusion/physical-expr/src/expressions/binary.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -878,13 +878,13 @@ impl PhysicalExpr for BinaryExpr {
878878
strictly_order_preserving: false,
879879
}),
880880
Operator::And => Ok(ExprProperties {
881-
sort_properties: r_order.and_or(&l_order),
881+
sort_properties: l_order.and(&r_order),
882882
range: l_range.and(r_range)?,
883883
preserves_lex_ordering: false,
884884
strictly_order_preserving: false,
885885
}),
886886
Operator::Or => Ok(ExprProperties {
887-
sort_properties: r_order.and_or(&l_order),
887+
sort_properties: l_order.or(&r_order),
888888
range: l_range.or(r_range)?,
889889
preserves_lex_ordering: false,
890890
strictly_order_preserving: false,

‎datafusion/sqllogictest/test_files/order.slt‎

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1591,6 +1591,77 @@ physical_plan
15911591
statement ok
15921592
DROP TABLE mixed_null_placement;
15931593

1594+
# ASC NULLS FIRST survives OR but not AND. The per-operator rules are
1595+
# unit-tested in sort_properties.rs; this checks the planner uses them.
1596+
query I
1597+
COPY (VALUES
1598+
(CAST(NULL AS BOOLEAN), false),
1599+
(CAST(NULL AS BOOLEAN), true),
1600+
(false, true),
1601+
(true, true))
1602+
TO 'test_files/scratch/order/kleene_nulls_first.csv'
1603+
OPTIONS ('format.has_header' 'true');
1604+
----
1605+
4
1606+
1607+
statement ok
1608+
CREATE EXTERNAL TABLE kleene_nulls_first (a BOOLEAN, b BOOLEAN)
1609+
STORED AS CSV
1610+
WITH ORDER (a ASC NULLS FIRST)
1611+
WITH ORDER (b ASC NULLS FIRST)
1612+
LOCATION 'test_files/scratch/order/kleene_nulls_first.csv'
1613+
OPTIONS ('format.has_header' 'true');
1614+
1615+
# a AND b is (false, NULL, false, true) in scan order, so it needs sorting.
1616+
query B
1617+
SELECT a AND b AS c FROM kleene_nulls_first ORDER BY c ASC NULLS FIRST;
1618+
----
1619+
NULL
1620+
false
1621+
false
1622+
true
1623+
1624+
# AND must not claim ASC NULLS FIRST.
1625+
query TT
1626+
EXPLAIN SELECT a AND b AS c FROM kleene_nulls_first ORDER BY c ASC NULLS FIRST;
1627+
----
1628+
logical_plan
1629+
01)Sort: c ASC NULLS FIRST
1630+
02)--Projection: kleene_nulls_first.a AND kleene_nulls_first.b AS c
1631+
03)----TableScan: kleene_nulls_first projection=[a, b]
1632+
physical_plan
1633+
01)SortPreservingMergeExec: [c@0 ASC]
1634+
02)--SortExec: expr=[c@0 ASC], preserve_partitioning=[true]
1635+
03)----ProjectionExec: expr=[a@0 AND b@1 as c]
1636+
04)------RepartitionExec: partitioning=RoundRobinBatch(2), input_partitions=1, maintains_sort_order=true
1637+
05)--------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/order/kleene_nulls_first.csv]]}, projection=[a, b], output_orderings=[[a@0 ASC], [b@1 ASC]], file_type=csv, has_header=true
1638+
1639+
# a OR b is (NULL, true, true, true) in scan order, already ASC NULLS FIRST,
1640+
# so no SortExec.
1641+
query B
1642+
SELECT a OR b AS c FROM kleene_nulls_first ORDER BY c ASC NULLS FIRST;
1643+
----
1644+
NULL
1645+
true
1646+
true
1647+
true
1648+
1649+
query TT
1650+
EXPLAIN SELECT a OR b AS c FROM kleene_nulls_first ORDER BY c ASC NULLS FIRST;
1651+
----
1652+
logical_plan
1653+
01)Sort: c ASC NULLS FIRST
1654+
02)--Projection: kleene_nulls_first.a OR kleene_nulls_first.b AS c
1655+
03)----TableScan: kleene_nulls_first projection=[a, b]
1656+
physical_plan
1657+
01)SortPreservingMergeExec: [c@0 ASC]
1658+
02)--ProjectionExec: expr=[a@0 OR b@1 as c]
1659+
03)----RepartitionExec: partitioning=RoundRobinBatch(2), input_partitions=1, maintains_sort_order=true
1660+
04)------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/order/kleene_nulls_first.csv]]}, projection=[a, b], output_orderings=[[a@0 ASC], [b@1 ASC]], file_type=csv, has_header=true
1661+
1662+
statement ok
1663+
DROP TABLE kleene_nulls_first;
1664+
15941665
# Union a query with the actual data and one with a constant
15951666
query I
15961667
SELECT (SELECT c from ordered_table ORDER BY c LIMIT 1) UNION ALL (SELECT 23 as c from ordered_table ORDER BY c LIMIT 1) ORDER BY c;

‎docs/source/library-user-guide/upgrading/55.0.0.md‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1372,6 +1372,28 @@ following the pattern in [`parquet/examples/object_store.rs`]
13721372

13731373
See [PR #24030](https://github.com/apache/datafusion/pull/24030) for details.
13741374

1375+
### `SortProperties::and_or` replaced by `and` and `or`
1376+
1377+
`datafusion_expr_common::sort_properties::SortProperties::and_or` has been
1378+
removed. Call `and` for `AND` and `or` for `OR`:
1379+
1380+
```rust,ignore
1381+
// Before (54.0.0)
1382+
let props = lhs.and_or(&rhs);
1383+
1384+
// After (55.0.0)
1385+
let props = lhs.and(&rhs); // for AND
1386+
let props = lhs.or(&rhs); // for OR
1387+
```
1388+
1389+
The two operators do not preserve the same sort orders. `AND` keeps an ordering
1390+
only when nulls sort after `true` (`ASC NULLS LAST` or `DESC NULLS FIRST`), and
1391+
`OR` only when nulls sort before `false` (`ASC NULLS FIRST` or
1392+
`DESC NULLS LAST`). `and_or` did not say which operator the caller meant, so it
1393+
could not be right for both.
1394+
1395+
See [PR #24276](https://github.com/apache/datafusion/pull/24276) for details.
1396+
13751397
[`parquet` crate]: https://crates.io/crates/parquet
13761398
[`parquetobjectreader`]: https://docs.rs/parquet/59.1.0/parquet/arrow/async_reader/struct.ParquetObjectReader.html
13771399
[`parquetobjectwriter`]: https://docs.rs/parquet/59.1.0/parquet/arrow/async_writer/struct.ParquetObjectWriter.html

0 commit comments

Comments
 (0)