...
A new solution is being proposed where each path component of the Cps Path is looked up in constant time, thus addressing performance issues.
...
Objective of
...
the proposed solution
The objective is to achieve the maximum performance for queries.As will be demonstrated by performance tests later in this document, the existing solution has the following performance characteristics:
- For a query that will return 1 out of N items, the current best theoretical time complexity is constant, O(1). The existing solution is linear, O(N).
- For a query that will return all N items, the current best theoretical time complexity is quadraticlinear, O(N2).
Objective of the proposed solution
The objective is to achieve the maximum performance for queries.
...
- ). The existing solution is quadratic, O(N2).
| Operation | Existing solution | Proposed solution |
|---|---|---|
| Query 1 out of N | O(N) | O(1) |
...
| Query N out |
The solution proposed in this document satisfies these performance targets.
| Operation | Existing solution | Proposed solution |
|---|---|---|
| Query 1 out of N | O(N2) | O(1N) |
| Query all out of N | O(N2) | O(N) |
Implementation Proposal
Implementation Proposal
The 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.
...
In this case, a query that matches a single device node is executed, such as this for descendant CPS path:
//openroadm-device[@device-id="C201-7-1A-14"]or this for absolute CPS path:
/openroadm-devices/openroadm-device[@device-id="C201-7-1A-19"]Here is a summary of test results:.
| 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 |
|
Note: constant to within ±1 ms |
Time complexity of | O(N) | O(N) |
| Time complexity of proposed solution | O(N) | O(1) |
| Comments | This may be O(1) or O(N) depending on how many nodes are matched by the descendant |
...
In this case, a query that matches many device nodes using an absolute cps path is executed:.
| Fetch descendants | Omit Descendants | Direct Descendants | All Descendants | |||
|---|---|---|---|---|---|---|
| Query | /openroadm-devices/openroadm-device[@status="success"] | Fetch descendants | Omit Descendants | Direct Descendants | All Descendants/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) |
...