Кластеризованный индекс MS SQL

Кучи, кластеризованные индексы и некластеризованные индексы

Рассмотрим теорию индексов.

• SQL Server хранит данные на страницах размером 8 килобайт – 8,060 байт

• Страницы принадлежащие объекту(например таблице) связаны в двунаправленный список

• Первые 8 страниц «объекта» хранятся в смешанных участках. После этого данные хранятся только в унифицированных участках.

• 8 страниц группируются в «участки». Смешаные участки хранят данные из разных «объектов». Унифицированные участки хранят данные одного «объекта»

• SQL Server использует страницы именуемыми — «карты размещения индексов» (Index Allocation Map) или кратко — IAM для определения страниц принадлежащих «объекту»

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

Кучи подходят для хранения небольшого количества данных.

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

Кластеризованный индекс хранит в своих узлах-листьях реальные строки данных.

Некластеризованный индекс является вспомогательной структурой, которая указывает данные в таблице

Кластеризованные индексы

  • В SQL Server индексы организованы в виде сбалансированных деревьев. Каждая страница в сбалансированном дереве индекса называется узлом индекса.

< >Верхний узел сбалансированного дерева называется корневым. Узлы нижнего уровня индекса называются конечными. < >Все уровни индекса между корневыми и конечными узлами называются промежуточными. < >В кластеризованном индексе конечные узлы содержат страницы данных базовой таблицы. < >На страницах индекса корневого и промежуточного узлов находятся строки индекса. < >Каждая строка индекса содержит ключевое значение и указатель либо на страницу промежуточного уровня сбалансированного дерева, либо на строку данных на конечном уровне индекса. < >Страницы на каждом уровне связаны в двунаправленный список.На схеме — кластеризованный индекс выглядит в виде B-дерева, где хранятся реальные строки данных таблицы в отсортированном порядке в узлах-листьях.

Т.Е. данные будут храниться так:

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

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

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

Т.к. кластеризованный индекс хранит реальные данные, нельзя создать более одного кластеризованного индекса в таблице.

Некластеризованные индексы

Некластеризованный индекс не содержит реальных данных таблицы в узлах-листьях. Узлы-листья содержат один из двух типов информации о местоположении строк данных.

Если в таблице не создан кластеризованный индекс, то некластеризованные индексы по этой таблице хранят в своих узлах-листьях идентификаторы строк (Row ID на первой схеме). Идентификатор строки указывает на реальную строку данных в таблице, по сути это — значение, включающее в себя номер файла данных, номер страницы и местоположение строки на этой странице.

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

Возможно создать до 249 некластеризованных индексов на одну таблицу.

Схема 1

Все мы помним хрестоматийное объяснение «что такое индексы в БД и как они облегчают задачи поиска нужных строк». Уверен, у большинства из вас перед глазами встаёт нечто подобное:

И сразу становится очевидно, насколько меньше данных нужно перелопатить для поиска двух-трёх нужных строк. Гениально. Просто. Понятно.
И лично мне всегда казалось, что улучшать эту схему некуда… Пока я не познакомился с кластерными индексами. Оказалось, что всё не так уж радужно с «обычными» индексами.
Итак, что же такое кластерный индекс, чем он лучше некластерного, и как с ним обстоит дело у MySQL.

Некластерные индексы

Чтобы не запутаться, до поры до времени будем рассматривать простой индекс по одному полю. Упрощённо некластерный индекс можно представить как отдельную таблицу, каждая строка в которой ссылается на одну или несколько строк в таблице с данными. Строки в индексной таблице упорядочены и сгруппированы по значениям ключевых полей. Представим элементарный запрос:
SELECT * FROM `t1` WHERE `fld1` = 12;
Совсем без индексации будет прочитана и проверена каждая строка, и неудовлетворяющие условию строки просто не попадут в результат. Но прочитаны они будут.
При использовании «обычного», некластерного индекса, задача поиска сильно ускоряется. Во-первых, индексная таблица весит много меньше таблицы с данными, а значит элементарно может быть прочитана быстрее. Во-вторых, СУБД чаще всего стараются кешировать индексы в оперативную память, которая сама по себе много шустрее жёсткого диска*. В-третьих, в индексах отсутствуют дублирующиеся строки. А значит, как только мы нашли первое значение, поиск можно прекращать — оно же и последнее. В-четвёртых, данные в индексе отсортированы. А в-третьих и в-четвёртых вместе позволяют использовать алгоритм бинарного поиска (он же метод деления пополам), эффективность которого многократно превосходит простой перебор.
* Если ресурсы позволяют, таблицу данных тоже можно (и нужно) кешировать в оперативную память. Однако индексам и месту для них в оперативной памяти, по понятным причинам, принято уделять больше внимания.
Индексация — великая сила. Но если представить все указатели индексной таблицы на строки в таблице данных ОДНОВРЕМЕННО, получится достаточно сложная «паутина»:

