...

Of course, the performance gap widens as the database grows larger, owing to the different time complexity.

...

Description of existing Cps Path query algorithms

The current implementation of Cps Path queries relies on regular expressions in the generated SQL queries.

...

• For a query that will return 1 out of N items, the best possible time complexity is constant, O(1).
• For a query that will return all N items, the best possible time complexity is linear, 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.

...