Lucene (Elasticsearch, Solr) のインデックスには結局どんな情報が保存されているのか

Apache Luceneで凝ったことをする場合でも、通常、インデックスの構造までは意識しない場合が多いと思います。（Luceneに依存するSolrやElasticsearchも同様）筆者もその方針で開発を行うことが多く、その時々のニーズに合致するAPIだけを操作しています。そんなわけで、タイトル通り「Luceneのインデックスには結局どんな情報が保存されているのか」というシーズ的な切り口で調べてまとめたことが無かったので、やってみました。

実はLuceneのドキュメントには、ほぼこの切り口に対応する箇所があります。Lucene 8.6.3であれば、こちらです。

Package org.apache.lucene.codecs.lucene86 Description
https://lucene.apache.org/core/8_6_3/core/org/apache/lucene/codecs/lucene86/package-summary.html

このドキュメントは上述のドキュメントの単なる読書メモとも言えるかもしれません。以下、Lucene 8.6.3に関する記述です。

語の定義

• ドキュメントはフィールドの配列である。
• フィールドはタームの配列である。フィールドには名前がついている。
• タームはバイト列である。ただし、異なるフィールド中の同じバイト列は、別のタームと見なす。

転置インデックス

転置インデックスとは、タームから、そのタームを含むドキュメント番号の列を効率的に引けるようにしたデータ構造である。あるドキュメントがタームの配列であるのとは転置の関係にある。

フィールドの種類

• Stored: フィールドの内容が可逆に保存される。
• Indexed: 転置インデックスが保存される。Storedかつindexedということもある。
• Tokenized: 転置インデックスを保存するとき、フィールドの内容を複数のタームに分割する指定。この分割をトークナイズと呼ぶ。分割しない場合、フィールドの内容全体で一つのタームである。

セグメント

Luceneのインデックスは複数のセグメントに分割されることがある。セグメントはそれぞれ独立に検索処理することができる。インデックスのセグメント構成が変化するパターンは2通り：

• 追加されたドキュメントのための新しいセグメントを作る。
• 既存のセグメント同士をマージする。

ドキュメント番号

Luceneはドキュメントを番号で識別する。セグメント内での通し番号と、そこから導かれるインデックス全体での通し番号がある。標準的には、セグメントごとのベースドキュメント番号を決め、それとセグメント内での通し番号の和がインデックス全体での通し番号になるようにする。ドキュメント番号はセグメントのマージに変化することがあるので、Luceneの外部に保存しておく場合には注意が必要である。

Index Structure Overview

以下、全てのファイルはセグメントごとに存在する。

Segment Info（拡張子：.si）

セグメントのメタ情報を格納するファイル。

• SegVersion: このセグメントを作成した（完成させたという意味だと思われる）コードのバージョン。
• SegMinVersion: このセグメントにドキュメントを追加した中で最古のコードのバージョン。
• SegSize: このセグメント内のドキュメント数。
• IsCompoundFile: このセグメントがcompound fileかどうか。
  • （メモ）Compound fileは、おそらく、ファイルハンドラの枯渇を防ぐために、ファイルシステム上は単一のファイルとして書き出す機能？
• Diagnostics Map: デバッグ情報。Luceneバージョン、OSバージョン、Javaバージョン、セグメントが作成された理由（マージ、ディスクへの書き出し、addIndexes）、など。
  • （メモ）マージとaddIndexesは異なる？
• Files: このセグメントが参照しているファイルの一覧。

Field Names（拡張子：.fnm）

セグメント中に存在するフィールドのメタ情報を格納するファイル。

• FieldsCount: セグメント中に存在するフィールドの数。

以下、フィールドごとの情報：

• FieldName: フィールド名。UTF-8文字列。
• FieldNumber: フィールドの通し番号。　
• FieldBits: 各種フラグ。
  • 0x1のビット：Term Vectorsを保存するフラグ。
  • 0x2のビット：Normalization Factorを保存するフラグ。
  • 0x4のビット：転置インデックスを保存するフラグ
    • （メモ）IndexOptionsがあれば不要？
