Indexes (InterBase et Firebird)

Alexey Kovyazin, dernière mise à jour le 07-Sept-2005

Le concept qui sert de base aux index est simple et visuel, et constitue l’un des fondements les plus importants de la conception de bases de données. Sur la base des index, de nombreux objets fondamentaux des bases de données sont établis, et de plus, l’utilisation correcte des index est la clé de l’amélioration de la productivité des applications de bases de données. Cependant, qu’est-ce qu’un index ? Un index est un pointeur ordonné des enregistrements dans la table. Pointeur signifie que l’index contient les valeurs d’un ou de plusieurs champs de la table ainsi que les adresses des pages de données où ces valeurs sont situées (pour plus de détails sur les pages de données, voir le chapitre « Structure de la base de données InterBase ») (partie 4). En d’autres termes, un index se compose de paires de valeurs « valeur du champ » - « emplacement physique de ce champ ».

Ainsi, par la valeur du champ (ou des champs) inclus dans l’index, nous pouvons trouver rapidement, à l’aide de l’index, l’endroit dans la table où est alloué l’enregistrement contenant cette valeur. Ordonné signifie que les valeurs des champs stockées dans l’index sont ordonnées. Très souvent, l’index est comparé à un catalogue de bibliothèque, dans lequel tous les livres sont enregistrés sur des fiches et ordonnés d’une certaine manière : selon l’alphabet ou les thèmes, et chaque fiche contient l’information indiquant exactement où le livre donné est alloué dans le stockage.

Pourquoi avons-nous besoin d’index ?

La seule chose que les index favorisent est l’accélération de la récupération des enregistrements par leur champ indexé (indexé - signifie inclus dans l’index). La fonction principale des index est de fournir une récupération rapide des enregistrements dans la table. Toute utilisation d’index se résume à cela.

Comment cette fonction de récupération est-elle réalisée ? À l’entrée de cette fonction, nous avons la valeur du champ indexé (ou de plusieurs champs). À la suite de la récupération, nous devrions recevoir l’enregistrement complet dans lequel le champ indexé a une valeur prédéfinie. D’abord, dans l’index (plus précisément, dans le tableau ordonné des valeurs du champ indexé), la valeur requise est recherchée, puis l’adresse de la page de données où se trouve l’enregistrement requis est prise, le serveur se rend sur cette page et lit l’enregistrement trouvé. Cela semble plutôt peu pratique, cependant, la recherche utilisant un index est plusieurs fois plus rapide que l’énumération séquentielle de toutes les valeurs de la table.

Si nous continuons l’analogie entre l’index et le catalogue de bibliothèque, nous verrons que la récupération d’enregistrements à l’aide d’un index est très similaire à la recherche d’un livre à l’aide d’une fiche. Lorsque nous trouvons un livre dans un catalogue assez petit (par rapport à l’ensemble du stockage de la bibliothèque), nous recevons immédiatement l’information sur l’endroit exact où le livre est stocké et nous pouvons nous y rendre directement. La recherche sans utiliser d’index peut être comparée à l’énumération séquentielle de tous les livres de la bibliothèque !

L’énumération de tous les enregistrements dans la table est appelée directe ou naturelle. Nous devons dire que malgré la puissance des ordinateurs modernes, l’énumération naturelle peut être très longue si la table contient un grand nombre d’enregistrements.

Comment sont-ils organisés ?

Un index ne fait pas partie de la table ; c’est un objet séparé connecté à la table et à d’autres objets de la base de données. C’est un point très important de l’implémentation du SGBD permettant de séparer le stockage de l’information de sa représentation.

InterBase, comme tout autre SGBD relationnel, stocke les enregistrements dans les tables de manière non ordonnée, c’est-à-dire qu’il ne se soucie pas du tout de la manière dont les enregistrements sont physiquement alloués dans la table. Le stockage non ordonné signifie que deux enregistrements ajoutés à la table l’un après l’autre peuvent ne pas être côte à côte. De plus, les données extraites de la table n’ont également aucun ordre, à part celui qui doit être explicitement spécifié par l’utilisateur effectuant une requête de récupération.

