Моя любимая функция в ClickHouse, или оптимизируем вообще всё с помощью cityHash64()

К написанию данной статьи меня подтолкнула другая статья:
«Не только sum() и uniq(): малоизвестные и очень полезные функции ClickHouse»
и вопрос автора: «В комментариях расскажите, какие „непопулярные“ функции кликхаус упростили вам жизнь.»
Недолго думая, я ответил: cityHash64().

Более 5 лет я работаю ClickHouse DBA и помогаю командам разработки и аналитики эффективно использовать ClickHouse. Неизменным помощником в этом мне служит хеш-функция cityHash64(). В данной статье мы поговорим в основном про оптимизацию SQL запросов с помощью хеш-функций. Вероятно, рассматриваемые приемы в той или иной степени актуальны не только для ClickHouse, но и для других баз данных, и могут быть полезны любому, кто пишет SQL запросы.

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

---

Для начала немного теории (можно прочитать по диагонали).

Зачем оно нам надо?

Общее для большинства рассматриваемых случаев – это превратить значение из десятков байт в одно число из 8 байт. Были тяжелые данные и большой расход памяти (привет, Memory limit exceeded), стало меньше данных и меньше расход памяти – всё просто.  Вообще это довольно общий рецепт оптимизации ClickHouse – обработать как можно меньше байт, но не всегда очевидно, как это сделать. Сегодня мы разберем конкретные примеры, которые лично я применяю достаточно регулярно. Надеюсь, и вам что-то из этого пригодится.

Что такое хеш-функции?

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

Что это за набор непонятных слов:

• Детерминированное, то есть, если f(x) – хеш-функция, x0 – константа и f(x0) = y0, то при повторных вычислениях всегда f(x0) = y0 (не может получиться f(x0) = y1, где y1 != y0). В общем, обычно мы имеем дело именно с такими функциями, а недетерминированные – это к примеру rand() или now().

• Псевдослучайное значит, что не вычисляя хеш функции, нельзя определить насколько большим или маленьким будет значение f(x0), и будет ли оно обладать каким-то иным свойством (например, определенной четностью и т.п.). А также, если x0 и x1 как-то связаны (например, x1 = x0 + 1), то ничего нельзя сказать о какой-либо связи значений f(x0) и f(x1).

• Равномерное распределение – это значит, что в любой равный диапазон значений хеш функции попадет примерно равное число элементов, если взять достаточно много f(x0), f(x1), f(x2)... То есть если диапазон возможных значений хеш-функции от 1 до 1000, то если мы возьмем 100 значений f(xi) для разных x, то среди результатов f(xi) у нас будет примерно по 50 значений <=500 и >500, примерно 10 в диапазоне от 523 до 622, примерно по 50 четных и нечетных, примерно по 33 с остатками от деления на 3 равными 0, 1 и 2 и т.п.

Есть и важное неприятное свойство хеш-функций – возможность коллизий.

Коллизия?

Коллизия – ситуация, когда для разных x0 и x1 получается f(x0) = f(x1), то есть для разных исходных значений мы получаем одинаковый хеш. Если диапазон значений хеш функции 2N, то вероятность, что не будет ни одной коллизии, равна примерно 50% для 2N/2 уникальных исходных значений. То есть для 64-битных хеш-функций (8 байт) можно не переживать за коллизии для 232 (~4 миллиарда) уникальных исходных элементов, если вы не банк. Если банк, тоже можно не переживать, если вы занимаетесь аналитикой, а не денежными переводами.

В аналитике коллизии практически никогда не страшны. Вам не важно, 1234567890 у вас пользователей или 1234567895. Если вы делаете принципиально разные выводы в этих случаях – это проблема не коллизий, а модели данных или оценки статистической значимости.

Почему именно cityHash64()?

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

Когда оно нам надо?

Допу��тим, вы храните какие-то относительно длинные строки (логи, URL-ы, cookies, почтовые адреса, HTML страницы и т.д.), массивы, UUID... Всё это сильно больше 8 байт. Если мы все исходные данные заменим на числа по 8 байт, то обработка их будет требовать гораздо меньше памяти (часто и меньше времени, несмотря на исходное вычисление cityHash64(), которое тоже не совсем "бесплатное", хоть и очень быстрое).

ℹ️ На всякий случай напомню, что 1 символ – это 1 байт. Но часто строки в unicode, а там 1 символ – это 2 и более байт, то есть "длинные" строки – это в рассматриваемом контексте на самом деле примерно любые строки.

---

Примеры использования.

Наконец, перейдем к примерам.

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

Подготовим тестовые данные.

Для тестов создадим две небольшие таблички: tmp_10M на 10 миллионов строк и tmp_1M на 1 миллион. В каждой по одной колонке s со случайными строками длиной до 20 символов:

