Sorting with inverted indexes

Hi,

Is there any way to achieve sorting with inverted indexes? (I mean sorting with the index itself.)
I got a simple table:

create table messages(
    id int primary key,
    accountId int,
    created timestamp,
    message string,
    labels jsonb,
    index account_created_idx (accountId, created desc),
    inverted index labels_idx(labels)
);

I want to order the results by “created” field.
Of course I can do this:

select * from messages@account_created_idx where accountId = 5 and labels @> '[12]' limit 100;

This will use the account_created_idx index and it will be sorted the way I want, but it won’t use the labels_idx inverted index so the query time will grow as the message count will increase for accountId = 5.

The second option is:

select * from messages@labels_idx where labels @> '[5]' order by created desc limit 100;

This is much more slower of course because of the sort.

The first option’s speed is acceptable but I’m curious if there is a way to achieve this sorting with inverted indexes.

Hi @szalair,

Unfortunately it’s not presently possible to achieve this kind of thing with an inverted index in Cockroach. I believe it’s possible that we could guarantee some kind of ordering on the primary key, but I don’t think we do this today.

I’m not sure whether or not it’s possible for us to do this on keys besides the primary key provided the index was constructed particularly for that, it’s possible we could do so in some limited cases, but figuring that out would require a larger investigation. But thanks for the interesting question! It’s something I’ll keep thinking about.

Justin

It would take some syntax extensions (similar to STORING indexes. I don’t think postgres has a counterpart to this feature), but we could support an alternative sort key in an inverted index. We currently append the PK to the keys that are generated by the inverted index; we could instead append a tuple of the sort key and PK. Then point lookups in the inverted index would come in the desired order (and multiple point lookups could be intersected efficiently, etc).

Thank you for the answers! If Ben’s solution could happen someday, it would be great! :slight_smile: