Wikipédia

Base de données orientée colonnes

système de gestion de base des données stockant les tableaux de données par colonnes et non par lignes
(Redirigé depuis BDOC)

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Une base de données orientée colonnes est un système de gestion de base de données (SGBD) qui stocke les tableaux de données par colonne et non par ligne.

L'orientation colonne permet un accès plus efficace aux données pour interroger un sous-ensemble de colonnes (en éliminant le besoin de lire les colonnes qui ne sont pas pertinentes), et plus d'options pour la compression des données. La compression par colonne est aussi plus efficace lorsque les données de la colonne se ressemblent. Cependant, elles sont généralement moins efficaces pour insérer de nouvelles données.

L'utilisation pratique d'un stockage en colonnes par rapport à un stockage en lignes diffère peu dans le monde des bases de données relationnelles . Les bases de données en colonnes et en lignes peuvent toutes deux utiliser des langages d'interrogation de base de données traditionnels tels que SQL pour charger des données et effectuer des requêtes. Les bases de données en colonnes et en lignes peuvent devenir l'épine dorsale d'un système pour servir les données aux outils courants d'extract-transform-load (ETL) et de visualisation des données.

Description

modifier

Un système de base de données relationnelle doit présenter ses données sous une forme de table à deux dimensions, en lignes et colonnes, mais ne peut être stockée que sous une forme à une seule dimension.

Par exemple, une base de données pourrait contenir cette table:

RowId EmpId Nom Prénom Salaire
001 10 Durant Jacques 40000
002 12 Dupont Marie 50000
003 11 Martin Jeanne 44000
004 22 Dupont Robert 94000

Cette table simple inclut un identifiant de ligne rowid, un identifiant d'employé empid, des colonnes Nom et Prénom, et un salaire. Ce format bidimensionnel est une abstraction. Dans une mise en œuvre réelle, le matériel de stockage exige que les données soient rangées en colonnes.

Cette table peut être présente dans la mémoire de l'ordinateur (RAM) ou sur son disque dur. Bien que la mémoire RAM et les disques durs fonctionnent différemment, le système d'exploitation les abstrait. Ainsi, la table à deux dimensions vue par l'utilisateur est représentée par le système de gestion de la base de données comme une suite d'octets pour que le système d'exploitation puisse l'écrire en mémoire ou sur le disque.

Les opérations les plus coûteuses impliquant les disques durs sont les fonctions de recherche. Afin d'améliorer les performances globales, les données connexes doivent être stockées de manière à minimiser le nombre de recherches. C'est ce qu'on appelle le principe de localité, et le concept de base apparaît dans des contextes différents. Les disques durs sont organisés en une série de blocs d'une taille fixe, généralement suffisante pour stocker plusieurs lignes de la table. En organisant les données de la table de manière que les lignes s'insèrent dans ces blocs, et en regroupant les lignes apparentées dans des blocs séquentiels, le nombre de blocs qui doivent être lus ou recherchés est le plus souvent minimisé, ainsi que le nombre de recherches.

Une étude de Pinnecke et al.[1] couvre les techniques d'hybridation colonnes/lignes en 2017.

Base de données orientées lignes

modifier

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.

Base de données orientées colonnes

modifier

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.[réf. nécessaire]

Avantages

modifier

Temps d'accès

modifier

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].

Compression

modifier

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].

Historique

modifier

Les bases de données en colonnes ou les fichiers transposés ont été mis en œuvre dès les premiers jours du développement des SGBD. TAXIR a été la première application d'un système de stockage de bases de données orienté colonnes, axé sur la recherche d'informations en biologie[12] en 1969. Des données cliniques provenant de dossiers de patients comportant beaucoup plus d'attributs qu'il n'était possible d'analyser ont été traitées en 1975 et après par un système de base de données orienté temps (TODS). Statistique Canada a mis en œuvre le système RAPID[13] en 1976 et l'a utilisé pour le traitement et l'extraction du recensement canadien de la population et des logements ainsi que pour plusieurs autres applications statistiques. RAPID a été partagé avec d'autres organismes statistiques du monde entier et a été largement utilisé dans les années 1980. Il a continué à être utilisé par Statistique Canada jusqu'aux années 1990.

