オブジェクトストレージ向けの高性能な全文検索を構築する

TL;DR

ClickHouse の全文インデックスを、オブジェクトストレージ上でも効率よく動作するように再設計しました。

新しいレイアウトはシーケンシャルアクセスを優先し、インデックス対象のテキスト列をまったく読まずに、多くのクエリにインデックスだけで応答できます。

この記事は、新しい設計を開発したエンジニア自身が執筆した詳細解説です。

オブジェクトストレージ向けに全文検索を見直す #

ClickHouse の全文検索は、列指向の分析データベースに高速でネイティブなテキストインデックスを持ち込むために、いくつかの版を重ねてきました。そのたびに、性能、使いやすさ、クエリエンジンとの統合が向上してきました。

ClickHouse Cloud の登場で、新しい制約が加わりました。

データがローカルディスクではなくオブジェクトストレージに保存されていても、テキストインデックスは同じ高い性能を発揮しなければなりません。

リモートのオブジェクトストレージに対するデータの読み書きは、性能特性が根本的に異なります。ランダムリードや、数バイトの参照を頻繁に繰り返す設計は、規模が大きくなるとボトルネックになります。

私たちは、これらの制約を念頭に置いて新しいテキストインデックスを再設計しました。

この記事では、まず新しいテキストインデックスの内部設計と、全文検索の際にクエリエンジンがそれをどう使うかを説明します。後半では、実装の詳細から離れて、設定と使い方に移ります。

ClickHouse の全文検索の概要と、どのような場面で使うべきかについては、GA アナウンスをご覧ください。

新しいテキストインデックスの設計 #

ClickHouse Cloud のキャッシュに関する以前の記事で述べたように、データがリモートのオブジェクトストレージにある場合、実際のボトルネックは帯域幅ではなくレイテンシです。

オブジェクトストレージは高いスループットを提供しますが、アクセスレイテンシはローカルディスクよりも大幅に高くなります。

従来のテキストインデックスは散在した参照パターンに依存していました。これはローカルディスクでは効率的でしたが、小さく不連続な参照が多数発生してレイテンシが増幅されるため、オブジェクトストレージでは遅くなっていました。

オブジェクトストレージで高い性能を維持するために、シーケンシャルアクセスパターンを優先する形へテキストインデックスを再設計しました。これにより、ローカルディスクでの全文検索の性能を落とすことなく、オブジェクトストレージを効率よく使えます。

この実装を確認するために、関連するインデックスのデータ構造をすべて順に見ていきます。まずは、インデックスがディスク上にどう保存されるかからです。

おさらいとして、ClickHouse はテーブルのデータをデータパートの集まりとしてディスクに保存します。

各データパートには、範囲の絞り込みに使うスパースな主キーインデックスが含まれ、さらに minmax、set、Bloom フィルターといった二次的なデータスキッピングインデックスを含むこともあります。

テキストインデックスは、この 2 番目の分類に属します。他のデータスキッピングインデックスと同様に、テキスト内容の全文検索を高速化したい列ごとに定義します。下の図に示すように、各データパートの中に、列ファイルや主キーインデックスと並べて保存されます。

上の図のように、テキストインデックスは内部的に 3つの主要コンポーネントで構成され、それぞれがパートごとに別ファイルとして保存されます。

① 辞書ファイル(text_idx.dct.idx)
② スパース辞書インデックスファイル(text_idx.idx)
③ ポスティングリストファイル(text_idx.pst.idx)

以降の図では、わかりやすさのためにこのファイル名を使います。

続く節で、各コンポーネントを順に見ていきます。

① オブジェクトストレージ向けの辞書レイアウト #

辞書は、テキストインデックスのうち、インデックス化したすべてのトークンを保存する部分です。各トークンについては、ポスティングリストへの参照も保存します。ポスティングリストは、そのトークンを含むすべての行位置を表します。

以前の版のテキストインデックスでは、辞書は有限状態トランスデューサー(FST)というデータ構造に基づいていました。FST は本質的には、接頭辞と接尾辞を圧縮したトライです。FST はコンパクトに保存でき、ローカル SSD では高速に参照できます。しかし FST は多数の小さなランダムリードにも依存しており、インデックスがオブジェクトストレージに置かれると極めて非効率になります。

そこで、2つの目標を掲げて辞書レイアウトを再設計しました。1つ目は、ランダムリードよりもシーケンシャルアクセスパターンを優先することです。2つ目は、インデックス参照でランダムな参照を完全には避けられない以上、少なくともクエリあたりの回数をできる限り減らすことです。これにより、インデックス化するデータセットが増えても、エンドツーエンドのクエリレイテンシを小さく、予測可能に保てます。

このために、新しいテキストインデックスの辞書はブロックベースのレイアウトを採用しています。トークンをアルファベット順に並べ、dictionary_block_size 件(既定値 512)ずつの固定サイズのブロックにまとめます。

これにより、続く節で説明するように、シーケンシャルリード、効率的な圧縮、ポスティングリストへの高速なアクセスが可能になります。

辞書ブロックのシーケンシャルリード #

下の図は、同じ辞書ファイル(text_idx.dct.idx)内の異なるオフセットに置かれた複数の辞書ブロックを示しています。

各ブロックは、ソート済みトークンの自己完結したかたまりであり、シーケンシャルに読み取れます。

ブロックをシーケンシャルに読むことで、散在したランダムアクセスを避けられ、インデックスファイルがオブジェクトストレージ上にあっても参照を効率的に保てます。

ブロック内のフロントコーディング圧縮 #

ブロックを見ると、連続するトークンが共通の接頭辞を持つことが多いとすぐに気づきます。たとえば「algo」「algorithm」「algorithmic」です。すべてのトークンを完全な文字列で保存するのは無駄です。

シーケンシャルなレイアウトを保ちつつ辞書ブロックをコンパクトにするために、新しい設計ではフロントコーディングでトークンを圧縮します。この圧縮方式では、各ブロックの先頭トークンはそのまま保存します。続くトークンはそれぞれ、直前のトークンと共有する接頭辞の長さと、残りの接尾辞に置き換えます。

フロントコーディングにより、ディスク上のブロックサイズは大幅に小さくなります。

下の図のトークン列は読みやすさのために添えたものです。ディスク上に保存されるのは、符号化した (prefix_length, suffix) の値(紫色で強調)のみです。

辞書ブロック内のポスティングリストオフセット #

