Data warehouse I

Week 6

Based on Benoît Groz's slides

Table des matières

Indexation
B-trees
Bitmap Indexes
Bitmap Join Indexes
Jointures et partitionnement
Clustering

Indexation

Indexation dans les SGBD

Objectif des index : accélérer l'accès aux données nécessaires à la requête.

SELECT * FROM Employee WHERE EmployeeKey = 1234;
-- En utilisant un index sur EmployeeKey: 1 accès disque.
-- Sans index : nécessaire de scanner toute la table Employee.

Inconvénient : toute mise à jour d'un attribut indexé impose de mettre à jour l'index.
⇒ maintenir trop d'index aboutit à une dégradation des performances.

Commençons par discuter du concept d'indexation dans les bases de données. L'objectif principal d'un index est d'accélérer l'accès aux données. Cependant, il y a des compromis à prendre en compte lorsque les index sont fréquemment mis à jour, car cela peut dégrader les performances.

Explications :

Expliquez que l'indexation est un équilibre entre des lectures plus rapides et des écritures plus lentes, surtout dans des environnements où les données sont souvent mises à jour. Soulignez comment ce compromis devient une considération clé dans les grandes bases de données comme les entrepôts de données.

Taxonomie des Index

Monocolonne vs multicolonnes
Groupant (ordonné ou clustering) vs non-groupant :
- Dans un index groupant, les tuples sont physiquement ordonnés selon la clé d'index.
- On a au plus 1 index groupant, mais peut avoir plusieurs index non-groupants.
Unique vs non-unique : dans un index unique, il existe un seul tuple pour chaque valeur de la clé: un index non-unique permet à plusieurs tuples de partager la même valeur de clé.
Dense vs épars : un index dense a une entrée pour chaque tuple, un index épars ne référence qu'une partie des enregistrements.

Il existe différents types d'index à prendre en compte, y compris les index monocollonne versus multicollonnes, uniques versus non-uniques, et denses versus épars.

Explications :

Cette diapositive introduit la taxonomie des index, c'est-à-dire les différentes catégories d'index que nous pouvons utiliser dans une base de données. L'un des concepts les plus délicats à saisir ici est la distinction entre index denses et index épars, ainsi que les cas où chaque type est le plus approprié.

Index denses :
Un index dense contient une entrée pour chaque ligne d'une table, ce qui signifie que chaque enregistrement de la table est représenté dans l'index. Cela peut être particulièrement utile lorsque vous avez besoin d'un accès rapide et direct à chaque enregistrement individuel de la table. Par exemple, pour des requêtes fréquentes qui nécessitent d'accéder rapidement à des enregistrements spécifiques ou dans des environnements où chaque enregistrement est important, un index dense est idéal. Cependant, l'inconvénient est que cet index prend plus de place et peut devenir coûteux à maintenir, notamment en cas de modifications fréquentes (insertions, suppressions, mises à jour).
Index épars :
Un index épars, quant à lui, ne contient une entrée que pour certaines lignes, souvent sur la base d'une clé primaire ou d'une colonne spécifiée. Par exemple, il peut n'y avoir des entrées que pour les premières lignes de chaque page de données ou à intervalles réguliers dans la table. Cela réduit la taille de l'index et améliore l'efficacité en termes de stockage et de maintenance, surtout lorsque seules certaines parties des données sont fréquemment consultées. Cependant, cet index est moins précis, car il nécessite parfois de scanner plusieurs lignes pour trouver l'enregistrement spécifique souhaité. Il est donc utilisé lorsque les requêtes ne nécessitent pas un accès immédiat à chaque enregistrement, mais seulement à des plages ou des regroupements de données.

Cas d'utilisation :

Index dense :
Idéal pour des tables de petite ou moyenne taille où chaque ligne doit être accessible de manière individuelle et où les requêtes visent des lignes spécifiques.
Index épars :
Préféré pour les tables très volumineuses où l'accès direct à chaque ligne n'est pas nécessaire, mais où des plages de données sont régulièrement consultées. Cela économise de l'espace et accélère les opérations de maintenance de l'index.

Index et partitions

Index local : les partitions de l'index suivent les partitions de la BD (bijections entre les partitions de la table et de l'index). Facilite la maintenance. Le plus courant en entrepôt.
Index global partitionné : partitions de l'index ne correspondent pas aux partitions de la table. Plutôt OLTP.
Index global non-partitionné : index non partitionné, surtout utilisé pour assurer les contraintes de clé unique. En entrepôt ce rôle peut être assuré par ETL.

Lors du travail avec des partitions, il existe plusieurs types de partitionnement d'index : local, global partitionné, et global non-partitionné.

Explications :

Le partitionnement est une technique clé dans les grandes bases de données, en particulier dans les entrepôts de données, car il permet de diviser les données volumineuses en sections plus petites et plus gérables. Chaque partition peut être gérée séparément, ce qui facilite l'accès, l'organisation et l'optimisation des données. C'est particulièrement utile pour des tables de grande taille, car cela permet d'améliorer les performances des requêtes et de simplifier la maintenance des données.

La partie plus complexe concerne les différences entre index locaux et index globaux, deux stratégies de gestion des index lorsqu'on utilise des partitions :

Index Locaux :

Un index local est un index qui est divisé en partitions de la même manière que la table sous-jacente. Chaque partition de l'index correspond directement à une partition des données. Cela signifie qu'il existe une correspondance parfaite (une bijection) entre les partitions de l'index et celles de la table.

Exemple : Si une table est partitionnée par date (par exemple, par mois), un index local aura une partition d'index pour chaque mois, et cette partition ne contiendra que les entrées d'index relatives aux données de ce mois.

Avantages des index locaux :

