連続配置埋め込み索引¶

翻訳について: 正本は英語版です。日本語版が古い場合は英語版を参照してください。

ステータス: 2.5.x ラインへの提案。SCHEMA_VERSION は 13 のまま、新しいランタイム依存も増えません。返る答えは現行スキャンが既に返しているものとビット単位で同一です (同スコア行の順序を含みます)。

1. 何が変わり、何が変わらないか¶

ローカルのベクトル検索は、最新 MAX_MEMORIES 行をコサインで順位付けします。そのスキャンの phase 1 が、埋め込みを読み出します。

SELECT id, embedding FROM memories
 WHERE <isolation> AND embedding IS NOT NULL [AND <source>]
 ORDER BY created_at DESC
 LIMIT ?

基準機・768 次元 10 万行での実測では、時間の内訳は次のとおりです。

区間	時間	占有
SQLite の行読み出し (索引順・blob 込み)	485.9 ms	72.9%
`b"".join` + `frombuffer`	162.3 ms	24.4%
行列積そのもの	18.1 ms	2.7%
同じ演算を連続配置ファイルから	95.1 ms	7.0 倍速

律速は演算ではありません。保存されたバイト列を、Python オブジェクトを 1 行ずつ作りながら numpy 配列にするところです。本設計は (id, embedding) の供給元を、 numpy が求める形に既に並んだファイルへ移すだけで、他は何も変えません。

演算は意図して numpy のままにします。 この変更の価値は「厳密であること」であり、再実装が失うのはまさにその後半です。

同じバイト列での実測で、手書きの Go 内積は numpy と 77.9% の行で不一致でした (最大絶対差 1.9e-5)。しかも Go の 2 実装同士が、94.4% の行で食い違いました。すべては総和順序の問題で、ブロック化された BLAS の順序を手書きループで再現することはできません。

ある行の内積は他のどの行にも依存しないので、mat @ query_vec の呼び出しを保つ限りスコアは同一になり、既存の等価性ゲートはそのまま効きます。

ひとつ但し書きがあります。fallback の走査を、窓をチャンクで読む形にした後で実測して分かったことです。「同じ呼び出し」は「同じバイト列を同じ形で」までを含みます。

ある行の内積は他の行に依存しませんが、BLAS は行数でカーネルを選ぶため、プラットフォーム依存の閾値を下回ると最下位ビットが動きます。Apple Accelerate では、64 次元で 64 行未満、768 次元で 16 行未満の行列が窓全体の結果と約 1 ULP 食い違い、それより大きい行列はすべてビット一致しました。

索引は選択した行を 1 つの行列として採点し、走査は今では 512 行以上のチャンクで採点します (短い尾は直前のチャンクに併合します)。したがって、どちらもこれまでに測った閾値の上に留まります。テストはこれを仮定せず、走るその機械で実測します。

2. 索引が保たねばならない不変条件¶

走査窓は MAX_MEMORIES のままにします。索引はコーパス全域を見ることもできますが、今日より多くの行を順位付けするスキャンは違う答えを返します。それは別のゲートを必要とする別の機能であって、本設計ではありません。

行の順序は created_at DESC、次に id ASC です。この順序が tie-break そのものです。survivors は scan 順を保ち、top-limit のカットは scan 順へ戻し、 heapq.nlargest は安定です。

しかもこれは順序だけでなく、membership も決めます。created_at を共有する行の群を limit が切るとき、生き残るのは id の小さい方です。本番コーパスでは 1.6% の行が同一 agent の別の行と created_at を共有しており (最大 9 行)、普通のテスト fixture には現れない程度に稀で、稼働中には起きる程度には多いという頻度帯にあります。

さらに、その順序を継承するのでなく明示します。現在 id ASC は、末尾列が created_at DESC である索引を SQLite が歩く副産物にすぎず、SQL は一切それを要求していません。加えて、ある軸の組み合わせは索引走査ではなくソートに解決します。ソータは安定を保証しません。

, id ASC の追加は仮定せず実測しました。ソートを誘発する項は、この作業が速くしようとしているスキャン自体の費用になるからです。結果は全ケースで同一順序・同一プランでした。測定記録: benchmarks/measurements/results-scan-order-stability.md。

スキャンの他の部分は触りません。 2 段構成、hydrate 前の limit カット、isolation 軸を再適用する by-id hydrate は、すべてそのままです。

3. 索引は権威ではない¶

isolation_where() が isolation 述語の単一の出所であり続け、hydrate はそれを再適用し続けます。索引が軸の列を持つ理由はただ 1 つ、top-k のカットが hydrate より前に起きるからです。

軸を無視する索引はコーパス全体を順位付けし、hydrate が後で落とす行で top-k を埋め、短くて誤った答えを返します。バケットがコーパスに対して小さいほど、被害は大きくなります。