テキスト検索では、辞書でトークンを見つけたら、次にそのトークンが現れる行を特定しなければなりません。各トークンの行位置はポスティングリストに保存されています。

そのため、各辞書エントリはポスティングリストファイル(text_idx.pst.idx)内のバイトオフセットを保持しており、ClickHouse はトークンのポスティングリストへ直接ジャンプできます。

この図はデータの構成を概念的に示した簡略版です。実際のポスティングリストの保存には特殊なケースを実装しており、後で詳しく説明します。

ここまで、新しいテキストインデックスを構成する 3つの主要コンポーネントの 1つ目である辞書レイアウトを見てきました。次はスパースインデックスです。これにより ClickHouse は、辞書ファイル全体を走査せずに正しい辞書ブロックをすばやく見つけられます。

② 辞書参照を高速化するスパースインデックス #

数百万のトークンが数千の辞書ブロックに分散している可能性があるため、指定したトークンを含む辞書ブロックをすばやく見つける手段が必要です。

もちろん、すべての辞書ブロックを読み込むか走査する(あるいはその中で二分探索する)こともできますが、それでは許容できないほど遅くなります。

スパースインデックスは、各辞書ブロックの先頭トークンと、辞書ファイル(text_idx.dct.idx)内でのそのブロックのバイトオフセットを記録します。これでこの問題が解決します。

スパースインデックス自体は別ファイル(text_idx.idx)に保存されます。辞書ブロックやポスティングリストと比べてスパースインデックスは非常に小さいため、常にメモリに読み込まれたままになります。

下の図は、スパースインデックスファイル(text_idx.idx)が、辞書ファイル内の異なるオフセットにある辞書ブロックを指している様子を示しています。

ClickHouse の主キーインデックスの仕組みを知っていれば、この設計は見慣れたものでしょう。実際、どちらのインデックスも同じ種類の「スパースインデックス化」を行っています。ブロックごとにエントリポイントを保存し、目当ての近傍までジャンプし、そこからシーケンシャルに走査します。違いは、ここではブロックの中身が行の値ではなく辞書のトークンである点です。

スパースインデックスと辞書ブロックはランダム I/O を最小限に抑え、参照の大部分をシーケンシャルに進められるようにして、ローカルディスクとオブジェクトストレージのどちらでも辞書アクセスを効率的に保ちます。

辞書ブロックとスパースインデックスがそろえば、エンジンはトークンを効率よく特定できます。

次のステップは、トークンが現れる行位置を保存するポスティングリストの読み取りです。

③ ポスティングリスト: トークンから行位置への対応付け #

前の節では、辞書エントリがディスク上のポスティングリストをどう参照するかを、簡略化したレイアウトで示しました。

実際には、ポスティングリストのサイズは大きくばらつきます。データセット内に 1 回か 2 回しか現れないトークンもあれば、数百万行に現れるトークンもあります。

あらゆるサイズのポスティングリストを効率よく表現するために、ClickHouse の新しいテキストインデックスは、ポスティングリストのサイズに応じて異なる表現を使い分けます。

• Roaring Bitmap ポスティングリスト: 行 ID が 12 個を超えるポスティングリストに使用
• VarInt 符号化ポスティングリスト: 行 ID が 7〜12 個のポスティングリストに使用
• 埋め込みポスティングリスト: 行 ID が 6 個以下のポスティングリストに使用

以下で各表現を説明します。

Roaring Bitmap ポスティングリスト(行 ID が 12 個超) #

行 ID が 12 個を超えるポスティングリストは、Roaring Bitmap と呼ばれる形式で保存します。

Roaring Bitmap は圧縮ビットマップの一種で、32 ビット整数の大きな集合を保持しながら、高速な積集合と和集合の演算に対応します。どちらの演算も、複数のポスティングリストを組み合わせる hasAnyTokens() や hasAllTokens() のような SQL 関数にとって重要です。

内部レイアウト

Roaring Bitmap は 32 ビットの整数空間を上位と下位の半分ずつに分割します。上位半分は行 ID の上位 16 ビットに基づき、65,536 通りの値を表します。

下位半分は 3 種類のコンテナのいずれかに保存されます。コンテナは、含まれる行 ID の数に応じて最もコンパクトな内部表現を選びます。

• Array コンテナ: スパースなチャンクに使用
• Bitmap コンテナ: 密なチャンクに使用
• Run-length コンテナ: 連続した並びが多いチャンクに使用

この適応的なレイアウトのおかげで、Roaring Bitmap は内部のデータ分布が大きく異なるポスティングリストを効率よく圧縮でき、集合演算も高速に行えます。

例

これがなぜ重要かを見るために、大きなテキストデータセット内のトークン connect を考えます。connect が行 ID 65,536、65,538、65,539、65,542 と、テーブル全体に散在するさらに数万の行 ID に現れるとします。これらの数値を 32 ビット整数のソート済みの単純な配列として保存すると、1 エントリあたり 4 バイトかかり、50,000 件の一致行を保存するだけで約 200 KB になります。

Roaring Bitmap では、各値の上位 16 ビット(0x0001)がコンテナを識別します。コンテナは、65,536〜131,071 の範囲の行 ID を担当するバケットです。下位 16 ビット(0x0006)は、そのコンテナ内に保存される値です。この例では、4つの行 ID すべてが同じコンテナに入ります。

各コンテナは、含まれる行 ID の分布に基づいて、それぞれ独立に内部レイアウトを選びます。

ディスク上のレイアウト

大きなポスティングリストに対して、Roaring Bitmap は非常にうまく機能します。圧縮率が高く、検索時に複数のポスティングリストの積集合を取るといった効率的なクエリ演算が可能です。

内部的には、Roaring Bitmap のポスティングリストはさらにブロックに分割されます(posting_list_block_size で制御)。各ブロックは、含まれる行 ID の最小値と最大値を記録します。このメタデータにより、クエリエンジンは、他の述語ですでに除外された行範囲に当たるブロックを解凍せずに済み、検索時の無駄な処理を減らせます。

制約

ただし Roaring Bitmap には、必須のメタデータのために無視できない大きさの最小サイズがあります。このオーバーヘッドは大きなポスティングリストでは問題になりませんが、小さなポスティングリストでは無駄になります。自然言語やテキストのデータセットには出現のまれなトークンが数多くあるため、そうしたトークンに特化した表現を導入することが重要になります。ClickHouse の転置インデックスは、このようなケースのために 2つの表現を追加で使います。

