Skip to main content

CollapsingMergeTree

Движок наследует функциональность от MergeTree и добавляет в алгоритм слияния кусков данных логику сворачивания (удаления) строк.

CollapsingMergeTree асинхронно удаляет (сворачивает) пары строк, если все поля в ключе сортировки (ORDER BY) эквивалентны, за исключением специального поля Sign, которое может принимать значения 1 и -1. Строки без пары сохраняются. Подробнее смотрите в разделе Сворачивание (удаление) строк.

Движок может значительно уменьшить объём хранения и, как следствие, повысить эффективность запросов SELECT.

Создание таблицы

CREATE TABLE [IF NOT EXISTS] [db.]table_name [ON CLUSTER cluster]
(
name1 [type1] [DEFAULT|MATERIALIZED|ALIAS expr1],
name2 [type2] [DEFAULT|MATERIALIZED|ALIAS expr2],
...
) ENGINE = CollapsingMergeTree(sign)
[PARTITION BY expr]
[ORDER BY expr]
[SAMPLE BY expr]
[SETTINGS name=value, ...]

Подробности про CREATE TABLE смотрите в описании запроса.

Параметры CollapsingMergeTree

  • sign — Имя столбца с типом строки: 1 — строка состояния, -1 — строка отмены состояния.

    Тип данных столбца — `Int8`.

Секции запроса

При создании таблицы с движком CollapsingMergeTree используются те же секции запроса, что и при создании таблицы с движком MergeTree.

Устаревший способ создания таблицы
Важно

Не используйте этот способ в новых проектах и по возможности переведите старые проекты на способ описанный выше.

CREATE TABLE [IF NOT EXISTS] [db.]table_name [ON CLUSTER cluster]
(
name1 [type1] [DEFAULT|MATERIALIZED|ALIAS expr1],
name2 [type2] [DEFAULT|MATERIALIZED|ALIAS expr2],
...
) ENGINE [=] CollapsingMergeTree(date-column [, sampling_expression], (primary, key), index_granularity, sign)

Все параметры, кроме ver имеют то же значение, что и в MergeTree.

  • sign — Имя столбца с типом строки: 1 — строка состояния, -1 — строка отмены состояния.

    Тип данных столбца — Int8.

Сворачивание (удаление) строк

Данные

Рассмотрим ситуацию, когда необходимо сохранять постоянно изменяющиеся данные для какого-либо объекта. Кажется логичным иметь одну строку для объекта и обновлять её при любом изменении, однако операция обновления является дорогостоящей и медленной для СУБД, поскольку требует перезаписи данных в хранилище. Если необходимо быстро записать данные, обновление не допустимо, но можно записать изменения объекта последовательно как описано ниже.

Используйте специальный столбец Sign. Если Sign = 1, то это означает, что строка является состоянием объекта, назовём её строкой состояния. Если Sign = -1, то это означает отмену состояния объекта с теми же атрибутами, назовём её строкой отмены состояния.

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

┌──────────────UserID─┬─PageViews─┬─Duration─┬─Sign─┐
│ 4324182021466249494 │ 5 │ 146 │ 1 │
└─────────────────────┴───────────┴──────────┴──────┘

Через некоторое время мы регистрируем изменение активности пользователя и записываем его следующими двумя строками.

┌──────────────UserID─┬─PageViews─┬─Duration─┬─Sign─┐
│ 4324182021466249494 │ 5 │ 146 │ -1 │
│ 4324182021466249494 │ 6 │ 185 │ 1 │
└─────────────────────┴───────────┴──────────┴──────┘

Первая строка отменяет предыдущее состояние объекта (пользователя). Она должна повторять все поля из ключа сортировки для отменённого состояния за исключением Sign.

Вторая строка содержит текущее состояние.

Поскольку нам нужно только последнее состояние активности пользователя, строки

┌──────────────UserID─┬─PageViews─┬─Duration─┬─Sign─┐
│ 4324182021466249494 │ 5 │ 146 │ 1 │
│ 4324182021466249494 │ 5 │ 146 │ -1 │
└─────────────────────┴───────────┴──────────┴──────┘

можно удалить, сворачивая (удаляя) устаревшее состояние объекта. CollapsingMergeTree выполняет это при слиянии кусков данных.

