В прошлых статьях мы рассмотрели механизм индексирования PostgreSQL и интерфейс методов доступа, а также хеш-индексы, B-деревья, GiST, SP-GiST, GIN, RUM и BRIN. Нам осталось посмотреть на индексы Блума.
Общая идея
Классический фильтр Блума — структура данных, позволяющая быстро проверить принадлежность элемента множеству. Фильтр очень компактен, но допускает ложные срабатывания: он имеет право ошибиться и счесть элемент принадлежащим множеству (false positive), но не имеет права сказать, что элемента нет в множестве, если на самом деле он там присутствует (false negative).
Фильтр представляет собой битовый массив (называемый также сигнатурой) длиной m бит, изначально заполненный нулями. Выбираются k различных хеш-функций, которые отображают любой элемент множества в k битов сигнатуры. Чтобы добавить элемент в множество, нужно установить в сигнатуре каждый из этих битов в единицу. Следовательно, если все соответствующие элементу биты установлены в единицу — элемент может присутствовать в множестве; если хотя бы один бит равен нулю — элемент точно отсутствует.
В случае индекса СУБД мы фактически имеем N отдельных фильтров, построенных для каждой индексной строки. Как правило, в индекс включаются несколько полей; значения этих полей и составляют множество элементов для каждой из строк.
Благодаря выбору размера сигнатуры m, можно находить компромисс между объемом индекса и вероятностью ложного срабатывания. Область применения Блум-индекса — большие, достаточно «широкие» таблицы, запросы к которым могут использовать фильтрацию по любым из полей. Этот метод доступа, как и BRIN, можно рассматривать как ускоритель последовательного сканирования: все найденные индексом совпадения необходимо перепроверять по таблице, но есть шанс вовсе не рассматривать значительную часть строк.
Устройство
Мы уже говорили о сигнатурных деревьях в контексте метода доступа GiST. В отличие от этих деревьев, Блум-индекс представляет собой плоскую структуру. Он состоит из метастраницы, за которой следуют обычные страницы с индексными строками. Каждая индексная строка содержит сигнатуру и ссылку на табличную строку (TID), как схематически показано на рисунке.
Создание и выбор значений параметров
При создании Блум-индекса в параметрах хранения указывается общий размер сигнатуры (length) и число устанавливаемых битов отдельно для каждого поля, включенного в индекс (col1—col32):
create index on ... using bloom(...) with (length=..., col1=..., col2=..., ...);
Способ указания числа битов выглядит странно: эти числа должны быть параметром не индекса, а класса операторов. Просто в настоящее время классы операторов нельзя параметризовать, хотя работа над этим ведется.
Как выбрать подходящие значения? Теория говорит о том, что если задаться вероятностью p ложного срабатывания фильтра, то оптимальное число бит сигнатуры можно оценить как
m = −n log2(p) / ln(2), где n — число полей в индексе, а число устанавливаемых бит k = −log2(p).
Внутри индекса сигнатура хранится как массив двубайтовых целых чисел, так что значение m можно смело округлять сверху до 16.
Выбирая вероятность p, следует учитывать размер индекса, который будет равен примерно
(m/8 + 6)N, где N — число строк в таблице, а 6 — размер указателя TID в байтах.
Несколько моментов:
- Вероятность ложного срабатывания p относится к одному фильтру; при сканировании таблицы мы ожидаем получить Np ложных срабатываний (для запроса, который возвращает мало строк, конечно). Например, для таблицы в миллион строк и вероятности 0,01 в среднем можно ожидать в плане запроса «Rows Removed by Index Recheck: 10000».
- Фильтр Блума — вероятностная структура. Говорить о конкретных числах имеет смысл, только усредняя достаточно много значений, а в каждом конкретном случае можно получить все, что угодно.
- Приведенные выше оценки основаны на идеализированной математической модели и ряде допущений. На практике же результат скорее всего получается хуже. Так что к формулам стоит относиться спокойно: это просто способ выбрать начальные значения для дальнейших экспериментов.
- Метод доступа позволяет выбрать число устанавливаемых бит отдельно для каждого поля. Есть разумное предположение, что на самом деле оптимальное число зависит от распределения значений в столбце. Если хочется заморочиться, можно посмотреть, например, эту статью (буду признателен за ссылки на другие исследования). Но сначала перечитайте предыдущий пункт.
Обновление
При вставке в таблицу новой строки формируется сигнатура: для значений всех индексированных полей устанавливаются в единицу все соответствующие им биты. По классике необходимо иметь k различных хеш-функций; на практике же обходятся генератором псевдослучайных чисел, порождающий элемент (seed) для которого выбирается каждый раз с помощью единственной хеш-функции.
Обычный фильтр Блума не поддерживает удаления элементов, но для Блум-индекса этого и не требуется: при удалении строки из таблицы удаляется вся сигнатура целиком вместе со строкой индекса.
Изменение, как обычно, состоит из удаления старой версии строки и вставке новой (при этом сигнатура вычисляется заново).
Сканирование
Поскольку единственное, что умеет фильтр Блума — это проверять принадлежность элемента множеству, то и единственная поддерживаемая Блум-индексом операция — проверка на равенство (как в хеш-индексе).
Как мы говорили, Блум-индекс является плоским, так что при индексном доступе он всегда читается подряд и целиком. В процессе чтения строится битовая карта, которая затем используется для доступа к таблице.
При традиционном индексном доступе предполагается, что потребуется прочитать немного индексных страниц, которые к тому же могут вскоре понадобиться снова; поэтому они помещаются в буферный кэш. Чтение же Блум-индекса — это фактически последовательное сканирование. Чтобы не допустить вытеснение из кэша полезной информации, чтение происходит через небольшое буферное кольцо, точно так же, как и при последовательном сканировании таблиц.
Следует учесть, что чем больше размер Блум-индекса, тем менее привлекательным он будет казаться планировщику — эта зависимость линейна, в отличие от древовидных индексов.
Пример
Таблица
Посмотрим на Блум-индекс на примере большой таблицы flights_bi из прошлой статьи. Напомню, что размер этой таблицы составляет 4 ГБ при примерно 30 миллионах строк. Определение таблицы:
demo=# \d flights_bi
Table "bookings.flights_bi"
Column | Type | Collation | Nullable | Default
--------------------+--------------------------+-----------+----------+---------
airport_code | character(3) | | |
airport_coord | point | | |
airport_utc_offset | interval | | |
flight_no | character(6) | | |
flight_type | text | | |
scheduled_time | timestamp with time zone | | |
actual_time | timestamp with time zone | | |
aircraft_code | character(3) | | |
seat_no | character varying(4) | | |
fare_conditions | character varying(10) | | |
passenger_id | character varying(20) | | |
passenger_name | text | | |
Начнем с создания расширения — Блум-индекс входит в стандартную поставку начиная с версии 9.6, но недоступен по умолчанию.
demo=# create extension bloom;
CREATE EXTENSION
С помощью BRIN в прошлый раз нам удалось проиндексировать три поля (scheduled_time, actual_time, airport_utc_offset). Блум-индексы не зависят от физического расположения данных, поэтому попробуем включить в индекс почти все поля таблицы. Однако исключим время (scheduled_time и actual_time) — методом поддерживается только сравнение на равенство, но запрос по точному времени вряд ли кому-то интересен (можно было бы построить индекс по выражению, округлив время до суток, но мы не будем этого делать). Еще нам придется исключить координаты аэропорта (airport_coord) — забегая вперед, тип point не поддерживается.
Чтобы выбрать значения параметров, возьмем вероятность ложного срабатывания 0,01 (понимая, что реально получится больше). Приведенные выше формулы для n = 9 и N = 30 000 000 дают размер сигнатуры 96 бит и предлагают устанавливать 7 бит на элемент. Расчетный размер индекса — 515 МБ (примерно восьмая часть таблицы).
(При минимальном размере сигнатуры в 16 бит формулы обещают в два раза меньший индекс, но позволяют надеяться лишь на вероятность 0,5, что совсем плохо.)
Классы операторов
Итак, пробуем создать индекс.
demo=# create index flights_bi_bloom on flights_bi
using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name)
with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7);
ERROR: data type character has no default operator class for access method "bloom"
HINT: You must specify an operator class for the index or define a default operator class for the data type.
Печаль: в расширении нам дают всего лишь два класса операторов:
demo=# select opcname, opcintype::regtype
from pg_opclass
where opcmethod = (select oid from pg_am where amname = 'bloom')
order by opcintype::regtype::text;
opcname | opcintype
----------+-----------
int4_ops | integer
text_ops | text
(2 rows)
К счастью, не составляет труда создать аналогичные классы и для других типов данных. В класс операторов для метода bloom должен входить ровно один оператор — равенство — и ровно одна вспомогательная функция — хеширование. Самый простой способ найти нужные операторы и функции для произвольного типа — заглянуть в системный каталог на классы операторов метода hash:
demo=# select distinct
opc.opcintype::regtype::text,
amop.amopopr::regoperator,
ampr.amproc
from pg_am am, pg_opclass opc, pg_amop amop, pg_amproc ampr
where am.amname = 'hash'
and opc.opcmethod = am.oid
and amop.amopfamily = opc.opcfamily
and amop.amoplefttype = opc.opcintype
and amop.amoprighttype = opc.opcintype
and ampr.amprocfamily = opc.opcfamily
and ampr.amproclefttype = opc.opcintype
order by opc.opcintype::regtype::text;
opcintype | amopopr | amproc
-----------+----------------------+--------------
abstime | =(abstime,abstime) | hashint4
aclitem | =(aclitem,aclitem) | hash_aclitem
anyarray | =(anyarray,anyarray) | hash_array
anyenum | =(anyenum,anyenum) | hashenum
anyrange | =(anyrange,anyrange) | hash_range
...
Имея эту информацию, создадим два недостающих класса:
demo=# CREATE OPERATOR CLASS character_ops
DEFAULT FOR TYPE character USING bloom AS
OPERATOR 1 =(character,character),
FUNCTION 1 hashbpchar;
CREATE OPERATOR CLASS
demo=# CREATE OPERATOR CLASS interval_ops
DEFAULT FOR TYPE interval USING bloom AS
OPERATOR 1 =(interval,interval),
FUNCTION 1 interval_hash;
CREATE OPERATOR CLASS
Для точек (тип point) хеш-функция не определена; именно по этой причине мы не сможем построить Блум-индекс по такому полю (точно так же, как не сможем выполнить хеш-соединение по полям этого типа).
Пробуем снова:
demo=# create index flights_bi_bloom on flights_bi
using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name)
with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7);
CREATE INDEX
Размер индекса составляет 526 МБ, что несколько больше рассчетного — из-за того, что в формуле мы не учитываем накладных расходов на служебную информацию в каждом блоке.
demo=# select pg_size_pretty(pg_total_relation_size('flights_bi_bloom'));
pg_size_pretty
----------------
526 MB
(1 row)
Запросы
Теперь мы можем выполнять поиск по самым разным критериям, и он будет поддержан индексом.
Как мы говорили, фильтр Блума — вероятностная структура, поэтому эффективность в каждом конкретном случае может получиться разная. Например, посмотрим записи, относящиеся к двум пассажирам, Мирославу Сидорову:
demo=# explain(costs off,analyze)
select * from flights_bi where passenger_name='MIROSLAV SIDOROV';
QUERY PLAN
--------------------------------------------------------------------------------------------------
Bitmap Heap Scan on flights_bi (actual time=2639.010..3010.692 rows=2 loops=1)
Recheck Cond: (passenger_name = 'MIROSLAV SIDOROV'::text)
Rows Removed by Index Recheck: 38562
Heap Blocks: exact=21726
-> Bitmap Index Scan on flights_bi_bloom (actual time=1065.191..1065.191 rows=38564 loops=1)
Index Cond: (passenger_name = 'MIROSLAV SIDOROV'::text)
Planning time: 0.109 ms
Execution time: 3010.736 ms
и Марфе Соловьевой:
demo=# explain(costs off,analyze)
select * from flights_bi where passenger_name='MARFA SOLOVEVA';
QUERY PLAN
---------------------------------------------------------------------------------------------------
Bitmap Heap Scan on flights_bi (actual time=9980.884..10142.684 rows=2 loops=1)
Recheck Cond: (passenger_name = 'MARFA SOLOVEVA'::text)
Rows Removed by Index Recheck: 3950168
Heap Blocks: exact=45757 lossy=67332
-> Bitmap Index Scan on flights_bi_bloom (actual time=1037.588..1037.588 rows=212972 loops=1)
Index Cond: (passenger_name = 'MARFA SOLOVEVA'::text)
Planning time: 0.157 ms
Execution time: 10142.730 ms
В одном случае фильтр допустил всего 40 тысяч ложных срабатываний, в другом — аж 4 миллиона. Соответственно отличается и время выполнения запросов.
А вот результаты для поиска тех же самых строк, используя не имя, а номер документа. Мирослав:
demo=# explain(costs off,analyze)
demo-# select * from flights_bi where passenger_id='5864 006033';
QUERY PLAN
-------------------------------------------------------------------------------------------------
Bitmap Heap Scan on flights_bi (actual time=13747.305..16907.387 rows=2 loops=1)
Recheck Cond: ((passenger_id)::text = '5864 006033'::text)
Rows Removed by Index Recheck: 9620258
Heap Blocks: exact=50510 lossy=165722
-> Bitmap Index Scan on flights_bi_bloom (actual time=937.202..937.202 rows=426474 loops=1)
Index Cond: ((passenger_id)::text = '5864 006033'::text)
Planning time: 0.110 ms
Execution time: 16907.423 ms
И Марфа:
demo=# explain(costs off,analyze)
select * from flights_bi where passenger_id='2461 559238';
QUERY PLAN
--------------------------------------------------------------------------------------------------
Bitmap Heap Scan on flights_bi (actual time=3881.615..3934.481 rows=2 loops=1)
Recheck Cond: ((passenger_id)::text = '2461 559238'::text)
Rows Removed by Index Recheck: 30669
Heap Blocks: exact=27513
-> Bitmap Index Scan on flights_bi_bloom (actual time=1084.391..1084.391 rows=30671 loops=1)
Index Cond: ((passenger_id)::text = '2461 559238'::text)
Planning time: 0.120 ms
Execution time: 3934.517 ms
Эффективность снова сильно отличается, на этот раз больше повезло Марфе.
Заметим, что поиск одновременно по двум полям будет выполняться значительно эффективнее, поскольку вероятность ложного срабатывания p превращается в p2:
demo=# explain(costs off,analyze)
select * from flights_bi
where passenger_name='MIROSLAV SIDOROV'
and passenger_id='5864 006033';
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on flights_bi (actual time=872.593..877.915 rows=2 loops=1)
Recheck Cond: (((passenger_id)::text = '5864 006033'::text)
AND (passenger_name = 'MIROSLAV SIDOROV'::text))
Rows Removed by Index Recheck: 357
Heap Blocks: exact=356
-> Bitmap Index Scan on flights_bi_bloom (actual time=832.041..832.041 rows=359 loops=1)
Index Cond: (((passenger_id)::text = '5864 006033'::text)
AND (passenger_name = 'MIROSLAV SIDOROV'::text))
Planning time: 0.524 ms
Execution time: 877.967 ms
А вот условие с логическим «или» не поддерживается совсем — это ограничение не данного метода доступа, а планировщика. Остается, конечно, вариант прочитать индекс два раза, построить две битовые карты и объединить их, но это скорее всего слишком накладно, чтобы такой план был выбран.
Сравнение с BRIN и Hash
Области применения Блум-индексов и индексов BRIN, очевидно, пересекаются. Это большие таблицы, для которых желательно обеспечить поиск по разным полям, причем точность поиска приносится в жертву компактности.
BRIN-индексы компактнее (скажем, до десятков мегабайт в нашем примере) и могут поддерживать поиск по диапазону, но имеют очень сильное ограничение, связанное с физическим расположением данных в файле. Блум-индексы получаются больше (сотни мегабайт), зато не имеют никаких ограничений, кроме наличия подходящей функции хеширования.
Как и индексы Блума, хеш-индексы поддерживают единственную операцию проверки на равенство. Хеш-индекс обеспечивает недостижимую для Блума точность поиска, но и размер его существенно больше (в нашем примере — гигабайт только по одному полю, а по нескольким полям хеш-индекс создать нельзя).
Свойства
По традиции посмотрим на свойства (запросы приводились ранее).
Свойства метода:
amname | name | pg_indexam_has_property
--------+---------------+-------------------------
bloom | can_order | f
bloom | can_unique | f
bloom | can_multi_col | t
bloom | can_exclude | f
Очевидно, метод доступа позволяет строить индексы по нескольким столбцам — Блум-индекс по одному стоблцу вряд ли имеет смысл.
Свойства индекса:
name | pg_index_has_property
---------------+-----------------------
clusterable | f
index_scan | f
bitmap_scan | t
backward_scan | f
Единственно возможный способ сканирования — по битовой карте. Поскольку индекс всегда сканируется целиком, нет смысла реализовывать обычный индексный доступ, при котором TID-ы возвращаются по одному.
name | pg_index_column_has_property
--------------------+------------------------------
asc | f
desc | f
nulls_first | f
nulls_last | f
orderable | f
distance_orderable | f
returnable | f
search_array | f
search_nulls | f
Здесь все «прочерки», и даже с неопределенными значениями этот метод доступа работать не умеет.
И напоследок
Не исключаю, что эта серия статей продолжится в будущем с появлением новых интересных типов индексов, но сейчас пришло время остановиться.
Хочу выразить благодарность своим коллегам из Postgres Professional (некоторые из которых являются авторами многих рассмотренных методов доступа) за чтение черновиков и высказанные замечания. И, конечно же, я признателен вам за терпение и ценные комментарии. Ваше внимание дало мне силы дойти до этой точки. Спасибо!
Комментариев нет:
Отправить комментарий