Improve performance of order by index optimization

[andrii0lomakin]

Current order by optimization of queries is simple.
If we have small enough records in index and have non composite index we iterate through them.
But there is much more elegant idea of optimization of order by.
When we fetch data using index range query we can iterate through index in both directions descending and ascending so just by passing the flag of direction of iteration in index range query method we can provide much broader "order by" optimizations, actually we will simply not have restrictions of order by optimization which we have now.
Also very interesting point is that index iterators, they ask many additional memory areas to iterate which kill CPU cache locality for data which we really need to fetch so such proposed approach will be faster too.

Actually I would remove iterators from index at all.
They may be not thread safe either, because implementation com.orientechnologies.common.concur.resource.OSharedResourceIterator does not deal with thread safety of state between iterations.

Much efficient approach in this case is to introduce firstKey/lastKey methods in idex and use between queries. In such case we will iterate only through data which we need and will not prefetch unneeded data and drop iterators from index.

[lvca]

So this query:

select from Customer order by name

When you've 10M of Customer records, how do you prefetch so many records?

[andrii0lomakin]

We do not need to.
Range query will do pagination in thread safe manner.

[lvca]

So without iterators how do you lazy browse results?

[andrii0lomakin]

Paginated range query is lazy browsing of results, for example com.orientechnologies.orient.core.index.sbtree.OSBTreeMapEntryIterator in reallity paginated query.

[andrii0lomakin]

I got what you mean how to do async queries on the fly, but it is already implemented using listeners - com.orientechnologies.orient.core.index.OIndex#getValuesBetween. All records loaded using com.orientechnologies.orient.core.index.OIndex.IndexValuesResultListener not collections.

[lvca]

So do you mean to add a direction in OTreeInternal.loadEntriesMajor() to move forward and backward and use the OSBTreeMapEntryIterator to browse item?

[andrii0lomakin]

In such way it is up to listener how to process them. But only needed records will be loaded in ordered manner.

[andrii0lomakin]

I meant to add direction in com.orientechnologies.orient.core.index.OIndexEngine#getEntriesMajor and listener will follow through records in needed order.

[lvca]

Gotcha, +1