SQLite Graph Accelerator

Problem

Many applications already store relationships in SQLite as foreign keys, but deep multi-hop traversals get slow in plain indexed SQL. Moving the data into a separate graph database means a second system to keep in sync.

Approach

• I built a loadable SQLite extension in Rust that discovers existing foreign keys and treats them as graph edges, so no data moves.
• Reads use a validated compressed sparse row (CSR) sidecar plus a small write overlay, and fall back to indexed SQL whenever the sidecar is stale, so SQLite stays the source of truth.
• SQL table functions cover neighbors, BFS and DFS traversal with filters, shortest path and weighted cheapest path.
• Every query is bounded by rows, depth, visited nodes and frontier size, and reports whether it was truncated and which backend served it.
• It is usable from Python, Node, Go and Rust, and the repo includes fuzz targets and numbered design-decision records.

Architecture

1. SQLite tables
2. FK discovery
3. CSR sidecar
4. Freshness check
5. Traversal or SQL fallback
6. Bounded result

Outcome

On the SNAP soc-Epinions1 graph (75,879 nodes, 508,837 edges), BFS was 4.7× faster than indexed SQLite at depth 4 and 26× faster at depth 6. The trade-offs: one-hop queries are no faster, and writes cost 3 to 10% more.

What I learnedA fast path is only safe with a correct fallback. Checking freshness on every query and dropping to SQL keeps results right when the sidecar lags behind writes.