«Покрывающий индекс» не просто еще одна фича, которая может пригодиться. Это вещь сугубо практичная. Без них Index Only Scan может не дать выигрыша. Хотя и покрывающий индекс в разных ситуациях эффективен по-разному.
Но, по-порядку: покрывающий индекс — это индекс, который содержит все значения столбцов, необходимые запросу; при этом обращение к самой таблице уже не требуется. Речь здесь будет не совсем о покрывающих индексах: строго говоря, в Postgres появились так называемые инклюзивные индексы. О «почти» и других нюансах можно прочитать в статье Егора Рогова, входящей в его индексный сериал из 10 (!) частей. Почти. Такие индексы формируются с ключевым словом INCLUDE. А инклюзивный индекс создается специально для поиска по типичным запросам: к поисковому индексу добавляются значения полей, по которым искать нельзя, они нужны только для того, чтобы не обращаться лишний раз к таблице.
Этот патч вошел в версию PostgreSQL 11. Анастасия Лубенникова (Postgres Professional) доработала метод btree так, чтобы в индекс можно было включать дополнительные столбцы. К 12-й GiST дозрел.
Конструктивное желание иметь инклюзивные индексы для GiST возникло давно: пробный патч Андрей Бородин предложил сообществу еще в середине апреля 2018-го года. Но патчи для методов доступа GiST/SP-GiST не успели созреть до выхода этой версии. Он и проделал всю основную, очень непростую работу.
В начале августа 2019-го Александр Коротков добавил косметические улучшения и закоммитил патч.
прямоугольников. Для демонстрации и некоторого исследования мы сгенерим набор из 3 млн. Заодно немного слов о типе box, так как не все манипуляции с ним интуитивны.
В документации читаем: «значения типа box записываются в одной из следующих форм: Тип box — то есть прямоугольник — в Postgres давно, он определяется 2-мя точками (геометрический тип point) — противоположными вершинами прямоугольника (то есть прямоугольник не может быть косым, заваленным набок).
( ( x1 , y1 ) , ( x2 , y2 ) ) ( x1 , y1 ) , ( x2 , y2 ) x1 , y1 , x2 , y2
На практике приходится писать, скажем, вот так:
SELECT box('1,2', '3,4'); box ------------- (3,4),(1,2)
(1 row)
Сначала Postgres показывает нам верхнюю правую вершину, потом нижнюю левую. Если напишем так,
SELECT box('5,2', '3,4'); box ------------- (5,4),(3,2)
(1 row)
то убедимся, что Postgres отдал вовсе не те вершины, которые дали ему. Он вычислил верхнюю правую и нижнюю левую по нашим верхней левой и нижней правой. Это удобное свойство, когда заранее не известно расположение вершин — при случайной генерации, например. Запись '1,2', '3,4' эквивалентна point(1,2), point(3,4). Такая форма иногда удобней.
За дело: поиск в 3 млн. прямоугольников
CREATE TABLE boxes(id serial, thebox box, name text);
Будем генерировать 3 млн. случайных прямоугольников. Хотим нормальное распределение, но чтобы не пользоваться расширением tablefunc, применим подход „для бедных“: используем random()-random(), который тоже даёт симпатичную (см рис.) картинку с прямоугольниками, которых тем больше, чем ближе они к центру. Их центры тяжести тоже случайны. Такие распределения характерны для некоторых видов реальных городских данных. А желающие углубиться в законы статистики или освежить воспоминания, могут почитать про разность случайных величин, например, здесь.
INSERT INTO boxes(thebox, name) SELECT box( point( random()-random(), random()-random() ), point( random()-random(), random()-random() ) ), 'box no.' || x FROM generate_series(1,3000000) AS g(x);
Теперь можно начать поиск. Размер таблицы, который показывает \dt+, 242MB.
Ищем без индекса:
EXPLAIN ANALYZE SELECT thebox, name FROM boxes WHERE thebox @> box('0.5, 0.4','0.3, 0.2'); QUERY PLAN -------------------------------------------------------------------------------------- Gather (cost=1000.00..47853.00 rows=3000 width=46) (actual time=0.140..246.998 rows=139189 loops=1) Workers Planned: 2 Workers Launched: 2 -> Parallel Seq Scan on boxes (cost=0.00..46553.00 rows=1250 width=46) (actual time=0.011..106.708 rows=46396 loops=3) Filter: (thebox @> '(0.5,0.4),(0.3,0.2)'::box) Rows Removed by Filter: 953604 Planning Time: 0.040 ms Execution Time: 259.262 ms
(8 rows)
Видим, что идёт Parallel Seq Scan — последовательное сканирование (хотя и распараллеленное).
Создаём обычный, неинклюзивный индекс:
CREATE INDEX ON boxes USING gist(thebox);
Размер индекса boxes_thebox_idx, который показывает \di+, 262MB. В ответ на тот же запрос получаем:
EXPLAIN ANALYZE SELECT thebox, name FROM boxes WHERE thebox @> box('0.5, 0.4','0.3, 0.2'); QUERY PLAN -------------------------------------------------------------------------------- Bitmap Heap Scan on boxes (cost=159.66..9033.30 rows=3000 width=46) (actual time=29.101..80.283 rows=139189 loops=1) Recheck Cond: (thebox @> '(0.5,0.4),(0.3,0.2)'::box) Heap Blocks: exact=30629 -> Bitmap Index Scan on boxes_thebox_idx (cost=0.00..158.91 rows=3000 width=0) (actual time=25.029..25.029 rows=139189 loops=1) Index Cond: (thebox @> '(0.5,0.4),(0.3,0.2)'::box) Planning Time: 0.053 ms Execution Time: 86.206 ms
(7 rows)
Время поиска сократилось раза в три и вместо Parallel Seq Scan получили Bitmap Index Scan. Он не распараллеливается, но работает быстрее.
Теперь убьем старый индекс и создадим инклюзивный:
CREATE INDEX ON boxes USING spgist(thebox) INCLUDE(name);
Индекс boxes_thebox_name_idx пожирней: 356MB. Поехали:
EXPLAIN ANALYZE SELECT thebox, name FROM boxes WHERE thebox @> box('0.5, 0.4','0.3, 0.2'); QUERY PLAN ------------------------------------------------------------------------------ Bitmap Heap Scan on boxes (cost=207.66..9081.30 rows=3000 width=46) (actual time=86.822..152.014 rows=139189 loops=1) Recheck Cond: (thebox @> '(0.5,0.4),(0.3,0.2)'::box) Heap Blocks: exact=30629 -> Bitmap Index Scan on boxes_thebox_name_idx (cost=0.00..206.91 rows=3000 width=0) (actual time=83.044..83.044 rows=139189 loops=1) Index Cond: (thebox @> '(0.5,0.4),(0.3,0.2)'::box) Planning Time: 3.807 ms Execution Time: 157.997 ms
(7 rows)
Читаем настольной книге творца индексов, в ч. Используется Index Only Scan, но картина печальная: время почти в 2 раза больше, чем без него. I:
Поэтому метод доступа возвращает все версии строк, попадающие под условие поиска, независимо от того, видны они текущей транзакции или нет. ‹‹Индексы в PostgreSQL не содержат информации, позволяющей судить о видимости строк. Проблема решается тем, что PostgreSQL поддерживает для таблиц так называемую карту видимости, в которой процесс очистки (vacuum) отмечает страницы, в которых данные не менялись достаточно давно для того, чтобы их видели все транзакции, независимо от времени начала и уровня изоляции. Однако если бы механизму индексирования приходилось каждый раз заглядывать в таблицу для определения видимости, этот метод сканирования ничем не отличался бы от обычного индексного сканирования. Если идентификатор строки, возвращенной индексом, относится к такой странице, то видимость можно не проверять.››
Повторяем: Делаем VACUUM.
EXPLAIN ANALYZE SELECT thebox, name FROM boxes WHERE thebox @> box('0.5, 0.4','0.3, 0.2'); QUERY PLAN -------------------------------------------------------------------------------- Index Only Scan using boxes_thebox_name_idx on boxes (cost=0.41..236.91 rows=3000 width=46) (actual time=0.104..38.651 rows=139189 loops=1) Index Cond: (thebox @> '(0.5,0.4),(0.3,0.2)'::box) Heap Fetches: 0 Planning Time: 0.052 ms Execution Time: 44.337 ms
(5 rows)
Совсем другое дело! Выигрыш вдвое по сравнению с неинклюзивным индексом.
Селективность и выигрыш
Эффективность работы инклюзивных индексов сильно зависит от селективности условий в запросах. Чтобы немного поисследовать эту зависимость, будем решать обратную задачу: сгенерим табличку с индексом по типу point и будем искать, сколько точек попадет в заданный box. Точки равномерно размажем по квадрату.
CREATE TABLE test_covergist(id serial, tochka point, name text);
INSERT INTO test_covergist(tochka, name) SELECT point(trunc(1000000*random()), trunc(1000000*random())), 'point no.' || g.x FROM generate_series(1,3000000) AS g(x);
Размер таблицы 211 MB.
CREATE INDEX on test_covergist USING gist(tochka);
Размер 213 MB.
Заберем в квадрат заведомо все имеющиеся точки:
EXPLAIN (ANALYZE, buffers) SELECT tochka, name FROM test_covergist WHERE box('0,0','3000000,3000000') @> tochka; QUERY PLAN ------------------------------------------------------------------------------------- Bitmap Heap Scan on test_covergist (cost=135.66..8778.83 rows=3000 width=32) (actual time=1087.964..1864.059 rows=3000000 loops=1) Recheck Cond: ('(3000000,3000000),(0,0)'::box @> tochka) Heap Blocks: exact=27025 Buffers: shared read=54287 -> Bitmap Index Scan on test_covergist_tochka_idx (cost=0.00..134.91 rows=3000 width=0) (actual time=1084.949..1084.949 rows=3000000 loops=1) Index Cond: (tochka <@ '(3000000,3000000),(0,0)'::box) Buffers: shared read=27262 Planning Time: 0.102 ms Execution Time: 2029.501 ms
(9 rows)
Мы попросили EXPLAIN показать буферы. Это пригодится. Сейчас время исполнения запроса больше 2 секунд, видно, что Buffers: shared read=54287. В другой ситуации мы могли бы увидеть смесь shared read и shared hit — то есть некоторые буферы читаются с диска (или из кэша ОС), а некоторые из буферного кэша. Мы знаем примерный размер таблицы и индексов, поэтому обезопасим себя, задав shared buffers так, чтобы всё уместилось — перезапустим Postgres с опцией
-o "-c shared_buffers=1GB"
Теперь:
EXPLAIN (ANALYZE, buffers) SELECT tochka, name FROM test_covergist WHERE box('0,0','3000000,3000000') @> tochka; QUERY PLAN ------------------------------------------------------------------------------- Bitmap Heap Scan on test_covergist (cost=135.66..8778.83 rows=3000 width=32) (actual time=231.032..613.326 rows=3000000 loops=1) Recheck Cond: ('(3000000,3000000),(0,0)'::box @> tochka) Heap Blocks: exact=27025 Buffers: shared hit=54248 -> Bitmap Index Scan on test_covergist_tochka_idx (cost=0.00..134.91 rows=3000 width=0) (actual time=228.068..228.068 rows=3000000 loops=1) Index Cond: (tochka <@ '(3000000,3000000),(0,0)'::box) Buffers: shared hit=27223 Planning Time: 0.070 ms Execution Time: 755.915 ms
(9 rows)
То есть shared read стали shared hit, а время сократилось раза в три.
Спойлер: это число не изменится при любой селективности. Еще важная деталь в EXPLAIN: возвращается 3 млн точек, а прогноз возвращаемого числа записей 3 тыс. И план не поменяется: при любом размере прямоугольника будет Bitmap Index Scan on test_covergist_tochka_idx. Оптимизатор не умеет оценивать кардинальность при работе с типами box или point.
Приведем еще два замера с числом выдаваемых записей, различающихся на порядки:
EXPLAIN (ANALYZE, buffers) SELECT tochka, name FROM test_covergist WHERE box('0,0','300000,300000') @> tochka; QUERY PLAN --------------------------------------------------------------------------------------- Bitmap Heap Scan on test_covergist (cost=135.66..8778.83 rows=3000 width=32) (actual time=27.889..134.054 rows=269882 loops=1) Recheck Cond: ('(300000,300000),(0,0)'::box @> tochka) Heap Blocks: exact=27024 Buffers: shared hit=29534 -> Bitmap Index Scan on test_covergist_tochka_idx (cost=0.00..134.91 rows=3000 width=0) (actual time=24.847..24.847 rows=269882 loops=1) Index Cond: (tochka <@ '(300000,300000),(0,0)'::box) Buffers: shared hit=2510 Planning Time: 0.074 ms Execution Time: 151.269 ms
(9 rows)
Возвращается в 10 с лишним раз меньше записей (actual… rows=269882), время уменьшилось примерно в 5 раз.
EXPLAIN (ANALYZE, buffers) SELECT tochka, name FROM test_covergist WHERE box('0,0','30000,30000') @> tochka; QUERY PLAN ---------------------------------------------------------------------------------------------- Bitmap Heap Scan on test_covergist (cost=135.66..8778.83 rows=3000 width=32) (actual time=1.882..16.095 rows=2780 loops=1) Recheck Cond: ('(30000,30000),(0,0)'::box @> tochka) Heap Blocks: exact=2624 Buffers: shared hit=2655 -> Bitmap Index Scan on test_covergist_tochka_idx (cost=0.00..134.91 rows=3000 width=0) (actual time=1.035..1.035 rows=2780 loops=1) Index Cond: (tochka <@ '(30000,30000),(0,0)'::box) Buffers: shared hit=31 Planning Time: 0.154 ms Execution Time: 16.702 ms
(9 rows)
Содержимое квадрата 30К × 30К (2780) считается всего за 16 мс. А когда записей десятки, извлекаются они уже за доли мс, а такие измерения не очень надежны.
Наконец, измеряем то же самое с инклюзивным индексом:
CREATE INDEX on test_covergist USING gist(tochka) INCLUDE(name);
Размер 316 MB.
EXPLAIN (ANALYZE, buffers) SELECT tochka, name FROM test_covergist WHERE box('0,0','3000000,3000000') @> tochka; QUERY PLAN --------------------------------------------------------------------------------------- Index Only Scan using test_covergist_tochka_name_idx on test_covergist (cost=0.41..216.91 rows=3000 width=32) (actual time=0.160..568.707 rows=3000000 loops=1) Index Cond: (tochka <@ '(3000000,3000000),(0,0)'::box) Heap Fetches: 0 Buffers: shared hit=40492 Planning Time: 0.090 ms Execution Time: 709.837 ms
(6 rows)
Время практически то же самое, что и с обычными индексом, хотя и Index Only Scan.
Но:
EXPLAIN (ANALYZE, buffers) SELECT tochka, name FROM test_covergist WHERE box('0,0','300000,300000') @> tochka; QUERY PLAN -------------------------------------------------------------------------------------------- Index Only Scan using test_covergist_tochka_name_idx on test_covergist (cost=0.41..216.91 rows=3000 width=32) (actual time=0.083..53.277 rows=269882 loops=1) Index Cond: (tochka <@ '(300000,300000),(0,0)'::box) Heap Fetches: 0 Buffers: shared hit=3735 Planning Time: 0.077 ms Execution Time: 66.162 ms
(6 rows)
А была 151 мс. И, соответственно:
EXPLAIN (ANALYZE, buffers) SELECT tochka, name FROM test_covergist WHERE box('0,0','300000,300000') @> tochka; QUERY PLAN -------------------------------------------------------------------------------------------- Index Only Scan using test_covergist_tochka_name_idx on test_covergist (cost=0.41..216.91 rows=3000 width=32) (actual time=0.043..0.639 rows=2780 loops=1) Index Cond: (tochka <@ '(30000,30000),(0,0)'::box) Heap Fetches: 0 Buffers: shared hit=52 Planning Time: 0.053 ms Execution Time: 0.791 ms
(6 rows)
Это уже доли мс для тех же 2780 записей-точек.
Буферы как ружья
Объяснение можно искать и найти в не стрелявшем пока, но висевшем на стене ружье: количестве прочитанных блоков. В случае инклюзивного индекса читаются только блоки самого индекса (Heap Fetches: 0). В трех случаях это были цифры 40492, 3735 и 52. А вот когда используется обычный индекс, то прочитанные блоки состоят из суммы прочитанных в индексе Bitmap Heap Scan (54248 при 3 млн. записей) и тех, что пришлось прочитать из heap (27223), так как из обычного индекса извлечь поле name нельзя. 54248+27223=81471. В эксклюзивном было 40492. Для двух других случаев: 29534+2510=31044 и 2655+31=2686. В случае обычного индекса читается все равно больше блоков, но с улучшением селективности число прочитанных блоков начинает различаться на порядки, а не в 2 раза за счет того, что число необходимых блоков из хипа падает медленней, чем чтение блоков индекса.
На всякий случай повторим те же действия, сгенерив таблицу с 300 тыс, а не с 3 млн записей: Но, может быть, дело вовсе не в селективности, а просто в размере таблицы?
CREATE TABLE test_covergist_small(id serial, tochka point, name text);
INSERT INTO test_covergist_small(tochka, name) SELECT point(trunc(1000000*random()), trunc(1000000*random())), 'point no.' || g.x FROM generate_series(1,300000) AS g(x);
CREATE INDEX ON test_covergist_small USING gist(tochka);
EXPLAIN (ANALYZE, buffers) SELECT tochka, name FROM test_covergist_small WHERE box('0,0','3000000,3000000') @> tochka; QUERY PLAN ---------------------------------------------------------------------------- Bitmap Heap Scan on test_covergist_small (cost=14.61..867.19 rows=300 width=31) (actual time=36.115..130.435 rows=300000 loops=1) Recheck Cond: ('(3000000,3000000),(0,0)'::box @> tochka) Heap Blocks: exact=2500 Buffers: shared hit=5225 -> Bitmap Index Scan on test_covergist_small_tochka_idx (cost=0.00..14.53 rows=300 width=0) (actual time=35.894..35.895 rows=300000 loops=1) Index Cond: (tochka <@ '(3000000,3000000),(0,0)'::box) Buffers: shared hit=2725 Planning Time: 0.060 ms Execution Time: 158.580
(9 rows)
Дальше повторим то же для инклюзивного индекса. Вот результаты:
Дальше, как и в случае с 3 млн, всё встало на свои места. В случае 100% охвата точек запрос выполнялся даже чуть медленней, чем с обычным индексом. То есть важна именно селективность.
Вывод тот же: во многих ситуациях такие индексы заметно ускоряют запросы. В нашей компании тестировали инклюзивные индексы GiST на реальных данных — наборе с несколькими миллионами прямоугольников на карте Москвы. Но проиллюстрировать картинками и цифрами тестов статью не получится: эти данные не лежат в открытом доступе.
Вместо заключения
Вернемся на минутку к случайным прямоугольникам. Попробуем проделать то же с spgist. Вспомнить или узнать, что это, понять отличия SP-GiST от GiST можно, прочитав статью Индексы в PostgreSQL — 6. Создадим инклюзивный индекс:
CREATE INDEX ON boxes USING spgist(thebox) INCLUDE(name);
ERROR: access method "spgist" does not support included columns
Увы нам, для SP-GiST инклюзивные индексы пока не реализованы.
Значит есть пространство для совершенствования!
