cancel
Showing results for 
Search instead for 
Did you mean: 

Join the community at Nodes 2022, our free virtual event on November 16 - 17.

Possible to granularly iterate over or "walk" an index from a starting node?

haniwalta
Node

Hello!

I have tried googling this question in different ways and cannot find a definitive answer, although the functionality seems unlikely (from what I've found) but maybe possible(??).

Q: In any of the Neo4j versions with or without any of the libraries or APIs, is it possible to linearly traverse or "walk" a single-property b-tree index from an arbitrary starting node in that index, essentially using the index as a sorted linked list? E.g. starting at an indexed node in the middle of a single property index, is it possible to determine which N nodes are directly above and/or below that position in the index in ~O(N) db hits?

The specific context for this question is difficult to articulate, but my project involves ~10 million nodes that all share the same four b-tree property indexes that linearly rank the nodes. For performance reasons I would like to start at an arbitrary node, then read an arbitrary number of nodes directly above and/or below that node traversing along one of the indexes in O(N) database hits, N being the number of nodes read above/below.

I know I could accomplish this with 40 million relationships that would form sorted linked lists along those 4 indexes, but if possible I would like to avoid this because:

  • The indexed property values will be changing somewhat frequently and I would rather not deal with keeping the sorted linked lists updated myself (would probably need to make a custom procedure using the Java dev API), whereas property indexes will stay updated behind the scenes
  • There is much else happening in this db, and I would like to avoid those 40 million relationships if b-tree index traversal could accomplish the same thing.

I found the (deprecated, to be replaced at some point) traversal framework in the Java API but that appears to only work with relationships. I essentially want that framework, but using indexes instead. Is this possible somehow?

1 REPLY 1

Well if an IndexSeekByRange is used that should work.

For example, if there's an index on :Person(born), then you could use:

MATCH (p:Person) 
WHERE p.born > 1950
RETURN p.born as dob
ORDER BY dob ASC
LIMIT 10

And that should walk the index getting 10 nodes within that range. Also, because the predicate acts as a type hint (the planner now knows this is an index with integer types), it can plan this using index-backed ordering, so the ordering as well as the projection of the property is driven by the index.