Make BEST_COMPRESSION compress more aggressively? [LUCENE-9447]

[asfimport]

The Lucene86 codec supports setting a "Mode" for stored fields compression, that is either "BEST_SPEED", which translates to blocks of 16kB or 128 documents (whichever is hit first) compressed with LZ4, or "BEST_COMPRESSION", which translates to blocks of 60kB or 512 documents compressed with DEFLATE with default compression level (6).

After looking at indices that spent most disk space on stored fields recently, I noticed that there was quite some room for improvement by increasing the block size even further:

Block size	Stored fields size
60kB	168412338
128kB	130813639
256kB	113587009
512kB	104776378
1MB	100367095
2MB	98152464
4MB	97034425
8MB	96478746

For this specific dataset, I had 1M documents that each had about 2kB of stored fields each and quite some redundancy.

This makes me want to look into bumping this block size to maybe 256kB. It would be interesting to re-do the experiments we did on #7162 to see how this affects the merging speed. That said I don't think it would be terrible if the merging time increased a bit given that we already offer the BEST_SPEED option for CPU-savvy users.

---

Migrated from LUCENE-9447 by Adrien Grand (@jpountz), resolved Aug 26 2020
Pull requests: apache/lucene-solr#1748, apache/lucene-solr#1762

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

From my experiments done on #7162, increasing block size for the most part is a workaround, it only helps hide the waste of rebooting the deflate dictionary from scratch for every block? So the "crappy preset" tried to show that there.

Sadly I couldn't find a decent/simple way to use preset dictionary that made me happy with what is available in the JDK. It doesn't expose some zlib methods that you would need (e.g. retrieving current dictionary) and as I mentioned, there were some inefficiencies, at least with how we had compression hooked in at the time.

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

I collected some data using various block sizes and a preset dict that consists of the first 32kB of the dataset like on #7162. The dataset consists of 1M highly compressible doucments whose total uncompressed size is 2.2GB.

Block size	Preset dict	Stored fields size	Index time	Merge time
BEST_SPEED	No	304MB	9s	200ms
60kB	No	100.6MB	14s	70ms
60kB	Yes	64.5MB	17s	50ms
256kB	No	63.8MB	16.5s	40ms
256kB	Yes	54.7MB	17.5s	40ms
1MB	No	54.7MB	16s	32ms
1MB	Yes	52.3MB	16.5s	32ms

Merging is always fast, because in this case we copy the compressed data directly. It looks like the relative inefficiency of the preset dictionary decreases as the block size increases, but I still worry that preset dictionaries would be challenging to integrate while still copying compressed data when merging as we can only do it if blocks use the same dictionary?

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

+1 to simply switch to bigger default block size (256 KB seems good) for now.  At least for this particular corpus, the reduction is massive (~33%).

It would be nice if we could auto-adapt the block size based on how compressible the stored fields really are, dynamically tuning the index size vs CPU cost of doc retrieval, but that can come later.

But, do we have any benchmarks that measure the CPU impact to retrieving stored fields?  That is the downside of compressing bigger blocks, right?  Higher per-hit decode cost (if the hit is in a new block).

E.g. Lucene's facet implementation relies on this, since resolving its int ordinals to human friendly facet labels is done by loading a document for each ordinal.  @gautamworah96 is working on switching to doc values in #10490 to reduce this cost.

Sharing the compression dictionary across blocks would be amazing, but that is surely complex, and would indeed likely reduce how often we could bulk-copy compressed blocks during merging.  But, maybe that is OK?  Increasing indexing cost in order to get a smaller index is often a good tradeoff?  Does zlib maybe support merging dictionaries / quickly re-writing a previously compressed output based on a new dictionary?  Maybe we (later!) could switch to a different implementation that would offer such "expert" APIs?

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

