Покрывающий индекс: 14 вопросов об индексах в SQL Server, которые вы стеснялись задать / Хабр

Содержание

Оптимизация сложных запросов MySQL / Хабр

Введение

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

Прежде всего хотелось бы ограничить круг рассматриваемых проблем оптимизации «широкими» и большими таблицами. Скажем до 10m записей и размером до 20Gb, с большим количеством изменяемых запросов к ним. Если в вашей в таблице много миллионов записей, каждая размером по 100 байт, и пять несложных возможных запросов к ней — это статья не для Вас. NB: Рассматривается движок MySQL innodb/percona — в дальнейшем просто MySQL.

Большинство запросов не являются очень сложными. Поэтому очень важно знать как построить индекс для использования нужным запросом и/или модифицировать запрос таким образом, чтобы он использовал уже имеющиеся индексы. Мы рассмотрим работу оптимизатора для выбора индекса обычных запросов (select_type=simple), без джойнов, подзапросов и объединений.

Отбросим простейшие случаи для очень небольших таблиц, для которых оптимизатор зачастую использует type=all (полный просмотр) вне зависимости от наличия индексов — к примеру, классификатор с 40-ка записями. MySQL имеет алгоритм использования нескольких индексов (index merge), но работает этот алгоритм не очень часто, и только без order by. Единственный разумный способ пытаться использовать index merge — случаи выборки по разным столбцам с OR.

Еще одно отступление: подразумевается что читатель уже знаком с explain. Часто сам запрос немного модифицируется оптимизатором, поэтому для того, чтобы понять, почему использовался или нет тот или иной индекс, следует вызвать

explain extended select xxx;

а затем

show warnings;

который и покажет измененный оптимизатором запрос.

Покрывающий индекс — от толстых таблиц к индексам

Итак задача: пусть у нас есть довольно простой запрос, который выполняется довольно часто, но для такого частого вызова относительно медленно. Рассмотрим стратегию приведения нашего запроса к using index, как к наиболее быстрому выбору.

Почему using index? Да, MySQL используют только B-tree индексы, но тем не менее MySQL старается по возможности держать индексы целиком в памяти (и при этом может даже добавить поверх них адаптивные хеш-индексы) — собственно все это и дает сказочный прирост производительности MySQL по отношению к другим базам данных. К тому же оптимизатор зачастую предпочтет использовать хоть и не лучший, но уже загруженный в память индекс, нежели более лучший, но на диске (для type=index/range). Отсюда несколько выводов:

слишком тяжелые индексы — зло. Либо они не будут использоваться потому что они еще не в памяти, либо их не будут грузить в память потому что при этом вытеснятся другие индексы.

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

Нюанс — индексировать/сортировать по TEXT — обрекать себя на постоянный using filesort.

Один тонкий момент, про который иногда забываешь — MySQL создает только кластерные индексы. Кластерный — по сути указывающий не на абсолютное положение записи в таблице, а (условно) на запись первичного ключа, который в свою очередь позволяет извлечь саму искомую запись. Но MySQL, не мудрствуя лукаво, для того чтобы обойтись без второго лукапа, поступает просто — расширяя любой ключ на ширину первичного ключа. Таким образом если у вас в таблице primary key (ID), key (A,B,C), то в реальности у вас второй ключ не (A,B,C), а (A,B,C,ID). Отсюда мораль — толстый первичный ключ суть зло.

Следует указать на разницу в кешировании запросов в разных базах. Если PostgreSQL/Oracle кешируют планы запросов (как бы prepare for some timeout), то MySQL просто кеширует СТРОКУ запроса (включая значение параметров) и сохраняет результат запроса. То есть если последовательно селектировать

select AAA from BBB where CCC=DDD

несколько раз — то, если DDD не содержит изменяющихся функций, и таблица AAA не изменилась (в смысле используемой изоляции), результат будет взят прямо из кеша. Довольно спорное улучшение.

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

Во-первых, смотрим на клоз order by. Используемый индекс должен начинаться с тех же столбцов что упомянуты в order by, в той же или в полностью обратной сортировке. Если сортировка не прямая и не обратная — индекс не может быть использован. Здесь есть одно но… MySQL до сих пор не поддерживает индексов со смешанными сортировками. Индекс всегда asc. Так что если у вас есть order by A asc, B desc — распрощайтесь с using index.

Столбцы, которые извлекаются, должны присутствовать в покрывающем индексе. Очень часто это невыполнимое условие в связи с бесконечным ростом индекса, что, как известно, зло. Поэтому существует способ обойти этот момент — использование self join‘а. То есть разделение запроса на выбор строк и извлечение данных. Во-первых, выбираем по заданному условию только столбцы первичного ключа (который всегда присутствует в кластером индексе), и во-вторых, полученный результат джойним к селекту всех требуемых столбцов, используя этот самый первичный ключ. Таким образом у нас будет чистый using index в первом селекте, и eq_ref (суть множественный const) для второго селекта. Итак, мы получаем что-то похожее на:
```
select AAA,BBB,CCC,DDD from tableName as a join tableName as b using (PK) «where over table b»
```

Далее клоз where. Здесь в худшем случае мы можем перебрать весь индекс (type=index), но по возможности стоит стремиться использовать функции, не выводящие за рамки type=range (>, >=, <, <=, like «xxx%» и так далее). Используемый индекс должен включать все поля из where, для того чтобы сохранить using index. Как уже было отмечено выше — можно пытаться использовать index_merge — но зачастую это просто не возможно со сложными условиями.

Собственно, это все, что можно сделать для случая, когда мы имеем только один вид запроса. К сожалению, оптимизатор MySQL не всегда при наличии покрывающего индекса может выбрать именно его для выполнения запроса. Что ж, в таком случае приходится помогать оптимизатору с помощью стандартных хинтов use/force index.

Вычленение толстых полей из покрывающего индекса — от толстых индексов к тонким

Но что делать, если у нас запросы бывают нескольких видов, или требуются разные сортировки и при этом используются толстые поля (varchar)? Просто посчитайте размер индекса поля varchar(100) в миллионе записей. А если это поле используется в разных видах запросов — для которых у нас разные покрывающие индексы? Возможно ли иметь в памяти только ОДИН индекс по этому толстому полю, сохранив при этом ту же (или почти ту же) производительность в разных запросах? Итак — последний пункт.

Толстые и тонкие поля. Очевидно, что иметь несколько РАЗНЫХ вариантов ключей с использованием толстых полей — непозволительная роскошь. Поэтому по возможности мы должны пытаться иметь только один ключ начинающийся на толстое поле. И здесь уместно использовать некоторый искусственный алгоритм замены условий. То есть заменить условие по толстому полю на джойн по результатам этого условия. К примеру:
```
select A from tableName where A=1 or fatB='test'
```
вместо создания ключа key(fatB, A) мы создадим тонкий ключ key(A) и толстый key(fatB). И перепишем условие след образом.
```
create temporary table tmp as select PK from tableName where fatB='test';
select A from tableName left join tmp using (PK) where A=1 or tmp.PK is not null;
```

Следовательно, мы можем иметь много тонких ключей, для разных запросов и только один толстый по полю fatB. Реальная экономия памяти, при почти полном сохранении производительности.

Задание для самостоятельного разбора

Требуется создать минимальное количество ключей (с точки зрения памяти) и оптимизировать запросы вида:

select A,B,C,D from tableName where A=1 and B=2 or C=3 and D like 'test%';  
select A,C,D from tableName where B=3 or C=3 and D ='test' order by B;

Допустим запросы не сводимы к type=range.

Список используемой литературы

High Performance MySQL, 2nd Edition

Optimization, Backups, Replication, and More

By Baron Schwartz, Peter Zaitsev, Vadim Tkachenko, Jeremy D. Zawodny, Arjen Lentz, Derek J. Balling

Publisher: O’Reilly Media

Released: June 2008

Pages: 712

www.mysqlperformanceblog.com

Повесть о кластеризованном индексе / Хабр

После перехода на SQL Server с Oracle удивляет многое. Трудно привыкнуть к автоматическим транзакциям – после update не нужно набирать commit (что приятно), зато в случае ошибки не сможешь набрать rollback (что просто кошмарно). Трудно привыкнуть к архитектуре, в которой журнал используется и для отката, и для наката транзакций. Трудно привыкнуть к ситуации «писатель блокирует читателей, читатель блокирует писателей», а когда привыкнешь – ещё труднее отвыкнуть. И совсем не последнее место в рейтинге трудностей играет засилье кластеризованных индексов. По умолчанию первичный ключ таблицы – именно кластеризованный индекс, и поэтому почти у всех таблиц он есть.

На самом деле зверь этот совсем нестрашный и даже очень полезный. Давайте попробуем разобраться, зачем он нужен и как его использовать.

Файлы, страницы, RID

Данные любой таблицы физически сохранены в файле базы данных. Файл БД делится на страницы (page) – логические единицы хранения для сервера. Страница в MS SQL Server обязательно имеет размер 8 килобайт (8192 байта), из них под данные отдано 8060 байт. Для каждой строки можно указать её физический адрес, так называемый Row ID (RID): в каком файле она находится, в какой по порядку странице этого файла, в каком месте страницы. Страницу таблица присваивает целиком – на одной странице могут быть данные только одной таблицы. Более того, при необходимости считать/записать строку сервер считывает/записывает всю страницу, поскольку так получается гораздо быстрее.

Как устроен B-tree индекс?

B-tree означает balanced tree, «сбалансированное дерево». Индекс содержит ровно одну корневую страницу, которая является точкой входа для поиска. Корневая страница содержит значения ключей и ссылки на страницы следующего уровня для данных значений индекса. При поиске по индексу находится последнее значение, которое не превосходит искомое, и происходит переход на соответствующую страницу. На последнем, листьевом уровне дерева перечислены все ключи, и для каждого из них указана ссылка (bookmark) на данные таблицы. Естественным кандидатом на роль ссылки является RID, и он в самом деле используется в этом качестве для случая кучи. На следующем рисунке буквы B обозначают ссылки на строки таблицы.

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

