Crate sqlitegraph

Expand description

SQLite-based graph database with unified backend support.

sqlitegraph provides a lightweight, deterministic graph database for embedded Rust applications. It supports explicit SQLite, Native V3, and Combined backend modes through a unified API.

§Architecture

The crate is organized into focused modules:

sqlitegraph/
├── graph/           # Core graph database (SqliteGraph, GraphEntity, GraphEdge)
├── backend/         # Unified backend trait (GraphBackend, SqliteGraphBackend, NativeGraphBackend)
├── algo/            # Graph algorithms (PageRank, Betweenness, Louvain, Label Propagation)
├── hnsw/            # Vector similarity search (HNSW index, distance metrics)
├── cache/           # LRU-K adjacency cache for traversal optimization
├── introspection/   # Debugging and observability APIs
├── progress/        # Progress tracking for long-running operations
├── mvcc/            # MVCC-lite snapshot system
├── pattern_engine/  # Triple pattern matching
├── query/           # High-level query interface
└── recovery/        # Backup and restore utilities

§Features

Explicit Backend Modes: Choose SQLite, Native V3, or Combined mode through one config surface
Entity and Edge Storage: Rich metadata support with JSON serialization
Pattern Matching: Efficient triple pattern matching with cache-enabled fast-path
Traversal Algorithms: Built-in BFS, k-hop, and shortest path algorithms
Graph Algorithms: PageRank, Betweenness Centrality, Louvain, Label Propagation
Vector Search: HNSW approximate nearest neighbor search with persistence
MVCC Snapshots: Read isolation with snapshot consistency
Bulk Operations: High-performance batch insertions for large datasets
Introspection: Debugging APIs for cache stats, file sizes, edge counts
Progress Tracking: Callback-based progress for long-running algorithms

§Quick Start

use sqlitegraph::{open_graph, GraphConfig, BackendKind};

// Use SQLite backend (default)
let cfg = GraphConfig::sqlite();
let graph = open_graph("my_graph.db", &cfg)?;

// Or use Native backend (V3 experimental backend)
let cfg = GraphConfig::native();
let graph = open_graph("my_graph.db", &cfg)?;

// Or use Combined mode (SQLite-authoritative contract; CombinedGraphBackend today)
let cfg = GraphConfig::combined();
let graph = open_graph("my_graph.db", &cfg)?;

// Both backends support the same operations
let node_id = graph.insert_node(/* node spec */)?;
let neighbor_ids = graph.neighbors(node_id, /* query */)?;

§Backend Selection

§Feature Matrix

Feature	SQLite Backend	Native Backend	Combined Backend
Status	Stable	Experimental	Phase 2 authority seam
Authority	SQLite	Native V3	SQLite
ACID Transactions	✅ Full	✅ WAL-based	Delegates to SQLite today
Graph Algorithms	✅ Full support	✅ Full support	Delegates to SQLite today
HNSW Vector Search	✅ With persistence	✅ With persistence (V3 KV)	Delegates to SQLite today
Turbovec Acceleration	❌	✅ Feature-gated, large-vector routing	❌
MVCC Snapshots	✅	✅	Delegates to SQLite today
Pattern Matching	✅	✅	Delegates to SQLite today
Raw SQL Access	✅ Native	❌ Not supported	✅ Native
File Format	SQLite DB	Custom binary (V3)	SQLite DB
Default Traversal Runtime	SQLite table/index path	V3 edge-store / B+Tree path	SQLite table/index path today via `CombinedGraphBackend`
Optional materialized live reads	N/A	CSR runtime views	Untyped `neighbors()` / `bfs()` / `k_hop()` / `node_degree()` / `shortest_path()` via opt-in CSR fallback; specialist mode, not default
Atomic SQLite + graph materialization	N/A	N/A	Not yet implemented
Materialized freshness gate	N/A	Backend-local runtime versioning	`materialized_version >= authoritative_version` required
Incremental materialized maintenance	N/A	N/A	Combined mode refreshes affected CSR rows on edge insert/delete when `PreferMaterialized` is enabled

§When to Use SQLite Backend

Choose SQLite backend when:

ACID guarantees are critical for your application
Raw SQL access needed for complex queries or joins
Database compatibility with SQLite tools (sqlite3, DB Browser)
Mature ecosystem with third-party tooling
HNSW persistence required

§When to Use Native Backend

Choose Native backend when:

Performance is critical (faster reads/writes)
No external dependencies desired (pure Rust)
Fast startup with large datasets
Custom binary format (V3) acceptable
You can tolerate experimental backend status while native-v3 traversal uses CSR runtime views layered over the edge-store/B+Tree source of truth, with CSR/sharding still treated as experimental infrastructure

§When to Use Combined Backend

Choose Combined mode when:

