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

Введение

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

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

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

примечание

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

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

Набор данных

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

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

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

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

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

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

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

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

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

Ответ будет:

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

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

примечание

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

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

Ответ:

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

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

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

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

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

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

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

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

Разреженная индексация возможна, потому что ClickHouse хранит строки для части на диске в порядке, определяемом колонкой(ами) первичного ключа. Вместо того чтобы непосредственно находить отдельные строки (как в индексе на основе B-дерева), разреженный первичный индекс позволяет быстро (с помощью бинарного поиска по индексным записям) идентифицировать группы строк, которые могут соответствовать запросу. Найденные группы потенциально соответствующих строк (гранулы) затем параллельно передаются в движок 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 выдаст ошибку.

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

В самоуправляемом кластере 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 показывает, что 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".
• абстрактная версия нашей таблицы hits с упрощенными значениями для 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 последовательных гранул (обратите внимание наClause GRANULARITY 4 в операторе ALTER TABLE выше) - минимальное и максимальное значение URL:

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

Вторая запись в индексе ('mark 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, когда использовался общий поиск исключений.

Обратите внимание, что дополнительная таблица оптимизирована для ускорения выполнения нашего примера запроса с фильтрацией по UserIDs, и для ускорения запросов с фильтрацией по 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 является последней ключевой колонкой, после колонок с более низкой кардинальностью, которые используются для обеспечения хорошего отношения сжатия для некоторых колонок таблицы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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