[Proposal] Return most recent results first

[Fangjin Yang]

I've heard numerous folks in the community request for the ability to return results for an interval in reverse order (with most recent timestamps first). Most often, I hear this feedback for people using the select query, where queries often have page through numerous results before reaching the most recent ones.

Although there are several workarounds on the client side that can be instrumented to support this use case, returning most recent results can also be supported natively in Druid. I am writing this proposal to begin the discussion. If users are interested in contributing, this thread can be used to coordinate the development.

Query Context

We can add a new flag in the query context that will return reversed results. 

Reversing the Cursor

This flag will be passed down through the various query engines, through makeCursorBasedQuery(), and through the adaptors.makeCursors() method.

For IncrementalIndexStorageAdapter, we can simply reverse the cursorMap.

For QueryableIndexStorageAdapter, things get more tricky. We'll need reversible offset objects for filtered and non-filtered queries. The non-filtered index is more straightforward to implement. For the filtered case, we'll need the bitmap indexes to support reversible iterators. Concise sets already support this out of the box, but the immutable concise set will need to be adjusted to support this as well. Roaring bitmaps currently have no concept of a reversible cursor, and we'll need to either throw an exception, or add the logic to roaring bitmaps.

Merging Results

Care needs to be taken here as most of the merge logic assumes timestamps are ordered naturally. We'll need the ability to use different comparators based on the query. I believe this can be tricky to get right, so many new unit tests will be required.

Thoughts?

-- FJ

[Daniel Lemire]

 Roaring bitmaps currently have no concept of a reversible cursor, and we'll need to either throw an exception, or add the logic to roaring bitmaps.

I do not think that this is quite correct. With Roaring, you can iterate through the values in reverse order :

http://lemire.me/docs/RoaringBitmap/org/roaringbitmap/buffer/ImmutableRoaringBitmap.html#getReverseIntIterator--

So it is a simple matter of using the available API. 

[Fangjin Yang]

My bad, good to know. Thanks Daniel.

[Xavier]

My only concern with reverse cursor is the added complexity and potential for bugs / performance regressions.

Currently there are quite a few places in the query path that assume things are traversed in increasing time order, and take advantage of this to take some shortcuts and speed things up. I know this is the case for groupBy, for instance. 

An alternative would be to keep the same cursor direction, but implement sorting on the results. This would also give the flexibility of re-ordering results based on things other than time which I think would be more beneficial overall. 

[Fangjin Yang]

I worry about the performance of just sorting the results as the select query isn't the fastest as is. Also, the result set from select can be substantial, which means multiple queries need to be issued to get all the results from a time range before the results can be sorted.

[nav...@gmail.com]

I've found ImmutableRoaringReverseIntIterator is not cloneable. Could you check https://github.com/lemire/RoaringBitmap/pull/54?

2015년 9월 1일 화요일 오후 11시 18분 34초 UTC+9, Daniel Lemire 님의 말:

[Daniel Lemire]

Thanks to your PR, the issue is already fixed. Thanks. I am issuing a new release.

[Daniel Lemire]

The version with the fix will be 0.5.13, should be available today from the maven repository.

[nav...@gmail.com]

Thanks for the quick answer. 

2015년 11월 26일 목요일 오후 11시 17분 57초 UTC+9, Daniel Lemire 님의 말:

[Fangjin Yang]

Thanks for the contrib! We should be able to get to review it after thanksgiving.

[Charles Allen]

https://github.com/metamx/bytebuffer-collections/pull/21 submitted to get the workflow going for "proper" druid support

[Fangjin Yang]

BTW, a lot of this work has been done in the following PR: https://github.com/druid-io/druid/pull/2014/files