Практическое введение в первичные индексы в ClickHouse

Введение

В этом руководстве мы подробно рассмотрим индексацию ClickHouse. Мы подробно иллюстрируем и обсуждаем:

• чем индексация в ClickHouse отличается от традиционных систем управления реляционными базами данных
• как ClickHouse создает и использует разреженный первичный индекс таблицы
• какие лучшие практики существуют для индексации в ClickHouse

Вы можете по желанию самостоятельно выполнять все SQL-операторы и запросы ClickHouse, приведённые в этом руководстве на вашем собственном компьютере. Для установки ClickHouse и начала работы см. Quick Start.

примечание

Это руководство фокусируется на разрежённых первичных индексах ClickHouse.

Для ClickHouse вторичных индексов пропуска данных, см. Учебное пособие.

Набор данных

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

• Мы будем использовать подмножество из 8,87 миллионов строк (событий) из образца данных.
• Неразжатый размер данных составляет 8,87 миллионов событий и около 700 МБ. При хранении в ClickHouse это сжимается до 200 МБ.
• В нашем подмножестве каждая строка содержит три столбца, указывающих на интернет-пользователя (столбец UserID), который кликнул по URL (URL столбец) в определенное время (EventTime столбец).

С этими тремя столбцами мы уже можем сформулировать некоторые типичные запросы веб-аналитики, такие как:

• "Каковы топ 10 самых кликабельных URL для конкретного пользователя?"
• "Каковы топ 10 пользователей, которые чаще всего кликают по определенному URL?"
• "Какое самое популярное время (например, дни недели), когда пользователь кликает по конкретному URL?"

Тестовая машина

Все данные о времени выполнения, приведённые в этом документе, основаны на запуске ClickHouse 22.2.1 локально на MacBook Pro с чипом Apple M1 Pro и 16 ГБ ОЗУ.

Полное сканирование таблицы

Чтобы увидеть, как запрос выполняется над нашим набором данных без первичного ключа, мы создаём таблицу (с движком таблицы MergeTree), выполняя следующий SQL-оператор DDL:

Затем вставьте подмножество набора данных hits в таблицу с помощью следующего SQL-оператора вставки. Это используется табличная функция URL, чтобы загрузить подмножество полного набора данных, размещённых удалённо на clickhouse.com:

Ответ:

Вывод результата клиента ClickHouse показывает нам, что оператор выше вставил 8,87 миллионов строк в таблицу.

Наконец, чтобы упростить обсуждение в дальнейшем в этом руководстве и сделать диаграммы и результаты воспроизводимыми, мы оптимизируем таблицу, используя ключевое слово FINAL:

примечание

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

Теперь мы выполняем наш первый запрос веб-аналитики. Следующий запрос вычисляет топ 10 самых кликабельных URL для интернет-пользователя с UserID 749927693:

Ответ на запрос:

Вывод результата клиента ClickHouse указывает на то, что ClickHouse выполнил полное сканирование таблицы! Каждая строка из 8,87 миллионов строк нашей таблицы была передана в ClickHouse. Это не масштабируется.

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

Связанный контент

• Блог: Ускорение запросов ClickHouse

Дизайн индексов ClickHouse

Дизайн индекса для массовых объемов данных

В традиционных системах управления реляционными базами данных первичный индекс содержал бы одну запись на строку таблицы. Это привело бы к тому, что первичный индекс содержал бы 8,87 миллионов записей для нашего набора данных. Такой индекс позволяет быстро находить конкретные строки, обеспечивая высокую эффективность для запросов поиска и обновления точек. Поиск записи в структуре данных B(+)-Tree имеет среднюю временную сложность O(log n); более точно, log_b n = log_2 n / log_2 b, где b - это коэффициент разветвления B(+)-Tree, а n - количество индексированных строк. Поскольку b обычно составляет от нескольких сотен до нескольких тысяч, B(+)-Tree представляют собой очень мелкие структуры, и для поиска записей требуется минимальное количество запросов к диску. С 8,87 миллионами строк и коэффициентом разветвления 1000 в среднем требуется 2,3 запроса к диску. Эта возможность сопровождается издержками: дополнительными накладными расходами на диск и память, более высокими затратами на вставку при добавлении новых строк в таблицу и записи в индекс, а также иногда ребалансировкой B-Tree.

Учитывая проблемы, связанные с индексами B-Tree, движки таблиц в ClickHouse используют иной подход. Семейство движков MergeTree в ClickHouse было разработано и оптимизировано для обработки огромных объемов данных. Эти таблицы предназначены для приёма миллионов вставок строк в секунду и хранения очень больших (сотни петабайт) объемов данных. Данные быстро записываются в таблицу по частям с применением правил для слияния частей в фоновом режиме. В ClickHouse каждая часть имеет собственный первичный индекс. Когда части объединяются, также объединяются и их первичные индексы. На очень большом масштабе, для которого разработан ClickHouse, крайне важно быть очень эффективным с точки зрения использования диска и памяти. Поэтому вместо индексирования каждой строки, первичный индекс для части имеет одну запись индекса (называемую 'меткой') на группу строк (называемую 'гранулой') - этот метод называется разреженный индекс.