• IndexOptions: 転置インデックスに関する詳細な設定。
  • 0: 転置インデックスを保存しない。
  • 1: ドキュメント番号のみを保存する。
  • 2: ドキュメント番号とタームの出現回数を保存する。
  • 3: ドキュメント番号とタームの出現回数とポジションを保存する。
  • 4: ドキュメント番号とタームの出現回数とポジションとオフセットを保存する。
• DocValuesBits: Normalization FactorとDocValues、それぞれに関する詳細な設定。
  • （メモ）Normalization Factorのエンコーディングも変えられる？また、DocValuesのエンコーディングにはSORTED_SETとSORTED_NUMERICもあるのでは？
  • 0: 保存しない。
  • 1: NUMERICで保存する。
  • 2: BINARYで保存する。
  • 3: SORTEDで保存する。
• DocValuesGen: DocValuesのバージョン番号。デフォルトは-1で、それ以上であればアップデートがあることを示す。
  • （メモ）In-place updateで使用？
• Attributes: コーデックで使用するメタ情報（？）。
• PointDimensionCount, PointNumBytes: フィールドの内容が点としてインデックスされる場合の、次元数と次元ごとのバイト数。

Stored Field Values

フィールドの内容。検索結果に含めることを想定している。3つのファイルから成る。

Fields Data File（拡張子：.fdt）

フィールドの内容がおおむね16KBごとのチャンクに分割され、それぞれLZ4で圧縮されて保存されている。ただし：

• ドキュメントが複数のチャンクにまたがることはない。
• 32KBを超えるドキュメントは、16KBまでのブロックという更に細かい単位に分割されて圧縮される。これにより、あるフィールドの内容を取得するには、それが入っているブロックまでを伸長すれば良い。
• さらに、チャンクごとのメタデータとして元のフィールド長が保存されているので、それに達するまで伸長すればよく、ブロックの残りの部分の伸長は省略できる。
• 最悪ケース（おそらくランダムなデータ）でも、圧縮によるサイズ増は0.5%未満である。

Fields Index File（拡張子：.fdx）

• ブロックごとの最初のドキュメント番号の配列
• 対応するディスク上の位置の配列

あるドキュメントのフィールドの内容を取り出すには、前者を二分探索して、後者を見ればディスク上の位置が分かる。

Fields Meta File（拡張子：.fdm）

Fields Index File中の配列は、どちらも単調増加することを利用して圧縮されているが、この圧縮に関するメタデータ。

Term Dictionary, Term Frequency Data, Term Proximity Data

セグメント中に存在するタームに関するファイル。

基本的なアイデア

• ポジションは、フィールド中でどこにタームが出現するかを示す整数
  • おそらく、転じて、フィールド中のタームの特定の出現そのものもポジションと呼ぶ。言い換えれば、あるフィールド中に同じタームが何度か出現した場合、それらをそれぞれ区別するならポジションと呼ぶ。
• ペイロードは、ポジションに付加された任意のデータ。
• オフセットは、ポジションに付加された、トークナイズ前のバイト列のどこから（始点）どこまで（終点）に対応するかというデータ。ペイロードの一種である。

Term Dictionary（拡張子：.tim）

（フィールドごとの）タームとその情報やその情報へのポインタの配列。