Индексу выделяется новая страница – тоже на листьевом уровне.

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

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

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

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

Куча мала

Рассмотрим некоторую модельную таблицу, организованную в виде кучи: какого-то определённого порядка в записях нет.
RID, который запись получает в самом начале, остаётся с ней почти всегда. В редких случаях записи в куче могут перемещаться на другую страницу – это происходит, когда после обновления строка перестаёт помещаться на то место, которое она занимала. Но в таком случае на прежнем месте остаётся ссылка на новое размещение – то есть, зная RID, полученный строкой при добавлении, строку можно найти всегда. Поэтому для индексов на куче наилучший выбор для ссылки на данные – именно RID.

Предположим, в таблице 200 тысяч записей, и в каждую страницу помещается от 48 до 52 записей. Будем считать, что таблица занимает 4000 страниц. Допустим, нам нужно найти все записи, в которых поле [City] имеет значение ‘Perm’. Также допустим, что их всего 3, но мы об этом пока не знаем.

Серверу придётся просканировать все 4000 страниц. Даже если сервер найдёт все 3 записи, ему всё равно придётся идти до конца – ведь нет гарантии, что больше нужных записей нет. Итак, для выполнения запроса понадобится 4000 логических чтений страницы.

А если у нас есть индекс, в котором можно искать двоичным поиском – скажем, дерево высоты 3? Тогда серверу потребуется 3 чтения индексных страниц для того, чтобы найти адрес первой записи. Адреса второй и третьей записей будут лежать рядом – либо в той же странице, либо в следующей: страницы индекса по горизонтали соединены ссылками. То есть после максимум 4 чтений сервер наверняка знает RID всех трёх записей. Если сильно не повезёт, все 3 записи лежат в разных страницах. Таким образом, при наличии индекса после 7 логических чтений страницы все 3 записи наверняка будут найдены. 7 против 4000 – впечатляет.

Но так хорошо будет, когда записей мало. А если это не ‘Perm’, а ‘Moscow’, и нужных записей не 3, а 20 тысяч? Это не очень много, всего 10 процентов от общего количества записей. Но картина быстро становится не столь радужной.

За 3 чтения сервер найдёт первую запись. А затем ему потребуется считать 20 тысяч RID и 20 тысяч раз прочитать страницу, чтобы получить строку: мы помним, что сервер читает данные только целыми страницами. Вполне может получиться так, что нужные записи рассеяны по всей таблице, и для обеспечения 20 тысяч логических чтений потребуется считать большую часть страниц с диска. Ещё хорошо, если не все. Вместо 4 тысяч логических чтений мы получаем 20 тысяч.

Индекс очень хорошо работает на поиске небольшого количества значений, но плохо работает на прохождении больших диапазонов.

Оптимизатор запросов прекрасно осведомлён об этом. Поэтому если он ожидает, что поиск по индексу даст достаточно большой диапазон, вместо поиска по индексу он выберет полное сканирование таблицы. Это, кстати, одно из редких мест, где Оптимизатор может ошибиться, даже имея правильные статистики. Если на самом деле требуемые данные расположены очень компактно (например, 20 тысяч логических чтений – это 60 раз прочесть блок с диска и 19940 раз прочесть блок в кэше), то принудительное использование индекса даст выигрыш в памяти и в скорости.

А как же быть с диапазонами?

Проблема именно в том, что в конце поиска по индексу сервер получает не данные, а только адрес, по которому они лежат. Серверу ещё нужно идти по этому адресу и брать данные оттуда. Вот было бы здорово, если бы в конце пути сразу лежали данные!
Некоторые, собственно, и лежат. Значения ключей, например, лежат именно в индексе – за ними идти не нужно. Только за неключевыми полями. А что будет, если неключевые поля тоже положить в индекс? Ну допустим, не все, а только те, которые нужны сканирующему запросу?

А будет в таком случае индекс с добавочными (included) столбцами. Он проигрывает обычному индексу по размеру: его листьевые страницы содержат не только ключи и адреса строк, но и часть данных. В поиске одиночного значения такой индекс работает не хуже, а в сканировании диапазонов – намного, намного лучше. Если индекс покрывает запрос (то есть содержит все столбцы, перечисленные в запросе), то для выполнения запроса таблица не нужна вообще. Возможность взять все требуемые данные из индекса, не обращаясь к закладкам, даёт громадный выигрыш.

Вернёмся к нашему модельному примеру. Предположим, что требуемые для запроса столбцы включены в индекс. Для простоты предположим, что в листьевую страницу индекса попадают ровно 50 записей (ключи, добавленные столбцы, ссылки на записи). Тогда сканирование 20 тысяч записей потребует чтения всего лишь 400 страниц индекса – вместо 20 тысяч логических чтений для непокрывающего индекса.

400 против 20 тысяч – разница в 50 раз. Оптимизатор запросов недаром любит предлагать включить в индекс те или иные столбцы.

А может, стоит добавить в индекс все столбцы? Тогда любой запрос будет покрыт индексом обязательно. Более того, тогда в листьях даже не нужны RID, потому что ни за какими данными такой индекс не будет обращаться в таблицу, у него всё под рукой. Да в таком случае становится не нужна и сама таблица!

И мы пришли к концепции кластеризованного индекса. Он устроен как обычное B-дерево, но в его листьевых страницах вместо ссылок на записи таблицы расположены сами данные, а отдельной от него таблицы больше нет. Таблица не может иметь кластеризованный индекс, она может быть кластеризованным индексом.

Любое сканирование по ключу в кластеризованном индексе будет лучше, чем полный просмотр таблицы. Даже если просканировать нужно 97% всех записей.

Где подвох?

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

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

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

Представим себе сканирование диапазона в 20 тысяч записей по некластеризованному индексу, построенному на кластеризованном. Теперь понадобится выполнить не 20 тысяч логических чтений страницы по известному RID, а 20 тысяч поисков в кластеризованном индексе – и каждый поиск потребует 3, а то и более, логических чтений.

А если ключ кластеризованного индекса не уникален? А так не бывает. Для сервера он обязательно уникален. Если пользователь попросил создать неуникальный кластеризованный индекс, сервер к каждому ключу припишет 4-байтовое целое число, которое обеспечит уникальность ключа. Делается это прозрачно для пользователей: сервер не только не сообщает им точного значения числа, но и не выдаёт сам факт его наличия. Уникальность ключа нужна именно для возможности однозначной идентификации записей – чтобы ключ кластеризованного индекса мог служить адресом строки.

Так делать или не делать?

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

Предлагается следующий алгоритм выбора:

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

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

Однозначно лучшего выбора кандидата на кластеризацию среди всех покрывающих индексов нет. Следует кластеризовать какой-то из этих индексов, принимая во внимание следующее:
- Длина ключа. Ключ кластеризованного индекса является ссылкой на строку и хранится на листьевом уровне некластеризованного индекса. Меньшая длина ключа означает меньше места на хранение и более высокую производительность.
- Степень покрытия. Кластеризованный индекс содержит все поля «бесплатно», и покрывающий индекс с самым большим набором полей – хороший кандидат на кластеризацию.
- Частота использования. Поиск одиночного значения в покрывающем индексе – самый быстрый возможный поиск, а кластеризованный индекс – покрывающий для любого запроса.

Постскриптум. Почему он единственный?

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

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

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

Ключи кластеризованного индекса представляют собой ссылки на данные, которые хранятся в листьях некластеризованных индексов. Если бы кластеризованных индексов могло бы быть несколько, среди них всё равно пришлось бы выделять «основной», тот, ключи которого являются идентификаторами данных.

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

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

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

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

Удачи всем в кластеризации ваших индексов!

Выбор и использование индексов MySQL

Первичный индекс

При построении первичного индекса необходимо учитывать несколько факторов:

INT + AUTO_INCREMENT — лучший выбор
использовать строки — плохо, много места и долгая обработка
MyISAM пакует индексы — еще медленнее для строк (до 6 раз)
InnoDB включает первичный индекс во вторичные — дополнительное место
в InnoDB первичный ключ — кластерный индекс по умолчанию
Случайные строки (MD5, SHA1) — медленные выборки и вставка (соседние записи не являются соседними в индексе)
Хранение UUID — удалить тире, еще лучше преобразовать в BINARY(16) с помощью UNHEX()

Виды индексов

Поиск элемента в хорошей хэш-таблице занимает О(1).
В хорошо сбалансированном дереве — O(log(n)).
В массиве — O(n).
Наилучшие алгоритмы сортировки имеют сложность O(n*log(n)).
Плохие алгоритмы сортировки — O(n²).

https://habrahabr.ru/company/mailru/blog/266811/

B-TREE

Возможности

B-TREE — основной используемый типа индекса. Поиск может выполняться:

по полному значению
по левостороннему префиксу, по первой колонке индекса
по интервалу значений (range), только для первой колонки
по фиксированному значению первой колонки (или нескольких) и интервалу на последующую

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

Ограничения

Для B-TREE индексов существуют и ограничения:

нельзя искать по суффиксу (имена, оканчивающиеся на определенную букву)
нельзя пропустить колонку в индексе
не учитываются колонки справа от сравнения с интервалом (date_of_birth):

WHERE last_name="Smith" AND
      first_name LIKE 'J%' AND
      date_of_birth = '1976-12-23'

IN (v1,v2,v3) тоже считается интервалом (range), но после него учитываются.

HASH

Особенности

Основное преимущество — очень быстрый поиск по полному значению индекса, но масса ограничений:

нельзя использовать для покрывающих индексов
нельзя использовать для поиска по префиксу
нельзя использовать для сортировки
не может использовать в выражениях <, >, только в =, IN, <>
не эффективен при частых коллизиях

