PolarDB:IMCI の全文検索機能の分析

IMCI は、ドキュメント ID のセットであるポスティングリストを圧縮および計算するために、Roaring Bitmaps (RBM) アルゴリズムを使用します。

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

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

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

パフォーマンスの特徴:

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

• SIMD 命令を使用して、積集合や和集合などのセット操作を高速化します。

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

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

IMCI は、FST アルゴリズムを使用してターム辞書を構築し、時間とスペースの効率のバランスを取ります。

• スペース効率: term の共通のプレフィックスとサフィックスを共有することで、ストレージスペースを効果的に圧縮します。

• 時間効率: term のクエリの時間計算量は O(L) です。ここで、L は term の長さです。

たとえば、順次入力されるターム China、Chinese、love について、それぞれのポスティングリストのアドレスオフセットが 5、10、15 であると仮定します。結果として得られる辞書を次の図に示します。この図は、FST がプレフィックスとサフィックスを共有することでスペースを節約するだけでなく、異なる遷移がそれぞれ一意の関連値を持つことを保証することを示しています。クエリは初期状態 0 から始まり、ターム内の各文字の出力ノードをたどります。出力ノードが存在する場合、関連値が累積されます。`Chinese` の場合、最終的な関連値は 15 であり、最後の文字は終了状態にあります。これは、タームが辞書に存在することを意味します。さらに、FST のプレフィックス計算は文字ではなくバイトに基づいているため、UTF-8 などのエンコーディングもサポートします。

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

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

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

• MATCH 関数

  PolarDB IMCI では、行ストアに全文検索インデックスが作成されているかどうかに関係なく、すべての全文検索に MATCH 関数を使用できます。行ストアにインデックスが作成されていない場合、クエリは直接列ストアノードにルーティングされます。インデックスが存在する場合、クエリはコスト評価に基づいてインテリジェントにルーティングされます。最適化フェーズでの補助テーブルの同期やキャッシュの読み込みなど、MySQL ネイティブの全文検索インデックスでの時間のかかる操作が列ストアのパフォーマンスに影響を与えないように、PolarDB はクエリルーティングの早い段階でこれらのプロセスをスキップします。

  実行中、IMCI は 2 つの検索方法を提供します：FtsTableScan 演算子と MATCH 式です。前者は転置インデックスを介して一致する行を直接取得し、高選択性のシナリオに適しています。後者は行番号に基づいてインデックスを検索し、先行する条件によってすでに大量のデータが除外されている状況に適しています。これら 2 つの方法の実行効率は、他の述語のフィルタリング効果に依存します。したがって、列ストアオプティマイザーは、統計に基づいてフィルタリング率を推定し、最適な戦略を動的に選択します。演算子方式が選択されると、システムは自動的に MATCH 関数を FtsTableScan + Filter 演算子に書き換えます。

  全文検索インデックスは非同期で構築されるため、新しいデータの可視性に短い遅延が発生する可能性があります。デフォルトでは、列ストアエグゼキュータは、インデックス付けされていないデータに対してフルテーブルスキャンを実行してクエリ結果を補完し、完全性を保証します。また、このステップをスキップするかどうかを制御するパラメーターも提供されており、高い同時実行性、大容量データのシナリオでパフォーマンスと一貫性の間の柔軟なトレードオフを可能にします。ユーザーは、インデックス構築パラメーターを調整してデータ同期頻度を高速化し、フルスキャンの範囲を縮小して、クエリ効率をさらに向上させることもできます。

• LIKE 高速化

  特定の条件下で、PolarDB IMCI は LIKE と MATCH の間の変換をサポートします。LIKE を MATCH に変換するのは、主にクエリを高速化して、フルテーブルスキャンでの行ごとの文字列比較のオーバーヘッドを削減するために使用されます。

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

  ただし、ngram トークン化のマッチングメカニズムと LIKE 演算子の間にはセマンティックな違いがあります。たとえば、"abbc" は ab、bb、bc にトークン化されます。これは "abc" の ab と bc と重複し、誤って一致として識別される可能性があります。したがって、元の LIKE 式は、結果の正確性を保証するために、後続のフィルター条件として正確な検証のために保持されます。

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

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

インデックス検索はセグメントごとに実行されます。主なプロセスには、辞書データの読み取り、FST オブジェクトの構築、辞書内のターゲットタームの検索、そして対応するポスティングリストを読み取って RBM オブジェクトを構築することが含まれます。

2 つの特定のクエリモードがあります。

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

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

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

この設計により、メモリ使用量と I/O オーバーヘッドを合理的にバランスさせながら、クエリ効率が保証されます。