Александр Зайцев. Чёрная магия ClickHouse: индексы пропуска

Это перевод статьи: Alexander Zaitsev. ClickHouse Black Magic: Skipping Indices

Содержание

  1. Содержание
  2. Вступление
  3. Введение
  4. Определение индекса
  5. Типы индексов
  6. Что такое фильтр Блума?
  7. Когда НЕ использовать индексы пропуска
  8. Следующие этапы

Вступление

Написано в соавторстве с ведущим инженером поддержки Михаилом Филимоновым.

О, в этих смутных контурах провижу Я очертанья грозные событий, Нам предстоящих.

Уильям Шекспир

(Перевод Т. Гнедич цитируется по ПСС в восьми томах. Издательство "Искусство", 1959, т. 5.)

Индексы ClickHouse отличаются от индексов обычных реляционных систем управления базами данных (RDMS) следующими свойствами:

  • Первичные ключи не обеспечивают уникальности,
  • Здесь нет внешних ключей и обычных индексов, основанных на двоичных деревьях.

Вместо них в ClickHouse используются вторичные индексы пропуска. Они часто приводят в замешательство даже опытных пользователей ClickHouse и не просты в настройке. Однако, если использовать их правильно, они могут драматически улучшить производительность запросов. В этой статье мы погрузимся в индексы пропуска и изучим толику чёрной магии ClickHouse.

Введение

Давайте для начала рассмотрим, как устроено хранилище ClickHouse.

Данные в таблицах типа MergeTree образуют куски.

  • Каждый кусок - это каталог на устройстве хранения, содержащий по файлу для каждого столбца и несколько дополнительных файлов с метаданными.
  • Столбец содержит массив значений, порядок которых соответствует порядку строк.
  • Данные в столбцах сортируются по ключу таблицы, указанному в ORDER BY.
  • Каждые 8192 строк в куске называются гранулой.

Размер гранулы определяется параметром index_granularity в определении таблицы MergeTree, но иногда ClickHouse может настраивать его адаптивно. В главном индексе таблицы, которым является PRIMARY KEY и который обычно совпадает с порядком, указанным в ORDER BY, есть ссылки на гранулы. Поскольку гранула - это 8192 строк, индекс является разряжённым. Индекс также ссылается на особые файлы меток, по файлу для каждого столбца, которые ссылаются на данные в самих файлах столбцов.

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

А затем просмотреть страницу в поисках самого слова.

Можно взять другой пример - Британскую Энциклопедию. В этом случае можно найти том по таблице разделов.

Однако, если нужно найти что-то не соответствующее порядку сортировки, то алфавитный индекс использовать не получится. Допустим, нужно найти все статьи об античной культуре. В таком случае нужно выполнить полное сканирование или воспользоваться специальным предметным указателем, который часто можно найти в конце книги. Такой указатель ссылается на несколько страниц, на которых можно найти информацию по теме. Он не настолько эффективен, как алфавитный, но тем не менее позволяет избежать полного сканирования.

Основной вопрос: возможно ли ускорить поиск, избежав создания дополнительных копий данных?

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

Индексы пропуска ClickHouse используют очень похожую идею - они вставляют в гранулу что-то вроде "выжимки знаний" о её содержимом. Эта выжимка знаний позволяет быстро найти страницы/гранулы, которые нужно просканировать и отбросить все остальные.

Определение индекса

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

INDEX название_индекса выражение TYPE type(...) GRANULARITY значение_гранулярности
  • название_индекса - любая строка, уникальная в рамках таблицы,
  • выражение – выражение из столбцов таблицы. Обычно это просто имя одной колонки,
  • тип – тип индекса, в котором определяется это "дополнительное знание", которое хранится в индексе. Мы обсудим его в следующей главе.

Последний параметр GRANULARITY - самый интересный. Чтобы сделать индекс ещё эффективнее, в нём можно собирать информацию о нескольких гранулах сразу. Это позволяет ClickHouse быстрее пропускать гранулы. Так, GRANULARITY 1 означает, что индекс хранится для каждой гранулы, а GRANULARITY 10 означает, что индекс хранится для 10 гранул и т.п. Оптимальное значение зависит от распределения данных.

