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

アーキテクチャの概要

これは私たちの VLDB 2024 科学論文 のウェブ版です。私たちはその背景や経緯についても ブログに投稿 しており、ClickHouseのCTOであり創設者であるアレクセイ・ミロビドフが行ったVLDB 2024のプレゼンテーションを視聴することをお勧めします:

概要​

過去数十年の間に、保存され分析されるデータの量は指数関数的に増加しています。業界やセクターを問わず、企業はこのデータを利用して製品を改善し、パフォーマンスを評価し、ビジネスにとって重要な決定を行うようになっています。しかし、データのボリュームがインターネットスケールで増大するにつれて、企業は、リアルタイムのレイテンシ（例えば、ユースケースに応じて1秒未満）を期待しつつ、より高い同時クエリ数を用いて、歴史的データと新データをコスト効果的かつスケーラブルに管理する必要があります。

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

1 はじめに​

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

ClickHouseは、現代の分析データ管理の5つの重要な課題への対処を目的としています:

  1. 高い取り込み率を持つ巨大なデータセット。ウェブ分析、金融、eコマースなどの業界での多くのデータ駆動アプリケーションには、巨大で継続的に増加するデータ量があります。巨大なデータセットを扱うためには、分析データベースは効率的なインデクシングと圧縮戦略を提供するだけでなく、単一のサーバーが数十TBのストレージに制限されるため、複数のノードにわたるデータの分散（スケールアウト）を可能にする必要があります。さらに、最近のデータは通常、歴史的なデータよりもリアルタイムの洞察にとってより関連性があります。その結果、分析データベースは、新しいデータを一貫して高いレートまたはバーストで取り込むことができ、かつ同時に報告クエリを遅延させることなく、歴史的データを「優先度を下げる」（例：集約、アーカイブ）ことができる必要があります。

  2. 多数の同時クエリと低レイテンシの期待。クエリは一般にアドホック（例：探索的データ分析）または繰り返し（例：定期的なダッシュボードクエリ）に分類できます。ユースケースがインタラクティブであるほど、クエリのレイテンシは低くなることが期待され、これがクエリの最適化と実行において課題を生み出します。繰り返しクエリは、さらにワークロードに応じて物理データベースのレイアウトを適応させる機会を提供します。その結果、データベースは、CPU、メモリ、ディスク、およびネットワークI/Oなどの共有システムリソースへの優先されたアクセスを保証する必要があります。また、大量のクエリが同時に実行される場合でも、リソースの使用量や優先度に応じたリソースの管理をする必要があります。

  3. データストア、ストレージ場所、フォーマットの多様なランドスケープ。既存のデータアーキテクチャと統合するために、現代の分析データベースは、あらゆるシステム、場所、フォーマットで外部データを読み書きするための高いオープン性を示すべきです。

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

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

Image 01

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

2 アーキテクチャ​

Image 02

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

図2 に示すように、ClickHouseエンジンは、クエリ処理層（セクション 4 で説明）、ストレージ層（セクション 3）、および統合層（セクション 5）の3つの主要な層に分かれています。これに加えて、アクセス層はユーザーセッションとアプリケーションとの様々なプロトコルを介した通信を管理します。スレッディング、キャッシング、ロールベースのアクセス制御、バックアップ、および継続的モニタリングのための直交コンポーネントがあります。ClickHouseは、依存関係なしにC++で作られた単一の静的リンクバイナリです。

クエリ処理は、受信クエリの解析、論理および物理クエリ計画の構築と最適化、実行という従来のパラダイムに従います。ClickHouseはMonetDB/X100 [11] に似たベクトル化された実行モデルを使用し、オポチュニスティックコードコンパイル [53] と組み合わせています。クエリは、機能豊富なSQL方言、PRQL [76] またはKustoのKQL [50] で記述できます。

ストレージ層は、テーブルデータのフォーマットと位置をカプセル化する異なるテーブルエンジンで構成されています。テーブルエンジンは3つのカテゴリーに分けられます: 最初のカテゴリーは、ClickHouseの主要な永続化フォーマットを表す^^MergeTree^^*ファミリーのテーブルエンジンです。LSMツリーのアイデアに基づいて [60]、テーブルは水平にソートされた^^parts^^に分割され、バックグラウンドプロセスによって継続的にマージされます。個別の^^MergeTree^^*テーブルエンジンは、マージがその入力^^parts^^から行をどのように組み合わせるかによって異なります。例えば、行は集約または置き換えが可能です。

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

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

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

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

3 ストレージ層​

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

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

^^MergeTree^^*^^table engine^^ の各テーブルは、不変のテーブル^^parts^^ のコレクションとして構成されます。^^Parts^^ は、行のセットがテーブルに挿入されるたびに作成されます。^^Parts^^ は自己完結型であり、その内容を中央カタログへの追加のルックアップなしに解釈するために必要なすべてのメタデータを含んでいます。テーブルごとの^^parts^^の数を低く保つために、バックグラウンドのマージジョブが定期的に複数の小さな^^parts^^を大きな^^part^^に結合し、設定可能な^^part^^サイズ（デフォルトで150 GB）に達するまで繰り返します。^^Parts^^はテーブルの^^primary key^^カラム（セクション 3.2 参照）でソートされているため、高効率なk-wayマージソート [40] がマージに使用されます。ソース^^parts^^は非アクティブとしてマークされ、参照カウントがゼロに減少するたびに最終的に削除されます。すなわち、もはや彼らから読み取られるクエリはありません。

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

Image 03

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

図3 は、^^MergeTree^^*-エンジンテーブルへの4つの同期挿入と2つの非同期挿入を示しています。2回のマージによって、アクティブな^^parts^^の数は最初の5から2に減少しました。

LSMツリー [58] およびさまざまなデータベースにおける実装 [13, 26, 56] に比べて、ClickHouseはすべての^^parts^^を平等に扱い、階層に配置するのではありません。その結果、マージは同じレベルの^^parts^^に限定されなくなります。これは^^parts^^の暗黙的な時間的順序を回避し、トンボストーンに基づかない更新および削除のための代替メカニズムが必要です（セクション 3.4 参照）。ClickHouseは挿入をディスクに直接書き込む一方で、他のLSMツリー型ストアは通常、書き込み前ログを使用します（セクション 3.7 参照）。

^^Part^^はディスク上のディレクトリに対応しており、各カラムに1つのファイルを含んでいます。最適化として、小さな^^part^^（デフォルトで10 MB未満）のカラムは、読み取りと書き込みのための空間的局所性を高めるために、単一のファイルに連続して保存されます。^^Part^^の行はさらに8192レコードのグループ、グラニュールに論理的に分割されます。^^Granule^^は、ClickHouseのスキャンおよびインデックスルックアップオペレーターによって処理される最小の不可分なデータユニットを表します。ただし、ディスク上のデータの読み取りと書き込みは^^granule^^レベルではなく、カラム内の隣接する複数のグラニュールを組み合わせたブロックの粒度で行われます。新しいブロックは、設定可能なバイトサイズごとの^^block^^（デフォルトで1MB）に基づいて形成されます。すなわち、^^block^^内の^^granules^^の数は可変であり、カラムのデータタイプおよび分布に依存します。ブロックはさらに圧縮され、そのサイズとI/Oコストを削減します。デフォルトで、ClickHouseは一般的な圧縮アルゴリズムとしてLZ4 [75] を採用しますが、ユーザーはGorilla [63] やFPC [12] などの特殊なコーデックも指定できます。圧縮アルゴリズムはチェーン化することもできます。たとえば、数値の論理的冗長性をデルタコーディング [23] を使用して最初に削減し、その後重い圧縮を行い、最後にAESコーデックを使用してデータを暗号化することが可能です。ブロックは、ディスクからメモリに読み込まれる際にオンザフライで非圧縮されます。圧縮にもかかわらず、個々のグラニュールへの迅速なランダムアクセスを可能にするために、ClickHouseはさらに各カラムにマッピングを保存し、各^^granule^^のIDを、カラムファイル中のその圧縮^^block^^のオフセットと非圧縮^^block^^中の^^granule^^のオフセットと関連付けます。

