Edge-Sorted Indexes

An edge-sorted index keeps, per anchor vertex, that anchor’s neighbours over one relationship type pre-ordered by a property of the neighbour. Eligible ordered pages use this index to select candidates instead of starting with an unordered traversal. Residual filters, additional hops and secondary ordering still require work; an API page size is not a fixed bound on candidates read.

This is a patinaDB extension. The grammar reference lives in Cypher Support → DDL; this chapter is the conceptual and worked-example companion.

The problem it solves

One shape shows up nearly everywhere you build on a graph:

• a user’s most recent tickets,
• the newest comments under a post,
• a person’s activity feed / timeline,
• the top-N items per parent, ordered by a timestamp, score, or price.

In Cypher it reads:

MATCH (u:User {name: 'Ada'})-[:REPORTED]->(t:Ticket)
RETURN t
ORDER BY t.created_at DESC
LIMIT 10

Simple to write, but normally expensive. To return ten rows the engine must:

1. traverse the whole fan-out — every REPORTED edge Ada has, even if she filed 50 000 tickets,
2. read the sort property (created_at) off every one of those targets, then
3. sort all of them just to discard everything below the top ten.

The work is proportional to the anchor’s degree, not to the LIMIT. For a hub vertex — a power user, a popular post, a busy parent — that is the difference between a feed that renders instantly and one that stalls.

What patinaDB does

An edge-sorted index stores a sorted adjacency: for each anchor, its targets over one relationship type are already laid out in target-property order. The query above becomes:

1. seek to the anchor’s slice of the index,
2. iterate in created_at order (DESC walks it in reverse),
3. take k and stop.

That is O(n + k) (skip n, take k) — no fan-out, no materialising the whole neighbour set, no post-sort. A power user with 50 000 tickets costs the same top-ten as one with twelve. The index is maintained synchronously on every write (edge create/delete, and moving a target when its sort property changes), so it is never stale.

The DDL and a worked example

The syntax names the traversal shape and the target property to order by. Both orientations are supported:

-- outbound anchor: (anchor)-[:REL]->(target)
CREATE EDGE SORTED INDEX [name] FOR ()-[:REPORTED]->(m:Ticket) ON m.created_at

-- inbound anchor: (target)<-[:REL]-(anchor)
CREATE EDGE SORTED INDEX [name] FOR (m:Ticket)<-[:HAS_LABEL]-()  ON m.created_at

SHOW EDGE SORTED INDEXES

Fast-path eligibility is narrower than valid Cypher syntax. Besides the basic single-key shape, RFC 0035 adds direct-property secondary ordering, deterministic residual filters and fixed-hop continuation for a single resolved anchor. Identity WITH target projections can retain this access path. Computed sort expressions and renamed sort bindings are not covered by this extension. Keep a stable tie-breaker where your pagination contract requires one; do not remove it merely to obtain an index hit. Verify the entire query with EXPLAIN, including filters, cursor and WITH clauses.

The name is optional and cosmetic — a def is identified by its shape (direction, relationship type, target label, target property), so two CREATEs of the same shape are idempotent.

The following was run end-to-end against a live server on a tiny User → REPORTED → Ticket graph; the output is real.

Build the graph

CREATE (u:User {name:'Ada'})
CREATE (t1:Ticket {id:1, title:'Login fails',    created_at:'2026-07-01T09:00:00'})
CREATE (t2:Ticket {id:2, title:'Slow dashboard', created_at:'2026-07-03T14:30:00'})
CREATE (t3:Ticket {id:3, title:'Export broken',  created_at:'2026-07-05T08:15:00'})
CREATE (t4:Ticket {id:4, title:'Typo in header', created_at:'2026-07-06T11:45:00'})
CREATE (u)-[:REPORTED]->(t1)
CREATE (u)-[:REPORTED]->(t2)
CREATE (u)-[:REPORTED]->(t3)
CREATE (u)-[:REPORTED]->(t4)

Create the index

$ patinadb feeddb query \
    "CREATE EDGE SORTED INDEX ticket_feed FOR ()-[:REPORTED]->(m:Ticket) ON m.created_at"
status: 'Edge sorted index ticket_feed created FOR ()-[:REPORTED]->(:Ticket) ON created_at'

$ patinadb feeddb query "SHOW EDGE SORTED INDEXES"
edgeSortedIndexes: ['FOR ()-[:REPORTED]->(:Ticket) ON created_at']

Creating the index over a populated graph backfills the existing edges, so you can create it any time.

Page 1 — newest first

$ patinadb feeddb query \
    "MATCH (u:User {name:'Ada'})-[:REPORTED]->(t:Ticket)
     RETURN t.id, t.title, t.created_at
     ORDER BY t.created_at DESC LIMIT 2"
t.created_at: ['2026-07-06T11:45:00', '2026-07-05T08:15:00']
t.id: [4, 3]
t.title: ['Typo in header', 'Export broken']

Confirm the index serves it

EXPLAIN shows the physical plan. When an edge-sorted index covers the query, the Physical: footer names limit.edge_sorted_topk:

