Repository navigation
Traversal 2 to 4x slower than raw SQLite: per-hop prepare, O(n) queue.shift #12
Description
Measurements (100k nodes, 500k edges, out-degree 5)
| Operation | sqlite-graph | raw better-sqlite3 + hydrate |
|---|---|---|
| traverse out unique depth 2 | 1.03ms | 0.22ms |
| traverse out unique depth 3 (~155 nodes) | 3.79ms | 1.10ms |
| shortestPath (any edge) | 1.66ms | 0.85ms |
toPaths on a 30-node, degree-4 graph: depth 5 = 1,364 paths in 19ms, depth 6 = 5,460 paths in 361ms (4x paths, 19x time).
Causes
getNode,getNeighbors,getAllNeighborscalldb.prepare()on every hop (TraversalQuery.ts:490,546,561). An interleaved A/B with a statement cache measured median ~4.0ms to ~2.7ms at depth 3.queue.shift()is O(n) per dequeue in all BFS loops.toPathscopies aSetper enqueued path.- In
unique()mode, nodes are marked visited on dequeue, so duplicates are enqueued before being discarded.
Not recommended
A naive recursive CTE was 10 to 90x slower than JS BFS (27ms at 1k, 290ms at 10k for depth 3), since it cannot keep a global visited set.
Benchmark report: 2026-11-02, Apple M2 Pro, Node 22, at a7f9ea7.
Activity
michaeloboyle commentedon Nov 2, 2026
Correction: the shortestPath row in this issue (1.66ms vs 0.85ms) is invalid. The benchmark's random pairs were correlated with the edge generator and all 30 sat at distance 2. With uncorrelated pairs, shortestPath takes ~2.5s at 100k nodes; tracked in #16. The traversal numbers here are unaffected.