column_with_dictionary_task.txt

Кодирование строк со словарём и обработка запроса без декодирования строк

===Мотивация

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

Пример на данных Метрики Приложений:

(вырезано цензурой)

Почему это неизбежно? %%Enum%% часто невозможно использовать, потому что для них все возможные значения надо описать заранее, или необходимо уметь делать %%ALTER%% скриптом. Внешние словари или идентификаторы, выбранные вручную, требуют наличия ещё одной базы данных и являются более громоздким решением.

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

Это всё происходит, потому что тратится много CPU на разжатие данных, много memory bandwidth на последующее перекладывание длинных строчек, а также много CPU на повторяющиеся вычисления на одних и тех же строчках.


===Общие соображения

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

Возникает вопрос, как поддерживать словарь. Было бы заманчиво сделать его общим на столбец всей таблицы. Но это слишком сложно - ведь тогда для постоянного обновления словаря, пришлось бы иметь key-value базу. Особенно сложно в случае с реплицированными таблицами - очень сложная синхронизация, из-за которой такой подход вообще нецелесообразен.

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

Поэтому предлагается сделать словарь part-local. В каждом part-е у столбца может быть свой словарь. Это делает поддержку словаря тривиальной, но возникают сложности при обработке данных - ведь из разных part-ов будут считываться данные с разным словарём. Чтобы с этим работать, надо применять небольшие хитрости - типа выполнения первой стадии агрегации на данных из разных part-ов независимо; уметь при необходимости мержить словари или материализовать столбцы в полноценные для последующей обработки как обычно.

Для использования кодирования по словарю, пользователю надо будет указать в таблице специальный тип данных (%%StringWithDictionary%%). Хотелось бы конечно, чтобы работало само магически из коробки для обычного %%String%%, но начальную реализацию придётся делать более явной.


===Реализация

====Структуры данных и сериализация.

Нужно сделать тип данных %%DataTypeWithDictionary%%. Он принимает в качестве параметра тип данных для идентификаторов (например, %%DataTypeUInt32%%); вложенный тип данных (почти всегда - %%DataTypeString%%); и максимальный размер словаря (например, по-умолчанию - 65536).
В качестве типа данных для идентификаторов есть всего три варианта - %%UInt8%%, %%UInt16%%, %%UInt32%%.
(%%UInt64%% бесполезен (такие большие словари непрактичны), и скорее всего, почти во всех случаях достаточно будет %%UInt16%%)

Для пользователя, в таблице можно будет указать, скорее всего, лишь %%StringWithDictionary%% (опционально, с параметром %%max_dictionary_size%%). Вложенные типы данных, отличные от %%String%%, имеют техническое значение и недоступны для использования в таблицах.

Сейчас для сериализации и десериализации, типы данных поддерживают использование нескольких потоков данных (%%serializeBinaryBulkWithMultipleStreams%%), как например, %%Array%%, %%Nullable%%. Эти потоки данных согласованы друг с другом: каждый из них содержит засечки, которые позволяют позиционироваться для чтения соответствующих значений. Но для поддержки словарей, придётся ввести понятие - дополнительных данных для сериализации/десериализации. Отличие в том, что для этих дополнительных данных засечки не пишутся, а читаются и пишутся они целиком и один раз. То есть, при чтении %%StringWithDictionary%% из любого места, целиком один раз считывается соответствующий словарь. Можно оформить такой вид данных тоже как %%IDataType::Substream::Type%% (= %%Dictionary%%), но обрабатывать его особенным образом.

Нужно сделать столбец %%ColumnWithDictionary%%. Это контейнер (составной столбец) из двух других столбцов - ключей (чисел) и уникальных значений (обычно строк). Для примера, имеем %%ColumnWithDictionary(ColumnUInt32, ColumnString)%%. %%ColumnUInt32%% содержит числовые идентификаторы, и размер этого подстолбца такой, как у %%ColumnWithDictionary%%. %%ColumnString%% содержит значения, на которые отображены числовые идентификаторы. Размер этого подстолбца равен максимальному значению числового идентификатора. Отображение - идентификатор -> значение, получается неявным образом - надо всего лишь посмотреть в подстолбце %%ColumnString%% значение по позиции, равной соответствующему идентификатору.

Также %%ColumnWithDictionary%% в качестве служебных данных содержит:
- Хэш-таблицу, отображающую строку в идентификатор (обратное отображение): %%StringRef -> UInt32%%. Замечание: в качестве значений в %%ColumnWithDictionary%% могут быть не обязательно строки. Но для этих случаев всё-равно для общности используется %%StringRef%%.
- Хэш-код словаря (%%SipHash%%), позволяющий быстро проверить идентичность словарей (возможно, также значение, которое говорит, что хэш-код не вычислен).

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

