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

F.7. bloom — метод доступа к индексу с использованием фильтра Блума
F.7. bloom — метод доступа к индексу с использованием фильтра Блума
Назад НаверхПредметный указатель F. Дополнительные поставляемые модули и расширенияНачало Далее

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

F.7.1. Параметры
F.7.2. Примеры
F.7.3. Интерфейс класса операторов
F.7.4. Ограничения
F.7.5. Авторы

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

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

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

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

F.7.1. Параметры #

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

length

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

col1 — col32

Количество бит, генерируемых для каждого столбца индекса. Имя каждого параметра относится к номеру управляемого им столбца индекса. По умолчанию используется 2 бита, а максимальное значение - 4095. Параметры для неиспользуемых столбцов индекса игнорируются.

F.7.2. Примеры #

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

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, так как они имеют значения по умолчанию.

Вот более полный пример определения и использования индекса Блюма, а также сравнение с эквивалентными индексами B-дерева. Индекс Блюма значительно меньше индекса 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..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)

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

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

Иметь индекс Блюма, определенный на таблице, лучше, чем btree, при обработке этого типа поиска: 

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

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

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

Хотя этот запрос выполняется намного быстрее, чем с любым из одиночных индексов, мы платим штраф в размере индекса. Каждый из одно-колоночных btree индексов занимает 88.5 МБ, так что общее необходимое пространство составляет 531 МБ, что более чем в три раза превышает пространство, используемое bloom индексом.

F.7.3. Интерфейс класса операторов #

Класс операторов для индексов Bloom требует только хеш-функцию для типа данных, по которому создается индекс, и оператор равенства для поиска. В этом примере показано определение класса операторов для типа данных text: 

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

F.7.4. Ограничения #

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

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

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

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

F.7.5. Авторы #

Федор Сигаев , Postgres Professional, Москва, Россия

Александр Коротков , Postgres Professional, Москва, Россия.

Олег Бартунов , Postgres Professional, Москва, Россия

Назад Наверх Далее
F.6. basic_archive — пример модуля архивации WAL Начало F.8. btree_gin — GIN классы операторов с поведением B-tree