Индексы в PostgreSQL — 10


В прошлых статьях мы рассмотрели механизм индексирования PostgreSQL и интерфейс методов доступа, а также хеш-индексы, B-деревья, GiST, SP-GiST, GIN, RUM и BRIN. Нам осталось посмотреть на индексы Блума.

Bloom

Общая идея


Классический фильтр Блума — структура данных, позволяющая быстро проверить принадлежность элемента множеству. Фильтр очень компактен, но допускает ложные срабатывания: он имеет право ошибиться и счесть элемент принадлежащим множеству (false positive), но не имеет права сказать, что элемента нет в множестве, если на самом деле он там присутствует (false negative).

Фильтр представляет собой битовый массив (называемый также сигнатурой) длиной m бит, изначально заполненный нулями. Выбираются k различных хеш-функций, которые отображают любой элемент множества в k битов сигнатуры. Чтобы добавить элемент в множество, нужно установить в сигнатуре каждый из этих битов в единицу. Следовательно, если все соответствующие элементу биты установлены в единицу — элемент может присутствовать в множестве; если хотя бы один бит равен нулю — элемент точно отсутствует.

В случае индекса СУБД мы фактически имеем N отдельных фильтров, построенных для каждой индексной строки. Как правило, в индекс включаются несколько полей; значения этих полей и составляют множество элементов для каждой из строк.

Благодаря выбору размера сигнатуры m, можно находить компромисс между объемом индекса и вероятностью ложного срабатывания. Область применения Блум-индекса — большие, достаточно «широкие» таблицы, запросы к которым могут использовать фильтрацию по любым из полей. Этот метод доступа, как и BRIN, можно рассматривать как ускоритель последовательного сканирования: все найденные индексом совпадения необходимо перепроверять по таблице, но есть шанс вовсе не рассматривать значительную часть строк.

Устройство


Мы уже говорили о сигнатурных деревьях в контексте метода доступа GiST. В отличие от этих деревьев, Блум-индекс представляет собой плоскую структуру. Он состоит из метастраницы, за которой следуют обычные страницы с индексными строками. Каждая индексная строка содержит сигнатуру и ссылку на табличную строку (TID), как схематически показано на рисунке.

tlv3xpdlc4iw25iuma6yurx8wto.png

Создание и выбор значений параметров


При создании Блум-индекса в параметрах хранения указывается общий размер сигнатуры (length) и число устанавливаемых битов отдельно для каждого поля, включенного в индекс (col1—col32):

create index on ... using bloom(...) with (length=..., col1=..., col2=..., ...);

Способ указания числа битов выглядит странно: эти числа должны быть параметром не индекса, а класса операторов. Просто в настоящее время классы операторов нельзя параметризовать, хотя работа над этим ведется.

Как выбрать подходящие значения? Теория говорит о том, что если задаться вероятностью p ложного срабатывания фильтра, то оптимальное число бит сигнатуры можно оценить как
m = −n log2(p) / ln (2), где n — число полей в индексе, а число устанавливаемых бит k = −log2(p).

Внутри индекса сигнатура хранится как массив двубайтовых целых чисел, так что значение m можно смело округлять сверху до 16.

Выбирая вероятность p, следует учитывать размер индекса, который будет равен примерно
(m/8 + 6)N, где N — число строк в таблице, а 6 — размер указателя TID в байтах.

Несколько моментов:

  • Вероятность ложного срабатывания p относится к одному фильтру; при сканировании таблицы мы ожидаем получить Np ложных срабатываний (для запроса, который возвращает мало строк, конечно). Например, для таблицы в миллион строк и вероятности 0,01 в среднем можно ожидать в плане запроса «Rows Removed by Index Recheck: 10000».
  • Фильтр Блума — вероятностная структура. Говорить о конкретных числах имеет смысл, только усредняя достаточно много значений, а в каждом конкретном случае можно получить все, что угодно.
  • Приведенные выше оценки основаны на идеализированной математической модели и ряде допущений. На практике же результат скорее всего получается хуже. Так что к формулам стоит относиться спокойно: это просто способ выбрать начальные значения для дальнейших экспериментов.
  • Метод доступа позволяет выбрать число устанавливаемых бит отдельно для каждого поля. Есть разумное предположение, что на самом деле оптимальное число зависит от распределения значений в столбце. Если хочется заморочиться, можно посмотреть, например, эту статью (буду признателен за ссылки на другие исследования). Но сначала перечитайте предыдущий пункт.


Обновление


При вставке в таблицу новой строки формируется сигнатура: для значений всех индексированных полей устанавливаются в единицу все соответствующие им биты. По классике необходимо иметь k различных хеш-функций; на практике же обходятся генератором псевдослучайных чисел, порождающий элемент (seed) для которого выбирается каждый раз с помощью единственной хеш-функции.