Разреженный индекс возможен, потому что ClickHouse сохраняет строки для части на диске в порядке первичных ключевых столбцов. Вместо того, чтобы напрямую находить отдельные строки (как делает индекс на основе B-Tree), разреженный первичный индекс позволяет быстро (путём бинарного поиска по записям индекса) определить группы строк, которые могут соответствовать запросу. Обнаруженные группы потенциально соответствующих строк (гранулы) затем параллельно передаются в движок ClickHouse для поиска совпадений. Такая конструкция индекса позволяет сделать первичный индекс небольшим (он может и должен полностью умещаться в основной памяти), при этом значительно ускоряя время выполнения запросов: особенно для запросов диапазона, характерных для случаев использования аналитики данных.

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

Таблица с первичным ключом

Создайте таблицу с составным первичным ключом, использующим столбцы UserID и URL:

Подробности оператора DDL

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

• Задает составной ключ сортировки для таблицы через оператор ORDER BY.

• Явно контролирует количество записей индекса, которые будет иметь первичный индекс, через настройки:

  • index_granularity: явно установлен в его значение по умолчанию 8192. Это означает, что для каждой группы из 8192 строк первичный индекс будет иметь одну запись. Например, если таблица содержит 16384 строки, индекс будет иметь две записи.

  • index_granularity_bytes: установлено значение 0 для отключения адаптивной гранулярности индекса. Адаптивная гранулярность индекса означает, что ClickHouse автоматически создаёт одну запись для группы из n строк, если верно одно из следующих условий:

    • Если n меньше 8192 и размер данных строки для этих n строк больше или равен 10 МБ (значение по умолчанию для index_granularity_bytes).

    • Если размер данных строки для n строк меньше 10 МБ, но n равно 8192.

  • compress_primary_key: установлено значение 0 для отключения сжатия первичного индекса. Это позволит нам, при желании, осмотреть его содержимое позже.

Первичный ключ в операторе DDL, приведённом выше, приводит к созданию первичного индекса на основе двух указанных столбцов ключей.

Затем вставьте данные:

Ответ выглядит так:

И оптимизируйте таблицу:

Мы можем использовать следующий запрос для получения метаданных о нашей таблице:

Ответ:

Вывод клиента ClickHouse показывает:

• Данные таблицы хранятся в широком формате в определенной директории на диске, что означает, что внутри этой директории будет один файл данных (и один файл меток) на каждый столбец таблицы.
• Таблица содержит 8,87 миллионов строк.
• Неразжатый размер данных всех строк вместе составляет 733,28 МБ.
• Сжатый размер на диске всех строк вместе составляет 206,94 МБ.
• Таблица имеет первичный индекс с 1083 записями (называемыми "метками"), и размер индекса составляет 96,93 КБ.
• В общей сложности данные таблицы и файлы меток и файл первичного индекса вместе занимают 207,07 МБ на диске.

Данные хранятся на диске, упорядоченные по столбцам первичного ключа

Наша таблица, которую мы создали выше имеет:

• составной первичный ключ (UserID, URL) и
• составной ключ сортировки (UserID, URL, EventTime).

примечание

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

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

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

• Первичный ключ должен быть префиксом ключа сортировки, если оба указаны.

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

примечание

ClickHouse позволяет вставлять несколько строк с одинаковыми значениями столбцов первичного ключа. В этом случае (см. строчку 1 и строчку 2 на диаграмме ниже), окончательный порядок определяется указанным ключом сортировки и, следовательно, значением столбца EventTime.

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

• для представления на диске существует один файл данных (*.bin) на каждый столбец таблицы, где все значения для этого столбца хранятся в сжатом формате, и
• 8,87 миллионов строк хранятся на диске в лексикографическом порядке по возрастанию по столбцам первичного ключа (и дополнительным столбцам ключа сортировки), то есть в этом случае:
  • сначала по UserID,
  • затем по URL,
  • и, наконец, по EventTime:

UserID.bin, URL.bin, и EventTime.bin - это файлы данных на диске, где хранятся значения столбцов UserID, URL и EventTime.

примечание

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

• Мы начинаем нумерацию строк с 0, чтобы быть в соответствии с внутренней системой нумерации строк ClickHouse, которая также используется для сообщений журнала.

Данные организованы в гранулы для параллельной обработки данных

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

примечание

Значения столбцов не хранятся физически внутри гранул: гранулы — это всего лишь логическая организация значений столбцов для обработки запросов.

На следующей диаграмме показано, как (значения столбцов) 8,87 миллионов строк нашей таблицы организованы в 1083 гранулы в результате того, что в операторе DDL таблицы указана настройка index_granularity (установленная по умолчанию на значение 8192).

Первые (по физическому порядку на диске) 8192 строки (их значения столбцов) логически принадлежат грануле 0, затем следующие 8192 строки (их значения столбцов) принадлежат грануле 1 и так далее.

примечание

• Последняя гранула (гранула 1082) "содержит" менее 8192 строк.

