Оптимизация запросов
Сканирование по битовой карте
13
Авторские права
© Postgres Professional, 2019–2022
Авторы: Егор Рогов, Павел Лузанов, Павел Толмачев, Илья Баштанов
Использование материалов курса
Некоммерческое использование материалов курса (презентации,
демонстрации) разрешается без ограничений. Коммерческое
использование возможно только с письменного разрешения компании
Postgres Professional. Запрещается внесение изменений в материалы
курса.
Обратная связь
Отзывы, замечания и предложения направляйте по адресу:
edu@postgrespro.ru
Отказ от ответственности
Компания Postgres Professional не несет никакой ответственности за
любые повреждения и убытки, включая потерю дохода, нанесенные
прямым или непрямым, специальным или случайным использованием
материалов курса. Компания Postgres Professional не предоставляет
каких-либо гарантий на материалы курса. Материалы курса
предоставляются на основе принципа «как есть» и компания Postgres
Professional не обязана предоставлять сопровождение, поддержку,
обновления, расширения и изменения.
2
Темы
Сканирование по битовой карте
Сравнение эффективности разных методов доступа
3
Битовая карта
Построение битовой карты (Bitmap Index Scan)
Сканирование по битовой карте (Bitmap Heap Scan)
Точные и неточные фрагменты
Параллельное сканирование (Parallel Bitmap Heap Scan)
Объединение битовых карт
4
Bitmap 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
Многократный просмотр одних и тех же табличных страниц крайне
неэффективен. Даже в лучшем случае, если нужная страница
находится в буферном кеше, ее нужно найти и заблокировать (см. курс
DBA2: тема «Буферный кеш» модуля «Журналирование»), а в худшем
приходится иметь дело со случайными чтениями с диска.
Чтобы не тратить ресурсы на повторный просмотр табличных страниц,
применяется еще один способ доступа — сканирование по битовой
карте. Он похож на обычный индексный доступ, но происходит в два
этапа.
Сначала сканируется индекс (Bitmap Index Scan) и в локальной памяти
процесса строится битовая карта. Битовая карта состоит из
фрагментов. Фрагменты соответствуют табличным страницам,
а каждый бит фрагмента соответствует версии строки в этой странице.
При построениии битовой карты в ней отмечаются те версии строк,
которые удовлетворяют условию и должны быть прочитаны.
За счет разделения битовой карты на фрагменты карта, в которой
отмечено немного версий, будет занимать мало места.
5
Bitmap Heap 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
Когда индекс просканирован и битовая карта готова, начинается
сканирование таблицы (Bitmap Heap Scan). При этом:
- используется собственный механизм предвыборки, при котором
асинхронно читаются effective_io_concurrency страниц (по умолчанию
значение равно единице);
- на одной странице может проверяться несколько версий строк, но
каждая страница просматривается ровно один раз.
7
Parallel Bitmap Heap 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
Сканирование по битовой карте может выполняться параллельно.
Первый этап — сканирование индекса — всегда выполняется
последовательно ведущим процессом.
А второй этап — сканирование таблицы — выполняется рабочими
процессами параллельно. Это происходит аналогично параллельному
последовательному сканированию.
9
Неточные фрагменты
Битовая карта без потери точности
пока размер карты не превышает work_mem,
информация хранится с точностью до версии строки
Битовая карта с потерей точности
если память закончилась, происходит огрубление
части уже построенной карты до отдельных страниц
требуется примерно 1 МБ памяти на 64 ГБ данных;
ограничение памяти может быть превышено
Битовая карта хранится в локальной памяти обслуживающего процесса
и под ее хранение выделяется work_mem байт. Временные файлы
никогда не используются.
Если карта перестает помещаться в work_mem, часть ее фрагментов
«огрубляется» — каждый бит начинает соответствовать целой
странице, а не отдельной версии строки (lossy bitmap). Стоимость
обработки таких фрагментов увеличивается. Освободившееся место
используется для того, чтобы продолжить строить карту.
В принципе, при сильно ограниченном work_mem и большой выборке,
битовая карта может не поместиться в памяти, даже если в ней совсем
не останется информации на уровне версий строк. В таком случае
ограничение work_mem нарушается — под карту будет дополнительно
выделено столько памяти, сколько необходимо.
10
Неточные фрагменты
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
точный
фрагмент
неточный фрагмент,
требуется перепроверка
На рисунке показана битовая карта, состоящая из двух фрагментов.
Первый фрагмент — точный, каждый его бит соответствует одной
версии строки. Второй фрагмент — неточный, в нем каждый бит
соответствует целой странице.
Неточные фрагменты требуют перепроверки условий для всех версий
строк в табличной странице, а это сказывается на производительности.
Если две битовые карты объединяются, причем фрагмент хотя бы
одной из карт неточен, то и результирующий фрагмент тоже
вынужденно будет неточным. Поэтому размер work_mem играет
большую роль для эффективности сканирования по битовой карте.
12
Сравнение эффективности
Сравнение различных методов доступа
Кластеризация
13
Сравнение эффективности
время
селективность
0 1s
1
s
2
I
n
d
e
x
S
c
a
n
B
i
t
m
a
p
I
n
d
e
x
S
c
a
n
Seq Scan
пропорционально
кол-ву строк
пропорционально
кол-ву страниц
Индексное сканирование лучше всего работает при очень высокой
селективности, когда по индексу выбирается одно или несколько
значений.
При средней селективности лучше всего показывает себя сканирование
по битовой карте. Оно работает лучше индексного сканирования,
поскольку обходится без повторных чтений одних и тех же страниц.
Однако при сканировании по битовой карте возникают накладные
расходы на построение карты, поэтому при высокой селективности оно
проигрывает.
При низкой селективности лучше всего работает последовательное
сканирование: если надо выбрать все или почти все табличные строки,
обращение к индексным страницам только увеличивает накладные
расходы. Этот эффект усиливается в случае вращающихся дисков, где
стоимость произвольного чтения существенно выше стоимости чтения
последовательно расположенных страниц.
Значение селективности, при котором становится выгодно
переключиться на другой метод доступа, сильно зависит от конкретной
таблицы и конкретного индекса. Планировщик учитывает множество
параметров, чтобы выбрать наиболее подходящий способ.
Еще одно замечание: при индексном доступе результат возвращается
отсортированным, что в ряде случаев увеличивает привлекательность
такого доступа даже при низкой селективности.
14
Index Scan / Bitmap Scan
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 9
1 3 6 9 12
1 2 3 4 5 6 7 8 9 10 11 12 13 14
страницы
упорядочены
Если данные в таблице физически упорядочены, обычное индексное
сканирование не будет читать табличную страницу повторно. В таком
(нечастом на практике) случае метод сканирования по битовой карте
теряет смысл, проигрывая обычному индексному сканированию.
Разумеется, планировщик это тоже учитывает (как именно –
рассматривается в теме «Статистика»).
16
Сравнение эффективности
время
селективность
0 1
I
n
d
e
x
S
c
a
n
B
i
t
m
a
p
I
n
d
e
x
S
c
a
n
Seq Scan
худший
случай
I
n
d
e
x
O
n
l
y
S
c
a
n
лучший
случай
Эффективность сканирования только индекса сильно зависит от
актуальности карты видимости (и от того, сколько страниц
действительно содержат только актуальные версии строк).
В лучшем случае этот метод доступа может быть эффективней
последовательного сканирования даже при низкой селективности (если
индекс меньше, чем таблица, и особенно на SSD-дисках).
В худшем случае, когда требуется проверять видимость каждой строки,
метод вырождается в обычное индексное сканирование.
Поэтому планировщику приходится учитывать состояние карты
видимости: при неблагоприятном прогнозе исключительно индексное
сканирование не применяется из-за опасности получить замедление
вместо ускорения.
17
Итоги
Сканирование по битовой карте
исключает повторное чтение табличных страниц
позволяет объединять несколько индексов
эффективно при средней селективности
Несколько методов доступа позволяют планировщику
выбрать лучший, учитывая различные факторы:
селективность условия
необходимость обращения к таблице
полноту карты видимости
соответствие порядка данных в таблице и в индексе
необходимость получить отсортированную выборку
потребность быстрого получения первых результатов
и другие
18
Практика
1. Создайте индекс по столбцу amount таблицы перелетов
(ticket_flights).
2. Напишите запрос, находящий информацию о перелетах
стоимостью более 180 000 руб. (менее 1% строк).
Какой метод доступа был выбран? Сколько времени
выполняется запрос?
Запретите выбранный метод доступа, снова выполните
запрос и сравните время выполнения. Прав ли был
оптимизатор?
3. Повторите пункт 2 для стоимости менее 44 000 руб. (чуть
более 90% строк).
2. Для запрета метода доступа установите один из параметров
в значение off:
- enable_seqscan,
- enable_indexscan,
- enable_bitmapscan.
Например:
SET enable_seqscan = off;
3. Не забудьте восстановить значение измененного параметра,
например:
RESET enable_seqscan;