You want an explicit SQLite-authoritative contract today
You intend to adopt future SQLite + graph materialization work without changing the public mode selection later
You want an explicit combined-mode type today, where CombinedGraphBackend preserves a separate public seam without yet providing a distinct atomic graph-materialization boundary
You may want to opt into materialized live traversal reads later via CombinedConfig, while keeping SQLite as the fallback authority
You accept the current tradeoff: modest cold-read gains in exchange for materially slower writes when PreferMaterialized is enabled, with no current end-to-end mixed-workload win
You want stale materialized views rejected automatically, not merely bypassed when rows are missing
You want an explicit rebuild/publish step via CombinedGraphBackend::publish_materialized_views()
You want incremental upkeep for affected live traversal rows without turning graph materialization into a second source of truth

§Thread Safety

§SqliteGraph is NOT Thread-Safe

SqliteGraph uses interior mutability (RefCell) and is not Sync:

use sqlitegraph::SqliteGraph;
use std::thread;

let graph = SqliteGraph::open("test.db")?;

// ❌ WRONG: Sharing graph across threads for writes
let graph_clone = graph;
thread::spawn(move || {
    graph_clone.insert_node(...)?; // DATA RACE!
});

// ✅ CORRECT: Use snapshots for concurrent reads
let snapshot = graph.snapshot()?;
thread::spawn(move || {
    let neighbors = snapshot.neighbors(node_id)?; // Thread-safe
});

§Concurrent Read Access

Use GraphSnapshot for thread-safe concurrent reads:

use sqlitegraph::{GraphSnapshot, SqliteGraph};

let graph = SqliteGraph::open("my_graph.db")?;

// Create multiple snapshots for concurrent reads
let snapshot1 = graph.snapshot()?;
let snapshot2 = graph.snapshot()?;

// Both snapshots can be used concurrently (thread-safe)
let handle1 = std::thread::spawn(move || {
    snapshot1.neighbors(node_id)
});

let handle2 = std::thread::spawn(move || {
    snapshot2.neighbors(node_id)
});

§Write Serialization

All writes must be serialized:

// ✅ CORRECT: Single thread for all writes
let graph = SqliteGraph::open("my_graph.db")?;
for i in 0..1000 {
    graph.insert_node(...)?;
    graph.insert_edge(...)?;
}

// ❌ WRONG: Concurrent writes
let graph = Arc::new(Mutex::new(graph));
let handle1 = thread::spawn(|| {
    let g = graph.lock().unwrap();
    g.insert_node(...)
});
let handle2 = thread::spawn(|| {
    let g = graph.lock().unwrap();
    g.insert_node(...)
});
// Even with Mutex, this can cause issues due to RefCell

§Error Handling

All operations return Result<T, SqliteGraphError>:

use sqlitegraph::{SqliteGraph, SqliteGraphError};

let graph = SqliteGraph::open("my_graph.db")?;

match graph.insert_node(node_spec) {
    Ok(node_id) => println!("Created node {}", node_id),
    Err(SqliteGraphError::EntityNotFound) => {
        println!("Node not found");
    }
    Err(SqliteGraphError::DatabaseError(e)) => {
        eprintln!("Database error: {}", e);
    }
    Err(e) => {
        eprintln!("Other error: {}", e);
    }
}

§Performance Comparison

§Read Performance

SQLite Backend: 10-100μs per neighbor lookup (cached: ~100ns)
Native Backend: 1-10μs per neighbor lookup (cached: ~100ns)
Cache hit ratio: 80-95% for traversal workloads

§Write Performance

SQLite Backend: 100-500μs per insert (transaction-batched)
Native Backend: 10-100μs per insert (transaction-batched)
Bulk insert: 10-100x faster with bulk_insert_entities()

§Memory Usage

Base overhead: O(V + E) for graph storage
Cache overhead: 10-20% additional memory
HNSW index: 2-3x vector data size

§Public API Organization

This crate exports a clean, stable public API organized as follows:

§Core Types

GraphEntity - Graph node/vertex representation
GraphEdge - Graph edge/relationship representation
GraphBackend - Unified trait for backend implementations
SqliteGraphBackend - SQLite backend implementation
[CombinedGraphBackend] - Combined-mode SQLite-authoritative wrapper
[V3Backend] - Native V3 backend implementation

§Configuration

BackendKind - Runtime backend selection enum
GraphConfig - Unified configuration for both backends
[CombinedConfig] - Combined-mode read/fallback configuration
SqliteConfig - SQLite-specific options
NativeConfig - Native-specific options
open_graph() - Unified factory function

§Operations

