В рамках 18 релиза СУБД Tantor Postgres мы рассказывали об оптимизациях, которые помогают планировщику сделать более точный выбор между Nested Loop и Hash Join. В следующем релизе у нас планируются оптимизации, которые позволят ускорить выполнение как Nested Loop, так и Hash Join. Сегодня мы расскажем об одном из таких методов - фильтре Блума.

Что такое фильтр Блума в SQL?

Определение фильтра Блума можно найти в любой статье, и все они начинаются примерно одинаково:

Фильтр Блума — это вероятностная структура данных для быстрой проверки принадлежности элемента множеству. Она может дать два ответа: «элемента точно нет» или «элемент возможно есть». Ложноположительные срабатывания возможны, ложноотрицательные — нет.

Обычно на этом месте автор статьи переходит к формуле оптимального числа хеш-функций, а читатель - к следующей вкладке. Поэтому давайте сразу к тому, зачем эта штука вообще нужна в СУБД:

Оптимизация JOIN. Самое частое применение. При hash join строится фильтр Блума по ключам одной таблицы, и им заранее отсеиваются строки другой таблицы, которые заведомо не найдут пару. Это уменьшает объём данных, доходящих до собственно соединения. В PostgreSQL такие фильтры используются, например, для параллельных hash join, в SQL Server они называются bitmap-фильтрами, в Oracle — bloom filter pruning.

Учитывая, что на момент, когда выходит эта статья, я уже оценил эффект от этой фичи в Tantor Postgres, могу сказать, что данное определение работу фильтра отражает прекрасно. Дополним теорию практическим примером (все примеры ниже выполняются на Tantor Postgres 18.4, в ванильном PostgreSQL такой оптимизации нет):

DROP TABLE IF EXISTS orders, active_customers;
 
CREATE TABLE orders (
    order_id    int,
    customer_id int
);
 
-- 10 млн заказов, customer_id из диапазона 1..10_000_000
INSERT INTO orders
SELECT g, (random() * 10000000)::int + 1
FROM generate_series(1, 10000000) g;
 
CREATE TABLE active_customers (customer_id int);
INSERT INTO active_customers
SELECT generate_series(1, 100000);   -- 1% пространства ключей
 
ANALYZE active_customers;
ANALYZE orders;

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

SET max_parallel_workers_per_gather = 0;
SET enable_hashjoin_bloom = off;
 
explain (analyze, verbose, buffers off, costs off)
SELECT o.*
FROM orders o
JOIN active_customers c ON o.customer_id = c.customer_id;

План:

"Hash Join (actual time=17.580..1719.505 rows=100053.00 loops=1)"
"  Hash Cond: (o.customer_id = c.customer_id)"
"  ->  Seq Scan on public.orders o (actual time=0.025..602.263 rows=10000000.00 loops=1)"
"  ->  Hash (actual time=17.334..17.337 rows=100000.00 loops=1)"
"        Buckets: 131072  Batches: 1  Memory Usage: 4540kB"
"        ->  Seq Scan on public.active_customers c (actual time=0.013..7.712 rows=100000.00 loops=1)"

На узел Hash Join приходят две таблицы: в active_customers 100 тыс. записей, а в orders - 10 млн. На соединение хешированием этих двух таблиц приходится большая часть времени выполнения запроса.
Выполним тот же запрос, включив bloom-фильтр (enable_hashjoin_bloom=on):

"Hash Join (actual time=26.034..878.077 rows=100053.00 loops=1)"
"  Hash Cond: (o.customer_id = c.customer_id)"
"  ->  Seq Scan on public.orders o (actual time=0.034..806.095 rows=100286.00 loops=1)"
"        Bloom Filter 1: keys=(o.customer_id) checked=9999999 rejected=9899714 (99.0%)"
"  ->  Hash (actual time=25.537..25.538 rows=100000.00 loops=1)"
"        Buckets: 131072  Batches: 1  Memory Usage: 4540kB"
"        Bloom Filter 1: bits=8388608 hashes=10 memory=1024kB checked=9999999 rejected=9899714"
"        ->  Seq Scan on public.active_customers c (actual time=0.014..12.260 rows=100000.00 loops=1)"

В плане запроса появилась новая секция Bloom Filter, которая говорит нам о том, что он был здесь применен. Разберём по шагам, что же именно сделал bloom-фильтр, и что изменилось после его включения.

Шаг 1. Построение фильтра.

На этапе построения хеш-таблицы (узел Hash) Tantor Postgres дополнительно прогнал все 100 тыс. значений customer_id из active_customers через набор хеш-функций и выставил соответствующие биты в битовом массиве. Параметры фильтра видны прямо в плане:

