ClickHouseがグラニュール単位のデータスキッピングでTop-Nクエリを高速化する方法

TL;DR

ClickHouse は Top-N を第一級のクエリパターンとして扱います。データスキッピングインデックスの min/max メタデータを使用することで、データを読み込む前にグラニュール全体をスキップできます。本記事の例では、これにより Top-N クエリが 5〜10 倍高速化し、読み込みデータ量が 10〜100 分の 1 に削減されました。特に大規模なテーブルやコールドキャッシュで効果を発揮します。

手短な解説動画をご覧になりたいですか？
Mark が ClickHouse の Top-N クエリ最適化の仕組みを解説しています:

一般的なクエリパターンの最適化 #

ClickHouse が性能面で優位性を維持しているのは、一般的な分析クエリパターンを体系的に特定し、エンジンレベルでそのそれぞれを徹底的に最適化しているからです。

Top-N クエリは、そうしたパターンの中でも最も重要なものの一つです。

実際の分析ワークロード、ダッシュボード、監視クエリ、ランキングレポート、探索的分析などで頻繁に登場します。

「最新のイベントを表示する」

「収益上位の顧客は誰か？」

「今日の最も高額な注文はどれか？」

SELECT *
FROM orders
ORDER BY total_amount DESC
LIMIT 3;

長い時間をかけて、エンジンには Top-N クエリを高速化するために特別に設計された多数の低レベル最適化が蓄積されてきました。ストリーミング実行、read-in-order、遅延読み込み(lazy reading)などです。

本ブログでは、このツールボックスに加わったもう一つの最適化に焦点を当てます。データスキッピングインデックスを活用してデータ読み込み前に不要な処理を排除する新しい方法であり、データサイズが増大しても Top-N クエリをさらに高速化します。

ClickHouse による Top-N クエリの既存の最適化 #

ClickHouse は、Top-N クエリを効率的かつ高速に実行するため、すでにいくつかの最適化を適用しています:

1. ストリーミング Top-N(メモリ使用量の制限):
   ClickHouse はすべての行を一度にソートしません。代わりにデータをストリーミングし、現在の Top-N 候補のみを保持するため、メモリ使用量はテーブルサイズではなく N に比例した量にとどまります。

2. Read-in-order(ソートを完全に回避):
   ディスク上のデータがすでに ORDER BY カラム順に並んでいるか、プロジェクション経由でその順序で読み込める場合、ClickHouse はソートを回避して先頭の行を順番に読み込むだけで済みます。

3. 遅延読み込み(ソート対象外のカラムの読み込みを延期):
   クエリが多くのカラムを選択している場合でも、ClickHouse はまず順序付けに必要なカラムのみを使って Top-N 行を特定し、その後でそれらの行の残りのカラムを読み込むことができます。これにより I/O が劇的に削減されます。

これらの最適化は互いに直交しています。Top-N クエリ実行の異なる側面に対処するものであり、単一のクエリ内で個別に適用することも、組み合わせて適用することもできます。

これらの最適化があっても、最終的に返される行がほんの数行であっても、Top-N クエリは依然として関連するすべてのグラニュールをスキャンする必要があります。

不足していた要素: データを読み込む前にスキップする #

ClickHouse は、データスキッピングインデックスを静的または動的な Top-N フィルタリングに活用することで、Top-N クエリ向けに直交する追加の最適化を適用し、処理が必要な行数を大幅に削減します。

この記事の以降では、最もシンプルなケースから順に、この仕組みが実際にどのように機能するかを説明します。

静的 Top-N フィルタリング(述語なし) #

まずは最もシンプルなケースとして、述語やフィルターのない Top-N クエリから見ていきます。

1SELECT * FROM T ORDER BY c ASC LIMIT 3;

WHERE 句がない場合でも、ORDER BY カラム c に minmax データスキッピングインデックスが存在すれば、ClickHouse は読み込むデータ量を削減できます。

これを説明するために、テーブル T が 5 つのグラニュール(ClickHouse における最小処理単位で、デフォルトではそれぞれ 8,192 行を保持)で構成されていると仮定します。各グラニュールについて、カラム c の最小値と最大値が以下のように minmax データスキッピングインデックスに格納されています:

ORDER BY c LIMIT 3 に対して ClickHouse は以下を実行します:

• minmax インデックスの min(c) の値のみを確認する。
  最小の min 値は以下の通り:

  • グラニュール 5 → min = 1
  • グラニュール 3 → min = 5
  • グラニュール 2 → min = 10

• ディスクからはグラニュール 5、3、2 のみを読み込む

• それらの行をマージし、上位 3 つの値を返す

残りのグラニュールはすべて完全にスキップされます。

(なお、実際にはデータが複数の隣接グラニュールにまたがるブロック単位で処理され、複数のスレッドが並列でデータを処理するため、3 つを超えるグラニュールが読み込まれる場合があります。)

ベンチマーク: 静的 Top-N #