$ patinadb feeddb query \
    "EXPLAIN MATCH (u:User {name:'Ada'})-[:REPORTED]->(t:Ticket)
     RETURN t ORDER BY t.created_at DESC LIMIT 2"
plan: 'Limit skip=0 count=2
  Project items=1 distinct=false return_star=false
    Sort keys=1
      MatchScan required=[(u:User) -[entry](t:Ticket) → PropertyIndex[created_at] SORTED SCAN DESC est.5]
Physical:
  limit.edge_sorted_topk
'

If you drop the index (or the query shape does not match), the footer names a different path — always run EXPLAIN to confirm the index is doing the work.

Page 2 — keyset pagination

To page forward, carry a cursor: the sort value of the last row on the previous page (2026-07-05T08:15:00), and ask for rows strictly beyond it. For a DESC feed that is <:

$ patinadb feeddb query \
    "MATCH (u:User {name:'Ada'})-[:REPORTED]->(t:Ticket)
     WHERE t.created_at < '2026-07-05T08:15:00'
     RETURN t.id, t.title, t.created_at
     ORDER BY t.created_at DESC LIMIT 2"
t.created_at: ['2026-07-03T14:30:00', '2026-07-01T09:00:00']
t.id: [2, 1]
t.title: ['Slow dashboard', 'Login fails']

This single-value example assumes distinct creation times. For duplicate timestamps, use the stable two-key cursor below; a strict timestamp-only cursor would skip remaining rows with the boundary timestamp.

Stable cursors, filters and additional hops

Use a unique tie-breaker and carry both ordered values from the last row:

This recipe assumes non-null cursor fields and uniqueness across result rows, not merely target vertices. If a join produces several rows for one target, its identifier alone cannot distinguish those rows at a page boundary. Include the required continuation identity in the application’s ordering/cursor, or deliberately deduplicate before pagination (which may select the fallback plan). Nullable cursor fields need explicit null-aware predicates; ordinary =, < and > comparisons to null do not match null rows.

MATCH (author:Author {author_id:$author})
      <-[:AUTHORED_BY]-(comment:Comment)<-[:HAS_COMMENT]-(ticket:Ticket)
WHERE split(ticket.issue_key, '-')[0] IN $allowed
  AND (comment.created_at < $after_time
       OR (comment.created_at = $after_time AND comment.comment_id > $after_id))
WITH comment
ORDER BY comment.created_at DESC, comment.comment_id ASC
LIMIT $limit
RETURN comment.comment_id, comment.created_at, comment.body

The corresponding existing-format index is:

CREATE EDGE SORTED INDEX
FOR (comment:Comment)<-[:AUTHORED_BY]-() ON comment.created_at

The first page omits the cursor predicate. When the complete shape is eligible, EXPLAIN reports limit.edge_sorted_topk. The reader seeks using a proven necessary primary-key bound, keeps the boundary group, and still evaluates the original cursor and permission predicates. Secondary ordering is resolved inside complete primary groups. Only matching rows count toward SKIP/LIMIT; multiple matching ticket continuations retain their Cypher row multiplicity.

The extension currently admits a uniform primary value domain, across the indexed target label/property, of strings, integers, booleans or legacy timestamps, with missing properties handled by ordinary null ordering. Mixed primary domains and unsupported types fall back. Temporal Cypher values are distinct from legacy timestamps; this extension does not add multikey temporal acceleration. Optional source matches, variable-length source paths, DISTINCT before the page, unsupported expressions and insufficient secondary-label coverage also retain ordinary execution. Optional hydration after the page is separate and can be used without changing the inner page’s eligibility.

Large primary tie groups and restrictive permission filters can still require many reads. A secondary key is not physically stored in this single-property index, and no universal constant-time or fixed-read-count guarantee is made. The index and residual traversal use the same query snapshot, but independent page requests do not share a frozen snapshot: concurrent changes to ordering keys can move rows across pages. Use a supported fixed historical view when the application needs a frozen feed.