カラムはさらに^^dictionary^^でエンコードされたり、2つの特別なラッパーデータ型を使用してNullableにすることができます: LowCardinality(T) は元のカラム値を整数IDで置き換え、その結果、少数の一意の値を持つデータに対してストレージオーバーヘッドを大幅に削減します。Nullable(T) はカラムTに内部ビットマップを追加し、カラム値がNULLであるかどうかを示します。

最後に、テーブルは任意のパーティショニング式を使用して範囲、ハッシュ、またはラウンドロビンでパーティション分割することができます。パーティションプルーニングを可能にするために、ClickHouseは各パーティションのパーティショニング式の最小値と最大値も保存します。ユーザーはオプションで、次数推定を提供する高度なカラム統計（例：HyperLogLog [30] やt-digest [28] 統計）を作成することもできます。

3.2 データプルーニング​

ほとんどのユースケースにおいて、単一のクエリに回答するためにペタバイトのデータをスキャンすることは遅すぎて高コストです。ClickHouseは、検索中に多数の行をスキップすることを可能にする3つのデータプルーニング技術をサポートしており、それによりクエリの速度が大幅に向上します。

まず、ユーザーはテーブルに対して**^^primary key^^インデックス**を定義することができます。^^Primary key^^カラムは、各^^part^^内の行のソート順序を決定します。すなわち、インデックスはローカルクラスタ型です。ClickHouseは、各^^granule^^の最初の行の^^primary key^^カラム値から^^granule^^のIDへのマッピングも各^^part^^のために保存します。すなわち、インデックスはスパースです [31]。得られるデータ構造は通常、メモリに完全に留まるのに十分小さいです。例えば、810万行をインデックス化するのにわずか1000エントリが必要です。^^Primary key^^の主な目的は、バイナリサーチを使用して頻繁にフィルタリングされるカラムに対して等号および範囲の述語を評価することであり、逐次スキャンに代わって使用されます（セクション 4.4 を参照）。ローカルソートはさらに、^^parts^^のマージやクエリ最適化に活用されます。例えば、ソートベースの集約や、^^primary key^^カラムがソーティングカラムの接頭辞を構成する場合にソートオペレーターを物理的実行計画から削除することができます。

図4 は、ページインプレッション統計を持つテーブルの^^primary key^^インデックスの例を示しています。クエリ内の範囲述語に一致するグラニュールを、^^primary key^^インデックスをバイナリサーチすることで見つけることができます。

Image 04

図4: ^^primary key^^インデックスを使用してフィルタを評価する。

次に、ユーザーはテーブルプロジェクションを作成できます。つまり、異なる^^primary key^^ [71] でソートされた同じ行を含むテーブルの代替バージョンです。プロジェクションは、メインテーブルの^^primary key^^とは異なるカラムでフィルタリングするクエリを迅速化するためには効果的ですが、挿入、マージ、およびスペース消費のためのオーバーヘッドが増加します。デフォルトでは、プロジェクションはメインテーブルに新たに挿入された^^parts^^からのみ遅延的に人口され、既存の^^parts^^ からはユーザーが^^projection^^を完全に具現化しない限り、人口されません。クエリオプティマイザは、推定されるI/Oコストに基づいて、メインテーブルまたは^^projection^^のいずれかを読むことを選択します。^^Part^^に対して^^projection^^が存在しない場合、クエリ実行は対応するメインテーブルの部分にフォールバックします。

三番目に、スキッピングインデックスは、プロジェクションの軽量な代替手段を提供します。スキッピングインデックスのアイデアは、複数の連続したグラニュールのレベルで小さなメタデータを格納し、関連性のない行をスキャンするのを避けることを可能にすることです。スキッピングインデックスは、任意のインデックス式と設定可能な粒度で作成できます。すなわち、^^skipping index^^ブロック内のグラニュールの数です。利用可能な^^skipping index^^タイプは以下を含みます: 1. 最小最大インデックス [51] は、各インデックス^^block^^のインデックス式の最小値と最大値を保存します。このインデックスタイプは、小さな絶対範囲のローカルクラスタ型データに対してよく機能します。 2. セットインデックスは、設定可能な数のユニークインデックス^^block^^値を保存します。これらのインデックスは、小さなローカル基数、つまり「塊で集まった」値を持つデータに最適です。 3. ブルームフィルターインデックス [9] は、設定可能な誤検知率を持つ行、トークン、またはn-グラム値のために構築されます。これらのインデックスはテキスト検索 [73] をサポートしますが、最小最大インデックスやセットインデックスとは異なり、範囲やネガティブ述語では使用できません。

3.3 マージ時のデータ変換​

ビジネスインテリジェンスおよび可観測性ユースケースでは、常に高いレートまたはバーストで生成されたデータを扱う必要があります。また、最近生成されたデータは通常、歴史的データよりも有意義なリアルタイムの洞察にとって関連性が高いです。そのようなユースケースは、データベースが高いデータ取り込みレートを維持すると同時に、集約やデータ経年化のような技術を通じて過去データのボリュームを継続的に削減することを必要とします。ClickHouseは、異なるマージ戦略を使用して既存のデータの継続的な増分変換を許容します。マージ時のデータ変換はINSERT文のパフォーマンスを妨げることはありませんが、テーブルに未承諾の（例：古いまたは未集約の）値が絶対に含まれないことを保証することはできません。必要に応じて、すべてのマージ時変換は、SELECT文でFINALキーワードを指定することによってクエリ時に適用できます。

置き換えマージは、所持する^^part^^の作成タイムスタンプに基づいてトゥプルの最も最近挿入されたバージョンのみを保持し、古いバージョンは削除されます。トゥプルは、同じ^^primary key^^カラムの値を持つ場合に相等しいと見なされます。どのトゥプルを保持するかを明示的に制御するために、比較用に特別なバージョンカラムを指定することもできます。置き換えマージは、通常は更新が頻繁なユースケースでのマージ時更新機構として使用されるか、INSERT時のデータ重複排除の代替手段として使用されます（セクション 3.5 を参照）。

集約マージは、同じ^^primary key^^カラムの値を持つ行を集約された行にまとめます。非^^primary key^^カラムは、要約値を保持する部分集約状態でなければなりません。2つの部分集約状態（例：avg()のための合計とカウント）は、新しい部分集約状態に組み合わされます。集約マージは、通常のテーブルの代わりにマテリアライズドビューで使用されます。マテリアライズドビューは、ソーステーブルに対する変換クエリに基づいて人口されます。ClickHouseは、他のデータベースとは異なり、ソーステーブルの全内容でマテリアライズドビューを定期的に更新しません。むしろ、マテリアライズドビューは、ソーステーブルに新しい^^part^^が挿入される時に変換クエリの結果で徐々に更新されます。