Обычный фильтр Блума не поддерживает удаления элементов, но для Блум-индекса этого и не требуется: при удалении строки из таблицы удаляется вся сигнатура целиком вместе со строкой индекса.

Изменение, как обычно, состоит из удаления старой версии строки и вставке новой (при этом сигнатура вычисляется заново).

Сканирование


Поскольку единственное, что умеет фильтр Блума — это проверять принадлежность элемента множеству, то и единственная поддерживаемая Блум-индексом операция — проверка на равенство (как в хеш-индексе).

Как мы говорили, Блум-индекс является плоским, так что при индексном доступе он всегда читается подряд и целиком. В процессе чтения строится битовая карта, которая затем используется для доступа к таблице.

При традиционном индексном доступе предполагается, что потребуется прочитать немного индексных страниц, которые к тому же могут вскоре понадобиться снова; поэтому они помещаются в буферный кэш. Чтение же Блум-индекса — это фактически последовательное сканирование. Чтобы не допустить вытеснение из кэша полезной информации, чтение происходит через небольшое буферное кольцо, точно так же, как и при последовательном сканировании таблиц.

Следует учесть, что чем больше размер Блум-индекса, тем менее привлекательным он будет казаться планировщику — эта зависимость линейна, в отличие от древовидных индексов.

Пример


Таблица


Посмотрим на Блум-индекс на примере большой таблицы flights_bi из прошлой статьи. Напомню, что размер этой таблицы составляет 4 ГБ при примерно 30 миллионах строк. Определение таблицы:

demo=# \d flights_bi
                          Table "bookings.flights_bi"
       Column       |           Type           | Collation | Nullable | Default
--------------------+--------------------------+-----------+----------+---------
 airport_code       | character(3)             |           |          |
 airport_coord      | point                    |           |          |
 airport_utc_offset | interval                 |           |          |
 flight_no          | character(6)             |           |          |
 flight_type        | text                     |           |          |
 scheduled_time     | timestamp with time zone |           |          |
 actual_time        | timestamp with time zone |           |          |
 aircraft_code      | character(3)             |           |          |
 seat_no            | character varying(4)     |           |          |
 fare_conditions    | character varying(10)    |           |          |
 passenger_id       | character varying(20)    |           |          |
 passenger_name     | text                     |           |          |

Начнем с создания расширения — Блум-индекс входит в стандартную поставку начиная с версии 9.6, но недоступен по умолчанию.

demo=# create extension bloom;
CREATE EXTENSION

С помощью BRIN в прошлый раз нам удалось проиндексировать три поля (scheduled_time, actual_time, airport_utc_offset). Блум-индексы не зависят от физического расположения данных, поэтому попробуем включить в индекс почти все поля таблицы. Однако исключим время (scheduled_time и actual_time) — методом поддерживается только сравнение на равенство, но запрос по точному времени вряд ли кому-то интересен (можно было бы построить индекс по выражению, округлив время до суток, но мы не будем этого делать). Еще нам придется исключить координаты аэропорта (airport_coord) — забегая вперед, тип point не поддерживается.

Чтобы выбрать значения параметров, возьмем вероятность ложного срабатывания 0,01 (понимая, что реально получится больше). Приведенные выше формулы для n = 9 и N = 30 000 000 дают размер сигнатуры 96 бит и предлагают устанавливать 7 бит на элемент. Расчетный размер индекса — 515 МБ (примерно восьмая часть таблицы).

(При минимальном размере сигнатуры в 16 бит формулы обещают в два раза меньший индекс, но позволяют надеяться лишь на вероятность 0,5, что совсем плохо.)

Классы операторов


Итак, пробуем создать индекс.

demo=# create index flights_bi_bloom on flights_bi
using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name)
with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7);
ERROR:  data type character has no default operator class for access method "bloom"
HINT:  You must specify an operator class for the index or define a default operator class for the data type.

Печаль: в расширении нам дают всего лишь два класса операторов:

demo=# select opcname, opcintype::regtype
from pg_opclass
where opcmethod = (select oid from pg_am where amname = 'bloom')
order by opcintype::regtype::text;
 opcname  | opcintype
----------+-----------
 int4_ops | integer
 text_ops | text
(2 rows)

К счастью, не составляет труда создать аналогичные классы и для других типов данных. В класс операторов для метода bloom должен входить ровно один оператор — равенство — и ровно одна вспомогательная функция — хеширование. Самый простой способ найти нужные операторы и функции для произвольного типа — заглянуть в системный каталог на классы операторов метода hash:

