Skip to content

Commit 6131a98

Browse files
authored
Resolve named windows referenced inside OVER (...) (apache#26400)
## Which issue does this PR close? - Closes apache#26364. ## Rationale for this change `OVER (w ROWS BETWEEN ...)` silently dropped the named window `w`. The planner only resolved `OVER w`; for a name inside the parentheses it ignored `WindowSpec::window_name`, so the window kept the frame but lost `w`'s `PARTITION BY` and `ORDER BY` and produced wrong results without an error. ## What changes are included in this PR? `match_window_definitions` now resolves a named window referenced inside `OVER (...)` the way the SQL standard and PostgreSQL do: - The window copies the referenced window's `PARTITION BY` and `ORDER BY`, and adds its own frame. - It may add an `ORDER BY` only when the referenced window has none. - It is an error to add a `PARTITION BY`, to override an existing `ORDER BY`, or to copy a window that has a frame. A window definition can also reference an earlier definition, such as `WINDOW w2 AS (w1 ROWS ...)`. Only earlier definitions can be referenced, so references cannot form a cycle. ## What is the testing strategy for this PR? New cases in `window.slt` cover inheriting with an added frame, adding an `ORDER BY`, a definition that references an earlier one, `OVER (w)`, and each error. All of them fail without the fix. ## Are there any user-facing changes? Queries that used `OVER (w ...)` now return correct results. Queries that relied on the old behavior to override `w`'s `PARTITION BY` or `ORDER BY` now get a planning error, as in PostgreSQL.
1 parent d6fee72 commit 6131a98

2 files changed

Lines changed: 289 additions & 47 deletions

File tree

‎datafusion/sql/src/select.rs‎

Lines changed: 138 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,8 @@ use arrow::datatypes::DataType;
3434
use datafusion_common::error::DataFusionErrorBuilder;
3535
use datafusion_common::tree_node::{TreeNode, TreeNodeRecursion};
3636
use datafusion_common::{
37-
Column, DFSchema, DFSchemaRef, HashMap, Result, not_impl_err, plan_err,
37+
Column, DFSchema, DFSchemaRef, DataFusionError, HashMap, Result, not_impl_err,
38+
plan_err,
3839
};
3940
use datafusion_common::{NullHandling, RecursionUnnestOption, UnnestOptions};
4041
use datafusion_expr::ExprSchemable;
@@ -55,9 +56,9 @@ use datafusion_expr::{
5556

5657
use indexmap::IndexMap;
5758
use sqlparser::ast::{
58-
Distinct, Expr as SQLExpr, GroupByExpr, NamedWindowExpr, OrderBy,
59-
SelectItemQualifiedWildcardKind, WildcardAdditionalOptions, WindowType,
60-
visit_expressions_mut,
59+
Distinct, Expr as SQLExpr, GroupByExpr, Ident, NamedWindowExpr, OrderBy, Query,
60+
SelectItemQualifiedWildcardKind, VisitMut, VisitorMut, WildcardAdditionalOptions,
61+
WindowSpec, WindowType,
6162
};
6263
use sqlparser::ast::{NamedWindowDefinition, Select, SelectItem, TableWithJoins};
6364

@@ -99,7 +100,7 @@ impl<S: ContextProvider> SqlToRel<'_, S> {
99100
pub(super) fn select_to_plan(
100101
&self,
101102
mut select: Select,
102-
query_order_by: Option<OrderBy>,
103+
mut query_order_by: Option<OrderBy>,
103104
planner_context: &mut PlannerContext,
104105
) -> Result<LogicalPlan> {
105106
// Check for unsupported syntax first
@@ -131,6 +132,8 @@ impl<S: ContextProvider> SqlToRel<'_, S> {
131132
// Handle named windows before processing the projection expression
132133
check_conflicting_windows(&select.named_window)?;
133134
self.match_window_definitions(&mut select.projection, &select.named_window)?;
135+
self.match_window_definitions(&mut select.qualify, &select.named_window)?;
136+
self.match_window_definitions(&mut query_order_by, &select.named_window)?;
134137

135138
// Process the SELECT expressions
136139
let select_exprs = self.prepare_select_exprs(
@@ -1420,58 +1423,146 @@ impl<S: ContextProvider> SqlToRel<'_, S> {
14201423
})
14211424
}
14221425

1423-
// If the projection is done over a named window, that window
1424-
// name must be defined. Otherwise, it gives an error.
1426+
/// Replaces every window that references a named window, as in `OVER w`
1427+
/// or `OVER (w ...)`, with the resolved window specification.
1428+
///
1429+
/// Subqueries are skipped: each resolves names against its own `WINDOW`
1430+
/// clause when it is planned.
14251431
fn match_window_definitions(
14261432
&self,
1427-
projection: &mut [SelectItem],
1433+
node: &mut impl VisitMut,
14281434
named_windows: &[NamedWindowDefinition],
14291435
) -> Result<()> {
14301436
let named_windows: Vec<(&NamedWindowDefinition, String)> = named_windows
14311437
.iter()
14321438
.map(|w| (w, self.ident_normalizer.normalize(w.0.clone())))
14331439
.collect();
1434-
for proj in projection.iter_mut() {
1435-
if let SelectItem::ExprWithAlias { expr, alias: _ }
1436-
| SelectItem::UnnamedExpr(expr) = proj
1437-
{
1438-
let mut err = None;
1439-
let _ = visit_expressions_mut(expr, |expr| {
1440-
if let SQLExpr::Function(f) = expr
1441-
&& let Some(WindowType::NamedWindow(ident)) = &f.over
1442-
{
1443-
let normalized_ident =
1444-
self.ident_normalizer.normalize(ident.clone());
1445-
for (
1446-
NamedWindowDefinition(_, window_expr),
1447-
normalized_window_ident,
1448-
) in named_windows.iter()
1449-
{
1450-
if normalized_ident.eq(normalized_window_ident) {
1451-
f.over = Some(match window_expr {
1452-
NamedWindowExpr::NamedWindow(ident) => {
1453-
WindowType::NamedWindow(ident.clone())
1454-
}
1455-
NamedWindowExpr::WindowSpec(spec) => {
1456-
WindowType::WindowSpec(spec.clone())
1457-
}
1458-
})
1459-
}
1460-
}
1461-
// All named windows must be defined with a WindowSpec.
1462-
if let Some(WindowType::NamedWindow(ident)) = &f.over {
1463-
err = Some(plan_err!("The window {ident} is not defined!"));
1464-
return ControlFlow::Break(());
1465-
}
1466-
}
1467-
ControlFlow::Continue(())
1468-
});
1469-
if let Some(err) = err {
1470-
return err;
1471-
}
1440+
let mut resolver = NamedWindowResolver {
1441+
planner: self,
1442+
named_windows: &named_windows,
1443+
query_depth: 0,
1444+
};
1445+
match node.visit(&mut resolver) {
1446+
ControlFlow::Break(e) => Err(e),
1447+
ControlFlow::Continue(()) => Ok(()),
1448+
}
1449+
}
1450+
1451+
/// Returns the window specification of the named window `ident`.
1452+
///
1453+
/// A window definition may only reference windows defined before it, so
1454+
/// references cannot form a cycle.
1455+
fn resolve_named_window(
1456+
&self,
1457+
ident: &Ident,
1458+
named_windows: &[(&NamedWindowDefinition, String)],
1459+
) -> Result<WindowSpec> {
1460+
let normalized_ident = self.ident_normalizer.normalize(ident.clone());
1461+
let Some(position) = named_windows
1462+
.iter()
1463+
.position(|(_, name)| *name == normalized_ident)
1464+
else {
1465+
return plan_err!("The window {ident} is not defined!");
1466+
};
1467+
let (NamedWindowDefinition(_, window_expr), _) = named_windows[position];
1468+
let earlier_windows = &named_windows[..position];
1469+
match window_expr {
1470+
NamedWindowExpr::NamedWindow(base) => {
1471+
self.resolve_named_window(base, earlier_windows)
1472+
}
1473+
NamedWindowExpr::WindowSpec(spec) => {
1474+
self.resolve_window_spec(spec, earlier_windows)
1475+
}
1476+
}
1477+
}
1478+
1479+
/// Resolves a window specification that may reference a named window, as
1480+
/// in `OVER (w ROWS BETWEEN 1 PRECEDING AND CURRENT ROW)`.
1481+
///
1482+
/// Following the SQL standard and PostgreSQL, the specification copies
1483+
/// the referenced window's `PARTITION BY` and `ORDER BY`, may add an
1484+
/// `ORDER BY` only when the referenced window has none, and may add a
1485+
/// frame only when the referenced window has none.
1486+
fn resolve_window_spec(
1487+
&self,
1488+
spec: &WindowSpec,
1489+
named_windows: &[(&NamedWindowDefinition, String)],
1490+
) -> Result<WindowSpec> {
1491+
let Some(base_name) = &spec.window_name else {
1492+
return Ok(spec.clone());
1493+
};
1494+
let base = self.resolve_named_window(base_name, named_windows)?;
1495+
if !spec.partition_by.is_empty() {
1496+
return plan_err!(
1497+
"Cannot override PARTITION BY clause of window {base_name}"
1498+
);
1499+
}
1500+
if !spec.order_by.is_empty() && !base.order_by.is_empty() {
1501+
return plan_err!("Cannot override ORDER BY clause of window {base_name}");
1502+
}
1503+
if base.window_frame.is_some() {
1504+
return plan_err!(
1505+
"Cannot copy window {base_name} because it has a frame clause"
1506+
);
1507+
}
1508+
let order_by = if spec.order_by.is_empty() {
1509+
base.order_by
1510+
} else {
1511+
spec.order_by.clone()
1512+
};
1513+
Ok(WindowSpec {
1514+
window_name: None,
1515+
partition_by: base.partition_by,
1516+
order_by,
1517+
window_frame: spec.window_frame.clone(),
1518+
})
1519+
}
1520+
}
1521+
1522+
/// Resolves named window references in the expressions of a single `SELECT`.
1523+
struct NamedWindowResolver<'a, 'b, S: ContextProvider> {
1524+
planner: &'a SqlToRel<'b, S>,
1525+
named_windows: &'a [(&'a NamedWindowDefinition, String)],
1526+
/// Number of subqueries enclosing the expression being visited.
1527+
query_depth: usize,
1528+
}
1529+
1530+
impl<S: ContextProvider> VisitorMut for NamedWindowResolver<'_, '_, S> {
1531+
type Break = DataFusionError;
1532+
1533+
fn pre_visit_query(&mut self, _query: &mut Query) -> ControlFlow<Self::Break> {
1534+
self.query_depth += 1;
1535+
ControlFlow::Continue(())
1536+
}
1537+
1538+
fn post_visit_query(&mut self, _query: &mut Query) -> ControlFlow<Self::Break> {
1539+
self.query_depth -= 1;
1540+
ControlFlow::Continue(())
1541+
}
1542+
1543+
fn post_visit_expr(&mut self, expr: &mut SQLExpr) -> ControlFlow<Self::Break> {
1544+
if self.query_depth > 0 {
1545+
return ControlFlow::Continue(());
1546+
}
1547+
let SQLExpr::Function(f) = expr else {
1548+
return ControlFlow::Continue(());
1549+
};
1550+
let resolved = match &f.over {
1551+
Some(WindowType::NamedWindow(ident)) => {
1552+
self.planner.resolve_named_window(ident, self.named_windows)
1553+
}
1554+
Some(WindowType::WindowSpec(spec)) if spec.window_name.is_some() => {
1555+
self.planner.resolve_window_spec(spec, self.named_windows)
1556+
}
1557+
_ => return ControlFlow::Continue(()),
1558+
};
1559+
match resolved {
1560+
Ok(spec) => {
1561+
f.over = Some(WindowType::WindowSpec(spec));
1562+
ControlFlow::Continue(())
14721563
}
1564+
Err(e) => ControlFlow::Break(e),
14731565
}
1474-
Ok(())
14751566
}
14761567
}
14771568

