lubitz
September 25, 2026, 12:46pm
1
The current CR implementation with DBAL adapter stores the graph in a relational database. This is in general not the most efficient way of storing graphs. The nodes are stored only with information about there parent/child relations (hierarchy relation) and their siblings (position). This works very well for queries of direct childs and parents.
But if you query nodes within a sub-tree of the graph you have to build the whole graph first and filter afterwards. This is very slow if you do searches on bigger sub-trees, e.g. “find all headlines of the website” or “find all news article from may in all categories”.
The goal is to remove the recursive queries (CTEs) if applicable and replace them with path-based queries. This shall result in:
Better read performance (Reduced subset to work on, no need to build the full graph)
Easier SQL queries (CTEs → Simple SELECT Statements)
Improved sorting (less recalculation of positions)
For all details have a look into this experiment PR description:
9.2 ← dlubitz:feature/fractional-indexing-paths
opened 09:00AM - 04 Sep 26 UTC
# Problem
The current CR implementation with DBAL adapter stores the graph in a… relational database. This is in general not the most efficient way of storing graphs. The nodes are stored only with information about there parent/child relations (hierarchy relation) and their siblings (position). This works very well for queries of direct childs and parents.
But if you query nodes within a sub-tree of the graph you have to build the whole graph first and filter afterwards. This is very slow if you do searches on bigger sub-trees, e.g. "find all headlines of the website" or "find all news article from may in all categories".
# Idea
Before Neos 9 we also had this issue, but solved it by **using paths** to store the "position" in the graph on each node. So you can easily reduce the set of possible node candidates, matching your criteria to only a specific subgraph - without building it.
But there were reasons for changing this in Neos 9.
## CTE vs Path
Using the CTEs (recursive queries) allows us to only store the information about the parent/child relation and the position of below the parent. This makes it easy to move nodes in the tree without the need to update any other children in the path. The tree is build on read. But this requires to build the full tree, to figure out, if a node is part of a subtree or not.
The path stores the position in the tree, which allows it easily to figure this out, without building the tree. You can fetch by simple string comparison all nodes belong to a subtree, or all ancestors by the segements in your path.
But this brings the cost of recalculating the paths on every move move (incl. their children).
Another issues (that already in Neos 8 exists) is the limitation of the path length, which results in the limitation of the graph depth. The index size in the database is limited (based on field type, configuration, etc). So we can't simple let the path grow infinite. With reaching some path lenght the index simply skips the information behind that limit, which makes the path fuzzy/wrong on deep graphs.
## Fractional indexing
See: https://observablehq.com/@dgreensp/implementing-fractional-indexing
The fractional indexing is an idea to keep the path as compact as possible, always allow to move/create node between other nodes.
This approach allows in theory to have "**infinite" space between two fragements**. Which means you can always put a node between to existing nodes, without changing the paths of the existing nodes.
The format is quite compacat, if the nodes are well distributed or created in the right order. Appending or prepending nodes keeps a very compact fragment (1.000.000 nodes -> 5 chars). But there are also circumstances, which will lead to fast increasing fragemens. So if you create/move node into the same gap multiple times (>1000), the fragment can quicky reach the lenght of 169 chars.
But the fragments are rebalanceable, so you can distributes new fragements over all children and reduce the length of each to 2-5 chars (see above).
By combining all fragments of each node (parent-childnode-relation) to a path we have a fully sortable and queriable for the whole CR.
**One thing to highlight is that a path, build with fractional indexing, includes also the position of the child node bekow his parent.**
Example paths:
```
a0
a0/a0
a0/a0/a0
a0/a0/a1
a0/a0/a2
a0/a0/a1
a0/a0/a3
a0/a0/a4
a0/a0/a5
a0/a0/a6
...
a0/a0/a3/a0
a0/a0/a3/a4/a0HO
a0/a0/a3/a4/a0HO/a0
```
## Advantages
### Better read performance
With the paths we can filter the result set of nodes to the needed subgraph without building it recursive. So we can save a lot of unecessary work on database level.
### Easier SQL queries
Removing the CTEs will result in easier to read SQL queries.
### Sort order included
As the fragment also contain the position/order of a node between its siblings, we get the sort order included.
### Improved sorting (gaped positions vs. fractional indexing)
Currently we use a "gap" approach for sorting with a static gap of 128. Which also requires rebalancing from time to time. The fractional indexing wouldn't need the rebalancing from pure sorting perspective, as it has always a fragment in between two other.
## Drawbacks
### More load on write side
The biggest advantage of the CTE is, that we don't need to do changes to the descendents of a moved node. The descendents are still in the same place - from a relative perspective. So they have the same distance in the graph as before.
With paths, we break this as the path contains information of the position of the parents in the graph. So we need to update all descendents of a moved node. This leads also to **materialized node edges** for each descendent node.
Luckily, the path updates are quite cheap, as we only need a string replacement of the path prefix here.
### Limited path length -> graph depth
Due to the limitation of the indexable data, the length of the path is limited - which results in a limitation of the graph.
The fractional indexing reduces the storage room, especially of siblings (if well distributed or rebalanced), so a broad graph is no concern. But the depth of the graph is strongly bound to the length of the path and caps it by ~120-180 levels (3-6 chars per level).
### Changed query result order
### Path maintenance
## Possible tweaks
Similar to Neos 8, we can allow longer paths than the index can handle. This would allow to store even deeper graphs, but without the performance of an index-fittig-graph. Queries on deeper levels would simply be slower, but still work.
# Performance analysis
I did a quick performance analysis with the [existing benchmark suite](https://github.com/neos/contentrepository-benchmarktests) for the CR. **I had to reduce the maximum graph depth to 250 levels, as the path can't handle deeper graphs due to his length restrictions.**
Scenarios:
| File | Sample | Depth | Breadth |
|---|---|---:|---:|
| `01-BalancedGraph.json` | `twoLevels` | 2 | 10 |
| `01-BalancedGraph.json` | `fourLevels` | 4 | 10 |
| `02-BroadGraph.json` | `firstSample` | 1 | 11110 |
| `03-DeepGraph.json` | `firstSample` | 250 | 1 |
## Subgraph queries (the changed read path)
| Scenario | Metric | cte (before) | path (after) | Change |
|---|---|---:|---:|---:|
| **Balanced** d=2 b=10 | descendants | 3.15 ms | 1.42 ms | **−55%** (2.2×) |
| | subtree | 3.08 ms | 1.60 ms | **−48%** (1.9×) |
| | ancestors | 1.43 ms | 0.35 ms | **−75%** (4.1×) |
| | children / parent / id / reference | 0.5–0.6 ms | 0.5–0.6 ms | ±2% |
| | backReference | 0.64 ms | 0.72 ms | +12% |
| **Balanced** d=4 b=10 | descendants | 290.3 ms | 79.7 ms | **−72%** (3.6×) |
| | subtree | 313.2 ms | 89.9 ms | **−71%** (3.5×) |
| | ancestors | 14.57 ms | 0.48 ms | **−97%** (30.4×) |
| | children / parent / id | 0.3–2.0 ms | 0.3–2.0 ms | ±4% |
| | reference | 0.67 ms | 0.57 ms | −15% |
| | backReference | 5.22 ms | 5.21 ms | −0.2% |
| **Broad** d=1 b=11110 | descendants | 162.3 ms | 74.9 ms | **−54%** (2.2×) |
| | subtree | 177.6 ms | 84.0 ms | **−53%** (2.1×) |
| | ancestors | 15.07 ms | 0.45 ms | **−97%** (33.7×) |
| | children / parent / id / reference | 0.35–2.0 ms | 0.36–2.0 ms | ±5% |
| | backReference | 5.24 ms | 5.43 ms | +4% |
| **Deep** d=250 b=1 | descendants | 73.88 ms | 2.52 ms | **−97%** (29.3×) |
| | subtree | 75.35 ms | 3.26 ms | **−96%** (23.1×) |
| | ancestors | 1.72 ms | 0.43 ms | **−75%** (4.0×) |
| | children / parent / id | 0.33–0.51 ms | 0.37–0.57 ms | +10…+13% |
| | reference | 0.56 ms | 0.67 ms | +20% |
| | backReference | 0.69 ms | 0.77 ms | +12% |
## Command runtime and ContentGraph queries
| Scenario | commandRuntime cte → path | Change | `contentGraphQueryTime.*` |
|---|---|---:|---|
| Balanced d=2 | 884 → 878 ms | −0.7% | all within ±12% (sub-ms, noise) |
| Balanced d=4 | 87 631 → 94 473 ms | +7.8% | within ±16% (sub-ms); ancestors 3.28 → 3.30 ms (+0.5%) |
| Broad | 98 411 → 102 036 ms | +3.7% | within ±18% (sub-ms); ancestors 3.34 → 3.33 ms (−0.2%) |
| Deep | 1 973 → 2 211 ms | +12.1% | within ±23% (sub-ms); ancestors 0.40 → 0.42 ms (+6.8%) |
## Raw per-run values for the metrics that moved
| Scenario | Metric | cte runs 1 / 2 / 3 | path runs 1 / 2 / 3 |
|---|---|---|---|
| Balanced d=2 | descendants | 3.15 / 3.04 / 3.19 ms | 1.42 / 1.37 / 1.42 ms |
| | subtree | 3.21 / 3.08 / 3.08 ms | 1.80 / 1.58 / 1.60 ms |
| | ancestors | 1.40 / 1.43 / 1.47 ms | 0.34 / 0.35 / 0.37 ms |
| Balanced d=4 | descendants | 286.2 / 290.3 / 294.2 ms | 79.7 / 80.6 / 78.8 ms |
| | subtree | 313.2 / 315.3 / 312.6 ms | 89.9 / 87.3 / 90.5 ms |
| | ancestors | 14.60 / 14.47 / 14.57 ms | 0.48 / 0.44 / 0.58 ms |
| Broad | descendants | 163.9 / 162.2 / 162.3 ms | 77.3 / 74.8 / 74.9 ms |
| | subtree | 183.8 / 177.6 / 175.7 ms | 84.0 / 86.5 / 82.9 ms |
| | ancestors | 14.95 / 15.07 / 15.42 ms | 0.54 / 0.45 / 0.44 ms |
| Deep | descendants | 73.9 / 74.6 / 72.3 ms | 2.52 / 2.50 / 2.58 ms |
| | subtree | 75.5 / 73.6 / 75.4 ms | 3.26 / 3.25 / 3.44 ms |
| | ancestors | 1.72 / 1.72 / 1.90 ms | 0.43 / 0.43 / 0.50 ms |
## Result
The benchmark shows a significant impovement of descendants, subtree and ancestors queries with the path-based queries.
But it also shows the costs on write side within the increased command runtime.
I also want to point out, that the current benchmark tests to not cover queries with e.g. NodeType filter or similar, where the path-based queries should show their real benefit. As it allows to reduce the resultset without building the whole subgraph.
# Disclaimer
Most changes of this PR are AI generated and not ment to get merged. It's only an experimental implementation to see effects and limitations of a general change from CTEs to path-based queries in the CR.
What is the plan?
Implement fractional indexing as path segments
Implement NodeSortPaths
Adapt Neos ContentGraphDbalAdapter to NodeSortPaths
Replace CTE Queries (findSubtree, findDescendantNodes, findAncestorNodes, …) with path based queries
Verify and document performance impact (before/after, read/write)
Who will work on this?
@lubitz anyone who wants to join in
What do we need? I’d like to apply for a funding of 4.000 € / 40h.
Please add your vote to the poll or leave your comment/questions below.
I’ll close the voting on Monday 5th October 2026 12:00 CEST.
1 Like