...

• NCMP CM-handle de-registration moved from average quadratic to linear time (constant rate). De-registering 20,000 CM-handles is thousands of times faster now.
• CPS Path Queries have moved from worst-case quadratic to linear time complexity, and best case linear to constant. Queries that took days previously take minutes or seconds now.
• Memory usage during read operations has decreased by more than 90%.
• Not only has performance increased, but reliability and robustness. It is now possible for a single batch operation to handle tens of thousands of elements, where it would have failed before.

...

Recently, functionality was added to enable reading whole lists (CPS-1696). Here we compare performance of reading a container node containing a list, versus reading the list (with all descendants).

As can be seen, it is slower reading the list than reading the parent node containing the list.

...

There have been massive orders-of-magnitude improvements to query performance. Formerly, queries had quadratic complexity, which is now linear. In the last month alone, performance has improved by 100x.

With a simple improvement, some cases can be made constant time instead of linear.

In the graphs below, time is measured in milliseconds.

Query one device out of many using absolute cps path

In this case, a query that matches a single device node using an absolute cps path is executed.TO DO Fill this section. See here for a previous PoC analysis: CPS-1646 CpsPath queries using path-component lookup

Query one device out of many using descendant cps path

In this case, a query that matches a single device node using a descendant cps path is executed.

Query all devices using absolute cps path

In this case, a query that matches all device nodes using an absolute cps path is executed.

Query all devices using descendant cps path

In this case, a query that matches all device nodes using a descendant cps path is executed.

Commentary

Suggested improvement: For absolute cps path queries, the complexity can be reduced to best-case constant time (so it is no longer linear on the total number of fragments in the database).

Add a condition to the WHERE clause in the SQL to narrow the search space to children of the parent. For example:

SELECT * FROM fragment WHERE (existing conditions)

  AND parent_id IN (SELECT id FROM fragment WHERE xpath = '/parent-xpath')

(Note we used "parent_id IN" as there may be multiple parents with the same xpath during query across anchors.

Comparison of NCMP Performance across versions

...