‎datafusion/sqllogictest/test_files/window.slt‎

Lines changed: 151 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3481,6 +3481,157 @@ SELECT
34813481
ORDER BY C3
34823482
LIMIT 5
34833483

3484+
# A window that references a named window inherits its PARTITION BY and ORDER BY
3485+
statement ok
3486+
CREATE TABLE named_window_prices(ticker VARCHAR, ts INT, price DOUBLE) AS VALUES
3487+
('BTC', 1, 100.0), ('BTC', 2, 105.0), ('BTC', 3, 102.0),
3488+
('DOGE', 1, 0.1), ('DOGE', 2, 0.2), ('DOGE', 3, 0.15);
3489+
3490+
# Adding a frame to a named window keeps its PARTITION BY and ORDER BY
3491+
query TIRRR
3492+
SELECT ticker, ts, price,
3493+
MAX(price) OVER (w ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS named_plus_frame,
3494+
MAX(price) OVER (PARTITION BY ticker ORDER BY ts ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS inline
3495+
FROM named_window_prices
3496+
WINDOW w AS (PARTITION BY ticker ORDER BY ts)
3497+
ORDER BY ticker, ts
3498+
----
3499+
BTC 1 100 100 100
3500+
BTC 2 105 105 105
3501+
BTC 3 102 105 105
3502+
DOGE 1 0.1 0.1 0.1
3503+
DOGE 2 0.2 0.2 0.2
3504+
DOGE 3 0.15 0.2 0.2
3505+
3506+
# Adding an ORDER BY to a named window that only partitions
3507+
query TII
3508+
SELECT ticker, ts,
3509+
ROW_NUMBER() OVER (w ORDER BY ts DESC) AS rn
3510+
FROM named_window_prices
3511+
WINDOW w AS (PARTITION BY ticker)
3512+
ORDER BY ticker, ts
3513+
----
3514+
BTC 1 3
3515+
BTC 2 2
3516+
BTC 3 1
3517+
DOGE 1 3
3518+
DOGE 2 2
3519+
DOGE 3 1
3520+
3521+
# A window definition can reference an earlier one
3522+
query TIR
3523+
SELECT ticker, ts,
3524+
SUM(price) OVER w2 AS running
3525+
FROM named_window_prices
3526+
WINDOW w1 AS (PARTITION BY ticker ORDER BY ts),
3527+
w2 AS (w1 ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
3528+
ORDER BY ticker, ts
3529+
----
3530+
BTC 1 100
3531+
BTC 2 205
3532+
BTC 3 307
3533+
DOGE 1 0.1
3534+
DOGE 2 0.3
3535+
DOGE 3 0.45
3536+
3537+
# Referencing a named window inside parentheses without adding anything
3538+
query TII
3539+
SELECT ticker, ts, ROW_NUMBER() OVER (w) AS rn
3540+
FROM named_window_prices
3541+
WINDOW w AS (PARTITION BY ticker ORDER BY ts)
3542+
ORDER BY ticker, ts
3543+
----
3544+
BTC 1 1
3545+
BTC 2 2
3546+
BTC 3 3
3547+
DOGE 1 1
3548+
DOGE 2 2
3549+
DOGE 3 3
3550+
3551+
statement error DataFusion error: Error during planning: The window w is not defined!
3552+
SELECT MAX(price) OVER (w ROWS BETWEEN 1 PRECEDING AND CURRENT ROW)
3553+
FROM named_window_prices
3554+
3555+
statement error DataFusion error: Error during planning: Cannot override PARTITION BY clause of window w
3556+
SELECT MAX(price) OVER (w PARTITION BY ts)
3557+
FROM named_window_prices
3558+
WINDOW w AS (ORDER BY ts)
3559+
3560+
statement error DataFusion error: Error during planning: Cannot override ORDER BY clause of window w
3561+
SELECT MAX(price) OVER (w ORDER BY price)
3562+
FROM named_window_prices
3563+
WINDOW w AS (PARTITION BY ticker ORDER BY ts)
3564+
3565+
statement error DataFusion error: Error during planning: Cannot copy window w because it has a frame clause
3566+
SELECT MAX(price) OVER (w ROWS BETWEEN 1 PRECEDING AND CURRENT ROW)
3567+
FROM named_window_prices
3568+
WINDOW w AS (PARTITION BY ticker ORDER BY ts ROWS UNBOUNDED PRECEDING)
3569+
3570+
# A window definition cannot reference a later one
3571+
statement error DataFusion error: Error during planning: The window w2 is not defined!
3572+
SELECT SUM(price) OVER w1
3573+
FROM named_window_prices
3574+
WINDOW w1 AS (w2 ROWS UNBOUNDED PRECEDING),
3575+
w2 AS (PARTITION BY ticker ORDER BY ts)
3576+
3577+
# Named windows are resolved in QUALIFY
3578+
query TIR
3579+
SELECT ticker, ts, price
3580+
FROM named_window_prices
3581+
QUALIFY MAX(price) OVER (w ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) = price
3582+
WINDOW w AS (PARTITION BY ticker ORDER BY ts)
3583+
ORDER BY ticker, ts
3584+
----
3585+
BTC 1 100
3586+
BTC 2 105
3587+
DOGE 1 0.1
3588+
DOGE 2 0.2
3589+
3590+
query TI
3591+
SELECT ticker, ts
3592+
FROM named_window_prices
3593+
QUALIFY ROW_NUMBER() OVER w = 1
3594+
WINDOW w AS (PARTITION BY ticker ORDER BY ts)
3595+
ORDER BY ticker
3596+
----
3597+
BTC 1
3598+
DOGE 1
3599+
3600+
# Named windows are resolved in ORDER BY
3601+
query TI
3602+
SELECT ticker, ts
3603+
FROM named_window_prices
3604+
WINDOW w AS (PARTITION BY ticker ORDER BY ts)
3605+
ORDER BY ROW_NUMBER() OVER (w ROWS UNBOUNDED PRECEDING) DESC, ticker
3606+
----
3607+
BTC 3
3608+
DOGE 3
3609+
BTC 2
3610+
DOGE 2
3611+
BTC 1
3612+
DOGE 1
3613+
3614+
# A subquery resolves window names against its own WINDOW clause
3615+
query I
3616+
SELECT (SELECT MAX(rn) FROM (
3617+
SELECT ROW_NUMBER() OVER (w ROWS UNBOUNDED PRECEDING) AS rn
3618+
FROM named_window_prices
3619+
WINDOW w AS (PARTITION BY ticker ORDER BY ts)))
3620+
FROM named_window_prices
3621+
WINDOW w AS (ORDER BY ts)
3622+
LIMIT 1
3623+
----
3624+
3
3625+
3626+
statement error DataFusion error: Error during planning: The window w is not defined!
3627+
SELECT (SELECT MAX(rn) FROM (
3628+
SELECT ROW_NUMBER() OVER w AS rn FROM named_window_prices))
3629+
FROM named_window_prices
3630+
WINDOW w AS (ORDER BY ts)
3631+
3632+
statement ok
3633+
DROP TABLE named_window_prices;
3634+
34843635
# Create a source where there is multiple orderings.
34853636
statement ok
34863637
CREATE EXTERNAL TABLE multiple_ordered_table (

0 commit comments

Comments
 (0)