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

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

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

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

Сейчас в YDB реализованы локальные Блум-индексы и min_max-индекс.

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

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

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

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

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

Локальные блум-индексы

Тип bloom_filter работает как в строковых (OLTP), так и в колоночных (OLAP) таблицах, но реализация различается:

• В строковых таблицах фильтр строится как префиксный фильтр Блума по левому префиксу первичного ключа. Индексируемые колонки должны образовывать непрерывное ведущее подмножество колонок первичного ключа. Это ускоряет точечные чтения и сканы по диапазону, ограничивающие ведущие колонки ключа. Для создания префиксного фильтра Блума используйте ALTER TABLE ... ADD INDEX, для удаления — ALTER TABLE ... DROP INDEX.
• В колоночных таблицах фильтр строится по значениям индексируемой колонки в каждом фрагменте данных (порции) и применяется при аналитических сканах для пропуска фрагментов, не содержащих искомое значение.

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

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

min_max-индекс

min_max-индекс — частный случай локального индекса, который хранит минимальное и максимальное значение одной индексируемой колонки для каждого фрагмента данных.

При чтении с фильтром специального вида по колонке с min_max-индексом YDB сначала читает сохранённые для фрагмента минимальное и максимальное значения и проверяет, пересекается ли интервал из фильтра с этим диапазоном. Если интервалы не пересекаются, предикат гарантированно ложен на всех значениях фрагмента, поэтому фрагмент можно не читать. Это полезно для диапазонных предикатов и условий равенства (частный случай диапазонного предиката) по колонкам с небольшим разбросом между минимальным и максимальным значениями внутри хранимых фрагментов.

Пример:

В хранилище для таблицы events в одном из фрагментов колонки level типа Int32 находятся значения [5, 5, 9, 5, 9, 13]. Тогда минимальное значение — 5, максимальное — 13. Для запроса SELECT * FROM events WHERE level = 15 интервал фильтра — [15, 15]. Он не пересекается с интервалом [5, 13], поэтому такой фрагмент можно не читать из хранилища.

Предикаты min_max-индекса

Оптимизатор может использовать min_max-индекс для предикатов =, <, <=, >, >=, BETWEEN, а также совместимых комбинаций с AND или OR.

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

• min_max-индекс
• ALTER TABLE ADD INDEX