Base de données orientée colonnes

Une table de données orientée lignes sérialise toutes les valeurs d'une ligne ensemble, puis les valeurs de la ligne suivante, etc.

001:10,Durant,Jacques,40000;
002:12,Dupont,Marie,50000;
003:11,Martin,Jeanne,44000;
004:22,Dupont,Robert,94000;

Lorsque les données sont insérées dans la table, un ID interne leur est attribué, l’identifiant de colonne rowid qui est utilisé en interne dans le système pour faire référence aux données. Dans ce cas, les enregistrements ont des identifiants de colonne séquentiels indépendants de l'empid attribué par l'utilisateur. Dans cet exemple, le SGBD utilise des entiers courts pour stocker les rowid. Dans la pratique, des nombres plus grands, de 64 ou 128 bits, sont normalement utilisés.

Les systèmes orientés ligne sont conçus pour retourner efficacement les données d'une ligne entière, ou enregistrement, en un minimum d'opérations. Cela correspond au cas d'utilisation courant où le système tente de récupérer des informations sur un objet particulier, par exemple les coordonnées d'un utilisateur dans un système rolodex ou des informations sur un produit dans un système de commerce en ligne. En stockant les données de l'enregistrement dans un seul bloc sur le disque, avec les enregistrements associés, le système peut récupérer rapidement les enregistrements avec un minimum d'opérations sur le disque.

Les systèmes orientés ligne ne sont pas efficaces pour effectuer des opérations sur l'ensemble de la table, par opposition à un petit nombre d'enregistrements spécifiques. Par exemple, pour trouver tous les enregistrements de la table d'exemple dont les salaires sont compris entre 40 000 et 50 000, le SGBD devrait parcourir l'ensemble de la table à la recherche d'enregistrements correspondants. Si le tableau d'exemple présenté ci-dessus tient probablement dans un seul bloc de disque, ce n'est pas le cas d'un tableau comportant ne serait-ce que quelques centaines de lignes, et plusieurs opérations sur disque seraient nécessaires pour récupérer les données et les examiner.

Pour améliorer les performances de ce type d'opérations (qui sont très courantes et constituent généralement l'intérêt d'utiliser un SGBD), la plupart des SGBD prennent en charge l'utilisation d'index de base de données, qui stockent toutes les valeurs d'un ensemble de colonnes avec des indicateurs rowid vers la table d'origine.

Un index sur la colonne salaire ressemblerait à ceci:

55000:004; 
60000:001;
80000:002;
94000:003;

Comme ils ne stockent que des éléments de données uniques, plutôt que des lignes entières, les index sont généralement beaucoup plus petits que dans les stockages de la table principale. L'analyse de cet ensemble de données plus petit réduit le nombre d'opérations sur le disque. Si l'index est fortement utilisé, il peut réduire considérablement le temps des opérations courantes. Cependant, la maintenance des index ajoute une surcharge au système, en particulier lorsque de nouvelles données sont écrites dans la base de données. Les enregistrements doivent non seulement être stockés dans la table principale, mais les index qui y sont rattachés doivent également être mis à jour.

