CollapsingMergeTree テーブルエンジン

MergeTree を継承し、マージ処理中に行を折りたたむロジックを追加したものです。

​

説明

CollapsingMergeTree エンジンは MergeTree を継承し、 マージ処理中に行を折りたたむロジックを追加したものです。 CollapsingMergeTree テーブルエンジンは、 特別なフィールド Sign を除き、ソートキー (ORDER BY) 内のすべてのフィールドが同一で、 Sign の値が 1 または -1 である行のペアを非同期に削除 (折りたたみ) します。 反対の値を持つ Sign のペアが存在しない行は保持されます。

詳細については、このドキュメントの Collapsing セクションを参照してください。

このエンジンを使用すると、ストレージ使用量を大幅に削減でき、 その結果として SELECT クエリの効率が向上する可能性があります。

​

パラメータ

このテーブルエンジンのすべてのパラメータは、Sign パラメータを除き、 MergeTree のものと同じ意味を持ちます。

• Sign — 行タイプを表すカラム名です。1 は「状態行」、-1 は「取消行」を表します。型: Int8.

​

テーブルの作成

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, ...]

• クエリパラメータの説明については、クエリの説明を参照してください。
• CollapsingMergeTree テーブルを作成する際は、MergeTree テーブルを作成する場合と同様に、同じクエリ句が必要です。

​

折りたたみ

​

データ

あるオブジェクトについて、継続的に変化するデータを保存する必要がある状況を考えてみましょう。 オブジェクトごとに 1 行を持ち、変更があるたびに更新するのが理にかなっているように思えるかもしれませんが、 更新操作ではストレージ上のデータを書き換える必要があるため、DBMS にとって高コストで低速です。 すばやくデータを書き込む必要がある場合、大量の更新を行う方法は現実的ではありませんが、 オブジェクトの変更内容を順次書き込むことは常に可能です。 そのために、特別なカラム Sign を使用します。

• Sign = 1 の場合、その行は 状態行、つまり 現在の有効な状態を表すフィールドを含む行 を意味します。
• Sign = -1 の場合、その行は 取消行、つまり 同じ属性を持つオブジェクトの状態を打ち消すために使用される行 を意味します。

たとえば、ある Web サイトでユーザーが何ページ閲覧し、それぞれにどれくらい滞在したかを計算したいとします。 ある時点で、ユーザーアクティビティの状態を表す次の行を書き込みます。

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

後の時点で、ユーザーアクティビティの変化を記録し、次の2行を書き込みます。

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

最初の行は、オブジェクト (この場合はユーザー) の直前の状態を打ち消します。 取消行では、Sign を除き、“canceled” 行のソートキーのフィールドをすべてコピーする必要があります。 上の2行目には現在の状態が入っています。

必要なのはユーザーアクティビティの最新の状態だけなので、以下に示すように、元の 状態行 と挿入した 取消行 行は削除でき、これによりオブジェクトの無効な (古い) 状態が折りたたまれます。

┌──────────────UserID─┬─PageViews─┬─Duration─┬─Sign─┐
│ 4324182021466249494 │         5 │      146 │    1 │ -- 古い「状態行」は削除可能
│ 4324182021466249494 │         5 │      146 │   -1 │ -- 「取消行」は削除可能
│ 4324182021466249494 │         6 │      185 │    1 │ -- 新しい「状態行」は残る
└─────────────────────┴───────────┴──────────┴──────┘

CollapsingMergeTree は、データパーツのマージ時に、まさにこの折りたたみ動作を実行します。

各変更に対して 2 行が必要になる理由 については、Algorithm の段落でさらに説明しています。

このようなアプローチの特徴

1. データを書き込むプログラムは、それを打ち消せるように、オブジェクトの状態を覚えておく必要があります。取消行には、状態行 のソートキー フィールドのコピーと、逆の Sign を含める必要があります。これにより保存領域の初期サイズは増えますが、データを高速に書き込めます。
2. カラム内の長大化する配列は、書き込み負荷の増加によってエンジンの効率を低下させます。データが単純であるほど、効率は高くなります。
3. SELECT の結果は、オブジェクトの変更履歴の整合性に大きく左右されます。挿入するデータは、正確に準備してください。データに不整合があると、予測不能な結果になることがあります。たとえば、session depth のような非負のメトリクスに負の値が入ることがあります。

​

アルゴリズム

