Локальные индексы

Понятие локального индекса

Локальный индекс — вспомогательная структура, которая хранится вместе с данными таблицы и применяется на этапе чтения из хранилища. Она не материализует отдельную индексную таблицу.

Локальные индексы работают как фильтры чтения основной таблицы: оптимизатор запросов и слой хранения используют их, чтобы пропускать нерелевантные фрагменты данных при сканировании.

Сейчас в YDB реализованы локальные Блум-индексы; в будущем планируются и другие виды локальных индексов.

Блум-индексы

Блум-индексы — частный случай локального индекса, построенный на основе фильтра Блума.

При чтении для каждого фрагмента данных индекс проверяет, может ли в нём встречаться искомое значение (или набор n-грамм). Если фильтр сообщает, что значение точно не встречается, фрагмент пропускается без чтения проиндексированных колонок. Если фильтр «пропускает» проверку, значение может присутствовать — в том числе из-за ложноположительного срабатывания, — и фрагмент нужно читать. Это уменьшает объём фактически прочитанных данных при селективных запросах.

Типы блум-индексов

• bloom_filter — строит фильтр по точным значениям индексируемой колонки. Подходит для условий равенства (=), проверки вхождения в список (IN) и других сравнений на равенство для поддерживаемых типов.
• bloom_ngram_filter — строит фильтр по n-граммам строковой колонки (String, Utf8). При поиске по подстроке или шаблону (LIKE) запрос разбивается на n-граммы; если в индексе фрагмента нет хотя бы одной из требуемых n-грамм, в нём не может быть искомой подстроки, и фрагмент пропускается. Поддерживается только в колоночных таблицах.

Дополнительные материалы

• Блум-индексы
• ALTER TABLE ADD INDEX