効果を示すため、匿名化された Web アナリティクスサンプルデータを使用します。gp3 EBS ボリューム(16,000 IOPS、最大スループット 1,000 MiB/s)を備えた AWS m6i.8xlarge EC2 インスタンス(32 コア、128 GB RAM)上でテーブルを作成し、データをロードしました。

述語のない Top-N クエリの例は以下の通りです:

1SELECT URL, EventTime 
2FROM hits 
3ORDER BY EventTime
4LIMIT 10;

25.12 において、データスキッピングインデックスに基づく新しい最適化を適用しない場合、3 回の実行のうち最速のものは 0.044 秒で完了しました:

110 rows in set. Elapsed: 0.044 sec. Processed 100.08 million rows, 1.20 GB (2.27 billion rows/s., 27.26 GB/s.)
2Peak memory usage: 2.23 MiB.
3
410 rows in set. Elapsed: 0.044 sec. Processed 100.08 million rows, 1.20 GB (2.29 billion rows/s., 27.56 GB/s.)
5Peak memory usage: 2.25 MiB.
6
710 rows in set. Elapsed: 0.044 sec. Processed 100.08 million rows, 1.20 GB (2.27 billion rows/s., 27.33 GB/s.)
8Peak memory usage: 2.24 MiB.

hits テーブルの約 1 億行すべてが処理されたことにご注目ください。

次に、新しい use_skip_indexes_for_top_k 設定を有効にして、データスキッピングインデックスに基づく新しい最適化を適用して同じクエリを実行します。なお、このテーブルには EventTime カラムに minmax データスキッピングインデックスが設定されています。

1SELECT URL, EventTime 
2FROM hits 
3ORDER BY EventTime
4LIMIT 10
5SETTINGS use_skip_indexes_for_top_k = 1;

この場合、3 回の実行のうち最速のものは 0.009 秒で完了しました:

110 rows in set. Elapsed: 0.009 sec. Processed 163.84 thousand rows, 4.95 MB (17.48 million rows/s., 528.35 MB/s.)
2Peak memory usage: 917.51 KiB.
3
410 rows in set. Elapsed: 0.009 sec. Processed 163.84 thousand rows, 4.95 MB (18.03 million rows/s., 544.98 MB/s.)
5Peak memory usage: 198.47 KiB.
6
710 rows in set. Elapsed: 0.009 sec. Processed 163.84 thousand rows, 4.95 MB (18.19 million rows/s., 549.68 MB/s.)
8Peak memory usage: 198.47 KiB.

これは以前と比べて約 5 倍高速です。テーブル全体の約 1 億行を処理する代わりに、ClickHouse は約 16 万 3,000 行のみを処理し、読み込みデータ量を約 1.2 GB からわずか 4.95 MB に削減しました。

この I/O 面のメリットはテーブルサイズとともに大きくなります。テーブルが数十億行、数兆行に達し、特にキャッシュがコールドな状態では、グラニュールレベルで不要な読み込みを回避することがますます大きな効果を生み出します。

重要なのは、この削減が行を読み込む前に、グラニュールレベルのメタデータのみに基づいて行われる点です。

動的 Top-N 閾値フィルタリング(述語あり) #

ここまでは、ORDER BY カラムの静的な min/max メタデータを使用してグラニュールを事前選択できる、述語なしの Top-N クエリを見てきました。

Top-N クエリに述語も含まれる場合、データスキッピングは動的になります。

クエリの実行中、ClickHouse は現在の Top-N 結果セットを継続的に維持します。現在の N 番目の値が、実質的に動的な閾値として機能します。

このメカニズムは、ClickHouse 25.9 で導入されたセカンダリインデックス向けストリーミングを基盤としています。データスキッピングインデックスを事前に評価するのではなく、ClickHouse はデータスキッピングインデックスのチェックとデータ読み込みを交互に行います。(述語評価のためのプライマリインデックス分析を経て)グラニュールが読み込み対象になるとすぐに、対応する minmax データスキッピングインデックスのエントリが参照されます。

その時点で、現在の Top-N 閾値がグラニュールの min/max メタデータと比較されます。グラニュールに Top-N 結果セットを改善する値が含まれる可能性がない場合、そのグラニュールは即座にスキップされ、読み込まれることはありません。

実行が進んでより良い Top-N 候補が見つかるにつれて閾値はさらに厳しくなり、ClickHouse はクエリ実行中に動的に除外できるグラニュールの数を増やしていきます。Top-N の結果が揃った時点でクエリは停止するため、閾値が厳しくなるほど、ClickHouse はより早い段階でグラニュールの読み込みとスキップを終了できます。

ベンチマーク: 動的 Top-N #

これらのメカニズムの有効性を、今度は述語を含む別の Top-N クエリの例で実証します:

1SELECT URL,EventTime 
2FROM hits 
3WHERE URL LIKE '%google%'
4ORDER BY EventTime
5LIMIT 10;

25.12 において、データスキッピングインデックスに基づく新しい動的 Top-N 閾値フィルタリングを適用しない場合、3 回の実行のうち最速のものは 0.325 秒で完了しました。実行ごとの素のデータ処理動作を得るため、すべての実行でクエリ条件キャッシュを無効化しています。