VarInt 符号化ポスティングリスト(行 ID が 7〜12 個) #

行 ID が 7〜12 個の小さなポスティングリストについては、テキストインデックスは行 ID を VarInt 圧縮した整数の単純な並びとして保存します。

VarInt は各バイトを、7 ビットのデータ(ペイロード)と 1 ビットの継続ビットに分けます。その結果、128 未満の値は 1 バイト、16,384 未満の値は 2 バイトで済み、以降も同様です。

小さなポスティングリストの行 ID は比較的小さな整数であることが多いため、この VarInt 符号化は平均して非常によく圧縮できます。たとえば、行 ID が 12 個のポスティングリストは、通常わずか数十バイトしか消費しません。

ここで Roaring を使わない理由

こうしたポスティングリストに Roaring を使うのは非効率です。シリアライズした構造には、ヘッダーとコンテナのメタデータのために約 48 バイトの最小サイズがあるからです。したがって、VarInt の単純なリストの方が、より小さく単純な選択肢になります。

埋め込みポスティングリスト(行 ID が 6 個以下) #

テキストインデックスの開発中に、実際のデータセットでは、トークンの種類の大多数はカーディナリティがきわめて低いことがわかりました。私たちは、大規模で性質のまったく異なる 2つのデータセットを調べました。

• 社内のログファイルデータセット。トークンの種類は 217.9 億

