Zero-Cost NDV Estimation from Columnar File Metadata

Each language version is independently generated for its own context, not a direct translation.

🕵️‍♂️ Le Détective du "Zéro Coût" : Deviner l'Invisible

Imaginez que vous êtes dans une immense bibliothèque (une base de données) remplie de milliers de livres (des fichiers de données). Votre mission est de savoir combien de mots différents il y a dans un chapitre spécifique, sans avoir à ouvrir un seul livre, sans lire une seule page, et sans dépenser de temps ni d'énergie. C'est ce que les chercheurs appellent estimer le NDV (Nombre de Valeurs Distinctes).

Habituellement, pour savoir combien de mots différents il y a, il faut lire tout le texte. C'est lent et coûteux. Mais ce papier propose une astuce de génie : deviner le nombre de mots en regardant simplement l'étiquette sur la couverture du livre.

📦 L'Analogie des Boîtes de Jouets

Pour comprendre la méthode, imaginons que les données sont stockées dans des boîtes (les "Row Groups" ou groupes de lignes). Chaque boîte contient des jouets (les données).

Le papier utilise deux indices cachés sur les étiquettes de ces boîtes pour faire son calcul :

1. L'Indice de la Taille de la Boîte (L'Inversion du Dictionnaire)

Le concept : Imaginez que dans une boîte, on a rangé des jouets en utilisant un code. Au lieu d'écrire "Voiture", "Voiture", "Voiture", "Avion", on écrit "1, 1, 1, 2". On a un petit dictionnaire à côté qui dit : "1 = Voiture", "2 = Avion".
L'astuce : Si vous connaissez la taille totale de la boîte (l'espace occupé par le dictionnaire + les codes) et la taille moyenne d'un jouet, vous pouvez faire un calcul à l'envers pour deviner combien de types de jouets différents (le dictionnaire) il y a.
Quand ça marche : C'est très précis si les jouets sont bien mélangés dans toutes les boîtes. C'est comme si chaque boîte contenait un peu de tout.
Le problème : Si les jouets sont triés (toutes les voitures dans la boîte 1, tous les avions dans la boîte 2), cette méthode se trompe. Elle pensera qu'il n'y a que deux types de jouets au total, alors qu'il y en a peut-être des milliers.

2. L'Indice des Extrêmes (Le Collectionneur de Timbres)

Le concept : Regardons maintenant les étiquettes qui disent "Le jouet le plus petit ici" et "Le jouet le plus grand ici" pour chaque boîte.
L'astuce : Si vous avez 50 boîtes et que vous voyez 45 valeurs "min" et "max" différentes, cela vous donne une idée de la diversité globale. Les chercheurs utilisent une vieille théorie mathématique appelée le problème du collectionneur de timbres.
- L'image : Imaginez que vous collectionnez des timbres. Si vous ouvrez 50 enveloppes (les boîtes) et que vous trouvez 45 timbres différents, vous pouvez estimer qu'il y a probablement beaucoup plus de timbres dans le monde entier, mais pas infini.
Quand ça marche : Cette méthode est excellente quand les données sont triées ou séparées par catégories (comme dans notre exemple des voitures et des avions). Elle voit la diversité des extrêmes là où la première méthode échouait.

🧠 Le Chef d'Orchestre (Le Détecteur de Distribution)

Le vrai génie du papier, c'est qu'ils ne choisissent pas au hasard. Ils ont créé un petit détecteur automatique (un chef d'orchestre) qui regarde comment les boîtes sont organisées :

Si les boîtes se chevauchent beaucoup (les mêmes types de jouets sont partout) ➡️ Il utilise la méthode de la taille.
Si les boîtes sont très différentes les unes des autres (chaque boîte a son propre univers) ➡️ Il utilise la méthode des extrêmes.

Ensuite, il prend le résultat le plus élevé des deux méthodes. Pourquoi ? Parce que dans ce jeu de devinette, il vaut mieux surestimer un peu que de sous-estimer gravement.

🚀 À quoi ça sert ? (Pourquoi se donner la peine ?)

Pourquoi faire tout cela sans lire les données ?

Économiser de l'argent et du temps : Dans les ordinateurs modernes (surtout ceux qui utilisent des puces graphiques/GPU pour aller vite), il faut savoir combien de mémoire réserver pour un calcul. Si on se trompe, le calcul plante ou est trop lent.
Optimisation intelligente : C'est comme un chef de cuisine qui, en regardant juste la liste des ingrédients sur le paquet, sait exactement combien de casseroles il lui faut pour cuisiner un plat pour 1000 personnes, sans avoir à ouvrir le paquet.

🏁 Conclusion

En résumé, cette recherche montre qu'on peut deviner la complexité d'une base de données en utilisant uniquement les "étiquettes" (métadonnées) qui sont déjà écrites sur les fichiers. C'est gratuit, instantané, et ça évite d'avoir à ouvrir les fichiers pour les lire.

C'est comme si vous pouviez deviner combien de personnes différentes sont dans une ville géante en regardant seulement la taille des immeubles et la liste des numéros de téléphone des immeubles, sans jamais avoir à frapper à une porte !

Each language version is independently generated for its own context, not a direct translation.

Titre

Estimation NDV à coût nul à partir des métadonnées de fichiers colonnaires

1. Problématique

Dans les moteurs de requêtes distribués accélérés par GPU (comme Theseus développé par VoltronData), l'optimisation basée sur le coût (CBO) nécessite des estimations précises du nombre de valeurs distinctes (NDV - Number of Distinct Values) d'une colonne. Ces estimations sont cruciales pour :

La réorganisation des jointures.
La poussée des agrégats (aggregate pushdown).
L'allocation mémoire des noyaux GPU.

Cependant, dans les formats de fichiers colonnaires comme Apache Parquet, le champ distinct_count est rarement rempli car son calcul exact est coûteux. Les méthodes alternatives (échantillonnage, sketches HyperLogLog) nécessitent soit l'accès aux données (ce qui annule l'avantage de la planification basée uniquement sur les métadonnées), soit une infrastructure d'écriture supplémentaire. L'objectif est donc d'exploiter uniquement les métadonnées existantes pour obtenir une estimation fiable sans accéder aux pages de données.

