Как фильтр Блума ускоряет JOIN'ы в PostgreSQL

Вот важная новость с фронта ИИ: alex7six 21 минуту назад Как фильтр Блума ускоряет JOIN'ы в PostgreSQL 8 мин 777 Блог компании Тантор Лабс PostgreSQL * SQL * Базы данных * Обзор В рамках 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;План:"Hash Join (actual time=17. 00 loops=1)" " Hash Cond: (o.

customer_id)" " -> Seq Scan on public. orders o (actual time=0. 00 loops=1)" " -> Hash (actual time=17.

Этот прогресс даёт важные сигналы о будущем отрасли, и технологический мир внимательно наблюдает.