• タームごとの情報。
  • Byte: タームに対応するバイト列。ただし、直前のタームと前方一致する部分は省略されているので、ランダムアクセスはできない。
  • DocFreq: そのタームを含むドキュメントの数
  • TotalTermFreq: そのタームの全ドキュメントを通じての出現回数
  • 各種ポインタ。ただし、直前のタームからの差分で保存されているので、ランダムアクセスはできない。
    • DocFPDelta: ドキュメント番号と出現回数、SkipFPDelta: スキップリストへのポインタ（Frequencies and Skip Dataへ）
      • ただし前者について、対象が単一のドキュメントの場合は、ポインタではなく即値になる。
    • PosFPDelta, PosVIntBlockFPDelta: ポジションへのポインタ。ただし後者（ドキュメントを128件ごとのブロックに分割したとき、余りにあたるドキュメントに関する部分）については、ポジションとペイロードは同一ファイルに保存されるので、ペイロードへのポインタも兼ねる。（Positionsへ）
    • PayFPDelta: ペイロード（オフセットを含む）へのポインタ（Payloads and Offsetsへ）
• タームごとの統計値を、フィールドごとに寄せたもの。
  • FieldNumber: フィールドの通し番号
  • NumTerms: フィールド中のターム数
  • RootCode: そのフィールドに関するタームごとの情報の先頭へのポインタ
  • SumTotalTermFreq: 任意のタームの全ドキュメントを通じての出現回数
  • SumDocFreq: フィールド中のタームのDocFreqの総和
  • DocCount: 少なくとも一つのタームを含むドキュメントの数

Term Index（拡張子：.tip）

Term Dictionaryへのインデックス。実体はフィールドごとのFST (Finite State Transducer) である。タームの前方部分列に対して、マッチする Term Dictionary の始点へのポインタを返す。

Frequencies and Skip Data（拡張子：.doc）

タームごとの以下の情報。出現頻度はフィールドごとのオプションである。

• ドキュメント番号と出現頻度のペアの配列。いわゆるポスティングリスト。
• 各種スキップリスト。各種リストが長い場合のランダムアクセスを効率化するための構造である。
  • ポスティングリストへのスキップリスト
  • ポジションの配列へのスキップリスト
  • ペイロードの配列へのスキップリスト

Positions（拡張子：.pos）

タームごとドキュメントごとのポジションの情報。これはフィールドごとのオプションである。全てのフィールドについてポジションが省略される場合は、ファイル自体が省略される。

パフォーマンスのため、Payloads and Offsetsにあたる情報の一部を持つこともある。具体的には、ドキュメントを128件ごとのブロックに分割したとき、余りにあたるドキュメントに関する部分を持つ。

Payloads and Offsets（拡張子：.pay）

タームごとドキュメントごとポジションごとのペイロードとオフセットの情報。

Normalization Factor

ドキュメントごとフィールドごとの正規化係数の情報。直感的には、フィールドの内容の長さのことである。

Norms Data（拡張子：.nvd）

• 各ドキュメントがフィールドの内容を持っているかどうかのビット列
• 正規化係数の配列

Norms Metadata（拡張子：.nvm）

Norms Dataのインデックス。以下の情報を持つエントリの列である。

• フィールド番号
• 上述のビット列の先頭へのポインタ
• 上述のビット列の長さ
• フィールドの内容を持っているドキュメントの数
• 正規化係数あたりの長さ
• 正規化係数の配列の先頭へのポインタ

Term Vectors

ベクトル空間モデルにおけるドキュメントの表現。ただし、実際にはポジションやペイロードも入っている。これまで挙げてきた情報を別の単位に寄せたものとも言えるかもしれない。

Fields Data Fileと同様のチャンクに分割されている。

Vector Data File（拡張子：.tvd）

• DocBase: チャンク内で最小のドキュメント番号
• ChunkDocs: チャンク内のドキュメント数
• NumFields: ドキュメントごとのフィールド数
• FieldNums: チャンクごとのフィールド番号の配列
• FieldNumOffs: 具体的なフィールドの内容へのポインタ
• Flags（フィールドごとの場合と、ドキュメントごとフィールドごとの場合がある）
  • ポジションの有無
  • オフセットの有無
  • ペイロードの有無
