Graph Databases
Graph databases (Neo4j, Amazon Neptune, Dgraph, TigerGraph, ArangoDB) store data as nodes and edges — first-class relationships. Where SQL needs expensive recursive JOINs to traverse connections, graph databases traverse relationships in O(1) per hop using index-free adjacency. They excel at social networks, recommendation engines, fraud detection, and any domain where 'how are these things connected?' is the dominant question.
Foundational.
How it works
A graph database models data as nodes (entities) and edges (relationships between entities), with both carrying properties (key-value attributes). The defining feature is index-free adjacency: each node stores direct pointers to its connected neighbors, so traversing an edge is a constant-time pointer dereference — no JOIN, no index lookup, no scan.
This is the opposite of the relational model, where relationships are inferred at query time by matching foreign keys across tables. In SQL, a friend-of-friend query is two JOINs; in a graph database, it's two pointer hops. The performance difference becomes dramatic as the graph depth grows.
Reference implementations:
- Neo4j — the dominant property graph; Cypher query language; ACID compliant; in-process clustering.
- Amazon Neptune — managed graph service supporting both property graph (Gremlin/openCypher) and RDF (SPARQL).
- Dgraph — horizontally-sharded graph database with GraphQL-native API.
- TigerGraph — designed for very large graphs and parallel traversal (used in finance).
Index-free adjacency is the key concept. In a relational database, finding Bob's friends requires looking up Bob's user_id in an index on friends.user_id, then reading those rows. If you then want friends-of-friends, you do it again — each hop is a separate index lookup that may span disk pages.
In a graph database, Bob's node physically stores pointers (or relationship records) to his friends. Finding his friends is a single pointer dereference; finding friends-of-friends is two. The cost depends on the number of edges traversed, not the size of the graph. A billion-node graph doesn't make 2-hop traversal slower — it makes 2-hop traversal as fast as on a thousand-node graph (assuming the working set fits in cache).
This is why graph queries that take minutes in SQL can take milliseconds in Neo4j at scale. But there's a flip side: graph databases don't naturally partition across machines. Neo4j's causal cluster replicates the entire graph to every node — horizontal write scaling is limited. Dgraph and JanusGraph partition graphs across machines but lose some index-free adjacency benefits when traversals cross shards.
The canonical question: is 'how are these connected?' a query you run often? If yes — friend recommendations, fraud rings, dependency graphs, network topology, knowledge graphs — a graph database will out-perform SQL by orders of magnitude. If your queries are mostly 'give me entity X by ID' or 'aggregate all rows matching predicate Y', a graph database is the wrong tool — it adds complexity for no gain.
Classic graph use cases:
- Social networks — friend recommendations, mutual connections, 'people you may know' queries traverse 2-3 hops efficiently.
- Recommendation engines — 'users who bought this also bought…' is a graph traversal: item → users who bought → other items those users bought. Amazon and Netflix variants of this exist.
- Fraud detection — fraud rings share phones, addresses, devices, payment methods. Finding a connected subgraph of suspicious accounts is a graph pattern match.
- Identity and access management (IAM) — users in groups that have roles that grant permissions is a graph; inheritance traversals are graph traversals.
- Knowledge graphs — Wikipedia/DBpedia, Google Knowledge Graph, enterprise taxonomies. Entity disambiguation and semantic queries are graph-native.
- Network and IT operations — dependency graphs, root-cause analysis (what depends on this failing service?).
- Routing and logistics — shortest-path queries on road or supply-chain graphs.
When NOT to use a graph database:
- Simple key-value access (use Redis/DynamoDB).
- Document-shaped aggregates (use MongoDB).
- Massive write throughput time-series (use Cassandra).
- Tabular analytics and aggregation (use a columnar warehouse).
- You only have a handful of relationships and can live with 1-2 JOINs in SQL.
The Achilles' heel of graph databases is horizontal scaling. The whole point — index-free adjacency — assumes you can dereference any edge locally. When you shard a graph across machines, edges that cross shards force network hops, and the O(1)-per-hop property degrades.
Neo4j addresses this by replicating the full graph to every cluster member; writes go to the leader, reads can be served by any follower. This is fine for read-heavy workloads (most graph use cases are) but limits write throughput to a single machine.
For sharded graphs, options include:
- JanusGraph — open-source, runs on top of a storage backend (Cassandra, HBase) and an index backend (Elasticsearch). Trades index-free adjacency for horizontal scaling.
- Dgraph — designed from scratch for sharding; uses Badger (a Go LSM tree) as storage, GraphQL-native API.
- Amazon Neptune — managed; supports both property graph (Gremlin, openCypher) and RDF (SPARQL); handles sharding internally.
If you need both deep traversals and horizontal scale, the trade-offs are real — usually you partition the graph by some subgraph (per-customer, per-tenant) so most traversals stay local.
You're building a fraud-detection feature: when a new account signs up, check if its phone, email, address, or device is shared with a known-fraudulent account within 3 hops. Which store is the best fit, and why?
Pick one answer.
Your team is considering migrating from PostgreSQL to Neo4j because 'graphs are cooler'. The app is a billing system: invoices, line items, customers, payments, all accessed by ID and joined 1-2 tables deep. What's the right call?
Pick one answer.
What does 'index-free adjacency' mean in a graph database, and why does it matter?
Pick one answer.
Why is horizontal scaling hard for graph databases?
Pick one answer.
Engineering mental model
Mental model. Think of Graph Databases as a deliberate boundary in a system. The boundary exists because something becomes harder to manage when everything is done in one place: latency, scale, failure isolation, consistency, cost, or team ownership. The useful question is not “what does Graph Databases mean?” but “what pressure makes this boundary worth introducing, and what new failure mode does it create?”
Before choosing Graph Databases, name the workload, the critical user path, the dominant bottleneck, the failure you are trying to absorb, and the trade-off you are willing to accept. If you cannot name those five things, the design is probably premature.
SELECT id, created_at
FROM records
WHERE tenant_id = ?
ORDER BY created_at DESC
LIMIT 50;
-- Ask: which index makes this query predictable at scale?Back-of-the-envelope reasoning
Example: 5M writes/day × 1 KB/row ≈ 5 GB/day of logical data. Add indexes, replication, backups and growth headroom before sizing a real store.
Interactive thought experiment: Graph Databases
Change the variables below and predict what breaks first in Graph Databases. The production lab can later reuse these same inputs.
Change one variable at a time. Predict the failure mode first, then move the slider and see whether your mental model matches the simplified system response.
If you are stuck on Graph Databases, start by drawing the request path and marking every network hop, stateful component, queue, cache and failure boundary. Then estimate where the system will saturate.
You increase traffic by 10× in a system using Graph Databases. What should you inspect first?
Pick one answer.
Which statement is the safest engineering habit when using Graph Databases?
Pick one answer.
You have dashboards for traffic, latency, errors and saturation. You can change the architecture, but every change has operational cost.
Production scenario: your system uses Graph Databases, traffic suddenly spikes, and p99 latency doubles. What is your first move?
Interview drill
Answer this without notes: When would you choose Graph Databases, and when would you intentionally avoid it? Mention at least one bottleneck it addresses, one failure mode it introduces, and one alternative. Then quantify the workload you are designing for.
For Graph Databases, start with access patterns rather than brand names. Identify the dominant reads/writes, data relationships, consistency requirements, partition key, hot keys and failure behavior before choosing a storage strategy.
Numerical sanity check
A rough capacity check: required write throughput ≈ peak writes/s × average record size. At 5,000 writes/s and 2 KB average payloads, the raw incoming data stream is about 10 MB/s before indexes, replication and overhead.
Do not optimize for a memorized definition. Reason from the workload and failure mode.
A team proposes Graph Databases because it 'scales'. What workload characteristic would make that choice a poor fit?
Pick one answer.
What you gain, what you pay
- +Multi-hop relationship queries are O(1) per hop — orders of magnitude faster than SQL JOINs for traversals.
- +Schema is naturally flexible — node and edge properties can vary, no migrations for new fields.
- +Cypher/Gremlin query languages express graph patterns concisely.
- +ACID transactions supported (Neo4j specifically).
- +Excellent for query patterns SQL handles poorly (recommendations, fraud, lineage).
- −Horizontal scaling is hard — index-free adjacency is fundamentally local.
- −Single-leader write throughput ceiling in Neo4j — not for high-write workloads.
- −Operational complexity — fewer DBAs know graph databases than SQL.
- −Smaller ecosystem — fewer tools, fewer ORMs, less community wisdom.
- −Not appropriate for tabular, key-value, or document-shaped data — adds overhead for no benefit.
- −Cross-shard traversals in sharded graphs (JanusGraph, Dgraph) lose the O(1)-per-hop property.
How this breaks in production
- Super-node problem — a node with millions of edges (a celebrity, a hub airport) makes traversals through it slow.
- Cross-shard traversal latency — sharded graphs pay network hops for edges crossing shards.
- Choosing a graph database when SQL would do — paying complexity tax for no benefit.
- Unbounded graph growth without compaction/cleanup — old nodes and edges accumulate.
- Write throughput bottlenecks in single-leader setups — Neo4j can't keep up with high-write event ingestion.
- Query patterns that don't match the graph shape — e.g., trying to use Cypher for analytical aggregations.
Don't fall into these traps
- •Migrating to a graph database without first checking if your queries actually need multi-hop traversal.
- •Modeling tabular data as a graph (every row a node, every foreign key an edge) — adds overhead with no benefit.
- •Not addressing the super-node problem — a few popular nodes dominate query time.
- •Assuming graph databases scale horizontally like Cassandra — they don't.
- •Picking Cypher/Gremlin/SPARQL without considering team familiarity and tooling.
- •Forgetting that graph queries can be expressed in SQL with recursive CTEs when the depth is shallow.
Real systems using this
How real systems implement this
- Neo4j at Cisco — Cisco uses Neo4j for identity and access management — role inheritance, permission propagation, and dependency graphs. Multi-hop queries ('who has access to this resource, directly or via group inheritance?') are graph-native.
- TigerGraph at financial institutions — TigerGraph is used by banks for real-time fraud ring detection — graph pattern matching over millions of accounts, devices, and transactions, finding suspicious subgraphs in milliseconds.
- Amazon Neptune — Managed graph service used by customers for fraud detection, recommendation engines, and knowledge graphs. Supports both property graph (Gremlin/openCypher) and RDF (SPARQL) on the same backend.
- LinkedIn — Maintains a graph database layer for connections and recommendations over its member graph — one of the largest production graph deployments, with custom sharding and traversal optimizations beyond off-the-shelf tools.
Practice saying it out loud
- Q1When is a graph database the right choice? When is it the wrong one?
- Q2Design a recommendation engine: 'users who watched X also watched Y'. Compare SQL, graph, and Cassandra-based implementations.
- Q3What is index-free adjacency, and why does it matter for performance?
- Q4Your Neo4j cluster is hitting write throughput limits. What are your options?
- Q5How would you detect a fraud ring in a graph of accounts sharing devices, phones, and addresses?
Further reading & references
Core explanations are original NO CAP material. External references are provided for deeper study and standards.
What next?
Mark as understood once the mental model clicks.
Next recommended
Denormalization