110 rows in set. Elapsed: 0.333 sec. Processed 100.00 million rows, 9.42 GB (299.96 million rows/s., 28.26 GB/s.)
2Peak memory usage: 143.92 MiB.
3
410 rows in set. Elapsed: 0.325 sec. Processed 100.00 million rows, 9.42 GB (307.37 million rows/s., 28.95 GB/s.)
5Peak memory usage: 138.46 MiB.
6
710 rows in set. Elapsed: 0.334 sec. Processed 100.00 million rows, 9.42 GB (299.55 million rows/s., 28.22 GB/s.)
8Peak memory usage: 147.47 MiB.

hits テーブルの 1 億行すべてが処理されたことにご注目ください。

次に、セカンダリインデックス向けストリーミングを有効にし、新しい use_top_k_dynamic_filtering 設定を有効にすることで、データスキッピングインデックスに基づく新しい動的 Top-N 閾値フィルタリングを適用して同じクエリを実行します。なお、このテーブルには EventTime カラムに minmax データスキッピングインデックスが設定されており、動的 Top-N 閾値フィルタリングの効果を完全に切り分けるため、すべての実行でクエリ条件キャッシュを無効化しています。

1SELECT URL,EventTime 
2FROM hits 
3WHERE URL LIKE '%google%'
4ORDER BY EventTime
5LIMIT 10
6SETTINGS
7  use_query_condition_cache = 0,
8  use_skip_indexes_on_data_read = 1,
9  use_skip_indexes_for_top_k = 1,
10  use_top_k_dynamic_filtering = 1;

この場合、3 回の実行のうち最速のものは 0.033 秒で完了しました:

110 rows in set. Elapsed: 0.034 sec. Processed 7.66 million rows, 515.98 MB (227.36 million rows/s., 15.32 GB/s.)
2Peak memory usage: 51.30 MiB.
3
410 rows in set. Elapsed: 0.034 sec. Processed 7.59 million rows, 509.67 MB (224.45 million rows/s., 15.08 GB/s.)
5Peak memory usage: 51.29 MiB.
6
710 rows in set. Elapsed: 0.033 sec. Processed 7.67 million rows, 520.58 MB (234.95 million rows/s., 15.96 GB/s.)
8Peak memory usage: 47.28 MiB.

これは以前と比べて約 10 倍高速です。テーブル全体の約 1 億行を処理する代わりに、ClickHouse は約 700 万行のみを処理し、読み込みデータ量を約 9.42 GB から約 520.58 MB に削減しました。

前述の例と同様に、この I/O 面のメリットはテーブルサイズとともに大きくなります。テーブルが数十億行や数兆行に達する場合(特にキャッシュがコールドな場合)、現在の Top-N 結果を改善できないグラニュールを動的にスキップすることは、ますます大きな効果を生み出します。

前述の通り、ClickHouse はクエリ実行中に現在の Top-N 閾値を継続的に維持し、minmax データスキッピングインデックスを使用して、Top-10 の結果を改善できない値を持つグラニュールを動的にスキップすることでこれを実現しています。

本番規模での検証 #

これらのメカニズムは、非常に大規模な本番テーブルでも検証されています。

500 億行のテーブルを対象とした初期テストでは、スキッピングインデックスフィルタリングを使用した Top-N クエリが 0.2 秒未満で完了し、極端な規模であってもグラニュールレベルのプルーニングが有効であることが確認されました。今後の改善により、さらに高速化される見込みです。

Top-N をメタデータの問題へと転換する #

データスキッピングに基づく Top-N フィルタリングにより、ClickHouse は Top-N クエリをメタデータ主導のプルーニング問題へと転換します。

現在の Top-N 閾値とグラニュールレベルの min/max メタデータを比較することで、ClickHouse は 1 行も読み込むことなくテーブルの大部分をスキップできます。シンプルな Top-N クエリでは、このプルーニングは事前に実行されます。述語を含むクエリでは、実行が進んで閾値が厳しくなるにつれて動的に実行されます。

このようなメタデータ主導のプルーニングは、オブジェクトストレージやコンピュート・ストレージ分離型のモダンなアーキテクチャにおいて特に強力です。不要な読み込みを回避することで、CPU だけでなくネットワーク I/O やレイテンシも削減できるためです。

本記事の例では、このアプローチにより結果を改善できないグラニュールをスキップするだけで、Top-N クエリを 5〜10 倍高速化し、読み込みデータ量を 1〜2 桁削減できました。

極めて重要な点として、この最適化はストリーミング実行、read-in-order、遅延読み込みといった既存の Top-N テクニックと共存します。それぞれの最適化が異なるボトルネックに対処するため、これらを組み合わせることで、ClickHouse は Top-N クエリを数百万行から数十億行へと効率的にスケールさせることができます。

ユーザーにとっては、おなじみの ORDER BY … LIMIT N というクエリパターンが、データ量の増加に伴ってより積極的なプルーニングの恩恵を受けられるようになることを意味します。一般的なクエリパターンを、データに一切触れる前に解決可能な問題として扱うことによって。