Понимание индексов пропуска данных ClickHouse

Введение

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

Тем не менее, независимо от того, насколько тщательно настроен первичный ключ, неизбежно будут случаи использования запросов, которые не могут эффективно его использовать. Пользователи часто полагаются на ClickHouse для данных типа временных рядов, но они также часто хотят анализировать эти же данные по другим бизнес-измерениям, таким как идентификатор клиента, URL веб-сайта или номер продукта. В таком случае производительность запросов может значительно ухудшиться, поскольку может потребоваться полное сканирование каждого значения в колонке для применения условия в предложении WHERE. Хотя ClickHouse всё равно остаётся относительно быстрым в этих условиях, оценка миллионов или миллиардов отдельных значений приведёт к тому, что "неиндексированные" запросы будут выполняться гораздо медленнее, чем запросы на основе первичного ключа.

В традиционной реляционной базе данных одним из способов решения этой проблемы является прикрепление одного или нескольких "вторичных" индексов к таблице. Это структура b-дерева, которая позволяет базе данных находить все соответствующие строки на диске за O(log(n)) времени вместо O(n) времени (сканирование таблицы), где n — количество строк. Однако этот тип вторичного индекса не будет работать для ClickHouse (или других столбцовых баз данных), поскольку на диске нет отдельных строк, которые можно было бы добавить в индекс.

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

Основная операция

Пользователи могут применять индексы пропуска данных только для таблиц семейства MergeTree. Каждый индекс пропуска имеет четыре основных аргумента:

• Имя индекса. Имя индекса используется для создания файла индекса в каждой партиции. Также оно требуется в качестве параметра при удалении или материализации индекса.
• Выражение индекса. Выражение индекса используется для вычисления набора значений, хранящихся в индексе. Это может быть комбинация колонок, простых операторов и/или подмножества функций, определяемых типом индекса.
• TYPE. Тип индекса управляет расчётом, который определяет, возможно ли пропускать чтение и оценку каждого блока индекса.
• GRANULARITY. Каждый индексированный блок состоит из GRANULARITY гранул. Например, если гранус первичного индекса таблицы составляет 8192 строки, а гранулярность индекса — 4, то каждый индексированный "блок" будет состоять из 32768 строк.

Когда пользователь создаёт индекс пропуска данных, в каждой директории части данных таблицы будет два дополнительных файла.

• skp_idx_{index_name}.idx, который содержит упорядоченные значения выражения.
• skp_idx_{index_name}.mrk2, который содержит соответствующие смещения в сопутствующих файлах данных колонки.

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

CREATE TABLE skip_table
(
  my_key UInt64,
  my_value UInt64
)
ENGINE MergeTree primary key my_key
SETTINGS index_granularity=8192;

INSERT INTO skip_table SELECT number, intDiv(number,4096) FROM numbers(100000000);

При выполнении простого запроса, который не использует первичный ключ, сканируются все 100 миллионов записей в колонке my_value:

SELECT * FROM skip_table WHERE my_value IN (125, 700)

┌─my_key─┬─my_value─┐
│ 512000 │      125 │
│ 512001 │      125 │
│    ... |      ... |
└────────┴──────────┘

