メインコンテンツへスキップ
メインコンテンツへスキップ

なぜ ClickHouse はこれほど高速なのか？

データベースの性能は、データの指向性 だけでなく、多くの要因に左右されます。 ここでは、特に他のカラム指向データベースと比較したときに、ClickHouse がこれほど高速に動作する理由について、より詳しく説明します。

アーキテクチャの観点から見ると、データベースは少なくともストレージレイヤーとクエリ処理レイヤーで構成されます。ストレージレイヤーはテーブルデータの保存・読み込み・管理を担い、クエリ処理レイヤーはユーザーのクエリを実行します。ClickHouse は他のデータベースと比べて、この両方のレイヤーにおいて革新的な仕組みを備えており、非常に高速な挿入処理と SELECT クエリを実現しています。

ストレージ層：同時に行われる INSERT は互いに独立している​

ClickHouse では、各テーブルは複数の「テーブルパーツ」から構成されます。ユーザーがテーブルにデータを挿入するたび（INSERT 文）に、新しい part が作成されます。クエリは、クエリの実行開始時点で存在するすべてのテーブルパーツに対して常に実行されます。

パーツが過剰に蓄積されるのを避けるために、ClickHouse はバックグラウンドで merge 処理を実行し、複数の小さいパーツを継続的に 1 つの大きなパーツへと結合します。

このアプローチにはいくつかの利点があります。すべてのデータ処理を バックグラウンドでのパーツマージにオフロード できるため、データ書き込みは軽量かつ非常に効率的になります。個々の INSERT は、「グローバル」、すなわちテーブル単位のデータ構造を更新する必要がないという意味で「ローカル」です。その結果、複数の同時 INSERT は互いに、あるいは既存のテーブルデータと同期をとる必要がなく、INSERT はディスク I/O の速度にほぼ近い速度で実行できます。

🤿 この内容の詳細は、VLDB 2024 論文の Web 版の On-Disk Format セクションを参照してください。

ストレージレイヤー：同時実行される INSERT と SELECT の分離​

INSERT は SELECT クエリから完全に分離されており、挿入されたデータパーツのマージ処理は、同時実行中のクエリに影響を与えることなくバックグラウンドで行われます。

🤿 このトピックの詳細は、VLDB 2024 論文の Web 版の Storage Layer セクションで解説しています。

ストレージ層: マージ時の計算​

他のデータベースとは異なり、ClickHouse はすべての付加的なデータ変換処理をバックグラウンドの merge プロセス中に実行することで、データ書き込みを軽量かつ効率的に保っています。これには次のようなものがあります：

  • Replacing merge: 入力パーツ内の行について、最新バージョンのみを保持し、それ以外のすべての行バージョンを破棄します。Replacing merge は、マージ時に行うクリーンアップ処理と考えることができます。

  • Aggregating merge: 入力パーツ内の中間集約状態を結合して、新しい集約状態を作成します。一見すると理解が難しそうに見えますが、実際にはインクリメンタルな集約を実装しているだけです。

  • TTL (time-to-live) merge: 特定の時間ベースのルールに基づいて、行を圧縮・移動・削除します。

これらの変換のポイントは、ユーザークエリの実行時点からマージの実行時点へと処理（計算）を移すことです。これは次の 2 つの理由で重要です。

一方で、ユーザークエリは「変換済み」データ、例えば事前集約されたデータを活用できる場合、場合によっては 1000 倍以上高速になることがあります。

他方で、マージの実行時間の大部分は、入力パーツの読み込みと出力パーツの保存に費やされます。マージ中にデータを変換するための追加の処理は、通常マージの実行時間にそれほど大きな影響を与えません。これらすべての仕組みは完全に透過的であり、（パフォーマンス以外では）クエリ結果に影響を与えません。

🤿 この内容については、VLDB 2024 論文の Web 版にある Merge-time Data Transformation セクションでさらに深く掘り下げています。

ストレージ層: データプルーニング​

実際には、多くのクエリは繰り返し実行されます。つまり、定期的な間隔で、まったく同じか、わずかな変更（例: パラメータ値のみ変更）だけを加えて実行されます。同じ、あるいは類似したクエリを何度も実行することで、インデックスを追加したりデータを再編成し、頻出クエリがより高速にアクセスできるようにすることができます。このアプローチは「データプルーニング」とも呼ばれ、ClickHouse はそのために次の 3 つの手法を提供しています。

  1. テーブルデータのソート順序を定義する Primary key indexes。適切に選択された primary key により、上記クエリの WHERE 句のようなフィルタを、全カラムスキャンではなく高速な二分探索で評価できます。より技術的に言えば、スキャンの実行時間はデータサイズに対して線形ではなく対数オーダーになります。

  2. テーブルの代替的な内部バージョンとしての Table projections。同じデータを保持しつつ、別の primary key でソートして保存します。頻出するフィルタ条件が複数ある場合に projections が有用です。

  3. カラム内に追加のデータ統計情報（例: 最小値・最大値、ユニーク値の集合など）を埋め込む Skipping indexes。Skipping indexes は primary key や table projections とは直交する概念であり、カラム内のデータ分布によってはフィルタ評価を大幅に高速化できます。

これら 3 つの手法はすべて、フルカラム読み取りの際にできるだけ多くの行をスキップすることを目的としています。なぜなら、データを読む最速の方法は「そもそも読まないこと」だからです。

🤿 このトピックの詳細は、VLDB 2024 論文の Web 版にある Data Pruning セクションを参照してください。

ストレージレイヤー: データ圧縮​

これに加えて、ClickHouse のストレージレイヤーは、生のテーブルデータをさまざまなコーデックを用いて追加で（かつオプションで）圧縮します。

