When the relationships are the data. A query that needs four self-joins in SQL is one traversal here — but that specialization comes at a real cost.
Prerequisites: Relational Modeling, Choosing a Database Time to read: ~18 minutes
A social network. “Find friends of my friends who live in Lahore and work in tech, whom I don’t already follow.”
In SQL:
SELECT DISTINCT u2.*
FROM follows f1
JOIN follows f2 ON f2.follower_id = f1.followee_id
JOIN users u2 ON u2.id = f2.followee_id
LEFT JOIN follows f3 ON f3.follower_id = 1 AND f3.followee_id = u2.id
WHERE f1.follower_id = 1
AND u2.city = 'Lahore' AND u2.industry = 'tech'
AND f3.followee_id IS NULL;
Two hops. Already awkward. Now make it four hops (“people connected to me through up to four degrees”), and the SQL becomes a recursive CTE whose intermediate result sets explode.
📐 The arithmetic that kills it: with an average of 200 connections per person,
1 hop → 200
2 hops → 40,000
3 hops → 8,000,000
4 hops → 1,600,000,000 rows in the intermediate set
Each join is an index lookup over the whole follows table. The cost grows with total data
size, not with the size of the local neighbourhood you’re exploring.
🚨 This is the concept to know, and it’s the reason graph databases exist.
In a relational database, following a relationship means an index lookup — go to the B-tree, search for the key, find the rows. O(log n) against the whole table, for every hop.
In a native graph database, each node stores direct pointers to its neighbours. Traversing an edge is dereferencing a pointer — O(1), independent of graph size.
Relational: follow relationship → index lookup in a table of 5 billion rows
Graph: node → pointer → neighbour node (like following a linked list)
📐 The consequence: a 4-hop traversal in a graph database costs the same whether your graph has 1 million nodes or 1 billion, because you only touch the nodes you actually visit. In SQL, every join gets slower as the table grows.
That’s the entire value proposition. Everything else about graph databases follows from it.
Property graph — the common model (Neo4j, Neptune, JanusGraph):
(:Person {name: "Bilal", city: "Lahore"})-[:FOLLOWS {since: 2024}]->🚨 Relationships being first-class citizens with their own properties is the key modeling difference. In SQL a relationship is a row in a junction table; here it’s a traversable object.
Cypher (Neo4j’s query language) makes the traversal visual — the syntax literally draws the pattern:
MATCH (me:Person {id: 1})-[:FOLLOWS]->(friend)-[:FOLLOWS]->(fof:Person)
WHERE fof.city = 'Lahore' AND fof.industry = 'tech'
AND NOT (me)-[:FOLLOWS]->(fof)
AND me <> fof
RETURN fof, count(*) AS mutual_friends
ORDER BY mutual_friends DESC
LIMIT 20;
Compare that to the SQL above. The graph version reads like the question. Variable-depth traversal is a single character change:
MATCH path = (a:Person {id: 1})-[:FOLLOWS*1..4]->(b:Person {id: 999})
RETURN path ORDER BY length(path) LIMIT 1; -- shortest path, up to 4 hops
Writing that in SQL is a recursive CTE with cycle detection and manual depth limiting.
RDF / triple stores (subject → predicate → object, queried with SPARQL) are the other model —
used for knowledge graphs, semantic web, and ontologies. Less common in application development.
Use one when:
| Use case | Why |
|---|---|
| Social networks | Friends-of-friends, mutual connections, degrees of separation |
| Recommendations | “People who bought X also bought Y” is a 2-hop traversal |
| Fraud detection | Fraud rings are literally graph patterns — shared devices, addresses, cards |
| Knowledge graphs | Entities and their relationships, with inference |
| Network/IT topology | Impact analysis: “what breaks if this router fails?” |
| Permissions hierarchies | “Can this user access this resource through any group or role chain?” |
| Supply chain / dependency graphs | Multi-level impact and provenance |
| Identity resolution | Merging records that share attributes transitively |
🚨 The fraud detection case is the most compelling, because it’s a query that’s essentially impossible otherwise: “find groups of accounts connected by shared devices, IPs, or payment methods within 3 hops, where at least one is flagged.” In SQL that’s a nightmare; in Cypher it’s five lines. And the pattern — a ring of connections — is a graph structure by definition.
Don’t use one when:
⚖️ Graph databases are a specialized tool, and the trade-offs are real.
🚨 Sharding is genuinely hard. This is the biggest practical limitation. Partitioning a graph means cutting edges, and every cut edge becomes a network hop during traversal. There’s no partitioning that avoids this — graphs resist it by nature (this is the NP-hard graph partitioning problem). So most graph databases scale up, not out, and large graphs are a real operational challenge.
Compare to a relational database, where sharding by user ID keeps most queries local. A social graph has no such clean boundary — that’s the point of a social graph.
Other costs:
🚨 Most “we need a graph database” cases don’t. Try these:
1. Recursive CTEs in Postgres. For modest depth and modest graph size, this works well:
WITH RECURSIVE reachable AS (
SELECT followee_id, 1 AS depth FROM follows WHERE follower_id = 1
UNION
SELECT f.followee_id, r.depth + 1
FROM follows f JOIN reachable r ON f.follower_id = r.followee_id
WHERE r.depth < 3
)
SELECT * FROM reachable;
Fine for hierarchies, org charts, category trees, and shallow social queries.
2. Apache AGE — a Postgres extension adding graph queries with Cypher syntax. You get graph querying without a second database, which is often the right compromise.
3. Precomputed adjacency in a key-value store. For social feeds, storing each user’s follower list in Redis and intersecting sets in the application is frequently faster than a graph traversal — and this is what large social networks actually do at scale.
4. Denormalize the traversal result. If the query is “friends of friends” and it’s run constantly, precompute it. → Caching
5. A graph processing framework for one-off analytics (PageRank, community detection) — Spark GraphX, NetworkX — rather than a graph database.
🎙️ “I’d check whether a recursive CTE in Postgres handles this first. If traversals are the core query and go beyond 3 hops at scale, a graph database earns its place — but for a 2-hop ‘friends-of-friends’ on a moderate dataset, adding a second datastore isn’t justified.”
🚨 A useful reality check: Facebook does not run Neo4j.
Facebook’s TAO is a purpose-built distributed store for their social graph, built on sharded
MySQL with a very large caching layer. It handles objects (nodes) and associations (edges) with
simple, well-defined operations — assoc_get, assoc_count, assoc_range — and no general
traversal. At their scale, the winning design was a restricted graph API that shards cleanly, not
a general-purpose graph database.
Twitter’s FlockDB (now retired) was similar: a distributed store for adjacency lists, optimized for set operations (intersection, difference) rather than deep traversal.
The lesson worth taking: at extreme scale, social graphs are usually served by specialized sharded key-value stores with adjacency lists, because general graph traversal doesn’t distribute. Graph databases shine in the middle ground — complex traversals over graphs that fit on a few machines, where query expressiveness matters more than raw scale.
🎙️ “For a social feed at scale I’d use adjacency lists in a sharded key-value store rather than a graph database — Facebook’s TAO is essentially that. Graph databases are better for fraud detection or knowledge graphs, where traversals are genuinely deep and the graph fits on fewer machines.”
That’s a strong, non-obvious answer.
| Decision | Gain | Cost |
|---|---|---|
| Graph database | O(1) traversal per hop; expressive queries | Hard to shard; smaller ecosystem; weak aggregations |
| Recursive CTE in Postgres | No new system; SQL | Degrades with depth and graph size |
| Adjacency lists in a KV store | Shards cleanly; very fast for 1–2 hops | No deep traversal; application does the work |
| Precomputed traversals | Instant reads | Staleness; storage; recomputation cost |
| Apache AGE (Postgres extension) | Cypher without a second database | Less mature than Neo4j |
1. Feel the difference. Load a social graph (the SNAP datasets are free — try the Facebook or Twitter ego networks) into both Postgres and Neo4j. Run:
Plot the times against hop count. The two curves diverging is the whole chapter in one graph.
2. Write the same query twice. Take “shortest path between two users” and implement it as a
recursive CTE in Postgres and as shortestPath() in Cypher. Compare the code length and the
correctness edge cases (cycles!) you had to handle manually in SQL.
3. Build a fraud ring detector. Create accounts sharing devices and payment methods. Then in Cypher:
MATCH (a:Account)-[:USED_DEVICE]->(d:Device)<-[:USED_DEVICE]-(b:Account)
WHERE a <> b AND a.flagged = true
RETURN b, count(d) AS shared ORDER BY shared DESC;
Then try to express it in SQL. The difference in effort is the argument.
4. Try Apache AGE in Postgres — Cypher queries against a Postgres-backed graph. It’s often the best of both worlds for teams already on Postgres.