図5 は、ページインプレッション統計を持つテーブルに対して定義された^^materialized view^^を示しています。ソーステーブルに挿入された新しい^^parts^^には、変換クエリが地域別にグループ化された最大および平均レイテンシを計算し、その結果が^^materialized view^^に挿入されます。集約関数avg()とmax()は、実際の結果ではなく部分集約状態を返します。^^materialized view^^に対して定義された集約マージは、異なる^^parts^^で部分集約状態を継続的に組み合わせます。最終結果を得るために、ユーザーは^^materialized view^^内の部分集約状態をavg()とmax()で統合します。

Image 05

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

^^TTL^^（生存時間）マージは、歴史的データの経年化を提供します。削除および集約マージとは異なり、^^TTL^^マージは、一度に1つの^^part^^のみを処理します。^^TTL^^マージは、トリガーとアクションを持つルールの観点で定義されます。トリガーは、各行のタイムスタンプを計算する式であり、これは^^TTL^^マージが実行される時間と比較されます。これにより、ユーザーは行単位の粒度でアクションを制御できますが、すべての行が特定の条件を満たすかどうかを確認し、全体の^^part^^に対してアクションを実行するだけで十分と考えられることがわかりました。可能なアクションには以下が含まれます: 1.^^Part^^を別のボリューム（例：より安価で遅いストレージ）に移動する、2.^^Part^^を再圧縮する（例：より重いコーデックを使用して）、3.^^Part^^を削除する、4.ロールアップ、すなわちグルーピングキーと集約関数を使用して行を集約することです。

例えば、リスト1 のログテーブル定義を考えてみてください。ClickHouseは、タイムスタンプカラムの値が1週間を超えた^^parts^^を遅いが安価な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週間後に^^part^^をオブジェクトストレージに移動します。

3.4 更新と削除​

^^MergeTree^^*テーブルエンジンの設計は、追加専用のワークロードを好むが、一部のユースケースでは、時折既存のデータを修正する必要があります。データを更新または削除するための2つのアプローチがあり、いずれも同時挿入を^^block^^していません。

ミューテーションは、テーブルのすべての^^parts^^をインプレースで書き換えます。テーブル（削除）やカラム（更新）が一時的にサイズを2倍にするのを防ぐために、この操作は非原子的です。すなわち、並行のSELECT文は、変異した^^parts^^と未変異の^^parts^^を読み取り、データが操作の終了時に物理的に変更されることを保証します。削除ミューテーションは、すべての^^parts^^のすべてのカラムを書き直すため、依然として高コストです。

代替案として、軽量削除は内部ビットマップカラムを更新するだけで、行が削除されているかどうかを示します。ClickHouseは、追加のフィルターをビットマップカラムに付加してSELECTクエリを修正し、削除された行を結果から除外します。削除された行は、未来の不規則なタイミングでの通常のマージによってのみ物理的に削除されます。カラム数に応じて、軽量削除はミューテーションよりもはるかに速くなる可能性がありますが、SELECTは遅くなります。

同じテーブルで行われる更新および削除操作は、論理的な衝突を避けるために稀で直列化されることが期待されます。

3.5 冪等な挿入​

実践で頻繁に発生する問題は、クライアントがデータをテーブルに挿入するためにサーバーに送信した後の接続タイムアウトをどのように処理するかです。この状況では、クライアントがデータが正常に挿入されたかどうかを区別するのが難しいです。この問題は、クライアントからサーバーにデータを再送信し、^^primary key^^ や一意の制約に依存して重複挿入を拒否することによって従来解決されてきました。データベースは、二分木 [39, 68] 、基数木 [45] 、またはハッシュテーブル [29] に基づくインデックス構造を使用して必要なポイントルックアップを迅速に実行します。これらのデータ構造はすべてのタプルをインデックス化するため、広範なデータセットや高い取り込みレートに対しては、スペースと更新オーバーヘッドが負担になります。

ClickHouseは、各挿入が最終的に^^part^^を作成するという事実に基づいて、より軽量な代替手段を提供します。具体的には、サーバーは最後に挿入された^^parts^^のハッシュを維持（例えば、N=100）し、既知のハッシュを持つ^^parts^^の再挿入を無視します。非レプリケートテーブル及びレプリケートテーブルのハッシュは、それぞれKeeperにローカルに保存されます。その結果、挿入は冪等性を持ち、すなわちクライアントはタイムアウト後に同じバッチの行を再送信するだけで、サーバーが重複排除を処理すると考えることができます。重複排除プロセスをより制御したい場合、クライアントはオプションで挿入トークンを提供できます。これは^^part^^ハッシュとして機能します。ハッシュに基づいた重複排除は、新しい行のハッシュを計算することに関連するオーバーヘッドを伴いますが、ハッシュの保存および比較のコストは無視できるものです。

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

レプリケーションは高可用性（ノード障害に対する耐障害性）の前提条件ですが、負荷分散やゼロダウンタイムのアップグレードにも使用されます [14]。ClickHouseにおいて、レプリケーションはテーブルの状態の概念に基づいており、テーブルの^^parts^^（セクション 3.1）およびカラム名やタイプなどのテーブルメタデータを含みます。ノードは以下の3つの操作を使用してテーブルの状態を進めます：1. 挿入は新しいパートを状態に追加します、2. マージは新しいパートを追加し、既存の^^parts^^を状態から削除します、3. 変異やDDLステートメントは^^parts^^を追加および削除し、テーブルメタデータを変更します。操作は単一のノードでローカルに実行され、グローバルなレプリケーションログに状態遷移のシーケンスとして記録されます。

レプリケーションログは通常3つのClickHouse Keeperプロセスのアンサンブルによって維持され、Raftコンセンサスアルゴリズム [59]を使用して、ClickHouseノードの^^cluster^^に対して分散型で耐障害性のある調整レイヤーを提供します。すべての^^cluster^^ノードは、初めにレプリケーションログの同じ位置を指します。ノードがローカルの挿入、マージ、変異、およびDDLステートメントを実行する間、レプリケーションログは他のすべてのノードで非同期に再生されます。その結果、レプリケートされたテーブルは最終的に一貫性のあるものであり、ノードは最新の状態に収束する間、一時的に古いテーブルの状態を読み取ることができます。前述の多くの操作は、新しい状態を採用するノードの定足数（例：ノードの過半数またはすべてのノード）まで同期的に実行されることができます。

例として、図6は3つのClickHouseノードの^^cluster^^内にある最初は空のレプリケートされたテーブルを示しています。ノード1は最初に2つの挿入ステートメントを受け取り、それらをレプリケーションログに記録します（1 2）。次に、ノード2は最初のログエントリを取得して再生し（3）、ノード1から新しいパートをダウンロードします（4）。一方、ノード3は両方のログエントリを再生します（3 4 5 6）。最後に、ノード3は両方の^^parts^^を新しいパートにマージし、入力^^parts^^を削除し、レプリケーションログにマージエントリを記録します（7）。

Image 06

図6: 3つのノードの^^cluster^^におけるレプリケーション。

3つの最適化により、同期を高速化できます。第一に、^^cluster^^に新しいノードが追加された場合、そのノードはレプリケーションログを最初から再生するのではなく、最後のレプリケーションログエントリを記録したノードの状態を単にコピーします。第二に、マージはローカルで再実行するか、他のノードから結果パートを取得することによって再生されます。正確な動作は設定可能で、CPU消費とネットワークI/Oのバランスを取ることを可能にします。例えば、データセンター間のレプリケーションは、運用コストを最小限に抑えるために、通常はローカルマージを好みます。第三に、ノードは相互に独立したレプリケーションログエントリを並行して再生します。これは、例えば、同じテーブルに連続的に挿入された新しい^^parts^^の取得や、異なるテーブルでの操作を含みます。

