| 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) | O(1) |
...
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 list elements with descendant Cps Path
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.
Work Breakdown for Implementation
...