|
| 1 | +"""A sort by a rolling or running aggregate sorts (#354). |
| 2 | +
|
| 3 | +DataFusion 55 reads an aggregate's set monotonicity (`max`, `count` and |
| 4 | +unsigned `sum` only rise as values join the set, `min` only falls) as an |
| 5 | +ordering of the window column, and drops a later sort that ordering |
| 6 | +satisfies. The orderings it derives do not hold for LTSeq's windows: |
| 7 | +
|
| 8 | +- a sliding frame with no `partition_by` over a sorted argument is claimed |
| 9 | + ascending (descending for `min`) whichever way the argument is sorted, and |
| 10 | + a rolling `count` falls once NULLs enter the frame; |
| 11 | +- a running frame is claimed `ASC NULLS LAST`, but its value is NULL until |
| 12 | + the first non-NULL argument (apache/datafusion#27267); |
| 13 | +- an unsigned `sum` wraps on overflow. |
| 14 | +
|
| 15 | +So every window aggregate LTSeq builds claims no order, and these tests check |
| 16 | +the sorted rows against an oracle computed in Python, not only against the |
| 17 | +same rows sorted after `collect()`. |
| 18 | +""" |
| 19 | + |
| 20 | +from __future__ import annotations |
| 21 | + |
| 22 | +import datetime |
| 23 | +from collections import Counter |
| 24 | +from decimal import Decimal |
| 25 | + |
| 26 | +import pyarrow as pa |
| 27 | +import pytest |
| 28 | + |
| 29 | +from ltseq import LTSeq |
| 30 | + |
| 31 | +# Distinct values, so a sort by `x` fixes the table order. |
| 32 | +VALUES = { |
| 33 | + "int64": (pa.int64(), [5, -3, 7, 0, 2, -8, 4]), |
| 34 | + "uint64": (pa.uint64(), [5, 3, 7, 0, 2, 8, 4]), |
| 35 | + "float64": (pa.float64(), [0.5, -3.25, 7.0, 0.0, 2.5, -8.0, 4.0]), |
| 36 | + "decimal": ( |
| 37 | + pa.decimal128(10, 2), |
| 38 | + [Decimal(v) for v in ("5.10", "-3.25", "7.00", "0.00", "2.50", "-8.75", "4.05")], |
| 39 | + ), |
| 40 | + "string": (pa.string(), ["e", "c", "g", "a", "b", "h", "d"]), |
| 41 | + "date": ( |
| 42 | + pa.date32(), |
| 43 | + [datetime.date(2024, 1, d) for d in (5, 3, 7, 1, 2, 8, 4)], |
| 44 | + ), |
| 45 | +} |
| 46 | +NUMERIC = ("int64", "uint64", "float64", "decimal") |
| 47 | + |
| 48 | +# Which rows of VALUES are NULL. |
| 49 | +NULLS = { |
| 50 | + "no_nulls": set(), |
| 51 | + "one_null": {1}, |
| 52 | + "three_nulls": {0, 3, 5}, |
| 53 | + "all_null": set(range(7)), |
| 54 | +} |
| 55 | + |
| 56 | +# The table's order: by the argument either way, or by row id, which leaves |
| 57 | +# the argument (and its NULLs) unordered. |
| 58 | +ORDERS = { |
| 59 | + "x_asc": (("x", "i"), [False, False]), |
| 60 | + "x_desc": (("x", "i"), [True, False]), |
| 61 | + "row_id": (("i",), [False]), |
| 62 | +} |
| 63 | + |
| 64 | +# (id, frame width or None for a running frame, aggregate, argument types) |
| 65 | +WINDOWS = [ |
| 66 | + *[ |
| 67 | + (f"rolling({w}).{agg}", w, agg, types) |
| 68 | + for w in (2, 3) |
| 69 | + for agg, types in ( |
| 70 | + ("max", tuple(VALUES)), |
| 71 | + ("min", tuple(VALUES)), |
| 72 | + ("count", tuple(VALUES)), |
| 73 | + ("sum", NUMERIC), |
| 74 | + ) |
| 75 | + ], |
| 76 | + ("cum_max", None, "max", tuple(VALUES)), |
| 77 | + ("cum_min", None, "min", tuple(VALUES)), |
| 78 | + ("cum_sum", None, "sum", NUMERIC), |
| 79 | +] |
| 80 | + |
| 81 | + |
| 82 | +def derive_m(t, width, agg, partitioned): |
| 83 | + by = {"partition_by": "g"} if partitioned else {} |
| 84 | + if width is None: |
| 85 | + return t.derive(m=lambda r: getattr(r.x, f"cum_{agg}")(**by)) |
| 86 | + return t.derive(m=lambda r: getattr(r.x.rolling(width, **by), agg)()) |
| 87 | + |
| 88 | + |
| 89 | +def window_value(agg, frame): |
| 90 | + present = [v for v in frame if v is not None] |
| 91 | + if agg == "count": |
| 92 | + return len(present) |
| 93 | + if not present: |
| 94 | + return None |
| 95 | + return {"max": max, "min": min, "sum": sum}[agg](present) |
| 96 | + |
| 97 | + |
| 98 | +def in_sort_order(values, desc): |
| 99 | + """`values` where `sort` puts them: NULLs last ascending, first |
| 100 | + descending, which is what it asks DataFusion for.""" |
| 101 | + nulls = [v for v in values if v is None] |
| 102 | + present = sorted((v for v in values if v is not None), reverse=desc) |
| 103 | + return nulls + present if desc else present + nulls |
| 104 | + |
| 105 | + |
| 106 | +def oracle(rows, order, width, agg, partitioned): |
| 107 | + """The rows in table order (`ORDERS[order]`), each with its window |
| 108 | + value `m`, computed from the frame's values.""" |
| 109 | + if order == "row_id": |
| 110 | + ordered = sorted(rows, key=lambda r: r["i"]) |
| 111 | + else: |
| 112 | + desc = order == "x_desc" |
| 113 | + nulls = sorted((r for r in rows if r["x"] is None), key=lambda r: r["i"]) |
| 114 | + present = sorted( |
| 115 | + (r for r in rows if r["x"] is not None), key=lambda r: r["x"], reverse=desc |
| 116 | + ) |
| 117 | + ordered = nulls + present if desc else present + nulls |
| 118 | + seen: dict[object, list] = {} |
| 119 | + out = [] |
| 120 | + for row in ordered: |
| 121 | + part = seen.setdefault(row["g"] if partitioned else None, []) |
| 122 | + part.append(row["x"]) |
| 123 | + frame = part if width is None else part[-width:] |
| 124 | + out.append({**row, "m": window_value(agg, frame)}) |
| 125 | + return out |
| 126 | + |
| 127 | + |
| 128 | +def table_rows(type_name, nulls): |
| 129 | + arrow_type, values = VALUES[type_name] |
| 130 | + xs = [None if index in NULLS[nulls] else v for index, v in enumerate(values)] |
| 131 | + return [{"i": i, "g": i % 2, "x": x} for i, x in enumerate(xs)], pa.table( |
| 132 | + { |
| 133 | + "i": pa.array(range(len(xs)), pa.int64()), |
| 134 | + "g": pa.array([i % 2 for i in range(len(xs))], pa.int64()), |
| 135 | + "x": pa.array(xs, arrow_type), |
| 136 | + } |
| 137 | + ) |
| 138 | + |
| 139 | + |
| 140 | +def as_tuple(row): |
| 141 | + return (row["i"], row["g"], row["x"], row["m"]) |
| 142 | + |
| 143 | + |
| 144 | +def check_sorted(t, expected_rows, label): |
| 145 | + """`t.sort("m")` and `t.sort("m", desc=True)`, whole and through a |
| 146 | + TopK, against the oracle's rows.""" |
| 147 | + n = len(expected_rows) |
| 148 | + expected_counts = Counter(map(as_tuple, expected_rows)) |
| 149 | + for desc in (False, True): |
| 150 | + expected_ms = in_sort_order([r["m"] for r in expected_rows], desc) |
| 151 | + sorted_t = t.sort("m", desc=desc) |
| 152 | + got = sorted_t.to_dicts() |
| 153 | + assert [r["m"] for r in got] == expected_ms, f"{label} desc={desc}" |
| 154 | + assert Counter(map(as_tuple, got)) == expected_counts, f"{label} desc={desc}" |
| 155 | + # The differential cross-check the issue states its criteria in. |
| 156 | + collected = t.collect().sort("m", desc=desc).to_dicts() |
| 157 | + assert [r["m"] for r in collected] == expected_ms, f"{label} desc={desc} collected" |
| 158 | + top = sorted_t.slice(0, n - 1).to_dicts() |
| 159 | + assert [r["m"] for r in top] == expected_ms[: n - 1], f"{label} desc={desc} slice" |
| 160 | + assert not Counter(map(as_tuple, top)) - expected_counts, f"{label} desc={desc} slice" |
| 161 | + |
| 162 | + |
| 163 | +def window_cases(): |
| 164 | + for name, width, agg, types in WINDOWS: |
| 165 | + for type_name in types: |
| 166 | + yield pytest.param(width, agg, type_name, id=f"{name}-{type_name}") |
| 167 | + |
| 168 | + |
| 169 | +@pytest.mark.parametrize("width, agg, type_name", list(window_cases())) |
| 170 | +def test_sort_by_window_sorts(engine_config, width, agg, type_name): |
| 171 | + engine_config(target_partitions=2, batch_size=3) |
| 172 | + for nulls in NULLS: |
| 173 | + rows, arrow_rows = table_rows(type_name, nulls) |
| 174 | + for order, (keys, desc) in ORDERS.items(): |
| 175 | + for partitioned in (False, True): |
| 176 | + t = LTSeq.from_arrow(arrow_rows).sort(*keys, desc=desc) |
| 177 | + t = derive_m(t, width, agg, partitioned) |
| 178 | + expected = oracle(rows, order, width, agg, partitioned) |
| 179 | + label = f"{nulls} {order} partitioned={partitioned}" |
| 180 | + got = Counter(map(as_tuple, t.to_dicts())) |
| 181 | + assert got == Counter(map(as_tuple, expected)), label |
| 182 | + check_sorted(t, expected, label) |
| 183 | + |
| 184 | + |
| 185 | +# The issue's cases, and the running ones found with them, in every engine |
| 186 | +# and input layout. |
| 187 | +ISSUE_CASES = [ |
| 188 | + ("rolling(2).max int64 desc", pa.int64(), [3, 2, 1, 0], True, 2, "max"), |
| 189 | + ("rolling(2).max string desc", pa.string(), ["a", "b", "c"], True, 2, "max"), |
| 190 | + ("rolling(2).sum uint64 desc", pa.uint64(), [0, 1, 2, 3], True, 2, "sum"), |
| 191 | + ("rolling(2).count nulls asc", pa.int64(), [1, 2, None, None], False, 2, "count"), |
| 192 | + ("rolling(2).min int64 asc", pa.int64(), [0, 1, 2, 3], False, 2, "min"), |
| 193 | + ("cum_max leading NULL", pa.int64(), [None, 1, 2], True, None, "max"), |
| 194 | + ("cum_sum uint64 leading NULL", pa.uint64(), [None, 1, 2], True, None, "sum"), |
| 195 | +] |
| 196 | + |
| 197 | + |
| 198 | +@pytest.mark.parametrize("case", ISSUE_CASES, ids=[c[0] for c in ISSUE_CASES]) |
| 199 | +def test_issue_cases_in_every_layout(engine_layout, data_layout, case): |
| 200 | + name, arrow_type, xs, x_desc, width, agg = case |
| 201 | + arrow_rows = pa.table( |
| 202 | + { |
| 203 | + "i": pa.array(range(len(xs)), pa.int64()), |
| 204 | + "g": pa.array([0] * len(xs), pa.int64()), |
| 205 | + "x": pa.array(xs, arrow_type), |
| 206 | + } |
| 207 | + ) |
| 208 | + t = data_layout(arrow_rows) |
| 209 | + read_type = t.to_arrow().schema.field("x").type |
| 210 | + # Parquet strings come back as views (layouts.py); CSV infers int64 for |
| 211 | + # unsigned values, whose sum DataFusion never claimed ordered. |
| 212 | + as_written = read_type == arrow_type or ( |
| 213 | + read_type == pa.string_view() and arrow_type == pa.string() |
| 214 | + ) |
| 215 | + if not as_written: |
| 216 | + pytest.skip(f"this input layout reads x back as {read_type}") |
| 217 | + t = derive_m(t.sort("x", "i", desc=[x_desc, False]), width, agg, partitioned=False) |
| 218 | + rows = [{"i": i, "g": 0, "x": x} for i, x in enumerate(xs)] |
| 219 | + expected = oracle(rows, "x_desc" if x_desc else "x_asc", width, agg, partitioned=False) |
| 220 | + check_sorted(t, expected, name) |
| 221 | + |
| 222 | + |
| 223 | +def test_wrapped_cum_sum_sorts(): |
| 224 | + """An unsigned running sum wraps on overflow, so it is not monotonic.""" |
| 225 | + t = ( |
| 226 | + LTSeq.from_arrow(pa.table({"i": [0, 1], "x": pa.array([2**64 - 1, 1], pa.uint64())})) |
| 227 | + .sort("i") |
| 228 | + .derive(m=lambda r: r.x.cum_sum()) |
| 229 | + ) |
| 230 | + assert [r["m"] for r in t.sort("m").to_dicts()] == [0, 2**64 - 1] |
| 231 | + |
| 232 | + |
| 233 | +def test_table_cum_sum_sorts(): |
| 234 | + """`LTSeq.cum_sum` builds its window apart from `derive`.""" |
| 235 | + t = ( |
| 236 | + LTSeq.from_arrow(pa.table({"x": pa.array([None, 1, 2], pa.uint64())})) |
| 237 | + .sort("x", desc=True) |
| 238 | + .cum_sum("x") |
| 239 | + ) |
| 240 | + assert [r["x_cumsum"] for r in t.sort("x_cumsum").to_dicts()] == [2, 3, None] |
| 241 | + |
| 242 | + |
| 243 | +def test_head_tail_and_writers_read_the_sorted_order(tmp_path): |
| 244 | + t = ( |
| 245 | + LTSeq.from_dict({"x": [3, 2, 1, 0]}) |
| 246 | + .sort("x", desc=True) |
| 247 | + .derive(m=lambda r: r.x.rolling(2).max()) |
| 248 | + .sort("m") |
| 249 | + ) |
| 250 | + assert [r["m"] for r in t.head(2).to_dicts()] == [1, 2] |
| 251 | + assert [r["m"] for r in t.tail(2).to_dicts()] == [3, 3] |
| 252 | + path = tmp_path / "sorted.parquet" |
| 253 | + t.write_parquet(str(path)) |
| 254 | + assert [r["m"] for r in LTSeq.read_parquet(str(path)).to_dicts()] == [1, 2, 3, 3] |
| 255 | + csv_path = tmp_path / "sorted.csv" |
| 256 | + t.write_csv(str(csv_path)) |
| 257 | + assert [r["m"] for r in LTSeq.read_csv(str(csv_path)).to_dicts()] == [1, 2, 3, 3] |
| 258 | + |
| 259 | + |
| 260 | +def test_plan_keeps_the_sort(): |
| 261 | + """The physical plan sorts by the window column above the window.""" |
| 262 | + t = ( |
| 263 | + LTSeq.from_dict({"x": [3, 2, 1, 0]}) |
| 264 | + .sort("x", desc=True) |
| 265 | + .derive(m=lambda r: r.x.rolling(2).max()) |
| 266 | + ) |
| 267 | + physical = t.sort("m").explain_plan()[1] |
| 268 | + lines = physical.splitlines() |
| 269 | + window = next(i for i, line in enumerate(lines) if "BoundedWindowAggExec" in line) |
| 270 | + assert any( |
| 271 | + "SortExec" in line and "CURRENT ROW@" in line and "ASC NULLS LAST" in line |
| 272 | + for line in lines[:window] |
| 273 | + ), physical |
0 commit comments