3.7 ACID準拠​

同時に多数の読み取りおよび書き込み操作のパフォーマンスを最大化するために、ClickHouseはできるだけロックを避けます。クエリは、クエリの開始時に作成されたすべての^^parts^^のスナップショットに対して実行されます。これにより、並列INSERTやマージで挿入された新しい^^parts^^（セクション 3.1）が実行に参加しないようにします。同時に^^parts^^が変更または削除されるのを防ぐために（セクション 3.4）、処理された^^parts^^の参照カウントはクエリの実行中の期間中増加します。形式的には、これはバージョン管理された^^parts^^に基づくMVCCバリアントによって実現されたスナップショット分離に対応します [6]。その結果、ステートメントは一般にACID準拠ではなく、スナップショットが取得される時点で同時に書き込みが行われる限りでは、単一のパートにのみ影響を与えるという稀なケースを除きます。

実際には、ClickHouseの書き込みを多く使用する意思決定のユースケースのほとんどでは、停電時に新しいデータが失われる小さなリスクを許容します。データベースは、この特性を利用して、デフォルトで新しく挿入された^^parts^^をディスクにコミット（fsync）することを強制せず、カーネルが書き込みをバッチ処理することを許可しますが、その結果^^atomicity^^を犠牲にします。

4 クエリ処理層​

Image 07

図7: SIMDユニット、コア、ノードにおける並列処理。

図7に示されているように、ClickHouseはデータ要素、データチャンク、およびテーブルシャードのレベルでクエリを並列化します。複数のデータ要素を同時にSIMD命令を使用して演算子の中で処理できます。単一ノード内では、クエリエンジンは複数のスレッドで演算子を同時に実行します。ClickHouseはMonetDB/X100 [11]と同様のベクタリゼーションモデルを使用しており、演算子は単一行ではなく、複数行（データチャンク）を生成、パス、消費します。これにより、仮想関数呼び出しのオーバーヘッドを最小限に抑えます。ソーステーブルが互いに重複しないテーブルシャードに分割されている場合、複数のノードが同時にシャードをスキャンできます。その結果、すべてのハードウェアリソースが完全に活用され、クエリ処理はノードを追加することによって水平に、コアを追加することによって垂直にスケーリングすることができます。

このセクションの残りでは、最初にデータ要素、データチャンク、および^^shard^^の粒度での並列処理を詳細に説明します。次に、クエリパフォーマンスを最大化するための選択された主要な最適化を示します。最後に、ClickHouseが同時クエリの存在の中で共有システムリソースをどのように管理しているかについて議論します。

4.1 SIMD並列化​

演算子間で複数の行を渡すことはベクタリゼーションの機会を生み出します。ベクタリゼーションは手動で書かれたインストリンシック [64, 80] またはコンパイラの自動ベクタリゼーション [25]に基づいています。ベクタリゼーションの恩恵を受けるコードは異なる計算カーネルにコンパイルされます。例えば、クエリ演算子の内部のホットループは、非ベクタリゼーションされたカーネル、自動ベクタリゼーションされたAVX2カーネル、および手動ベクタリゼーションされたAVX-512カーネルの観点から実装できます。最速のカーネルは、cpuid命令に基づいて実行時に選択されます。このアプローチにより、ClickHouseは15年前のシステム（最低でもSSE 4.2を必要とする）で動作しながら、最新のハードウェアで大幅な速度向上を提供できます。

4.2 マルチコア並列化​

Image 08

図8: 3レーンでの物理演算子プラン。

ClickHouseは、SQLクエリを物理プラン演算子の有向グラフに変換する従来のアプローチ [31]を採用しています。演算子プランの入力は、ネイティブまたはサポートされている3rdパーティフォーマットのいずれかでデータを読み取る特別なソース演算子によって表されます（セクション 5を参照）。同様に、特別なシンク演算子は結果を所望の出力フォーマットに変換します。物理演算子プランは、設定可能な最大ワーカースレッド数（デフォルトではコア数）およびソーステーブルサイズに基づいて、クエリコンパイル時に独立した実行レーンに展開されます。レーンは、並行演算子によって処理されるデータを非重複の範囲に分解します。並列処理の機会を最大化するために、レーンは可能な限り遅くマージされます。

例として、図8のノード1のボックスは、ページインプレッション統計を持つテーブルに対する典型的なOLAPクエリの演算子グラフを示しています。最初のステージでは、ソーステーブルの3つの非重複の範囲が同時にフィルタリングされます。再分配交換演算子は、最初と2番目のステージ間で結果チャンクを動的にルーティングして、処理スレッドが均等に利用されるように保ちます。スキャンされた範囲の選好度が大きく異なる場合、最初のステージ後にレーンが不均衡になることがあります。第二のステージでは、フィルタを通過した行がRegionIDによってグループ化されます。集計演算子は、RegionIDをグルーピングカラムとして持ち、avg()の部分集計状態として各グループの合計とカウントを維持します。ローカル集計結果は、最終的にグローバル集計結果に向けてGroupStateMerge演算子によってマージされます。この演算子は、パイプラインを分割するものであり、集計結果が完全に計算されるまで第3ステージを開始できません。第3ステージでは、結果グループがまず再分配交換演算子によって同じサイズの3つの非重複のパーティションに分割され、その後AvgLatencyによってソートされます。ソートは3つのステップで行われます：最初に、ChunkSort演算子が各パーティションの個々のチャンクをソートします。次に、StreamSort演算子がローカルなソート済み結果を維持し、受信したソート済みチャンクと2ウェイマージソートを使用して組み合わせます。最後に、MergeSort演算子がローカル結果をkウェイソートを使用して組み合わせ、最終結果を取得します。

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

ワーカースレッドは、物理演算子プランを継続的に traversし、状態遷移を実行します。CPUキャッシュをホットに保つために、プランには同じスレッドが同じレーンで連続する演算子を処理すべきというヒントが含まれています。並列処理は段階内の非重複入力での水平方向（例：図8では、Aggregate演算子が同時に実行される）およびパイプラインブレーカーによって分離されていない段階間の垂直方向で発生します（例：図8では、同じレーンのFilterおよびAggregate演算子が同時に実行される）。新しいクエリが開始されたり、同時クエリが完了する際の過剰および過少のサブスクリプションを回避するために、並列性の度合いはクエリ開始時に指定されたクエリのワーカースレッドの最大数（セクション 4.5を参照）之间でミッドクエリで変更できます。

演算子は、実行時にクエリ実行にさらに影響を与える二つの方法があります。第一に、演算子は動的に新しい演算子を作成し、接続することができます。これは、メモリ消費が設定された閾値を超えたときにクエリをキャンセルするのではなく、外部の集計、ソート、または結合アルゴリズムに切り替えるために主に使用されます。第二に、演算子はワーカースレッドに非同期キューに移動するように要求できます。これにより、リモートデータを待機する際にワーカースレッドをより効果的に使用できます。

ClickHouseのクエリ実行エンジンおよびモーセル駆動型並列性 [44]は、レーンが通常異なるコア / NUMAソケットで実行され、ワーカースレッドが他のレーンからタスクを奪うことができるという点で類似しています。また、中央のスケジューリングコンポーネントはなく、代わりにワーカースレッドが演算子プランを継続的に traversすることによって自分でタスクを選択します。モーセル駆動型並列性とは異なり、ClickHouseはプランに最大の並列性の度合いを組み込み、デフォルトのモーセルサイズの約100,000行に比べてソーステーブルを分割するためにかなり大きな範囲を使用します。これは場合によっては滞留が発生するかもしれません（例：異なるレーンでfilter演算子の実行時間が大きく異なる場合）が、Repartitionなどの交換演算子を積極的に使用することで、少なくともステージ間でそのような不均衡が蓄積されるのを避けることができます。

