Résoudre les goulots d'étranglement avec les index SQL et les partitions

Publié: 2022-03-11

Dans la première leçon de SQL Indexes Explained, nous avons appris que les requêtes SELECT sont plus rapides lorsque les données sont déjà triées par valeurs de colonnes spécifiques.

Dans la deuxième leçon, nous avons appris la structure de base des index B-tree et comment les utiliser pour réduire le volume de données auxquelles nous accédons lors de l'exécution d'une requête. Nous avons également compris comment implémenter des requêtes joignant plusieurs tables et comment les index peuvent accélérer ces requêtes.

Nous avons également mis en évidence deux scénarios où l'utilisation d'index dans SQL est utile. Lorsque les index couvrent des index contenant toutes les colonnes de la requête (conditions WHERE , conditions JOIN et liste SELECT ), nous évitons de lire entièrement la table correspondante. Alternativement, les index peuvent aider lorsqu'ils réduisent le nombre de blocs de données accessibles à une petite fraction de la taille de la table.

Sinon, il est plus efficace de parcourir toute la table que de lire à partir d'un index et de sauter de manière aléatoire dans les deux sens jusqu'aux lignes correspondantes de la table.

Requêtes de plage SQL

Les requêtes qui peuvent tirer parti des index incluent généralement des conditions qui réduisent considérablement la plage de valeurs possibles qu'une ou plusieurs colonnes peuvent prendre. Les requêtes de plage restreignent les données en fonction de conditions telles que "la valeur de la colonne A doit être comprise entre X et Y".

Un bon exemple de ceci est la requête de l'exercice 4 de la deuxième leçon :

 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;

Ici, nous avons deux gammes. Le premier est la plage de dates, la période entre le 13 août 2020 et le 14 août 2020. Le second est la plage numérique la plus petite possible. La condition est équivalente à r.HotelID BETWEEN 3 AND 3 .

