Индексы (InterBase и Firebird)

Алексей Ковязин, последнее обновление 07-Сен-2005

Концепция, положенная в основу индексов, проста и наглядна и является одной из важнейших основ проектирования баз данных. На основе индексов строятся многие базовые объекты базы данных, и, более того, правильное использование индексов является ключом к повышению производительности приложений баз данных. Однако что такое индекс? Индекс - это упорядоченный указатель на записи в таблице. Указатель означает, что индекс содержит значения одного или нескольких полей таблицы и адреса страниц данных, где эти значения расположены (подробнее о страницах данных см. главу «Структура базы данных InterBase») (часть 4). Другими словами, индекс состоит из пар значений «значение поля» - «физическое расположение этого поля».

Таким образом, по значению поля (или полей), включенного в индекс, используя индекс, мы можем быстро найти то место в таблице, где находится запись, содержащая это значение. Упорядоченный означает, что значения полей, хранящиеся в индексе, упорядочены. Очень часто индекс сравнивают с библиотечным каталогом, в котором все книги записаны на карточки и упорядочены некоторым образом: по алфавиту или темам, и в каждой карточке содержится информация о том, где именно данная книга находится в хранилище.

Зачем нужны индексы?

Единственное, чему способствуют индексы, - это ускорение поиска записей по индексируемому полю (индексируемое - означает включенное в индекс). Основная функция индексов - обеспечить быстрый поиск записей в таблице. Любое использование индекса сводится к этому.

Как реализована эта функция поиска? На входе этой функции мы имеем значение индексируемого поля (или нескольких полей). В результате поиска мы должны получить всю запись, в которой индексируемое поле имеет заданное значение. Сначала в индексе (точнее, в упорядоченном массиве значений индексируемого поля) ищется требуемое значение, затем берется адрес страницы данных, где находится требуемая запись, сервер переходит на эту страницу и читает найденную запись. Это выглядит довольно неудобно, однако поиск с использованием индекса во много раз быстрее, чем последовательный перебор всех значений из таблицы.

Если продолжить аналогию между индексом и библиотечным каталогом, мы увидим, что поиск записей с использованием индекса очень похож на поиск книги по карточке. Когда мы находим книгу в довольно небольшом каталоге (по сравнению со всем библиотечным хранилищем), мы сразу получаем информацию о том, где именно хранится книга, и можем идти прямо туда. Поиск без использования индекса можно сравнить с последовательным перебором всех книг в библиотеке!

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

Как они организованы?

Индекс не является частью таблицы, это отдельный объект, связанный с таблицей и другими объектами базы данных. Это очень важный момент реализации СУБД, позволяющий отделить хранение информации от ее представления.

InterBase, как и любая другая реляционная база данных, хранит записи в таблицах в неупорядоченном виде, то есть вообще не заботится о том, как записи физически расположены в таблице. Неупорядоченное хранение означает, что две записи, добавленные в таблицу одна за другой, могут не находиться рядом друг с другом. Более того, данные, извлекаемые из таблицы, также не имеют порядка, кроме того, который должен быть явно указан пользователем, выполняющим поисковый запрос.

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

Разделение хранения данных и их представления дает дополнительные преимущества по сравнению с прямой сортировкой - возможно, вам потребуется сортировать исходную таблицу разными способами. Тогда вам помогут индексы - для каждой таблицы может быть до 64 индексов!

Если говорить о реализации индексов на физическом уровне, они представляют собой бинарное дерево, узлы которого представляют пары «значение поля в индексе» - «расположение данных в таблице». Поиск требуемой записи в индексе выполняется с помощью механизма хэш-поиска - одного из самых быстрых алгоритмов поиска.

Применение индексов

Теперь, когда ясно, что мы можем требовать от индексов, самое время узнать об их функции в базе данных. Индексы используются в трех основных случаях:

Ускорение выполнения запросов. Индексы создаются для полей, используемых в условиях поиска SQL-запросов.
Поддержка уникальности значений в полях; ограничение первичного ключа (о котором рассказывалось в главе «Таблицы. Первичные ключи») требует, чтобы в таблице не было двух одинаковых значений полей, входящих в первичный ключ. Чтобы выполнить это условие, при вставке новой записи следует искать то же значение, которое будет вставлено. Для поиска записей используется особая разновидность индекса - уникальный индекс (см. ниже).
Поддержка ссылочной целостности. Ограничения внешних ключей (которые рассматриваются в главе «Ограничения базы данных») используются для проверки того, что значения, вставляемые в таблицу, обязательно существуют в другой таблице. При создании внешнего ключа автоматически создается индекс. Этот индекс применяется для ускорения запросов, использующих соединение таблиц, а также для проверки условий внешнего ключа. Мы кратко рассмотрели все возможные применения индексов. Теперь рассмотрим особенности каждого случая более подробно и ответим на наиболее часто возникающие вопросы, касающиеся применения индексов.

