SKIP/LIMIT offset exhaustion in Neo4j large-dataset pagination

The Offset Performance Threshold

There is no single, universal offset value where Neo4j shifts from an index-assisted seek to a full scan. Instead, SKIP operates with linear O(n) complexity. The engine must materialize and discard every record preceding the offset before returning the requested page. In a dataset of ten million records, you will likely violate a two-second latency requirement long before reaching the end of the set, as the cumulative cost of db hits increases incrementally with each page.

Keyset Pagination and Completeness

Keyset pagination (cursor-based) maintains O(log n) performance by using a WHERE clause to jump directly to the next starting point via an index. However, it cannot guarantee completeness or uniqueness if the ordering property is non-unique or subject to concurrent mutation:

• Non-unique properties: If multiple records share the same value, the cursor may stop in the middle of a group of identical values, causing some records to be skipped or duplicated across pages.
• Concurrent mutations: If a record is inserted or deleted with a value lower than the current cursor, the relative position of the remaining records shifts, leading to "drift" where the client may see the same record twice or miss one entirely.

Label Heterogeneity and Reliability

Label heterogeneity affects the initial entry point of the query. A query targeting a specific label using a label-specific index is significantly more efficient than a generic node scan. However, once the traversal begins, the reliability of the cursor depends entirely on the index used for the sort property, not the labels themselves. If the cursor relies on a property that is not consistently present across all labels in the result set, those nodes may be excluded from the pagination sequence.

Implementation Strategy

To maintain sub-two-second latency across ten million records, replace SKIP/LIMIT with a keyset approach using a unique tie-breaker (such as a UUID or the internal element ID) to ensure stability.

// Example: Keyset pagination with a unique tie-breaker
MATCH (n:User)
WHERE (n.timestamp < $lastTimestamp) 
   OR (n.timestamp = $lastTimestamp AND n.uuid < $lastUuid)
RETURN n
ORDER BY n.timestamp DESC, n.uuid DESC
LIMIT 25

Verification Steps

1. Run PROFILE on your current SKIP query. Observe the db hits metric as you increase the offset; you will see a linear increase in cost.
2. Run PROFILE on the keyset query. The db hits should remain nearly constant regardless of how deep you are in the dataset.

Diagnostic Requirement: Please specify if your sorting property is immutable. If the property used for the cursor is updated frequently, a different architectural approach (such as a materialized snapshot) may be required to prevent result drift.