La principale raison pour laquelle les index améliorent considérablement les performances sur les grands ensembles de données est que les index des bases de données sur une ou plusieurs colonnes sont généralement triés par valeur, ce qui rend les opérations de requêtes de plage (comme l'exemple ci-dessus "trouver tous les enregistrements dont le salaire est compris entre 40 000 et 50 000") très rapides.

Un certain nombre de bases de données orientées lignes sont conçues pour tenir entièrement dans la mémoire vive, une base de données en mémoire. Ces systèmes ne dépendent pas des opérations sur disque et ont un accès simultané à l'ensemble des données. Cela réduit le besoin d'index, car il faut le même nombre d'opérations pour analyser complètement les données d'origine qu'un index complet à des fins d'agrégation typique. Ces systèmes peuvent donc être plus simples et plus petits, mais ne peuvent gérer que des bases de données qui tiennent en mémoire.

Une base de données orientée colonne organise en série toutes les valeurs d'une colonne, puis les valeurs de la colonne suivante, et ainsi de suite.

Pour notre table d'exemple, les données seraient stockées de cette manière :

10:001,12:002,11:003,22:004;
Durant:001,Dupont:002,Martin:003,Dupont:004;
Jacques:001,Marie:002,Jeanne:003,Robert:004;
40000:001,50000:002,44000:003,94000:004;

Dans cette disposition, n'importe laquelle des colonnes correspond à une structure plus proche d'un index d’un système orienté ligne. Cela peut prêter à confusion et mener à l’opinion erroné qu'une base de données orienté colonne "n'est en fait qu'une" base de données orientées en ligne avec un index sur chaque colonne. Cependant, c'est l’organisation des données qui diffère radicalement. Dans un système orienté ligne, les indices font correspondre les valeurs des colonnes aux numéros de ligne, alors que dans un système orienté colonne, les colonnes font correspondre les numéros de ligne aux valeurs des colonnes[2]. Cela peut sembler subtil, mais la différence peut être observée lors de la modification du stockage dans lequel les deux éléments "Dupont", ci-dessus, sont comprimés en un seul élément avec deux numéros de ligne :

…;Durant:001;Dupont:002,004;Martin:003;…

Le fait qu'un système orienté colonnes soit plus efficace ou non dépend fortement de la charge de travail à automatiser. Les opérations qui récupèrent toutes les données d'un objet donné (la ligne entière) sont plus lentes. Un système orienté ligne peut récupérer la ligne en une seule lecture du disque, alors que de nombreuses opérations sur le disque sont nécessaires pour collecter les données de plusieurs colonnes dans une base de données orientée colonne. Cependant, les opérations sur une rangée entière sont généralement rares.

Dans la majorité des cas, seul un sous-ensemble limité de données est récupéré. Dans une application rolodex, par exemple, il est beaucoup plus courant de collecter les noms et prénoms de plusieurs lignes pour établir une liste de contacts que de lire toutes les données d'une seule adresse. C’est encore plus vrai pour écrire dans la base de données, en particulier si les données ont tendance à être "clairsemés" avec de nombreuses colonnes facultatives. C'est pourquoi les bases de données orientées colonnes ont démontré d'excellentes performances, malgré de nombreux inconvénients théoriques[3].

Le partitionnement, l'indexation, les caches, les vues, les cubes OLAP et les systèmes transactionnels tel que le write ahead logging ou le Multiversion Concurrency Control changent tous drastiquement l'organisation physique des données. Cela dit, les bases de données orientées Processus de transaction en ligne (OLTP) sont principalement orientées ligne, alors que les bases de données Online Analytical Processing (OLAP) sont un équilibre entre l'orientation lignes et l'orientation colonnes.

Les comparaisons entre les bases de données orientées lignes et colonnes portent généralement sur l'efficacité de l'accès au disque dur pour une charge de travail donnée, car le temps de recherche est incroyablement long par rapport aux autres goulots d'étranglement des ordinateurs. Par exemple, un disque dur Serial ATA (SATA) typique a un temps de recherche moyen compris entre 16 et 22 millisecondes[4], alors que l'accès à la DRAM (mémoire vive dynamique) sur un processeur Intel Core i7 prend en moyenne 60 nanosecondes, soit près de 400 000 fois plus vite[5]. Les bases de données en colonnes améliorent les performances en réduisant la quantité de données à lire sur le disque, à la fois en compressant efficacement les données en colonnes similaires et en ne lisant que les données nécessaires pour répondre à la requête.

En pratique, les bases de données en colonnes sont bien adaptées aux charges de travail de type OLAP (Traitement analytique en ligne) (par exemple, les entrepôts de données) qui impliquent généralement des requêtes très complexes sur toutes les données (éventuellement des Pétaoctets). Cependant, l'écriture de données dans une base de données en colonnes nécessite un certain travail. Les transactions (INSERTs) doivent être séparées en colonnes et compressées au fur et à mesure de leur stockage, ce qui la rend moins adaptée aux charges de travail OLTP (Traitement des transactions en ligne). Les bases de données orientées lignes sont bien adaptées aux charges de travail de type OLTP qui sont plus chargées en transactions interactives. Par exemple, la récupération de toutes les données d'une seule ligne est plus efficace lorsque ces données sont situées à un seul endroit (ce qui minimise les recherches sur le disque), comme dans les architectures orientées lignes. Cependant, les systèmes orientés colonnes ont été développés comme des hybrides capables d'effectuer à la fois des opérations OLTP et OLAP. Certaines des contraintes OLTP, auxquelles sont confrontés ces systèmes orientés colonne, sont résolues en utilisant (entre autres qualités) le stockage de données en mémoire[6]. Les systèmes orientés colonne adaptés aux rôles OLAP et OLTP réduisent efficacement l'empreinte totale des données en supprimant le besoin de systèmes séparés[7].

Les données en colonnes sont de type uniforme ; par conséquent, les données en colonnes offrent certaines possibilités d'optimisation de la taille de stockage qui ne sont pas disponibles dans les données en lignes. Par exemple, de nombreux schémas de compression modernes et populaires, tels que LZW (Lempel-Ziv-Welch) ou le codage par plages (run-length encoding), utilisent la similarité des données adjacentes pour les compresser. Les valeurs manquantes et les valeurs répétées, fréquentes dans les données cliniques, peuvent être représentées par un marqueur de deux bits[8]. Bien que les mêmes techniques puissent être utilisées sur des données orientées ligne, une mise en œuvre typique donnera des résultats moins efficaces[2].

Pour améliorer la compression, le tri des lignes peut également être utile. Par exemple, en utilisant des index bitmap, le tri peut améliorer la compression d'un ordre de grandeur[9]. Pour maximiser les avantages de l'ordre lexicographique en matière de compression par rapport au codage par plages, il est préférable d'utiliser des colonnes à faible cardinalité comme premières clés de tri[10]. Par exemple, dans un tableau comportant des colonnes sexe, âge, nom, il serait préférable de trier d'abord sur la valeur sexe (cardinalité de deux), puis âge (cardinalité de <128), puis nom.

La compression en colonnes permet de réduire l'espace disque au détriment de l'efficacité de la récupération. Plus la compression adjacente est importante, plus l'accès aléatoire peut devenir difficile, car les données doivent être décompressées pour être lues. C'est pourquoi les architectures orientées colonnes sont parfois enrichies de mécanismes supplémentaires visant à minimiser le besoin d'accès aux données compressées [11].