Ускорение выполнения запросов с помощью индексов

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

Второй момент более важен. Это затраты при изменении данных в таблице. В реляционной СУБД, как известно, записи в таблицах неупорядочены, и поэтому добавление/удаление записей происходит без значительных затрат ресурсов сервера. Даже если запись удаляется из середины базы данных, нет перемещения объемов данных для заполнения этой пустоты - это не требуется: сервер просто пометит пустое место и запишет туда что-нибудь при необходимости. Что касается добавления, в большинстве случаев оно выполняется в конец таблицы. Однако, хотя сервер не перемещает основные данные в таблице при изменении, данные, хранящиеся в индексах, переупорядочиваются каждый раз при добавлении/удалении записей! Другими словами, серверу приходится перестраивать индекс при добавлении записи в середину таблицы. Конечно, реализация индекса так или иначе рассчитана на частые реорганизации, но эти операции тем не менее занимают время и ресурсы процессора, и при большом количестве индексов в таблице изменение данных в ней может быть гораздо медленнее, чем в той же таблице без индексов!

Это две основные причины, препятствующие всеобщему индексированию. Кроме них, есть еще несколько замечаний, ограничивающих применение индексов. Первое - правило 20 %. Оно гласит, что если поисковый запрос возвращает более 20 % записей из таблицы, использование индекса может замедлить поиск данных! Конечно, ситуация зависит от конкретного запроса и условий, заданных для поиска, но следует помнить, что 20 % записей - это порог, когда эффективность использования индексов становится сомнительной. Второе замечание сформулировано не так четко. Оно связано с работой оптимизатора InterBase.

Оптимизатор - это совокупность механизмов, которые разрабатывают план выполнения запроса. Когда пользователь передает любой SQL-запрос в InterBase, он указывает, что сервер должен вернуть после выполнения запроса, но не определяет, КАК сервер должен выполнить запрос. Оптимизатор на основе данного запроса создает план его выполнения, т.е. откуда и в каком порядке будут взяты данные для выполнения запроса, какие индексы при этом будут использованы. Когда сервер анализирует условия выборки (это в основном части выражения WHERE, ORDER BY и т.д.) для каждого поля, включенного в условие, сервер пытается использовать индекс. К сожалению, алгоритм создания плана несовершенен, и оптимизатор часто использует индексы, которые не слишком эффективны для конкретного запроса, из-за чего время выполнения может существенно замедлиться. Поэтому создание ненужных индексов может привести к созданию неоптимальных планов.

Следует отметить, что в клоне Yaffil эта проблема решена благодаря использованию современных алгоритмов создания планов. Третий случай, когда индекс не нужен, - это поля с ограниченным набором значений. Например, поле, хранящее информацию о поле человека и содержащее только два возможных значения - «F» и «M»; нет смысла индексировать это поле. Итак, мы рассмотрели основные ограничения при создании индексов. Теперь следует рассмотреть проблему, когда необходимо использовать индексы для достижения повышения производительности. Существует 3 основных случая, когда поле должно быть индексировано:

Когда это поле используется в условиях выборки в запросах
Когда соединения таблиц используют это поле
Когда это поле используется в операторе сортировки ORDER BY Если поле применяется указанным выше способом, создание индекса для него может привести к улучшению производительности запросов.

Рассмотрим синтаксис создания индексов. Вот полный формат команды DDL, которая позволяет создавать индексы:

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

Минимальное выражение, создающее индекс, выглядит следующим образом:

CREATE INDEX my_index ON Table_example(ID)

В этом примере индекс с именем my_index создается для таблицы Table_example, а поле ID является индексируемым полем. Индекс является восходящим, т.е. значения в нем упорядочены по возрастанию, а также неуникальным, что означает, что поле ID может содержать несколько одинаковых значений. Это, конечно, самый простой пример индекса - самый распространенный. Как видно из описания синтаксиса, индекс может содержать не одно, а несколько полей. Такой индекс используется, когда запросы часто выполняются и содержат комбинацию индексированных полей в условиях поиска или сортировки. Например, если у нас есть таблица, содержащая поля Фамилия, Имя, Отчество, такой индекс будет применяться при выполнении запроса, использующего сортировку по Фамилии, Имени и Отчеству. В общем случае не обязательно указывать условия для всех 3 полей, используемых в индексе, чтобы воспользоваться его преимуществами. Если мы хотим отсортировать результат запроса, индекс будет использован в случае, если первое поле в условии сортировки совпадает с первым полем в индексе. Например, наш индекс будет применен в случае сортировки по Фамилии и Имени.

Согласно документации, для оптимизации выполнения запроса, содержащего в операторе WHERE соединение полей с условием OR, следует использовать не составной индекс, а несколько одиночных для всех полей, включенных в условие 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 name {ACTIVE | INACTIVE};

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

ALTER INDEX name INACTIVE; ALTER INDEX name 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 name;

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

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