Skip to content

Commit ce39143

Browse files
committed
fix: Support RANGE window frames over binary ORDER BY keys
Closes apache#24327. A window with an `ORDER BY` over a binary column and no explicit frame gets the default `RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`. Computing that frame's bounds goes through `extract_window_frame_target_type`, which had no arm for the binary types, so any window function whose leading `ORDER BY` key was `Binary`/`LargeBinary`/`BinaryView`/`FixedSizeBinary` failed with: Internal error: Cannot run range queries on datatype: Binary Binary is orderable, so peer/range comparison is well defined for it in exactly the same way it already is for `Utf8`. Accept the binary types alongside the string types. A finite RANGE offset such as `1 PRECEDING` asks for more than ordering: the bound is computed as `current_value - 1`, so the order key type must also support arithmetic. Binary does not, and neither do the `Utf8`, `Boolean`, `List` and `Null` order keys that `extract_window_frame_target_type` already accepted. For those, `ScalarValue::sub_checked` failed during execution and the error was swallowed by the overflow handling from apache#22140, which collapses a failed bound to the partition edge. So SELECT COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW) FROM (VALUES ('a'), ('b'), ('c')) t(x) silently returned the running count 1, 2, 3 -- the whole partition -- rather than an error. Reject the offset form during planning for every target type that has no arithmetic. For the string, boolean, list and null order keys this turns a wrong result into a plan error, which matches PostgreSQL's "RANGE with offset PRECEDING/FOLLOWING is not supported for column type ...". `WindowFrame::free_range()` becomes public so that check can be expressed in the vocabulary the crate already uses for "bounds that need no arithmetic". Document the restriction in the window functions user guide, and the changed SQL behavior in the 55.0.0 upgrade guide. Signed-off-by: Fredrik Fornwall <[email protected]>
1 parent bbb552f commit ce39143

5 files changed

Lines changed: 185 additions & 1 deletion

File tree

