Explication des index SQL, pt. 2

Dans la première leçon de SQL Indexes Explained , nous avons appris à utiliser le tri pour accélérer la récupération des données. Bien que l'exécution de notre requête soit plus rapide après le tri des lignes, le tri implique de lire chaque ligne au moins une fois et de les déplacer. Cela rend la méthode plus lente et moins efficace que la simple lecture séquentielle de la table entière.

La conclusion logique semble être que nous devrions conserver des copies triées — que nous appellerons officiellement index SQL , préfixés par IX_ — d'une table donnée. Les algorithmes de récupération du premier article seraient alors applicables, et nous n'aurions pas besoin de trier le tableau avant de commencer.

L'index en tant que copie triée du tableau

Jetons un coup d'œil à la mise en œuvre littérale de cette idée, en utilisant à nouveau Google Sheets. Notre feuille de calcul de réservation devient une collection de cinq feuilles contenant les mêmes données. Chaque feuille est triée selon différents ensembles de colonnes.

Les exercices ici sont destinés à être moins exigeants que dans l'article précédent du didacticiel sur l'index SQL - ils peuvent être effectués plus au toucher qu'en fonction de la minuterie et du nombre de lignes. Certains exercices sembleront très similaires, mais cette fois, nous explorons :

1. Comment récupérer plus efficacement des données lors de l'utilisation d'index séparés plutôt que de tables primaires triées
2. Comment maintenir l'ordre dans chaque index et table lors de la modification des données

Le didacticiel précédent était axé sur les lectures, mais dans de nombreuses dynamiques de données courantes du monde réel, y compris nos réservations d'hôtel, nous devons prendre en compte les effets de l'indexation sur les performances d'écriture, à la fois pour l'insertion de nouvelles données et la mise à jour des données existantes.

Exercice préliminaire : Annuler une réservation

Pour avoir une idée des performances de l'index SQL à l'aide de la stratégie de table triée, votre tâche consiste à supprimer une réservation pour le client 12, à partir du 22 août 2020, dans l'hôtel 4. Gardez à l'esprit que vous devez supprimer une ligne de toutes les copies de la table et maintenir le bon tri.

Terminé? Il devrait être clair que l'idée de conserver plusieurs copies triées de la table n'est pas aussi bonne qu'il n'y paraît. Si vous avez encore des doutes, vous pouvez également essayer de réinsérer la réservation que vous venez de supprimer ou de modifier la date d'une réservation existante.

Alors que les copies triées de la table permettent une récupération plus rapide, comme nous venons de l'apprendre, la modification des données est un cauchemar. Chaque fois que nous aurons besoin d'ajouter, de supprimer ou de mettre à jour une ligne existante, nous devrons récupérer toutes les copies de la table, trouver une ligne et/ou l'endroit où elle doit être ajoutée ou déplacée, et enfin déplacer des blocs de données.

Index SQL utilisant des adresses de ligne

Cette feuille de calcul contient des index qui utilisent une approche différente. Les lignes d'index sont toujours triées selon des critères spécifiques, mais nous ne conservons pas toutes les autres informations dans la ligne d'index. Au lieu de cela, nous gardons uniquement « l'adresse de la ligne », l'adresse de la ligne dans la feuille Réservations, représentant la table elle-même, dans la colonne H.

Toutes les implémentations RDBMS utilisent une capacité au niveau du système d'exploitation pour trouver rapidement le bloc sur le disque à l'aide d'une adresse physique. Les adresses de ligne consistent généralement en une adresse de bloc plus la position de la ligne dans le bloc.

Faisons quelques exercices pour apprendre comment fonctionne cette conception d'index.

Exercice 1 : Toutes les réservations d'un client

Comme dans le premier article, vous allez simuler l'exécution de la requête SQL suivante :

 SELECT * FROM Reservations WHERE ClientID = 12;

Là encore, il existe deux approches raisonnables. La première consiste simplement à lire toutes les lignes de la table Reservations et à récupérer uniquement les lignes correspondant aux critères :

 For each row from Reservations If Reservations.ClientID = 12 then write down Reservations.*

La deuxième approche consiste à lire les données de la feuille IX_ClientID et, pour tout élément correspondant aux critères, à rechercher une ligne dans la table Reservation en fonction de la valeur rowAddress :

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

Ici, l'expression Get first row from est implémentée par une boucle similaire à celles vues dans l'article précédent :

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

