Представление иерархии и выполнение иерархических запросов в ClickHouse с использованием хешей
Привет, Хабр! Достаточно часто используются иерархические фильтры или отчеты с иерархией, и представление иерархии может быть актуально как для UI (например, иерархических фильтров), так и для отчетов или дашбордов. Если рассматривать только структуру запроса с иерархией, без расчета промежуточных итогов и т.д., то сохранение структуры иерархического UI элемента при большом уровне вложенности, а также передача этой иерархии с UI на бэкенд и дальше, например, в виде SQL запроса в СУБД может быть относительно нетривиальной задачей. При относительно большом уровне вложенности (например, иерархия в 10 уровней), при решении «в лоб» и сохранении всех 10 выбранных значений на последнем уровне иерархии, станет неудобно хранить и передавать в качестве параметров с UI на бэкенд (для 1000 строк и 10 уровней вложенности может быть уже условно 10000 параметров), также растет и количество параметров в SQL, и проблемы усугубляются в случае микросервисной архитектуры, когда запрос SQL не сразу отправляется, например, в ClickHouse, а ещё эти 10000 параметров «путешествуют» из UI в один или несколько микросервисов, пока не попадут в ClickHouse. В связи с этим хочу рассмотреть одно из возможных решений проблемы с помощью хеширования на примере C# и ClickHouse, но это «не идеи, проверенные на продакшене», больше тема к обсуждению. Тем, кому интересно решение проблем иерархических запросов на примере C# и ClickHouse — добро пожаловать под кат :)
Рассмотрим пример иерархического контрола (например, иерархического фильтра), причем у нас есть 2 продукта, 3 клиента, 2 склада, всего 12 записей, из них 3 записи выбраны.
Для нагляжности создадим схему данных ClickHouse и 12 строк тестовых данных:
CREATE OR REPLACE TABLE sales
(
order_number Int64,
amount Float64,
order_date Date,
product_id Int64,
customer_id Int64,
store_id Int64
) ENGINE = Log;
INSERT INTO sales
SELECT toString(1000000000 + number) AS order_number,
number % 100 AS amount,
dateAdd(number % 700, toDate('2023-01-01')),
number / 6 % 2 + 1 AS product_id,
number / 2 % 3 + 1 AS customer_id,
number % 2 + 1 AS store_id
FROM system.numbers
LIMIT 12;ClickHouse поддерживает murmurHash2_32, и здесь используется MurmurHash2 для иллюстрации, т.к. он быстрый, и более сложный для примера и не нужен, и коллизии достаточно просто разрешить проверкой реальных значений из запроса. По поводу объединения хешей — предлагается использовать ещё более простой подход, чем в ClickHouse, считаем, что для иллюстрации этого достаточно, т.е. обычный XOR для объединения двух хешей. Конечно, для использования в продакшене нужно учесть разные типы данных, выбрать подходящую инкрементальную хеш функцию и т.д.
Предлагается рассчитывать хеши вида:
SELECT murmurHash2_32(product_id) AS product_id_hash,
murmurHash2_32(bitXor(customer_id, product_id_hash)) AS customer_id_hash,
murmurHash2_32(bitXor(store_id, customer_id_hash)) AS store_id_hash,
order_number,
amount,
order_date,
product_id,
customer_id,
store_id
FROM sales;Это дает результат запроса такого вида (в выделенных строках — то, что соответствует иерархическому фильтру из UI, пока без фильтрации):
В качестве иллюстрации подсчитаем MurmurHash2 на C# для первых двух выбранных строк, т.е. для Product #1 и Customer #1 (что соответствует двум складам, Store #1 и Store #2).
using System;
public class MurmurHash2
{
public static uint Hash(byte[] data, uint seed = 0)
{
const uint m = 0x5bd1e995;
const int r = 24;
int length = data.Length;
uint h = seed ^ (uint)length;
int i = 0;
while (length >= 4)
{
uint k = BitConverter.ToUInt32(data, i);
k *= m;
k ^= k >> r;
k *= m;
h *= m;
h ^= k;
i += 4;
length -= 4;
}
switch (length)
{
case 3:
h ^= (uint)(data[i + 2] << 16);
goto case 2;
case 2:
h ^= (uint)(data[i + 1] << 8);
goto case 1;
case 1:
h ^= data[i];
h *= m;
break;
}
h ^= h >> 13;
h *= m;
h ^= h >> 15;
return h;
}
public static void Main(string[] args)
{
const UInt64 product1 = 1;
const UInt64 customer1 = 1;
var bytesProduct1 = BitConverter.GetBytes(product1);
UInt64 hashProduct1 = Hash(bytesProduct1);
var combinedProduct1Customer1 = (hashProduct1 ^ customer1);
var bytesCombinedProduct1Customer1 = BitConverter.GetBytes(combinedProduct1Customer1);
UInt64 hashCombinedProduct1Customer1 = Hash(bytesCombinedProduct1Customer1);
Console.WriteLine($"Hash value: {hashProduct1}, {hashCombinedProduct1Customer1}");
}
}Этот C# код возвращает следующие хеши для уровня Product и для уровня Customer: Hash value: 3340017859, 1304444856. Для Store значение не вычисляется в C#, т.к. нас устраивают оба склада Store #1 и Store #2.
SQL решения в лоб (конечно, можно упростить первые два условия в WHERE, здесь простейшее решение, для наглядности):
SELECT order_number,
amount,
order_date,
product_id,
customer_id,
store_id
FROM sales
WHERE product_id = 1 AND customer_id = 1 AND store_id = 1
OR product_id = 1 AND customer_id = 1 AND store_id = 2
OR product_id = 1 AND customer_id = 3 AND store_id = 2;
Видно, что даже для 12 строк и трех уровней иерархии уже 9 параметров.
SQL решения через хеши для трех выбранных строк, соответствующих выбранным элементам из UI фильтра, причем фильтрация по хешу на уровне Customer дает две записи (со Store #1 и Store #2), и ещё одна фильтрация на уровне Store дает одну запись:
SELECT murmurHash2_32(product_id) AS product_id_hash,
murmurHash2_32(bitXor(customer_id, product_id_hash)) AS customer_id_hash,
murmurHash2_32(bitXor(store_id, customer_id_hash)) AS store_id_hash,
order_number,
amount,
order_date,
product_id,
customer_id,
store_id
FROM sales
WHERE customer_id_hash = 1304444856
OR store_id_hash = 3547175208;
Видно, что в WHERE с хешами всего два параметра, а в предыдущем решении 9.
Таким образом, видны преимущества работы с хешами, особенно если сохранить иерархические результаты во временную таблицу. Что касается коллизий — их легко разрешить, т.к. в результатах запроса есть все данные для этого. Также легко хранить структуру запроса (всего 2 хеша вместо 9 параметров WHERE), и наблюдаем снижение количества параметров — это удобнее для микросервисной архитектуры. Использование хешей может быть плюсом и при логировании параметров с точки зрения их шифрования. Конечно, для использования в продакшене нужно учесть разные типы данных, выбрать подходящую инкрементальную хеш функцию и т.д.
Надеюсь, такое решение может быть интересно в текущем виде, или вдохновит на лучшее:)