Cependant, nous ne pouvons pas nous passer de l’ordonnancement des données stockées : les utilisateurs finaux des applications veulent voir les données dans un ordre défini - par exemple, les noms de famille des personnes selon l’alphabet. Les index résolvent le problème de la représentation des données de manière ordonnée. Les valeurs des champs inclus dans l’index sont ordonnées et représentées dans une vue spéciale, optimisée pour la recherche des valeurs requises (c’est précisément essentiel pour créer des séquences ordonnées).

Séparer le stockage des données de leur représentation donne des avantages supplémentaires par rapport au tri direct - peut-être aurez-vous besoin de trier la table initiale de différentes manières. Alors les index vous aideront - il peut y avoir jusqu’à 64 index pour chaque table !

Si nous parlons de l’implémentation des index au niveau physique, ils représentent un arbre binaire dont les nœuds représentent des paires « valeur du champ dans l’index » - « allocation des données dans la table ». La récupération de l’enregistrement requis dans l’index est effectuée à l’aide du mécanisme de recherche par hachage - l’un des algorithmes de recherche les plus rapides.

Application des index

Maintenant qu’il est clair ce que nous pouvons exiger des index, il est temps de connaître leur fonction dans une base de données. Les index sont utilisés dans trois cas principaux :

Accélération de l’exécution des requêtes. Les index sont créés pour les champs utilisés dans les conditions de recherche des requêtes SQL.
Prise en charge de l’unicité des valeurs dans les champs ; une contrainte de clé primaire (dont il a été question dans le chapitre « Tables. Clés primaires ») exige qu’il n’y ait pas deux valeurs identiques des champs inclus dans une clé primaire dans la table. Pour satisfaire cette condition, lors de l’insertion d’un nouvel enregistrement, vous devez rechercher la même valeur qui sera insérée. Pour la récupération des enregistrements, une variété spéciale d’index est utilisée - un index unique (voir ci-dessous).
Prise en charge de l’intégrité référentielle. Les contraintes de clés étrangères (qui sont examinées dans le chapitre « Contraintes de base de données ») sont utilisées pour vérifier que les valeurs insérées dans la table existent nécessairement dans une autre table. Lors de la création d’une clé étrangère, un index est automatiquement créé. Cet index est appliqué pour accélérer les requêtes utilisant la jointure de tables, ainsi que pour vérifier les conditions de la clé étrangère. Nous avons brièvement couvert toutes les applications possibles des index. Maintenant, nous examinerons les particularités de chaque cas plus en détail et répondrons aux questions les plus fréquemment posées concernant l’application des index.

Accélération de l’exécution des requêtes à l’aide d’index

Il est décrit ci-dessus que l’application des index peut grandement accélérer l’exécution des requêtes. C’est vraiment le cas dans la plupart des situations, mais il y a certaines réserves. D’abord, nous répondrons à la question fréquemment posée par ceux qui se sont familiarisés avec les index. Si les index accélèrent la récupération depuis une base de données, pourquoi n’indexerions-nous pas tous les champs de la table ? Il y a deux aspects qui bloquent l’indexation générale - l’espace disque et les coûts lors de la modification des données dans la table. Chaque index créé a une taille égale à la taille des données dans le champ indexé, plus la taille des données d’allocation des enregistrements. Si nous créons des index pour chaque champ de la table, leur taille totale sera supérieure à la taille des données dans la table ! Par conséquent, la création d’un grand nombre d’index entraîne une énorme dépense d’espace disque.

Le deuxième aspect est plus important. Ce sont les dépenses lors de la modification des données dans la table. Dans un SGBD relationnel, comme vous le savez, les enregistrements dans les tables ne sont pas ordonnés et par conséquent l’ajout/suppression d’enregistrements se fait sans dépenses significatives de ressources du serveur. Même si un enregistrement est supprimé du milieu d’une base de données, il n’y a pas de déplacement de quantités de données pour combler ce vide - ce n’est pas requis : le serveur marquera simplement l’endroit vide et y écrira quelque chose si nécessaire. Quant à l’ajout, dans la plupart des cas, il est exécuté à la fin de la table. Cependant, bien que le serveur ne déplace pas les données principales dans la table lors de la modification, les données stockées dans les index sont réordonnées à chaque ajout/suppression d’enregistrements ! En d’autres termes, le serveur doit reconstruire l’index lors de l’ajout d’un enregistrement au milieu de la table. Certes, l’implémentation des index est en quelque sorte conçue pour des réorganisations fréquentes, mais ces opérations prennent néanmoins du temps et des ressources du processeur, et lorsqu’il y a un grand nombre d’index dans la table, la modification des données dans celle-ci peut être beaucoup plus lente que dans la même table sans index !