• Мы упомянули в начале этого руководства в разделе "Детали оператора DDL", что мы отключили адаптивную гранулярность индекса (чтобы упростить обсуждение в этом руководстве, а также сделать диаграммы и результаты воспроизводимыми).

  Поэтому все гранулы (кроме последней) нашей примерной таблицы имеют одинаковый размер.

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

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

• Мы начинаем нумерацию гранул с 0, чтобы быть в соответствии с внутренней системой нумерации ClickHouse, которая также используется для сообщений журнала.

Первичный индекс имеет одну запись на каждую гранулу

Первичный индекс создаётся на основе гранул, показанных на диаграмме выше. Этот индекс — это несжатый плоский файл массива (primary.idx), содержащий так называемые числовые метки индекса, начиная с 0.

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

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

Всего индекс имеет 1083 записи для нашей таблицы с 8.87 миллионами строк и 1083 гранулами:

примечание

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

• Файл первичного индекса полностью загружается в основную память. Если файл больше доступного свободного пространства памяти, то ClickHouse выдаст ошибку.

Изучение содержимого первичного индекса

В самоуправляемом кластерe ClickHouse мы можем использовать табличную функцию file для изучения содержимого первичного индекса нашей таблицы-примера.

Для этого сначала необходимо скопировать файл первичного индекса в user_files_path узла из работающего кластера:

• Шаг 1: Получить часть пути, содержащую файл первичного индекса
SELECT path FROM system.parts WHERE table = 'hits_UserID_URL' AND active = 1

возвращает /Users/tomschreiber/Clickhouse/store/85f/85f4ee68-6e28-4f08-98b1-7d8affa1d88c/all_1_9_4 на тестовой машине.

• Шаг 2: Получить user_files_path
Путь по умолчанию для user_files_path в Linux: /var/lib/clickhouse/user_files/

и в Linux вы можете проверить, изменился ли он: $ grep user_files_path /etc/clickhouse-server/config.xml

На тестовой машине путь: /Users/tomschreiber/Clickhouse/user_files/

• Шаг 3: Скопировать файл первичного индекса в user_files_path

cp /Users/tomschreiber/Clickhouse/store/85f/85f4ee68-6e28-4f08-98b1-7d8affa1d88c/all_1_9_4/primary.idx /Users/tomschreiber/Clickhouse/user_files/primary-hits_UserID_URL.idx

Теперь можно изучить содержимое первичного индекса через SQL:

• Получить количество записей
SELECT count( )<br/>FROM file('primary-hits_UserID_URL.idx', 'RowBinary', 'UserID UInt32, URL String'); возвращает 1083
• Получить первые две метки индекса
SELECT UserID, URL<br/>FROM file('primary-hits_UserID_URL.idx', 'RowBinary', 'UserID UInt32, URL String')<br/>LIMIT 0, 2;

возвращает

240923, http://showtopics.html%3...<br/> 4073710, http://mk.ru&pos=3_0

• Получить последнюю метку индекса
SELECT UserID, URL FROM file('primary-hits_UserID_URL.idx', 'RowBinary', 'UserID UInt32, URL String')<br/>LIMIT 1082, 1; возвращает 4292714039 │ http://sosyal-mansetleri...

Это точно соответствует нашей диаграмме содержимого первичного индекса для нашей таблицы-примера:

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

• Метки индекса UserID:

  Сохраняемые значения UserID в первичном индексе отсортированы в порядке возрастания.
  'метка 1' на диаграмме выше, таким образом, указывает, что значения UserID всех строк таблицы в грануле 1 и во всех последующих гранулах гарантированно больше или равны 4.073.710.

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

• Метки индекса URL:

  Довольно схожая кардинальность столбцов первичного ключа UserID и URL означает, что метки индекса для всех столбцов ключа после первого столбца в общем случае лишь указывают диапазон данных, пока значение столбца ключа-предшественника остаётся одинаковым для всех строк таблицы как минимум в пределах текущей гранулы.
  Например, поскольку значения UserID для меток 0 и 1 различаются на диаграмме выше, ClickHouse не может предположить, что все значения URL всех строк таблицы в грануле 0 больше или равны 'http://showtopics.html%3...'. Однако, если бы значения UserID для меток 0 и 1 были одинаковыми на диаграмме выше (что означает, что значение UserID остаётся одинаковым для всех строк таблицы в пределах гранулы 0), ClickHouse мог бы предположить, что все значения URL всех строк таблицы в грануле 0 больше или равны 'http://showtopics.html%3...'.

  Мы обсудим последствия этого на производительности выполнения запросов более подробно позже.

Первичный индекс используется для выбора гранул

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

Следующий запрос вычисляет топ 10 самых часто кликаемых URL для UserID 749927693.

Результат:

Вывод для клиента ClickHouse теперь показывает, что вместо выполнения полного сканирования таблицы было обработано только 8.19 тысяч строк.

Если трассировка логов включена, то файл логов сервера ClickHouse показывает, что ClickHouse выполнял бинарный поиск среди 1083 меток индекса UserID, чтобы определить гранулы, которые могут содержать строки со значением столбца UserID 749927693. Это требует 19 шагов со средней временной сложностью O(log2 n):

