PolarDB:IMCI における全文検索機能の分析

インメモリー列指向インデックスは、RBM (Roaring Bitmaps) アルゴリズムを使用してポスティングリスト (つまり、ドキュメント ID のセット) を圧縮および計算します。

RBM の実装は CRoaring ライブラリに基づいており、データ密度に応じてストレージ戦略を動的に選択します：

• ポスティングリスト内のドキュメント ID の数が所定のしきい値より小さい場合、ストレージには std::array が使用されます。

• 数がしきい値を超えると、ストレージは roaring::Roaring64Map 型に切り替わり、高い圧縮率を維持しながら大規模なスパースまたは密なデータを処理します。

パフォーマンス特性：

• インデックス構築中に O(logN) の計算量での検索をサポートします。

• 積集合や和集合などの集合演算に対する SIMD 命令アクセラレーションをサポートします。

• データがディスクに書き込まれる際の領域再編成をサポートし、断片化を削減します。

• クエリ中の高速フィルタリングとイテレータ最適化のために、minimum/maximum 値の使用をサポートします。

インメモリー列指向インデックスは、時間効率と空間効率のバランスを取るために、有限状態トランスデューサー (FST) アルゴリズムを使用してターム辞書を構築します。

• 空間効率：タームの共通のプレフィックスとサフィックスを共有することで、ストレージ領域を効果的に圧縮します。

• 時間効率：ターム検索の時間計算量は O(L) です。ここで L はタームの長さです。

たとえば、ターム China、Chinese、love がこの順序で挿入され、それらのポスティングリストのアドレスオフセットが 5、10、15 であると仮定します。構築される辞書は次の図のようになります。この図は、FST が共通のプレフィックスとサフィックスを共有して領域を節約するだけでなく、各遷移に一意の関連値が保証されることを示しています。クエリは初期状態 0 から始まり、タームの各文字について、その文字の出力エッジがあるかを確認します。エッジが存在する場合、クエリは関連値を累積します。そうでない場合、クエリは現在の状態が最終状態であるかを確認します。たとえば、Chinese は 15 の関連値を累積し、その最後の文字が最終状態であるため、そのタームは辞書に存在することがわかります。さらに、FST のプレフィックス計算は文字ベースではなくバイトベースであるため、UTF-8 などのエンコーディングもサポートします。

PolarDB のインメモリー列指向インデックスの全文検索インデックスが SPIMI で構築される際、インメモリー列指向インデックスはターゲット列の列ストアデータを継続的に読み取り、各行をトークン化してタームのセットを取得し、各タームとそれに対応する行番号をハッシュテーブルに追加しながらメモリ使用量を累積します。メモリ使用量がセグメントサイズのしきい値を超えると、インメモリー列指向インデックスはハッシュテーブル内のタームとポスティングリストから辞書を構築し、メモリをリセットして、すべての列ストアデータが処理されるまで次の行の処理に進みます。ハッシュテーブル (std::unordered_map) から辞書 (FST) を構築する主なプロセスは次のとおりです：まず、ハッシュテーブルをターム (キー) でソートします。次に、ハッシュテーブル内のすべてのポスティングリストを順にディスクにシリアライズし、ディスク上の相対オフセットアドレスを記録します。その後、各タームとそのタームのポスティングリストのオフセットアドレスを FST アルゴリズムに順に追加して辞書を構築します。最後に、辞書を圧縮してディスクに書き込み、現在のセグメント情報 (辞書サイズ、辞書開始アドレス、ポスティングリスト開始アドレス、行番号範囲など) をメタデータに記録します。PolarDB は、外部ソートを避けるためにグローバル辞書を構築しません (グローバル辞書は、その上にタームインデックスを構築するためにプレフィックスで分割する必要もあります)。代わりに、列ストアストレージは追記専用の書き込みモデルを使用するため、PolarDB はメモリしきい値に基づいて複数のローカル辞書を生成する軽量な構築方法を使用します。次の図にその例を示します。メモリが十分な場合は、メモリしきい値をできるだけ大きくします。これにより、同じタームのより多くのインスタンスが同じ転置セグメントに格納されることで、領域を節約し、クエリパフォーマンスを向上させることができます。