Эмуляция через B-TREE

Предположим, у нас есть большой и медленный индекс по url:

SELECT id FROM url WHERE url="http://www.mysql.com";

Можно построить быстрый индекс по url_crc, индекса по url нет:

SELECT id FROM url WHERE url='http://www.mysql.com'
AND url_crc=CRC32('http://www.mysql.com');

Выборка ведется по url для разрешения коллизий.

Заполнение url_crc — триггер или слой модели. Внимательно выбираем хэш-функцию, SHA1, MD5 — слишком сложные и длинные.

crc32-trigger.sql

DELIMITER $$
CREATE TRIGGER `url_crc_fill` BEFORE INSERT ON `url`
  FOR EACH ROW BEGIN
    SET NEW.url_crc = CRC32(NEW.url);
  END $$
DELIMITER ;

Еще один пример для точного поиска по адресу:

DROP TRIGGET IF EXISTS `address_crc_fill_insert`;
DROP TRIGGET IF EXISTS `address_crc_fill_update`;
 
DELIMITER $$
CREATE TRIGGER `address_crc_fill_insert` BEFORE INSERT ON `MarketNavigator`
  FOR EACH ROW BEGIN
    SET NEW.FullAddressCRC = CRC32(NEW.FullAddress);
  END $$
 
CREATE TRIGGER `address_crc_fill_update` BEFORE UPDATE ON `MarketNavigator`
  FOR EACH ROW BEGIN
    IF NEW.FullAddress <> OLD.FullAddress THEN
      SET NEW.FullAddressCRC = CRC32(NEW.FullAddress);
    END IF;
  END $$
 
DELIMITER ;

Использование индексов

Принцип изолирования колонок

Индекс не используется, если колонка внутри выражения или вызова функции:

SELECT actor_id FROM actor WHERE actor_id + 1 = 5;
SELECT ... WHERE TO_DAYS(CURRENT_DATE) * TO_DAYS(date_col) <= 10;

Часто можно переписать запрос с учетом принципа изолирования колонок, тогда индексы используются:

SELECT actor_id FROM actor WHERE actor_id = 4;
SELECT ... WHERE date_col >= DATE_SUB(CURRENT_DATE, INTERVAL 10 DAY);

Префиксные индексы и селективность

Для длинных строк часто имеет смысл строить индекс по префиксу строки (а не по полному значению), уменьшая место и ускоряя обработку.

При этом важно не забывать о селективности:

selectivity = cardinality / общее количество значений
cardinality - количество различных значений

Длина префикса — компромисс между хорошей селективностью и занимаемым местом.

По реальным данным считаем селективность для различных длин префиксов, выбираем оптимальную.

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

Определяет физический порядок записей. В случае InnoDB это единая структура для хранения и индекса, и данных. В качестве кластеризованного индекса выбираются:

1. первичный ключ
2. первый уникальный ключ, если нет первичного
3. суррогатный первичный ключ в порядке добавления записей, если нет уникальных ключей

Все прочие созданные индексы ссылаются не на записи, а на значения кластеризованного индекса, это важная особенность InnoDB.

Преимущества

очень быстрая выборка по первичному ключу
эффективный поиск по интервалу первичного ключа
быстрая сортировка по первичному ключу
покрывающие индексы автоматически используют первичный ключ
быстрая вставка в порядке сортировки первичного ключа

Недостатки

вторичные индексы занимают больше места
при поиске по вторичному ключу выполняется дополнительный просмотр по первичному
при обновлении первичного ключа — перемещение строки
медленная вставка, если порядок не совпадает с сортировкой первичного ключа

Как правило, достоинства перевешивают недостатки.

Покрывающие (covering) индексы

MySQL может брать данные из индекса, не обращаясь к записи, в результате получаем значительное увеличение производительности:

меньше обрабатываемых данных
быстрее навигация по записям
лучшее кеширование
для InnoDB — нет дополнительного поиска по первичному ключу

CREATE INDEX store_film ON inventory(store_id, film_id, name);
 
SELECT store_id, film_id FROM inventory WHERE store_id = 1;
 
SELECT store_id, film_id
  FROM inventory
  WHERE store_id = 1 AND name LIKE 'Secret%';

Существуют ограничения:

работает только для B-TREE индексов
все запрашиваемые колонки должны быть в индексе
условие LIKE — только по префиксу (pattern%)

Например, в приведенном ниже запросе покрывающий индекс не используется: поле price не в индексе, LIKE не по префиксу:

SELECT store_id, film_id, price
  FROM store_film
  WHERE store_id = 1 AND
        name LIKE '%mission%';

Дублирующиеся и избыточные индексы

Дублирующиеся (dublicate) индексы — индексы по одним и тем же колонкам в том же порядке, всегда нужно оставлять только один.

Избыточные (redundant) индексы — если один индекс содержит другой: (A,B) и (A,B,C).

Прежде чем добавить новый индекс — смотрим, нельзя ли расширить старый, но возможны варианты:

(A INT, B INT) и (A INT, B INT, C VARCHAR)

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

Многокритериальные индексы

Если необходим поиск по форме, содержащей много полей:

CREATE INDEX search ON people(gender,eye_color,hair_color,city,age);

Работает с запросами gender, gender+country, gender+country+region. Но что делать с поиском по region+age?

Можно построить еще один индекс, однако большое количество индексов (по одному на каждую комбинацию) - плохо.

Иногда можно извернуться, указав отсутствующее в запросе поле со всеми возможными значениями

... WHERE eye_color IN('brown','blue','hazel')
    AND hair_color IN('black','red','blonde','brown')
    AND gender IN('M','F');

Сортировка по индексам

Для того, чтобы индексы использовались при сортировке, необходимо выполнение следующих требований:

порядок колонок в индексе должен точно совпадать с ORDER BY
не работает для разнонаправленной сортировки (ASC/DESC) при нескольких колонках в ORDER BY
для JOIN — если ORDER BY содержит только колонки первой таблицы
левосторонняя префиксность, кроме случаев ограничения в WHERE по константе

Пример:

CREATE INDEX rental_date (rental_date,inventory_id,customer_id);
 
SELECT rental_id, staff_id FROM rental
  WHERE rental_date = '2005-05-25'
  ORDER BY inventory_id, customer_id;

Сортировка по индексу не работает в следующих случаях:

... WHERE rental_date = '2005-05-25' ORDER BY inventory_id, staff_id;

... WHERE rental_date = '2005-05-25' ORDER BY inventory_id DESC, customer_id ASC;

... WHERE rental_date = '2005-05-25' ORDER BY customer_id;

... WHERE rental_date > '2005-05-25' ORDER BY inventory_id, customer_id;
          AND hair_color IN('black','red','blonde','brown')
          AND gender IN('M','F');

Порядок следования полей в индексе

При построении индекса в большинстве случаев можно придерживаться следующего принципа:

сначала колонки, по которым делается выборка по значению, в порядке убывания селективности
потом колонка, по которой делается выборка по интервалу

CREATE INDEX ON employees(department_id, education_type, gender, age);
                          ^              ^               ^       ^
SELECTIVITY:              10             3               2       20

В тексте WHERE порядок следования условий как правило не играет роли, оптимизатор запросов достаточно умный.

В SORT — еще как влияет, поэтому нужно еще и учитывать наиболее частые сортировки.

Что покрывающие индексы и покрытый запросы на сервер SQL? — sql

Можете ли вы объяснить понятия и отношения между охватывающими индексами и охватываемыми запросами в Microsoft SQL Server?

sql

sql-server

indexing

Поделиться

Источник

TheVillageIdiot

04 марта 2009 в 05:37

8 Ответов

Поделиться

Mitch Wheat

04 марта 2009 в 05:39

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

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

Следующие ссылки могут быть полезны, если вы новичок в индексации понятий:

Поделиться

Suresh

19 сентября 2012 в 14:02

Индекс покрытия — это индекс Non-Clustered . Как кластеризованные, так и некластеризованные индексы используют структуру данных B-дерева для улучшения поиска данных, разница заключается в том, что в листьях кластеризованного индекса физически хранится целая запись (т. е. строка)!, но это не относится к Некластеризованным индексам. Следующие примеры иллюстрируют это:

Пример: у меня есть таблица с тремя столбцами: ID, Fname и Lname.

Однако для некластеризованного индекса существует две возможности: либо таблица уже имеет кластеризованный индекс, либо его нет:

Как показывают две диаграммы, такие некластеризованные индексы не обеспечивают хорошей производительности, поскольку они не могут найти любимое значение (т. е. Lname) только из B-дерева. Вместо этого они должны сделать дополнительный шаг поиска (Либо Key, либо RID look up), чтобы найти значение Lname. И вот тут-то на экране появляется покрытый индекс. Здесь некластеризованный индекс на ID покрывает значение Lname прямо рядом с ним в листьях B-дерева, и больше нет необходимости в каком-либо типе поиска.

Поделиться

TheEsnSiavashi

10 декабря 2016 в 00:42

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

Запрос превращается в закрытый запрос с помощью разумного расположения индексов.

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

Покрывающий индекс -это индекс, который используется в покрытом запросе. Не существует такой вещи, как индекс, который сам по себе является охватывающим индексом. Индекс может быть покрывающим индексом по отношению к запросу А, но в то же время не являться покрывающим индексом по отношению к запросу В.

Поделиться

yfeldblum

04 марта 2009 в 05:52

Вот статья в devx.com , в которой говорится::

Создание некластеризованного индекса, содержащего все столбцы, используемые в запросе SQL, называется методом индексного покрытия

Я могу только предположить, что покрытый запрос -это запрос, который имеет индекс, который покрывает все столбцы в его возвращаемом наборе записей. Одно предостережение — индекс и запрос должны быть построены так, чтобы позволить серверу SQL фактически сделать вывод из запроса, что индекс полезен.

