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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Индексы пропуска не интуитивно понятны, особенно для пользователей, привыкших к вторичным индексам на основе строк из мира РСУБД или инвертированным индексам из документов. Для получения каких-либо преимуществ применение индекса пропуска данных 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-tree или инвертированных индексов для поиска документов, поведение индекса пропуска данных не поддаётся легкому предсказанию. Их добавление в таблицу влечёт за собой значительные затраты как на загрузку данных, так и на запросы, которые по причинам, которые могут оказаться различными, не приносят пользы от индекса. Их всегда следует тестировать на реальных типах данных, а тестирование должно включать различные варианты типа, размера гранулярности и других параметров. Тестирование часто показывает образцы и проблемы, которые не очевидны только из теоретических экспериментов.