上記の通常の転置インデックス構築に加えて、PolarDB のインメモリー列指向インデックスの全文検索インデックスは、システムがバックグラウンドでアイドル状態のときに転置インデックスを非同期でマージすることもサポートします。PolarDB のインメモリー列指向インデックスの列ストアインデックスは、通常テーブルのセカンダリインデックスです。INSERT の際、データは常に挿入順に列ストアストレージエンジンに列ごとに追記されます。DELETE は削除マークを使用し、UPDATE は DELETE と INSERT に変換されます。インメモリー列指向インデックスは、配列 InsertMask を使用して可視性チェックのために列ストアデータ内の各行の挿入バージョンをマークし、lsm DeleteMask を使用して既存の行を削除済みとしてマークします。同時に、非同期の Compaction や Recycle などのバックグラウンド操作がデータを再編成し、領域を再利用します。列ストアエンジンの一部として、PolarDB のインメモリー列指向インデックスの全文検索インデックスも、バックグラウンドの非同期転置インデックス Compaction タスクを使用して、削除マークが付けられたデータを定期的にクリーンアップし、領域を節約し、クエリパフォーマンスを向上させます。転置インデックスのマージは、転置セグメントを単位として行われます。複数の転置セグメントが新しい転置セグメントにマージされ、元の転置セグメントは変更されません。これにより、クエリが使用する転置インデックスのスナップショットオブジェクトが無効になるのを防ぎます。マージが完了すると、新しい転置インデックススナップショットが生成され、新しいクエリは新しいスナップショットを使用します。ローカル構築方法と削除マークの設計により、PolarDB のインメモリー列指向インデックスの全文検索インデックスでは、一括挿入がグローバルな再構築をトリガーすることはなく、増分部分のみが構築されます。更新コストも、削除マークを付けるだけで済むため非常に低く、頻繁な更新シナリオでも書き込みパフォーマンスに影響を与えません。さらに、定期的なバックグラウンドの非同期マージにより、よりコンパクトな転置インデックスが生成され、クエリパフォーマンスが向上します。列ストアの同時クエリ機能と組み合わせることで、この仕組みは巨大なデータシナリオでもミリ秒レベルの応答要件を満たします。

PolarDB のインメモリー列指向インデックスの全文検索インデックスは、MySQL 公式の MATCH 関数と LIKE 演算子をサポートしています。

• MATCH 関数

  PolarDB のインメモリー列指向インデックスは、行ストアに全文検索インデックスが存在するかどうかにかかわらず、MATCH 関数を使用した全文検索をサポートします。行ストアインデックスが存在しない場合、クエリは直接列ストアノードにルーティングされます。行ストアインデックスが存在する場合、クエリはコスト評価に基づいてインテリジェントに分散されます。ネイティブの MySQL 全文検索インデックスが最適化フェーズでトリガーする補助テーブルの同期やキャッシュの読み込みなどの時間のかかる操作が列ストアのパフォーマンスに影響を与えないようにするため、PolarDB はクエリ分散の開始時にこれらの操作をスキップします。

  実行フェーズでは、インメモリー列指向インデックスは 2 つの検索方法を提供します：FtsTableScan 演算子と MATCH 式です。前者は転置インデックスから直接一致する行を取得し、高いフィルター率のシナリオに適しています。後者は行番号でインデックスを検索し、先行する条件によってすでにほとんどのデータがフィルタリングされているシナリオに適しています。両方の方法の実行効率は、他の述語がデータをどれだけうまくフィルタリングするかに依存します。したがって、列ストアオプティマイザは統計からフィルター率を推定し、最適な戦略を動的に選択します。演算子方式が選択されると、システムは自動的に MATCH 関数を FtsTableScan + Filter 演算子に書き換えます。

  全文検索インデックスは非同期で構築されるため、新しいデータの可視性にわずかな遅延が生じることがあります。デフォルトでは、列ストアの Executor は、クエリ結果の完全性を保証するために、インデックス化されていないデータに対してフルテーブルスキャンを行い、クエリ結果を補完します。このステップをスキップするかどうかをパラメータで制御できるため、高い同時実行性と大規模なデータ量のシナリオで、パフォーマンスと一貫性のバランスを柔軟に取ることができます。また、インデックス構築パラメータを調整してデータ同期頻度を上げ、フルテーブルスキャンの範囲を狭めることで、クエリ効率をさらに向上させることもできます。

