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

Блум-индексы — локальные вспомогательные структуры на основе фильтра Блума, которые ускоряют селективные запросы за счёт пропуска фрагментов данных, в которых искомое значение гарантированно отсутствует. В отличие от глобальных вторичных индексов, они работают как фильтры чтения основной таблицы и уменьшают объём данных, которые нужно фактически читать.

Типы

Поддерживаются два типа:

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

Параметры и значения по умолчанию

Полный перечень параметров WITH (...) и значений по умолчанию:

• bloom_filter
  • false_positive_probability — целевая вероятность ложноположительного срабатывания фильтра: доля фрагментов, которые фильтр не отсечёт, хотя искомого значения в них нет (диапазон (0, 1)). Меньшее значение уменьшает число лишних чтений, но увеличивает размер индекса.
    • Если параметр не указан, для строковых таблиц используется 0.0001, для колоночных — 0.1. Более строгий порог по умолчанию в строковых таблицах соответствует OLTP-сценарию точечных чтений; в колоночных — аналитическим сканам, где допустим больший компромисс между размером индекса и отсечением фрагментов.
  • Индексируемые колонки — типы YQL, для которых определено сравнение на равенство, кроме Yson, Json и JsonDocument (см. операторы сравнения). В колоночной таблице допускается одна колонка; в строковой — несколько.
• bloom_ngram_filter (колонки String, Utf8; только колоночные таблицы)
  • ngram_size — размер n-граммы, целое число от 3 до 8 (по умолчанию 3).
  • false_positive_probability — целевая вероятность ложноположительного срабатывания (диапазон (0, 1); по умолчанию 0.1).
  • case_sensitive — учёт регистра при построении n-грамм: true или false (по умолчанию true).

Синтаксис создания: CREATE TABLE, ALTER TABLE ADD INDEX.

Изменение параметров после создания: ALTER INDEX.

Примеры

Создание таблицы с индексом bloom_filter:

CREATE TABLE events (
    id Uint64,
    resource_id Utf8,
    message Utf8,
    PRIMARY KEY (id),
    INDEX idx_bloom LOCAL USING bloom_filter
        ON (resource_id)
        WITH (false_positive_probability = 0.01)
);

Добавление bloom_ngram_filter к существующей таблице:

ALTER TABLE events
  ADD INDEX idx_ngram LOCAL USING bloom_ngram_filter
  ON (message)
  WITH (
    ngram_size = 3,
    false_positive_probability = 0.01,
    case_sensitive = true
  );

Изменение параметров:

ALTER TABLE events ALTER INDEX idx_ngram SET (
    ngram_size = 4,
    false_positive_probability = 0.005,
    case_sensitive = false
);

Настройка параметров

Если после развёртывания индекса запросы всё ещё читают слишком много данных, попробуйте уменьшить false_positive_probability. Если индекс занимает слишком много места — попробуйте увеличить его.

Значения меняются через ALTER INDEX, см. пример.

Рекомендации:

• Начните с false_positive_probability = 0.01, затем корректируйте по фактическим метрикам чтения и размеру индекса.
• ngram_size для bloom_ngram_filter обычно начинают с 3; увеличение значения может сделать фильтрацию строже для более длинных подстрок.
• Меняйте параметры по одному и сравнивайте результат на одной и той же нагрузке.

Особенности и ограничения

• Индекс всегда локальный (LOCAL); глобального варианта нет.
• В запросах не используется синтаксис VIEW <index> (в отличие, например, от полнотекстовых индексов).
• Фильтр применяется при чтении только к тем фрагментам данных, для которых при записи или слиянии порций уже сохранён блок индекса, для остальных фрагментов пропуск по этому индексу не выполняется.

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

• Вторичные индексы
• Справочник YQL: CREATE TABLE
• Справочник YQL: SELECT
• Справочник YQL: ALTER TABLE
• Быстрый старт