...
The new approach involves adding a column to the Fragment table, storing the last path component (called xpath_component here). TODO description of new algorithmThe 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.
For example, given this Cps Path:
...
A PoC was developed so that performance could be compared against existing Cps Path Query algorithms.
Performance Improvement
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.
...
...
Query one device from many, using descendant cps path
In this case, a query that matches a single device node is executed, such as:
//openroadm-device[@device-id="C201-7-1A-14"]| Case |
|---|
| Descendant Cps Path | 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.
Query one device from many, using absolute cps path
...
/openroadm-devices/openroadm-device[@device-id="C201-7-1A-19"]...
In this case, a query that matches a single device node using an absolute cps path is executed, such as:
...
/openroadm-devices/openroadm-device[@device-id="C201-7-1A-...
19"]
...
...
/openroadm-devices/openroadm-device[@device-id="C201-7-1A-46"]...
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 descendant cps path
...
//openroadm-device[@ne-state="inservice"]...
//openroadm-device[@ne-state="inservice"]...
In this case, a query that matches many device nodes using a descendant cps path is executed:
//openroadm-device[@ne-state="inservice"]| Omit Descendants |
|---|
Direct Descendants |
|---|
All Descendants | ||
|---|---|---|
Query many devices from many, using absolute cps path
...
/openroadm-devices/openroadm-device[@status="success"]...
/openroadm-devices/openroadm-device[@status="success"]...
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
- For querying 1 out of many nodes, new algorithm is constant
- For querying many out of many nodes, existing algorithm is quadratic
- For querying many out of many nodes, new algorithm is linear
Work Breakdown
In addition to the changes outlined above, there is additional work remaining for this change to be production-ready.
The main algorithm was mostly done during the PoC (all integration tests are passing for the PoC). The existing PoC code can thus be refactored to make it production ready.
DB upgrade
Because a new column is being added to the Fragment table, this column needs to be populated. An SQL script will be needed to provide a value for of the new xpath_component field based on existing xpath field.
Cps Path Parser changes
CpsPathBuilder and CpsPathQuery classes from cps-path-parser module will need to be updated to provide the individual path components.
...
/openroadm-devices/openroadm-device[@status="success"]...