Например, объединение таблицы само по себе может не получить выгоды от такого индекса (в зависимости от интеллекта планировщика выполнения запроса SQL):

PersonID ParentID Name
1        NULL     Abe
2        NULL     Bob
3        1        Carl
4        2        Dave

Предположим, что есть индекс на PersonID,ParentID,Name — это будет покрывающий индекс для такого запроса, как:

SELECT PersonID, ParentID, Name FROM MyTable

Но такой вопрос как этот:

SELECT PersonID, Name FROM MyTable LEFT JOIN MyTable T ON T.PersonID=MyTable.ParentID

Вероятно, это не принесло бы так много пользы, хотя все столбцы находятся в индексе. Почему? Потому что вы на самом деле не говорите ему, что хотите использовать тройной индекс PersonID,ParentID,Name .

Вместо этого вы создаете условие, основанное на двух столбцах — PersonID и ParentID (что исключает Name), а затем запрашиваете все записи со столбцами PersonID, Name . На самом деле, в зависимости от реализации, индекс может помочь последней части. Но для первой части вам лучше иметь другие индексы.

Поделиться

Shalom Craimer

04 марта 2009 в 05:57

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

Это первый шаг на пути к повышению эффективности работы рассматриваемой системы sql.

Поделиться

Learning

04 марта 2009 в 05:43

покрывающий индекс-это тот, который дает каждый требуемый столбец и в котором SQL сервер не должен прыгать назад к кластеризованному индексу, чтобы найти какой-либо столбец. Это достигается с помощью некластеризованного индекса и параметра INCLUDE для покрытия столбцов.
Неключевые столбцы могут быть включены только в некластеризованные индексы. Столбцы не могут быть определены как в ключевом столбце, так и в списке INCLUDE. Имена столбцов не могут быть повторены в списке INCLUDE. Неключевые столбцы могут быть удалены из таблицы только после первого удаления неключевого индекса. Подробности смотрите здесь

Поделиться

Sadia Aziz

06 марта 2013 в 06:43

Когда я просто вспомнил, что кластеризованный индекс состоит из упорядоченного по ключам списка без кучи из ALL столбцов в определенной таблице, для меня загорелся свет. Слово «cluster», таким образом, относится к тому факту, что существует «cluster» всех столбцов, подобно скоплению рыб в этом «hot spot». Если нет индекса, покрывающего столбец, содержащий искомое значение (правая часть уравнения), то план выполнения использует кластеризованный индекс, который ищет в представлении кластеризованного индекса запрошенный столбец, поскольку он не находит запрошенный столбец ни в одном другом индексе «covering». Пропущенный вызовет оператор поиска кластеризованного индекса в предлагаемом плане выполнения, где искомое значение находится в столбце внутри упорядоченного списка, представленного кластеризованным индексом.

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

Поделиться

Bob Letts

10 декабря 2013 в 00:37

Postgres Professional, Москва — Разработчик СУБД Postgres Pro / Статьи / Хабр

Приятно видеть знакомые фамилии в списке Acknowledgments официального релиза PostgreSQL 12. Мы решили свести вместе попавшие в релиз новшества и некоторые багфиксы, над которыми трудились наши разработчики.

1. Поддержка JSONPath

