Bookmark Lookup

Автор: Craig Freedman Bookmark Lookup

Перевод Ирины Наумовой

В своей прошлой статье, я рассказал о том, как SQL Server использует индекс для эффективного обращения к строке, квалифицируемой предикатом. Для принятия решения о том использовать ли индекс, SQL Server рассматривает несколько факторов, которые включают проверку того, покрывает ли индекс все используемые в запросе столбцы задействованной таблицы.

Что означает "индекс покрывает столбец"

Куча или кластерный индекс для таблицы (часто называемые "базой таблицы") содержит (или покрывает) все столбцы таблицы. С другой стороны, некластеризованные индексы, содержат (или покрывают) только некоторое подмножество столбцов в таблице. Ограничивая набор столбцов, сохраненных в некластеризованном индексе, мы можем сохранять большее количество строк на каждой странице. Таким образом, мы экономим дисковое пространство и улучшаем эффективность поиска и сканирования, снижая количество операций ввода-вывода и число затрагиваемых страниц.
Каждый некластеризованный индекс покрывает ключевые столбцы, которые были определены при его создании. Также, если база таблицы - это кластерный индекс, каждый построенный на этой таблице некластеризованный индекс, покрывает ключи кластерного индекса (часто называемые "ключ кластеризации") независимо от того, являются ли они частью ключевых столбцов некластеризованного индекса. В SQL Server 2005 также можно добавлять дополнительные неключевые столбцы к некластеризованному индексу, используя предложение "Include" в инструкции создания индекса.
В качестве примера рассмотрим следующую схему:

create table T_heap (a int, b int, c int, d int, e int) create index T_heap_a on T_heap (a) create index T_heap_bc on T_heap (b, c) create index T_heap_d on T_heap (d) include (e)   create table T_clu (a int, b int, c int, d int, e int) create unique clustered index T_clu_a on T_clu (a) create index T_clu_b on T_clu (b) create index T_clu_ac on T_clu (a, c) create index T_clu_d on T_clu (d) include (e)

Ниже приведена таблица покрытия столбцов индексами для этого примера:

Индекс	Покрываемые столбцы
T_heap_a	a
T_heap_bc	b, c
T_heap_d	d, e
T_clu_a	a, b, c, d, e
T_clu_b	a, b
T_clu_ac	a, c
T_clu_d	a, d, e

Обратите внимание что порядок столбцов в индексе не соответствует покрытию колонок.

Какое отношение это имеет к поиску по индексу и поиску закладок?

Давайте рассмотрим следующий запрос (будем использовать вышеприведенную схему):

select e from T_clu where b = 2

На первый взгляд, кажется, что этот запрос является прекрасным кандидатом для поиска по некластеризованному индексу, созданному по столбцу b (T_clu_b), и при использовании предиката выборки "b = 2". Однако, этот индекс не покрывает столбец "e", таким образом поиск или сканирование этого индекса не может вернуть значение столбца "e". Решение простое. Для каждой строки, которую мы выбираем из некластеризованного индекса, мы можем найти значение столбца "e" в кластерном индексе. Мы называем эту операцию "поиск закладки". " Закладка" - это указатель на строку в куче или кластерном индексе. Мы сохраняем закладку для каждой строки в некластеризованном индексе для того, чтобы можно было перейти из некластеризованного индекса к соответствующей строке в базе таблицы.

Следующий рисунок иллюстрирует поиск закладки:

План исполнения для примера

В SQL Server 2000 поиск закладки осуществляется с помощью специального итератора, который используется и тогда, когда база таблицы является кластеризованным индексом, и тогда, когда это куча:

|--Bookmark Lookup(BOOKMARK:([Bmk1000]), OBJECT:([T_clu]))        |--Index Seek(OBJECT:([T_clu].[T_clu_b]), SEEK:([T_clu].[b]=2) ORDERED FORWARD)

В SQL Server 2005 используется сканирование кластерного индекса, если база таблицы - кластеризованный индекс, или RID (record ID) если базовая таблица - куча:

|--Nested Loops(Inner Join, OUTER REFERENCES:([T_clu].[a]))        |--Index Seek(OBJECT:([T_clu].[T_clu_b]), SEEK:([tempdb].[dbo].[T_clu].[b]=(2)) ORDERED FORWARD)        |--Clustered Index Seek(OBJECT:([T_clu].[T_clu_a]), SEEK:([T_clu].[a]= [T_clu].[a]) LOOKUP ORDERED FORWARD)

|--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000]))        |--Index Seek(OBJECT:([T_heap].[T_heap_a]), SEEK:([T_heap].[a]=(2)) ORDERED FORWARD)        |--RID Lookup(OBJECT:([T_heap]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)

Можно сказать, что поиск по кластерному индексу - это поиск закладки с ключевым словом LOOKUP в тексте плана исполнения или атрибутом Lookup="1" в плане исполнения формата XML. Я поясню поведение вложенного цикла в следующей статье. Циклические соединения и поиск по кластеризованному индексу (или поиск по RID) делают то же самое что и поиск закладки в SQL Server 2000.

Выгоды и потери

Поиск закладки - недешевая операция. Предположим (типичная ситуация) что между индексными ключами некластеризованного и кластеризованного индексов нет никакой корреляции, и при каждом поиске закладки выполняется ввод-вывод в кластерный индекс случайного типа. Случайные операции ввода-вывода обходятся дорого. При сравнении различных альтернатив плана, включая сканирование, поиск и поиск закладок, оптимизатор должен решить, что обойдётся дешевле. Он может выбрать операции ввода-вывода последовательного типа (используя сканирование индекса), но при этом будет затронуто большое число строк. Если он выберет поиск с условием, селективность уменьшится, и будут охвачены все требующиеся столбцы. И наконец, он может выбрать вариант с меньшим числом операций случайного ввода-вывода, затронув меньше строк, и используя поиск с условием, характеризуемый большей селективностью и наличием поиска закладок.
В некоторых случаях Вы можете заставить оптимизатор использовать лучший вариант плана, создав новый индекс, или добавив один или несколько столбцов к существующему индексу. Это позволит устранить поиск закладок или заменить сканирование поиском. В SQL Server 2000 единственным способом добавления столбцов к индексу являлось добавление ключевых столбцов. Как я уже упомянул выше, в SQL Server 2005, Вы можете добавлять также столбцы, используя предложение 'include' в инструкции создания индекса. Присоединяемые столбцы более эффективны, чем ключевые столбцы; они экономят дисковое пространство и делают поиск и модификацию индекса более эффективными.
Не стоит забывать, что всякий раз, когда Вы создаете новые индексы или добавляете новые ключевые/присоединяемые столбцы к существующему индексу, выделяется дополнительное дисковое пространство, и это делает более дорогостоящими операции поиска и модификации индекса. Таким образом, необходимо найти баланс между частотой использования и важностью использующих новый индекс запросов, чтобы его добавление/изменение не привело к замедлению выборки или внесения изменений в данные.