データスキッピングインデックスとプロジェクション — ソートキー外の条件を速くする

一言でいうと

スキップインデックスは、行の位置を指すB-treeではなく、グラニュールのグループごとに付けた要約(最小値・最大値、値の集合、ブルームフィルター)です。「ここには絶対にない」と言えるときだけ、そのグループをスキップします。プロジェクションは、パートの中に隠した、別のソート順(または事前に集計した)コピーです。どちらも、すでにあるパートにはMATERIALIZEして初めてできあがり、どちらもディスクで代償を払います。

なぜ必要なのか

前のモジュールで、ソートキーがほとんどすべてを決めることを見ました。ところが、ソートキーは1つです。ログテーブルを時刻(ts)でソートしておけば、「昨日の午後」は速いのですが、障害調査で「このtrace_idの1行」を探すときは、100万行をすべて読みます。行指向DBなら、補助のB-treeインデックスをもう1つ作るところです。公式ドキュメントは、その方法が列指向の保存では通用しないと説明しています。ディスク上に、行単位で指す「行」が別にないからです。

ClickHouseが出した答えには、2つの方向があります。1つは読まなくてよいグラニュールをもっと多く見つけ出すこと(スキップインデックス)、もう1つは別のソートキーを持つコピーをもう1つ置くこと(プロジェクション、または前のモジュールのマテリアライズドビュー)です。どちらが合うかは、データの分布が決めます。

どう動くのか

インデックス1つは、4つの要素で定義されます。名前、式、種類(TYPE)、GRANULARITYです。GRANULARITYは、グラニュール何個を1つのグループとして要約するかを表します。1なら8192行ごと、4なら32768行ごとに要約を1つ作ります。ドキュメントが紹介する種類は、次のとおりです。

種類	グループごとに記録するもの	向いているケース
`minmax`	式の最小値・最大値	ソートキーとともにおおよそ大きくなる列の範囲条件
`set(N)`	異なる値をN個まで(あふれたら空にします)	全体では多様でも、グループの中では数個しかない列
`bloom_filter`	値の集合のブルームフィルター(偽陽性のデフォルトは0.025)	まれな値を1つ探す、「干し草の山の中の針」
`ngrambf_v1`・`tokenbf_v1`	n-gramやトークンのブルームフィルター	文字列の部分検索。26.2から非推奨の予定で、`text`インデックスが推奨されます

このPod(26.8)で、100万行・グラニュール123個のテーブルにADD INDEX idx_trace trace_id TYPE bloom_filter GRANULARITY 1を実行すると、EXPLAIN indexes = 1にSkipの欄が現れますが、Granules: 123/123です。インデックスは定義だけができ、既存のパートにはインデックスファイルがありません(system.data_skipping_indicesのサイズは0)。ドキュメントのとおり、新しく入ってくるデータにだけ適用されるからです。ALTER TABLE ... MATERIALIZE INDEX idx_traceは、既存のパートにファイルを作るミューテーションなので、パート名がall_1_1_1からall_1_1_1_2に変わり、そのあとはGranules: 3/123、読んだ行は24,576行になります。探す行は1行ですが、ブルームフィルターの偽陽性で、グラニュールを2つ余分に読みました。

同じminmaxでも、結果は両極端です。時間とともに大きくなるseqの範囲条件は、1/123グラニュールだけを残しました。時間と無関係に均等に散らばるuser_idは、どのグラニュールにも最小値の近くと最大値の近くが入っているため、123/123、つまり1つもスキップできませんでした。ドキュメントの表現のとおり、役に立つスキップインデックスは、たいていソートキーと対象の列との強い相関を必要とします。値がグループの中に1回しかなくても、そのグループ全体を読む必要があるので、相関がなければ、インデックスは計算コストを増やすだけです。

そんなときに使うのがプロジェクションです。ADD PROJECTION p_user (SELECT * ORDER BY user_id)のあとにMATERIALIZE PROJECTIONを実行すると、パートごとにuser_idの順にソートし直したコピーができます。クエリは相変わらずskp.logsに向かい、オプティマイザーが読む量が最も少ない側を選びます。このPodで、WHERE user_id = 4242は100万行から8,192行に減り、system.query_logのprojections列にskp.logs.p_userが残りました。GROUP BYを含むプロジェクションは、隠れたAggregatingMergeTreeになり、事前に集計したコピーになります。サービス・時間ごとのcount・avgのプロジェクションは4,320行で、サービスごとの集計クエリが、元のテーブルの代わりにそれだけを読みました。

代償はディスクで払います。このPodで、p_userのコピーは約24.6MBで、コピーを含むパート全体(約52.9MB)の半分近くでした。集計プロジェクションは約36KB、ブルームフィルターのインデックスは約1MB、minmaxインデックスは1KB強でした。プロジェクションには制約もあります。ドキュメントが述べているとおり、元のテーブルと異なるTTLは指定できず、連鎖させられず、定義にWHEREやJOINを使えず、プロジェクションのあるテーブルに軽量DELETEを実行すると、デフォルト設定(lightweight_mutation_projection_mode = throw)では拒否されます(Podでエラーコード344を確認)。

最後に、測るときの落とし穴を1つ。このPodの26.8でデフォルトで有効になっているクエリ条件キャッシュ(use_query_condition_cache)は、「この条件に合う行がなかったグラニュール」を記憶しています。同じ条件のクエリを2回目に実行したら、読んだ行が100万から0に落ちました。インデックスの効果を比較するときは、use_query_condition_cache = 0を指定して測ります。

現場での姿

最もよくある間違いは、「よく絞り込む列だからインデックスを付けよう」と、均等に散らばった列にminmaxやsetを付けることです。EXPLAINのSkip欄が123/123なら、そのインデックスはコストがかかるだけです。付ける前に、対象の列がソートキーと相関しているかをまず見ます。

2番目は、本番で稼働中の大きなテーブルにADD INDEXだけを行って、「なぜ速くならないのか」と悩むことです。新しいパートにだけできるので、既存のデータはMATERIALIZEする必要がありますが、それはすべてのパートを書き直すミューテーションです。空いている時間帯に、進行をsystem.mutationsで見ながら行います。

3番目は、trace_idやrequest_idのようなユニークな値の検索です。ブルームフィルターがよく合う、ほぼ唯一の場面で、文字列の部分検索なら、26.xではtextインデックスをまず検討します。プロジェクションは、「2番目のソートキーが必ず必要で、ディスクを2倍使ってもかまわない」という判断が立ってから使います。

次のラボですること

skp.logsに100万行を入れて、パートを1つにマージします。ブルームフィルターのインデックスをADDしただけの状態のEXPLAINを保存し、MATERIALIZEしたあとに読んだ行を測ります。seqとuser_idにminmaxを付けて効果を比べ、user_idのプロジェクションとサービス・時間の集計プロジェクションを作ってquery_logで確認し、最後に、これらすべてが使ったディスクをsystemテーブルから読みます。