Add a built-in UDAF approx_sum_topn based on space saving algorithm
- Lingua principale
- Rust
- Stelle
- 9.3k
- Fork
- 2.4k
- Merge medio
- 3g 11h
- PR unite (30g)
- 360
Descrizione
**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**
Guida per i contributori
Apri la guida per i contributori
Direzione di ricerca
Non vengono indicati file di implementazione o test. Inizia esaminando il supporto UDAF esistente di DataFusion e il paper proposto sull’algoritmo per il risparmio di spazio, quindi determina come APPROX_SUM_TOPN debba accettare chiavi raggruppate e restituire un array di structs. Il lavoro è completato quando una UDAF integrata produce al massimo top_k risultati approssimati per ogni gruppo, con le colonne di valore sommato e chiave richieste.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Valutazione
- Stack tecnologico
- rust, sql
- Ambito
- backend, data
- Tipo di issue
- Funzionalità
- Difficoltà
- 5/5
- Tempo stimato
- Più di una settimana
- Stato di attività
- Ferma
- Chiarezza
- Abbastanza chiara
- Idoneità per principianti
- 30/100