пятница, 20 апреля 2018 г.

Индексы в PostgreSQL — 10

Статья Егора Рогова, завершающая цикл публикаций об индексах в PostgreSQL в нашем техническом блоге на Хабре. Не исключено, что эта серия статей продолжится в будущем с появлением новых интересных типов индексов, но сейчас пришло время остановиться. Автор выражает благодарность своим коллегам из Postgres Professional (некоторые из которых являются авторами многих рассмотренных методов доступа) за чтение черновиков и высказанные замечания.

В прошлых статьях мы рассмотрели механизм индексирования PostgreSQL и интерфейс методов доступа, а также хеш-индексы, B-деревья, GiST, SP-GiST, GIN, RUM и BRIN. Нам осталось посмотреть на индексы Блума.

Bloom


Общая идея

Классический фильтр Блума — структура данных, позволяющая быстро проверить принадлежность элемента множеству. Фильтр очень компактен, но допускает ложные срабатывания: он имеет право ошибиться и счесть элемент принадлежащим множеству (false positive), но не имеет права сказать, что элемента нет в множестве, если на самом деле он там присутствует (false negative).

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

В случае индекса СУБД мы фактически имеем N отдельных фильтров, построенных для каждой индексной строки. Как правило, в индекс включаются несколько полей; значения этих полей и составляют множество элементов для каждой из строк.

Благодаря выбору размера сигнатуры m, можно находить компромисс между объемом индекса и вероятностью ложного срабатывания. Область применения Блум-индекса — большие, достаточно «широкие» таблицы, запросы к которым могут использовать фильтрацию по любым из полей. Этот метод доступа, как и BRIN, можно рассматривать как ускоритель последовательного сканирования: все найденные индексом совпадения необходимо перепроверять по таблице, но есть шанс вовсе не рассматривать значительную часть строк.


Читать статью полностью в нашем блоге на www.habrahabr.ru:

Предыдущие 9 статей Егора Рогова об индексах в PostgreSQL


Индексы в PostgreSQL — 9
BRIN
Индексы в PostgreSQL — 8
RUM
Индексы в PostgreSQL — 7
GIN
Индексы в PostgreSQL — 6
SP-GiST
Индексы в PostgreSQL — 5
GiST
Индексы в PostgreSQL — 4
Btree
Индексы в PostgreSQL — 3
Hash
Индексы в PostgreSQL — 2
 Интерфейс 
Индексы в PostgreSQL — 1
 Предисловие 

Поделись этим