4.3 マルチノード並列化​

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

図8のノード2 ... Nは、クリック統計テーブルのシャードを保持する他のノードで実行されるプランの断片を示しています。これらのノードはローカルデータをフィルタリングおよびグループし、その結果をイニシエータノードに送信します。ノード1のGroupStateMerge演算子は、最終的にローカルおよびリモートの結果をマージします。

4.4 ホリスティックパフォーマンス最適化​

このセクションでは、クエリ実行のさまざまな段階に適用される主要なパフォーマンス最適化を選択して紹介します。

クエリ最適化。最初のセットの最適化は、クエリのASTから得られた意味的クエリ表現の上に適用されます。こうした最適化の例には、定数畳み込み（例：concat(lower('a'),upper('b'))は'aB'になります）、特定の集約関数からスカラーを抽出（例：sum(a2)は2 * sum(a)になります）、共通部分式の排除、および平凡なフィルターの否定をINリストに変換することが含まれます（例：x=c OR x=dはx IN (c,d)になります）。最適化された意味的クエリ表現は、その後、論理演算子プランに変換されます。論理プランの上の最適化には、フィルタープッシュダウン、関数評価およびソートステップの順序入れ替え（どちらがより高コストであると見積もられるかに基づく）があります。最後に、論理クエリプランは物理演算子プランに変換されます。この変換は、関連するテーブルエンジンの特性を利用できます。たとえば、^^MergeTree^^-^^table engine^^の場合、ORDER BYカラムが^^primary key^^の接頭辞を形成する場合、データはディスク順に読み取ることができ、ソート演算子はプランから削除することができます。また、集計におけるグルーピングカラムが^^primary key^^の接頭辞を形成する場合、ClickHouseはソート集約 [33]を使用できます。すなわち、前もってソートされた入力の同じ値の集約ランを直接集計することができます。ハッシュ集約と比較して、ソート集約はメモリを大幅に使わず、集約値はランが処理された後にすぐに次の演算子に渡すことができます。

クエリコンパイル。ClickHouseは、隣接したプラン演算子を動的にディス向けに結合する LLVMベースのクエリコンパイルを採用しています [38, 53]。たとえば、式a * b + c + 1は、3つの演算子の代わりに1つの演算子に結合できます。式に加えて、ClickHouseはGROUP BY用に一度に複数の集約関数を評価するためや、複数のソートキーによるソーティングのためにコンパイルを使用します。クエリコンパイルは、仮想呼び出しの数を減らし、データをレジスタまたはCPUキャッシュに保ち、ブランチ予測器を助けます。さらに、実行時コンパイルは、論理最適化やコンパイラに実装されたぺぺーホール最適化の豊富なセットを可能にし、ローカルで利用可能な最速のCPU命令へのアクセスを提供します。コンパイルは、同じ正規の、集約またはソート式が設定された回数よりも多く、異なるクエリによって実行されるときにのみ開始されます。コンパイルされたクエリ演算子はキャッシュされ、将来のクエリで再利用されることができます。[7]

^^Primary key^^インデックス評価。ClickHouseは、条件の論理和が^^primary key^^カラムの接頭辞を構成する場合に、WHERE条件を^^primary key^^インデックスを使用して評価します。^^primary key^^インデックスは、キー値の辞書順に並んだ範囲に対して左から右に分析されます。^^primary key^^カラムに関連するフィルター句は三進法を用いて評価されます - 範囲内の値がすべて真であるか、すべて偽であるか、真/偽が混在する状態です。後者の場合、範囲はサブ範囲に分割され、再帰的に分析されます。フィルター条件内の関数に対する追加の最適化もあります。最初に、関数はモノトニシティを記述する特性を持ちます。たとえば、toDayOfMonth(date)は月内で区間ごとにモノトニックです。モノトニシティ特性により、関数がソートされた入力キー値範囲でソートされた結果を出力するかどうかを推測できます。第二に、いくつかの関数は与えられた関数結果の前像を計算できます。これは、キー列に対する比較において定数を置き換えるために、キー列の値を前像と比較するために使用されます。たとえば、toYear(k) = 2024は、k >= 2024-01-01 && k < 2025-01-01に置き換えることができます。

データスキッピング。ClickHouseは、セクション 3.2で示されたデータ構造を使用して、クエリ実行時のデータ読み取りを回避しようとします。さらに、異なるカラムに対するフィルターは、推定された選好度の降順で、ヒューリスティックに基づいて順次評価されます。少なくとも1つの一致する行を含むデータチャンクのみが次の述語に渡されます。これにより、読み取るデータの量と述語から述語への実行する計算の数が徐々に減少します。この最適化は、少なくとも1つの高選好の述語が存在する場合にのみ適用されます。さもなくば、クエリの遅延はすべての述語を並行して評価する場合と比べて悪化します。

ハッシュテーブル。ハッシュテーブルは、集約やハッシュ結合のための基本的なデータ構造です。適切なタイプのハッシュテーブルを選択することはパフォーマンスにとって重要です。ClickHouseは、ハッシュ関数、アロケータ、セルタイプ、およびリサイズポリシーをバリエーションポイントとして持つ汎用ハッシュテーブルテンプレートからさまざまなハッシュテーブル（2024年3月時点で30以上）をインスタンス化します。グルーピングカラムのデータ型、推定されるハッシュテーブルのカーディナリティ、およびその他の要因に応じて、各クエリの演算子に最適なハッシュテーブルが選択されます。ハッシュテーブルに対して実装されたさらなる最適化には以下が含まれます：

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

結合。ClickHouseは、元々結合を初歩的にしかサポートしていなかったため、歴史的に多くのユースケースは非正規化テーブルに頼りました。現在、このデータベースはSQLで利用可能なすべての結合タイプ（内部、左/右/完全外部、クロス、経時的）を提供し、ハッシュ結合（ナイーブ、グレース）、ソートマージ結合、および高速なキーと値のルックアップを持つテーブルエンジン用のインデックス結合などの異なる結合アルゴリズムも提供しています。

結合は最も高コストなデータベース操作の一つであるため、従来の結合アルゴリズムの並列バリアントを提供することが重要であり、理想的には設定可能なスペース/時間のトレードオフを提供します。ハッシュ結合に関して、ClickHouseは [7]からの非ブロック、シェアパーティションアルゴリズムを実装しています。例えば、図9のクエリは、ページヒット統計テーブル上での自己結合によってユーザーがURL間をどのように移動するかを計算します。結合のビルドフェーズは、ソーステーブルの3つの非重複の範囲をカバーする3レーンに分割されます。グローバルハッシュテーブルの代わりに、パーティション化されたハッシュテーブルが使用されます。（通常、3つの）ワーカースレッドは、ハッシュ関数のモジュロを計算することによってビルド側の各入力行のターゲットパーティションを決定します。ハッシュテーブルパーティションへのアクセスは、Gather交換演算子を使用して同期されます。プローブフェーズは、入力タプルのターゲットパーティションを同様に見つけます。このアルゴリズムは各タプルごとに2つの追加のハッシュ計算を導入しますが、ハッシュテーブルパーティションの数に応じて、ビルドフェーズでのラッチ競合を大幅に削減します。

