[Feature Request] Improve BKD Tree DocIds Encoding for 24 and 32 bit variations

[expani]

Is your feature request related to a problem? Please describe

Lucene represents the docIds using 24 bits if the maximum docId within a leaf is <= 16,777,215 here else it represents the docId as a regular integer using 32 bits without any encoding.

A lucene segment can have around 2 billion docs and a significant amount of docIds might be represented using the 24 and 32 bits representation.

Most of the time spent in range queries are while collecting docIds readDelta16,
readInts24 and readInts32

If we can reduce the amount of bytes used to represent docIds, we can improve the reading time ( search ) especially for range queries over larger ranges and reduce the index size.

Some existing tickets that have already discussed this area are :

• Optimize readInts24 performance for DocIdsWriter apache/lucene#12527
• Understand/Improve the performance of numeric range queries #9541
• Understand/Improve the performance of range queries #11251

Describe the solution you'd like

I was trying to find the common prefix amongst the docIds when they are represented using 24 and 32 bit variation based on the NYC Taxi data for the field fare_amount with around 20 million docs.

I found that a lot of leaf blocks that were represented using 24 bits had common prefixes ( from MSB/Leftmost bit ) ranging from 8bits to 15 bits. Having 8 bits common doesn't really help in encoding as the docIds will be represented using 24 bit. But, having 15 common bits can help us save 7 bits per docId in a leaf of 512 docIds reducing the number of bytes used to represent a leaf block by 445 bytes. ((512* 7 ) / 8 ) = 448- 3 bytes ( used to represent the common prefix as VInt)

Similarly when performing a force merge on the segment, Lucene also used 32 bits representation for around 1000 leaf blocks and I saw common prefixes ranging from 7-15 bits amongst them. The best case of 15 bit common prefix in this case would save 956 bytes per leaf block.

I am planning to introduce a new encoding for 24 and 32 bit representation which will also store the common prefix and benchmark the changes in indexing and search performance.

Related component

Search:Performance

Describe alternatives you've considered

No response

Additional context

No response

[peternied]

[Triage - attendees 1 2 3 4 5 6 7 8]
@expani Thanks for creating this issue, can you create a pull request to address this?

[expani]

@peternied I will run some OSB benchmarks with my changes to Lucene core and update here with the findings.

[expani]

Performed a POC on OS 2.13 ( Lucene 9.10 ) by prefix encoding the docIds for 24 and 32 bit cases.

kdd file size is seeing a reduction of 17% on NYC Taxi index based out of OSB without any segment merges.

Baseline OS 2.13 => 5.603 GB

ll DocIdsBenchmark/opensearch-2.13.0-unpatch/data/nodes/0/indices/byUCjsO_T_yn2dBgs6Owaw/0/index/ | grep kdd
-rw-r--r--. 1 ec2-user ec2-user 1480153195 May 28 15:07 _7w.kdd
-rw-r--r--. 1 ec2-user ec2-user 1154177696 May 28 15:10 _cf.kdd
-rw-r--r--. 1 ec2-user ec2-user 1482800206 May 28 15:19 _k5.kdd
-rw-r--r--. 1 ec2-user ec2-user 1486112481 May 28 15:25 _q2.kdd

Prefix Encoded OS 2.13 => 4.663 GB

ll DocIdsBenchmark/opensearch-2.13.0-patch/data/nodes/0/indices/7UMER0DZRuCOviarxAQmOw/0/index/ | grep kdd
-rw-r--r--. 1 ec2-user ec2-user 1149777642 May 28 12:56 _5k.kdd
-rw-r--r--. 1 ec2-user ec2-user 1290313662 May 28 13:04 _d8.kdd
-rw-r--r--. 1 ec2-user ec2-user 1299432668 May 28 13:13 _lh.kdd
-rw-r--r--. 1 ec2-user ec2-user  924449744 May 28 13:14 _ns.kdd

I am seeing poor performance across different queries and the reason looks like CPU branch mis-prediction.

Async profiler command used

./bin/asprof `jps | grep OpenSearch | awk '{print $1}'` -e branch-misses -f unpatch_branch_miss_range_nyctaxi_3.html -d 150

Flamegraph of CPU Branch miss for baseline OS 2.13

Overall Branch mis-prediction in readInts24 and readints32 is cumulatively around 6-7%

Flamegraph of CPU Branch miss for prefix encoding OS 2.13

Overall Branch mis-prediction in readIntsPrefix ( new method that decodes prefix encoded docIds ) is cumulatively around 25-30%

I will try to explore the possibility of changing the decoding logic for unpacking prefix encoded docIds ( will try changing encoding later if this is successful ) to not use any conditional (if-else) statements.