Оптимизация запросов

Индексный доступ

Авторские права

Авторы: Егор Рогов, Павел Лузанов, Павел Толмачев, Илья Баштанов

Использование материалов курса

Некоммерческое использование материалов курса (презентации,

демонстрации) разрешается без ограничений. Коммерческое

использование возможно только с письменного разрешения компании

Postgres Professional. Запрещается внесение изменений в материалы

курса.

Обратная связь

Отзывы, замечания и предложения направляйте по адресу:

edu@postgrespro.ru

Отказ от ответственности

Компания Postgres Professional не несет никакой ответственности за

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

прямым или непрямым, специальным или случайным использованием

материалов курса. Компания Postgres Professional не предоставляет

каких-либо гарантий на материалы курса. Материалы курса

предоставляются на основе принципа «как есть» и компания Postgres

Professional не обязана предоставлять сопровождение, поддержку,

обновления, расширения и изменения.

Темы

B-деревья

Сканирование индекса

Сканирование только индекса

Индексы с дополнительными столбцами

Дубликаты в индексе

B-дерево

Индекс

вспомогательная структура во внешней памяти

сопоставляет ключи и идентификаторы строк таблицы

Устройство: дерево поиска

сбалансированное

сильно ветвистое

только сортируемые типы данных (операции «больше», «меньше»)

результаты автоматически отсортированы

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

ускорение доступа

поддержка ограничений целостности

В этом модуле мы будем рассматривать только один из доступных

в PostgreSQL типов индексов: B-дерево (B-tree). Это самый часто

применяющийся на практике тип индекса. Некоторые другие типы

индексов рассмотрены в курсе DEV2.

Как и все индексы в PostgreSQL, B-дерево является вторичной

структурой — индекс не содержит в себе никакой информации, которую

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

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

небольшую часть таблицы: выборки малого количества строк, а также

поддержки ограничений целостности (первичных и уникальных ключей).

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

(ключи поиска) и идентификаторы строк таблицы. Для этого в индексе

B-tree строится упорядоченное дерево ключей, в котором можно быстро

найти нужный ключ, а вместе с ним — и ссылку на табличную строку.

Но проиндексировать можно только данные, допускающие сортировку

(должны быть определены операции «больше», «меньше»). Например,

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

плоскости — нет (для них существуют другие типы индексов).

Особенностями B-дерева является его сбалансированность

(постоянная глубина) и сильная ветвистость. Хотя размер дерева

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

имеют глубину не больше 4–5.

B-дерево

14 3 5 2 1 10 12 8 7 13 11 4 9 6

1 9

1 3 6 9 12

1 2 3 4 5 6 7 8 9 10 11 12 13 14

корень

листья

внутренние

страницы

табличные

страницы

На слайде представлен пример B-дерева (верхняя часть рисунка).

У дерева есть корневая, внутренние и листовые страницы.

Страницы состоят из индексных записей, каждая из которых содержит:

- значения столбцов, по которым построен индекс (такие столбцы

называются ключевыми);

- ссылку на другую страницу индекса или версию строки.

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

Листовые страницы ссылаются непосредственно на табличные версии

строк, содержащие ключи индексирования.

Внутренние страницы ссылаются на нижележащие страницы индекса,

а значения ключей определяют диапазон значений, которые можно

обнаружить, спустившись по ссылке.

Самая верхняя страница дерева, на которую нет ссылок, называется

корнем.

Индексная страница может быть заполнена не полностью. Свободное

место используется для вставки в индекс новых значений. Если же на

странице не хватает места — она разделяется на две новых страницы.

Разделившиеся страницы никогда не объединяются, и это в некоторых

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

Index scan: одно значение

14 3 5 2 1 10 12 8 7 13 11 4 9 6

1 9

1 3 6 9 12

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Рассмотрим поиск одного значения с помощью индекса. Например,

нам нужно найти в таблице строку, где значение проиндексированного

столбца равно четырем.

Начинаем с корня дерева. Индексные записи в корневой странице

определяют диапазоны значений ключей в нижележащих страницах:

«от 1 до 9» и «9 и больше». Нам подходит диапазон «от 1 до 9», что

соответствует строке с ключом 1. Заметим, что ключи хранятся

упорядоченно, следовательно, поиск внутри страницы выполняется

очень эффективно.

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

В ней мы находим диапазон «от 3 до 6» (ключ 3) и переходим

к странице третьего уровня.

Эта страница является листовой. В ней мы находим ключ, равный 4,

и переходим на страницу таблицы.

В действительности процесс более сложен: мы не говорили про

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

далее. Но не будем углубляться в детали реализации.

Обратите внимание: на этой и следующих иллюстрациях цветом

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

Index scan: диапазон

14 3 5 2 1 10 12 8 7 13 11 4 9 6

1 9

1 3 6 9 12

1 2 3 4 5 6 7 8 9 10 11 12 13 14

страницы

читаются

хаотично

B-дерево позволяет эффективно искать не только отдельные значения,