Мы видим в трассировке лога выше, что одна метка из 1083 существующих меток удовлетворяет запросу.

Подробности логов трассировки

Была идентифицирована метка 176 (найденная левая граница метки является включающей, найденная правая граница метки является исключающей), и поэтому все 8192 строки из гранулы 176 (которая начинается с строки 1.441.792 - мы увидим это позже в этом руководстве) затем подаются в ClickHouse для поиска действительных строк со значением столбца UserID 749927693.

Мы также можем воспроизвести это, используя предложение EXPLAIN в нашем примере запроса:

Ответ выглядит следующим образом:

Вывод для клиента показывает, что одна из 1083 гранул была выбрана как возможный источник строк со значением столбца UserID 749927693.

Заключение

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

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

Это первый этап (выбор гранул) выполнения запроса в ClickHouse.

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

Мы обсудим этот второй этап более подробно в следующем разделе.

Файлы меток используются для определения местоположения гранул

Следующая диаграмма иллюстрирует часть файла первичного индекса для нашей таблицы.

Как обсуждалось выше, в результате бинарного поиска по 1083 меткам индекса UserID была выбрана метка 176. Её соответствующая гранула 176 может содержать строки со значением столбца UserID 749.927.693.

Подробности выбора гранулы

Диаграмма выше показывает, что метка 176 — это первая запись индекса, где как минимум значение UserID ассоциированной гранулы 176 меньше, чем 749.927.693, и минимальное значение UserID для гранулы 177 для следующей метки (метка 177) больше, чем это значение. Поэтому только соответствующая гранула 176 для метки 176 может содержать строки со значением столбца UserID 749.927.693.

Чтобы подтвердить (или опровергнуть), что какие-то строки в грануле 176 содержат значение столбца UserID 749.927.693, все 8192 строки, принадлежащие этой грануле, нужно передать в ClickHouse.

Для этого ClickHouse необходимо знать физическое местоположение гранулы 176.

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

Следующая диаграмма показывает три файла меток UserID.mrk, URL.mrk и EventTime.mrk, которые хранят физические местоположения гранул для столбцов UserID, URL и EventTime таблицы.

Мы обсудили, что первичный индекс — это плоский несжатый файл массива (primary.idx), содержащий метки индекса, которые нумеруются, начиная с 0.

Аналогично, файл меток также является плоским несжатым файлом массива (*.mrk), содержащим метки, которые нумеруются, начиная с 0.

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

Каждая запись файла меток для конкретного столбца хранит два местоположения в виде смещений:

• Первое смещение ('block_offset' на диаграмме выше) находит блок в файле данных сжатого столбца, который содержит сжатую версию выбранной гранулы. Этот сжатый блок потенциально содержит несколько сжатых гранул. На чтение расположенный сжатый блок файла распаковывается в основную память.

• Второе смещение ('granule_offset' на диаграмме выше) из файла меток предоставляет местоположение гранулы в данных распакованного блока.

Все 8192 строки, принадлежащие найденной распакованной грануле, затем передаются в ClickHouse для дальнейшей обработки.

примечание

• Для таблиц с широким форматом и без адаптивной гранулярности индекса ClickHouse использует файлы меток .mrk так, как показано выше, которые содержат записи с двумя 8-байтными адресами на запись. Эти записи являются физическими местоположениями гранул однотипного размера.

Гранулярность индекса по умолчанию является адаптивной по умолчанию, но для нашей таблицы-примера мы отключили адаптивную гранулярность индекса (чтобы упростить обсуждение в данном руководстве, а также сделать диаграммы и результаты воспроизводимыми). Наша таблица использует широкий формат, потому что размер данных больше, чем min_bytes_for_wide_part (который по умолчанию составляет 10 МБ для самоуправляемых кластеров).

• Для таблиц с широким форматом и с адаптивной гранулярностью индекса ClickHouse использует файлы меток .mrk2, которые содержат подобные записи файлов меток .mrk, но с дополнительным третьим значением на запись: количество строк в грануле, к которой относится запись.

• Для таблиц с компактным форматом ClickHouse использует файлы меток .mrk3.

Почему файлы меток

Почему первичный индекс не содержит напрямую физические местоположения гранул, соответствующих меткам индекса?

Поскольку в очень крупных масштабах, для которых разработан ClickHouse, важно быть очень эффективным с точки зрения использования диска и памяти.

Файл первичного индекса должен помещаться в основную память.

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

Кроме того, эта информация о смещении нужна только для столбцов UserID и URL.

Информация о смещении не нужна для столбцов, которые не используются в запросе, например, EventTime.

Для нашего примера запроса ClickHouse нужны только два смещения физического местоположения для гранулы 176 в файле данных UserID (UserID.bin) и два смещения физического местоположения для гранулы 176 в файле данных URL (URL.bin).

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

Следующая диаграмма и текст ниже иллюстрируют, как для нашего примера запроса ClickHouse находит гранулу 176 в файле данных UserID.bin.

Мы обсуждали ранее в данном руководстве, что ClickHouse выбрал метку первичного индекса 176 и, следовательно, гранулу 176 как потенциально содержащую соответствующие строки для нашего запроса.

