Graph Databases: Property Graphs, Cypher, and When Joins Are the Problem

TL;DR: A graph database treats relationships as first-class storage primitives. Nodes and edges carry properties; traversal follows pointers rather than computing joins. This makes multi-hop queries (friend-of-friend, permission chains, fraud rings) orders of magnitude faster than recursive SQL CTEs once you pass 3-4 hops. Neo4j's index-free adjacency gives O(degree) per hop instead of O(log N) per join^[1]. Meta TAO serves over 10 billion graph reads per second using a narrow graph API over sharded MySQL^[2]. Use a graph database when your queries traverse deep relationships. Use Postgres when depth is 2 or less.

Learning Objectives#

After this module, you will be able to:

• Model a domain as a property graph with labeled nodes, typed edges, and properties
• Write basic Cypher queries with pattern matching and variable-length paths
• Distinguish property graphs from RDF triple stores and choose between them
• Recognize workloads where a graph database beats a relational one
• Reason about scaling limits: supernodes, partitioning hardness, and horizontal strategies

Intuition#

Think about giving directions in a city. If someone asks "how do I get from the library to the bakery?", you do not consult a giant spreadsheet of every intersection in town. You start at the library, look at the streets leaving it, pick one, walk to the next intersection, look at the streets leaving that intersection, and repeat. Each step costs you one glance at the current intersection, regardless of how many intersections exist in the entire city.

A relational database answering "who are Alice's friends-of-friends?" works like the spreadsheet approach. It scans a friendships table (potentially billions of rows), joins it against itself, and filters. Each hop multiplies the intermediate result set. A four-hop query on a social graph with average degree 250 touches up to 250^4 candidate paths before filtering.

A graph database works like walking the city. It starts at Alice's node, follows her outgoing FRIEND pointers (a handful), then follows each friend's FRIEND pointers in turn. The cost at each hop is proportional to the number of neighbors at that node, not the size of the entire graph. This is the fundamental insight: when your question is "what connects to this thing?", pointer-chasing beats index-lookup.

The rest of this chapter makes that intuition precise: the data model, the query languages, the physical storage trick that makes it fast, and the scaling problems that make it hard.

Theory#

The property graph model#

A property graph is a directed, labeled multigraph where both nodes and edges carry key-value properties^[3]. Each node has zero or more labels (like :Person, :Company). Each edge has exactly one type (like :FRIEND, :WORKS_AT), a direction, and its own property map. Multiple edges of different types can connect the same pair of nodes.

A property graph fragment: nodes carry labels and properties; edges carry types, direction, and their own properties.

