ClickHouseにおけるMapルックアップ性能の改善

特定のキーを独立したカラムとしてマテリアライズすることで、ClickHouseのMapカラムのルックアップを最適化し、クエリ性能を向上させる方法を紹介します。

​

問題

a['key'] のような Map のルックアップは線形計算量で動作するため (こちらで説明しています) 、非効率になる場合があります。これは、テーブルから特定のキーに対応する値を選択するには、Map カラム内の全行 (N) にわたってすべてのキー (約 M) を走査する必要があり、結果として約 MxN 回のルックアップが発生するためです。

Map を使ったルックアップは、String カラムに比べて 10 倍遅くなることがあります。以下の実験でも、コールドクエリで約 10 倍の速度低下が見られるほか、処理されるデータ量にも桁違いの差 (7.21 MB 対 5.65 GB) があることが示されています。

-- SpanNameをStringとして、ResourceAttributesをMapとしてテーブルを作成する
DROP TABLE IF EXISTS tbl;
CREATE TABLE tbl (
    `Timestamp` DateTime64(9) CODEC (Delta(8), ZSTD(1)),
    `TraceId` String CODEC (ZSTD(1)),
    `ServiceName` LowCardinality(String) CODEC (ZSTD(1)),
    `Duration` UInt8 CODEC (ZSTD(1)), -- Int64
    `SpanName` LowCardinality(String) CODEC (ZSTD(1)),
    `ResourceAttributes` Map(LowCardinality(String), String) CODEC (ZSTD(1))
)
ENGINE = MergeTree
PARTITION BY toDate(Timestamp)
ORDER BY (ServiceName, SpanName, toUnixTimestamp(Timestamp), TraceId);

-- ResourceAttributes用のランダムなMapデータを生成するUDFを作成する
DROP FUNCTION IF EXISTS genmap;
CREATE FUNCTION genmap AS (n) -> arrayMap (x-> (x::String, (x*rand32())::String), range(1, n));

-- genmapが意図通りに動作しているか確認する
SELECT genmap(10)::Map(String, String);

-- 100万行を挿入する
INSERT INTO tbl
SELECT
    now() - randUniform(1, 1000000.) as Timestamp,
    randomPrintableASCII(2) as TraceId,
    randomPrintableASCII(2) as ServiceName,
    rand32() as Duration,
    randomPrintableASCII(2) as SpanName,
    genmap(rand64()%500)::Map(String, String) as ResourceAttributes
FROM numbers(1_000_000);

-- SpanNameへのクエリは高速
-- [cold] 0 rows in set. Elapsed: 0.642 sec. Processed 1.00 million rows, 7.21 MB (1.56 million rows/s., 11.22 MB/s.)
-- [warm] 0 rows in set. Elapsed: 0.164 sec. Processed 1.00 million rows, 7.21 MB (6.10 million rows/s., 43.99 MB/s.)
SELECT
    COUNT(*),
    avg(Duration/1E6) as average,
    quantile(0.95)(Duration/1E6) as p95,
    quantile(0.99)(Duration/1E6) as p99,
    SpanName
FROM tbl
GROUP BY SpanName ORDER BY 1 DESC LIMIT 50 FORMAT Null;

-- ResourceAttributesへのクエリは低速
-- [cold] 0 rows in set. Elapsed: 6.432 sec. Processed 1.00 million rows, 5.65 GB (155.46 thousand rows/s., 879.07 MB/s.)
-- [warm] 0 rows in set. Elapsed: 5.935 sec. Processed 1.00 million rows, 5.65 GB (168.50 thousand rows/s., 952.81 MB/s.)
SELECT
    COUNT(*),
    avg(Duration/1E6) as average,
    quantile(0.95)(Duration/1E6) as p95,
    quantile(0.99)(Duration/1E6) as p99,
    ResourceAttributes['1'] as hostname
FROM tbl
GROUP BY hostname ORDER BY 1 DESC LIMIT 50 FORMAT Null;

解決策 クエリを改善するには、Mapカラム内の特定のキーの値を既定値とする別のカラムを追加し、それをマテリアライズして既存の行にも値を設定できます。こうすることで、必要な値を挿入時に抽出して保存できるため、クエリ時のルックアップを高速化できます。

-- Mapの特定のキーをデフォルト値とするカラムを追加することで解決する
ALTER TABLE tbl ADD COLUMN hostname LowCardinality(String) DEFAULT ResourceAttributes['1'];
ALTER TABLE tbl MATERIALIZE COLUMN hostname;

-- hostname（新しいカラム）へのクエリが高速化された
-- [cold] 0 rows in set. Elapsed: 2.215 sec. Processed 1.00 million rows, 21.67 MB (451.52 thousand rows/s., 9.78 MB/s.)
-- [warm] 0 rows in set. Elapsed: 0.541 sec. Processed 1.00 million rows, 21.67 MB (1.85 million rows/s., 40.04 MB/s.)
SELECT
    COUNT(*),
    avg(Duration/1E6) as average,
    quantile(0.95)(Duration/1E6) as p95,
    quantile(0.99)(Duration/1E6) as p99,
    hostname
FROM tbl
GROUP BY hostname ORDER BY 1 DESC LIMIT 50 FORMAT Null;

-- キャッシュをクリアしてコールドクエリを実行する
SYSTEM DROP FILESYSTEM CACHE;