Ce sont deux raisons principales qui interfèrent avec l’indexation générale. En plus de celles-ci, il y a encore quelques remarques restreignant l’application des index. La première est la règle des 20 %. Elle dit que si la requête de récupération renvoie plus de 20 % des enregistrements de la table, l’utilisation de l’index peut ralentir la récupération des données ! Certes, la situation dépend d’une requête concrète et des conditions définies pour la récupération, mais nous devons nous rappeler que 20 % des enregistrements sont un seuil où l’efficacité de l’utilisation des index devient douteuse. La deuxième remarque n’est pas formulée aussi clairement. Elle est liée au travail de l’optimiseur InterBase.

L’optimiseur est un ensemble de mécanismes qui élaborent le plan d’exécution de la requête. Lorsque l’utilisateur donne une requête SQL à InterBase, il spécifie ce que le serveur doit retourner après l’exécution de la requête, mais ne définit pas COMMENT le serveur doit exécuter la requête. L’optimiseur, sur la base de la requête donnée, crée le plan de son exécution, c’est-à-dire d’où et dans quel ordre les données pour exécuter la requête seront prises, quels index seront utilisés à ce moment-là. Lorsque le serveur analyse les conditions de récupération (ce sont principalement des parties de l’expression WHERE, ORDER BY, etc.) pour chaque champ inclus dans la condition, le serveur essaie d’utiliser un index. Malheureusement, l’algorithme de création du plan est incomplet et l’optimiseur utilise fréquemment des index qui ne sont pas trop efficaces pour la requête concrète, ce qui peut ralentir considérablement le temps d’exécution. Par conséquent, la création d’index inutiles peut conduire à la création de plans non optimaux.

Il convient de noter que dans le clone Yaffil, ce problème est résolu grâce à l’utilisation d’algorithmes modernes de création de plans. Le troisième cas où un index n’est pas nécessaire concerne les champs avec un ensemble limité de valeurs - par exemple, le champ stockant l’information sur le sexe de la personne et contenant seulement deux valeurs possibles - « F » et « M » ; il n’y a aucun intérêt à indexer ce champ. Ainsi, nous avons examiné les principales contraintes de création d’index. Maintenant, nous devons aborder le problème de savoir quand il est nécessaire d’utiliser des index pour atteindre une amélioration de la productivité. Il y a 3 cas principaux où un champ doit être indexé :

Lorsque ce champ est utilisé dans les conditions de récupération des requêtes
Lorsque les jointures de tables utilisent ce champ
Lorsque ce champ est utilisé dans la clause de tri ORDER BY

Si le champ est appliqué de la manière mentionnée ci-dessus, la création de l’index pour celui-ci peut conduire à une amélioration de la productivité des requêtes.

Examinons la syntaxe de création des index. Voici le format complet de la commande DDL qui permet de créer des index :

CREATE [UNIQUE] [ASC[ENDING] | DESC[ENDING]] INDEX index ON table (col [, col …]);

L’expression minimale créant l’index est la suivante :

CREATE INDEX my_index ON Table_example(ID)

Dans cet exemple, l’index nommé my_index est créé pour la table Table_example, et le champ ID est le champ indexé. L’index est ascendant, c’est-à-dire que les valeurs y sont ordonnées par ordre croissant, ainsi que non unique, ce qui signifie que le champ ID peut avoir plusieurs valeurs identiques. C’est certainement l’exemple le plus simple d’index - le plus courant. Comme nous pouvons le voir dans la description de la syntaxe, un index peut contenir non pas un, mais plusieurs champs. Un tel index est utilisé lorsque des requêtes sont fréquemment exécutées et contiennent une combinaison de champs indexés dans les conditions de recherche ou de tri. Par exemple, si nous avons une table contenant les champs Nom, Prénom, Patronyme, un tel index sera appliqué lors de l’exécution de la requête qui utilise le tri par Nom, Prénom et Patronyme. En général, il n’est pas nécessaire de spécifier les conditions pour les 3 champs appliqués dans l’index pour utiliser ses avantages. Si nous voulons trier le résultat de la requête, l’index sera utilisé dans le cas où le premier champ dans une condition de tri coïncide avec le premier champ de l’index. Par exemple, notre index sera appliqué dans le cas d’un tri par Nom et Prénom.