Vous pouvez trouver une ligne avec une rowAddress donnée en faisant glisser vers le bas jusqu'à ce que vous trouviez une ligne, ou en utilisant un filtre sur la colonne rowAddress.

S'il n'y avait qu'une poignée de réservations à retourner, l'approche utilisant l'index serait meilleure. Cependant, avec des centaines (ou parfois même des dizaines) de lignes à renvoyer, le simple fait d'utiliser directement la table Reservations peut être plus rapide.

Le volume de lectures dépend de la valeur de ClientID. Pour la valeur la plus grande, vous devez lire l'index entier, tandis que pour la valeur la plus basse, c'est au début de l'index. La valeur moyenne est la moitié du nombre de lignes.

Nous reviendrons sur cette partie plus tard et présenterons une solution efficace. Pour l'instant, concentrons-nous sur la partie après avoir trouvé la première ligne correspondant à nos critères.

Exercice 2 : Le nombre de réservations commençant à une date donnée

La tâche consiste à compter le nombre d'enregistrements le 16 août 2020, en utilisant la nouvelle conception de l'index.

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16','YYYY-MM-DD');

L'approche consistant à utiliser l'index approprié pour le comptage est supérieure à une analyse de table, quel que soit le nombre de lignes impliquées. La raison en est que nous n'avons pas du tout besoin d'accéder à la table Reservations - nous avons toutes les informations dont nous avons besoin dans l'index lui-même :

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

L'algorithme est fondamentalement le même que celui utilisant des tables triées. Cependant, la ligne d'index est beaucoup plus courte que la ligne de table, donc notre SGBDR devrait lire moins de blocs de données sur le disque.

Exercice 3 : Enquête criminelle (liste d'invités compte tenu de l'hôtel et de la plage de dates)

Préparons une liste des invités arrivés à l'hôtel 3 les 13 et 14 août 2020.

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13','YYYY-MM-DD') AND TO_DATE('2020-08-14','YYYY-MM-DD') ) AND HotelID = 3;

Nous pouvons lire toutes les lignes de la table Reservations ou utiliser l'un des index disponibles. Après avoir fait le même exercice avec une table triée selon des critères précis, nous avons découvert que l'index IX_HotelID_DateFrom est le plus efficace.

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

Pouvons-nous concevoir un index encore plus efficace ?

Nous accédons au tableau en raison de la valeur ClientID , la seule information dont nous avons besoin pour la liste des invités que nous signalons. Si nous incluons cette valeur dans l'index SQL, nous n'avons pas du tout besoin d'accéder à la table. Essayez de préparer une liste lisant uniquement à partir d'un tel index, IX_HotelID_DateFrom_ClientID :

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

Lorsque l'index contient toutes les informations nécessaires à l'exécution de la requête, on dit que l'index couvre la requête.

Exercice 4 : Liste des noms des invités au lieu des identifiants

Une liste d'identités d'invités serait inutile pour un policier enquêtant sur un crime. Nous devons fournir des noms :

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

Pour fournir une liste, outre les données de la table Reservations , nous avons également besoin d'une table Clients contenant des informations sur les clients, qui se trouvent dans cette feuille Google.

Cet exercice est similaire au précédent, tout comme l'approche.

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

L'expression Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID peut être implémentée en parcourant la table ou en utilisant notre index. Si nous utilisons un balayage de table, pour chaque ClientID de la boucle While , nous devrions lire en moyenne la moitié des lignes de la table Clients :

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

L'implémentation d'index que nous avons envisagée jusqu'à présent (appelons-la une implémentation d'index « plate ») ne serait pas très utile. Nous devrions lire le même nombre de lignes (bien que des lignes plus petites) à partir de l'index, puis passer à la ligne dans Clients using RowAddress :

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

Remarque : ici, PK fait référence à la « clé primaire », un terme que nous explorerons plus tard dans la série.

Existe-t-il un moyen d'accomplir cela sans avoir à lire autant de lignes? Oui, c'est exactement à cela que servent les index B-tree.

Index d'arbre équilibré (arbre B)

Divisons les lignes de Clients_PK_Flat en blocs de quatre lignes et créons une liste contenant la valeur du dernier ClientID du bloc et l'adresse du début du bloc (colonne IndexRowAddress ). La structure de données d'index de base de données résultante, que vous pouvez trouver dans la feuille Clients_PK_2Levels. Essayez comment la nouvelle structure vous aide à trouver un client ayant un ClientID de 28. L'algorithme devrait ressembler à ceci :

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

