Оптимизация запросов
Индексный доступ
13
Авторские права
© Postgres Professional, 2019–2022
Авторы: Егор Рогов, Павел Лузанов, Павел Толмачев, Илья Баштанов
Использование материалов курса
Некоммерческое использование материалов курса (презентации,
демонстрации) разрешается без ограничений. Коммерческое
использование возможно только с письменного разрешения компании
Postgres Professional. Запрещается внесение изменений в материалы
курса.
Обратная связь
Отзывы, замечания и предложения направляйте по адресу:
Отказ от ответственности
Компания Postgres Professional не несет никакой ответственности за
любые повреждения и убытки, включая потерю дохода, нанесенные
прямым или непрямым, специальным или случайным использованием
материалов курса. Компания Postgres Professional не предоставляет
каких-либо гарантий на материалы курса. Материалы курса
предоставляются на основе принципа «как есть» и компания Postgres
Professional не обязана предоставлять сопровождение, поддержку,
обновления, расширения и изменения.
2
Темы
B-деревья
Сканирование индекса
Сканирование только индекса
Индексы с дополнительными столбцами
Дубликаты в индексе
3
B-дерево
Индекс
вспомогательная структура во внешней памяти
сопоставляет ключи и идентификаторы строк таблицы
Устройство: дерево поиска
сбалансированное
сильно ветвистое
только сортируемые типы данных (операции «больше», «меньше»)
результаты автоматически отсортированы
Использование
ускорение доступа
поддержка ограничений целостности
В этом модуле мы будем рассматривать только один из доступных
в PostgreSQL типов индексов: B-дерево (B-tree). Это самый часто
применяющийся на практике тип индекса. Некоторые другие типы
индексов рассмотрены в курсе DEV2.
Как и все индексы в PostgreSQL, B-дерево является вторичной
структурой — индекс не содержит в себе никакой информации, которую
нельзя было бы получить из самой таблицы. Индекс можно удалить и
пересоздать. Индексы нужны для ускорения операций, затрагивающих
небольшую часть таблицы: выборки малого количества строк, а также
поддержки ограничений целостности (первичных и уникальных ключей).
Любой индекс сопоставляет значения проиндексированных полей
(ключи поиска) и идентификаторы строк таблицы. Для этого в индексе
B-tree строится упорядоченное дерево ключей, в котором можно быстро
найти нужный ключ, а вместе с ним — и ссылку на табличную строку.
Но проиндексировать можно только данные, допускающие сортировку
(должны быть определены операции «больше», «меньше»). Например,
числа, строки и даты могут быть проиндексированы, а точки на
плоскости — нет (для них существуют другие типы индексов).
Особенностями B-дерева является его сбалансированность
(постоянная глубина) и сильная ветвистость. Хотя размер дерева
зависит от проиндексированных столбцов, на практике деревья обычно
имеют глубину не больше 4–5.
4
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-дерева (верхняя часть рисунка).
У дерева есть корневая, внутренние и листовые страницы.
Страницы состоят из индексных записей, каждая из которых содержит:
- значения столбцов, по которым построен индексакие столбцы
называются ключевыми);
- ссылку на другую страницу индекса или версию строки.
Внутри страницы ключи всегда упорядочены.
Листовые страницы ссылаются непосредственно на табличные версии
строк, содержащие ключи индексирования.
Внутренние страницы ссылаются на нижележащие страницы индекса,
а значения ключей определяют диапазон значений, которые можно
обнаружить, спустившись по ссылке.
Самая верхняя страница дерева, на которую нет ссылок, называется
корнем.
Индексная страница может быть заполнена не полностью. Свободное
место используется для вставки в индекс новых значений. Если же на
странице не хватает места — она разделяется на две новых страницы.
Разделившиеся страницы никогда не объединяются, и это в некоторых
случаях может приводить к разрастанию индекса.
5
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,
и переходим на страницу таблицы.
В действительности процесс более сложен: мы не говорили про
неуникальные ключи, про проблемы одновременного доступа и так
далее. Но не будем углубляться в детали реализации.
Обратите внимание: на этой и следующих иллюстрациях цветом
выделены те строки и те страницы, которые потребовалось прочитать.
7
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) и так далее.
9
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. параллель-
ное сканирование
Индексный доступ может выполняться в параллельном режиме. Это
происходит в два этапа. Сначала ведущий процесс спускается от корня
дерева к листовой странице. Затем рабочие процессы выполняют
параллельное чтение листовых страниц индекса, двигаясь по
указателям.
Процесс, прочитавший индексную страницу, выполняет и чтение
необходимых табличных страниц. При этом может получиться так, что
одну и ту же табличную страницу прочитают несколько процессов (этот
пример показан на иллюстрации: последняя табличная страница
содержит строки, ссылки на которые ведут от нескольких индексных
страниц, прочитанных разными процессами). Конечно, сама страница
будет находиться в буферном кеше в одном экземпляре.
11
Число рабочих процессов
Равно нулю (параллельный план не строится)
если размер выборки < min_parallel_index_scan_size = 512kB
Фиксировано
если для таблицы указан параметр хранения parallel_workers
Вычисляется по формуле
1 + log
3
(размер выборки / min_parallel_index_scan_size)
Но не больше, чем max_parallel_workers_per_gather
Число рабочих процессов выбирается примерно так же, как и в случае
последовательного сканирования. Сравнивается объем данных,
который предполагается прочитать из индекса (определяемый числом
индексных страниц) со значением параметра
min_parallel_index_scan_size (по умолчанию 512kB).
Если в случае последовательного сканирования таблицы объем данных
определялся размером всей таблицы, то при индексном доступе
планировщик должен спрогнозировать, сколько индексных страниц
будет прочитано. Как именно это происходит, рассматривается позже
в теме «Статистика».
Если размер выборки меньше, параллельный план не рассматривается
оптимизатором. Например, никогда не будет выполняться параллельно
доступ к одному значению — в этом случае просто нечего
распараллеливать.
Если размер выборки достаточно велик, число рабочих процессов
определяется по формуле, если только оно не указано явно
в параметре хранения parallel_workers таблицы (не индекса!).
Число процессов в любом случае не будет превышать значения
параметра max_parallel_workers_per_gather.
13
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)
достаточно часто — именно этот процесс обновляет карту видимости.
Планировщик не знает точно, сколько табличных страниц потребуют
проверки, но учитывает оценку этого числа. При плохом прогнозе
планировщик может отказаться от использования сканирования только
индекса.
При обработке каждой индексной записи сначала проверяется наличие
табличной страницы в карте видимости, а при ее отсутствии читается
сама табличная страница.
15
Include-индексы
Индекс с дополнительными неключевыми столбцами
CREATE INDEX ... INCLUDE (...)
Неключевые