How SQLite Graph Storage Handles Traversal and Search Efficiently

The SQLite graph storage system achieves efficient traversal and search by mapping graph operations to indexed relational queries, utilizing B-tree indexes on qualified names and composite edge keys, while an in-memory buffer enables bulk persistence via direct page writes.

The repository implements a hybrid architecture that maintains an in-memory graph buffer before persisting to a SQLite backend. This design leverages SQLite's native indexing capabilities to transform expensive graph traversal operations into fast index lookups, achieving logarithmic complexity for node retrieval and sub-linear scans for edge operations.

Hybrid Architecture: In-Memory Buffer with Indexed SQLite Persistence

The system maintains the entire program graph in memory using the graph buffer (src/graph_buffer/graph_buffer.h and src/graph_buffer/graph_buffer.c) before dumping to disk. This two-phase approach allows for rapid bulk insertion while ensuring the on-disk representation supports efficient querying through strategic indexing.

Schema Design for Fast Lookups

The SQLite schema employs targeted indexes that convert graph traversal into relational algebra operations. The nodes table includes a UNIQUE index on qualified_name (idx_node_qn), providing O(log N) direct access to nodes by their fully-qualified identifiers. For edge traversal, the edges table utilizes a composite index on (source_id, target_id, type) (idx_edge_src_tgt_type), enabling the engine to fetch all outgoing or incoming edges through single indexed range scans. Additional indexes on idx_node_label and idx_edge_type support bulk searches via cbm_gbuf_find_by_label for nodes by label or edges by type without table scans.

Optimized Traversal Strategies

Traversal operations translate to prepared SQL statements that exploit these indexes, avoiding full table scans.

Node Retrieval by Qualified Name

The most common access pattern—locating a node by its fully-qualified name—utilizes the unique index idx_node_qn. The function cbm_gbuf_find_by_qn maps to a query that performs an index seek rather than a linear scan, critical during indexing and query processing.

Edge Traversal with Composite Indexes

Graph traversal becomes a series of fast SELECT operations through the cbm_gbuf_find_edges_by_source_type function. This API generates queries like SELECT target_id FROM edges WHERE source_id=? AND type=?, which hit the composite index idx_edge_src_tgt_type to retrieve connected nodes instantly.

JSON Property Indexing

Node and edge properties store as JSON blobs, but the SQLite JSON1 extension enables indexed property access. The system creates indexes like CREATE INDEX idx_node_props ON nodes(json_extract(properties_json, '$.key')), allowing predicate filtering on structured metadata without deserialization overhead.

High-Performance Bulk Operations

The system optimizes the write path to minimize persistence overhead.

Direct-Page Bulk Dumping

The cbm_gbuf_dump_to_sqlite function implements a direct-page writer that bypasses standard transaction overhead, writing SQLite pages directly. IDs pre-allocate via an atomic counter, ensuring sequential storage that maximizes B-tree efficiency during the bulk insert.

Prepared Statement Caching

Traversal helper functions utilize cached prepared statements. The preparation cost pays once, while subsequent traversals execute against indexed tables with minimal overhead, as demonstrated in the benchmark scripts (scripts/benchmark-search-graph.sh).

Incremental Maintenance Without Full Rebuilds

The storage supports efficient updates through cbm_gbuf_delete_by_file, which issues targeted DELETE FROM nodes WHERE file_path=? operations. Foreign key constraints cascade edge deletions automatically, keeping the graph synchronized with minimal I/O compared to complete rebuilds.

Implementation Examples

The following code demonstrates the API usage that leverages these optimizations, as tested in tests/test_graph_buffer.c:

// 1️⃣ Upsert a node – the buffer guarantees O(1) insert and later
//    the SQLite dump creates the UNIQUE index on qualified_name.
nodeID := cbm_gbuf_upsert_node(gb,
    "class",               // label
    "User",                // name
    "my.pkg.User",         // qualified_name
    "src/user.go",         // file_path
    12, 20,                // start/end line
    `{"visibility":"public"}`)

// 2️⃣ Find a node by its qualified name (used during traversal)
node := cbm_gbuf_find_by_qn(gb, "my.pkg.User")
if node != nil {
    fmt.Printf("found node %d at %s\n", node.id, node.file_path)
}

// 3️⃣ Get all outgoing edges of a given type (graph traversal)
var edges []*cbm_gbuf_edge_t
var cnt int
cbm_gbuf_find_edges_by_source_type(gb, node.id, "inherits", &edges, &cnt)
for _, e := range edges {
    fmt.Printf("inherits → node %d\n", e.target_id)
}

// 4️⃣ Search nodes by label (e.g. all functions)
var fnodes []*cbm_gbuf_node_t
cbm_gbuf_find_by_label(gb, "function", &fnodes, &cnt)

// 5️⃣ Persist the whole graph to SQLite (one‑shot bulk dump)
err := cbm_gbuf_dump_to_sqlite(gb, "/tmp/project_graph.db")
if err != nil { log.Fatal(err) }

Summary

• SQLite graph storage achieves efficient traversal through strategic B-tree indexes on qualified names and composite edge keys
• The JSON1 extension enables indexed property queries without full blob deserialization
• Bulk persistence via cbm_gbuf_dump_to_sqlite uses direct-page writes for optimal write performance
• Incremental updates via file-path deletion avoid costly full graph rebuilds
• Prepared statement caching eliminates repeated query compilation overhead

Frequently Asked Questions

How does the SQLite graph storage achieve O(log N) node lookup?

The storage creates a unique index idx_node_qn on the qualified_name column of the nodes table. This index transforms node lookups into B-tree seeks, reducing complexity from O(N) linear scans to O(log N) index operations.

What indexing strategy enables fast graph traversal in SQLite?

Traversal relies on a composite index idx_edge_src_tgt_type covering (source_id, target_id, type). This allows the engine to retrieve all edges for a given source node and type through a single indexed range scan, effectively turning graph traversal into fast relational queries.

How does the system handle property searches on JSON data?

The implementation uses SQLite's JSON1 extension with functions like json_extract and json_each. The system creates specialized indexes on extracted JSON keys, enabling sub-linear property searches without loading entire JSON blobs into application memory.

Why is bulk dumping faster than individual INSERT statements?

The cbm_gbuf_dump_to_sqlite function writes SQLite pages directly, bypassing the usual transaction overhead and row-by-row processing. Combined with pre-allocated sequential IDs via atomic counters, this approach achieves near raw-disk write speeds compared to transactional INSERT overhead.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}