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..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)

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

=# 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)

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

=# 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)

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

=# 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)

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

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

Класс операторов для индексов Блума требует наличия только хеш-функции для индексируемого типа данных и оператора равенства для поиска. Этот пример демонстрирует определение класса операторов для типа данных 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-2024