Индексы, кластеры

В правильно спроектированной базе данных каждая таблица содержит первичный ключ, что означает наличие индекса. В большинстве СУБД используются индексы . Отметим, что если используется составной индекс, то поиск по всем атрибутам, входящим в индекс, начиная со второго, будет медленным. Допустим, определен индекс index1(id1, id2), в этом случае поиск значений, удовлетворяющих условию id2=1, будет медленным (не исключено, что оптимизатор вообще не будет использовать этот индекс для обработки данного условия и будет принято решение о полном сканировании данных), а поиск значений, удовлетворяющих условию id1=1 and id2=1, будет быстрым. Данные особенности следует учитывать при определении индексов в схеме базы данных, а именно:

• индексировать нужно атрибуты, по которым наиболее часто осуществляется поиск или соединение. Наличие индекса замедляет операции модификации, но ускоряет поиск;
• наличие индекса обязательно, если для атрибута или набора атрибутов указано ограничение unique. Такие индексы СУБД создает автоматически, если в описании таблицы указаны ограничения unique;
• индекс может быть использован для выборки данных в заданном порядке. В этом случае не вызывается процесс сортировки ответа, а используется уже готовый индекс;
• атрибуты, входящие во внешний ключ, также следует индексировать, если СУБД не делает эту операцию автоматически при декларации внешнего ключа;
• в некоторых СУБД поддерживаются bitmap-индексы, которые очень эффективны при поиске на равенство, но для поиска на этот тип индексов не годится;
• в некоторых СУБД поддерживаются хеш-индексы, например для кластеров. Такие индексы эффективно используются при поиске на равенство.

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

Для того чтобы выбрать тот или иной тип индекса, требуется внимательно изучить руководство администратора СУБД. Оптимизатор SQL использует различные типы доступа к данным при обработке запросов, и индексирование существенно влияет на выбор оптимизатора.

Приведем некоторые способы доступа к данным на примере выборки select id, name from xtable where id=10:

• Таблица не индексирована. В этом случае применяется полное сканирование, которое не является эффективным, если объем данных большой, в таблице много данных, не удовлетворяющих условию, размер кортежа существенно превосходит размер атрибута id.
• Атрибут id индексирован; тип индекса – . Тогда применяется индексное сканирование; полное сканирование может быть выбрано только в случае, если объем данных, удовлетворяющих данному условию, является большим (эта информация анализируется статистическим оптимизатором) и сравним с количеством записей в таблице. Индексное сканирование применяется лишь тогда, когда размер индексированных атрибутов меньше размера кортежа и все необходимые для обработки запроса данные могут быть получены из индекса; в остальных случаях может быть применено полное сканирование.
• Атрибут id входит в составной индекс, и является первым (лидирующим) атрибутом индекса, при этом тип индекса – . Аналогично предыдущему примеру,  применяется индексное сканирование.
• Атрибут id входит в составной индекс, он не первый атрибут индекса; тип индекса – . Индексное сканирование применяется лишь тогда, когда размер индексированных атрибутов меньше размера кортежа и все необходимые для обработки запроса данные могут быть получены из индекса; в остальных случаях применяется полное сканирование.
• Атрибут id индексирован; тип индекса – хеш. Здесь применяется индексное сканирование для поиска на =; если бы условие было id <=10, то применение хеш-индекса для такого поиска не эффективно.
• Атрибут id индексирован; тип индекса – bitmap. Здесь применяется индексное сканирование для поиска на =; если бы условие было id <=10, то применение bitmap-индекса для такого поиска не эффективно.
• Атрибут id является ключом хеш-кластера. В этом случае применяется алгоритм хеширования при поиске блока данных для чтения. При хорошем алгоритме и правильном размере кластера поиск может быть осуществлен за одно чтение; при ошибках в выборе алгоритма и блока кластера это может составить до нескольких тысяч операций чтения блоков.
• Атрибут id является ключом индексного кластера. Здесь применяется индексное сканирование, почти аналогично случаю с индексом .
• Таблица кластеризована, id не является ни кластерным ключом, ни лидирующим в составном индексе . В этой ситуации для кластера применяется полное сканирование.

Мы привели только некоторые правила выполнения операции поиска в зависимости от наличия и типа индекса. В реализации используемой вами СУБД могут быть приняты иные принципы. Подробности использования типов сканирования при поиске данных даются в руководстве по настройке СУБД и в руководстве администратора СУБД.

А почему бы не проиндексировать все, если индексный поиск быстрее полного сканирования? Очевидно, что индекс занимает место на диске, вопрос в том – сколько. Например, индексируется атрибут integer – это 4 байта. Но в кроме собственно значения ключа в индексе хранятся и внутренний идентификатор кортежа, и некоторая служебная информация, так что все вместе может составлять 4-8 байт. Чтобы точно посчитать эту величину для используемой вами СУБД, следует обратиться к руководству администратора: посмотрите размер идентификаторов ROWID (Oracle), RID (DB2) и т.д., а также размер страницы индекса (как правило, это 4 Кбайт).

При выборе стратегии индексации следует придерживаться двух простых принципов:

• чем больше индексов, тем выше затраты на выполнение DML-операций. По грубым оценкам затрат: если принять за 1 работу по вставке строки в таблицу, то работа по вставке той же записи в один индекс равна 2 или 3 (для разных СУБД);
• в любое значение может быть найдено за такое количество операций чтения, сколько уровней у дерева (дерево трех уровней для значений integer, например, содержит порядка 533 731 324 ключей, если страница дерева 4 Кбайт). Такие индексы отлично используются при поиске на =, <, >, <=, >=, between, и достаточно хорошо модифицируются. В bitmap-индексах содержатся готовые битовые векторы, отражающие вхождение или невхождение значения в ответ при поиске на равенство, но такие индексы плохо модифицируются и больше подходят для хранилищ данных, например для индексирования вхождения слов в текстовый документ. Хеш-индексы позволяют осуществлять поиск на равенство, хеш-функция используется для поиска блока кластеризованных данных, содержащего нужные значения. Если алгоритм хеш-функции хорош и размер кластера указан верно, то поиск может быть осуществлен за одно чтение. Эти индексы, как правило, используют для создания кластеров.

Обратите внимание, хранит ли СУБД в индексах NULL. Если NULL в индексе не хранится, то вероятность использования полного сканирования для атрибутов без декларации not NULL резко повышается. Если NULL хранится в индексе (обычно его считают самым большим или самым маленьким при построении и специальным значением при построении bitmap и хеш-индексов), то выясните, для каких операций поиска индексы будут использованы оптимизатором SQL. Эта информация, как правило, содержится в руководстве администратора. Можно проверить и экспериментально, создав тестовую таблицу с объемом данных примерно 20 тыс. записей (чтобы оптимизатор не выбирал полное сканирование по причине малого объема) и выполнив исследуемый запрос, а затем произвести explain плана запроса (если подобный сервис предоставляется СУБД).