ClickHouse содержит несколько разных типов индексов пропуска, которые отличаются разновидностью информации, хранящейся в грануле. Давайте рассмотрим их!

Типы индексов

Самый простой - minmax. Он хранит минимальное и максимальное значение столбца (или выражения) в определённой грануле. При исполнении запросов ClickHouse может быстро проверить, что значения столбца находятся за пределами без сканирования столбца. Это лучше работает в случае, если значение столбца медленно меняется по порядку сортировки.

Например, возьмём такую таблицу:

CREATE TABLE temperature_sensors(
    sensor_id Int32,
    datetime DateTime,
    value Decimal(5,2)
) Engine = MergeTree 
   PARTITION BY toYYYYMM(datetime) 
   ORDER BY (sensor_id, datetime);

Температура датчика изменяется медленее времени, поэтому если нужно запускать запросы вида 'WHERE value > 100', то индекс minmax окажет значительную помощь.

ALTER TABLE temperature_sensors ADD INDEX temp value TYPE(minmax) GRANULARITY 1

Примечание: Если индекс добавляется к существующей таблице, то он не обновляется автоматически. ALTER TABLE изменяет только метаданные, поэтому индекс считается только для вновь вставляемых данных. Для обновления задним числом нужна дополнительная команда DDL:

ALTER TABLE temperature_sensors MATERIALIZE INDEX temp

Set(N) - это другой тип индекса. Он хранит все отличающиеся значения столбца или выражения в грануле. Если индексируемый столбец используется в выражении WHERE, ClickHouse может прочитать малое множество, а не весь столбец. Он хорошо подходит, если в столбце содержится небольшое количество отличающихся значений в грануле, но значения меняются по порядку сортировки таблицы. Например, возьмём такую таблицу:

CREATE TABLE stats(
    source_ip IPv4,
    datetime DateTime,
    country String,
    ...
    INDEX country_idx country Set(100) GRANULARITY 100
) Engine = MergeTree
   PARTITION BY toYYYYMM(datetime)
   ORDER BY (source_ip, datetime);

Упорядоченные IP-адреса обычно близки друг к другу географически, поэтому имеет смысл создать индекс 'Set' для столбца 'country'. Одна гранула содержит одну страну или небольшое их количество, поэтому запросы с указанием страны могут воспользоваться этим индексом.

Параметр индекса Set ограничивает максимальное количество значений, хранящихся в индексе. '0' означает - неограниченно. Размер индекса должен быть значительно меньше размера самого столбца, в противном случае от него нет никакой выгоды.

Фильтрующие индексы Блума. Фильтрующий индекс Блума - непростая штука, которая осложняется тем, что ClickHouse поддерживает фильтрующие индексы Блума трёх типов:

  • tokenbf_v1(размер_фильтра_блума_в_байтах, количество_хэш_функций, зерно_случайности): Входная строка делится на алфавитно-цифровые фрагменты, а каждый фрагмент сортируется с помощью фильтра Блума (см. ниже). Он подходит для поиска точного совпадения с искомой строкой. Например, если есть столбец 'url' и нужно найти определённую часть URL или параметр запроса.
  • ngrambf_v1(n, размер_фильтра_блума_в_байтах, количество_хэш_функций, зерно_случайности): В этом случае входная строка делится на n-грамы (первый параметр - размер n-грамы, обычно 3 или 4), а затем сохраняется в фильтр Блума. Он может работать для полнотекстового поиска.
  • bloom_filter([ложно_положительный]): Это наиболее общий случай. Входные строки хранятся в фильтре Блума "как есть". Он подходит для поиска точных совпадений в строках, а также в массивах.

Что такое фильтр Блума?

Что такое фильтры Блума? Это вероятностная структура данных для ускорения поиска. "Вероятностная" означает, что она не точная, но подходит для индексов пропуска. Как же это возможно? Давайте представим.

