Use bitpack encoding for LID blocks

[cheb0]

LIDs (posting lists) blocks are the most crucial data structure for search along with tokens. Currently, we utilize varints, which are slow and inefficient.

The proposed solution is to use bitpack encoding. There are two libraries to test in Go:

• ready to use library intcomp which works on top of 128 numbers chunks. Bit width is defined for every 32 numbers.
• Daniel Lemire's fastPFOR delta which is ported to Go. It tries to find optimal bit width for 128 numbers at the same time cutting large detas and placing them in a footer of the page. The algorithm is tuned for 64k pages

Need to test:

• dataset size overhead
• search and throughput performance metrics
• estimate how much is the overhead if we disable zstd for LID blocks

[dkharms]

I wanted to know why exactly LIDs? In which load scenarios you've noticed that we spend a lot of CPU time decoding LIDs? I've only noticed that we spend a lot of time decoding MIDs.

Also, this change will block us from using roaring bitmaps for storing LIDs - I am not sure that it will be space efficient but definitely more efficient (in terms of performance) for search and aggregations queries.

[cheb0]

I wanted to know why exactly LIDs? In which load scenarios you've noticed that we spend a lot of CPU time decoding LIDs? I've only noticed that we spend a lot of time decoding MIDs.

Also, this change will block us from using roaring bitmaps for storing LIDs - I am not sure that it will be space efficient but definitely more efficient (in terms of performance) for search and aggregations queries.

We spend quite some time decoding LIDs. For a test aggregation I've seen total time reading from disk + unpacking drops from 14 millis to 8 millis. The performance impact depends on how much we do on top of reading from disk. Obviously, it only relates to cold query runs.

I have not seen major performance for MIDs, but maybe I need to redo measurements. Obviously, it's also easy to support MIDs.

As for bitmaps, use of bitpack doesn't block anything. In fact, we will use bitmap for long LID lists like level. We will also use bitmaps for intersecting LID lists in LID tree while maintaining the same Volcano style iterator model we have right now (I am not sure, but I believe we can do it). And we also effectively evaluate expressions like level:[0 to 3] using bitmaps if underlying LIDs list is stored as bitmap.

It seems bleeding edge columnar compression formats tend to choose the most effective compression method based on block stastistics and sampling. Relying everything on a single data structure doesn't look like a winning strategy.

[dkharms]

As for bitmaps, use of bitpack doesn't block anything. In fact, we will use bitmap for long LID lists like level.

So you suggest to use different encoding techniques for different cases, right? Of course, that makes sense.

But there is catch: bitpacking + lid-at-a-time iterator model is very different from bitmaps + lid-batch-at-a-time and I am not sure that we will be able to come up with a decent interface for both approaches.

Also, I think there will a pretty significant performance penalty when we will perform transformation bitpack-lids -> bitmap. I guess it's all worth to measure.

[cheb0]

I wanted to know why exactly LIDs? In which load scenarios you've noticed that we spend a lot of CPU time decoding LIDs? I've only noticed that we spend a lot of time decoding MIDs.

I think I finally got why you are saying this. There two types of blocks which are read on search requests:

• MID and RID blocks for every found lid which is a part of
• LID blocks for searching and iterating through posting lists

It depends on fractions size and query parameters (search/hist/agg) if we read more MID or LID blocks. For prod we have pretty much often the following picture, so LID blocks unpacking dominate CPU usage:

I'm pretty sure there are cases where MID blocks are also bottlenecks like our scenario for seqbench.

[dkharms]

It depends on fractions size and query parameters (search/hist/agg) if we read more MID or LID blocks. For prod we have pretty much often the following picture, so LID blocks unpacking dominate CPU usage

I guess it can be explained by predicate, for example if user queries foo:bar AND message:*, then we would end up with the following tree:

AND [
	[foo-node]: [ block#1{100, 101, 102, 103} ]
	[message-node]: [ block#1{1, 2, 3, 4}, block#2{5, 6, 7, 8}, ..., block#25{100, 101, 102, 103}]
]

And we will waste a lot of CPU decoding LIDs blocks which will be dropped.
It's interesting that here we can clearly see the benefits that index-selectivity can give us.