vector_top_k JOIN with regular table causes pathological query plan (3700x slower than subquery)
Maintainer thường phản hồi trong vòng 11 ngày
Chưa có ai nhận issue này.
Đánh giá
- Độ khó
- 4/5
- Thời gian dự kiến
- 3-5 ngày
- Mức phù hợp với người mới
- 38/100
- Loại issue
- Lỗi
- Độ rõ ràng
- Khá rõ ràng
- Mức độ hoạt động
- Đình trệ
- Lĩnh vực
- databases, performance
Hướng nghiên cứu
Bắt đầu bằng cách chạy bản tái hiện SQL và kiểm tra hành vi của bộ lập kế hoạch bảng ảo của SQLite xung quanh xBestIndex của vector_top_k. So sánh EXPLAIN QUERY PLAN và kết quả profiler cho JOIN so với CROSS JOIN, cũng như cho cách khắc phục bằng subquery. Được xem là hoàn thành khi xFilter được gọi một lần thay vì một lần cho mỗi mục đủ điều kiện, kèm theo một bài kiểm thử hồi quy có thể tái hiện.
Do mô hình lập chỉ mục viết ra từ nội dung của issue.
Mô tả
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.
- Ngôn ngữ chính
- C
- Star
- 17.3k
- Fork
- 562
- Merge trung bình
- 10 ngày 15 giờ
- Pull request đã merge (30 ngày)
- 1
Chuẩn bị môi trường
- Có Dockerfile hoặc tệp Docker Compose
- Không có mẫu pull request
- Đọc hướng dẫn đóng góp
Bắt đầu từ đâu
- Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
- Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
- Fork repository và làm thay đổi trên một nhánh.
- Mở pull request có tham chiếu số hiệu của issue.
Issue khác của tursodatabase/libsql
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 68/100
tursodatabase/libsql#2320 ·
Maintainer thường phản hồi trong vòng 11 ngày
-
`cloudflare` feature: hrana streams are never closedCó thể đã có người làm @pcbeingused333 đã nhận 4 ngày trước. Đang mở
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 72/100
tursodatabase/libsql#2312 ·
Maintainer thường phản hồi trong vòng 11 ngày
-
bottomless: finished S3 upload tasks are never reaped, so sqld memory grows by ~10 KB per WAL batchCó thể đã có người làm @pavanmanishd đã nhận 25 ngày trước. Đang mở
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 83/100
tursodatabase/libsql#2298 · 1 bình luận ·
Maintainer thường phản hồi trong vòng 11 ngày
-
Rust local Row::get_value truncates embedded NUL TEXT and panics on malformed UTF-8 (0.9.30)Có thể đã có người làm @Sanjays2402 đã nhận 35 ngày trước. Đang mở
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 82/100
tursodatabase/libsql#2285 ·
Maintainer thường phản hồi trong vòng 11 ngày
-
libsql-ffi: broken builds under Nix on macOSCó thể đã có người làm @frectonz đã nhận 85 ngày trước. Đang mở
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 86/100
tursodatabase/libsql#2275 ·
Maintainer thường phản hồi trong vòng 11 ngày
Tất cả issue của tursodatabase/libsql
Issue tương tự
-
Độ khó 1/5 Dưới một giờ Mức phù hợp với người mới 92/100
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 78/100
JulianKemmerer/PipelineC#395 ·
-
upstream-blocked
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 65/100
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 76/100
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 70/100
libretro/parallel-n64#858 ·