apache / apache/datafusion

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

Aperta
#2,365 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub
enhancement
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

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.