The supernode breaks the promise

A supernode's relationship chain is enormous, so expanding through it scans millions of edges and the O(1)-per-hop promise collapses on that single node — which is why you traverse from the low-degree side (The Rock has 232M inbound but few outbound) and group its edges by type and direction.

Previously

The planner anchors on the few, not the many — but what if the 'many' is unavoidable because a single node has millions of edges? That's a supernode, and expanding through its giant relationship chain scans millions of records: the O(1)-per-hop promise collapses on that one node. Reads are only half the damage, though — what happens when everyone tries to ADD an edge to that same celebrity at once?

Scene 09

The supernode breaks the promise

Watch
Try it
Predict
Capture

What to watch for

Two nodes, side by side. Erin has five relationship records — a normal node; a traversal that grazes her lights just a few neighbors. The Rock has so many followers that we can only draw a fan, each edge labeled ×10M (it really has ~232M). Watch a traversal try to expand INTO The Rock: it has to walk its entire relationship chain. The scan floods the fan… and stalls. It can't finish — every hop the curriculum promised was O(1) just turned into 'scan millions of edges' on this one node.

The same social graph.
Erin (node 5, badge '5') is a normal node — five relationship records.
The Rock (node 11) is a supernode (a dense node): a vertex with a huge degree — degree is just the number of edges on a node — drawn as a fan of ~20 edges, each labeled ×10M to stand in for its 232M-record chain (a real hub is too big to draw).
Expanding INTO that chain ('who follows The Rock?') must scan the whole fan, so the violet edges flood and the scan never finishes — that is the drowning.
The inset is the persistent spine: a normal hop lights a few nodes; a hop through the supernode lights its entire chain.

Implementation

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

Traversal.expand

a hop walks the node's relationship chain — O(degree), not O(1)

1def expand(node, rel_type, direction):
2    out = []
3    # walk the doubly-linked relationship chain for this side
4    rel = node.first_rel(rel_type, direction)
5    while rel is not None:          # O(degree) — the whole cost
6        out.append(rel.other_end(node))
7        rel = rel.next_in_chain     # one pointer follow per edge
8    return out
9 
10# inbound  on The Rock: ~232M iterations → drowns
11# outbound on The Rock: ~3 iterations    → instant

Planner.pickExpandSide

expand cost is O(degree) on that side, so walk whichever direction is shorter

1def pick_expand_side(node, rel_type):
2    # cost of a hop = how many edges hang off this side
3    in_deg  = node.degree(rel_type, INBOUND)
4    out_deg = node.degree(rel_type, OUTBOUND)
5    # walk from the low-degree side — fewer pointer follows
6    if in_deg <= out_deg:
7        return INBOUND
8    return OUTBOUND
9 
10# The Rock: in_deg ~232M, out_deg ~3 → pick OUTBOUND
11# (same node, opposite cost — degree, not the node, is the bill)

Store.denseNodeGroups

a dense node splits its one mixed chain into per-(type, direction) groups

1DENSE_THRESHOLD = 50   # ≥ this many edges → 'dense' layout
2 
3def first_rel(node, rel_type, direction):
4    if node.degree() < DENSE_THRESHOLD:
5        return node.head_of_single_chain   # one mixed chain
6    # dense: jump straight to the right group's head
7    grp = node.group_record(rel_type, direction)
8    return grp.chain_head                   # no scan to locate it
9 
10# so EXPAND lands on the short chain directly,
11# never touching the giant one beside it

Sources

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

Scene 09 of 16, in the It breaks act — The supernode shatters the O(1)-per-hop promise.. A supernode is a vertex with a huge degree, and its relationship chain is so long that any traversal THROUGH it must scan millions of edges — so the O(1)-per-hop promise dies on that one node, and the fix is to expand from the low-degree side.

Up next. A supernode wrecks reads by being a long chain to scan. Now flip to writes: historically, adding an edge took a lock on the WHOLE node, so every concurrent 'follow The Rock' serialized on one lock and throughput collapsed. Fixing that needed a finer-grained lock — and it's a clean little half-step on the same supernode picture.

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