アーキテクチャ概要

2024年の VLDB 論文のドキュメント版

これは、VLDB 2024 の学術論文の Web 版です。背景や公開までの経緯についてはブログ記事でも紹介しています。あわせて、ClickHouse の CTO であり生みの親でもある Alexey Milovidov による VLDB 2024 のプレゼンテーションもぜひご覧ください。

​

要旨

ここ数十年で、保存・分析されるデータ量は指数関数的に増加してきた。業種や分野を問わず、多くの企業が、製品の改善、パフォーマンスの評価、そして事業上重要な意思決定のためにこうしたデータに依存するようになっている。しかし、データ量がますますインターネットスケールへと拡大するにつれ、企業には、履歴データと新規データをコスト効率とスケーラビリティを保ちながら管理しつつ、多数の同時実行クエリによって、リアルタイムのレイテンシ (ユースケースによっては1秒未満など) で分析することが求められるようになった。

本稿では、高いインジェスト率でペタバイト規模のデータセットに対する高性能分析向けに設計された、広く利用されているオープンソースのOLAPデータベースであるClickHouseの概要を示す。そのストレージ層は、従来のログ構造マージ (LSM) ツリーに基づくデータフォーマットと、履歴データをバックグラウンドで継続的に変換 (たとえば集約やアーカイブ) する新しい手法を組み合わせている。クエリは扱いやすいSQL方言で記述され、必要に応じてコードコンパイルを行う最先端のベクトル化クエリ実行エンジンによって処理される。ClickHouseは、クエリで無関係なデータを評価しないよう、プルーニング技法を積極的に活用している。ほかのデータ管理システムは、table function、テーブルエンジン、またはデータベースエンジンのレベルで統合できる。実環境でのベンチマークは、ClickHouseが市場で最速級の分析データベースの1つであることを示している。

​

1 はじめに

本稿では、数兆行・数百カラムのテーブルに対する高性能な分析クエリ向けに設計された列指向OLAPデータベースである ClickHouse について説明します。ClickHouse は 2009 年に、Web スケールのログファイルデータ向けのフィルタおよび集約演算子として始まり、2016 年にオープンソース化されました。図 1 は、本稿で説明する主要な機能が ClickHouse に導入された時期を示しています。

ClickHouse は、現代の分析データ管理における 5 つの重要な課題に対応するよう設計されています。

1. 高いインジェスト率を伴う巨大なデータセット。Web analytics、金融、e-commerce などの分野における多くのデータ駆動型アプリケーションは、巨大で継続的に増加するデータ量を特徴としています。こうした巨大なデータセットを扱うには、分析データベースは効率的な索引付けと圧縮戦略を提供するだけでなく、単一のサーバーでは数十テラバイトのストレージに限られるため、データを複数ノードに分散できること (スケールアウト) も必要です。さらに、リアルタイムの洞察では、過去のデータよりも最新のデータの方が重要であることが少なくありません。その結果、分析データベースには、新しいデータを継続的に高いレートで、あるいはバースト的に取り込めることに加え、並行して実行されるレポート用クエリを遅くすることなく、過去データの優先度を継続的に下げること (たとえば集約やアーカイブ) が求められます。

2. 低レイテンシが求められる多数の同時クエリ。クエリは一般に、アドホックなもの (たとえば探索的データ分析) と定常的なもの (たとえば定期的な dashboard クエリ) に分類できます。ユースケースの対話性が高いほど、より低いクエリレイテンシが求められ、クエリ最適化と実行における課題が大きくなります。定常的なクエリではさらに、workload に合わせてデータベースの物理レイアウトを最適化する機会も得られます。そのため、データベースは、頻出クエリを最適化できるプルーニング手法を提供すべきです。また、クエリの優先度に応じて、多数のクエリが同時に実行されている場合でも、CPU、メモリ、ディスク、ネットワーク I/O などの共有システムリソースへの均等または優先的なアクセスを提供しなければなりません。

3. 多様なデータストア、保存場所、フォーマットの環境。既存のデータアーキテクチャと統合するために、現代の分析データベースは、あらゆるシステム、場所、フォーマットにある外部データを読み書きできるよう、高い開放性を備えている必要があります。

4. 性能の詳細な分析を支援する、使いやすいクエリ言語。OLAP データベースの実運用では、さらに「ソフト」な要件も生じます。たとえば、ニッチなプログラミング言語ではなく、ユーザーはしばしば、ネストしたデータ型と幅広い通常の関数、集約関数、ウィンドウ関数を備えた表現力の高い SQL方言 を通じてデータベースとやり取りすることを好みます。また、分析データベースは、システム全体や個々のクエリの性能を詳しく調べるための高度なツールも提供すべきです。

5. 業界水準の堅牢性と柔軟なデプロイ。汎用ハードウェアは信頼性が高いとは限らないため、データベースはノード障害に対する堅牢性を確保するためにデータのレプリケーションを提供しなければなりません。また、データベースは古いラップトップから高性能なサーバーまで、あらゆるハードウェア上で動作する必要があります。最後に、JVM ベースのプログラムにおけるガーベジコレクションのオーバーヘッドを避け、ベアメタル性能 (たとえば SIMD) を実現するために、データベースは理想的には対象プラットフォーム向けのネイティブバイナリとしてデプロイされます。

​

2 アーキテクチャ

図2に示すように、ClickHouseエンジンは3つの主要な層、すなわちクエリ処理層 (4節で説明) 、ストレージ層 (3節) 、インテグレーション層 (5節) に分かれています。これらに加えて、アクセス層がユーザーセッションの管理と、さまざまなプロトコルを介したアプリケーションとの通信を担います。さらに、スレッド処理、cache、ロールベースアクセス制御、バックアップ、継続的な監視のための独立したコンポーネントも存在します。ClickHouseは、依存関係のない単一の静的リンク済みバイナリとしてC++で構築されています。

クエリ処理は、受信したクエリのパース、論理および物理クエリプランの構築と最適化、そして実行という従来のパラダイムに従います。ClickHouseは、MonetDB/X100 ^[11] に類似したベクトル化実行モデルを、機会的なコードコンパイル ^[53] と組み合わせて使用します。クエリは、高機能なSQL方言、PRQL ^[76]、またはKustoのKQL ^[50] で記述できます。

ストレージ層は、テーブルデータのフォーマットと格納場所をカプセル化するさまざまなテーブルエンジンで構成されます。テーブルエンジンは3つのカテゴリに分類されます。第1のカテゴリは MergeTree* ファミリーのテーブルエンジンで、ClickHouseにおける主要な永続化フォーマットを表します。LSMツリー ^[60] の考え方に基づき、テーブルは水平方向に分割されたソート済みパーツに分かれ、それらはバックグラウンドプロセスによって継続的にマージされます。個々の MergeTree* テーブルエンジンは、マージ時に入力パーツの行をどのように結合するかという点で異なります。たとえば、古い行は集計または置換できます。

第2のカテゴリは特殊用途のテーブルエンジンで、クエリ実行の高速化や分散に使用されます。このカテゴリには、Dictionary と呼ばれるインメモリのキー・バリューテーブルエンジンが含まれます。dictionary は、内部または外部のデータソースに対して定期的に実行されるクエリの結果を cache します。これにより、ある程度のデータの古さを許容できるシナリオでは、アクセスレイテンシを大幅に低減できます。特殊用途のテーブルエンジンの他の例としては、一時テーブルに使用される純粋なインメモリエンジンや、透過的なデータシャーディングのための Distributed テーブルエンジン (後述) があります。

第3のカテゴリのテーブルエンジンは、リレーショナルデータベース (例: PostgreSQL、MySQL) 、publish/subscribe システム (例: Kafka、RabbitMQ ^[24]) 、またはキー・バリューストア (例: Redis) などの外部システムと双方向にデータをやり取りするための仮想テーブルエンジンです。仮想エンジンは、データレイク (例: Iceberg、Delta Lake、Hudi ^[36]) やオブジェクトストレージ内のファイル (例: AWS S3、Google GCP) とも連携できます。

ClickHouse は、スケーラビリティと可用性を実現するために、複数のクラスター ノードにまたがるテーブルのシャーディングとレプリケーションをサポートしています。シャーディングでは、シャーディング式に従ってテーブルを一連の分片に分割します。各分片は相互に独立したテーブルで、通常は異なるノードに配置されます。クライアントは分片を直接読み書きして個別のテーブルとして扱うことも、すべての分片をグローバルに見渡せる特別なテーブルエンジン Distributed を使用することもできます。シャーディングの主な目的は、個々のノードの容量を超えるデータセット (通常は数十 TB 規模) を処理することです。また、テーブルの read-write 負荷を複数ノードに分散し、負荷分散を実現する目的でも利用されます。これとは別に、ノード障害への耐性を高めるため、1 つの分片を複数ノードにレプリケートすることもできます。そのため、各 Merge-Tree* テーブルエンジンには対応する ReplicatedMergeTree* エンジンが用意されており、Raft コンセンサス ^[59] に基づくマルチマスターの協調スキーム (Apache Zookeeper のドロップイン置換として C++ で実装された Keeper を使用) によって、すべての分片が常に設定可能な数のレプリカを持つことを保証します。セクション 3.6 では、このレプリケーション機構を詳しく説明します。例として、Figure 2 には、2 つの分片を持ち、それぞれが 2 つのノードにレプリケートされたテーブルが示されています。

最後に、ClickHouse データベースエンジンは、オンプレミス、クラウド、スタンドアロン、またはインプロセス モードで運用できます。オンプレミス モードでは、ユーザーは ClickHouse を単一サーバーとして、またはシャーディングやレプリケーションを備えたマルチノード クラスターとしてローカルにセットアップします。クライアントは、native、MySQL、PostgreSQL のバイナリ wire protocol、または HTTP REST API を介してデータベースと通信します。クラウド モードは、完全マネージド型かつオートスケーリング対応の DBaaS である ClickHouse Cloud によって提供されます。本稿ではオンプレミス モードに焦点を当てていますが、続編の文献で ClickHouse Cloud のアーキテクチャを説明する予定です。standalone mode では、ClickHouse はファイルの分析や変換を行うコマンドライン ユーティリティとして動作し、cat や grep などの Unix ツールに対する SQL ベースの代替手段となります。事前の設定は不要ですが、standalone mode は単一サーバーに限定されます。最近では、Jupyter notebooks ^[37] や Pandas DataFrame ^[61] を使った対話的データ分析のユースケース向けに、chDB ^[15] と呼ばれるインプロセス モードが開発されました。DuckDB ^[67] に着想を得た chDB は、ClickHouse を高性能な OLAP エンジンとしてホスト プロセスに組み込みます。他のモードと比べると、同じアドレス空間で実行されるため、コピーを伴わずにソース データと結果データをデータベースエンジンとアプリケーションの間で効率的に受け渡せます。

​

3 ストレージ層

この節では、ClickHouseのネイティブなストレージフォーマットである MergeTree* テーブルエンジンについて説明します。まず、そのディスク上の表現を説明し、続いて ClickHouse における 3 つのデータプルーニング手法を取り上げます。その後、同時実行中の insert に影響を与えることなくデータを継続的に変換する merge 戦略を紹介します。最後に、update と delete の実装方法に加え、データの重複排除、データのレプリケーション、および ACID 準拠について説明します。

​

3.1 ディスク上のフォーマット