Une autre base de données orientée colonnes était SPSS[14].

Parmi les anciens progiciels de bases de données orientées colonnes, citons :

Depuis 2004 environ, il existe d'autres implémentations open source et commerciales. MonetDB (en) a été publié sous une licence open source le 30 septembre 2004[15], suivi de près par la défunte C-Store (en).

C-store était un projet universitaire qui a finalement donné naissance, grâce à Michael Stonebraker, membre de l'équipe, à Vertica (en), qu'il a cofondé en 2005[16].

Le projet X100 lié à MonetDB a évolué vers VectorWise (en)[17]. Druid est une base de données orientée colonne qui a été mis en open-source fin 2012 et est maintenant utilisé par de nombreuses organisations[18].

Les SGBD relationnelles classiques peuvent utiliser des stratégies orientées colonnes en mélangeant des tables orientées lignes et des tables orientées colonnes (par exemple Oracle Database qui le réserve aux tables "in memory" via un module payant, ou Microsoft SQL Server avec les index columnstore inclus dans toutes les éditions, mêmes gratuites). Malgré la complexité du SGBD, cette approche s'est avérée précieuse depuis les années 2010 à aujourd'hui. Par exemple, en 2014, Citusdata a introduit des tables orientées colonnes pour PostgreSQL[19] et McObject a ajouté la prise en charge du stockage en colonnes avec la sortie d'eXtremeDB (en) Financial Edition en 2012[20], qui a ensuite été utilisé pour établir une nouvelle norme de performance audité indépendamment par STAC-M3 benchmark.

Exemples de bases de données orientées colonnes

modifier
  • BigTable, la base de données de Google
  • HBase, une base de données s'inspirant des publications de Google sur BigTable
  • IBM Informix Warehouse Accelerator, module intimement couplé avec le moteur OLTP, permettant la transformation des données choisies en base de données orientée colonne, « in memory »
  • Sybase IQ : ASIQ
  • Vertica
  • Oracle Database 12c avec l'option IN-Memory : représentation en mémoire des tables au format colonnes.
  • Microsoft SQL Server, depuis la version 2012 par l'utilisation d'index columnstore ou de tables verticales (clustered columnstore index) disponible en standard.
  • ClickHouse, développé par Yandex
  • Amazon Redshift, la base de données cloud d'Amazon (basée sur la base de données libre PostgreSQL 8.0.2)

Notes et références

