SortProperties::and_or claims orderings that Kleene AND/OR do not preserve

[Nagato-Yuzuru]

Describe the bug

See context #11596 (comment)

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 same sorted inputs can leave one operator's output sorted and break the other's.

Both inputs ASC NULLS FIRST:

a       = [NULL,  NULL, false, true]
b       = [false, true, true,  true]
a AND b = [false, NULL, false, true]   -- not sorted
a OR  b = [NULL,  true, true,  true]   -- sorted ASC NULLS FIRST

Both inputs ASC NULLS LAST:

a       = [false, false, NULL,  NULL]
b       = [false, false, false, true]
a AND b = [false, false, false, NULL]  -- sorted ASC NULLS LAST
a OR  b = [false, false, NULL,  true]  -- not sorted

Current and_or returns Ordered with the input options for all four results.

To Reproduce

DataFusion CLI v54.1.0
> set datafusion.execution.target_partitions = 1;

COPY (SELECT * FROM (VALUES
  (CAST(NULL AS BOOLEAN), false),
  (CAST(NULL AS BOOLEAN), true),
  (false,                 true),
  (true,                  true)
) AS t(a, b))
TO '/tmp/bool_nulls_first.csv' STORED AS CSV;

CREATE EXTERNAL TABLE demo_nf (a BOOLEAN, b BOOLEAN)
STORED AS CSV
WITH ORDER (a ASC NULLS FIRST)
WITH ORDER (b ASC NULLS FIRST)
LOCATION '/tmp/bool_nulls_first.csv'
OPTIONS ('format.has_header' 'true');

-- Both columns really do match their declared orderings.
SELECT * FROM demo_nf;

-- AND: ordering silently violated
SELECT a, b, a AND b AS c FROM demo_nf ORDER BY c ASC NULLS FIRST;

EXPLAIN SELECT a, b, a AND b AS c FROM demo_nf ORDER BY c ASC NULLS FIRST;

Get

+-------+-------+
| a     | b     |
+-------+-------+
| NULL  | false |
| NULL  | true  |
| false | true  |
| true  | true  |
+-------+-------+


+-------+-------+-------+
| a     | b     | c     |
+-------+-------+-------+
| NULL  | false | false |         <- false before NULL: NULLS FIRST silently violated
| NULL  | true  | NULL  |    
| false | true  | false |
| true  | true  | true  |
+-------+-------+-------+

+---------------+-------------------------------+
| plan_type     | plan                          |
+---------------+-------------------------------+
| physical_plan | ┌───────────────────────────┐ |
|               | │       DataSourceExec      │ |
|               | │    --------------------   │ |
|               | │          files: 1         │ |
|               | │        format: csv        │ |
|               | └───────────────────────────┘ |
|               |                               |
+---------------+-------------------------------+

The optimizer elides the sort

Expected behavior

Correct order.

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.

Run the exact same query on the exact same table with OR instead of AND:

> SELECT a, b, a OR b AS c FROM demo_nf ORDER BY c ASC NULLS FIRST;
+-------+-------+------+
| a     | b     | c    |
+-------+-------+------+
| NULL  | false | NULL |
| NULL  | true  | true |
| false | true  | true |
| true  | true  | true |
+-------+-------+------+

OR genuinely preserves ASC NULLS FIRST. And with ASC NULLS LAST inputs the roles swap exactly: OR breaks while AND preserves (mirror repro omitted for brevity).

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.

Additional context

This is an API change, which is why it is filed separately from #11596. The counterexample above uses matching nulls_first, so #24206's fix does not cover it.

[Nagato-Yuzuru]

take