Performance of OptionalIndex::SparseBlock::rank_if_exists

[PSeitz]

OptionalIndex::SparseBlock::rank_if_exists::binary_search is dominating the profile of the aggregation query with 86% The performance on 10M elements is still not terrible performance wise with 140ms.

Potential Improvements

• Lower the sparse/dense threshold, so it will be less of an issue
  • This costs compression ratio
• Use the passed docid block for incremental searches (https://github.com/quickwit-oss/tantivy/pull/1950)
  • This may add some complexity, since one passed docid block may span multiple dense/sparse blocks of different sparse/dense types
• Test exponential search instead of binary_search
• Different sparse format
  • The current format is basically &[u16]. That's great for select queries with direct access, but not great for rank queries. A different sparse format could try to strike a different balance between rank and select.

[fulmicoton]

@PSeitz thanks for documenting this. I suspect two codec might not be enough. Around the limit, sparse is not very good. One obvious solution could be to use split the u16 space into 256.

We could then have 256 u16 to express the cumulated number of elements lower than <= i * 256.

rank_if_exists would then be 1 lookup followed by a binary search in maximum 256 elements. select would be a binary search in a 256 elements followed by 1 lookup