Bloom Filter 1: bits=8388608 hashes=10 memory=1024kB

То есть массив на 8,4 млн бит (1 МБ памяти), каждое значение отмечается десятью хеш-функциями. Построение стоило нам времени: узел Hash замедлился с 17,3 до 25,5 мс. Это и есть цена фичи - плата за построение.

Шаг 2. Проталкивание условия вниз (pushdown).

Обычно условие соединения o.customer_id = c.customer_id проверяется на узле Hash Join - то есть все 10 млн строк orders должны сначала доехать от Seq Scan до Hash Join, и только там выяснится, что 99% из них не нужны.

Bloom-фильтр позволяет проверить это условие раньше - прямо на уровне сканирования orders. Смотрим план:

-> Seq Scan on public.orders o (actual time=0.034..806.095 rows=100286.00 loops=1)
     Bloom Filter 1: keys=(o.customer_id) checked=9999999 rejected=9899714 (99.0%)

Строка Bloom Filter появилась внутри Seq Scan. Для каждой из 10 млн просканированных строк (checked=9999999) фильтр отвечал на вопрос «а есть ли вообще такой customer_id среди активных клиентов?». В 9 899 714 случаях ответ был «точно нет» (rejected), и строка отбрасывалась сразу на узле сканирования таблицы orders.

Время выполнения узла увеличилось с 602 до 806 мс - это накладные расходы на применение bloom-фильтра.

Шаг 3. Результат.

Из Seq Scan наверх, к Hash Join, вышло не 10 млн строк, а всего 100 286 (rows=100286.00). Именно эти строки и дошли до операции соединения Hash Join.

Откуда взялись лишние 233 строки? Итоговый результат запроса - 100 053 строки, а фильтр пропустил 100 286. Разница в 233 строки - это ложноположительные срабатывания: для них все десять битов случайно оказались выставлены другими значениями, и фильтр сказал «возможно есть». Ошибки это не создает: такие строки просто не найдут пару в хеш-таблице и будут отброшены уже на узле Hash Join. Фильтр Блума не может ошибиться в другую сторону: потерять нужную строку он не способен, поэтому результат запроса остаётся корректным.

Сравним время выполнения всех узлов плана:

Как видим, запрос ускорился вдвое из-за сокращения времени выполнения самой ресурсоемкой операции - Hash Join.

А может ли применение bloom-фильтра сделать хуже? Да, в том случае, если ресурсы затраченные на его построение и применение не будут компенсированы ускорением операции Hash Join. Сэмулируем такой случай:

TRUNCATE active_customers;
INSERT INTO active_customers
SELECT generate_series(1, 9500000);  -- 95% пространства ключей

В данном случае bloom-фильтр должен будет откинуть не 99% строк как в примере выше, а всего лишь 5%, т.к. почти каждый customer_id из orders найдется среди активных клиентов таблицы active_customers.

enable_hashjoin_bloom = off:

"Hash Join (actual time=3686.180..10541.744 rows=9499724.00 loops=1)"
"  Hash Cond: (c.customer_id = o.customer_id)"
"  ->  Seq Scan on public.active_customers c (actual time=0.063..613.167 rows=9500000.00 loops=1)"
"  ->  Hash (actual time=3581.865..3581.872 rows=10000000.00 loops=1)"
"        Buckets: 16777216  Batches: 1  Memory Usage: 521697kB"
"        ->  Seq Scan on public.orders o (actual time=0.053..700.691 rows=10000000.00 loops=1)"

enable_hashjoin_bloom = on:

"Hash Join (actual time=5414.793..12388.729 rows=9499724.00 loops=1)"
"  Hash Cond: (o.customer_id = c.customer_id)"
"  ->  Seq Scan on public.orders o (actual time=0.034..741.536 rows=9995087.00 loops=1)"
"        Bloom Filter 1: keys=(o.customer_id) checked=100989 rejected=4913 (4.9%)"
"  ->  Hash (actual time=5321.682..5321.684 rows=9500000.00 loops=1)"
"        Buckets: 16777216  Batches: 1  Memory Usage: 465057kB"
"        Bloom Filter 1: bits=134217728 hashes=10 memory=16384kB checked=100989 rejected=4913"
"        ->  Seq Scan on public.active_customers c (actual time=0.064..670.680 rows=9500000.00 loops=1)"

Если посмотреть внимательно план, то можно заметить, что у нас таблицы active_costumers и orders меняются местами при разных значениях enable_hashjoin_bloom. Для сравнения времени выполнения узлов это не критично, т.к. обе таблицы содержат примерно одинаковое количество записей.