2. Méthodologie

L'auteur propose une approche hybride exploitant deux signaux implicites présents dans les métadonnées Parquet (et généralisables à d'autres formats) :

A. Inversion de l'équation de taille du dictionnaire

Pour les colonnes encodées par dictionnaire, la taille non compressée ( $S$ ) d'un chunk de colonne est la somme de la taille du dictionnaire et des indices. L'équation est :
$S = ndv \times len + (N - nulls) \times \lceil \log_2(ndv) \rceil / 8$
Où $ndv$ est le nombre de valeurs distinctes, $len$ la longueur moyenne des valeurs, et $N$ le nombre de lignes.

Méthode : En connaissant $S$ , $N$ , et en estimant $len$ , on résout cette équation pour $ndv$ en utilisant la méthode de Newton-Raphson.
Hypothèse : Cette méthode est précise lorsque les valeurs distinctes sont bien réparties (well-spread) à travers les groupes de lignes.

B. Estimation par diversité Min/Max (Modèle du Collecteur de Coupons)

Les statistiques de chaque groupe de lignes contiennent les valeurs minimales et maximales.

Principe : On traite les $n$ groupes de lignes comme $n$ tirages d'un problème de collecteur de coupons. Si l'on observe $m_{min}$ valeurs minimales distinctes sur $n$ groupes, on peut inverser l'espérance du modèle pour estimer la population totale ( $NDV$ ) :
$E[m_{min}] = NDV \times (1 - e^{-n/NDV})$
Hypothèse : Cette méthode est robuste pour les données triées ou partitionnées, où chaque groupe de lignes couvre une plage de valeurs distincte, ce qui génère une grande diversité de min/max.

C. Détection de distribution et Combinaison

Un détecteur de distribution analyse les chevauchements de plages et la monotonie des min/max entre les groupes de lignes pour classer les données :

Bien réparties : L'inversion du dictionnaire est utilisée.
Triées/Partitionnées : L'estimation Min/Max est utilisée.
Mixte : Le système prend le maximum des deux estimations (borné par le nombre de lignes non nulles et les contraintes de type), car chaque méthode sous-estime dans des régimes différents.

3. Contributions Clés

Équation fermée et résolution numérique : Une méthode pour déduire le NDV de la taille du dictionnaire via une itération de Newton-Raphson, incluant une estimation de la longueur moyenne des valeurs à partir des min/max.
Réinterprétation des statistiques Min/Max : La reconnaissance que les min/max par groupe de lignes agissent comme des sketches de cardinalité implicites, récupérables via l'inversion du modèle du collecteur de coupons.
Détection de distribution légère : Un algorithme qui route vers l'estimateur le plus pertinent en fonction de la structure des données (chevauchement des plages, monotonie).
Prédiction de mémoire par lot : Utilisation du modèle du collecteur de coupons pour prédire la taille du dictionnaire nécessaire pour un lot de données spécifique sans le lire, essentiel pour l'allocation mémoire GPU.

4. Résultats et Évaluation

Déploiement : La technique a été implémentée dans Theseus, un moteur de requêtes GPU distribué.
Précision : Sur des charges de travail de production avec des données Parquet réelles, les erreurs d'estimation étaient généralement inférieures à 10 % pour les colonnes bien réparties.
Robustesse : L'approche hybride a corrigé les sous-estimations systématiques de l'inversion du dictionnaire sur les données triées, grâce à l'estimateur Min/Max.
Coût : L'algorithme est O(n) en temps (où $n$ est le nombre de groupes de lignes) et O(1) en espace mémoire, ne nécessitant qu'un seul passage sur les métadonnées.

Note : L'auteur précise que les données expérimentales détaillées ont été perdues suite à la liquidation de VoltronData, mais l'article reconstruit l'approche de mémoire et prévoit une reproduction sur des benchmarks publics.

5. Signification et Applicabilité

Généralisation : La méthode ne se limite pas à Parquet. Elle s'applique à tout format disposant d'un encodage par dictionnaire avec une taille non compressée rapportée et de statistiques par partition (ex: ORC, et potentiellement F3).
Impact : Elle permet une optimisation de requêtes à coût nul (sans accès aux données), rendant possible des décisions d'optimisation complexes (comme la réécriture de requêtes ou l'allocation GPU) uniquement basées sur les métadonnées du catalogue.
Innovation : Elle transforme des statistiques conçues pour le predicate pushdown (saut de groupes de lignes) en outils puissants d'estimation de cardinalité, comblant un vide critique dans les optimiseurs de requêtes modernes.