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

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

Типы

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

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

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

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

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

Тип bloom_ngram_filter поддерживается только в колоночных таблицах.

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

Полный перечень параметров 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
  );

Создание строковой (OLTP) таблицы с префиксными фильтрами Блума по префиксам первичного ключа. В строковых таблицах индексируемые колонки должны образовывать левый префикс первичного ключа:

CREATE TABLE orders (
    customer_id Utf8,
    order_id Utf8,
    amount Decimal(10,2),
    PRIMARY KEY (customer_id, order_id),
    -- Префиксный фильтр Блума по первой колонке ключа
    INDEX idx_customer LOCAL USING bloom_filter
        ON (customer_id)
        WITH (false_positive_probability = 0.001),
    -- Префиксный фильтр Блума по всему первичному ключу
    INDEX idx_full_key LOCAL USING bloom_filter
        ON (customer_id, order_id)
);

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

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> (в отличие, например, от полнотекстовых индексов).
• Фильтр применяется при чтении только к тем фрагментам данных, для которых при записи или слиянии порций уже сохранён блок индекса, для остальных фрагментов пропуск по этому индексу не выполняется.
• На строковых таблицах bloom_filter реализован как префиксный фильтр Блума: индексируемые колонки должны образовывать левый префикс первичного ключа. Фильтр строится по этому префиксу ключа и ускоряет точечные чтения и сканы по диапазону, ограничивающие префикс. Два индекса bloom_filter с одинаковой длиной префикса не допускаются.

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

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