Image 09

図9: 3つのハッシュテーブルパーティションによる並列ハッシュ結合。

4.5 ワークロードアイソレーション​

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

同時性制御は、多数の同時クエリがあるシナリオでのスレッドのオーバーサブスクリプションを防ぎます。より具体的には、各クエリのワーカースレッドの数は、利用可能なCPUコアの数に対する指定された比率に基づいて動的に調整されます。

ClickHouseは、サーバー、ユーザー、クエリレベルでメモリアロケーションのバイトサイズを追跡し、柔軟なメモリ使用制限を設定できるようにします。メモリオーバーコミットは、クエリが保証メモリを超えて追加の空きメモリを使用できるようにし、他のクエリのメモリ制限を保証します。さらに、集約、ソート、結合句のメモリ使用量を制限することができ、メモリ制限が超えた場合に外部アルゴリズムにフェイルバックします。

最後に、I/Oスケジューリングにより、ユーザーはワークロードクラスに対して最大帯域幅、交戦リクエスト、およびポリシー（例：FIFO、SFC [32]）に基づいてローカルおよびリモートディスクへのアクセスを制限できます。

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

リアルタイム意思決定アプリケーションは、多くの場所でのデータへの効率的かつ低遅延のアクセスに依存することがよくあります。OLAPデータベースに外部データを利用可能にする2つのアプローチがあります。プッシュベースのデータアクセスでは、サードパーティコンポーネントがデータベースと外部データストアを橋渡しします。これに関する一例は、リモートデータを宛先システムにプッシュするための専門ETLツールです。プルベースのモデルでは、データベース自体がリモートデータソースに接続し、ローカルテーブルにクエリ用のデータをプルするか、リモートシステムにデータをエクスポートします。プッシュベースのアプローチはより多用途で一般的ですが、より大きなアーキテクチャフットプリントとスケーラビリティのボトルネックを伴います。対照的に、データベース内でのリモート接続は、ローカルデータとリモートデータの結合などの興味深い機能を提供しつつ、全体のアーキテクチャを単純に保ち、洞察までの時間を短縮します。

このセクションの残りでは、リモートロケーションでデータにアクセスすることを目的としたClickHouseにおけるプルベースのデータインテグレーション方法を探ります。SQLデータベースにおけるリモート接続のアイデアは新しいものではないことに注意します。たとえば、SQL/MED規格 [35]は、2001年に導入され、2011年からPostgreSQLによって実装されています [65]。これは、外部データを管理するための統一インターフェースとして外国データラッパーを提案しています。他のデータストアやストレージフォーマットとの最大の相互運用性は、ClickHouseの設計目標の一つです。2024年3月現在、ClickHouseはすべての分析データベースにおいて、私たちの知識の範囲内で最も多くの組み込みデータインテグレーションオプションを提供しています。

外部接続性。ClickHouseは、ODBC、MySQL、PostgreSQL、SQLite、Kafka、Hive、MongoDB、Redis、S3/GCP/Azureオブジェクトストア、およびさまざまなデータレイクとの接続を提供する 50+ 統合テーブル関数とエンジンを提供します。これらをさらに、以下のボーナス図で示されているカテゴリーに分類します（元のVLDB論文には含まれていません）。

Image 10

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

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

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

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

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

最後に、ディクショナリーは、対応する統合テーブル関数またはエンジンに対してほぼすべての可能なデータソースに対して任意のクエリを使用してポピュレートできます。ランタイムの振る舞いはアクティブであり、リモートストレージからデータが一定の間隔で引き出されます。

データフォーマット。サードパーティシステムと対話するために、最新の分析データベースはあらゆる形式のデータを処理できる必要があります。そのネイティブフォーマットに加えて、ClickHouseは 90+ のフォーマットをサポートしており、CSV、JSON、Parquet、Avro、ORC、Arrow、Protobufが含まれます。各フォーマットは入力フォーマット（ClickHouseが読み取ることのできるもの）、出力フォーマット（ClickHouseがエクスポートできるもの）、または両方であることができます。Parquetのような分析指向のフォーマットは、クエリ処理に統合されており、すなわち、オプティマイザーは組み込まれた統計を利用でき、フィルターは圧縮データ上で直接評価されます。

互換性インターフェース。ネイティブのバイナリワイヤプロトコルやHTTPに加えて、クライアントはMySQLやPostgreSQLのワイヤプロトコル互換インターフェースを介してClickHouseと対話できます。この互換性機能は、ベンダーがまだネイティブのClickHouse接続を実装していない場合の独自のアプリケーション（例：特定のビジネスインテリジェンスツール）からのアクセスを可能にします。

6 パフォーマンスを特徴として​

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

6.1 組み込みパフォーマンス分析ツール​

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

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

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

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

クエリの説明。他のデータベースと同様に、SELECTクエリは、そのクエリのAST、論理および物理演算子プラン、および実行時の動作に関する詳細なインサイトのためにEXPLAINの前に記述できます。

6.2 ベンチマーク​

ベンチマーキングは、十分に現実的ではないため批判されることがありますが [10, 52, 66, 74]、それでもデータベースの強みと弱みを特定するのに役立ちます。以下に、ClickHouseのパフォーマンスを評価するためにベンチマークがどのように使用されるかについて議論します。

6.2.1 非正規化テーブル​

非正規化されたファクトテーブルに対するフィルタリングおよび集約クエリは、歴史的にClickHouseの主要な使用ケースを表しています。ClickBenchの実行時間を報告します。これは、クリックストリームおよびトラフィック分析で使用されるアドホックおよび周期的なレポートクエリをシミュレートするこの種の典型的なワークロードです。このベンチマークは、1億件の匿名ページヒットを持つテーブルに対して43のクエリから構成されており、これはウェブ上で最大の分析プラットフォームの1つから取得されています。オンラインダッシュボード [17] は、2024年6月時点で45以上の商業データベースおよび研究データベースの測定値（コールド/ホット実行時間、データインポート時間、ディスクサイズ）を表示します。結果は、公開されているデータセットおよびクエリに基づいて独立した貢献者によって提出されます [16]。クエリは、順次およびインデックススキャンのアクセスパスをテストし、CPU、IO、またはメモリに制約のある関係演算子を常に露呈します。

図10 は、分析に頻繁に使用されるデータベースでClickBenchの全クエリを順次実行した場合の、総相対コールドおよびホット実行時間を示しています。測定は、16 vCPUs、32 GB RAM、5000 IOPS / 1000 MiB/sのディスクを持つ単一ノードAWS EC2 c6a.4xlargeインスタンスで行われました。Redshift（ra3.4xlarge、12 vCPUs、96 GB RAM）およびSnowfake（warehouse size S: 2x8 vCPUs、2x16 GB RAM）の比較可能なシステムが使用されました。物理データベース設計はわずかに調整されており、たとえば主キーを指定しますが、個々のカラムの圧縮を変更したり、プロジェクションを作成したり、スキッピングインデックスを作成することはありません。また、各コールドクエリ実行の前にLinuxページキャッシュをフラッシュしますが、データベースやオペレーティングシステムのノブを調整することはありません。各クエリに対して、データベース間で最も速い実行時間がベースラインとして使用されます。他のデータベースの相対クエリ実行時間は ( + 10)/(_ + 10) として計算されます。データベースの総相対実行時間は、クエリごとの比率の幾何平均です。研究データベースUmbra [54] は、全体的なホット実行時間の最良を達成していますが、ClickHouseはホットおよびコールド実行時間においてすべての商用データベースを上回っています。

