В прошлых статьях мы рассмотрели
механизм индексирования PostgreSQL и
интерфейс методов доступа, а также
хеш-индексы,
B-деревья,
GiST,
SP-GiST,
GIN,
RUM и
BRIN. Нам осталось посмотреть на индексы Блума.
Bloom
Общая идея
Классический фильтр Блума — структура данных, позволяющая быстро проверить принадлежность элемента множеству. Фильтр очень компактен, но допускает ложные срабатывания: он имеет право ошибиться и счесть элемент принадлежащим множеству (false positive), но не имеет права сказать, что элемента нет в множестве, если на самом деле он там присутствует (false negative).
Фильтр представляет собой битовый массив (называемый также
сигнатурой) длиной
m бит, изначально заполненный нулями. Выбираются
k различных хеш-функций, которые отображают любой элемент множества в
k битов сигнатуры. Чтобы добавить элемент в множество, нужно установить в сигнатуре каждый из этих битов в единицу. Следовательно, если все соответствующие элементу биты установлены в единицу — элемент может присутствовать в множестве; если хотя бы один бит равен нулю — элемент точно отсутствует.
В случае индекса СУБД мы фактически имеем
N отдельных фильтров, построенных для каждой индексной строки. Как правило, в индекс включаются несколько полей; значения этих полей и составляют множество элементов для каждой из строк.
Благодаря выбору размера сигнатуры
m, можно находить компромисс между объемом индекса и вероятностью ложного срабатывания. Область применения Блум-индекса — большие, достаточно «широкие» таблицы, запросы к которым могут использовать фильтрацию по любым из полей. Этот метод доступа, как и BRIN, можно рассматривать как ускоритель последовательного сканирования: все найденные индексом совпадения необходимо перепроверять по таблице, но есть шанс вовсе не рассматривать значительную часть строк.