• 自然言語のウェブコーパス Fineweb(https://huggingface.co/datasets/HuggingFaceFW/fineweb)。トークンの種類は 255.1 億

  結果は両データセットで一貫していました。

1. 全トークンのうち、それぞれ 94.5% と 90.2% が 6 行以下にしか現れません。
2. トークンのカーディナリティの中央値は、それぞれ 2 と 1 です。
3. カーディナリティが 12 を超えるトークンは、それぞれ全トークンの 3% と 6.1% にすぎません。12 は、それ以下では Roaring Bitmap に固定的なオーバーヘッドが生じるしきい値です。
4. 埋め込みポスティングリストのしきい値 6 はメモリレイアウト上の理由で選んだ値ですが、両データセットで P90 のトークンの 90% を捕捉していました(偶然ですが、経験的にはほぼぴったり一致しています)。

小さなポスティングリストを別に保存するのが無駄な理由

大半のトークンにとって、Roaring Bitmap の完全な仕組み(コンテナのメタデータと、ファイル内の独立したエントリ)は大きなオーバーヘッドになります。要素が 6 個以下のポスティングリストであれば、インデックスはポスティングリストファイルへの書き込みを完全に省略できます。

埋め込みレイアウト

そこで、トークンが現れる行が 6 行以下であれば、ポスティングリストファイルへのバイトオフセットの位置に、行 ID をそのまま辞書エントリへ埋め込みます。その結果、追加の間接参照やディスクアクセスなしにポスティングリスト全体を読み取れます。

小オブジェクト最適化との関係

この考え方は、システムプログラミングでいう小オブジェクト最適化(SSO、Short String Optimization など)から着想を得ています。小オブジェクト最適化では、非常に小さな値を別の場所ではなくインラインで保存します。まれなトークン(自然言語のデータセットではきわめてよく見られます)に対して、この手法は保存のオーバーヘッドと余分な I/O の両方をなくします。

ここまでで、新しいテキストインデックスの 3つの主要データ構造である辞書ブロック、スパースインデックス、ポスティングリストを説明しました。

これらの部品がクエリ実行時にどう連携するかを見る前に、パートのマージへ少し寄り道します。テキストインデックスのレイアウトは、そこでも重要な役割を果たします。

テキストインデックスの効率的なマージ #

先に述べたように、テキストインデックスは各データパートの中に、辞書、スパースインデックス、ポスティングリストの 3つの別ファイルとして保存されます。

ClickHouse はバックグラウンドで小さなデータパートを継続的に大きなパートへマージし、マージ対象パートのすべてのファイルを書き直します。これらのファイルがオブジェクトストレージ上にある場合、マージの性能はアクセスパターンに大きく左右されます。

新しいテキストインデックスのレイアウトは、マージ時の効率的なシーケンシャルアクセスを支えるように設計されています。辞書ブロックはすでにソート順で保存されているため、テキストインデックスをゼロから再構築する必要はありません。代わりに ClickHouse は、テーブルの行データに使うのと同じ単一のマージパスで辞書をマージできます。

マージ中は、両パートの辞書をシーケンシャルに読み取り、交互に組み合わせて新しいソート済み辞書を作ります。ランダム I/O を避けられるため、インデックスファイルがオブジェクトストレージ上にあってもインデックスのマージは効率的です。

下のアニメーションは、2つのデータパートのマージを示しています。説明を絞るために、辞書ファイルのマージだけを示しています。データパートの他のファイルも同じパスでマージされますが、表示は省いています。

上のアニメーションには示していませんが、ポスティングリストファイル(text_idx.pst.idx)内のポスティングリストも同じパスで更新されます。パート本体のマージで生成された行 ID の対応表を使って行番号を付け替えるため、元のテキスト列を再度読む必要はありません。

その結果、テキストインデックスのマージは軽量で、元のテキストデータのサイズではなく、インデックス自体のサイズに比例してスケールします。

同じくアニメーションには示していませんが、スパースインデックスファイル(text_idx.idx)は、マージ後の辞書ブロックからマージ後のパート用に再構築されます。

パートのマージを説明したので、クエリ実行に戻り、検索時に辞書ブロック、スパースインデックス、ポスティングリストがどう連携するかを見ていきます。

クエリエンジンはテキストインデックスをどう使うか #

テキストインデックスを持つ次のテーブルと、

CREATE TABLE docs
(
    `key` UInt64,
    `doc` String,
    INDEX idx(doc) TYPE text(tokenizer = splitByNonAlpha)
)
ENGINE = MergeTree()
ORDER BY key;

次のクエリを考えます。

SELECT count() FROM docs WHERE hasToken(doc, 'clickhouse');

ここでは、トークン clickhouse を検索しています。

このクエリを実行したときに内部で何が起きるかを順に見ていきます。

ステップ 1: 一致する行番号の特定 #

まず、トークン clickhouse を含む辞書ブロックがどれかを知る必要があります。

すべてのブロックをシーケンシャルに走査するのはコストが高すぎます。代わりに、スパースインデックスを使って正しいブロックを見つけます。

スパースインデックスは各ブロックの先頭トークンだけを保持しているため、upper bound(上界)を使った二分探索で候補ブロックを特定します。検索トークン自体はたいていスパースインデックスには現れませんが、upper bound から、そのトークンがインデックス化されていればどのブロックに入るはずかがわかります。

スパースインデックスは比較的小さく、常にメインメモリに置かれています。そのため、二分探索自体はわずか数マイクロ秒で終わります。

下の図では、スパースインデックスの参照が、clickhouse を含む可能性のある辞書ブロックのエントリを返します。そのオフセットから、辞書ファイルのどのブロックを読めばよいかがわかります。

次に、見つかった辞書ブロックをシーケンシャルに読み取り、そのトークンを走査します。

辞書はオブジェクトストレージ上にあるため、ブロックの走査はブロック内の 1 点を参照するのとほぼ同じ速さです。実行時間は、リクエストを発行して結果を受け取るまでのレイテンシに支配されます。

下の図では、スパースインデックスから、辞書ファイル内の候補辞書ブロックのオフセットが得られます。このブロックをシーケンシャルに読み、clickhouse が見つかるまで走査します。

辞書ブロックで clickhouse が見つかったら、対応するポスティングリストをポスティングリストファイルから読み取ります。

下の図では、候補の辞書ブロックから、ポスティングリストファイル内のポスティングリストのオフセットが得られます。そのポスティングリストを取得します。

取得したポスティングリストには、一致する行番号が含まれています。

エンジンは次に、実行時にそれをどう適用するかを決めなければなりません。

ステップ 2: 実行モードの選択 #

インデックス参照は、一致した行の行番号を、データパートの列内のオフセットとして返します。

クエリの形と使われたテキスト検索関数に応じて、ClickHouse はこのオフセットを 3つの方法で適用できます。効率の高い順に並べると次のとおりです。

• エンジンはオフセットから仮想列を構築し、次のいずれかを行います

  • インデックス対象のテキスト列の読み取りを完全に省略する
  • 仮想列で候補集合を絞り込んでから、残った行を検査する

• より複雑な検索パターンでは、従来のスキッピングインデックス評価にフォールバックします。この場合、インデックスは一致を含み得ないグラニュールをスキップするためだけに使われます。

続く 3つの節で、これら 3つの方式を説明します。

ステップ 2A: ダイレクトリードモード #

テキストインデックスは、ClickHouse のスキッピングインデックスの中でも特殊です。そのポスティングリストには、クエリに一致する正確な行番号が含まれます。偽陽性はなく、追加のフィルタリングも不要です。

一致する行がすでに正確にわかっているので、通常のフィルタリングステップを省略して、行レベルのマスキングへ直接進めます。

仮想列による行レベルのマスキング

ポスティングリスト内の行 ID を使って仮想的なブール列(クエリの実行中だけ存在する内部列)を構築し、一致する行をすべて 1、それ以外の行をすべて 0 に設定します。

PREWHERE へのクエリ書き換え

ClickHouse は次に、この仮想列でフィルタリングするようクエリを自動的に書き換えます。たとえば、クエリ

SELECT count() FROM docs WHERE hasToken(doc, 'clickhouse');

は、次のように書き換えられます。

SELECT count() FROM docs PREWHERE _text_index_virtual_idx = 1;

PREWHERE の評価

PREWHERE 句の条件は、他の WHERE 条件より先に評価されます。次の処理ステップ(WHERE)へ渡るのは一致した行だけです。一致しない行をできる限り早い段階で取り除くので、I/O も、後続の演算子が処理する行数も減ります。

複数トークン

クエリに複数のトークンが含まれる場合(複数の hasToken 条件や、複数トークンを渡す hasAnyTokens/hasAllTokens 呼び出し)、トークンごとに同じ参照処理を独立に行い、それぞれのポスティングリストを得ます。その後、これらのポスティングリストに対するビット演算で仮想列を埋めます。連言条件(すべてのトークンが一致する必要がある)には AND、選言条件(いずれかのトークンが一致すればよい)には OR を使います。これにより行のフィルタリングは高速に保たれ、行ごとの文字列評価を避けられます。

ダイレクトリードモードと呼ぶ理由

ここまで説明した処理は、ClickHouse 内部で「ダイレクトリード」モードと呼ばれています。テキストインデックスを活用する最も自然で、最も効率的な方法です。

インデックス対象のテキスト列はまったく読まれません。クエリは、テキストインデックスに保存された行レベルの情報だけで応答されます。

制約と対応関数

ダイレクトリードが安全なのは、インデックスのトークンが検索値と正確に対応し、偽陽性が起こり得ない場合に限られます。これに該当するのが、SQL 関数の hasToken、hasAnyTokens、hasAllTokens です。

ステップ 2B: ヒント付きダイレクトリード #

一部の述語では、通常のダイレクトリードはできません。たとえば、次のクエリを考えます。

SELECT col1, col2 FROM table WHERE col3 LIKE '%clickhouse performance%'

インデックスをヒントとして使う

ここでテキストインデックスを使うために、ClickHouse は検索パターンをトークン化し、トークン clickhouse と performance をインデックスで参照します。しかし、両方のトークンを含む行がパターン全体に一致するとは限りません。2つの単語が離れて現れる(clickhouse has great performance)ことも、順序が異なる(the performance of clickhouse)こともあります。つまり、インデックスだけに頼ると偽陽性が生じ得ます。それでも、インデックスを「ヒント」として使い、clickhouse と performance を両方そろえて含んではいない行を除外することはできます。

パート内のほとんどの行が両方のトークンをそろえて含んではいないなら、コストの高い LIKE 評価を列に対して実行する前に、インデックスで候補の大部分を除外できます。

ヒント付きダイレクトリードモード

これを「ヒント付きダイレクトリード」モードと呼びます。仮想列で候補集合を絞り込み、その後、残った行に対して元の LIKE 述語を評価します。

ポスティングリストの読み取りコスト

この工夫に伴う課題の 1つは、ポスティングリストの読み取りにもコストがかかることです。シークと解凍が必要になります。たとえば、トークン「clickhouse」が行の 80% に現れるなら、インデックスで除外できる行は比較的少ないのに、全行分の I/O はそのままかかります。この場合は、インデックスをまったく読まずに LIKE 述語を列に対して直接評価する方が有利です。

選択率に基づく判断

この判断のために、ClickHouse は辞書からすでに得られるトークンごとのカーディナリティを使い、ポスティングリストの本体を一切読まずに一致集合のカーディナリティを推定します。推定値が text_index_hint_max_selectivity × N(既定値はパート内の全行数の 20%)以下なら、ヒントを採用します。ポスティングリストを読んで仮想列を埋め、LIKE の検査が走る前に一致しない行を除外します。推定値がしきい値を超える場合は、ヒントを捨てます。仮想列はすべて 1 にし、インデックスの I/O は発生させず、元の述語だけでフィルタリングします。

オブザーバビリティ

この 2つの結果はプロファイルイベント TextIndexUseHint と TextIndexDiscardHint として公開され、クエリログで確認できます。これにより、あるクエリでインデックスが寄与しているかどうかを把握できます。

対応関数

対応する SQL 関数: like、startsWith、endsWith、mapContainsKeyLike/ValueLike

ステップ 2C: スキッピングインデックスモード #

述語がダイレクトリード最適化もヒントモードも活用できない場合、オプティマイザーはその述語を、ClickHouse のスキッピングインデックス基盤を使うフォールバックの読み取りモードに割り当てます。述語は列に対して通常どおり評価されます。

この手法は、match、multiSearchAll、multiSearchAny のようなより複雑なパターンに使われます。

たとえば、次のクエリを考えます。

SELECT col1, col2 FROM table WHERE match(col3, 'connect.*timeout')

このような正規表現の述語は、信頼できるトークンの集合へ分解できません。このパターンは順序と近接の制約を表しており、インデックスにはそれを検証する手段がないからです。オプティマイザーはこれを従来の読み取りモードで評価します。

テキストインデックスはグラニュール単位で使われます。各グラニュールがパターンを満たし得るトークンを含むかを調べ、含まないグラニュールをスキップします。

ダイレクトリードより遅い理由

この粗いフィルターを通過したすべてのグラニュールについて、エンジンは col3 を完全に解凍し、実際の文字列データに対して正規表現を評価するために 1 行ずつ走査しなければなりません。テキスト列は一般に幅が広く解凍コストが高いうえ、ありふれた単語に一致するパターンでは大半のグラニュールが候補として残り得ます。インデックスはグラニュール境界で I/O を減らしますが、支配的なコスト(列の解凍と走査)は残ります。

対応する述語に対してダイレクトリードが埋めるのは、まさにこの差です。インデックスがすでに知っている一致を列の解凍で確かめ直すのではなく、ポスティングリストの結果をそのまま使います。

ここまでで、テキストインデックスの内部設計と、それに対してクエリがどう実行されるかを説明しました。

次の節では、実装の詳細から離れて、設定と使い方に移ります。

テキストインデックスの定義 #

以下の詳細に入る前に実践的な概要を手早くつかみたい方は、下の短い動画をご覧ください。ClickHouse でテキストインデックスを作成して使う手順を示しています。

テキストインデックスの作成方法を見る前に、まずどの列型をインデックス化できるかを確認します。

テキストインデックスは、String 型と FixedString 型の列、および文字列を含む Array 列と Map 列に定義できます。

Nullable と LowCardinality の文字列にも対応しており、前述のデータ型はすべて自由に組み合わせられます。たとえば Array(Nullable(FixedString)) です。

では、テキストインデックスの作成方法を見ていきます。

テキストインデックスの作成 #

テーブルにインデックスを追加する方法は 2つあります。CREATE TABLE クエリの一部としてテーブル作成時に追加する方法と、既存のテーブルに ALTER クエリを実行する方法です。インデックスのパラメーターはどちらの方法でも同じです。詳細はドキュメントを参照してください。

構文:

CREATE/ALTER TABLE 
...
   INDEX text_idx(str) TYPE text(
                               -- Mandatory parameters:
                               tokenizer = splitByNonAlpha
                                           | splitByString[(S)]
                                           | ngrams[(N)]
                                           | sparseGrams[(min_length[, max_length[, min_cutoff_length]])]
                                           | array
                               -- Optional parameters:
                               [, preprocessor = expression(str)]
                               -- See documentation for optional advanced parameters
				    ...
                           )
...

例:

CREATE TABLE my_table
(
   key UInt64,
   str String,
   INDEX text_idx(str) TYPE text(tokenizer = ‘splitByNonAlpha’,
preprocessor = lower(str))
)
ENGINE = MergeTree
ORDER BY key

これにより作成されるテキストインデックスは、まず ‘str’ 列に挿入された文字列を小文字化し、次に英数字以外の文字で分割し、上で説明した検索に最適化されたテキストインデックス構造に保存します。たとえば ‘HeLlo my1!!!NAME&is,234234’ は [‘hello’, ‘my1’, ‘name’, ‘is’, ‘234234’] に分割され、これらのトークンを高速に検索できるようになります。

検索を行う前に、まずインデックスのパラメーター、特にトークナイザーとプリプロセッサーを見ていきます。

インデックスのパラメーターとトークン化 #

トークン化と前処理は、テキストインデックスを他のインデックスから分ける 2つの重要な要素で、ノイズの多いテキストデータでも簡単かつ高速に検索できるようにします。2つを組み合わせると、INSERT 時に強力なデータ変換を自動で行えます。たとえば cafe を検索して ‘cafe’、‘café’、‘Café’、‘CAFÉ’ などに一致させる、直感的な検索が実現できます。

詳しく見ていきます。

前処理 #

プリプロセッサーは、トークン化の前に入力列に対して実行されます。インデックス作成時に入力列へ直接適用する関数(例: INDEX idx(lower(col)))とは異なり、プリプロセッサーの式は、同じインデックス対象列に対して専用のテキスト検索関数 hasToken、hasAllTokens、hasAnyTokens を実行したときに、その入力にも自動で適用されます。ClickHouse の豊富な文字列関数と組み合わせれば、テキストの小文字化、アクセント記号の除去、HTML の処理、UTF8 正規化の適用などを行える強力な前処理パイプラインが得られます。

プリプロセッサーの構文は次のとおりです。

preprocessor = expression(<column-name>)

補足:

• expression() は必要に応じて単純にも複雑にもでき、任意の数の関数を入れ子にできます(ただし、挿入される各行に対して実行される点は念頭に置いてください)。
• 式に含まれる関数は必ず決定的でなければなりません。
• <column-name> はインデックス定義と一致していなければなりません。つまり、インデックスを INDEX <idx-name>(lower(col1)) と定義したなら、プリプロセッサーの式も lower(col1) に対して呼び出す必要があります。この一致は ClickHouse が強制します。

例 #

シナリオ 1: 入力データは人間が書いたテキストで、大文字と小文字が混在し、句読点を含みます。インデックスはテキストを小文字化し、検索時に大文字小文字を区別しない一致を可能にします。

preprocessor = lower(col)

Input:       'Hello World! My_Name IS John123'
Preprocessed: 'hello world! my_name is john123'

シナリオ 2: 入力データは複数行の文字列を含みますが、検索に関係するのは最初の行だけです。

preprocessor = substringIndex(col, '\n', 1)

Input:       'Hello World\nSecond Line\nThird Line'
Preprocessed: 'Hello World'

シナリオ 3: 入力データは HTML 文字列で構成されます。プリプロセッサーでまず HTML 要素を除去(空白に置換)し、その結果を小文字化します。

preprocessor = lower(extractTextFromHTML(col))

Input: 'Hello WorldMy ,[object Object], IS Sarah456'
Preprocessed: 'hello world my name is sarah456'

シナリオ 4: 入力データは大文字小文字が混在し、アクセント記号付きのテキスト(フランス語、ドイツ語など)を含みます。まずテキストにケースフォールディングを適用し、次にその結果からダイアクリティカルマーク(アクセント記号)を取り除きます。

preprocessor = removeDiacriticsUTF8(caseFoldUTF8(col))

Input:       'Héllo Wörld ÑOÑO Ångström'
Preprocessed: 'hello world nono angstrom'

前処理を確認したので、次はトークン化を見ていきます。トークン化は、入力テキストをインデックス化のためにどうトークンへ分割するかを定義します。

トークン化 #

これがパズルの最後のピースです。トークナイザーは、列の各行をどうトークンへ分割するかを指定します。どのクエリがインデックスに一致し、どのクエリが一致しないかに影響するため、これは重要な決定です。たとえば、空白でデータを分割するインデックスは単語の一部には一致しません(‘caf’ は ‘cafe’ に一致しません)が、ngram 長 3 の ngram トークナイザーを使うインデックスでは、‘caf’ が ‘cafe’ に一致します。

トークナイザーには、大きく分けていくつかの種類があります。

splitBy 系トークナイザー #

‘splitByNonAlpha’ と ‘splitByString’ トークナイザーは、その名前のとおり、入力を英数字以外の文字、または独自の区切り文字で分割します。製品レビューのような大半の自然言語テキストや、一貫した区切り文字を持つドメイン固有の文字列の分割に役立ちます。

例:

-- splitByNonAlpha
‘hello my1!!!name&is,234234’ -> [‘hello’, ‘my1’, ‘name’, ‘is’, ‘234234’]

-- splitByString with default ' ' separator
'hello my name is John' -> ['hello', 'my', 'name', 'is', 'John']

-- splitByString with custom separators [', ', '; ', '\n']
'apples, oranges; bananas\npears' -> ['apples', 'oranges', 'bananas', 'pears']

-- splitting csv data (custom separator ',')
'hello,world,foo,bar' -> ['hello', 'world', 'foo', 'bar']

*-gram 系トークナイザー #

‘ngrams’ と ‘sparseGrams’ トークナイザーは、文字列をそれぞれ固定長と可変長のトークンに分割します。‘ngrams’ トークナイザーの ngram 長は、1〜8 の整数を省略可能なパラメーターとして指定できます(例: tokenizer = ngrams(3))。明示しない場合の既定の ngram サイズは 3 です。sparseGrams 関数は特殊なアルゴリズムを使い、min_ngram_length と max_ngram_length パラメーターで制御される可変長の ngram を出力します。詳細は sparseGrams 関数のドキュメントを参照してください。

例:

-- ngrams (default size 3)
'hello' -> ['hel', 'ell', 'llo']

-- ngrams (size 4)
'hello' -> ['hell', 'ello']

-- sparseGrams (default min_length=3, max_length=100)
'hello' -> ['hel', 'hell', 'hello', 'ell', 'ello', 'llo']

その他のトークナイザー #

array トークナイザーはトークン化を行いません。つまり、各行の値をそのまま 1つのトークンとして扱います(array 関数を参照)。

'hello my name is John' -> ['hello my name is John']

近日提供予定の unicodeWord トークナイザーは、ASCII 文字を一貫した既定の方法で分割し、非 ASCII の Unicode 文字はそれぞれ 1 文字ずつ独立したトークンに分割します。これにより、中国語、日本語、韓国語などの空白で区切られない言語に対する基本的なトークン化に対応します。

'Hello世界' -> ['Hello', '世', '界']

利用可能なトークナイザーはすべて system.tokenizers に一覧されます。ただし、この一覧には現在非推奨の Bloom フィルターインデックス tokenbf_v1 と ngrambf_v1 も含まれています。これらは、テキストインデックスに比べて汎用性と性能が低く、使いにくいため、もう推奨されません。

インデックスの準備ができたので、検索クエリでの使い方を見ていきます。

クエリでテキストインデックスを使う #

お待ちかねの部分です。列にインデックスを設定できたので、データを投入してテキスト検索を試してみます。

=、IN、LIKE といった一般的な文字列検索関数(完全な一覧は後述)も既定でテキストインデックスを活用しますが、最良の結果を得るには、新しいテキスト検索関数 hasAnyTokens と hasAllTokens の使用を推奨します。

推奨の検索関数を使う #

関数 hasAnyTokens と hasAllTokens は、それぞれ指定したトークンのいずれか、またはすべてに一致します。これらの関数はテキストインデックス専用に作られており、維持すべき従来の挙動がないため、プリプロセッサーなど新しいテキストインデックスの機能をすべて既定で利用できます。

この 2つの関数は、検索トークンを文字列または処理済みトークンの配列として受け取ります。文字列の場合は、インデックス対象列と同じプリプロセッサーとトークナイザーで前処理とトークン化が行われます。配列の場合は、検索前に前処理もトークン化も適用されません。

例: トークン検索 #

テーブルとインデックスを作成し、データを投入します。

CREATE TABLE articles
(
    key    UInt64,
    str    String,
    INDEX  text_idx(str) TYPE text(tokenizer = 'splitByNonAlpha', preprocessor = lower(str))
)
ENGINE = MergeTree
ORDER BY key;

INSERT INTO articles VALUES
    (1, 'ClickHouse is FAST'),
    (2, 'fast cars and SLOW trains'),
    (3, 'The Quick Brown Fox'),
    (4, 'CLICKHOUSE is Scalable');

hasAny/AllTokens に文字列を入力として渡すと、検索前に前処理とトークン化が適用されます。

SELECT key, str
FROM articles
WHERE hasAnyTokens(str, 'ClickHouse');

-- Result:
-- ┌─key─┬─str───────────────────┐
-- │   1 │ ClickHouse is FAST    │
-- │   4 │ CLICKHOUSE is Scalable│
-- └─────┴───────────────────────┘

SELECT key, str
FROM articles
WHERE hasAllTokens(str, 'clickhouse FaSt');

-- Result:
-- ┌─key─┬─str────────────────┐
-- │   1 │ ClickHouse is FAST │
-- └─────┴────────────────────┘

配列オーバーロードを使う場合、トークンは前処理もトークン化も行われず、配列内の文字列をそのまま使って検索します。

-- Notice that while 'slow' matches (since 'SLOW' was stored as 'slow' in the index), 'FAST' in row 1 does not match, despite matching the un-pre-processed text in the column, since it was stored in the index as 'fast' and 'FAST' != 'fast'.
SELECT key, str
FROM articles
WHERE hasAnyTokens(str, ['FAST', 'slow']);

-- Result:
-- ┌─key─┬─str───────────────────────┐
-- │   2 │ fast cars and SLOW trains │
-- └─────┴───────────────────────────┘

-- The below example only matches because the format of the input tokens is the same as that of the preprocessed and tokenized index rows.
SELECT key, str
FROM articles
WHERE hasAllTokens(str, ['quick', 'fox']);

-- Result:
-- ┌─key─┬─str─────────────────┐
-- │   3 │ The Quick Brown Fox │
-- └─────┴─────────────────────┘

上の例の fiddle リンクはこちらです: https://fiddle.clickhouse.com/6bde1e09-4ef7-41f6-844f-7c2386a48399

文字列として渡す場合、検索トークンは元の列のテキストと同じ形式である必要はありません。これにより、大文字小文字やアクセント記号を区別しない検索や、タグを気にせずに HTML を検索するなど、多くの柔軟な検索ができます。しかも元のデータを変更する必要はなく、データは元の形式のまま返されます。

例: 部分一致 #

ngrams トークナイザーは、インデックス作成時にテキストを重なり合う文字の並びへ分割し、単語の一部や部分文字列での一致を可能にします。専門用語、製品名、識別子など、ユーザーが単語の一部しか知らない可能性がある対象の検索に特に有用です。

テーブルとインデックスを作成し、データを投入します。

CREATE TABLE packages
(
    key    UInt64,
    str    String,
    INDEX  text_idx(str) TYPE text(tokenizer = 'ngrams', preprocessor = lower(str))
)
ENGINE = MergeTree
ORDER BY key;
INSERT INTO packages VALUES
    (1, 'ClickHouse - fast OLAP database'),
    (2, 'PostgreSQL - advanced relational database'),
    (3, 'Elasticsearch - distributed search engine'),
    (4, 'ClickHouse Cloud - serverless ClickHouse');

単語の一部を含む行を検索します。'elastic' は 'Elasticsearch' に一致し、'house' は 'ClickHouse' を含む両方の行に一致します。

SELECT key, str
FROM packages
WHERE hasAnyTokens(str, 'elastic house');
-- Result:
-- ┌─key─┬─str───────────────────────────────────────┐
-- │   1 │ ClickHouse - fast OLAP database           │
-- │   3 │ Elasticsearch - distributed search engine │
-- │   4 │ ClickHouse Cloud - serverless ClickHouse  │
-- └─────┴───────────────────────────────────────────┘

hasAllTokens を使い、複数の部分トークンがすべて含まれることを要求します。

SELECT key, str
FROM packages
WHERE hasAllTokens(str, 'postgres sql');
-- Result:
-- ┌─key─┬─str─────────────────────────────────────────┐
-- │   2 │ PostgreSQL - advanced relational database   │
-- └─────┴─────────────────────────────────────────────┘

ngrams インデックスは splitByNonAlpha のような単語ベースのインデックスより大きく、インデックス走査の段階で偽陽性が多くなることがあります(ただしクエリ結果は常に正確です)。既定の選択肢としてではなく、単語の部分一致が本当に必要な場合に使うのが最適です。

例: 配列データ #

array トークナイザーは、すでに Array(String) 型である列に自然に適合します。配列の各要素が 1つのトークンになり、プリプロセッサーは不要です。きちんと配列として保存されたタグ形式のデータに最適で、'machine learning' や 'distributed systems' のような複数語のタグを 1つのトークンとして保持できる点が重要です。splitByNonAlpha のような空白ベースのトークナイザーでは、これらは分割されてしまいます。

テーブルとインデックスを作成し、データを投入します。

CREATE TABLE job_listings
(
    key  UInt64,
    tags Array(String),
    INDEX text_idx(tags) TYPE text(tokenizer = 'array')
)
ENGINE = MergeTree
ORDER BY key;
INSERT INTO job_listings VALUES
    (1, ['rust', 'distributed systems', 'database']),
    (2, ['golang', 'machine learning', 'distributed systems']),
    (3, ['rust', 'machine learning', 'data engineering']),
    (4, ['python', 'data engineering', 'database']);

hasAnyTokens を使い、指定したタグのいずれかが付いた求人を探します。

SELECT key, tags
FROM job_listings
WHERE hasAnyTokens(tags, ['rust', 'golang']);

1-- Result:
2-- ┌─key─┬─tags───────────────────────────────────────────────┐
3-- │   1 │ ['rust','distributed systems','database']          │
4-- │   2 │ ['golang','machine learning','distributed systems']│
5-- │   3 │ ['rust','machine learning','data engineering'].    │
6-- └─────┴────────────────────────────────────────────────────┘

hasAllTokens を使い、指定したタグがすべて付いている求人を探します。

SELECT key, tags
FROM job_listings
WHERE hasAllTokens(tags, ['machine learning', 'distributed systems']);

1-- Result:
2-- ┌─key─┬─tags───────────────────────────────────────────────┐
3-- │   2 │ ['golang','machine learning','distributed systems']│
4-- └─────┴────────────────────────────────────────────────────┘

タグはすでに配列として適切に構造化されているため、ここでは hasAnyTokens と hasAllTokens の配列オーバーロードが自然な選択です。検索トークンは配列のまま渡すので、前処理もトークン化も行わず、インデックス化された要素と厳密に照合します。ただし、検索トークンの大文字小文字には注意してください。列データにまったく前処理をしていないため、入力と同じ大文字小文字のトークンだけが一致します。データがすでに小文字化されているとわかっていれば問題ありませんが、その場合も検索側のタグを小文字にそろえる必要があります。

上の例を見て、データがすでに配列でトークン化済みなら、なぜわざわざテキストインデックスを付けるのか、という疑問が浮かぶかもしれません。答えはもちろん性能です。以下は、1,000 万行という比較的小さなテーブルにテキストインデックスを追加して得られた高速化の例です。

-- Create table
CREATE TABLE job_listings
(
    `key` UInt64,
    `tags` Array(String)
)
ENGINE = MergeTree
ORDER BY key;

-- Insert 10 million rows of random arrays of 5 strings
INSERT INTO job_listings SELECT
    number,
    arrayMap(x -> (['rust', 'distributed systems', 'database', 'golang', 'machine learning', 'data engineering', 'python'][(rand((number * 7) + x) % 7) + 1]), range(5))
FROM numbers(10000000);

10000000 rows in set. Elapsed: 13.501 sec. Processed 10.00 million rows, 80.00 MB (740.71 thousand rows/s., 5.93 MB/s.)
Peak memory usage: 383.27 MiB.

-- Search without an index
SELECT count()
FROM job_listings
WHERE has(tags, 'machine learning');

   ┌─count()─┐
1. │ 5373152 │ -- 5.37 million
   └─────────┘

1 row in set. Elapsed: 0.198 sec. Processed 10.00 million rows, 1.02 GB (50.49 million rows/s., 5.13 GB/s.)
Peak memory usage: 50.27 MiB.

-- Add an index using ALTER TABLE
ALTER TABLE job_listings
    (ADD INDEX text_idx tags TYPE text(tokenizer = 'array') GRANULARITY 100000000);

-- Materialize the index on existing data, this takes a while but is a one-time op
ALTER TABLE job_listings
    (MATERIALIZE INDEX text_idx)
SETTINGS mutations_sync = 2;

-- Search with the index, achieving a speedup of more than 7x!
SELECT count()
FROM job_listings
WHERE hasAllTokens(tags, ['machine learning']);

   ┌─count()─┐
1. │ 5373152 │ -- 5.37 million
   └─────────┘

1 row in set. Elapsed: 0.027 sec. Processed 10.00 million rows, 10.00 MB (368.23 million rows/s., 368.23 MB/s.)
Peak memory usage: 5.42 MiB.

その他の対応関数 #

hasAnyTokens と hasAllTokens 以外にも、テキストインデックスは多くの関数を高速化します。ただし、これらはインデックスより前から存在する関数であり、プリプロセッサーの式には対応していません。

• =: 値全体の完全一致。array トークナイザーでのみ有用
• IN: 上と同じだが、複数の値に対応
• LIKE / match: パターン一致。splitByNonAlpha、ngrams、sparseGrams でのみ機能し、パターンから完全なトークンを抽出できる場合に限る(例: '%clickhouse%' ではなく '% clickhouse %'。'%word1 word2 word3%' のクエリは、インデックスで 'word2' を検索し、パターンの残りについては一致した行に対する総当たり検索にフォールバックする)
• startsWith / endsWith: LIKE と同様のトークン抽出の要件がある。関数が単語全体を抽出できればインデックスの恩恵を受ける。たとえば startsWith(col, word1, word2) はインデックスで word1 を検索し、パターンの残りは総当たり検索にフォールバックする。一方、startsWith(col, word1 word2)(余分な空白に注意)は両方の単語にインデックスを使う
• hasToken / hasTokenOrNull: トークン化済みの単一トークンに一致。検索語をトークン化せず、プリプロセッサーにも対応しない
• has: Array(String) 列内の単一トークンに一致
• mapContains / mapContainsKey: マップのキーに対して一致。mapKeys(map) に対するインデックスが必要
• mapContainsValue: マップの値に対して一致。mapValues(map) に対するインデックスが必要
• mapContainsKeyLike / mapContainsValueLike: マップのキー/値に対するパターン一致
• map['key'] = value: mapKeys または mapValues に対して定義されたインデックスがあれば使用される

完全な詳細はドキュメントを参照してください。関数と、それぞれが対応するインデックスの一覧はこのページにあります。否定形の関数(!=、NOT IN、NOT LIKE)はテキストインデックスに対応していません。テキストインデックスは、テーブルに存在する単語とそのポスティングリストしか記録していないためです。

現在の機能を説明したので、テキストインデックスの今後を見ていきます。

今後の予定 #

まだ終わりではありません。現在は、JSON 列のインデックス化、LIKE と正規表現パターンのより高速な評価、テキスト処理の改善、そしてフレーズ検索に取り組んでいます。フレーズ検索では、インデックスはトークンが行に現れるかどうかだけでなく、行内のどこに現れるかも把握します。

今後の予定を確認したところで、新しいテキストインデックスがすでに実現していることと、それが ClickHouse Cloud のユーザーにとって何を意味するかを見ていきます。

ClickHouse Cloud のユーザーにとっての意味 #

複数回の改良と大規模な性能改善を経て、ClickHouse のテキストインデックスは、データがローカルディスクにあってもオブジェクトストレージにあっても、同じ高性能な全文検索を実現するようになりました。

新しいインデックスレイアウトはシーケンシャルアクセスパターンを優先し、多くの述語を、インデックス対象のテキスト列をディスクから読まずにインデックスだけで解決できます。

ClickHouse Cloud では、新しいインデックスは他の大規模ワークロードを支えるアーキテクチャの恩恵をそのまま受けられます。並列レプリカは全文検索クエリを多数のノードへ分散し、分散キャッシュはホットなインデックスデータをコンピュートの近くに保持し、共有オブジェクトストレージによって、すべてのノードがデータを再配置することなく同じインデックスファイルにアクセスできます。

その結果、全文検索は ClickHouse Cloud の他の部分と同じようにスケールします。ノードを追加すれば、クエリは速くなります。

次回のベンチマーク記事もご期待ください。新しいテキストインデックスを従来のテキスト検索エンジンと比較し、テキスト中心のワークロードで以前の Bloom フィルターベースの手法を置き換える理由を示します。