Skip to content

[SQL] Compile SQL window ROWS queries to RANGE (ROW_NUMBER) #6613

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
mihaibudiu merged 1 commit into from
Jul 15, 2026
Merged

[SQL] Compile SQL window ROWS queries to RANGE (ROW_NUMBER) #6613

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
54 changes: 27 additions & 27 deletions docs.feldera.com/docs/sql/aggregates.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -221,33 +221,6 @@ The following window aggregate functions are supported:
</tr>
</table>

:::warning Potential inefficiency

@mihaibudiu mihaibudiu Jul 10, 2026

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This paragraph was moved down in the file


The window aggregate functions `RANK`, `DENSE_RANK`, and `ROW_NUMBER`
may be very expensive to evaluate incrementally, because it's possible
for a very small input change to produce a very large output change:
inserting or deleting a single row can change the numbering of all
subsequent rows in the same group. These functions can have a
reasonable cost in three circumstances:

- each modified group (created by `PARTITION BY`) is relatively small in size

- new insertions and deletions feature rows that appear towards the
end of the order produced by the `ORDER BY` clause

- they are used in a TopK pattern with a small limit.
The topK is expressed in SQL with the following structure:

```sql
SELECT * FROM (
SELECT empno,
row_number() OVER (ORDER BY empno) rn
FROM empsalary) emp
WHERE rn < 3
```

:::

## Pivots

The SQL `PIVOT` operation can be used to turn rows into columns. It
Expand Down Expand Up @@ -375,6 +348,33 @@ Window aggregation functions need to store the entire collection that
is being aggregated -- the space overhead is thus O(N). The work
performed is expected to be O(D log N).

The window aggregate functions `RANK`, `DENSE_RANK`, and `ROW_NUMBER`
may be very expensive to evaluate incrementally, because it's possible
for a very small input change to produce a very large output change:
inserting or deleting a single row can change the numbering of all
subsequent rows in the same group. These functions can have a
reasonable cost in three circumstances:

- each modified group (created by `PARTITION BY`) is relatively small in size

- new insertions and deletions feature rows that appear towards the
end of the order produced by the `ORDER BY` clause

- they are used in a TopK pattern with a small limit.
The topK is expressed in SQL with the following structure:

```sql
SELECT * FROM (
SELECT empno,
row_number() OVER (ORDER BY empno) rn
FROM empsalary) emp
WHERE rn < 3
```

Window aggregation functions involving `ROWS BETWEEN` are implemented
behind the scenes by computing `ROW_NUMBER` for each `PARTITION BY`
group, so they inherit the cost of `ROW_NUMBER` as described above.

### `DISTINCT`

The `DISTINCT` operation can be used with an aggregation or in a
Expand Down
14 changes: 5 additions & 9 deletions docs.feldera.com/docs/sql/unsupported-operations.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -22,9 +22,11 @@ The following aggregate functions are not supported:

### `FIRST_VALUE` and `LAST_VALUE` limited to unbounded range

`FIRST_VALUE()` and `LAST_VALUE()` are only supported for windows with
an unbounded range (e.g., `RANGE BETWEEN UNBOUNDED PRECEDING AND
CURRENT ROW`). Custom `RANGE` bounds or `ROWS` frames are not yet
`FIRST_VALUE()` and `LAST_VALUE()` are only supported for frames whose
bounds are `UNBOUNDED PRECEDING`, `CURRENT ROW`, or `UNBOUNDED
FOLLOWING` (with `RANGE` or `ROWS`): `FIRST_VALUE` requires the frame
to start at `UNBOUNDED PRECEDING`, and `LAST_VALUE` requires the frame
to end at `UNBOUNDED FOLLOWING`. Numeric bounds are not yet
supported.
See [#3918](https://github.com/feldera/feldera/issues/3918).

Expand All @@ -34,12 +36,6 @@ Window functions using `ORDER BY` on `VARCHAR`/`STRING`,
`DOUBLE`/`FLOAT` or `VARBINARY` columns are not yet supported.
See [#457](https://github.com/feldera/feldera/issues/457).

### `ROWS` frame type not supported

The `ROWS` frame specification in window functions is not yet
supported. Only `RANGE` frames are currently accepted. See
[#457](https://github.com/feldera/feldera/issues/457). This
limitation affects TPC-DS query q51.

### `EXCLUDE` clause not supported

Expand Down
1 change: 0 additions & 1 deletion python/tests/runtime_aggtest/lateness_tests/test_lateness_check.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -65,7 +65,6 @@ def __init__(self):
ts,
SUM(value) OVER (ORDER BY ts ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) AS rolling_sum
FROM purchase"""
self.expected_error = "Not yet implemented"


class lateness_interval_add(TstView):
Expand Down
2 changes: 2 additions & 0 deletions ...va/org/dbsp/sqlCompiler/compiler/frontend/calciteCompiler/optimizer/CalciteOptimizer.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -364,6 +364,8 @@ public String toString() {
// See discussion in https://issues.apache.org/jira/browse/CALCITE-6020
CoreRules.PROJECT_TO_LOGICAL_PROJECT_AND_WINDOW
));
this.addStep(new SimpleOptimizerStep("Window ROWS to RANGE", 0,
new RowsToRangeRule()));
this.addStep(new SimpleOptimizerStep("Isolate DISTINCT aggregates", 0,
CoreRules.AGGREGATE_EXPAND_DISTINCT_AGGREGATES_TO_JOIN,
CoreRules.AGGREGATE_EXPAND_DISTINCT_AGGREGATES
Expand Down
Loading