Image 11

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

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

図11 は、2018年3月から2024年3月までの間に77のClickHouseバージョンについてVersionsBenchの実行時間の推移を示しています。個々のクエリの相対実行時間の違いを補正するために、すべてのバージョンにわたる最小クエリ実行時間に対する比率を重みとして幾何平均を使用して実行時間を正規化します。VersionBenchのパフォーマンスは、過去6年間で1.72倍向上しました。長期サポート（LTS）を持つリリースの日付はx軸に示されています。一部の期間でパフォーマンスが一時的に悪化しましたが、LTSリリースは一般的に前のLTSバージョンと同等またはそれ以上のパフォーマンスを持っています。2022年8月の大幅な改善は、セクション 4.4. で説明されているカラムごとのフィルタ評価技術によって引き起こされました。

Image 12

図11: VersionsBench 2018-2024の相対ホット実行時間。

6.2.2 正規化テーブル​

クラシックなデータウェアハウジングでは、データはしばしばスタースキーマやスノーフレイクスキーマを使用してモデル化されます。TPC-Hクエリ（スケールファクター100）の実行時間を示しますが、正規化テーブルはClickHouseの新興の使用ケースであることに注意してください。図12 は、セクション 4.4. で説明されている並列ハッシュ結合アルゴリズムに基づいたTPC-Hクエリのホット実行時間を示しています。測定は、64 vCPUs、128 GB RAM、5000 IOPS / 1000 MiB/sのディスクを持つ単一ノードAWS EC2 c6i.16xlargeインスタンスで行われました。5回の実行の中で最も速いものが記録されました。参照のため、同等のサイズのSnowfakeシステム（ウェアハウスサイズL、8x8 vCPUs、8x16 GB RAM）でも同じ測定を行いました。11のクエリの結果はテーブルから除外されています：クエリQ2、Q4、Q13、Q17、およびQ20-22には、ClickHouse v24.6の時点でサポートされていない相関サブクエリが含まれています。クエリQ7-Q9およびQ19は、結合を行うための結合再配置や結合述語プッシュダウンなどの拡張されたプランレベルの最適化に依存しています（ClickHouse v24.6の時点でいずれも不足）。2024年に実装が計画されています [18]。残りの11のクエリのうち、5（6）のクエリはClickHouseでより速く実行されました（Snowfake）。前述の最適化はパフォーマンスにとって重要であることが知られているため [27]、実装されるとこれらのクエリの実行時間がさらに改善されることが期待されます。

Image 13

図12: TPC-Hクエリのホット実行時間（秒）。

分析データベースは、近年の学術的および商業的関心の大きな対象となってきました [1]。Sybase IQ [48]、Teradata [72]、Vertica [42]、およびGreenplum [47]のような初期のシステムは、高価なバッチETLジョブと、オンプレミスな性質に起因する限定された弾力性が特徴でした。2010年代初頭、クラウドネイティブなデータウェアハウスおよびデータベース-as-a-service（DBaaS）提供の出現により（Snowfake [22]、BigQuery [49]、およびRedshift [4] など）、組織の分析にかかるコストと複雑さが劇的に削減され、高可用性と自動リソーススケーリングの恩恵を受けることができました。最近では、分析実行カーネル（たとえば、Photon [5] およびVelox [62]）は、さまざまな分析、ストリーミング、および機械学習アプリケーションで使用されるための共修正データ処理を提供します。

ClickHouseに最も類似したデータベースは、Druid [78] およびPinot [34] です。両者のシステムは、高いデータ取り込み速度でリアルタイム分析をターゲットにしています。ClickHouseと同様に、テーブルはセグメントと呼ばれる水平な^^parts^^に分割されます。ClickHouseは小さな^^parts^^を継続的にマージし、オプションでセクション 3.3, の技術を使用してデータボリュームを削減しますが、DruidおよびPinotでは^^parts^^は永遠に不変です。また、DruidとPinotは、テーブルを作成、変更、および検索するために専門のノードを必要としますが、ClickHouseはこれらのタスクのためにモノリシックなバイナリを使用します。

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

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

DuckDB [67] は、ホストプロセスに埋め込むことを目的としていますが、クエリ最適化およびトランザクションも提供します。これは、OLAPクエリと時折のOLTPステートメントを混在させるために設計されました。DuckDBはこれに応じて、ハイブリッドワークロードで良好なパフォーマンスを達成するために、順序保持辞書や参照フレームなどの軽量圧縮手法を採用したDataBlocks [43] ストレージフォーマットを選びました。対照的に、ClickHouseは追加専用の使用ケースに最適化されており、つまり更新や削除はなく、またはごく稀です。ブロックはLZ4のような重い技術を使用して圧縮され、ユーザーが頻繁なクエリを加速するためにデータプルーニングを積極的に行い、残りのクエリに対するI/Oコストがデコンプレッションコストを上回ることを前提としています。DuckDBは、HyperのMVCCスキームに基づいた可直列性トランザクション [55] を提供していますが、ClickHouseはスナップショットアイソレーションのみを提供します。

8 結論と展望​

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

2024年に予定されているすべての機能と強化は、市場公開ドキュメント [18] で確認できます。予定されている改善には、ユーザートランザクションのサポート、PromQL [69] を代替クエリ言語としての追加、新しいデータ型の実装（例：JSON）や結合のプランレベルの最適化、軽量削除と補完するための軽量更新の実装が含まれています。

謝辞​

バージョン24.6に基づき、SELECT * FROM system.contributors は、ClickHouseに貢献した1994人を返します。ClickHouse Inc.のエンジニアリングチーム全員と、ClickHouseの素晴らしいオープンソースコミュニティに感謝の意を表したいと思います。

