Technology · Graph database
Graph Databases
Specialized storage engines optimized for highly connected data and recursive graph traversals. Labeled property graphs, index-free adjacency, social relationships, fraud detection, graph sharding bottlenecks, and relational alternatives.
11 min read
Graph databases treat relationships between data points as first-class citizens. While relational databases model relationships through foreign keys and join tables, and document stores model them through embedded lists, graph engines store explicit pointers directly between nodes. This architecture makes traversing deep, multi-hop relationship paths orders of magnitude faster than evaluating recursive SQL joins.
Popular engines include Neo4j (the benchmark labeled property graph engine), Amazon Neptune, TigerGraph, and distributed frameworks like Apache HugeGraph.
When to reach for one
- Deep or variable-depth relationship traversals: Finding "friends of friends of friends", common connections between two arbitrary users, or degree-of-separation paths.
- Relationship-based access control (ReBAC / Zanzibar): Evaluating whether user Alice can read document Doc-42 through a deeply nested tree of teams, folders, and inherited group memberships.
- Fraud and AML ring detection: Uncovering suspicious circular money flows, shared phone numbers, or synthetic identities linking accounts across multiple hops in real time.
- Recommendation engines: Computing real-time collaborative filtering (for example, "users who liked this podcast also listen to these other three shows").
- Knowledge graphs and data lineage: Tracking dependency graphs of microservices, cloud resources, pipelines, and schema definitions.
If your dataset is tabular, writes are predominantly independent records, or queries scan flat collections (such as e-commerce checkout histories or metrics series), a relational or columnar database is far better suited.
The property graph data model
Most production graph databases use the Labeled Property Graph model:
- Nodes (Vertices): Discrete entities such as people, servers, accounts, or documents. Nodes hold labels (like
:Useror:Document) and key-value properties (name: "Alice",created_at: 1718000000). - Edges (Relationships): Directed, typed connections between two nodes (such as
:MEMBER_OF,:FOLLOWS,:OWNS). Edges are never dangling; they always connect a start node and an end node. - Properties on edges: Relationships can store properties directly, such as
weight: 0.85,since: 2021, orrole: "admin". - Index-free adjacency: Each node contains direct physical memory pointers to its incoming and outgoing relationships.
Index-free adjacency vs relational joins
In a relational database (like PostgreSQL), querying a 4-hop friendship chain requires joining the friendships table four times against itself:
SELECT f4.friend_id
FROM friendships f1
JOIN friendships f2 ON f1.friend_id = f2.user_id
JOIN friendships f3 ON f2.friend_id = f3.user_id
JOIN friendships f4 ON f3.friend_id = f4.user_id
WHERE f1.user_id = 42;Each join step performs an index lookup in logarithmic time O(log N). As the table grows to 100 million rows, each join step incurs significant B-tree traversal overhead, cache thrashing, and memory allocations.
In a graph database with index-free adjacency, the starting node is located once via an index. From that point forward, traversing to neighbor nodes follows direct physical memory or disk pointers in constant time O(1) per edge:
Relational Join Tables (B-Tree Lookups)
- Standard SQL syntax
- Easy to shard by primary key or hash
- Trivial single-row inserts and point updates
- Query latency scales with total table size O(log N)
- Deep joins explode memory and CPU usage
Pick it when: 1 to 2 hop known joins, transactional OLTP.
Graph DB (Index-Free Adjacency)
- Traversal latency depends only on visited subgraph size, not total graph size
- Natural syntax for paths and variable hops
- Traverses millions of hops per second per node
- Difficult to partition across multiple servers
- High memory requirements to keep the pointer graph in RAM
Pick it when: Variable depth queries (3+ hops), fraud detection, ReBAC.
Why sharding graphs is fundamentally hard
Relational, document, and key-value databases shard cleanly because records can be hashed by a partition key (user_id or tenant_id). Cross-shard queries are infrequent, and writes are localized.
Graphs, however, suffer from the graph partitioning problem:
Partitioning a graph to minimize cross-server edges (the Minimum Cut problem) is NP-hard. Furthermore, real-world graphs exhibit power-law distributions: a single celebrity node (like a public figure with 50 million followers) contains millions of edges, concentrating query load and preventing even distribution across shards.
Consequently, most production graph deployments adopt one of two architectural patterns:
- Vertical scaling with read replicas: Keep the entire graph on a single large server with 1 TB+ of RAM. Replicate the graph asynchronously to read replicas for query concurrency.
- Domain-separated graphs: Partition strictly by tenant ID if customers operate completely isolated subgraphs (common in B2B SaaS).
Alternatives: Adjacency lists in SQL and KV stores
Before introducing a specialized graph database into your production infrastructure, evaluate lightweight alternatives:
- Adjacency lists in Redis: Store forward sets in Redis sets (
SADD user:42:following 101 102). Intersecting two users' friends is a single, blazingly fastSINTER user:42:following user:99:followingexecuted in memory. - Recursive Common Table Expressions (CTEs): Modern PostgreSQL handles 2 to 3 hop traversals cleanly using
WITH RECURSIVE. If queries are shallow and bounded, Postgres avoids adding an extra datastore. - KV edge tables (TAO architecture): Meta's TAO stores nodes and edges in MySQL shards, fronted by an extensive write-through cache cluster. Edges are keyed by
(id1, edge_type, id2). This handles high-throughput 1-hop and 2-hop queries at massive scale without requiring index-free adjacency.
Numbers to quote
- Local RAM traversal speed
- 1,000,000 to 4,000,000 hops/sec per core
- Network hop penalty
- 100x to 1,000x slower per cross-machine hop
- Practical traversal depth
- 3 to 4 hops in real time; deeper requires batch algorithms
- RAM footprint
- 15 to 30 bytes per node and relationship pointer in memory
- B-Tree join vs pointer traversal
- Graph is 10x to 100x faster for 3+ hop queries
Where it bites
- The supernode (celebrity) bottleneck: Traversing through a node with 10 million edges stalls the traversal thread and floods memory buffers. Queries must enforce strict degree limits (e.g.
LIMIT 100). - Operational complexity: Graph databases have smaller open-source communities, fewer managed cloud offerings, and idiosyncratic query optimizers compared to relational mainstays.
- Bulk aggregations are slow: Counting all nodes matching a property across the entire database is an expensive full-graph scan. Use an analytical engine like ClickHouse for bulk metrics.
Try it
Relationship-based Authorization Service HLD
Design a low-latency authorization engine evaluated over a deep graph of users, groups, and permissions.