Indeed larger blocks make retrieval slower. I left the idea of using preset dictionaries out for now and did more tests. In particular I played with the idea of compressing with DEFLATE on top of LZ4 or LZ4 on top of LZ4. Because LZ4 only replaces duplicate strings with references, compressing multiple times with it helps bring some strings closer to each other, which sometimes mean they would now be closer than the window size (32kB for DEFLATE, 64kB for LZ4). This blog post talks a bit more about this idea and here are data points on the same dataset as previously. LZ4H means the high-compression mode of LZ4, which does more work to find longer duplicate strings.

 

Method	Index size(MB)	Index time(s)	Avg fetch time (us)
LZ4(16kB) (BEST_SPEED)	304,2	9	5
LZ4(60kB)	141,7	7,5	10
LZ4H+LZ4(60kB)	120,1	16,5	9
LZ4H(60kB)	120,1	15	8
LZ4H+LZ4+HUFFMAN_ONLY(60kB)	105,8	19	25
LZ4H+HUFFMAN_ONLY(60kB)	105,7	16,5	23
LZ4(256kB)	105,1	7,5	33
LZ4H+DEFLATE(60kB)	102,7	17,5	26
DEFLATE(60kB) (BEST_COMPRESSION)	100,6	14	35
LZ4(1MB)	96,5	7,5	115
LZ4H(256kB)	68,4	14,5	22
LZ4H+LZ4(256kB)	64,6	15	29
DEFLATE(256kB)	63,8	16,5	110
LZ4H+HUFFMAN_ONLY(256kB)	59,1	15	54
LZ4H+LZ4+HUFFMAN_ONLY(256kB)	57,7	15,5	58
LZ4H(1MB)	56,1	16,5	76
DEFLATE(1MB)	54,7	16	411
LZ4H+DEFLATE(256kB)	54,5	15,5	57
LZ4H+LZ4(1MB)	49,4	17	117
LZ4H+HUFFMAN_ONLY(1MB)	47,9	17.5	170
LZ4H+LZ4+HUFFMAN_ONLY(1MB)	44,6	18	194
LZ4H+DEFLATE(1MB)	40,8	18,5	172

Unfortunately, I get very different numbers for enwiki documents, which are less redundant and where Huffman compression is an important part of the compression ratio of DEFLATE, which makes DEFLATE alone unbeatable.

Method	Index size(MB)	Index time(s)	Avg fetch time (us)
LZ4(16kB) (BEST_SPEED)	558,8	14,5	83
LZ4(60kB)	526,2	15	120
LZ4(256kB)	523,1	15	323
LZ4(1MB)	521,3	15,5	1151
LZ4H+LZ4(60kB)	425,4	37	115
LZ4H(60kB)	424,2	32	112
LZ4H+LZ4(256kB)	397,5	49	267
LZ4H(256kB)	396,4	43	267
LZ4H+LZ4(1MB)	390,9	64	875
LZ4H(1MB)	389,8	61	887
LZ4H+HUFFMAN_ONLY(60kB)	377,6	35	240
LZ4H+DEFLATE(60kB)	376,5	41	228
LZ4H+HUFFMAN_ONLY(256kB)	357,1	45	668
LZ4H+DEFLATE(256kB)	356,7	53	694
LZ4H+HUFFMAN_ONLY(1MB)	352,3	65	2350
LZ4H+DEFLATE(1MB)	352,1	73	2460
DEFLATE(60kB) (BEST_COMPRESSION)	338,1	34	237
DEFLATE(256kB)	328,5	37	732
DEFLATE(1MB)	326,3	39	2624

Based on this data I think that Mike's suggestion to increase the block size to 256kB is a safe trade-off. I wonder whether we should also increase the block size for CompressionMode.BEST_SPEED to 64kB.

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

I opened a pull request with these changes: apache/lucene-solr#1748.

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

but I still worry that preset dictionaries would be challenging to integrate while still copying compressed data when merging as we can only do it if blocks use the same dictionary?

Yes, it probably needs total redesign/thought. The copying of compressed data is really important so that merge isn't horrible...

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

