Использование bloom

Евгения Кузина

Обзор

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

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

Ложных отрицательных срабатываний при использовании bloom-индекса не происходит, таким образом, с помощью него можно эффективно исключить наличие элемента в таблице.

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

Ограничения

Bloom-индексы имеют следующие ограничения:

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

  • Для поиска поддерживается исключительно оператор равенства (=).

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

  • Значения NULL игнорируются при создании индекса bloom.

Установка

Пакет, требуемый для установки bloom, поставляется с ADP. Чтобы использовать bloom, необходимо только выполнить команду CREATE EXTENSION в той базе данных, в которую вы хотите установить расширение:

CREATE EXTENSION bloom;
ПРИМЕЧАНИЕ
Если расширение bloom создано в базе данных template1, используемой в качестве темплейта по умолчанию, во всех вновь создаваемых базах данных будет установлено это расширение.

ADP использует версию 1.0 расширения bloom. Чтобы это проверить, можно выполнить следующий запрос:

SELECT extversion FROM pg_extension
    WHERE extname = 'bloom';
 extversion
1.0

После создания расширения bloom его функции становятся доступны в текущей базе данных.

Создание bloom-индекса

Чтобы создать bloom-индекс, воспользуйтесь командой CREATE INDEX. В выражении USING должен быть указан метод — bloom, а также могут быть установлены следующие параметры в выражении WITH:

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

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

CREATE INDEX <имя_индекса> ON <имя_таблицы> USING bloom (<столбец1>, <столбец2>...<столбецN>)
       WITH (length=<значение_length>, col1=<значение_col1>, col2=<значение_col2>... colN=<значение_colN>);

Тестирование bloom-индекса

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

Для тестирования индексов создайте таблицу и заполните ее данными:

CREATE TABLE table_bloom (field1 int,
                          field2 int,
                          field3 int,
                          field4 text,
                          field5 int);

INSERT INTO table_bloom SELECT (random() * 1000000)::int,
                               (random() * 1000000)::int,
                               (random() * 1000000)::int,
                               md5(i::text),
                               floor(random()* 10010)
                               FROM generate_series(1,100*1e6) i;

Вызовите функцию pg_relation_size, чтобы определить размер таблицы:

SELECT pg_size_pretty(pg_relation_size('table_bloom'));
 pg_size_pretty
----------------
 8054 MB

Создайте индекс B-дерево:

CREATE INDEX idx_btree ON table_bloom (field1, field2, field3, field4, field5);

Проверьте размер индекса:

SELECT pg_size_pretty(pg_relation_size('idx_btree'));
 pg_size_pretty
----------------
 7327 MB

Отключите последовательное сканирование, чтобы гарантировать использование индексов планировщиком запросов:

SET enable_seqscan = off;

Соберите статистику для планировщика запросов с помощью команды ANALYZE:

 ANALYZE table_bloom;

Для оценки производительности используйте команду EXPLAIN ANALYZE. Выполните два запроса, чтобы получить более объективные данные:

EXPLAIN ANALYZE SELECT * FROM table_bloom WHERE field3 = 665955 and field5 = 9044;
                                                            QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using idx_btree on table_bloom  (cost=0.57..4751544.58 rows=1 width=49) (actual time=5827.032..5827.033 rows=0 loops=1)
   Index Cond: ((field3 = 665955) AND (field5 = 9044))
   Heap Fetches: 0
 Planning Time: 0.066 ms
 JIT:
   Functions: 1
   Options: Inlining true, Optimization true, Expressions true, Deforming true
   Timing: Generation 0.121 ms, Inlining 0.000 ms, Optimization 0.000 ms, Emission 0.000 ms, Total 0.121 ms
 Execution Time: 5827.240 ms
EXPLAIN ANALYZE SELECT * FROM table_bloom WHERE field2 = 293202 and field3 = 12624;
                                                           QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using idx_btree on table_bloom  (cost=0.57..4751544.74 rows=1 width=49) (actual time=5790.038..5790.040 rows=0 loops=1)
   Index Cond: ((field2 = 293202) AND (field3 = 12624))
   Heap Fetches: 0
 Planning Time: 0.068 ms
 JIT:
   Functions: 1
   Options: Inlining true, Optimization true, Expressions true, Deforming true
   Timing: Generation 0.136 ms, Inlining 0.000 ms, Optimization 0.000 ms, Emission 0.000 ms, Total 0.136 ms
 Execution Time: 5790.268 ms

Время выполнения запросов 5827.240 мс и 5790.268 мс соответственно, размер индекса B-дерево 7327 MB.

Создайте bloom-индекс для тех же столбцов:

CREATE INDEX idx_bloom ON table_bloom USING bloom (field1, field2, field3, field4, field5)
            WITH(length=64, col1=4, col2=4, col3=4, col4=4, col5=4);

Определите размер индекса:

SELECT pg_size_pretty(pg_relation_size('idx_bloom'));
 pg_size_pretty
----------------
 1342 MB

Выполните те же запросы:

EXPLAIN ANALYZE SELECT * FROM table_bloom WHERE field3 = 665955 and field5 = 9044;
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on table_bloom  (cost=1687292.00..1687296.02 rows=1 width=49) (actual time=763.776..763.778 rows=0 loops=1)
   Recheck Cond: ((field3 = 665955) AND (field5 = 9044))
   Rows Removed by Index Recheck: 861
   Heap Blocks: exact=861
   ->  Bitmap Index Scan on idx_bloom  (cost=0.00..1687292.00 rows=1 width=0) (actual time=732.889..732.890 rows=861 loops=1)
         Index Cond: ((field3 = 665955) AND (field5 = 9044))
 Planning Time: 0.080 ms
 JIT:
   Functions: 2
   Options: Inlining true, Optimization true, Expressions true, Deforming true
   Timing: Generation 0.267 ms, Inlining 2.481 ms, Optimization 17.609 ms, Emission 10.009 ms, Total 30.366 ms
 Execution Time: 1839.632 ms
EXPLAIN ANALYZE SELECT * FROM table_bloom WHERE field2 = 293202 and field3 = 12624;
                                                           QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on table_bloom  (cost=1687292.00..1687296.02 rows=1 width=49) (actual time=1144.026..1144.028 rows=0 loops=1)
   Recheck Cond: ((field2 = 293202) AND (field3 = 12624))
   Rows Removed by Index Recheck: 930
   Heap Blocks: exact=930
   ->  Bitmap Index Scan on idx_bloom  (cost=0.00..1687292.00 rows=1 width=0) (actual time=1044.350..1044.351 rows=930 loops=1)
         Index Cond: ((field2 = 293202) AND (field3 = 12624))
 Planning Time: 0.078 ms
 JIT:
   Functions: 2
   Options: Inlining true, Optimization true, Expressions true, Deforming true
   Timing: Generation 0.229 ms, Inlining 2.192 ms, Optimization 13.375 ms, Emission 8.267 ms, Total 24.063 ms
 Execution Time: 1144.350 ms

Время выполнения запросов 1839.632 мс и 1144.350 мс соответственно, размер bloom-индекса 1342 MB.

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

Нашли ошибку? Выделите текст и нажмите Ctrl+Enter чтобы сообщить о ней