modifier
  1. ↑ Marcus Pinnecke, David Broneske, Gabriel Campero Durand et Gunter Saake, « Are Databases Fit for Hybrid Workloads on GPUs? A Storage Engine's Perspective », 2017 IEEE 33rd International Conference on Data Engineering (ICDE), IEEE,‎ (DOI 10.1109/icde.2017.237, lire en ligne, consulté le )
  2. ↑ a et b Daniel J. Abadi, Samuel R. Madden et Nabil Hachem, « Column-stores vs. row-stores », Proceedings of the 2008 ACM SIGMOD international conference on Management of data - SIGMOD '08, ACM Press,‎ (DOI 10.1145/1376616.1376712, lire en ligne, consulté le )
  3. ↑ Daniel J. Abadi, Peter A. Boncz et Stavros Harizopoulos, « Column-oriented database systems », Proceedings of the VLDB Endowment, vol. 2, no 2,‎ , p. 1664–1665 (ISSN 2150-8097, DOI 10.14778/1687553.1687625, lire en ligne, consulté le )
  4. ↑ (en) Manuel Masiero et Achim Roos published, « Western Digital's 4 TB WD4001FAEX Review: Back In Black », sur Tom's Hardware, (consulté le )
  5. ↑ (en) « Development Tools », sur Intel (consulté le )
  6. ↑ Florian Funke, Alfons Kemper et Thomas Neumann, « Compacting transactional data in hybrid OLTP&OLAP databases », Proceedings of the VLDB Endowment, vol. 5, no 11,‎ , p. 1424–1435 (ISSN 2150-8097, DOI 10.14778/2350229.2350258, lire en ligne, consulté le )
  7. ↑ Hasso Plattner, « A common database approach for OLTP and OLAP using an in-memory column database », Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, ACM,‎ (DOI 10.1145/1559845.1559846, lire en ligne, consulté le )
  8. ↑ Stephen Weyl, James Fries, Gio Wiederhold et Frank Germano, « A modular self-describing clinical databank system », Computers and Biomedical Research, vol. 8, no 3,‎ , p. 279–293 (ISSN 0010-4809, DOI 10.1016/0010-4809(75)90045-2, lire en ligne, consulté le )
  9. ↑ Daniel Lemire, Owen Kaser et Kamel Aouiche, « Sorting improves word-aligned bitmap indexes », Data & Knowledge Engineering, vol. 69, no 1,‎ , p. 3–28 (ISSN 0169-023X, DOI 10.1016/j.datak.2009.08.006, lire en ligne, consulté le )
  10. ↑ Daniel Lemire et Owen Kaser, « Reordering columns for smaller indexes », Information Sciences, vol. 181, no 12,‎ , p. 2550–2570 (ISSN 0020-0255, DOI 10.1016/j.ins.2011.02.002, lire en ligne, consulté le )
  11. ↑ Dominik Ślȩzak, Jakub Wróblewski, Victoria Eastwood et Piotr Synak, « Brighthouse », Proceedings of the VLDB Endowment, vol. 1, no 2,‎ , p. 1337–1345 (ISSN 2150-8097, DOI 10.14778/1454159.1454174, lire en ligne, consulté le )
  12. ↑ George F. Estabrook et Robert C. Brill, « The theory of the TAXIR accessioner », Mathematical Biosciences, vol. 5, nos 3-4,‎ , p. 327–340 (ISSN 0025-5564, DOI 10.1016/0025-5564(69)90050-9, lire en ligne, consulté le )
  13. ↑ M.J. Turner, R. Hammond et P. Cotton, « A DBMS For Large Statistical Databases », Fifth International Conference on Very Large Data Bases, 1979. (conférence), IEEE,‎ (DOI 10.1109/vldb.1979.718147, lire en ligne, consulté le )
  14. ↑ Norman H. Nie, SCSS, a user's guide to the SCSS conversational system, McGraw-Hill, (ISBN 0-07-046538-X, 978-0-07-046538-1 et 0-07-046533-9, OCLC 6277729, lire en ligne)
  15. ↑ (en-US) « About Us », sur www.monetdb.org (consulté le )
  16. ↑ Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan et Nga Tran, « The vertica analytic database », Proceedings of the VLDB Endowment, vol. 5, no 12,‎ , p. 1790–1801 (ISSN 2150-8097, DOI 10.14778/2367502.2367518, lire en ligne, consulté le )
  17. ↑ Doug Inkster, Marcin Zukowski et Peter Boncz, « Integration of vectorwise with ingres », ACM SIGMOD Record, vol. 40, no 3,‎ , p. 45–53 (ISSN 0163-5808, DOI 10.1145/2070736.2070747, lire en ligne, consulté le )
  18. ↑ « Druid | Powered by Apache Druid », sur druid.apache.org (consulté le )
  19. ↑ (en) « Contributors to citusdata/cstore_fdw », sur GitHub (consulté le )
  20. ↑ (en-US) « McObject eXtremeDB Financial Edition In-Memory DBMS Breaks Through Capital Markets’ Data Management Bottleneck », sur Bobsguide, (consulté le )

Articles connexes

modifier
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Base_de_données_orientée_colonnes&oldid=219166610 ».