• LIKE 高速化

  特定の条件下で、PolarDB のインメモリー列指向インデックスは LIKE と MATCH の相互変換をサポートします。LIKE から MATCH への変換は、主にクエリの高速化のためで、フルテーブルスキャンにおける大量の文字列の行ごとの比較のオーバーヘッドを削減するためです。

  現在、この変換は、列ストアの全文検索インデックスが ngram トークナイザーを使用し、ngram のトークン長が LIKE のパターン文字列の長さ以下である場合にのみ有効になります。この条件下で、オプティマイザは LIKE '%abc%' のような述語を FtsTableScan + Filter 演算子に書き換え、転置インデックスを使用して候補行を迅速にフィルタリングできます。

  ただし、ngram トークン化のマッチングメカニズムは LIKE のセマンティクスとは異なるため (たとえば、"abbc" は ab、bb、bc にトークン化され、これらは "abc" の ab と bc と重なり、誤って一致と判断されることがあります)、結果の正確性を保証するために、元の LIKE 式は後続のフィルター条件として正確な検証を行うために保持されます。

  このメカニズムは、セマンティクスの正確さと実行効率を効果的にバランスを取りながら、クエリパフォーマンスを大幅に向上させます。

PolarDB のインメモリー列指向インデックスの転置インデックスは、複数の転置セグメントで構成されます。各転置セグメントには、独自のメタデータ、1 つのターム辞書、および一連のポスティングリストが含まれており、各タームは 1 つのポスティングリストに一意に対応します。メタデータには、辞書とポスティングリストの開始アドレスなどの情報が記録されます。メタデータは小さく、インデックスアクセスを高速化するためにデフォルトでメモリに常駐します。

転置インデックスの検索は、転置セグメントごとに行われます。主なプロセスには、辞書データの読み取り、有限状態トランスデューサー (FST) 辞書オブジェクトの構築、辞書でのターゲットタームの検索、および対応するポスティングリストを読み取って RBM (Roaring Bitmap) ポスティングリストオブジェクトを構築することが含まれます。

具体的には、クエリは 2 つのモードに分かれます：

1. 演算子クエリ：すべての転置セグメントのメタデータを走査し、辞書の開始アドレスを取得し、辞書データをロードし、辞書オブジェクトを構築して、ターゲットタームを検索します。タームが見つかった場合、そのタームのポスティングリストのオフセットアドレスをセグメント内の開始アドレスと組み合わせて、完全なポスティングリストオブジェクトを読み取ります。

2. 式クエリ：行番号に基づいて転置セグメントのセットを特定し、メタデータ内の行番号範囲によってさらにフィルタリングし、その後、一致する転置セグメントに対して演算子クエリと同様の辞書検索とポスティングリストの読み取りを行います。

パフォーマンスを向上させるため、インメモリー列指向インデックスはターム辞書のキャッシュをサポートします。このキャッシュは独立した LRU (Least Recently Used) キャッシュメカニズムを使用し、スケジューリングモジュールがそのキャッシュのメモリクォータを動的に調整します。単一のポスティングリストは通常小さく (ほとんどが 1 回の 4 KB の I/O のみ必要)、ポスティングリストも多数存在するため、キャッシュヒット率とキャッシュの利点は限定的です。したがって、メモリリソースの無駄を避けるため、ポスティングリストのキャッシュはデフォルトで無効になっています。

この設計は、クエリ効率を確保しながら、メモリ使用量と I/O オーバーヘッドのバランスを取ります。