xorq paging is not repeatable: window_to_parquet sorts on one key with no tie-breaker, and does not order at all when unsorted

[paddymul]

Problem

_window_to_parquet (buckaroo/xorq_buckaroo.py, lines 302-330 in 0.15.6) serves each scroll window as expr.limit(end - start, offset=start). With a sort it first applies expr.order_by(expr[sort_col].asc()), a single key. With no sort it applies no order_by at all.

Neither is repeatable. DataFusion runs the plan on parallel partitions, so an unordered LIMIT/OFFSET takes rows from whichever partition finishes first, and a sort on a key with ties (rows with equal values in the sort column) leaves the order among the tied rows to the merge. The same window request returns different rows on different calls.

import hashlib, io, tempfile
from pathlib import Path
import numpy as np, pyarrow as pa, pyarrow.parquet as pq
import xorq.api as xo
from buckaroo.xorq_buckaroo import window_to_parquet

N = 2_000_000
rng = np.random.default_rng(0)
table = pa.table({"row": np.arange(N), "g": rng.integers(0, 200, N), "v": rng.random(N)})
with tempfile.TemporaryDirectory() as tmp:
    path = Path(tmp) / "t.parquet"
    pq.write_table(table, path)  # 27 MB
    expr = xo.connect().read_parquet(str(path))

    def distinct(**kw):
        seen = set()
        for _ in range(6):
            got = pq.read_table(io.BytesIO(window_to_parquet(expr, 100_000, 100_050, **kw)))
            seen.add(hashlib.md5(got.to_pandas().to_csv().encode()).hexdigest())
        return len(seen)

    print(distinct())              # 5 distinct results in 6 identical calls
    print(distinct(sort_col="g"))  # 6 distinct results in 6 identical calls

The same request ordered by ["g", "row"] returns 1 distinct result in 6 calls.

Impact

Scrolling a grid over a parquet file larger than DataFusion's scan-split threshold (10,485,760 bytes in xorq-datafusion 0.2.7) repeats some rows and never shows others. Sorting by any column with duplicates, such as a category or a date, does the same at any file size where the plan is parallel. An author's own order_by inside the expression does not help, because the window is taken above it.

Suggested fix

Let the embedder name a row-order column, a column with no ties such as 0..N-1 in the file's row order. A row_order_column field on the /load_expr payload, and the same keyword on the xorq infinite widget, would cover both transports, since both drive window_to_parquet.

When it is given:

• no user sort: order_by(row_order_column);
• user sort: the user's key, then row_order_column ascending as the last key, so ties stay in row order whichever direction the user sorted;
• optionally, when there is no sort and no search filter and the embedder says the column is contiguous from 0 in physical order, fetch the window as row_order_column >= start AND row_order_column < end instead of OFFSET. Measured on a 287 MB file: 19-24 ms at any depth when the file has a parquet page index, against 100-374 ms for ORDER BY ... OFFSET, which reads and discards the skipped rows.

When it is not given, behaviour stays as it is, and the limitation is worth a line in the docs: a window over an expression with no total order is not repeatable.

Context

Identified while designing tallyman's row-order contract (buckaroo-data/tallyman#181, ADR-008), under which every file tallyman writes carries a __row_order column for this purpose. Measured on buckaroo 0.15.6, xorq 0.3.26, xorq-datafusion 0.2.7, 14 cores. Distinct from #923 (the cost of re-executing an aggregate per window) and #956 (the row cache key lacks a data version).