メインコンテンツまでスキップ
メインコンテンツまでスキップ

アーキテクチャの概要

This is the web version of our VLDB 2024 scientific paper. We also blogged about its background and journey, and recommend watching the VLDB 2024 presentation by ClickHouse CTO and creator, Alexey Milovidov:

ABSTRACT

過去数十年にわたり、保存および分析されるデータ量は指数関数的に増加しています。さまざまな産業や業界の企業は、このデータを利用して製品を改善し、パフォーマンスを評価し、ビジネス上重要な意思決定を行うようになっています。しかし、データ量がインターネットスケールに達するにつれて、企業は歴史的データと新データをコスト効率よくスケーラブルな方法で管理し、高い同時クエリ数とリアルタイムのレイテンシ(使用例に応じて1秒未満)を期待して分析する必要があります。

この論文では、ペタバイト級のデータセットに対して高性能な分析を行うために設計された人気のオープンソースOLAPデータベース、ClickHouseの概要を示します。そのストレージ層は、伝統的なログ構造マージ(LSM)ツリーに基づいたデータ形式と、バックグラウンドでの歴史的データの継続的な変換(例:集約、アーカイブ)のための新しい技術を組み合わせています。クエリは便利なSQLダイアレクトで書かれ、最先端のベクトル化クエリ実行エンジンによって処理され、オプションでコードコンパイルも可能です。ClickHouseは、クエリ内で無関係なデータを評価しないよう積極的にプルーニング技術を使用します。他のデータ管理システムは、テーブル関数、テーブルエンジン、またはデータベースエンジンレベルで統合できます。実世界のベンチマークは、ClickHouseが市場で最も高速な分析データベースの一つであることを示しています。

1 INTRODUCTION

この論文では、高パフォーマンスの分析クエリを行うために設計された列指向OLAPデータベースであるClickHouseについて説明します。ClickHouseは、2009年にWebスケールのログファイルデータ用のフィルターと集約演算子として開始され、2016年にオープンソース化されました。Figure 1は、この論文で説明されている主要な機能がClickHouseに導入された時期を示しています。

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

  1. 高い取り込みレートの巨大データセット。Web分析、金融、eコマースのようなデータ駆動型アプリケーションは、巨大で常に増加するデータ量が特徴です。巨大データセットを処理するために、分析データベースは効率的なインデックス作成や圧縮戦略だけでなく、複数のノードにデータを分散させる(スケールアウト)能力を提供する必要があります。単一サーバーは数十テラバイトのストレージに制限されているため、最近のデータはリアルタイムインサイトに対して歴史的データよりも重要であることが多いです。その結果、分析データベースは高レートまたはバーストで新しいデータを取り込む能力を有し、さらに並行報告クエリを遅くせずに歴史的データを「重要度を下げる」(例:集約、アーカイブ)必要があります。

  2. 低レイテンシーでの多くの同時クエリ。クエリは一般に、アドホック(例:探索的データ分析)または再発(例:定期的なダッシュボードクエリ)に分類できます。用途がインタラクティブであればあるほど、クエリレイテンシーは低くなることが期待され、クエリ最適化および実行において課題を引き起こします。再発クエリは、作業負荷に応じてデータベースの物理的なレイアウトを調整する機会も提供します。そのため、データベースは頻繁なクエリを最適化できるプルーニング技術を提供すべきです。クエリの優先度に応じて、データベースは同時に多くのクエリが実行されていても、CPU、メモリ、ディスク、ネットワークI/Oなどの共有システムリソースへの平等または優先アクセスを保証する必要があります。

  3. 多様なデータストア、ストレージ場所、フォーマットの景観。既存のデータアーキテクチャと統合するために、現代の分析データベースは、いかなるシステム、場所、またはフォーマットであっても外部データを読み書きするために高い程度のオープン性を示す必要があります。

  4. パフォーマンスイントロスペクションをサポートする便利なクエリ言語。OLAPデータベースの実際の使用は、追加の「ソフト」要件を持ちます。たとえば、ニッチなプログラミング言語の代わりに、ユーザーはしばしばネストされたデータ型と幅広い通常の、集約、およびウィンドウ関数を備えた表現豊かなSQLダイアレクトでデータベースとインターフェースすることを好みます。分析データベースは、システムや個別クエリのパフォーマンスをイントロスペクトするために洗練されたツールも提供する必要があります。

  5. 業界標準の堅牢性および多様な展開。一般的なハードウェアは信頼性が低いため、データベースはノードの障害に対して堅牢性を提供するためにデータ複製を行わなければなりません。また、データベースは古いラップトップから強力なサーバーまで、任意のハードウェアで稼働する必要があります。最後に、JVMベースのプログラムにおけるガベージコレクションのオーバーヘッドを回避し、ベアメタルパフォーマンス(例:SIMD)を可能にするために、理想的にはデータベースはターゲットプラットフォームのネイティブバイナリとして展開されるべきです。

Image 01

Figure 1: ClickHouseのタイムライン。

2 ARCHITECTURE

Image 02

Figure 2: ClickHouseデータベースエンジンの高レベルアーキテクチャ。

Figure 2に示されるように、ClickHouseエンジンは、クエリ処理層(4節で説明)、ストレージ層(3節)、および統合層(5節)という3つの主要な層に分かれています。また、アクセス層がユーザーセッションとアプリケーションとの通信をさまざまなプロトコル経由で管理します。スレッド処理、キャッシング、ロールベースのアクセス制御、バックアップ、および継続的監視のための直交コンポーネントがあります。ClickHouseは、依存関係のない単一の静的リンクされたバイナリとしてC++で構築されています。

クエリ処理は、受信クエリの解析、論理プランと物理プランの構築および最適化、そして実行の従来のパラダイムに従っています。ClickHouseは、MonetDB/X100に似たベクトル化実行モデルを使用し、この組み合わせで機会主義的なコードコンパイルを行います。クエリは、機能が豊富なSQLダイアレクト、PRQL、またはKustoのKQLで書くことができます。

ストレージ層は、テーブルデータのフォーマットと場所をカプセル化するさまざまなテーブルエンジンで構成されています。テーブルエンジンは3つのカテゴリに分かれます。最初のカテゴリは、ClickHouseでの主要な永続フォーマットを表すMergeTreeファミリーのテーブルエンジンです。LSMツリーに基づくアイデアを基に、テーブルは水平にソートされたパーツに分割され、バックグラウンドプロセスによって継続的にマージされます。個々のMergeTreeテーブルエンジンは、入力パーツから行をどのようにマージするかで異なります。たとえば、古くなった場合には行を集約したり置き換えたりすることができます。

2番目のカテゴリは、クエリ実行を高速化または分散させるための特定目的のテーブルエンジンです。このカテゴリには、辞書と呼ばれるメモリ内キー値テーブルエンジンが含まれています。辞書は、内部または外部データソースに対して定期的に実行されるクエリの結果をキャッシュします。これにより、データの古さをある程度許容できるシナリオでのアクセスレイテンシーが大幅に削減されます。特定目的のテーブルエンジンの他の例には、一時的なテーブル用に使用される純粋なメモリ内エンジンや、透明なデータシャーディング用の分散テーブルエンジンがあります(下記を参照)。

テーブルエンジンの3番目のカテゴリは、リレーショナルデータベース(例:PostgreSQL、MySQL)、パブリッシュ/サブスクライブシステム(例:Kafka、RabbitMQ [24])、またはキー/値ストア(例:Redis)との双方向データ交換用の仮想テーブルエンジンです。仮想エンジンは、データレイク(例:Iceberg、DeltaLake、Hudi [36])やオブジェクトストレージ内のファイル(例:AWS S3、Google GCP)とも相互作用できます。

ClickHouseは、スケーラビリティと可用性のために、複数のクラスターノードにわたるテーブルのシャーディングと複製をサポートしています。シャーディングは、シャーディング式によってテーブルをテーブルシャードのセットに分割します。個々のシャードは相互に独立したテーブルであり、通常は異なるノードに配置されます。クライアントは、シャードを直接読み書きでき、つまりそれらを別個のテーブルとして扱うこともできますし、すべてのテーブルシャードのグローバルビューを提供する分散特殊テーブルエンジンを使用することもできます。シャーディングの主な目的は、個々のノードの容量を超えるデータセットを処理することです(通常、数十テラバイトのデータ)。シャーディングの別の使用法は、テーブルの読み書き負荷を複数のノードに分散させること、つまり負荷分散です。そのため、シャードはノード障害に対する耐障害性のために複製されることができます。この目的のために、各Merge-Treeテーブルエンジンには、その対応するReplicatedMergeTreeエンジンがあり、Raftコンセンサスに基づくマルチマスターコーディネーション方式を使用します [59](C++で書かれたApache Zookeeperのドロップイン置き換えであるKeeperによって実装)を使用하여、常に設定可能な数のレプリカを各シャードに持つことを保証します。セクション3.6では、レプリケーションメカニズムについて詳しく説明します。例として、Figure 2は、2つのノードに複製された2つのシャードを持つテーブルを示しています。

最後に、ClickHouseデータベースエンジンは、オンプレミス、クラウド、スタンドアロン、またはプロセス内モードで運用できます。オンプレミスモードでは、ユーザーはClickHouseを単一サーバーまたはシャーディングおよび/または複製を持つマルチノードクラスタとしてローカルにセットアップします。クライアントは、ネイティブ、MySQLの、PostgreSQLのバイナリワイヤプロトコル、またはHTTP REST APIを介してデータベースと通信します。クラウドモードは、完全に管理され、自動スケーリングするDBaaSオファリングであるClickHouse Cloudによって表されます。この論文はオンプレミスモードに焦点を当てていますが、次回の publication でClickHouse Cloudのアーキテクチャを説明する予定です。スタンドアロンモードは、ClickHouseをファイルの分析と変換のためのコマンドラインユーティリティに変え、catやgrepのようなUnixツールのSQLベースの代替手段を提供します。このモードは事前の設定を必要とせず、単一のサーバーに制限されます。最近、Jupyterノートブック[37]のようなインタラクティブなデータ分析の使用例のために、chDBと呼ばれるプロセス内モードが開発されました[15]。DuckDB[67]からインスピレーションを得たchDBは、ClickHouseをホストプロセスに高性能OLAPエンジンとして組み込みます。その他のモードと比較して、データベースエンジンとアプリケーション間で、同じアドレス空間で実行されるため、データソースと結果データを効率的に渡すことができます。

3 STORAGE LAYER

このセクションでは、ClickHouseのネイティブストレージフォーマットとしてのMergeTree*テーブルエンジンについて説明します。ディスク上の表現を説明し、ClickHouseにおける3つのデータプルーニング技術について議論します。その後、同時挿入に影響を与えることなくデータを継続的に変換するマージ戦略を紹介します。最後に、更新と削除、データ重複排除、データ複製、ACID準拠がどのように実装されているかを説明します。

3.1 On-Disk Format

MergeTree*テーブルエンジン内の各テーブルは、不変のテーブルパーツのコレクションとして整理されます。行のセットがテーブルに挿入されると、パーツが作成されます。パーツは、その内容を解釈するために中央カタログへの追加の検索なしに必要なすべてのメタデータを含むという点で自己完結しています。テーブルごとのパーツの数を少なく保つために、バックグラウンドマージジョブは定期的に複数の小さなパーツをより大きなパーツに統合し、設定可能なパーツサイズ(デフォルトでは150 GB)に達するまで続けます。パーツはテーブルの主キー列によってソートされているため(3.2節を参照)、効率的なk方向マージソートがマージに使用されます。元のパーツは非アクティブとしてマークされ、その参照カウントがゼロに減少すると最終的に削除されます。すなわち、他のクエリがそれらから読み取ることはありません。

