ClickHouseのデータスキッピングインデックスを理解する

スキップ索引を使用すると、ClickHouse は一致する値が含まれないことが確実な大量のデータchunkの読み取りをスキップできます。

​

はじめに

ClickHouseのクエリパフォーマンスには、多くの要因が影響します。ほとんどのケースで重要になるのは、クエリのWHERE句の条件を評価する際に、ClickHouseが主キーを利用できるかどうかです。そのため、最も一般的なクエリパターンに合った主キーを選択することが、効果的なテーブル設計には不可欠です。

とはいえ、主キーをどれほど慎重に調整しても、それを効率的に利用できないクエリのユースケースは必ず存在します。一般に、ユーザーは時系列データのためにClickHouseを利用しますが、同じデータを顧客ID、WebサイトのURL、製品番号など、別の業務上の次元で分析したいこともよくあります。その場合、WHERE句の条件を適用するために各カラム値のフルスキャンが必要になることがあり、クエリパフォーマンスは大幅に低下する可能性があります。そのような場合でもClickHouseは比較的高速ですが、数百万から数十億もの個々の値を評価する必要があるため、「索引なし」のクエリは主キーに基づくクエリに比べてはるかに遅く実行されます。

従来のリレーショナルデータベースでは、この問題への対処法の1つとして、テーブルに1つ以上の「セカンダリ」索引を追加します。これはb-tree構造で、nを行数とすると、データベースは一致するすべての行を、O(n)時間 (テーブルスキャン) ではなくO(log(n))時間でディスク上から見つけることができます。しかし、この種のセカンダリ索引は、ClickHouse (または他のカラム指向データベース) では機能しません。ディスク上には、索引に追加できる個々の行が存在しないためです。

その代わりに、ClickHouseは別の種類の索引を提供しており、特定の状況ではクエリ速度を大幅に向上させることができます。これらの構造は「Skip」索引と呼ばれます。これは、一致する値が含まれないことが確実な大量のデータchunkを、ClickHouseが読み飛ばせるようにするためです。

​

基本的な動作

データスキッピングインデックスを使用できるのは、MergeTree family のテーブルだけです。各データスキッピングインデックスには、4 つの主要な引数があります。

• 索引名。索引名は、各パーティションに索引ファイルを作成するために使われます。また、索引を削除またはマテリアライズする際のパラメータとしても必要です。
• 索引式。索引式は、索引に格納される値の集合を計算するために使われます。これは、カラム、単純な演算子、または索引タイプによって決まる関数のサブセットを組み合わせたものにできます。
• TYPE。索引のタイプは、各索引ブロックについて、読み取りと評価をスキップできるかどうかを判断する計算を制御します。
• GRANULARITY。各索引付きブロックは、GRANULARITY 個のグラニュールで構成されます。たとえば、テーブルのプライマリ索引の granularity が 8192 行で、索引の granularity が 4 の場合、各索引付き “block” は 32768 行になります。

ユーザーがデータスキッピングインデックスを作成すると、テーブルの各 data part ディレクトリに 2 つの追加ファイルが作成されます。

• skp_idx_{index_name}.idx。順序付けられた式の値が格納されます
• skp_idx_{index_name}.mrk2。関連するデータカラムファイル内の対応するオフセットが格納されます。

クエリの実行時に関連するカラムファイルを読み取る際、WHERE 句のフィルタ条件の一部がスキップ索引式に一致すると、ClickHouse は索引ファイルのデータを使って、関連する各データブロックを処理する必要があるか、それとも読み飛ばせるかを判断します (そのブロックが主キーの適用によってまだ除外されていないことを前提とします) 。ごく単純化した例として、予測しやすいデータがロードされた次のテーブルを考えてみましょう。

CREATE TABLE skip_table
(
  my_key UInt64,
  my_value UInt64
)
ENGINE MergeTree primary key my_key
SETTINGS index_granularity=8192;

INSERT INTO skip_table SELECT number, intDiv(number,4096) FROM numbers(100000000);

主キーを使わない単純なクエリを実行すると、my_value カラム内の 1 億件のエントリすべてがスキャンされます:

SELECT * FROM skip_table WHERE my_value IN (125, 700)

┌─my_key─┬─my_value─┐
│ 512000 │      125 │
│ 512001 │      125 │
│    ... |      ... |
└────────┴──────────┘