Создаем и заполняем тестовые таблицы

CREATE TABLE tmp_10M (
    s String
)
ENGINE = MergeTree
ORDER BY (s);

CREATE TABLE tmp_1M (
    s String
)
ENGINE = MergeTree
ORDER BY (s);

insert into tmp_10M
    select s
    from generateRandom('s String', 1, 20)
    limit 10_000_000
;

insert into tmp_1M
    select s
    from generateRandom('s String', 2, 20)
    limit 1_000_000
;

Пример содержимого таблицы

select *
from tmp_1M
order by rand()
limit 3;
┌─s────────────────────┐
│ bIIB.47drsUnI;{      │
│ aqkH                 │
│ LUR?H45\S 27pH;},tf< │
└──────────────────────┘

Оптимизация количества уникальных значений.

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

select uniqExact(s)
from tmp_10M;
┌─uniqExact(s)─┐
│      8467558 │ -- 8.47 million
└──────────────┘
1 row in set. Elapsed: 1.303 sec. Processed 10.00 million rows, 190.01 MB (7.67 million rows/s., 145.83 MB/s.)
Peak memory usage: 856.95 MiB.

select uniqExact(cityHash64(s))
from tmp_10M;
┌─uniqExact(cityHash64(s))─┐
│                  8467558 │ -- 8.47 million
└──────────────────────────┘
1 row in set. Elapsed: 0.473 sec. Processed 10.00 million rows, 190.01 MB (21.12 million rows/s., 401.31 MB/s.)
Peak memory usage: 411.91 MiB.

Здесь и далее нас будет интересовать в основном статистика по продолжительности выполнения запроса (Elapsed) и главное по расходу памяти (Peak memory usage), так как именно падение запросов по памяти – это самое неприятное, что обычно случается.

В данном случае мы видим двукратное сокращение расхода памяти (412 MiB vs 857 MiB) и бонусом трехкратное ускорение выполнения запроса (0.473 sec. vs 1.303 sec.). Мы получаем выигрыш в расходе памяти, так как “заменили” строки на числа.

ℹ️ Вы можете ожидать, что чем длиннее строки, тем больше будет выигрыш. Однако, это не так. ClickHouse для подсчета уникальных строк и так сравнивает не сами строки, а хеши, просто не 64-битные, как мы, а 128-битные, поэтому выигрыш и составил около 2-х раз.

Оптимизация IN.

Найдем теперь, сколько строк из tmp_1M есть в tmp_10M через использование IN ():

select count(), uniq(s)
from tmp_1M
where
    s in (
        select s
        from tmp_10M
    )
;
┌─count()─┬─uniq(s)─┐
│  163097 │   28956 │
└─────────┴─────────┘
1 row in set. Elapsed: 3.823 sec. Processed 11.00 million rows, 209.01 MB (2.88 million rows/s., 54.67 MB/s.)
Peak memory usage: 1.50 GiB.

select count(), uniq(s)
from tmp_1M
where
    cityHash64(s) in (
        select cityHash64(s)
        from tmp_10M
    )
;
┌─count()─┬─uniq(s)─┐
│  163097 │   28956 │
└─────────┴─────────┘
1 row in set. Elapsed: 0.996 sec. Processed 11.00 million rows, 209.01 MB (11.05 million rows/s., 209.95 MB/s.)
Peak memory usage: 385.81 MiB.

На этот раз мы выиграли в 4 раза и по памяти, и по скорости. Опять же вместо проверки на in() по набору строк, проверяем по хешам. Естественно, хешировать надо и проверяемые значения, и проверяемое множество.

Оптимизация JOIN.

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

select count()
from (
    select s
    from tmp_1M
) any inner join (
    select s
    from tmp_10M
) using s
;
┌─count()─┐
│   28956 │
└─────────┘
1 row in set. Elapsed: 1.538 sec. Processed 11.00 million rows, 209.01 MB (7.15 million rows/s., 135.93 MB/s.)
Peak memory usage: 1.42 GiB.

select count()
from (
    select cityHash64(s) as s
    from tmp_1M
) any inner join (
    select cityHash64(s) as s
    from tmp_10M
) using s
;
┌─count()─┐
│   28956 │
└─────────┘
1 row in set. Elapsed: 0.557 sec. Processed 11.00 million rows, 209.01 MB (19.76 million rows/s., 375.45 MB/s.)
Peak memory usage: 813.58 MiB.

Опять выигрыш по памяти почти в 2 раза, а по скорости – в 3 раза.

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

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

Например:

select count(), uniqExact(s)
from tmp_10M;
┌──count()─┬─uniqExact(s)─┐
│ 10000000 │      8467558 │
└──────────┴──────────────┘
1 row in set. Elapsed: 1.036 sec. Processed 10.00 million rows, 190.01 MB (9.65 million rows/s., 183.37 MB/s.)
Peak memory usage: 856.20 MiB.

Представим, что для нас 856 MiB – это слишком большой расход памяти, и мы решили разбить подсчет на 10 пачек. Сделаем это через остатки от деления cityHash64(s) на 10:

select count(), uniqExact(s)
from tmp_10M
where cityHash64(s) % 10 = 0;
┌─count()─┬─uniqExact(s)─┐
│  944417 │       846309 │
└─────────┴──────────────┘
1 row in set. Elapsed: 0.218 sec. Processed 10.00 million rows, 190.01 MB (45.96 million rows/s., 873.39 MB/s.)
Peak memory usage: 119.10 MiB.

Как видим расход памяти сократился почти в 10 раз. Повторим для cityHash64(s) % 10 = 1, cityHash64(s) % 10 = 2, …, cityHash64(s) % 10 = 9 и просуммируем результаты.

ℹ️ Конечно, как и при любом другом способе разбиения на пачки, нужно следить, чтобы пачки были такими, чтобы общий результат можно было корректно вычислить из результатов запросов для отдельных пачек (может где-то не просуммировать, а повторно взять min/max и т.п.).
Иногда достаточно посчитать только одну пачку (например, так можно ускорять построение графиков на дашбордах, немного жертвуя точностью).

Хранение очень тяжелых колонок.

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

Для следующего набора примеров создадим еще одну таблицу: tmp_100k. На этот раз со 100k строк длиной до 100k символов:

Создаем тестовую таблицу с длинными строками

CREATE TABLE tmp_100k (
    s String,
    s_hash UInt64 DEFAULT cityHash64(s),
    value UInt32 DEFAULT rand()
)
ENGINE = MergeTree
ORDER BY (s);

insert into tmp_100k (s)
    select s
    from generateRandom('s String', 3, 100_000)
    limit 100_000
;

Дополнительно в таблице мы объявили колонку s_hash UInt64 DEFAULT cityHash64(s) – она автоматически заполнилась хешами значений исходной колонки s. А также добавили колонку value UInt32 DEFAULT rand() со случайными числами.

ℹ️ Такие тяжелые колонки лучше не добавлять в ключ сортировки таблицы (ORDER BY (s)). Для подобной таблицы лучше было бы ORDER BY (s_hash), но мы не будет так делать, чтобы не создавать в тесте дополнительного преимущества методу с хешем.

Используем предварительно подсчитанный хеш на диске.

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

select uniqCombined(20)(s)
from tmp_100k;
┌─uniqCombined(20)(s)─┐
│               99945 │
└─────────────────────┘
1 row in set. Elapsed: 1.580 sec. Processed 100.00 thousand rows, 5.00 GB (63.27 thousand rows/s., 3.16 GB/s.)
Peak memory usage: 111.05 MiB.

select uniqCombined(20)(cityHash64(s))
from tmp_100k;
┌─uniqCombined⋯yHash64(s))─┐
│                   100146 │
└──────────────────────────┘
1 row in set. Elapsed: 1.339 sec. Processed 100.00 thousand rows, 5.00 GB (74.69 thousand rows/s., 3.74 GB/s.)
Peak memory usage: 110.69 MiB.

Как видим вычисление хеша в запросе нам ничего не дало. Обратим внимание на статистику запроса: 3.74 GB/s. – это скорость чтения данных с диска. Мы уперлись в нее и физически не можем сделать запрос быстрее. Но у нас уже есть заранее посчитанный хеш в колонке s_hash, попробуем посчитать через нее:

select uniqCombined(20)(s_hash)
from tmp_100k;
┌─uniqCombined(20)(s_hash)─┐
│                   100084 │
└──────────────────────────┘
1 row in set. Elapsed: 0.009 sec. Processed 100.00 thousand rows, 800.00 KB (10.76 million rows/s., 86.09 MB/s.)
Peak memory usage: 651.03 KiB.

Ускорились более чем в 100 раз, неплохо. Еще бы, ведь прочитали всего 800.00 KB вместо 5.00 GB в первом случае (показывается объем распакованных данных без учета сжатия, но тут это не принципиально).

Еще раз акцентирую: тут важно понимать, что ускорились мы не за счет того, что долго было вычислять cityHash64(s) (а теперь он готовый на диске лежит и его не надо считать), а за счет того, что теперь мы не читаем с диска тяжелую колонку s, а вместо нее читаем гораздо более легкую s_hash. Можно сделать uniqCombined(20)(cityHash64(s_hash)) и скорость останется такой же быстрой (только на очень больших данных может стать чуть медленнее).