(В Release Notes это звучит как Add support for the SQL/JSON path language (Nikita Glukhov, Teodor Sigaev, Alexander Korotkov, Oleg Bartunov, Liudmila Mantrova)

Сам этот патч, возможности JSONPath и история вопроса обсуждались в деталях в отдельной статье здесь на хабре. JSONPath — серьезное достижение Postgres Professional и одно из главных новшеств PostgreSQL 12 вообще.

В 2014 году А.Коротковым, О.Бартуновым и Ф.Сигаевым было разработано расширение jsquery, вошедшее в результате в версию Postgres Pro Standard 9.5 (и в более поздние версии Standard и Enterprise). Оно дает дополнительные, очень широкие возможности для работы с json(b).

Когда появился стандарт SQL:2016, оказалось, что его семантика не так уж сильно отличается от нашей в расширении jsquery. Не исключено, что авторы стандарта даже поглядывали на jsquery, изобретая JSONPath. Нашей команде пришлось реализовывать немного по-другому то, что у нас уже было и, конечно, много нового тоже.

Хотя специальный патч с функциями до сих пор не закоммичен, в патче JSONPath уже есть ключевые функции для работы с JSON(B), например:

jsonb_path_query('{"a": [1,2,3,4,5]}', '$.a[*] ? (@ > 2)') возвращает 3, 4, 5
jsonb_path_query('{"a": [1,2,3,4,5]}', '$.a[*] ? (@ > 5)') возвращает 0 записей

Кроме того, были оптимизированы и некоторые функции, которые уже работали с JSON раньше. Этим успешно занимался Никита Глухов.

Например, оператор #>>, соответствующий функциям jsonb_each_text() и jsonb_array_elements_text(), раньше достаточно быстро преобразовывал JsonbValue в text, но работал неторопливо с другими типами. Сейчас всё работает быстро.

«Под капотом» индексов Postgres / Блог компании Mail.ru Group / Хабр

^{Капитан Немо у штурвала «Наутилуса»}

Индексы — один из самых мощных инструментов в реляционных базах данных. Мы используем их, когда нужно быстро найти какие-то значения, когда объединяем базы данных, когда нужно ускорить работу SQL-операторов и т.д. Но что представляют собой индексы? И как они помогают ускорять поиск по БД? Для ответа на эти вопросы я изучил исходный код PostgreSQL, отследив, как происходит поиск индекса для простого строкового значения. Я ожидал найти сложные алгоритмы и эффективные структуры данных. И нашёл.

Здесь я расскажу о том, как устроены индексы и как они работают. Однако я не ожидал, что в их основе лежит информатика. В понимании подноготной индексов также помогли комментарии в коде, объясняющие не только как работает Postgres, но и почему он так работает.

Алгоритм поиска последовательностей в Postgres демонстрирует странности: он зачем-то просматривает все значения в таблице. В моём прошлом посте использовался вот такой простой SQL-оператор для поиска значения “Captain Nemo”:

Postgres спарсил, проанализировал и спланировал запрос. Затем ExecSeqScan (встроенная функция на языке С, реализующая поиск последовательностей SEQSCAN) быстро нашла нужное значение:

Но затем по необъяснимой причине Postgres продолжил сканировать всю базу, сравнивая каждое значение с искомым, хотя оно уже было найдено!

Если бы таблица содержала миллионы значений, то поиск занял бы очень много времени. Конечно, этого можно избежать, если убрать сортировку и переписать запрос так, чтобы он останавливался на первом найденном совпадении. Но проблема более глубока, и заключается она в неэффективности самого механизма поиска в Postgres. Использование поиска последовательностей для сравнения каждого значения в таблице — процесс медленный, неэффективный и зависящий от порядка размещения записей. Должен быть другой способ!

Решение простое: нужно создать индекс.

Сделать это просто, достаточно выполнить команду:

Разработчики на Ruby предпочли бы использовать миграцию add_index с помощью ActiveRecord, при которой была бы выполнена та же команда CREATE INDEX. Обычно, когда мы перезапускаем select, Postgres создаёт дерево планирования. Но в данном случае оно будет несколько отличаться:

Обратите внимание, что в нижней части используется INDEXSCAN вместо SEQSCAN. INDEXSCAN не будет сканировать всю базу в отличие от SEQSCAN. Вместо этого он использует только что созданный индекс, чтобы быстро и эффективно найти нужную запись.

Создание индекса позволяет решить проблему производительности, но не даёт ответов на ряд вопросов:

Что именно представляет собой индекс в Postgres?

Как именно он выглядит, какова его структура?

Каким образом индекс ускоряет поиск?

Давайте ответим на эти вопросы, изучив исходники на языке С.
Начнём с документации для команды CREATE INDEX:

Здесь отображены все параметры, которые можно использовать при создании индекса. Обратите внимание на параметр USING method: он описывает, индекс какого вида нам нужен. На той же странице приведена информация о method, аргументе ключевого слова USING:

Оказывается, в Postgres реализовано четыре разных вида индексов. Их можно использовать для различных типов данных или в зависимости от ситуации. Поскольку мы не определяли параметр USING, то index_users_on_name по умолчанию представляет собой индекс вида “btree” (B-Tree).

Что такое B-Tree и где найти о нём информацию? Для этого изучим соответствующий файл с исходным кодом Postgres:

Вот что говорится о нём в README:

Кстати, сам README является 12-страничным документом. То есть нам доступны не только полезные комментарии в коде на С, но и вся необходимая информация о теории и конкретной реализации сервера БД. Чтение и разбор кода в opensource-проектах часто является непростой задачей, но только не в Postgres. Разработчики постарались облегчить нам процесс понимания устройства их детища.

Обратите внимание, что в первом же предложении есть ссылка на научную публикацию, в которой объяснено, что такое B-Tree (а значит, и как работают индексы в Postgres): Efficient Locking for Concurrent Operations on B-Trees за авторством Лемана (Lehman) и Яо (Yao).

В статье описывается улучшение, внесённое авторами в алгоритм B-Tree в 1981 году. Об этом мы поговорим чуть позже. Сам алгоритм был разработан в 1972 году, так выглядит пример простого B-Tree:

Название является сокращением от англ. “balanced tree”. Алгоритм позволяет ускорить операцию поиска. Например, нам нужно найти значение 53. Начнём с корневого узла, содержащего значение 40:

Оно сравнивается с искомым значением. Поскольку 53 > 40, то далее мы следуем по правой ветви дерева. А если бы мы искали, например, значение 29, то пошли бы по левой ветви, потому что 29 < 40. Следуя по правой ветви, мы попадаем в дочерний узел, содержащий два значения:

На этот раз мы сравниваем 53 со значениями 47 и 62: 47 < 53 < 62. Обратите внимание, что значения внутри узлов отсортированы. Поскольку искомое значение меньше одного и больше другого, то далее мы следуем по центральной ветви и попадаем в дочерний узел, содержащий три значения:

Сравниваем со списком отсортированных значений (51 < 53 < 56), идём по второй из четырёх ветвей и наконец попадаем в дочерний узел с искомым значением:

За счёт чего этот алгоритм ускоряет поиск:

Значения (ключи) внутри каждого узла отсортированы.

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

Леман и Яо нарисовали свою диаграмму больше 30 лет назад, какое она имеет отношение к современному Postgres? Оказывается, созданный нами index_users_on_name очень похож на эту самую диаграмму. При выполнении команды CREATE INDEX Postgres сохраняет все значения из пользовательской таблицы в виде ключей дерева B-Tree. Так выглядит узел индекса:

Каждая запись в индексе состоит из структуры на языке С, называющейся IndexTupleData, а также содержит значение и битовый массив (bitmap). Последний используется для экономии места, в него записывается информация о том, принимают ли атрибуты индекса в ключе значение NULL. Сами значения следуют в индексе за битовым массивом.

Вот как выглядит структура IndexTupleData:

t_tid: это указатель на какой-либо другой индекс или запись в БД. Обратите внимание, что это не указатель на физическую память из языка С. Здесь содержатся данные, по которым Postgres ищет сопоставленные страницы памяти.

t_info: здесь содержится информация об элементах индекса. Например, сколько значений в нём хранится, равны ли они NULL и т.д.

Для лучшего понимания, рассмотрим несколько записей из index_users_on_name:

Здесь вместо value вставлены некоторые имена из БД. Узел из верхнего дерева содержит ключи “Dr. Edna Kunde” и “Julius Powlowski”, а узел нижнего — “Julius Powlowski” и “Juston Quitzon”. В отличие от диаграммы Лемана и Яо, Postgres повторяет родительские ключи в каждом дочернем узле. Например, “Julius Powlowski” является ключом в верхнем дереве и в дочернем узле. Указатель t_tid ссылается с Julius в верхнем узле на такое же имя в нижнем узле. Если вы хотите глубже изучить хранение значений ключей в узлах B-Tree, обратитесь к файлу itup.h:

Вернёмся к нашему исходному оператору SELECT:

Как именно в Postgres осуществляется поиск значения “Captain Nemo” в индексе index_users_on_name? Почему использование индекса позволяет искать быстрее по сравнению с поиском последовательности? Давайте взглянем на некоторые имена, хранящиеся в нашем индексе:

Это корневой узел в index_users_on_name. Я просто развернул дерево так, чтобы имена умещались целиком. Здесь четыре имени и одно значение NULL. Postgres автоматически создал этот корневой узел, как только был создан сам индекс. Обратите внимание, что за исключением NULL, обозначающего начало индекса, остальные четыре имени идут в алфавитном порядке.

Как вы помните, B-Tree является сбалансированным деревом. Поэтому в данном примере дерево имеет пять дочерних узлов:

Имена, идущие в алфавитном порядке до “Dr. Edna Kunde”

Имена между “Dr. Edna Kunde” и “Julius Powlowski”

Имена между “Julius Powlowski” и “Monte Nicolas”

…и т.д.

Поскольку мы ищем “Captain Nemo”, то Postgres идёт по первой ветви направо (при алфавитной сортировке искомое значение идёт до “Dr. Edna Kunde”):

Как видно из иллюстрации, далее Postgres находит узел с нужным значением. Для теста я добавил в таблицу 1000 имён. Этот правый узел содержал 240 из них. Так что дерево существенно ускорило процесс поиска, поскольку остальные 760 значений остались «за бортом».

Если вы хотите узнать больше об алгоритме поиска нужного узла в B-Tree, обратитесь к комментариям к функции _bt_search.

Итак, Postgres перешёл в узел, содержащий 240 имён, среди которых ему нужно найти значение “Captain Nemo”.

Для этого используется не поиск последовательности, а бинарный поисковый алгоритм. Для начала система сравнивает ключ, который находится в середине списка (позиция 50%):

Искомое значение идёт по алфавиту после “Breana Witting”, поэтому Postgres перескакивает к ключу, находящемуся на позиции 75% (три четверти списка):

На этот раз наше значение должно быть выше. Тогда Postgres прыгает на некоторое значение выше. В моём случае системе понадобилось восемь раз прыгать по списку ключей в узле, пока она не нашла наконец нужное значение:

Подробнее об алгоритме поиска значения внутри узла можно почитать в комментариях к функции _bt_binsrch:

Если у вас есть желание, то некоторое количество теории о деревьях B-Tree можно почерпнуть из научной работы Efficient Locking for Concurrent Operations on B-Trees.

Добавление ключей в B-Tree. Процедура внесения новых ключей в дерево выполняется по очень интересному алгоритму. Обычно ключ записывается в узел в соответствии с принятой сортировкой. Но что делать, если в узле уже нет свободного места? В этом случае Postgres разделяет узел на два более мелких и вставляет в один из них ключ. Также добавляет в родительский узел ключ из «точки разделения» и указатель на новый дочерний узел. Конечно, родительский узел тоже приходится разделять, чтобы вставить этот ключ, в результате процедура добавления в дерево одного единственного ключа превращается в сложную рекурсивную операцию.

Удаление ключей из B-Tree. Тоже довольно любопытная процедура. При удалении ключа из какого-то узла Postgres, если это возможно, объединяет его дочерние узлы. Это тоже может быть рекурсивная операция.

Деревья B-Link-Tree. На самом деле, в работе Лемана и Яо описывается придуманное ими нововведение, связанное с параллелизмом и блокированием, когда одно дерево используется несколькими потоками. Код Postgres и его алгоритмы должны поддерживать многопоточность, потому что к одному индексу могут обращаться (или модифицировать его) одновременно несколько клиентов. Если добавить по указателю от каждого узла на следующий дочерний узел («стрелка вправо»), то один поток может искать по дереву, в то время как другой будет разделять узел без блокирования всего индекса:

Возможно, вы знаете всё о том, как использовать Postgres, но знаете ли вы, как он устроен внутри, что у него «под капотом»? Изучение информатики, помимо работы над текущими проектами, не досужее развлечение, а часть процесса развития разработчика. Год от года наши программные инструменты становятся сложнее, многограннее, лучше, облегчая нам процесс создания сайтов и приложений. Но мы не должны забывать, что в основе всего этого лежит наука информатика. Мы, как и всё сообщество opensource-разработчиков Postgres, стоим на плечах наших предшественников, таких как Леман и Яо. Поэтому не доверяйтесь слепо инструментам, которые вы повседневно используете, изучайте их устройство. Это поможет вам достичь более высокого профессионального уровня, вы сможете найти для себя информацию и решения, о которых ранее и не подозревали.

Использование покрывающих индексов для повышения производительности запросов

Введение

Есть много способов измерить производительность базы данных. Мы можем посмотреть на его общую доступность; то есть: могут ли наши пользователи получать нужную информацию, когда она им нужна? Мы можем рассмотреть его параллелизм; сколько пользователей могут запрашивать базу данных одновременно? Мы даже можем наблюдать за количеством транзакций, которые происходят в секунду, чтобы оценить уровень активности.

Однако часто для наших пользователей все сводится к одному очень простому, но несколько нечеткому измерению — воспринимаемой отзывчивости.Или, другими словами, когда пользователь отправляет запрос, получает ли он свои результаты, не ожидая слишком долго?

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

Однако в этой статье я сосредоточусь на одном конкретном методе, который можно использовать для повышения производительности — создании покрывающих индексов.

Обновление индексации

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

Индексы

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

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

Кластеризованный индекс — это индекс, конечные узлы которого, то есть самый нижний уровень индекса, содержат фактические страницы данных базовой таблицы.Следовательно, индекс и сама таблица для всех практических целей одно и то же. Каждая таблица может иметь только один кластерный индекс. Дополнительные сведения о кластерных индексах см. В разделе электронной документации «Структуры кластеризованных индексов» (http://msdn.microsoft.com/en-us/library/ms177443.aspx).

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

Во многих проектах баз данных широко используются кластерные индексы. Фактически, обычно рекомендуется включать кластерный индекс в каждую таблицу; конечно, это рисование очень широкой кистью, и наверняка будут исключения. Дополнительные сведения о преимуществах кластерных индексов см. В статье передового опыта SQL Server, озаглавленной «Сравнение таблиц, организованных с помощью кластеризованных индексов, с кучей» на TechNet.

Рассмотрим пример. На рисунке 1 таблица Customers имеет кластерный индекс, определенный в столбце Customer_ID.Когда выполняется запрос, выполняющий поиск по столбцу Customer_ID, SQL Server перемещается по кластеризованному индексу, чтобы найти нужную строку и возвращает данные. Это можно увидеть в операции поиска кластерного индекса в плане выполнения запроса.

Рисунок 1. План выполнения кластерного индекса

Следующая инструкция Transact-SQL использовалась для создания кластеризованного индекса для столбца Customer_ID.

СОЗДАТЬ КЛАСТЕРНЫЙ ИНДЕКС [ix_Customer_ID] НА [dbo].[Клиенты]

(

[Customer_ID] ASC

) С (PAD_INDEX = ВЫКЛ., STATISTICS_NORECOMPUTE = ВЫКЛ., SORT_IN_TEMPDB = ВЫКЛ., IGNORE_DUP_KEY = ВЫКЛ., DROPKS_EXISTING = ВЫКЛ., ONLINE_ONLINE = ВКЛ.) [ПЕРВИЧНЫЙ]

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

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

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

В следующем примере некластеризованный составной индекс был создан для таблицы Customers, как описано в следующем коде Transact-SQL.

СОЗДАТЬ НЕЗАКЛЮЧЕННЫЙ ИНДЕКС [ix_Customer_Name] ON [dbo]. [Клиенты]

(

[Last_Name] ASC,

[First_Name] ASC

) WITH (PAD_INDEX = OFF, STATISTICS_INDEX = OFF, STATISTICS_INDEX_INDEX = OFF, STATISTICS_INDOM_INDEX = OFF, STATISTICS_IN = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]

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

Рисунок 2 . План выполнения некластеризованного индекса

Дополнительные сведения о кластерных индексах см. В разделе электронной документации «Структуры некластеризованных индексов».

Использование некластеризованных индексов

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

Поиск ключей

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

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

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

Результатом этого запроса было 1000 строк, и почти 100% затрат на запрос были напрямую связаны с операцией поиска ключа. Если углубиться в операцию поиска ключей, мы поймем, почему.

Рисунок 3. Свойства операции поиска ключа

Эта операция поиска ключа была выполнена 1000 раз, по одному разу для каждой строки набора результатов.

Использование сканирования таблиц

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

Чтобы проиллюстрировать это, давайте изменим запрос так, чтобы он извлекал больше строк. На рисунке 4. показан новый запрос вместе с фактическим планом выполнения, использованным для его разрешения.

Рис. 4. Сканирование таблицы

Новый запрос выполняет поиск клиентов, чьи фамилии находятся между «Роланд» и «Смит». В нашей базе их 69 000.Из фактического плана выполнения мы видим, что оптимизатор запросов определил, что накладные расходы на выполнение поиска по ключу для каждой из 69 000 строк были больше, чем просто обход всей таблицы с помощью сканирования таблицы. Следовательно, наш индекс ix_Customer_Name вообще не использовался во время запроса.

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

Рисунок 5. Свойства для операции сканирования таблицы

Может возникнуть соблазн заставить SQL Server разрешить запрос с использованием некластеризованного индекса, предоставив табличную подсказку, как показано на следующем рисунке.

Рисунок 6. Использование табличной подсказки для решения запроса

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

На рис. 7 показаны свойства поиска по ключу, когда мы заставили SQL Server использовать некластеризованный индекс ix_Customer_Name.Расчетная стоимость оператора для поиска ключа составляет 57,02 по сравнению с 12,17 для сканирования кластеризованного индекса, показанного на рисунке 5. Принуждение SQL Server к использованию индекса значительно повлияло на производительность, и не в лучшую сторону!

Рисунок 7 . Свойства поиска по ключу для подсказки таблицы

Индексы покрытия

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

Давайте начнем с изменения нашего запроса, чтобы он больше не выбирал столбец Email_Address . На рисунке 8 показан этот обновленный запрос вместе с фактическим планом его выполнения.

Рисунок 8 . Уменьшенный запрос для исключения поиска по ключу

Новый план выполнения был оптимизирован и использует только некластеризованный индекс ix_Customer_Name . Если посмотреть на свойства поставщиков операций, то это станет еще одним свидетельством улучшения.Свойства показаны на рисунке 9.

Рисунок 9. Уменьшенный запрос для исключения свойств Key Lookup

Расчетная стоимость оператора резко снизилась, с 12,17 на рисунке 5 до 0,22 на рисунке 9. Мы также можем посмотреть на характеристики логического и физического чтения, включив STATISTICS IO , однако для этой демонстрации достаточно просмотреть затраты оператора. для каждой операции.

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

Использование столбца кластеризованных ключей

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

Рисунок 10 . Покрывающий индекс с использованием ключей кластерного индекса

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

Добавление ключевых столбцов в индекс

Чтобы повысить вероятность того, что некластеризованный индекс является покрывающим, возникает соблазн начать добавлять дополнительные столбцы к ключу индекса. Например, если мы регулярно запрашиваем отчество и номер телефона клиента, мы можем добавить эти столбцы в индекс ix_Customer_Name. Или, чтобы продолжить наш предыдущий пример, мы могли бы добавить столбец Email_Address в индекс, как показано в следующем коде Transact-SQL.

СОЗДАТЬ НЕКЛАСТЕРНЫЙ ИНДЕКС [ix_Customer_Email] НА [dbo].[Клиенты]

(

[Фамилия] ASC,

[Имя] ASC,

[Email_Address] ASC

) С (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_OFF_TEMPDOPB = OFF, SORT_IN_OFF_TEMPDB = OFF_IN_OFF_TEMPDB = OFF_IN_OFF_TEMPDB_OFF_IN_D_IN_OFF_DEMPDB , ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]

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

Кроме того, для индексов есть некоторые встроенные ограничения. В частности, как в SQL Server 2005, так и в SQL Server 2008 индексы ограничены 16 ключевыми столбцами или 900 байтами, в зависимости от того, что наступит раньше. Некоторые типы данных не могут использоваться в качестве ключей индекса, например varchar (max) .

Включая неключевые столбцы

SQL Server 2005 предоставил новую функцию для некластеризованных индексов — возможность включать дополнительные неключевые столбцы на конечный уровень некластеризованных индексов. Эти столбцы технически не являются частью индекса, однако они включены в конечный узел индекса. SQL Server 2005 и SQL Server 2008 позволяют включать до 1023 столбцов в листовой узел.

Чтобы создать некластеризованный индекс с включенными столбцами, используйте следующий синтаксис Transact-SQL.

СОЗДАТЬ НЕЗАКЛЮЧЕННЫЙ ИНДЕКС [ix_Customer_Email] ON [dbo]. [Клиенты]

(

[Last_Name] ASC,

[First_Name] ASC

)

INCLUDE ([E-mail_Address] = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]

Повторное выполнение нашего запроса дает план выполнения, который использует наш новый индекс для быстрого возврата набора результатов.План выполнения представлен на Рисунке 11.

Рисунок 11. Покрывающий запрос с включенными столбцами

Обратите внимание, что даже несмотря на то, что наш запрос выбирает столбцы, которые не являются частью ключа некластеризованного индекса, SQL Server по-прежнему может разрешить запрос без использования поиска по ключу для каждой строки. Поскольку индекс ix_CustomerEmail включает столбец Email_Address как часть своего определения, индекс «покрывает» запрос. Свойства оператора поиска по некластеризованному индексу подтверждают наши выводы, как показано на рисунке 12.

Рисунок 12. Свойства выполнения для покрывающего запроса с включенными столбцами

Из этого плана выполнения мы видим, что стоимость оператора оценки снизилась с 12,17 на рисунке 5 до 0,41. Включение дополнительного неключевого столбца значительно повысило производительность запроса.

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

Сводка

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

индекс, содержащий все запрашиваемые столбцы

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

Чтобы охватить весь запрос, индекс должен содержать
все столбцов из оператора SQL, в частности также
столбцы из выбирают пункт как
показано в следующем примере:

  CREATE INDEX sales_sub_eur
    По продажам
     (secondary_id,  eur_value )

  ВЫБРАТЬ СУММУ ( eur_value )
  От продаж
 ГДЕ secondary_id =?

Конечно, индексирование , где
пункт имеет приоритет над другими пунктами.Колонка
SUBSIDIARY_ID , таким образом, находится на первой позиции, поэтому он
квалифицируется как предикат доступа.

План выполнения показывает сканирование индекса без последующей таблицы
доступ ( ДОСТУП К ТАБЛИЦЕ ПО ИНДЕКСУ ROWID ).

DB2

  Объясните план
-------------------------------------------------- -------------
ID | Операция | Ряды | Стоимость
 1 | ВОЗВРАТ | | 21 год
 2 | GRPBY (ПОЛНАЯ) | 1 из 34804 (.00%) | 21 год
 3 | IXSCAN SALES_SUB_EUR | 34804 из 1009326 (3,45%) | 19

Информация о предикатах
 3 - НАЧАЛО (Q1.SUBSIDIARY_ID =?)
      СТОП (Q1.SUBSIDIARY_ID =?)

Oracle

  --------------------------------- -------------------------
| Id | Операция | Имя | Ряды | Стоимость |
-------------------------------------------------- --------
| 0 | ВЫБРАТЬ ЗАЯВЛЕНИЕ | | 1 | 104 |
| 1 | СОРТИРОВАТЬ АГРЕГАТ | | 1 | |
| * 2 | СКАНИРОВАНИЕ ДИАПАЗОНА ИНДЕКСА | SALES_SUB_EUR | 40388 | 104 |
-------------------------------------------------- --------

Информация о предикате (определяется идентификатором операции):
-------------------------------------------------- -
   2 - доступ ("SUBSIDIARY_ID" = TO_NUMBER (: A))

Индекс охватывает весь запрос, поэтому его также называют
, индекс покрытия .

Примечание

Если индекс запрещает доступ к таблице, он также называется
, индекс покрытия .

Этот термин вводит в заблуждение, поскольку звучит как указатель
свойство. Сканирование только индекса фразы правильно предполагает, что это
план выполнения операции.

В индексе есть копия столбца EUR_VALUE , поэтому
база данных может использовать значение, хранящееся в индексе. Доступ к таблице не
требуется, потому что индекс содержит всю информацию, чтобы удовлетворить
запрос.

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

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

Важно

Преимущество в производительности только для индекса
сканирование зависит от количества доступных строк и кластеризации индекса
фактор.

Сканирование только индекса — это агрессивная стратегия индексирования. Не
разработать индекс для сканирования только индекса при подозрении только потому, что он
без необходимости использует память и увеличивает затраты на обслуживание, необходимые для
обновить выписок.См. Глава 8, « Изменение данных ».
На практике вам следует сначала проиндексировать без учета предложения select и расширить индекс только в том случае, если
необходимо.

Сканирование только для индексации также может вызвать неприятные сюрпризы, например, если
мы ограничиваем запрос последними продажами:

  SELECT SUM (eur_value)
  От продаж
 ГДЕ secondary_id =?
     И дата_продажи>?

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

DB2

  Объясните план
-------------------------------------------------- -----------------
ID | Операция | Ряды | Стоимость
 1 | ВОЗВРАТ | | 13547
 2 | GRPBY (ПОЛНАЯ) | 1 из 1223 (0,08%) | 13547
 3 |  ПОЛУЧИТЬ ПРОДАЖУ  | 1223 из 34804 (3.51%) | 13547
 4 | RIDSCN | 34804 из 34804 (100,00%) | 32
 5 | СОРТИРОВКА (УНИКАЛЬНАЯ) | 34804 из 34804 (100,00%) | 32
 6 | IXSCAN SALES_SUB_EUR | 34804 из 1009326 (3,45%) | 19

Информация о предикатах
 3 - SARG (?

Oracle

  --------------------------------- -----------------------------
| Id | Операция | Имя | Строки | Стоимость |
-------------------------------------------------- ------------
| 0 | ВЫБРАТЬ ЗАЯВЛЕНИЕ | | 1 | 371 |
| 1 | СОРТИРОВАТЬ АГРЕГАТ | | 1 | |
| * 2 |  ДОСТУП К ТАБЛИЦЕ ПО ИНДЕКСУ ROWID  | ПРОДАЖА | 2019 | 371 |
| * 3 | СКАНИРОВАНИЕ ДИАПАЗОНА ИНДЕКСА | SALES_DATE | 10541 | 30 |
-------------------------------------------------- ------------

Информация о предикате (определяется идентификатором операции):
-------------------------------------------------- -
   2 - фильтр ("SUBSIDIARY_ID" = TO_NUMBER (: A))
   3 - доступ ("SALE_DATE">: B)

Доступ к таблице увеличивает время ответа, хотя запрос выбирает меньше строк.Важным фактором является не количество строк в запросе. доставляет, но сколько строк база данных должна проверить, чтобы их найти.

`Предупреждение`

Расширение , где пункт может вызвать «нелогичное» поведение производительности. Проверить план выполнения перед расширением запросов.

Если индекс больше нельзя использовать для сканирования только индекса, оптимизатор выберет следующий лучший план выполнения. Это означает оптимизатор может выбрать совершенно другой план выполнения или, как указано выше, аналогичный план выполнения с другим индексом.В этом случае он использует индекс SALE_DATE , что является остатком от предыдущей главы.

С точки зрения оптимизатора, этот индекс имеет два преимущества перед SALES_SUB_EUR . Оптимизатор считает, что фильтр на SALE_DATE более избирательный, чем на ДОПОЛНИТЕЛЬНЫЙ_ИД . Вы можете увидеть это в соответствующих «Строках» столбец двух последних планов выполнения (около 10 000 против 40 000). Эти Однако оценки являются чисто произвольными, поскольку в запросе используются параметры связывания. SALE_DATE условие может, например, выбрать всю таблицу при предоставлении дата первой продажи.

Второе преимущество индекса SALES_DATE состоит в том, что имеет лучший коэффициент кластеризации. Это веская причина, потому что Таблица ПРОДАЖИ растет только в хронологическом порядке. Новые строки всегда добавляется в конец таблицы до тех пор, пока нет удаленных строк. В поэтому порядок таблиц соответствует порядку индекса, потому что оба примерно отсортирован в хронологическом порядке - индекс имеет хорошую кластеризацию фактор.

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

`Примечание`

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

В этом конкретном примере произошло счастливое совпадение. Новый фильтр SALE_DATE не только предотвратил сканирование только индекса, но и одновременно открыл новый путь доступа. Оптимизатор был Таким образом, можно ограничить влияние этого изменения на производительность. Это, однако также возможно предотвратить сканирование только индекса, добавив столбцы в другие статьи. Однако добавление столбца в предложение select никогда не может открыть новый путь доступа. что может ограничить влияние потери сканирования только индекса.

`Подсказка`

Поддерживайте сканирование только индекса.

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

Индексы на основе функций могут также вызывают неприятные сюрпризы в связи со сканированием только индекса. An index на UPPER (last_name) нельзя использовать только для индекса сканирование при выборе столбца LAST_NAME . В предыдущем разделе мы должны проиндексировали сам столбец LAST_NAME для поддержки LIKE filter и разрешить его использование для сканирования только индекса при выборе столбца LAST_NAME .

`Подсказка`

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

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

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

`Наконечник`

Избегайте выберите * и выберите только нужные столбцы.

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

DB2

Ограничения DB2 LUW индекс до 64 столбцов с максимальной длиной ключа 25% страницы размер.

DB2 также поддерживает INCLUDE предложение о добавлении неключевых столбцов в уникальных индексов. Это позволяет продлить уникальный индекс с дополнительными столбцами, чтобы можно было использовать индекс для сканирования только индекса без изменения семантики уникальность.

MySQL

MySQL с InnoDB ограничивает общую длину ключа (все столбцы) до 3072 байт. Кроме того, длина каждого столбца ограничена. до 767 байт, если innodb_large_prefix не включен или форматы строк, отличные от DYNAMIC или СЖАТЫЕ . Это было по умолчанию до и включая MySQL 5.6. Индексы MyISAM ограничены 16 столбцы и максимальная длина ключа 1000 байт.

MySQL имеет уникальную функцию, называемую «индексирование префикса». (иногда также называется «частичной индексацией»). Это означает индексацию только первые несколько символов столбца, поэтому он не имеет никакого отношения с частичными индексами, описанными в главе 2. Если вы индексируете столбец, который превышает допустимая длина столбца (767, 1000 или 3072 байта, как описано выше) MySQL может - в зависимости от SQL режим и ряд формат - соответственно обрезать столбец.В этом случае создать индекс оператор успешно с предупреждением «Указанный ключ слишком длинный; максимальная длина ключа… байтов ». Это означает, что в индексе нет полной копии этого столбец больше - выбор столбца предотвращает сканирование только индекса (аналогично индексам на основе функций).

Вы можете явно использовать префиксную индексацию MySQL для предотвратить превышение предела общей длины ключа, если вы получите ошибку сообщение «Указанный ключ слишком длинный; максимальная длина ключа… байтов.” В следующем примере индексируются только первые десять символов LAST_NAME столбец.

  СОЗДАТЬ ИНДЕКС .. НА сотрудников ( last_name (10) )

Oracle

Максимальная длина ключа индекса зависит от размера блока и параметры хранения индекса (75% размера блока базы данных за вычетом накладных расходов). B-дерево индекс ограничен 32 столбцами.

При использовании Oracle 11 g со всеми значениями по умолчанию на месте (8k блоков) максимальная длина ключа индекса составляет 6398 байт.Превышение этого предела вызывает сообщение об ошибке «ORA-01450: максимум. длина ключа (6398) превышена. "

PostgreSQL

База данных PostgreSQL поддерживает сканирование только индекса с момента выпуска 9.2.

Длина записей B-дерева ограничена 2713 байтами (жестко запрограммировано, примерно BLCKSZ / 3 ). Соответствующая ошибка сообщение « размер строки индекса ... превышает максимум btree, 2713 ”появляется только при выполнении вставки или обновления , превышающего лимит.B-дерево индексы могут содержать до 32 столбцы.

SQL Server

Начиная с версии 2016, SQL Server поддерживает до 32 ключевых столбцов с до 1700 байт (900 байт для кластеризованных индексов). Неключевые столбцы не учитывают это предел.

`Совет`

Запросы, которые не выбирают столбцы таблицы, часто выполняется при сканировании только индекса.

Можете придумать значимый пример?

.

`Не только для SELECT, но и для операторов UPDATE - SQLServerCentral`

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

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

Рассмотрим следующий оператор T-SQL:

  ИСПОЛЬЗУЙТЕ AdventureWorks2017
  ИДТИ
  УСТАНОВИТЬ СТАТИСТИКУ IO, TIME ON - профайлер бедного человека; Я все время использую для настройки производительности
  ИДТИ
  ВЫБЕРИТЕ SalesOrderID, AccountNumber, CustomerID
         ОТ Sales.SalesOrderHeader
         ГДЕ SalesPersonID = 277
         ЗАКАЗАТЬ ПО 1
  ИДТИ
  УСТАНОВИТЬ СТАТИСТИКУ IO, TIME OFF
  ИДТИ
  - (473 ряда затронуты)
  - стоимость запроса = 0,545; 689 логических чтений

И дает план запроса:

Обратите внимание на сканирование кластерного индекса с общей стоимостью запроса 0.545. Исходный индекс IX_SalesOrderHeader_SalesPersonID основан на одном столбце SalesPersonID. Если мы запустим тот же запрос с другим SalesPersonID:

  УСТАНОВИТЬ СТАТИСТИКУ IO, TIME ON
  ИДТИ
  ВЫБЕРИТЕ SalesOrderID, AccountNumber, CustomerID - поиск индекса заметки (IX_SalesOrderHeader_SalesPersonID),
         FROM Sales.SalesOrderHeader - но результирующий поиск ключа
         ГДЕ SalesPersonID = 285
         ЗАКАЗАТЬ ПО 1
  ИДТИ
  УСТАНОВИТЬ СТАТИСТИКУ IO, TIME OFF
  ИДТИ
  - (затронуто 16 рядов)
  - стоимость запроса = 0.052; 50 логических чтений

С планом запроса

Странный; тот же запрос, но разные планы запросов. Причина в основном в размере (количестве строк) в наборах результатов. Первый запрос вернул 473 строки, а второй запрос - 16 строк. В первом запросе компилятор решил (исходя из статистики), что лучше выполнить сканирование кластерного индекса из-за большего набора результатов.

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

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

  СОЗДАТЬ НЕКЛАССНЫЙ ИНДЕКС IX_SalesOrderHeader_SalesPersonID НА Sales.SalesOrderHeader
         ([SalesPersonID] ASC)
         ВКЛЮЧИТЬ (AccountNumber, CustomerID)
         С (DROP_EXISTING = ON, ONLINE = ON, DATA_COMPRESSION = ROW)
  ИДТИ

Столбец SalesOrderID (PK) не нужен, так как он автоматически добавляется в индекс. Итак, запустив первый SELECT, мы получим:

  УСТАНОВИТЬ СТАТИСТИКУ IO, TIME ON
  ИДТИ
  ВЫБЕРИТЕ SalesOrderID, AccountNumber, CustomerID - теперь поиск по индексу (поскольку индекс "покрывает")
         ОТ ПРОДАЖ.SalesOrderHeader
         ГДЕ SalesPersonID = 277
         ЗАКАЗАТЬ ПО 1
  ИДТИ
  УСТАНОВИТЬ СТАТИСТИКУ IO, TIME OFF
  ИДТИ
  - (затронуты 473 строки)
  - стоимость запроса = 0,005; 5 логических чтений

с планом запроса

Вау, значительное улучшение: логическая страница 689 читается до 5, а стоимость запроса с 0,545 до 0,005.

Выполняя повторный запрос 2, получаем

  УСТАНОВИТЬ СТАТИСТИКУ IO, TIME ON
  ИДТИ
  ВЫБЕРИТЕ SalesOrderID, AccountNumber, CustomerID
         ОТ ПРОДАЖ.SalesOrderHeader
         ГДЕ SalesPersonID = 285
         ЗАКАЗАТЬ ПО 1
  ИДТИ
  УСТАНОВИТЬ СТАТИСТИКУ IO, TIME OFF
  ИДТИ
  - (затронуто 16 рядов)
  - стоимость запроса = 0,005; 3 логических чтения

с тем же планом запроса, что и выше. Обратите внимание на то, что запрос упал с 50 логических страниц до 3. Это отличный пример того, как покрывающий индекс может принести большую пользу запросу SELECT. Обратите внимание, что оба запроса использовали один и тот же план запроса.

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

Итак, теперь у нас есть индекс покрытия, основанный на SalesPersonID. Давайте теперь посмотрим на похожий (по логике) оператор UPDATE T-SQL:

  ОБНОВЛЕНИЕ soh
         УСТАНОВИТЬ AccountNumber = AccountNumber + '*',
               RevisionNumber = RevisionNumber + 1,
               ModifiedDate = GETDATE ()
         ОТ Sales.SalesOrderHeader soh
         ПРИСОЕДИНЯЙТЕСЬ к Sales.SalesPerson sp
           ON sp.BusinessEntityID = soh.SalesPersonID
         ГДЕ sp.TerritoryID = 1;
  ИДТИ
  - Сканирование кластерного индекса на IX_SalesOrderHeader_SalesPersonID (60% плана запроса)
  - (Вывод = SalesOrderID, RevisionNumber, AccountNumber, SalesPersonID)
  - Общая стоимость запроса = 9,01

с приблизительным планом запроса

где числа зеленого цвета (вверху) взяты из предполагаемого плана запроса.Обратите внимание, что в обеих таблицах выполняется сканирование кластеризованного индекса и что сканирование SalesOrderHeader составляет 60% от стоимости плана запроса.

Этот оператор обновления имеет 2 дополнительных столбца, которых нет в покрывающем индексе: RevisionNumber и ModifiedDate. Если мы пересмотрим индекс покрытия как

  СОЗДАТЬ НЕКЛАССНЫЙ ИНДЕКС IX_SalesOrderHeader_SalesPersonID НА Sales.SalesOrderHeader
         ([SalesPersonID] ASC)
         ВКЛЮЧИТЬ (AccountNumber, CustomerID, RevisionNumber, ModifiedDate)
         С (DROP_EXISTING = ON, ONLINE = ON, DATA_COMPRESSION = ROW)
  ИДТИ

И повторно запустите тот же оператор UPDATE выше, мы получим поиск по индексу: IX_SalesOrderHeader_SalesPersonID, со стоимостью запроса = 6% и общей стоимостью плана запроса = 0.146. Предполагаемый план запроса:

Теперь есть поиск по индексу для Sales.SalesOrderHeader с поиском только 6% от общего плана запроса, а общая стоимость плана запроса снизилась с 9,01 до 0,146. Теперь давайте посмотрим на еще одно ОБНОВЛЕНИЕ, но сначала вернемся к исходному индексу покрытия:

  СОЗДАТЬ НЕКЛАССНЫЙ ИНДЕКС IX_SalesOrderHeader_SalesPersonID НА Sales.SalesOrderHeader
         ([SalesPersonID] ASC)
         ВКЛЮЧИТЬ (AccountNumber, CustomerID)
         С (DROP_EXISTING = ON, ONLINE = ON, DATA_COMPRESSION = ROW)
  ИДТИ

Этот второй оператор UPDATE все еще находится в продаже.SalesOrderHeader:

  ОБНОВЛЕНИЕ soh
         УСТАНОВИТЬ AccountNumber = AccountNumber + '*',
               RevisionNumber = RevisionNumber + 1,
               ModifiedDate = GETDATE ()
         ОТ Sales.SalesOrderHeader soh
         ГДЕ SalesPersonID в (275,280,285,290)
  ИДТИ
  - теперь мы получаем сканирование кластерного индекса на PK_SalesOrderHeader с планом запроса = 74%
  - Общая стоимость тарифного плана 0,731

и с исходным индексом покрытия есть предполагаемый план запроса

На этот раз он запрашивает пересмотренный индекс с INCLUDE (RevisionNumber, AccountNumber).Если мы применим тот же индекс покрытия, что и для первого обновления:

  СОЗДАТЬ НЕКЛАССНЫЙ ИНДЕКС IX_SalesOrderHeader_SalesPersonID НА Sales.SalesOrderHeader
         ([SalesPersonID] ASC)
         ВКЛЮЧИТЬ (AccountNumber, CustomerID, RevisionNumber, ModifiedDate)
         С (DROP_EXISTING = ON, ONLINE = ON, DATA_COMPRESSION = ROW)
  ИДТИ

И повторно запустите запрос 2 ^nd UPDATE, мы получим поиск некластеризованного индекса по IX_SalesOrderHeader_SalesPersonID (стоимость запроса 4%), а общая стоимость плана запроса равна 0.149

где мы видим, что общая стоимость плана запроса снизилась с 0,731 до 0,149, а сканирование кластерного индекса, занимающее 74% стоимости запроса, снижается до поиска по индексу, стоимость которого составляет всего 4% от общей стоимости запроса для таблицы Sales.SalesOrderHeader

`Выводы`

Итак, теперь у нас есть покрывающий индекс, улучшающий производительность операторов SELECT и Update.

Обычно покрывающие индексы не только помогают повысить производительность запроса SELECT, но и, как показано, могут повысить производительность ОБНОВЛЕНИЯ. Хотя здесь это не показано, я столкнулся с клиентским сценарием, использующим поиск KEY (как описано в примере SELECT выше) для оператора UPDATE, который имел проблемы с взаимоблокировкой из-за параллелизма, а также двойного поиска по соответствующей таблице. Добавление индекса покрытия также решило эту проблему. В любом случае, как всегда говорит Microsoft: «Тестируй, тестируй, тестируй!»

.Сервер

`sql - как работает индекс покрытия SQL?`

Переполнение стека

Около
Продукты
Для команд

Переполнение стека Общественные вопросы и ответы
Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
Вакансии Программирование и связанные с ним технические возможности карьерного роста
Талант Нанимайте технических специалистов и создавайте свой бренд работодателя
Реклама Обратитесь к разработчикам и технологам со всего мира
О компании

.

Ноябрь 2024
Пн	Вт	Ср	Чт	Пт	Сб	Вс
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

Покрывающий индекс: 14 вопросов об индексах в SQL Server, которые вы стеснялись задать / Хабр

Оптимизация сложных запросов MySQL / Хабр

Введение

Покрывающий индекс — от толстых таблиц к индексам

Вычленение толстых полей из покрывающего индекса — от толстых индексов к тонким

Задание для самостоятельного разбора

Список используемой литературы

Повесть о кластеризованном индексе / Хабр

Файлы, страницы, RID

Как устроен B-tree индекс?

Куча мала

А как же быть с диапазонами?

Где подвох?

Так делать или не делать?

Постскриптум. Почему он единственный?

Выбор и использование индексов MySQL

Первичный индекс

Виды индексов

B-TREE

Возможности

Ограничения

HASH

Особенности

Эмуляция через B-TREE

Использование индексов

Принцип изолирования колонок

Префиксные индексы и селективность

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

Преимущества

Недостатки

Покрывающие (covering) индексы

Дублирующиеся и избыточные индексы

Многокритериальные индексы

Сортировка по индексам

Порядок следования полей в индексе

Что покрывающие индексы и покрытый запросы на сервер SQL? — sql

8 Ответов

Похожие вопросы:

Postgres Professional, Москва — Разработчик СУБД Postgres Pro / Статьи / Хабр

1. Поддержка JSONPath

«Под капотом» индексов Postgres / Блог компании Mail.ru Group / Хабр

Использование покрывающих индексов для повышения производительности запросов

Введение

Обновление индексации

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

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

Использование некластеризованных индексов

Поиск ключей

Использование сканирования таблиц

Индексы покрытия

Использование столбца кластеризованных ключей

Добавление ключевых столбцов в индекс

Включая неключевые столбцы

Сводка

индекс, содержащий все запрашиваемые столбцы

Примечание

Важно

Предупреждение

Примечание

Подсказка

Подсказка

Наконечник

Совет

Не только для SELECT, но и для операторов UPDATE - SQLServerCentral

Выводы

sql - как работает индекс покрытия SQL?

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

`Предупреждение`

`Примечание`

`Подсказка`

`Подсказка`

`Наконечник`

`Совет`

`Не только для SELECT, но и для операторов UPDATE - SQLServerCentral`

`Выводы`

`sql - как работает индекс покрытия SQL?`

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