行は、2つのモードで挿入できます。:同期挿入モードでは、各INSERTステートメントが新しいパーツを作成し、それをテーブルに追加します。マージのオーバーヘッドを最小化するために、データベースクライアントはトゥプルを一度に20,000行など一括で挿入することを推奨されています。しかし、データがリアルタイムで分析されるべきである場合、クライアント側のバッチ処理によって引き起こされる遅延はしばしば受け入れられないものです。たとえば、可視性の使用例は、数千の監視エージェントがイベントやメトリクスデータを継続的に小さな量で送信することを含みます。このようなシナリオでは、ClickHouseが同じテーブルへの複数の受信INSERTから行をバッファリングし、バッファサイズが設定可能な閾値を超えるか、タイムアウトが切れるまで新しいパーツを作成しない非同期挿入モードを利用できます。

Image 03

Figure 3: MergeTree*-エンジンテーブルの挿入とマージ。

Figure 3は、MergeTree*-エンジンテーブルへの4つの同期および2つの非同期挿入を示しています。2つのマージは、アクティブなパーツの数を最初の5つから2つに減らしました。

LSMツリー [58] とそのさまざまなデータベースでの実装 [13, 26, 56] では、ClickHouseはすべてのパーツを平等に扱い、階層に配置することはありません。その結果、マージはもはや同じレベルのパーツに限られません。これは、パーツの暗黙の時間的順序を放棄することも意味し、トゥームストーンに基づかない他の更新および削除のメカニズムが必要になります(3.4節を参照)。ClickHouseは挿入をディスクに直接書き込みますが、他のLSMツリーベースのストアは通常、先行書き込みログを使用します(3.7節を参照)。

パーツはディスク上のディレクトリに対応し、各列用に1つのファイルを含みます。最適化として、小さなパーツ(デフォルトでは10MB未満)の列は、読み書きの空間的局所性を向上させるために、単一のファイルに連続して保存されます。パーツの行はさらに8192レコードのグループ、すなわちグラニュールに論理的に分割されます。グラニュールは、ClickHouseのスキャンおよびインデックスルックアップ演算子が処理する最小の不可分なデータユニットを表します。ただし、ディスク上のデータの読み書きはグラニュールレベルではなく、カラム内の隣接するグラニュールを結合したブロックのグラニュラリティで行われます。新しいブロックは、設定可能なバイトサイズ(デフォルトは1MB)に基づいて形成され、すなわち、ブロック内のグラニュールの数は変動し、列のデータ型と分布に依存します。さらに、ブロックはそのサイズとI/Oコストを削減するために圧縮されます。ClickHouseはデフォルトでLZ4 [75] を一般的な圧縮アルゴリズムとして使用しますが、ユーザーは浮動小数点データ用のGorilla [63] やFPC [12]のような特殊なコーデックも指定できます。圧縮アルゴリズムはチェインされることもあります。たとえば、数値の論理的冗長性を最初にデルタコーディング [23]を使用して削減し、その後で重い圧縮を行い、最後にAESコーデックを使用してデータを暗号化することが可能です。ブロックは、ディスクからメモリに読み込まれるときにリアルタイムで解凍されます。圧縮にもかかわらず、ClickHouseは各列に対して、各グラニュールIDをカラムファイル内のその圧縮ブロックのオフセットおよび非圧縮ブロック内のグラニュールのオフセットに関連付けるマッピングも保存します。

列はさらに辞書エンコード [2, 77, 81] されたり、Nullableを持つ内部ビットマップを追加したりすることができます。LowCardinality(T)は、元のカラムの値を整数IDで置き換え、ユニークな値が少ないデータのストレージオーバーヘッドを大幅に削減します。Nullable(T) は、カラム T に対して、カラム値が NULL であるかどうかを表す内部ビットマップを追加します。

最後に、テーブルは任意のパーティショニング式を使用して範囲、ハッシュ、またはラウンドロビンでパーティショニングできます。パーティションプルーニングを有効にするために、ClickHouseは、各パーティションの最小値と最大値をパーティショニング式の形式で追加で保存します。ユーザーは、ハイパーログログ [30] やt-digest [28] 統計のような高度なカラム統計を任意で作成し、基数推定も提供できます。

3.2 Data Pruning

ほとんどの使用例では、ペタバイトのデータをスキャンして単一のクエリに応答することは非常に遅くコストがかかります。ClickHouseは、検索中の大多数の行をスキップすることを可能にする3つのデータプルーニング技術をサポートしており、それによってクエリを大幅に高速化することができます。

最初に、ユーザーはテーブルに主キーインデックスを定義できます。主キー列は、各パーツ内の行のソート順を決定します。つまり、インデックスはローカルにクラスタ化されたものになります。ClickHouseは、各グラニュールの最初の行の主キー列値からそのグラニュールIDへのマッピングを、各パーツのために追加でも保存します。すなわち、インデックスはスパースです [31]。生成されるデータ構造は通常メモリ内に完全に保持できるほど小さく、たとえば810万行をインデックスするにはわずか1000エントリが必要です。主キーの主な目的は、順次スキャンの代わりにバイナリ検索を使用して、頻繁にフィルタされるカラムに対する等号および範囲述語を評価することです(4.4節を参照)。ローカルソートはさらにパーツのマージやクエリ最適化にも活用されることができ、並べ替え列の接頭辞を形成する主キー列があれば、物理的実行プランからソート演算子を削除することができます。

Figure 4は、ページインプレッション統計のテーブルの主キーインデックスをEventTime列に示しています。クエリ内の範囲述語に一致するグラニュールは、EventTimeを順次スキャンする代わりに、主キーインデックスをバイナリ検索することで見つけることができます。

Image 04

Figure 4: 主キーインデックスを使用したフィルターの評価。

第二に、ユーザーはテーブルのプロジェクションを作成できます。つまり、異なる主キーでソートされた同じ行を含むテーブルの代替バージョンです [71]。プロジェクションは、メインテーブルの主キーとは異なる列でフィルタリングするクエリのスピードを向上させることができますが、挿入、マージ、スペース消費に対するオーバーヘッドが増加します。デフォルトでは、プロジェクションはメインテーブルに新しく挿入されたパーツからのみ遅延的にポピュレートされますが、ユーザーがプロジェクションをすべて具現化しない限り、既存のパーツからは取得されません。クエリオプティマイザは、メインテーブルまたはプロジェクションからの読み取りを、推定されたI/Oコストに基づいて選択します。パーツのプロジェクションが存在しない場合、クエリの実行は対応するメインテーブルパーツにフォールバックします。

第三に、スキッピングインデックスはプロジェクションに対する軽量の代替手段を提供します。スキッピングインデックスのアイデアは、複数の連続するグラニュールのレベルでの小さなメタデータを保存し、不必要な行をスキャンするのを防ぐことです。スキッピングインデックスは、任意のインデックス式に対して作成され、設定可能なグラニュラリティ、つまりスキッピングインデックスブロック内のグラニュール数を使用できます。利用可能なスキッピングインデックスタイプには以下が含まれます:1. 最小-最大インデックス [51]、各インデックスブロックのインデックス式の最小値と最大値を保存します。このインデックスタイプは、絶対範囲が小さいローカルクラスタデータに適しています、例:緩くソートされたデータ。2. セットインデックスは、設定可能な数のユニークなインデックスブロック値を保存します。これらのインデックスは、小さなローカル基数のデータ、つまり「クランプされている」値で使用するのが最良です。3. ブルームフィルタインデックス [9] は、行、トークン、またはn-グラム値のために構築され、設定可能な誤検知率を持ちます。これらのインデックスはテキスト検索 [73] をサポートしますが、最小-最大およびセットインデックスとは異なり、範囲や否定述語に使用することはできません。

3.3 Merge-time Data Transformation

ビジネスインテリジェンスや可視化の使用例では、常に高いレートまたはバーストで生成されるデータを処理する必要があります。また、最近生成されたデータは通常、歴史的データよりも意味のあるリアルタイムインサイトのためにより関連性が高いです。このような使用例では、データベースは高いデータ取り込みレートを維持しながら集約やデータの老化といった技術を用いて歴史的データのボリュームを継続的に削減する必要があります。ClickHouseは、さまざまなマージ戦略を用いて既存データの継続的な増分変換を可能にします。マージ時のデータ変換はINSERTステートメントのパフォーマンスを損なうことはありませんが、テーブルに不要な(例:古いまたは非集約)値が決して含まれないことを保証することはできません。必要に応じて、すべてのマージ時変換は、SELECTステートメントでFINALキーワードを指定することによりクエリ時間に適用できます。

置換マージは、各トゥプルの含まれるパーツの作成タイムスタンプに基づいて、最も最近挿入されたバージョンのみを保持します。古いバージョンは削除されます。トゥプルは、同じ主キー列値を持つ場合には等価と見なされます。どのトゥプルが保持されるかを明示的に制御するために、比較のための特別なバージョン列を指定することも可能です。置換マージは、通常頻繁に更新される使用例でのマージ時更新メカニズムとして、または挿入時データ重複排除の代替手段(3.5節を参照)として一般的に使用されます。

集約マージは、同じ主キー列値を持つ行を集約行にまとめます。非主キー列は、要約値を保持する部分集約状態でなければなりません。2つの部分集約状態、例えばavg()のための合計とカウントは、新しい部分集約状態に結合されます。集約マージは、通常のテーブルよりもマテリアライズドビューに使用されます。マテリアライズドビューは、ソーステーブルに対する変換クエリに基づいてポピュレートされます。ClickHouseは、他のデータベースとは異なり、ソーステーブルの全内容でマテリアライズドビューを定期的に更新することはありません。むしろ、マテリアライズドビューは新しいパーツがソーステーブルに挿入されるときに変換クエリの結果で増分的に更新されます。

Figure 5は、ページインプレッション統計のテーブルに定義されたマテリアライズドビューを示しています。ソーステーブルに挿入された新しいパーツについて、変換クエリは地域ごとに最大および平均レイテンシーを計算し、その結果をマテリアライズドビューに挿入します。集約関数avg()およびmax()は、実際の結果の代わりに部分集約状態を返します。マテリアライズドビューに対して定義された集約マージは、異なるパーツの部分集約状態を継続的に結合します。最終的な結果を得るために、ユーザーはマテリアライズドビュー内の部分集約状態をavg() および max() で consolidation します。

Image 05

Figure 5: マテリアライズドビューにおける集約マージ。

TTL(有効期限)マージは歴史的データの老化を提供します。削除や集約マージとは異なり、TTLマージは一度に1つのパーツのみを処理します。TTLマージは、トリガーとアクションのルールによって定義されます。トリガーは、各行に対してタイムスタンプを計算する式であり、 TTLマージが実行される時点と比較されます。この機能により、ユーザーは行の粒度でアクションを制御できますが、すべての行が指定された条件を満たすかどうかを確認し、全体のパーツに対してアクションを実行するのが十分とされます。考えられるアクションには、1. パーツを別のボリュームに移動(例:より安価で遅いストレージ)する、2. パーツを再圧縮する(例:より重いコーデックを使用)、3. パーツを削除する、4. ロールアップ(つまり、行をグルーピングキーおよび集約関数を使用して集約する)があります。

例として、Listing 1.のログテーブル定義を考えます。ClickHouseは、タイムスタンプ列の値が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 '

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

3.4 Updates and Deletes

MergeTree*テーブルエンジンの設計は、パンのみのワークロードを優遇しますが、一部の使用例では、たまに既存データを変更する必要があります(例えば、規制遵守のため)。更新または削除データに対する2つのアプローチがあり、どちらも並行挿入をブロックしません。

