Индексы
Концепция, положенная в основу индексов, проста и наглядна и является одной из важнейших основ проектирования баз данных. На основе индексов базируются многие основополагающие объекты базы данных, к тому же правильное использование индексов является ключом к улучшению производительности приложений баз данных.
Что же представляет собой индекс? Индекс - это упорядоченный указатель на записи в таблице. Указатель означает, что индекс содержит значения одного или нескольких полей в таблице и адреса страниц данных, на которых располагаются эти значения. Другими словами, индекс состоит из пар значений "значение поля" - "физическое расположение этого поля". Таким образом, по значению поля (или полей), входящего в индекс, при помощи индекса можно быстро найти то место в таблице, где располагается запись, содержащая это значение.
Упорядоченный - означает, что значения полей, хранящихся в индексе, упорядочены.
Очень часто индекс сравнивают с библиотечным каталогом, в котором все книги записаны на карточки и упорядочены каким-то образом: по алфавиту или по темам, а в каждой карточке написано, где именно в хранилище располагается данная книга.
Для чего нужны индексы?
Единственное, чему способствуют индексы, - это ускорению поиска записи по ее индексированному полю (индексированное - значит входящее в индекс).
Итак, основная функция индексов - обеспечивать быстрый поиск записи в таблице. Любое использование индексов сводится именно к этому.
Как реализована эта функция поиска? На входе функции мы имеем значение индексированного поля (или нескольких полей). В результате поиска мы должны получить всю запись, в которой индексированное поле имеет заданное значение. Сначала в индексе (точнее, в упорядоченном массиве значений индексированного поля) ищется нужное значение, затем берется адрес страницы данных, на которой лежит искомая запись, сервер перемещается на эту страницу и читает найденную запись. Выглядит довольно громоздко, однако поиск с помощью индекса происходит во много раз быстрее, чем при последовательном переборе всех значений из таблицы.
Если продолжить аналогию индекса с библиотечным каталогом, то поиск записи с помощью индекса очень похож на поиск книги с помощью карточки. Сюит нам найти книгу в относительно небольшом по объему каталоге (по сравнению со всем библиотечным хранилищем), как сразу получаем информацию о точном местонахождении книги и можем направиться прямиком туда. Поиск же без использования индекса можно сравнить с последовательным перебором всех книг в библиотеке!
Перебор всех записей в таблице называется прямым или естественным (NATURAL). Надо сказать, что, несмотря на мощности современных компьютеров, при достаточно большом количестве записей в таблице естественный перебор может быть очень долгим процессом.
Как устроены индексы
Индекс не является частью таблицы - это отдельный объект, связанный с таблицей и другими объектами базы данных. Это очень важный момент реализации СУБД, который позволяет отделить хранение информации от ее представления.
InterBase, как и всякая другая реляционная база данных, хранит записи в таблицах в неупорядоченном виде, т. е. совершенно не заботится о том, как физически располагаются записи в таблице. Неупорядоченность хранения означает, что две записи, добавляемые в таблицу одна за другой, совсем не обязательно окажутся "рядом". Более того, данные, извлекаемые из таблицы, также не имеют какого-либо порядка, кроме того, который явно должен быть указан пользователем, составляющим запрос на выборку.
Однако без упорядочения хранящихся данных обойтись невозможно: конечные пользователи приложений хотят видеть свои данные в определенном порядке - например, фамилии людей по алфавиту. Задачу представления данных в упорядоченном виде решают индексы. Значения полей, входящих в индекс упорядочены и представлены в особом виде, оптимизированном для поиска нужных значений (а именно это и нужно для построения упорядоченных последовательностей). Отделение хранения данных от их представления дает дополнительные преимущества по сравнению с непосредственной сортировкой - исходную таблицу может потребоваться отсортировать по-разному. Тогда на помощь приходят индексы - их может быть до 64 на каждую таблицу!
Если говорить о реализации индексов на физическом уровне, то они представляют двоичное дерево, узлы которого представляют собой пары "значение поля в индексе" - "расположение данных в таблице". Поиск нужной записи в индексе идет с помощью механизма хеш-поиска - одною из самых быстрых алгоритмов поиска.
Применение индексов
Теперь, когда ясно, что можно требовать от индексов, настало время разобраться с тем, какую роль они играют в базе данных. Индексы используются в трех основных случаях:
Ускорение выполнения запросов. Индексы создаются для полей, которые используются в условиях поиска SQL-запросов.
Обеспечение уникальности значений в полях; Ограничение первичного ключа (о которых рассказывалось в главе "Таблицы. Первичные ключи") требует, чтобы во всей таблице не нашлось двух одинаковых значений полей, входящих в первичный ключ. Чтобы выполнить это условие, необходимо при каждой вставке новой записи производить поиск такого же значения, которые будет вставлено. Для поиска записи используется особая разновидность индекса - уникальный индекс (см. ниже).
Обеспечение ссылочной целостности. Ограничения внешних ключей Foreign key (которые рассмотрены в главе "Ограничения базы данных") используются для проверки того, чтобы вставляемые в таблицу значения обязательно существовали в другой таблице. При создании внешнего ключа автоматически создается индекс, который применяется как для ускорения запросов, использующих соединение таблиц, так и для проверки условий внешнего ключа.
Вот вкратце и все возможные применения индексов. Теперь мы рассмотрим особенности каждого случая более подробно и ответим на ряд часто возникающих вопросов, связанных с применением индексов.
Ускорение выполнения запросов с помощью индексов
Выше описано, что применение индексов может значительно ускорить выполнение запросов. Это действительно так для большинства случаев, но есть и определенные оговорки. Сначала ответим на вопрос, часто возникающий у тех, кто познакомился с индексами. Раз индексы ускоряют выборку из базы данных, почему бы не проиндексировать все поля в таблице? Есть два момента, препятствующих всеобщей индексации, - это дисковое пространство и издержки при модификации данных в таблице. Каждый создаваемый индекс имеет объем, равный объему данных в индексированном поле, плюс объем данных о расположении записей. Если создать индексы на каждое поле в таблице, то их суммарный объем будет больше, чем объем данных в таблице! Поэтому создание большого количества индексов приводит к большому расходу дискового пространства.
Второй момент более важен - это издержки при модификации данных в таблице. В реляционной СУБД, как вы знаете, записи в таблицах неупорядочены и потому добавление/удаление записей происходят без значительных затрат ресурсов сервера. Даже если удаляется запись из середины базы данных, то не происходит перемещения объемов данных для того, чтобы закрыть "дыру", - это попросту не нужно: сервер просто пометит освободившееся место и при случае запишет туда что-нибудь. Что касается добавления, то оно почти всегда происходит в конец таблицы. Однако хотя основные данные в таблице и не "дергаются" сервером при модификации, но данные, хранящиеся в индексах, переупорядочиваются каждый раз при добавлении/удалении записей! То есть серверу при добавлении записи в середину таблицы, например, приходится перестраивать индекс! Конечно, реализация индекса некоторым образом рассчитана на частые перестройки, но эти действия все же занимают время и ресурсы процессора и при слишком большом количестве индексов в таблице модификация данных в ней может быть в десятки раз медленнее, чем у такой же таблицы без индексов!
Это две основные причины, которые препятствуют всеобщей индексации. Помимо них есть и еще несколько замечаний, ограничивающих применение индекса. Первое - это правило 20 %. Оно гласит, что если запрос на выборку возвращает более 20 % записей из таблицы, то использование индекса может замедлить выборку данных! Конечно, ситуация зависит от конкретного запроса и условий, наложенных на выборку, но нужно помнить, что 20 % записей являются порогом, когда эффективность использования индексов ставится под вопрос. Второе замечание формулируется не так очевидно. Оно связано с работой оптимизатора InterBase.
Оптимизатор - это совокупность механизмов, которые разрабатывают таи выполнения запроса. Когда пользователь передает InterBase какой-либо SQL-запрос, он указывает, ЧТО должен вернуть сервер в результате выполнения запроса, но не определяет, КАК сервер должен выполнять запрос. Оптимизатор на основе переданного запроса строит план его выполнения, т. е. откуда и в каком порядке будут браться данные для выполнения запроса, какие индексы будут при этом использоваться. Когда сервер анализирует условия на выборку (это в основном части выражения WHERE, ORDER BY и т. д.), то для каждого поля, входящего в условие, сервер пытается использовать индекс. К сожалению, алгоритм создания плана несовершенен и оптимизатор часто использует индексы, которые не слишком эффективны для конкретного запроса, из-за чего может существенно замедлиться время выполнения. Поэтому создание лишних индексов может привести к созданию неоптимальных планов.
Надо отметить, что в клоне Yaffil эта проблема разрешена за счет использования современных алгоритмов построения планов.
Третьим случаем, когда индекс не нужен, являются поля с ограниченным набором значений - например, поле, которое хранит информацию о поле человека и содержит только два возможных значения - "м" и "ж"; нет никакого смысла индексировать это поле.
Итак, основные ограничения на создание индексов мы рассмотрели. Теперь следует рассмотреть вопрос, когда следует использовать индексы, чтобы добиться улучшения производительности. Существует 3 основных случая, когда необходимо проиндексировать поле:
- Когда это поле используется в условиях поиска в запросах.
- Когда соединения таблиц (JOIN) используют это поле.
- Когда это поле используется в предложениях сортировки 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 может иметь несколько одинаковых значений. Это, конечно же, самый простой пример индекса - самый распространенный.
Как видно из описания синтаксиса, индекс может содержать не одно, а несколько полей. Такой индекс используется при часто выполняющихся запросах, которые содержат в условиях поиска или сортировки сочетание индексированных полей. Например, если у нас есть таблица, содержащая поля Фамилия, Имя, Отчество, то при запросе, использующем сортировку по ФИО, будет применен 1акой индекс. Вообще говоря, необязательно вводить условия на все 3 поля, применяемые в индексе, чтобы использовать его преимущества. Если мы желаем сортировать результат запроса, то индекс будет использован в случае, если первое поле в условии сортировки совпадает с первым полем в индексе, например наш индекс будет задействован в случае сортировки по Фамилии и Имени.
В документации для оптимизации выполнения запроса, содержащего в предложении WHERE соединение полей с условием OR рекомендуется, использовать не составной индекс, а несколько одинарных индексов на все поля, входящие в условие OR.
К вопросу о порядке сортировки индекса: как видно, он может быть либо возрастающим (ASQENDING]), либо убывающим (DESCENDING]). Зачем нужны разные порядки сортировки? Очевидно, для разных сортировок! Если мы желаем сортировать людей по фамилии в возрастающем порядке, то создаем возрастающий индекс (ASC), а если в убывающем (от Я до А) - то убывающий! А если хотим и то и другое, то необходимо создавать оба индекса.
Обеспечение ссылочной целостности с помощью индексов
В определении индекса имеется еще одна опция - UNIQUE. Если ее указать, то индекс позволит заносить в таблицу только уникальные значения. Фактически это служит основой для реализации уникальных ключей (UNIQUffi KEY). Уникальные ключи широко используются в базах данных. То есть РК - это уникальный ключ-индекс, но не всякий UK - это РК. Выше речь шла только о РК. Первичный ключ (Primary key) - самый распространенный вид уникального ключа. При создании первичного ключа на таблицу автоматически создается уникальный индекс, который получает имя, составленное из RDBSPRIMARYNNN, где NNN - последовательный уникальный в пределах базы данных номер. Таким образом, с помощью уникального индекса реализуются два из важнейших ограничений ссылочной целостности - уникальный ключ и первичный ключ. Очевидно, что понятие уникальности несовместимо с понятием неопределенного значения, т. е. другими словами, в полях, содержащихся в уникальных индексах, не должно быть значений типа NULL. Перед созданием уникального индекса на поле следует придать ему статус NOT NULL. Если индекс создается для уже существующих данных, то при создании будет проверено, не содержит ли индексированное поле повторяющихся значений. И если содержит, то в создании индекса будет отказано.
Помимо ограничений уникального и первичного ключа, механизм индексов лежит в основе реализации еще одного ограничения ссылочной целостности - внешнего ключа. Ограничение внешнего ключа накладывается на одно или несколько полей какой-либо таблицы и препятствует внесению в эти поля таких значений, которые не входят в первичный ключ другой, родительской таблицы. Для реализации внешнего ключа, т. е. для осуществления проверки того, существует ли значение в родительской таблице, автоматически создается особый индекс. Он имеет наименование RDB$FOREIGNNN, где NNN - последовательный у никальный в пределах базы данных номер.
Почему именно механизм индексов используется для реализации ограничений ссылочной целостности? Дело в том, что индексы в InterBase находятся в особом, привилегированном положении - говорят, что они выполняются вне контекста транзакций. Это очень важное свойство. О транзакциях мы поговорим позже, в посвященной им главе, а пока лишь скажем, что нахождение индексов вне транзакций означает, что все пользователи, одновременно работающие с данными в одной и той же таблице, вынуждены соблюдать ограничения ссылочной целостности.
Оптимизация производительности индексов
В названии этого раздела можно обнаружить некоторый парадокс - индексы, как говорилось выше, служат для того, чтобы ускорить выполнение запросов, и оказывается, что их самих надо тоже оптимизировать! Но что делать (такова жизнь) - кто-то должен заботиться и об индексах.
Что же случается с индексами? Почему они "теряют форму"? Нам придется еще раз сказать о том, что индексы реализованы в виде двоичного дерева И когда в таблицу добавляется (изменяется, удаляется - выберите по вкусу) новая запись, в дерево добавляется новая веточка. Причем веточки добавляются не в середину дерева, а на концах других веточек. Постепенно дерево становится все более "раскидистым" (также говорят - несбалансированным), а поиск по нему - все менее эффективным. Поправить положение может перестройка дерева или (в некоторых случаях) пересчет статистики. Периодически требуется пересоздавать индекс, чтобы восстанавливать его производительность. Пересоздание индекса происходит в следующих случаях:
· При перестройке индекса с помощью команды ALTER INDEX.
· При удалении и повторном создании индекса командами DROP INDEX и CREATE INDEX.
· При резервном копировании и восстановлении из резервной копии с использованием инструмента gbak.
Также можно использовать пересчет статистики. Но надо понимать, что это действие не изменяет состояние индекса, а просто сообщает оптимизатору точные данные о его состоянии, что позволяет правильно использовать этот индекс. Другими словами, пересчет статистики - это не "лечение" индекса, а только точная диагностика его состояния.
Рассмотрим подробнее все эти способы оптимизации индексов.
Использование команды ALTER INDEX имеет следующий формат:
ALTER INDEX name {ACTIVE | INACTIVE};
|
Здесь name - имя индекса, a 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, так как эти индексы являются неотъемлемой частью табличных ключей.
