Oh My Learning

Neo4j: Graph Modeling and Traversal-Centric Query Design

seven-databases/06 mid drafted · 8 min read

Seven Databases in Seven Weeks (Perkins, Redmond, Wilson), Chapter 6

Prerequisites seven-databases/01 seven-databases/02

Neo4j: Graph Modeling and Traversal-Centric Query Design#

TL;DR#

Neo4j stores data as nodes and relationships (a property graph), with each relationship physically stored as a direct pointer between two nodes — so traversing a connection is a cheap pointer-follow, not a join, and traversal cost stays roughly constant regardless of total database size. It is the right tool specifically when the relationships themselves — not just the entities — are what your queries need to explore, especially at variable or unknown depth.

The idea#

PostgreSQL (seven-databases/02) can represent relationships via foreign keys, and can even answer "friends of friends" with a self-join. But each additional hop is another join, and a query for "friends of friends of friends, at any depth up to 6" either needs a fixed number of joins written in advance or a recursive CTE that gets progressively more expensive as the graph grows — because a relational join, even an indexed one, generally costs more as the table (and the intermediate result sets) grow.

Neo4j inverts this: instead of computing relationships at query time by matching foreign key values across tables (which requires scanning/index-probing proportional to data volume), it stores each relationship as a direct, physical link between two node records — "index-free adjacency." Traversing from one node to its neighbors is then a fixed-cost pointer dereference, regardless of how many other nodes and relationships exist in the entire database. This is the single fact that explains why Neo4j is dramatically faster than a relational join for deep, variable-length traversals, and no better (often worse) for the kind of flat, aggregate-heavy queries relational databases excel at.

How it works#

The property graph model, concretely#

A social/professional network might model:

(Dana:Person {name: "Dana Lee"})
(Sam:Person {name: "Sam Ortiz"})
(Neo4jCo:Company {name: "Acme Corp"})

(Dana)-[:KNOWS {since: 2020}]->(Sam)
(Dana)-[:WORKS_AT {role: "Engineer"}]->(Neo4jCo)
(Sam)-[:WORKS_AT {role: "Designer"}]->(Neo4jCo)

Nodes have labels (Person, Company) and properties (name); relationships are directed, typed (KNOWS, WORKS_AT), and can themselves carry properties (since, role). This is richer than a plain graph (nodes and edges only) — it's a property graph, meaning both nodes and relationships carry arbitrary key-value data, which is what makes it expressive enough to model real domains directly rather than as an abstraction layered on top of a generic graph.

Cypher: pattern-matching as the query paradigm#

Neo4j's query language, Cypher, describes the shape you're looking for using an ASCII-art-like syntax, rather than describing joins:

MATCH (p:Person {name: "Dana Lee"})-[:KNOWS]->(friend)-[:WORKS_AT]->(c:Company)
RETURN friend.name, c.name

This reads almost like the diagram above: find a Person named Dana Lee, follow a KNOWS relationship to a friend, follow that friend's WORKS_AT relationship to a Company, return the friend's name and company. There is no explicit join clause because the pattern is the join — Cypher's engine walks the physical relationship pointers directly.

Variable-length traversal — where the model earns its keep#

Worked example. "Find everyone reachable from Dana within 1 to 4 KNOWS hops":

MATCH (p:Person {name: "Dana Lee"})-[:KNOWS*1..4]->(reachable)
RETURN DISTINCT reachable.name

In PostgreSQL, the equivalent needs a recursive CTE that re-joins the knows table against itself up to 4 times, and its cost grows with the size of the intermediate result sets at each level — for a densely-connected graph, this can explode combinatorially. In Neo4j, each hop is a pointer-follow from whatever nodes were reached at the previous depth; the cost is proportional to the actual size of the traversed neighborhood, not the size of the whole database. This is the concrete, measurable reason "shortest path," "friends of friends," and "is there a connection at all between A and B" queries are Neo4j's signature use case — recommendation engines, fraud-ring detection (does this new account share any indirect connection to known fraud accounts?), and permission/access-graph resolution all have this shape.

Indexes still matter — for entry points, not traversal#

Index-free adjacency speeds up traversal between already-found nodes, but you still need an index to find your starting node quickly (e.g., an index on Person.name to jump straight to Dana Lee instead of scanning every node). Neo4j supports property indexes for exactly this purpose — the mental model is "index to get in, pointer-follow to get around," which is a different division of labor than PostgreSQL's "index for everything, including intermediate join steps."

Consistency and scaling model#

