Add a built-in UDAF approx_sum_topn based on space saving algorithm
- 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.**
Suppose we want to get the top 5 _LO_SUPPKEY_ for each _LO_SHIPMODE_ based on _SUM(LO_EXTENDEDPRICE)_ in descending order, it can be achieved by the following SQL:
```
select LO_SHIPMODE,
collect(LO_SUPPKEY)
from
(select LO_SHIPMODE,
LO_SUPPKEY,
ROW_NUMBER() OVER (PARTITION BY LO_SHIPMODE
ORDER BY SUM_LO_EXTENDEDPRICE desc) as rank_num
from
(select LO_SHIPMODE,
LO_SUPPKEY,
SUM(LO_EXTENDEDPRICE) as SUM_LO_EXTENDEDPRICE
from LINEORDER
group by 1,
2) T0) T1
where rank_num <= 5
group by 1
```
However, if the cardinality of _LO_SUPPKEY_ may be extremely large, like billions, it will be very resource consuming to finish the inner most subquery
```
select LO_SHIPMODE,
LO_SUPPKEY,
SUM(LO_EXTENDEDPRICE) as SUM_LO_EXTENDEDPRICE
from LINEORDER
group by 1,
2
```
and the sort operation in the window function.
**Describe the solution you'd like**
It's would be better to provide a way to achieve an approximate topN result for each group. Therefore, we propose a UDAF to achieve this, like following:
```
select LO_SHIPMODE,
APPROX_SUM_TOPN(LO_EXTENDEDPRICE, [LO_SUPPKEY], 5) as SUM_LO_EXTENDEDPRICE
from LINEORDER
group by 1
```
where the parameters for the UDAF _APPROX_SUM_TOPN_ will like _(column_to_be_summed, [column1_to_be_topped, column2_to_be_topped, ...], top_k)_.
The result of this UDAF will be a nested structure. It's an array of struct, which contains at most _top_k_ structs of (column_to_be_summed, column1_to_be_topped, column2_to_be_topped, ...) which is calculated based on the space saving algorithm introduced in [paper](http://home.cse.ust.hk/~raywong/comp5331/References/EfficientComputationOfFrequentAndTop-kElementsInDataStreams.pdf)
**Describe alternatives you've considered**
**Additional context**
Contributor guide
Research direction
No implementation files or tests are named. Start by reviewing DataFusion's existing UDAF support and the proposed space-saving algorithm paper, then determine how APPROX_SUM_TOPN should accept grouped keys and return an array of structs. Done means a built-in UDAF produces at most top_k approximate results for each group with the requested summed value and key columns.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust, sql
- Domain
- backend, data
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100