demo=# select distinct
       opc.opcintype::regtype::text,
       amop.amopopr::regoperator,
       ampr.amproc
  from pg_am am, pg_opclass opc, pg_amop amop, pg_amproc ampr
 where am.amname = 'hash'
   and opc.opcmethod = am.oid
   and amop.amopfamily = opc.opcfamily
   and amop.amoplefttype = opc.opcintype
   and amop.amoprighttype = opc.opcintype
   and ampr.amprocfamily = opc.opcfamily
   and ampr.amproclefttype = opc.opcintype
order by opc.opcintype::regtype::text;
 opcintype |       amopopr        |    amproc    
-----------+----------------------+--------------
 abstime   | =(abstime,abstime)   | hashint4
 aclitem   | =(aclitem,aclitem)   | hash_aclitem
 anyarray  | =(anyarray,anyarray) | hash_array
 anyenum   | =(anyenum,anyenum)   | hashenum
 anyrange  | =(anyrange,anyrange) | hash_range
 ...

Имея эту информацию, создадим два недостающих класса:

demo=# CREATE OPERATOR CLASS character_ops
DEFAULT FOR TYPE character USING bloom AS
  OPERATOR  1  =(character,character),
  FUNCTION  1  hashbpchar;
CREATE OPERATOR CLASS

demo=# CREATE OPERATOR CLASS interval_ops
DEFAULT FOR TYPE interval USING bloom AS
  OPERATOR  1  =(interval, interval),
  FUNCTION  1  interval_hash;
CREATE OPERATOR CLASS

Для точек (тип point) хеш-функция не определена; именно по этой причине мы не сможем построить Блум-индекс по такому полю (точно так же, как не сможем выполнить хеш-соединение по полям этого типа).

Пробуем снова:

demo=# create index flights_bi_bloom on flights_bi
using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name)
with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7);
CREATE INDEX

Размер индекса составляет 526 МБ, что несколько больше рассчетного — из-за того, что в формуле мы не учитываем накладных расходов на служебную информацию в каждом блоке.

demo=# select pg_size_pretty(pg_total_relation_size('flights_bi_bloom'));
 pg_size_pretty
----------------
 526 MB
(1 row)

Запросы


Теперь мы можем выполнять поиск по самым разным критериям, и он будет поддержан индексом.

Как мы говорили, фильтр Блума — вероятностная структура, поэтому эффективность в каждом конкретном случае может получиться разная. Например, посмотрим записи, относящиеся к двум пассажирам, Мирославу Сидорову:

demo=# explain(costs off,analyze)
select * from flights_bi where passenger_name='MIROSLAV SIDOROV';
                                            QUERY PLAN
--------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on flights_bi (actual time=2639.010..3010.692 rows=2 loops=1)
   Recheck Cond: (passenger_name = 'MIROSLAV SIDOROV'::text)
   Rows Removed by Index Recheck: 38562
   Heap Blocks: exact=21726
   ->  Bitmap Index Scan on flights_bi_bloom (actual time=1065.191..1065.191 rows=38564 loops=1)
         Index Cond: (passenger_name = 'MIROSLAV SIDOROV'::text)
 Planning time: 0.109 ms
 Execution time: 3010.736 ms

и Марфе Соловьевой:

demo=# explain(costs off,analyze)
select * from flights_bi where passenger_name='MARFA SOLOVEVA';
                                            QUERY PLAN
---------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on flights_bi (actual time=9980.884..10142.684 rows=2 loops=1)
   Recheck Cond: (passenger_name = 'MARFA SOLOVEVA'::text)
   Rows Removed by Index Recheck: 3950168
   Heap Blocks: exact=45757 lossy=67332
   ->  Bitmap Index Scan on flights_bi_bloom (actual time=1037.588..1037.588 rows=212972 loops=1)
         Index Cond: (passenger_name = 'MARFA SOLOVEVA'::text)
 Planning time: 0.157 ms
 Execution time: 10142.730 ms

В одном случае фильтр допустил всего 40 тысяч ложных срабатываний, в другом — аж 4 миллиона. Соответственно отличается и время выполнения запросов.

А вот результаты для поиска тех же самых строк, используя не имя, а номер документа. Мирослав:

demo=# explain(costs off,analyze)
demo-# select * from flights_bi where passenger_id='5864 006033';
                                           QUERY PLAN
-------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on flights_bi (actual time=13747.305..16907.387 rows=2 loops=1)
   Recheck Cond: ((passenger_id)::text = '5864 006033'::text)
   Rows Removed by Index Recheck: 9620258
   Heap Blocks: exact=50510 lossy=165722
   ->  Bitmap Index Scan on flights_bi_bloom (actual time=937.202..937.202 rows=426474 loops=1)
         Index Cond: ((passenger_id)::text = '5864 006033'::text)
 Planning time: 0.110 ms
 Execution time: 16907.423 ms