Сравним время выполнения всех узлов плана:

Мы видим, что увеличилось время выполнения узла Hash, т.к. при построении хеш-таблицы теперь вместо 100 тыс. значений через набор хеш-функций для построение bloom-фильтра прогоняются 9.5 млн записей. Применение самого bloom-фильтра при выполнении Seq Scan on orders привело к отбрасыванию всего 4.9% строк (rejected=4913), при этом проверено было всего 100 тысяч строк из 10 млн (checked=100989). Почему? Дело в адаптивном отключении фильтра: исполнитель следит за эффективностью фильтра на лету, и если тот не оправдывает себя, просто перестаёт его применять. А время выполнения узла Hash Join почти одинаково, т.к. ему на вход идет примерно одинаковое количество строк.

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

Тестирование на реальных примерах

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

В 1С:ERP есть такой процесс, как закрытие месяца, и в ходе его выполнения встречаются много запросов, подходящих под условие применения bloom-фильтра, т.к. постоянно соединяются таблицы с тысячами и миллионами записей. Вот один из запросов, на котором сработал bloom-фильтр:

• off - https://explain.tensor.ru/archive/explain/6f12119c3ff724f469d3f23c0a9fd261:0:2026-06-29

• on - https://explain.tensor.ru/archive/explain/80a5edf9096f374dcb3d6b4699450891:0:2026-06-29

Визуальное сравнение узлов, которые ускоряет bloom-фильтр:

В данном примере у нас ускоряются три последовательных Hash Join за счет значительного снижения количества записей, идующих к ним на вход, и сам узел Seq Scan тоже выполнился быстрее, что ускорило запрос с 40 до 15 секунд.

Взглянем на часть текста запроса, который изображен выше:

FROM _AccumRg127724 T17
LEFT OUTER JOIN _Reference181 T18
ON (T17._Fld127725RRef = T18._IDRRef) AND (T18._Fld1551 = CAST(0 AS NUMERIC))
LEFT OUTER JOIN _Reference230 T19
ON (T18._Fld4875RRef = T19._IDRRef) AND (T19._Fld1551 = CAST(0 AS NUMERIC))
WHERE ((T17._Fld1551 = CAST(0 AS NUMERIC))) AND (T17._Period > '2018-03-31 23:59:59'::timestamp AND T17._Period < '3999-11-01 00:00:00'::timestamp AND T17._Active = TRUE AND (T17._Fld127725RRef IN
(SELECT
T20._Q_001_F_000RRef AS Q_001_F_000RRef
FROM pg_temp.tt50 T20) AND ((T17._Fld127727RRef <> '\2646\000\025\351/(\002\021\337r\017\234UmM'::bytea) OR (T17._Fld127727RRef <> T19._Fld155113RRef)))

При enable_hashjoin_bloom = off таблица T17 последовательно соединяется с таблицами T18, T19, T20. При enable_hashjoin_bloom = on при сканировании таблицы T17 bloom-фильтр применяется из таблицы T20, с которой без bloom-фильтра планировщик соединялся последней. При этом именно соединение с таблицей T20 позволяет значительно сократить количество выбираемых записей, в то время как соединения с таблицами T18 иT19 количество записей никак не сокращает. Таким образом, применение bloom-фильтра на этом примере позволило на более раннем этапе применить более селективный отбор, чего до этого планировщик не делал.

Следующий пример более простой и массовый - это формирование отчета по заказам клиентов в 1С:ERP.

Bloom-фильтр:

off - https://explain.tensor.ru/archive/explain/f8f8866673696b803666eb4cde1f9dd5:0:2026-07-12

on - https://explain.tensor.ru/archive/explain/9fc24890d53f211fa83be2b4ce887fc0:0:2026-07-12

Этот пример похож на синтетический пример, которы мы разбирали в начале статьи: соединение двух таблиц, строится bloom-фильтр по меньшей из таблиц, и его применение к большой таблице фильтрует большую часть строк (почти 100%):

Запрос ускоряется с 1200 до 700 мс.

Заключение

Развитие планировщика - это не поиск одной "волшебной" оптимизации, а последовательное внедрение улучшений, каждое из которых делает выполнение запросов эффективнее. Bloom-фильтр - одно из таких нововведений, которое появится в следующем релизе СУБД Tantor Postgres. За каждой подобной возможностью стоят исследования, эксперименты и тщательная проверка на реальных рабочих нагрузках, чтобы оптимизация приносила пользу именно там, где это действительно необходимо.

Далее планируем рассказать и о других оптимизациях планировщика, которые выйдут в следующей версии нашей СУБД. Подписывайтесь, чтобы не пропустить.