Теперь ClickHouse использует выбранный номер метки (176) из индекса для поиска в массиве позиции в файле меток UserID.mrk, чтобы получить два смещения для определения местоположения гранулы 176.

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

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

ClickHouse необходимо определить местоположение (и передать все значения) гранулы 176 как из файла данных UserID.bin, так и из файла данных URL.bin, чтобы выполнить наш пример запроса (топ 10 самых кликаемых URL для интернет-пользователя с UserID 749.927.693).

Диаграмма выше показывает, как ClickHouse находит гранулу для файла данных UserID.bin.

Параллельно ClickHouse делает то же самое для гранулы 176 для файла данных URL.bin. Две соответствующие гранулы выравниваются и передаются в движок ClickHouse для дальнейшей обработки, то есть для агрегации и подсчёта значений URL для каждой группы для всех строк, где UserID равен 749.927.693, перед окончательным выводом 10 наибольших групп URL в нисходящем порядке по количеству.

Использование нескольких первичных индексов

Вторичные столбцы ключа могут быть (не)эффективными

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

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

примечание

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

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

Мы используем запрос, который вычисляет топ 10 пользователей, которые чаще всего кликали по URL "http://public_search":

Ответ:

Вывод клиента указывает на то, что ClickHouse почти выполнил полное сканирование таблицы, несмотря на то, что столбец URL является частью составного первичного ключа! ClickHouse считал 8.81 миллиона строк из 8.87 миллионов строк таблицы.

Если trace_logging включен, то файл логов сервера ClickHouse показывает, что ClickHouse использовал генерический алгоритм поиска исключений среди 1083 меток индекса URL, чтобы определить те гранулы, которые могут содержать строки со значением столбца URL "http://public_search":

Мы можем видеть в примере трассировки выше, что 1076 (через метки) из 1083 гранул были выбраны как потенциально содержащие строки с совпадающим значением URL.

Это приводит к тому, что 8.81 миллиона строк передаются в движок ClickHouse (параллельно, используя 10 потоков), чтобы найти строки, которые действительно содержат значение URL "http://public_search".

Однако, как мы увидим позже, только 39 гранул из выбранных 1076 гранул действительно содержат совпадающие строки.

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

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

Для иллюстрации этого приведём некоторые детали о том, как работает алгоритм генерического поиска исключений.

Алгоритм генерического поиска исключений

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

В качестве примера для обоих случаев мы предположим:

• запрос, который ищет строки со значением URL = "W3".
• абстрактную версию нашей таблицы хитов с упрощёнными значениями для UserID и URL.
• тот же составной первичный ключ (UserID, URL) для индекса. Это означает, что строки сначала упорядочены по значениям UserID. Строки с одинаковым значением UserID затем упорядочены по URL.
• размер гранулы равен двум, то есть каждая гранула содержит две строки.

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

Столбец ключа-предшественника имеет низкую(ую) кардинальность

Предположим, что UserID имеет низкую кардинальность. В этом случае вероятно, что одно и то же значение UserID распределено по нескольким строкам таблицы и гранулам, и, следовательно, метки индекса. Для меток индекса с одинаковым UserID значения URL для меток индекса отсортированы в порядке возрастания (поскольку строки таблицы упорядочены сначала по UserID, а затем по URL). Это позволяет эффективную фильтрацию, как описано ниже:

Есть три различных сценария для процесса выбора гранулы для нашего абстрактного примера данных на диаграмме выше:

1. Метка индекса 0, для которой значение URL меньше, чем W3, и для которой значение URL следующей по порядку метки индекса также меньше, чем W3, может быть исключена, потому что метки 0 и 1 имеют одно и то же значение UserID. Обратите внимание, что это условие исключения гарантирует, что гранула 0 полностью состоит из значений UserID U1, так что ClickHouse может предположить, что также и максимальное значение URL в грануле 0 меньше, чем W3, и исключить гранулу.

2. Метка индекса 1, для которой значение URL меньше (или равно) W3, и для которой значение URL следующей по порядку метки индекса больше (или равно) W3, выбирается, потому что это означает, что гранула 1 может содержать строки с URL W3.

3. Метки индекса 2 и 3, для которых значение URL больше, чем W3, могут быть исключены, поскольку метки индекса в первичном индексе хранят значения столбцов ключа для первой строки таблицы для каждой гранулы, а строки таблицы отсортированы на диске по значениям столбцов ключа, поэтому гранулы 2 и 3 не могут содержать значение URL W3.

Столбец ключа-предшественника имеет высокую(ую) кардинальность

Когда у UserID высокая кардинальность, маловероятно, что одно и то же значение UserID распределено по нескольким строкам таблицы и гранулам. Это означает, что значения URL для меток индекса не монотонно возрастают:

Как мы можем видеть на диаграмме выше, все показанные метки, значения URL которых меньше, чем W3, выбираются для передачи строк их соответствующих гранул в движок ClickHouse.

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