И эта паутина, со множеством пересекающихся стрелок, подводит нас к проблеме (просто таки наглядно её демонстрирует), которую создаёт некластерный индекс.

Фрагментация

Оптимизатор MySQL может принять решение вообще не использовать индексы для поиска по небольшим таблицам (до пары десятков записей — зависит от конкретной структуры данных и индекса). Почему? Потому что поиск простым перебором читает данные последовательно. А указатель в индексе ссылается на разрозненные участки данных. И прыжки по ссылкам из индекса в конечном итоге могут стоить дороже полного перебора.
Итак, что мы имеем на данном этапе эволюции индексирования. Представьте большую, фрагментированную с точки зрения индексации, таблицу. Как данные приходили хаотичными и неотсортированными, так они и сохранялись. Теперь представьте индексную таблицу к ней. И наш старый добрый запрос:
SELECT * FROM `t1` WHERE `fld1` = 12;
Что происходит? Находится значение в индексе — это быстро и просто — и из таблицы данных читаются строки, на которые этот индекс ссылается. Естественно, при большой фрагментированности таблицы накладные расходы на чтение из разных её частей становятся ощутимыми.
И вот тут-то нам и пригодятся…

Кластерные индексы

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

Кластерный индекс — это древовидная структура данных, при которой значения индекса хранятся вместе с данными, им соответствующими. И индексы, и данные при такой организации упорядочены. При добавлении новой строки в таблицу, она дописывается не в конец файла*, не в конец плоского списка, а в нужную ветку древовидной структуры, соответствующую ей по сортировке.
* В разных движках и при разных настройках это может быть вовсе и не конец, и вовсе и не файла. Слово файл здесь означает «некую единицу измерения данных, соответствующую одной таблице», а «конец файла» употребляется как символ последовательной, линейной записи.
Один из самых мощных и производительных движков для MySQL — InnoDB. Тому много причин, и одна из них — кластерные индексы. Проще всего понять как устроены кластерные индексы, если представить их в динамике: как они разрастаются по мере добавления данных, и как начинает ветвиться таблица.

Первый этап: плоский список

Данные в InnoDB хранятся страницами по 16 Кб. Размер одной страницы — это предельный размер узла нашей древовидной структуры, от которого зависит в какой момент начнётся ветвление. Если вся таблица помещается в одну страницу, то она хранится в виде плоского списка, отсортированного по ключевому полю, без отдельной индексной таблицы.

Точно такими же маленькими табличками в будущем будут представлены все наши данные, а соединять их в дерево будут цепочки индексных страниц.

Второй этап: дерево

Когда данные перестают помещаться в одну страницу, список превращается в дерево. Страница с данными разделяется на две, причём в том узле (на той странице), где раньше были данные, теперь располагается индекс, охватывающий обе новые страницы. Конкретный узел такого дерева обязан включать в себя индексы всех дочерних узлов или конечные данные, если узел последний. Узлы могут ссылаться друг на друга только в одном направлении: от родителя к потомку.

По мере добавления всё новых и новых данных, дерево будет усложняться и углубляться. И чем больше оно будет и ветвистее, тем больший выйгрышь даст такая схема хранения данны.

