| Table of Contents |
|---|
...
| 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"] |
| Comparison graph |
|
|
| Graph detail |
|
|
Time complexity of | O(N) | O(N) |
| Time complexity of proposed solution | O(N) | Near-constant, O(1) |
| Comments | The use of LIKE 'openroadm-device[%' in the query to match candidates | The use of the absolute path narrows the search space to only direct children of /openroadm-devices - for 3000 devices, we only need to scan 3000 fragments instead of 250k. (Technically this is still O(N), but linear on the number of items in the list, not the number of fragments in the DB.) |
...
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.
Fetch descendants
The proposed solution can broadly be broken into two major changes:
- Cps Path query using path-component look-up
- Using recursive SQL to fetch descendants of nodes returned from 1.
I proposed that the recursive SQL to fetch descendants be implemented first as an independent change, as it move worst-case complexity from O(N2) to O(N). By contrast, the query using path-component look-up will improve best-case performance from O(N) to O(1).
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).
...