The alternative model is the RDF triple store: every fact is a (subject, predicate, object) triple governed by W3C standards. SPARQL is the query language. RDF excels at composing data from many sources via global URIs (Wikidata stores 16.6 billion triples this way^[4]) and supports formal inference via OWL/SHACL. The trade-off: edge properties require reification (a single property-graph edge with three attributes becomes 4-7 triples), and single-node RDF engines like Blazegraph become unstable at around 16 billion triples (Wikidata's 16.6B required splitting the graph into partitions)^[4:1].

When to pick which:

For the rest of this chapter, property graph is the default model.

Index-free adjacency#

The physical trick that makes graph traversal fast is index-free adjacency: each node record stores a direct pointer (file offset or memory address) to its first relationship record, and each relationship record links to the next relationship for the same node^[1:1].

In Neo4j's native store format, node records are 15 bytes, relationship records are 34 bytes, and property records are 41 bytes. These fixed-size records form linked lists on disk. To find all of Alice's friends, the engine reads Alice's node record, follows the pointer to her first relationship, then walks the linked list. No index lookup. No table scan. Cost: O(degree of Alice)^[1:2].

Fixed-size records form linked lists; traversal follows pointers without consulting a global index.

Compare this to a relational JOIN: the database must look up the friendships table's B-tree index for every hop. On a table with billions of rows, each B-tree lookup is O(log N). At four hops, you pay 4 * O(log N) per path, and the intermediate result set grows multiplicatively with fan-out.

LinkedIn's engineering team described this concretely: a typical member's second-degree network is 50,000+ entities, "too large to pre-materialize and store" yet the join to produce it "is daunting, particularly if you have to search a table of billions of edges stored in conventional sorted storage"^[5].

Query languages: Cypher, Gremlin, SPARQL, and GQL#

Cypher is declarative and reads like ASCII art. Nodes are parentheses, edges are square brackets, arrows give direction:

-- Friends of Alice's friends who are not already Alice's friends
MATCH (alice:Person {name: 'Alice'})-[:FRIEND]->(f)-[:FRIEND]->(fof:Person)
WHERE NOT (alice)-[:FRIEND]->(fof) AND alice <> fof
RETURN DISTINCT fof.name
LIMIT 20

Variable-length paths make recursive queries trivial:

-- Shortest path from Alice to Bob, up to 6 hops
MATCH p = shortestPath(
  (a:Person {name: 'Alice'})-[:FRIEND*..6]-(b:Person {name: 'Bob'})
)
RETURN [n IN nodes(p) | n.name] AS chain, length(p) AS hops

Gremlin is imperative. Each step in the pipeline transforms the traversal:

g.V().has('Person','name','Alice')
  .out('FRIEND').out('FRIEND')
  .where(neq('alice'))
  .values('name').dedup().limit(20)

Gremlin runs on any TinkerPop-compliant store (JanusGraph, Neptune, ArangoDB). It is more flexible (Turing-complete with closures) but harder to optimize because the engine cannot easily reorder imperative steps^[6].

SPARQL targets RDF triples and supports federation across endpoints. It is the only choice for querying Wikidata, DBpedia, and other linked-data sources.

GQL (ISO/IEC 39075:2024) is the first new ISO database query language since SQL^[7]. It standardizes the pattern-matching core shared by Cypher, PGQL, and G-CORE. SQL/PGQ mirrors the same patterns inside SQL. For day-one decisions, Cypher is the practical choice; GQL matters for future-proofing.

The major systems#

Neo4j's standard store format supports up to 34 billion nodes and 34 billion relationships^[8]. For larger graphs, distributed systems like Dgraph use predicate-based sharding: all instances of the friend predicate live on one Raft group, so an N-hop traversal along one predicate type requires only N network hops regardless of data size^[9].

Graph algorithms and the bridge to ML#

Graph databases are not just for CRUD queries. Common analytical algorithms include:

• Shortest path / Dijkstra - routing, social distance
• PageRank - influence scoring, search ranking
• Community detection (Louvain) - fraud ring identification, market segmentation
• Node embeddings (node2vec, GraphSAGE) - convert graph structure into feature vectors for downstream ML models

The bridge to ML is significant: node embeddings let you feed graph topology into recommendation engines, anomaly detectors, and classification models without hand-engineering features. Neo4j's Graph Data Science library, TigerGraph's in-database analytics, and standalone tools like PyTorch Geometric all operate in this space.

Scaling: the hard problems#

The supernode problem. Real graphs follow power-law degree distributions. A celebrity with 15 million followers has a single node with 15 million outgoing edges. Traversing that node's neighbors is no longer O(1); it is O(15M). The shard owning that node becomes a hot spot^[10].

Supernode mitigation: split a high-degree node into a fanout tree of sub-shards, bounding per-node edge counts and enabling parallel traversal.

Mitigations: (1) hash-partition the supernode's edges into meta-nodes (the "fanout pattern"), (2) vertex-centric indexes that seek within the edge list by property, (3) pre-computed caches of the most recent or popular subset (TAO caches a bounded number of edges per association list^[11]).

Partitioning hardness. Graphs resist partitioning because edges cross partition boundaries. Vertex-based sharding (NebulaGraph, JanusGraph on Cassandra) stores each vertex's edges locally, but a 4-hop traversal crossing shard boundaries takes 4 network round trips. Predicate-based sharding (Dgraph) avoids this for single-predicate paths but complicates cross-predicate queries.

Neo4j Fabric (now "composite databases") coordinates federated queries across constituent shards that hold disjoint portions of the graph. It is real but partial: you must manually decide how to partition, and cross-shard queries pay coordination overhead.

Real-World Example#

Meta TAO: a graph serving layer at planetary scale#

Meta's TAO (The Associations and Objects store) is the system behind Facebook's social graph. It is not a general graph database. It is a narrow-API graph serving layer over sharded MySQL, purpose-built for the workload shape of a social network: overwhelmingly read-dominant (500:1 read-to-write ratio)^[2:1].

Scale: TAO served 1 billion reads per second in 2013 with a 96.4% follower-tier cache hit rate^[11:1]. By 2021, it exceeded 10 billion reads per second^[2:2]. By 2022, Meta reported "more than one quadrillion" queries per day^[12].

Data model: Two primitives only. Object(id, otype, fields) for nodes. Association(id1, atype, id2, time, fields) for edges. Queries are limited to assoc_get, assoc_count, assoc_range, and mutations. No general pattern matching. No variable-length paths.

Architecture: A two-tier cache per region sits between PHP web servers and MySQL. Many follower tiers handle reads; one leader per shard per region coordinates writes. Inverse edges are maintained automatically so "who follows me?" is as fast as "who do I follow?". MySQL remains the source of truth because the operational tooling (backup, migration, monitoring) is mature and well-understood^[11:2].

TAO's two-tier cache per region: follower tiers absorb the 99.8% read load at a 96.4% hit rate; the single leader per shard coordinates writes to MySQL, which remains the source of truth.

Key lesson: The hyperscale social graphs (TAO, Twitter's FlockDB, LinkedIn's LIquid) are not general graph databases. They sacrifice query expressiveness for horizontal scale. If your workload fits a fixed set of query patterns, a narrow graph API over a proven storage engine (MySQL, Cassandra) will outscale any general-purpose graph database by orders of magnitude.

Trade-offs#

Common Pitfalls#

Exercise#

Design a permission system for a B2B SaaS with organizations, teams, projects, roles, and resources. Users inherit permissions through nested group memberships up to 6 levels deep. Pick between Postgres, Neo4j, and a dedicated authz service (SpiceDB, OpenFGA). Justify with query patterns.

Key Takeaways#

• Graph databases shine when queries traverse 3+ hops. At depth 1-2, Postgres with a JOIN is simpler and sufficient.
• Index-free adjacency makes neighbor access O(degree) per hop instead of O(log N) per join. This is the physical reason graphs win on deep traversals.
• Cypher (and the emerging GQL standard) is the most approachable graph query language. Gremlin is more powerful and less readable. SPARQL is for RDF only.
• The supernode problem is the #1 production pathology. Monitor degree distributions and apply the fanout pattern before a celebrity node melts your cluster.
• Scaling graph databases horizontally remains genuinely hard. Most production systems at hyperscale (TAO, FlockDB, LIquid) use narrow graph APIs over proven storage engines, not general-purpose graph databases.
• Property graphs are the right default for application development. RDF triple stores are the right choice for knowledge graphs that need inference, linked-data composition, or W3C interoperability.
• When your graph query pattern is fixed and your scale is extreme, build a specialized serving layer rather than deploying a general graph database.

Further Reading#

• TAO: Facebook's Distributed Data Store for the Social Graph (Bronson et al., USENIX ATC 2013) - The reference paper for narrow-API graph serving at planetary scale; essential reading for understanding the gap between "graph database" and "graph serving layer."
• Neo4j Graph Database Concepts - The canonical property-graph primer; start here if you have never modeled a graph.
• Understanding Neo4j's data on disk - Fixed-size record internals that make index-free adjacency concrete; read this to understand why traversal is O(degree).
• ISO/IEC 39075:2024 GQL Standard - The first new ISO database query language since SQL; defines the future of declarative graph querying.
• Apache TinkerPop / Gremlin Documentation - The portable traversal machine and its imperative query language; relevant if you use JanusGraph or Neptune.
• Dgraph Architecture - Predicate sharding, Raft consensus per group, and Badger storage in one document; the clearest distributed-graph-database architecture reference.
• LIquid: The Soul of a New Graph Database, Part 1 (LinkedIn Engineering, 2020) - Why LinkedIn built a custom graph engine with wait-free reads and log-structured storage for a 675M-member economic graph.
• Wikidata Query Service graph database reload at home, 2025 edition - The clearest operational picture of RDF scaling pain in the wild; 16.6 billion triples on a single-node Blazegraph instance approaching its ceiling.

Flashcards#

References#