Зачем нужны две строки для каждого изменения описано в разделе Алгоритм.

Особенности подхода

  1. Программа, которая записывает данные, должна помнить состояние объекта, чтобы иметь возможность отменить его. Строка отмены состояния должна содержать копию полей сортировочного ключа предыдущей строки состояния с противоположным значением Sign. Это увеличивает начальный размер хранилища, но позволяет быстро записывать данные.
  2. Длинные растущие массивы в Столбцах снижают эффективность работы движка за счёт нагрузки на запись. Чем проще данные, тем выше эффективность.
  3. Результаты запроса SELECT сильно зависят от согласованности истории изменений объекта. Будьте точны при подготовке данных для вставки. Можно получить непредсказуемые результаты для несогласованных данных, например отрицательные значения для неотрицательных метрик, таких как глубина сеанса.

Алгоритм

Во время объединения кусков данных, каждая группа последовательных строк с одинаковым сортировочным ключом (ORDER BY) уменьшается до не более чем двух строк, одна из которых имеет Sign = 1 (строка состояния), а другая строка с Sign = -1 (строка отмены состояния). Другими словами, записи сворачиваются.

Для каждого результирующего куска данных ClickHouse сохраняет:

  1. Первую строку отмены состояния и последнюю строку состояния, если количество строк обоих видов совпадает и последняя строка — строка состояния.
  2. Последнюю строку состояния, если строк состояния на одну больше, чем строк отмены состояния.
  3. Первую строку отмены состояния, если их на одну больше, чем строк состояния.
  4. Ни одну из строк во всех остальных случаях.

Также, если строк состояния как минимум на 2 больше, чем строк отмены состояния, или, наоборот, строк отмены состояния как минимум на 2 больше, чем строк состояния, то слияние продолжается, но ClickHouse трактует подобные ситуации как логическую ошибку и записывает её в лог сервера. Подобная ошибка может возникнуть, если один и тот же блок данных вставлен несколько раз.

Как видно, от сворачивания не должны меняться результаты расчётов статистик. Изменения постепенно сворачиваются так, что остаются лишь последнее состояние почти каждого объекта.

Столбец Sign необходим, поскольку алгоритм слияния не гарантирует, что все строки с одинаковым ключом сортировки будут находиться в одном результирующем куске данных и даже на одном физическом сервере. ClickHouse выполняет запросы SELECT несколькими потоками, и он не может предсказать порядок строк в результате. Если необходимо получить полностью свёрнутые данные из таблицы CollapsingMergeTree, то необходимо агрегирование.

Для завершения свертывания добавьте в запрос секциюGROUP BY и агрегатные функции, которые учитывают знак. Например, для расчета количества используйте sum(Sign) вместоcount(). Чтобы вычислить сумму чего-либо, используйте sum(Sign * x) вместоsum(х), и так далее, а также добавьте HAVING sum(Sign) > 0 .

Таким образом можно вычислять агрегации count, sum и avg. Если объект имеет хотя бы одно не свёрнутое состояние, то может быть вычислена агрегация uniq. Агрегации min и max невозможно вычислить, поскольку CollapsingMergeTree не сохраняет историю значений свернутых состояний.

Если необходимо выбирать данные без агрегации (например, проверить наличие строк, последние значения которых удовлетворяют некоторым условиям), можно использовать модификатор FINAL для секции FROM. Это вариант существенно менее эффективен.

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

Исходные данные:

┌──────────────UserID─┬─PageViews─┬─Duration─┬─Sign─┐
│ 4324182021466249494 │ 5 │ 146 │ 1 │
│ 4324182021466249494 │ 5 │ 146 │ -1 │
│ 4324182021466249494 │ 6 │ 185 │ 1 │
└─────────────────────┴───────────┴──────────┴──────┘

Создание таблицы:

CREATE TABLE UAct
(
UserID UInt64,
PageViews UInt8,
Duration UInt8,
Sign Int8
)
ENGINE = CollapsingMergeTree(Sign)
ORDER BY UserID

Insertion of the data:

INSERT INTO UAct VALUES (4324182021466249494, 5, 146, 1)
INSERT INTO UAct VALUES (4324182021466249494, 5, 146, -1),(4324182021466249494, 6, 185, 1)