変異は、テーブルのすべてのパーツをその場で書き換えます。テーブル(削除)またはカラム(更新)が一時的にサイズを2倍にするのを防ぐために、この操作は非原子的であり、並行的なSELECTステートメントは変異したパーツと未変異のパーツを読み取る可能性があります。変異は、操作の終わりにデータが物理的に変更されることを保証します。しかし、削除変異は依然として高価であり、すべてのパーツ内のすべてのカラムを書き換えます。

代わりに、軽量削除は、行が削除されたかどうかを示す内部ビットマップカラムのみを更新します。ClickHouseは、削除された行を結果から除外するために、SELECTクエリに追加のフィルターをビットマップカラムに追加します。削除された行は、指定されていない未来の時点での通常のマージによってのみ物理的に削除されます。列の数に応じて、軽量削除は変異よりもはるかに高速になる可能性がありますが、SELECTは遅くなります。

同じテーブルに対して行われる更新と削除操作は、論理的な競合を避けるためにまれで直列化されることが期待されます。

3.5 Idempotent Inserts

実際に頻繁に発生する問題は、クライアントがデータをテーブルに挿入するためにサーバーに送信した後に接続タイムアウトをどのように処理すべきかということです。この場合、クライアントはデータが正常に挿入されたのかどうかを区別するのが難しくなります。この問題は、クライアントからサーバーへデータを再送信し、主キーまたは一意性制約に依存して重複した挿入を拒否することによって伝統的に解決されます。データベースは、バイナリツリー [39, 68]、ラジックスツリー [45]、またはハッシュテーブル [29] に基づくインデックス構造を迅速に使用して、必要なポイントルックアップを実行します。これらのデータ構造はすべてのトゥプルをインデックスしているため、大規模データセットと高い取り込み率に対して、そのスペースと更新のオーバーヘッドは高くなります。

ClickHouseは、各挿入が最終的にパーツを作成するという事実に基づいたより軽量な代替手段を提供します。具体的には、サーバーは最後に挿入されたN個のパーツ(例:N=100)のハッシュを保持し、既知のハッシュを持つパーツの再挿入を無視します。複製されていないテーブルと複製テーブルのハッシュは、それぞれKeeperにローカルに保存されます。その結果、挿入は冪等になります。つまり、クライアントはタイムアウト後に同じバッチの行を再送信し、サーバーが重複排除に対応していると仮定できます。重複除去プロセスのより良い制御のために、クライアントはオプションでパートハッシュとして機能する挿入トークンを提供できます。ハッシュベースの重複除去は新しい行をハッシュするに伴うオーバーヘッドを伴いますが、ハッシュを保存して比較するコストは無視できるものです。

### <Anchor id="page-5-0"/>3.6 データレプリケーション \{#3-6-data-replication}