Facilité de maintenance : Lorsqu'une partition de la table est supprimée, ajoutée ou modifiée, l'index local correspondant est automatiquement mis à jour ou supprimé, sans affecter les autres partitions. Cela réduit le coût de maintenance, car il n'est pas nécessaire de reconstruire tout l'index globalement.
Performances : Si une requête est limitée à une partition spécifique (par exemple, des données d'une certaine période), seul l'index local de cette partition est utilisé, réduisant ainsi la quantité de données à parcourir.
Simplicité de gestion : L'alignement direct des partitions de l'index avec celles des données permet une gestion plus prévisible et plus simple.

Inconvénients :

Limité par la structure de la table : Puisque l'index local est lié aux partitions de la table, il n'est pas possible d'utiliser un index local si une requête concerne plusieurs partitions en même temps de manière complexe. Cela peut entraîner des scans plus longs si les requêtes ne sont pas bien alignées avec les partitions de l'index.

Index Globaux :

Un index global, contrairement à un index local, n'est pas divisé selon les partitions de la table. L'index global couvre l'intégralité de la table, quelle que soit la manière dont celle-ci est partitionnée. Il contient une entrée pour chaque ligne de la table, indépendamment des partitions.

Exemple : Si une table est partitionnée par mois, un index global couvrira toujours l'ensemble des données, sans distinction des partitions. Cela signifie que l'index global peut être utilisé pour des requêtes qui traversent plusieurs partitions, sans avoir à traiter chaque partition individuellement.

Avantages des index globaux :

Flexibilité : Les index globaux peuvent être utilisés pour des requêtes qui nécessitent d'accéder à des données réparties sur plusieurs partitions, car ils ne sont pas limités à une seule partition. Cela peut être particulièrement utile pour des requêtes complexes qui ne se limitent pas à une seule période ou à une seule catégorie de données.
Moins de fragmentation : Un index global maintient une vue cohérente et continue de toutes les données, ce qui peut réduire le besoin de traiter des partitions distinctes dans certains cas.

Inconvénients :

Maintenance coûteuse : Comme l'index global n'est pas aligné sur les partitions, il doit être mis à jour dans son intégralité lorsque des données sont ajoutées, supprimées ou modifiées dans n'importe quelle partition. Cela signifie que les opérations de maintenance, telles que la suppression de partitions, nécessitent souvent la reconstruction ou la mise à jour complète de l'index global, ce qui peut être coûteux en termes de performances.
Gestion plus complexe : En raison de la couverture de toutes les partitions, les index globaux peuvent être plus difficiles à optimiser, et les coûts de mise à jour peuvent devenir un facteur limitant dans des environnements de grandes bases de données avec des modifications fréquentes.

Cas d'utilisation :

Index local :

Idéal lorsque les requêtes sont généralement confinées à une seule partition, comme les requêtes temporelles (ex. : « afficher les ventes de juin »). Les index locaux sont également préférés lorsque des partitions individuelles sont ajoutées ou supprimées régulièrement, comme dans les systèmes où les anciennes données sont archivées par lot.

Index global :

Plus adapté lorsque les requêtes couvrent plusieurs partitions ou lorsque la structure des partitions ne correspond pas aux requêtes les plus fréquentes. Par exemple, si les requêtes traversent souvent plusieurs périodes de temps, un index global pourrait être plus efficace.

B-trees

Bayer, McCreight '72

Index typique en BD opérationnelle : B-tree (B+).

Caractéristiques :

Entre $m$ et $2m$ clés par noeud (ou moins à la racine).
Les feuilles sont au même niveau (arbre équilibré).

Les B-trees sont une structure d'index typique dans les bases de données opérationnelles. Ils équilibrent les performances en veillant à ce que l'arbre reste équilibré et que tous les nœuds feuille soient au même niveau.

Explications :

Ici, expliquez l'importance des B-trees dans les bases de données relationnelles, où les arbres équilibrés permettent une recherche, une insertion et une suppression efficaces. L'intuition derrière les B-trees est leur temps d'accès logarithmique, ce qui les rend optimaux pour de nombreuses charges de travail de base de données.

B-trees en pratique

La plupart du temps, un arbre $B$ d'ordre $t$ est par un arbre qui satisfait les propriétés suivantes :

Chaque nœud a au plus 2t-1 clés.
Chaque nœud qui n'est ni racine ni feuille possède au moins t-1 clés.
Si l'arbre est non vide, la racine est aussi non vide.
Un nœud qui possède k fils contient k - 1 clefs.
Toutes les feuilles se situent à la même hauteur.

B+-trees (variante la plus utilisée)

Bayer, McCreight '72

Comme B-tree, mais les pointeurs vers les données sont uniquement dans les feuilles.

Caractéristiques :

Les clés sont uniquement dans les feuilles.
Les feuilles peuvent être liées en une liste chaînée.

Les B+-trees sont une variante des B-trees où les pointeurs de données sont uniquement stockés dans les feuilles. Cela les rend plus efficaces pour les requêtes de plages.

Explications :

Les B+-trees sont une variante très couramment utilisée des B-trees standards, et on peut se demander pourquoi cette variante est plus populaire, en particulier dans les environnements tels que les entrepôts de données. La différence fondamentale entre ces deux structures réside dans la manière dont les données sont organisées et accédées dans les nœuds internes et les feuilles.

B-trees standards :

Dans un B-tree standard, les nœuds internes contiennent à la fois les clés d'index et les pointeurs vers les enregistrements de données correspondants. Cela signifie que les données peuvent être directement accessibles à partir de n'importe quel niveau de l'arbre, qu'il s'agisse des nœuds internes ou des feuilles. Bien que cela puisse sembler avantageux, cette structure présente des inconvénients, notamment en termes d'efficacité lors de la navigation dans l'arbre pour certaines opérations comme les requêtes de plages.

B+-trees :

Dans un B+-tree, les nœuds internes ne contiennent que des clés d'index, tandis que les données elles-mêmes ne sont stockées que dans les nœuds feuilles. Les nœuds internes servent donc uniquement à guider la recherche vers les nœuds feuilles, où les données sont réellement stockées. Cette séparation simplifie la structure et présente plusieurs avantages, en particulier pour les requêtes courantes dans les entrepôts de données.

Pourquoi les B+-trees sont préférés :

Séparation des données et des index : Le fait de stocker les données uniquement dans les feuilles permet de rendre les nœuds internes plus légers et plus compacts, ce qui accélère les opérations de recherche. Cela est crucial dans des environnements où les arbres d'indexation peuvent devenir très grands (par exemple, dans les entrepôts de données), car il permet de naviguer plus rapidement dans l'arbre sans avoir à examiner les données à chaque niveau.
Accès séquentiel rapide : Dans les B+-trees, les feuilles sont souvent reliées entre elles sous la forme d'une liste chaînée. Cela permet un accès séquentiel très rapide aux données, en particulier pour les requêtes de plages (par exemple, rechercher toutes les lignes où une colonne a une valeur comprise entre X et Y). Les B+-trees permettent ainsi de parcourir efficacement les données, de feuille en feuille, sans avoir à remonter constamment dans les nœuds internes, contrairement aux B-trees standards. Ce type de requête est courant dans les entrepôts de données, où les utilisateurs interrogent souvent des plages de dates, de produits, ou d'autres attributs.
Optimisation pour les requêtes de plages : Les requêtes de plages sont des requêtes où l'on cherche des données comprises entre deux valeurs spécifiques (par exemple, « rechercher tous les produits vendus entre janvier et mars »). Les B+-trees sont particulièrement efficaces pour ce type de requête, car une fois la feuille de départ trouvée (grâce aux nœuds internes), le parcours des autres feuilles contenant les données dans la plage est linéaire et rapide grâce à la structure chaînée des feuilles. Les B-trees standards, en revanche, ne sont pas aussi optimisés pour cela, car les données étant stockées à différents niveaux, il peut être nécessaire de revenir aux nœuds internes pour accéder à des données supplémentaires.
Meilleure gestion de l'espace : Puisque les B+-trees ne stockent les données que dans les feuilles, les nœuds internes contiennent uniquement les clés d'index et les pointeurs. Cela permet une utilisation plus efficace de l'espace de stockage dans les nœuds internes, rendant l'arbre globalement plus compact et plus facile à maintenir. Cela se traduit par des arbres moins profonds, ce qui accélère les recherches et réduit les accès disque, une optimisation précieuse dans les grandes bases de données.
Rééquilibrage simplifié : Les B+-trees, comme les B-trees, se rééquilibrent automatiquement lorsqu'il y a des insertions ou des suppressions, mais la structure plus simple des B+-trees (où seules les feuilles contiennent les données) rend ce rééquilibrage plus efficace. Ce point est important dans les systèmes où des modifications fréquentes peuvent avoir lieu, comme les mises à jour par lots dans un entrepôt de données.
Adaptabilité aux systèmes OLAP (Online Analytical Processing) : Les entrepôts de données sont souvent utilisés pour des systèmes OLAP, où les requêtes analytiques (qui explorent de grandes quantités de données et demandent souvent des résumés ou des plages) sont prédominantes. Les B+-trees sont mieux adaptés à ces types de requêtes, car leur conception favorise la recherche et la récupération efficace de grands ensembles de données via des scans séquentiels des feuilles.

Résumé des avantages des B+-trees :

Recherche plus rapide et efficace grâce à une navigation plus légère dans les nœuds internes.
Accès séquentiel optimisé pour les requêtes de plages, particulièrement utile dans les entrepôts de données.
Utilisation efficace de l'espace en limitant les données aux nœuds feuilles, ce qui rend les nœuds internes plus compacts.
Adaptabilité aux environnements à grande échelle comme les entrepôts de données, où des requêtes fréquentes et lourdes en termes de données sont exécutées.

B+-trees : index groupant (clustered)

Bayer, McCreight '72

Caractéristique principale : quand la table est triée dans l'ordre de l'index.

B-trees sous Oracle

De quelle sorte d'index s'agit-il ? B/B+ ? Particularités ?

Les B-trees sous Oracle: propriétés

Généralement, une clé d'index associée à un ROWID.
Pour un index composite, possibilité d'effectuer un index skip-scan.
Index clustering factor : mesure la corrélation entre l'ordre de l'index et la répartition des enregistrements dans les blocs de données. Estime le nombre de blocs à lire pour parcourir toute la table dans l'ordre de l'index.

-- Définir un index B-tree
CREATE INDEX cust_gender_adr_idx ON Customers(gender, address);

SELECT * FROM Customers WHERE address = '36 Quai des Orfèvres';

Oracle implémente les B-trees d'une manière légèrement différente. Par exemple, dans Oracle, chaque clé d'index est associée à un ROWID, ce qui aide à localiser les lignes rapidement."

Explications :

L'optimisation des B-trees sous Oracle repose notamment sur l'utilisation des ROWIDs. Ces ROWIDs (Row Identifiers) sont une fonctionnalité spécifique à Oracle qui permet de localiser rapidement les enregistrements dans la base de données. Les ROWIDs jouent un rôle central dans la manière dont Oracle implémente les index, notamment les B-trees, car ils agissent comme des pointeurs directs vers les lignes spécifiques des données stockées dans les blocs physiques. Cela accélère considérablement les recherches.

Qu'est-ce qu'un ROWID ?

Un ROWID est une sorte d'adresse physique qui identifie de manière unique chaque ligne dans une table Oracle. Il contient plusieurs informations essentielles :

Identifiant de fichier : le fichier physique dans lequel la ligne est stockée.
Numéro de bloc : le bloc de données spécifique à l'intérieur de ce fichier.
Position de ligne : la position exacte de la ligne à l'intérieur de ce bloc.

Ces trois éléments combinés permettent à Oracle de localiser directement une ligne dans la base de données, sans avoir à parcourir de nombreuses structures intermédiaires. En d'autres termes, le ROWID indique à Oracle où chercher physiquement l'enregistrement sur le disque.

Pourquoi les ROWIDs améliorent-ils les performances des B-trees ?

Dans les B-trees d'Oracle, chaque entrée d'index (chaque clé) est associée à un ROWID. Cela signifie que lorsqu'une recherche est effectuée dans l'arbre pour localiser une clé spécifique, une fois que la clé est trouvée dans l'index, Oracle utilise immédiatement le ROWID pour accéder directement à l'enregistrement correspondant dans la table. Ce processus est beaucoup plus rapide que dans des systèmes où il est nécessaire de parcourir des pointeurs indirects ou de scanner des portions importantes de la table.

Voici quelques raisons pour lesquelles l'utilisation des ROWIDs dans les B-trees améliore les performances :

Accès direct aux données : Grâce aux ROWIDs, Oracle peut accéder directement à l'emplacement exact de l'enregistrement, ce qui évite d'avoir à scanner l'intégralité d'une table ou de nombreux blocs de données. Dans des bases de données de grande taille, où les tables peuvent contenir des millions de lignes, cela permet de réduire drastiquement le nombre d'opérations d'E/S (entrées/sorties) nécessaires pour trouver un enregistrement.
Optimisation des requêtes de recherche : Lorsque vous exécutez une requête qui utilise un B-tree (par exemple, pour rechercher une valeur spécifique), une fois que la clé est trouvée dans l'index, Oracle n'a pas besoin de passer par des étapes supplémentaires pour retrouver la ligne correspondante. Le ROWID fournit un accès immédiat à la ligne exacte, améliorant ainsi la vitesse de traitement des requêtes.
Efficacité des jointures : Les jointures dans une base de données relationnelle impliquent souvent la recherche de lignes dans une table en fonction des valeurs trouvées dans une autre table. Les ROWIDs jouent ici un rôle crucial dans l'optimisation des jointures, car une fois que les valeurs de jointure sont identifiées, Oracle peut utiliser les ROWIDs pour accéder directement aux enregistrements correspondants dans les autres tables, sans avoir besoin de faire un scan complet.
Index composite et "skip-scan" : Dans les index composites (qui indexent plusieurs colonnes), Oracle peut également utiliser les ROWIDs pour réaliser des skip-scans. Cela signifie qu'il est capable de "sauter" certaines parties de l'index pour accéder directement aux segments pertinents. Par exemple, si une requête ne filtre que sur une des colonnes de l'index composite, Oracle peut parcourir l'index de manière plus intelligente en utilisant les ROWIDs pour éviter de scanner l'index entier.
Moins d'opérations coûteuses : Les ROWIDs réduisent considérablement la charge de travail d'Oracle, car la base de données n'a pas besoin de parcourir les blocs de données de manière séquentielle ou de rechercher les informations dans d'autres index. Le ROWID pointe directement vers la ligne de données, ce qui signifie moins de travail pour le système de gestion de bases de données et, par conséquent, une meilleure performance globale.

Pourquoi on peut trouver les ROWIDs difficiles à comprendre :

Les ROWIDs ne sont pas toujours intuitifs car, contrairement à des concepts plus abstraits comme les clés primaires ou les clés étrangères, un ROWID est très physique et lié à la structure de stockage réelle de la base de données. Les personnes qui ont une expérience limitée avec les bases de données peuvent être plus habitués à penser en termes de modèles logiques (tables, colonnes, lignes) plutôt qu'en termes de blocs de disque et d'adresses physiques. Par conséquent, l'idée qu'une ligne peut être identifiée par son emplacement physique exact (fichier, bloc, position) peut être difficile à saisir.

Voici quelques points pour aider à mieux comprendre les ROWIDs :

Simplification visuelle : Il peut être utile de représenter un ROWID comme une adresse postale : le fichier est comme une rue, le bloc est comme un numéro de maison, et la position de la ligne est comme un appartement. Cela rend la notion plus tangible.
Rôle clé dans la performance : Insistez sur le fait que les ROWIDs permettent un accès direct aux données. Contrairement aux clés primaires, qui sont logiques, les ROWIDs permettent à Oracle d'éviter de longues recherches en allant directement à l'emplacement physique exact d'une ligne.
Utilisation dans les optimisations internes : Soulignez que les ROWIDs ne sont pas seulement un outil de localisation, mais qu'ils sont également utilisés par Oracle pour optimiser diverses opérations, comme les jointures, les scans d'index, et les recherches dans les B-trees.

Résumé des avantages des ROWIDs dans Oracle :

Accès direct et rapide aux enregistrements physiques dans les blocs de données.
Réduction des scans de table et des opérations d'E/S coûteuses.
Optimisation des opérations de recherche et de jointure grâce à la capacité de pointer directement vers des enregistrements spécifiques.
Efficacité accrue dans les environnements où les tables sont volumineuses ou où des jointures complexes sont nécessaires.

B-trees: propriétés

Avantages :

Insertions, mises à jour, suppressions en $O(log_m(n))$.
Indépendant du type de données (exige seulement un ordre).
Doit être rééquilibré si modiﬁcations des données (pas si grave en DW)
Structure à 1 dimension: clé = 1 attribut ou suite d'attributs (ordonnée).
Efficace pour les requêtes d'intervalles et sur clé primaire.

Faiblesses :

Peu approprié pour les requêtes multidimensionnelles.
Inefficace sur les attributs de faible cardinalité.

Par exemple, index sur sexe: 1.000.000 rows, ≈ 50% M/F
⇒ 500.000 accès. Table scan plus rapide.

Les B-trees offrent plusieurs avantages, y compris des insertions et suppressions efficaces. Cependant, ils ne sont pas idéaux pour les requêtes multidimensionnelles ou les attributs à faible cardinalité.

Explications :

Cette diapositive aborde certains inconvénients des B-trees. Le concept le plus difficile à comprendre est pourquoi les B-trees ne fonctionnent pas bien pour les données multidimensionnelles. L'intuition ici est que les B-trees sont optimisés pour les données unidimensionnelles, ce qui signifie qu'ils sont inefficaces lorsque les requêtes impliquent plusieurs attributs.

Besoins d'indexation en entrepôt

Utilisation de l'ETL pour appliquer les contraintes UNIQUE.
Requêtes avec plusieurs filtres dans la clause WHERE et jointures fréquentes entre table de faits et dimensions.

Autres considérations :

Aggregations sur niveaux de hiérarchie.
Données de cubes éparses.
Mises à jour en batch.

⇒ B-tree sera utilisé presque exclusivement pour les colonnes unique.

Les index ROLAP typiques incluent :

Bitmap index
Bitmap join index

Dans un entrepôt de données, les B-trees sont principalement utilisés pour les colonnes uniques. D'autres stratégies d'indexation, comme les index bitmap, sont souvent mieux adaptées pour les requêtes multidimensionnelles.

Explications :

Vous devez comprendre que dans un entrepôt de données, la charge de travail est différente des systèmes OLTP (traitement transactionnel en ligne). Alors que les B-trees fonctionnent bien pour les index uniques, les index bitmap sont plus efficaces lorsque les requêtes impliquent plusieurs filtres, ce qui est typique dans un environnement d'entrepôt.

Bitmap Indexes

Bitmap Index

Idée : coder chaque valeur d'un attribut dans un bitmap (bit-array).

Bitmap index sur attribut $a$ dans relation $R$ ($n$ enregistrements) :

Structure qui stocke un bitmap ($n$ bits) par valeur de $a$
$i^{ème}$ bit = 1 dans le bitmap correspondant à la valeur de $a$ dans le tuple $i$, 0 dans les autres bitmaps.

Book

| BookID | Title            | Binding   | Language |
|--------|------------------|-----------|----------|
| 3240   | Le Petit Prince  | Hardcover | French   |
| 2211   | Winnie the Pooh  | Hardcover | English  |
| 9754   | Paddington Bear  | Paperback | NULL     |
| 4315   | Pinocchio        | Hardcover | Italian  |
| 2368   | Les Vacances     | Paperback | French   |

Bitmap index sur Binding

|           | Hardcover | Paperback |
|-----------|-----------|-----------|
| **Row 1** | 1         | 0         |
| **Row 2** | 1         | 0         |
| **Row 3** | 0         | 1         |
| **Row 4** | 1         | 0         |
| **Row 5** | 0         | 1         |

Représentation binaire

Hardcover: 11010  
Paperback: 00101

Passons maintenant aux index bitmap. Ceux-ci sont très efficaces pour les attributs à faible cardinalité, où chaque valeur possible d'un attribut est représentée par un bitmap.

Explications :

Les index bitmap et les B-trees sont deux types d'index couramment utilisés dans les bases de données, mais ils sont conçus pour traiter des types de données et des charges de travail différents. La principale différence entre ces deux structures réside dans leur manière de stocker et de gérer les données indexées, ainsi que dans leur efficacité pour différents types de requêtes.

Quand les index bitmap surpassent les B-trees traditionnels ?

La partie complexe à saisir est qu'il ne s'agit pas seulement de choisir entre un index bitmap ou un B-tree, mais plutôt de comprendre quand l'un est plus performant que l'autre. En règle générale, les index bitmap surpassent les B-trees dans les situations suivantes :

Attributs avec faible cardinalité (peu de valeurs distinctes) :
Les index bitmap sont particulièrement efficaces lorsque les colonnes à indexer ont un nombre limité de valeurs distinctes, c'est-à-dire une faible cardinalité. Un attribut avec une faible cardinalité signifie que cet attribut n'a que quelques valeurs possibles. Voici quelques exemples :
- Un champ sexe dans une table d'employés avec les valeurs possibles "Homme" et "Femme".
- Un champ statut dans une table de commandes avec des valeurs telles que "En cours", "Terminée", ou "Annulée".
- Un champ booléen oui/non pour indiquer une présence ou une absence.
Dans ces cas, chaque valeur distincte de l'attribut peut être représentée par un bitmap (une série de bits). Chaque bit dans ce bitmap indique si une ligne particulière dans la table contient cette valeur. Par exemple, pour un champ "sexe" avec les valeurs "Homme" et "Femme", vous auriez deux bitmaps :
- Un bitmap pour les hommes, avec un bit "1" pour chaque ligne où la valeur est "Homme", et "0" sinon.
- Un bitmap pour les femmes, avec un bit "1" pour chaque ligne où la valeur est "Femme", et "0" sinon.
Pourquoi c'est efficace ?

Dans ce contexte, l'index bitmap permet d'effectuer des opérations booléennes (comme AND, OR, NOT) très rapidement sur ces bitmaps. Par exemple, pour rechercher toutes les lignes où le sexe est "Homme" et où le statut de commande est "Terminée", il suffit de faire un ET logique (AND) entre les bitmaps des hommes et des commandes terminées. Cette opération sur les bits est extrêmement rapide, car elle est effectuée directement en mémoire, sans avoir à parcourir de nombreux blocs de données comme c'est le cas avec un B-tree.
Colonnes fréquemment utilisées dans des filtres complexes :
Les index bitmap sont également très performants lorsque plusieurs colonnes, chacune avec une faible cardinalité, sont utilisées dans des filtres ou des clauses WHERE complexes. Par exemple, supposons une requête qui filtre sur trois colonnes : sexe (homme/femme), statut de commande (terminée/en cours/annulée), et méthode de paiement (carte, espèces, virement). Avec des index bitmap, les filtres peuvent être appliqués efficacement en combinant plusieurs bitmaps à l'aide d'opérations booléennes.

Exemple :
- Requête : "Trouver tous les hommes dont la commande est terminée et payée par carte.
- L'index bitmap permettra d'exécuter cette requête en faisant un ET logique entre les bitmaps de ces trois attributs (homme, commande terminée, et paiement par carte). Cette opération est extrêmement rapide car elle est réalisée directement en mémoire sur les bitmaps.
Dans les bases de données traditionnelles avec des B-trees, une requête similaire nécessiterait soit :
- De scanner plusieurs index B-tree, ce qui peut être lent si les colonnes sont dispersées dans la table.
- De parcourir de nombreux nœuds dans chaque index B-tree pour appliquer chaque filtre, ce qui nécessite plusieurs lectures disque.
Chargement des données en lecture-intensive (cas des entrepôts de données) :
Les index bitmap sont souvent utilisés dans les entrepôts de données (data warehouses) où la charge de travail est majoritairement en lecture et où les mises à jour sont rares. Dans les systèmes de bases de données transactionnels (OLTP), les B-trees sont généralement préférés pour les opérations fréquentes de lecture et d'écriture, car ils permettent d'insérer, de mettre à jour et de supprimer des lignes de manière efficace. Cependant, dans un environnement OLAP (Online Analytical Processing), où l'accent est mis sur l'exécution de requêtes complexes sur de grandes quantités de données avec de nombreux filtres, les index bitmap deviennent extrêmement utiles.

Exemple d'entrepôt de données :

Dans un entrepôt de données utilisé pour des analyses marketing, vous pouvez avoir des colonnes telles que la région géographique, le type de produit, ou le segment de marché. Ces colonnes ont généralement peu de valeurs distinctes mais sont fréquemment interrogées en combinaison (par exemple, "produits vendus en Europe pour le segment de marché B2B"). Les index bitmap permettent d'exécuter de telles requêtes de manière très efficace.

Pourquoi les B-trees sont moins efficaces dans ces cas :

Les B-trees sont conçus pour gérer des attributs avec une haute cardinalité (beaucoup de valeurs distinctes) et des opérations fréquentes de modification. Cependant, pour des colonnes avec une faible cardinalité, un index B-tree doit parcourir de nombreux nœuds internes avant de trouver les valeurs, ce qui peut devenir inefficace dans les scénarios où plusieurs filtres doivent être appliqués simultanément. De plus, les B-trees sont plus lents pour combiner des filtres complexes car ils nécessitent souvent des scans multiples d'index, ce qui implique plus d'opérations de lecture disque.

Cas d'utilisation typiques des index bitmap :

Bases de données décisionnelles et analytiques :
Dans les entrepôts de données où les requêtes analytiques sont courantes, les index bitmap sont souvent utilisés pour optimiser les requêtes complexes qui combinent plusieurs colonnes à faible cardinalité. Cela inclut des applications comme l'analyse de données financières, la gestion des stocks, ou les systèmes de reporting.
Colonnes avec peu de valeurs distinctes :
Les index bitmap sont idéaux pour les colonnes comme :
- Genre (homme/femme), état civil (marié/célibataire).
- Statuts d'une commande (en cours/terminée/annulée).
- Méthodes de paiement (carte, espèces, virement).
- Catégories de produits (électronique, vêtements, alimentation).

Résumé des avantages des index bitmap :

Efficacité sur les colonnes à faible cardinalité : Les index bitmap sont optimisés pour les attributs ayant peu de valeurs distinctes.
Opérations booléennes rapides : Les bitmaps permettent d'effectuer des opérations AND, OR, NOT directement en mémoire sur les bits, sans devoir parcourir des index complexes.
Optimisation pour les systèmes de lecture-intensive : Les index bitmap sont parfaits pour les environnements OLAP où l'accent est mis sur la lecture de grandes quantités de données.
Combinaison de plusieurs filtres : Ils permettent de combiner efficacement plusieurs conditions de filtre, ce qui est idéal pour les requêtes décisionnelles complexes.

Bitmap compression

Les vecteurs de bits sont épars lorsque l'attribut a une haute cardinalité :

Opportunités pour compression, en particulier RLE (Run-Length Encoding).

Inconvénients :

Compression rend les mises à jour coûteuses.
Il faut décompresser à l'exécution de la requête.
En OLTP, utiliser des bitmaps compressés peut entraîner des verrous sur de nombreux enregistrements.

Les index bitmap peuvent être optimisés davantage grâce à la compression, en particulier lorsque les bitmaps sont épars, ce qui arrive souvent avec des attributs à haute cardinalité.

Explications :

Les index bitmap peuvent prendre beaucoup d'espace de stockage dans les grandes bases de données, surtout lorsqu'ils sont utilisés pour des colonnes avec de nombreuses lignes. Une manière de réduire cet espace est d'utiliser une technique de compression comme le Run-Length Encoding (RLE), qui permet de compresser les bitmaps en représentant de longues séquences de bits identiques de manière plus concise.

Qu'est-ce que l'encodage par longueurs (RLE) ?

L'encodage par longueurs est une technique de compression qui consiste à remplacer une série de bits consécutifs identiques (que ce soit des "0" ou des "1") par une simple paire de valeurs représentant :

Le bit (0 ou 1).
La longueur de la séquence de ce bit.

Plutôt que de stocker chaque bit individuellement, le RLE compresse ces séquences en ne stockant que la valeur du bit et la longueur de la séquence, ce qui permet d'économiser de l'espace, surtout lorsque le bitmap contient beaucoup de séquences répétitives.

Exemple simple de RLE :

Prenons un bitmap simple représentant les résultats d'une requête :

100000000000000011111

Au lieu de stocker chaque bit individuellement, ce bitmap pourrait être compressé comme suit :

1 : Un "1", suivi de 1 fois.
0 : Un "0", suivi de 15 fois.
1 : Un "1", suivi de 5 fois.

Le résultat compressé serait donc :

(1, 1), (0, 15), (1, 5)

Cette représentation est beaucoup plus compacte que de stocker chaque bit séparément, et c'est ainsi que l'encodage par longueurs peut réduire considérablement la taille des index bitmap, surtout si le bitmap contient de longues séquences de "0" ou de "1".

Pourquoi le RLE est-il efficace dans les index bitmap ?

Compression efficace pour les bitmaps épars :
Les bitmaps épars sont des bitmaps où la majorité des bits sont des "0", avec relativement peu de "1". Cela arrive fréquemment dans les colonnes avec une faible cardinalité (par exemple, un champ "sexe" ou "statut") lorsque la base de données contient beaucoup de lignes. Dans un bitmap épars, le RLE est extrêmement efficace car il peut compresser de longues séquences de "0" en un simple couple indiquant la longueur de la séquence.

Exemple :

Si vous avez une colonne indiquant le statut de commande (en cours, terminée, annulée) dans une grande base de données, avec beaucoup de commandes terminées mais peu de commandes annulées, le bitmap correspondant à "annulée" sera très épars, contenant principalement des "0". Le RLE peut compresser ce bitmap efficacement, car les séquences de "0" peuvent être représentées par des longueurs plutôt que par des bits individuels.
Réduction de l'espace de stockage :
L'encodage par longueurs réduit l'espace de stockage en remplaçant de longues séquences de bits identiques par une description compacte. Cela est particulièrement utile dans les entrepôts de données où les bitmaps peuvent être très volumineux en raison du nombre de lignes dans les tables. Grâce à cette compression, les index bitmap peuvent rester beaucoup plus légers en termes de stockage.

Exemple concret :

Supposons qu'une table de 1 million de lignes ait une colonne avec seulement 3 valeurs possibles. Chaque bitmap associant une valeur pourrait avoir beaucoup de séquences de "0" si les autres valeurs dominent. Avec le RLE, ces séquences de "0" sont compressées, ce qui réduit la taille de l'index.
Adapté aux requêtes de lecture :
L'encodage par longueurs est bien adapté aux entrepôts de données ou aux environnements où les requêtes sont principalement des lectures (OLAP), et où les mises à jour sont peu fréquentes. Dans ces contextes, l'efficacité de la compression l'emporte sur les coûts de gestion associés aux modifications.

Limites du RLE et impact sur les performances lors des mises à jour :

Bien que le RLE soit extrêmement efficace pour compresser les bitmaps dans les environnements de lecture intensive, il présente certains inconvénients lorsqu'il s'agit de mises à jour fréquentes. Voici pourquoi :

Coût des mises à jour :
Le principal inconvénient de l'encodage par longueurs est que les mises à jour des données deviennent plus coûteuses. Lorsqu'une ligne est insérée ou mise à jour dans une table, cela peut entraîner une modification du bitmap, et donc la nécessité de décompresser la séquence de bits concernée, de la modifier, puis de recompresser le bitmap. Ce processus de décompression et de recompression peut être lourd en termes de calcul et entraîner une dégradation des performances.

Exemple :

Si une ligne est insérée dans un bloc où il y avait auparavant une longue séquence de "0", l'encodage RLE doit décompresser cette séquence, insérer un "1" au bon endroit, puis recompresser le reste du bitmap. Cette opération est beaucoup plus coûteuse que dans un B-tree où seules certaines parties de l'arbre doivent être ajustées.
Problèmes de fragmentation :
Les modifications fréquentes des bitmaps (par exemple, des ajouts ou suppressions de lignes) peuvent provoquer une fragmentation des séquences compressées, rendant la compression moins efficace et augmentant la taille de l'index au fil du temps. Cela entraîne des temps d'accès plus longs et nécessite des opérations de maintenance pour recompresser ou réorganiser les bitmaps.
Adapté aux environnements de lecture-intensive :
En raison du coût élevé des mises à jour, l'encodage par longueurs est principalement utilisé dans les entrepôts de données ou d'autres environnements OLAP, où les écritures et les mises à jour sont rares. Dans ces systèmes, la compression RLE permet des gains significatifs en termes de stockage et de performances de requête, mais sans subir le coût des mises à jour fréquentes.

Pourquoi RLE est utilisé dans les entrepôts de données :

Mises à jour peu fréquentes :
Dans les entrepôts de données, la plupart des opérations concernent des lectures pour des analyses ou des rapports, avec très peu de modifications des données sous-jacentes. Dans ce contexte, les inconvénients du RLE liés aux mises à jour sont négligeables comparés aux gains en stockage et en performances de lecture.
Optimisation des requêtes analytiques :
Les requêtes analytiques, typiques des entrepôts de données, impliquent souvent des filtres complexes sur plusieurs colonnes (par exemple, segment de marché, région géographique, etc.). Le RLE permet de stocker les bitmaps de manière compacte, rendant les opérations booléennes (comme AND, OR, NOT) plus rapides, car elles peuvent être effectuées directement sur des bitmaps compressés.

Résumé des avantages et inconvénients du RLE dans les index bitmap :

Avantages :

Réduction de l'espace de stockage : Le RLE permet de compresser efficacement les bitmaps épars, économisant de l'espace dans les environnements avec beaucoup de lignes et peu de valeurs distinctes.
Optimisation pour les lectures : Le RLE est parfaitement adapté aux environnements de lecture-intensive comme les entrepôts de données, où les requêtes analytiques sont fréquentes et les modifications des données sont rares.
Performances accrues des requêtes : Les bitmaps compressés permettent d'accélérer les opérations booléennes sur les données.

Inconvénients :

Coût élevé des mises à jour : Les modifications des bitmaps (ajouts, suppressions, ou mises à jour) nécessitent de décompresser et recompresser les bitmaps, ce qui peut rendre les écritures et les mises à jour beaucoup plus coûteuses.
Fragmentation possible : Des mises à jour fréquentes peuvent provoquer une fragmentation des séquences de bits, réduisant l'efficacité de la compression.

Bitmap Indexes: intérêt

Avantages :

Pas besoin de stocker ROWID : chaque bit-vecteur est plus compact qu'un B-tree.
Les bitmaps sont suffisamment petits pour être stockés en mémoire.
Opérations booléennes sur les bitmaps (AND, OR, XOR, NOT) sont très rapides.
Efficace sur les attributs de faible cardinalité.
Pas trop ineﬃcace sur attributs de haute cardinalité.
Compression efficace pour les vecteurs épars.

Faiblesses :

Maintenance coûteuse : tous les index doivent être mis à jour lors d'une insertion.
L'espace de stockage croît avec les attributs de haute cardinalité.
Coût de décompression.

Les index bitmap présentent plusieurs avantages : ils ne stockent pas de ROWIDs, ils sont compacts et permettent des opérations booléennes rapides. Cependant, ils ont aussi quelques faiblesses, notamment dans les environnements où les mises à jour sont fréquentes.

Explications :

Cette diapositive met en avant pourquoi les index bitmap sont si efficaces dans un contexte d'entrepôt de données. Le point clé est que les index bitmap sont efficaces pour les systèmes à forte charge de lecture, mais peuvent devenir encombrants dans des environnements avec beaucoup de mises à jour en raison de la nécessité de maintenir les bitmaps compressés.

Bitmap index: opérations booléennes

Book

| BookID | Title            | Binding   | Language | Price |
|--------|------------------|-----------|----------|-------|
| 3240   | Le Petit Prince  | Stapled   | French   |35     |
| 2211   | Winnie the Pooh  | Hardcover | English  |40     |
| 9754   | Paddington Bear  | Paperback | NULL     |35     |
| 4315   | Pinocchio        | Stapled   | Italian  |15     |
| 2368   | Les Vacances     | Paperback | French   |40     |

SELECT * FROM Book
WHERE Binding != 'Stapled' 
    AND Price BETWEEN 20 AND 40;

Hardcover: 01000     40: 01001
Paperback: 00101     35: 10100
Stapled: 10010       15: 00010
NOT Stapled: 01101   35 OR 40: 11101
 -----------------------------------
| NOT Stapled AND (35 OR 40): 01101 |
 -----------------------------------

Les index bitmap excellent dans l'exécution des opérations booléennes comme AND, OR et NOT. Par exemple, nous pouvons rapidement filtrer des données en combinant les bitmaps pour différentes conditions.

Explications :

Les opérations booléennes sur les bitmaps sont à la fois simples et rapides, ce qui rend les index bitmap extrêmement puissants pour les requêtes impliquant plusieurs conditions. Veillez à clarifier comment les différents bitmaps sont combinés (par exemple, en utilisant AND pour trouver les lignes qui satisfont toutes les conditions).

Bitmap Join Indexes

Bitmap join index

Objectif : indexer une relation $R$ sur un attribut $a$ d'une autre relation $R'$.

But : précalculer la(les) jointure(s) pour économiser du temps d'exécution.

Stocker un bitmap sur $R$ pour chaque valeur de $n'$.

Sales

| ShopID | BookID | Count |
|--------|--------|-------|
| 1      | 3240   | 2     |
| 1      | 2368   | 1     |
| 2      | 3240   | 4     |
| 2      | 9754   | 8     |
| 2      | 2211   | 5     |
| 3      | 9754   | 3     |

Book

| BookID | Title            | Binding   | Language |
|--------|------------------|-----------|----------|
| 3240   | Le Petit Prince  | Hardcover | French   |
| 2211   | Winnie the Pooh  | Hardcover | English  |
| 9754   | Paddington Bear  | Paperback | NULL     |
| 4315   | Pinocchio        | Hardcover | Italian  |
| 2368   | Les Vacances     | Paperback | French   |

Bitmap (join) index sur Sales de l'attribut Binding:

Hardcover: 101010
Paperback: 010101

Les index de jointure bitmap nous permettent de pré-calculer des jointures, ce qui peut réduire de manière significative le temps d'exécution des requêtes en évitant de recalculer les jointures à la volée.

Explications :

On peut avoir du mal à comprendre le concept d'un index de jointure. Au lieu de calculer les jointures au moment de la requête, un index de jointure stocke le résultat de la jointure à l'avance. Cela est particulièrement utile dans des environnements comme les entrepôts de données, où les jointures entre les tables de faits et de dimensions sont courantes.

Bitmap/JOIN indexes sous Oracle

Exemples de commandes SQL :

-- Bitmap index
CREATE BITMAP INDEX binding_ix ON Book(binding);

-- Bitmap join index
CREATE BITMAP JOIN INDEX binding_bjix ON Sales(Book.binding) 
    FROM Sales, Book WHERE Sales.BookID = Book.BookID;

Note : JOIN INDEX ≠ INDEX JOIN

Dans Oracle, nous pouvons créer des index de jointure bitmap pour stocker efficacement le résultat d'une jointure entre deux tables. Cela est particulièrement utile dans les schémas en étoile, où les jointures entre les tables de faits et de dimensions sont fréquentes.

Explications :

La difficulté ici est de comprendre comment l'implémentation d'Oracle diffère. Expliquez que, bien que les index de jointure traditionnels soient rares dans les systèmes OLTP, ils sont essentiels dans les entrepôts de données en raison du grand nombre de jointures entre les tables de faits et de dimensions.

Jointures et partitionnement

Requêtes en étoile

Requêtes typiques en entrepôt : joignent une grande table de faits avec plusieurs petites tables de dimensions.

Les jointures traditionnelles dans les SGBD se calculent par paires, l'optimiseur choisit l'ordre des jointures pour minimiser la taille des résultats intermédiaires.

Problème : la seule table liée aux autres est la table des Faits.

Approche alternative : calculer d'abord le produit cartésien des dimensions filtrées, puis joindre avec les faits. Plus efficace avec des prédicats très sélectifs.

Bitmap indexes/ bitmap join indexes permettent optimiser de telles requêtes.

Dans un schéma en étoile, les requêtes impliquent souvent la jointure d'une grande table de faits avec plusieurs petites tables de dimensions. Les index de jointure bitmap sont particulièrement utiles ici pour optimiser ces requêtes.

Explications :

Les requêtes en étoile sont courantes dans les entrepôts de données et peuvent être très lentes si elles ne sont pas correctement optimisées. La partie la plus complexe est de comprendre que les opérations de jointure traditionnelles sont calculées par paires, tandis que les index de jointure bitmap permettent de pré-calculer plusieurs jointures, ce qui réduit considérablement le temps d'exécution des requêtes.

Requêtes en étoile (2)

Exemple :

10.000.000 tuples de ventes.
Requête sélectionne 10 stores (parmi 100), 50 produits (parmi 1000), 20 jours (parmi 1000).
Répartition uniforme des ventes parmi stores, etc.

Nous avons ici un exemple typique de requête en étoile dans un entrepôt de données. Nous travaillons avec 10 millions de tuples de ventes, et la requête sélectionne 10 magasins parmi 100, 50 produits parmi 1000, et 20 jours parmi 1000. La répartition des ventes est uniforme entre les magasins, les produits, et les dates.

Dans cette représentation, nous voyons comment la requête se décompose en une série de sélections et de jointures sur les tables de dimensions, telles que 'Store', 'Product', et 'Date', avant de joindre les résultats avec la table des faits 'Sales'.

Les deux arbres

Les deux arbres dans l'image représentent **deux manières différentes** de structurer et d'exécuter la requête en étoile, mais ils ont des différences importantes dans l'ordre et l'optimisation des opérations. Voici une explication détaillée de la différence entre ces deux arbres :

1. Premier arbre (à gauche)

Structure :

Cet arbre commence par appliquer les sélections sur les tables de dimensions avant de faire les jointures avec la table des faits ('Sales').
- Sélection des magasins où country = 'France' dans la table 'Store'.
- Sélection des produits où product = 'BD' dans la table 'Product'.
- Sélection des dates où month = 'jan 15' dans la table 'Date'.
Après avoir appliqué ces sélections sur les dimensions, les résultats filtrés des dimensions sont ensuite rejoints (via des jointures naturelles ⨝) avec la table de faits 'Sales'.

Interprétation et optimisation :

Pré-filtrage des dimensions : Dans ce premier arbre, les sélections sont appliquées avant les jointures. Cela signifie que les tables de dimensions sont filtrées en premier, avant d'être jointes à la table de faits. Cela permet de réduire la taille des données à manipuler dès le début, car seules les données pertinentes des dimensions sont jointes à la table de faits.
Avantage : Cette méthode est plus efficace dans les situations où la table de faits est très volumineuse (comme dans les entrepôts de données), car elle minimise le nombre de tuples à examiner lors des jointures. En filtrant les tables de dimensions en amont, il y a moins de données à manipuler dans la table de faits lors de la jointure.

2. Deuxième arbre (à droite)

Structure :

Dans ce deuxième arbre, les jointures sont exécutées avant d'appliquer les sélections.
- Les tables 'Store', 'Product', et 'Date' sont d'abord jointes à la table 'Sales' sans filtrage préalable.
- Ensuite, les sélections sont appliquées aux résultats des jointures.
  - Sélection des magasins où country = 'France'.
  - Sélection des produits où product = 'BD'.
  - Sélection des dates où month = 'jan 15'.

Interprétation et optimisation :

Jointures avant filtrage : Ici, l'optimisation des sélections est retardée jusqu'à après la jointure. Cela signifie que toutes les lignes des dimensions sont d'abord jointes avec la table de faits, puis les conditions de sélection sont appliquées après la jointure.
Désavantage : Cette approche est généralement moins efficace que la première, car elle implique de joindre plus de données dès le départ (sans filtrage). En joignant d'abord toutes les lignes des dimensions, y compris celles qui ne correspondent pas aux critères de la requête, vous augmentez la quantité de données à manipuler, ce qui peut ralentir la requête. Ensuite, les sélections réduisent enfin le résultat, mais après un traitement de données inutilement volumineux.

Résumé des différences :

Premier arbre (à gauche) :
- Les sélections sont appliquées en premier sur les dimensions, ce qui permet de réduire le nombre de données à manipuler avant les jointures avec la table des faits. Cela améliore l'efficacité de la requête en limitant les jointures à des données filtrées.
Deuxième arbre (à droite) :
- Les jointures sont effectuées d'abord, sans filtrage préalable des dimensions. Ensuite, les sélections sont appliquées. Cela entraîne des jointures sur un ensemble de données plus important que nécessaire, ce qui est généralement moins efficace en termes de performances.

Conclusion :

Le premier arbre (à gauche) est plus optimisé pour des entrepôts de données, car il applique les sélections avant les jointures, réduisant ainsi le volume de données manipulé par la table des faits, ce qui est crucial pour les performances dans des systèmes avec des données massives. Le deuxième arbre (à droite), en revanche, exécute les jointures sans filtrer d'abord les données, ce qui peut entraîner un traitement plus long et plus coûteux en termes de ressources.

Explications :

Explication du schéma en étoile :
Le modèle en étoile est une structure de base de données couramment utilisée dans les entrepôts de données, où une table de faits (ici 'Sales') est entourée de plusieurs tables de dimensions (ici 'Store', 'Product', 'Date'). Chaque table de dimension stocke des informations descriptives sur les entités qui influencent les ventes (magasins, produits, dates), tandis que la table des faits contient les données de transactions réelles.
Importance des sélections sur les dimensions :
Les requêtes en étoile commencent souvent par des sélections sur les tables de dimensions. Dans cet exemple, la requête filtre sur 10 magasins, 50 produits, et 20 jours. Cela signifie que seuls ces enregistrements dans les dimensions pertinentes sont nécessaires pour l'exécution de la requête. Cela permet de réduire la taille de l'ensemble de données à traiter lors de la jointure avec la table des faits.
- Exemple de prédicats appliqués :
  - Sélection des magasins en France : σ country='France'.
  - Sélection des produits d'une catégorie spécifique : σ product='BD'.
  - Sélection des ventes faites en janvier : σ month='jan 15'.
Jointures avec la table des faits (Sales) :
Après avoir appliqué les sélections sur les dimensions, la requête exécute des jointures entre ces dimensions filtrées et la table de faits ('Sales'). Dans les requêtes en étoile, la table des faits est généralement très volumineuse, donc les optimisations de ces jointures sont cruciales pour les performances. Le schéma en étoile permet de pré-filtrer les dimensions, ce qui limite la quantité de données à parcourir dans la table de faits.
- Impact de la répartition uniforme :
  La répartition uniforme des ventes entre les magasins, les produits et les dates simplifie l'analyse des résultats. Cela signifie que les données sont réparties de manière égale, ce qui rend les statistiques des résultats plus prévisibles et plus simples à analyser. Cela peut aussi aider à améliorer l'efficacité des jointures car les données ne sont pas concentrées dans quelques enregistrements.
Optimisation avec les index bitmap :
Dans un entrepôt de données, des index bitmap peuvent être utilisés pour optimiser ces requêtes en étoile. Les index bitmap sont particulièrement efficaces pour filtrer les dimensions avec peu de valeurs distinctes, comme les magasins, les produits ou les dates dans cet exemple. Ces index permettent d'accélérer les jointures avec la table des faits en minimisant le nombre de lignes à examiner.
- Explication des index bitmap :
  Les index bitmap permettent d'associer chaque valeur d'une dimension à un bitmap, un tableau de bits qui indique quelles lignes de la table des faits correspondent à cette valeur. En combinant ces bitmaps pour les différentes dimensions (via des opérations booléennes telles que AND et OR), on peut rapidement identifier les lignes pertinentes dans la table des faits sans parcourir l'ensemble des données.

Requêtes en étoile (Oracle)

Si des index bitmap (ou bitmap join index) sont présents sur toutes les clés étrangères nécessaires dans la table de faits, Oracle peut utiliser la "star transformation".

Étapes :

Sélectionner les tuples pertinents dans la table de faits.
- Utiliser les IDs pertinents des dimensions pour générer un bitmap par FK.
Intersection des bitmaps pour filtrer les faits à joindre aux dimensions.

Paramètre à régler : STAR_TRANSFORMATION_ENABLED = true.

DB2 a une approche similaire, mais utilise un semijoin par dimension avec un B-tree sur les FKs au lieu de bitmaps.

Lors de l'utilisation d'Oracle, les index bitmap et les index de jointure peuvent être combinés pour permettre une 'transformation en étoile'. Cela permet une exécution très efficace des requêtes en étoile.

Explications :

La transformation en étoile d'Oracle est une technique avancée d'optimisation des requêtes. La partie délicate consiste à comprendre comment l'optimiseur sélectionne les données de dimension pertinentes et génère des bitmaps pour filtrer efficacement la table de faits. Soulignez l'importance d'activer le paramètre STAR_TRANSFORMATION_ENABLED pour que cette optimisation fonctionne.

Clustering

Passons au clustering. Le clustering regroupe les enregistrements qui sont fréquemment accédés ensemble, ce qui peut accélérer considérablement l'exécution des requêtes en réduisant les entrées/sorties disque.

Explications :

Le clustering est une technique puissante, mais elle est plus complexe que l'indexation traditionnelle car elle modifie la disposition physique des données. Expliquez que le clustering est souvent utilisé lorsque certains groupes de données sont fréquemment interrogés ensemble, réduisant ainsi le besoin d'accéder à plusieurs blocs sur disque.

Clustered indexes" in Oracle

La plupart du temps, les tables d'une base de données ne sont pas stockées dans un ordre particulier (heap-organized table).

Index-organized-table (Oracle) : un B+-tree contient directement les données de la table, ce qui économise une indirection (le chargement du bloc de donnée).

Autres indexes sur la table ne stockent qu'un logical ROWID.

Exemple de création d'une table organisée par index :

-- Creating an index-organized table
CREATE TABLE FrenchCities (
    zip int PRIMARY KEY, city_name VARCHAR2(20)
)
ORGANIZATION INDEX
MAPPING TABLE; -- optional, creates a table mapping logical rowids
-- the mapping table is necessary to support bitmap indexes

Clusters" in Oracle: Table clusters

Objectif : grouper des tables qui partagent des colonnes et sont souvent interrogées ensemble dans un table cluster.

Index cluster : stocke ensemble (même bloc) les lignes de toutes les tables ayant la même valeur de clé du cluster.
Hash cluster : stocke ensemble les lignes ayant la même valeur de hash sur la clé du cluster.

-- Creating a clustered table
CREATE CLUSTER personnel(department NUMBER(4));

CREATE TABLE dept_10
CLUSTER personnel (department_id)
AS SELECT * FROM employees WHERE department_id = 10;

CREATE CLUSTER personnel(department NUMBER(4))
HASHKEYS 10;
-- HASHKEYS est idéalement à peu près le nb de valeurs unique
-- des options permettent de redéfinir fonction de hash, espace de stockage...

Clusters" in Oracle: Avantages et Faiblesses

Avantages :

Accélère les jointures (moins de blocs à charger).
Économie d'espace (répétition de la clé évitée).

Faiblesses :

Coût de maintenance élevé.
Les scans de tables sont plus lents.

Les clusters de tables ont des avantages clairs, comme une exécution plus rapide des jointures et une réduction du stockage. Cependant, ils ont également un coût de maintenance plus élevé, surtout lorsque les données sont fréquemment mises à jour.

Explications :

Le principal défi ici est de comprendre les compromis. Les clusters améliorent les performances des requêtes mais peuvent ralentir les insertions et mises à jour en raison de la nécessité de maintenir le regroupement physique des enregistrements.

Multidimensional clustering

Un index multicolonne serait coûteux et inutile si l'on ne filtre pas sur un préfixe de la clé.

Le multidimensional clustering stocke des tuples proches sur les colonnes du cluster à proximité.

Linear ordering : ordre lexicographique sur les colonnes du cluster.
Interleaved ordering : ordre défini par la courbe de Lebesgue (Z-curve).

Le clustering multidimensionnel est une technique qui permet de stocker des tuples proches en fonction de plusieurs colonnes du cluster dans une base de données. Contrairement à un index multicolonne traditionnel, qui serait coûteux et peu efficace si l'on ne filtre pas sur un préfixe de la clé, le clustering multidimensionnel garantit que les enregistrements proches sur plusieurs dimensions sont stockés ensemble.

Il existe deux principaux types d'ordonnancement pour ce clustering :

L'ordre linéaire : qui suit un ordre lexicographique classique sur les colonnes du cluster.
L'ordre entrelacé : défini par la courbe de Lebesgue, également connue sous le nom de courbe Z, qui permet de regrouper des points proches dans l'espace multidimensionnel en les intercalant sur plusieurs dimensions.

Explications :

Problème avec les index multicolonnes classiques :
- Les index multicolonnes sont utilisés pour indexer plusieurs colonnes simultanément. Cependant, ces index ne sont efficaces que si les requêtes filtrent en utilisant un préfixe de la clé multicolonne (par exemple, dans un index sur les colonnes `A` et `B`, les requêtes filtrant sur `A` seront optimisées, mais pas nécessairement celles qui ne filtrent que sur `B`).
- Cela signifie que si vous avez besoin de filtrer ou de rechercher sur plusieurs dimensions sans respecter un ordre strict (comme le préfixe d'un index), les index multicolonnes peuvent devenir inefficaces ou coûteux.
Multidimensional Clustering :
- Le clustering multidimensionnel permet de stocker les enregistrements de manière plus efficace pour les requêtes qui filtrent sur plusieurs dimensions à la fois. Il vise à regrouper les enregistrements proches dans un espace multidimensionnel afin que les données fréquemment interrogées ensemble (par exemple, sur plusieurs colonnes) soient physiquement stockées à proximité sur le disque, ce qui réduit le coût des E/S (accès disque).
- Cette approche est particulièrement utile dans des environnements avec de grands volumes de données, comme les entrepôts de données, où les requêtes impliquent souvent plusieurs dimensions simultanément (par exemple, des requêtes sur les ventes par produit, magasin, et période).
Ordre linéaire vs ordre entrelacé (Z-curve) :
- Ordre linéaire (Linear Ordering) : L'ordre linéaire est basé sur un ordre lexicographique traditionnel. Cela signifie que les enregistrements sont ordonnés de manière séquentielle en fonction des colonnes du cluster (par exemple, d'abord sur `A`, puis sur `B`). Cet ordonnancement est simple mais peut être sous-optimal lorsque les données sont distribuées sur plusieurs dimensions et que les requêtes concernent souvent plusieurs colonnes.
- Ordre entrelacé (Interleaved Ordering) : L'ordre entrelacé, basé sur la courbe de Lebesgue ou Z-curve, est une manière plus sophistiquée d'ordonner les enregistrements. Il consiste à entrelacer les bits des valeurs de plusieurs colonnes (dimensions) pour garantir que les enregistrements proches dans plusieurs dimensions sont également proches dans l'espace de stockage.
  - Explication de la courbe Z (Z-curve) : La courbe Z organise les points dans l'espace multidimensionnel en entrelaçant les bits de leurs coordonnées sur chaque dimension. Cela permet de conserver une proximité spatiale dans un espace multidimensionnel en une seule dimension. Par exemple, dans un espace à deux dimensions, les coordonnées `(x, y)` sont converties en une seule valeur de rang en intercalant les bits des deux coordonnées.
    - Exemple :
      - `(1, 1)` devient `11` en binaire, ce qui correspond à `3` en décimal.
      - `(2, 0)` devient `1000` en binaire, ce qui correspond à `8` en décimal.
    En suivant la courbe Z, les points qui sont spatialement proches dans l'espace à deux dimensions restent également proches en termes d'ordre de stockage.
Avantages de la courbe Z :
- L'avantage principal de l'utilisation de la courbe Z est qu'elle permet de préserver la proximité multidimensionnelle lors du stockage sur disque, ce qui améliore l'efficacité des requêtes sur plusieurs dimensions. Par exemple, une requête qui interroge des plages de valeurs sur plusieurs colonnes (dimensions) bénéficiera de cette organisation car les données seront regroupées de manière optimale.
Conclusion :
- En utilisant un ordonnancement linéaire, les enregistrements sont stockés de manière séquentielle selon l'ordre des colonnes, ce qui est efficace pour des requêtes sur une seule dimension principale.
- Avec un ordonnancement entrelacé (courbe Z), les enregistrements proches dans plusieurs dimensions sont stockés ensemble, ce qui est idéal pour les bases de données qui sont interrogées régulièrement sur plusieurs dimensions simultanément, comme dans les entrepôts de données. Cela permet une meilleure gestion de la proximité entre les enregistrements et des performances optimisées pour les requêtes multidimensionnelles.

Création d'une table multidimensionnelle (Oracle)

Réorganisation d'une table en une table groupée

-- Creating an attribute-clustered table
CREATE TABLE sales (
    prod_id NUMBER(6) NOT NULL,
    cust_id NUMBER NOT NULL,
    time_id DATE NOT NULL,
    amount_sold NUMBER(10,2) NOT NULL
)
CLUSTERING BY INTERLEAVED ORDER (time_id, prod_id, cust_id);
-- CLUSTERING BY LINEAR ORDER (time_id, prod_id,cust_id);

Il est possible d'ajouter du clustering d'attributs pour les jointures :

-- Join attribute clustering
ALTER TABLE sales
    ADD CLUSTERING
        sales JOIN product ON (sales.prod_id=products.product_id)
        BY INTERLEAVED ORDER (time_id, product_cat);

Clusters" in Oracle: Avantages du clustering par attribut

Avantages :

Demande moins d'espace que les index.
Réduit les accès en permettant d'accéder directement aux régions pertinentes.
- Sous Oracle : Utilisé avec zone maps, in-memory min/max pruning, et exadata storage indexes.
L'ordre d'entrelacement est (à peu près) indépendant de l'ordre des colonnes.
Permet une meilleure compression des données.

Faiblesses :

Coût élevé, donc non maintenu par oracle après les mises à jour.

Le clustering par attribut réduit l'espace de stockage et peut améliorer les performances en permettant au système d'accéder directement aux régions de données pertinentes.

Explications :

Clustering par attribut dans Oracle : Vue d'ensemble

Le clustering par attribut dans Oracle est une technique qui permet de regrouper les données qui sont fréquemment accédées ensemble, en fonction de certaines colonnes. Cela offre plusieurs avantages par rapport à d'autres techniques comme les index classiques, mais présente également des inconvénients, notamment en termes de coût et de maintenance.

Avantages du clustering par attribut :

Demande moins d'espace que les index :
- Un des avantages principaux du clustering par attribut est qu'il nécessite moins d'espace de stockage que les index classiques. Cela s'explique par le fait que les données sont stockées de manière groupée directement dans la structure physique de la table, ce qui réduit la nécessité d'utiliser des structures d'index externes et volumineuses.
- Contrairement aux index B-tree, qui doivent créer une structure supplémentaire pour chaque clé d'index, le clustering par attribut regroupe directement les lignes similaires sur le disque. Cela économise non seulement de l'espace, mais réduit également les accès disque lorsqu'il est bien optimisé.
Réduction des accès en permettant d'accéder directement aux régions pertinentes :
- Le clustering par attribut permet de stocker des groupes de données proches sur le disque, ce qui réduit le nombre d'opérations d'E/S (entrées/sorties). Cela est particulièrement utile pour les requêtes fréquentes qui filtrent sur les mêmes colonnes, car les données pertinentes sont stockées dans des blocs proches les uns des autres.
- Plutôt que de devoir scanner toute une table ou parcourir un index en plusieurs étapes, Oracle peut accéder directement aux régions pertinentes où les données filtrées sont stockées, ce qui améliore considérablement les performances des requêtes.
Utilisé avec des fonctionnalités avancées sous Oracle :
- Le clustering par attribut fonctionne particulièrement bien lorsqu'il est couplé avec d'autres fonctionnalités d'Oracle, comme :
  - Zone Maps : Les Zone Maps permettent de stocker des informations sur les plages de valeurs (par exemple, la valeur minimale et maximale d'une colonne) dans chaque "zone" de stockage. Cela permet à Oracle d'ignorer les zones de données qui ne contiennent pas les valeurs pertinentes à la requête.
  - In-memory Min/Max Pruning : Dans les systèmes de base de données en mémoire, Oracle utilise le pruning (élagage) Min/Max, où les zones contenant des valeurs non pertinentes (hors des plages demandées) sont automatiquement exclues de la requête. Cela permet une lecture plus rapide des données en ne récupérant que les parties pertinentes.
  - Exadata Storage Indexes : Sur les systèmes Oracle Exadata, les storage indexes permettent de maintenir des métadonnées sur les valeurs stockées dans chaque région de données. Cela permet à Oracle de savoir quelles régions de données peuvent être exclues d'une requête, encore une fois, en fonction des valeurs minimales et maximales présentes dans les blocs de données. Cela améliore les performances de lecture en évitant de lire les données inutiles.
- Résumé : Avec ces fonctionnalités avancées, Oracle est capable d'utiliser le clustering par attribut pour optimiser les performances de lecture en combinant les données regroupées avec des techniques permettant d'éviter l'accès aux zones non pertinentes.
L'ordre d'entrelacement est (à peu près) indépendant de l'ordre des colonnes :
- Un avantage clé du clustering par attribut est qu'il n'impose pas de dépendance stricte entre l'ordre des colonnes dans la table et l'ordre dans lequel les colonnes sont utilisées dans les requêtes. En d'autres termes, l'ordre d'entrelacement des colonnes (comment les colonnes sont utilisées pour regrouper les données) est flexible, permettant à Oracle de maintenir l'efficacité des requêtes même si les colonnes ne sont pas interrogées dans l'ordre strict de leur stockage.
- Cela contraste avec les index multicolonnes classiques, qui exigent souvent que les requêtes respectent un certain ordre pour que l'index soit pleinement utilisé. Avec le clustering par attribut, l'entrelacement permet une plus grande flexibilité dans la manière d'interroger les colonnes.
Permet une meilleure compression des données :
- Le clustering par attribut favorise une compression plus efficace des données. En regroupant des lignes similaires ou connexes dans des blocs adjacents, Oracle peut appliquer des techniques de compression plus agressives. Lorsque les données sont similaires, elles prennent moins de place une fois compressées.
- De plus, des techniques comme l'encodage par longueurs (RLE) ou la compression par dictionnaire deviennent plus efficaces lorsque des données similaires sont regroupées physiquement, car les séquences répétées peuvent être mieux compressées.

Faiblesses du clustering par attribut :

Coût élevé :
- Le clustering par attribut peut être coûteux à mettre en place et à maintenir. En effet, cette technique implique souvent une réorganisation importante des données physiques sur le disque pour garantir que les enregistrements similaires soient stockés ensemble.
- Ce processus de clustering demande des ressources importantes (temps de traitement, espace disque temporaire, etc.) pour être initialement configuré et réorganisé lors de l'ingestion de nouvelles données.
Non maintenu par Oracle après les mises à jour :
- Après des mises à jour ou des insertions dans une table, Oracle ne maintient pas automatiquement le clustering par attribut. Cela signifie que lorsque des données sont modifiées, le regroupement des enregistrements peut être perturbé, ce qui dégrade les performances.
- Pour maintenir les avantages du clustering, des opérations de maintenance régulières sont nécessaires, comme la réorganisation des données, ce qui peut être coûteux en termes de performances et de ressources. C'est pour cette raison que le clustering par attribut est souvent recommandé dans des environnements où les données sont majoritairement en lecture (comme les entrepôts de données) et où les mises à jour sont rares.

Résumé : Avantages et faiblesses du clustering par attribut dans Oracle

Avantages :
- Réduction de l'espace : Moins de stockage requis par rapport aux index classiques.
- Accès optimisé : Accès direct aux régions pertinentes de données, réduisant les E/S.
- Intégration avec des fonctionnalités avancées : Comme les Zone Maps, le Min/Max Pruning, et les Exadata Storage Indexes.
- Ordre d'entrelacement flexible : Indépendant de l'ordre des colonnes dans les requêtes.
- Compression améliorée : Optimisation des techniques de compression grâce au regroupement des données similaires.
Faiblesses :
- Coût de mise en place élevé : Le clustering nécessite beaucoup de ressources pour être initialisé et maintenu.
- Non maintenu après les mises à jour : Les données doivent être réorganisées manuellement après les modifications, ce qui rend cette technique moins adaptée aux systèmes avec des mises à jour fréquentes.

En conclusion, le clustering par attribut est une technique puissante dans Oracle pour optimiser l'accès aux données et réduire l'espace de stockage, mais elle est surtout utile dans des environnements de lecture-intensive où les mises à jour sont rares, comme les entrepôts de données.

Pour aller plus loin

Clusters" dans différents SGBD

Clustering dans différents SGBD :

MySQL (InnoDB) : Clustered index.
PostgreSQL : CLUSTER table (réorganisation unique).
DB2 : Clustered index, MDC (Multidimensional Clustering).
SQL Server : Clustered index, columnstores pour multidimensional clustering.

Note : la Z-curve est aussi utilisée pour des objets spatiaux dans Oracle, SQL Server, et DB2.

Différents systèmes de gestion de bases de données (SGBD) implémentent le clustering de manière différente. Par exemple, MySQL et SQL Server prennent en charge les index clusterisés, tandis que PostgreSQL ne prend en charge qu'une seule réorganisation à la fois.

Explications :

Clustering dans différents systèmes de gestion de bases de données (SGBD)

Le clustering des données est une technique qui permet d'optimiser l'organisation physique des données sur le disque pour améliorer les performances des requêtes, en regroupant les données qui sont souvent accédées ensemble. Cette technique est utilisée dans de nombreux systèmes de gestion de bases de données (SGBD), mais elle est implémentée de manières différentes selon le SGBD.

1. MySQL (InnoDB) : Clustered index

Clustered Index dans InnoDB : InnoDB, le moteur de stockage par défaut de MySQL, utilise des clustered indexes. Un clustered index signifie que les données sont stockées physiquement sur le disque dans l'ordre de l'index primaire. Autrement dit, la table elle-même est organisée selon l'ordre de la clé primaire.

Comment cela fonctionne : Chaque table dans InnoDB possède un clustered index sur la clé primaire, et les lignes sont stockées directement dans cet index. Cela permet d'accéder rapidement aux enregistrements lorsqu'on utilise la clé primaire. Si une table n'a pas de clé primaire explicite, InnoDB en génère une automatiquement.
Avantage : Les requêtes qui filtrent ou trient les données en fonction de la clé primaire bénéficient de performances accrues car les enregistrements sont physiquement ordonnés sur le disque. Cela réduit le nombre d'accès disque nécessaires pour récupérer des données triées ou filtrées par la clé primaire.
Inconvénient : L'utilisation d'un clustered index implique que chaque table ne peut avoir qu'un seul clustered index. De plus, si une requête trie les données en fonction d'une autre colonne que la clé primaire, il n'y a aucun avantage, et les performances peuvent être réduites si les mises à jour ou les insertions nécessitent la réorganisation des données pour maintenir l'ordre de la clé primaire.

2. PostgreSQL : CLUSTER table (réorganisation unique)

CLUSTER dans PostgreSQL : PostgreSQL prend en charge une commande appelée CLUSTER qui permet de réorganiser physiquement une table selon l'ordre d'un index existant. Cela est similaire à un clustered index, mais avec une différence clé : la réorganisation n'est effectuée qu'une seule fois lors de l'exécution de la commande CLUSTER.

Comment cela fonctionne : Lorsqu'une table est "clustered" selon un index, PostgreSQL réorganise les données pour correspondre à l'ordre de l'index. Cependant, contrairement à MySQL ou d'autres systèmes qui maintiennent cet ordre en permanence, PostgreSQL ne maintient pas cet ordre lors des insertions, mises à jour ou suppressions ultérieures. L'utilisateur doit exécuter manuellement la commande CLUSTER pour réorganiser à nouveau la table si nécessaire.
Avantage : Cette approche permet de réorganiser une table pour optimiser certaines requêtes sans imposer la surcharge d'un clustered index maintenu en permanence. Cela peut être utile pour des tables qui sont rarement modifiées et qui nécessitent des performances optimales pour des lectures spécifiques.
Inconvénient : Comme le clustering n'est pas maintenu automatiquement, les performances peuvent se dégrader avec le temps, à mesure que la table est modifiée, jusqu'à ce que la commande CLUSTER soit exécutée à nouveau. Cette approche nécessite donc une maintenance manuelle pour conserver les avantages du clustering.

3. DB2 : Clustered index, MDC (Multidimensional Clustering)

Clustered Index dans DB2 : Comme d'autres SGBD, DB2 prend en charge les clustered indexes, où les données sont organisées sur le disque selon l'ordre d'un index particulier (souvent la clé primaire). Cela permet d'améliorer les performances des requêtes qui accèdent aux données dans l'ordre de l'index.

Multidimensional Clustering (MDC) : Un autre concept avancé dans DB2 est le Multidimensional Clustering (MDC). Le MDC permet de regrouper des données selon plusieurs dimensions simultanément. Cela signifie que DB2 peut organiser les données physiquement sur plusieurs colonnes (par exemple, regrouper des données par produit, magasin et date).

Comment cela fonctionne : Avec MDC, les tables sont divisées en blocs de clustering en fonction de plusieurs dimensions. Ces blocs sont physiquement organisés pour minimiser les E/S lors des requêtes. Cela améliore considérablement les performances des requêtes complexes qui filtrent ou agrègent des données selon plusieurs colonnes à la fois.
Avantage : Le clustering multidimensionnel optimise les performances des requêtes sur plusieurs colonnes en garantissant que les données proches dans plusieurs dimensions sont stockées ensemble. Cela est particulièrement utile dans les entrepôts de données, où les requêtes multidimensionnelles sont fréquentes.
Inconvénient : Le MDC est plus coûteux à maintenir, car les nouvelles insertions ou modifications doivent être organisées dans plusieurs dimensions simultanément, ce qui peut rendre les mises à jour et insertions plus coûteuses.

4. SQL Server : Clustered index, columnstores pour multidimensional clustering

Clustered Index dans SQL Server : SQL Server utilise également des clustered indexes, comme dans MySQL et DB2. Cela signifie que les données dans une table sont stockées dans l'ordre du clustered index (souvent la clé primaire). Il ne peut y avoir qu'un seul clustered index par table, et cet index améliore les performances des requêtes qui filtrent ou trient les données en fonction de cette clé.

Columnstores et Multidimensional Clustering : SQL Server offre également des index en colonnes (columnstore indexes), qui sont particulièrement utiles pour le clustering multidimensionnel dans des environnements OLAP (analytique). Avec un index en colonnes, les données sont organisées en colonnes plutôt qu'en lignes, ce qui améliore les performances des requêtes qui lisent ou agrègent de grandes quantités de données sur plusieurs dimensions.

Comment cela fonctionne : Les columnstores stockent les valeurs des colonnes individuellement plutôt que par ligne. Cela permet de compresser les données plus efficacement et d'améliorer les performances des requêtes analytiques qui nécessitent l'accès à des ensembles de colonnes spécifiques (par exemple, lorsque seules certaines dimensions d'une table sont interrogées).
Avantage : Les columnstores optimisent les requêtes analytiques sur de grandes tables en minimisant les E/S et en améliorant la compression des données. Cela rend SQL Server particulièrement performant pour les entrepôts de données ou les bases de données décisionnelles qui nécessitent des analyses multidimensionnelles.
Inconvénient : Les columnstores ne sont pas toujours efficaces pour les mises à jour fréquentes. Ils sont mieux adaptés aux environnements où les données sont principalement lues (OLAP) plutôt que mises à jour régulièrement.

La Z-curve dans Oracle, SQL Server, et DB2 :

La courbe de Lebesgue (ou Z-curve) est une technique utilisée pour le clustering multidimensionnel dans plusieurs SGBD, y compris Oracle, SQL Server, et DB2. Comme mentionné dans la diapositive précédente, la Z-curve permet de regrouper les points proches dans un espace multidimensionnel en entrelaçant les bits des différentes dimensions, de manière à conserver la proximité spatiale dans un espace linéaire (sur le disque).

Oracle : La Z-curve est utilisée pour organiser des données spatiales ou multidimensionnelles, en particulier dans les index spatiaux ou dans des environnements où des requêtes sur plusieurs colonnes ou dimensions sont courantes.
SQL Server : SQL Server utilise également la Z-curve dans certains types d'index spatiaux ou de clustering multidimensionnel, pour organiser les données efficacement et minimiser les E/S lors des requêtes multidimensionnelles complexes.
DB2 : En plus du Multidimensional Clustering (MDC), DB2 utilise également des courbes comme la Z-curve pour optimiser les requêtes spatiales et multidimensionnelles.

Résumé :

MySQL (InnoDB) : Utilise des clustered indexes où la table est organisée physiquement selon l'ordre de la clé primaire. Avantageux pour des requêtes basées sur la clé primaire, mais limité à un seul index par table.
PostgreSQL : Permet une réorganisation manuelle de la table avec la commande CLUSTER, mais ne maintient pas cet ordre après des insertions/mises à jour.
DB2 : Offre des clustered indexes et le Multidimensional Clustering (MDC), qui permettent d'organiser les données sur plusieurs dimensions simultanément, mais au prix d'une maintenance plus complexe.
SQL Server : Utilise des clustered indexes et des columnstore indexes, qui sont idéaux pour les entrepôts de données et les requêtes multidimensionnelles, mais ne sont pas adaptés aux systèmes à forte charge d'écriture.
La Z-curve : Utilisée dans plusieurs SGBD (Oracle, SQL Server, DB2) pour optimiser l'organisation des données spatiales et multidimensionnelles, en préservant la proximité des données lors de leur stockage.

Ce clustering par attribut est crucial dans les SGBD qui doivent traiter de grandes quantités de données sur plusieurs dimensions, et chaque système implémente cette fonctionnalité de manière spécifique pour maximiser les performances en fonction de ses propres priorités et environnements d'utilisation.

Autres structures de stockage physique

Pour les informations multidimensionnelles ou spatiales :

UB-tree : un B-tree sur Z-order.
R-tree et ses variantes.
Kd-tree.
Grid files.
Multidimensional hashing.

Enfin, examinons quelques structures de stockage alternatives comme les R-trees, kd-trees et les fichiers de grille, qui sont utiles pour les données multidimensionnelles ou spatiales.

Explications :

Introduction : Structures de stockage pour les données multidimensionnelles ou spatiales

Les données multidimensionnelles (ou spatiales) sont des données qui doivent être indexées et stockées en fonction de plusieurs dimensions simultanément. Ces dimensions peuvent être des coordonnées géographiques (latitude, longitude), des périodes temporelles, ou des attributs complexes (comme des produits, des régions et des périodes pour les analyses commerciales). Gérer ces types de données dans des bases de données relationnelles exige des structures de stockage et des index plus sophistiqués que les B-trees classiques, qui sont optimisés pour des recherches unidimensionnelles.

Voici les principales structures de stockage utilisées pour ces types de données, chacune ayant ses propres avantages en fonction des cas d'utilisation.

1. UB-tree : Un B-tree sur Z-order (courbe Z)

UB-tree (Universal B-tree) :
- Le UB-tree est une variante du B-tree classique qui est conçue pour gérer des données multidimensionnelles. Il s'appuie sur le principe de la Z-order (ou Z-curve), qui est une méthode d'entrelacement des bits des différentes dimensions pour transformer une représentation multidimensionnelle en une représentation unidimensionnelle tout en préservant la proximité spatiale.
- Fonctionnement :
  - Les points dans un espace multidimensionnel (par exemple, des points dans un plan en 2D) sont d'abord projetés dans un espace unidimensionnel en utilisant la courbe Z, qui entrelace les bits des coordonnées de chaque dimension.
  - Une fois que les coordonnées ont été converties en un espace linéaire, elles sont indexées à l'aide d'un B-tree. Cela permet d'utiliser un index B-tree classique pour effectuer des recherches efficaces dans l'espace multidimensionnel.
- Avantages :
  - Le UB-tree permet de préserver la proximité spatiale des points dans l'espace multidimensionnel, de sorte que les points proches dans l'espace réel restent également proches dans l'index.
  - Les requêtes de plage (par exemple, trouver tous les points dans une région donnée) peuvent être optimisées grâce à cette structure.
- Cas d'utilisation :
  - Le UB-tree est particulièrement utilisé pour les bases de données géospatiales ou les entrepôts de données nécessitant des recherches sur plusieurs dimensions simultanément. Par exemple, des analyses impliquant des requêtes de plage sur des données géographiques (comme les coordonnées latitude et longitude) peuvent être optimisées avec un UB-tree.

2. R-tree et ses variantes

R-tree (Rectangle-tree) :
- Le R-tree est une structure d'index utilisée pour les données spatiales, comme les points, les lignes et les rectangles. Chaque nœud d'un R-tree représente un rectangle minimal englobant (bounding box) qui contient plusieurs objets spatiaux. Les nœuds peuvent se chevaucher, ce qui permet de stocker des formes géométriques de différentes tailles.
- Fonctionnement :
  - Dans un R-tree, les objets spatiaux sont représentés par des rectangles qui englobent leur espace (en 2D, un rectangle, en 3D, un cuboïde, etc.).
  - Chaque nœud d'un R-tree est un rectangle qui peut contenir des sous-rectangles. Les rectangles de plus haut niveau contiennent des rectangles de plus bas niveau, formant ainsi une hiérarchie.
  - Pour effectuer une recherche, les rectangles contenant les objets d'intérêt sont explorés et comparés à la région de la requête (comme une recherche de points dans une certaine région géographique).
- Avantages :
  - Le R-tree est bien adapté pour les requêtes de proximité spatiale, comme la recherche de tous les objets dans une certaine région géographique.
  - Il est également efficace pour les requêtes de voisinage (par exemple, trouver tous les objets à proximité d'un point donné).
- Variantes du R-tree :
  - R*-tree : Une version améliorée du R-tree qui minimise le chevauchement entre les rectangles pour optimiser les performances.
  - R+-tree : Une variante qui évite le chevauchement des nœuds, ce qui améliore les performances de certaines requêtes mais complique la gestion des mises à jour.
- Cas d'utilisation :
  - Les Systèmes d'Information Géographique (SIG) utilisent fréquemment des R-trees pour indexer des données spatiales comme des cartes, des routes, des bâtiments, etc.
  - Ils sont également utilisés dans des applications de recherche d'images où l'on cherche à comparer des formes géométriques.

3. Kd-tree (K-dimensional tree)

Kd-tree (Arbre k-dimensionnel) :
- Le Kd-tree est une structure d'index utilisée pour organiser des points dans un espace k-dimensionnel. Contrairement à un B-tree qui fonctionne principalement dans un espace unidimensionnel, un Kd-tree permet de diviser l'espace en fonction de plusieurs dimensions à la fois.
- Fonctionnement :
  - Le Kd-tree divise récursivement l'espace en sous-espaces plus petits à chaque niveau de l'arbre, en alternant la dimension utilisée pour le découpage (par exemple, diviser en fonction de l'axe X à un niveau, puis en fonction de l'axe Y au niveau suivant).
  - Chaque nœud de l'arbre stocke un point et divise l'espace en deux sous-espaces : un contenant les points inférieurs à la valeur de la dimension et un contenant les points supérieurs.
- Avantages :
  - Le Kd-tree est particulièrement efficace pour les requêtes de voisinage (par exemple, trouver les points les plus proches dans un espace multidimensionnel).
  - Il est également utile pour les requêtes de plage où l'on recherche des points dans une certaine région d'un espace multidimensionnel.
- Cas d'utilisation :
  - Le Kd-tree est couramment utilisé dans les applications de reconnaissance de formes et de recherche de plus proches voisins (k-nearest neighbors) dans des espaces de grande dimension.
  - Il est également utilisé dans les bases de données géospatiales et pour les requêtes sur des bases de données décisionnelles impliquant plusieurs dimensions.

4. Grid files

Grid files (Fichiers de grille) :
- Les Grid files sont une méthode d'indexation pour organiser des points dans un espace multidimensionnel à l'aide d'une grille régulière. Chaque cellule de la grille peut contenir plusieurs points ou objets, et la recherche d'un point implique de trouver la cellule de la grille correspondante.
- Fonctionnement :
  - L'espace est divisé en une grille régulière, chaque dimension étant découpée en intervalles égaux.
  - Les points sont ensuite placés dans la cellule correspondante de la grille. Pour retrouver un point, il suffit de trouver la cellule de la grille contenant ce point.
  - Chaque cellule de la grille peut pointer vers une région du disque où sont stockés les points.
- Avantages :
- Les Grid files permettent un accès rapide aux points dans un espace multidimensionnel, en particulier lorsque les points sont distribués de manière régulière.
- Ils sont simples à mettre en œuvre et peuvent être très efficaces pour les requêtes qui accèdent directement à certaines zones d'un espace.
Inconvénient :
Si les données sont distribuées de manière irrégulière, certaines cellules peuvent devenir surchargées tandis que d'autres restent vides, ce qui peut entraîner des déséquilibres dans les performances.

Cas d'utilisation :

Les Grid files sont souvent utilisés dans les bases de données spatiales pour des requêtes de proximité ou des requêtes de voisinage.

5. Multidimensional hashing (Hachage multidimensionnel)

Multidimensional hashing (Hachage multidimensionnel) :
- Le hachage multidimensionnel est une méthode d'indexation qui applique une fonction de hachage à plusieurs dimensions pour générer une clé unique. Cette clé peut ensuite être utilisée pour accéder directement à un emplacement sur le disque.
- Fonctionnement :
  - Chaque dimension d'un point dans un espace multidimensionnel est hachée séparément, puis les valeurs de hachage sont combinées pour produire une clé unique qui correspond à une région dans l'espace de stockage.
  - Cela permet de stocker des points dans un espace multidimensionnel de manière directe, sans avoir besoin d'organiser physiquement les données.
- Avantages :
  - Le hachage multidimensionnel permet un accès direct aux données sans nécessiter de parcours d'index ou d'arbre.
  - Il est efficace pour les requêtes qui demandent des points spécifiques dans un espace multidimensionnel.
- Inconvénient :
  - Il est moins efficace pour les requêtes de plage ou les requêtes de voisinage car il ne préserve pas la proximité spatiale. Deux points proches dans un espace multidimensionnel peuvent se retrouver très éloignés dans l'espace haché.
- Cas d'utilisation :
  - Le hachage multidimensionnel est souvent utilisé pour des recherches précises (exact match queries) dans des environnements multidimensionnels où la proximité n'est pas un facteur clé.

Résumé :

UB-tree : Une version multidimensionnelle du B-tree qui utilise la courbe Z pour indexer des points dans un espace multidimensionnel.
R-tree : Utilisé pour les données spatiales, indexant des objets géométriques à l'aide de rectangles englobants. Variantes comme le R*-tree et R+-tree optimisent davantage les performances.
Kd-tree : Conçu pour organiser des points dans un espace k-dimensionnel, efficace pour les requêtes de voisinage et de plage.
Grid files : Utilise une grille régulière pour diviser l'espace et permet un accès rapide aux points en fonction de leurs coordonnées.
Multidimensional hashing : Permet un accès direct aux points hachés dans un espace multidimensionnel, mais moins efficace pour les requêtes de plage.

Ces structures sont cruciales pour les bases de données qui gèrent des données spatiales ou multidimensionnelles, comme les Systèmes d'Information Géographique (SIG) ou les entrepôts de données qui traitent des analyses complexes sur plusieurs dimensions.

Oracle's Zone Maps

IBM DB2 a un outil similaire.

Les zone maps sont des structures d'index qui stockent les valeurs min/max de chaque colonne pour chaque zone.

Efficace lorsque les données sont groupées sur les attributs de la zone map.
Plus compact que les index classiques (granularité = 1 zone au lieu d'un tuple).
Problème : les intervalles de certaines zones peuvent devenir non-fiables après des mises à jour.

Oracle utilise également les zone maps, qui stockent les valeurs minimales et maximales pour chaque zone de données. Cela aide à filtrer rapidement les lignes non pertinentes lors de l'exécution des requêtes.

Explications :

Oracle's Zone Maps : Vue d'ensemble

Les Zone Maps sont une technique d'indexation utilisée dans Oracle (et un outil similaire existe dans IBM DB2) pour améliorer les performances des requêtes dans les bases de données de grande taille, en particulier dans des environnements de lecture-intensive comme les entrepôts de données. Elles permettent d'accélérer les requêtes en stockant des informations sur les plages de valeurs dans des "zones", ce qui permet d'éviter de lire des blocs de données entiers lors de l'exécution des requêtes.

1. Fonctionnement des Zone Maps :

Une zone map stocke les valeurs minimales et maximales pour chaque colonne d'une table dans chaque zone de stockage.
- Chaque zone correspond à un ensemble de blocs physiques sur le disque. Typiquement, une zone regroupe plusieurs blocs (par exemple, 1 Mo de données), et la zone map enregistre les valeurs extrêmes (min et max) pour chaque colonne dans cette zone.
Lorsqu'une requête est exécutée et qu'elle interroge des colonnes pour certaines plages de valeurs, Oracle peut utiliser la zone map pour savoir quelles zones contiennent les valeurs demandées et ignorer celles qui ne les contiennent pas.
- Exemple : Si une requête cherche toutes les lignes où la colonne "date" est comprise entre le 1er janvier et le 31 mars, Oracle consulte la zone map pour voir quelles zones de données contiennent ces valeurs. Si une zone a un min(date) de juillet et un max(date) d'août, cette zone sera ignorée, ce qui permet de gagner du temps en évitant de lire des blocs inutiles.

2. Comparaison avec les index classiques :

Les zone maps fonctionnent différemment des index classiques tels que les B-trees ou les bitmap indexes. Voici quelques différences principales :

Granularité des zone maps :
- Contrairement aux index classiques qui fonctionnent généralement au niveau de chaque ligne (tuple), les zone maps opèrent à une granularité plus grossière, c’est-à-dire au niveau des zones de données (qui regroupent plusieurs blocs de données). Cela signifie que les zone maps sont plus compactes et nécessitent moins d'espace de stockage que les index traditionnels.
- Par exemple, une zone de 1 Mo peut contenir plusieurs milliers de lignes, mais la zone map n'enregistre que les valeurs min et max pour chaque colonne dans cette zone, au lieu de stocker un index pour chaque ligne. Cela réduit considérablement la taille de l'index.
Accès direct aux zones pertinentes :
- Lorsqu'une requête est exécutée, Oracle peut directement consulter la zone map pour identifier les zones pertinentes (celles dont les plages de valeurs contiennent potentiellement les résultats de la requête) et éviter de lire des zones non pertinentes. Cela permet de réduire les E/S (lectures disque), surtout dans les bases de données de grande taille où chaque accès disque coûte cher en termes de performances.
- Cette approche est particulièrement utile lorsque les données sont groupées ou clustérisées par attributs, ce qui permet de regrouper les valeurs similaires dans les mêmes zones, améliorant ainsi l'efficacité des requêtes.
Moins d'espace de stockage :
- Parce que les zone maps opèrent à une granularité plus large (niveau zone au lieu de niveau ligne), elles occupent moins d'espace sur le disque que les index classiques. Dans des environnements où l'optimisation du stockage est importante, les zone maps permettent de réduire la taille des structures d'indexation tout en maintenant de bonnes performances pour les requêtes.

3. Avantages des Zone Maps :

Optimisation des requêtes :
- Lorsqu'une base de données contient des millions (ou milliards) de lignes, parcourir chaque ligne pour évaluer si elle satisfait une condition de requête devient coûteux en termes de performances.
- Les zone maps permettent à Oracle de réduire drastiquement la quantité de données à lire en consultant simplement les plages de valeurs pour chaque zone. Cela est particulièrement efficace pour les requêtes de plage ou les requêtes analytiques où des filtres sur des colonnes comme des dates, des montants ou des catégories sont souvent utilisés.
Plus compactes que les index classiques :
- En stockant les valeurs min et max pour chaque zone, les zone maps permettent de minimiser l'empreinte mémoire et l'espace disque par rapport aux index de granularité fine (comme les B-trees ou bitmap indexes), qui indexent chaque ligne individuellement.
Efficace pour les données groupées :
- Les zone maps sont particulièrement efficaces lorsque les données sont clustérisées ou groupées par certaines colonnes, c'est-à-dire lorsque des plages de valeurs similaires sont stockées dans les mêmes zones. Cela maximise l'efficacité des requêtes de filtre et des analyses, car les zones pertinentes peuvent être identifiées rapidement et avec une grande précision.
- Par exemple, si les données sont groupées par date dans une table de ventes, une requête qui cherche toutes les ventes faites en janvier pourra ignorer toutes les zones qui ne contiennent pas de dates en janvier, améliorant ainsi la vitesse d'exécution.
Intégration avec des technologies Oracle avancées :
- Les zone maps sont souvent utilisées en conjonction avec des fonctionnalités avancées d'Oracle, telles que :
- Oracle Exadata : Oracle Exadata utilise des storage indexes, qui fonctionnent de manière similaire aux zone maps, en stockant des métadonnées sur les plages de valeurs pour optimiser l'accès aux données sur des systèmes de stockage distribués.
- Oracle In-Memory : La technologie Oracle In-Memory utilise des zone maps en mémoire pour effectuer des opérations de pruning (élagage) des blocs qui ne contiennent pas les valeurs pertinentes, ce qui accélère encore davantage les requêtes analytiques.

4. Faiblesses des Zone Maps :

Problèmes de fiabilité après des mises à jour :
- Les zone maps fonctionnent bien dans des environnements où les données sont principalement en lecture et où les mises à jour sont peu fréquentes. Cependant, après des mises à jour ou des insertions fréquentes, les plages min/max des zones peuvent devenir non fiables.
- Problème : Lorsqu'une nouvelle valeur est insérée dans une zone existante, la valeur min ou max de cette zone peut changer, et la zone map doit être mise à jour en conséquence. Si cela n'est pas fait, les intervalles de certaines zones peuvent devenir inexactes, ce qui peut entraîner des erreurs ou des inefficacités dans les requêtes.
- En raison de ce problème, les zone maps nécessitent parfois une réorganisation manuelle des données ou des opérations de maintenance pour s'assurer que les zones reflètent toujours les bonnes plages de valeurs.
Moins adaptées aux environnements à mises à jour fréquentes :
- Les zone maps sont idéalement adaptées aux systèmes de lecture-intensive où les mises à jour sont rares, comme les entrepôts de données. Cependant, dans des environnements où les données sont fréquemment mises à jour, insérées ou supprimées, la gestion des zone maps devient plus complexe et peut réduire leur efficacité.

IBM DB2 : Un outil similaire

IBM DB2 offre un outil similaire aux zone maps d'Oracle. Dans DB2, cette technique est souvent utilisée dans le contexte de Multidimensional Clustering (MDC) ou d'autres types de gestion de données analytiques.

Comme Oracle, DB2 permet de stocker des métadonnées sur les plages de valeurs dans des zones de stockage spécifiques pour éviter de lire des blocs non pertinents lors de l'exécution des requêtes.
L'objectif reste le même : réduire les E/S en évitant de lire les blocs de données qui ne contiennent pas de résultats pertinents pour la requête.

Résumé : Avantages et inconvénients des Zone Maps

Avantages :
- Optimisent les requêtes en réduisant la quantité de données à lire pour chaque requête.
- Stockage compact par rapport aux index classiques, car elles opèrent à une granularité de zone plutôt qu'au niveau ligne.
- Efficaces dans des environnements de lecture-intensive, comme les entrepôts de données.
- Intégration avec des technologies avancées comme Oracle Exadata et Oracle In-Memory.
Inconvénients :
- Problèmes de fiabilité après des mises à jour fréquentes, car les plages min/max doivent être mises à jour en permanence.
- Moins adaptées aux environnements transactionnels où les données sont mises à jour fréquemment.

Les Zone Maps sont donc une solution efficace pour améliorer les performances des requêtes dans les bases de données volumineuses, mais elles doivent être utilisées avec précaution dans des environnements à mise à jour fréquente. Leur efficacité repose principalement sur des données groupées et majoritairement en lecture, comme dans les entrepôts de données.

Résumé

B-trees / B+-trees :

Monocolonne vs Multicolonnes : Ces index peuvent être soit monocolonne (une seule colonne), soit multicolonnes (plusieurs colonnes).
Groupant vs Non-groupant : Les B+-trees peuvent être utilisés comme index groupant (clustered) lorsque la table est triée selon la clé d'index.
Unique vs Non-unique : Les B-trees peuvent supporter des index uniques ou non-uniques.
Dense vs Épars : Les B+-trees sont généralement denses car ils référencent chaque tuple.

Index Bitmap :

Monocolonne vs Multicolonnes : Les index bitmap peuvent être soit monocolonne, soit multicolonnes.
Groupant vs Non-groupant : Les index bitmap sont généralement non-groupants.
Unique vs Non-unique : Les index bitmap sont typiquement utilisés pour des valeurs non-uniques, notamment pour des attributs de faible cardinalité.
Dense vs Épars : Les index bitmap sont en général épars, surtout lorsqu'on utilise des techniques de compression comme l'encodage par longueur de course (RLE).

Index Bitmap de Jointure :

Monocolonne vs Multicolonnes : Les index bitmap de jointure peuvent être multicolonnes puisqu'ils joignent plusieurs tables.
Groupant vs Non-groupant : Ceux-ci sont généralement non-groupants.
Unique vs Non-unique : Ils peuvent être non-uniques puisqu'ils joignent des tables sur des attributs qui ne sont pas nécessairement uniques.
Dense vs Épars : Comme les index bitmap, ils sont généralement épars.

Index Clustered (groupants) :

Monocolonne vs Multicolonnes : Ces index peuvent être soit monocolonne, bien qu'ils soient souvent utilisés avec une seule colonne.
Groupant vs Non-groupant : Ces index sont toujours groupants car les données sont physiquement ordonnées selon l'index.
Unique vs Non-unique : Les index clustered peuvent être uniques ou non-uniques.
Dense vs Épars : Les index clustered sont généralement denses, car chaque tuple est référencé.

Bibliographie

Lecture des plans

EXPLAIN (ANALYZE, FORMAT JSON) ...
Copiez le plan
Allez sur https://tatiyants.com/pev/