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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