Exercice 1 : Périodes (requêtes de plage de dates et d'heures)

Ajoutons une colonne appelée CheckInTime à la table Reservations . Vous pouvez voir des exemples de données dans cette feuille de calcul. Notez qu'il existe un index unique couvrant à la fois CheckInTime et ClientId .

Écrivez une requête qui renverrait les noms des clients qui se sont enregistrés le 15 août 2020.

Les développeurs SQL inexpérimentés écrivent généralement la requête suivante :

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE TO_DATE(r.CheckInTime, 'YYYY-MM-DD') = '2020-08-15';

Ils supposent que l'exécution de la requête ressemblerait à ceci :

 Get first row from IX_CheckInTime_ClientID where TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' While found and TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName Get next row from IX_CheckInTime_ClientID

Le problème est qu'aucun SGBDR au moment d'écrire ces lignes n'est capable de générer un tel plan d'exécution. Ils voient TO_DATE (syntaxe Oracle) comme une fonction qui transforme la valeur de la colonne CheckInTime en quelque chose de non indexé. Ainsi, les plans d'exécution qu'ils ont tendance à générer ressemblent à ceci :

 For each row from IX_CheckInTime_ClientID If TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' then Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName

L'exécution serait plus rapide que la lecture de toutes les lignes de la table Reservations car la ligne d'index est plus étroite que la ligne de la table. Une ligne plus petite signifie qu'il faudrait accéder à moins de blocs à partir du disque.

Cependant, nous savons que le premier plan d'exécution serait beaucoup plus efficace. Pour persuader notre SGBDR d'utiliser cette approche, nous devons réécrire la requête :

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.CheckInTime >= TO_DATE('2020-08-15 00:00:00', 'YYYY-MM-DD HH:MI:SS') AND r.CheckInTime < TO_DATE('2020-08-16 00:00:00', 'YYYY-MM-DD HH:MI:SS');

Il s'agit d'une requête de plage appropriée, que tout bon SGBDR comprend. Notre RDBMS détermine que nous voulons des données de la table Reservations où la valeur de CheckInTime - et non quelque chose qui en est dérivé - appartient à la plage bien définie. Le plan d'exécution qu'il génère ressemblerait plutôt à :

 Get first row from IX_CheckInTime_ClientID where CheckInTime >= '2020-08-15 00:00:00' While found and CheckInTime < '2020-08-16 00:00:00' Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName Get next row from IX_CheckInTime_ClientID

C'est ce que nous voulons vraiment : tirer parti non seulement de l'index lui-même, mais aussi du fait qu'il est trié.

Exercice 2 : `LIKE` avec un caractère générique au début

Cette fois, notre détective vient à l'hôtel avec de vagues informations sur le suspect : juste que le nom de famille se termine par « -fils ». Le détective veut les noms et prénoms de tous ces invités :

 SELECT FirstName, LastName FROM Clients WHERE LastName LIKE '%son';

Pour la table Clients et un index sur LastName , nous utiliserons cette feuille de calcul. Notez les résultats que la requête renverrait. Pensez aux différentes approches que vous pouvez appliquer.

Approche par balayage de table

La stratégie la plus simple consiste à lire toutes les données de la table et à noter les noms des invités lorsque leur nom de famille se termine par "-son":

 For each row from Clients If LastName like '%son' then write down FirstName, LastName

Ici, nous aurions à lire l'intégralité du tableau de manière séquentielle.

Utilisation d'un index

Essayons de profiter de l'index sur la colonne LastName . Accédez à la feuille IX_LastName, utilisez-la pour rechercher tous les clients répondant au critère donné et notez leurs noms.

Il s'avère que vous devez lire l'intégralité de l'index pour trouver tous les Anderson, Robinson et Thompson du tableau. Est-ce mieux que d'utiliser un balayage de table ? En plus de lire l'intégralité de l'index, vous deviez également trouver, pour chaque entrée correspondante, la ligne correspondante de la table à l'aide de la valeur rowAddress , puis notez le FirstName à partir de là :

 For each row from IX_LastName If LastName like '%son' then Fetch Clients.* where RowAddress = IX_LastName.RowAddress Write down FirstName, LastName

Pour nous, il était plus simple et plus rapide de lire le tableau de manière séquentielle. Pour notre SGBDR, cela dépendrait du pourcentage de lignes satisfaisant aux critères. S'il n'y a qu'une poignée d'Andersons, de Robinsons et de Thompsons dans une grande table, un SGBDR lira moins de blocs de données à partir d'entrées d'index beaucoup plus étroites, même s'il doit lire quelques blocs de la table lorsqu'une correspondance est trouvée. Sinon, l'analyse de la table prend moins de temps.

Ordonner les données dans l'index ne fournit aucune aide pour une telle requête. La taille plus petite de la ligne d'index peut être utile, mais seulement parfois.

Exercice 3 : `LIKE` avec un caractère générique à la fin

La prochaine fois que notre détective viendra, nous devrons trouver tous les clients dont le nom de famille commence par "Rob-".

 SELECT FirstName, LastName FROM Clients WHERE LastName LIKE 'Rob%';

Essayez d'extraire les données correspondant à la requête à partir de la même feuille de calcul.

Si vous avez utilisé l'approche par balayage de table, vous avez raté l'occasion de tirer pleinement parti de l'index IX_LastName . Il est beaucoup plus rapide de localiser la première entrée de l'index commençant par "Rob-" (Roberts), de lire les lignes suivantes (à la fois Robertses et Robinsons) et de s'arrêter lorsque LastName ne correspond plus au critère :

 Get first row from IX_LastName where LastName <= 'Rob' While found and LastName < 'Roc' Fetch Clients.* where rowAddress = IX_LastName.rowAddress Write down FirstName, LastName Get next from IX_LastName

Dans ce cas, après la recherche du B-tree pour la première entrée, nous ne lisons que les entrées satisfaisant au critère. On arrête de lire dès qu'on lit un nom qui ne correspond pas au critère.

Résoudre les problèmes de mise à l'échelle de B-tree

Généralement, lorsque nous déployons une nouvelle base de données, il existe quelques tables de recherche remplies et des tables transactionnelles vides. Le système fonctionne bien dès le départ, surtout si l'on respecte les bonnes pratiques de conception de bases de données en normalisant les tables ; créer des clés primaires, étrangères et uniques ; et prendre en charge les clés étrangères avec les index correspondants.

Après quelques mois ou années, lorsque le volume de données a considérablement augmenté la complexité du système et de la base de données, nous commençons à remarquer une dégradation des performances. Des opinions surgissent sur les raisons pour lesquelles le système a ralenti et sur ce qu'il faut faire pour y remédier.

L'opinion populaire est souvent que la taille de la base de données est le principal coupable. La solution semble être de supprimer les données historiques dont nous n'avons pas besoin quotidiennement et de les placer dans une base de données distincte pour les rapports et les analyses.

Explorons d'abord l'hypothèse principale.

Requêtes de plage SQL : le temps d'exécution dépend-il de la taille de la table ?

Considérez une requête de plage typique à partir d'une seule table :

 SELECT Column1, …, ColumnN FROM Table WHERE Column BETWEEN X AND Y;

En supposant qu'il existe un index sur Column , le plan d'exécution optimal est :

 Get first row from IX_Column where Column between X and Y While found and Column <= Y Fetch Table.* where rowAddress = IX_Column.rowAddress Write down Column1, …, ColumnN Get next row from IX_Column

Comptons les blocs qu'un SGBDR devra lire pour renvoyer ces données.

La partie Get first row est implémentée par la recherche B-tree que nous avons présentée dans la deuxième leçon. Le nombre de blocs qu'il doit lire est égal à la profondeur du B-tree. Après cela, nous lisons les éléments suivants à partir du niveau feuille de l'index.

Avec les requêtes OLTP, tous les résultats se trouvent généralement dans un bloc d'index (parfois deux, mais rarement plus). En plus de cela, pour chaque entrée d'index, nous avons accès à un bloc dans la table pour trouver la ligne correspondante en fonction de son adresse. Certaines lignes de table peuvent se trouver dans le même bloc de table que nous avons déjà chargé, mais pour simplifier l'estimation, supposons que nous chargeons un nouveau bloc à chaque fois.

Donc la formule est :

B = D + 1 + R

B est le nombre total de blocs lus, D est la profondeur de l'arbre B et R est le nombre de lignes renvoyées par la requête.

Le seul paramètre qui dépend du nombre de lignes dans la table est D, la profondeur du B-tree.

Pour simplifier les calculs et faire un point, supposons que 1 000 entrées d'index tiennent dans un bloc. D = 1 tant qu'il y a moins de 1 000 lignes dans la table. Pour les tables contenant des transactions commerciales, cela peut être le cas le premier jour ouvrable après le déploiement du système. Bientôt, la profondeur de l'arbre B augmentera. Tant qu'il y a moins d'un million de lignes dans la table, l'index sera composé de deux niveaux.

Si nous sommes gênés par les temps de réponse lents de la base de données et que nous blâmons le volume de données pour cela, notez que les tables de transactions ne contiennent souvent que des millions de lignes. Étant donné que seulement 1 million de lignes correspondent à un index B-tree à deux niveaux, la profondeur doit être d'au moins trois. La profondeur n'atteindra pas quatre à moins qu'il n'y ait plus d'un milliard de lignes dans la table. Nous avons maintenant une estimation plus précise :

B = 4 + R

Si R est petit, réduire la profondeur de l'arbre B à deux accélérerait considérablement la requête. Lorsque nous recherchons par une valeur de clé primaire ou unique, le système lira quatre blocs au lieu de cinq, ce qui représente une amélioration de 20 %. Si la requête renvoie plus de lignes, l'amélioration peut ne pas être perceptible. Le problème est que, pour de nombreuses applications, nous pourrions ne pas être en mesure de prendre en charge les opérations commerciales requises en conservant moins d'un million de transactions dans la base de données.

La conclusion semble donc être que la taille de la table n'a pas d'importance ; en d'autres termes, déplacer des données historiques est une perte de temps et de ressources.

Mais pas si vite : apprenons-en plus sur la structure d'un index B-tree et comment les changements de données l'affectent.

Détails de la mise en œuvre de l'index B-tree

Dans notre couverture des index B-tree dans la deuxième leçon, nous avons vu que tous les niveaux d'un arbre équilibré sont (physiquement) ordonnés par des valeurs de colonne clés. Cependant, lorsque nous voulons insérer, mettre à jour ou supprimer un élément, nous devons souvent déplacer une grande quantité de données pour préserver l'ordre.

Disons que nous insérons au milieu d'un bloc qui se trouve être plein. Nous devons diviser le bloc, réorganiser les données et parfois même mettre à jour les données sur un autre niveau B-tree pointant vers le niveau actuel.

Pour rendre ces cas plus efficaces, chaque élément d'index contient des pointeurs vers les lignes précédentes et suivantes, ce qui le rend doublement lié. Pour l'insertion en général, cela signifie qu'il suffit d'écrire les nouveaux éléments aussi près que possible du précédent et de corriger les pointeurs.

Lorsque nous devons également scinder un bloc, nous devons écrire un nouvel élément dans le niveau B-tree précédent. Il s'agit simplement de corriger quelques pointeurs supplémentaires, pas besoin de réécrire de grandes parties de l'arbre. Après une scission, les deux blocs de données sont approximativement à moitié pleins. Selon l'endroit où il y a de l'espace libre sur le disque, les blocs «voisins» peuvent être physiquement assez éloignés.

Après un certain temps, la fragmentation des index augmente et le ralentissement de l'exécution des requêtes devient perceptible. Avec un SGBDR exécutant les requêtes comme nous les avons décrites, l'hypothèse de l'ordre et de la proximité des éléments devient de moins en moins correcte, ce qui entraîne beaucoup plus de lectures. Dans le pire des cas, tous les blocs de données étant à moitié vides, le système doit lire deux fois plus de blocs.

Maintenance de l'index B-tree

Le remède à cela est la défragmentation d'index (ou "réindexation"). Chaque SGBDR fournit une fonctionnalité pour recréer un index entier ; après la réindexation, les index sont de nouveau ordonnés physiquement.

La réindexation est une opération assez rapide, même si elle lit et écrit un grand volume de données. Les SGBDR modernes offrent généralement deux modes de réindexation, le plus rapide nécessitant le verrouillage des tables pendant le traitement. Dans tous les cas, il est préférable de réindexer en heures creuses. Sinon, le traitement risque de ralentir les performances de la base de données.

Suppression des données historiques

Lorsque nous avons des tables avec des milliards, voire des centaines de millions de lignes, il peut ne pas être possible d'effectuer une opération de réindexation pendant les heures creuses.

Pour éviter cette situation, le déplacement des données historiques hors d'une base de données OLTP peut être la solution. Cependant, si nous supprimons simplement les lignes qui sont plus anciennes qu'un seuil spécifique, nous rendons les index encore plus fragmentés et nous devons les réindexer encore plus fréquemment.

Le partitionnement SQL à la rescousse ?

Il existe un moyen d'éviter la fragmentation causée par la suppression des données historiques, en ne conservant que les transactions "actives" dans la base de données de production. L'idée que tous les principaux SGBDR implémentent est de diviser une table en plus petits morceaux (appelés partitions ) et de fournir la possibilité de les ajouter, de les supprimer et même de les basculer entre les tables (par exemple, d'une table active à une table historique avec le même structure).

Examinons la table des Reservations telle qu'elle est partitionnée dans cette feuille de calcul. Le tableau est divisé par mois, avec des noms de partition mappés sur des périodes de date et d'autres feuilles de calcul. Pour voir comment s'exécute une requête sur une table partitionnée, nous allons faire quelques exercices.

Exercice 4 : Requête de partition en SQL

À partir de la feuille de calcul liée ci-dessus, essayez d'extraire les données demandées par la requête suivante, sans utiliser d'index :

 SELECT HotelID, ReservationID, ClientID, DateFrom, DateTo FROM Reservations WHERE DateFrom BETWEEN TO_DATE('2021-03-01','YYYY-MM-DD') AND TO_DATE('2021-03-03');

Vous avez probablement compris que vous deviez d'abord consulter la feuille de mappage de partition et trouver la partition contenant les réservations de mars 2021. Après cela, vous avez ouvert la partition correspondante, lu les données de manière séquentielle et filtré les lignes qui ne satisfaisaient pas le état.

Bien que simple, vous n'aimiez probablement pas garder si peu de lignes après en avoir lu autant. La lecture de la partition de mars était meilleure que la lecture de l'intégralité du tableau des réservations, mais ce n'était toujours pas idéal. Qu'en est-il des index ?

Index globaux

Les SGBDR nous permettent de créer un index global pour couvrir toutes les partitions d'une table partitionnée. Mais il n'y a aucune différence entre le fonctionnement des index globaux et réguliers en dessous : les index globaux ne sont pas sensibles aux partitions. Ainsi, les requêtes CRUD utilisant un index global n'impliquent pas la carte de partition pour sa table.

Nous n'avons besoin de mettre à jour la carte de partition que lorsque nous supprimons une partition entière. Nous devons ensuite supprimer toutes les lignes de l'index qui pointent vers la partition supprimée. Cela signifie que l'ensemble de l'index global doit être reconstruit.

Une fenêtre d'indisponibilité reste nécessaire car les index ne peuvent pas être utilisés tant que les éléments obsolètes n'ont pas été supprimés. Si nous pouvons supprimer régulièrement des partitions, en limitant le nombre de partitions actives, l'opération de réindexation peut s'inscrire dans la fenêtre d'indisponibilité. Ainsi, l'utilisation de partitions aide à résoudre le problème d'origine en raccourcissant le temps requis pour les tâches de maintenance, y compris la maintenance des index globaux.

Mais que se passe-t-il si nous ne pouvons toujours pas nous permettre la panne ?

Index partitionnés globalement

Cette stratégie résout ce problème : nous partitionnons simplement l'index de la même manière que nous partitionnons la table. Dans les feuilles de calcul auxquelles la feuille de calcul de partition est liée, chaque partition contient sa partie de la table Reservations et une feuille d'index appelée IX_DateFrom, toutes deux partitionnées par DateFrom .

Pour exécuter la requête de l'exercice 4, un SGBDR doit d'abord examiner une carte de partitions d'index et identifier les partitions contenant des dates de la plage. (Dans notre cas, il ne s'agit que d'une partition d'index.) Après cela, il utiliserait des recherches B-tree, passerait au niveau feuille et accéderait finalement à la table en utilisant l'adresse de ligne correspondante.

Lorsque nous supprimons une partition d'une table, il suffit de supprimer la partition correspondante de l'index. Aucun temps d'arrêt n'est nécessaire.

Index locaux

Le principal inconvénient des index partitionnés globalement est que nous devons prendre soin de supprimer à la fois la table et la partition d'index correspondante. Il n'y a qu'un léger surcoût associé à la lecture et à la maintenance de la carte des partitions d'index elle-même.

Les index locaux impliquent une approche similaire mais légèrement différente. Au lieu de partitionner un seul index global, nous créons un index local à l' intérieur de chaque partition de table. Ce faisant, les index locaux partagent le principal avantage des index partitionnés globalement, c'est-à-dire l'absence de temps d'arrêt, tout en évitant leurs inconvénients.

Cela semble être une solution parfaite. Mais avant de célébrer, examinons le plan d'exécution possible de quelques requêtes.

Exercice 5 : Index partitionné localement

Essayez d'exécuter à nouveau la requête, cette fois en utilisant l'index partitionné localement sur DateFrom .

Vous avez probablement utilisé ce plan d'exécution :

 For all partitions where [StartDateFrom, StartDateTo) intersects ['2021-03-01', '2021-03-03'] Get first row from IX_DateFrom where DateFrom between '2021-03-01' and '2021-03-03' While found and DateFrom < '2021-03-04' Fetch Reservations.* where RowAddress = IX_DateFrom.RowAddress Write down HotelID, ReservationID, ClientID, DateFrom, DateTo Get next row from IX_DateFrom

Nous avons de la chance que toutes les dates appartiennent à une seule partition, nous n'avons donc dû parcourir qu'un seul index local. Si la période était de six mois, il faudrait lire six index locaux.

Exercice 6 : En contraste

Votre tâche consiste à utiliser à nouveau la carte de partition des réservations, cette fois pour dresser une liste des périodes pendant lesquelles le client 124 a visité l'hôtel 1 :

 SELECT DateFrom, DateTo FROM Reservations WHERE ClientID = 124 AND HotelID = 1;

Ici, nous pouvons voir le principal inconvénient des index locaux. Nous avons dû lire la feuille d'index local IX_HotelID_CientID de chaque partition de la table Reservations :

 For all partitions Get first row from IX_HotelID_ClientID where ClientID = 124 and HotelID = 1 While found and ClientID = 124 and HotelID = 1 Fetch Reservations.* where RowAddress = IX_HotelID_ClientID.RowAddress Write down DateFrom, DateTo Get next row from IX_HotelID_ClientID

Cette exécution lirait clairement plus de blocs et prendrait plus de temps que si la table n'était pas partitionnée.

Ainsi, bien que nous ayons trouvé un moyen de maintenir la santé de nos index pendant la période creuse, la stratégie a également ralenti certaines de nos requêtes.

Si notre business model nous permet de garder un petit nombre de partitions ou au moins les requêtes les plus fréquentes contiennent des critères permettant au SGBDR de ne lire qu'une ou deux partitions, cette solution pourrait être ce dont nous avons besoin. Sinon, nous ferions mieux d'éviter le partitionnement et de travailler à l'amélioration du modèle de données, des index et des requêtes, ainsi qu'à l'amélioration du serveur de base de données.

Index en SQL : ce qu'il faut apprendre ensuite

C'est la fin de notre voyage. Dans SQL Indexes Explained, je me suis concentré sur l'implémentation d'index qui est commune à tous les SGBDR modernes. Je me suis également concentré sur les sujets qui intéressent les développeurs d'applications, au détriment des sujets qui concernent généralement les administrateurs de bases de données. Ce dernier ferait bien de rechercher l'impact du facteur de remplissage sur la fragmentation de l'index, mais les personnes dans les deux rôles trouveront probablement utile d'en savoir plus sur :

Mise en cache des données et des index
Structures d'index non B-tree, telles que les index de hachage, GiST, bitmap et columnstore
Index clusterisés (appelés tables organisées en index dans Oracle)
Index fonctionnels
Index partiels

L'approche de partitionnement dont nous avons parlé est le partitionnement par plage . C'est le type de partitionnement le plus couramment utilisé, mais il en existe d'autres, comme le partitionnement par hachage et le partitionnement par liste. En outre, certains SGBDR offrent l'option de plusieurs niveaux de partitionnement.

Enfin, les développeurs SQL feraient bien d'explorer d'autres sujets importants autour de l'exécution des requêtes RDBMS, d'abord l'analyse des requêtes, puis la compilation, la mise en cache et la réutilisation du plan d'exécution basé sur les coûts.

Pour les quatre RDMBS avec lesquels j'ai de l'expérience, je recommande ces ressources comme prochaines étapes :

Oracle

Présentation de l'optimiseur
Index et tableaux organisés en index
Gestion des index
Présentation des partitions
Guide de partitionnement
Demander à Tom

PostgreSQLName

Traitement des requêtes
Index dans PostgreSQL
Index dans PostgreSQL (Documentation officielle)
Gestion des tampons
Partitionnement de table
Guide de partitionnement

Microsoft SQL Server

Architecture de traitement des requêtes
Index
Tables et index partitionnés

MySQL/MariaDB

Présentation du plan d'exécution des requêtes
Optimisation et Index
Partitionnement - Notions de base
Partitionnement - Documentation
Documentation MariaDB : Optimisation des requêtes et index