Concrete scenario
A fraud check must traverse variable-depth relationships among accounts, devices, and cards, while a user page needs only direct friends.
Mechanics
Relational recursive queries and graph adjacency traversal both cost work proportional to the visited structure, filters, indexes, and cache behavior; there is no general O(log N)^D rule. Graph stores make relationships first-class and can avoid repeated global index lookups for each hop.
Failure mode
A supernode can expand to millions of edges, exhausting a latency budget. Partitioning a connected graph and maintaining relationship updates can also be difficult.
Trade-off
Graph databases improve expressive traversals and relationship-centric models, but add another query language and operational system. Bounded indexed joins can remain simpler and fast in SQL.
Worked example: fraud ring detection
Question: "Find accounts within 4 hops of a flagged account through shared devices, cards, phone numbers or addresses."
- Graph: 100M accounts, 300M devices, cards and phones, and 1B edges. Average degree per account is about 5.
- A naive 4-hop expansion touches roughly 5^4 = 625 nodes, but real graphs have skew. One shared public-WiFi "device" might connect 200k accounts.
In SQL (Postgres recursive CTE):
WITH RECURSIVE reach(id, depth) AS (SELECT 'acct_1', 0 UNION SELECT e.dst, r.depth + 1 FROM reach r JOIN edges e ON e.src = r.id WHERE r.depth < 4) SELECT DISTINCT id FROM reach;
Each hop is an index lookup on edges(src): about 3-4 B-tree page touches per expanded node. For 625 nodes that is about 2,500 page touches, a few milliseconds when cached, which is perfectly fine. Trouble starts with deeper or variable-length paths, cycle detection, shortest-path and pattern matching, where the SQL becomes hard to write and optimize.
In a native graph (Neo4j):
MATCH (a:Account {id:'acct_1'})-[:USES*1..4]-(b:Account) RETURN DISTINCT b
Each hop follows stored relationship pointers. The query is also far easier to express and change.
Decision table
| Workload | Relational | Graph database |
|---|---|---|
| Fixed 1-2 hop joins (friends list, order to items) | Best: simple, indexed | Overkill |
| Hierarchies (org chart, categories) | Good: recursive CTE, ltree, closure table | Good |
| Variable-depth paths, shortest path, cycles | Painful SQL, unpredictable plans | Natural fit |
| Pattern matching (fraud rings, knowledge graphs) | Hard | Natural fit |
| Heavy aggregation over all nodes (PageRank on billions) | Poor | Better done in batch graph engines (Spark GraphX, Pregel-style) |
| Planet-scale social graph lookups | Sharded SQL behind a graph-aware cache | Rarely a general graph database |
How real systems do it
- Meta TAO: a graph API ("objects and associations") backed by sharded MySQL and a massive cache. Mostly 1-hop queries at huge scale.
- LinkedIn: custom in-memory graph services (LIquid) for degree-of-connection queries.
- Banks and fraud teams: commonly Neo4j, TigerGraph or Amazon Neptune for investigative multi-hop queries.