The access pattern is discovered, not declared; CSR

Why can graph work not batch by address, and what does CSR layout buy?

CaseConstructed case · Amara at Haatly

Friends of friends that never finishes

Haatly adds a feature to the item page: "friends of friends who bought this". It is a three-hop question: start from the viewer, look at the people they follow, then the people those people follow, then the people those follow, and keep the ones who bought this item. Amara builds it the obvious way, with an edge table in PostgreSQL (follows(follower_id, followee_id)) and three self-joins.

For most users the page takes about 3 seconds. For a handful of users the query never finishes. These users follow, or are followed by, accounts with 2 million followers (large shops and local celebrities). Elin suggests adding more database servers. Amara adds two replicas and nothing changes: one query is still one query, and it is slow on every server.

This is not a tuning mistake. Graph work breaks an assumption that text and vector search still kept. We start there.

How it ends →

Text search and vector search both preserved one useful thing: the set of records to examine was determined by the query. An inverted index turns query words into lists of documents. An ANN structure (approximate nearest neighbour, a vector index that returns close vectors without comparing all of them) turns a query vector into cells or hops. In both cases you can look at the query and know, at least roughly, where to go.

Graph traversal destroys that. A graph is a set of vertices (things, here users) joined by edges (relations, here "follows"). Traversal means walking along edges. The answer to "who is within three hops of this vertex" (a hop is one step along one edge) cannot be written as a predicate over stored values. It is defined step by step: read this vertex, discover its neighbours, read those, discover their neighbours. The address of the next read is a function of the data you just read, not of the query you were given.

Everything in this article follows from that one sentence:

Prefetch (loading data before it is asked for) needs future addresses. You do not have them.
Vectorization (processing many values with one instruction) needs a batch of independent operations. You have a dependency chain.
Data skipping (ignoring a block because min/max summaries prove it holds nothing relevant) needs a bound on what a block contains. Reachability has no such bound: you cannot prove a partition holds no relevant vertex without following the edges into it.
Cost estimation needs selectivity (the fraction of rows a condition keeps). The size of a three-hop neighbourhood depends on the degrees of vertices you have not visited yet.

This is also the family where this mechanism's shared template collapses. Text projects documents to postings, vectors to short codes, geometry to bounding boxes (Geospatial): each is a lossy filter with no false negatives, followed by a refine step. There is no lossy projection of a graph that preserves reachability. Any structure that lets you skip edges can make you miss paths. So graph engines cannot buy pruning. They buy something else, and the rest of this article explains what.

Adjacency list and CSR

The relational encoding of a graph is an edge table: one row per edge. A one-hop expansion is then a self-join (joining a table to itself), and a k-hop traversal is k self-joins, with one index lookup for each row of the frontier (the set of vertices reached in the latest hop). Each lookup is a B-tree descent (walking down the levels of the index): several dependent cache misses. A dependent miss is one that cannot start before the previous one has finished. So the pointer chasing happens inside the index, not in the data.

Adjacency list storage removes that layer. Store each vertex's neighbours next to each other, and expansion becomes a direct read of a contiguous run: one dependent miss to find the run, then sequential bytes.

CSR (Compressed Sparse Row) pushes this to its limit. It uses two arrays: one array of neighbour ids, and one offset array indexed by vertex id. The neighbours of vertex v are nbrs[off[v] : off[v+1]].

Worked example

Four vertices 0 to 3 and five edges: 0→1, 0→2, 1→2, 2→0, 2→3.

nbrs = [1, 2,   2,   0, 3 ]      # all neighbour ids, grouped by source vertex
off  = [0,      2,   3,      5, 5]   # off[v] = where vertex v's run starts
# neighbours of vertex 2 = nbrs[off[2] : off[3]] = nbrs[3:5] = [0, 3]
# vertex 3 has no outgoing edges: nbrs[5:5] is empty

There is no per-vertex header and no pointer. Neighbours of one vertex sit next to each other in memory.

CSR is not a new idea across the platform: it is columnar layout for graphs. (Columnar layout stores each field of many records together instead of storing record by record.) CSR is dense, addressed by offset, has no per-record header, and is sequential inside a run. It also inherits columnar's exact trade-off: it is excellent for scanning and effectively immutable, because inserting one edge shifts every later offset. So:

Mutable graph stores use adjacency lists with spare space per vertex (slack) or chunking.
Analytical graph engines build a CSR once per run.

This is the same fork as row versus column storage, and the same resolution: the mutable store is the source of truth, and the immutable layout is built for the query.

Two things should be stated plainly.

"Index-free adjacency" is a real mechanism described in inflated terms. The honest claim: keeping the neighbour list materialized removes one index descent per hop. That is a constant factor of perhaps 3 to 10 times per hop. It compounds with depth, so it is decisive at four hops and roughly irrelevant at one. The common marketing claim, that graph databases beat relational ones by orders of magnitude on joins in general, is folklore. A modern columnar engine doing a hash join over an edge table beats a pointer-chasing graph engine on bulk one-hop work. The hash join is bandwidth-bound and vectorized; the traversal is latency-bound. The crossover depends on depth and selectivity: few starting points and many hops favour traversal; many starting points and few hops favour joins.

The index is directional, so you store the graph twice. CSR as shown answers "who does vertex 2 follow?". To answer "who follows vertex 2?" you need a reverse CSR built from the same edges flipped. This is the directional-index rule again: a mapping and its inverse are different structures. The cost is doubled edge storage and a second write path. It is the reason undirected graphs are cheaper than they look, and directed graphs queried in both directions are more expensive than they look.

One line: CSR is columnar layout for graphs. It removes an index descent per hop, at the price of immutability and a second copy for the reverse direction.