Explication des index SQL, pt. 1

Correctement utilisé, un index de base de données SQL peut être si efficace qu'il peut sembler magique. Mais la série d'exercices suivante montrera qu'en dessous, la logique de la plupart des index SQL - et leur utilisation correcte - est assez simple.

Dans cette série, SQL Indexes Explained , nous passerons en revue les motivations pour utiliser des index pour accéder aux données et pour concevoir des index de la même manière que tous les SGBDR modernes. Nous examinerons ensuite les algorithmes utilisés pour renvoyer des données pour des modèles de requête spécifiques.

Vous n'avez pas besoin d'en savoir beaucoup sur les index pour pouvoir suivre SQL Indexes Explained . Il n'y a que deux conditions préalables :

• Connaissances de base en SQL
• Connaissance de base de tout langage de programmation

Les principaux sujets abordés par SQL Indexes Explained sont :

• Pourquoi avons-nous besoin d'index de base de données SQL ? visualisation des plans d'exécution à l'aide d'index
• Conception d'index : quels index rendent une requête rapide et efficace
• Comment nous pouvons écrire une requête pour utiliser efficacement les index
• L'impact de l'utilisation des index en SQL sur l'efficacité en lecture/écriture
• Couverture des index
• Le partitionnement, son impact sur la lecture et l'écriture, et quand l'utiliser

Il ne s'agit pas seulement d'un didacticiel sur les index SQL, mais d'une plongée approfondie dans la compréhension des mécanismes sous-jacents des index.

Nous allons comprendre comment un SGBDR utilise les index en faisant des exercices et en analysant nos méthodes de résolution de problèmes. Notre matériel d'exercice se compose de Google Sheets en lecture seule. Pour faire un exercice, vous pouvez copier la feuille Google ( Fichier → Faire une copie ) ou copier son contenu dans votre propre feuille Google.

Dans chaque exercice, nous montrerons une requête SQL qui utilise la syntaxe Oracle. Pour les dates, nous utiliserons le format ISO 8601, YYYY-MM-DD .

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

La première tâche (ne le faites pas tout de suite) consiste à rechercher toutes les lignes de la feuille de calcul Réservation pour un client spécifique d'un système de réservation d'hôtel et à les copier dans votre propre feuille de calcul, en simulant l'exécution de la requête suivante :

 SELECT * FROM Reservations WHERE ClientID = 12;

Mais nous voulons suivre une méthode particulière.

Approche 1 : pas de tri, pas de filtrage

Pour la première tentative, n'utilisez aucune fonctionnalité de tri ou de filtrage. Veuillez noter le temps passé. La feuille résultante doit contenir 73 lignes.

Ce pseudocode illustre l'algorithme permettant d'accomplir la tâche sans tri :

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

Dans ce cas, nous avons dû vérifier les 841 lignes à renvoyer et copier 73 lignes satisfaisant la condition.

Approche 2 : tri uniquement

Pour la deuxième tentative, triez la feuille en fonction de la valeur de la colonne ClientID . N'utilisez pas de filtres. Enregistrez le temps et comparez-le avec le temps qu'il a fallu pour terminer la tâche sans trier les données.

Après le tri, l'approche ressemble à ceci :

 For each row from Reservations If ClientID = 12 then fetch Reservations.* Else if ClientID > 12 exit

Cette fois, nous avons dû vérifier "seulement" 780 lignes. Si nous pouvions en quelque sorte sauter à la première rangée, cela prendrait encore moins de temps.

Mais si nous devions développer un programme pour la tâche, cette solution serait encore plus lente que la première. En effet, nous devrions d'abord trier toutes les données, ce qui signifie que chaque ligne devrait être consultée au moins une fois. Cette approche n'est bonne que si la feuille est déjà triée dans l'ordre souhaité.

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

Maintenant, la tâche consiste à compter le nombre d'enregistrements le 16 août 2020 :

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

Utilisez la feuille de calcul de l'exercice 1. Mesurez et comparez le temps passé à effectuer la tâche avec et sans tri. Le nombre correct est 91.

Pour l'approche sans tri, l'algorithme est fondamentalement le même que celui de l'exercice 1.

L'approche de tri est également similaire à celle de l'exercice précédent. Nous allons juste scinder la boucle en deux parties :

 -- Assumption: Table reservation is sorted by DateFrom -- Find the first reservation from the 16th of August 2020. Repeat Read next row Until DateFrom = '2020-08-16' -- Calculate the count While DateFrom = '2020-08-16' Increase the count Read the next row

Exercice 3 : Enquête criminelle

L'inspecteur de police demande à voir la liste des clients arrivés à l'hôtel 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;

Approche 1 : Trier par date uniquement

L'inspecteur veut la liste rapidement. Nous savons déjà qu'il vaut mieux trier le tableau/tableur en fonction de la date d'arrivée. Si nous venons de terminer l'exercice 2, nous avons de la chance que le tableau soit déjà trié. Nous appliquons donc une approche similaire à celle de l'exercice 2.

S'il vous plaît, essayez d'enregistrer l'heure, le nombre de lignes que vous avez dû lire et le nombre d'éléments sur la liste.

 -- Assumption: Table reservation is sorted by DateFrom -- Find the first reservation from the 13th of August 2020. Repeat Read next row Until DateFrom >= '2020-08-13' -- Prepare the list While DateFrom < '2020-08-15' If HotelID = 3 then write down the ClientID Read the next row

