:Implémentation de l'opérateur TopK dans l'index columnstore

ORDER BY column LIMIT offset, count

File de priorité (TopK basé sur un tas)

Le système maintient un tas max de taille K. Pour chaque enregistrement parcouru, il vérifie son appartenance au top K ; si c'est le cas, il remplace l'élément supérieur et rééquilibre le tas. Une fois le balayage terminé, le tas contient les K plus grands enregistrements.

Cette méthode est efficace pour un K faible. Cependant, lorsque K est élevé (par exemple 1 000 100), deux problèmes surviennent :

• Pression mémoire : le tas peut excéder la capacité mémoire disponible.

• Inefficacité du cache : les opérations sur le tas nécessitent des accès mémoire aléatoires. Avec un K élevé, cela provoque de fréquents défauts de cache et réduit le débit.

Troncature lors du tri fusion

Utilisée par PolarDB, ClickHouse, SQL Server et DuckDB, cette approche génère des séquences triées pendant le tri, puis tronque chaque séquence fusionnée à offset + limit enregistrements. Seuls les enregistrements compris dans l'intervalle [offset, offset + limit) étant pertinents, il n'est pas nécessaire de trier l'intégralité des données.

Cette technique passe à l'échelle sur disque lorsque la mémoire est insuffisante. Toutefois, la troncature n'est bénéfique que si la séquence triée est suffisamment longue. Dans le cas d'une pagination profonde avec un K élevé, les premières séquences triées lors de la fusion sont souvent plus courtes que offset + limit, obligeant ainsi le système à trier l'ensemble du jeu de données avant que la troncature ne prenne effet.

Filtre d'entrée auto-affûtant

Proposé initialement par Goetz Graefe et adopté par ApsaraDB for ClickHouse, ce mécanisme maintient une valeur de seuil correspondant à la borne supérieure des enregistrements susceptibles d'apparaître dans le résultat top K. Les enregistrements dépassant ce seuil sont exclus avant même d'intégrer une séquence triée. Après la construction de chaque séquence triée, si sa longueur dépasse K, le K-ième enregistrement devient le nouveau seuil. Ce nouveau seuil étant toujours inférieur ou égal au précédent, le filtre s'affûte continuellement.

Exemple (K = 3) :

Contrairement aux opérations sur tas, le filtre auto-affûtant accède à la mémoire de manière séquentielle, tant pour le filtrage par seuil que pour l'accumulation des séquences triées. Cela évite la pénalité liée aux accès aléatoires inhérente à la gestion d'un tas.

Algorithme mémoire : filtre d'entrée auto-affûtant accéléré par SIMD

Lorsque la mémoire est suffisante, IMCI privilégie le filtre d'entrée auto-affûtant plutôt qu'une file de priorité. L'utilisation d'une file de priorité avec un K élevé est problématique pour deux raisons :

• Les accès mémoire aléatoires lors de la maintenance du tas dégradent les performances lorsque K est grand.

• La taille du tas devant être égale à K, la pression mémoire augmente linéairement avec K.

Le filtre auto-affûtant contourne ces deux obstacles :

• Le filtrage par seuil et l'accumulation des séquences triées effectuent tous deux des accès mémoire séquentiels.

• Ce filtre fonctionne correctement quelle que soit la valeur de K, couvrant ainsi la pagination superficielle et profonde sans condition de limite.

Accélération SIMD : le filtrage par seuil est une opération simple, répétitive et fréquente consistant à comparer chaque enregistrement au seuil actuel. IMCI accélère ce processus via des instructions SIMD (Single Instruction Multiple Data), appliquant la même comparaison à plusieurs enregistrements en parallèle. Le filtre réutilise l'infrastructure d'évaluation d'expressions déjà employée par le filtre de prédicat de balayage de table, évitant ainsi tout chemin de code supplémentaire.

Algorithme disque : élagage basé sur ZoneMap avec tri fusion

En cas de mémoire insuffisante, IMCI recourt au tri fusion avec troncature. L'usage du filtre auto-affûtant sur disque est écarté pour les raisons suivantes :

• L'écriture sur disque des séquences triées accumulées et l'exécution d'un tri externe lors de la préfusion génèrent un volume important d'E/S disque.

• Avec un K élevé, la préfusion risque de traiter une quantité significative de données situées hors de l'intervalle [offset, offset + limit) avant qu'un seuil utile ne soit établi.

