Friends of friends melts a join — the pointer walk that replaces the self-join

In a relational store every extra hop of 'friends of friends' is another self-join of the friendship table, so the intermediate rows explode combinatorially (50 → 2,500 → 6.25M → 312M), while the same question answered by walking from person to person only ever touches the people you actually reach.

Scene 01

Friends of friends melts a join

Watch
Try it
Predict
Capture

What to watch for

One question: 'who are Alice's friends of friends of friends?' On the LEFT, a relational store answers it by joining the friendship table to itself once per hop — watch the intermediate-row counter as the depth climbs. On the RIGHT, the same question is answered by walking from Alice, person to person, lighting up only the people the walk actually reaches. Watch the two numbers pull apart.

Two ways to answer one question — 'who are Alice's friends of friends of friends?'
Left: a relational store keeps friendships in a join table (USER_FRIEND), so each extra hop is another self-join of that table to itself; the intermediate-row counter explodes 50 → 2,500 → 6.25M → 312M until the engine can't finish.
Right: the SAME question answered as a pointer walk that starts on Alice and steps from person to person — each step is a HOP (traverse one edge), and the walk only ever lights up the people it actually reaches.
A store built so that a hop is a step you FOLLOW rather than a table you re-join is a GRAPH DATABASE — its cost tracks the reachable set it visits, not the table's cartesian product.
(The faint greyed corner is the course's spine: a local walk lights a few nodes, but whole-graph work lights up everything — the tension the finale resolves.)

Implementation

Highlighted lines are the ones running in the diagram right now.

Relational.friendsOfFriends

answering it as a table: each hop joins USER_FRIEND to itself once more

1def friends_of_friends(start, depth):
2    rows = [(start,)]                 # depth 0: just Alice
3    for hop in range(depth):          # ONE self-join per hop
4        # join USER_FRIEND again: every row fans to its friends
5        rows = [(*r, f)
6                for r in rows
7                for f in friends_of(r[-1])]   # ~degree each
8    return dedup(last_col(rows))      # ...after materializing rows

Walk.expand

answering it as a walk: step edge by edge, never revisiting a person

1def expand(start, depth):
2    seen = {start}
3    frontier = [start]
4    for hop in range(depth):          # one step per hop
5        nxt = []
6        for person in frontier:
7            for friend in neighbors(person):  # follow an edge
8                if friend not in seen:        # skip the visited
9                    seen.add(friend); nxt.append(friend)
10        frontier = nxt                # only the newly reached
11    return seen - {start}

cost(depth)

the two cost curves side by side, as the depth knob drives them

1def relational_cost(depth):
2    return DEGREE ** depth            # 50^d candidate rows
3 
4def walk_cost(depth):
5    # bounded by distinct people reachable, not 50^d
6    return len(reachable_within(start, depth))

Sources

Where this sits in Build a graph database (Neo4j / Dgraph-style)

Scene 01 of 16, in the Why graphs act — Friends-of-friends melts a join; edges go first-class.. The canonical graph workload — 'friends of friends of friends' — is one self-join per hop, and the intermediate row count explodes combinatorially until a relational engine can't finish; the same query as a pointer walk visits only the people you actually reach.

Up next. The pointer walk won because it treated a friendship as a thing you can FOLLOW, not a row you have to re-join. But we drew that edge by hand — we never said how the data is actually shaped so that an edge becomes followable. Before we can make hops cheap, we need a data model where an edge is a first-class object, not a row in a join table.

All 16 scenes in Build a graph database (Neo4j / Dgraph-style) · Every curriculum

Built with Arqly

Every scene in Build a graph database (Neo4j / Dgraph-style) builds on the one before it.All 16 Build a graph database (Neo4j / Dgraph-style) scenes