‎datafusion/expr/src/window_frame.rs‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -282,7 +282,11 @@ 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+
/// Such bounds are located by comparing order key values, whereas a finite
287+
/// offset bound (e.g. `5 PRECEDING`) has to be computed arithmetically from
288+
/// the current row's order key value.
289+
pub fn free_range(&self) -> bool {
286290
(self.start_bound.is_unbounded()
287291
|| self.start_bound == WindowFrameBound::CurrentRow)
288292
&& (self.end_bound.is_unbounded()

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

Lines changed: 14 additions & 0 deletions
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,
@@ -1109,6 +1110,19 @@ fn coerce_window_frame(
11091110
}
11101111
WindowFrameUnits::Rows | WindowFrameUnits::Groups => DataType::UInt64,
11111112
};
1113+
1114+
// A finite offset bound (e.g. `5 PRECEDING`) is computed as
1115+
// `current_value ± offset`, so it is only meaningful for target types that
1116+
// support arithmetic. Strings, binaries, booleans and lists are orderable --
1117+
// which is all a free range frame needs -- but have no such arithmetic.
1118+
let supports_offset_arithmetic =
1119+
target_type.is_numeric() || matches!(target_type, DataType::Interval(_));
1120+
if !supports_offset_arithmetic && !window_frame.free_range() {
1121+
return plan_err!(
1122+
"RANGE frames with finite offsets are not supported for ORDER BY type {target_type}"
1123+
);
1124+
}
1125+
11121126
window_frame.start_bound =
11131127
coerce_frame_bound(&target_type, window_frame.start_bound)?;
11141128
window_frame.end_bound = coerce_frame_bound(&target_type, window_frame.end_bound)?;

‎datafusion/sqllogictest/test_files/window.slt‎

Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6874,3 +6874,133 @@ 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+
# An order key only needs to be comparable for a free range frame, whose bounds
6952+
# are all UNBOUNDED or CURRENT ROW. A finite offset such as `1 PRECEDING` instead
6953+
# has to be computed as `current_value - 1`, so it additionally requires
6954+
# arithmetic on the order key type. Reject such frames during planning for every
6955+
# order key type that has no arithmetic, rather than silently widening the frame
6956+
# to the whole partition.
6957+
query error DataFusion error: type_coercion\ncaused by\nError during planning: RANGE frames with finite offsets are not supported for ORDER BY type Binary
6958+
SELECT COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
6959+
FROM (VALUES (arrow_cast('a', 'Binary'))) t(x)
6960+
6961+
query error DataFusion error: type_coercion\ncaused by\nError during planning: RANGE frames with finite offsets are not supported for ORDER BY type Utf8
6962+
SELECT COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
6963+
FROM (VALUES ('a')) t(x)
6964+
6965+
# The end bound is rejected on the same grounds as the start bound.
6966+
query error DataFusion error: type_coercion\ncaused by\nError during planning: RANGE frames with finite offsets are not supported for ORDER BY type Boolean
6967+
SELECT COUNT(*) OVER (ORDER BY x RANGE BETWEEN CURRENT ROW AND 1 FOLLOWING)
6968+
FROM (VALUES (true)) t(x)
6969+
6970+
query error DataFusion error: type_coercion\ncaused by\nError during planning: RANGE frames with finite offsets are not supported for ORDER BY type List\(Int64\)
6971+
SELECT COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
6972+
FROM (VALUES ([1,2])) t(x)
6973+
6974+
query error DataFusion error: type_coercion\ncaused by\nError during planning: RANGE frames with finite offsets are not supported for ORDER BY type Null
6975+
SELECT COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
6976+
FROM (VALUES (NULL)) t(x)
6977+
6978+
# Numeric order keys keep their finite offsets, decimals included.
6979+
query RI
6980+
SELECT x, COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
6981+
FROM (VALUES (arrow_cast(1.5, 'Decimal128(10, 2)')),
6982+
(arrow_cast(2.0, 'Decimal128(10, 2)'))) t(x)
6983+
ORDER BY x
6984+
----
6985+
1.5 1
6986+
2 2
6987+
6988+
# Free range frames over those same types keep working, so the rejection above is
6989+
# narrowed to the offset form rather than to the order key type as a whole.
6990+
query TI
6991+
SELECT x, COUNT(*) OVER (ORDER BY x)
6992+
FROM (VALUES ('a'), ('b'), ('b')) t(x)
6993+
ORDER BY x
6994+
----
6995+
a 1
6996+
b 3
6997+
b 3
6998+
6999+
query BI
7000+
SELECT x, COUNT(*) OVER (ORDER BY x RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)
7001+
FROM (VALUES (false), (true), (true)) t(x)
7002+
ORDER BY x
7003+
----
7004+
false 3
7005+
true 2
7006+
true 2

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

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1291,3 +1291,37 @@ let table_opts = TableParquetOptions::try_from(&proto_table_opts)?;
12911291
```
12921292

12931293
See [issue #24019](https://github.com/apache/datafusion/issues/24019) for details.
1294+
1295+
### RANGE window frames with offsets now reject ORDER BY types without arithmetic
1296+
1297+
A `RANGE` frame offset such as `1 PRECEDING` is measured in `ORDER BY` values
1298+
rather than in rows, so the frame bound is computed as `current_value - 1`. That
1299+
requires arithmetic on the `ORDER BY` type. Previously, for types that have no
1300+
such arithmetic -- `Utf8`, `Binary`, `Boolean`, `List` and `Null` -- the failure
1301+
was swallowed and the bound collapsed to the edge of the partition. For example:
1302+
1303+
```sql
1304+
SELECT x, COUNT(*) OVER (ORDER BY x RANGE BETWEEN 1 PRECEDING AND CURRENT ROW)
1305+
FROM (VALUES ('a'), ('b'), ('c')) t(x)
1306+
ORDER BY x;
1307+
```
1308+
1309+
Previously, this query returned the running counts `1`, `2`, `3`, as if the frame
1310+
had been `RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`. It now returns a
1311+
planning error stating that RANGE frames with finite offsets are not supported
1312+
for the `ORDER BY` type.
1313+
1314+
Such an `ORDER BY` type is still usable with the `UNBOUNDED PRECEDING`,
1315+
`CURRENT ROW` and `UNBOUNDED FOLLOWING` bounds, which are located by comparing
1316+
`ORDER BY` values rather than by computing them. Binary order keys additionally
1317+
gained support for those bounds in this release, having previously failed with
1318+
`Internal error: Cannot run range queries on datatype: Binary`.
1319+
1320+
**Who is affected:**
1321+
1322+
- Queries using `offset PRECEDING` or `offset FOLLOWING` in a `RANGE` frame over
1323+
a non-numeric, non-temporal `ORDER BY` key. To count rows rather than compare
1324+
values, use a `ROWS` frame; to keep the previous results, state the collapsed
1325+
bound explicitly as `UNBOUNDED PRECEDING` or `UNBOUNDED FOLLOWING`.
1326+
1327+
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 and the date/time 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)