したがって索引はフィルタしますが、「その行が誰のものか」について正しいことは決して求められません。義務は一方向だけです。

索引候補 ⊇ 権威が認める行

索引のフィルタが	起きること	深刻度
緩すぎる	hydrate が余分を落とす	正しい。無駄なだけ
厳しすぎる	行が気づかれずに消える	検出不能な recall 損失

守るのは片側だけなので、機械検査できます。ランダムなコーパスとランダムな軸値で包含を assert し、故意に厳しくした索引でそれが赤くなることを変異で確認します。

4. ファイル形式¶

ヘッダと、それに続く固定幅の並走配列です。

部位	内容
ヘッダ	マジック、形式版、次元、dtype、行数、watermark、および埋め込みモデル・次元・スコアリング版にわたる fingerprint
`embeddings`	`float32[count][dim]`、連続配置、正規順序
`ids`	`int64[count]`
`agent_code` / `project_code` / `channel_code` / `source_code`	`int32[count]`、ヘッダ内の小さな文字列表に intern
`created_at`	固定 19 バイト ASCII、列の正規形 `YYYY-MM-DD HH:MM:SS`

agent_code は isolation 述語が等値で比較する軸を担い、残る 3 つは小さな集合との比較になります。いずれにせよ、行ごとの判定は整数の比較です。

軸は低カーディナリティなので、intern は安価です。本番コーパスで agent 7 種・ project 12 種・channel 15 種・source id 38 種。軸一式で 1 行あたり 16 バイト、隣にある埋め込みは 3,072 バイトです。

source_code が存在するのは、カーディナリティを仮定せず実測したからです。source フィルタは JSON フィールドへの前方一致で、一見「索引には無理なもの」に見えます。しかし値が 38 種なら、前方一致は文字列表に対して小さなコード集合へ解決でき、行ごとの判定は整数の所属判定になります。これが無いとマルチユーザー会話からの recall はすべて旧経路に落ち、それは実トラフィックの相当部分にあたります。

形式で表現できない行は、落とさずに列挙します。 正規の 19 文字形から外れた created_at (import 経路が復元レコード自身の値を持ち越します) は配列から除外し、その id をヘッダに列挙します。クエリ経路は後述の tail 読み出しにその列挙を合流させるので、行は到達可能なままです。

列挙には上限があり、超えたらビルダーは構築を拒否します。穴の空いたコーパスを、それと告げずに提供するより、現行経路に留まる方が正しいからです。本番コーパスではこの列挙は空でした。両テーブルとも、created_at はすべて正規形です。

固定幅 ASCII であることが、merge の安全性を作ります。SQLite はこれらの値をテキストとして比較し、この形式の同一長文字列では、バイト比較と時系列比較が同じ比較になります。

5. 鮮度 — watermark¶

記憶システムにとって、陳腐化した索引は遅い索引より悪いものです。1 時間前に構築された索引は直近 1 時間の記憶を、それと告げずに落とします。そしてそれは最も引かれやすい記憶です。

索引は構築時点の最大 id を記録し、その watermark 以下の行にしか答えない。スキャンはそれを超える分を SQLite から厳密に読む。

ここから 5 つが従います。これが「再構築スケジュール」ではなく本設計である理由です。

新しい記憶が見えない窓が存在しなくなります。 「窓が小さい」ではなく、窓が無いということです。
再構築の頻度が correctness の問題でなくなり、純粋な性能ノブになります。遅れれば tail が伸びてレイテンシが観測可能に劣化するだけで、誤った答えは返しません。
tail は厳密です。 最も引かれやすい最新の行が、派生物から提供されることはありません。
削除に索引側の経路が一切不要です。 構築後に消えた行は候補には出ますが、hydrate が fail-closed で落とします。索引に delete も修復も compaction も要りません。壊れたら捨てて作り直します。
tail の読み出しは SQLite が最も得意な形 (索引順の最新数行) です。

watermark が答えられる問いは 1 つで、重要な問いはそれだけではありません。 watermark が示せるのは「その行が build 時に存在したか」であり、「その行が build 時に embedding を持っていたか」は示せません。

ベクトルがまだ NULL で builder が飛ばした行では、この 2 つが分かれます。その行は行列に入らず、id は watermark 以下なので tail も読まず、保守が embedding を埋めた瞬間に scan は返し、索引は返さなくなります。これは本節が冒頭で否定している「誰にも気づかれずに取りこぼす」状態そのもので、しかも到達経路は check_health(fix=True) です。その prefetch は、まさにそういう行を埋めるために存在します (bug-278)。

