Индексы в PostgreSQL — 1019.02.2018 12:03

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

Bloom

Общая идея

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

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

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

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

Устройство

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

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

При создании Блум-индекса в параметрах хранения указывается общий размер сигнатуры (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=# 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-индексы компактнее (скажем, до десятков мегабайт в нашем примере) и могут поддерживать поиск по диапазону, но имеют очень сильное ограничение, связанное с физическим расположением данных в файле. Блум-индексы получаются больше (сотни мегабайт), зато не имеют никаких ограничений, кроме наличия подходящей функции хеширования.

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

Свойства

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

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

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

name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | f bitmap_scan | t backward_scan | f
Единственно возможный способ сканирования — по битовой карте. Поскольку индекс всегда сканируется целиком, нет смысла реализовывать обычный индексный доступ, при котором TID-ы возвращаются по одному.

И напоследок

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

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