Sorting asc vs. desc performance in views and N1QL

SQL++
1

Hello,

We know that the views sort data in ascending order. Since N1QL uses views behind the scenes, we assume that ORDER BY in asc is performant. How does N1QL handle ORDER BY desc? Is there a difference in performance?

For example in SQL relational database when an index is created, one can specify the order (asc / desc). Is there something similar in N1QL? In particular for paging results, does it stop searching once it reaches the LIMIT or does it have to go through the whole index prior to sorting both for asc and desc.

It would also be helpful to know the type / name of the indexing algorithm that is being used.

Thank you,

Levon

2

N1QL does stop processing once the final result count specified by LIMIT is reached. It may scan more than LIMIT entries along the way, for example if there is a WHERE clause.

3

Hi Levon,

N1QL currently re-sorts the results, so there is no distinction in performance between ASC and DESC.

The view index is used to identify the range of matching documents. Once these documents are identified, all further processing happens inside the N1QL engine.

View indexes use a b-tree based algorithm and data structure for index maintenance and traversal.

N1QL uses a quicksort for sorting operations.

4

Hi,

Thank you for the response. So then I have the same question for the view. What are the performance ramifications of asc vs. desc search for the view? I know that when doing regular view queries (without N1QL), you can specify descending=true. Does the view query handle both cases with the same performance?

Also to clarify, N1QL does its own sorting, but if you specify ORDER BY as desc, would it pass descending=true to the view?

Thanks again in advance,

5

N1QL does not pass descending=true to the view. In fact, the ORDER BY expressions in N1QL do not need to match the view at all, and N1QL does not currently compare its ORDER BY expressions agains the view.

I will ask my colleagues from the indexing team to address your other question about views and descending order performance.

6

Thank you, please let me know once you have a change to ask your colleagues.

7

Hi Levon,

The view engine btree range scan algorithm does not have any performance impact on using asc or desc order. Use of asc or desc uses a different comparator (Less(k1, k2) = k1 < k2 or Less(k1, k2) k2 < k1 function). So the performance should be the same for both.

8

Hi Levon,

The view engine btree range scan algorithm does not have any performance impact on using asc or desc order. Use of asc or desc uses a different comparator (Less(k1, k2) = k1 < k2 or Less(k1, k2) k2 < k1 function). So the performance should be the same for both.