8192 rows in set. Elapsed: 0.079 sec. Processed 100.00 million rows, 800.10 MB (1.26 billion rows/s., 10.10 GB/s.

Теперь добавим очень простой индекс пропуска:

ALTER TABLE skip_table ADD INDEX vix my_value TYPE set(100) GRANULARITY 2;

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

Чтобы индексировать уже существующие данные, используйте следующую команду:

ALTER TABLE skip_table MATERIALIZE INDEX vix;

Запустите запрос повторно с только что созданным индексом:

SELECT * FROM skip_table WHERE my_value IN (125, 700)

┌─my_key─┬─my_value─┐
│ 512000 │      125 │
│ 512001 │      125 │
│    ... |      ... |
└────────┴──────────┘

8192 rows in set. Elapsed: 0.051 sec. Processed 32.77 thousand rows, 360.45 KB (643.75 thousand rows/s., 7.08 MB/s.)

Вместо обработки 100 миллионов строк объёмом 800 мегабайт ClickHouse обработал и проанализировал только 32768 строк объёмом 360 килобайт — четыре гранулы по 8192 строки каждая.

В более наглядной форме вот как были прочитаны и выбраны 4096 строк с my_value равным 125, и как последующие строки были пропущены без чтения с диска:

Пользователи могут получить подробную информацию о использовании индекса пропуска, включив трассировку при выполнении запросов. Из clickhouse-client установите send_logs_level:

SET send_logs_level='trace';

Это предоставит полезную информацию для отладки при попытке оптимизировать SQL-запрос и индексы таблицы. Из приведенного выше примера журнал отладки показывает, что индекс пропуска исключил все, кроме двух гранул:

<Debug> default.skip_table (933d4b2c-8cea-4bf9-8c93-c56e900eefd1) (SelectExecutor): Index `vix` has dropped 6102/6104 granules.

Типы индексов пропуска

minmax

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

Этот тип индекса работает должным образом только с скалярными или кортежными выражениями — индекс никогда не будет применяться к выражениям, которые возвращают массив или тип данных карты.

set

Этот лёгкий тип индекса принимает один параметр максимального размера набора значений на блок (0 допускает неограниченное количество дискретных значений). Этот набор содержит все значения в блоке (или пуст, если количество значений превышает max_size). Этот тип индекса хорошо работает с колонками с низкой кардинальностью внутри каждого набора гранул (по сути, "сгруппированных вместе"), но с высокой кардинальностью в целом.

Стоимость, производительность и эффективность этого индекса зависят от кардинальности внутри блоков. Если каждый блок содержит значительное количество уникальных значений, либо оценка условия запроса по большому набору индексов будет очень дорогостоящей, либо индекс не будет применён, потому что он пуст из-за превышения max_size.

Типы фильтров Блума

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

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

Существует три типа индексов пропуска данных на основе фильтров Блума:

• Базовый bloom_filter, который принимает один необязательный параметр допустимой "ложной положительной" ставки от 0 до 1 (если не указано, используется .025).

• Специализированный tokenbf_v1. Он принимает три параметра, все связанные с настройкой используемого фильтра Блума: (1) размер фильтра в байтах (большие фильтры имеют меньше ложных положительных срабатываний, но это стоит затрат на хранилище), (2) количество применяемых хеш-функций (опять же, большее количество хеш-фильтров уменьшает ложные положительные срабатывания), и (3) начальное значение для хеш-функций фильтра Блума. Посмотрите калькулятор здесь для более подробной информации о том, как эти параметры влияют на функциональность фильтра Блума. Этот индекс работает только с типами данных String, FixedString и Map. Входное выражение разбивается на последовательности символов, разделенные неалфавитными символами. Например, значение столбца This is a candidate for a "full text" search будет содержать токены This is a candidate for full text search. Он предназначен для использования в поисках LIKE, EQUALS, IN, hasToken() и подобных, для поиска слов и других значений в более длинных строках. Например, одним из возможных применений может быть поиск небольшого количества имён классов или номеров строк в колонке свободных строк журнала приложения.

• Специализированный ngrambf_v1. Этот индекс работает так же, как индекс токенов. Он принимает один дополнительный параметр перед настройками фильтра Блума, размер нграмм для индексации. Нграмма — это строка символов длины n из любых символов, так что строка A short string с размером нграммы 4 будет индексироваться следующим образом:

'A sh', ' sho', 'shor', 'hort', 'ort ', 'rt s', 't st', ' str', 'stri', 'trin', 'ring'

Этот индекс также может быть полезен для текстовых поисков, особенно в языках без разделителей слов, таких как китайский.

Функции индексов пропуска

Основная цель индексов пропуска данных — ограничить количество анализируемых данных популярными запросами. Учитывая аналитическую природу данных ClickHouse, паттерн этих запросов в большинстве случаев включает функциональные выражения. Соответственно, индексы пропуска должны корректно взаимодействовать с общими функциями, чтобы быть эффективными. Это может происходить либо когда:

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

Каждый тип индекса пропуска работает с подмножеством доступных функций ClickHouse, которые подходят для реализации индекса, перечисленных здесь. В общем, индексы set и базовые индексы на основе фильтров Блума (другой тип индекса set) являются неупорядоченными и, следовательно, не работают с диапазонами. В отличие от этого, индексы minmax работают особенно хорошо с диапазонами, поскольку определение того, пересекаются ли диапазоны, происходит очень быстро. Эффективность функций частичного совпадения LIKE, startsWith, endsWith и hasToken зависит от типа использованного индекса, выражения индекса и конкретной структуры данных.

Настройки индексов пропуска

Существуют две доступные настройки, которые применяются к индексам пропуска.

• use_skip_indexes (0 или 1, по умолчанию 1). Не все запросы могут эффективно использовать индексы пропуска. Если конкретное условие фильтрации, вероятно, будет включать большинство гранул, применение индекса пропуска данных несет с собой ненужные, а иногда и значительные затраты. Установите значение 0 для запросов, которые, вероятно, не принесут пользы от каких-либо индексов пропуска.
• force_data_skipping_indices (список имён индексов, разделённых запятыми). Эта настройка может быть использована, чтобы предотвратить некоторые виды неэффективных запросов. В обстоятельствах, когда запрос к таблице слишком дорогостоящий, если не используется индекс пропуска, использование этой настройки с одним или несколькими именами индексов вызовет исключение для любого запроса, который не использует указанный индекс. Это предотвратит потребление ресурсов сервера плохо написанными запросами.

Рекомендации по использованию индексов пропуска

Индексы пропуска не являются интуитивно понятными, особенно для пользователей, привыкших ко вторичным индексам на основе строк из области RDMS или инверсным индексам из документных хранилищ. Чтобы получить какую-либо пользу, применение индекса пропуска данных ClickHouse должно избежать достаточного количества чтений гранул, чтобы компенсировать стоимость вычисления индекса. Критически важно, если значение встречается даже один раз в индексированном блоке, это означает, что нужно считать весь блок в память и оценивать, и затраты на индекс были неоправданно понесены.

Рассмотрим следующее распределение данных:

Предположим, что первичный/порядковый ключ — это timestamp, и существует индекс на visitor_id. Рассмотрим следующий запрос:

SELECT timestamp, url FROM table WHERE visitor_id = 1001`

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

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

В большинстве случаев полезный индекс пропуска требует сильной корреляции между первичным ключом и целевой не первичной колонкой/выражением. Если корреляции нет (как на приведённой выше диаграмме), вероятность того, что условие фильтрации будет выполнено хотя бы для одной строки в блоке из нескольких тысяч значений, высока, и будет пропущено немного блоков. В отличие от этого, если диапазон значений для первичного ключа (например, время суток) сильно ассоциирован со значениями в потенциальной индексной колонке (таких как возраст телезрителей), тогда индекс типа minmax, скорее всего, будет полезным. Обратите внимание, что может быть возможно увеличить эту корреляцию при вставке данных, либо включая дополнительные колонки в ключ сортировки/ORDER BY, либо пакетно вставляя данные таким образом, чтобы значения, связанные с первичным ключом, группировались при вставке. Например, все события для определённого site_id могут быть сгруппированы и вставлены вместе в процессе загрузки, даже если первичный ключ — это временная метка, содержащая события из большого числа сайтов. Это приведет к множеству гранул, содержащих только несколько id сайтов, поэтому множество блоков можно будет пропустить, когда происходит поиск по конкретному значению site_id.

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

Наконец, ключевая рекомендация — тестировать, тестировать и тестировать. Снова, в отличие от вторичных индексов b-дерева или инверсных индексов для поиска документов, поведение индексов пропуска данных не предсказуемо. Добавление их в таблицу несет значительные затраты как на ввод данных, так и на запросы, которые по тем или иным причинам не приносят пользы от индекса. Их всегда следует тестировать на данных реального мира, и тестирование должно включать изменения в типе, размере гранулярности и других параметрах. Тестирование часто выявляет шаблоны и подводные камни, которые не очевидны из мысленных экспериментов.