neoremind created LUCENE-9932:
---------------------------------
Summary: Performance improvement for BKD index building
Key: LUCENE-9932
URL: https://issues.apache.org/jira/browse/LUCENE-9932
Project: Lucene - Core
Issue Type: Improvement
Components: core/index
Affects Versions: 8.8.2
Reporter: neoremind
In BKD index building, the input bytes must be sorted before calling BKD writer
related API. The sorting method leverages MSB Radix Sort algorithm, and the
comparing method takes both the bytes itself and the DocId, but in real cases,
DocIds are usually monotonically increasing. This could yield one possible
performance enhancer. I found this enhancement when I dig into one performance
issue in our system. Then I research on the possible solution.
DocId is usually increased by one when building index in a thread-safe way, by
assuming such condition, the comparing method can eliminate the unnecessary
comparing input - DocId, only leave the bytes itself to compare. In order to do
so, MSB radix sorting and its fallback sorting method must be *stable*, so that
when elements are the same, the sorting method maintains its original order
when added, which makes DocId still monotonically increasing. To make MSB Radix
Sort stable, it needs a trivial update; to make fallback sort table, use merge
sort instead of quick sort. Meanwhile, there should introduce a switch which is
able to turn the stable option on or off.
To validate how much performance could be gained. I make a benchmark taking
down only the time elapsed in _MutablePointsReaderUtils.sort_ stage.
*Test environment:*
MacBook Pro (Retina, 15-inch, Mid 2015), 2.2 GHz Intel Core i7, 16 GB 1600 MHz
DDR3
*Java version:*
java version "1.8.0_161"
Java(TM) SE Runtime Environment (build 1.8.0_161-b12)
Java HotSpot(TM) 64-Bit Server VM (build 25.161-b12, mixed mode)
*Testcase:*
bytesPerDim = [1, 2, 3, 4, 8, 16, 32]
dim = 1
doc num = 2,000,000
warm up 5 time, run 10 times to calculate average time used.
*Result:*
||bytesPerDim\scenario||disable sort doc id (PR branch)||enable sort doc id
(master branch)||
|1|30989.594 us|1151149.9 us|
|2|313469.47 us|1115595.1 us|
|3|844617.8 us|1465465.1 us|
|4|1350946.8 us|1465465.1 us|
|8|1344814.6 us|1458115.5 us|
|16|1344516.6 us|1459849.6 us|
|32|1386847.8 us|1583097.5 us|
*!benchmark_data.png|width=571,height=278!*
When there are many duplicate bytes (bytesPerDim = 1 or 2 or 3) which means
data cardinality is low. By disable sorting DocId, it runs 1.73x to 37x faster.
When data cardinality is high, the performance does not go backward, also runs
after.
PR is submitted, I only study how to make BKDWriter runs fast, to make it work
for Lucene index building, I am not sure where to integrate this change into.
If any committers have time, could you help me review if the issue makes sense?
Thanks very much.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