• NumTerms: ドキュメントごとフィールドごとのタームの数
• TermLengths: タームの長さ。直前のタームとの前方一致の長さと、残りの長さに分かれている。
• TermFreqs: 出現回数
• Positions: ポジション
• StartOffsets: オフセットの始点
• Lengths: オフセットの終点からオフセットの始点を引いた値
• PayloadLengths: ペイロードの長さ
• Terms: タームのバイト列
  • おそらく直前のタームとの前方一致は省略されていると思われる。
  • LZ4で圧縮されて保存されている。
• Payloads: ペイロード
  • LZ4で圧縮されて保存されている。

Vector Index File（拡張子：.tvx）

Fields Index Fileと同様。ただし、Fields Data FileではなくVector Data Fileを指している。

Per-Document Values

いわゆるDocVales。Stored field valuesと同様、フィールドの内容。違いは、メモリにロードされ、スコアリングなどに利用することが想定されている点。これに対して、Stored field valuesは検索結果の生成などに利用することが想定されている。

セグメントごとのドキュメント番号の上位16ビットごとのブロックに分割されて保存される。この範囲に含まれ、フィールドの内容が存在するドキュメントの数によって、エンコーディングが異なる。

• SPARSE: ドキュメント数が4,095以下。ドキュメント番号の下位16ビットはshortで保存する。
• DENSE: ドキュメント数が4,096以上65,535以下。どのドキュメントにフィールドの内容が存在するかをビットマップで表す。
• ALL: 全てのドキュメントにフィールドの内容が存在する。ドキュメント番号とフィールドの内容のインデックスが一致するため、ドキュメント番号を保存する必要はない。

さらに、値の型によってもエンコーディングが異なる。

• NUMERIC: 数値。
  • Delta-compressed: 最小値からの差分に圧縮して保存する。
  • Table-compressed: 値が256通り未満しかなく、値の間にギャップがある場合、値のテーブルを保存し、ドキュメントごとの値はそのテーブルのインデックスに圧縮して保存する。
  • GCD-compressed: 最大公約数が存在する場合（要は日付型）、最大公約数で割った値に圧縮して保存する。
  • Monotonic-compressed: 値が単調増加していく場合、期待値からの偏差に圧縮して保存する。
  • Const-compressed: 値が1通りしかない場合、その値のみを保存する。
• BINARY: バイナリで、ドキュメント順にソート。
  • Fixed-width: 単一のバイト列として保存する。固定長なので、その長さにドキュメント番号を掛ければポインタが出る。
  • Variable-width: 単一のバイト列として保存する。可変長なので、各ドキュメントごとの終点のポインタも保存する。
  • Prefix-compressed: 16ドキュメントごとのチャンクに分割して保存する。チャンクごとに最初のドキュメントについては完全なバイト列が、他のドキュメントについては前方一致しない部分だけが保存される。
    • （メモ）A reverse lookup index is written from a portion of every 1024th term. の意味が分からない……
• SORTED: バイナリで、重複を排除して内容順にソートし、プレフィックスを使った圧縮を行う。ドキュメントごとの値としてはソートされたバイナリの内容を指すポインタを保存する。ポインタの配列はNUMERICのように圧縮する。
• SORTED_SET: SORTEDと同様だが、ドキュメントごとに複数のポインタを持てる。
• SORTED_NUMERIC: 数値で、内容順にソートし、NUMERICのように圧縮する。ドキュメントごとの値としてはソートされた数値の内容を指すポインタを保存する。ポインタの配列もNUMERICのように圧縮する。

Live Documents

ドキュメント数ぶんのビットマップである。論理削除されたドキュメントに対応するビットは倒される。論理削除されたドキュメントが存在しない場合、ファイルごと省略される。

Point Values

フィールドの内容を点としてインデックスする場合に使う情報。実体はkd木である（正確にはBkd-Treeという構造らしい）。

• 次元数や次元ごとのバイト数などのメタデータ（拡張子：.kdm）
• 節点（拡張子：.kdi）
• 葉（拡張子：.kdm）
  • （メモ）メタデータと拡張子が重なっているがtypoか？