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

примечание

Эта страница переведена при помощи нейросети GigaChat.

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

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

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

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

Параметры

Индекс принимает следующие параметры в своем предложении 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, поскольку они имеют значения по умолчанию.

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

=# 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..2137.14 rows=3 width=24) (actual time=16.971..16.971 rows=0 loops=1)
   Filter: ((i2 = 898732) AND (i5 = 123451))
   Rows Removed by Filter: 100000
 Planning Time: 0.346 ms
 Execution Time: 16.988 ms
(5 rows)

Даже с определенным индексом B-дерева результат все равно будет последовательным сканированием:

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

Наличие индекса bloom, определенного для таблицы, лучше, чем B-дерево при обработке этого типа поиска:

=# 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
----------------
 1584 kB
(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=0.388..0.388 rows=0 loops=1)
   Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
   Rows Removed by Index Recheck: 29
   Heap Blocks: exact=28
   ->  Bitmap Index Scan on bloomidx  (cost=0.00..1792.00 rows=2 width=0) (actual time=0.356..0.356 rows=29 loops=1)
         Index Cond: ((i2 = 898732) AND (i5 = 123451))
 Planning Time: 0.099 ms
 Execution Time: 0.408 ms
(8 rows)

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

=# 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=24.34..32.03 rows=2 width=24) (actual time=0.028..0.029 rows=0 loops=1)
   Recheck Cond: ((i5 = 123451) AND (i2 = 898732))
   ->  BitmapAnd  (cost=24.34..24.34 rows=2 width=0) (actual time=0.027..0.027 rows=0 loops=1)
         ->  Bitmap Index Scan on btreeidx5  (cost=0.00..12.04 rows=500 width=0) (actual time=0.026..0.026 rows=0 loops=1)
               Index Cond: (i5 = 123451)
         ->  Bitmap Index Scan on btreeidx2  (cost=0.00..12.04 rows=500 width=0) (never executed)
               Index Cond: (i2 = 898732)
 Planning Time: 0.491 ms
 Execution Time: 0.055 ms
(9 rows)

Хотя этот запрос выполняется намного быстрее, чем любой из одиночных индексов, выходит, что «платим» за это увеличением размера индекса. Каждый из одностолбцовых индексов B-дерева занимает 2 МБ, поэтому общее необходимое пространство составляет 12 МБ, что в восемь раз превышает объем пространства, используемого индексом bloom.

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

Класс оператора для индексов bloom требует только хеш-функцию для индексируемого типа данных и оператор равенства для поиска. В этом примере показано определение класса операторов для типа данных 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.

Параметры​

Примеры​

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

Ограничения​

Параметры

Примеры

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

Ограничения