En utilisant cette approche, nous avons dû lire 511 lignes pour compiler une liste de 46 invités. Si nous pouvions glisser avec précision vers le bas, nous n'avions pas réellement besoin d'effectuer 324 lectures à partir du cycle de répétition juste pour localiser la première arrivée le 13 août. Cependant, nous avons encore dû lire plus de 100 lignes pour vérifier si le client est arrivé à l'hôtel avec un HotelID de 3 .

L'inspecteur a attendu tout ce temps mais n'était pas content : au lieu des noms des clients et d'autres données pertinentes, nous n'avons fourni qu'une liste d'identifiants sans signification.

Nous reviendrons sur cet aspect plus tard dans la série. Trouvons d'abord un moyen de préparer la liste plus rapidement.

Approche 2 : Trier par hôtel, puis par date

Pour trier les lignes selon HotelID puis DateFrom , nous pouvons sélectionner toutes les colonnes, puis utiliser l'option de menu Google Sheets Data → Sort range .

 -- Assumption: Sorted according to HotelID and DateFrom -- Find the first reservation for the HotelID = 3. Repeat Read next row Until HotelID >= 3 -- Find the first arrival at the hotel on 13th of August While HotelID = 3 and DateFrom < '2020-08-13' Read the next row -- Prepare the list While HotelID = 3 and DateFrom < '2020-08-15' Write down the ClientID Read the next row

Nous avons dû sauter les 338 premières arrivées avant de localiser la première à notre hôtel. Après cela, nous avons parcouru 103 arrivées précédentes pour localiser la première le 13 août. Enfin, nous avons copié 46 valeurs consécutives de ClientID . Cela nous a aidés que dans la troisième étape, nous avons pu copier un bloc d'ID consécutifs. Dommage que nous ne puissions pas sauter d'une manière ou d'une autre à la première rangée de ce bloc.

Approche 3 : Trier par hôtel uniquement

Essayez maintenant le même exercice en utilisant la feuille de calcul commandée par HotelID uniquement.

L'algorithme appliqué au tableau trié par HotelID uniquement est moins efficace que lorsque nous trions par HotelID et DateFrom (dans cet ordre) :

 -- Assumption: Sorted according to HotelID -- Find the first reservation for the HotelID = 3. Repeat Read next row Until HotelID >= 3 -- Prepare the list While HotelID = 3 If DateFrom between '2020-08-13' and '2020-08-14' Write down the ClientID Read the next row

Dans ce cas, nous devons lire les 166 arrivées à l'hôtel avec un HotelID de 3 , et pour chacune, vérifier si le DateFrom appartient à l'intervalle demandé.

Approche 4 : Trier par date, puis par hôtel

Est-il vraiment important de trier d'abord par HotelID puis DateFrom ou vice versa ? Découvrons-le : essayez d'abord de trier par DateFrom , puis par HotelID .

 -- Assumption: Sorted according to DateFrom and HotelID -- Find the first arrival on 13th of August While DateFrom < '2020-08-13' Read the next row --Find the first arrival at the Hotel While HotelID < 3 and DateFrom < '2020-08-15' Read the next row Repeat If HotelID = 3 Write down the ClientID Read the next row Until DateFrom > '2020-08-14' or (DateFrom = '2020-08-14' and HotelID > 3)

Nous avons localisé la première ligne avec la date pertinente, puis en savoir plus jusqu'à ce que nous ayons localisé la première arrivée à l'hôtel. Après cela, pour un certain nombre de rangées, les deux conditions étaient remplies, la bonne date et le bon hôtel. Cependant, après les arrivées à l'hôtel 3, nous avons eu des arrivées aux hôtels 4, 5, etc., pour la même date. Après eux, nous avons dû lire à nouveau les lignes du lendemain pour les hôtels 1 et 2, jusqu'à ce que nous puissions lire les arrivées consécutives à notre hôtel d'intérêt.

Comme nous pouvons le voir, toutes les approches ont un seul bloc de données consécutif au milieu de l'ensemble complet de lignes, représentant des données partiellement appariées. Les approches 2 et 4 sont les seules où la logique nous permet d'arrêter complètement l'algorithme avant d'atteindre la fin des correspondances partielles.

L'approche 4 a des données entièrement correspondantes dans deux blocs, mais l'approche 2 est la seule où les données ciblées sont toutes dans un bloc consécutif.

D'après les chiffres, il est clair que l'approche 2 présente le plus d'avantages dans ce cas.

Explication des index SQL : conclusions et suite

Faire ces exercices devrait permettre de clarifier les points suivants :

1. La lecture à partir d'un tableau correctement trié est plus rapide.
2. Si une table n'est pas déjà triée, le tri prend plus de temps que la lecture d'une table non triée.
3. Trouver un moyen de passer à la première ligne correspondant à une condition de recherche dans le tableau trié permettrait d'économiser beaucoup de lectures.
4. Il serait utile d'avoir une table triée à l'avance.
5. Il serait utile de conserver les copies triées du tableau pour les requêtes les plus fréquentes.

Maintenant, une copie triée d'une table ressemble presque à un index de base de données. Le prochain article de SQL Indexes Explained couvre une implémentation d'index rudimentaire. Merci d'avoir lu!