Серые страницы идентичны странице первого этапа — это просто отсортированные данные, листья (конечные узлы) нашего дерева. Голубые страницы — это промежуточные узлы дерева, содержащие только индекс и не содержащие данных. Стрелками помечены пути поиска определённых значений ключа.
Вспомним наш запрос (зелёная стрелка):
SELECT * FROM `t1` WHERE `fld1` = 12;
Обращаясь к таблице, запрос попадает на первую страницу и получает индекс, тут же отправляющий его на конечную страницу с данными, где находятся строки, удовлетворяющие критериям поиска. Страница уже прочитана на этапе поиска, все данные собраны, БД может вернуть ответ.
Однако индекс, указывающий на другую страницу, не обязательно ведёт сразу на страницу с данными. Индекс может указывать на страницу с промежуточным индексом. Возможно, при больших объёмах таблицы, БД придётся провести больше итераций поиска, но каждая такая итерация включает минимальный объём данных, а потому в целом всё равно поиск проходит быстрее.
Здесь действует простое правило, актуальное для любого типа индекса: чем разнообразнее данные, тем эффективнее использовать индекс для поиска конкретных значений.
Поскольку данные являются частью индекса, отсортированы и целенаправленно фрагментированы, очевидно что для одной таблицы может использоваться только один кластерный ключ. Из такой, достаточно сложной логики хранения индексов и данных, есть ещё одно важное следствие: операции записи, а особенно изменение имеющихся данных ключевых полей — крайне ресурсоёмкий процесс. Старайтесь использовать для кластерных индексов редко изменяемые поля.
Что касается сложных (составных) кластерных ключей, для них действует абсолютно такая же схема, только сортировка данных осуществляется по двум полям. Сам же индекс мало отличается от некластерного составного ключа.

Кластерные ключи в InnoDB

Здесь всё просто. Каждая таблица InnoDB имеет кластерный ключ. Каждая. Без исключения.
Гораздо интереснее, какие поля для этого выбираются.

  • Если в таблице задан PRIMARY KEY — это он
  • Иначе, если в таблице есть UNIQUE (уникальные) индексы — это первый из них
  • Иначе InnoDB самостоятельно создаёт скрытое поле с суррогатным ID размером в 6 байт

До третьего пункта лучше не доводить свой многострадальный сервер, и добавить таки ID самостоятельно.
И не забывайте, что InnoDB во вторичных ключах хранит полный набор значений полей кластерного ключа в качестве ссылки на конечную строку в таблице. Чем больше первичный ключ, тем больше вторичные ключи.

Для чего нужны индексы? У индексов таблиц в РСУБД два назначения – используются для эффективного поиска и для сортировки.

Сегодня хочу рассказать о том, каким образом устроены индексы в реляционных базах данных, в частности в Microsoft SQL Server. Сразу оговорюсь, что этот материал для начального уровня, здесь я не буду рассматривать структуру B-Tree и многие глубокие вещи. В этом обзоре предлагаю на начальном уровне разобраться с базовыми понятиями индексов. В обзоре будут примеры алгоритмов, поэтому у тебя, для понимания, ты должен знать, что такое сортировка, разница в поиске в сортированном и несортированном массивах. В этом обзоре я буду проводить ассоциации со структурами и массивами – как аналог таблиц в реляционных СУБД.

Итак – поехали.

Предлагаю рассмотрение начать с простой таблицы – сотрудники. Нам этой таблицы более чем достаточно для разбора материала.

В процедурном языке программирования в паскаль или си – аналог таблицы — это массив элементом которого является структура с теми же полями что и наша таблица.

Этот массив не отсортирован, поэтому любая операция извлечения данных (select … from employees) с условием или без такового будет сопровождаться перебором всех элементов нашего массива, даже если нам нужно будет элемент по ID у нас нет индекса и SQL Server пока ничего не знает сколько раз этот элемент будет встречаться, поэтому всегда будет полный перебор. Предлагаю выполнить запрос с условием по ID и без условия и сравнить планы запросов

select * from employees

select * from employees where ID = 4

Видна абсолютная идентичность планов как по стоимости (50% верхний от общего плана и половина так же 2й запрос нижний с условием). В плане запроса мы видим, что 100% от всего запроса занимает Table Scan – сканирование таблицы – это и есть полный перебор элементов массива.

А что бы было если бы наш массив был бы отсортированным по уникальному полю ID? Ты же прекрасно понимаешь, что можно было бы не полным перебором найти нужный элемент, например, половинным делением или другим алгоритмом?

