Zero-Cost NDV Estimation from Columnar File Metadata

Il documento presenta un metodo a costo zero per stimare il numero di valori distinti (NDV) nelle colonne dei file columnar, sfruttando esclusivamente i metadati esistenti senza richiedere ulteriore storage o accesso ai dati, combinando l'inversione dell'equazione di dimensione del dizionario con un modello del raccoglitore di coupon per adattarsi a diverse distribuzioni dei dati.

L'essenziale

Immagina di avere una biblioteca gigantesca piena di libri (i tuoi dati), ma hai solo il catalogo esterno (i metadati) e non puoi entrare nelle stanze per contare i libri uno per uno. Inoltre, non hai tempo di aprire i libri perché sei di fretta. Come fai a sapere quanti titoli diversi ci sono in totale?

Questo è il problema che risolve il paper di Claude Brisson. L'autore ha inventato un metodo "magico" per indovinare il numero di valori unici (chiamato NDV o Number of Distinct Values) in un file di dati, usando solo le informazioni già scritte sull'etichetta del file, senza mai toccare i dati veri e propri. È come stimare il numero di persone in una folla guardando solo le loro ombre proiettate sul muro, senza contare i volti.

Ecco come funziona, spiegato con due metafore semplici:

1. Il Trucco della "Valigia" (Inversione della Dimensione del Dizionario)

Immagina che ogni colonna di dati sia una valigia piena di oggetti. Se gli oggetti sono pochi e ripetitivi (come 100 magliette rosse e 100 blu), puoi usare un sistema intelligente: crei un "dizionario" con i nomi dei colori (Rosso, Blu) e poi, invece di scrivere "Rosso" ogni volta, scrivi solo il numero "1".

Il file ti dice: "Ehi, la mia valigia compressa pesa X chili".
Il metodo dell'autore fa un ragionamento inverso:

• "So quanto pesa la valigia (X chili)."
• "So quanto pesa mediamente un oggetto (la lunghezza media delle parole)."
• "So quanti oggetti ci sono in totale (il numero di righe)."

Usando una formula matematica (un po' come risolvere un'equazione di scuola superiore), l'autore "smonta" la valiglia mentalmente e dice: "Se pesa così tanto e gli oggetti sono così leggeri, allora devono esserci circa Y oggetti diversi nel dizionario".
Quando funziona bene: Quando gli oggetti sono distribuiti uniformemente in tutta la valigia.

2. Il Trucco del "Raccolto di Biglietti" (Min/Max e il Collezionista)

Ora immagina che la biblioteca sia divisa in 50 scaffali (i row groups). Su ogni scaffale, c'è un cartellino che dice: "Qui c'è il libro più piccolo (Min) e quello più grande (Max)".

Se i libri sono mischiati a caso, ogni scaffale avrà quasi lo stesso libro più piccolo e lo stesso più grande. Ma se i libri sono ordinati (es. dal 1 al 1000), il primo scaffale avrà il libro 1 e 20, il secondo il 21 e 40, e così via.

L'autore usa una teoria matematica chiamata "Problema del Collezionista di Biglietti".

• Se guardi i cartellini "Min" e "Max" di tutti gli scaffali, conti quanti valori diversi vedi.
• Se vedi molti valori diversi, significa che i dati sono ben distribuiti e puoi stimare il totale.
• Se vedi pochi valori diversi (perché gli scaffali si sovrappongono molto), il metodo dice: "Ok, questo metodo non è preciso qui, proviamo l'altro".

Quando funziona bene: Quando i dati sono ordinati o divisi in gruppi netti (come i libri ordinati per autore).

Il "Detective" Intelligente

Il vero genio di questo lavoro è il rilevatore di distribuzione. È come un detective che guarda i cartellini dei 50 scaffali e dice:

• "Oh, vedo che i valori minimi e massimi si sovrappongono molto? Allora i dati sono mischiati a caso. Usiamo il Trucco della Valigia."
• "Oh, vedo che i valori sono in ordine crescente e non si sovrappongono? Allora i dati sono ordinati. Usiamo il Trucco del Collezionista."