8192 rows in set. Elapsed: 0.079 sec. Processed 100.00 million rows, 800.10 MB (1.26 billion rows/s., 10.10 GB/s.

では、非常に基本的なスキップ索引を追加します:

ALTER TABLE skip_table ADD INDEX vix my_value TYPE set(100) GRANULARITY 2;

通常、スキップ索引が適用されるのは新たに挿入されたデータのみであるため、索引を追加しただけでは上記のクエリには影響しません。

既存のデータにも索引を適用するには、このステートメントを使用します：

ALTER TABLE skip_table MATERIALIZE INDEX vix;

新たに作成した索引でクエリを再実行します。

SELECT * FROM skip_table WHERE my_value IN (125, 700)

┌─my_key─┬─my_value─┐
│ 512000 │      125 │
│ 512001 │      125 │
│    ... |      ... |
└────────┴──────────┘

8192 rows in set. Elapsed: 0.051 sec. Processed 32.77 thousand rows, 360.45 KB (643.75 thousand rows/s., 7.08 MB/s.)

800メガバイトの1億行を処理する代わりに、ClickHouseが実際に読み取って解析したのは、わずか360キロバイトの32768行だけでした — つまり、各8192行から成る4つのグラニュールです。

これをより視覚的に示すと、my_value が 125 の4096行がどのように読み取られて選択され、その後の行が ディスクから読み取られることなくどのようにスキップされたかは次のとおりです。

クエリ実行時にトレースを有効にすると、スキップ索引の使用状況に関する詳細情報を確認できます。clickhouse-client では、send_logs_level を設定します:

SET send_logs_level='trace';

これは、SQLクエリやテーブルの索引を調整する際に役立つデバッグ情報を提供します。 上記の 例では、デバッグログから、スキップ索引によって2つのグラニュールを除くすべてが除外されたことがわかります。

<Debug> default.skip_table (933d4b2c-8cea-4bf9-8c93-c56e900eefd1) (SelectExecutor): Index `vix` has dropped 6102/6104 granules.

​

スキップ索引の種類

​

minmax

この軽量な索引タイプは、パラメータを必要としません。各ブロックについて、索引式の最小値と最大値を格納します (式がタプルの場合は、タプル要素の各メンバーの値を個別に格納します) 。このタイプは、値に対して緩やかに ソートされる傾向があるカラムに適しています。この索引タイプは通常、クエリ処理時に適用するコストが最も低くなります。

このタイプの索引が正しく機能するのは、スカラー式またはタプル式に対してのみです。Array または Map データ型を返す式に索引が適用されることはありません。

​

set

この軽量な索引タイプは、ブロックごとの値セットの max_size という単一のパラメータを受け取ります (0 を指定すると、 個別の値の数は無制限になります) 。このセットには、そのブロック内のすべての値が含まれます (値の数が max_size を超える場合は空になります) 。この索引タイプは、各グラニュールのセット内では低カーディナリティ (つまり値が「ひとかたまりに集まっている」状態) でありながら、全体としてはカーディナリティが高いカラムに適しています。

この索引のコスト、性能、および有効性は、ブロック内のカーディナリティに依存します。各ブロックに多数の一意な値が含まれている場合、大きな索引セットに対してクエリ条件を評価するコストが非常に高くなるか、max_size を超えて索引が空になるため、その索引は適用されません。

​

テキスト

自然言語や自由形式のテキスト検索 (たとえば、大きなテキストカラム内の単語やフレーズを検索する場合) を含むワークロード向けに、ClickHouse は テキスト索引 (真の転置索引) を提供しています。 テキスト索引は、効率的な全文検索セマンティクスとトークン化されたルックアップをサポートします。決定論的なトークン索引付けと優れた性能を備え、hasAnyToken や hasAllTokens などの検索関数に加え、一般的なテキスト検索関数全般も最適化できるため、全文検索クエリにはこれを使用することを推奨します。

詳しくは、テキスト索引のドキュメントをこちらで参照してください。

​

ブルームフィルタの型

Bloom filter は、わずかな偽陽性の可能性と引き換えに、集合への所属を省スペースで判定できるデータ構造です。スキップ索引では、偽陽性は大きな問題になりません。デメリットは不要ないくつかのブロックを読み込むだけだからです。ただし、偽陽性の可能性があるということは、索引対象の式は true になることがある程度見込まれるものである必要があります。そうでないと、有効なデータまでスキップされるおそれがあります。

ブルームフィルタは、多数の離散的な値に対する判定を効率よく処理できるため、判定対象の値を多く生成する条件式に適しています。特に、ブルームフィルタ索引は Array に適用でき、この場合は配列内のすべての値が判定対象になります。また、mapKeys または mapValues 関数を使って keys または values のいずれかを配列に変換することで、Map にも適用できます。

ブルームフィルタに基づくデータスキッピングインデックスの型は 3 つあります。

• 基本的な bloom_filter。0 から 1 の範囲で許容される「偽陽性率」を表す、省略可能な 1 つのパラメータを取ります (未指定の場合は .025 が使用されます) 。

• 特化型の tokenbf_v1 (非推奨)。これは 3 つのパラメータを取り、いずれも使用するブルームフィルタの調整に関係します。(1) フィルタのサイズ (バイト単位。大きいほど偽陽性は減りますが、その分ストレージコストが増えます) 、(2) 適用する hash function の数 (これも多いほど偽陽性を減らせます) 、(3) ブルームフィルタの hash function 用の seed です。これらのパラメータがブルームフィルタの動作にどのように影響するかの詳細は、こちら の計算機を参照してください。 この索引は String、FixedString、Map データ型でのみ動作します。入力式は、英数字以外の文字で区切られた文字列に分割されます。たとえば、カラム値が This is a candidate for a "full text" search の場合、This is a candidate for full text search という token を含みます。これは、LIKE、EQUALS、IN、hasToken() など、長い文字列内の単語やその他の値を検索する用途を想定しています。たとえば、自由形式のアプリケーションログ行が入ったカラムから、少数のクラス名や行番号を検索するような用途が考えられます。

• 特化型の ngrambf_v1 (非推奨)。この索引は token 索引と同様に機能します。Bloom filter の設定の前に、追加で 1 つのパラメータ、つまり索引付けする ngram のサイズを取ります。ngram とは、任意の文字からなる長さ n の文字列です。したがって、A short string という文字列は、ngram サイズを 4 にすると次のように索引付けされます。

  'A sh', ' sho', 'shor', 'hort', 'ort ', 'rt s', 't st', ' str', 'stri', 'trin', 'ring'
  

この索引は、テキスト検索、特に中国語のように単語の区切りがない言語の検索にも有用です。

全文検索の workload では、非推奨の tokenbf_v1 または ngrambf_v1 索引ではなく、専用の テキスト索引 (Text index for full-text search を参照) の使用を推奨します。 テキスト索引は真の転置索引を提供し、token ベースのブルームフィルタ索引と比べて、検索性能が高く、動作がより予測しやすく、柔軟性にも優れています。

​

スキップ索引と関数

データスキップ索引の主な目的は、よく使われるクエリで分析対象となるデータ量を抑えることです。ClickHouse のデータは分析用途が中心であるため、この種のクエリのパターンには多くの場合、関数式が含まれます。そのため、スキップ索引が効果的に機能するには、一般的な関数と正しく連携できる必要があります。これは、次のいずれかの場合に当てはまります。

• データが挿入され、索引が関数式として定義されている場合 (式の結果は索引ファイルに格納されます) 、または
• クエリの処理時に、その式が格納済みの索引値に適用され、ブロックを除外するかどうかが判定される場合。

各タイプのスキップ索引は、索引実装に応じて利用可能な ClickHouse 関数の一部に対して動作します。対応する一覧は こちらにあります。一般に、set 索引と Bloom filter ベースの索引 (set 索引の別種) は、どちらも順序を持たないため、範囲条件には対応しません。これに対して minmax 索引は範囲条件との相性が特によく、範囲が積集合を持つかどうかを非常に高速に判定できます。LIKE、startsWith、endsWith、hasToken といった部分一致関数の有効性は、使用する索引の種類、索引式、そしてデータの具体的な形状に依存します。

​

スキップ索引の設定

スキップ索引に適用できる設定は 2 つあります。

• use_skip_indexes (0 または 1。デフォルトは 1)。 すべてのクエリがスキップ索引を効率的に利用できるわけではありません。 特定のフィルタ条件で ほとんどのグラニュールが対象になる可能性が高い場合、データスキッピングインデックスを適用すると不要な、場合によっては大きな、コストが発生します。 どのスキップ索引を使っても 効果が見込めないクエリでは、この値を 0 に設定してください。
• force_data_skipping_indices (索引名のカンマ区切りリスト)。 この設定は、ある種の非効率な クエリを防ぐために使用できます。 スキップ索引を使用しないとテーブルへのクエリのコストが高くなりすぎる場合、この設定に 1 つ以上の索引名を指定すると、 指定した索引を使用しないクエリでは例外が返されます。 これにより、不適切に書かれたクエリが サーバーリソースを消費するのを防げます。

​

スキップ索引のベストプラクティス

スキップ索引は直感的に理解しにくく、特に RDBMS における行ベースのセカンダリ索引や、ドキュメントストアの転置索引に慣れている人にはなおさらです。効果を得るには、ClickHouse のデータスキッピングインデックスによって、索引の計算コストに見合うだけのグラニュールの読み取りを回避できなければなりません。特に重要なのは、索引対象のブロック内にある値が 1 回でも出現すると、そのブロック全体をメモリに読み込んで評価する必要があり、索引のコストだけが無駄に発生してしまう点です。

次のようなデータ分布を考えてみましょう。

プライマリ / ORDER BY キーが timestamp で、visitor_id に索引があるとします。次のクエリを考えてみましょう。

SELECT timestamp, url FROM table WHERE visitor_id = 1001`

この種のデータ分布では、従来の二次索引は非常に有効に機能します。要求された visitor_id を持つ 5 行を見つけるために 32768 行すべてを読む代わりに、二次索引にはその 5 行の位置だけが含まれるため、読み取るのは ディスク上のその 5 行だけで済みます。一方、ClickHouse のデータスキッピングインデックスでは、まったく逆になります。 スキップ索引の種類に関係なく、visitor_id カラム内の 32768 個の値すべてが検査されます。

そのため、ClickHouse クエリを高速化しようとして、キーとなる カラムに単純に索引を追加すればよいと考えるのは、多くの場合誤りです。この高度な機能は、主キーの変更 (How to Pick a Primary Key を参照) 、projections の使用、または materialized view の使用といった他の選択肢を検討したうえでのみ使うべきです。データスキッピングインデックスが適切な場合であっても、索引とテーブルの 両方を慎重にチューニングする必要があることが少なくありません。

ほとんどの場合、有用なスキップ索引には、主キーと対象となる非主キーカラム/式の間に強い相関が必要です。 相関がない場合 (上の図のように) は、数千個の値から成る ブロック内で少なくとも 1 行がフィルタ条件を満たす可能性が高く、スキップできるブロックはほとんどありません。これに対して、主キーの値の範囲 (たとえば時刻) が 候補となる索引カラムの値 (たとえばテレビ視聴者の年齢) と強く結び付いている場合は、minmax 型の索引 が有効である可能性が高くなります。なお、データ挿入時にこの相関を高められる場合があります。たとえば、 ソート/ORDER BY キーに追加のカラムを含める、あるいは主キーに関連する値が INSERT 時にまとまるように insert を batch 化する方法です。たとえば、 主キーが多数のサイトのイベントを含む timestamp であっても、特定の site_id のイベントをすべて 取り込みプロセスでまとめてグループ化し、一緒に挿入できます。これにより、少数の site id しか含まないグラニュールが多数できるため、 特定の site_id 値で検索する際に多くのブロックをスキップできるようになります。

スキップ索引のもう 1 つの有力な候補は、個々の値がデータ内では比較的スパースな高カーディナリティの式です。たとえば、 API リクエスト内の error code を追跡するオブザーバビリティプラットフォームが考えられます。特定の error code は、データ内ではまれであっても、検索において 特に重要である場合があります。error_code カラムに対する set スキップ索引を使えば、error を含まない 大多数のブロックを読み飛ばせるため、error に焦点を当てたクエリを大幅に改善できます。

最後に、最も重要なベストプラクティスは、とにかく何度もテストすることです。繰り返しになりますが、ドキュメント検索用の b-tree 二次索引や転置索引とは異なり、 データスキッピングインデックスの挙動は簡単には予測できません。これらを table に追加すると、データの取り込み時にも、またさまざまな理由で索引の恩恵を受けないクエリに対しても、 無視できないコストが発生します。必ず実際のデータに近いデータでテストすべきであり、テストには型、granularity サイズ、その他の parameter の違いも 含める必要があります。テストによって、机上の検討だけでは 見えてこないパターンや落とし穴が明らかになることはよくあります。

​

関連ドキュメント

• ベストプラクティスガイド
• データスキッピングインデックスの使用例
• データスキッピングインデックスの操作
• システムテーブルの情報