vector_top_k JOIN with regular table causes pathological query plan (3700x slower than subquery)

オープン
#2,212 コメント 0 件 リアクション 1 件 担当者 0 名 GitHub で見る

メンテナーはふだん 11 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
38/100
issue の種類
バグ
明瞭さ
おおむね明確
活発さ
停滞
技術スタック
c, sql, sqlite

調査の方向性

まず SQL の再現手順を実行し、vector_top_k の xBestIndex 周辺における SQLite の仮想テーブルプランナーの動作を調査します。JOIN と CROSS JOIN の場合、およびサブクエリによる回避策について、EXPLAIN QUERY PLAN とプロファイラーの結果を比較します。完了条件は、該当するエントリごとに 1 回ではなく xFilter が 1 回だけ呼び出され、再現可能な回帰テストがあることです。

索引モデルが issue の本文から書いたものです。

説明

Summary

When joining vector_top_k() with a regular table using JOIN ... ON, the SQLite query planner inverts the join order when the regular table has WHERE predicates. This causes the virtual table xFilter to be called once per row of the regular table instead of once total, resulting in catastrophic performance degradation.

Reproduction

Database: ~12,000 entries with 512-dim float32 embeddings, WAL mode.

-- Index definition
CREATE INDEX idx_entries_embedding ON entries (
  libsql_vector_idx(embedding, 'metric=cosine', 'compress_neighbors=float8', 'max_neighbors=50')
);

-- FAST (10ms): vector_top_k alone
SELECT id FROM vector_top_k('idx_entries_embedding', vector32(?), 50);

-- FAST (10ms): JOIN without WHERE clause on entries
SELECT e.id FROM vector_top_k('idx_entries_embedding', vector32(?), 50) AS v
JOIN entries AS e ON e.rowid = v.id;

-- SLOW (26,000ms, 100% CPU): JOIN with WHERE clause on entries
SELECT e.id FROM vector_top_k('idx_entries_embedding', vector32(?), 50) AS v
JOIN entries AS e ON e.rowid = v.id
WHERE e.superseded_by IS NULL;

-- FAST (6ms): CROSS JOIN forces correct order
SELECT e.id FROM vector_top_k('idx_entries_embedding', vector32(?), 50) AS v
CROSS JOIN entries AS e ON e.rowid = v.id
WHERE e.superseded_by IS NULL;

-- FAST (11ms): Subquery avoids join entirely
SELECT * FROM entries
WHERE rowid IN (SELECT id FROM vector_top_k('idx_entries_embedding', vector32(?), 50))
  AND superseded_by IS NULL;

Analysis

When the entries table has a WHERE predicate (superseded_by IS NULL), the query planner decides to scan entries first and probe vector_top_k in the inner loop. With ~11,500 qualifying rows, this means ~11,500 ANN searches instead of 50 rowid lookups.

V8 profiler confirms 99.9% of CPU time is spent in the libsql native module executing repeated vector searches.

The root cause appears to be that vector_top_k's xBestIndex does not report a high enough cost to prevent the planner from placing it in the inner loop when there are competing predicates on the joined table.

Workarounds

  1. Use CROSS JOIN instead of JOIN (forces left-to-right evaluation)
  2. Use WHERE rowid IN (SELECT id FROM vector_top_k(...)) instead of JOIN
  3. Split into two application-level queries

Environment

  • libsql native: 0.5.22
  • @libsql/client: 0.17.0
  • macOS arm64 (Apple M2)
  • Node.js v25.5.0

Notes

This is the same class of issue documented for FTS5 virtual tables on the SQLite forum:

The Turso DiskANN blog post (https://turso.tech/blog/approximate-nearest-neighbor-search-with-diskann-in-libsql) shows the WHERE rowid IN pattern first, suggesting awareness of this issue.

主要言語
C
スター
17.3k
フォーク
562
平均マージ
10日 15時間
マージ済み PR(30日)
1

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

tursodatabase/libsql のほかの issue

tursodatabase/libsql の issue をすべて見る

似ている issue

C の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。