И Марфа:

demo=# explain(costs off,analyze)
select * from flights_bi where passenger_id='2461 559238';
                                            QUERY PLAN
--------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on flights_bi (actual time=3881.615..3934.481 rows=2 loops=1)
   Recheck Cond: ((passenger_id)::text = '2461 559238'::text)
   Rows Removed by Index Recheck: 30669
   Heap Blocks: exact=27513
   ->  Bitmap Index Scan on flights_bi_bloom (actual time=1084.391..1084.391 rows=30671 loops=1)
         Index Cond: ((passenger_id)::text = '2461 559238'::text)
 Planning time: 0.120 ms
 Execution time: 3934.517 ms

Эффективность снова сильно отличается, на этот раз больше повезло Марфе.

Заметим, что поиск одновременно по двум полям будет выполняться значительно эффективнее, поскольку вероятность ложного срабатывания p превращается в p2:

demo=# explain(costs off,analyze)
select * from flights_bi
where passenger_name='MIROSLAV SIDOROV'
  and passenger_id='5864 006033';
                                                     QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on flights_bi (actual time=872.593..877.915 rows=2 loops=1)
   Recheck Cond: (((passenger_id)::text = '5864 006033'::text)
               AND (passenger_name = 'MIROSLAV SIDOROV'::text))
   Rows Removed by Index Recheck: 357
   Heap Blocks: exact=356
   ->  Bitmap Index Scan on flights_bi_bloom (actual time=832.041..832.041 rows=359 loops=1)
         Index Cond: (((passenger_id)::text = '5864 006033'::text)
                   AND (passenger_name = 'MIROSLAV SIDOROV'::text))
 Planning time: 0.524 ms
 Execution time: 877.967 ms

А вот условие с логическим «или» не поддерживается совсем — это ограничение не данного метода доступа, а планировщика. Остается, конечно, вариант прочитать индекс два раза, построить две битовые карты и объединить их, но это скорее всего слишком накладно, чтобы такой план был выбран.

Сравнение с BRIN и Hash


Области применения Блум-индексов и индексов BRIN, очевидно, пересекаются. Это большие таблицы, для которых желательно обеспечить поиск по разным полям, причем точность поиска приносится в жертву компактности.

BRIN-индексы компактнее (скажем, до десятков мегабайт в нашем примере) и могут поддерживать поиск по диапазону, но имеют очень сильное ограничение, связанное с физическим расположением данных в файле. Блум-индексы получаются больше (сотни мегабайт), зато не имеют никаких ограничений, кроме наличия подходящей функции хеширования.

Как и индексы Блума, хеш-индексы поддерживают единственную операцию проверки на равенство. Хеш-индекс обеспечивает недостижимую для Блума точность поиска, но и размер его существенно больше (в нашем примере — гигабайт только по одному полю, а по нескольким полям хеш-индекс создать нельзя).

Свойства


По традиции посмотрим на свойства (запросы приводились ранее).

Свойства метода:

 amname |     name      | pg_indexam_has_property
--------+---------------+-------------------------
 bloom  | can_order     | f
 bloom  | can_unique    | f
 bloom  | can_multi_col | t
 bloom  | can_exclude   | f

Очевидно, метод доступа позволяет строить индексы по нескольким столбцам — Блум-индекс по одному стоблцу вряд ли имеет смысл.

Свойства индекса:

     name      | pg_index_has_property
---------------+-----------------------
 clusterable   | f
 index_scan    | f
 bitmap_scan   | t
 backward_scan | f

Единственно возможный способ сканирования — по битовой карте. Поскольку индекс всегда сканируется целиком, нет смысла реализовывать обычный индексный доступ, при котором TID-ы возвращаются по одному.

        name        | pg_index_column_has_property
--------------------+------------------------------
 asc                | f
 desc               | f
 nulls_first        | f
 nulls_last         | f
 orderable          | f
 distance_orderable | f
 returnable         | f
 search_array       | f
 search_nulls       | f

Здесь все «прочерки», и даже с неопределенными значениями этот метод доступа работать не умеет.

И напоследок


Не исключаю, что эта серия статей продолжится в будущем с появлением новых интересных типов индексов, но сейчас пришло время остановиться.

Хочу выразить благодарность своим коллегам из Postgres Professional (некоторые из которых являются авторами многих рассмотренных методов доступа) за чтение черновиков и высказанные замечания. И, конечно же, я признателен вам за терпение и ценные комментарии. Ваше внимание дало мне силы дойти до этой точки. Спасибо!

© Habrahabr.ru