Full Text Search in SmithDB: Designing an Inverted Index for Object Storage｜SmithDB における全文検索：オブジェクトストレージ用の逆インデックス設計 | AIニュース最前線

![image](https://cdn.prod.website-files.com/65c81e88c254bb0f97633a71/6a286ea9750766ce561e8761_Group%202147239256.png) ## 概要 SmithDB は、オブジェクトストレージに保存された大規模で深くネストされた JSON ドキュメントからなる基盤データであっても、エージェントのトレースに対して全文検索および JSON フィルタリングをサポートし、中央値 (P50) レイテンシは 400 ミリ秒です。 全文検索はすでに確立された分野です。Lucene は 20 年以上の歴史を持ち、[Tantivy](https://github.com/quickwit-oss/tantivy) や [Quickwit](https://quickwit.io/blog/quickwit-101) は既に検索とインデックス化をオブジェクトストレージ上に実装しています。しかし、SmithDB へのテキスト検索機能を実装するにあたり、エージェントのトレースを検索ワークロード向けにインデックス化する課題が固有のものであることを踏まえ、第一原理からアプローチすることを選択しました。 ## SmithDB は検索に対して異なるアプローチを必要とする ## 課題 1: エージェントトレースのユニークなデータ特性 すべての LangSmith イベントは、その総バイト数の圧倒的多数を占めるフィールドとして inputs と outputs をエンコードしています。入出力のペイロードサイズが 1 MB+ となることは珍しくなく、一部では圧縮解除状態で数百メガバイトに達するものもあります。これらのコンテンツカラムは、ID、タイムスタンプ、その他のメタデータカラムを桁違いに上回っています。 また、元の [SmithDB ブログ投稿](https://www.langchain.com/blog/introducing-smithdb#agents-present-a-new-data-problem) で言及されている通り、エージェントのトレースに関連するペイロードは時間とともにサイズが増え続けています。これは、LLM のコンテキストウィンドウサイズが大きくなり、エージェントがより長い時間範囲で実行される結果として、LLM がより多くのコンテキストを蓄積するためです。 これらの特性は、検索インデックスの通常の経済性を逆転させます。従来のログエンジンは数十億件の*小規模な*ドキュメントをインデックス化するため、インデックスサイズは各ドキュメントに対して相対的に小さくなります。一方、LangSmith のエージェントトレースでは、数十億件の*巨大な*ドキュメントをインデックス化しており、1 つのドキュメントが多数の小規模なログ行よりも多くのインデックスデータを生成します。[一般的に](https://aws.amazon.com/blogs/big-data/amazon-opensearch-service-101-how-many-shards-do-i-need/)、ログにおけるソースデータとインデックスの比率は約 1:1.25 です。しかし、LangSmith のエージェントトレースでは、平均して約 1:1.9 に近いことが観測されています。これにより、4 つの重要な帰結が生じます： - インデックスを持たないコンテンツフィルタは壊滅的に遅くなります。「タイムアウトをツール出力が言及する実行を検索する」というクエリを実行する場合、候補範囲内のすべてのペイロードをスキャンしない限り不可能ですが、そうすれば 3 行の結果を得るために何ギガバイトものデータをスキャンすることになります。 - 用語の出現頻度は Zipf 分布に従います。自然言語や JSON ペイロードはべき乗則（パワーロー）を示し、「agents」「import」「role」「type」や普遍的なキーなどの限られたトークンはほぼすべての文書に現れる一方、長いテールにある用語は一度または二度しか出現しません。インデックスは、用語頻度の何桁ものオーダーにわたってコンパクトで剪定可能である必要があり、それらはすべて 1 つのファイル内に収められます。 - 複数のクエリモードが重要です。ユーザーはパス（「この実行に inputs.content.messages が含まれるか？」）、値（「…Alex に言及している場所」）、自由テキスト（「…どこかでレイテンシの回帰を言及しているか」）によって検索を行います。 インデックス付き検索は、コンテンツクエリがペイロード全体のスキャンを実行するのを防ぐものであり、重く偏った半構造化ペイロードを受け入れる必要があります。 ## 課題 2: オブジェクトストレージ SmithDB はすべての永続データをオブジェクトストレージに保持するため、計算ノードは比較的ステートレスとなり、システムはローカルディスクを管理することなくノードを追加することでスケーリングできます。 クエリのコストは概ね **(オブジェクトストレージに対して発行されるリクエスト数) × (1 リクエストあたりの読み取りバイト数)** に比例します。オブジェクトストレージにおいて: - 各オブジェクトストアのリクエストには、数十ミリ秒から数百ミリ秒のレイテンシが伴います。 - リクエストごとのスループットは限定的であるため、必要な場合にのみ取得する前に、大規模な投稿リストや位置リストを取得しようとすると、クエリ全体のボトルネックになる可能性があります。 SmithDB の逆インデックスのすべての側面、ストレージレイアウトからクエリ実行に至るまで、これらの制約を念頭に置いて設計されています。 ## SmithDB 検索クエリの形状 逆インデックスのストレージレイアウトについてさらに深く掘り下げる前に、このインデックスが対応する主なクエリパターンを確認しましょう。SmithDB のクエリ表面は、3 つの述語ファミリーに集約され、それぞれが対象とするマッチング内容と許容されるパターン構文において異なります。 - 第一はパスの存在（json_key）です。このドキュメントにキー K が含まれているか？例えば json_key(inputs, "author.name") は、どのドキュメントが author.name に言及しているかを問うものです。パスの存在判定では、キーパス自体に対する LIKE 演算もサポートされます：json_key(inputs, "author.%") や json_key(inputs, "%.user_id") は第一級クエリとして扱われます。パターンはパス内の任意の位置（プレフィックス、サフィックス、インフィックス）に配置できます。 - 第二はキー付き値（json_key_search）です。キー K の値が V に一致するか？json_key_search(inputs, "author.name", "Jane") が標準的な形式です。クエリは単一のトークンでも、複数トークンのフレーズ（json_key_search(inputs, "title", "latency regression"）でも構いません。フレーズ版では隣接性が追加され、「latency regression」はこれらの単語が値内で連続して出現するドキュメントのみと一致し、値内のどこかに存在すればよいわけではありません。 - 第三は全文検索（search）です。インデックスされた値のいずれかが Q に一致するか？search(error, "timeout") はテキスト列を直接検索します；search(inputs, "latency regression") はパスに関係なく、すべての JSON 値を対象に検索を行います。 要約すると： Shape What it matches json_key key path exists json_key_search path + value search text column or any JSON value 後続の各セクションはこの表を参照します。「パスのみクエリ」と言う場合は json_key を指し、「キー付き値」は json_key_search を、「全文検索」は search を意味します。 ## インデックス付き検索の概要 インデックス付き検索（inverted index）は、[Lucene](https://lucene.apache.org/) から [Tantivy](https://github.com/quickwit-oss/tantivy) に至るまで、あらゆる検索ライブラリを支えるデータ構造です。これは教科書の末尾にある索引のようなもので、ある用語を一度参照するだけで、その用語が言及されているページに直接ジャンプでき、すべてのページを読み込む必要がありません。SmithDB はこの考え方を基盤とし、オブジェクトストレージに保存される大規模なエージェント・トレースペイロード用に、ストレージレイアウトを特化させています。 ## 用語、ポスティング、位置情報 インデックス付き検索の構造は、以下の3つの概念に基づいています： - 用語（term）は、索引付けの基本単位です。JSONパス、キー付き値、またはテキストトークンとなります。 - ポスティング（posting）は、その用語を含む文書IDのソート済みセットです。 - 位置情報（position）は、文書内で用語が出現する場所であり、これがフレーズ検索を可能にします。 テキストに基づいて索引付けされた5つのトレース例を見てみましょう： doc 0: "langchain agents emit traces" doc 1: "langsmith engine runs deep agents" doc 2: "langchain deep agents workflow" doc 3: "agents emit deep langsmith traces" doc 4: "deep langsmith powers the engine" インデックスは、各用語ごとに1エントリを保持し、その用語に言及している文書への参照を含みます： term posting list positions ────────── ────────────── ───────────────────────── agents [0, 1, 2, 3] 0:[1] 1:[4] 2:[2] 3:[0] deep [1, 2, 3, 4] 1:[3] 2:[1] 3:[2] 4:[0] emit [0, 3] 0:[2] 3:[1] engine [1, 4] 1:[1] 4:[4] langchain [0, 2] 0:[0] 2:[0] langsmith [1, 3, 4] 1:[0] 3:[3] 4:[1] powers [4] 4:[2] runs [1] 1:[2] the [4] 4:[3] traces [0, 3] 0:[3] 3:[4] workflow [2] 2:[3] 各用語は辞書エントリの一つです：値を参照し、その投稿リスト（posting list）を読み取れば、どのドキュメントを取得すべきかが明確になります。"search("deep agents")" のようなクエリでは、deep の投稿リスト [1, 2, 3, 4] と agents の投稿リスト [0, 1, 2, 3] を交差させて [1, 2, 3] を得ますが、これはペイロードのスキャンを必要としません。 positions カラムは、各ドキュメントにおいてその用語が出現するトークンのオフセット（位置）を記録しています。例えば "1:[0]" はドキュメント 1 の位置 0 を意味します。これがフレーズ検索を可能にする理由です："search("langsmith engine")" というクエリは、langsmith がオフセット 0 にあり engine がオフセット 1 にあるためドキュメント 1 に一致しますが（0 + 1 == 1）、powers と the がその間に挟まっているドキュメント 4 には一致しません（langsmith は位置 1、engine は位置 4）。 ## なぜ Vortex を採用し Tantivy を選ばなかったのか [Tantivy](https://github.com/quickwit-oss/tantivy) は優れた検索インデックスライブラリであり、Rust における Lucene スタイルの検索のための明白な参照点です。当初はこれを直接採用できるかどうかを問いましたが、最終的にたどり着いた設計は Tantivy に強く影響を受けています。しかし、いくつかの制約により、そのまま私たちのユースケースに適合させるには不自然なものとなりました： - オブジェクトストレージであり、ローカルディスクではありません。Tantivy は mmap を中心に構築されており、すべてのバイトがマイクロ秒単位でアクセス可能であり、ランダム I/O は事実上無料です。一方、オブジェクトストレージでは往復に約 100 ミリ秒を要し、レイアウトと結合（coalescing）がクエリの遅延を決定する要因となり、CPU の性能は主要因ではありません。 - カラム型エンジンに埋め込まれています。SmithDB のクエリは Apache DataFusion を経由して Vortex 上で実行されます。検索機能も他の述語と同じスキャンパイプラインを通じてプッシュダウンされたいと考えており、独自のセグメントモデルと I/O 仮定を持つ並列クエリスタックとして独立して動作させることは望んでいません。 - ドキュメント ID は Vortex の行とアライメントされています。Tantivy のライターは挿入順で独自のセグメントローカルなドキュメント ID を割り当て、マージのたびに再番号付けを行います。一方、SmithDB ではインデックスが対応する Vortex データファイル内の行位置を直接指す必要があります（コアイベントデータファイルには Vortex を使用しています）。つまり、ドキュメント ID は行インデックスそのものであり、翻訳テーブルは不要で、クエリ実行時に照合すべき第二の識別子も存在しません。また、データファイルの行順序に従うマージ処理でも再マッピングは不要です。さらに、コンパクションによる行位置の再マッピングも、本ブログ記事の後半で詳述する通り、Tantivy のインデックスマージとは相性が良くありません。 ## SmithDB 向け逆インデックス開発への道のり ## Vortex の簡単な解説 [Vortex](https://vortex.dev/) は、SmithDB がオブジェクトストレージに使用する拡張可能かつ列指向のファイル形式です。Parquet などの固定フォーマットとは異なり、Vortex ではプラグイン可能なエンコーディングとカスタムファイルレイアウトを許可しており、これによりファイルフォーマットのフォーク（分岐）を行うことなく、ワークロードに合わせて圧縮や I/O アクセスパターンを最適化できます。 すべての読み取り操作では、統計情報を用いて行グループ全体を*剪定（prune）*し、残った行をマスクまで*フィルタリング*し、クエリが実際に必要とする列のみを*投影（project）*します。 [Vortex](https://docs.vortex.dev/developer-guide/internals/io) ファイルにおける I/O の単位は**セグメント**です。これは連続した物理的なバイト範囲のことです。オブジェクトストレージでは 1 ラウンドトリップに約 100 ms かかるため、クエリレイテンシを削減するための主要なレバーは、リクエスト数を最小化することにあります。Vortex の I/O スケジューラは、近接するセグメント読み取りを単一のリクエストに統合し、1 MB のギャップ内の読み取りを 1 つにまとめます（最大 16 MB のウィンドウまで）。これにより、インデックスにおけるシーケンシャルアクセスパターンが、オブジェクトストアの GET リクエスト数に非常に少ないものに対応します。 ![image](https://cdn.prod.website-files.com/65c81e88c254bb0f97633a71/6a2870b4ffb42f044f4e2890_CleanShot%202026-06-08%20at%2017.31.48.png) ## 私たちの（失敗に終わった）最初の試み 最初のバージョンは、教科書的な逆インデックスのほぼ直訳でした。2 つのカラム（パス用の term_key とトークン用の term_value）により、1 つのレイアウトで 3 つのクエリ形状すべてに対応可能となりました：*path-existence* は term_key を読み取り、*keyed search* は両カラムにわたる投稿リストを交差させ、*full-text* は term_value のみで交差させます。投稿リストは List 形式のセルとして保存され、位置情報は List > 形式でした。 Vortex のデフォルト設定に頼りました：term カラムには FSST エンコーディングを、投稿リストと位置情報には bitpacked エンコーディングを、クエリ時にプルーニング（不要なデータの除外）が可能なゾーン化ストレージレイアウトを採用しました。フレーズ検索に必要な位置情報だけが他のすべてのカラムよりも桁違いに大きかったため、インデックスはコアのランデータとは別のファイルに保持することにしました。これにより、インデックスの構築とマージをコアの書き込みパスから切り離すことができました。Vortex の API は行インデックスとマスクを対象とするため、インデックスフィルタリングを兄弟ファイルに委譲する構成は自然なものでした。 ![image](https://cdn.prod.website-files.com/65c81e88c254bb0f97633a71/6a2870cdc5a71693ece14812_CleanShot%202026-06-08%20at%2017.31.21.png) スケーラビリティの観点では、3 つの問題が顕在化しました： - 用語ごとの符号化制御がない。Vortex は列全体に対して符号化を選択しており、用語ごとではないため、単一の共通トークン（agent, langchain）がチャンク内のすべての用語に大きなビット幅を強制し、ビットパッキングの効率が低下する。列の残りの部分はキャッシュ動作の悪化と読み込みサイズの増大という代償を支払わされ、高頻度用語に対してのみより積極的なビットパッキングを適用するための手段が存在しなかった。 - 固定サイズ行グループは用語の偏りを無視していた。各行グループに一定数の用語をバッチ処理したがため、単一の高頻度用語が一つの行グループを圧縮後 100 MB を超えるように押し上げ、別の行グループは数 MB のまま放置される事態が生じた。クエリ実行時にはこれが巨大なオブジェクトストア GET 操作となり、マージ時には巨大なメモリ内デコード処理となった。 - マージでは位置情報の再構成が必要だった。2 つのセグメントをマージするには、完全な位置情報 List > をデコードし、内部リストを新しいドキュメント順序に並べ替え、すべての外側オフセットを再計算する必要がある。コンパクション時に CPU 時間と割り当て量が急増した。インデックスのバイトの 70% 以上が位置情報である場合、これが主要なコンパクションコストとなった。 ![image](https://cdn.prod.website-files.com/65c81e88c254bb0f97633a71/6a2870e21928bba3a44eeca4_CleanShot%202026-06-08%20at%2017.32.28.png) ## 第 2 回試行：V2 インバートドインデックスのストレージレイアウト 私たちの V2 レイアウトは、「1 ロウグループあたりの N 語」という組織単位を**バイト予算制約付きのロウグループ**に変更し、各列ごとのバイトレイアウトを直接 Vortex のデフォルトに依存するのではなく、自前で管理することで、V1 で生じたすべての 3 つの問題に対処します。このセクションの後半では、新しい組織単位の概要、その内部に含まれる要素、そしてなぜそのバイト予算を獲得できたのかというエンコーディングの選択について順を追って解説していきます。 ## バイト単位でサイズ指定されたロウグループ ロウグループはプルーニングと I/O の単位であるため、固定された行数ではなく、独立した固定の*バイト*予算に基づいてロウグループのサイズを決定します。 - 投稿データ用として 32 MB：クエリがロウグループの投稿データを参照する際の、最悪ケースにおけるオブジェクトストア GET の上限を制限します。 - 生テキストデータ用として 64 MB：1 ロウグループあたりの生バイト数の上限を設定します。 語数ではなく*バイト*単位でサイズ指定することが、V1 の第 3 の問題を解決する鍵となります。語の偏在（タームスキュー）により、語数は I/O サイズを推定するための良い指標とはなり得ません。V1 のロウグループにおいて、頻度の高い語が 1 つでも含まれるだけで、圧縮後であっても 500 MB を超えてしまう可能性があるからです。一方、バイト予算を設定することで、クエリ実行時にオブジェクトストアから取得するデータ量やメモリーフットプリントに対する、あらゆるロウグループの上限値を明確に保証できます。 用語列に対してゾーンストレージレイアウトを採用し、各ロウグループごとの最小値・最大値・カウント情報を保持させることで、クエリプランナーは FST（Finite State Transducer）にアクセスする前に、完全に不要なロウグループをスキップできるようになります。特定のプレフィックスを対象とするパスクエリにおいては、これが最も大きな削減効果をもたらします。なぜなら、多くのロウグループには述語の範囲内に該当するデータがそもそも含まれていないからです。 ![image](https://cdn.prod.website-files.com/65c81e88c254bb0f97633a71/6a2870f7b90de3322e541d9c_CleanShot%202026-06-08%20at%2017.30.53.png) ## 行グループ内の構造 各行グループは 4 つの列を保持しています（用語キーには 3 つの列が含まれ、位置情報はスキップされます）。 - term — バイナリレイアウトであり、そのバイト列は FST（有限状態トランジューサ）です。これは各用語を順序番号（この行グループ内の行インデックス）にマッピングします。当社の FST の利用方法は Tantivy に着想を得ています。 - term_info — 用語のメタデータ：文書数およびポストイングと位置情報へのオフセットを含みます。 - postings — バイナリブロッブです。各用語ごとのリストは、128 ドキュメントブロックに分割されたビットパック化された差分値で構成され、残りの 128 ドキュメント未満の部分は VInt（可変長整数）で末尾に付加されます。 - positions — バイナリブロッブであり、同じエンコーディングを使用します。これは term_value の場合にのみ存在します。パスの有無はドキュメントレベルでの質問であるため、term_key はこの列を完全にスキップします。 検索処理は、辞書への 1 回の走査、オフセットテーブルの読み取り、および 1 回のバイト範囲フェッチで構成されます。FST が用語を順序番号に解決し、その順序番号が term_info をインデックスして、ポストイングへのオフセット（およびフレーズクエリの 경우）位置情報へのオフセットを取得します。クエリはこれらのバイト範囲を直接読み取ります。ペイロードのスキャンもネストされたリストのデコードも行われません。また、各列が独立したチャンク化レイアウトであるため、フレーズでないクエリでは term と term_info および postings のみをフェッチし、positions 列を開くことはありません。 ![image](https://cdn.prod.website-files.com/65c81e88c254bb0f97633a71/6a28710d37faefe45b09e0fc_CleanShot%202026-06-08%20at%2017.29.57.png) ## エンコーディングの選択 **用語辞典には FST を使用します。** 279 万回の用語出現を持つ代表的な行グループにおいて、FST を明白な代替案（Vortex のデフォルトである FSST 文字列エンコード、プレフィックス共有 keep_add、および単純な zstd）と比較しました。勝敗の形状は一意性（cardinality）に依存します： Column | Unique terms | Raw | FSST | zstd | FST ---|---|---|---|---|--- term_key (JSON paths) | 546 | 88.8 MiB | 34.7 MiB | 16.3 KiB | **3.8 KiB** term_value (token values) | 1.41M | 55.1 MiB | 65.7 MiB | 21.7 MiB | 32.7 MiB term_value:term_key combined | 2.79M | 146.6 MiB | 81.7 MiB | 31.3 MiB | 37.6 MiB term_key では、数百万行にわたって数百の JSON パスが繰り返されるため、FST は辞典全体を**3.8 KiB**に圧縮します。これは生バイトの 4 桁小さく、zstd の約 4 分の 1 です。高一意性の term_value カラムでは、FST は zstd よりも約 1.5 倍大きくなりますが、それでも FSST を上回ります。重要な点は、**zstd が不透明である**ことです。すべての参照にはブロックの展開が必要です。一方、FST は*インデックスそのもの*です。完全一致検索、プレフィックスおよび範囲スキャン、そしてオートマトンウォーク（LIKE、ファジー、正規表現）はすべて、ハッシュ化なしで圧縮バイトに対して直接実行され、計算コストは O(|term|) です。 また、キー検索とフルテキストクエリの形状を、1 つの行グループごとに単一の FST に統合します。そのために、term_value エントリを {token}\0{flattened_path} として保存します。キー検索は完全一致による FST ルックアップとなり、フルテキスト検索は token\0 に対するプレフィックススキャンとなり、そのトークンが出現するすべてのパスを走査します。 **各用語に対してブロックビットパック化された差分を使用しています。** ポスティングと位置情報の両方で、同じ Tantivy/Lucene スタイルの 2 層エンコーディングを採用しています。このエンコーディングの形状こそが、用語ごとの制御を可能にし、マージを低コストにする理由です。 各用語ごとのリストは、固定された**128 要素ブロック**と、128 未満の残りの要素からなるテールに分割されます： ![image](https://cdn.prod.website-files.com/65c81e88c254bb0f97633a71/6a2871ac91a0ca576133d56a_CleanShot%202026-06-08%20at%2019.11.35.png) ブロック内では、ID 自体ではなく連続するドキュメント ID 間の差分を保存し、そのブロックの最大差分に収まる最小幅でビットパック化します。密集した規則的な ID の列は、それぞれ数ビットにまで圧縮されます。末尾の不完全なブロック（高頻度用語では定義上稀であり、低頻度用語ではPostingリスト全体がこれに該当）については VInt にフォールバックし、小さな差分に対して約 1 バイトとなり、長いテールでも緩やかに性能を低下させます。 この方式により、v1 の List エンコーディングにはなかった 2 つの特性が生じます： - 用語ごとの符号化であり、列ごとの符号化ではありません。各用語はブロックごとに独自のビット幅を選択します：頻出する用語（例：agent）は文書あたり 3〜4 ビットで圧縮され、稀な用語は VInt の末尾部分から決して離れません。v1 では列全体に一つの幅を強制していたため、頻出用語がすべてのデータのバイト数を膨らませていました。 - Vortex には非公開です。Vortex は符号化されたバイト列を単一のバイナリ・ブロブとして認識するだけで、読み取りパスで Arrow にデコードすることはありません。これにより、クエリは必要なバイト範囲のみを取得し、必要に応じてブロックをデコードし、スキップリストのルールで除外される部分をスキップしてデコードを飛ばすことが可能になります。 ## FST 利用における Tantivy との相違点 Tantivy も FST を活用していますが、セグメントごとに 1 つずつの FST を構築し、シャード分割を行います。一方、私たちは行グループごとに 1 つずつの FST を構築します。行グループサイズの FST は十分に小さいため、書き込み側はこれを通じてストリーム処理を行い、メモリ上にセグメント全体の FST を保持する必要がありません。また、クエリ実行時に FST の処理が行われる前に、ゾーンレベルのプルーニングによってほとんどの行グループが除外されます。トレードオフとして、1 回の参照でファイルあたり複数の FST にアクセスする可能性がありますが、プルーニングによりこのコストは実際には稀になります。残存する FST は十分に小さいため、その探索処理は軽量です。 ## 次のステップ パート 2 では、逆インデックスの構築とマージの実装方法、および読み取りパスでどのようにインデックスを活用しているかについて探ります。 *私たちは、エージェントの観測性に伴うシステム課題を解決するために SmithDB を構築しています。このようなインフラストラクチャ開発に興味がある場合、*[採用情報はこちら](https://www.langchain.com/careers#explore-jobs)*です。* ![image](https://cdn.prod.website-files.com/65b8cd72835ceeacd4449a53/69ce01ea562f8cc223cabf25_Frame%202147254328.svg) ## エージェントが実際に何をしているかを確認する LangSmith は、当社のエージェントエンジニアリングプラットフォームであり、開発者がすべてのエージェントの意思決定をデバッグし、変更の評価を行い、ワンクリックでデプロイできるように支援します。

SmithDB における全文検索：オブジェクトストレージ用の逆インデックス設計

背景や根拠まで確認しますか？

関連記事