Skip to content

Commit d96eccb

Browse files
edubraqdclaude
edubraqd
and
claude
committed
review: reject list ORDER BY keys in the free RANGE fallback
The peer comparison and the sort disagree on element NULLs: compare_rows applies NULLS FIRST/LAST to the top-level value only and then goes through ScalarValue::partial_cmp, whose partial_cmp_list always orders a NULL element after a non-NULL one, while the sorter's make_comparator applies the option to the elements too. Rejecting lists in the fallback is simpler than reconciling the two. Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent 3c5ef2e commit d96eccb

2 files changed

Lines changed: 30 additions & 100 deletions

File tree

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

Lines changed: 18 additions & 79 deletions
Original file line numberDiff line numberDiff line change
@@ -1150,59 +1150,39 @@ fn supports_free_range_frame(col_type: &DataType) -> bool {
11501150
}
11511151
}
11521152

1153-
/// Whether `col_type` is a list whose elements the RANGE peer check cannot
1154-
/// compare. Such a key sorts fine, since the sorter uses `make_comparator`,
1155-
/// but the peer check goes through `ScalarValue::partial_cmp`, which compares
1156-
/// list elements with the arrow `lt`/`eq` kernels and fails at execution when
1157-
/// they reject the element type (see `list_element_comparable`).
1158-
fn is_list_of_uncomparable(col_type: &DataType) -> bool {
1153+
/// Whether `col_type` is a list, possibly behind dictionary or run-end
1154+
/// encoding.
1155+
///
1156+
/// Lists are kept out of the free-range fallback because their peer
1157+
/// comparison and the sort do not agree on element NULLs: `compare_rows`
1158+
/// applies the NULLS FIRST / NULLS LAST option to the top-level value only and
1159+
/// then calls `ScalarValue::partial_cmp`, whose `partial_cmp_list` always
1160+
/// orders a NULL element after a non-NULL one (Postgres semantics), while the
1161+
/// sorter's `make_comparator` applies the option to the elements as well. Under
1162+
/// `ORDER BY d, l NULLS FIRST` with tied `d`, the sort puts `[NULL]` before
1163+
/// `[1]` and the peer check orders them the other way round.
1164+
fn is_list_type(col_type: &DataType) -> bool {
11591165
match col_type {
1160-
DataType::List(field)
1161-
| DataType::LargeList(field)
1162-
| DataType::FixedSizeList(field, _) => {
1163-
!list_element_comparable(field.data_type())
1164-
}
1165-
DataType::Dictionary(_, value_type) => is_list_of_uncomparable(value_type),
1166-
DataType::RunEndEncoded(_, value_type) => {
1167-
is_list_of_uncomparable(value_type.data_type())
1166+
DataType::List(_) | DataType::LargeList(_) | DataType::FixedSizeList(_, _) => {
1167+
true
11681168
}
1169+
DataType::Dictionary(_, value_type) => is_list_type(value_type),
1170+
DataType::RunEndEncoded(_, value_type) => is_list_type(value_type.data_type()),
11691171
_ => false,
11701172
}
11711173
}
11721174

1173-
/// Mirrors what the arrow comparison kernels (`lt`, `eq`) accept: they unwrap
1174-
/// one run-end-encoded layer, then one dictionary layer, and compare what is
1175-
/// left only if it is a flat type. A nested element (`Struct`, `List`, ...) or a
1176-
/// second encoding layer (`Dictionary<Dictionary<..>>`, `Dictionary<REE<..>>`)
1177-
/// is rejected, even though `DataType::is_nested` sees through encodings.
1178-
fn list_element_comparable(elem_type: &DataType) -> bool {
1179-
let elem_type = match elem_type {
1180-
DataType::RunEndEncoded(_, value_type) => value_type.data_type(),
1181-
other => other,
1182-
};
1183-
let elem_type = match elem_type {
1184-
DataType::Dictionary(_, value_type) => value_type.as_ref(),
1185-
other => other,
1186-
};
1187-
!elem_type.is_nested()
1188-
&& !matches!(
1189-
elem_type,
1190-
DataType::Dictionary(_, _) | DataType::RunEndEncoded(_, _)
1191-
)
1192-
}
1193-
11941175
/// Errors if any ORDER BY expression has a type not supported in a free RANGE
11951176
/// frame: a type with neither an offset target nor a sound peer comparison, or
1196-
/// a list whose elements cannot be compared (see `is_list_of_uncomparable`).
1177+
/// a list (see `is_list_type`).
11971178
fn check_free_range_order_by_types(
11981179
expressions: &[Sort],
11991180
schema: &DFSchema,
12001181
) -> Result<()> {
12011182
for sort in expressions {
12021183
let t = sort.expr.get_type(schema)?;
12031184
let supported = supports_free_range_frame(&t)
1204-
|| (extract_window_frame_target_type(&t).is_some()
1205-
&& !is_list_of_uncomparable(&t));
1185+
|| (extract_window_frame_target_type(&t).is_some() && !is_list_type(&t));
12061186
if !supported {
12071187
return plan_err!(
12081188
"RANGE window frames are not supported for ORDER BY type {t}"
@@ -1683,47 +1663,6 @@ mod test {
16831663
}))
16841664
}
16851665

1686-
#[test]
1687-
fn free_range_list_element_comparable() {
1688-
use super::list_element_comparable;
1689-
use DataType::*;
1690-
let dict = |v: DataType| Dictionary(Box::new(Int32), Box::new(v));
1691-
let ree = |v: DataType| {
1692-
RunEndEncoded(
1693-
Arc::new(Field::new("run_ends", Int32, false)),
1694-
Arc::new(Field::new("values", v, true)),
1695-
)
1696-
};
1697-
let list = |v: DataType| List(Arc::new(Field::new_list_field(v, true)));
1698-
1699-
// flat elements, optionally behind one encoding layer, compare fine
1700-
for t in [
1701-
Int64,
1702-
Utf8,
1703-
Boolean,
1704-
Null,
1705-
Duration(TimeUnit::Second),
1706-
dict(Utf8),
1707-
ree(Utf8),
1708-
ree(dict(Utf8)),
1709-
] {
1710-
assert!(list_element_comparable(&t), "{t} should be comparable");
1711-
}
1712-
1713-
// nested elements and a second encoding layer are not: the arrow
1714-
// comparison kernels unwrap only one run-end and one dictionary layer
1715-
for t in [
1716-
Struct(vec![Field::new("c0", Int64, true)].into()),
1717-
list(Int64),
1718-
dict(list(Int64)),
1719-
dict(dict(Utf8)),
1720-
dict(ree(Utf8)),
1721-
ree(ree(Utf8)),
1722-
] {
1723-
assert!(!list_element_comparable(&t), "{t} should not be comparable");
1724-
}
1725-
}
1726-
17271666
macro_rules! assert_analyzed_plan_eq {
17281667
(
17291668
$plan: expr,

‎datafusion/sqllogictest/test_files/window.slt‎

Lines changed: 12 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -7155,31 +7155,22 @@ select count(*) over (order by l) from (values ([struct(1)]), ([struct(2)])) t(l
71557155
query error DataFusion error: Internal error: Uncomparable values: List\(\[\[1\]\]\), List\(\[\[1\]\]\)
71567156
select count(*) over (order by l) from (values ([[1]]), ([[2]])) t(l)
71577157

7158-
# after a duration key the free-range check looks at every ORDER BY type: a
7159-
# list of primitives is still fine,
7160-
query I
7161-
select count(*) over (order by d, l) from (values (arrow_cast(1, 'Duration(Second)'), [1]), (arrow_cast(1, 'Duration(Second)'), [2])) t(d, l)
7162-
----
7163-
1
7164-
2
7165-
7166-
# but a list of nested elements is rejected at planning, instead of reaching
7167-
# the execution error above
7158+
# after a duration key the free-range check looks at every ORDER BY type, and
7159+
# a list is rejected at planning even though it sorts fine: the RANGE peer
7160+
# check (`compare_rows`, then `ScalarValue::partial_cmp`) always orders a NULL
7161+
# list element after a non-NULL one, while the sort applies NULLS FIRST to the
7162+
# elements as well, so with tied durations `[NULL]` and `[1]` would be sorted
7163+
# one way and compared the other
71687164
query error Error during planning: RANGE window frames are not supported for ORDER BY type List
7169-
select count(*) over (order by d, l) from (values (arrow_cast(1, 'Duration(Second)'), [struct(1)]), (arrow_cast(1, 'Duration(Second)'), [struct(2)])) t(d, l)
7165+
select count(*) over (order by d, l nulls first) from (values (arrow_cast(1, 'Duration(Second)'), [NULL]), (arrow_cast(1, 'Duration(Second)'), [1])) t(d, l)
71707166

7171-
# the check mirrors the arrow comparison kernels, not `DataType::is_nested`:
7172-
# the kernels unwrap a single dictionary layer, so a list of doubly
7173-
# dictionary-encoded strings is also rejected at planning
7167+
# the check is on the type, not the values: a list without NULLs and a
7168+
# dictionary-encoded list are rejected the same way
71747169
query error Error during planning: RANGE window frames are not supported for ORDER BY type List
7175-
select count(*) over (order by d, l) from (values (arrow_cast(1, 'Duration(Second)'), [arrow_cast(arrow_cast('a', 'Dictionary(UInt32, Utf8)'), 'Dictionary(Int32, Dictionary(UInt32, Utf8))')])) t(d, l)
7170+
select count(*) over (order by d, l) from (values (arrow_cast(1, 'Duration(Second)'), [1]), (arrow_cast(1, 'Duration(Second)'), [2])) t(d, l)
71767171

7177-
# while a single dictionary layer compares fine
7178-
query I
7179-
select count(*) over (order by d, l) from (values (arrow_cast(1, 'Duration(Second)'), [arrow_cast('a', 'Dictionary(Int32, Utf8)')]), (arrow_cast(1, 'Duration(Second)'), [arrow_cast('b', 'Dictionary(Int32, Utf8)')])) t(d, l)
7180-
----
7181-
1
7182-
2
7172+
query error Error during planning: RANGE window frames are not supported for ORDER BY type Dictionary\(Int32, List
7173+
select count(*) over (order by d, l) from (values (arrow_cast(1, 'Duration(Second)'), arrow_cast([1], 'Dictionary(Int32, List(Int64))')), (arrow_cast(1, 'Duration(Second)'), arrow_cast([2], 'Dictionary(Int32, List(Int64))'))) t(d, l)
71837174

71847175
# Window functions are not allowed in WHERE or HAVING: both are evaluated before
71857176
# window functions are computed, so they are rejected during planning

0 commit comments

Comments
 (0)