MergeTree* テーブルエンジンの各テーブルは、不変なテーブルパーツの集合として構成されます。パーツは、行のまとまりがテーブルに挿入されるたびに作成されます。パーツは自己完結型であり、その内容を解釈するために必要なすべてのメタデータを含むため、中央カタログに追加でルックアップしなくても扱えます。テーブルごとのパーツ数を少なく保つため、バックグラウンドのマージジョブが複数の小さなパーツを定期的に 1 つの大きなパーツへ統合し、設定可能なパーツサイズ (デフォルトは 150 GB) に達するまでこれを続けます。パーツはテーブルの主キーカラムでソートされているため (Section 3.2) を参照) 、マージには効率的な k-way マージソート ^[40] が用いられます。元のパーツは非アクティブとしてマークされ、参照カウントがゼロ、つまりそれらを参照するクエリがなくなると、最終的に削除されます。

行は 2 つのモードで挿入できます。同期挿入モードでは、各 INSERT ステートメントごとに新しいパーツが作成され、テーブルに追加されます。マージのオーバーヘッドを最小限に抑えるため、データベースクライアントはタプルをまとめて挿入することが推奨されます。たとえば、一度に 20,000 行を挿入します。ただし、データをリアルタイムで分析する必要がある場合、クライアント側のバッチ処理による遅延はしばしば許容できません。たとえば、オブザーバビリティのユースケースでは、何千もの監視エージェントが少量のイベントデータやメトリクスデータを継続的に送信することがよくあります。このようなシナリオでは非同期挿入モードを利用できます。このモードでは、ClickHouse は同じテーブルに対する複数の受信 INSERT の行をバッファリングし、バッファサイズが設定可能なしきい値を超えるか、タイムアウトになるまで新しいパーツを作成しません。

図 3 は、MergeTree* エンジンのテーブルに対する 4 回の同期挿入と 2 回の非同期挿入を示しています。2 回のマージによって、アクティブなパーツ数は当初の 5 個から 2 個に減少しました。