Vous avez probablement compris que nous pouvons ajouter un autre niveau. Le niveau 1 se compose de quatre lignes, comme vous pouvez le voir dans l'onglet IX_Clients_PK. Pour trouver le nom de l'invité avec un ClientID de 28, vous devez lire trois blocs (nœuds) de données (un par niveau) à partir de la structure de la clé primaire et enfin passer à la ligne Clients avec l'adresse 42.

La structure de cet index SQL est appelée arbre équilibré. L'arbre est équilibré lorsque le chemin du nœud racine à chaque nœud de niveau feuille a la même longueur, sa soi-disant profondeur B-tree. Dans notre cas, la profondeur est de trois.

À partir de maintenant, nous considérerons que chaque index a une structure en arbre B, même si nos feuilles de calcul ne contiennent que des entrées au niveau feuille. Les faits les plus importants à connaître sur B-tree sont :

• La structure d'index B-tree est l'index le plus couramment utilisé par tous les principaux SGBDR du marché.
• Tous les niveaux d'un arbre équilibré sont classés par valeurs de colonne clé.
• Les données sont lues à partir du disque par blocs.
• Un nœud B-tree contient un ou plusieurs blocs.
• Le facteur le plus important affectant les performances des requêtes est le nombre de blocs lus à partir du disque.
• Le nombre d'éléments dans chaque nouveau niveau d'arbre B, en commençant par la racine, se terminant au niveau de la feuille, augmente de façon exponentielle.

Exercice 5 : Enquête criminelle, partie II

Maintenant, l'inspecteur de police recherche une liste des noms des clients correspondants, des dates d'arrivée et des noms d'hôtels de tous les hôtels de la ville A.

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

Approche 1

Si nous utilisons l'index IX_DateFrom_HotelID_ClientID , alors pour chaque ligne de la plage de dates, nous devrions accéder à la table Hotels et vérifier si l'hôtel est de la ville A. Si c'est le cas, nous devrions également accéder à la table Clients pour lire le nom du client.

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Approche 2

L'utilisation IX_HotelID_DateFrom_ClientID nous donne un plan d'exécution plus efficace.

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Dans la table Hotels , nous trouvons tous les hôtels de la ville A. Connaissant l'ID de ces hôtels, nous pouvons lire les éléments suivants de l'index IX_HotelID_DateFrom_ClientID . De cette façon, après avoir trouvé la première ligne du niveau feuille de l'arbre B pour chaque hôtel et date, nous ne lisons pas les réservations des hôtels en dehors de la ville A.

Ici, nous pouvons voir que lorsque nous avons un index de base de données adapté à nos objectifs, une jointure supplémentaire peut en fait accélérer une requête.

La structure B-tree et la façon dont elle est mise à jour chaque fois qu'une ligne est insérée, mise à jour ou supprimée seront abordées plus en détail lorsque j'expliquerai la motivation du partitionnement et son impact. Le fait est que nous pouvons considérer cette opération comme rapide chaque fois que nous utilisons un index.

La requête d'index en SQL : les détails font toute la différence

En ce qui concerne les index et les bases de données, travailler au niveau du langage SQL masque dans une certaine mesure les détails d'implémentation. Ces exercices sont destinés à vous aider à vous faire une idée du fonctionnement des plans d'exécution lors de l'utilisation de différents index SQL. Après avoir lu l'article, j'espère que vous serez en mesure de deviner le meilleur plan d'exécution compte tenu des index disponibles et des index de conception qui rendraient une requête aussi rapide et efficace que possible.

Dans la prochaine partie de cette série, nous utiliserons et développerons les compétences nouvellement acquises pour étudier et comprendre les meilleures pratiques et les anti-modèles les plus courants dans l'utilisation des index en SQL. J'ai une liste de bonnes et meilleures pratiques que je souhaite aborder dans la prochaine partie, mais pour rendre le prochain article plus pertinent pour vos besoins et votre expérience, n'hésitez pas à poster vos propres questions auxquelles vous aimeriez voir des réponses .

Dans la dernière partie de SQL Indexes Explained , nous découvrirons également le partitionnement des tables et des index, les bonnes et les mauvaises motivations pour l'utiliser, et son impact sur les performances des requêtes et la maintenance de la base de données.