REFERENCES​

  • [1] Daniel Abadi, Peter Boncz, Stavros Harizopoulos, Stratos Idreaos, and Samuel Madden. 2013. 現代の列指向データベースシステムの設計と実装. https://doi.org/10.1561/9781601987556
  • [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
  • [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.
  • [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
  • [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: 湖のハウスシステム向けの高速クエリエンジン (SIGMOD '22). Association for Computing Machinery, New York, NY, USA, 2326–2339. https://doi.org/10.1145/3514221. 3526054
  • [6] Philip A. Bernstein and Nathan Goodman. 1981. 分散データベースシステムにおける同時制御. ACM Computing Survey 13, 2 (1981), 185–221. https://doi.org/10.1145/356842.356846
  • [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
  • [8] Daniel Gomez Blanco. 2023. 実用的オープンテレメトリー. Springer Nature.
  • [9] Burton H. Bloom. 1970. 許容誤差をもつハッシュコーディングにおける空間/時間トレードオフ. Commun. ACM 13, 7 (1970), 422–426. https://doi.org/10.1145/362686. 362692
  • [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- 04936-6_5
  • [11] Peter Boncz, Marcin Zukowski, and Niels Nes. 2005. MonetDB/X100: ハイパーパイプラインクエリ実行. In CIDR.
  • [12] Martin Burtscher and Paruj Ratanaworabhan. 2007. ダブル精度浮動小数点データの高スループット圧縮. In Data Compression Conference (DCC). 293–302. https://doi.org/10.1109/DCC.2007.44
  • [13] Jef Carpenter and Eben Hewitt. 2016. Cassandra: 完全ガイド (第2版). O'Reilly Media, Inc.
  • [14] Bernadette Charron-Bost, Fernando Pedone, and André Schiper (Eds.). 2010. レプリケーション: 理論と実践. Springer-Verlag.
  • [15] chDB. 2024. chDB - 組込OLAP SQLエンジン. Retrieved 2024-06-20 from https://github.com/chdb-io/chdb
  • [16] ClickHouse. 2024. ClickBench: 分析データベース向けのベンチマーク. Retrieved 2024-06-20 from https://github.com/ClickHouse/ClickBench
  • [17] ClickHouse. 2024. ClickBench: 比較測定. Retrieved 2024-06-20 from https://benchmark.clickhouse.com
  • [18] ClickHouse. 2024. ClickHouseロードマップ2024 (GitHub). Retrieved 2024-06-20 from https://github.com/ClickHouse/ClickHouse/issues/58392
  • [19] ClickHouse. 2024. ClickHouseバージョンベンチマーク. Retrieved 2024-06-20 from https://github.com/ClickHouse/ClickBench/tree/main/versions
  • [20] ClickHouse. 2024. ClickHouseバージョンベンチマーク結果. Retrieved 2024-06-20 from https://benchmark.clickhouse.com/versions/
  • [21] Andrew Crotty. 2022. MgBench. Retrieved 2024-06-20 from https://github.com/ andrewcrotty/mgbench
  • [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. 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
  • [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
  • [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
  • [25] LLVM documentation. 2024. LLVMにおける自動ベクトル化. Retrieved 2024-06-20 from https://llvm.org/docs/Vectorizers.html
  • [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
  • [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
  • [28] Ted Dunning. 2021. t-digest: 分布の効率的な推定. Software Impacts 7 (2021). https://doi.org/10.1016/j.simpa.2020.100049
  • [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- 2_11
  • [30] Philippe Flajolet, Eric Fusy, Olivier Gandouet, and Frederic Meunier. 2007. HyperLogLog: ほぼ最適な基数推定アルゴリズムの分析. In AofA: 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
  • [31] Hector Garcia-Molina, Jefrey D. Ullman, and Jennifer Widom. 2009. データベースシステム - 完全な書籍 (第2版).
  • [32] Pawan Goyal, Harrick M. Vin, and Haichen Chen. 1996. スタートタイム公平キューイング: 統合サービスパケットスイッチングネットワークのスケジューリングアルゴリズム. 26, 4 (1996), 157–168. https://doi.org/10.1145/248157.248171
  • [33] Goetz Graefe. 1993. 大規模データベースのためのクエリ評価技術. ACM Comput. Surv. 25, 2 (1993), 73–169. https://doi.org/10.1145/152610.152611
  • [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億5300万人のユーザー向けのリアルタイム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
  • [35] ISO/IEC 9075-9:2001 2001. 情報技術 — データベース言語 — SQL — パート9: 外部データの管理 (SQL/MED). 標準. International Organization for Standardization.
  • [36] Paras Jain, Peter Kraft, Conor Power, Tathagata Das, Ion Stoica, and Matei Zaharia. 2023. 湖の家ストレージシステムの分析と比較. CIDR.
  • [37] Project Jupyter. 2024. Jupyter Notebooks. Retrieved 2024-06-20 from https: //jupyter.org/
  • [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
  • [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
  • [40] Donald E. Knuth. 1973. プログラミングの芸術, 第3巻: ソートと検索. Addison-Wesley.
  • [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
  • [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. 14778/2367502.2367518
  • [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
  • [44] Viktor Leis, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2014. モーサル駆動並列性: マルチコア時代のNUMA対応クエリ評価フレームワーク. 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
  • [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. 2013.6544812
  • [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
  • [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: //doi.org/10.1145/3448016.3457562
  • [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.
  • [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: Web規模でのインタラクティブSQL分析の10年. Proc. VLDB Endow. 13, 12 (aug 2020), 3461–3472. https://doi.org/10.14778/3415478.3415568
  • [50] Microsoft. 2024. Kustoクエリ言語. Retrieved 2024-06-20 from https: //github.com/microsoft/Kusto-Query-Language
  • [51] Guido Moerkotte. 1998. 小さな物理化された集計: データウェアハウジング用の軽量インデックス構造. In Proceedings of the 24rd International Conference on Very Large Data Bases (VLDB '98). 476–487.
  • [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: //doi.org/10.1145/3538712.3538723
  • [53] Thomas Neumann. 2011. 現代ハードウェアのために効率的なクエリプランをコンパイルする. Proc. VLDB Endow. 4, 9 (jun 2011), 539–550. https://doi.org/10.14778/ 2002938.2002940
  • [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-neumanncidr20.pdf
  • [55] Thomas Neumann, Tobias Mühlbauer, and Alfons Kemper. 2015. メインメモリデータベースシステムのための迅速な可直列化多バージョン同時制御. 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
  • [56] LevelDB on GitHub. 2024. LevelDB. Retrieved 2024-06-20 from https://github. com/google/leveldb
  • [57] Patrick O'Neil, Elizabeth O'Neil, Xuedong Chen, and Stephen Revilak. 2009. スター スキーマ ベンチマークと拡張ファクトテーブル インデックス. In Performance Evaluation and Benchmarking. Springer Berlin Heidelberg, 237–252. https: //doi.org/10.1007/978-3-642-10424-4_17
  • [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
  • [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. 5555/2643634.2643666
  • [60] Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil. 1996. ログ構造マージツリー（LSM-Tree）. Acta Inf. 33, 4 (1996), 351–385. https: //doi.org/10.1007/s002360050048
  • [61] Pandas. 2024. Pandasデータフレーム. Retrieved 2024-06-20 from https://pandas. pydata.org/
  • [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: //doi.org/10.14778/3554821.3554829
  • [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
  • [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
  • [65] PostgreSQL. 2024. PostgreSQL - 外部データラッパー. Retrieved 2024-06-20 from https://wiki.postgresql.org/wiki/Foreign_data_wrappers
  • [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
  • [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
  • [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.
  • [69] Navin C. Sabharwal and Piyush Kant Pandey. 2020. Prometheusクエリ言語（PromQL）を使用した作業. In Monitoring Microservices and Containerized Applications. https://doi.org/10.1007/978-1-4842-6216-0_5
  • [70] Todd W. Schneider. 2022. ニューヨーク市のタクシーおよびハイヤー車両データ. Retrieved 2024-06-20 from https://github.com/toddwschneider/nyc-taxi-data
  • [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.
  • [72] Teradata. 2024. Teradataデータベース. Retrieved 2024-06-20 from https://www. teradata.com/resources/datasheets/teradata-database
  • [73] Frederik Transier. 2010. インメモリテキスト検索エンジンのためのアルゴリズムとデータ構造. Ph.D. Dissertation. https://doi.org/10.5445/IR/1000015824
  • [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
  • [75] LZ4 website. 2024. LZ4. Retrieved 2024-06-20 from https://lz4.org/
  • [76] PRQL website. 2024. PRQL. Retrieved 2024-06-20 from https://prql-lang.org [77] Till Westmann, Donald Kossmann, Sven Helmer, and Guido Moerkotte. 2000. 圧縮データベースの実装とパフォーマンス. SIGMOD Rec.
  • 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
  • [79] Tianqi Zheng, Zhibin Zhang, and Xueqi Cheng. 2020. SAHA: 分析用SQLデータベースのための文字列適応型ハッシュテーブル. Applied Sciences 10, 6 (2020). https: //doi.org/10.3390/app10061915
  • [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. 1145/564691.564709
  • [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. 2006.150