apache / apache/datafusion

Add a built-in UDAF approx_sum_topn based on space saving algorithm

Open
#2,365 0 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.**

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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.