[insert_node()], [insert_edge()] - Single entity/edge insertion
bulk_insert_entities(), bulk_insert_edges() - Batch operations
[neighbors()] - Direct neighbor queries
[bfs()], [k_hop()], [shortest_path()] - Graph traversal algorithms
pattern_engine - Pattern matching and triple storage

§Graph Algorithms

pagerank - PageRank centrality
betweenness_centrality - Betweenness centrality
louvain_communities - Louvain community detection
label_propagation - Label propagation algorithm

§Vector Search

hnsw::HnswIndex - HNSW vector search index
hnsw::HnswConfig - HNSW configuration
hnsw::DistanceMetric - Distance metrics (Cosine, Euclidean, etc.)

§Utilities

SqliteGraphError - Comprehensive error handling
GraphSnapshot - MVCC snapshot system
GraphIntrospection - Introspection and debugging APIs
ProgressCallback - Algorithm progress tracking
recovery - Database backup and restore utilities

Re-exports§

pub use graph_opt::GraphEdgeCreate;
pub use graph_opt::GraphEntityCreate;
pub use graph_opt::bulk_insert_edges;
pub use graph_opt::bulk_insert_entities;
pub use graph_opt::cache_stats;
pub use index::add_label;
pub use index::add_property;
pub use mvcc::GraphSnapshot;
pub use mvcc::SnapshotState;
pub use mvcc::VersionedSnapshot;
pub use pattern_engine::PatternTriple;
pub use pattern_engine::TripleMatch;
pub use pattern_engine::match_triples;
pub use query::GraphQuery;
pub use recovery::dump_graph_to_path;
pub use recovery::load_graph_from_path;
pub use recovery::load_graph_from_reader;
pub use snapshot::SnapshotId;
pub use temporal::LineageBarcode;
pub use temporal::TemporalBarcode;
pub use temporal::TemporalPersistencePoint;
pub use temporal::compute_temporal_barcode;
pub use temporal::cycle_rank_snapshot;
pub use temporal::cycle_scc_barcode;
pub use temporal::scc_lineage_barcode;
pub use temporal::temporal_persistence_sweep;
pub use backend::native::v3::V3Backend as NativeGraphBackend;
pub use backend::BackendDirection;
pub use backend::ChainStep;
pub use backend::GraphBackend;
pub use backend::BackupResult;
pub use backend::EdgeSpec;
pub use backend::NeighborQuery;
pub use backend::NodeSpec;
pub use backend::SqliteGraphBackend;
pub use config::BackendKind;
pub use config::GraphConfig;
pub use config::NativeConfig;
pub use config::SqliteConfig;
pub use config::open_graph;
pub use errors::SqliteGraphError;
pub use graph::GraphEdge;
pub use graph::GraphEntity;
pub use graph::SqliteGraph;
pub use algo::async_traversal::bfs_async;
pub use algo::async_traversal::k_hop_async;
pub use algo::betweenness_centrality;
pub use algo::betweenness_centrality_with_progress;
pub use algo::label_propagation;
pub use algo::louvain_communities;
pub use algo::louvain_communities_with_progress;
pub use algo::pagerank;
pub use algo::pagerank_with_progress;
pub use progress::ConsoleProgress;
pub use progress::NoProgress;
pub use progress::ProgressCallback;
pub use progress::ProgressState;
pub use introspection::EdgeCount;
pub use introspection::GraphIntrospection;
pub use introspection::IntrospectError;
pub use cache::CacheStats;

Modules§

algo: Graph algorithms for centrality, community detection, and structure analysis.
backend: Backend trait bridging sqlitegraph with higher-level graph consumers.
backend_selector
bench_gates
bench_meta
bench_regression
bench_utils
bfs
cache: Bounded adjacency cache for graph traversal optimization.
config: Configuration for backend selection and backend-specific options.
cypher: Cypher-inspired query language for SQLiteGraph.
dsl
errors
graph: SQLite-backed graph database implementation.
graph_opt
hnsw: Hierarchical Navigable Small World (HNSW) Vector Search
index
inference: Graph-Based Inference Engine
introspection: Graph introspection APIs for debugging and observability.
multi_hop
mvcc: MVCC-lite snapshot system for SQLiteGraph
pattern
pattern_engine: Lightweight triple pattern matcher for SQLiteGraph.
progress: Progress tracking for long-running operations.
query
query_cache: High-level query cache layer for SQLiteGraph.
recovery
schema
sharding: CSR sharding for prompt-local subgraph traversal.
snapshot: Snapshot isolation for ACID compliance
temporal: Temporal topology analysis — SCC persistence barcode over the MVCC version chain (ported from geographdb’s temporal_persistence_sweep). Temporal topology analysis over the MVCC version chain.
typed_digraph

Structs§

Label
NodeId
PropertyKey
PropertyValue

Functions§

match_triples_fast: Execute cache-enabled fast-path pattern matching.