そこで build は、それらも列挙します。unembedded_ids がヘッダで excluded_ids の隣に並び、同じ exact な tail 読み出しに乗ります。上限は 2 つのリストの合計に掛かります (同じ文にバインドされるためです)。超えたコーパスは、自分の穴を列挙できない索引を出荷するのではなく、build を辞退します。

merge は ordered merge であって concatenation ではありません。 tail は索引より一様に新しいと仮定して前に繋ぎたくなりますが、それを保証するものはありません。

import 経路は復元レコードの元の created_at を持ち越す一方、id は AUTOINCREMENT で新規採番されます。そのため、古い export を既に新しい行を持つ DB に戻すと「新しい id × 古い created_at」が生まれます。本番コーパスに今日その逆転はありませんが、それは誰にも気づかれずに真でなくなる類の事実です。

両側とも既にソート済みなので、(created_at DESC, id ASC) で merge しても前置と費用は変わらず、この故障モードだけが消えます。

6. 不在・破損・次元不一致¶

索引は最も強い意味で任意です。置き換えられる側のスキャンはそのまま残り、正しいままであり、フォールバックであり続けます。3 つの条件がそこへ戻します。ファイルが無い、ファイルが自身の整合検査 (行数とファイル長、または fingerprint) に落ちる、クエリベクトルの次元がヘッダと一致しない、の 3 つです。

モデル入れ替えの途中で残る混在次元のコーパスは第 4 の条件で、これは読み手ではなく ビルダーが拒否します。

現行スキャンは、幅違いの行を skip する前に窓を適用します。最新 MAX_MEMORIES 行の中で生き残ったものを順位付けするということです。単一幅しか持たない索引は、他の幅が存在する限り、その窓を再現できません。自分の幅の最新 MAX_MEMORIES 行を順位付けてしまうからで、それは行数が増えるということです。各行のスコアが同一でも、行数が違えば答えが違います。

よってコーパスが混在している間は、ビルドを拒否します。この状態は構造的に一時的で、その間ずっと、この索引が置き換える側のスキャンは正しいまま (ただ遅いだけ) です。それこそ、本設計全体が安全に行おうとしている取引です。

フォールバックは見えなければなりません。 痕跡がログ 1 行だけなら、1 週間死んでいる索引は「なぜか速くない」としか読めません。このプロジェクトが、既に一度犯した失敗です。この条件は、システムの健全性を読む者が出会う場所に報告します。

7. 本設計が意図的に含まないもの¶

あらゆる近似。 量子化も近傍近似も行いません。それらが買うのは常駐メモリであり、「どこまでの劣化を許すか」という別の問いを伴う別の問題です。混ぜれば、この変更を既存スイートで検定可能にしている厳密性を失います。
第 1 弾での episodes。 ただし、その後も外したままにはしていません。episode 側のスキャンは構造的に同一で、形式もそのまま適用できましたが、episodes は行数の 5 分の 1 だったので、第 1 弾は memories だけを索引化し、次の一手は測定に委ねました。

測定の答えは、索引の無い episode スキャンが、5 倍の行数を持つ索引済み memory スキャンよりクエリあたり高い、でした。そこで episode テーブルも自分の索引ファイルを持ち、同じ読み出し経路で供給されます。episodes には source 列が無いので、読み出し経路は索引を引く前に episode スキャンの source 規則を適用します。索引がテーブルに無い列を問われることはありません。 - 修復。 索引は派生物です。backup せず、直しもしません。削除して作り直します。 - 構築後の再タグ付け。 行を別の project / channel へ移すと、索引の軸列は次の再構築まで古いままです。緩い方向は hydrate が救い、厳しい方向は再構築まで取りこぼします。再タグ付けは稀なので、これは解決せず受容します。次の読み手が自分で発見せずに済むよう、ここに明記します。

8. どう検定するか¶

等価性ゲートは既に存在します。本リポジトリのベンチマークハーネスは連続行列を事前ロードし、同じ mat @ q を呼び、無改変の検索と 2 つの水準で比較します。結果 id 列とそのコサイン、そして recall 経路全体の message id 列を、実コーパス上で比較します。これは置き換えではなく、バックエンドの追加として使います。

既存ゲートには見えないものが 2 つあるので、それを足します。

同スコア行。 十分に分離したベクトルのコーパスは、どんな tie-break でも同じ順位になります。等しい類似度の行を含む fixture を与えなければ、ゲートは一度も試していない順序を「一致」と報告します。
軸付きクエリ。 既存ハーネスは channel / project / source フィルタがあると元の関数にフォールバックするので、軸を持つ呼び出し (つまり実運用のほぼ全て) は一度も通っていません。

等価性ゲートと包含 assert の両方を、変異で確認します。故意に 1 箇所崩した順序はゲートを赤くしなければならず、故意に厳しくした索引は包含テストを赤くしなければならず、各変異が自分の検査だけを殺すことを確認します。