You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "Nagato-Yuzuru (via GitHub)" <gi...@apache.org> on 2026/08/09 18:30:27 UTC
[I] SortProperties::and_or claims orderings that Kleene AND/OR do not preserve [datafusion]
Nagato-Yuzuru opened a new issue, #24208:
URL: https://github.com/apache/datafusion/issues/24208
### Describe the bug
See context https://github.com/apache/datafusion/issues/11596#issuecomment-5232788766
`SortProperties::and_or` propagates orderings as if NULL always propagated to the result, like it does for the arithmetic operators. It doesn't: `AND`/`OR` follow three-valued logic, where `NULL AND false = false` and
`NULL OR true = true`.
As a result the output can be unordered even when both inputs are sorted with *identical* sort options:
```text
a = [NULL, NULL, false, true] -- ASC NULLS FIRST
b = [false, true, true, true] -- ASC NULLS FIRST
a AND b = [false, NULL, false, true] -- not sorted under any SortOptions
```
### To Reproduce
Need to examine the code:
[`and_or` in sort_properties.rs](https://github.com/apache/datafusion/blob/main/datafusion/expr-common/src/sort_properties.rs).
The counterexample above falsifies the current logic for any operand pair with matching `SortOptions` other than `ASC NULLS LAST` / `DESC NULLS FIRST`.
The truth table in the linked comment reproduces with:
```sql
DataFusion CLI v54.1.0
> WITH v(x) AS (VALUES (true), (false), (NULL))
SELECT a.x, b.x, a.x AND b.x, a.x OR b.x
FROM v a, v b
ORDER BY 1 NULLS LAST, 2 NULLS LAST;
+-------+-------+-------------+------------+
| x | x | a.x AND b.x | a.x OR b.x |
+-------+-------+-------------+------------+
| false | false | false | false |
| false | true | false | true |
| false | NULL | false | NULL |
| true | false | false | true |
| true | true | true | true |
| true | NULL | NULL | true |
| NULL | false | false | NULL |
| NULL | true | NULL | true |
| NULL | NULL | NULL | NULL |
+-------+-------+-------------+------------+
9 row(s) fetched.
```
### Expected behavior
Kleene `AND` is `min` under the truth ordering `false < NULL < true`, so it is monotone w.r.t. that ordering. The sort options whose physical order realizes that ordering are exactly `ASC NULLS LAST` and its reverse `DESC NULLS FIRST`.
Therefore:
- `AND` preserves ordering iff both operands are sorted with the same options, and those options are `ASC NULLS LAST` or `DESC NULLS FIRST`.
- `OR` is the mirror image (`max` under `NULL < false < true`): `ASC NULLS FIRST` or `DESC NULLS LAST`.
- Everything else is `Unordered`, including the `(Ordered, Singleton)` arms: the literal can be `NULL` (`x AND NULL` breaks `ASC NULLS FIRST` the same way), and `SortProperties` doesn't know the literal's value.
The preserving options for `AND` and `OR` are disjoint, so the shared `and_or` method cannot be correct for both operators. It should be split into separate `and` / `or` methods and `and_or` deprecated.
This is an API change, which is why it is filed separately from #11596.
### Additional context
Found while working on #11596. The fix there only tightens `and_or`'s `nulls_first` check — strictly better than the current behavior, but still not sound for `AND`/`OR`: the counterexample above uses matching `nulls_first`.
Since the value domain is just `{false, true, NULL}` and an ordering violation always shows up between two rows, the proposed rule can be verified exhaustively over all two-row inputs, the test suite can prove the rule.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] SortProperties::and_or claims orderings that Kleene AND/OR do not preserve [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 closed issue #24208: SortProperties::and_or claims orderings that Kleene AND/OR do not preserve
URL: https://github.com/apache/datafusion/issues/24208
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] SortProperties::and_or claims orderings that Kleene AND/OR do not preserve [datafusion]
Posted by "Nagato-Yuzuru (via GitHub)" <gi...@apache.org>.
Nagato-Yuzuru commented on issue #24208:
URL: https://github.com/apache/datafusion/issues/24208#issuecomment-5233160738
take
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org