Tuesday, August 21, 2012

Lucene's new BlockPostingsFormat, thanks to Google Summer of Code

Another summer wraps up, another successful Google Summer of Code project finished in Apache Lucene!

We had two projects this summer; here I'll describe Han Jiang's project (I was his mentor). The second project, separating StorableField and IndexableField, is also very exciting and wrapping up now.

The goal of Han's project was to create a compelling replacement int-block postings format, improving on the aging variable-int postings format that Lucene has used forever. The project was definitely a success! This morning I merged over the feature branch we had been using all summer, committing to both Lucene's trunk (future 5.x) and Lucene 4.x branch (to be 4.0 GA). This means Lucene 4.0 GA will have the new BlockPostingsFormat available.

The new postings format shows incredible search performance gains versus the current default postings format. I tested with luceneutil on the full May 2012 English Wikipedia index (33.3 million documents, 15 GB index):

TaskQPS baseStdDev baseQPS packedStdDev packed% change
AndHighLow353.099.16317.062.5313%-7%
Fuzzy253.081.0249.583.4114%-1%
Respell41.230.5639.671.378%-0%
PKLookup169.411.94166.691.573%-0%
Fuzzy133.070.8235.240.931%-12%
IntNRQ3.820.014.090.280%-14%
MedSpanNear1.460.031.600.035%-13%
HighSpanNear0.550.010.620.019%-17%
LowSpanNear2.650.063.080.0312%-19%
HighSloppyPhrase0.630.020.740.029%-23%
OrHighHigh3.040.173.550.350%-35%
HighPhrase0.650.000.760.049%-24%
OrHighMed6.620.397.750.800%-37%
LowSloppyPhrase2.340.042.780.0514%-23%
Wildcard17.200.2020.420.7612%-24%
OrHighLow7.290.448.670.920%-39%
AndHighMed23.110.6127.550.3414%-23%
LowPhrase7.440.109.010.4413%-28%
Prefix324.650.3529.941.2314%-28%
MedPhrase3.470.044.240.1815%-28%
MedSloppyPhrase2.030.042.510.0419%-28%
LowTerm145.810.36182.142.0223%-26%
MedTerm51.640.2565.571.1424%-29%
HighTerm8.490.0310.940.2325%-32%
AndHighHigh6.520.198.700.1926%-40%


The gains are awesome! After this change has baked for a while I expect we'll make it the default postings format, maybe in time for 4.1.

This effort has been a long time coming: ever since the creation of flexible indexing, allowing for full pluggability of all files in the index, we have wanted to improve on Lucene's postings format. Early int-block prototypes showed great performance.

The new format stores postings data in fixed blocks of 128 ints. Each block is encoded using a simple packed ints format. The .doc file interleaves docID delta and term frequency blocks, and also includes skip data, while the .pos file holds position deltas. Offsets and payloads, if present, are stored in the .pay file. On the full English Wikipedia index used in the above test this resulted in a nice reduction of disk usage: 13.7 GB (new) vs 14.7 GB (current). That's ~7% smaller.

The format only uses packed int blocks for high-frequency terms: low frequency terms (that appear in less than 128 documents), and the final partial-block of a high frequency term, are stored in the same variable-int format as today's default. Skip points are stored at the start of each block (except the first block).

Han built and tested a number of fun ideas, including skipping within blocks (with partial block decoding), using PForDelta instead of simple packed ints, wrapping with PulsingPostingsFormat, all sorts of different ways to decode packed ints, different values for blockSize and skipMultiplier, encoding all-single-values very compactly, etc. We spent lots of electricity running all sorts of benchmarks. Some ideas worked and some didn't, and things did not go according to the original plan! Such is the healthy unpredictable, zig-zag, iterative nature of open-source development/exploration, yet in the end we find ourselves with a great new postings format.

Thank you Han Jiang for such an important improvement to Lucene, and thank you Google for sponsoring this effort through Google Summer of Code.

6 comments:

  1. Nice one Mike and great to hear a pure success not only with the code but also with the mentoring of the project as a whole. I suspect that your student Han Jiang will be sticking around in the Lucene circle for a while ;0) I'll look forward to your follow up post if/when the code makes it into 4.1!

    ReplyDelete
  2. Thanks Mike! It is always enjoyable to discuss with you! I'll be glad to contribute if we need any further optimization!

    ReplyDelete
  3. We just published a paper where we use exactly the same scheme (as far as I can tell). We call it SIMD-BP128.

    You might be interested in the following blog post:

    Fast integer compression: decoding billions of integers per second
    http://lemire.me/blog/archives/2012/09/12/fast-integer-compression-decoding-billions-of-integers-per-second/

    You will find a link to our paper as well as our C++ in the blog post.


    Though we wrote our software in C++, I ported some schemes in Java:

    https://github.com/lemire/JavaFastPFOR

    ReplyDelete
  4. Hi Daniel,

    VERY interesting! Thank you for writing the paper and sharing your source code under the generous Apache Software License 2. I'll read the paper ... it looks very thorough.

    I would love to do our packed bit decoding in C w/ SIMD instructions...

    ReplyDelete
  5. Hey Mike and Han, Kudos to the great work.

    Just a clarification, does this block posting codec comes along with the 4.0 GA?

    ReplyDelete
  6. Hi Ramprakash,

    Yes, BlockPostingsFormat is available in 4.0, however it's not the default format, and I think the format has changed from 4.0 to 4.1 so if you index with it you'll have to re-index after upgrading.

    As of 4.1 it's the default and will have full back compat ...

    ReplyDelete