Alla fine, il sistema prende la stima migliore delle due e la controlla con dei limiti logici (ad esempio, non può esserci più di un certo numero di valori diversi rispetto al numero totale di righe).

Perché è importante?

Prima di questo metodo, per sapere quanti valori unici c'erano, i computer dovevano:

1. Leggere tutti i dati (lento e costoso).
2. Oppure, gli scrittori del file dovevano calcolare questo numero mentre scrivevano (richiedeva più tempo e spazio).

Con questo metodo, il computer guarda solo l'etichetta del file (i metadati), fa due calcoli rapidissimi e ha una stima con un errore spesso inferiore al 10%.

A cosa serve nella vita reale?
Immagina di dover organizzare una festa (una query di database) su un computer super veloce (GPU). Devi sapere quante persone ci saranno per preparare abbastanza sedie (memoria) e decidere chi serve cosa (ottimizzazione). Se sbagli il calcolo, la festa si blocca o sprechi soldi. Questo metodo permette di pianificare la festa guardando solo l'invito, senza dover chiamare tutti gli ospiti per confermare la presenza.

In sintesi: è un modo intelligente per indovinare la complessità di un dato guardando solo l'etichetta, risparmiando tempo, energia e memoria, rendendo i database molto più veloci ed efficienti.

Sommario tecnico

1. Il Problema

Nell'ambito dei motori di query distribuiti accelerati da GPU (come Theseus sviluppato da VoltronData), è fondamentale disporre di stime accurate del Numero di Valori Distinti (NDV) per una colonna al fine di ottimizzare i costi di esecuzione (es. ordinamento delle join, spinta degli aggregati, allocazione della memoria GPU).

Tuttavia, nei file colonnaari come Apache Parquet, il campo distinct_count è raramente popolato perché il calcolo esatto è costoso e spesso omesso dagli strumenti di scrittura. Le alternative tradizionali presentano svantaggi significativi:

• Campionamento: Richiede l'accesso ai dati, violando il principio della pianificazione basata solo sui metadati.
• Sketch (es. HyperLogLog): Richiedono infrastruttura lato scrittura o accesso ai dati.

L'obiettivo del paper è rispondere alla domanda: Quali informazioni sulla cardinalità sono già codificate implicitamente nei metadati esistenti dei file colonnaari, senza richiedere accesso ai dati o storage aggiuntivo?

2. Metodologia

L'autore propone un metodo che sfrutta due segnali complementari presenti nei metadati dei file Parquet (e generalizzabili ad altri formati come ORC e F3):

A. Inversione dell'Equazione di Dimensione del Dizionario

I file Parquet utilizzano la codifica a dizionario per colonne con cardinalità bassa-media. Ogni chunk di colonna espone una dimensione totale decompressa ($S$) nella sua metadati.
L'equazione che lega la dimensione allo storage è:
$$S = ndv \times len + (N - nulls) \times \lceil \log_2(ndv) \rceil / 8$$
Dove:

• $ndv$: numero di valori distinti (incognita).
• $len$: lunghezza media in byte dei valori.
• $N$: numero di righe.
• $nulls$: numero di valori nulli.

Il metodo risolve questa equazione per $ndv$ utilizzando il metodo di Newton-Raphson. Per stimare $len$ (non direttamente memorizzato), si calcola la media delle lunghezze dei valori minimi e massimi osservati nei diversi gruppi di righe.

• Validità: Funziona bene quando i valori distinti sono ben distribuiti ("well-spread") tra i gruppi di righe.
• Fallback: Se la cardinalità supera la soglia del dizionario, il sistema rileva il fallback alla codifica "plain" e tratta la stima come un limite inferiore.

B. Stima della Diversità Min/Max (Modello del Collezionista di Coupon)

