How Graph Databases Actually Work (And When SQL Joins Stop Making Sense)

Quick Answer

A graph database stores nodes, edges, and properties directly, instead of reconstructing relationships through joins at query time. A real test against a 1,365-user network shows why this matters: going from 4 hops to 5 hops of traversal is a one-character change in networkx (cutoff=5), while the equivalent SQL query needs an entirely new, hand-written JOIN clause, and at 5 hops alone it returns 1,024 rows for only 1,024 actual distinct destinations — a count that would have included duplicates had the same node been reachable by more than one path.

The Data Model: Nodes, Edges, and Properties

This is not a post about vector databases. If you've read this site's posts on vector embeddings or vector databases, those are about representing meaning as coordinates in high-dimensional space and finding things that are mathematically similar. A graph database is a completely different data model, with nothing to do with embeddings or similarity search: it stores data as explicit nodes (entities, like a person or a product), edges (named, directed relationships between two nodes, like FOLLOWS or PURCHASED), and properties (key-value attributes on either). The question a graph database answers well isn't "what's similar to this?" — it's "what's connected to this, and how, and how far away?"

A relational database can represent the same information — a users table, a follows table with two foreign keys — and for most queries that's completely fine. The property graph model earns its place specifically when the question you're asking is about traversal: not "get me this row" but "starting from this node, follow these kinds of relationships outward, as many hops as it takes, and tell me what you find." That's the exact shape of question relational joins handle increasingly badly as the hop count grows, and graph databases handle natively, because of how they physically store relationships.

Why Relational Joins Struggle With Deep Relationships

In a relational database, a relationship between two rows isn't really stored — it's reconstructed at query time by matching a foreign key against a primary key, which is what a JOIN does. To answer "who does Alice's network reach in 3 hops," the database has to join the relationship table to itself three times: once to find Alice's direct connections, again to find their connections, again for the next layer. Each additional hop isn't a small addition to the query — it's an entirely new JOIN clause, and the number of rows those joins can produce grows with the branching factor of the data raised to the power of the hop count.

To make that concrete rather than asserted, I built a small "follows" network (1,365 users, branching factor 4, 5 levels deep) and ran the identical question — "who is reachable from the root user within k hops" — two ways against the exact same data: once as a graph traversal (via Python's networkx library, which models the index-free adjacency a real graph database uses), and once as a chain of SQL self-joins over the same edges loaded into SQLite.

Proving It: The Same Query, Two Ways, Real Numbers

The real, measured results from running both against the same 1,365-node graph:

• 1 hop: networkx finds 4 distinct reachable users; the SQL self-join (1 join) returns 4 rows.
• 2 hops: networkx finds 20; the SQL query (2 joins) returns 16 rows for this level alone.
• 3 hops: networkx finds 84 reachable in total; the 3-way self-join above returns 64 rows at this level.
• 4 hops: networkx finds 340 total reachable; a 4-way self-join returns 256 rows at this level.
• 5 hops: networkx finds all 1,364 non-root users reachable in one traversal call that took 0.396 milliseconds; the 5-way self-join (five JOIN clauses, written out by hand) returns 1,024 rows at this level and took 0.783 milliseconds for a dataset this small.

Two things are visible in that real output, not just asserted. First, the row counts explode with the branching factor raised to the hop count (4, 16, 64, 256, 1,024 — exactly 4^k) because the SQL query enumerates every distinct path, not every distinct destination. Second, and more important for how you'd actually write this: the networkx call to go from 4 hops to 5 hops is a one-character change (cutoff=4 to cutoff=5); the SQL version needs an entirely new JOIN clause hand-written into the query for every additional hop, which is exactly why relational databases don't offer a clean way to ask "however many hops it takes" — you cannot self-join an unknown number of times without either a hard-coded cap or recursive CTEs that effectively reimplement graph traversal inside SQL.

The Duplicate-Path Problem and Index-Free Adjacency

That row-explosion problem gets worse, not better, once a graph has more than one path to the same destination, which is normal in a real social network (two mutual friends both leading to the same third person). I tested this directly with a tiny diamond-shaped graph: A follows B and C, and both B and C follow D. Asking "who can A reach in 2 hops" via networkx correctly returns D once, as part of the distinct reachable set {B: 1, C: 1, D: 2}. The equivalent SQL self-join query against the exact same four edges returns D twice — [('D',), ('D',)] — because it found two separate paths (A-B-D and A-C-D) and SQL's JOIN has no concept of "I've already reached this node, don't count it again." Getting the distinct answer out of SQL requires remembering to add DISTINCT and hoping no other part of the query depends on counting paths rather than nodes.

A graph database avoids all of this with a storage structure called index-free adjacency: each node physically stores direct references to the relationships and nodes it's connected to, so moving from one node to its neighbors is a constant-time pointer-chase, not an index lookup followed by a join. Traversing further out simply means repeating that pointer-chase from each node you've already reached — the engine naturally tracks what it's already visited, the same way the networkx BFS above did, which is precisely why the distinct-node answer comes out right without extra DISTINCT logic bolted on.

Querying With Cypher (and Other Graph Query Languages)

Graph databases expose this traversal model directly in their query language instead of forcing you to write out one join per hop. Neo4j's Cypher (verified against Neo4j's own current documentation) uses an ASCII-art-like pattern syntax: (a)-[:FOLLOWS]->(b) literally reads as "node a, follows relationship, pointing to node b." Variable-length traversal — the exact thing that required a hand-written new JOIN per hop in SQL — is expressed with a range directly on the relationship: [:FOLLOWS*1..3] means "follow this relationship type repeatedly, between 1 and 3 times," with no change to the query's shape regardless of how deep that range goes:

// Cypher: Neo4j's graph query language, verified against Neo4j's
// own documentation. This answers "who does Alice reach within 3 hops
// of FOLLOWS relationships", matching the same question asked above.

MATCH (a:User {name: 'Alice'})-[:FOLLOWS*1..3]->(reached:User)
RETURN DISTINCT reached.name

// Compare to the equivalent single-hop pattern:
MATCH (a:User {name: 'Alice'})-[:FOLLOWS]->(b:User)
RETURN b.name

Cypher isn't the only graph query language in use. Gremlin (from Apache TinkerPop) takes an imperative, step-by-step traversal style instead of Cypher's declarative pattern matching, and is used by databases like Amazon Neptune and JanusGraph. SPARQL is the query language for RDF-style graphs (a different, more formal triple-based model, common in knowledge-graph and semantic-web contexts). GQL, ratified as an ISO standard, is a newer attempt at a vendor-neutral graph query language that several vendors are converging toward.

When Relational Is Still the Right Call

None of this means you should reach for a graph database by default. For the vast majority of application data — a user's own orders, a product catalog, one or two levels of "get this row and its direct parent" — a relational database with proper indexes is simpler, has more mature tooling, better transactional guarantees for most workloads, and a much larger hiring pool. The crossover point is specifically variable-depth or unbounded-depth relationship questions: fraud rings (is this new account connected, through any chain of shared devices or payment methods, to a known bad actor?), recommendation chains (people who are two or three steps removed in a social graph), permission inheritance in an access-control system, or dependency graphs in a build system. If your query naturally has the word "and then" repeated an unknown number of times in it, that's the graph database's territory.

You don't have to use a dedicated graph database engine to get this, either. Besides Neo4j, options include Amazon Neptune and ArangoDB (multi-model, with a graph query layer), Memgraph (an in-memory, Cypher-compatible engine built for real-time traversal), and even extensions to Postgres like Apache AGE that bolt Cypher-style querying onto a relational engine you may already be running. The right choice depends on how central graph traversal is to your workload versus how much you'd rather keep everything in one database you already operate.

Frequently Asked Questions