ClickHouseがデータパーツをマージする際、 同じソートキー (ORDER BY) を持つ連続した行の各グループは、最大2行までに減らされます。 つまり、Sign = 1 の「状態行」と Sign = -1 の「取消行」です。 言い換えると、ClickHouseではエントリが折りたたまれます。

ClickHouseは、生成された各データパーツについて次を保存します。

1.	「状態行」と「取消行」の数が一致し、かつ最後の行が「状態行」である場合、最初の「取消行」と最後の「状態行」。
2.	「状態行」の数が「取消行」より多い場合、最後の「状態行」。
3.	「取消行」の数が「状態行」より多い場合、最初の「取消行」。
4.	その他すべての場合、どの行も保存しません。

さらに、「状態行」が「取消行」より2行以上多い場合、 または「取消行」が「状態行」より2行以上多い場合、マージは継続されます。 ただし、ClickHouseはこの状況を論理エラーとして扱い、server log に記録します。 このエラーは、同じデータが複数回挿入された場合に発生することがあります。 したがって、折りたたみによって統計の計算結果が変わるべきではありません。 変更は徐々に折りたたまれ、最終的にはほぼすべてのオブジェクトで最後の状態だけが残ります。

マージアルゴリズムでは、 同じソートキーを持つすべての行が同じ結果データパーツ内、さらには同じ物理サーバー上に配置されるとは限らないため、Signカラムが必要です。 ClickHouseは複数のスレッドでSELECTクエリを処理するため、結果内の行の順序を予測できません。

CollapsingMergeTreeテーブルから完全に「折りたたまれた」データを取得する必要がある場合は、集約が必要です。 折りたたみを完了するには、GROUP BY句と、符号を考慮した集約関数を使うクエリを記述します。 たとえば、件数を計算するには count() の代わりに sum(Sign) を使用します。 何らかの合計を計算するには、以下の例のように、sum(x) の代わりに HAVING sum(Sign) > 0 と組み合わせて sum(Sign * x) を使用します。

集約 count、sum、avg はこの方法で計算できます。 オブジェクトに少なくとも1つの未折りたたみの状態があれば、集約 uniq も計算できます。 一方、集約 min と max は計算できません。 これは、CollapsingMergeTree が折りたたまれた状態の履歴を保存しないためです。

集約せずにデータを取り出す必要がある場合 (たとえば、最新の値が特定の条件に一致する行が存在するかどうかを確認する場合) 、 FROM句にFINAL修飾子を使用できます。結果を返す前にデータがマージされます。 CollapsingMergeTree では、各キーについて最新の状態行のみが返されます。

​

例

​

使用例

以下のサンプルデータを例にします。

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

CollapsingMergeTree を使用して、テーブル UAct を作成しましょう:

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

次に、データをいくつか挿入します。

INSERT INTO UAct VALUES (4324182021466249494, 5, 146, 1)

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

2 つの異なるデータパーツを作成するために、INSERT クエリを 2 回使用します。

1 回のクエリでデータを挿入すると、ClickHouse が作成するデータパーツは 1 つだけで、その後マージは実行されません。

データは次のように選択できます。

SELECT * FROM UAct

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

上で返されたデータを見て、折りたたみが発生したかどうかを確認してみましょう… 2つの INSERT クエリによって、2つのデータパーツが作成されました。 SELECT クエリは2つのスレッドで実行されたため、行の順序はランダムになっています。 ただし、データパーツのマージがまだ行われていないため、折りたたみは発生していません また、ClickHouse は予測できないタイミングでバックグラウンドでデータパーツをマージするためです。

そのため、集約が必要になります。 これには sum 集約関数と HAVING 句を使用します。

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 │
└─────────────────────┴───────────┴──────────┘

集約が不要で、折りたたみを強制したい場合は、FROM 句で FINAL 修飾子を使用することもできます。

SELECT * FROM UAct FINAL

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

この方法でデータを選択するのは効率が低く、スキャンするデータ量が多い場合 (数百万行) には推奨されません。

​

別のアプローチの例

このアプローチの考え方は、マージではキーフィールドだけが考慮されるという点です。 そのため、“cancel” の行では、Sign カラムを使わなくても、合計時に前のバージョンの行を相殺できる負の値を指定できます。

この例では、以下のサンプルデータを使用します。

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

この方法では、負の値を格納できるように、PageViews と Duration のデータ型を変更する必要があります。 そのため、collapsingMergeTree を使用してテーブル UAct を作成する際に、これらのカラムの型を 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;

┌──────────────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 │
└─────────────────────┴───────────┴──────────┴──────┘