Le tri fusion avec troncature évite ces écueils. De plus, l'élagage basé sur les ZoneMap réduit davantage les E/S en exploitant les statistiques min/max des séquences triées pour ignorer celles qui ne contribuent pas au résultat.

Fonctionnement de l'élagage ZoneMap :

Chaque séquence triée stocke ses valeurs minimale et maximale. Une valeur de barrière classe toutes les séquences triées en trois types :

Deux règles d'élagage permettent d'éliminer les séquences triées n'ayant aucun impact sur le résultat :

• Si le total des enregistrements de type A + type B est < offset, tous les enregistrements de type A se trouvent dans l'intervalle [0, offset). Excluez le type A des fusions ultérieures.

• Si le total des enregistrements de type A est > offset + limit, tous les enregistrements de type C se trouvent dans l'intervalle [offset + limit, N). Excluez le type C des fusions ultérieures.

Processus d'élagage :

1. Construisez une ZoneMap contenant les valeurs min et max de chaque séquence triée.

2. Identifiez la Barrière 1 (la plus grande possible) telle que les enregistrements de type A + type B soient < offset.

3. Identifiez la Barrière 2 (la plus petite possible) telle que les enregistrements de type A soient > offset + limit.

4. Utilisez la Barrière 1 et la Barrière 2 pour exclure les séquences triées correspondantes des fusions ultérieures.

Sélection dynamique de l'algorithme

Plutôt que d'utiliser un seuil K fixe, IMCI sélectionne l'algorithme dynamiquement via un mécanisme de repli :

1. Démarrez toujours avec l'algorithme mémoire.

2. Si la mémoire reste suffisante tout au long du processus, terminez le calcul en mémoire.

3. Si la mémoire vient à manquer (par exemple, espace insuffisant pour mettre en cache assez de séquences triées contenant plus de K enregistrements, ou espace insuffisant pour terminer la préfusion), déclenchez le mécanisme de repli :

   • Collectez les valeurs min/max des séquences triées en mémoire et construisez une ZoneMap.

   • Sauvegardez ces séquences triées sur disque.

   • Basculez vers l'algorithme disque pour la suite du calcul.

4. Terminez le calcul à l'aide de l'algorithme disque.

Les deux algorithmes utilisant les mêmes structures de données, le repli ne nécessite aucune réorganisation des données. Les séquences triées accumulées durant la phase mémoire sont directement exploitées par l'algorithme disque, sans perte de précision.

Matérialisation tardive

Lors de la construction des séquences triées, IMCI ne matérialise que les ID de ligne ainsi que les colonnes ou expressions référencées dans la clause ORDER BY. Les colonnes de sortie sont récupérées depuis le stockage une fois le jeu de résultats TopK déterminé.

Cette approche réduit la surcharge de deux manières :

• Les ID de ligne étant compacts, davantage d'enregistrements tiennent dans le même budget mémoire, ce qui étend le champ d'application de l'algorithme mémoire.

• Les enregistrements étant fréquemment réordonnés durant le calcul TopK via des opérations de copie et d'échange, la matérialisation des seuls ID de ligne minimise le coût unitaire de ces opérations par enregistrement.

La contrepartie est que la récupération des colonnes de sortie par ID de ligne après le tri peut entraîner des E/S aléatoires. Toutefois, dans les scénarios de pagination profonde, le jeu de résultats réel étant restreint (par exemple 100 enregistrements), cet impact reste négligeable.

Délégation du calcul (Computing pushdown)

Durant l'exécution du filtre auto-affûtant, la valeur de seuil actuelle est déléguée à l'opérateur de balayage de table sous forme de nouveau prédicat. Le balayage de table peut alors appliquer ce prédicat via l'infrastructure d'élagage existante, filtrant ainsi au niveau du pack ou du groupe de lignes avant que les données n'atteignent l'opérateur TopK.

Cela réduit la surcharge à deux niveaux :

• Réduction des E/S : les packs ou groupes de lignes ne contenant que des enregistrements supérieurs au seuil sont entièrement ignorés.

• Réduction du calcul : les packs ou groupes de lignes filtrés ne sont pas traités par les opérateurs de niveau supérieur.

SELECT
    l_orderkey,
    sum(l_quantity)
FROM
    lineitem
GROUP BY
    l_orderkey
ORDER BY
    sum(l_quantity) DESC
LIMIT
    1000000, 100;