カラムストアは、同じ型で似たデータ分布を持つ値がまとまって配置されるため、このような圧縮に特に適しています。

ユーザーは、カラムがさまざまな汎用圧縮アルゴリズム（ZSTD など）や特殊なコーデックを使って圧縮されるように指定できます。例えば、浮動小数点値には Gorilla や FPC、整数値には Delta や GCD、さらには暗号化コーデックとして AES を使用できます。

データ圧縮は、データベーステーブルのストレージサイズを削減するだけでなく、多くの場合クエリ性能も向上させます。ローカルディスクやネットワーク I/O がしばしばスループットの制約を受けるためです。

🤿 これについてさらに詳しくは、VLDB 2024 論文の Web 版の On-Disk Format セクションを参照してください。

最先端のクエリ処理レイヤー​

最後に、ClickHouse はベクトル化クエリ処理レイヤーを採用しており、クエリ実行を可能な限り並列化することで、最大限の速度と効率を得るためにすべてのリソースを活用します。

「ベクトル化」とは、クエリプランのオペレーターが中間結果の行を 1 行ずつではなくバッチ単位で渡すことを意味します。これにより CPU キャッシュをより有効に活用でき、オペレーターは SIMD 命令を適用して複数の値を一度に処理できます。実際、多くのオペレーターは SIMD 命令セットの世代ごとに複数のバージョンを持っています。ClickHouse は、実行しているハードウェアの機能に基づいて、最新かつ最速のバージョンを自動的に選択します。

最新のシステムには多数の CPU コアがあります。すべてのコアを活用するために、ClickHouse はクエリプランを複数のレーンに展開し、通常はコアごとに 1 レーンを割り当てます。各レーンはテーブルデータの重複しない範囲を処理します。こうすることで、利用可能なコア数に応じて、データベースの性能は「垂直方向」にスケールします。

1 台のノードではテーブルデータを保持するには小さすぎる場合、ノードを追加してクラスタを構成できます。テーブルは分割（シャーディング）され、ノード間で分散できます。ClickHouse はテーブルデータを保持するすべてのノード上でクエリを実行し、利用可能なノード数に応じて「水平方向」にスケールします。

🤿 この内容については、VLDB 2024 論文の Web 版にある Query Processing Layer セクションで詳しく解説しています。

細部まで徹底したこだわり​

「ClickHouse は freak system だ ― 君たちはハッシュテーブルを 20 種類も持っている。ほとんどのシステムは 1 種類しか持たないのに、君たちはこんなに素晴らしいものをたくさん持っている」 ... 「ClickHouse が驚異的なパフォーマンスを発揮できるのは、こうした特化コンポーネントを数多く備えているからだ」 Andy Pavlo, Database Professor at CMU

ClickHouse を際立たせているのは、低レベルな最適化への徹底したこだわりです。単に動作するデータベースを作ることと、多様なクエリタイプ、データ構造、分布、インデックス構成にわたってスピードを出せるように設計・実装することとは別物です。この「freak system」的な職人芸が真価を発揮するのは、まさにこの後者の領域です。

ハッシュテーブル。 例としてハッシュテーブルを考えてみましょう。ハッシュテーブルは、結合や集約で用いられる中核的なデータ構造です。プログラマとしては、次のような設計判断を検討する必要があります。

  • どのハッシュ関数を選ぶか
  • 衝突解決方法: オープンアドレッシングか、チェイニングか
  • メモリレイアウト: キーと値を 1 つの配列にするか、別々の配列にするか
  • 充填率: いつ、どのようにリサイズするか？ リサイズ時に値をどう移動させるか？
  • 削除: ハッシュテーブルでエントリの削除（追い出し）を許可すべきか？

サードパーティライブラリが提供する標準的なハッシュテーブルでも機能的には動作しますが、高速ではありません。優れたパフォーマンスには、入念なベンチマークと試行錯誤が不可欠です。

ClickHouse のハッシュテーブル実装は、クエリとデータの特性に基づいて、30 種類以上の事前コンパイル済みハッシュテーブルのバリアントの中から最適なものを選択します。

アルゴリズム。 アルゴリズムについても同様です。例えばソートであれば、次の点を検討します。

  • 何をソートするのか: 数値、タプル、文字列、構造体のどれか？
  • データは RAM 上にあるか？
  • 安定ソートである必要があるか？
  • すべてのデータをソートする必要があるか、それとも部分ソートで十分か？

データ特性に依存したアルゴリズムは、汎用的なものより高い性能を発揮することがよくあります。データ特性が事前には分からない場合、システムはさまざまな実装を試し、実行時に最もよく動作するものを選択できます。例としては、ClickHouse における LZ4 伸長の実装方法に関する記事を参照してください。

🤿 このテーマについては、VLDB 2024 論文の Web 版にあるホリスティックなパフォーマンス最適化のセクションで詳しく解説しています。

VLDB 2024 paper​

2024年8月、私たちの初めての研究論文がVLDBで採択され、論文集に掲載されました。 VLDBは、大規模データベースに関する国際会議であり、データマネジメント分野を代表する主要な会議の1つとして広く認識されています。 数百件におよぶ投稿のうち、採択率はおおよそ20%程度です。

論文のPDF版や、そのWeb版をお読みいただけます。 Web版では、ClickHouseを非常に高速にしている、最も興味深いアーキテクチャおよびシステム設計コンポーネントについて簡潔に説明しています。

ClickHouseのCTOであり開発者である Alexey Milovidov がこの論文を発表しました（スライドはこちら）。 その後に行われたQ&Aセッションは、すぐに時間切れになってしまいました。 発表の録画は以下から視聴できます。