...
A new algorithm for queries is being proposed, avoiding regular expressions, so that query duration is independent of database size.
Objective
The objective is to achieve the maximum theoretical performance for queries.
- For a query that will return 1 out of N items, the best theoretical time complexity is constant, O(1).
- For a query that will return all N items, the best theoretical time complexity is linear, O(N).
Complexity of existing solution
As will be demonstrated by performance tests later in this document, the existing solution has the following performance characteristics:
...
| Operation | Existing solution | Proposed solution |
|---|---|---|
| Query 1 out of N | O(N) | O(1) |
| Query all out of N | O(N2) | O(N) |
Implementation Proposal
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.
...
- Storing only 'books' will allow for removing the 'LIKE' operator from the SQL query, potentially speeding queries in the general case.
With further development, this could allow for GET operation (getDataNodes) to return whole lists, using an index-only lookup. (Though given how fast proposed query solution is, the existence of the GET operation is questionable.) - Storing "books[@title='Matilda']" will allow for optimization of queries where the leaf-condition references the key leaf (as defined in the Yang model), thus skipping both the LIKE operator and the attribute check, but only in this specific case.
A note on fetching descendant nodes
The above sections only partly describe the current and proposed solutions. In both cases, a CPS path query is actually sent as two database queries:
...
This would allow for an index-only lookup of the item, without needing the LIKE comparison or the attribute check.
Work Breakdown for Implementation
In addition to the changes outlined above, there is additional work remaining for this change to be production-ready.
...