Selon la documentation, pour l’optimisation de l’exécution de requêtes contenant dans la clause WHERE une jointure de champs avec la condition OR, nous devrions utiliser non pas l’index agrégé, mais plusieurs index simples pour tous les champs inclus dans la condition OR.

Что касается вопроса о порядке сортировки индекса, он может быть либо возрастающим, либо убывающим. Зачем нам нужны разные порядки сортировки? Очевидно, для разных сортировок! Если мы хотим отсортировать людей по фамилии в возрастающем порядке, мы создаем возрастающий индекс (ASC), а если в убывающем (от Z до A) - то убывающий! Если мы хотим и то, и другое, нам придется создать оба индекса.

Поддержка ссылочной целостности с помощью индексов

В определении индекса есть еще одна опция - UNIQUE. Если мы ее укажем, индекс позволит вставлять в таблицу только уникальные значения. Фактически, это основа для реализации уникальных ключей. Уникальные ключи широко используются в базах данных. То есть РК - это уникальный ключ-индекс, но не каждый UK является РК. Выше мы говорили только о РК. Первичный ключ - это наиболее часто используемый тип уникального ключа. При создании первичного ключа для таблицы автоматически создается уникальный индекс. Ему присваивается имя, состоящее из RDB$PRIMARYNNN, где NNN - последовательный уникальный номер в пределах базы данных. Таким образом, два основных ограничения ссылочной целостности - уникальный ключ и первичный ключ реализуются с помощью уникального индекса. Очевидно, что понятие уникальности несовместимо с понятием неопределенного значения. Другими словами, в полях, входящих в уникальные индексы, не должно быть значений типа NULL. Перед созданием уникального индекса для поля необходимо установить ограничение NOT NULL. Если индекс создается для уже существующих данных, то при создании проверяется, не содержат ли индексируемые поля повторяющихся значений. Если содержат, вам будет запрещено создавать индекс.

Помимо ограничений уникального и первичного ключа, механизм индексов лежит в основе реализации еще одного ограничения ссылочной целостности - внешнего ключа. Ограничение внешнего ключа устанавливается для одного или нескольких полей любой таблицы и предотвращает вставку в эти поля значений, которые не входят в первичный ключ другой, родительской таблицы. Для реализации внешнего ключа, т.е. для выполнения проверки наличия значения в родительской таблице, автоматически создается специальный индекс. Его имя - RDB$FOREIGNNN, где NNN - последовательный уникальный номер в пределах базы данных.

Почему механизм индексов используется для реализации ограничений ссылочной целостности? Дело в том, что индексы в InterBase находятся в особом, привилегированном положении - говорят, что они выполняются вне контекста транзакций. Это очень важное свойство. Мы поговорим о транзакциях позже, в главе, посвященной им. Сейчас мы лишь упомянем, что когда индексы находятся вне транзакций, это означает, что все пользователи, одновременно работающие с данными в одной таблице, должны соблюдать ограничения ссылочной целостности.

Оптимизация производительности индексов

В названии этой части можно обнаружить некоторый парадокс - индексы, как было сказано выше, предназначены для ускорения выполнения запросов, и оказывается, что их тоже нужно оптимизировать! Но что поделать (такова жизнь) - кто-то должен заботиться об индексах. Что происходит с индексами? Почему они “теряют форму”? Придется еще раз сказать, что индексы реализованы в виде бинарного дерева. И когда в таблицу добавляется новая запись (обновляется, удаляется - как угодно), в дерево добавляется новая ветвь. Эти ветви добавляются не в середину дерева, а к вершинам других ветвей. Постепенно дерево становится все более и более ветвистым (или несбалансированным), а поиск - менее эффективным. Перестройка дерева или (в некоторых случаях) пересчет статистики могут улучшить ситуацию.