но и диапазоны значений (по условиям «меньше», «больше», «меньше

или равно», «больше или равно», а также «between»).

Вот как это происходит. Сначала мы ищем крайний ключ условия.

Например, для условия «от 4 до 9» мы можем выбрать значение 4 или

9, а для условия «меньше 9» надо взять 9. Затем спускаемся до

листовой страницы индекса так, как мы рассматривали в предыдущем

примере, и получаем первое значение из таблицы.

Дальше остается двигаться по листовым страницам индекса вправо

(или влево, в зависимости от условия), перебирая строки этих страниц

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

На слайде показан пример поиска значений по условию «x BETWEEN 4

AND 9» или, что тоже самое, «x >= 4 AND x <= 9». Спустившись к

значению 4, мы затем перебираем ключи 5, 6, и так далее до 9.

Встретив ключ 10, прекращаем поиск.

Нам помогают два свойства: упорядоченность ключей на всех

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

Обратите внимание, что к одной и той же табличной странице нам

пришлось обращаться несколько раз. Мы прочитали последнюю

страницу таблицы (значение 4), затем первую (5), затем опять

последнюю (6) и так далее.

Parallel Index Scan

14 3 5 2 1 10 12 8 7 13 11 4 9 6

1 9

1 3 6 9 12

1 2 3 4 5 6 7 8 9 10 11 12 13 14

1. спуск

к листу

2. параллель-

ное сканирование

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

происходит в два этапа. Сначала ведущий процесс спускается от корня

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

параллельное чтение листовых страниц индекса, двигаясь по

указателям.

Процесс, прочитавший индексную страницу, выполняет и чтение

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

одну и ту же табличную страницу прочитают несколько процессов (этот

пример показан на иллюстрации: последняя табличная страница

содержит строки, ссылки на которые ведут от нескольких индексных

страниц, прочитанных разными процессами). Конечно, сама страница

будет находиться в буферном кеше в одном экземпляре.

Число рабочих процессов

Равно нулю (параллельный план не строится)

если размер выборки < min_parallel_index_scan_size = 512kB

Фиксировано

если для таблицы указан параметр хранения parallel_workers

Вычисляется по формуле

1 + ⌊ log

(размер выборки / min_parallel_index_scan_size) ⌋

Но не больше, чем max_parallel_workers_per_gather

Число рабочих процессов выбирается примерно так же, как и в случае

последовательного сканирования. Сравнивается объем данных,

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

индексных страниц) со значением параметра

min_parallel_index_scan_size (по умолчанию 512kB).

Если в случае последовательного сканирования таблицы объем данных

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

планировщик должен спрогнозировать, сколько индексных страниц

будет прочитано. Как именно это происходит, рассматривается позже

в теме «Статистика».

Если размер выборки меньше, параллельный план не рассматривается

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

доступ к одному значению — в этом случае просто нечего

распараллеливать.

Если размер выборки достаточно велик, число рабочих процессов

определяется по формуле, если только оно не указано явно

в параметре хранения parallel_workers таблицы (не индекса!).

Число процессов в любом случае не будет превышать значения

параметра max_parallel_workers_per_gather.

Index Only Scan

14 3 5 2 1 10 12 8 7 13 11 4 9 6

1 9

1 3 6 9 12

1 2 3 4 5 6 7 8 9 10 11 12 13 14

страницы нет

в карте видимости,

проверка по таблице

страница есть

в карте видимости,

проверка не нужна

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

уже есть в самом индексе — к таблице в этом случае обращаться не

надо. Такой индекс называется покрывающим для запроса.

Это хорошая оптимизация, исключающая обращения к табличным

страницам. Но, к сожалению, индексные страницы не содержат

информацию о видимости строк — чтобы проверить, надо ли

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

в табличную страницу, что сводит оптимизацию на нет.

Поэтому критическую роль в эффективности сканирования только

индекса играет карта видимости. Если табличная страница содержит

гарантированно видимые данные, и это отражено в карте видимости,

к такой табличной странице обращаться не надо. Но страницы, не

отмеченные в карте видимости, посетить все-таки придется.

Это одна из причин, по которой стоит выполнять очистку (vacuum)

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

Планировщик не знает точно, сколько табличных страниц потребуют

проверки, но учитывает оценку этого числа. При плохом прогнозе

планировщик может отказаться от использования сканирования только

индекса.

При обработке каждой индексной записи сначала проверяется наличие

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

сама табличная страница.

Include-индексы

Индекс с дополнительными неключевыми столбцами

CREATE INDEX ... INCLUDE (...)

Неключевые столбцы

не используются при поиске по индексу

не учитываются ограничением уникальности

значения хранятся в индексной записи

и возвращаются без обращения к таблице

Покрывающий индекс как правило увеличивает эффективность

выборки. Чтобы сделать индекс покрывающим, в него может

понадобиться добавить столбцы, но это не всегда возможно:

- добавление столбца в уникальный индекс нарушит гарантию

уникальности исходных столбцов;

- тип данных добавляемого столбца может не поддерживаться

