...
| Fetch descendants | Omit Descendants | Direct Descendants | All Descendants |
|---|---|---|---|
| Query | /openroadm-devices/openroadm-device[@status="success"] | /openroadm-devices/openroadm-device[@status="success"] | /openroadm-devices/openroadm-device[@status="success"] |
| Comparison graph |
|
|
|
| Graph detail |
|
|
|
Time complexity of | Unclear, as there is very high variance. Likely O(N). | O(N2) | O(N2) |
| Time complexity of proposed solution | O(N) | O(N) | O(N) |
Possible improvements
Cps Path Query capabilities can be extended
Presently, Cps Path queries limit leaf-condition, text-condition, etc. to the final path component. The proposed solution allows for future improvement where leaf conditions could be applied to any or all path components.
...
Presently, only case 1 will return data (because 'code' is the list key for 'categories'), and cases 2 and 3 return nothing. Given the proposed solution uses an SQL sub-query for each path-component, the query generator can be adapted to support cases 2 and 3, with no expected performance impact.
Other operations can be accelerated
The same algorithm to improve query performance could also be used to improve performance of other operations, such as GET, UPDATE, and DELETE data nodes. However, some of these existing operations have "plural" implementations taking Collections as parameters, such as getDataNodesForMultipleXpaths. Additional investigation is needed for these cases.
Optimization: Index-only lookup when list key is used in leaf condition
Given the following CPS path query:
...
This would allow for an index-only lookup of the node, without needing the LIKE comparison or the attribute check.
Work Breakdown for Implementation
Beside the work done in the PoC implementation, there is additional work for this change to be production-ready. The main algorithm is mostly complete in the PoC (all integration tests are passing for the PoC). The existing PoC code can thus be refactored to make it production ready.
Cps Path Parser changes
The PoC uses String.split for parsing path components, which means paths containing '/' in the leaf condition are not parsed correctly, such as //books[@title='GNU/Linux']. CpsPathBuilder and CpsPathQuery classes from cps-path-parser module will need to be updated to provide the individual path components (in normalized form).
DB upgrade
Because a new column is being added to the Fragment table, the new column needs to be populated during DB upgrade (to maintain backwards compatibility with existing databases). An SQL script will be needed to provide a value for of the new xpath_component field based on existing xpath field.
...