Для записи в таблицу (например, %%INSERT SELECT%%), необходимо уметь преобразовывать %%ColumnString%% в %%ColumnWithDictionary%%. Для этого мы кладём все строки в хэш-таблицу, чтобы их уникализировать. Затем присваиваем им номера. (Замечение: в каком порядке присваивать номера? Можно в порядке расположения в хэш-таблице. Это даст лучшую кэш-локальность при загрузке словаря в память (в памяти надо сформировать ту же самую хэш-таблицу, и это проще при записи. Но есть недостаток - на разных машинах из-за отличий в платформе или по другим причинам, может использоваться разная хэш-функция, и тогда преимущество теряется, и в худшем случае, сформированный словарь может не совпасть на репликах. В связи с тем, что словарь всегда маленький, может быть лучше отсортировать уникальные строки и дать им номера в сортированном порядке.)

Для чтения форматов надо уметь добавлять одно значение (%%IColumn::insert%%) в столбец %%ColumnWithDictionary%%. Для этого мы держим там хэш-таблицу, и присваиваем номера новым уникальным строкам по мере их нахождения (дописываем их в конец %%ColumnString%%). Возможно, что при %%DataTypeStringWithDictionary::serializeBinaryBulk...%%, мы должны будем "нормализовать" словарь, перенумеровав значения согласно порядку в хэш-таблице или по сортированному порядку строк.

Сложный момент: в обеих случаях по мере формирования словаря, мы можем решить, что его использование нецелесообразно или невозможно (количество уникальных строк стало больше, чем максимальный размер словаря). Например, если мы хотели преобразовать %%ColumnString%% в %%ColumnWithDictionary%%, можно решить, что это преобразование ненужно, и возвращать исходный столбец %%ColumnString%%. Но это невозможно, когда мы имеем %%ColumnWithDictionary(..., ColumnString)%% и добавляем туда значения по одному методом %%insert%%.

Тут есть два варианта. 1. %%ColumnWithDictionary(..., ColumnString)%% может поддержать случай, когда словаря нет, а он просто хранит внутри себя полноценный столбец. Вроде нормально. 2. Не использовать %%ColumnWithDictionary(..., ColumnString)%% при заполнении данных как например, при чтении форматов данных. В этом случае, метод %%DataTypeWithDictionary::createColumn%% должен создавать полноценный столбец (%%ColumnString%%). Мы будем заполнять полноценный столбец, а превращаться в столбец %%ColumnWithDictionary(..., ColumnString)%% он будет только при сериализации и десериализации %%DataTypeStringWithDictionary%%.

Словарь сериализуется следующим образом: в начале указывается номер версии (на всякий случай), затем размер словаря (для того, чтобы не надо было ресайзить хэш-таблицу при его чтении), хэш-код словаря, а затем все значения в порядке их идентификаторов (по сути, просто сериализуется соответствующий подстолбец со значениями). Словарь на диске сжимается, наравне с другими данными. Можно кодировать, что словарь отсутствует, специальным нулевым номером версии. В этом случае на диск запишется файл с таким недословарём, который всего-лишь позволяет решить, что дальше нужно читать поток данных с полноценным столбцом полного размера. Потоки данных со значениями словаря и с столбцом полного размера, лучше обозначить по-разному (разные %%Substream::Type%%, записывать в разные файлы).

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

====Вычисления.

Для вычисления функций над %%ColumnWithDictionary%%, надо добавить свойство функции %%useDefaultImplementationForColumnsWithDictionary%%, по аналогии с %%Const%% и %%Nullable%%. В этом случае, если функция ещё и является %%isDeterministicInScopeOfQuery%%, то она будет вычисляться над словарём. Здесь есть разные случаи:

Если единственный неконстантный аргумент функции - %%ColumnWithDictionary%% (пример: %%length(EventName)%%), или все неконстантные агрументы - %%ColumnWithDictionary%% с совпадающим словарём (пример: %%EventName1 = EventName2%%), то мы применяем функцию непосредственно над словарём. Замечание: в качестве технической особенности, может возвращаться %%ColumnWithDictionary%% с не строковым значением. Для примера, результат функции %%length%% - %%ColumnWithDictionary(..., ColumnUInt64)%%, так как функция length: %%String -> UInt64%%. Это - временный столбец, который может дальше участвовать в вычислениях, но при первой необходимости будет преобразован в полноценный столбец. Если функция не является инъективной, то результирующий словарь надо уникализировать - ведь в дальнейшем он может использоваться при %%GROUP BY%%.

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

Если среди аргументов есть как %%ColumnWithDictionary%%, так и полноценные столбцы, то столбец %%ColumnWithDictionary%% придётся превратить в полноценный и затем вычислить функции как обычно. На выходе - полноценный столбец.

Если функция не %%isDeterministicInScopeOfQuery%% (пример: %%runningDifference%%), то столбцы %%ColumnsWithDictionary%% превращаются в полноценные, а потом функция вычисляется как обычно.

Если функция не %%useDefaultImplementationForColumnsWithDictionary%%, то это значит, что она может иметь какую-то особенную реализацию для %%ColumnsWithDictionary%%.

При %%ColumnWithDictionary::filter%%, словарь не фильтруется (и не меняется). То есть, возможна ситуация, когда маленький столбец таскает за собой толстый словарь.

Для некоторых задач (например, %%ColumnsWithDictionary::insertRangeFrom%%, а также %%ColumnsWithDictionary::gather%%) необходимо уметь помержить два словаря вместе и пересчитать идентификаторы.

Одно из основных преимуществ от использования словарей ожидается от их использования при %%GROUP BY%%. Для этого мы агрегируем данные по идентификаторам, а также захватываем %%ColumnPtr%% на словарь и запоминаем хэш-код словаря. Если на следующей итерации (для следующего блока) столбец имеет такой же словарь - то продолжаем агрегацию. А если нет, то одно из двух: либо мержим словари и перестраиваем хэш-таблицу, заменяя в ней ключи на новые; либо конвертируем значения в полноценные и дальше продолжаем агрегировать по полноценным значениям без использования преимущества от словаря. То же самое происходит при мерже нескольких частично агрегированных данных из разных потоков.

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

В агрегатные функции по-умолчанию передаётся раскрытое значение (%%ColumnString%%, а не %%ColumnWithDictionary(..., ColumnString)%%) и агрегатные функции работают как обычно. Казалось бы, можно было бы использовать преимущество словаря для реализации %%uniq%%. Но это не получается, из-за того, что словари могут быть разными, а операция "смены словаря" возможна не для всех состояний агрегатных функций.