индексом.

В таких случаях начиная с версии PostgreSQL 11 можно добавить

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

https://postgrespro.ru/docs/postgresql/13/sql-createindex

Значения таких столбцов не формируют дерево индекса, а просто

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

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

могут возвращаться без обращения к таблице.

В настоящее время include-индексы поддерживаются только для

индексов на основе B-деревьев и для GiST-индексов.

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

стоит путать эти два термина. Индекс вполне может быть покрывающим

для некоторого запроса, но не использовать предложение INCLUDE.

А Include-индекс может не быть покрывающим для каких-то запросов.

Parallel Index Only Scan

14 3 5 2 1 10 12 8 7 13 11 4 9 6

1 9

1 3 6 9 12

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Сканирование только индекса может выполняться параллельно. Это

происходит точно так же, как и при обычном индексном сканировании:

ведущий процесс спускается от корня к листовой странице, а затем

рабочие процессы параллельно сканируют листовые страницы

индекса, обращаясь при необходимости к соответствующим страницам

таблицы для проверки видимости.

Дубликаты в индексе

14 3 5 2 1 10 12 8 7 13 11 3 4 9 6

1 4 9

1 9 12

1 2 3 3

4 6

9 10 11 12 13 144 5

6 7 8

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

указывающие на разные версии строк таблицы.

Дубликаты возникают по двум причинам. Во-первых, разные строки

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

в этом случае мы имеем дело с неуникальным индексом. Во-вторых,

из-за работы механизма многоверсионности могут возникать разные

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

(и затем удаляются очисткой) и в уникальных индексах тоже.

Предположим, что в таблицу была добавлена еще одна строка со

значением 3.

Новую индексную запись невозможно добавить в уже заполненную

листовую страницу (с ключами 3, 4, 5) и происходит расщепление:

в индексе появляется еще одна листовая страница и записи

распределяются между ними.

В вышестоящей внутренней странице (с ключами 1, 3, 6) должна

появиться индексная запись, ссылающаяся на новую листовую

страницу. Но для этой записи нет места; поэтому внутренняя страница

также расщепляется. (Для корректной работы индекса во время

расщепления внутренние страницы одного уровня на самом деле тоже

связаны двунаправленным списком.)

В корневой странице дерева нашлось место для новой записи, поэтому

расщепления корня и увеличения глубины дерева в данном случае не

произошло.

На рисунке новые страницы показаны розовым цветом.

Исключение дубликатов

14 3 5 2 1 10 12 8 7 13 11 3 4 9 6

1 9

1 3 6 9 12

1 2 3 4 5 6 7 8 9 10 11 12 13 14

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

никогда не объединяются. Начиная с 13-й версии для избежания

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

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

запись со списком ссылок на версии строк.

Для экономии ресурсов группировка записей происходит только в том

случае, если иначе страницу пришлось бы расщепить. Поскольку

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

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

разрастание даже уникальных индексов. Но если известно, что

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

хранения deduplicate_items.

В нашем примере дублирующиеся тройки сгруппированы в одну

индексную запись. За счет этого удалось избежать расщеплений;

размер индекса не изменился.

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

значения которых можно сравнивать побитно (не подходят типы

numeric, float4, float8, jsonb; для некоторых правил сортировки не

подходят текстовые типы). Механизм не работает с Include-индексами,

не реализована поддержка типов-контейнеров.

https://postgrespro.ru/docs/postgresql/13/btree-implementation#BTREE-DE

DUPLICATION

При обновлении версии сервера с помощью pg_upgrade необходимо

выполнить REINDEX для существующих индексов, чтобы

задействовать для них возможность устранения дубликатов.

Итоги

Индексы

ускоряют доступ при высокой селективности

поддерживают ограничения целостности

позволяют получить отсортированные данные

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

позволяют экономить на обращении к таблице

Возможен параллельный индексный доступ

Практика

1. Напишите запрос, выбирающий максимальную сумму

бронирования.

Проверьте план выполнения. Какой метод доступа выбрал

планировщик? Эффективен ли такой доступ?

2. Создайте индекс по столбцу bookings.total_amount.

Снова проверьте план выполнения запроса. Какой метод

доступа выбрал планировщик теперь?

3. При создании индекса можно указать порядок сортировки

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

направлении?

4. В демонстрации был создан include-индекс для таблицы

билетов. Замените им индекс, поддерживающий первичный

ключ таблицы.

1. Этот запрос можно написать как минимум двумя разными способами.

Во-первых, можно воспользоваться предложениями ORDER BY и LIMIT

1. Во-вторых, можно вывести максимальное число с помощью

агрегатной функции max.

Попробуйте оба варианта.

3. Подсказка: это важно для индексов, построенных по нескольким

столбцам.

4. Используйте команду ALTER TABLE … DROP CONSTRAINT для

удаления старого ограничения целостности вместе с соответствующим

индексом, и команду ALTER TABLE … ADD CONSTRAINT … USING

INDEX для создания нового ограничения, используя существующий

индекс.