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

Введение

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

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

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

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

Основная работа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

minmax

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

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

set

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

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

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

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

Поскольку фильтры Блума могут более эффективно обрабатывать тестирование для большого количества дискретных значений, они могут быть уместны для условных выражений, которые выдают больше значений для тестирования. В частности, индекс фильтра Блума может применяться к массивам, где каждая величина массива тестируется, и к картам, преобразуя либо ключи, либо значения в массив с использованием функций 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-грамм для индексации. N-грамма — это строка длиной n любых символов, поэтому строка A short string с размером n-грамм 4 будет индексироваться как:

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

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

Основная цель индексов пропуска данных — ограничить количество данных, анализируемых популярными запросами. Учитывая аналитический характер данных 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. Рассмотрим следующий запрос:

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

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

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

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

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