I've been playing more with the idea of preset dictionaries and found some combinations that are providing interesting results. In order to preserve bulk merging I'm still splitting data into blocks the same way as today, but then I have sub blocks too where the first one is compressed on its own and serves as a preset dictionary for all other sub blocks.

On the same dataset I've been using in previous comments:

Block size	Size of first sub-block	Size of other sub blocks	Index size(MB)	Index time(s)	Avg fetch time (us)
256kB	8kB	48kB	70,1	14,5	36
1MB	8kB	48kB	62,5	14	42

One benefit of this approach is that increasing the overall block size no longer hurts fetch times too much because we can usually skip decompressing most sub blocks. And it improves compression ratios since all sub blocks but the first one start with an ok preset dictionary. As Robert noted, setting preset dictionaries is costly, which is why I'm using a preset dictionary of 8kB, which seems to be a good trade-off between index-time overhead and compression ratios.

I find it generally better than both the current approach (DEFLATE with blocks of 60kB) and the new one I was considering (DEFLATE with blocks of 256kB) which is promising, so I'll look into cleaning up the very hacky patch I wrote to test this.

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

I opened a pull request, with this new approach. There is a lot of changed lines due to the ceremony of introducing a codec/format and moving the old one to backward-codecs, but you can really focus on the new Lucene87StoredFieldsFormat class to see what the patch does: it splits stored fields into blocks that contain an 8kB dictionary that is compressed on its own plus 10 sub blocks of 48kB each (so 488kB in total). Here is how it compares with the current codec for BEST_COMPRESSION on the JSON logs I used for testing in previous comments and a subset of enwiki docs:

Dataset	Method	Index size(MB)	Index time(s)	Avg fetch time (us)
JSON logs	Lucene50StoredFieldsFormat/BEST_COMPRESSION	100.6	14	35
JSON logs	Lucene87StoredFieldsFormat/BEST_COMPRESSION	64.9	14	41
enwiki	Lucene50StoredFieldsFormat/BEST_COMPRESSION	338.1	34	237
enwiki	Lucene87StoredFieldsFormat/BEST_COMPRESSION	338.0	35	250

So in short it doesn't make things worse on text data like enwiki but makes the compression ratio much better on highly compressible data while preserving similar indexing and fetching times.

Similar approaches might be interesting to look into for BEST_SPEED (preset dictionaries would be easy to support with LZ4) but I'd rather explore this separately.

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

+1 for this approach: we stop leaving so much compression ratio on the table, but the bulk merge still works so that performance isn't bad. I agree, let's explore this for LZ4 as a followup too: maybe with some different parameters/tradeoffs it can give a big boost to the default format without adding overhead.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 913976d in lucene-solr's branch refs/heads/master from Adrien Grand
https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=913976d

LUCENE-9447: Make BEST_COMPRESSION better with highly compressible data. (#1762)

This makes BEST_COMPRESSION split blocks into sub blocks and use preset
dictionaries to improve compression ratios.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 97cbb3d in lucene-solr's branch refs/heads/branch_8x from Adrien Grand
https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=97cbb3d

LUCENE-9447: Make BEST_COMPRESSION better with highly compressible data. (#1762)

This makes BEST_COMPRESSION split blocks into sub blocks and use preset
dictionaries to improve compression ratios.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 741251b in lucene-solr's branch refs/heads/master from Adrien Grand
https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=741251b

LUCENE-9447: Fix test failure.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 4787042 in lucene-solr's branch refs/heads/master from Simon Willnauer
https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=4787042

LUCENE-9447: suppress DeflateWithPresetCompressingStoredFieldsData since it doesn't add any attributes

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit f525262 in lucene-solr's branch refs/heads/branch_8x from Simon Willnauer
https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=f525262

LUCENE-9447: suppress DeflateWithPresetCompressingStoredFieldsData since it doesn't add any attributes