Paginating Deep Graph Traversals in Neo4j with APOC and LIMIT/SKIP

Problem: Unbounded Traversals Spike Latency

When a Cypher query asks for all friends‑of‑friends up to five hops starting from a single user, Neo4j expands the frontier breadth‑first. In a densely connected social graph each hop can multiply the number of candidate nodes, producing millions of intermediate paths before any limit is applied. The result is unpredictable latency, sudden memory spikes, and occasional out‑of‑memory errors.

Thesis: Bounding Work with LIMIT and SKIP

By wrapping APOC’s path expansion procedures with SKIP and LIMIT (or using the built‑in pagination helpers) you force the planner to stop expanding after a fixed number of rows per request. The work per request becomes predictable, latency stabilises, and the heap usage stays within expected bounds.

How Neo4j Executes a Traversal

Neo4j’s execution engine first evaluates the apoc.path.expandConfig call, creating a frontier of nodes and relationships that satisfies the depth and filter criteria. Only after this expansion does it apply subsequent operators such as Order By, Skip and Limit. If the expansion is unbounded, the frontier can grow large before the pagination operators even see it.

Worked Example: Paginated Friends‑of‑Friends up to 5 Hops

Run the following statement in Neo4j Browser, Neo4j Desktop, or an Aura free instance. Ensure the APOC plugin is installed and enabled.

MATCH (start:User {userId: $userId})
CALL apoc.path.expandConfig(start, {
    relationshipFilter: 'FRIEND>',
    labelFilter: '+User',
    minLevel: 1,
    maxLevel: 5,
    uniqueness: 'NODE_GLOBAL'
}) YIELD path
RETURN last(nodes(path)) AS friendOfFriend,
       length(path) AS hops
ORDER BY friendOfFriend.userId
SKIP $skip
LIMIT $limit

Where:

• $userId is the identifier of the starting user.
• $skip and $limit are pagination parameters (e.g., 0 and 20 for the first page).
• The ORDER BY clause guarantees a stable order so that successive pages do not shift results.

To verify that pagination is applied early, prepend PROFILE to the query and inspect the plan output. You should see a Skip and Limit operator positioned after the PathExpansion node. The planner will also show the estimated number of database hits for the expansion step; with pagination enabled the hits reported for the expansion will be capped by the limit value plus the skip offset.

If you run the same query without SKIP and LIMIT, the profile will display a much larger number of hits and a higher memory allocation metric, illustrating the trade‑off.

Trade‑off and Limitations

• Planning overhead: Adding SKIP and LIMIT introduces extra operators in the execution plan, which adds a few milliseconds of planning time.
• Order stability: Without a deterministic ORDER BY, the same skip/limit pair can return different rows on subsequent calls as the underlying expansion order may vary.
• Dense graphs: Even with pagination, a highly connected node can cause a large frontier before the limit is applied. Mitigate this by tightening the relationshipFilter or labelFilter in apoc.path.expandConfig (e.g., only follow FRIEND relationships of type CLOSE).

Actionable Steps

1. Enable APOC: place apoc.conf in conf/ and set dbms.security.procedures.unrestricted=apoc.* (or use the APOC plugin UI in Neo4j Desktop).
2. Store the Cypher fragment above as a reusable parameterised query in your application layer.
3. Run PROFILE on a representative dataset (e.g., a copy of your production graph trimmed to a few hundred thousand nodes) and compare the Database Hits and Memory Allocation values between the paginated and non‑paginated versions.
4. Monitor heap usage via Neo4j metrics (dbms.memory.heap.max, dbms.memory.heap.used) while load‑testing the paginated query to ensure it stays within expected bounds.