Предположим, что нужно найти значение в списке длиной n. Для построения фильтра Блума сделаем следующее:

  1. Сначала создадим битовый массив, обычно он называется вектором. Давайте обозначим длину вектора как m, m < n. Изначально все биты вектора равны нулю.
  2. Для каждого входного значения посчитаем хэш-функцию, которая вернёт хэш в диапазоне [0 .. m-1]. Проставим единицу соответствующие биты вектора.

После обработки списка значений некоторые биты вектора будут единичными. Это означает, что элемент с таким значением хэша наблюдался в списке.

Для поиска элемента в списке нужно посчитать хэш и проверить, равен ли соответствующий бит единице или нулю. Если он равен нулю, то это 100% гарантия, что элемента нет в списке. Если бит равен единице, то придётся просканировать весь список. Возможны ложно-положительные срабатывания из-за коллизий хэшей. Этот метод лучше работает для ответа на вопрос, отсутствует ли элемент в списке или возможно он содержится в списке. В лучшем случае вместо сканирования начального набора данных из n элементов сканируется только намного меньший вектор из m/8 байт.

Если думать о битах, то можно решить, что чем меньше значение m, тем быстрее будет сканироваться вектор, но на самом деле при этом будет больше коллизий. Возможность коллизий зависит от количества отличающихся значений в исходном множестве, а также оно пропорционально 1/m. Чтобы уменьшить количество коллизий, можно использовать несколько хэш-функций.

В ClickHouse вектор фильтра Блума строится и хранится для гранулы (или нескольких гранул). Поэтому для каждой гранулы можно быстро определить, отсутствует ли искомое значение и можно ли полностью пропустить гранулу. С другой стороны, ложно-положительные срабатывания бесполезны и нужно по возможности уменьшить их вероятность.

Остался лишь вопрос, как выбрать оптимальные параметры размера вектора и количества хэш-функций для того, чтобы фильтр Блума оставался компактным и в то же время уменьшить ложно-положительные срабатывания? Это очень хороший вопрос. Ответ в значительной мере зависит от набора данных и их распределения. Изучим этот вопрос и дадим немного практических рекомендаций по фильтрам Блума в следующей статье. Но сначала вернёмся немного назад.

Когда НЕ использовать индексы пропуска

Индексы пропуска хороши, но как и любые другие типы требуют затрат. Например, подсчёт векторов фильтров Блума может быть очень дорогим при вставке данных и при операциях слияния. Поэтому их стоит использовать только в том случае, если сокращается время выполнения запросов.

Индекс эффективен в том случае, если он значительно меньше самого столбца, в противном случае он может замедлить выполнение запроса. Помните, что ClickHouse может просто загрузить столбец полностью, применить фильтр и решить, какие гранулы прочитать из соседних столбцов. В обработке запросов этот этап называется PREWHERE. Если хотите сравнить размер индекса пропуска с размером проиндексированного столбца, обратитесь к таблице system.data_skipping_indices.

Также запомните, что индекс должен действительно пропускать. Если для каждой гранулы индекс срабатывает положительно, то он просто тратит процессорное время.

Использование индексов пропуска для столбцов, которые уже есть в PRIMARY KEY также не имеет смысла. Если PRIMARY KEY можно применить для выполнения запроса, то он всегда будет быстрее.

Следующие этапы

В этой статье мы представили индексы пропуска ClickHouse. Индексы в традиционных базах данных используется для нахождения данных, совпадающих с условием фильтрации. Индексы пропуска, наоборот, содержат дополнительную информацию, которая позволяет ClickHouse быстро принять решение, что определённая часть данных не соответствует условиям фильтрации, и пропустить её. Но для эффективности нужно аккуратное проектирование и настройка с использованием знаний данных и их распределения в индексируемых столбцах. Вот где начинается настоящее волшебство. Скоро мы расскажем заклинания. Не переключайтесь!