Вообще, когда таблица не отсортирована, как в нашем случае – данные хранятся в «куче (heap)». Но можно упорядочить данные по выбранному критерию, по любому набору полей в нашей таблице, например по – LastName,FirstName,MiddleName или по ID и дать команду SQL Server что бы он поддерживал нужную нам последовательность – порядок данных в таблице. Эта команда – создать кластерный индекс. Кластерный индекс – это альтернатива куче. В куче данные лежат хаотично – в таком порядке в каком их положили в БД (со временем, после дефрагментации, сжатия файлов БД – порядок данных в куче изменится), а более точно – имея кучу – SQL Server не следит за упорядочиванием данных в таблице. Но если мы создадим кластерный индекс на таблице – сервер будет всегда поддерживать данные в том порядке в каком мы указали в кластерном индексе. Ну и стоит упомянуть очевидное – в таблице может быть только один кластерный индекс, или его совсем может не быть, в таблице вместо кластерного индекса – куча.

Предлагаю создать кластерный индекс по ФИО и первичный ключ (не кластерный индекс) по ID.

Проверим – какие индексы у нас есть на нашей таблице: exec sp_helpindex ’employees’

В описании индекса (index_description) видно, что индекс pk_employees – уникальный. Разница в уникальном и не уникальном индексе почти отсутствует, за исключением, когда мы ищем в уникальном индексе строки – при нахождении одной строки – можно остановиться и выдать результат, если мы создадим неуникальный индекс и будем по нему искать – то поиск будет изначально строки с требуемым условием, а после сканирование рядом находящихся строк. Например, в нашем кластерном неуникальном индексе если мы зададим условие ФИО – «Иванов Андрей Сидорович» — мы получим 2 строки – найдется сначала одна строка, и далее рядом лежащие строки, подпадающие по условие.

Заново выполним запросы, которые уже смотрели:

select * from employees

select * from employees where ID = 4

select ID from employees where ID = 4

Посмотрим, что за данные вывел наш запрос и сравним планы запросов:

Здесь, если ты заметил, простой селект из таблицы всех полей вывел сортированный результат по полям кластерного индекса – Фамилия, Имя, Отчество. После создания кластерного индекса данные в таблице стали именно по этим полям упорядочены, т.е. сначала по фамилии – Баранов, Иванов, после внутри одинаковых фамилий порядок по 2му полю по имени – Баранов Андрей, а после Баранов Петр, и уже если совпадают и Фамилия, и Имя, упорядочивание поддерживается по следующему, в нашем случае последнему 3му полю – Отчеству.

Ну и здесь стоит отметить, что наш кластерный индекс – составной. Составной индекс, это когда тело индекса (список полей) состоит из 2х и более полей.

Теперь разбираемся что нам выдал план запроса

Первый запрос – select * from employees

выдает нам сканирование кластерного индекса, ну и как мы видим результат выдал в отсортированном виде в том в каком задали тело индекса. Это частный случай. На самом деле наличие кластерного индекса не гарантирует нам результат отсортированным, если мы явно не зададим нужный order by. Это может случиться, например, когда данных в таблице много и они не умещаются в оперативную память сервера, а такой запрос выполняется несколькими клиентам в разный промежуток времени. И, например, на сервере 1Гб оперативной памяти, а таблица наша 10гб размером. Такой запрос за 10 раз считает в оперативную память по гигабайту и выдаст клиенту результат. И когда клиент в следующий раз без order by выполнит этот же запрос – мы понимаем, что сортировка не требуется и сервер вполне можем сначала отдать то что уже в кэше (в оперативной памяти – последний 1гб), а после заново просканировать и выдать недостающие данные.

Третий запрос – select ID from employees where ID = 4

Выдает нам поиск в индексе – это практически самый быстрый поиск с помощью индекса, в плане только 2 элемента – поиск и вывод.

А вот второй запрос намного сложнее третьего — select * from employees where ID = 4

И давай разберемся что это все означает и причины возникновения дополнительных элементов в плане запроса.

Изначально мы видим поиск по не кластерному индексу pk_employees – это операция нахождения нужных строк по заданному условию – where ID = 4. Ровно такая же команда в 3м плане запроса.

Далее Compute Scalar – мы выводим наше вычисляемое поле FullName – поле вычисляется «на лету» при запросе.

Ну и Key Lookup – операция достаточно тяжелая. Возникает из-за того, что в нашем не кластерном индексе указано только единственное поле ID, а в запросе мы хотим видеть все поля и те, которых нет в не кластерном индексе. И именно из-за этой причины сервер достает оставшиеся данные из кластерного индекса (ну или из кучи бы доставал, если бы не было кластерного индекса).

