疎な主キー — キーの順序が何を読み飛ばさせるか

一言でいうと

MergeTreeのプライマリインデックスは、行ごとではなくグラニュール(デフォルトは8192行)ごとに先頭行のキー値を1つだけ記録します。そのためインデックスにできるのは、「このグラニュールには探している値があり得ない」と判定することだけです。どれだけ絞り込めるかは、ソートキーの列の順序と前の列のカーディナリティ(値の種類の数)で決まります。

なぜ必要なのか

行指向DBのB-treeは、1行1行を指します。数十億行ならインデックスがメモリに収まらず、分析クエリはどのみち数百万行を走査するので、1行をピンポイントで指す能力はあまり役に立ちません。ClickHouseは逆の道を選びました。ディスク上の行をソートキーの順に並べ、8192行のまとまりごとに先頭のキー値だけを記録します。200万行のテーブルのインデックスはキー値245個で、圧縮したファイルで数百バイトなので、常にメモリに置いておけます。

代償は精度です。インデックスが選ぶ単位がグラニュールなので、探す行が1つでも8192行を読みます。そしてインデックスはソート順そのものなので、1つのテーブルに対してソート順は1つだけです。速くなるクエリもあれば、まったく恩恵を受けられないクエリもあります。このモジュールは、その「どちらか」を数値で見分ける方法を扱います。前のモジュールで見た「ソートキーで絞り込むときだけスキップされる」をさらに一歩進めて、2番目のキー列で絞り込むと何が起きるかを見ます。

どう動くのか

同じ200万行を、ORDER BY (site, user_id)とORDER BY (user_id, site)の2つのテーブルに入れ、245個のグラニュールのうち選ばれたものを塗り分けた図です。1つ目のテーブルでsiteで絞り込むと、docsのまとまり50個を二分探索で選びます。user_idで絞り込むと、サイトごとのまとまりから1、2個ずつ、合計9個をgeneric exclusion searchで選びます。2つ目のテーブルでuser_idで絞り込むと1個、siteで絞り込むと245個すべてを読みます

ORDER BY (site, user_id)のテーブルは、まずsiteでソートし、同じsiteの中ではuser_idでソートします。サイトが5つなら、ディスク上にはサイトごとのまとまり5つが順に並びます。ここにEXPLAIN indexes = 1を付けると、PrimaryKeyの段階が何グラニュールを選んだかがわかります。

PrimaryKey
  Keys: site
  Condition: (site in ['docs.example', 'docs.example'])
  Parts: 1/1
  Granules: 50/245
  Search Algorithm: binary search

最初のキー列で絞り込むと二分探索になります。インデックスが最初の列を基準にソートされているので、docsが始まるマークと終わるマークをすぐに見つけられます。2番目の列のuser_idだけで絞り込むと、話が変わります。user_idはサイトのまとまりごとに0からやり直すため、全体ではソートされていません。このときClickHouseはgeneric exclusion searchを使います。隣り合う2つのマークのキー値を見て、その間で前の列の値が変わらなければ、後ろの列の範囲が決まるので、「この区間に4242はない」と判定できます。前の列が変わる区間は判定できないので残します。公式ガイドの結論はこれです。このアルゴリズムは、前のキー列のカーディナリティが低いときに効果的です。ラボのPodでは、user_id = 4242で245個のうち9個が選ばれました。

キーの順序を逆にしたORDER BY (user_id, site)のテーブルでは、結果も逆になります。user_idは今度は最初の列なので、1個のグラニュールで済みます。ところがsiteで絞り込むと245/245、つまりすべてを読みます。ユーザー5万人がグラニュール245個に散らばっていて、1グラニュールに約200人が入っており、隣り合うマークの間で前の列のuser_idがほとんど毎回変わるため、どの区間も除外できません。前の列のカーディナリティが高いと、後ろの列はインデックスとして役に立ちません。

グラニュールのサイズも調整のつまみです。テーブル設定index_granularity = 1024で作ると、マークが246個から1955個に増え、user_id = 4242を探すときに読む行数は73,728から9,216に減りました。その代わり、インデックスファイル(system.partsのprimary_key_size)が大きくなります。インデックスをメモリに置く設計なので、グラニュールを細かく分けるほど、メモリを多く使います。

最後に、PRIMARY KEYとORDER BYは異なっていてもかまいません。ソートは(site, user_id, ts)で行いつつ、インデックスには(site, user_id)だけを記録させることができます。MergeTreeのドキュメントの規則は1つで、プライマリキーがソートキーの先頭部分でなければなりません。先頭部分でないものを書くと、テーブルが作成されません(「Primary key must be a prefix of the sorting key」)。ラボのPodで、同じソートの2つのテーブルを比べたところ、プライマリキーのファイルが1,620バイトから647バイトに減りました。絞り込みに使わない後ろの列は、ソートにだけ関わり、インデックスには入らなくてもかまいません。

1つ落とし穴があります。26.8はクエリ条件キャッシュがデフォルトで有効なので、同じWHEREを2回目に実行すると、「前回、条件に合う行がなかったグラニュール」をスキップします。user_id = 4242のクエリが、1回目は73,728行、2回目は40,960行を読みました。インデックスの性能を測るときは、--use_query_condition_cache 0を付けて測ります。

現場での姿

「idでソートしたのに、なぜサイト別のレポートが遅いのか」という質問をよく受けます。答えはたいていキーの順序です。クエリのWHEREにほぼ必ず入る列、その中でも種類の少ない列を先頭に置き、範囲でよく絞り込む時間の列をその後ろに置きます。1日分のサイトレポートなら、(site, ts)は(site, user_id)より読む行数を数分の1に減らします。このモジュールのラボの最後のステップがこれです。

2番目によくあるのは、「すべてのクエリを速くしたい」と、種類の多い列からキーに並べてしまうことです。後ろの列ほど、前の列が隣り合うマークの間で同じ値にとどまっていないと役に立ちません。上のgeneric exclusion searchの規則が、列ごとに重なっていくのです。絞り込みに使わない後ろの列はインデックスから外してPRIMARY KEYを先頭部分に縮め、別のソートがどうしても必要なクエリは、あとのモジュールのプロジェクションやマテリアライズドビューで解決します。

公式ドキュメント(Choosing a primary key)は、ソートキーはテーブルを作るときに決める必要があり、あとから付け足せないと述べています。ソートを変えるには新しいテーブルを作って移す必要があるので、最初に作るときに代表的なクエリ数個のEXPLAINを先に見るのが、いちばんコストの低い方法です。

次のラボですること

sparse.hitsを(site, user_id)で作って200万行を入れ、パートを1つにマージします。siteで絞り込むときとuser_idだけで絞り込むときのEXPLAINを保存して、選ばれたグラニュールと検索方式を書き写し、キーの順序を逆にしたテーブルで2つのクエリのrows_readを測ります。グラニュールを1024行に縮めたテーブルのマーク数と、PRIMARY KEYを別に指定したテーブルのインデックスサイズを比べたあと、1日分のサイトレポートのクエリに合うソートキーを選んで、読む行数を4分の1以下に減らします。