Propagation of ordered `SortProperties` should consider `nulls_first`

[jonahgao]

Describe the bug

For binary expressions or multi-input functions , if their args are ordered but the nulls_first option in SortOptions differs, they are still very likely to be unordered.

For example, as pointed out by @2010YOUY01 in #11571 (comment)

Looks like the following logic is not completely correct 🤔 e.g. base is DESC NULLS FIRST num is ASC NULLS LAST This implementation will return log(base, num) is ASC NULLS LAST But the actual output might look like

NULL
NULL
1
2
NULL

Which is unordered.

To Reproduce

Need to examine the code.

• The methods of SortProperties, such as add, sub, seem to not consider nulls_first.
• Similar to log.rs (should be fixed in PR 11571), the implementation of ScalarUDFImpl::output_ordering also needs to be reviewed.

Expected behavior

No response

Additional context

No response

[Nagato-Yuzuru]

take

[Nagato-Yuzuru]

I discovered and_or is also incorrect here. DataFusion's three-valued bool nulls_first consistency check is not sound.

NULL does not always propagate. null AND false = false.

DataFusion CLI v54.1.0
> WITH v(x) AS (VALUES (true), (false), (NULL))
SELECT a.x AS a,
       b.x AS b,
       a.x AND b.x AS and_,
       a.x OR  b.x AS or_
FROM v a, v b
ORDER BY 1 NULLS LAST, 2 NULLS LAST;
+-------+-------+-------+-------+
| a     | b     | and_  | or_   |
+-------+-------+-------+-------+
| 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.

Counterexample:
a = [null, null, false, true], b = [false, true, true, true], both ASC NULLS FIRST. a AND b = [false, null, false, true] not sorted.

Will fix in the same PR.

Update: fixing this properly requires an API change. AND and OR propagate orderings differently under three-valued logic.AND is monotone w.r.t. false < true < null (realized by ASC NULLS LAST / DESC NULLS FIRST), while OR is monotone w.r.t. NULL < false < true (ASC NULLS FIRST / DESC NULLS LAST)

So the shared SortProperties::and_or cannot be sound for both operators and needs to be split into separate and / or methods. To keep the fix for this issue free of API changes, I'll open a new issue for the and_or split.