A single Neo4j instance offers full ACID transactions, similar in spirit to PostgreSQL's guarantees (seven-databases/02) — this is a deliberate CP-leaning choice per seven-databases/01, because graph data (especially anything representing permissions, ownership, or financial relationships) often has correctness requirements that make eventual consistency risky. Neo4j scales primarily by adding read replicas (causal clustering); write scaling is bounded by a single primary, similar to MongoDB's replica-set model (seven-databases/04) and unlike HBase's or DynamoDB's native write-sharding — graph databases in general resist horizontal write-sharding because a relationship straddling a shard boundary defeats the whole "physical pointer" advantage that makes the model fast.

Pros#

  • Traversal cost stays roughly proportional to the size of the traversed neighborhood, not the whole dataset — variable-depth, relationship-heavy queries that would be painfully expensive or impossible to express cleanly in SQL become natural and fast.
  • Cypher's pattern-matching syntax reads close to how you'd draw the relationship on a whiteboard, reducing the gap between "how the domain expert describes the question" and "how the query is written."
  • ACID transactions give the same correctness guarantees as a relational database for data that's naturally graph-shaped but still needs strong consistency (e.g., access-control graphs).

Cons#

  • Write scaling is bounded by a single primary in the same way as PostgreSQL and MongoDB — Neo4j does not natively shard writes the way HBase or DynamoDB do, because sharding a graph without destroying its adjacency advantage is a genuinely hard problem.
  • For flat, aggregate-heavy queries with few or no traversals (sums, counts, filters on a single entity type), a graph database offers no advantage over a relational or document store and adds unfamiliar tooling for no benefit.
  • Modeling everything as a graph, when most of the domain's actual queries are non-relational (e.g., "list all products under $50"), tends to fight the tool rather than leverage it — graph databases are easy to over-apply once a team learns Cypher and starts reaching for it by default.

Alternatives#

  • PostgreSQL with recursive CTEs (seven-databases/02) — viable for shallow, bounded-depth traversals (e.g., a fixed 2-level category hierarchy) where the combinatorial cost of recursive joins never becomes a real problem.
  • A dedicated graph-processing framework on top of a big-data store (e.g., Spark GraphX) — appropriate for offline, batch graph analytics over enormous graphs (whole-network centrality, community detection) rather than interactive, low-latency traversal queries, which is Neo4j's sweet spot.
  • Embedding relationship data in a document store (seven-databases/04) — viable when relationships are shallow and bounded (a post's comments) rather than deep and variable — see the embedding discussion in seven-databases/04.

When to use it#

Reach for Neo4j when the relationships between entities, not just the entities, are central to your queries, especially when traversal depth is variable or unknown in advance — recommendation systems, fraud/anomaly detection via connection analysis, permission and org-hierarchy resolution, and knowledge graphs are the canonical fits.

When NOT to use it#

Avoid it when your dominant queries are flat aggregates or lookups with little to no multi-hop traversal — you'd gain nothing over PostgreSQL (seven-databases/02) and lose SQL's broader tooling and team familiarity. Avoid it too when you need horizontal write-scaling beyond a single primary at very high volume, which fights the graph model's core adjacency advantage. See seven-databases/09 for the full framework.

Key takeaways / mental model#

Neo4j's advantage is structural, not incidental: relationships are physically stored as direct pointers, so traversal cost tracks the size of what you actually traverse, not the size of the whole database — which is exactly backwards from a relational join's cost profile. Reach for it precisely when your queries are shaped like "follow this connection, however many hops it takes," not "look up rows matching a filter."

Self-check questions#

  1. Explain, in your own words, why a 4-hop "friends of friends of friends of friends" query gets proportionally more expensive in PostgreSQL as the dataset grows, but stays roughly the same cost in Neo4j regardless of total dataset size.
  2. A team wants to model a simple product catalog (products, categories, one level of nesting) in Neo4j "because graphs are more flexible." What would you push back on, and what would you suggest instead?
  3. Why does index-free adjacency help with traversal but not with finding your starting node? What role do indexes still play in a Neo4j query?
  4. Given a fraud-detection system needing to check "is this new account connected, through any chain of shared devices/emails/payment methods, to a known fraud ring, however indirectly?" — would you reach for Neo4j, HBase, or PostgreSQL, and why?

References#

  • Seven Databases in Seven Weeks (Perkins, Redmond, Wilson), Chapter 6: "Neo4j."
  • See also: seven-databases/01 (CAP framing), seven-databases/02 (PostgreSQL's join-based alternative), ddia/02 (data models) for deeper background.