Ogni gruppo di righe (row group) memorizza statistiche di minimo e massimo. Invece di usarle solo per il predicate pushdown, il paper le tratta come campioni impliciti della cardinalità globale.

• Si conta il numero di valori minimi distinti ($m_{min}$) e massimi distinti ($m_{max}$) tra tutti i gruppi di righe.
• Si applica il modello del collezionista di coupon per invertire la relazione tra il numero di campioni ($n$ gruppi di righe) e il numero di valori unici osservati, stimando la cardinalità totale ($NDV$).
• Validità: Questo approccio è robusto per dati ordinati o partizionati, dove i gruppi di righe coprono intervalli di valori distinti, evitando che i minimi/massimi si sovrappongano eccessivamente (situazione in cui l'inversione del dizionario fallirebbe).

C. Rilevamento della Distribuzione e Ibridazione

Poiché i due metodi hanno profili di accuratezza complementari (vedi Tabella 1 del paper), viene implementato un rilevatore di distribuzione leggero che analizza:

1. Sovrapposizione degli intervalli: Quanto si sovrappongono i range min/max tra gruppi di righe consecutivi.
2. Monotonicità: La progressione dei punti medi dei range.

In base a questi indicatori, il sistema classifica i dati come "Ben distribuiti", "Ordinati/Partizionati" o "Misti". La stima finale è il massimo tra le due stime ottenute, vincolato dai limiti superiori deterministici (es. range di valori per interi o date).

3. Contributi Chiave

1. Equazione chiusa per NDV: Una formula che lega la dimensione dello storage del dizionario alla cardinalità, risolta iterativamente.
2. Statistica Min/Max come Sketch: Il riconoscimento che le statistiche di minimo/massimo per gruppo di righe fungono da sketch di cardinalità impliciti, recuperabili tramite l'inversione del modello del collezionista di coupon.
3. Rilevatore di Distribuzione: Un meccanismo che instrada automaticamente tra i due stimatori in base alla struttura dei dati.
4. Predizione della Memoria per Batch: Utilizzo del modello del collezionista di coupon per prevedere la memoria necessaria per i dizionari nei batch GPU senza leggere i dati.

4. Risultati e Validazione

• Implementazione: La tecnica è stata implementata e validata su carichi di lavoro di produzione nel motore Theseus di VoltronData.
• Accuratezza: Per colonne ben distribuite, l'errore è tipicamente sotto il 10%. Per colonne ordinate, l'approccio ibrido corregge efficacemente la sottostima del metodo basato sul dizionario.
• Complessità: L'algoritmo è estremamente efficiente:
  • Tempo: $O(n)$ dove $n$ è il numero di gruppi di righe (singolo passaggio sui metadati).
  • Spazio: $O(1)$ (utilizzando sketch come HyperLogLog per contare i minimi/massimi distinti).
• Perdita dei Dati: L'autore nota che l'implementazione e i dati sperimentali dettagliati sono andati persi a seguito della liquidazione di VoltronData; il paper ricostruisce l'approccio dalla memoria.

5. Significato e Applicazioni

• Ottimizzazione Zero-Cost: Permette di ottenere stime di cardinalità affidabili senza accedere ai dati, abilitando ottimizzazioni basate sui costi (cost-based optimization) in ambienti dove l'accesso ai dati è costoso o lento (es. GPU, cloud storage).
• Generalizzabilità: Il metodo non è limitato a Parquet, ma si applica a qualsiasi formato colonnaare che supporti la codifica a dizionario e statistiche di partizione (es. ORC, F3).
• Impatto Pratico: Ha permesso di spingere gli aggregati sotto le join, riducendo il volume dei dati prima delle operazioni GPU, migliorando le prestazioni complessive del motore di query.

In sintesi, il paper dimostra che i metadati dei file colonnaari contengono informazioni sufficienti per stimare la cardinalità con alta precisione, trasformando statistiche progettate per l'eliminazione dei dati (predicate pushdown) in strumenti potenti per l'ottimizzazione delle query.