...
The new approach involves adding a column to the Fragment table, storing the last path component (called xpath_component here). The new column is indexed, to allow constant-time lookups.
| id | parent_id | anchor_id | xpath | xpath_component |
|---|---|---|---|---|
| 1 | NULL | 3 | /bookstore | bookstore |
| 2 | 1 | 3 | /bookstore/categories[@code='1'] | categories[@code='1'] |
| 3 | 2 | 3 | /bookstore/categories[@code='1']/books[@title='Matilda'] | books[@title='Matilda'] |
| 4 | 2 | 3 | /bookstore/categories[@code='1']/books[@title='The Gruffalo'] | books[@title='The Gruffalo'] |
The new approach will first look for "bookstore", and using that as the parent ID, look for ''categories[@code='1']", and using that as parent ID, look for "books" or xpath component starting with "books[", before finally applying leaf condition checks.
...
A PoC was developed so that performance could be compared against existing Cps Path Query algorithms.
Test data
These tests were performed using the openroadm model, present in the integration-test module of CPS source code repo.
In this case, each 'device' node is comprised of 86 cps data nodes. In these tests, 4 anchors were populated using the same data.
Performance Improvement
Query one device from many, using descendant cps path
...
//openroadm-device[@device-id="C201-7-1A-14"]
| Case |
|---|
| Query one out of many using descendant cps path | Query one out of many using absolute cps path | |
|---|---|---|
| Query | //openroadm-device[@device-id="C201-7-1A-14"] | /openroadm-devices/openroadm-device[@device-id="C201-7-1A-19"] |
| Graph |
As seen in the graphs, query performance for current master branch is linear on the size of the database, while the PoC implementation is constant time (independent of DB size).
...
(Note, I have not illustrated all different fetchDescendantOptions, as it has only minor impact in this case of fetching 1 device node.
Query many devices from many, using
...
descendant cps path
In this case, a query that matches a single many device node nodes using an absolute a descendant cps path is executed, such as:
/openroadm-devices/openroadm-device[@device@ne-idstate="C201-7-1A-19"]inservice"]
| Omit Descendants | Direct Descendants | All Descendants |
|---|---|---|
In above cases, it is observed that the existing algorithm grows quadratically - O(n2), e.g. doubling from 1000 to 2000 nodes takes 4 times longer (going from 40 to 160 seconds).
The PoC algorithm grows linearly - O(n), e.g. doubling from 1000 to 2000 nodes takes 2 times longer (going from 3.5 to 7 seconds)As seen in the graph, query performance for current master branch is linear on the size of the database, while the PoC implementation is constant time.
Query many devices from many, using
...
absolute cps path
In this case, a query that matches many device nodes using a descendant an absolute cps path is executed:
/openroadm-devices/openroadm-device[@ne-state@status="inservicesuccess"]
| Omit Descendants | Direct Descendants | All Descendants |
|---|---|---|
...
In above cases, it is observed that the existing algorithm grows quadratically - O(n2), while the PoC algorithm grows linearly - O(n).
Summary of performance
As can be seen in the cases below, the existing algorithm using regex has linear time complexity, on the the size of the database. The new algorithm is constant time.
- For querying 1 out of many nodes, existing algorithm is linear time (linear on fragment table size).
- For querying 1 out of many nodes, new algorithm is constant time.
- For querying many out of many nodes, existing algorithm is quadratic on fragment table size.
- For querying many out of many nodes, new algorithm is linear on fragment table size.
- In all cases, there is an easily observed massive reduction in query duration using new algorithm.
Work Breakdown
In addition to the changes outlined above, there is additional work remaining for this change to be production-ready.
...