Contexte technique

Un processeur moderne exécute entre 4 et 8 instructions par nanoseconde, alors qu’un accès à la RAM nécessite 50 à 100 ns. Cette différence implique qu’un cœur peut réaliser 400 à 800 instructions avant de devoir attendre une donnée en mémoire principale. Les caches intégrés (L1 ≈ 1 ns) réduisent ce délai de 50 à 100 fois, mais leur capacité reste limitée : typiquement 64 KB pour le L1 et quelques centaines de mégaoctets pour les niveaux supérieurs.

Dans les bases de données, les agrégations GROUP BY sont souvent implémentées avec une table de hachage qui s’étend proportionnellement au nombre de groupes uniques. Si chaque groupe correspond à une entrée distincte, les accès à la table de hachage deviennent « cold », c’est‑à‑dire qu’ils se traduisent par des lectures depuis la RAM plutôt que depuis le cache.

Expérimentation sur Pivot Lake

Le blog décrit un test sur un serveur bare‑metal AMD EPYC 9124 Genoa (16 cœurs, 128 GB DDR5). Le code Rust suivant illustre la version naïve :

fn consume(
    &mut self,
    batch: RecordBatch,
    _sender: &mut dyn Sender,
) -> unary::Result<()> {
    let group_keys = batch.column(self.key_column).as_primitive::();
    for &key in group_keys.values() {
        *self.counts.entry(key).or_insert(0) += 1;
    }
}

La requête SELECT count(*), UserID FROM hits GROUP BY UserID porte sur 99 M de lignes contenant ~17 M d’identifiants uniques. Le serveur est limité à un seul cœur (affinité taskset -c 3) afin de mesurer précisément les compteurs de performance.

Le premier passage dure 3,9 s, le second 3,6 s (les données sont déjà en page‑cache). Les compteurs perf stat révèlent que 50,1 % des cycles sont bloqués par la mémoire (backend_bound_memory) tandis que seulement 16,1 % des cycles aboutissent à la retraite d’une micro‑opération (retiring).

Un second compteur montre 76 190 837 remplissages de lignes depuis la DRAM. Chaque ligne vaut 64 octets, soit environ 4,5 GB de données transférées depuis la mémoire principale pendant l’exécution de la requête.

Analyse des goulots d’étranglement

Ces mesures confirment que le processeur passe la moitié de son temps à attendre des chargements mémoire, ce qui explique l’apparente saturation CPU à 100 % sans réelle progression du travail. La cause principale est le manque de localisation des accès : chaque clé de groupe entraîne un saut vers une adresse aléatoire dans la table de hachage, provoquant des miss de cache L1/L2 et forçant le contrôleur DRAM à fournir les lignes.

Le ratio 4,5 GB / 3,6 s ≈ 1,25 GB·s⁻¹ montre que le débit effectif de la mémoire est bien inférieur aux capacités théoriques du DDR5, car les accès sont non séquentiels et ne profitent pas du préchargement.

Optimisation par partitionnement radix

Pour réduire les miss, l’article propose le partitionnement radix : les clés sont d’abord réparties en 4096 partitions (vecteurs de SlabVec) afin que chaque partition tienne dans le cache L2 ou L3. Cette phase de « shuffle » crée des accès séquentiels, puis chaque partition est agrégée indépendamment, limitant les sauts d’adresse. Bien que le texte ne fournisse pas de mesures post‑optimisation, la théorie indique que le taux de backend_bound_memory devrait chuter drastiquement, augmentant la proportion de cycles retiring et réduisant le temps total de la requête.

En résumé, la latence mémoire, et non la puissance de calcul, constitue le facteur limitant des agrégations GROUP BY lorsqu’elles utilisent des structures de hachage naïves. Le recours à des algorithmes de partitionnement qui favorisent la localisation des données est essentiel pour exploiter pleinement les capacités des CPU modernes.