...

Path queries using path-component lookup

Objective

Complexity of existing solution

As will be demonstrated by performance tests later in this document, the existing solution has the following performance characteristics: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 current time complexity is constantlinear, O(1N).
• For a query that will return all N items, the best theoretical current time complexity is linearquadratic, O(N²).

Complexity of existing solution

Objective

The objective is to achieve the maximum theoretical performance for queries.As will be demonstrated by performance tests later in this document, the existing solution has the following performance characteristics:

• For a query that will return 1 out of N items, the current best theoretical time complexity is linearconstant, O(N1).
• For a query that will return all N items, the current best theoretical time complexity is quadraticlinear, O(N²)).

The solution proposed in this document satisfies these performance targets.

...