...
| 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) | to or O(N) | , depending on how many nodes are matched by the descendant | For example, it is O(N) with the above query, but O(1) when using this query: | O(1) |
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 database size).
(Note, I have not illustrated all different fetchDescendantOptions, as it has only minor impact in this case of fetching 1 device node.)
Query all devices (N out of N) using descendant cps path
In this case, a query that matches many all device nodes using a descendant cps path is executed:
...
.
| Fetch descendants | Omit Descendants | Direct Descendants | All Descendants | |||
|---|---|---|---|---|---|---|
| Query | //openroadm-device[@ne-state="inservice"] | Fetch descendants | Omit Descendants | Direct Descendants | All Descendants//openroadm-device[@ne-state="inservice"] | //openroadm-device[@ne-state="inservice"] |
| 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) |
...
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).
Query all
...
devices (N out of N) using absolute cps path
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 |
|---|---|---|---|
| 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 of proposed solution
...
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 conditions could be applied to any or all path components.
For example, given these queries:
- /bookstore/categories[@code='1']/books[@title='Matilda']
- /bookstore/categories[@name='SciFi']/books[@title='Matilda']
- /bookstore/categories/books[@title='Matilda']
Presently, only case 1 will return data, and cases 2 and 3 return nothing. Given the proposed solution uses an SQL sub-query for each path-component, with a little work, cases 2 and 3 could be supported.
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. (In fact, the exact same code could be used.)
However, some of these existing operations have "plural" implementations taking Collections as parameters, such as getDataNodesForMultipleXpaths. Additional investigation is needed for these cases
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. (In fact, the exact same code could be used.)
However, some of these existing operations have "plural" implementations taking Collections as parameters, such as getDataNodesForMultipleXpaths. Additional investigation is warranted.
Note: In the event that all operations are using the new approach - using xpath_component - then it may be possible to remove the xpath field entirely from the fragments table.
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 will allow for future improvement where conditions could be applied to any or all path components.
For example, given these two queries:
- /bookstore/categories[@code='1']/books[@title='Matilda']
- /bookstore/categories[@name='SciFi']/books[@title='Matilda']
- /bookstore/categories/books[@title='Matilda']
Presently, only case 1 will return data, as "categories[@code='1']" is the list element reference, with 'code' being the list key for categories.
Cases 2 and 3 will return nothing. Given the proposed solution uses an SQL sub-query for each path-component, with a little work, cases 2 and 3 would be supported.
Index-only lookup where leaf-condition is in the xpath
Note in Given the following CPS path query:
...
We can optimize for this case, using an index-only lookup.by checking if xpath_component = "books[@title='Matilda']", thus avoiding the need to examine the attributes field in the fragment table.
In the PoC implementation, the following is a Given the following SQL snippet from the SQL generated from the CPS path query:
...
This would allow for an index-only lookup of the itemnode, without needing the LIKE comparison or the attribute check.
...