5.15. A multilevel indexing structure (path tree)

In this example, a multi-level tree structure is used to index event nodes (here Event1, Event2 and Event3, in this case with a YEAR-MONTH-DAY granularity, making this a timeline indexing structure. However, this approach should work for a wide range of multi-level ranges.

The structure follows a couple of rules:

  • Events can be indexed multiple times by connecting the indexing structure leafs with the events via a VALUE relationship.
  • The querying is done in a path-range fashion. That is, the start- and end path from the indexing root to the start and end leafs in the tree are calculated
  • Using Cypher, the queries following different strategies can be expressed as path sections and put together using one single query.

The graph below depicts a structure with 3 Events being attached to an index structure at different leafs.

Figure 5.15. Graph

Return zero range

Here, only the events indexed under one leaf (2010-12-31) are returned. The query only needs one path segment rootPath (color Green) through the index.

Figure 5.16. Graph

Query 

MATCH rootPath=(root)-[:`2010`]->()-[:`12`]->()-[:`31`]->(leaf),(leaf)-[:VALUE]->(event)
WHERE root.name = 'Root'
RETURN event.name
ORDER BY event.name ASC

Returning all events on the date 2010-12-31, in this case Event1 and Event2

Result

event.name
2 rows

"Event1"

"Event2"

Try this query live create (_0 {`name`:"Y11M01"}) create (_1 {`name`:"Y10M12D31"}) create (_2 {`name`:"Y10M12"}) create (_3 {`name`:"Event2"}) create (_4 {`name`:"Y11M11D02"}) create (_5 {`name`:"Y11"}) create (_6 {`name`:"Event3"}) create (_7 {`name`:"Y10"}) create (_8 {`name`:"Root"}) create (_9 {`name`:"Event1"}) create (_10 {`name`:"Y11M01D01"}) create (_11 {`name`:"Y11M12D03"}) create _0-[:`01`]->_10 create _0-[:`02`]->_4 create _0-[:`03`]->_11 create _1-[:`NEXT`]->_10 create _1-[:`VALUE`]->_3 create _1-[:`VALUE`]->_9 create _2-[:`31`]->_1 create _4-[:`NEXT`]->_11 create _5-[:`01`]->_0 create _7-[:`12`]->_2 create _8-[:`2010`]->_7 create _8-[:`2011`]->_5 create _10-[:`NEXT`]->_4 create _10-[:`VALUE`]->_3 create _11-[:`VALUE`]->_6 MATCH rootPath=(root)-[:`2010`]->()-[:`12`]->()-[:`31`]->(leaf), (leaf)-[:VALUE]->(event) WHERE root.name = 'Root'RETURN event.name ORDER BY event.name ASC

Return the full range

In this case, the range goes from the first to the last leaf of the index tree. Here, startPath (color Greenyellow) and endPath (color Green) span up the range, valuePath (color Blue) is then connecting the leafs, and the values can be read from the middle node, hanging off the values (color Red) path.

Figure 5.17. Graph

Query 

MATCH startPath=(root)-[:`2010`]->()-[:`12`]->()-[:`31`]->(startLeaf),
  endPath=(root)-[:`2011`]->()-[:`01`]->()-[:`03`]->(endLeaf),
  valuePath=(startLeaf)-[:NEXT*0..]->(middle)-[:NEXT*0..]->(endLeaf),
  vals=(middle)-[:VALUE]->(event)
WHERE root.name = 'Root'
RETURN event.name
ORDER BY event.name ASC

Returning all events between 2010-12-31 and 2011-01-03, in this case all events.

Result

event.name
4 rows

"Event1"

"Event2"

"Event2"

"Event3"

Try this query live create (_0 {`name`:"Y11M01"}) create (_1 {`name`:"Y10M12D31"}) create (_2 {`name`:"Y10M12"}) create (_3 {`name`:"Event2"}) create (_4 {`name`:"Y11M11D02"}) create (_5 {`name`:"Y11"}) create (_6 {`name`:"Event3"}) create (_7 {`name`:"Y10"}) create (_8 {`name`:"Root"}) create (_9 {`name`:"Event1"}) create (_10 {`name`:"Y11M01D01"}) create (_11 {`name`:"Y11M12D03"}) create _0-[:`01`]->_10 create _0-[:`02`]->_4 create _0-[:`03`]->_11 create _1-[:`NEXT`]->_10 create _1-[:`VALUE`]->_3 create _1-[:`VALUE`]->_9 create _2-[:`31`]->_1 create _4-[:`NEXT`]->_11 create _5-[:`01`]->_0 create _7-[:`12`]->_2 create _8-[:`2010`]->_7 create _8-[:`2011`]->_5 create _10-[:`NEXT`]->_4 create _10-[:`VALUE`]->_3 create _11-[:`VALUE`]->_6 MATCH startPath=(root)-[:`2010`]->()-[:`12`]->()-[:`31`]->(startLeaf), endPath=(root)-[:`2011`]->()-[:`01`]->()-[:`03`]->(endLeaf), valuePath=(startLeaf)-[:NEXT*0..]->(middle)-[:NEXT*0..]->(endLeaf), vals=(middle)-[:VALUE]->(event) WHERE root.name = 'Root'RETURN event.name ORDER BY event.name ASC

Return partly shared path ranges

Here, the query range results in partly shared paths when querying the index, making the introduction of and common path segment commonPath (color Black) necessary, before spanning up startPath (color Greenyellow) and endPath (color Darkgreen) . After that, valuePath (color Blue) connects the leafs and the indexed values are returned off values (color Red) path.

Figure 5.18. Graph

Query 

MATCH commonPath=(root)-[:`2011`]->()-[:`01`]->(commonRootEnd),
  startPath=(commonRootEnd)-[:`01`]->(startLeaf), endPath=(commonRootEnd)-[:`03`]->(endLeaf),
  valuePath=(startLeaf)-[:NEXT*0..]->(middle)-[:NEXT*0..]->(endLeaf),
  vals=(middle)-[:VALUE]->(event)
WHERE root.name = 'Root'
RETURN event.name
ORDER BY event.name ASC

Returning all events between 2011-01-01 and 2011-01-03, in this case Event2 and Event3.

Result

event.name
2 rows

"Event2"

"Event3"

Try this query live create (_0 {`name`:"Y11M01"}) create (_1 {`name`:"Y10M12D31"}) create (_2 {`name`:"Y10M12"}) create (_3 {`name`:"Event2"}) create (_4 {`name`:"Y11M11D02"}) create (_5 {`name`:"Y11"}) create (_6 {`name`:"Event3"}) create (_7 {`name`:"Y10"}) create (_8 {`name`:"Root"}) create (_9 {`name`:"Event1"}) create (_10 {`name`:"Y11M01D01"}) create (_11 {`name`:"Y11M12D03"}) create _0-[:`01`]->_10 create _0-[:`02`]->_4 create _0-[:`03`]->_11 create _1-[:`NEXT`]->_10 create _1-[:`VALUE`]->_3 create _1-[:`VALUE`]->_9 create _2-[:`31`]->_1 create _4-[:`NEXT`]->_11 create _5-[:`01`]->_0 create _7-[:`12`]->_2 create _8-[:`2010`]->_7 create _8-[:`2011`]->_5 create _10-[:`NEXT`]->_4 create _10-[:`VALUE`]->_3 create _11-[:`VALUE`]->_6 MATCH commonPath=(root)-[:`2011`]->()-[:`01`]->(commonRootEnd), startPath=(commonRootEnd)-[:`01`]->(startLeaf), endPath=(commonRootEnd)-[:`03`]->(endLeaf), valuePath=(startLeaf)-[:NEXT*0..]->(middle)-[:NEXT*0..]->(endLeaf), vals=(middle)-[:VALUE]->(event) WHERE root.name = 'Root'RETURN event.name ORDER BY event.name ASC