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

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

https://habr.com/ru/articles/1012624/

#sql #clickhouse #cityhash #хешфункции #хеширование #аналитика #анализ_данных #оптимизация #хеш #data_engineering

[Перевод] Ломаем хэши CityHash64, MurmurHash2/3, wyhash и не только…

Хэш-функции — невероятно красивые математические объекты. Они могут отображать произвольные данные на небольшую область выходных данных фиксированного размера таким образом, что отображение оказывается детерминированным, хоть и кажется случайным. Такая «детерминированная случайность» невероятно полезна для широкого спектра применений, например, для хэш-таблиц , контрольных сумм , алгоритмов Монте-Карло , распределённых алгоритмов без коммуникаций и так далее. В этой статье мы взглянем на тёмную сторону хэш-функций: ситуации, когда всё идёт не так. К счастью, такое, по сути, в реальной жизни никогда не происходит из-за неудачных входных данных (по крайней мере, в случае хороших хэш-функций). Однако кроме программ существуют и люди, и не все из них настроены миролюбиво, поэтому нам следует обратиться за ответами к сфере компьютерной безопасности. Я вкратце объясню основы безопасности хэш-функций, а затем покажу, насколько легко поломать эту безопасность для некоторых популярных некриптографических хэш-фукнкций. Для затравки скажу, что в этой статье объясняется, как генерировать за секунду тысячи подобных строк: cityhash64("orlp-cityhash64-D-:K5yx*zkgaaaaa") == 1337 murmurhash2("orlp-murmurhash64-bkiaaa&JInaNcZ") == 1337 murmurhash3("orlp-murmurhash3_x86_32-haaaPa*+") == 1337 farmhash64("orlp-farmhash64-/v^CqdPvziuheaaa") == 1337 Также я покажу, как можно создавать очень специфичные пары строк, которые можно произвольно конкатенировать таким образом, что при конкатенации k строк любая из 2 k комбинаций будет иметь одинаковый хэш вне зависимости от использованного для хэш-функции порождающего значения (seed): a = "xx0rlpx!xxsXъВ" b = "xxsXъВxx0rlpx!" murmurhash2(a + a, seed) == murmurhash2(a + b, seed) murmurhash2(a + a, seed) == murmurhash2(b + a, seed) murmurhash2(a + a, seed) == murmurhash2(b + b, seed) a = "!&orlpՓ" b = "yǏglp$X" murmurhash3(a + a, seed) == murmurhash3(a + b, seed) murmurhash3(a + a, seed) == murmurhash3(b + a, seed) murmurhash3(a + a, seed) == murmurhash3(b + b, seed)

https://habr.com/ru/articles/858960/

#хэшфункции #murmur #cityhash #farmhash #hash_function