apache / apache/datafusion

Improved performance of RANGE window functions using Segment Trees

Open
#4,904 4 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
I am not sure this is an important feature to add, but I wanted to write it down.

Basically there is an interesting algorithm called `Segment Tree` which is described in :

> Efficient processing of window functions in analytical SQL queries
> by Viktor Leis, Kan Kundhikanjana, Alfons Kemper, Thomas Neumann

https://dl.acm.org/doi/10.14778/2794367.2794375

[p1058-leis.pdf](https://github.com/apache/arrow-datafusion/files/10417023/p1058-leis.pdf)

This algorithm handles window functions with `RANGE` window functions well, at least that is the claim. It might be a reasonable structure to implement instead of the "MovingMinMax" added in https://github.com/apache/arrow-datafusion/pull/4675 by @berkaycpp and @mustafasrepo .

**Describe the solution you'd like**

If we hit unacceptable performance of window functions (especially with largely varying `RANGE`), this might an algorithm worth looking into.

As a reminder a `RANGE` window frame is determined in terms of the values of the partition, not the number of rows:

```sql

❯ create table foo as values (1), (2), (3), (4), (5), (6), (6), (6);
0 rows in set. Query took 0.000 seconds.

❯ select column1, first_value(column1) OVER (ORDER BY column1 RANGE 3 PRECEDING) from foo;
+---------+--------------------------+
| column1 | FIRST_VALUE(foo.column1) |
+---------+--------------------------+
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
| 6 | 3 |
| 6 | 3 |
| 6 | 3 |
+---------+--------------------------+

❯ select column1, first_value(column1) OVER (ROWS 3 PRECEDING) from foo;
+---------+--------------------------+
| column1 | FIRST_VALUE(foo.column1) |
+---------+--------------------------+
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
| 6 | 3 |
| 6 | 4 |
| 6 | 5 |
+---------+--------------------------+
8 rows in set. Query took 0.001 seconds.
```

**Describe alternatives you've considered**
A clear and concise description of any alternative solutions or features you've considered.

**Additional context**
Add any other context or screenshots about the feature request here.

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the existing MovingMinMax approach from pull request #4675 and the linked paper on segment trees for analytical SQL window functions. Use the supplied RANGE-versus-ROWS examples and varying RANGE sizes to define benchmark cases; done should include evidence that the alternative improves RANGE window performance without changing results.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust, sql
Domain
database
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.