| Table of Contents |
|---|
...
The test timings used to generate the charts in this document is available as a spreadsheet: CPS-1646 CpsPath queries using path-component lookup.xlsx
Query one device out of many
...
In this case, a query that matches a single device node is executed.
| 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.) |
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 the case of fetching 1 device node.
Query all devices
...
using descendant cps path
In this case, a query that matches all device nodes using a descendant cps path is executed.
| Fetch descendants | Omit Descendants | Direct Descendants | All Descendants |
|---|---|---|---|
| Query | //openroadm-device[@ne-state="inservice"] | //openroadm-device[@ne-state="inservice"] | //openroadm-device[@ne-state="inservice"] |
| Comparison graph |
|
|
|
| Graph detail |
|
|
|
Time complexity of | Unclear, as there is very high variance. Probably O(N). | O(N2) | O(N2) |
| Time complexity of proposed solution | O(N) | O(N) | O(N) |
Query all
...
devices 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 |
|---|---|---|---|
| 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.
...
Optimization: Index-only lookup when list key is used in leaf condition
Given the following CPS path query:
/bookstore/categories[@code='1']/books[@title='Matilda']...
In this case, the bookstore model specifies that the 'title' leaf is the key for 'books', and thus the xpath is encoded in the database as: /bookstore/categories[
...
@code='
...
1']/books[@title='Matilda']
...
We can optimize for this case, by checking if xpath_component = "books[@title='Matilda']
...
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:
/bookstore/categories[@code='1']/books[@title='Matilda']In this case, the bookstore model specifies that the 'title' leaf is the key for 'books', and thus the xpath is encoded in the database as: /bookstore/categories[@code='1']/books[@title='Matilda']
We can optimize for this case, by checking if xpath_component = "books[@title='Matilda']", thus avoiding the need to examine the attributes field in the fragment table (thus the entire operation involves only database indexes).
In the PoC implementation, the following is a snippet from the SQL generated from the CPS path query:
| Code Block | ||
|---|---|---|
| ||
AND (xpath_component = 'books' OR xpath_component LIKE 'books[%')
AND (attributes @> '{"title":"Matilda"}') |
It may be replaced with this to add the new functionality:
| Code Block | ||
|---|---|---|
| ||
AND (
xpath_component = 'books[@title=''Matilda'']'
OR (
(xpath_component = 'books' OR xpath_component LIKE 'books[%')
AND (attributes @> '{"title":"Matilda"}')
)
) |
This would allow for an index-only lookup of the node, without needing the LIKE comparison or the attribute check.
Optimization: Faster look-ups for lists and list elements
Given the bookstore model where books are stored in a list, and given a path query //books[@price=15], using proposed solution, this would use a LIKE 'books[' to find potential matches.
AND (xpath_component = 'books' OR xpath_component LIKE 'books[%')The use of the LIKE operator in this case would result in O(N) time, as every fragment may need to be compared against the LIKE pattern. There is a solution which may push this case toward constant O(1) performance, namely adding the list name as an indexed column to the fragments table - note only list elements need this field populated, container nodes can set this field to NULL:
...
", thus avoiding the need to examine the attributes field in the fragment table (thus the entire operation involves only database indexes).
In the PoC implementation, the following is a snippet from the SQL generated from the CPS path query:
| Code Block | ||
|---|---|---|
| ||
AND (xpath_component = 'books' OR xpath_component LIKE 'books[%')
AND (attributes @> '{"title":"Matilda"}') |
It may be replaced with this to add the new functionality:
| Code Block | ||
|---|---|---|
| ||
AND (
xpath_component = 'books[@title=''Matilda'']'
OR (
(xpath_component = 'books' OR xpath_component LIKE 'books[%')
AND (attributes @> '{"title":"Matilda"}')
)
) |
This would allow for an index-only lookup of the node, without needing the LIKE comparison or the attribute check.
Optimization: Faster look-ups for lists and list elements
Given the bookstore model where books are stored in a list, and given a path query //books[@price=15], using proposed solution, this would use a LIKE 'books[' to find potential matches.
AND (xpath_component = 'books' OR xpath_component LIKE 'books[%')The use of the LIKE operator in this case would result in O(N) time, as every fragment may need to be compared against the LIKE pattern. There is a solution which may push this case toward constant O(1) performance, namely adding the list name as an indexed column to the fragments table - note only list elements need this field populated, container nodes can set this field to NULL:
| id | parent_id | anchor_id | xpath | xpath_component | list_name |
|---|---|---|---|---|---|
| 1 | NULL | 3 | /bookstore | bookstore | NULL |
| 2 | 1 | 3 | /bookstore/categories[@code='1'] | categories[@code='1'] | categories |
| 3 | 2 | 3 | /bookstore/categories[@code='1']/books[@title='Matilda'] | books[@title='Matilda'] | books |
| 4 | 2 | 3 | /bookstore/categories[@code='1']/books[@title='The Gruffalo'] | books[@title='The Gruffalo'] | books |
Our query could be modified to replace the LIKE with an indexed look up:
AND (xpath_component = 'books' OR list_name = 'books')This would give rise to constant time look up in such cases. If this solution is not implemented, users can work around this problem wrapping lists in container nodes, with the container being included in the descendant query, e.g. instead of //books[@title='Matilda'], change the model and use //books/book[@title='Matilda'] as a query. This would then have O(1) performance.
Note: if we wish to avoid creating additional database fields, using list/container name field would offer the best balance of performance, e.g.
| id | parent_id | anchor_id | xpath | container | |
|---|---|---|---|---|---|
| 1 | NULL | 3 | /bookstore | bookstore | |
| 2 | 1 | 3 | /bookstore/categories[@code='1'] | categories | |
| 3 | 2 | 3 | /bookstore/categories[@code='1']/books[@title=' | The GruffaloMatilda'] | books |
| 4 | 2 | 3 | /bookstore/categories[@code='1']/books[@title='The Gruffalo'] | books |
Our query could be modified to replace the LIKE with an indexed look up:
AND (xpath_component = 'books' OR list_name = 'books')This would give rise to constant time look up in such cases. If this solution is not implemented, users can work around this problem wrapping lists in container nodes, with the container being included in the descendant query, e.g. instead of //In this case, attributes for any list element path component would need to be looked up (so it would no longer be index-only). My suspicion is that this would have better general performance than using xpath_component alone, but testing is needed to verify.
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.
For example, given these queries:
- /bookstore/categories[@code='1']/books[@title='Matilda']
...
- /bookstore/categories[@name='SciFi']/books[@title='Matilda']
...
Note: if we wish to avoid creating additional database fields, using list/container name field would offer the best balance of performance, e.g.
...
In this case, attributes for any list element path component would need to be looked up (so it would no longer be index-only).
Work Breakdown for Implementation
...
- /bookstore/categories/books[@title='Matilda']
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 little expected performance impact. Note this feature would require storing the container/list name as an indexed field, as described in the previous section.
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.
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.
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).
...