Периодически требуется пересоздавать индекс для восстановления его производительности. Пересоздание индекса происходит в следующих случаях:

При перестройке индекса с помощью команды ALTER INDEX.
При удалении и повторном создании индекса с помощью команд DROP INDEX и CREATE INDEX.
При резервном копировании и восстановлении из резервной копии с помощью инструмента gbak.

Также можно использовать пересчет статистики. Но необходимо понимать, что эта операция не меняет состояние индекса, она лишь сообщает оптимизатору точную информацию о его состоянии, позволяя правильно использовать этот индекс. Другими словами, пересчет статистики - это не “лечение” индекса, а лишь точная диагностика его состояния. Рассмотрим все эти способы оптимизации индексов более подробно. Использование команды ALTER INDEX имеет следующий формат:

ALTER INDEX имя {ACTIVE | INACTIVE};

Здесь имя - это имя индекса, а ACTIVE и INACTIVE - два состояния индекса, в которые его можно перевести с помощью команды ALTER INDEX. Параметр ACTIVE означает, что индекс активен и может применяться во всех запросах и процедурах. Если вы установите для индекса значение INACTIVE, это приведет к отключению его использования. Для перестройки дерева необходимо последовательно выполнить две команды:

ALTER INDEX имя INACTIVE; ALTER INDEX имя ACTIVE;

Таким образом, индекс будет перестроен. Использование ALTER INDEX имеет ряд ограничений: нельзя перестраивать индексы, используемые в первичных, уникальных и внешних ключах; нельзя перестраивать индекс, если он в данный момент используется каким-либо запросом; а также для изменения индекса необходимо иметь права администратора (SYSDBA) или быть создателем данного индекса.

Пересоздание индекса с помощью команд DROP INDEX и CREATE INDEX приводит к полному удалению индекса из базы данных, а затем к его созданию с чистого листа. Синтаксис команды DROP INDEX очевиден:

DROP INDEX имя_индекса;

После удаления необходимо создать индекс с тем же именем и параметрами с помощью команды CREATE INDEX, синтаксис которой мы уже рассмотрели. Способ перестройки индекса путем его полного пересоздания имеет ограничения, аналогичные ограничениям для использования ALTER INDEX.

Третий способ перестройки индекса основан на свойстве резервных копий баз данных InterBase, создаваемых утилитой gbak. Дело в том, что при резервном копировании данные, входящие в индекс, не сохраняются в резервной копии, сохраняется только определение индекса. При восстановлении из резервной копии индекс пересоздается. Если вы хотите узнать о резервном копировании более подробно, обратитесь к главе “Резервное копирование и восстановление из резервной копии” (часть 4).

Четвертый способ повышения производительности индексов - сбор статистики по индексам с помощью команды SET STATISTICS. Статистика таблицы - это значение в диапазоне от 0 до 1, которое зависит от количества различных записей в таблице. Оптимизатор InterBase использует статистику для определения эффективности применения того или иного индекса в запросе. Когда количество записей в таблице может существенно измениться (например, из-за большого количества вставок или удалений), пересчет статистики может значительно повысить производительность. Команда пересчета статистики выглядит следующим образом:

SET STATISTICS INDEX имя;

Здесь имя - это имя индекса, для которого пересчитывается статистика. Пересчет статистики не перестраивает индекс, и поэтому он свободен от большинства ограничений, установленных для описанных выше способов повышения производительности, за исключением того, что пересчитывать статистику может только создатель индекса или системный администратор (пользователь с именем SYSDBA). Правильная статистика позволяет оптимизатору принять верное решение об использовании того или иного индекса.

Мы рассмотрели несколько способов повышения производительности индексов. С помощью команд ALTER INDEX и DROP/CREATE INDEX мы можем перестроить любые индексы, кроме системных индексов, создаваемых автоматически и предназначенных для обеспечения ссылочной целостности. Если вы хотите перестроить эти индексы, вам следует использовать команды изменения и создания таблиц - ALTER TABLE и CREATE TABLE, поскольку эти индексы являются неотъемлемой частью табличных ключей.