Skip to content

Commit 269431e

Browse files
authored
Make window aggregates claim no output order (#354) (#391)
DataFusion 55 turns an aggregate's set monotonicity into an ordering of the window column and drops a later sort that ordering satisfies. For the windows LTSeq builds the derived orderings are wrong: a sliding frame with no partition_by is claimed ascending whichever way its argument is sorted (rolling max over a descending column, rolling count once NULLs enter the frame, rolling unsigned sum), a running max or unsigned sum is claimed ASC NULLS LAST although it is NULL until the first non-NULL value (apache/datafusion#27267), and an unsigned sum wraps on overflow. A sort by such a column came back in the window's order, with no error. aggregate_to_window, which builds every window aggregate LTSeq plans, now wraps the aggregate in NoOrderClaim: the same aggregate in every respect (name, types, accumulators, statistics, rewrites) except that its set monotonicity is NotMonotonic. DataFusion 55 reads set monotonicity only for window orderings, so grouped and ungrouped aggregates are unchanged. The cost is the sort a cum_max or cum_min of a column without NULLs made unnecessary.
1 parent bc2cbb2 commit 269431e

5 files changed

Lines changed: 543 additions & 1 deletion

File tree

‎CHANGELOG.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -87,6 +87,7 @@ Literal values in lambdas are typed (#145). They used to be sent to the engine a
8787
- `partition()` gives each key the rows whose key columns equal it, for every key type (#258). It fetched a partition by writing the key into a SQL `WHERE` clause, so a `date` key read as integer arithmetic (`"k" = 2024-01-03` is 2024 − 1 − 3) and every date partition was empty, also for the dates `read_csv` infers; timestamp, binary, NaN, `time` and `duration` keys, among others, raised `KeyError`, and `map()` raised `RuntimeError` for them. A partition now compares its key as a value of the key column's own type. An aware key is looked up by its instant: the two occurrences of a repeated hour, which Python compares as equal, are two keys, each found by the value `keys()` lists and by its UTC `datetime`, and `map()` keeps both, where it kept one. NaN is one key that any NaN finds and that holds every NaN row, whatever its bits, also on Parquet; `distinct` keeps NaNs of other bits apart (#290), so `keys()` used to list one NaN per bit pattern. Distinct keys that convert to one Python value, such as `time64[ns]` values less than a microsecond apart, which are one `datetime.time`, raise `ValueError` when the keys are first used: `keys()` could list only one of them. `map()` of a `map()` result no longer raises `AttributeError`.
8888
- `derive()` evaluates a `lookup()` only when it is a derived column's whole expression and is called on a column, and its result has no columns but the input's and the derived ones (#223). An expression built on a lookup returned the bare looked-up value without an error: `r.pid.lookup(products, "name") == "ten"`, `.is_null()`, `* r.qty` and `fill_null()` gave the name or the price, and a lookup on a computed key, such as `r.code.s.lower().lookup(...)`, matched the column under it. These raise `ValueError` at the `derive()` call; derive the looked-up value, or the key, as a column of its own and use it in a later `derive()`. Every lookup also added each target column under an internal name, `_lkp_products_name` for a table read from `products.csv` and `_lkp_lookup_table_<id>_name`, which changed between runs, for any other; the result no longer has them. An input column with one of those names made the lookup fail, and a derived column with one came before the columns derived ahead of it; the internal names now differ from every input and derived column. Each lookup now reads its own table on its own key: a second lookup into the same table on another key read the first key's matches, and two tables read from files of the same name, such as `a/products.csv` and `b/products.csv`, were one target, so both lookups read the second. A target read from a file whose name has an uppercase letter or a dot, such as `Products.csv`, no longer fails, and a lookup of a column the target lacks raises `ColumnNotFoundError` naming that column, not an internal one.
8989
- Float `min` and `max` follow the contract's order on every path (#253): every NaN, whatever its sign bit, is greater than `+inf`, and `-0.0` equals `0.0`, so `max` is NaN when a NaN takes part and `min` is NaN only when every value is. This holds in `agg`, `group_by`, `pivot`, `min_if`/`max_if`, `group_ordered` (`agg`, `derive`, `filter`), `rolling(...).min()`/`.max()` and `cum_min`/`cum_max`. DataFusion gave three answers. Grouped, the NaN replaced the running value and the next value replaced the NaN, so the grouped `min` of `[1.0, NaN, 2.0]` was `2.0`, and the grouped `max` of `[-inf, -inf]` was `-1.797e308`. Ungrouped and in windows, a NaN with the sign bit set, which `inf - inf` and `0.0 / 0.0` give on x86-64, was below `-inf`. Ungrouped over Parquet, the answer came from the file's statistics, which leave NaN out; a float `min` or `max` now reads the rows, while `count` and the `min`/`max` of other types are still answered from statistics. The scan for an ungrouped `min` or `max` of any type also reads every row now, where it skipped files and rows that could not beat the value found so far: DataFusion compared floats there in its own order, so it skipped `0.0` after `-0.0` and a sign-bit NaN after `2.0`. When the values equal to the result differ in representation, the result is `0.0` for the zeros and `float("nan")` for the NaNs; otherwise it keeps their bits.
90+
- A sort by a `rolling(...)`, `cum_max`, `cum_min` or `cum_sum` column sorts (#354). DataFusion took the window column as already sorted, from the aggregate's claim that its value only rises (`max`, `count`, unsigned `sum`) or only falls (`min`), and dropped the sort, so the rows came back in the window's order, through `slice`, `head`, `tail` and the writers too, with no error. With no `partition_by`, a rolling `max` over a descending column, a rolling `count` once NULLs enter the frame and a rolling unsigned `sum` over a descending column fall: `sort("m")` of the rolling(2) `max` over `x` = `[3, 2, 1, 0]` sorted descending gave `[3, 3, 2, 1]`, now `[1, 2, 3, 3]`. A running `max` or unsigned `sum` is NULL until the column's first non-NULL value, so `sort("m")` put those NULL rows first instead of last (apache/datafusion#27267), and an unsigned running `sum` that wraps past `2**64 - 1` falls. Window aggregates now claim no order, so a sort by a window column always runs; the cost is the sort that a `cum_max` or `cum_min` of a column without NULLs made unnecessary.
9091
- Filters and reads of a Parquet float column keep its NaN rows (#291, #355). Parquet writers leave NaN out of a float column's min and max, and DataFusion read them as bounds on every value. A scan skipped the files, row groups and pages whose min and max a predicate could not match, although their NaN rows matched it: over `[1.0, nan, 2.0, nan]`, `x > 2.0` and `x == float("nan")` kept no rows, and `count()`, `head`, `search_first` and `assume_sorted` lost them the same way; over a directory, `sort("x", desc=True).head(2)` could skip the file holding a NaN. A file in which a float column held one value apart from NaN, with no NULL, read every NaN as that value: `[20.0, nan, 20.0]` read as three `20.0`, also in joins and aggregates over it. A bloom filter, which hashes a value's bits, skipped a row group whose zero had the other sign from the one compared: `x == r.z` on a derived `z = -0.0` lost the rows where `x` is `0.0`. A Parquet scan now reads no min or max for a `float16`, `float32` or `float64` column, from file statistics, row-group statistics or the page index, and no bloom filter, so nothing prunes by those columns and their values come from the file. Other columns prune as before, and `count()` and the `min`/`max` of other types are still answered from statistics. A filter on a float column now reads every file, row group and page that the filter's other conditions keep.
9192
- A table from `read_csv` or `read_parquet` reads the files its reader found at the call, each as it is when the table executes (#262). A file deleted after the call read as no rows in a single-file table, and a Parquet directory table answered `count()`, and for some files `to_arrow()`, from the deleted file's old statistics. The next execution now raises, naming the file, with the error each terminal raises for a failed read: `ValueError` from most, `RuntimeError` from `collect()` and `write_parquet()`. A directory created at a listed file's name raises the same way; a single-file table read the files in it. A Parquet directory table read a file rewritten after the call by its old size and footer, which gave the old row count, dropped rows that a filter pruned by the old statistics, or failed with a corrupt-page error; it now reads the new contents. A file added to the directory after the call is still not read. Each execution of a directory table now looks up each of its files, about one `stat` call per file. Each execution of a Parquet table also reads every file's footer again (#359). DataFusion reused a footer, and the statistics in it, while the file's size and modification time were unchanged, so a rewrite that kept both, within the filesystem's timestamp resolution, was read by the old footer: `count()` gave the old row count, and a filter dropped the rows the old statistics pruned. The partitions of one execution share the footer it read. A table executed again and again pays one footer read per file per execution: in a release build, `count()` over 1,000 two-row files took 23 ms instead of 12, over 10,000 such files 345 ms instead of about 110, and over one file with a 1.1 MB footer 7 ms instead of 1.
9293
- Column names with uppercase letters or dots work in `join` (every `how`; `on=`, `left_on=`/`right_on=`, a lambda and `strategy="merge"`), `link`, `semi_join`, `anti_join`, `intersect`, `except_`, `xunion`, `is_subset`, `lookup`, `align`, `pivot`, `search_pattern`, `search_pattern_count` and the `partition_by=` of `shift`, `diff`, `rolling` and `cum_sum`/`cum_max`/`cum_min` (#322). They named columns by strings that DataFusion reads as SQL identifiers, so `Date` was looked up as `date` and `a.b` as column `b` of a table `a`, and they failed during execution with a schema error; a `link` alias with an uppercase letter (`as_="Prod"`) failed the same way. A window's `partition_by="TXT"` on a table with a column `txt` partitioned by `txt`; names are case-sensitive, so it now raises. `rename` handles a name that holds a `"`.
Lines changed: 273 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,273 @@
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

‎src/transpiler/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,7 @@ mod literal_policy;
2727
mod literals;
2828
pub(crate) mod min_max;
2929
pub(crate) mod narrow_decimals;
30+
mod no_order_claim;
3031
mod opaque_cast;
3132
pub(crate) mod probe;
3233
mod resolve;

0 commit comments

Comments
 (0)