Оптимизация GROUP BY.

Попробуем выбрать топ 3 минимальных value в группировке по s:

select
    min(value) as value
from tmp_100k
group by s
order by value
limit 3;
┌─value─┐
│  8193 │
│ 50259 │
│ 67439 │
└───────┘
3 rows in set. Elapsed: 25.290 sec. Processed 100.00 thousand rows, 5.00 GB (3.95 thousand rows/s., 197.82 MB/s.)
Peak memory usage: 4.52 GiB.

select
    min(value) as value
from tmp_100k
group by cityHash64(s)
order by value
limit 3;
┌─value─┐
│  8193 │
│ 50259 │
│ 67439 │
└───────┘
3 rows in set. Elapsed: 3.110 sec. Processed 100.00 thousand rows, 5.00 GB (32.15 thousand rows/s., 1.61 GB/s.)
Peak memory usage: 120.34 MiB.

В варианте с group by cityHash64(s) мы получили оптимизацию по скорости и памяти на порядок по сравнению обычным group by s.

Уже неплохо, но попробуем пойти дальше и использовать уже сохраненную на диске колонку с хешем и сделать group by s_hash:

select
    min(value) as value
from tmp_100k
group by s_hash
order by value
limit 3;
┌─value─┐
│  8193 │
│ 50259 │
│ 67439 │
└───────┘
3 rows in set. Elapsed: 0.016 sec. Processed 100.00 thousand rows, 1.20 MB (6.30 million rows/s., 75.60 MB/s.)
Peak memory usage: 6.15 MiB.

Тут мы опять ускорились еще в 100 раз, так как нам не пришлось читать с диска тяжелую колонку s.

Но как быть, если значение колонки s нам всё-таки нужно после группировки? Ведь вариант из примера (когда нам нужны только значения агрегатов без значений групп) хоть и встречается, но сильно реже. На самом деле всё очень просто: мы можем использовать select any(s) при группировке по group by cityHash64(s) или group by s_hash. В подобных случаях (когда нам нужны не все группы, а как здесь топ 3 или отфильтрованные по какому-то условию) у нас прочитается или положится в память не вся тяжелая колонка s, а только необходимые ее значения.

А если у меня не строки?

Те же приемы можно применять для других тяжелых типов данных (UUID, ARRAY…) и для сочетаний нескольких колонок. Например, если мы считаем уникальные сочетания по нескольким колонкам, то вместо uniqExact(c1, c2…) можно делать uniqExact(cityHash64(c1, c2…)). Но есть важный нюанс: если хотя бы одно из значений ci равно null, то cityHash64(c1, c2…) = null, что нам не подходит, так как группы, например, (1, null) и (2, null) – это разные группы. Но это решается просто – нужно вместо cityHash64(c1, c2…) писать cityHash64(tuple(c1, c2…)).

ℹ️ tuple() – это такой специальный тип для сочетаний значений. Само слово tuple можно опускать и просто использовать скобки (по итогу получаются двойные скобки): cityHash64((c1, c2…)) – я вообще всегда делаю именно так, чтобы не думать, будет у нас там когда-то null или нет.

Валидация данных.

Иногда нам хочется глазами посмотреть на данные, но не упорядоченные (как это обычно бывает в ClickHouse) а случайные. Обычно мы делаем что-то вроде order by rand() limit 100. Но иногда хочется воспроизводимый пример. Например, мы сравниваем данные двух стендов, куда должны прийти одинаковые данные, или переписываем запрос и хотим быстро убедиться, что новый выдает примерно тоже самое, что и старый. Тогда мы можем использовать order by cityHash64((c1, c2…)) limit 100 – тогда данные будут случайно распределены, но при этом на одних и тех же исходных данных будет воспроизводиться одинаковый порядок.

Также хеш-функции помогают валидировать данные всей таблицы. Например, нам в примере выше глазами показалось, что всё сходится, но мы хотим убедиться в этом точнее. Один из способов – это подсчитать groupBitXor(cityHash64()). Мы можем вычислить groupBitXor(cityHash64(tuple(*))) для обоих результатов запросов/таблиц или groupBitXor(cityHash64(tuple(s))) для отдельных колонок, и убедиться, что данные сходятся. cityHash64() посчитает хеш для каждого значения, а groupBitXor() объединит всё в одно число, не зависящее от порядка обработки данных – получается что-то вроде чексуммы таблицы или колонки. Это не абсолютная проверка, но достаточно хорошая.

---

Заключение.

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

• Хеш-функции могут значительно ускорять SQL запросы и снижать расход памяти.

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

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

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

• Как всегда, Nullable – зло.