bloom — индексный метод доступа, основанный на фильтрах Блума

Модуль bloom предоставляет индексный метод доступа, основанный на фильтрах Блума.

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

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

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

Параметры

Индекс bloom принимает в своем предложении WITH следующие параметры:

length
Длина каждой сигнатуры (записи индекса) в битах, округленная вверх до ближайшего числа, кратного 16. Значение по умолчанию — 80 бит, а максимальное — 4096.

col1 — col32
Количество битов, генерируемых для каждого столбца индекса. В имени каждого параметра отражается номер столбца индекса, которым этот параметр управляет. Значение по умолчанию — 2 бита, а максимальное — 4095. Параметры для фактически неиспользуемых столбцов индекса игнорируются.

Примеры

Это пример создания индекса bloom:

CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
       WITH (length=80, col1=2, col2=2, col3=4);

Будет создан индекс с длиной сигнатуры 80 бит, в которой атрибуты i1 и i2 отображаются в 2 бита, а атрибут i3 — в 4. Указания length, col1 и col2 можно было бы опустить, поскольку в них задаются значения по умолчанию.

Ниже приводится более полный пример определения и использования индекса Блума, а также его сравнение с равнозначным индексом В-деревом. Индекс Блума значительно меньше индекса В-дерева и при этом может работать быстрее.

=# CREATE TABLE tbloom AS
   SELECT
     (random() * 1000000)::int as i1,
     (random() * 1000000)::int as i2,
     (random() * 1000000)::int as i3,
     (random() * 1000000)::int as i4,
     (random() * 1000000)::int as i5,
     (random() * 1000000)::int as i6
   FROM
  generate_series(1,10000000);
SELECT 10000000

Последовательное сканирование по этой большой таблице занимает много времени:

=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                              QUERY PLAN
-------------------------------------------------------------------​-----------------------------------
 Seq Scan on tbloom  (cost=0.00..213744.00 rows=250 width=24) (actual time=357.059..357.059 rows=0 loops=1)
   Filter: ((i2 = 898732) AND (i5 = 123451))
   Rows Removed by Filter: 10000000
 Planning Time: 0.346 ms
 Execution Time: 357.076 ms
(5 rows)

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

=# CREATE INDEX btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));
 pg_size_pretty
----------------
 386 MB
(1 row)
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                              QUERY PLAN
-------------------------------------------------------------------​-----------------------------------
 Seq Scan on tbloom  (cost=0.00..213744.00 rows=2 width=24) (actual time=351.016..351.017 rows=0 loops=1)
   Filter: ((i2 = 898732) AND (i5 = 123451))
   Rows Removed by Filter: 10000000
 Planning Time: 0.138 ms
 Execution Time: 351.035 ms
(5 rows)

Если определить для таблицы индекс Блума, поиск такого рода осуществляется эффективнее, нежели с индексом В-деревом:

=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('bloomidx'));
 pg_size_pretty
----------------
 153 MB
(1 row)
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                                     QUERY PLAN
-------------------------------------------------------------------​--------------------------------------------------
 Bitmap Heap Scan on tbloom  (cost=1792.00..1799.69 rows=2 width=24) (actual time=22.605..22.606 rows=0 loops=1)
   Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
   Rows Removed by Index Recheck: 2300
   Heap Blocks: exact=2256
   ->  Bitmap Index Scan on bloomidx  (cost=0.00..178436.00 rows=1 width=0) (actual time=20.005..20.005 rows=2300 loops=1)
         Index Cond: ((i2 = 898732) AND (i5 = 123451))
 Planning Time: 0.099 ms
 Execution Time: 22.632 ms
(8 rows)

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

=# CREATE INDEX btreeidx1 ON tbloom (i1);
CREATE INDEX
=# CREATE INDEX btreeidx2 ON tbloom (i2);
CREATE INDEX
=# CREATE INDEX btreeidx3 ON tbloom (i3);
CREATE INDEX
=# CREATE INDEX btreeidx4 ON tbloom (i4);
CREATE INDEX
=# CREATE INDEX btreeidx5 ON tbloom (i5);
CREATE INDEX
=# CREATE INDEX btreeidx6 ON tbloom (i6);
CREATE INDEX
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                                        QUERY PLAN
-------------------------------------------------------------------​--------------------------------------------------------
 Bitmap Heap Scan on tbloom  (cost=9.29..13.30 rows=1 width=24) (actual time=0.032..0.033 rows=0 loops=1)
   Recheck Cond: ((i5 = 123451) AND (i2 = 898732))
   ->  BitmapAnd  (cost=9.29..9.29 rows=1 width=0) (actual time=0.047..0.047 rows=0 loops=1)
         ->  Bitmap Index Scan on btreeidx5  (cost=0.00..4.52 rows=11 width=0) (actual time=0.026..0.026 rows=7 loops=1)
               Index Cond: (i5 = 123451)
         ->  Bitmap Index Scan on btreeidx2  (cost=0.00..4.52 rows=11 width=0) (actual time=0.007..0.007 rows=8 loops=1)
               Index Cond: (i2 = 898732)
 Planning Time: 0.264 ms
 Execution Time: 0.047 ms
(9 rows)

Хотя этот запрос выполняется быстрее, чем с каким-либо одиночным индексом, мы платим за это увеличением размера индекса. Каждый индекс В-дерево занимает 88,5 МБ, так что общий объем индексов составляет 531 МБ, что более чем в три раза больше объема индекса Блума.

Интерфейс класса операторов

Класс операторов для индексов Блума требует наличия только хеш-функции для индексируемого типа данных и оператора равенства для поиска. Этот пример демонстрирует определение класса операторов для типа данных text:

CREATE OPERATOR CLASS text_ops
DEFAULT FOR TYPE text USING bloom AS
    OPERATOR    1   =(text, text),
    FUNCTION    1   hashtext(text);

Ограничения

  • В этот модуль включены только классы операторов для int4 и text.

  • При поиске поддерживается только оператор =. Но в будущем возможно добавление поддержки для массивов с операциями объединения и пересечения.

  • Метод доступа bloom не поддерживает уникальные индексы (UNIQUE).

  • Метод доступа bloom не поддерживает поиск значений NULL.

Авторы

Федор Сигаев (teodor@postgrespro.ru), Postgres Professional, Москва, Россия

Александр Коротков (a.korotkov@postgrespro.ru), Postgres Professional, Москва, Россия

Олег Бартунов (obartunov@postgrespro.ru), Postgres Professional, Москва, Россия

Copyright © KVANTOM LLC, 2019-2025