LSM ツリー ^[58] と、さまざまなデータベースにおけるその実装 ^{[13, 26, [56]](#page-13-8)} と比べると、ClickHouse はすべてのパーツを階層構造に配置するのではなく、対等なものとして扱います。その結果、マージは同じレベルのパーツに限定されません。一方で、これによりパーツの暗黙的な時系列順も失われるため、トゥームストーンに基づかない更新および削除のための別の仕組みが必要になります (Section 3.4) を参照) 。ClickHouse は挿入を直接ディスクに書き込みますが、他の LSM ツリーベースのストアでは通常、先行書き込みログが使われます (Section 3.7) を参照) 。

1 つの パーツ はディスク上のディレクトリに対応しており、各カラムにつき 1 つのファイルを含みます。最適化のため、小さな パーツ (デフォルトでは 10 MB 未満) のカラムは、read/write 時の空間的局所性を高めるべく、1 つのファイルに連続して格納されます。パーツ の行はさらに論理的に 8192 レコードごとのグループに分割され、これを グラニュール と呼びます。グラニュール は、ClickHouse において scan 演算子および index ルックアップ演算子が処理する、最小の不可分データ単位です。ただし、ディスク上のデータの read/write は グラニュール 単位ではなく、1 つのカラム内で隣接する複数の グラニュール をまとめた block 単位で行われます。新しい block は、block ごとに設定可能なバイトサイズ (デフォルトでは 1 MB) に基づいて形成されます。つまり、1 つの block に含まれる グラニュール 数は可変であり、カラムの data type と distribution に依存します。さらに、block はサイズと I/O コストを削減するために圧縮されます。デフォルトでは、ClickHouse は汎用の圧縮アルゴリズムとして LZ4 ^[75] を使用しますが、ユーザーは浮動小数点データ向けに Gorilla ^[63] や FPC ^[12] のような専用 codec を指定することもできます。圧縮アルゴリズムは連鎖させることもできます。たとえば、まず delta coding ^[23] を使って数値の論理的冗長性を減らし、次に高圧縮率の圧縮を行い、最後に AES codec でデータを暗号化することが可能です。block は、ディスクから memory にロードされる際にオンザフライで伸長されます。圧縮されていても個々の グラニュール への高速なランダムアクセスを可能にするため、ClickHouse はさらに各カラムについて、各 グラニュール id を、その グラニュール を含む圧縮済み block の column file 内でのオフセットと、非圧縮 block 内での グラニュール のオフセットに対応付けるマッピングを保存します。

カラムにはさらに、Dictionary encoding ^{[2, 77, [81]](#page-13-12)} を適用したり、2 つの特別なラッパー data type を使って Nullable にしたりできます。LowCardinality(T) は元のカラム値を整数 id に置き換えることで、ユニークな値が少ないデータのストレージオーバーヘッドを大幅に削減します。Nullable(T) はカラム T に内部 bitmap を追加し、カラム値が NULL かどうかを表します。

最後に、table は任意のパーティション化式を用いて、range、hash、または round-robin でパーティション化できます。partition pruning を可能にするため、ClickHouse はさらに各パーティションについて、パーティション化式の最小値と最大値を保存します。ユーザーは必要に応じて、カーディナリティ推定も提供する、より高度なカラム STATISTICS (例: HyperLogLog ^[30] や t-digest ^[28] statistics) を作成することもできます.

​

3.2 データプルーニング

ほとんどのユースケースでは、1つのクエリに答えるためだけにPB規模のデータをスキャンするのは、遅すぎるうえコストもかかりすぎます。ClickHouseは、検索時に大半の行をスキップし、クエリを大幅に高速化できる3つのデータプルーニング手法をサポートしています。

まず、ユーザーはテーブルに主キー索引を定義できます。主キーカラムは、各パーツ内での行のソート順を決定します。つまり、この索引はローカルにクラスター化されています。さらにClickHouseは各パーツについて、各グラニュールの先頭行の主キーカラム値から、そのグラニュールのidへの対応を保持します。つまり、この索引はスパースです ^[31]。このデータ構造は通常、全体をメモリ内に保持できるほど小さく、たとえば810万行の索引付けに必要なエントリは1000件だけです。主キーの主な目的は、逐次スキャンではなく二分探索を使って、頻繁にフィルタされるカラムに対する等価条件や範囲条件を評価することです (Section 4.4)) 。さらに、このローカルなソート順は、パーツのマージやクエリ最適化にも活用できます。たとえば、ソートベースの集約や、主キーカラムがソートカラムのプレフィックスを成している場合に、物理実行計画からソート演算子を取り除くことが可能です。

Figure 4は、ページインプレッション統計を持つテーブルのカラムEventTime上の主キー索引を示しています。クエリ内の範囲条件に一致するグラニュールは、EventTimeを逐次スキャンする代わりに、主キー索引を二分探索することで見つけられます。

次に、ユーザーはテーブルプロジェクションを作成できます。これは、同じ行を含みながら、異なる主キーでソートされたテーブルの別バージョンです ^[71]。プロジェクションを使うと、メインテーブルの主キーとは異なるカラムでフィルタするクエリを高速化できますが、その代償としてinsert、merge、および容量消費のオーバーヘッドが増加します。デフォルトでは、プロジェクションはメインテーブルに新たに挿入されたパーツからのみ遅延的に生成され、ユーザーがプロジェクション全体をmaterializeしない限り、既存のパーツからは生成されません。クエリオプティマイザは、推定I/Oコストに基づいて、メインテーブルとプロジェクションのどちらを読み取るかを選択します。あるパーツにプロジェクションが存在しない場合、クエリ実行は対応するメインテーブルのパーツにフォールバックします。

3つ目に、スキッピング索引はプロジェクションに代わる軽量な選択肢を提供します。スキッピング索引の考え方は、連続する複数のグラニュール単位で少量のメタデータを保存し、それによって無関係な行のスキャンを回避するというものです。スキッピング索引は任意のindex expressionに対して作成でき、granularity、つまり1つのスキッピング索引ブロックに含まれるグラニュール数も設定可能です。利用可能なスキッピング索引の種類には、次のものがあります。1. Min-max索引 ^[51]。各索引ブロックについて、index expressionの最小値と最大値を保存します。この索引タイプは、絶対的な範囲が小さいローカルにクラスター化されたデータ、たとえば緩やかにソートされたデータで効果的です。2. Set索引。設定可能な数の、索引ブロック内の一意な値を保存します。これらの索引は、ローカルなカーディナリティが小さい、すなわち値が「まとまって存在する」データに最適です。3. Bloom filter索引 ^[9]。行、token、またはn-gramの値に対して、設定可能な偽陽性率で構築されます。これらの索引はテキスト検索をサポートします ^[73] が、Min-max索引やSet索引とは異なり、範囲条件や否定条件には使用できません。

​

3.3 マージ時のデータ変換

ビジネスインテリジェンスやオブザーバビリティのユースケースでは、継続的に高いレート、あるいは突発的なバーストで生成されるデータを扱う必要がよくあります。また、意味のあるリアルタイムのインサイトを得るうえでは、通常、過去のデータよりも最近生成されたデータのほうが重要です。このようなユースケースでは、データベースは高いデータインジェスト率を維持しつつ、集計やデータのエージングといった手法によって履歴データの量を継続的に削減できる必要があります。ClickHouse では、さまざまなマージ戦略を用いて既存データを継続的かつ段階的に変換できます。マージ時のデータ変換は INSERT ステートメントのパフォーマンスを損ないませんが、テーブルに不要な値 (たとえば古い値や未集計の値) が一切含まれないことまでは保証できません。必要に応じて、SELECT ステートメントでキーワード FINAL を指定することで、すべてのマージ時変換をクエリ時に適用できます。

Replacing merges は、タプルを含むパーツの作成タイムスタンプに基づいて、最後に挿入されたバージョンのタプルだけを保持し、古いバージョンを削除します。タプルは、同じ主キーカラム値を持つ場合に同一とみなされます。どのタプルを保持するかを明示的に制御するために、比較用の特別なバージョンカラムを指定することもできます。Replacing merges は一般に、マージ時の更新メカニズムとして (通常は更新が頻繁なユースケースで) 使用されるほか、挿入時のデータ重複排除 (Section 3.5)) の代替として使われることもあります。

Aggregating merges は、主キーカラム値が同じ行を 1 つの集計行にまとめます。主キー以外のカラムは、要約値を保持する部分集計状態でなければなりません。2 つの部分集計状態、たとえば avg() のための sum と count は、新しい部分集計状態に結合されます。Aggregating merges は、通常のテーブルではなく materialized view で使われるのが一般的です。materialized view は、ソーステーブルに対する変換クエリに基づいて作成されます。他のデータベースとは異なり、ClickHouse は materialized view をソーステーブル全体の内容で定期的に更新しません。代わりに、ソーステーブルに新しいパーツが挿入されるたびに、その変換クエリの結果で materialized view が段階的に更新されます。

図 5 は、ページインプレッション統計を持つテーブル上に定義された materialized view を示しています。ソーステーブルに新たに挿入されたパーツに対して、変換クエリは region ごとにグループ化して最大および平均レイテンシを計算し、その結果を materialized view に挿入します。接尾辞 -State を持つ集計関数 avg() と max() は、実際の結果ではなく部分集計状態を返します。materialized view に定義された aggregating merge は、異なるパーツ内の部分集計状態を継続的に結合します。最終結果を得るには、ユーザーは -Merge 接尾辞を付けた avg() および max() を使って、materialized view 内の部分集計状態を統合します。

TTL (time-to-live) merges は、履歴データのエージングを提供します。deleting merges や aggregating merges とは異なり、TTL merges は一度に 1 つのパーツだけを処理します。TTL merges は、トリガーとアクションを持つルールとして定義されます。トリガーは各行についてタイムスタンプを計算する式であり、その値は TTL merge の実行時刻と比較されます。これによりユーザーは行粒度でアクションを制御できますが、すべての行が所定の条件を満たすかどうかを確認し、パーツ全体に対してアクションを実行するだけで十分であることがわかっています。可能なアクションには、1. パーツを別のボリュームに移動する (たとえば、より安価で低速なストレージ) 、2. パーツを再圧縮する (たとえば、より高負荷な codec を使って) 、3. パーツを削除する、4. ロールアップ、すなわち grouping key と aggregate functions を使って行を集計する、があります。

例として、リスト 1 のロギングテーブル定義を考えてみましょう。ClickHouse は、timestamp カラムの値が 1 週間より古いパーツを、低速だが安価な S3 オブジェクトストレージへ移動します。

1 CREATE TABLE tab ( ts DateTime , msg String )
2 ENGINE MergeTree PRIMARY KEY ts
3 TTL ( ts + INTERVAL 1 WEEK ) TO VOLUME 's3 '

リスト1: 1週間後にパートをオブジェクトストレージに移動する。

​

3.4 更新と削除

MergeTree* テーブルエンジンは追記専用のワークロードに適した設計ですが、規制遵守などの理由から、既存データを必要に応じて変更しなければならないユースケースもあります。データを更新または削除する方法は 2 つあり、どちらも並行する INSERT をブロックしません。

ミューテーション は、テーブルのすべてのパーツをその場で書き換えます。テーブル (delete) またはカラム (update) のサイズが一時的に 2 倍になるのを防ぐため、この操作は非アトミックです。つまり、並行する SELECT ステートメントは、変更済みパーツと未変更パーツの両方を読み取る可能性があります。ミューテーションでは、処理の完了時点でデータが物理的に変更されていることが保証されます。削除ミューテーションは、すべてのパーツ内のすべてのカラムを書き換えるため、依然としてコストが高いままです。

代替手段として、論理削除 は、行が削除されているかどうかを示す内部のビットマップカラムだけを更新します。ClickHouse は SELECT クエリにビットマップカラムに対する追加のフィルタを適用し、削除された行を結果から除外します。削除された行が物理的に除去されるのは、将来のどこかの時点で通常のマージが行われたときだけです。カラム数によっては、論理削除は SELECT が遅くなる代わりに、ミューテーションより大幅に高速になる場合があります。

同じテーブルに対する更新および削除操作は、論理的な競合を避けるため、まれにしか行われず、直列に実行されることが想定されています。

​

3.5 冪等な挿入

実運用で頻繁に発生する問題の 1 つは、テーブルに挿入するためのデータをサーバーに送信した後で接続タイムアウトが発生した場合に、クライアントがそれをどう扱うべきかという点です。この状況では、データが正常に挿入されたのかどうかをクライアントが判別するのは困難です。従来、この問題はクライアントからサーバーへデータを再送し、重複した挿入を主キーや一意制約で拒否させることで解決されてきました。データベースは、二分木 ^{[39, [68]](#page-13-16)}、ラジックス木 ^[45]、またはハッシュテーブル ^[29] に基づく索引構造を用いて、必要なポイントルックアップを高速に実行します。これらのデータ構造はすべてのタプルに索引を付けるため、大規模なデータセットや高い取り込みレートでは、領域および更新のオーバーヘッドが無視できなくなります。

ClickHouse は、各 insert が最終的に 1 つのパーツを作成するという事実に基づく、より軽量な代替手段を提供します。より具体的には、サーバーは直近に挿入された N 個のパーツ (たとえば N=100) のハッシュを保持し、既知のハッシュを持つパーツの再挿入を無視します。非レプリケートテーブルとレプリケートテーブルのハッシュは、それぞれローカルと Keeper に保存されます。その結果、insert は冪等になり、つまりクライアントはタイムアウト後に同じ行のバッチをそのまま再送するだけで、サーバー側で重複排除が行われると考えてよくなります。重複排除プロセスをより細かく制御するために、クライアントはオプションで、パーツハッシュとして機能する挿入トークンを指定できます。ハッシュベースの重複排除では、新しい行のハッシュ化に伴うオーバーヘッドは発生するものの、ハッシュの保存と比較にかかるコストはごくわずかです。

​

3.6 データレプリケーション

レプリケーションは高可用性 (ノード障害に対する耐性) の前提条件ですが、負荷分散や無停止アップグレードにも利用されます ^[14]。ClickHouse では、レプリケーションはテーブル状態という考え方に基づいており、テーブル状態はテーブルパーツの集合 (Section 3.1)) と、カラム名や型などのテーブルメタデータで構成されます。ノードは 3 つの操作によってテーブル状態を進めます。1. insert は状態に新しいパーツを追加します。2. マージ は状態に新しいパーツを追加し、既存のパーツを状態から削除します。3. ミューテーション と DDL ステートメントは、具体的な操作に応じて、パーツの追加、パーツの削除、テーブルメタデータの変更を行います。これらの操作は単一ノード上でローカルに実行され、その状態遷移の列がグローバルなレプリケーションログに記録されます。

レプリケーションログは、通常は 3 つの ClickHouse Keeper プロセスから成るアンサンブルによって管理されます。これらのプロセスは、Raft コンセンサスアルゴリズム ^[59] を用いて、ClickHouse ノードのクラスターに対して分散型で耐障害性のある協調レイヤーを提供します。クラスター内のすべてのノードは、初期状態ではレプリケーションログ内の同じ位置を指しています。ノードがローカルで insert、マージ、ミューテーション、および DDL ステートメントを実行する一方で、レプリケーションログは他のすべてのノード上で非同期にリプレイされます。その結果、レプリケートテーブルは結果整合性にとどまります。つまり、ノードは最新の状態へ収束する途中で、一時的に古いテーブル状態を読み取ることがあります。前述の操作の多くは、ノードのクォーラム (たとえばノードの過半数または全ノード) が新しい状態を採用するまで、同期的に実行することもできます。

例として、Figure 6 は、3 つの ClickHouse ノードから成るクラスター内の、初期状態では空のレプリケートテーブルを示しています。まず Node 1 が 2 つの insert ステートメントを受け取り、それらを Keeper アンサンブルに保存されているレプリケーションログに記録します ( 1 2 ) 。次に、Node 2 は最初のログエントリを取得し ( 3 ) 、Node 1 から新しいパーツをダウンロードして ( 4 ) 、そのエントリをリプレイします。一方、Node 3 は両方のログエントリをリプレイします ( 3 4 5 6 ) 。最後に、Node 3 は 2 つのパーツを マージ して新しいパーツを作成し、入力パーツを削除して、その マージ エントリをレプリケーションログに記録します ( 7 ) 。

同期を高速化するための最適化が 3 つあります。第一に、新たにクラスターに追加されたノードはレプリケーションログを最初からリプレイするのではなく、最後のレプリケーションログエントリを書き込んだノードの状態をそのままコピーします。第二に、マージ はローカルで再実行するか、別のノードから結果パーツを取得することでリプレイされます。具体的な動作は設定可能で、CPU 使用量とネットワーク I/O のバランスを取れます。たとえば、データセンター間レプリケーションでは、運用コストを最小化するためにローカル マージ が一般に好まれます。第三に、ノードは互いに独立したレプリケーションログエントリを並列にリプレイします。これには、たとえば同じテーブルに連続して挿入された新しいパーツの取得や、異なるテーブルに対する操作が含まれます。

​

3.7 ACID 準拠

同時実行の読み取りおよび書き込み操作のパフォーマンスを最大化するため、ClickHouse は可能な限りラッチングを避けています。クエリは、クエリ開始時点で作成された、関係するすべてのテーブル内のすべてのパーツのスナップショットに対して実行されます。これにより、並列 INSERT や マージ (Section 3.1) によって新たに作成されたパーツは実行に含まれません。さらに、パーツが同時に変更または削除されることを防ぐため (Section 3.4)) 、処理対象パーツの参照カウントはクエリの実行中インクリメントされます。形式的には、これはバージョン管理されたパーツに基づく MVCC の一種 ^[6] によって実現されるスナップショット分離に相当します。その結果、スナップショット取得時に同時実行の書き込みがそれぞれ単一のパーツにしか影響しないというまれなケースを除き、ステートメントは一般に ACID 準拠ではありません。

実際には、ClickHouse の書き込み負荷が高い意思決定系ユースケースの多くでは、停電時に新しいデータが失われるわずかなリスクも許容されます。これを踏まえ、データベースはデフォルトでは新たに挿入されたパーツの disk へのコミット (fsync) を強制せず、その代わりにアトミック性を犠牲にして、カーネルが書き込みをまとめて処理できるようにしています。

​

4 クエリ処理レイヤー

図7に示すように、ClickHouse はデータ要素、データ chunk、テーブル分片の粒度でクエリを並列化します。複数のデータ要素は、SIMD 命令を使うことで、演算子内で同時に処理できます。単一ノードでは、クエリエンジンが複数のスレッドで演算子を同時に実行します。ClickHouse は MonetDB/X100 ^[11] と同じベクトル化モデルを採用しており、仮想関数呼び出しのオーバーヘッドを最小限に抑えるため、演算子は単一の行ではなく複数の行 (データ chunk) を生成し、受け渡し、消費します。ソーステーブルが互いに重ならないテーブル分片に分割されている場合は、複数のノードがそれらの分片を同時にスキャンできます。その結果、すべてのハードウェアリソースをフル活用でき、ノードを追加することで水平方向に、コアを追加することで垂直方向に、クエリ処理をスケールできます。

この節の残りでは、まずデータ要素、データ chunk、分片の各粒度における並列処理をより詳しく説明します。次に、クエリ性能を最大化するための主要な最適化をいくつか紹介します。最後に、複数のクエリが同時に実行される状況で、ClickHouse が共有システムリソースをどのように管理するかを説明します。

​

4.1 SIMD 並列化

演算子間で複数の行を受け渡すことで、ベクトル化の余地が生まれます。ベクトル化は、手書きのインストリンシック ^{[64, [80]](#page-13-19)} またはコンパイラによる自動ベクトル化 ^[25] に基づいて行われます。ベクトル化の恩恵を受けるコードは、異なるコンピュートカーネルとしてコンパイルされます。たとえば、クエリ演算子の内部ホットループは、非ベクトル化カーネル、自動ベクトル化された AVX2 カーネル、手動でベクトル化された AVX-512 カーネルで実装できます。最速のカーネルは、cpuid 命令に基づいて実行時に選択されます。このアプローチにより、ClickHouse は最小要件として SSE 4.2 を満たす 15 年前のシステムでも動作しつつ、最新のハードウェアでは大幅な高速化も実現できます。

​

4.2 マルチコア並列化

ClickHouse は、SQL クエリを物理プラン演算子の有向グラフに変換する従来型のアプローチ ^[31] を採用しています。演算子プランへの入力は、ネイティブまたはサポートされている任意のサードパーティ製フォーマットでデータを読み取る特別なソース演算子で表されます (セクション 5) を参照) 。同様に、特別なシンク演算子が結果を目的の出力フォーマットに変換します。物理演算子プランは、設定可能なワーカースレッドの最大数 (デフォルトではコア数) とソーステーブルのサイズに基づいて、クエリのコンパイル時に独立した実行レーンへと展開されます。レーンは、並列演算子で処理されるデータを互いに重ならない範囲に分割します。並列処理の機会を最大化するため、レーンのマージは可能な限り後段まで遅らせます。

例として、図 8 の Node 1 のボックスには、ページインプレッション統計を持つテーブルに対する典型的な OLAP クエリの演算子グラフが示されています。最初のステージでは、ソーステーブルの 3 つの互いに重ならない範囲が同時にフィルタリングされます。Repartition exchange 演算子は、結果 chunk を第 1 ステージと第 2 ステージの間で動的に振り分け、処理スレッドの負荷が均等になるようにします。スキャンされる範囲の選択率に大きな差がある場合、第 1 ステージの後でレーンの負荷が偏ることがあります。第 2 ステージでは、フィルターを通過した行が RegionID ごとにグループ化されます。Aggregate 演算子は、グループ化カラムとして RegionID を用い、avg() の部分集約状態としてグループごとの sum と count を持つローカルな結果グループを保持します。ローカルな集約結果は最終的に GroupStateMerge 演算子によってグローバルな集約結果へマージされます。この演算子はパイプラインブレーカーでもあるため、第 3 ステージは集約結果の計算が完了してからでないと開始できません。第 3 ステージでは、結果グループはまず Distribute exchange 演算子によって、ほぼ同じ大きさの 3 つの互いに重ならないパーティションに分割され、その後 AvgLatency によってソートされます。ソートは 3 段階で実行されます。まず、ChunkSort 演算子が各パーティション内の個々の chunk をソートします。次に、StreamSort 演算子がローカルなソート済み結果を保持し、それを流入してくるソート済み chunk と 2-way マージソートで結合します。最後に、MergeSort 演算子が k-way ソートを使ってローカル結果を結合し、最終結果を得ます。

演算子は状態機械であり、入力ポートと出力ポートを介して互いに接続されています。演算子が取り得る状態は、need-chunk、ready、done の 3 つです。need-chunk から ready へ移るには、chunk が演算子の入力ポートに置かれます。ready から done へ移るには、演算子が入力 chunk を処理して出力 chunk を生成します。done から need-chunk へ移るには、出力 chunk が演算子の出力ポートから取り除かれます。接続された 2 つの演算子における最初と 3 番目の状態遷移は、まとめて 1 つのステップとしてしか実行できません。ソース演算子 (シンク演算子) は、ready と done (need-chunk と done) の状態だけを持ちます。

ワーカースレッドは物理演算子プランを継続的にたどり、状態遷移を実行します。CPU キャッシュの局所性を保つため、プランには、同じレーン内で連続する演算子を同じスレッドが処理するべきであることを示すヒントが含まれています。並列処理は、ステージ内の互いに重ならない入力に対する水平方向 (たとえば 図 8 では Aggregate 演算子が同時実行される) と、パイプラインブレーカーで分離されていないステージ間の垂直方向 (たとえば 図 8 では同じレーン内の Filter 演算子と Aggregate 演算子が同時に実行できる) の両方で行われます。新しいクエリの開始時や、同時実行中のクエリの終了時に過剰割り当てや過少割り当てを避けるため、並列度はクエリの実行中であっても、クエリ開始時に指定されたそのクエリのワーカースレッド数の 1 から最大値までの範囲で変更できます (セクション 4.5) を参照) 。

演算子はさらに、実行時に 2 つの方法でクエリ実行に影響を与えることができます。第 1 に、演算子は新しい演算子を動的に作成して接続できます。これは主に、メモリ消費量が設定可能なしきい値を超えたときにクエリをキャンセルする代わりに、external aggregation、ソート、または JOIN アルゴリズムに切り替えるために使われます。第 2 に、演算子はワーカースレッドに非同期 queue へ移るよう要求できます。これにより、リモートデータを待機している間もワーカースレッドをより効率的に活用できます。

ClickHouse のクエリ実行エンジンと morsel-driven parallelism ^[44] は、レーンが通常は異なるコア / NUMA ソケット上で実行され、ワーカースレッドが他のレーンからタスクを奪えるという点で似ています。また、中央集権的なスケジューリングコンポーネントは存在せず、代わりに各ワーカースレッドが演算子プランを継続的にたどりながら、個別にタスクを選択します。morsel-driven parallelism とは異なり、ClickHouse では最大並列度をプランに組み込み、デフォルトの morsel サイズである約 100,000 行と比べてはるかに大きい範囲でソーステーブルを分割します。このため、場合によっては停滞が発生することがあります (たとえば、異なるレーン内の filter 演算子の実行時間に大きな差がある場合) 。しかし、Repartition のような exchange 演算子を広く用いることで、少なくともそのような不均衡がステージをまたいで蓄積していくのは防げると考えています。

​

4.3 マルチノード並列化

クエリのソーステーブルが分片化されている場合、クエリを受け取ったノード (イニシエーターノード) のクエリオプティマイザーは、可能な限り多くの処理を他のノードで実行しようとします。他のノードからの結果は、クエリプラン内のさまざまな地点で取り込むことができます。クエリの内容に応じて、リモートノードは 1. ソーステーブルの生のカラムをイニシエーターノードにストリーミング送信する、2. ソースカラムをフィルタリングして残った行を送信する、3. フィルタと集約のステップを実行し、部分集約状態を含むローカルの結果グループを送信する、または 4. フィルタ、集約、ソートを含むクエリ全体を実行します。

Figure 8 の Node 2 … N は、hits テーブルの分片を保持する他のノードで実行されるクエリプランの断片を示しています。これらのノードはローカルデータをフィルタリングしてグループ化し、その結果をイニシエーターノードに送信します。Node 1 上の GroupStateMerge operator は、結果グループが最終的にソートされる前に、ローカルとリモートの結果をマージします。

​

4.4 包括的な性能最適化

この節では、クエリ実行のさまざまな段階で適用される主要な性能最適化をいくつか紹介します。

クエリ最適化。最初の一連の最適化は、クエリの AST から得られる意味的なクエリ表現に対して適用されます。こうした最適化の例としては、定数畳み込み (例: concat(lower(‘a’),upper(‘b’)) は ‘aB’ になる) 、特定の 集約 関数からのスカラー値の抽出 (例: sum(a2) は 2 * sum(a) になる) 、共通部分式除去、等値フィルタの選言を IN リストに変換すること (例: x=c OR x=d は x IN (c,d) になる) などがあります。最適化後の意味的クエリ表現は、続いて論理演算子プランに変換されます。論理プランに対する最適化には、filter pushdown や、どちらのコストが高いと見積もられるかに応じた関数評価とソート手順の並べ替えが含まれます。最後に、論理クエリプランは物理演算子プランに変換されます。この変換では、対象となるテーブルエンジンの特性を活用できます。たとえば MergeTree-table engine の場合、ORDER BY カラムが主キーのプレフィックスを構成していれば、データをディスク上の順序で読み取れるため、ソート演算子をプランから除去できます。また、集約 における grouping カラムが主キーのプレフィックスを構成している場合、ClickHouse は sort 集約 ^[33] を使用できます。つまり、あらかじめソートされた入力内で同じ値が連続する部分を直接集約します。hash 集約 と比べると、sort 集約 はメモリ消費が大幅に少なく、その連続部分の処理が終わるとすぐに集約値を次の演算子に渡せます。

クエリコンパイル。ClickHouse は LLVM に基づくクエリコンパイル を用いて、隣接するプラン演算子を動的に融合します ^{[38, [53]](#page-13-0)}。たとえば、式 a * b + c + 1 は、3 つの演算子ではなく 1 つの演算子にまとめることができます。式に加えて、ClickHouse は複数の 集約 関数を一度に評価するため (つまり GROUP BY のため) や、複数のソートキーによるソートのためにもコンパイルを利用します。クエリコンパイルは仮想呼び出しの回数を減らし、データをレジスタや CPU cache に保持し、実行されるコード量が少なくなることで分岐予測にも役立ちます。さらに、実行時コンパイルにより、コンパイラに実装されている論理最適化や peephole 最適化など、さまざまな最適化が可能になり、その環境で利用可能な最速の CPU 命令も使えるようになります。コンパイルは、同じ通常の式、集約 式、またはソート式が、異なるクエリで設定可能な回数を超えて実行された場合にのみ開始されます。コンパイル済みのクエリ演算子は cache され、今後のクエリで再利用できます。[7]

主キー索引の評価。ClickHouse は、条件の連言標準形に含まれる filter clause の部分集合が主キーカラムのプレフィックスを構成している場合、主キー索引を使って WHERE 条件を評価します。主キー索引は、キー値の辞書順にソートされた範囲に対して左から右へ解析されます。主キーカラムに対応する filter clause は三値論理で評価されます。すなわち、その範囲内の値に対して、すべて真、すべて偽、または真と偽が混在、のいずれかです。最後のケースでは、その範囲は部分範囲に分割され、再帰的に解析されます。filter 条件内の関数に対しても追加の最適化があります。第一に、関数には単調性を表す特性があります。たとえば toDayOfMonth(date) は 1 か月の範囲内では区分的に単調です。単調性の特性により、ソート済みの入力キー値範囲に対して、その関数がソート済みの結果を生成するかどうかを推論できます。第二に、一部の関数は、与えられた関数結果の逆像を計算できます。これは、キーカラムに対する関数呼び出しと定数との比較を、キーカラムの値とその逆像との比較に置き換えるために使われます。たとえば、toYear(k) = 2024 は k >= 2024-01-01 && k < 2025-01-01 に置き換えられます。

データスキッピング。ClickHouse は、3.2 節で示したデータ構造を用いて、クエリ実行時のデータ読み取りを回避しようとします。さらに、異なるカラムに対するフィルタは、ヒューリスティクスおよび (任意の) カラム STATISTICS に基づく推定 selectivity の高い順に、順次評価されます。少なくとも 1 つの一致する行を含む data chunk だけが、次の predicate に渡されます。これにより、predicate ごとに、読み取るデータ量と実行すべき計算回数が徐々に減少します。この最適化は、少なくとも 1 つの高選択性の predicate が存在する場合にのみ適用されます。そうでなければ、すべての predicate を並列に評価する場合と比べて、クエリの latency が悪化してしまうためです。

ハッシュテーブル。ハッシュテーブルは、集約 やハッシュ結合における基本的なデータ構造です。適切な種類のハッシュテーブルを選ぶことは、性能を左右する重要な要素です。ClickHouse は、ハッシュ関数、アロケータ、セル型、リサイズポリシーを可変要素とする汎用ハッシュテーブルテンプレートから、さまざまなハッシュテーブルを 生成 します (2024 年 3 月時点で 30 種類以上) 。グループ化カラムのデータ型、推定されるハッシュテーブルのカーディナリティ、そのほかの要因に応じて、各クエリ演算子ごとに最も高速なハッシュテーブルが個別に選択されます。ハッシュテーブルに実装されている追加の最適化には、次のものがあります。

• 巨大なキー集合をサポートするための、256 個のサブテーブルから成る 2 レベル構成 (ハッシュの先頭 1 バイトに基づく) 、
• 4 つのサブテーブルを持ち、文字列長に応じて異なるハッシュ関数を使う文字列用ハッシュテーブル ^[79]、
• キー数が少ない場合に、キーを直接バケット索引として使用する (つまりハッシュ化しない) ルックアップテーブル、
• 比較コストが高い場合 (例: 文字列、AST) に衝突解決を高速化する、ハッシュ値を埋め込んだ値、
• 不要なリサイズを避けるため、実行時統計から予測したサイズに基づいてハッシュテーブルを作成すること、
• 作成と破棄のライフサイクルが同じ複数の小さなハッシュテーブルを、単一のメモリスラブ上に割り当てること、
• ハッシュマップごとおよびセルごとのバージョンカウンターを用いて、再利用のためにハッシュテーブルを即座にクリアすること、
• キーのハッシュ化後の値取得を高速化するために CPU prefetch (__builtin_prefetch) を使用すること。

JOIN。ClickHouse は当初、JOIN をごく限定的にしかサポートしていなかったため、歴史的に多くのユースケースでは非正規化テーブルに頼っていました。現在では、このデータベースは 提供 しています。SQL で利用可能なすべての JOIN 種類 (inner、left-/right/full outer、cross、as-of) に加え、ハッシュ結合 (naïve、grace) 、sort-merge join、高速なキー・バリューのルックアップを備えた table engines 向けの index join (通常は dictionaries) など、さまざまな JOIN アルゴリズムを。

JOIN はデータベース処理の中でも特に高コストな操作の 1 つであるため、古典的な JOIN アルゴリズムの並列版を提供し、理想的には空間と時間のトレードオフを設定可能にすることが重要です。ハッシュ結合については、ClickHouse は ^[7] の non-blocking shared partition algorithm を実装しています。たとえば、Figure 9 のクエリは、ページヒット統計テーブルに対する self-join によって、Users が URL 間をどのように移動するかを計算します。JOIN の build phase は 3 つのレーンに分割され、元テーブルの互いに重ならない 3 つの範囲を処理します。グローバルなハッシュテーブルの代わりに、パーティション化されたハッシュテーブルが使用されます。 (通常は 3 本の) worker thread は、ハッシュ関数の剰余を計算することで、build 側の各入力行について対象パーティションを決定します。ハッシュテーブルの各パーティションへのアクセスは、Gather exchange operator を使って同期されます。probe phase でも同様に、入力 tuple の対象パーティションを特定します。このアルゴリズムでは tuple ごとに追加で 2 回のハッシュ計算が発生しますが、ハッシュテーブルのパーティション数に応じて、build phase におけるラッチ競合を大幅に軽減できます。

​

4.5 ワークロード分離

ClickHouse では、同時実行制御、メモリ使用量の制限、I/O スケジューリングにより、クエリをワークロードクラスごとに分離できます。特定のワークロードクラスに対して共有リソース (CPU コア、DRAM、ディスク I/O、ネットワーク I/O) の制限を設定することで、それらのクエリが他の重要な業務クエリに影響しないようにできます。

同時実行制御は、同時実行クエリ数が多い状況でスレッドの過剰割り当てを防ぎます。具体的には、クエリごとのワーカースレッド数が、使用可能な CPU コア数に対する指定比率に基づいて動的に調整されます。

ClickHouse は、server、user、query の各レベルでメモリ割り当てのバイト数を追跡し、柔軟なメモリ使用量制限を設定できるようにします。メモリオーバーコミットにより、他のクエリのメモリ制限を確保しつつ、クエリは保証されたメモリを超える追加の空きメモリを利用できます。さらに、集約、ソート、join clauses のメモリ使用量も制限でき、メモリ制限を超えた場合は外部アルゴリズムへのフォールバックが行われます。

最後に、I/O スケジューリングにより、最大帯域幅、進行中のリクエスト数、ポリシー (例: FIFO、SFC ^[32]) に基づいて、ワークロードクラスごとにローカルおよびリモートのディスクアクセスを制限できます。

​

5 インテグレーション レイヤー

リアルタイムの意思決定アプリケーションでは、多くの場合、複数の場所にあるデータに効率よく低レイテンシでアクセスできることが求められます。外部データを OLAP データベースで利用可能にする方法には、2 つのアプローチがあります。プッシュ型のデータアクセスでは、サードパーティのコンポーネントがデータベースと外部データストアの橋渡し役となります。その一例が、リモートデータを宛先システムへプッシュする専用の extract-transform-load (ETL) ツールです。プル型モデルでは、データベース自体がリモートのデータソースに接続し、クエリのためにデータをローカルテーブルへ取り込んだり、データをリモートシステムへエクスポートしたりします。一般に、プッシュ型のアプローチはより汎用的で広く使われていますが、その分アーキテクチャは大きくなり、スケーラビリティ上のボトルネックも生じます。これに対して、データベースに直接組み込まれたリモート接続機能は、ローカルデータとリモートデータの結合などの興味深い機能を提供しつつ、全体のアーキテクチャをシンプルに保ち、インサイト獲得までの時間を短縮します。

この節の残りでは、リモート環境にあるデータにアクセスするための、ClickHouse におけるプル型のデータ統合手法を見ていきます。なお、SQL データベースにおけるリモート接続という考え方自体は新しいものではありません。たとえば、2001 年に導入され、2011 年から PostgreSQL で実装されている SQL/MED 標準 ^{[35] [65]} では、外部データを管理するための統一インターフェイスとして foreign data wrappers が提案されています。他のデータストアやストレージフォーマットとの最大限の相互運用性は、ClickHouse の設計目標の 1 つです。私たちの知る限り、2024 年 3 月時点で ClickHouse は、分析データベース全体の中でもっとも多くの組み込みデータ統合オプションを提供しています。

外部接続。ClickHouse は、ODBC、MySQL、PostgreSQL、SQLite、Kafka、Hive、MongoDB、Redis、S3/GCP/Azure のオブジェクトストア、および各種データレイクを含む外部システムやストレージロケーションに接続するために、50+ のインテグレーション テーブル関数とエンジンを提供しています。さらに、これらは次のボーナス図に示すカテゴリに分類できます (元の VLDB 論文には含まれていません) 。

Integration Table Functions による一時的なアクセス。テーブル関数は、探索的なアドホッククエリでリモートデータを読み取るために、SELECT クエリの FROM 句で呼び出せます。あるいは、INSERT INTO TABLE FUNCTION ステートメントを使って、リモートストアへデータを書き込む用途にも利用できます。

永続的なアクセス。リモートデータストアや処理システムへの永続的な接続を作成する方法は 3 つあります。

1 つ目は、インテグレーション テーブルエンジン です。これは、MySQL テーブルのようなリモートデータソースを、永続的なローカルテーブルとして表現します。ユーザーは、SELECT クエリとテーブル関数を組み合わせた CREATE TABLE AS 構文を使ってテーブル定義を保存します。たとえば、リモートのカラムの一部だけを参照するためにカスタムスキーマを指定したり、スキーマ推論を使ってカラム名と対応する ClickHouse の型を自動的に決定したりできます。さらに、ランタイム動作として受動型と能動型を区別できます。受動型テーブルエンジンはクエリをリモートシステムへ転送し、その結果でローカルのプロキシテーブルを埋めます。これに対して、能動型テーブルエンジンはリモートシステムから定期的にデータを取得するか、たとえば PostgreSQL の logical replication protocol を通じてリモートの変更を購読します。その結果、ローカルテーブルにはリモートテーブルの完全なコピーが保持されます。

2 つ目は、インテグレーション データベースエンジン です。これは、リモートデータストア内のテーブルスキーマにあるすべてのテーブルを ClickHouse にマッピングします。前者とは異なり、一般にリモートデータストアがリレーショナルデータベースであることが前提で、さらに DDL ステートメントのサポートも限定的です。

3 つ目は、辞書 です。対応するインテグレーション テーブル関数またはエンジンを使うことで、ほぼあらゆるデータソースに対する任意のクエリでデータを投入できます。ランタイム動作は能動型で、データは一定間隔でリモートストレージから取り込まれます。

データフォーマット。サードパーティのシステムとやり取りするために、現代の分析データベースは、あらゆるフォーマットのデータを処理できなければなりません。ClickHouse はネイティブフォーマットに加えて、CSV、JSON、Parquet、Avro、ORC、Arrow、Protobuf などを含む 90+ のフォーマットをサポートしています。各フォーマットは、入力フォーマット (ClickHouse が読み取れるもの) 、出力フォーマット (ClickHouse がエクスポートできるもの) 、またはその両方になりえます。Parquet のような分析向けフォーマットの一部はクエリ処理にも統合されており、たとえばオプティマイザは埋め込まれた統計情報を活用でき、フィルタは圧縮データに対して直接評価されます。

互換インターフェイス。ClickHouse は、ネイティブのバイナリ wire protocol と HTTP に加えて、MySQL または PostgreSQL の wire-protocol-compatible interfaces 経由でもクライアントとやり取りできます。この互換機能は、ベンダーがまだ ClickHouse へのネイティブ接続を実装していない proprietary applications (たとえば一部の business intelligence tools) からのアクセスを可能にするうえで有用です。

​

6 機能としてのパフォーマンス

この節では、パフォーマンス分析向けの組み込みツールを紹介し、実際のクエリとベンチマーククエリを用いてパフォーマンスを評価します。

​

6.1 組み込みの性能分析ツール

個々のクエリやバックグラウンド処理における性能ボトルネックを調査するために、さまざまなツールを利用できます。これらのツールはすべて、システムテーブルに基づく統一されたインターフェイスを通じて利用します。

サーバーおよびクエリのメトリクス。アクティブなパーツ数、ネットワークスループット、cache ヒット率などのサーバーレベルの統計に加え、読み取られたブロック数や索引の使用状況など、クエリごとの統計も提供されます。メトリクスは、同期的に (要求に応じて) 計算することも、設定可能なインターバルで非同期に計算することもできます。

サンプリングプロファイラ。サーバースレッドのコールスタックは、サンプリングプロファイラを使って収集できます。結果は必要に応じて、フレームグラフ可視化ツールなどの外部ツールにエクスポートできます。

OpenTelemetry インテグレーション。OpenTelemetry は、複数のデータ処理システムにまたがってデータ行をトレーシングするためのオープン標準です ^[8]。ClickHouse は、すべてのクエリ処理ステップについて、設定可能な粒度で OpenTelemetry のログスパンを生成できるほか、他のシステムからの OpenTelemetry のログスパンを収集して分析することもできます。

クエリの説明。他のデータベースと同様に、SELECT クエリの前に EXPLAIN を付けることで、クエリの AST、論理・物理演算子プラン、および実行時の動作について詳細な情報を得られます。

​

6.2 ベンチマーク

ベンチマークは現実を十分に反映していないとして批判されてきましたが ^{[10, 52, 66, [74]](#page-13-24)}、それでもデータベースの長所と短所を把握するうえで有用です。以下では、ClickHouse の性能評価にベンチマークがどのように用いられるかを説明します。

​

6.2.1 非正規化テーブル

非正規化されたファクトテーブルに対するフィルタおよび集計クエリは、歴史的に ClickHouse の主要なユースケースでした。ここでは、この種の典型的なワークロードであり、クリックストリーム分析やトラフィック分析で使われるアドホックおよび定期レポート用クエリをシミュレートする ClickBench の実行時間を示します。このベンチマークは、Web 最大級の分析プラットフォームの 1 つから取得した、匿名化済みの 1 億件のページヒットを含むテーブルに対する 43 個のクエリで構成されています。オンラインダッシュボード ^[17] では、2024 年 6 月時点で 45 を超える商用および研究用データベースの測定結果 (コールド/ホット実行時間、データ取り込み時間、ディスク上のサイズ) を確認できます。結果は、公開されているデータセットとクエリ ^[16] に基づき、独立した contributors によって提出されています。これらのクエリは、シーケンシャルスキャンおよび索引スキャンのアクセスパスを検証し、CPU、I/O、またはメモリが律速となるリレーショナル演算子を日常的にあぶり出します。

Figure 10 は、分析用途でよく使われるデータベースにおいて、すべての ClickBench クエリを順次実行した場合の相対的なコールド実行時間とホット実行時間の合計を示しています。測定は、16 vCPU、32 GB RAM、5000 IOPS / 1000 MiB/s disk を備えた単一ノードの AWS EC2 c6a.4xlarge インスタンスで実施されました。Redshift (ra3.4xlarge、12 vCPU、96 GB RAM) および Snowfake (warehouse size S: 2x8 vCPU、2x16 GB RAM) についても、同等のシステムが使用されました。物理データベース設計のチューニングは最小限にとどめており、たとえば主キーは指定していますが、個々のカラムの圧縮を変更したり、projections や スキッピングインデックス を作成したりはしていません。また、各コールドクエリの実行前には Linux の page cache を flush していますが、データベースやオペレーティングシステムの設定は調整していません。各クエリについては、データベース間で最速の実行時間をベースラインとして使用します。他のデータベースの相対クエリ実行時間は、( + 10)/(_ + 10) として計算されます。あるデータベースの総相対実行時間は、クエリごとの比率の幾何平均です。研究用データベース Umbra ^[54] は総合的なホット実行時間で最良の結果を達成していますが、ClickHouse はホット実行時間とコールド実行時間の両方で、他のすべての本番運用向けデータベースを上回っています。

より多様なワークロードにおける SELECTs のパフォーマンス推移を追跡するために、私たちは VersionsBench ^[19] と呼ばれる 4 つのベンチマークの組み合わせを 使用しています。このベンチマークは、新しいリリースが公開されるたびに月 1 回実行され、そのパフォーマンスを評価し ^[20]、パフォーマンスを低下させた可能性のあるコード変更を特定します。個々のベンチマークには次が含まれます。1. ClickBench (前述) 、2. MgBench ^[21] の 15 個のクエリ、3. 6 億行を持つ非正規化された Star Schema Benchmark ^[57] のファクトテーブルに対する 13 個のクエリ。4. 34 億行を持つ NYC Taxi Rides に対する 4 個のクエリ ^[70]。

Figure 11 は、2018 年 3 月から 2024 年 3 月までの 77 個の ClickHouse バージョンにおける VersionsBench 実行時間の推移を示しています。個々のクエリの相対実行時間の違いを補正するため、すべてのバージョンにおける最小クエリ実行時間との比率を重みとして、幾何平均を用いて実行時間を正規化しています。VersionsBench のパフォーマンスは、この 6 年間で 1.72 × 改善しました。長期サポート (LTS) リリースの日付は x 軸上に示されています。一部の期間では一時的にパフォーマンスが低下したものの、LTS リリースは一般に、直前の LTS バージョンと同等かそれ以上のパフォーマンスを備えています。2022 年 8 月の大幅な改善は、Section 4.4. で説明したカラム単位のフィルタ評価手法によるものです。

​

6.2.2 正規化テーブル

従来型のデータウェアハウスでは、データはスターまたはスノーフェイクスキーマでモデル化されることが一般的です。ここでは TPC-H クエリ (スケール係数 100) の実行時間を示しますが、正規化テーブルは ClickHouse における新たなユースケースとして注目されつつあることも付言しておきます。Figure 12 は、セクション 4.4. で説明した並列ハッシュ結合アルゴリズムに基づく TPC-H クエリのホット実行時間を示しています。測定は、64 vCPU、128 GB RAM、5000 IOPS / 1000 MiB/s のディスク性能を備えた単一ノードの AWS EC2 c6i.16xlarge インスタンスで実施しました。5 回の実行のうち最速の結果を記録しました。参考として、同程度の規模の Snowfake システム (warehouse size L、8x8 vCPU、8x16 GB RAM) でも同じ測定を行いました。11 件のクエリの結果は表から除外しています。クエリ Q2、Q4、Q13、Q17、および Q20-22 には、ClickHouse v24.6 時点ではサポートされていない相関サブクエリが含まれているためです。クエリ Q7-Q9 と Q19 は、実用的な実行時間を得るために、結合順序の並べ替えや結合述語のプッシュダウン (いずれも ClickHouse v24.6 時点では未実装) など、JOIN に対する拡張的なプランレベル最適化に依存しています。サブクエリの自動的な相関解除と、JOIN に対するより優れたオプティマイザサポートは、2024 年に実装が予定されています ^[18]。残る 11 件のクエリのうち、5 件は ClickHouse、6 件は Snowfake のほうが高速でした。前述の最適化は性能にとって重要であることが知られているため ^[27]、これらが実装されれば、これらのクエリの実行時間はさらに改善されると見込まれます。

​

7 関連研究

分析データベースは、ここ数十年にわたり学術界と産業界の双方で大きな関心を集めてきた ^[1]。Sybase IQ ^[48]、Teradata ^[72]、Vertica ^[42]、Greenplum ^[47] のような初期のシステムは、オンプレミスであるがゆえに、高コストなバッチ ETL ジョブと限られた弾力性を特徴としていた。2010年代初頭には、Snowfake ^[22]、BigQuery ^[49]、Redshift ^[4] などのクラウドネイティブなデータウェアハウスや database-as-a-service (DBaaS) の登場により、組織における分析のコストと複雑さは劇的に低下し、高可用性と自動的なリソーススケーリングの恩恵も受けられるようになった。さらに近年では、分析実行カーネル (例: Photon ^[5] と Velox ^[62]) が、さまざまな分析、ストリーミング、機械学習アプリケーションで利用できる共通のデータ処理機能を提供している。

目標と設計原則の観点で ClickHouse に最も近いデータベースは、Druid ^[78] と Pinot ^[34] である。どちらのシステムも、高いデータインジェスト率でのリアルタイム分析を対象としている。ClickHouse と同様に、テーブルは segments と呼ばれる水平分割されたパーツに分割される。ClickHouse は小さなパーツを継続的にマージし、さらに第 3.3, 節の手法を用いて必要に応じてデータ量を削減するのに対し、Druid と Pinot ではパーツは永続的に不変のままである。また、Druid と Pinot ではテーブルの作成、変更、検索のために専用ノードが必要だが、ClickHouse はこれらのタスクにモノリシックなバイナリを用いる。

Snowfake ^[22] は、共有ディスクアーキテクチャに基づく、広く利用されているプロプライエタリなクラウドデータウェアハウスである。テーブルを micro-partitions に分割するその方式は、ClickHouse におけるパーツの概念に類似している。Snowfake は永続化にハイブリッド PAX ページ ^[3] を使用する一方、ClickHouse のストレージフォーマットは厳密に列指向である。Snowfake はまた、自動生成される軽量な索引 ^{[31, [51]](#page-13-14)} を用いたローカルキャッシュとデータプルーニングを、高い性能を支える要素として重視している。ClickHouse の主キーと同様に、利用者は同じ値を持つデータを近接配置するために、任意でクラスタ化索引を作成できる。

Photon ^[5] と Velox ^[62] は、複雑なデータ管理システムの構成要素として使用されるよう設計されたクエリ実行エンジンである。どちらのシステムも入力としてクエリプランを受け取り、それをローカルノード上で Parquet (Photon) または Arrow (Velox) ファイル ^[46] に対して実行する。ClickHouse はこれらの汎用フォーマットでデータを取り込み・出力できるが、保存にはネイティブのファイルフォーマットを優先する。Velox と Photon はクエリプランを最適化しない一方で (Velox は基本的な式の最適化を行う) 、データ特性に応じてコンピュートカーネルを動的に切り替えるような実行時適応技法を利用している。同様に、ClickHouse のプラン演算子は

クエリのメモリ消費量に応じて、主として外部集約や結合演算子に切り替えるために、実行時に別の演算子を作成できる。Photon の論文では、コード生成を行う設計 ^{[38, 41, [53]](#page-13-0)} は、解釈型のベクトル化設計 ^[11] よりも開発とデバッグが難しいと指摘している。Velox builds におけるコード生成の (Experimental な) サポートでは、実行時に生成された C++ コードから作られた共有ライブラリを build およびリンクする一方で、ClickHouse は LLVM のオンデマンドコンパイル API と直接やり取りする。

DuckDB ^[67] もホストプロセスに組み込んで利用することを想定していますが、さらにクエリ最適化とトランザクションも提供します。これは、OLAP クエリに、たまに OLTP ステートメントが混在するような用途を想定して設計されています。そのため DuckDB は DataBlocks ^[43] ストレージフォーマットを採用しており、順序保持辞書や frame-of-reference ^[2] などの軽量な圧縮方式を用いて、ハイブリッドなワークロードで高い性能を実現しています。対照的に、ClickHouse は追記専用のユースケース、つまり更新や削除がない、あるいはまれなケース向けに最適化されています。ブロックは LZ4 のような重量級の手法で圧縮されますが、これは、ユーザーが頻繁なクエリを高速化するためにデータの pruning を積極的に活用し、残りのクエリでは I/O コストが解凍コストを大きく上回ることを前提としています。DuckDB は Hyper の MVCC 認証スキーム ^[55] に基づく直列化可能なトランザクションも提供しますが、ClickHouse が提供するのはスナップショット分離のみです。

​

8 結論と展望

オープンソースの高性能なOLAPデータベースである ClickHouse のアーキテクチャを示した。書き込みに最適化されたストレージ層と最先端のベクトル化クエリエンジンを基盤とすることで、ClickHouse は高いインジェスト率で、ペタバイト規模のデータセットに対するリアルタイム分析を実現する。バックグラウンドでデータを非同期にマージおよび変換することで、ClickHouse はデータ保守と並列インサートを効率的に分離する。ストレージ層では、スパースプライマリインデックス、スキッピングインデックス、プロジェクションテーブルを用いた積極的なデータプルーニングが可能である。さらに、ClickHouse における更新と削除、冪等なインサート、高可用性を実現するためのノード間データレプリケーションの実装について説明した。クエリ処理層は多様な手法でクエリを最適化し、サーバーおよびクラスターのあらゆるリソースを活用して実行を並列化する。インテグレーションテーブルエンジンと関数は、他のデータ管理システムやデータフォーマットとシームレスに連携するための便利な手段を提供する。ベンチマークを通じて、ClickHouse が市場で最速級の分析データベースの 1 つであることを示すとともに、実運用環境における ClickHouse の長年の導入事例を通して、典型的なクエリ性能が大幅に向上してきたことを示した。

2024 年に予定されているすべての機能と拡張は、公開ロードマップ ^[18] で確認できる。予定されている改善には、ユーザートランザクションのサポート、代替クエリ言語としての PromQL ^[69]、半構造化データ (JSON など) のための新しいデータ型、JOIN のプランレベル最適化の改善、さらに light-weight delete を補完する light-weight update の実装が含まれる。

​

謝辞

バージョン24.6時点で、SELECT * FROM system.contributors を実行すると、ClickHouse に貢献した 1994 人の名前が返されます。ClickHouse Inc. のエンジニアリングチームの皆様、そして ClickHouse のすばらしいオープンソースコミュニティの皆様が、このデータベースの構築に注いでくださった多大な努力と献身に、心より感謝いたします。

​

リファレンス

• ¹ Daniel Abadi、Peter Boncz、Stavros Harizopoulos、Stratos Idreaos、Samuel Madden. 2013. The Design and Implementation of Modern Column-Oriented Database Systems. https://doi.org/10.1561/9781601987556
• ² Daniel Abadi、Samuel Madden、Miguel Ferreira。2006年。Integrating Compression and Execution in Column-Oriented Database Systems. Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data (SIGMOD ‘06)、671–682。https://doi.org/10.1145/1142473.1142548
• ³ Anastassia Ailamaki、David J. DeWitt、Mark D. Hill、Marios Skounakis. 2001. Weaving Relations for Cache Performance. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB ‘01). Morgan Kaufmann Publishers Inc.、San Francisco、CA、USA、169–180.
• ⁴ Nikos Armenatzoglou, Sanuj Basu, Naga Bhanoori, Mengchu Cai, Naresh Chainani, Kiran Chinta, Venkatraman Govindaraju, Todd J. Green, Monish Gupta, Sebastian Hillig, Eric Hotinger, Yan Leshinksy, Jintian Liang, Michael McCreedy, Fabian Nagel, Ippokratis Pandis, Panos Parchas, Rahul Pathak, Orestis Polychroniou, Foyzur Rahman, Gaurav Saxena, Gokul Soundararajan, Sriram Subramanian, and Doug Terry. 2022. Amazon Redshift Re-Invented. In Proceedings of the 2022 International Conference on Management of Data (Philadelphia, PA, USA) (SIGMOD ‘22). Association for Computing Machinery, New York, NY, USA, 2205–2217. https://doi.org/10.1145/3514221.3526045
• ⁵ Alexander Behm, Shoumik Palkar, Utkarsh Agarwal, Timothy Armstrong, David Cashman, Ankur Dave, Todd Greenstein, Shant Hovsepian, Ryan Johnson, Arvind Sai Krishnan, Paul Leventis, Ala Luszczak, Prashanth Menon, Mostafa Mokhtar, Gene Pang, Sameer Paranjpye, Greg Rahn, Bart Samwel, Tom van Bussel, Herman van Hovell, Maryann Xue, Reynold Xin, and Matei Zaharia. 2022. Photon: A Fast Query Engine for Lakehouse Systems (SIGMOD ‘22). Association for Computing Machinery, New York, NY, USA, 2326–2339. https://doi.org/10.1145/3514221. 3526054
• ⁶ Philip A. Bernstein、Nathan Goodman. 1981. Concurrency Control in Distributed Database Systems. ACM Computing Survey 13, 2 (1981), 185–221. https://doi.org/10.1145/356842.356846
• ⁷ Spyros Blanas、Yinan Li、Jignesh M. Patel. 2011. Design and evaluation of main memory hash join algorithms for multi-core CPUs. Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data (Athens, Greece) (SIGMOD ‘11) 所収。Association for Computing Machinery, New York, NY, USA, 37–48. https://doi.org/10.1145/1989323.1989328
• ⁸ Daniel Gomez Blanco. 2023. Practical OpenTelemetry. Springer Nature.
• ⁹ Burton H. Bloom. 1970. Space/Time Trade-Ofs in Hash Coding with Allowable Errors. Commun. ACM 13, 7 (1970), 422–426. https://doi.org/10.1145/362686. 362692
• ¹⁰ Peter Boncz, Thomas Neumann, and Orri Erling. 2014. TPC-H Analyzed: Hidden Messages and Lessons Learned from an Infuential Benchmark. In Performance Characterization and Benchmarking. 61–76. https://doi.org/10.1007/978-3-319- 04936-6_5
• ¹¹ Peter Boncz、Marcin Zukowski、および Niels Nes。2005年。MonetDB/X100: Hyper-Pipelining Query Execution。CIDRにて。
• ¹² Martin Burtscher、Paruj Ratanaworabhan. 2007. High Throughput Compression of Double-Precision Floating-Point Data. In Data Compression Conference (DCC). 293–302. https://doi.org/10.1109/DCC.2007.44
• ¹³ Jef Carpenter、Eben Hewitt. 2016. Cassandra: The Defnitive Guide (第2版) . O’Reilly Media, Inc.
• ¹⁴ Bernadette Charron-Bost、Fernando Pedone、and André Schiper (編) . 2010. Replication: Theory and Practice. Springer-Verlag.
• ¹⁵ chDB. 2024. chDB - 組み込み型のOLAP SQL Engine。2024-06-20に https://github.com/chdb-io/chdb から取得。
• ¹⁶ ClickHouse. 2024. ClickBench: 分析データベース向けベンチマーク. 2024-06-20に取得、https://github.com/ClickHouse/ClickBench
• ¹⁷ ClickHouse. 2024. ClickBench: 比較測定。2024-06-20取得、https://benchmark.clickhouse.com より
• ¹⁸ ClickHouse. 2024. ClickHouse Roadmap 2024 (GitHub). https://github.com/ClickHouse/ClickHouse/issues/58392 より2024-06-20取得
• ¹⁹ ClickHouse. 2024. ClickHouse Versions Benchmark. 2024-06-20に https://github.com/ClickHouse/ClickBench/tree/main/versions から取得。
• ²⁰ ClickHouse. 2024. ClickHouse Versions Benchmark Results. https://benchmark.clickhouse.com/versions/ より2024-06-20取得
• ²¹ Andrew Crotty. 2022. MgBench. 2024-06-20に以下から取得：https://github.com/ andrewcrotty/mgbench
• ²² Benoit Dageville, Thierry Cruanes, Marcin Zukowski, Vadim Antonov, Artin Avanes, Jon Bock, Jonathan Claybaugh, Daniel Engovatov, Martin Hentschel, Jiansheng Huang, Allison W. Lee, Ashish Motivala, Abdul Q. Munir, Steven Pelley, Peter Povinec, Greg Rahn, Spyridon Triantafyllis, and Philipp Unterbrunner. 2016. The Snowfake Elastic Data Warehouse. In Proceedings of the 2016 International Conference on Management of Data (San Francisco, California, USA) (SIGMOD ‘16). Association for Computing Machinery, New York, NY, USA, 215–226. https: //doi.org/10.1145/2882903.2903741
• ²³ Patrick Damme, Annett Ungethüm, Juliana Hildebrandt, Dirk Habich, and Wolfgang Lehner. 2019. From a Comprehensive Experimental Survey to a Cost-Based Selection Strategy for Lightweight Integer Compression Algorithms. ACM Trans. Database Syst. 44, 3, Article 9 (2019), 46ページ. https://doi.org/10.1145/3323991
• ²⁴ Philippe Dobbelaere and Kyumars Sheykh Esmaili. 2017. Kafka versus RabbitMQ: A Comparative Study of Two Industry Reference Publish/Subscribe Implementations: Industry Paper (DEBS ‘17). Association for Computing Machinery, New York, NY, USA, 227–238. https://doi.org/10.1145/3093742.3093908
• ²⁵ LLVM ドキュメント。2024年。LLVM における自動ベクトル化。2024-06-20 に https://llvm.org/docs/Vectorizers.html から取得
• ²⁶ Siying Dong、Andrew Kryczka、Yanqin Jin、Michael Stumm. 2021. RocksDB: Evolution of Development Priorities in a キー・バリュー Store Serving Large-scale Applications. ACM Transactions on Storage 17, 4, Article 26 (2021), 32 pages. https://doi.org/10.1145/3483840
• ²⁷ Markus Dreseler, Martin Boissier, Tilmann Rabl, and Matthias Ufacker. 2020. Quantifying TPC-H choke points and their optimizations. Proc. VLDB Endow. 13, 8 (2020), 1206–1220. https://doi.org/10.14778/3389133.3389138
• ²⁸ Ted Dunning. 2021. The t-digest: 分布の効率的な推定. Software Impacts 7 (2021). https://doi.org/10.1016/j.simpa.2020.100049
• ²⁹ Martin Faust, Martin Boissier, Marvin Keller, David Schwalb, Holger Bischof, Katrin Eisenreich, Franz Färber, and Hasso Plattner. 2016. Footprint Reduction and Uniqueness Enforcement with Hash Indices in SAP HANA. In Database and Expert Systems Applications. 137–151. https://doi.org/10.1007/978-3-319-44406- 2_11
• ³⁰ Philippe Flajolet、Eric Fusy、Olivier Gandouet、Frederic Meunier。2007年。HyperLogLog: ほぼ最適なカーディナリティ推定アルゴリズムの解析。『AofA: Analysis of Algorithms, Vol. DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)』所収。Discrete Mathematics and Theoretical Computer Science、137–156。https://doi.org/10.46298/dmtcs.3545
• ³¹ Hector Garcia-Molina, Jefrey D. Ullman, and Jennifer Widom. 2009. Database Systems - The Complete Book (2. Ed.).
• ³² Pawan Goyal, Harrick M. Vin, and Haichen Chen. 1996. Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks. 26, 4 (1996), 157–168. https://doi.org/10.1145/248157.248171
• ³³ Goetz Graefe. 1993. Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25, 2 (1993), 73–169. https://doi.org/10.1145/152610.152611
• ³⁴ Jean-François Im, Kishore Gopalakrishna, Subbu Subramaniam, Mayank Shrivastava, Adwait Tumbde, Xiaotian Jiang, Jennifer Dai, Seunghyun Lee, Neha Pawar, Jialiang Li, and Ravi Aringunram. 2018. Pinot: 5億3,000万人のユーザー向けリアルタイムOLAP. In Proceedings of the 2018 International Conference on Management of Data (Houston, TX, USA) (SIGMOD ‘18). Association for Computing Machinery, New York, NY, USA, 583–594. https://doi.org/10.1145/3183713.3190661
• ³⁵ ISO/IEC 9075-9:2001 2001. 情報技術 — データベース言語 — SQL — 第9部：外部データの管理 (SQL/MED) 。規格。国際標準化機構。
• ³⁶ Paras Jain, Peter Kraft, Conor Power, Tathagata Das, Ion Stoica, and Matei Zaharia. 2023. Analyzing and Comparing Lakehouse Storage Systems. CIDR.
• ³⁷ Project Jupyter. 2024. Jupyter Notebooks. 2024-06-20閲覧、https: //jupyter.org/
• ³⁸ Timo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo, and Peter Boncz. 2018. Everything You Always Wanted to Know about Compiled and Vectorized Queries but Were Afraid to Ask. Proc. VLDB Endow. 11, 13 (sep 2018), 2209–2222. https://doi.org/10.14778/3275366.3284966
• ³⁹ Changkyu Kim, Jatin Chhugani, Nadathur Satish, Eric Sedlar, Anthony D. Nguyen, Tim Kaldewey, Victor W. Lee, Scott A. Brandt, and Pradeep Dubey. 2010. FAST: 最新のCPUおよびGPU向けの、高速でアーキテクチャ特性を考慮した木探索. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (Indianapolis, Indiana, USA) (SIGMOD ‘10). Association for Computing Machinery, New York, NY, USA, 339–350. https://doi.org/10.1145/1807167.1807206
• ⁴⁰ Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley.
• ⁴¹ André Kohn、Viktor Leis、Thomas Neumann. 2018. Adaptive Execution of Compiled Queries. In 2018 IEEE 34th International Conference on Data Engineering (ICDE). 197–208. https://doi.org/10.1109/ICDE.2018.00027
• ⁴² Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan, Nga Tran, Ben Vandiver, Lyric Doshi, and Chuck Bear. 2012. The Vertica Analytic Database: C-Store 7 Years Later. Proc. VLDB Endow. 5, 12 (aug 2012), 1790–1801. https://doi.org/10. 14778/2367502.2367518
• ⁴³ Harald Lang, Tobias Mühlbauer, Florian Funke, Peter A. Boncz, Thomas Neumann, and Alfons Kemper. 2016. Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation. 『Proceedings of the 2016 International Conference on Management of Data (San Francisco, California, USA) (SIGMOD ‘16)』所収. Association for Computing Machinery, New York, NY, USA, 311–326. https://doi.org/10.1145/2882903.2882925
• ⁴⁴ Viktor Leis、Peter Boncz、Alfons Kemper、および Thomas Neumann. 2014. Morseldriven parallelism: a NUMA-aware query evaluation framework for the manycore age. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (Snowbird, Utah, USA) (SIGMOD ‘14). Association for Computing Machinery, New York, NY, USA, 743–754. https://doi.org/10.1145/2588555. 2610507
• ⁴⁵ Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. The adaptive radix tree: ARTful indexing for main-memory databases. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). 38–49. https://doi.org/10.1109/ICDE. 2013.6544812
• ⁴⁶ Chunwei Liu、Anna Pavlenko、Matteo Interlandi、Brandon Haynes. 2023. A Deep Dive into Common Open Formats for Analytical DBMSs. 16, 11 (7月 2023), 3044–3056. https://doi.org/10.14778/3611479.3611507
• ⁴⁷ Zhenghua Lyu、Huan Hubert Zhang、Gang Xiong、Gang Guo、Haozhou Wang、Jinbao Chen、Asim Praveen、Yu Yang、Xiaoming Gao、Alexandra Wang、Wen Lin、Ashwin Agrawal、Junfeng Yang、Hao Wu、Xiaoliang Li、Feng Guo、Jiang Wu、Jesse Zhang、Venkatesh Raghavan。2021年。Greenplum: トランザクションおよび分析ワークロード向けのハイブリッドデータベース (SIGMOD ‘21) 。Association for Computing Machinery、New York, NY, USA、2530–2542。 https: //doi.org/10.1145/3448016.3457562
• ⁴⁸ Roger MacNicol and Blaine French. 2004. Sybase IQ Multiplex - 分析向けに設計された。In Proceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30 (Toronto, Canada) (VLDB ‘04). VLDB Endowment, 1227–1230.
• ⁴⁹ Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geofrey Romer, Shiva Shivakumar, Matt Tolton, Theo Vassilakis, Hossein Ahmadi, Dan Delorey, Slava Min, Mosha Pasumansky, and Jef Shute. 2020. Dremel: WebスケールでのインタラクティブSQL分析の10年. Proc. VLDB Endow. 13, 12 (aug 2020), 3461–3472. https://doi.org/10.14778/3415478.3415568
• ⁵⁰ Microsoft. 2024. Kusto Query Language. https: //github.com/microsoft/Kusto-Query-Language より2024-06-20取得
• ⁵¹ Guido Moerkotte. 1998. Small Materialized Aggregates: データウェアハウジングのための軽量な索引構造. In 第24回 International Conference on Very Large Data Bases (VLDB ‘98) 論文集. 476–487.
• ⁵² Jalal Mostafa、Sara Wehbi、Suren Chilingaryan、Andreas Kopmann。2022。SciTS: A Benchmark for Time-Series Databases in Scientifc Experiments and Industrial Internet of Things。Proceedings of the 34th International Conference on Scientifc and Statistical Database Management (SSDBM ‘22) 所収。Article 12。 https: //doi.org/10.1145/3538712.3538723
• ⁵³ Thomas Neumann. 2011. efficiently Compiling efficient Query Plans for Modern Hardware. Proc. VLDB Endow. 4, 9 (jun 2011), 539–550. https://doi.org/10.14778/ 2002938.2002940
• ⁵⁴ Thomas Neumann and Michael J. Freitag. 2020. Umbra: A Disk-Based System with In-Memory Performance. 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12-15, 2020, Online Proceedings 所収. www.cidrdb.org. http://cidrdb.org/cidr2020/papers/p29-neumanncidr20.pdf
• ⁵⁵ Thomas Neumann, Tobias Mühlbauer, and Alfons Kemper. 2015. Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (Melbourne, Victoria, Australia) (SIGMOD ‘15). Association for Computing Machinery, New York, NY, USA, 677–689. https://doi.org/10.1145/2723372. 2749436
• ⁵⁶ GitHub 上の LevelDB。2024年。LevelDB。 https://github. com/google/leveldb から 2024-06-20 に取得
• ⁵⁷ Patrick O’Neil, Elizabeth O’Neil, Xuedong Chen, and Stephen Revilak. 2009. The Star Schema Benchmark and Augmented Fact Table Indexing. In Performance Evaluation and Benchmarking. Springer Berlin Heidelberg, 237–252. https: //doi.org/10.1007/978-3-642-10424-4_17
• ⁵⁸ Patrick E. O’Neil、Edward Y. C. Cheng、Dieter Gawlick、および Elizabeth J. O’Neil。1996。The log-structured Merge-Tree (LSM-tree)。Acta Informatica 33 (1996) 、351–385。https://doi.org/10.1007/s002360050048
• ⁵⁹ Diego Ongaro、John Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference (USENIX ATC’14). 305–320. https://doi.org/doi/10. 5555/2643634.2643666
• ⁶⁰ Patrick O’Neil、Edward Cheng、Dieter Gawlick、Elizabeth O’Neil。1996年。The Log-Structured Merge-Tree (LSM-Tree)。Acta Inf. 33, 4 (1996), 351–385. https: //doi.org/10.1007/s002360050048
• ⁶¹ Pandas. 2024. Pandas Dataframes. https://pandas. pydata.org/ より 2024-06-20 取得
• ⁶² Pedro Pedreira, Orri Erling, Masha Basmanova, Kevin Wilfong, Laith Sakka, Krishna Pai, Wei He, および Biswapesh Chattopadhyay. 2022. Velox: Meta’s Unified Execution Engine. Proc. VLDB Endow. 15, 12 (2022年8月), 3372–3384. https: //doi.org/10.14778/3554821.3554829
• ⁶³ Tuomas Pelkonen、Scott Franklin、Justin Teller、Paul Cavallaro、Qi Huang、Justin Meza、Kaushik Veeraraghavan. 2015. Gorilla: A Fast, Scalable, in-Memory Time Series Database. Proceedings of the VLDB Endowment 8, 12 (2015), 1816–1827. https://doi.org/10.14778/2824032.2824078
• ⁶⁴ Orestis Polychroniou, Arun Raghavan, and Kenneth A. Ross. 2015. Rethinking SIMD Vectorization for In-Memory Databases. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD ‘15). 1493–1508. https://doi.org/10.1145/2723372.2747645
• ⁶⁵ PostgreSQL。2024年。PostgreSQL - 外部データラッパー。https://wiki.postgresql.org/wiki/Foreign&#95;data&#95;wrappers より2024-06-20取得
• ⁶⁶ Mark Raasveldt、Pedro Holanda、Tim Gubner、Hannes Mühleisen. 2018. Fair Benchmarking Considered difficult: Common Pitfalls In Database Performance Testing. In Proceedings of the Workshop on Testing Database Systems (Houston, TX, USA) (DBTest’18). 論文2、全6ページ。 https://doi.org/10.1145/3209950.3209955
• ⁶⁷ Mark Raasveldt、Hannes Mühleisen. 2019. DuckDB: An Embeddable Analytical Database (SIGMOD ‘19). Association for Computing Machinery, New York, NY, USA, 1981–1984. https://doi.org/10.1145/3299869.3320212
• ⁶⁸ Jun Rao and Kenneth A. Ross. 1999. Cache Conscious Indexing for Decision-Support in Main Memory. Proceedings of the 25th International Conference on Very Large Data Bases (VLDB ‘99), San Francisco, CA, USA, 78–89.
• ⁶⁹ Navin C. Sabharwal and Piyush Kant Pandey. 2020. Working with Prometheus Query Language (PromQL). 『Monitoring Microservices and Containerized Applications』所収. https://doi.org/10.1007/978-1-4842-6216-0&#95;5
• ⁷⁰ Todd W. Schneider. 2022. New York City Taxi and For-Hire Vehicle Data. 2024-06-20に https://github.com/toddwschneider/nyc-taxi-data から取得
• ⁷¹ Mike Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Sam Madden, Elizabeth O’Neil, Pat O’Neil, Alex Rasin, Nga Tran, and Stan Zdonik. 2005. C-Store: A Column-Oriented DBMS. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB ‘05). 553–564.
• ⁷² Teradata. 2024. Teradata Database. 2024-06-20に取得。https://www. teradata.com/resources/datasheets/teradata-database
• ⁷³ Frederik Transier. 2010. インメモリ・テキスト検索エンジンのためのアルゴリズムとデータ構造. 博士論文. https://doi.org/10.5445/IR/1000015824
• ⁷⁴ Adrian Vogelsgesang, Michael Haubenschild, Jan Finis, Alfons Kemper, Viktor Leis, Tobias Muehlbauer, Thomas Neumann, and Manuel Then. 2018. Get Real: How Benchmarks Fail to Represent the Real World. In Proceedings of the Workshop on Testing Database Systems (Houston, TX, USA) (DBTest’18). 論文番号1、全6ページ。 https://doi.org/10.1145/3209950.3209952
• ⁷⁵ LZ4 ウェブサイト。2024年。LZ4。https://lz4.org/ (2024-06-20 取得)
• ⁷⁶ PRQLウェブサイト。2024年。PRQL。2024-06-20に https://prql-lang.org より取得。⁷⁷ Till Westmann, Donald Kossmann, Sven Helmer, and Guido Moerkotte. 2000. The Implementation and Performance of Compressed Databases. SIGMOD Rec.
• 29, 3 (2000年9月), 55–67. https://doi.org/10.1145/362084.362137 ⁷⁸ Fangjin Yang, Eric Tschetter, Xavier Léauté, Nelson Ray, Gian Merlino, and Deep Ganguli. 2014. Druid: A Real-Time Analytical Data Store. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (Snowbird, Utah, USA) (SIGMOD ‘14). Association for Computing Machinery, New York, NY, USA, 157–168. https://doi.org/10.1145/2588555.2595631
• ⁷⁹ Tianqi Zheng, Zhibin Zhang, and Xueqi Cheng. 2020. SAHA: A String Adaptive Hash Table for Analytical Databases. Applied Sciences 10, 6 (2020). https: //doi.org/10.3390/app10061915
• ⁸⁰ Jingren Zhou and Kenneth A. Ross. 2002. SIMD 命令を用いたデータベース操作の実装. In 2002 ACM SIGMOD International Conference on Management of Data (SIGMOD ‘02) 論文集. 145–156. https://doi.org/10. 1145/564691.564709
• ⁸¹ Marcin Zukowski, Sandor Heman, Niels Nes, Peter Boncz. 2006. Super-Scalar RAM-CPU Cache Compression. 『Proceedings of the 22nd International Conference on Data Engineering (ICDE ‘06)』所収. 59. https://doi.org/10.1109/ICDE. 2006.150