レプリケーションは高い可用性(ノードの障害に対する耐障害性)の前提条件ですが、負荷分散やゼロダウンタイムのアップグレードにも使用されます [\[14\]](#page-12-17)。ClickHouseにおけるレプリケーションは、テーブル部分のセット(セクション [3.1)](#page-2-2) とカラム名や型などのテーブルメタデータで構成されるテーブルの状態という概念に基づいています。ノードは、テーブルの状態を以下の3つの操作を使用して前進させます。1. 挿入(Inserts)は状態に新しいパートを追加します。2. マージ(Merges)は新しいパートを追加し、状態から既存のパートを削除します。3. ミューテーション(Mutations)やDDLステートメントは、パーツを追加し、または削除し、またはテーブルメタデータを変更します。この操作は特定の動作に応じて異なります。操作は単一のノード上でローカルに実行され、グローバルレプリケーションログ内の状態遷移のシーケンスとして記録されます。

レプリケーションログは、通常3つのClickHouse Keeperプロセスのアンサンブルによって維持され、Raftコンセンサスアルゴリズム [\[59\]](#page-13-4) を使用して、ClickHouseノードのクラスターに対する分散で耐障害性のある調整層を提供します。すべてのクラスターノードは、最初はレプリケーションログの同じ位置を指しています。ノードがローカルな挿入、マージ、ミューテーション、DDLステートメントを実行している間、レプリケーションログは他のすべてのノードで非同期に再生されます。その結果、レプリケートされたテーブルは最終的に一貫性があるだけであり、つまり、ノードは最新の状態に収束する間に一時的に古いテーブルの状態を読み取ることができます。上記の多くの操作は、ノードの過半数またはすべてのノードが新しい状態を採用するまで、同期的に実行することもできます。

例として、 [図 6](#page-5-3) は、3つのClickHouseノードのクラスター内で最初は空のレプリケートテーブルを示しています。ノード1は最初に2つの挿入ステートメントを受信し、これらをレプリケーションログに記録します(1 2)。次にノード2は、最初のログエントリを取得して再生し(3)、ノード1から新しいパートをダウンロードします(4)。一方、ノード3は両方のログエントリを再生します(3 4 5 6)。最後に、ノード3は両方のパートを新しいパートにマージし、入力パートを削除し、レプリケーションログにマージエントリを記録します(7)。

<Anchor id="page-5-3"/><Image img={image_06} size="lg" alt="Image 06"/>

図 6: 3つのノードのクラスター内のレプリケーション。

同期を加速するための3つの最適化が存在します。まず、クラスターに追加された新しいノードは、レプリケーションログを最初から再生するのではなく、最後のレプリケーションログエントリを書き込んだノードの状態を単にコピーします。次に、マージはローカルで繰り返すか、別のノードから結果パートを取得することによって再生されます。正確な動作は設定可能で、CPU消費とネットワークI/Oとのバランスを取ることができます。例えば、データセンター間でのレプリケーションは、運用コストを最小限に抑えるためにローカルマージを優先することが一般的です。3つ目は、ノードが相互に独立したレプリケーションログエントリを並行して再生することです。これには、例えば、同じテーブルに連続して挿入された新しいパートの取得や、異なるテーブルに対する操作が含まれます。

### <Anchor id="page-5-1"/>3.7 ACID準拠 \{#3-7-acid-compliance}

同時に読み取りおよび書き込みを行う操作のパフォーマンスを最大化するため、ClickHouseはロックを可能な限り避けます。クエリは、クエリの開始時に作成される、関与するすべてのテーブルのすべてのパートのスナップショットに対して実行されます。これにより、並行して行われるINSERTやマージ(セクション [3.1)](#page-2-2) によって挿入された新しいパートが実行に参加しなくなります。パーツが同時に変更されたり削除されたりするのを防ぐために(セクション [3.4)](#page-4-0)、処理されたパーツの参照カウントはクエリの期間中増加します。形式的には、これはバージョン付きパーツに基づくMVCCの変種により実現されるスナップショット隔離に相当します [\[6\]](#page-12-18)。その結果、ステートメントは一般的にはACID準拠ではなく、スナップショットが取得される時点の並行書き込みが各々単一のパートにのみ影響を与える稀なケースを除いてそうなります。

実際には、ClickHouseの書き込みが多い意思決定の使用ケースのほとんどは、停電時に新しいデータを失う小さなリスクを許容します。データベースは、これを利用して、新しく挿入されたパーツのコミット(fsync)をデフォルトで強制せず、カーネルが原子性を犠牲にして書き込みをバッチ処理できるようにしています。

## <Anchor id="page-6-0"/>4 クエリ処理層 \{#4-query-processing-layer}

<Anchor id="page-6-1"/><Image img={image_07} size="lg" alt="Image 07"/>

図 7: SIMDユニット、コア、およびノード間の並行処理。

[図 7](#page-6-1) に示されているように、ClickHouseはデータ要素、データチャンク、テーブルシャードの階層でクエリを並列化します。複数のデータ要素は、SIMD命令を使用してオペレーター内で同時に処理されることがあります。単一のノード上では、クエリエンジンは複数のスレッドでオペレーターを同時に実行します。ClickHouseはMonetDB/X100と同じベクトル化モデルを使用しています [\[11\]](#page-12-0)。つまり、オペレーターは、単一の行ではなく複数の行(データチャンク)を生成、渡し、消費して、仮想関数呼び出しのオーバーヘッドを最小化します。ソーステーブルが互いに重複しないテーブルシャードに分割されている場合、複数のノードがシャードを同時にスキャンすることができます。その結果、すべてのハードウェアリソースが完全に利用され、クエリ処理はノードを追加することで水平方向に、コアを追加することで垂直方向にスケール可能です。

このセクションの残りでは、まずデータ要素、データチャンク、シャードの粒度での並列処理について詳細に説明します。次に、クエリパフォーマンスを最大化するための重要な最適化をいくつか紹介します。最後に、ClickHouseが同時クエリの存在下で共有システムリソースを管理する方法について説明します。

### 4.1 SIMD並列化 \{#4-1-simd-parallelization}

オペレーター間で複数の行を渡すことは、ベクトル化の機会を生み出します。ベクトル化は、手動で記述されたイントリンシック [\[64,](#page-13-18) [80\]](#page-13-19) またはコンパイラの自動ベクトル化 [\[25\]](#page-12-19) に基づいています。ベクトル化の恩恵を受けるコードは、異なる計算カーネルにコンパイルされます。例えば、クエリオペレーターの内側のホットループは、非ベクトル化カーネル、自動ベクトル化されたAVX2カーネル、手動でベクトル化されたAVX-512カーネルの観点から実装できます。最も高速なカーネルは、cpuid命令に基づいて[ランタイムで選択されます](https://clickhou.se/cpu-dispatch)。このアプローチにより、ClickHouseは15年前のシステムでも稼働可能(最低限SSE 4.2が必要)でありながら、最近のハードウェアで大幅な速度向上を提供します。

### 4.2 マルチコア並列化 \{#4-2-multi-core-parallelization}

<Anchor id="page-7-1"/><Image img={image_08} size="lg" alt="Image 08"/>

図 8: 3つのレーンを持つ物理オペレーター計画。

ClickHouseは、SQLクエリを物理プランオペレーターの有向グラフに変換する一般的なアプローチ [\[31\]](#page-12-13) を採用しています。オペレーター計画の入力は、ネイティブまたはサポートされている3rdパーティフォーマットのいずれかでデータを読み込む特殊なソースオペレーターによって表されます(セクション [5)](#page-9-0)を参照)。同様に、特別なシンクオペレーターは結果を望ましい出力フォーマットに変換します。物理オペレーター計画は、クエリコンパイル時に、設定可能な最大ワーカースレッド数(デフォルトではコアの数)とソーステーブルのサイズに基づいて独立した実行レーンに展開されます。レーンは、並列オペレーターによって処理されるデータを非重複レンジに分解します。並列処理の機会を最大化するために、レーンは可能な限り遅くまでマージされます。

例として、 [図 8](#page-7-1) 内のノード1のボックスは、ページインプレッション統計を持つテーブルに対する典型的なOLAPクエリのオペレーターグラフを示しています。最初のステージでは、ソーステーブルの3つの重複しないレンジが同時にフィルタリングされます。再分配交換オペレーターは、処理スレッドが均等に使用されるように、最初の段階と第2段階間で結果チャンクを動的にルーティングします。スキャンしたレンジの選択性が大幅に異なる場合、レーンは最初のステージの後に不均衡になることがあります。第2ステージでは、フィルターを生き残った行がRegionIDでグループ化されます。集約オペレーターは、RegionIDをグループ化カラムとして持つローカル結果グループを維持し、avg()の部分集約状態として各グループの合計とカウントを持ちます。ローカル集約結果は最終的にグループ状態マージオペレーターによってグローバル集約結果にマージされます。このオペレーターはパイプラインブレイカーでもあり、集約結果が完全に計算されるまで、第3ステージを開始できません。第3ステージでは、結果グループが最初に再分配交換オペレーターによって3つの等しい大きさの重複しないパーティションに分割され、次にAvgLatencyでソートされます。ソートは3ステップで実行されます。最初に、ChunkSortオペレーターが各パーティションの個々のチャンクをソートします。次に、StreamSortオペレーターがローカルソート結果を維持し、2ウェイマージソートを使用して、到着するソートチャンクと組み合わされます。最後に、MergeSortオペレーターがk-wayソートを使用してローカル結果を組み合わせ、最終結果を得ます。

オペレーターは状態機械であり、入力および出力ポートを介して互いに接続されています。オペレーターの3つの可能な状態は、need-chunk、ready、およびdoneです。need-chunkからreadyに移行するには、チャンクがオペレーターの入力ポートに置かれます。readyからdoneに移行するには、オペレーターが入力チャンクを処理し、出力チャンクを生成します。doneからneed-chunkに移行するには、出力チャンクがオペレーターの出力ポートから削除されます。2つの接続されたオペレーターでは、最初の状態遷移と第三の状態遷移は、結合されたステップでのみ実行可能です。ソースオペレーター(シンクオペレーター)は、readyおよびdone(need-chunkおよびdone)の状態のみを持ちます。

ワーカースレッドは、物理オペレーター計画を継続的に巡回し、状態遷移を実行します。CPUキャッシュを活性に保つために、計画には同じスレッドが同じレーンで連続するオペレーターを処理すべきというヒントが含まれています。並列処理は、ステージ内の重複しない入力を通じて水平方向に(例えば、 [図 8](#page-7-1) でAggregateオペレーターが並行して実行される)実行されるだけでなく、パイプラインブレイカーで分離されていないステージ間で垂直に実行されます(例えば、 [図 8](#page-7-1) で同じレーンのフィルターおよび集約オペレーターは同時に実行できます)。新しいクエリが開始する際や、同時クエリが終了する際に過剰および過少割り当てを避けるために、並列度はクエリ開始時にクエリに指定されたワーカースレッドの最大数と1の間でミッドクエリで変更できます(セクション [4.5)](#page-9-1)。

オペレーターは、次の2つの方法でランタイムのクエリ実行に影響を与えることができます。まず、オペレーターは動的に新しいオペレーターを作成して接続することができます。これは、メモリ消費が設定可能な閾値を超えるとクエリをキャンセルする代わりに、外部集約、ソート、または結合アルゴリズムに切り替えるために主に使用されます。次に、オペレーターはワーカースレッドに非同期キューに移動するように要求できます。これにより、リモートデータを待機する場合にワーカースレッドをより効果的に利用できます。

ClickHouseのクエリ実行エンジンとモーサル駆動の並列処理 [\[44\]](#page-12-20) は、レーンが通常異なるコア/NUMAソケットで実行され、ワーカースレッドが他のレーンからタスクを奪うことができる点で似ています。また、中央スケジューリングコンポーネントは存在せず、代わりにワーカースレッドがオペレーター計画を継続的に調査してタスクを個々に選択します。モーサル駆動の並列処理とは異なり、ClickHouseは最大の並列度を計画に埋め込み、デフォルトのモーサルサイズ約100,000行と比較して、ソーステーブルを分割するためにはるかに大きな範囲を使用します。これはある場合にはスタールを引き起こす可能性があります(例えば、異なるレーンのフィルターオペレーターのランタイムが大幅に異なる場合)が、再分配などの交換オペレーターを自由に使用することで、少なくともステージ間でその不均衡が蓄積されるのを防ぎます。

### 4.3 マルチノード並列化 \{#4-3-multi-node-parallelization}

クエリのソーステーブルがシャーディングされている場合、クエリを受け取ったノード(イニシエータノード)上のクエリオプティマイザーは、他のノードで可能な限り多くの作業を行おうとします。異なるノードからの結果は、クエリ計画の異なるポイントに統合できます。クエリに応じて、リモートノードは1. 生のソーステーブルのカラムをイニシエータノードにストリーミングする、2. ソースカラムをフィルタリングして生き残った行を送信する、3. フィルタリングおよび集約ステップを実行し、部分集約状態を持つローカル結果グループを送信する、または4. フィルタリング、集約、ソートを含むクエリ全体を実行します。

[図 8](#page-7-1) のノード2からNは、ヒットテーブルのシャードを保持する他のノード上で実行される計画の断片を示しています。これらのノードはローカルデータをフィルタリングおよびグループ化し、結果をイニシエータノードに送信します。ノード1のグループ状態マージオペレーターは、ローカルおよびリモートの結果をマージします。その後、結果グループは最終的にソートされます。

### <Anchor id="page-7-0"/>4.4 全体的パフォーマンス最適化 \{#4-4-holistic-performance-optimization}

このセクションでは、クエリ実行のさまざまな段階に適用される主要なパフォーマンス最適化をいくつか示します。

**クエリ最適化**。最初の一連の最適化は、クエリのASTから得られる意味論的クエリ表現の上に適用されます。このような最適化の例には、定数折りたたみ(例えば、concat(lower('a'),upper('b'))は'aB'になります)、特定の集約関数からスカラーを抽出すること(例えば、sum(a*2)は2 * sum(a)になります)、共通部分式の排除、そして等式フィルターの論理和をINリストに変換すること(例えば、x=c OR x=dはx IN (c,d)になります)。最適化された意味論的クエリ表現は、その後、論理オペレーター計画に変換されます。論理計画上での最適化には、フィルタープッシュダウン、関数評価とソートステップの順序付けが含まれます。どちらが高コストと見積もられるかによります。最後に、論理クエリ計画は物理オペレーター計画に変換されます。この変換は、関与するテーブルエンジンの特性を利用できます。たとえば、MergeTreeテーブルエンジンの場合、ORDER BYカラムが主キーのプレフィックスを形成していれば、データはディスク順に読み取られ、ソートオペレーターは計画から削除できます。また、集約におけるグループ化カラムが主キーのプレフィックスを形成している場合、ClickHouseはソート集約を使用し、つまりプリソートされたインプット内の同じ値の集約ランを直接集約します。ハッシュ集約と比較して、ソート集約はメモリ集約が大幅に少なく、集約値はランが処理された後に次のオペレーターに即座に渡すことができます。

**クエリコンパイル**。ClickHouseは、 [LLVMに基づくクエリコンパイル](https://clickhou.se/jit) を利用して、隣接する計画オペレーターを動的に融合します [\[38,](#page-12-22) [53\]](#page-13-0)。たとえば、式a * b + c + 1は、3つのオペレーターの代わりに単一のオペレーターにまとめることができます。表現に加えて、ClickHouseは同時に複数の集約関数を評価(つまり、GROUP BYの場合)し、1つ以上のソートキーでソートします。クエリコンパイルは、仮想呼び出しの数を減らし、データをレジスタまたはCPUキャッシュに保持し、実行が必要なコードを減らすことで分岐予測器を助けます。さらに、ランタイムコンパイルにより、論理的な最適化やコンパイラで実装された隙間最適化など、豊富な最適化のセットが可能となり、利用可能な最も高速なCPU命令にアクセスできます。コンパイルは、同じ通常の、集約、またはソート表現が異なるクエリによって、設定可能な回数以上に実行されるときのみ開始されます。コンパイルされたクエリオペレーターはキャッシュされ、今後のクエリで再利用できます。[7]

**主キーインデックスの評価**。ClickHouseは、WHERE条件内のフィルタ句の一部が主キー列のプレフィックスを構成する場合、主キーインデックスを使用して条件を評価します。主キーインデックスは、辞書順にソートされたキー値の範囲に対して左から右へと分析されます。主キー列に対応するフィルタ句は、三値論理を用いて評価されます - すべて真、すべて偽、または範囲内の値に対して真/偽が混在します。後者の場合、範囲は再帰的に分析されるサブ範囲に分割されます。フィルタ条件の関数に対しては追加の最適化が存在します。まず、関数には単調性を説明する特性があり、たとえば、toDayOfMonth(date)は月内で部分的に単調です。単調性特性により、関数がソートされた入力キー値範囲でソートされた結果を生成するかどうかを推測できます。次に、特定の関数結果の前像を計算できる機能がある関数もあります。これは、主キー列の関数呼び出しで定数の比較を前像との比較に置き換えるために使用されます。例えば、toYear(k) = 2024はk >= 2024-01-01 && k < 2025-01-01に置き換えることができます。

**データスキッピング**。ClickHouseは、セクション [3.2.](#page-3-0) で示されたデータ構造を使用して、クエリランタイム中にデータの読み取りを避けようとします。さらに、異なるカラムに対するフィルターは、推定選択性の降順の順序で逐次評価されます。少なくとも1つの一致する行を含むデータチャンクのみが次の述語に渡されます。これにより、逐次的に読み取るデータの量と各述語で行う計算の数が減少します。この最適化は、少なくとも1つの非常に選択的な述語が存在する場合にのみ適用されます。そうでなければ、並行してすべての述語を評価した場合と比較してクエリのレイテンシが悪化します。

**ハッシュテーブル**。ハッシュテーブルは、集約やハッシュジョインのための基本的なデータ構造です。最適なハッシュテーブルのタイプを選択することは、パフォーマンスにとって重要です。ClickHouseは、ハッシュ関数、アロケータ、セルタイプ、およびリサイズポリシーをバリエーションポイントとして持つ一般的なハッシュテーブルテンプレートから、さまざまなハッシュテーブルを[インスタンス化](https://clickhou.se/hashtables)します(2024年3月の時点で30以上)。グループ化カラムのデータ型、推定されるハッシュテーブルのカーディナリティ、その他の要因に基づいて、各クエリオペレーターに対して最速のハッシュテーブルが個別に選択されます。ハッシュテーブルに対して実装される追加の最適化には以下が含まれます。

- 256のサブテーブルを持つ2レベルのレイアウト(ハッシュの最初のバイトに基づいて)を使用して、大きなキーセットをサポートします。
- 異なる文字列の長さには異なるハッシュ関数を使用した4つのサブテーブルを持つ文字列ハッシュテーブル [\[79\]](#page-13-20)。
- キーが少数である場合、バケットインデックスとしてキーを直接使用するルックアップテーブル(つまり、ハッシュ化なし)。
- 比較が高コスト(例えば、文字列、AST)である場合に衝突解決を速めるための埋め込まれたハッシュを持つ値。
- 不必要なリサイズを回避するために、ランタイム統計から予測されたサイズに基づいてハッシュテーブルを作成します。
- 単一のメモリスラブで同じ作成/破壊ライフサイクルを持つ複数の小さなハッシュテーブルを割り当てます。
- ハッシュマップごとのおよびセルごとのバージョンカウンターを使用して、再利用のためにハッシュテーブルを瞬時にクリアします。
- ハッシュキーの取得を速めるために、CPUのプリフェッチ(__builtin_prefetch)を使用します。

**ジョイン**。ClickHouseはもともとジョインを基本的にサポートしていたため、多くの使用ケースは歴史的に非正規化テーブルに依存していました。今日、データベースはSQLで利用可能なすべてのジョインタイプ(内部、左/右/完全外部、交差、時点)を提供し、またハッシュジョイン(ナイーブ、グレース)、ソートマージジョイン、迅速なキー値ルックアップを持つテーブルエンジン向けのインデックスジョインなど、さまざまなジョインアルゴリズムを提供します。

ジョインはデータベース操作の中で最もコストがかかるため、古典的なジョインアルゴリズムの並列版を提供することが重要であり、理想的には設定可能な空間/時間トレードオフを備えています。ハッシュジョインに関しては、ClickHouseは非ブロッキングの共有パーティションアルゴリズムを実装します [\[7\]](#page-12-23)。例えば、[図 9](#page-8-3) のクエリは、ページヒット統計テーブルに対して自己ジョインを行い、ユーザーがURL間を移動する方法を計算します。ジョインのビルドフェーズは、ソーステーブルの3つの重複しないレンジをカバーする3つのレーンに分割されます。グローバルハッシュテーブルの代わりに、パーティションされたハッシュテーブルが使用されます。(通常3つの)ワーカースレッドは、ハッシュ関数のモジュロを計算することによってビルドサイドの各入力行のターゲットパーティションを決定します。ハッシュテーブルパーティションへのアクセスは、Gather交換オペレーターを使用して同期されます。プローブフェーズは、同様に入力タプルのターゲットパーティションを見つけます。このアルゴリズムは、各タプルあたり2つの追加のハッシュ計算を導入しますが、ビルドフェーズにおけるロック競合を大幅に減少させます。これはハッシュテーブルのパーティションの数によって左右されます。

<Anchor id="page-8-3"/><Image img={image_09} size="lg" alt="Image 09"/>

図 9: 3つのハッシュテーブルパーティションを持つ並列ハッシュジョイン。

### <Anchor id="page-9-1"/>4.5 ワークロードの分離 \{#4-5-workload-isolation}

ClickHouseは同時制御、メモリ使用の制限、およびI/Oスケジューリングを提供し、ユーザーがクエリをワークロードクラスに分離できるようにします。特定のワークロードクラスに対して共有リソース(CPUコア、DRAM、ディスクおよびネットワークI/O)に制限を設けることによって、これらのクエリが他の重要なビジネスクエリに影響を与えないようにします。

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

ClickHouseは、サーバーレベル、ユーザーレベル、およびクエリレベルでメモリ割り当てのバイトサイズを追跡し、柔軟なメモリ使用制限を設定できるようにしています。メモリオーバーコミットにより、クエリは保証されたメモリを超えて追加の空きメモリを使用でき、他のクエリのメモリ制限を保証します。さらに、集約、ソート、およびジョイン句に対するメモリ使用を制限でき、メモリ制限を超えた場合には外部アルゴリズムへのフォールバックが発生します。

最後に、I/Oスケジューリングを使用することで、ユーザーは最大帯域幅、途中リクエスト、およびポリシー(例:FIFO、SFC [\[32\]](#page-12-24))に基づいてワークロードクラスのローカルおよびリモートディスクアクセスを制限することができます。

### <Anchor id="page-9-0"/>5 統合レイヤー \{#5-integration-layer}

リアルタイムの意思決定アプリケーションは、複数の場所にあるデータへの効率的で低レイテンシのアクセスに依存することがよくあります。外部データをOLAPデータベースで利用可能にするための2つのアプローチが存在します。プッシュベースのデータアクセスでは、サードパーティコンポーネントがデータベースと外部データストアを橋渡しします。これに典型的な例が、リモートデータを宛先システムにプッシュするための特化した抽出変換ロード(ETL)ツールです。一方、プルベースモデルでは、データベース自体がリモートデータソースに接続して、データをローカルテーブルにクエリするために引き込むか、リモートシステムにデータをエクスポートします。プッシュベースのアプローチは、より柔軟で一般的ですが、アーキテクチャが大きく、スケーラビリティのボトルネックを伴います。それに対して、データベース内のリモート接続は、ローカルデータとリモートデータ間のジョインなど、興味深い機能を提供しながら、全体のアーキテクチャをシンプルに保ち、洞察までの時間を短縮します。

このセクションの残りでは、ClickHouseにおけるプルベースのデータ統合方法を探求し、リモートロケーションのデータへのアクセスを目的としています。SQLデータベースにおけるリモート接続の考え方は新しくはありません。たとえば、SQL/MED標準 [\[35\]](#page-12-25) は、2001年に導入され、2011年からPostgreSQLによって実装されているもので、外部データを管理するための統一インターフェースとして外部データラッパーを提案しています。ClickHouseの設計目標の1つは、他のデータストアやストレージフォーマットとの最大相互運用性を確保することです。2024年3月の時点で、ClickHouseは、すべての分析データベースにおいて最も多くの組み込みデータ統合オプションを提供していると私たちの知る限りです。

外部接続。ClickHouseは、ODBC、MySQL、PostgreSQL、SQLite、Kafka、Hive、MongoDB、Redis、S3/GCP/Azureオブジェクトストア、およびさまざまなデータレイクを含む外部システムおよびストレージロケーションとの接続のために[50以上](https://clickhou.se/query-integrations)の統合テーブル関数およびエンジンを提供しています。これらをさらに以下に示すボーナス図で分類します(元のvldb論文の一部ではありません)。

<Anchor id="bonus-figure"/><Image img={image_10} size="lg" alt="Image 10"/>

ボーナス図: ClickBenchの相互運用性オプション。

統合**テーブル関数**による一時的なアクセス。テーブル関数は、SELECTクエリのFROM句で呼び出されてリモートデータを読み取るための探索的なアドホッククエリに使用できます。あるいは、INSERT INTO TABLE FUNCTIONステートメントを使用してリモートストアにデータを書き込むために使用することもできます。

永続的なアクセス。リモートデータストアおよび処理システムと永続的な接続を作成するためには3つの方法が存在します。

まず、統合**テーブルエンジン**は、MySQLテーブルなどのリモートデータソースを永続的なローカルテーブルとして表現します。ユーザーは、CREATE TABLE AS構文を使用してテーブル定義を保存し、SELECTクエリとテーブル関数を組み合わせます。リモートカラムのサブセットのみを参照するためにカスタムスキーマを指定するか、スキーマ推論を使用してカラム名と同等のClickHouse型を自動的に決定することが可能です。受動的および能動的な実行時動作を区別します:受動的テーブルエンジンは、クエリをリモートシステムに転送し、結果をローカルプロキシテーブルに入力します。それに対して、能動的テーブルエンジンは、リモートシステムから定期的にデータをプルしたり、またはリモート変更にサブスクライブしたりします。たとえば、PostgreSQLの論理レプリケーションプロトコルを介して。結果として、ローカルテーブルにはリモートテーブルの完全なコピーが含まれます。

第二に、統合**データベースエンジン**は、リモートデータストア内のテーブルスキーマのすべてのテーブルをClickHouseにマッピングします。前者とは異なり、一般にリモートデータストアをリレーショナルデータベースであることを要求し、DDLステートメントに対する制限されたサポートを提供します。

第三に、**辞書**は、対応する統合テーブル関数またはエンジンに対してほぼすべてのデータソースに対する任意のクエリを使用して生成できます。ランタイム動作は能動的であり、リモートストレージからデータが一定の間隔で引き込まれます。

データフォーマット。サードパーティシステムと対話するために、最新の分析データベースはまた、あらゆるフォーマットでデータを処理できる必要があります。ClickHouseは、そのネイティブフォーマットに加えて、[90以上](https://clickhou.se/query-formats) のフォーマットをサポートしており、CSV、JSON、Parquet、Avro、ORC、Arrow、およびProtobufが含まれています。各フォーマットは、ClickHouseが読める入力フォーマット(つまり、入力フォーマット)、ClickHouseがエクスポートする出力フォーマット(出力フォーマット)、またはその両方に適用される場合があります。Parquetのような一部の分析指向のフォーマットは、クエリ処理と統合されており、つまり、オプティマイザーが埋め込まれた統計を利用し、フィルターが圧縮データ上で直接評価されます。

互換性インターフェース。ネイティブバイナリワイヤプロトコルとHTTPに加えて、クライアントはMySQLまたはPostgreSQLワイヤプロトコル互換インターフェースを介してClickHouseと対話できます。この互換性機能は、ベンダーがまだネイティブなClickHouse接続を実装していない専有アプリケーション(例えば、一部のビジネスインテリジェンスツール)からのアクセスを可能にするために便利です。

## 6 パフォーマンスを特徴として \{#6-performance-as-a-feature}

このセクションでは、パフォーマンス分析のための組み込みツールを紹介し、実世界のクエリとベンチマーククエリを使用してパフォーマンスを評価します。

### 6.1 組み込みパフォーマンス分析ツール \{#6-1-built-in-performance-analysis-tools}

個々のクエリやバックグラウンド操作のパフォーマンスボトルネックを調査するために利用できるさまざまなツールがあります。ユーザーは、システムテーブルに基づいた統一インターフェースを通してすべてのツールに対話します。

**サーバーおよびクエリメトリック**。アクティブパートの数、ネットワークスループット、キャッシュヒット率などのサーバーレベルの統計は、読み取られたブロック数やインデックス使用状況統計などのクエリごとの統計によって補完されます。メトリックは、同期的に(リクエスト時)または非同期的に設定可能な間隔で計算されます。

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

**OpenTelemetry統合**。OpenTelemetryは、複数のデータ処理システム間でデータ行をトレースするためのオープンスタンダードです [\[8\]](#page-12-26)。ClickHouseは、すべてのクエリ処理ステップに対して設定可能なグラニュラリティでOpenTelemetryログスパンを生成し、他のシステムからOpenTelemetryログスパンを収集および分析できます。

**クエリ説明**。他のデータベースと同様に、SELECTクエリの前にEXPLAINを付け加えることで、クエリのAST、論理および物理オペレータープラン、実行時の動作に関する詳細な洞察を得ることができます。

### 6.2 ベンチマーク \{#6-2-benchmarks}

ベンチマークは現実的でないとして批判されてきましたが [\[10,](#page-12-27) [52,](#page-13-22) [66,](#page-13-23) [74\]](#page-13-24)、それでもデータベースの強みと弱みを識別するために便利です。以下では、ClickHouseのパフォーマンスを評価するためにベンチマークがどのように使用されているかについて説明します。
#### 6.2.1 非正規化テーブル \{#6-2-1-denormalized-tables}

非正規化ファクトテーブルに対するフィルタリングおよび集約クエリは、これまでのところ ClickHouse の主要な使用ケースを表しています。私たちは、クリックストリームやトラフィック分析で使用されるアドホックおよび定期的なレポートクエリをシミュレートする、この種の典型的なワークロードである ClickBench の実行時間を報告します。このベンチマークは、世界最大の分析プラットフォームの一つから取得した、1 億の匿名化されたページヒットを含むテーブルに対する 43 のクエリで構成されています。オンラインダッシュボード [\[17\]](#page-12-28) は、2024 年 6 月時点で 45 以上の商業および研究データベースの測定値 (コールド/ホット実行時間、データインポート時間、ディスクサイズ) を示しています。結果は、公開されているデータセットとクエリに基づいて独立した寄稿者によって提出されました [\[16\]](#page-12-29)。これらのクエリは、順次およびインデックススキャンのアクセスパスをテストし、常に CPU、IO、またはメモリ制約のあるリレーショナルオペレーターを露呈します。

[図 10](#page-10-0) は、分析に頻繁に使用されるデータベースで全 ClickBench クエリを順次実行した際の、コールドおよびホット実行時間の合計相対値を示しています。測定は、16 vCPU、32 GB RAM、5000 IOPS / 1000 MiB/s ディスクを持つ単一ノードの AWS EC2 c6a.4xlarge インスタンスで行われました。同様のシステムが Redshift ([ra3.4xlarge](https://clickhou.se/redshift-sizes)、12 vCPU、96 GB RAM) および Snowfake ([ウェアハウスサイズ S](https://clickhou.se/snowflake-sizes): 2x8 vCPU、2x16 GB RAM) に使用されました。物理データベース設計は軽く調整されており、たとえば、主キーを指定しますが、個々のカラムの圧縮を変更したり、プロジェクションやスキッピングインデックスを作成したりはしません。また、各コールドクエリ実行前に Linux ページキャッシュをフラッシュしていますが、データベースやオペレーティングシステムの設定は調整しません。各クエリについて、データベース間で最速の実行時間が基準として使用されます。他のデータベースの相対クエリ実行時間は ( + 10)/(_ + 10) として計算されます。データベースの総相対実行時間は、各クエリの比率の幾何平均です。研究データベース Umbra [\[54\]](#page-13-25) が全体でのホット実行時間で最高の成果を上げていますが、ClickHouse はホットおよびコールド実行時間で他のすべての商用データベースを上回ります。

<Anchor id="page-10-0"/><Image img={image_11} size="lg" alt="Image 11"/>

図 10: ClickBench の相対コールドおよびホット実行時間。

SELECT のパフォーマンスをより多様なワークロードで時間をかけて追跡するために、私たちは [使用](https://clickhou.se/performance-over-years) バージョンベンチと呼ばれる 4 つのベンチマークの組み合わせを利用しています [\[19\]](#page-12-30)。このベンチマークは、新しいリリースが公開されるたびに毎月 1 回実行され、そのパフォーマンス [\[20\]](#page-12-31) を評価し、パフォーマンスを劣化させる可能性のあるコード変更を特定します。個々のベンチマークには次のものが含まれます: 1. ClickBench (上記で説明)、2. 15 MgBench [\[21\]](#page-12-32) クエリ、3. 6 億行の非正規化スタースキーマベンチマーク [\[57\]](#page-13-26) ファクトテーブルに対する 13 のクエリ。4. 34 億行の [NYC Taxi Rides](https://clickhou.se/nyc-taxi-rides-benchmark) に対する 4 クエリ [\[70\]](#page-13-27)。

[図 11](#page-10-5) は、2018 年 3 月から 2024 年 3 月までの 77 の ClickHouse バージョンに対する VersionsBench 実行時間の推移を示しています。個々のクエリの相対実行時間の違いを補正するために、全バージョンの中での最小クエリ実行時間に対する比率を重みとして、幾何平均を用いて実行時間を正規化します。VersionBench のパフォーマンスは過去 6 年間で 1.72 倍向上しました。長期サポート (LTS) リリースの日付は x 軸に示されています。いくつかの期間に一時的にパフォーマンスが低下しましたが、LTS リリースは一般的に以前の LTS バージョンと同等かそれ以上のパフォーマンスを有しています。2022 年 8 月の大幅な改善は、セクション [4.4.](#page-7-0) で説明されているカラムごとのフィルタ評価手法によってもたらされました。

<Anchor id="page-10-5"/><Image img={image_12} size="lg" alt="Image 12"/>

図 11: VersionsBench 2018-2024 の相対ホット実行時間。
#### 6.2.2 正規化テーブル \{#6-2-2-normalized-tables}

従来のデータウェアハウジングでは、データはしばしばスタースキーマやスノーフレークスキーマを使用してモデリングされます。TPC-H クエリ (スケールファクター 100) の実行時間を示しますが、正規化テーブルは ClickHouse にとって新たな使い方であることを指摘します。 [図 12](#page-10-6) は、セクション [4.4.](#page-7-0) で説明された並列ハッシュ結合アルゴリズムに基づく TPC-H クエリのホット実行時間を示しています。測定は、64 vCPU、128 GB RAM、5000 IOPS / 1000 MiB/s ディスクを持つ単一ノードの AWS EC2 c6i.16xlarge インスタンスで行われました。5 回の実行の中で最速のものが記録されました。参考のため、同じ測定を同等のサイズの Snowfake システム (ウェアハウスサイズ L、8x8 vCPU、8x16 GB RAM) でも行いました。11 クエリの結果はテーブルから除外されています: クエリ Q2、Q4、Q13、Q17、および Q20-22 には、ClickHouse v24.6 ではサポートされていない相関サブクエリが含まれています。クエリ Q7-Q9 および Q19 は、実行可能な実行時間を達成するために、結合のための拡張プランレベルの最適化に依存しています (ClickHouse v24.6 現在はこれらが欠けています)。自動サブクエリ非相関化と結合に対するより良いオプティマイザーサポートは、2024 年に実装される予定です [\[18\]](#page-12-33)。残りの 11 クエリのうち、ClickHouse で 5 (6) クエリが Snowfake よりも早く実行されました。前述の最適化はパフォーマンスにとって重要であることが知られているため [\[27\]](#page-12-34)、実装後にはこれらのクエリの実行時間がさらに改善されることが期待されます。

<Anchor id="page-10-6"/><Image img={image_13} size="lg" alt="Image 13"/>

図 12: TPC-H クエリのホット実行時間 (秒単位)。
## 7 関連研究 \{#7-related-work}

分析用データベースは、近年の学術および商業的な関心を集めています [\[1\]](#page-12-35)。初期のシステム、Sybase IQ [\[48\]](#page-13-28)、Teradata [\[72\]](#page-13-29)、Vertica [\[42\]](#page-12-36)、および Greenplum [\[47\]](#page-13-30) は、オンプレミスの性質により、コストのかかるバッチ ETL ジョブと限られた弾力性が特徴でした。2010 年代初頭、クラウドネイティブなデータウェアハウスやデータベース-as-a-Service (DBaaS) の登場により、Snowfake [\[22\]](#page-12-37)、BigQuery [\[49\]](#page-13-31)、および Redshift [\[4\]](#page-12-38) などによって、組織にとっての分析のコストと複雑さが劇的に削減され、高可用性と自動リソーススケーリングの恩恵を受けました。最近では、分析実行カーネル (例: Photon [\[5\]](#page-12-39) と Velox [\[62\]](#page-13-32)) が、さまざまな分析、ストリーミング、機械学習アプリケーションでの使用のために共同修正されたデータ処理を提供します。

ClickHouse の目標および設計原則に最も似ているデータベースは、Druid [\[78\]](#page-13-33) および Pinot [\[34\]](#page-12-40) です。これらのシステムは、高いデータ取り込み率でリアルタイム分析をターゲットとしています。ClickHouse のように、テーブルはセグメントと呼ばれる水平パーツに分割されます。ClickHouse は小さなパーツを定期的にマージし、オプションでデータボリュームを削減する技術を使用していますが、Druid と Pinot ではパーツは永遠に不変です。また、Druid と Pinot では、テーブルを作成、変更、および検索するために専門的なノードが必要ですが、ClickHouse ではこれらのタスクにモノリシックバイナリを使用します。

Snowfake [\[22\]](#page-12-37) は、共有ディスクアーキテクチャに基づく人気のある商用クラウドデータウェアハウスです。テーブルをマイクロパーテーションに分割するアプローチは、ClickHouse のパーツの概念に似ています。Snowfake は永続化のためにハイブリッド PAX ページ [\[3\]](#page-12-41) を使用しますが、ClickHouse のストレージ形式は厳密に列指向です。Snowfake では、ローカルキャッシュや自動的に作成された軽量インデックスを使用してデータのプルーニングを強調しており、良好なパフォーマンスのための源となっています [\[31,](#page-12-13) [51\]](#page-13-14)。ClickHouse の主キーに類似して、ユーザーは同じ値を持つデータを共置するためにクラスタードインデックスをオプションで作成できます。

Photon [\[5\]](#page-12-39) および Velox [\[62\]](#page-13-32) は、複雑なデータ管理システムのコンポーネントとして使用するために設計されたクエリ実行エンジンです。両システムはクエリプランを入力として受け取り、その後、ローカルノードで Parquet (Photon) または Arrow (Velox) ファイル上で実行されます [\[46\]](#page-13-34)。ClickHouse はこれらの一般的な形式でのデータの消費と生成が可能ですが、ストレージにはネイティブファイル形式を好みます。Velox と Photon はクエリプランを最適化しません (Velox は基本的な式の最適化を実行します)。しかし、データ特性に応じて動的に計算カーネルを切り替えるなどの実行時適応技術を利用しています。同様に、ClickHouse のプランオペレーターは実行時に外部の集約や結合オペレーターに切り替えるために他のオペレーターを作成することができます、主にクエリのメモリ消費量に基づいています。Photon 論文では、コード生成デザインは [\[38,](#page-12-22) [41,](#page-12-42) [53\]](#page-13-0) 解釈型ベクトルデザイン [\[11\]](#page-12-0) よりも開発とデバッグが難しいことが指摘されています。Velox におけるコード生成のサポートは、実行時に生成された C++ コードから作成された共有ライブラリをビルドしてリンクしますが、ClickHouse は LLVM のリクエスト時コンパイル API と直接インタラクションします。

DuckDB [\[67\]](#page-13-6) は、ホストプロセスによって埋め込まれることを目的としていますが、クエリ最適化およびトランザクションも提供します。OLAP クエリと時折の OLTP ステートメントを混ぜるために設計されました。したがって、DuckDB は、ハイブリッドワークロードで良好なパフォーマンスを実現するために、順序を保持する辞書や参照フレームのような軽量圧縮方法を採用する DataBlocks [\[43\]](#page-12-43) ストレージ形式を選択しました。一方、ClickHouse は追加のみのユースケース、すなわち、更新および削除がないか稀であることに最適化されています。ブロックは LZ4 のような重い圧縮手法を使用して圧縮されます。ユーザーがデータプルーニングを積極的に使用して頻繁にクエリを高速化し、I/O コストが残りのクエリの解凍コストを上回るという前提で行われます。DuckDB はまた、Hyper の MVCC スキーム [\[55\]](#page-13-35) に基づいた直列化可能なトランザクションを提供しますが、ClickHouse はスナップショット隔離のみを提供します。
## 8 結論と展望 \{#8-conclusion-and-outlook}

私たちは、オープンソースで高性能な OLAP データベースである ClickHouse のアーキテクチャを提示しました。書き込み最適化ストレージ層と最先端のベクトル化クエリエンジンを基盤に、ClickHouse はペタバイト規模のデータセットに対するリアルタイム分析を高い取り込み率で可能にします。データをバックグラウンドで非同期にマージおよび変換することで、ClickHouse はデータメンテナンスと並列挿入を効率的に分離します。そのストレージ層は、スパース主インデックス、スキッピングインデックス、プロジェクションテーブルを使用して攻撃的なデータプルーニングを可能にします。ClickHouse の更新と削除、冪等な挿入、そして高可用性のためのノード間のデータレプリケーションの実装を説明しました。クエリ処理層は豊富な技術を使用してクエリを最適化し、すべてのサーバーおよびクラスタリソースにわたって実行を並列化します。統合テーブルエンジンおよび関数は、他のデータ管理システムおよびデータ形式とシームレスに相互作用する便利な方法を提供します。ベンチマークを通じて、ClickHouse は市場で最も高速な分析データベースの一つであることを示し、ClickHouse の実世界のデプロイメントにおける典型的なクエリのパフォーマンスにおける重要な改善を示しました。

2024 年のために計画されているすべての機能と改善は、公開ロードマップ [\[18\]](#page-12-33) に記載されています。計画されている改善には、ユーザートランザクションのサポート、PromQL [\[69\]](#page-13-36) を代替クエリ言語としての実装、半構造化データ (例: JSON) 用の新しいデータ型、結合のプランレベルでの最適化の改善、および軽量削除を補完するための軽量更新の実装が含まれます。
## 感謝の意 \{#acknowledgements}

バージョン 24.6 に従い、SELECT * FROM system.contributors は ClickHouse に貢献した 1994 人の個人を返します。私たちは、ClickHouse Inc. のエンジニアリングチーム全員と、共にこのデータベースを構築するために努めた素晴らしいオープンソースコミュニティに感謝します。
## REFERENCES \{#references}

- <Anchor id="page-12-35"/>[1] Daniel Abadi, Peter Boncz, Stavros Harizopoulos, Stratos Idreaos, and Samuel Madden. 2013. 現代の列指向データベースシステムの設計と実装. https://doi.org/10.1561/9781601987556
- <Anchor id="page-12-10"/>[2] Daniel Abadi, Samuel Madden, and Miguel Ferreira. 2006. 列指向データベースシステムにおける圧縮と実行の統合. In Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data (SIGMOD '06). 671–682.https://doi.org/10.1145/1142473.1142548
- <Anchor id="page-12-41"/>[3] Anastassia Ailamaki, David J. DeWitt, Mark D. Hill, and Marios Skounakis. 2001. キャッシュパフォーマンスのための関係の織り交ぜ. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB '01). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 169–180.
- <Anchor id="page-12-38"/>[4] 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 の再発明. 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
- <Anchor id="page-12-39"/>[5] 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: Lakehouse システムのための高速クエリエンジン (SIGMOD '22). Association for Computing Machinery, New York, NY, USA, 2326–2339. [https://doi.org/10.1145/3514221.](https://doi.org/10.1145/3514221.3526054) [3526054](https://doi.org/10.1145/3514221.3526054)
- <Anchor id="page-12-18"/>[6] Philip A. Bernstein and Nathan Goodman. 1981. 分散データベースシステムにおける同時実行制御. ACM Computing Survey 13, 2 (1981), 185–221. https://doi.org/10.1145/356842.356846
- <Anchor id="page-12-23"/>[7] Spyros Blanas, Yinan Li, and Jignesh M. Patel. 2011. マルチコアCPU向けのメインメモリハッシュ結合アルゴリズムの設計と評価. In 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
- <Anchor id="page-12-26"/><Anchor id="page-12-14"/>[8] Daniel Gomez Blanco. 2023. 実用的なOpenTelemetry. Springer Nature.
- [9] Burton H. Bloom. 1970. ハッシュコーディングにおける空間/時間トレードオフ. Commun. ACM 13, 7 (1970), 422–426. [https://doi.org/10.1145/362686.](https://doi.org/10.1145/362686.362692) [362692](https://doi.org/10.1145/362686.362692)
- <Anchor id="page-12-27"/>[10] Peter Boncz, Thomas Neumann, and Orri Erling. 2014. TPC-H 分析: 影響力のあるベンチマークから得られた隠れたメッセージと教訓. In Performance Characterization and Benchmarking. 61–76. [https://doi.org/10.1007/978-3-319-](https://doi.org/10.1007/978-3-319-04936-6_5) [04936-6_5](https://doi.org/10.1007/978-3-319-04936-6_5)
- <Anchor id="page-12-0"/>[11] Peter Boncz, Marcin Zukowski, and Niels Nes. 2005. MonetDB/X100: ハイパーパイプラインクエリ実行. In CIDR.
- <Anchor id="page-12-8"/>[12] Martin Burtscher and Paruj Ratanaworabhan. 2007. ダブルプレシジョン浮動小数点データの高スループット圧縮. In Data Compression Conference (DCC). 293–302. https://doi.org/10.1109/DCC.2007.44
- <Anchor id="page-12-6"/>[13] Jef Carpenter and Eben Hewitt. 2016. Cassandra: Definitive Guide (第2版). O'Reilly Media, Inc.
- <Anchor id="page-12-17"/>[14] Bernadette Charron-Bost, Fernando Pedone, and André Schiper (編). 2010. レプリケーション: 理論と実践. Springer-Verlag.
- <Anchor id="page-12-3"/>[15] chDB. 2024. chDB - 埋め込みOLAP SQLエンジン. 2024-06-20に取得。 https://github.com/chdb-io/chdb
- <Anchor id="page-12-29"/>[16] ClickHouse. 2024. ClickBench: 分析データベースのベンチマーク. 2024-06-20に取得。 https://github.com/ClickHouse/ClickBench
- <Anchor id="page-12-28"/>[17] ClickHouse. 2024. ClickBench: 比較測定. 2024-06-20に取得。 https://benchmark.clickhouse.com
- <Anchor id="page-12-33"/>[18] ClickHouse. 2024. ClickHouse ロードマップ 2024 (GitHub). 2024-06-20に取得。 https://github.com/ClickHouse/ClickHouse/issues/58392
- <Anchor id="page-12-30"/>[19] ClickHouse. 2024. ClickHouse バージョン ベンチマーク. 2024-06-20に取得。 https://github.com/ClickHouse/ClickBench/tree/main/versions
- <Anchor id="page-12-31"/>[20] ClickHouse. 2024. ClickHouse バージョン ベンチマーク結果. 2024-06-20に取得。 https://benchmark.clickhouse.com/versions/
- <Anchor id="page-12-32"/>[21] Andrew Crotty. 2022. MgBench. 2024-06-20に取得。 [https://github.com/](https://github.com/andrewcrotty/mgbench) [andrewcrotty/mgbench](https://github.com/andrewcrotty/mgbench)
- <Anchor id="page-12-37"/>[22] 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. Snowflake 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:](https://doi.org/10.1145/2882903.2903741) [//doi.org/10.1145/2882903.2903741](https://doi.org/10.1145/2882903.2903741)
- <Anchor id="page-12-9"/>[23] Patrick Damme, Annett Ungethüm, Juliana Hildebrandt, Dirk Habich, and Wolfgang Lehner. 2019. 包括された実験調査から軽量整数圧縮アルゴリズムのコストベースの選択戦略へ. ACM Trans. Database Syst. 44, 3, Article 9 (2019), 46ページ. https://doi.org/10.1145/3323991
- <Anchor id="page-12-1"/>[24] Philippe Dobbelaere and Kyumars Sheykh Esmaili. 2017. Kafka と RabbitMQ: 2つの産業参照発行/購読実装の比較研究: 産業ペーパー (DEBS '17). Association for Computing Machinery, New York, NY, USA, 227–238. https://doi.org/10.1145/3093742.3093908
- <Anchor id="page-12-19"/>[25] LLVM documentation. 2024. LLVMにおける自動ベクトル化. 2024-06-20に取得。 https://llvm.org/docs/Vectorizers.html
- <Anchor id="page-12-7"/>[26] Siying Dong, Andrew Kryczka, Yanqin Jin, and Michael Stumm. 2021. RocksDB: 大規模アプリケーションにサービスを提供するキー・バリュー ストアの開発優先度の進化. ACM Transactions on Storage 17, 4, Article 26 (2021), 32ページ. https://doi.org/10.1145/3483840
- <Anchor id="page-12-34"/>[27] Markus Dreseler, Martin Boissier, Tilmann Rabl, and Matthias Ufacker. 2020. TPC-H ボトルネックの定量化とその最適化. Proc. VLDB Endow. 13, 8 (2020), 1206–1220. https://doi.org/10.14778/3389133.3389138
- <Anchor id="page-12-12"/>[28] Ted Dunning. 2021. t-digest: 分布の効率的な推定. Software Impacts 7 (2021). https://doi.org/10.1016/j.simpa.2020.100049
- <Anchor id="page-12-16"/>[29] Martin Faust, Martin Boissier, Marvin Keller, David Schwalb, Holger Bischof, Katrin Eisenreich, Franz Färber, and Hasso Plattner. 2016. SAP HANAにおけるハッシュインデックスを用いたフットプリントの削減と一意性の強制. In Database and Expert Systems Applications. 137–151. [https://doi.org/10.1007/978-3-319-44406-](https://doi.org/10.1007/978-3-319-44406-2_11) [2_11](https://doi.org/10.1007/978-3-319-44406-2_11)
- <Anchor id="page-12-11"/>[30] Philippe Flajolet, Eric Fusy, Olivier Gandouet, and Frederic Meunier. 2007. HyperLogLog: ほぼ最適な基数推定アルゴリズムの分析. In AofA: Analysis of Algorithms, Vol. DMTCS Proceedings vol. AH, 2007年アルゴリズム分析会議 (AofA 07). Discrete Mathematics and Theoretical Computer Science, 137–156. https://doi.org/10.46298/dmtcs.3545
- <Anchor id="page-12-13"/>[31] Hector Garcia-Molina, Jefrey D. Ullman, and Jennifer Widom. 2009. データベースシステム - 完全な本 (第2版).
- <Anchor id="page-12-24"/>[32] Pawan Goyal, Harrick M. Vin, and Haichen Chen. 1996. 開始時公平キューイング: 統合サービスパケットスイッチングネットワークのためのスケジューリングアルゴリズム. 26, 4 (1996), 157–168. https://doi.org/10.1145/248157.248171
- <Anchor id="page-12-21"/>[33] Goetz Graefe. 1993. 大規模データベース向けのクエリ評価技術. ACM Comput. Surv. 25, 2 (1993), 73–169. https://doi.org/10.1145/152610.152611
- <Anchor id="page-12-40"/>[34] 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億人のユーザー向けのリアルタイム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
- <Anchor id="page-12-25"/>[35] ISO/IEC 9075-9:2001 2001. 情報技術 - データベース言語 - SQL - 第9部: 外部データの管理 (SQL/MED). 規格. 国際標準化機構.
- <Anchor id="page-12-2"/>[36] Paras Jain, Peter Kraft, Conor Power, Tathagata Das, Ion Stoica, and Matei Zaharia. 2023. Lakehouse ストレージシステムの分析と比較. CIDR.
- <Anchor id="page-12-4"/>[37] Project Jupyter. 2024. Jupyter Notebooks. 2024-06-20に取得。 [https:](https://jupyter.org/) [//jupyter.org/](https://jupyter.org/)
- <Anchor id="page-12-22"/>[38] Timo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo, and Peter Boncz. 2018. コンパイルされたベクトル化クエリについて知りたかったことすべて、しかし尋ねるのが怖かったこと. Proc. VLDB Endow. 11, 13 (sep 2018), 2209–2222. https://doi.org/10.14778/3275366.3284966
- <Anchor id="page-12-15"/>[39] 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
- <Anchor id="page-12-5"/>[40] Donald E. Knuth. 1973. コンピュータプログラミングの技法, Volume III: ソートと検索. Addison-Wesley.
- <Anchor id="page-12-42"/>[41] André Kohn, Viktor Leis, and Thomas Neumann. 2018. コンパイルされたクエリの適応実行. In 2018 IEEE 34th International Conference on Data Engineering (ICDE). 197–208. https://doi.org/10.1109/ICDE.2018.00027
- <Anchor id="page-12-36"/>[42] Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan, Nga Tran, Ben Vandiver, Lyric Doshi, and Chuck Bear. 2012. Vertica Analytic Database: C-Store 7年後. Proc. VLDB Endow. 5, 12 (aug 2012), 1790–1801. [https://doi.org/10.](https://doi.org/10.14778/2367502.2367518) [14778/2367502.2367518](https://doi.org/10.14778/2367502.2367518)
- <Anchor id="page-12-43"/>[43] Harald Lang, Tobias Mühlbauer, Florian Funke, Peter A. Boncz, Thomas Neumann, and Alfons Kemper. 2016. データブロック: 圧縮ストレージ上でのハイブリッドOLTPとOLAPの両方を使用したもの. 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, 311–326. https://doi.org/10.1145/2882903.2882925
- <Anchor id="page-12-20"/>[44] Viktor Leis, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2014. モーセル駆動の並列性: 多コア時代のNUMAAware クエリ評価フレームワーク. 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.](https://doi.org/10.1145/2588555.2610507) [2610507](https://doi.org/10.1145/2588555.2610507)
- <Anchor id="page-13-17"/>[45] Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. 適応型ラジックスツリー: メインメモリデータベースのためのARTfulインデクシング. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). 38–49. [https://doi.org/10.1109/ICDE.](https://doi.org/10.1109/ICDE.2013.6544812) [2013.6544812](https://doi.org/10.1109/ICDE.2013.6544812)
- <Anchor id="page-13-34"/>[46] Chunwei Liu, Anna Pavlenko, Matteo Interlandi, and Brandon Haynes. 2023. 分析DBMS用の一般的なオープンフォーマットに関する詳細な考察. 16, 11 (jul 2023), 3044–3056. https://doi.org/10.14778/3611479.3611507
- <Anchor id="page-13-30"/>[47] 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, and Venkatesh Raghavan. 2021. Greenplum: トランザクションと分析のワークロード向けのハイブリッドデータベース (SIGMOD '21). Association for Computing Machinery, New York, NY, USA, 2530–2542. [https:](https://doi.org/10.1145/3448016.3457562) [//doi.org/10.1145/3448016.3457562](https://doi.org/10.1145/3448016.3457562)
- <Anchor id="page-13-28"/>[48] 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.
- <Anchor id="page-13-31"/>[49] 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: ウェブスケールでのインタラクティブなSQL分析の10年間. Proc. VLDB Endow. 13, 12 (aug 2020), 3461–3472. https://doi.org/10.14778/3415478.3415568
- <Anchor id="page-13-2"/>[50] Microsoft. 2024. Kusto Query Language. 2024-06-20に取得。 [https:](https://github.com/microsoft/Kusto-Query-Language) [//github.com/microsoft/Kusto-Query-Language](https://github.com/microsoft/Kusto-Query-Language)
- <Anchor id="page-13-14"/>[51] Guido Moerkotte. 1998. 小さなマテリアライズド集約: データウェアハウジング向けの軽量インデックス構造. In Proceedings of the 24rd International Conference on Very Large Data Bases (VLDB '98). 476–487.
- <Anchor id="page-13-22"/>[52] Jalal Mostafa, Sara Wehbi, Suren Chilingaryan, and Andreas Kopmann. 2022. SciTS: 科学実験と産業IoTにおける時間シリーズデータベースのベンチマーク. In Proceedings of the 34th International Conference on Scientific and Statistical Database Management (SSDBM '22). Article 12. [https:](https://doi.org/10.1145/3538712.3538723) [//doi.org/10.1145/3538712.3538723](https://doi.org/10.1145/3538712.3538723)
- <Anchor id="page-13-0"/>[53] Thomas Neumann. 2011. 効率的なクエリプランを現代ハードウェアに効率よくコンパイルする. Proc. VLDB Endow. 4, 9 (jun 2011), 539–550. [https://doi.org/10.14778/](https://doi.org/10.14778/2002938.2002940) [2002938.2002940](https://doi.org/10.14778/2002938.2002940)
- <Anchor id="page-13-25"/>[54] Thomas Neumann and Michael J. Freitag. 2020. Umbra: メモリ内パフォーマンスを持つディスクベース システム. In 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-neumann](http://cidrdb.org/cidr2020/papers/p29-neumann-cidr20.pdf)[cidr20.pdf](http://cidrdb.org/cidr2020/papers/p29-neumann-cidr20.pdf)
- <Anchor id="page-13-35"/>[55] Thomas Neumann, Tobias Mühlbauer, and Alfons Kemper. 2015. メインメモリデータベースシステムのための高速可 serializable マルチバージョン同時実行制御. 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.](https://doi.org/10.1145/2723372.2749436) [2749436](https://doi.org/10.1145/2723372.2749436)
- <Anchor id="page-13-8"/>[56] LevelDB on GitHub. 2024. LevelDB. 2024-06-20に取得。 [https://github.](https://github.com/google/leveldb) [com/google/leveldb](https://github.com/google/leveldb)
- <Anchor id="page-13-26"/>[57] Patrick O'Neil, Elizabeth O'Neil, Xuedong Chen, and Stephen Revilak. 2009. スタースキーマベンチマークおよび拡張ファクトテーブルインデクシング. In Performance Evaluation and Benchmarking. Springer Berlin Heidelberg, 237–252. [https:](https://doi.org/10.1007/978-3-642-10424-4_17) [//doi.org/10.1007/978-3-642-10424-4_17](https://doi.org/10.1007/978-3-642-10424-4_17)
- <Anchor id="page-13-7"/>[58] Patrick E. O'Neil, Edward Y. C. Cheng, Dieter Gawlick, and Elizabeth J. O'Neil. 1996. ログ構造マージツリー (LSMツリー). Acta Informatica 33 (1996), 351–385. https://doi.org/10.1007/s002360050048
- <Anchor id="page-13-4"/>[59] Diego Ongaro and John Ousterhout. 2014. 理解しやすいコンセンサスアルゴリズムを求めて. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference (USENIX ATC'14). 305–320. [https://doi.org/doi/10.](https://doi.org/doi/10.5555/2643634.2643666) [5555/2643634.2643666](https://doi.org/doi/10.5555/2643634.2643666)
- <Anchor id="page-13-3"/>[60] Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil. 1996. ログ構造マージツリー (LSM-Tree). Acta Inf. 33, 4 (1996), 351–385. [https:](https://doi.org/10.1007/s002360050048) [//doi.org/10.1007/s002360050048](https://doi.org/10.1007/s002360050048)
- <Anchor id="page-13-5"/>[61] Pandas. 2024. Pandas Dataframes. 2024-06-20に取得。 [https://pandas.](https://pandas.pydata.org/) [pydata.org/](https://pandas.pydata.org/)
- <Anchor id="page-13-32"/>[62] Pedro Pedreira, Orri Erling, Masha Basmanova, Kevin Wilfong, Laith Sakka, Krishna Pai, Wei He, and Biswapesh Chattopadhyay. 2022. Velox: Metaの統一実行エンジン. Proc. VLDB Endow. 15, 12 (aug 2022), 3372–3384. [https:](https://doi.org/10.14778/3554821.3554829) [//doi.org/10.14778/3554821.3554829](https://doi.org/10.14778/3554821.3554829)
- <Anchor id="page-13-10"/>[63] Tuomas Pelkonen, Scott Franklin, Justin Teller, Paul Cavallaro, Qi Huang, Justin Meza, and Kaushik Veeraraghavan. 2015. Gorilla: 高速でスケーラブルなインメモリ時系列データベース. Proceedings of the VLDB Endowment 8, 12 (2015), 1816–1827. https://doi.org/10.14778/2824032.2824078
- <Anchor id="page-13-18"/>[64] Orestis Polychroniou, Arun Raghavan, and Kenneth A. Ross. 2015. メモリ内データベース向けのSIMDベクトル化の再考. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD '15). 1493–1508. https://doi.org/10.1145/2723372.2747645
- <Anchor id="page-13-21"/>[65] PostgreSQL. 2024. PostgreSQL - 外部データラッパー. 2024-06-20に取得。 https://wiki.postgresql.org/wiki/Foreign_data_wrappers
- <Anchor id="page-13-23"/>[66] Mark Raasveldt, Pedro Holanda, Tim Gubner, and Hannes Mühleisen. 2018. 公正なベンチマーキングは難しいと考えられる: データベースパフォーマンステストにおける一般的な落とし穴. In Proceedings of the Workshop on Testing Database Systems (Houston, TX, USA) (DBTest'18). Article 2, 6ページ. https://doi.org/10.1145/3209950.3209955
- <Anchor id="page-13-6"/>[67] Mark Raasveldt and Hannes Mühleisen. 2019. DuckDB: 埋め込み可能な分析データベース (SIGMOD '19). Association for Computing Machinery, New York, NY, USA, 1981–1984. https://doi.org/10.1145/3299869.3320212
- <Anchor id="page-13-16"/>[68] Jun Rao and Kenneth A. Ross. 1999. メインメモリにおける意思決定支援のためのキャッシュ意識型インデクシング. In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB '99). San Francisco, CA, USA, 78–89.
- <Anchor id="page-13-36"/>[69] Navin C. Sabharwal and Piyush Kant Pandey. 2020. Prometheus Query Language (PromQL) の利用. In Monitoring Microservices and Containerized Applications. https://doi.org/10.1007/978-1-4842-6216-0_5
- <Anchor id="page-13-27"/>[70] Todd W. Schneider. 2022. ニューヨーク市のタクシーと運転手付き車両データ. 2024-06-20に取得。 https://github.com/toddwschneider/nyc-taxi-data
- <Anchor id="page-13-13"/>[71] 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: 列指向DBMS. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB '05). 553–564.
- <Anchor id="page-13-29"/>[72] Teradata. 2024. Teradata Database. 2024-06-20に取得。 [https://www.](https://www.teradata.com/resources/datasheets/teradata-database) [teradata.com/resources/datasheets/teradata-database](https://www.teradata.com/resources/datasheets/teradata-database)
- <Anchor id="page-13-15"/>[73] Frederik Transier. 2010. メモリ内テキスト検索エンジンのためのアルゴリズムとデータ構造. Ph.D. Dissertation. https://doi.org/10.5445/IR/1000015824
- <Anchor id="page-13-24"/>[74] Adrian Vogelsgesang, Michael Haubenschild, Jan Finis, Alfons Kemper, Viktor Leis, Tobias Muehlbauer, Thomas Neumann, and Manuel Then. 2018. 実際を見据えた: ベンチマークが現実の世界を表さない理由. In Proceedings of the Workshop on Testing Database Systems (Houston, TX, USA) (DBTest'18). Article 1, 6ページ. https://doi.org/10.1145/3209950.3209952
- <Anchor id="page-13-9"/>[75] LZ4 website. 2024. LZ4. 2024-06-20に取得。 https://lz4.org/
- <Anchor id="page-13-11"/><Anchor id="page-13-1"/>[76] PRQL website. 2024. PRQL. 2024-06-20に取得。 https://prql-lang.org [77] Till Westmann, Donald Kossmann, Sven Helmer, and Guido Moerkotte. 2000. 圧縮データベースの実装とパフォーマンス. SIGMOD Rec.
- <Anchor id="page-13-33"/>29, 3 (sep 2000), 55–67. https://doi.org/10.1145/362084.362137 [78] Fangjin Yang, Eric Tschetter, Xavier Léauté, Nelson Ray, Gian Merlino, and Deep Ganguli. 2014. Druid: リアルタイム分析データストア. 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
- <Anchor id="page-13-20"/>[79] Tianqi Zheng, Zhibin Zhang, and Xueqi Cheng. 2020. SAHA: 分析データベース用の文字列適応型ハッシュテーブル. Applied Sciences 10, 6 (2020). [https:](https://doi.org/10.3390/app10061915) [//doi.org/10.3390/app10061915](https://doi.org/10.3390/app10061915)
- <Anchor id="page-13-19"/>[80] Jingren Zhou and Kenneth A. Ross. 2002. SIMD命令を使用したデータベース操作の実装. In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data (SIGMOD '02). 145–156. [https://doi.org/10.](https://doi.org/10.1145/564691.564709) [1145/564691.564709](https://doi.org/10.1145/564691.564709)
- <Anchor id="page-13-12"/>[81] Marcin Zukowski, Sandor Heman, Niels Nes, and Peter Boncz. 2006. スーパー・スカラーRAM-CPUキャッシュ圧縮. In Proceedings of the 22nd International Conference on Data Engineering (ICDE '06). 59. [https://doi.org/10.1109/ICDE.](https://doi.org/10.1109/ICDE.2006.150) [2006.150](https://doi.org/10.1109/ICDE.2006.150)