Доступ к данным
Методы доступа
16
Авторские права
© Postgres Professional, 2019–2024
Авторы: Егор Рогов, Павел Лузанов, Павел Толмачев, Илья Баштанов
Фото: Олег Бартунов (монастырь Пху и пик Бхрикути, Непал)
Использование материалов курса
Некоммерческое использование материалов курса (презентации,
демонстрации) разрешается без ограничений. Коммерческое
использование возможно только с письменного разрешения компании
Postgres Professional. Запрещается внесение изменений в материалы
курса.
Обратная связь
Отзывы, замечания и предложения направляйте по адресу:
Отказ от ответственности
Компания Postgres Professional не несет никакой ответственности за
любые повреждения и убытки, включая потерю дохода, нанесенные
прямым или непрямым, специальным или случайным использованием
материалов курса. Компания Postgres Professional не предоставляет
каких-либо гарантий на материалы курса. Материалы курса
предоставляются на основе принципа «как есть» и компания Postgres
Professional не обязана предоставлять сопровождение, поддержку,
обновления, расширения и изменения.
2
Темы
Последовательное сканирование (Seq Scan)
Сканирование индекса (Index Scan)
Сканирование по битовой карте (Bitmap Scan)
Сканирование только индекса (Index-Only Scan)
Сравнение эффективности методов доступа
3
Seq Scan
Последовательное чтение всех страниц
страницы читаются в кеш
проверяется видимость версий строк
данные возвращаются в произвольном порядке
время сканирования зависит от физического размера файла
4 3 5 2 1 10 12 8 7 11 4 9 6
неактуальная
версия
N
U
L
L
В распоряжении оптимизатора имеется несколько способов доступа
к данным. Самый простой из них — последовательное сканирование
таблицы. Файл (или файлы) основного слоя таблицы читается
постранично от начала до конца. Напомним, что чтение происходит
через буферный кеш (для временных таблиц – через локальный кеш
сеанса).
Последовательное чтение файла позволяет использовать тот факт, что
операционная система обычно читает данные порциями большими, чем
размер страницы — с большой вероятностью несколько следующих
страниц уже окажутся в кеше ОС.
Последовательное сканирование эффективно работает, когда надо
прочитать всю таблицу или значительную ее часть (если селективность
условия низка).
При последовательном сканировании на каждой странице
рассматриваются все версии строк — в том числе и неактуальные
(мертвые) версии, которые еще не удалены процедурой очистки
(процессом автоочистки). Если в файлах таблицы остается много
мертвых, но не вычищенных версий строк, это будет приводить
к замедлению скорости работы последовательного сканирования.
В частности поэтому своевременное выполнение очистки может
существенно ускорить выполнение некоторых запросов.
Подробнее про версии строк, снимки данных и очистку ненужных
версий строк рассказано в курсе DBA2.
5
Массовое вытеснение
буферное кольцо (32 страницы)
shared_buffers
процесс
сканирует
таблицу
процесс
присоединился
к кольцу
При последовательном сканировании через буферный кеш проходит
большое количество страниц с «одноразовыми» данными, которые
могут вытеснять полезные страницы из буферов. Чтобы этого не
происходило, используются так называемые буферные кольца.
Для последовательного чтения большой таблицы (размер которой
превышает четверть буферного кеша) из всего кеша используются
только 32 страницы, в пределах которых действует вытеснение. При
этом остальные данные в буфере не страдают.
Если в процессе чтения меняются биты-подсказки или сами данные,
появляется грязный буфер. Такой буфер отцепляется от кольца и будет
вытеснен на общих основаниях, а в кольцо добавляется новый буфер.
Такая стратегия рассчитана на то, что в основном данные читаются,
а не меняются.
Если в процессе чтения таблицы другому процессу потребуются та же
таблица, он не начинает читать ее с начала, а подключается к
имеющемуся буферному кольцу. После окончания сканирования
процесс дочитывает «пропущенное» начало таблицы.
При работе с временными таблицами через локальный кеш механизм
буферных колец не используется.
7
B-дерево
Индекс
вспомогательная структура во внешней памяти
сопоставляет ключи и идентификаторы строк таблицы
Устройство: дерево поиска
сбалансированное
сильно ветвистое
только сортируемые типы данных (операции «больше», «меньше»)
результаты поиска автоматически отсортированы
Использование
ускорение доступа
поддержка ограничений целостности
В этой теме мы будем рассматривать только один из доступных
в PostgreSQL типов индексов: B-дерево (B-tree). Это наиболее часто
применяющийся на практике тип индекса. Некоторые другие типы
индексов рассмотрены далее в этом курсе в теме «Типы индексов».
Как и все индексы в PostgreSQL, B-дерево является вторичной
структурой — индекс не содержит в себе никакой информации, которую
нельзя было бы получить из самой таблицы, однако занимает
дополнительное место на диске. Индекс можно удалить и пересоздать.
Индексы нужны для ускорения операций, затрагивающих небольшую
часть таблицы: выборки малого количества строк, а также поддержки
ограничений целостности (первичных и уникальных ключей).
Индексы сопоставляют значения проиндексированных полей (ключи
поиска) и идентификаторы строк таблицы. Для этого в индексе B-tree
строится упорядоченное дерево ключей, в котором можно быстро найти
нужный ключ, а вместе с ним — и ссылки на версии строк.
Но проиндексировать можно только данные, допускающие сортировку
(должны быть определены операции «больше», «меньше»). Например,
числа, строки и даты могут быть проиндексированы, а точки на
плоскости — нет (для них существуют другие типы индексов). При
индексации текстовых строк нужно учитывать особенности правил
сортировки (подробнее см. курс DBA2, тема «Локализация»).
Особенностями B-дерева является его сбалансированность
(постоянная глубина) и сильная ветвистость. Хотя размер дерева
зависит от проиндексированных столбцов, на практике деревья обычно
имеют глубину не больше 4–5.
8
B-дерево
3 5 2 1 10 12 8 7
N
U
L
L
11 4
9
6
1 9
1 3 6 9 12
1 2 3 4 5 6 7 8 9 10 11 12 N
корень
листья
внутренние
страницы
табличные
страницы
4
В верхней части слайда приведен пример B-дерева. Его страницы
состоят из индексных записей, каждая из которых содержит:
●
ключ – значения столбцов, по которым построен индекс (такие
столбцы называются ключевыми);
●
ссылку на другую страницу индекса или ссылки на версии строк.
Внутри страницы ключи всегда упорядочены.
Листовые страницы ссылаются непосредственно на табличные
версии строк, содержащие ключи индексирования. Эти страницы
связаны двунаправленным списком, чтобы было удобно перебирать
ключи в порядке возрастания или убывания.
Внутренние страницы ссылаются на нижележащие страницы индекса,
а значения ключей определяют диапазон значений, которые можно
обнаружить, спустившись по ссылке.
Верхняя страница дерева, на которую нет ссылок, называется корнем.
Индексная страница может быть заполнена частично. Свободное
место используется для вставки в индекс новых записей. Если же на
странице не хватает места — она разделяется на две новых страницы.
Разделившиеся страницы никогда не объединяются, и это в некоторых
случаях может приводить к разрастанию индекса.
По умолчанию считается, что неопределенные значения «больше»
обычных, и они хранятся в дереве справа. Этот порядок можно
изменить при создании индекса с помощью предложений NULLS LAST
и NULLS FIRST.
9
Index Scan: одно значение
5 2 1 12 8 7 11 4 9 6
1 9
1 3 6 9 12
1 2 3 4 5 6 7 8 9 10 11 12 N
N
U
L
L
4 3 10
Рассмотрим, как происходит поиск одного значения с помощью
индекса. Например, нам нужно найти в таблице строку, в которой
значение проиндексированного столбца равно четырем.
Начинаем с корня дерева. Индексные записи в корневой странице
определяют диапазоны значений ключей в нижележащих страницах:
«от 1 до 9» и «9 и больше». Нам подходит диапазон «от 1 до 9», что
соответствует строке с ключом 1. Заметим, что ключи хранятся
упорядоченно, следовательно, поиск внутри страницы выполняется
очень эффективно.
Ссылка из найденной записи приводит нас к странице второго уровня.
В ней мы находим диапазон «от 3 до 6» (ключ 3) и переходим
к странице третьего уровня.
Эта страница является листовой. В ней мы находим ключ, равный 4,
и переходим на страницу таблицы.
Заметьте, что ключи могут повторяться, причем даже в уникальном
индексе: из-за работы механизма многоверсионности могут возникать
разные версии одной и той же строки. Для экономии места ключи
хранятся в индексной странице в одном экземпляре.
Прежде чем вернуть найденные версии строк, необходимо проверить
их видимость.
На иллюстрациях цветом выделены записи и страницы, которые
потребовалось прочитать.
11
Index Scan: диапазон
5 2 1 12 8 7 11 4 9 6
1 9
1 3 6 9 12
1 2 3 4 5 6 7 8 9 10 11 12 N
N
U
L
L
страницы
читаются
хаотично
4 3 10
B-дерево позволяет эффективно искать не только отдельные значения,
но и диапазоны значений (по условиям «меньше», «больше», «меньше
или равно», «больше или равно», а также «between»).
Вот как это происходит. Сначала мы ищем крайний ключ условия.
Например, для условия «от 4 до 9» мы можем выбрать значение 4
или 9, а для условия «меньше 9» надо взять 9. Затем спускаемся до
листовой страницы индекса так, как мы рассматривали в предыдущем
примере, и получаем первое значение из таблицы.
Дальше остается двигаться по листовым страницам индекса вправо
(или влево, в зависимости от условия), перебирая записи этих страниц
до тех пор, пока мы не встретим ключ, выпадающий из диапазона.
На слайде показан пример поиска значений по условию «x BETWEEN
4 AND 9» или, что тоже самое, «x >= 4 AND x <= 9». Спустившись
к значению 4, мы затем перебираем ключи 5, 6, и так далее до 9.
Встретив ключ 10, прекращаем поиск.
Нам помогают два свойства: упорядоченность ключей на всех
страницах и связанность листовых страниц двунаправленным списком.
Результат поиска автоматически получается отсортированным.
Обратите внимание, что к одной и той же табличной странице нам
пришлось обращаться несколько раз. Мы прочитали первую страницу
таблицы (значение 4), затем последнюю (тоже 4), затем опять первую
(5), затем опять последнюю (6) и так далее.
13
Bitmap Index Scan
3 5 2 1 10 12 8 7 11 4 9 6
1 9
1 3 6 9 12
1 2 3 4 5 6 7 8 9 10 11 12 N
4
N
U
L
L
Многократный просмотр одних и тех же табличных страниц крайне
неэффективен. Даже в лучшем случае, если нужная страница
находится в буферном кеше, ее нужно найти и заблокировать (см. курс
DBA2: тема «Буферный кеш» модуля «Журналирование»), а в худшем
приходится иметь дело со случайными чтениями с диска.
Чтобы не тратить ресурсы на повторный просмотр табличных страниц,
применяется еще один способ доступа — сканирование по битовой
карте. Он похож на обычный индексный доступ, но происходит в два
этапа.
Сначала сканируется индекс (Bitmap Index Scan) и в локальной памяти
процесса строится битовая карта. Битовая карта состоит из
фрагментов. Фрагменты соответствуют табличным страницам,
а каждый бит фрагмента соответствует версии строки в этой странице.
При построении битовой карты в ней отмечаются те версии строк,
которые удовлетворяют условию и должны быть прочитаны.
За счет разделения битовой карты на фрагменты карта, в которой
отмечено немного версий, будет занимать мало места.
14
Bitmap Heap Scan
5 2 1 12 8 7 11 4 9 6
1 9
1 3 6 9 12
1 2 3 4 5 6 7 8 9 10 11 12 N
N
U
L
L
4 3 10
Когда индекс просканирован и битовая карта готова, начинается
сканирование таблицы (Bitmap Heap Scan). При этом:
●
используется собственный механизм предвыборки, при котором
асинхронно читаются effective_io_concurrency страниц (по умолчанию
значение равно единице);
●
на одной странице может проверяться несколько версий строк,
но каждая страница просматривается ровно один раз.
16
Неточные фрагменты
Битовая карта без потери точности
пока размер карты не превышает work_mem,
информация хранится с точностью до версии строки
Битовая карта с потерей точности
если память закончилась, происходит огрубление
части уже построенной карты до отдельных страниц
требуется примерно 1 МБ памяти на 64 ГБ данных;
ограничение work_mem может быть превышено
Битовая карта хранится в локальной памяти обслуживающего
процесса, и под ее хранение выделяется work_mem байт. Временные
файлы никогда не используются.
Если карта перестает помещаться в work_mem, часть ее фрагментов
«огрубляется» — каждый бит начинает соответствовать целой
странице, а не отдельной версии строки (lossy bitmap). Стоимость
обработки таких фрагментов увеличивается. Освободившееся место
используется для того, чтобы продолжить строить карту.
В принципе, при сильно ограниченном work_mem и большой выборке
битовая карта может не поместиться в памяти, даже если в ней совсем
не останется информации на уровне версий строк. В таком случае
ограничение work_mem нарушается — под карту будет дополнительно
выделено столько памяти, сколько необходимо.
17
Неточные фрагменты
5 2 1 12 8 7 11 4 9 6
1 9
1 3 6 9 12
1 2 3 4 5 6 7 8 9 10 11 12 N
точный
фрагмент
неточный фрагмент,
требуется перепроверка
N
U
L
L
4 3 10
На рисунке показана битовая карта, состоящая из двух фрагментов.
Первый фрагмент — точный, каждый его бит соответствует одной
версии строки. Второй фрагмент — неточный, в нем каждый бит
соответствует целой странице.
Неточные фрагменты требуют перепроверки условий для всех версий
строк в табличной странице, а это сказывается на производительности.
Если две битовые карты объединяются, причем фрагмент хотя бы
одной из карт неточен, то и результирующий фрагмент тоже
вынужденно будет неточным. Поэтому размер work_mem играет
большую роль для эффективности сканирования по битовой карте.
19
Index Scan / Bitmap Scan
1 2 3 4 5 6 7 8 9 10 11 12
1 9
1 3 6 9 12
1 2 3 4 5 6 7 8 9 10 11 12 N
страницы
упорядочены
N
U
L
L
4
Если данные в таблице физически упорядочены, обычное индексное
сканирование не будет читать табличную страницу повторно. В таком
(нечастом на практике) случае метод сканирования по битовой карте
теряет смысл, проигрывая обычному индексному сканированию.
Разумеется, планировщик это тоже учитывает (как именно —
рассматривается в теме «Базовая статистика»).
21
Index-Only Scan
4 3 5 2 1 10 12 8 7 11 4 9 6
1 9
1 3 6 9 12
1 2 3 4 5 6 7 8 9 10 11 12 N
страница есть
в карте видимости,
проверка не нужна
страницы нет
в карте видимости,
проверка по таблице
N
U
L
L
Если в запросе требуются только проиндексированные данные, они уже
есть в самом индексе и к таблице обращаться не надо. Такой индекс
называется покрывающим для запроса.
Это хорошая оптимизация, исключающая обращения к табличным
страницам. Но, к сожалению, индексные страницы не содержат
информацию о видимости строк — чтобы проверить, надо ли
показывать найденную в индексе строку, мы вынуждены заглянуть
и в табличную страницу, что сводит оптимизацию на нет.
Поэтому критическую роль в эффективности сканирования только
индекса играет карта видимости. Если табличная страница содержит
гарантированно видимые данные и это отражено в карте видимости,
к такой табличной странице обращаться не надо. Но страницы, не
отмеченные в карте видимости, посетить все-таки придется.
Это одна из причин, по которым стоит выполнять очистку достаточно
часто — именно этот процесс обновляет карту видимости.
Планировщик не знает точно, сколько табличных страниц потребуют
проверки, но учитывает оценку этого числа. При плохом прогнозе
планировщик может отказаться от использования сканирования только
индекса.
При обработке каждой индексной записи в листовом узле сначала
проверяется наличие табличной страницы в карте видимости, а при ее
отсутствии читается сама табличная страница.
23
Многоколоночный индекс
1,A 2,C
1,A 1,C 2,N 3,C
1,A 1,B 1,C 2,A 2,B 2,N 2,D 3,A 3,C N,A N,N
NULL
1
C
3
A
2
A
1
A
1
B
3
C
NULL
2
B
2
D
NULL
NULL
2
A
Индекс можно создать по нескольким столбцам. В этом случае имеет
значение порядок следования столбцов и порядок сортировки.
На рисунке приведен пример многоколоночного индекса, построенного
по двум столбцам (оба — по возрастанию значений). Такой индекс
ускоряет поиск, если в запросе есть условие на один или несколько
первых ключей, поскольку в индексных записях ключи отсортированы
сначала по первому столбцу, затем по второму и так далее.
В примере, показанном на слайде, поиск происходит по первому и
второму столбцам; индекс подошел бы и для условия только на первый
столбец.
24
Многоколоночный индекс
1,A 2,C
1,A 1,C 2,N 3,C
1,A 1,B 1,C 2,A 2,B 2,N 2,D 3,A 3,C N,A N,N
NULL
1
C
3
A
2
A
1
A
1
B
3
C
NULL
2
B
2
D
NULL
NULL
2
A
Однако если запрос содержит условие только на второй столбец,
индекс оказывается бесполезным. На слайде видно, что листовые
записи, в которых второй столбец равен «A», могут оказаться в любом
месте индекса — у нас нет способа спуститься к ним от корня дерева.
Иногда в таких случаях планировщик все-таки прибегает к только
индексному сканированию, но при этом просматривается весь индекс
целиком.
Аналогично, индекс не может выдавать записи в порядке, отличном
от указанного при создании индекса. Например, показанный на слайде
индекс не может выдавать записи, отсортированные по первому
столбцу в порядке возрастания, а по второму — в порядке убывания.
26
Include-индексы
Индекс с дополнительными неключевыми столбцами
CREATE INDEX ... INCLUDE (...)
Неключевые столбцы
не используются при поиске по индексу
не учитываются ограничением уникальности
значения хранятся в индексной записи
и возвращаются без обращения к таблице
Покрывающий индекс, как правило, увеличивает эффективность
выборки. Чтобы сделать индекс покрывающим, в него может
понадобиться добавить столбцы, но это не всегда возможно:
●
добавление столбца в уникальный индекс нарушит гарантию
уникальности исходных столбцов;
●
тип данных добавляемого столбца может не поддерживаться
индексом.
В таких случаях можно добавить к индексу неключевые столбцы,
указав их в предложении INCLUDE.
Значения таких столбцов не формируют дерево индекса, а просто
хранятся как дополнительные сведения в индексных записях листовых
страниц. Поиск по неключевым столбцам не работает, но их значения
могут быть получены без обращения к таблице.
В настоящее время include-индексы поддерживаются только для
индексов на основе B-деревьев, GiST и SP-GiST-индексов.
Include-индексы создаются, чтобы индекс стал покрывающим, но не
стоит путать эти два термина. Индекс вполне может быть покрывающим
для некоторого запроса, но не использовать предложение INCLUDE.
А include-индекс может не быть покрывающим для каких-то запросов.
28
Сравнение эффективности
время
селективность
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
пропорционально
кол-ву строк
пропорционально
кол-ву страниц
Индексное сканирование лучше всего работает при очень высокой
селективности, когда по индексу выбирается одно или несколько
значений.
При средней селективности обычно лучше всего показывает себя
сканирование по битовой карте. Хотя этот способ требует
предварительного построения битовой карты, он выигрывает
у индексного сканирования, поскольку обходится без повторных чтений
одних и тех же страниц (если только данные в таблице не расположены
физически в нужном порядке, что бывает нечасто). В худшем случае
производительность индексного доступа пропорциональна числу
выбираемых строк, а сканирования по битовой карте — числу страниц.
При низкой селективности лучше всего работает последовательное
сканирование: если надо выбрать все или почти все табличные строки,
обращение к индексным страницам только увеличивает накладные
расходы. Этот эффект усиливается в случае вращающихся дисков, где
скорость произвольного чтения существенно ниже скорости чтения
последовательно расположенных страниц.
Значение селективности, при котором становится выгодно
переключиться на другой метод доступа, сильно зависит от конкретной
таблицы и конкретного индекса. Планировщик учитывает множество
параметров, чтобы выбрать наиболее подходящий способ.
Еще одно замечание: при индексном доступе результат возвращается
отсортированным, что в ряде случаев увеличивает привлекательность
такого доступа даже при низкой селективности.
29
Сравнение эффективности
время
селективность
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-дисках).
В худшем случае, когда требуется проверять видимость каждой строки,
метод вырождается в обычное индексное сканирование.
Поэтому планировщику приходится учитывать состояние карты
видимости: при неблагоприятном прогнозе исключительно индексное
сканирование не применяется из-за опасности получить замедление
вместо ускорения.
30
Итоги
Оптимизатор располагает несколькими методами доступа
последовательное сканирование
сканирование индекса
сканирование только индекса
сканирование по битовой карте
Модель стоимости учитывает множество параметров
31
Практика
1. Убедитесь, что при повторном выполнении запрос,
выбирающий все строки из таблицы flights, читает данные
из кеша СУБД.
2. В демонстрации был создан include-индекс для таблицы
билетов tickets. Замените им индекс, поддерживающий
первичный ключ.
3. Создайте индекс по столбцу amount таблицы перелетов
ticket_flights. Найдите перелеты стоимостью более
120 000 руб. (примерно 1 % строк). Какой метод доступа
был выбран?
4. Повторите п. 3 для стоимости менее 42 000 руб. (около
90% строк).
1. Используйте команду EXPLAIN с параметрами analyze и buffers.
4. Попробуйте также запретить выбранный метод доступа (параметр
enable_seqscan) и сравнить скорости выполнения.
