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

Надеюсь, такое решение может быть интересно в текущем виде, или вдохновит на лучшее 🙂