vector_top_k JOIN with regular table causes pathological query plan (3700x slower than subquery)
メンテナーはふだん 11 日以内に返信
まだ誰も着手していません。
評価
- 難易度
- 4/5
- 見積もり時間
- 3〜5日
- 初心者へのやさしさ
- 38/100
- issue の種類
- バグ
- 明瞭さ
- おおむね明確
- 活発さ
- 停滞
- 領域
- databases, performance
調査の方向性
まず 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
- Use
CROSS JOINinstead ofJOIN(forces left-to-right evaluation) - Use
WHERE rowid IN (SELECT id FROM vector_top_k(...))instead of JOIN - 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:
- https://sqlite.org/forum/info/509bdbe534f58f20 (FTS5 JOIN: 170s vs subquery: 439ms)
- https://sqlite.org/forum/info/81e6aa8343402ba5 (virtual table covering index limitations)
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
環境構築
- Dockerfile または Docker Compose ファイルあり
- プルリクエストのテンプレートなし
- コントリビューションガイドを読む
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
tursodatabase/libsql のほかの issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
tursodatabase/libsql#2320 ·
メンテナーはふだん 11 日以内に返信
-
`cloudflare` feature: hrana streams are never closed対応中かも @pcbeingused333 が 4 日前に担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
tursodatabase/libsql#2312 ·
メンテナーはふだん 11 日以内に返信
-
bottomless: finished S3 upload tasks are never reaped, so sqld memory grows by ~10 KB per WAL batch対応中かも @pavanmanishd が 25 日前に担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 83/100
tursodatabase/libsql#2298 · コメント 1 件 ·
メンテナーはふだん 11 日以内に返信
-
Rust local Row::get_value truncates embedded NUL TEXT and panics on malformed UTF-8 (0.9.30)対応中かも @Sanjays2402 が 35 日前に担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 82/100
tursodatabase/libsql#2285 ·
メンテナーはふだん 11 日以内に返信
-
libsql-ffi: broken builds under Nix on macOS対応中かも @frectonz が 85 日前に担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 86/100
tursodatabase/libsql#2275 ·
メンテナーはふだん 11 日以内に返信
tursodatabase/libsql の issue をすべて見る
似ている issue
-
難易度 1/5 1時間未満 初心者へのやさしさ 92/100
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
JulianKemmerer/PipelineC#395 ·
-
upstream-blocked
難易度 2/5 1〜3時間 初心者へのやさしさ 65/100
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 76/100
-
難易度 2/5 1〜3時間 初心者へのやさしさ 70/100
libretro/parallel-n64#858 ·