Например, рассмотрим метку индекса 0, для которой значение URL меньше, чем W3, и для которой значение URL следующей по порядку метки индекса также меньше, чем W3. Это исключение не может быть применено, потому что следующая по порядку метка индекса 1 не имеет того же значения UserID, что и текущая метка 0.

Это в конечном итоге препятствует ClickHouse делать предположения о максимальном значении URL в грануле 0. Вместо этого оно должно предположить, что гранула 0 может содержать строки со значением URL W3 и вынужденный выбрать метку 0.

Такая же ситуация применима для меток 1, 2 и 3.

Заключение

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

В нашей выборке данных для обоих столбцов ключа (UserID, URL) имеется схожая высокая кардинальность, и, как объяснено, алгоритм генерического поиска исключений не очень эффективен, когда у столбца ключа-предшественника для столбца URL высокая(ая) или схожая кардинальность.

Примечание об индексе пропуска данных

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

Например, эти два оператора создают и заполняют индекс пропуска данных типа minmax по столбцу URL нашей таблицы:

ClickHouse теперь создал дополнительный индекс, который хранит - для группы из 4 последовательных гранул (обратите внимание на GRANULARITY 4 в операторе ALTER TABLE выше) - минимальное и максимальное значение URL:

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

Вторая запись индекса ('метка 1') хранит минимальные и максимальные значения URL для строк, относящихся к следующим 4 гранулам нашей таблицы, и так далее.

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

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

Конкретное значение URL, которое ищет запрос (например, 'http://public_search'), с большой вероятностью находится между минимальным и максимальным значением, хранимым индексом для каждой группы гранул, в результате чего ClickHouse вынужден выбирать группу гранул (так как они могут содержать строку или строки, соответствующие запросу).

Необходимость использования нескольких первичных индексов

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

Если, кроме того, мы хотим сохранить хорошую производительность нашего примера запроса, который фильтрует строки по конкретному UserID, тогда нам нужно использовать несколько первичных индексов.

Ниже приведены способы достижения этой цели.

Варианты создания дополнительных первичных индексов

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

• Создать вторую таблицу с другим первичным ключом.
• Создать материализованное представление на нашей существующей таблице.
• Добавить проекцию к нашей существующей таблице.

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

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

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

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

А проекция является самым прозрачным вариантом, так как помимо автоматической синхронизации созданной (и скрытой) дополнительной таблицы с изменениями данных, ClickHouse автоматически выбирает наиболее эффективную версию таблицы для запросов:

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

Вариант 1: Вторичные таблицы

Мы создаем новую дополнительную таблицу, в которой меняем порядок столбцов ключа (по сравнению с нашей исходной таблицей) в первичном ключе:

Вставьте все 8.87 миллионов строк из нашей исходной таблицы в дополнительную таблицу:

Ответ будет таким:

И, наконец, оптимизируйте таблицу:

Поскольку мы изменили порядок столбцов в первичном ключе, вставленные строки теперь хранятся на диске в другом лексикографическом порядке (по сравнению с нашей исходной таблицей), и поэтому также 1083 гранулы этой таблицы содержат другие значения, чем раньше:

Это результативный первичный ключ:

Который теперь можно использовать для значительного ускорения выполнения нашего примерного запроса с фильтрацией по столбцу URL для вычисления топ-10 пользователей, которые чаще всего кликают на URL "http://public_search":

Ответ будет:

Теперь, вместо почти полного сканирования таблицы, ClickHouse выполнил этот запрос намного эффективнее.

С первичным индексом из исходной таблицы, где UserID был первым, а URL вторым столбцом ключа, ClickHouse использовал алгоритм поиска исключений общего вида по меткам индекса для выполнения этого запроса, и это было не очень эффективно из-за одинаково высокой кардинальности UserID и URL.

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

ClickHouse выбрал только 39 меток индекса вместо 1076, когда использовался общий поиск исключений.

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

Аналогично плохой производительности этого запроса с нашей исходной таблицей, наш пример запроса с фильтрацией по UserID не будет выполнен очень эффективно с новой дополнительной таблицей, потому что UserID теперь второй столбец ключа в первичном индексе этой таблицы, и поэтому ClickHouse будет использовать общий поиск исключений для выбора гранул, который не очень эффективен при одинаково высокой кардинальности UserID и URL. Раскройте поле для деталей.

Запрос с фильтрацией по UserID теперь имеет плохую производительность

Ответ будет:

Журнал сервера:

Теперь у нас есть две таблицы. Оптимизированы для ускорения запросов с фильтрацией по UserID и ускорения запросов с фильтрацией по URL соответственно:

Вариант 2: Материализованные представления

Создайте материализованное представление на нашей существующей таблице.

Ответ будет таким:

примечание

