ORDER BY can return NULLs out of order across sorted Parquet files #26278

Describe the bug

When sorted Parquet files containing NULLs share one scan partition, DataFusion can incorrectly treat their combined rows as sorted and remove the sort. ORDER BY x ASC NULLS FIRST then returns [NULL, 1, NULL, 2] instead of [NULL, NULL, 1, 2].

To Reproduce

Reproduced with Python 3.11, datafusion==55.0.0, and pyarrow==24.0.0. The same failure was also reproduced through the Rust API on DataFusion main at 9551051f13ee321eb0d41bf437f3718a138e12a2.

Save this as repro.py and run:

uv run --no-project --python 3.11 --with datafusion==55.0.0 --with pyarrow==24.0.0 repro.py

import tempfile
from pathlib import Path

import pyarrow as pa
import pyarrow.parquet as pq
from datafusion import SessionConfig, SessionContext

with tempfile.TemporaryDirectory() as directory:
    for name, values in [("a", [None, 1]), ("b", [None, 2])]:
        pq.write_table(
            pa.table({"x": pa.array(values, type=pa.int64())}),
            Path(directory) / f"{name}.parquet",
            sorting_columns=[pq.SortingColumn(0, nulls_first=True)],
        )

    ctx = SessionContext(SessionConfig().with_target_partitions(1))
    ctx.register_parquet("t", directory)
    result = ctx.sql("SELECT x FROM t ORDER BY x ASC NULLS FIRST")
    result.explain()
    print([row["x"] for batch in result.collect() for row in batch.to_pylist()])

Actual result:

[None, 1, None, 2]

The physical plan has DataSourceExec with output_ordering=[x@0 ASC] and no SortExec.

Expected behavior

[None, None, 1, 2]

Each file is sorted on its own. Reading the two files in sequence does not preserve NULLS FIRST ordering.

Additional context

For these files, the stored non-NULL min/max values are 1/1 and 2/2, and each file has null_count=1. The file-boundary check in MinMaxStatistics::new_from_files uses the min/max values without including NULLs in the bounds.

I have prepared a small fix with a regression test.

Willingness to contribute

I plan to contribute a fix for this bug independently.