Мы используем два запроса INSERT для создания двух различных кусков данных. Если вставить данные одним запросом, ClickHouse создаёт один кусок данных и никогда не будет выполнять слияние.

Получение данных:

SELECT * FROM UAct
┌──────────────UserID─┬─PageViews─┬─Duration─┬─Sign─┐
│ 4324182021466249494 │ 5 │ 146 │ -1 │
│ 4324182021466249494 │ 6 │ 185 │ 1 │
└─────────────────────┴───────────┴──────────┴──────┘
┌──────────────UserID─┬─PageViews─┬─Duration─┬─Sign─┐
│ 4324182021466249494 │ 5 │ 146 │ 1 │
└─────────────────────┴───────────┴──────────┴──────┘

Что мы видим и где сворачивание?

Двумя запросами INSERT, мы создали два куска данных. Запрос SELECT был выполнен в 2 потока, и мы получили случайный порядок строк. Сворачивание не произошло, так как слияние кусков данных еще не произошло. ClickHouse объединяет куски данных в неизвестный момент времени, который мы не можем предсказать.

Таким образом, нам нужна агрегация:

SELECT
UserID,
sum(PageViews * Sign) AS PageViews,
sum(Duration * Sign) AS Duration
FROM UAct
GROUP BY UserID
HAVING sum(Sign) > 0
┌──────────────UserID─┬─PageViews─┬─Duration─┐
│ 4324182021466249494 │ 6 │ 185 │
└─────────────────────┴───────────┴──────────┘

Если нам не нужна агрегация, но мы хотим принудительно выполнить свёртку данных, можно использовать модификатор FINAL для секции FROM.

SELECT * FROM UAct FINAL
┌──────────────UserID─┬─PageViews─┬─Duration─┬─Sign─┐
│ 4324182021466249494 │ 6 │ 185 │ 1 │
└─────────────────────┴───────────┴──────────┴──────┘

Такой способ выбора данных очень неэффективен. Не используйте его для больших таблиц.

Пример другого подхода

Исходные данные:

┌──────────────UserID─┬─PageViews─┬─Duration─┬─Sign─┐
│ 4324182021466249494 │ 5 │ 146 │ 1 │
│ 4324182021466249494 │ -5 │ -146 │ -1 │
│ 4324182021466249494 │ 6 │ 185 │ 1 │
└─────────────────────┴───────────┴──────────┴──────┘

Идея состоит в том, что слияния при сворачивании учитывают только ключевые поля, поэтому в отменяющей строке можно указать отрицательные значения, которые нивелируют предыдущую версию записи при суммировании без учета поля Sign. Для этого подхода необходимо изменить тип данных PageViews, Duration для хранения отрицательных значений UInt8 -> Int16.

CREATE TABLE UAct
(
UserID UInt64,
PageViews Int16,
Duration Int16,
Sign Int8
)
ENGINE = CollapsingMergeTree(Sign)
ORDER BY UserID

Тестируем подход:

insert into UAct values(4324182021466249494,  5,  146,  1);
insert into UAct values(4324182021466249494, -5, -146, -1);
insert into UAct values(4324182021466249494, 6, 185, 1);

select * from UAct final; // старайтесь не использовать final (он подходит только для тестов и маленьких таблиц)
┌──────────────UserID─┬─PageViews─┬─Duration─┬─Sign─┐
│ 4324182021466249494 │ 6 │ 185 │ 1 │
└─────────────────────┴───────────┴──────────┴──────┘
SELECT
UserID,
sum(PageViews) AS PageViews,
sum(Duration) AS Duration
FROM UAct
GROUP BY UserID
┌──────────────UserID─┬─PageViews─┬─Duration─┐
│ 4324182021466249494 │ 6 │ 185 │
└─────────────────────┴───────────┴──────────┘
select count() FROM UAct
┌─count()─┐
│ 3 │
└─────────┘
optimize table UAct final;

select * FROM UAct
┌──────────────UserID─┬─PageViews─┬─Duration─┬─Sign─┐
│ 4324182021466249494 │ 6 │ 185 │ 1 │
└─────────────────────┴───────────┴──────────┴──────┘