Вообще не кластерный индекс — это тот же отсортированный массив с телом индекса (что мы указали при объявлении) плюс дополнительная ссылка на страницу где аналогичная строка в куче если нет кластерного индекса или при наличии кластерного индекса – хранится в каждом строке не кластерного индекса не ссылка а тело кластерного индекса.

struct ix_Employee_FIO
{
int ID;
char TabNo;
char EmploymentDate;

};

Т.е. в нашем случае мы создали индекс pk_employee с полем (ID) уникальный и автоматически в индексе присутствует 3 поля нашего кластерного индекса. И так как наш кластерный индекс не уникальный, то однозначно идентифицировать по телу кластерного индекса мы не можем, поэтому SQL Server так же хранит не видимый для отображения поле счетчик 4х байтный, чтобы однозначно идентифицировать нужную нам строку, когда это требуется – для операции Lookup.

Операция Lookup это по сути запрос к кластерному индексу что бы в результате получить те поля которых нет в теле не кластерного индекса. А операция Nested Loop – это операция связи таблиц ну при Lookup связь строк не кластерного индекса с кластерным (или кучи если бы такая была у нас).

Вообще наш кластерный индекс весьма показателен с позиции какие кластерные индексы делать не нужно. Мы захотим сделать несколько не кластерных индексов в дальнейшем: по дате, по табельному номеру, по каким-то коротким полям и при этом во всех индексах будет дополнительно дублироваться Фамилия Имя Отчество – тело кластерного индекса плюс счетчик, в среднем это дополнительные до 300 байт к каждой строке (150 символов максимум и юникод один символ 2 байта) не кластерного индекса. Именно по этой причине рекомендуется тело кластерного индекса делать коротким и уникальным – идеальным претендентом на кластерный индекс это первичный ключ – поле ID – 4 байта всего против 48 байтов в нашей структуре с приведенными данными в среднем.

Теперь предлагаю рассмотреть несколько запросов для поиска по индексу.

Создадим новые индексы.

include (ID,TabNo,Gender);

Здесь, помимо тела индекса я добавил предложение include – в котором перечислил все остальные поля таблицы, которых нет в теле индекса этого и кластерного индексов, что бы избегать операции lookup – эту операцию мы рассмотрели выше.

Выполним запросы и посмотрим планы:

select * from employees with(index=ix_Employees_BirthDay)

where BirthDay >= ‘1980-01-01’ and EmploymentDate >= ‘2015-02-01’

select * from employees with(index=ix_Employees_EmploymentDate)

where BirthDay >= ‘1980-01-01’ and EmploymentDate >= ‘2015-02-01’

Видно, что разные сортировки при использовании разных индексов. По планам – по стоимости и структуре – планы идентичны.

За исключением, что в 1м индексе мы вычисляемое поле FullName включили в индекс, тем самым план стал чуть проще нежели во 2м запросе.

Вообще, как мы помним логическое «И» коммутативно – от перестановки слагаемых сумма (результат логического «И») не меняется, и для данного запроса можно использовать любой из этих двух индексов.

А вот для запросов:

select * from employees
where BirthDay >= ‘1980-01-01’
select * from employees
where EmploymentDate <= ‘2015-02-01’

Требуются разные индексы. Т.е. в обоих индексах есть поле BirthDay и EmploymentDate, но здесь важен порядок. В ix_Emplyees_BirthDay сортировка сначала по BirthDay и внутри повторений по EmploymentDate, в другом индексе поля поменяны местами, и соответственно именно поэтому индекс выбирается другой.

Если в условии есть поле, которое первое в теле индекса, то имеет смысл выбирать этот индекс для выборки, если первое, второе, третье – индекс сработает еще эффективнее.

Ну и напоследок предлагаю рассмотреть еще один индекс:

create nonclustered index ix_Employees_FullName on employees (FullName)

include (ID,TabNo,Gender,EmploymentDate,BirthDay) where Gender = ‘F’;

Здесь я просто хочу показать то, что в теле индекса могут быть вычисляемые поля, что полезно, когда эти поля используются в условиях и сортировках. И мы видим, что можно индекс строить не по всем строкам, а фильтровать по условиям. Иногда это удобно, например, меньше дискового пространства и в нашем случае поиск по мужчинам не имеет большого смысла их большинство – проще просканировать кластерный индекс, а женщина всего одна.

Надеюсь данная статья помогла устранить пробелы в знании об индексах.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *