...
| 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) |
Why does the existing solution have quadratic complexity in some cases?
The reason the existing solution is quadratic time when fetching descendants is because the path query translates into a number of SQL queries:
- An SQL query that returns nodes matching query criteria
- For each node returned from query 1: issue an SQL query to fetch that node with descendants, using a LIKE operator.
The LIKE operator has linear time complexity, as all nodes' xpaths in a given anchor need to be examined.
In the case of a query that matches all N nodes, we are issuing N queries, each with complexity O(N). Thus the overall complexity is O(N2).
Possible improvements of proposed solution
...