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

«Покрывающий индекс» не просто еще одна фича, которая может пригодиться. Это вещь сугубо практичная. Без них Index Only Scan может не дать выигрыша. Хотя и покрывающий индекс в разных ситуациях эффективен по-разному.

Речь здесь будет не совсем о покрывающих индексах: строго говоря, в Postgres появились так называемые инклюзивные индексы. Но, по-порядку: покрывающий индекс — это индекс, который содержит все значения столбцов, необходимые запросу; при этом обращение к самой таблице уже не требуется. Почти. О «почти» и других нюансах можно прочитать в статье Егора Рогова, входящей в его индексный сериал из 10 (!) частей. А инклюзивный индекс создается специально для поиска по типичным запросам: к поисковому индексу добавляются значения полей, по которым искать нельзя, они нужны только для того, чтобы не обращаться лишний раз к таблице. Такие индексы формируются с ключевым словом INCLUDE.

Анастасия Лубенникова (Postgres Professional) доработала метод btree так, чтобы в индекс можно было включать дополнительные столбцы. Этот патч вошел в версию PostgreSQL 11. Но патчи для методов доступа GiST/SP-GiST не успели созреть до выхода этой версии. К 12-й GiST дозрел.

Конструктивное желание иметь инклюзивные индексы для GiST возникло давно: пробный патч Андрей Бородин предложил сообществу еще в середине апреля 2018-го года. Он и проделал всю основную, очень непростую работу.

В начале августа 2019-го Александр Коротков добавил косметические улучшения и закоммитил патч.

Для демонстрации и некоторого исследования мы сгенерим набор из 3 млн. прямоугольников. Заодно немного слов о типе box, так как не все манипуляции с ним интуитивны.

Тип box — то есть прямоугольник — в Postgres давно, он определяется 2-мя точками (геометрический тип point) — противоположными вершинами прямоугольника (то есть прямоугольник не может быть косым, заваленным набок). В документации читаем: «значения типа box записываются в одной из следующих форм:

( ( 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 тыс. Спойлер: это число не изменится при любой селективности. Оптимизатор не умеет оценивать кардинальность при работе с типами box или point. И план не поменяется: при любом размере прямоугольника будет Bitmap Index Scan on test_covergist_tochka_idx.

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

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)

Дальше повторим то же для инклюзивного индекса. Вот результаты:



В случае 100% охвата точек запрос выполнялся даже чуть медленней, чем с обычным индексом. Дальше, как и в случае с 3 млн, всё встало на свои места. То есть важна именно селективность.

В нашей компании тестировали инклюзивные индексы 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 инклюзивные индексы пока не реализованы.
Значит есть пространство для совершенствования!