• мы меняем порядок столбцов ключа (по сравнению с нашей исходной таблицей) в первичном ключе представления
• материализованное представление поддерживается неявно созданной таблицей, порядок строк и первичный индекс которой основаны на заданном определении первичного ключа
• неявно созданная таблица перечисляется запросом SHOW TABLES и имеет имя, начинающееся с .inner
• также возможно сначала явно создать поддерживающую таблицу для материализованного представления, и затем представление может быть направлено на эту таблицу с помощью TO [db].[table] оператор
• мы используем ключевое слово POPULATE, чтобы немедленно заполнить неявно созданную таблицу всеми 8.87 миллионами строк из исходной таблицы hits_UserID_URL
• если новые строки вставляются в исходную таблицу hits_UserID_URL, то эти строки автоматически также вставляются в неявно созданную таблицу
• фактически неявно созданная таблица имеет тот же порядок строк и первичный индекс, что и вторичная таблица, которую мы создали явно:

ClickHouse хранит файлы данных столбца (.bin), файлы меток (.mrk2) и первичный индекс (primary.idx) неявно созданной таблицы в специальной папке в каталоге данных сервера ClickHouse:

Неявно созданная таблица (и ее первичный индекс), поддерживающая материализованное представление, теперь может использоваться для значительного ускорения выполнения нашего примера запроса с фильтрацией по столбцу URL:

Ответ будет:

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

Соответствующий трассировочный лог в файле журнала сервера ClickHouse подтверждает, что ClickHouse выполняет бинарный поиск по меткам индекса:

Вариант 3: Проекции

Создайте проекцию на нашей существующей таблице:

И материализуйте проекцию:

примечание