The RFC 0035 extension describes the development build, not a released-version guarantee. Component tests cover the unchanged Jira-shaped request, planner selection, duplicate continuations and pinned snapshots. A three-hour mixed regional simulation passed on the frozen development build (#1261, 2026-09-21); first-touch aggregation and long-tail filtered author pages remain performance limitations. This is not cold-start, real-WAN or production approval, nor a fixed latency guarantee per page.

Pages across an anchor frontier

A read-only query can build a frontier through earlier hops or UNWIND, then page over a final directed, fixed-length relationship to indexed targets:

MATCH (root:Account {id:$id})-[:FOLLOWS*1..2]->(author:Account)
WITH collect(DISTINCT author) AS authors
UNWIND authors AS author
MATCH (author)<-[:AUTHORED_BY]-(post:Post)
WHERE post.created_at < $before
RETURN post.id AS id, post.created_at AS created
ORDER BY created DESC, id ASC
SKIP $skip LIMIT $limit

Declare CREATE EDGE SORTED INDEX FOR (p:Post)<-[:AUTHORED_BY]-() ON p.created_at to make the final-hop index available. A regular property range index does not supply these per-anchor streams. Eligible plans report limit.edge_sorted_topk. The executor merges the streams, retains duplicate frontier rows and resolves complete primary ties before stopping. Only matching rows consume the page.

This frontier path currently supports uniform integer, boolean or legacy timestamp primary values, including missing values. Strings, floats, mixed primary types, secondary-only target label coverage and unsupported final-hop shapes retain ordinary execution. Earlier traversal still runs normally; a large frontier, large ties or restrictive residual filters can require substantial work. Index creation and maintenance have their ordinary costs. Independent page requests still observe independent snapshots.

When to use it — and when not

Reach for it when you have the “top-N neighbours by a neighbour property” shape over a skewed fan-out (some anchors have far more neighbours than others) and you want the first page to stay fast regardless of degree. Feeds, timelines, “latest N per parent”, and leaderboards-per-group are the sweet spot.

Each index covers exactly one (direction, relationship type, target label, target property) combination. Different primary sort properties or relationship types need separate definitions. Supported secondary sort keys do not require another index, but their tie-group work remains at read time.

Create it after a bulk load. Bulk import does not maintain edge-sorted indexes incrementally; CREATE EDGE SORTED INDEX after the load backfills the whole graph in one pass, and every write from then on keeps it live.

Skip it when the fan-out is small and uniform (a plain traverse-then-sort is already cheap), when you never LIMIT the result (you want all neighbours in order — there is no top-N to accelerate), or when the target property changes very frequently on high-degree anchors (see the write-cost note below).

Advisor: discovering you need one

You do not have to guess whether a query would benefit. patinaDB ships an advisor that recognises the traversal-fan-out + ORDER BY target.prop LIMIT shape and, when it is running the slow fan-out top-K only because no covering edge-sorted index exists, tells you the exact statement to create. It is advice only — it never creates anything and never changes how a query runs.

In EXPLAIN / PROFILE. When the plan falls onto the fan-out limit.bounded_topk for a coverable shape, the plan text carries an Advice: line naming the index that would flip it to limit.edge_sorted_topk:

EXPLAIN MATCH (u:User {uid: 1})-[:REPORTED]->(t:Ticket)
        RETURN t ORDER BY t.created_at DESC LIMIT 20

…
Physical:
  limit.bounded_topk
Advice: CREATE EDGE SORTED INDEX FOR ()-[:REPORTED]->(m:Ticket) ON m.created_at  (would serve this ORDER BY … LIMIT via edge_sorted_topk instead of a fan-out top-K)

Run that CREATE EDGE SORTED INDEX and the advice disappears — the plan now reads limit.edge_sorted_topk. That round-trip is the guarantee: an advice is emitted iff creating the named index would actually engage the fast path (it reuses the executor’s own coverage decision), so there are no false positives.

As a procedure. CALL patinadb.advisor(query) analyses an arbitrary query string and returns one row per suggestion:

CALL patinadb.advisor(
  'MATCH (u:User {uid: 1})-[:REPORTED]->(t:Ticket) RETURN t ORDER BY t.created_at DESC LIMIT 20'
) YIELD suggestion, reason, current_plan

It returns no rows (no error) when there is nothing to suggest: a non-traversal query, a shape an edge-sorted index cannot serve (variable-length, undirected, multi-anchor, no ORDER BY … LIMIT, a filtered/unlabeled target), or a query already served by a covering index. Use it to sweep your hot read queries and discover the exact indexes to declare.

Honest positioning and tradeoffs

How this compares to other graph databases. General-purpose graph databases, Neo4j included, index a relationship’s own properties, or a node’s properties — not a per-anchor adjacency pre-sorted by a neighbour’s property. For the top-N-neighbours-by-neighbour-property shape that means the usual plan is traverse-then-sort, exactly the cost this index removes. The underlying idea of a sorted adjacency is not new — bespoke feed and social-graph stores have long kept time-sorted association lists for precisely this access pattern — but exposing it as a declarative, general-purpose index you can CREATE over any (rel, target-property) pair, inside a Cypher database, is uncommon. That is the differentiator, stated plainly.

Write cost. The index is maintained synchronously, and the cost is not free:

• Creating or deleting an edge updates one index entry — cheap.
• Changing a target’s sort property moves that target in every anchor’s slice that points at it. For a target with high in-degree (many anchors point to it), a single SET t.created_at = … is O(in-degree) index moves. If your workload rewrites the sort property often on well-connected targets, weigh that against the read speedup.

Snapshot-carry caveat (clustered mode). In a Raft cluster the index definitions replicate via the Raft log — every node re-runs the DDL and builds its own copy, deterministically. They are not yet carried in Raft snapshots. A node that bootstraps purely from a streamed snapshot (after the log that carried the CREATE was purged) will lack the def and quietly fall back to traverse-then-sort until the DDL is re-issued. Correctness is never affected — only speed — and the fallback path returns identical rows. Re-issue the CREATE EDGE SORTED INDEX statements after such a bootstrap (they are idempotent) to restore the fast path. This is tracked in Limitations.