Skip to content

Commit f1f0449

Browse files
authored
fix: Support RANGE window frames over binary ORDER BY keys (apache#24357)
## Which issue does this PR close? - Closes apache#24327. ## Rationale for this change A window function over a binary `ORDER BY` key fails even with no frame clause: ```sql SELECT x, COUNT(*) OVER (ORDER BY x) FROM (VALUES (arrow_cast('a', 'Binary')), (arrow_cast('b', 'Binary'))) t(x); Internal error: Cannot run range queries on datatype: Binary. ``` `ORDER BY` without a frame defaults to `RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`, and `extract_window_frame_target_type` had no arm for the binary types. `LargeBinary`, `BinaryView`, `FixedSizeBinary` and dictionary-wrapped binary are affected too. Those bounds only need to compare order key values, which binary supports just as `Utf8` does. A finite offset like `1 PRECEDING` is different: the bound is computed as `current_value - 1`, which needs arithmetic on the order key type. Binary has none, and neither do `Utf8`, `Boolean`, `List` and `Null` -- yet offset frames over `Utf8`, `Boolean` and `List` keys were accepted, and since 54.0.0 the failing arithmetic is swallowed by the overflow handling from apache#22140, silently collapsing the bound to the partition edge: ```sql SELECT x, COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW) FROM (VALUES ('a'), ('b'), ('c')) t(x) ORDER BY x; ``` returns the running count `1`, `2`, `3` -- a silently widened frame -- instead of an error. This PR rejects such frames at planning time instead, matching PostgreSQL. ## What changes are included in this PR? - Accept the binary types in `extract_window_frame_target_type`. The existing dictionary arm already recurses into the value type. - Reject finite RANGE offsets during planning when the target type has no arithmetic, meaning anything other than the numerics and `Interval`. The message follows PostgreSQL's `RANGE with offset PRECEDING/FOLLOWING is not supported for column type ...`. - Make `WindowFrame::free_range()` `pub`, so the check reuses the crate's existing notion of "bounds that are UNBOUNDED or CURRENT ROW". - Document the restriction in the window functions guide and the `55.0.0` upgrade guide. ## Are these changes tested? Yes, in `window.slt`: all four binary types plus dictionary-wrapped binary, ascending and descending, an aggregate and `RANK`, with duplicate values asserting peer semantics rather than positional counting. Planning errors for offsets over `Binary`, `Utf8`, `Boolean`, `List(Int64)` and `Null`, on the end bound as well as the start. Free range frames over `Utf8` and `Boolean` still return results, and `Decimal128` keeps its offsets. The full sqllogictest suite passes. ## Are there any user-facing changes? Yes, one **breaking SQL change**: `RANGE BETWEEN <offset> PRECEDING/FOLLOWING` over a `Utf8`, `Binary`, `Boolean`, `List` or `Null` `ORDER BY` key now fails at planning time with `RANGE with offset PRECEDING/FOLLOWING is not supported for ORDER BY type ...`. Over `Utf8`, `Boolean` and `List` keys this replaces the silently widened frames described above; over `Null` and binary keys such queries already failed at planning time, so only the error message changes. The `55.0.0` upgrade guide entry covers the per-type history and the migration paths: use a `ROWS` frame to count rows, or state `UNBOUNDED PRECEDING` / `UNBOUNDED FOLLOWING` explicitly to compare against the partition edge. In the other direction, binary order keys now work with free range frames, where they previously raised the internal error above. `WindowFrame::free_range()` going from private to `pub` is additive, so not a breaking Rust API change. --- AI usage: Created with Claude Code and Opus 5. I have reviewed the code and made modifications where it made sense. I have also tested this end to end in an internal project. --------- Signed-off-by: Fredrik Fornwall <[email protected]>
1 parent 615c30b commit f1f0449

6 files changed

Lines changed: 210 additions & 2 deletions

File tree

‎datafusion/expr/src/window_frame.rs‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -282,7 +282,13 @@ impl WindowFrame {
282282

283283
/// Returns whether the window frame is "free range"; i.e. its start/end
284284
/// bounds are UNBOUNDED or CURRENT ROW.
285-
fn free_range(&self) -> bool {
285+
///
286+
/// This inspects only the bounds, not the frame units, so it returns `true`
287+
/// for ROWS and GROUPS frames with such bounds as well. For RANGE frames,
288+
/// such bounds are located by comparing order key values, whereas a finite
289+
/// offset bound (e.g. `5 PRECEDING`) has to be computed arithmetically from
290+
/// the current row's order key value.
291+
pub fn free_range(&self) -> bool {
286292
(self.start_bound.is_unbounded()
287293
|| self.start_bound == WindowFrameBound::CurrentRow)
288294
&& (self.end_bound.is_unbounded()

‎datafusion/optimizer/src/analyzer/type_coercion.rs‎

Lines changed: 15 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1068,6 +1068,7 @@ fn coerce_frame_bound(
10681068
fn extract_window_frame_target_type(col_type: &DataType) -> Result<DataType> {
10691069
if col_type.is_numeric()
10701070
|| col_type.is_string()
1071+
|| col_type.is_binary()
10711072
|| col_type.is_null()
10721073
|| matches!(
10731074
col_type,
@@ -1102,7 +1103,20 @@ fn coerce_window_frame(
11021103
.map(|s| s.expr.get_type(schema))
11031104
.transpose()?;
11041105
if let Some(col_type) = current_types {
1105-
extract_window_frame_target_type(&col_type)?
1106+
let target_type = extract_window_frame_target_type(&col_type)?;
1107+
// A finite offset bound (e.g. `5 PRECEDING`) is computed as
1108+
// `current_value ± offset`, so it is only meaningful for target
1109+
// types that support arithmetic. Strings, binaries, booleans
1110+
// and lists are orderable -- which is all a free range frame
1111+
// needs -- but have no such arithmetic.
1112+
let supports_offset_arithmetic =
1113+
target_type.is_numeric() || is_interval(&target_type);
1114+
if !supports_offset_arithmetic && !window_frame.free_range() {
1115+
return plan_err!(
1116+
"RANGE with offset PRECEDING/FOLLOWING is not supported for ORDER BY type {target_type}"
1117+
);
1118+
}
1119+
target_type
11061120
} else {
11071121
return internal_err!("ORDER BY column cannot be empty");
11081122
}

‎datafusion/sqllogictest/test_files/window.slt‎

Lines changed: 140 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6874,3 +6874,143 @@ ORDER BY id
68746874
2 NULL 3 3 3 3
68756875
3 NULL NULL NULL NULL NULL
68766876
4 7 7 7 7 7
6877+
6878+
# RANGE window frame over a binary ORDER BY key. The default frame for an
6879+
# ORDER BY without an explicit frame is RANGE BETWEEN UNBOUNDED PRECEDING AND
6880+
# CURRENT ROW, which used to fail with
6881+
# "Internal error: Cannot run range queries on datatype: Binary".
6882+
# Binary is orderable, so peer/range comparison is well defined just like Utf8.
6883+
query ?I
6884+
SELECT x, COUNT(*) OVER (ORDER BY x)
6885+
FROM (VALUES (arrow_cast('a', 'Binary')),
6886+
(arrow_cast('b', 'Binary')),
6887+
(arrow_cast('b', 'Binary')),
6888+
(arrow_cast('c', 'Binary'))) t(x)
6889+
ORDER BY x
6890+
----
6891+
61 1
6892+
62 3
6893+
62 3
6894+
63 4
6895+
6896+
query ?I
6897+
SELECT x, COUNT(*) OVER (ORDER BY x DESC RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
6898+
FROM (VALUES (arrow_cast('a', 'LargeBinary')),
6899+
(arrow_cast('b', 'LargeBinary')),
6900+
(arrow_cast('b', 'LargeBinary'))) t(x)
6901+
ORDER BY x
6902+
----
6903+
61 3
6904+
62 2
6905+
62 2
6906+
6907+
query ?I
6908+
SELECT x, COUNT(*) OVER (ORDER BY x RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)
6909+
FROM (VALUES (arrow_cast('a', 'BinaryView')),
6910+
(arrow_cast('b', 'BinaryView')),
6911+
(arrow_cast('b', 'BinaryView'))) t(x)
6912+
ORDER BY x
6913+
----
6914+
61 3
6915+
62 2
6916+
62 2
6917+
6918+
query ?I
6919+
SELECT x, COUNT(*) OVER (ORDER BY x)
6920+
FROM (VALUES (arrow_cast(arrow_cast('a', 'Binary'), 'FixedSizeBinary(1)')),
6921+
(arrow_cast(arrow_cast('b', 'Binary'), 'FixedSizeBinary(1)'))) t(x)
6922+
ORDER BY x
6923+
----
6924+
61 1
6925+
62 2
6926+
6927+
# A binary ORDER BY key nested in a dictionary resolves through the same arm.
6928+
query ?I
6929+
SELECT x, COUNT(*) OVER (ORDER BY x)
6930+
FROM (VALUES (arrow_cast(arrow_cast('a', 'Binary'), 'Dictionary(Int32, Binary)')),
6931+
(arrow_cast(arrow_cast('b', 'Binary'), 'Dictionary(Int32, Binary)')),
6932+
(arrow_cast(arrow_cast('b', 'Binary'), 'Dictionary(Int32, Binary)'))) t(x)
6933+
ORDER BY x
6934+
----
6935+
61 1
6936+
62 3
6937+
62 3
6938+
6939+
# A non-aggregate window function over a binary ORDER BY key.
6940+
query ?I
6941+
SELECT x, RANK() OVER (ORDER BY x)
6942+
FROM (VALUES (arrow_cast('a', 'Binary')),
6943+
(arrow_cast('b', 'Binary')),
6944+
(arrow_cast('b', 'Binary'))) t(x)
6945+
ORDER BY x
6946+
----
6947+
61 1
6948+
62 2
6949+
62 2
6950+
6951+
# Unsupported RANGE ORDER BY types still propagate the type-coercion error.
6952+
query error DataFusion error: type_coercion\ncaused by\nInternal error: Cannot run range queries on datatype: Struct\("c0": Int64\)
6953+
SELECT COUNT(*) OVER (ORDER BY x)
6954+
FROM (VALUES (struct(1))) t(x)
6955+
6956+
# An order key only needs to be comparable for a free range frame, whose bounds
6957+
# are all UNBOUNDED or CURRENT ROW. A finite offset such as `1 PRECEDING` instead
6958+
# has to be computed as `current_value - 1`, so it additionally requires
6959+
# arithmetic on the order key type. Reject such frames during planning for every
6960+
# order key type that has no arithmetic, rather than silently widening the frame
6961+
# to the whole partition.
6962+
query error DataFusion error: type_coercion\ncaused by\nError during planning: RANGE with offset PRECEDING/FOLLOWING is not supported for ORDER BY type Binary
6963+
SELECT COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
6964+
FROM (VALUES (arrow_cast('a', 'Binary'))) t(x)
6965+
6966+
# Dictionary-wrapped binary is unwrapped before checking offset arithmetic.
6967+
query error DataFusion error: type_coercion\ncaused by\nError during planning: RANGE with offset PRECEDING/FOLLOWING is not supported for ORDER BY type Binary
6968+
SELECT COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
6969+
FROM (VALUES (arrow_cast(arrow_cast('a', 'Binary'), 'Dictionary(Int32, Binary)'))) t(x)
6970+
6971+
query error DataFusion error: type_coercion\ncaused by\nError during planning: RANGE with offset PRECEDING/FOLLOWING is not supported for ORDER BY type Utf8
6972+
SELECT COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
6973+
FROM (VALUES ('a')) t(x)
6974+
6975+
# The end bound is rejected on the same grounds as the start bound.
6976+
query error DataFusion error: type_coercion\ncaused by\nError during planning: RANGE with offset PRECEDING/FOLLOWING is not supported for ORDER BY type Boolean
6977+
SELECT COUNT(*) OVER (ORDER BY x RANGE BETWEEN CURRENT ROW AND 1 FOLLOWING)
6978+
FROM (VALUES (true)) t(x)
6979+
6980+
query error DataFusion error: type_coercion\ncaused by\nError during planning: RANGE with offset PRECEDING/FOLLOWING is not supported for ORDER BY type List\(Int64\)
6981+
SELECT COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
6982+
FROM (VALUES ([1,2])) t(x)
6983+
6984+
query error DataFusion error: type_coercion\ncaused by\nError during planning: RANGE with offset PRECEDING/FOLLOWING is not supported for ORDER BY type Null
6985+
SELECT COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
6986+
FROM (VALUES (NULL)) t(x)
6987+
6988+
# Numeric order keys keep their finite offsets, decimals included.
6989+
query RI
6990+
SELECT x, COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
6991+
FROM (VALUES (arrow_cast(1.5, 'Decimal128(10, 2)')),
6992+
(arrow_cast(2.0, 'Decimal128(10, 2)'))) t(x)
6993+
ORDER BY x
6994+
----
6995+
1.5 1
6996+
2 2
6997+
6998+
# Free range frames over those same types keep working, so the rejection above is
6999+
# narrowed to the offset form rather than to the order key type as a whole.
7000+
query TI
7001+
SELECT x, COUNT(*) OVER (ORDER BY x)
7002+
FROM (VALUES ('a'), ('b'), ('b')) t(x)
7003+
ORDER BY x
7004+
----
7005+
a 1
7006+
b 3
7007+
b 3
7008+
7009+
query BI
7010+
SELECT x, COUNT(*) OVER (ORDER BY x RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)
7011+
FROM (VALUES (false), (true), (true)) t(x)
7012+
ORDER BY x
7013+
----
7014+
false 3
7015+
true 2
7016+
true 2

‎dev/update_function_docs.sh‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -317,6 +317,8 @@ where **offset** is an non-negative integer.
317317
318318
RANGE and GROUPS modes require an ORDER BY clause (with RANGE the ORDER BY must specify exactly one column).
319319
320+
In RANGE mode an **offset** is measured in ORDER BY values rather than in rows, so the bound is computed by adding it to or subtracting it from the current row's ORDER BY value. That restricts `offset PRECEDING` and `offset FOLLOWING` to ORDER BY types supporting such arithmetic, namely the numeric, date, and timestamp types. Other orderable types, such as strings and binaries, can still be used with `UNBOUNDED PRECEDING`, `CURRENT ROW` and `UNBOUNDED FOLLOWING`, which are located by comparing ORDER BY values.
321+
320322
## Filter clause for aggregate window functions
321323
322324
Aggregate window functions support the SQL `FILTER (WHERE ...)` clause to include only rows that satisfy the predicate from the window frame in the aggregation.

‎docs/source/library-user-guide/upgrading/55.0.0.md‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1408,3 +1408,47 @@ let table_opts = TableParquetOptions::try_from(&proto_table_opts)?;
14081408
```
14091409

14101410
See [issue #24019](https://github.com/apache/datafusion/issues/24019) for details.
1411+
1412+
### RANGE window frames with offsets now reject ORDER BY types without arithmetic
1413+
1414+
A `RANGE` frame offset such as `1 PRECEDING` is measured in `ORDER BY` values
1415+
rather than in rows, so the frame bound is computed as `current_value - 1`. That
1416+
requires arithmetic on the `ORDER BY` type. For types that have no such
1417+
arithmetic -- `Utf8`, `Binary`, `Boolean`, `List` and `Null` -- such frames are
1418+
now rejected when the query is planned:
1419+
1420+
```sql
1421+
SELECT x, COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
1422+
FROM (VALUES ('a'), ('b'), ('c')) t(x)
1423+
ORDER BY x;
1424+
-- Error during planning: RANGE with offset PRECEDING/FOLLOWING is not supported for ORDER BY type Utf8
1425+
```
1426+
1427+
What this replaces depends on the `ORDER BY` type. Over `Utf8`, `Boolean` and
1428+
`List` keys such queries planned successfully, and in DataFusion 54 the failing
1429+
frame-bound arithmetic was silently treated as an overflow
1430+
([#22140](https://github.com/apache/datafusion/pull/22140)): the bound collapsed
1431+
to the partition edge, and the query returned results computed over that wrongly
1432+
widened frame instead of an offset window. DataFusion 53 and earlier failed
1433+
during execution with an arithmetic error. Rows whose order key value was `NULL`
1434+
never reached the arithmetic, so queries where every order key value was `NULL`
1435+
returned correct results throughout; those also now fail at planning. Over a
1436+
`Null`-typed key the offset itself failed to coerce, erroring at planning time
1437+
with `Cast error: Casting from Utf8 to Null not supported`, and binary keys were
1438+
rejected for every `RANGE` frame with the internal error quoted below -- for
1439+
those two, only the error message changes.
1440+
1441+
Such an `ORDER BY` type is still usable with the `UNBOUNDED PRECEDING`,
1442+
`CURRENT ROW` and `UNBOUNDED FOLLOWING` bounds, which are located by comparing
1443+
`ORDER BY` values rather than by computing them. Binary order keys additionally
1444+
gained support for those bounds in this release, having previously failed with
1445+
`Internal error: Cannot run range queries on datatype: Binary`.
1446+
1447+
**Who is affected:**
1448+
1449+
- Queries using `offset PRECEDING` or `offset FOLLOWING` in a `RANGE` frame over
1450+
a non-numeric, non-temporal `ORDER BY` key. To count rows rather than compare
1451+
values, use a `ROWS` frame; to include everything up to the partition edge,
1452+
use `UNBOUNDED PRECEDING` or `UNBOUNDED FOLLOWING`.
1453+
1454+
See [issue #24327](https://github.com/apache/datafusion/issues/24327) for details.

‎docs/source/user-guide/sql/window_functions.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -145,6 +145,8 @@ where **offset** is an non-negative integer.
145145

146146
RANGE and GROUPS modes require an ORDER BY clause (with RANGE the ORDER BY must specify exactly one column).
147147

148+
In RANGE mode an **offset** is measured in ORDER BY values rather than in rows, so the bound is computed by adding it to or subtracting it from the current row's ORDER BY value. That restricts `offset PRECEDING` and `offset FOLLOWING` to ORDER BY types supporting such arithmetic, namely the numeric, date, and timestamp types. Other orderable types, such as strings and binaries, can still be used with `UNBOUNDED PRECEDING`, `CURRENT ROW` and `UNBOUNDED FOLLOWING`, which are located by comparing ORDER BY values.
149+
148150
## Filter clause for aggregate window functions
149151

150152
Aggregate window functions support the SQL `FILTER (WHERE ...)` clause to include only rows that satisfy the predicate from the window frame in the aggregation.

0 commit comments

Comments
 (0)