RÉSUMÉ
1 INTRODUCTION
- D’énormes jeux de données avec des taux d’ingestion élevés. De nombreuses applications orientées données dans des secteurs comme l’analytique web, la finance et le e-commerce se caractérisent par des volumes de données énormes et en croissance continue. Pour gérer de tels jeux de données, les bases de données analytiques doivent non seulement offrir des stratégies efficaces d’indexation et de compression, mais aussi permettre la distribution des données sur plusieurs nœuds (scale-out), car un seul serveur est limité à quelques dizaines de téraoctets de stockage. En outre, les données récentes sont souvent plus pertinentes pour des analyses en temps réel que les données historiques. Les bases de données analytiques doivent donc être capables d’ingérer de nouvelles données à des débits durablement élevés ou par pics, tout en « dépriorisant » en continu les données historiques (par exemple en les agrégeant ou en les archivant) sans ralentir les requêtes de reporting exécutées en parallèle.
- De nombreuses requêtes simultanées avec une exigence de faible latence. Les requêtes peuvent généralement être classées en deux catégories : ad hoc (par exemple pour l’analyse exploratoire de données) ou récurrentes (par exemple les requêtes périodiques d’un tableau de bord). Plus un cas d’usage est interactif, plus les latences attendues sont faibles, ce qui pose des défis en matière d’optimisation et d’exécution des requêtes. Les requêtes récurrentes offrent en outre la possibilité d’adapter l’organisation physique de la base de données à la charge de travail. Les bases de données doivent donc proposer des techniques d’élagage permettant d’optimiser les requêtes fréquentes. Selon la priorité des requêtes, elles doivent également assurer un accès égalitaire ou prioritaire aux ressources système partagées, telles que le CPU, la mémoire, le disque et les E/S réseau, même lorsqu’un grand nombre de requêtes s’exécutent simultanément.
- Des environnements variés en matière de magasins de données, d’emplacements de stockage et de formats. Pour s’intégrer aux architectures de données existantes, les bases de données analytiques modernes doivent faire preuve d’une grande ouverture afin de pouvoir lire et écrire des données externes, quel que soit le système, l’emplacement ou le format.
- Un langage de requête pratique avec prise en charge de l’introspection des performances. L’utilisation réelle des bases de données OLAP s’accompagne d’exigences supplémentaires plus « souples ». Par exemple, plutôt qu’un langage de programmation de niche, les utilisateurs préfèrent souvent interagir avec les bases de données au moyen d’un dialecte SQL expressif, avec des types de données imbriqués et un large éventail de fonctions classiques, d’agrégation et de fenêtre. Les bases de données analytiques doivent également fournir des outils sophistiqués pour inspecter les performances du système ou de requêtes individuelles.
- Une robustesse de niveau industriel et des options de déploiement variées. Le matériel standard n’étant pas fiable, les bases de données doivent assurer la réplication des données afin de résister aux défaillances de nœuds. Elles doivent aussi pouvoir fonctionner sur tout type de matériel, depuis de vieux ordinateurs portables jusqu’à de puissants serveurs. Enfin, pour éviter le surcoût du garbage collection dans les programmes basés sur la JVM et permettre des performances bare metal (par exemple SIMD), les bases de données sont idéalement déployées sous forme de binaires natifs pour la plateforme cible.
Figure 1 : chronologie de ClickHouse.
2 ARCHITECTURE
Figure 2 : architecture de haut niveau du moteur de base de données ClickHouse.
3 COUCHE DE STOCKAGE
Cette section présente les moteurs de table MergeTree* comme le format de stockage natif de ClickHouse. Nous décrivons leur représentation sur disque et examinons trois techniques d’élagage des données dans ClickHouse. Nous présentons ensuite des stratégies de fusion qui transforment continuellement les données sans perturber les insertions simultanées. Enfin, nous expliquons comment sont mises en œuvre les mises à jour et les suppressions, ainsi que la déduplication des données, la réplication des données et la conformité ACID.3.1 Format sur disque
Chaque table utilisant le moteur de table MergeTree* est organisée comme un ensemble de table parts immuables. Une part est créée chaque fois qu’un ensemble de lignes est inséré dans la table. Les parts sont autonomes, en ce sens qu’elles incluent toutes les métadonnées nécessaires pour interpréter leur contenu sans lookup supplémentaire dans un catalog central. Afin de limiter le nombre de parts par table, une tâche de merge en arrière-plan combine périodiquement plusieurs petites parts en une part plus grande, jusqu’à atteindre une part size configurable (150 GB par défaut). Comme les parts sont triées selon les colonnes de clé primaire de la table (voir Section 3.2), un algorithme efficace de tri par fusion k-way [40] est utilisé pour le merging. Les parts source sont marquées comme inactives puis, à terme, supprimées dès que leur compteur de références tombe à zéro, c.-à-d. qu’aucune requête ne les lit encore. Les lignes peuvent être insérées selon deux modes : en mode de Synchronous inserts, chaque instruction INSERT crée une nouvelle part et l’ajoute à la table. Pour minimiser l’overhead des merges, il est recommandé aux clients de base de données d’insérer les Tuples en masse, par exemple 20 000 lignes à la fois. Cependant, les délais causés par le client-side batching sont souvent inacceptables si les données doivent être analysées en real-time. Par exemple, les cas d’usage d’observability impliquent fréquemment des milliers d’agents de Monitoring envoyant en continu de petites quantités de données d’événements et de metrics. Dans ce type de scénario, on peut utiliser le mode d’asynchronous insert, dans lequel ClickHouse met en buffer les lignes de plusieurs INSERT entrants dans la même table et ne crée une nouvelle part qu’une fois que la taille du buffer dépasse un threshold configurable ou qu’un timeout expire.
Figure 3 : inserts et merges pour les tables utilisant le moteur MergeTree*.
3.2 Élagage des données
Dans la plupart des cas d’usage, parcourir des pétaoctets de données simplement pour répondre à une seule requête est trop lent et trop coûteux. ClickHouse prend en charge trois techniques d’élagage des données qui permettent d’ignorer la majorité des lignes lors des recherches et, par conséquent, d’accélérer considérablement les requêtes. Premièrement, les utilisateurs peuvent définir un index de clé primaire pour une table. Les colonnes de clé primaire déterminent l’ordre de tri des lignes au sein de chaque part, c.-à-d. que l’index y est clusterisé localement. ClickHouse stocke en outre, pour chaque part, une correspondance entre les valeurs des colonnes de clé primaire de la première ligne de chaque granule et l’identifiant du granule, c.-à-d. que l’index est clairsemé [31]. La structure de données qui en résulte est généralement assez compacte pour rester entièrement en mémoire ; par exemple, 1000 entrées seulement suffisent pour indexer 8,1 millions de lignes. L’objectif principal d’une clé primaire est d’évaluer les prédicats d’égalité et d’intervalle pour les colonnes fréquemment filtrées à l’aide d’une recherche binaire plutôt que de balayages séquentiels (section 4.4). Le tri local peut en outre être exploité pour les fusions de parts et l’optimisation des requêtes, par exemple pour l’agrégation basée sur le tri ou pour supprimer des opérateurs de tri du plan d’exécution physique lorsque les colonnes de clé primaire forment un préfixe des colonnes de tri. La figure 4 montre un index de clé primaire sur la colonne EventTime pour une table contenant des statistiques d’affichage de pages. Les granules qui correspondent au prédicat d’intervalle de la requête peuvent être trouvés par recherche binaire dans l’index de clé primaire au lieu de parcourir EventTime séquentiellement.
Figure 4 : Évaluation des filtres avec un index de clé primaire.
3.3 Transformation des données lors des fusions
Les cas d’usage de business intelligence et d’observabilité doivent souvent traiter des données générées à des débits durablement élevés ou par pics. En outre, les données récentes sont généralement plus pertinentes pour produire des informations exploitables en temps réel que les données historiques. De tels cas d’usage exigent des bases de données qu’elles prennent en charge des taux élevés d’ingestion de données tout en réduisant en continu le volume des données historiques grâce à des techniques comme l’agrégation ou le vieillissement des données. ClickHouse permet une transformation incrémentielle continue des données existantes au moyen de différentes stratégies de fusion. La transformation des données lors des fusions ne compromet pas les performances des instructions INSERT, mais elle ne peut pas garantir que les tables ne contiennent jamais de valeurs indésirables (par ex. obsolètes ou non agrégées). Si nécessaire, toutes les transformations effectuées lors des fusions peuvent être appliquées au moment de la requête en spécifiant le mot-clé FINAL dans les instructions SELECT. Les fusions de remplacement ne conservent que la version d’un tuple insérée le plus récemment, en se basant sur l’horodatage de création de la part qui le contient ; les versions plus anciennes sont supprimées. Les tuples sont considérés comme équivalents s’ils ont les mêmes valeurs dans les colonnes de clé primaire. Pour contrôler explicitement le tuple conservé, il est également possible de spécifier une colonne de version spéciale pour la comparaison. Les fusions de remplacement sont couramment utilisées comme mécanisme de mise à jour lors des fusions (généralement dans les cas d’usage où les mises à jour sont fréquentes), ou comme alternative à la déduplication des données au moment de l’insert (Section 3.5)). Les fusions d’agrégation regroupent les lignes ayant les mêmes valeurs dans les colonnes de clé primaire en une ligne agrégée. Les colonnes hors clé primaire doivent être dans un état d’agrégation partielle contenant les valeurs de synthèse. Deux états d’agrégation partielle, par ex. une somme et un décompte pour avg(), sont combinés en un nouvel état d’agrégation partielle. Les fusions d’agrégation sont généralement utilisées dans des vues matérialisées plutôt que dans des tables classiques. Les vues matérialisées sont alimentées à partir d’une requête de transformation sur une table source. Contrairement à d’autres bases de données, ClickHouse n’actualise pas périodiquement les vues matérialisées avec l’intégralité du contenu de la table source. Les vues matérialisées sont plutôt mises à jour de manière incrémentielle avec le résultat de la requête de transformation lorsqu’une nouvelle part est insérée dans la table source. La Figure 5 montre une vue matérialisée définie sur une table contenant des statistiques d’impressions de page. Pour les nouvelles parts insérées dans la table source, la requête de transformation calcule les latences maximales et moyennes, regroupées par région, puis insère le résultat dans une vue matérialisée. Les fonctions d’agrégation avg() et max() avec l’extension -State renvoient des états d’agrégation partielle au lieu de résultats effectifs. Une fusion d’agrégation définie pour la vue matérialisée combine en continu les états d’agrégation partielle dans différentes parts. Pour obtenir le résultat final, les utilisateurs consolident les états d’agrégation partielle dans la vue matérialisée à l’aide de avg() et max()) avec l’extension -Merge.
Figure 5 : Fusions d’agrégation dans les vues matérialisées.
3.4 Mises à jour et suppressions
La conception des moteurs de table MergeTree* privilégie les charges de travail en ajout uniquement, mais certains cas d’usage exigent de modifier occasionnellement des données existantes, par exemple pour satisfaire à des exigences de conformité réglementaire. Il existe deux approches pour mettre à jour ou supprimer des données, et aucune ne bloque les insertions parallèles. Les mutations réécrivent sur place toutes les parts d’une table. Pour éviter qu’une table (suppression) ou une colonne (mise à jour) ne double temporairement de taille, cette opération n’est pas atomique, c’est-à-dire que des instructions SELECT parallèles peuvent lire à la fois des parts mutées et non mutées. Les mutations garantissent que les données sont physiquement modifiées à la fin de l’opération. Les mutations de suppression restent coûteuses, car elles réécrivent toutes les colonnes de toutes les parts. Comme alternative, les lightweight deletes ne mettent à jour qu’une colonne bitmap interne, indiquant si une ligne est supprimée ou non. ClickHouse ajoute aux requêtes SELECT un filtre supplémentaire sur la colonne bitmap afin d’exclure les lignes supprimées du résultat. Les lignes supprimées ne sont physiquement retirées que lors des fusions régulières, à un moment ultérieur non spécifié. Selon le nombre de colonnes, les lightweight deletes peuvent être bien plus rapides que les mutations, au prix de SELECT plus lents. Les opérations de mise à jour et de suppression effectuées sur la même table sont censées être rares et sérialisées afin d’éviter les conflits logiques.3.5 Insertions idempotentes
Un problème fréquent en pratique est de savoir comment les clients doivent gérer les délais d’expiration de connexion après avoir envoyé des données au serveur pour les insérer dans une table. Dans cette situation, il est difficile pour les clients de déterminer si les données ont bien été insérées ou non. Traditionnellement, ce problème est résolu en renvoyant les données du client au serveur et en s’appuyant sur la clé primaire ou sur des contraintes d’unicité pour rejeter les insertions en double. Les bases de données effectuent rapidement les recherches ponctuelles nécessaires à l’aide de structures d’index fondées sur des arbres binaires [39, 68], des arbres radix [45] ou des tables de hachage [29]. Comme ces structures de données indexent chaque tuple, leur coût en espace et en mises à jour devient prohibitif pour de grands jeux de données et des taux d’ingestion élevés. ClickHouse propose une alternative plus légère, fondée sur le fait que chaque insertion finit par créer une part. Plus précisément, le serveur conserve les hachages des N dernières parts insérées (par exemple N=100) et ignore les réinsertions de parts dont le hachage est déjà connu. Les hachages des tables non répliquées et répliquées sont stockés respectivement en local et dans Keeper. Les insertions deviennent ainsi idempotentes, c’est-à-dire que les clients peuvent simplement renvoyer le même lot de lignes après un délai d’expiration et partir du principe que le serveur se charge de la déduplication. Pour un contrôle plus fin du processus de déduplication, les clients peuvent également fournir un jeton d’insertion qui tient lieu de hachage de part. Bien que la déduplication fondée sur le hachage entraîne un surcoût lié au calcul du hachage des nouvelles lignes, le coût de stockage et de comparaison des hachages est négligeable.3.6 Réplication des données
La réplication est un prérequis pour la haute disponibilité (tolérance aux défaillances des nœuds), mais elle sert aussi à la répartition de charge et aux mises à niveau sans interruption de service [14]. Dans ClickHouse, la réplication repose sur la notion d’états de table, qui se composent d’un ensemble de parts de table (section 3.1) et de métadonnées de table, telles que les noms de colonnes et les types. Les nœuds font évoluer l’état d’une table au moyen de trois opérations : 1. les insertions ajoutent une nouvelle part à l’état, 2. les fusions ajoutent une nouvelle part à l’état et en retirent des parts existantes, 3. les mutations et les instructions DDL ajoutent des parts, et/ou suppriment des parts, et/ou modifient les métadonnées de table, selon l’opération concernée. Les opérations sont exécutées localement sur un seul nœud et consignées comme une séquence de transitions d’état dans un journal global de réplication. Le journal de réplication est maintenu par un ensemble de généralement trois processus ClickHouse Keeper, qui utilisent l’algorithme de consensus Raft [59] pour fournir une couche de coordination distribuée et tolérante aux pannes à un cluster de nœuds ClickHouse. Tous les nœuds du cluster pointent initialement vers la même position dans le journal de réplication. Tandis que les nœuds exécutent localement des insertions, des fusions, des mutations et des instructions DDL, le journal de réplication est rejoué de manière asynchrone sur tous les autres nœuds. En conséquence, les tables répliquées ne sont cohérentes qu’à terme, c’est-à-dire que les nœuds peuvent temporairement lire d’anciens états de table tout en convergeant vers l’état le plus récent. La plupart des opérations susmentionnées peuvent aussi être exécutées de manière synchrone jusqu’à ce qu’un quorum de nœuds (par exemple, une majorité des nœuds ou l’ensemble des nœuds) ait adopté le nouvel état. À titre d’exemple, la figure 6 montre une table répliquée initialement vide dans un cluster de trois nœuds ClickHouse. Le nœud 1 reçoit d’abord deux instructions d’insertion et les consigne ( 1 2 ) dans le journal de réplication stocké dans l’ensemble Keeper. Ensuite, le nœud 2 rejoue la première entrée du journal en la récupérant ( 3 ) et en téléchargeant la nouvelle part depuis le nœud 1 ( 4 ), tandis que le nœud 3 rejoue les deux entrées du journal ( 3 4 5 6 ). Enfin, le nœud 3 fusionne les deux parts en une nouvelle part, supprime les parts d’entrée et consigne une entrée de fusion dans le journal de réplication ( 7 ).
Figure 6 : Réplication dans un cluster de trois nœuds.
3.7 Conformité ACID
Pour maximiser les performances des opérations concurrentes de lecture et d’écriture, ClickHouse évite autant que possible le verrouillage. Les requêtes sont exécutées sur un instantané de toutes les parts de toutes les tables impliquées, créé au début de la requête. Cela garantit que les nouvelles parts insérées par des INSERT parallèles ou des fusions (section 3.1) ne participent pas à l’exécution. Pour éviter que des parts soient modifiées ou supprimées simultanément (section 3.4), le compteur de références des parts traitées est incrémenté pendant toute la durée de la requête. Formellement, cela correspond à une isolation par instantané reposant sur une variante de MVCC [6] basée sur des parts versionnées. Par conséquent, les instructions ne sont généralement pas conformes à ACID, sauf dans le cas rare où les écritures concurrentes au moment de la prise de l’instantané n’affectent chacune qu’une seule part. En pratique, la plupart des cas d’usage de ClickHouse orientés prise de décision et générant beaucoup d’écritures tolèrent même un faible risque de perte de nouvelles données en cas de panne de courant. La base de données en tire parti en ne forçant pas, par défaut, le commit (fsync) des parts nouvellement insérées sur disque, ce qui permet au noyau de regrouper les écritures au prix de l’abandon de l’atomicité.
4 COUCHE DE TRAITEMENT DES REQUÊTES
Figure 7 : Parallélisation entre les unités SIMD, les cœurs et les nœuds.
4.1 Parallélisation SIMD
cpuid. Cette approche permet à ClickHouse de fonctionner sur des systèmes vieux de 15 ans (avec SSE 4.2 comme minimum), tout en offrant des accélérations significatives sur du matériel récent.
4.2 Parallélisation multicœur
Figure 8 : un plan physique d'opérateurs avec trois voies d'exécution.
4.3 Parallélisation sur plusieurs nœuds
4.4 Optimisation globale des performances
Cette section présente une sélection des principales optimisations de performances appliquées aux différentes étapes de l’exécution des requêtes. Optimisation des requêtes. Le premier ensemble d’optimisations s’applique à une représentation sémantique de la requête obtenue à partir de son AST. Parmi ces optimisations figurent le constant folding (par ex. concat(lower(‘a’),upper(‘b’)) devient ‘aB’), l’extraction de scalaires de certaines fonctions d’agrégation (par ex. sum(a2) devient 2 * sum(a)), l’élimination des sous-expressions communes et la transformation de disjonctions de filtres d’égalité en listes IN (par ex. x=c OR x=d devient x IN (c,d)). La représentation sémantique optimisée de la requête est ensuite transformée en plan logique d’opérateurs. Les optimisations appliquées à ce plan logique incluent le pushdown des filtres, ainsi que la réorganisation de l’évaluation des fonctions et des étapes de tri selon celle qui est estimée la plus coûteuse. Enfin, le plan logique de la requête est transformé en plan physique d’opérateurs. Cette transformation peut exploiter les particularités des moteur de table impliqués. Par exemple, dans le cas d’un table engine MergeTree, si les colonnes ORDER BY forment un préfixe de la clé primaire, les données peuvent être lues dans l’ordre du disque et les opérateurs de tri peuvent être supprimés du plan. De plus, si les colonnes de regroupement d’une agrégation forment un préfixe de la clé primaire, ClickHouse peut utiliser l’agrégation par tri [33], c’est-à-dire agréger directement les séquences de même valeur dans les entrées prétriées. Par rapport à l’agrégation par hachage, l’agrégation par tri consomme nettement moins de mémoire, et la valeur agrégée peut être transmise à l’opérateur suivant immédiatement après le traitement d’une séquence. Compilation des requêtes. ClickHouse utilise la compilation des requêtes basée sur LLVM pour fusionner dynamiquement des opérateurs de plan adjacents [38, 53]. Par exemple, l’expression a * b + c + 1 peut être combinée en un seul opérateur au lieu de trois. Outre les expressions, ClickHouse utilise également la compilation pour évaluer plusieurs fonctions d’agrégation en une seule fois (c.-à-d. pour GROUP BY) et pour le tri avec plusieurs clés de tri. La compilation des requêtes réduit le nombre d’appels virtuels, conserve les données dans les registres ou les caches CPU, et aide le prédicteur de branchement, car moins de code doit être exécuté. En outre, la compilation à l’exécution permet de tirer parti d’un large éventail d’optimisations, telles que les optimisations logiques et les optimisations locales implémentées dans les compilateurs, et donne accès aux instructions CPU locales les plus rapides disponibles. La compilation n’est déclenchée que lorsque la même expression régulière, d’agrégation ou de tri est exécutée par différentes requêtes plus d’un nombre configurable de fois. Les opérateurs de requête compilés sont mis en cache et peuvent être réutilisés par de futures requêtes.[7] Évaluation de l’index de clé primaire. ClickHouse évalue les conditions WHERE à l’aide de l’index de clé primaire si un sous-ensemble des clauses de filtre de la forme normale conjonctive de la condition constitue un préfixe des colonnes de la clé primaire. L’index de clé primaire est analysé de gauche à droite sur des plages de valeurs de clé triées lexicographiquement. Les clauses de filtre correspondant à une colonne de clé primaire sont évaluées à l’aide d’une logique ternaire : elles sont soit toutes vraies, soit toutes fausses, soit mixtes pour les valeurs de la plage. Dans ce dernier cas, la plage est divisée en sous-plages, qui sont analysées récursivement. Des optimisations supplémentaires existent pour les fonctions dans les conditions de filtre. Premièrement, les fonctions possèdent des propriétés décrivant leur monotonie ; par ex., toDayOfMonth(date) est monotone par morceaux à l’intérieur d’un mois. Ces propriétés de monotonie permettent de déduire si une fonction produit des résultats triés à partir de plages triées de valeurs de clé en entrée. Deuxièmement, certaines fonctions peuvent calculer l’image réciproque d’un résultat de fonction donné. Cela permet de remplacer des comparaisons de constantes avec des appels de fonction sur les colonnes de clé par des comparaisons entre la valeur de la colonne de clé et l’image réciproque. Par exemple, toYear(k) = 2024 peut être remplacé par k >= 2024-01-01 && k < 2025-01-01. Évitement de lecture de données. ClickHouse essaie d’éviter les lectures de données à l’exécution de la requête en utilisant les structures de données présentées dans la section 3.2. En outre, les filtres sur différentes colonnes sont évalués séquentiellement par ordre décroissant de sélectivité estimée, sur la base d’heuristiques et de statistiques de colonnes (facultatives). Seuls les chunks de données qui contiennent au moins une ligne correspondante sont transmis au prédicat suivant. Cela réduit progressivement la quantité de données lues et le nombre de calculs à effectuer d’un prédicat à l’autre. Cette optimisation n’est appliquée que lorsqu’au moins un prédicat hautement sélectif est présent ; sinon, la latence de la requête se dégraderait par rapport à une évaluation de tous les prédicats en parallèle. Tables de hachage. Les tables de hachage sont des structures de données fondamentales pour l’agrégation et les jointures par hachage. Choisir le bon type de table de hachage est essentiel pour les performances. ClickHouse instancie diverses tables de hachage (plus de 30 en mars 2024) à partir d’un modèle générique de table de hachage, avec pour points de variation la fonction de hachage, l’allocateur, le type de cellule et la politique de redimensionnement. Selon le type de données des colonnes de regroupement, la cardinalité estimée de la table de hachage et d’autres facteurs, la table de hachage la plus rapide est sélectionnée individuellement pour chaque opérateur de requête. Parmi les autres optimisations mises en œuvre pour les tables de hachage figurent :- une organisation à deux niveaux avec 256 sous-tables (basées sur le premier octet du hachage) pour prendre en charge d’énormes ensembles de clés,
- des tables de hachage pour chaînes [79] avec quatre sous-tables et différentes fonctions de hachage selon la longueur des chaînes,
- des tables de lookup qui utilisent directement la clé comme indice de bucket (c’est-à-dire sans hachage) lorsqu’il n’y a que peu de clés,
- des valeurs avec hachages intégrés pour accélérer la résolution des collisions lorsque la comparaison est coûteuse (par ex. chaînes, AST),
- la création de tables de hachage fondée sur des tailles prédites à partir de statistiques d’exécution afin d’éviter des redimensionnements inutiles,
- l’allocation de plusieurs petites tables de hachage ayant le même cycle de vie de création/destruction dans une même tranche mémoire,
- l’effacement instantané des tables de hachage en vue de leur réutilisation à l’aide de compteurs de version par table de hachage et par cellule,
- l’utilisation de la prélecture CPU (__builtin_prefetch) pour accélérer la récupération des valeurs après le hachage de la clé.
Figure 9 : Jointure par hachage parallèle avec trois partitions de table de hachage.
4.5 Isolation des charges de travail
ClickHouse offre un contrôle de la concurrence, des limites d’utilisation de la mémoire et une planification des E/S, ce qui permet aux utilisateurs d’isoler les requêtes dans des classes de charge de travail. En définissant des limites sur les ressources partagées (cœurs de CPU, DRAM, E/S disque et réseau) pour des classes de charge de travail spécifiques, ClickHouse garantit que ces requêtes n’affectent pas d’autres requêtes métier critiques. Le contrôle de la concurrence évite le surabonnement des threads dans les scénarios comportant un grand nombre de requêtes concurrentes. Plus précisément, le nombre de threads de travail par requête est ajusté dynamiquement selon un ratio spécifié par rapport au nombre de cœurs de CPU disponibles. ClickHouse suit la taille en octets des allocations mémoire au niveau du serveur, de l’utilisateur et de la requête, et permet ainsi de définir des limites souples d’utilisation de la mémoire. Le memory overcommit permet aux requêtes d’utiliser davantage de mémoire libre au-delà de la mémoire garantie, tout en garantissant des limites mémoire pour les autres requêtes. En outre, l’utilisation de la mémoire pour les clauses d’aggregation, de sort et de join peut être limitée, ce qui entraîne un basculement vers des algorithmes externes lorsque la limite mémoire est dépassée. Enfin, la planification des E/S permet aux utilisateurs de restreindre les accès aux disques locaux et distants pour les classes de charge de travail selon une bande passante maximale, les requêtes en cours et la politique (par ex. FIFO, SFC [32]).5 COUCHE D’INTÉGRATION
Les applications de prise de décision en temps réel dépendent souvent d’un accès efficace et à faible latence à des données réparties sur plusieurs sites. Il existe deux approches pour rendre des données externes accessibles dans une base de données OLAP. Avec un accès aux données de type push, un composant tiers fait le lien entre la base de données et des systèmes de stockage externes. Les outils spécialisés d’extract-transform-load (ETL), qui poussent les données distantes vers le système de destination, en sont un exemple. Dans le modèle pull, la base de données elle-même se connecte aux sources de données distantes et récupère les données pour les interroger dans des tables locales, ou exporte les données vers des systèmes distants. Bien que les approches de type push soient plus polyvalentes et plus répandues, elles impliquent une architecture plus lourde et créent un goulot d’étranglement en matière de montée en charge. À l’inverse, la connectivité distante directement dans la base de données offre des capacités intéressantes, comme les jointures entre données locales et distantes, tout en conservant une architecture simple et en réduisant le temps nécessaire pour obtenir des insights. Le reste de cette section explore les méthodes d’intégration de données de type pull dans ClickHouse, conçues pour accéder à des données distantes. Notons que l’idée de la connectivité distante dans les bases de données SQL n’est pas nouvelle. Par exemple, le standard SQL/MED [35], introduit en 2001 et implémenté par PostgreSQL depuis 2011 [65], propose les foreign data wrappers comme interface unifiée pour gérer des données externes. Une interopérabilité maximale avec d’autres systèmes de stockage et formats de données est l’un des objectifs de conception de ClickHouse. En mars 2024, ClickHouse offre, à notre connaissance, le plus grand nombre d’options d’intégration de données intégrées parmi toutes les bases de données analytiques. Connectivité externe. ClickHouse fournit plus de 50 fonctions de table et moteurs d’intégration pour se connecter à des systèmes externes et à des emplacements de stockage, notamment ODBC, MySQL, PostgreSQL, SQLite, Kafka, Hive, MongoDB, Redis, les stockages objet S3/GCP/Azure et divers data lakes. Nous les répartissons plus en détail dans les catégories présentées dans la figure bonus suivante (qui ne fait pas partie de l’article original du VLDB).
Figure bonus : options d’interopérabilité de ClickBench.
6 LA PERFORMANCE COMME FONCTIONNALITÉ
6.1 Outils intégrés d’analyse des performances
6.2 Tests de performance
6.2.1 Tables dénormalisées
Figure 10 : temps d’exécution relatifs à froid et à chaud de ClickBench.
Figure 11 : Temps d’exécution relatifs en cache chaud de VersionsBench 2018-2024.
6.2.2 Tables normalisées
Figure 12 : Temps d’exécution à chaud (en secondes) des requêtes TPC-H.
8 CONCLUSION ET PERSPECTIVES
REMERCIEMENTS
RÉFÉRENCES
- 1 Daniel Abadi, Peter Boncz, Stavros Harizopoulos, Stratos Idreaos, et Samuel Madden. 2013. The Design and Implementation of Modern Column-Oriented Database Systems. https://doi.org/10.1561/9781601987556
- 2 Daniel Abadi, Samuel Madden et Miguel Ferreira. 2006. Integrating Compression and Execution in Column-Oriented Database Systems. Dans les actes de la conférence internationale ACM SIGMOD 2006 sur la gestion des données (SIGMOD ‘06). 671–682.https://doi.org/10.1145/1142473.1142548
- 3 Anastassia Ailamaki, David J. DeWitt, Mark D. Hill, et Marios Skounakis. 2001. Weaving Relations for Cache Performance. Dans les actes de la 27th International Conference on Very Large Data Bases (VLDB ‘01). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 169–180.
- 4 Nikos Armenatzoglou, Sanuj Basu, Naga Bhanoori, Mengchu Cai, Naresh Chainani, Kiran Chinta, Venkatraman Govindaraju, Todd J. Green, Monish Gupta, Sebastian Hillig, Eric Hotinger, Yan Leshinksy, Jintian Liang, Michael McCreedy, Fabian Nagel, Ippokratis Pandis, Panos Parchas, Rahul Pathak, Orestis Polychroniou, Foyzur Rahman, Gaurav Saxena, Gokul Soundararajan, Sriram Subramanian et Doug Terry. 2022. Amazon Redshift Re-Invented. Dans les actes de l’International Conference on Management of Data 2022 (Philadelphie, Pennsylvanie, États-Unis) (SIGMOD ‘22). Association for Computing Machinery, New York, NY, USA, 2205–2217. https://doi.org/10.1145/3514221.3526045
- 5 Alexander Behm, Shoumik Palkar, Utkarsh Agarwal, Timothy Armstrong, David Cashman, Ankur Dave, Todd Greenstein, Shant Hovsepian, Ryan Johnson, Arvind Sai Krishnan, Paul Leventis, Ala Luszczak, Prashanth Menon, Mostafa Mokhtar, Gene Pang, Sameer Paranjpye, Greg Rahn, Bart Samwel, Tom van Bussel, Herman van Hovell, Maryann Xue, Reynold Xin, et Matei Zaharia. 2022. Photon: A Fast Query Engine for Lakehouse Systems (SIGMOD ‘22). Association for Computing Machinery, New York, NY, USA, 2326–2339. https://doi.org/10.1145/3514221. 3526054
- 6 Philip A. Bernstein and Nathan Goodman. 1981. Concurrency Control in Distributed Database Systems. ACM Computing Survey 13, 2 (1981), 185–221. https://doi.org/10.1145/356842.356846
- 7 Spyros Blanas, Yinan Li, and Jignesh M. Patel. 2011. Design and evaluation of main memory hash join algorithms for multi-core CPUs. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data (Athens, Greece) (SIGMOD ‘11). Association for Computing Machinery, New York, NY, USA, 37–48. https://doi.org/10.1145/1989323.1989328
- 8 Daniel Gomez Blanco. 2023. Practical OpenTelemetry. Springer Nature.
- 9 Burton H. Bloom. 1970. Space/Time Trade-Ofs in Hash Coding with Allowable Errors. Commun. ACM 13, 7 (1970), 422–426. https://doi.org/10.1145/362686. 362692
- 10 Peter Boncz, Thomas Neumann et Orri Erling. 2014. TPC-H Analyzed: Hidden Messages and Lessons Learned from an Infuential Benchmark. In Performance Characterization and Benchmarking. 61–76. https://doi.org/10.1007/978-3-319- 04936-6_5
- 11 Peter Boncz, Marcin Zukowski, and Niels Nes. 2005. MonetDB/X100: Hyper-Pipelining Query Execution. In CIDR.
- 12 Martin Burtscher et Paruj Ratanaworabhan. 2007. High Throughput Compression of Double-Precision Floating-Point Data. In Data Compression Conference (DCC). 293–302. https://doi.org/10.1109/DCC.2007.44
- 13 Jef Carpenter et Eben Hewitt. 2016. Cassandra: The Defnitive Guide (2nd ed.). O’Reilly Media, Inc.
- 14 Bernadette Charron-Bost, Fernando Pedone et André Schiper (dir.). 2010. Replication: Theory and Practice. Springer-Verlag.
- 15 chDB. 2024. chDB - un moteur SQL OLAP embarqué. Consulté le 2024-06-20 à l’adresse https://github.com/chdb-io/chdb
- 16 ClickHouse. 2024. ClickBench: a Benchmark For Analytical Databases. Consulté le 20/06/2024 sur https://github.com/ClickHouse/ClickBench
- 17 ClickHouse. 2024. ClickBench: Comparative Measurements. Consulté le 20/06/2024 sur https://benchmark.clickhouse.com
- 18 ClickHouse. 2024. ClickHouse Roadmap 2024 (GitHub). Consulté le 2024-06-20 à l’adresse https://github.com/ClickHouse/ClickHouse/issues/58392
- 19 ClickHouse. 2024. Benchmark des versions de ClickHouse. Consulté le 2024-06-20 à l’adresse https://github.com/ClickHouse/ClickBench/tree/main/versions
- 20 ClickHouse. 2024. Résultats du benchmark des versions de ClickHouse. Consulté le 20/06/2024 sur https://benchmark.clickhouse.com/versions/
- 21 Andrew Crotty. 2022. MgBench. Consulté le 2024-06-20 à l’adresse https://github.com/ andrewcrotty/mgbench
- 22 Benoit Dageville, Thierry Cruanes, Marcin Zukowski, Vadim Antonov, Artin Avanes, Jon Bock, Jonathan Claybaugh, Daniel Engovatov, Martin Hentschel, Jiansheng Huang, Allison W. Lee, Ashish Motivala, Abdul Q. Munir, Steven Pelley, Peter Povinec, Greg Rahn, Spyridon Triantafyllis, et Philipp Unterbrunner. 2016. The Snowfake Elastic Data Warehouse. Dans les actes de la conférence internationale de 2016 sur la gestion des données (San Francisco, Californie, États-Unis) (SIGMOD ‘16). Association for Computing Machinery, New York, NY, USA, 215–226. https: //doi.org/10.1145/2882903.2903741
- 23 Patrick Damme, Annett Ungethüm, Juliana Hildebrandt, Dirk Habich, et Wolfgang Lehner. 2019. From a Comprehensive Experimental Survey to a Cost-Based Selection Strategy for Lightweight Integer Compression Algorithms. ACM Trans. Database Syst. 44, 3, article 9 (2019), 46 pages. https://doi.org/10.1145/3323991
- 24 Philippe Dobbelaere et Kyumars Sheykh Esmaili. 2017. Kafka versus RabbitMQ : étude comparative de deux implémentations industrielles de référence du modèle publication/abonnement : article industriel (DEBS ‘17). Association for Computing Machinery, New York, NY, USA, 227–238. https://doi.org/10.1145/3093742.3093908
- 25 Documentation de LLVM. 2024. Auto-vectorisation dans LLVM. Consulté le 2024-06-20 à l’adresse https://llvm.org/docs/Vectorizers.html
- 26 Siying Dong, Andrew Kryczka, Yanqin Jin et Michael Stumm. 2021. RocksDB: Evolution of Development Priorities in a Key-value Store Serving Large-scale Applications. ACM Transactions on Storage 17, 4, article 26 (2021), 32 pages. https://doi.org/10.1145/3483840
- 27 Markus Dreseler, Martin Boissier, Tilmann Rabl, and Matthias Ufacker. 2020. Quantifying TPC-H choke points and their optimizations. Proc. VLDB Endow. 13, 8 (2020), 1206–1220. https://doi.org/10.14778/3389133.3389138
- 28 Ted Dunning. 2021. The t-digest: efficient estimates of distributions. Software Impacts 7 (2021). https://doi.org/10.1016/j.simpa.2020.100049
- 29 Martin Faust, Martin Boissier, Marvin Keller, David Schwalb, Holger Bischof, Katrin Eisenreich, Franz Färber, et Hasso Plattner. 2016. Footprint Reduction and Uniqueness Enforcement with Hash Indices in SAP HANA. In Database and Expert Systems Applications. 137–151. https://doi.org/10.1007/978-3-319-44406- 2_11
- 30 Philippe Flajolet, Eric Fusy, Olivier Gandouet et Frederic Meunier. 2007. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. In AofA: Analysis of Algorithms, vol. AH des actes DMTCS, 2007 Conference on Analysis of Algorithms (AofA 07). Discrete Mathematics and Theoretical Computer Science, 137–156. https://doi.org/10.46298/dmtcs.3545
- 31 Hector Garcia-Molina, Jefrey D. Ullman, et Jennifer Widom. 2009. Database Systems - The Complete Book (2. Ed.).
- 32 Pawan Goyal, Harrick M. Vin, and Haichen Chen. 1996. Ordonnancement équitable à temps de démarrage : un algorithme d’ordonnancement pour les réseaux à commutation de paquets à services intégrés. 26, 4 (1996), 157–168. https://doi.org/10.1145/248157.248171
- 33 Goetz Graefe. 1993. Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25, 2 (1993), 73–169. https://doi.org/10.1145/152610.152611
- 34 Jean-François Im, Kishore Gopalakrishna, Subbu Subramaniam, Mayank Shrivastava, Adwait Tumbde, Xiaotian Jiang, Jennifer Dai, Seunghyun Lee, Neha Pawar, Jialiang Li, et Ravi Aringunram. 2018. Pinot: Realtime OLAP for 530 Million Users. Dans les actes de l’International Conference on Management of Data 2018 (Houston, TX, USA) (SIGMOD ‘18). Association for Computing Machinery, New York, NY, USA, 583–594. https://doi.org/10.1145/3183713.3190661
- 35 ISO/IEC 9075-9:2001 2001. Technologies de l’information — Langage de base de données — SQL — Partie 9 : gestion des données externes (SQL/MED). Norme. Organisation internationale de normalisation.
- 36 Paras Jain, Peter Kraft, Conor Power, Tathagata Das, Ion Stoica et Matei Zaharia. 2023. Analyse et comparaison des systèmes de stockage lakehouse. CIDR.
- 37 Project Jupyter. 2024. Jupyter Notebooks. Consulté le 20/06/2024 sur https: //jupyter.org/
- 38 Timo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo et Peter Boncz. 2018. Everything You Always Wanted to Know about Compiled and Vectorized Queries but Were Afraid to Ask. Proc. VLDB Endow. 11, 13 (sept. 2018), 2209–2222. https://doi.org/10.14778/3275366.3284966
- 39 Changkyu Kim, Jatin Chhugani, Nadathur Satish, Eric Sedlar, Anthony D. Nguyen, Tim Kaldewey, Victor W. Lee, Scott A. Brandt, et Pradeep Dubey. 2010. FAST: fast architecture sensitive tree search on modern CPUs and GPUs. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (Indianapolis, Indiana, USA) (SIGMOD ‘10). Association for Computing Machinery, New York, NY, USA, 339–350. https://doi.org/10.1145/1807167.1807206
- 40 Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley.
- 41 André Kohn, Viktor Leis et Thomas Neumann. 2018. Adaptive Execution of Compiled Queries. Dans les actes de la 34e conférence internationale IEEE sur l’ingénierie des données (ICDE), 2018. 197–208. https://doi.org/10.1109/ICDE.2018.00027
- 42 Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan, Nga Tran, Ben Vandiver, Lyric Doshi et Chuck Bear. 2012. La base de données analytique Vertica : C-Store, sept ans plus tard. Proc. VLDB Endow. 5, 12 (août 2012), 1790–1801. https://doi.org/10. 14778/2367502.2367518
- 43 Harald Lang, Tobias Mühlbauer, Florian Funke, Peter A. Boncz, Thomas Neumann, et Alfons Kemper. 2016. Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation. Dans les actes de l’International Conference on Management of Data 2016 (San Francisco, Californie, États-Unis) (SIGMOD ‘16). Association for Computing Machinery, New York, NY, USA, 311–326. https://doi.org/10.1145/2882903.2882925
- 44 Viktor Leis, Peter Boncz, Alfons Kemper, et Thomas Neumann. 2014. Morseldriven parallelism: a NUMA-aware query evaluation framework for the manycore age. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (Snowbird, Utah, USA) (SIGMOD ‘14). Association for Computing Machinery, New York, NY, USA, 743–754. https://doi.org/10.1145/2588555. 2610507
- 45 Viktor Leis, Alfons Kemper et Thomas Neumann. 2013. The adaptive radix tree: ARTful indexing for main-memory databases. Dans 2013 IEEE 29th International Conference on Data Engineering (ICDE). 38–49. https://doi.org/10.1109/ICDE. 2013.6544812
- 46 Chunwei Liu, Anna Pavlenko, Matteo Interlandi et Brandon Haynes. 2023. Une analyse approfondie des formats ouverts couramment utilisés pour les DBMS analytiques. 16, 11 (juil. 2023), 3044–3056. https://doi.org/10.14778/3611479.3611507
- 47 Zhenghua Lyu, Huan Hubert Zhang, Gang Xiong, Gang Guo, Haozhou Wang, Jinbao Chen, Asim Praveen, Yu Yang, Xiaoming Gao, Alexandra Wang, Wen Lin, Ashwin Agrawal, Junfeng Yang, Hao Wu, Xiaoliang Li, Feng Guo, Jiang Wu, Jesse Zhang, et Venkatesh Raghavan. 2021. Greenplum : une base de données hybride pour des charges de travail transactionnelles et analytiques (SIGMOD ‘21). Association for Computing Machinery, New York, NY, USA, 2530–2542. https: //doi.org/10.1145/3448016.3457562
- 48 Roger MacNicol and Blaine French. 2004. Sybase IQ Multiplex - Designed for Analytics. Dans les actes de la Thirtieth International Conference on Very Large Data Bases - Volume 30 (Toronto, Canada) (VLDB ‘04). VLDB Endowment, 1227–1230.
- 49 Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geofrey Romer, Shiva Shivakumar, Matt Tolton, Theo Vassilakis, Hossein Ahmadi, Dan Delorey, Slava Min, Mosha Pasumansky, et Jef Shute. 2020. Dremel: A Decade of Interactive SQL Analysis at Web Scale. Proc. VLDB Endow. 13, 12 (août 2020), 3461–3472. https://doi.org/10.14778/3415478.3415568
- 50 Microsoft. 2024. Kusto Query Language. Consulté le 2024-06-20 à l’adresse https: //github.com/microsoft/Kusto-Query-Language
- 51 Guido Moerkotte. 1998. Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing. In Proceedings of the 24rd International Conference on Very Large Data Bases (VLDB ‘98). 476–487.
- 52 Jalal Mostafa, Sara Wehbi, Suren Chilingaryan, et Andreas Kopmann. 2022. SciTS: A Benchmark for Time-Series Databases in Scientifc Experiments and Industrial Internet of Things. In Proceedings of the 34th International Conference on Scientifc and Statistical Database Management (SSDBM ‘22). Article 12. https: //doi.org/10.1145/3538712.3538723
- 53 Thomas Neumann. 2011. efficiently Compiling efficient Query Plans for Modern Hardware. Proc. VLDB Endow. 4, 9 (jun 2011), 539–550. https://doi.org/10.14778/ 2002938.2002940
- 54 Thomas Neumann et Michael J. Freitag. 2020. Umbra : un système sur disque offrant des performances en mémoire. Dans les actes en ligne de la 10e Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, Pays-Bas, 12-15 janvier 2020. www.cidrdb.org. http://cidrdb.org/cidr2020/papers/p29-neumanncidr20.pdf
- 55 Thomas Neumann, Tobias Mühlbauer et Alfons Kemper. 2015. Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems. Dans les actes de la 2015 ACM SIGMOD International Conference on Management of Data (Melbourne, Victoria, Australie) (SIGMOD ‘15). Association for Computing Machinery, New York, NY, États-Unis, 677–689. https://doi.org/10.1145/2723372. 2749436
- 56 LevelDB sur GitHub. 2024. LevelDB. Consulté le 2024-06-20 sur https://github. com/google/leveldb
- 57 Patrick O’Neil, Elizabeth O’Neil, Xuedong Chen, and Stephen Revilak. 2009. The Star Schema Benchmark and Augmented Fact Table Indexing. In Performance Evaluation and Benchmarking. Springer Berlin Heidelberg, 237–252. https: //doi.org/10.1007/978-3-642-10424-4_17
- 58 Patrick E. O’Neil, Edward Y. C. Cheng, Dieter Gawlick, et Elizabeth J. O’Neil. 1996. The log-structured Merge-Tree (LSM-tree). Acta Informatica 33 (1996), 351–385. https://doi.org/10.1007/s002360050048
- 59 Diego Ongaro et John Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference (USENIX ATC’14). 305–320. https://doi.org/doi/10. 5555/2643634.2643666
- 60 Patrick O’Neil, Edward Cheng, Dieter Gawlick, et Elizabeth O’Neil. 1996. The Log-Structured Merge-Tree (LSM-Tree). Acta Inf. 33, 4 (1996), 351–385. https: //doi.org/10.1007/s002360050048
- 61 Pandas. 2024. Pandas DataFrames. Consulté le 2024-06-20 à l’adresse https://pandas. pydata.org/
- 62 Pedro Pedreira, Orri Erling, Masha Basmanova, Kevin Wilfong, Laith Sakka, Krishna Pai, Wei He, et Biswapesh Chattopadhyay. 2022. Velox: Meta’s Unified Execution Engine. Proc. VLDB Endow. 15, 12 (aug 2022), 3372–3384. https: //doi.org/10.14778/3554821.3554829
- 63 Tuomas Pelkonen, Scott Franklin, Justin Teller, Paul Cavallaro, Qi Huang, Justin Meza, et Kaushik Veeraraghavan. 2015. Gorilla: A Fast, Scalable, in-Memory Time Series Database. Proceedings of the VLDB Endowment 8, 12 (2015), 1816–1827. https://doi.org/10.14778/2824032.2824078
- 64 Orestis Polychroniou, Arun Raghavan et Kenneth A. Ross. 2015. Repenser la vectorisation SIMD pour les bases de données en mémoire. Dans les actes de la conférence internationale ACM SIGMOD 2015 sur la gestion des données (SIGMOD ‘15). 1493–1508. https://doi.org/10.1145/2723372.2747645
- 65 PostgreSQL. 2024. PostgreSQL - Foreign Data Wrappers. Consulté le 2024-06-20 sur https://wiki.postgresql.org/wiki/Foreign_data_wrappers
- 66 Mark Raasveldt, Pedro Holanda, Tim Gubner, et Hannes Mühleisen. 2018. Fair Benchmarking Considered difficult: Common Pitfalls In Database Performance Testing. Dans les actes du Workshop on Testing Database Systems (Houston, TX, USA) (DBTest’18). Article 2, 6 pages. https://doi.org/10.1145/3209950.3209955
- 67 Mark Raasveldt and Hannes Mühleisen. 2019. DuckDB: An Embeddable Analytical Database (SIGMOD ‘19). Association for Computing Machinery, New York, NY, USA, 1981–1984. https://doi.org/10.1145/3299869.3320212
- 68 Jun Rao et Kenneth A. Ross. 1999. Cache Conscious Indexing for Decision-Support in Main Memory. Dans les actes de la 25e conférence internationale sur les très grandes bases de données (VLDB ‘99). San Francisco, CA, USA, 78–89.
- 69 Navin C. Sabharwal et Piyush Kant Pandey. 2020. Working with Prometheus Query Language (PromQL). Dans Monitoring Microservices and Containerized Applications. https://doi.org/10.1007/978-1-4842-6216-0_5
- 70 Todd W. Schneider. 2022. New York City Taxi and For-Hire Vehicle Data. Consulté le 20/06/2024 sur https://github.com/toddwschneider/nyc-taxi-data
- 71 Mike Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Sam Madden, Elizabeth O’Neil, Pat O’Neil, Alex Rasin, Nga Tran, and Stan Zdonik. 2005. C-Store : un SGBD orienté colonnes. Dans les actes de la 31e conférence internationale sur les très grandes bases de données (VLDB ‘05). 553–564.
- 72 Teradata. 2024. Teradata Database. Consulté le 2024-06-20 à l’adresse https://www. teradata.com/resources/datasheets/teradata-database
- 73 Frederik Transier. 2010. Algorithms and Data Structures for In-Memory Text Search Engines. Thèse de doctorat. https://doi.org/10.5445/IR/1000015824
- 74 Adrian Vogelsgesang, Michael Haubenschild, Jan Finis, Alfons Kemper, Viktor Leis, Tobias Muehlbauer, Thomas Neumann, et Manuel Then. 2018. Get Real: How Benchmarks Fail to Represent the Real World. Dans les actes du Workshop on Testing Database Systems (Houston, TX, USA) (DBTest’18). Article 1, 6 pages. https://doi.org/10.1145/3209950.3209952
- 75 Site web de LZ4. 2024. LZ4. Consulté le 2024-06-20 sur https://lz4.org/
- 76 Site web de PRQL. 2024. PRQL. Consulté le 20/06/2024 sur https://prql-lang.org 77 Till Westmann, Donald Kossmann, Sven Helmer et Guido Moerkotte. 2000. The Implementation and Performance of Compressed Databases. SIGMOD Rec.
- 29, 3 (sept. 2000), 55–67. https://doi.org/10.1145/362084.362137 78 Fangjin Yang, Eric Tschetter, Xavier Léauté, Nelson Ray, Gian Merlino et Deep Ganguli. 2014. Druid: A Real-Time Analytical Data Store. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (Snowbird, Utah, USA) (SIGMOD ‘14). Association for Computing Machinery, New York, NY, USA, 157–168. https://doi.org/10.1145/2588555.2595631
- 79 Tianqi Zheng, Zhibin Zhang, et Xueqi Cheng. 2020. SAHA: A String Adaptive Hash Table for Analytical Databases. Applied Sciences 10, 6 (2020). https: //doi.org/10.3390/app10061915
- 80 Jingren Zhou and Kenneth A. Ross. 2002. Implémentation d’opérations de base de données à l’aide d’instructions SIMD. Dans les actes de la conférence internationale ACM SIGMOD 2002 sur la gestion des données (SIGMOD ‘02). 145–156. https://doi.org/10. 1145/564691.564709
- 81 Marcin Zukowski, Sandor Heman, Niels Nes et Peter Boncz. 2006. Super-Scalar RAM-CPU Cache Compression. In Proceedings of the 22nd International Conference on Data Engineering (ICDE ‘06). 59. https://doi.org/10.1109/ICDE. 2006.150