• проекция создаёт скрытую таблицу, порядок строк и первичный индекс которой основаны на заданной инструкции ORDER BY проекции
• скрытая таблица не отображается в результате выполнения запроса SHOW TABLES
• мы используем ключевое слово MATERIALIZE, чтобы немедленно заполнить скрытую таблицу всеми 8.87 миллионами строк из исходной таблицы hits_UserID_URL
• если новые строки вставляются в исходную таблицу hits_UserID_URL, то такие строки автоматически также вставляются в скрытую таблицу
• запрос всегда (синтаксически) нацелен на исходную таблицу hits_UserID_URL, но если порядок строк и первичный индекс скрытой таблицы позволяют выполнить запрос более эффективно, то будет использована эта скрытая таблица
• пожалуйста, обратите внимание, что проекции не делают запросы, использующие ORDER BY, более эффективными, даже если ORDER BY соответствует инструкциям ORDER BY проекции (см. https://github.com/ClickHouse/ClickHouse/issues/47333)
• фактически неявно созданная скрытая таблица имеет тот же порядок строк и первичный индекс, что и вторичная таблица, которую мы создали явно:

ClickHouse хранит файлы данных столбца (.bin), файлы меток (.mrk2) и первичный индекс (primary.idx) скрытой таблицы в специальной папке (отмеченной оранжевым на скриншоте ниже) рядом с файлами данных источника таблицы, файлами меток и файлами первичного индекса:

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

Ответ будет:

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

Соответствующий трассировочный лог в файле журнала сервера ClickHouse подтверждает, что ClickHouse выполняет бинарный поиск по меткам индекса:

Резюме

Первичный индекс нашей таблицы с составным первичным ключом (UserID, URL) был очень полезен для ускорения запроса с фильтрацией по UserID. Но этот индекс не предоставил значительной помощи в ускорении запроса с фильтрацией по URL, несмотря на то, что столбец URL является частью составного первичного ключа.

И наоборот: Первичный индекс нашей таблицы с составным первичным ключом (URL, UserID) ускорял запрос с фильтрацией по URL, но не предоставил большой поддержки запросу с фильтрацией по UserID.

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

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

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

Чем выше разница в кардинальности между столбцами ключа, тем больше имеет значение порядок этих столбцов в ключе. Мы продемонстрируем это в следующем разделе.

Эффективный порядок столбцов ключа

В составном первичном ключе порядок столбцов ключа может существенно влиять как на:

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

Чтобы продемонстрировать это, мы используем версию нашего набор веб-трафика, где каждая строка содержит три столбца, указывающих, был ли доступ по Интернету 'пользователя' (столбец UserID) к URL (столбец URL) отмечен как трафик ботов (столбец IsRobot).

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

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

Мы используем этот запрос для вычисления кардинальностей трех столбцов, которые мы хотим использовать в качестве столбцов ключа в составном первичном ключе (обратите внимание, что мы используем табличную функцию URL, чтобы запрашивать данные TSV с использованием гибкого подхода без необходимости создания локальной таблицы). Выполните этот запрос в clickhouse client:

Ответ будет:

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

Чтобы продемонстрировать это, мы создаем две версии таблицы для наших данных анализа трафика ботов:

• таблица hits_URL_UserID_IsRobot с составным первичным ключом (URL, UserID, IsRobot), где мы упорядочиваем столбцы ключа по кардинальности в порядке убывания
• таблица hits_IsRobot_UserID_URL с составным первичным ключом (IsRobot, UserID, URL), где мы упорядочиваем столбцы ключа по кардинальности в порядке возрастания

Создайте таблицу hits_URL_UserID_IsRobot с составным первичным ключом (URL, UserID, IsRobot):

И заполните её 8.87 миллиона строк:

Это ответ:

Далее, создайте таблицу hits_IsRobot_UserID_URL с составным первичным ключом (IsRobot, UserID, URL):

И заполните её теми же 8.87 миллионами строк, которые мы использовали для заполнения предыдущей таблицы:

Ответ будет:

Эффективная фильтрация по вторичным столбцам ключа

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

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

Для второго случая порядок столбцов ключа в составном первичном ключе имеет значение для эффективности алгоритма поиска исключений общего вида.

Это запрос, который фильтруется по столбцу UserID таблицы, где мы упорядочили столбцы ключа (URL, UserID, IsRobot) по кардинальности в порядке убывания:

Ответ будет:

Это тот же запрос на таблице, где мы упорядочили столбцы ключа (IsRobot, UserID, URL) по кардинальности в порядке возрастания:

Ответ будет:

Мы видим, что выполнение запроса значительно более эффективно и быстрее на таблице, где мы упорядочили столбцы ключа по кардинальности в порядке возрастания.

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

Оптимальное соотношение сжатия файлов данных

Этот запрос сравнивает коэффициент сжатия столбца UserID между двумя таблицами, которые мы создали выше:

Это ответ:

Мы можем видеть, что коэффициент сжатия для столбца UserID значительно выше для таблицы, где мы упорядочили ключевые столбцы (IsRobot, UserID, URL) по кардинальности в возрастающем порядке.

Хотя в обеих таблицах хранится совершенно одинаковые данные (мы вставили одинаковые 8,87 миллиона строк в обе таблицы), порядок ключевых столбцов в составном первичном ключе имеет значительное влияние на то, сколько дискового пространства требуется для сжатых данных в файлах данных столбца таблицы:

• в таблице hits_URL_UserID_IsRobot с составным первичным ключом (URL, UserID, IsRobot), где мы упорядочили ключевые столбцы по кардинальности в убывающем порядке, файл данных UserID.bin занимает 11.24 MiB дискового пространства
• в таблице hits_IsRobot_UserID_URL с составным первичным ключом (IsRobot, UserID, URL), где мы упорядочили ключевые столбцы по кардинальности в возрастающем порядке, файл данных UserID.bin занимает только 877.47 KiB дискового пространства

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

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

Диаграмма ниже показывает порядок строк на диске для первичного ключа, где ключевые столбцы упорядочены по кардинальности в возрастающем порядке:

Мы обсудили, что данные строк таблицы хранятся на диске, упорядоченные по столбцам первичного ключа.

На диаграмме выше строки таблицы (их значения столбцов на диске) сначала упорядочены по значению cl, и строки с одинаковым значением cl упорядочены по значению ch. И поскольку первый ключевой столбец cl имеет низкую кардинальность, вероятно, что существуют строки с одинаковым значением cl. Из-за этого также вероятно, что значения ch упорядочены (локально — для строк с одинаковым значением cl).

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

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

Теперь строки таблицы сначала упорядочены по значению ch, и строки с одинаковым значением ch упорядочены по значению cl. Но поскольку первый ключевой столбец ch имеет высокую кардинальность, маловероятно, что существуют строки с одинаковым значением ch. Поэтому также маловероятно, что значения cl упорядочены (локально — для строк с одинаковым значением ch).

Поэтому значения cl, скорее всего, находятся в случайном порядке и, следовательно, имеют плохую локальность и, соответственно, коэффициент сжатия.

Резюме

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

Связанный контент

• Блог: Ускорение ваших запросов в ClickHouse

Эффективная идентификация отдельных строк

Хотя в общем случае это не является лучшим случаем использования для ClickHouse, некоторые приложения, построенные поверх ClickHouse, требуют идентификации отдельных строк таблицы ClickHouse.

Интуитивным решением для этого может быть использование столбца UUID с уникальным значением для каждой строки и для быстрого извлечения строк использовать этот столбец в качестве столбца первичного ключа.

Для самого быстрого извлечения столбец UUID должен быть первым ключевым столбцом.

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

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

Конкретный пример

Конкретным примером является текстовый сервис pastila.nl, который Алексей Миловидов разработал и написал о нем в блоге.

На каждое изменение текстового поля данные автоматически сохраняются в строке таблицы ClickHouse (одна строка на изменение).

И один из способов идентификации и извлечения (конкретной версии) вставленного контента — использование хеша контента в качестве UUID для строки таблицы, содержащей контент.

Следующая диаграмма показывает

• порядок вставки строк при изменении контента (например, из-за нажатий клавиш при вводе текста в текстовое поле) и
• порядок данных на диске из вставленных строк при использовании PRIMARY KEY (hash):

Поскольку столбец hash используется как столбец первичного ключа,

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

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

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

Следующая диаграмма показывает

• порядок вставки строк при изменении контента (например, из-за нажатий клавиш при вводе текста в текстовое поле) и
• порядок данных на диске из вставленных строк при составном PRIMARY KEY (fingerprint, hash):

Теперь строки на диске сначала упорядочены по fingerprint, а для строк с одинаковым значением отпечатка их hash определяет окончательный порядок.

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

Компромисс состоит в том, что два поля (fingerprint и hash) необходимы для извлечения конкретной строки, чтобы оптимально использовать первичный индекс, который получается из составного PRIMARY KEY (fingerprint, hash).