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. It turns the query shape “a node’s neighbours, ordered by a property of the neighbour, top-N, paginated” from a traverse-then-sort into a seek + scan — no fan-out, no post-sort.

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

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 the CLI 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']

Keyset pagination is stable under concurrent writes (unlike SKIP n, which shifts when rows are inserted) and never re-scans the pages you have already seen.

Honest note on the cursor page. The bare top-N shape (page 1) is served by limit.edge_sorted_topk. Adding the keyset WHERE t.created_at < … currently changes the plan shape, so page 2 falls back to limit.bounded_topk — a bounded top-K heap that is O(k) memory and returns the correct rows, but still reads the fan-out to apply the filter. Pushing the cursor into an edge-sorted-index seek (so deep pages are O(log n + k)) is a planned follow-up. In practice the first page — the one users actually load — is the hot path, and it is fully covered.

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. If you sort the same neighbours by two different properties, or traverse two relationship types, you create one index per shape.

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.