[
https://issues.apache.org/jira/browse/LUCENE-9877?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17309746#comment-17309746
]
Greg Miller commented on LUCENE-9877:
-------------------------------------
Out of curiosity, I compared using zero exceptions (so essentially just vanilla
FOR instead of PFOR) in place of the 3 exceptions used today. I thought this
might provide a good reference of the gains we get from PFOR in general. I'm
still using "-source wikimedium10m" for this.
For starters, overall index size grew from ~3.82GB to ~3.88GB (~1.6% increase).
{code:java}
3816536
wikimedium10m.baseline.facets.taxonomy:Date.taxonomy:Month.taxonomy:DayOfYear.sortedset:Month.sortedset:DayOfYear.Lucene90.Lucene90.nd10M
3877028
wikimedium10m.candidate.facets.taxonomy:Date.taxonomy:Month.taxonomy:DayOfYear.sortedset:Month.sortedset:DayOfYear.Lucene90.Lucene90.nd10M
{code}
Digging into the PFOR blocks, it looks like they grew from ~235MB to ~279MB
(~16% increase). I'm only showing the histogram for the zero exception
candidate here. The baseline (standard 3 exceptions) is identical to the above
test.
{code:java}
PFOR BPV Histogram
0 *** [4.02 %] (239453 of
5959788)
1 ** [2.78 %] (165409 of
5959788)
2 ************************** [51.98 %] (3097737 of
5959788)
3 ***************** [32.61 %] (1943685 of
5959788)
4 **** [7.06 %] (420552 of
5959788)
5 * [1.49 %] (88700 of
5959788)
6 * [0.07 %] (4097 of
5959788)
7 * [0.00 %] (153 of 5959788)
8 * [0.00 %] (2 of 5959788)
9 [0.00 %] (0 of 5959788)
10 [0.00 %] (0 of 5959788)
11 [0.00 %] (0 of 5959788)
12 [0.00 %] (0 of 5959788)
13 [0.00 %] (0 of 5959788)
14 [0.00 %] (0 of 5959788)
15 [0.00 %] (0 of 5959788)
16 [0.00 %] (0 of 5959788)
17 [0.00 %] (0 of 5959788)
18 [0.00 %] (0 of 5959788)
19 [0.00 %] (0 of 5959788)
20 [0.00 %] (0 of 5959788)
21 [0.00 %] (0 of 5959788)
22 [0.00 %] (0 of 5959788)
23 [0.00 %] (0 of 5959788)
24 [0.00 %] (0 of 5959788)
25 [0.00 %] (0 of 5959788)
26 [0.00 %] (0 of 5959788)
27 [0.00 %] (0 of 5959788)
28 [0.00 %] (0 of 5959788)
29 [0.00 %] (0 of 5959788)
30 [0.00 %] (0 of 5959788)
31 [0.00 %] (0 of 5959788)
Total bytes used: 234757569
PFOR Exceptions Used Histogram
0 ************************** [51.83 %] (3088921 of
5959788)
1 ************ [22.78 %] (1357732 of
5959788)
2 ******** [14.63 %] (872061 of
5959788)
3 ****** [10.76 %] (641074 of
5959788)
{code}
Finally, the QPS impact is as follows:
{code:java}
TaskQPS baseline StdDevQPS pfor 0 exceptions
StdDev Pct diff p-value
Wildcard 77.24 (2.5%) 75.83 (4.6%)
-1.8% ( -8% - 5%) 0.118
HighSloppyPhrase 16.79 (3.0%) 16.51 (2.8%)
-1.7% ( -7% - 4%) 0.067
BrowseDateTaxoFacets 4.28 (4.6%) 4.21 (4.4%)
-1.6% ( -10% - 7%) 0.258
BrowseDayOfYearTaxoFacets 4.28 (4.6%) 4.22 (4.4%)
-1.6% ( -10% - 7%) 0.258
Prefix3 265.10 (1.8%) 260.93 (4.2%)
-1.6% ( -7% - 4%) 0.121
BrowseMonthTaxoFacets 5.03 (4.8%) 4.97 (4.5%)
-1.2% ( -9% - 8%) 0.414
Fuzzy2 58.97 (9.9%) 58.32 (11.0%)
-1.1% ( -20% - 22%) 0.740
OrHighLow 349.19 (5.8%) 346.12 (5.4%)
-0.9% ( -11% - 10%) 0.621
HighPhrase 240.19 (2.5%) 238.10 (3.6%)
-0.9% ( -6% - 5%) 0.367
LowTerm 1168.47 (3.7%) 1160.33 (3.1%)
-0.7% ( -7% - 6%) 0.516
OrHighNotHigh 533.28 (4.5%) 529.68 (4.8%)
-0.7% ( -9% - 8%) 0.645
LowSloppyPhrase 68.08 (2.7%) 67.62 (2.5%)
-0.7% ( -5% - 4%) 0.411
PKLookup 143.84 (2.8%) 142.97 (2.4%)
-0.6% ( -5% - 4%) 0.463
OrHighNotLow 606.15 (4.9%) 603.42 (5.9%)
-0.5% ( -10% - 10%) 0.791
Respell 48.93 (3.0%) 48.77 (3.0%)
-0.3% ( -6% - 5%) 0.722
OrNotHighHigh 714.82 (4.0%) 712.45 (2.6%)
-0.3% ( -6% - 6%) 0.754
MedSloppyPhrase 30.21 (3.1%) 30.11 (2.8%)
-0.3% ( -6% - 5%) 0.735
IntNRQ 189.36 (1.0%) 188.79 (0.9%)
-0.3% ( -2% - 1%) 0.317
HighIntervalsOrdered 2.85 (1.3%) 2.84 (1.7%)
-0.3% ( -3% - 2%) 0.563
AndHighLow 478.02 (3.8%) 477.52 (3.2%)
-0.1% ( -6% - 7%) 0.925
MedPhrase 371.46 (3.0%) 371.40 (3.4%)
-0.0% ( -6% - 6%) 0.987
OrNotHighLow 607.51 (3.9%) 607.79 (3.7%)
0.0% ( -7% - 7%) 0.969
OrHighHigh 19.26 (2.5%) 19.27 (2.6%)
0.1% ( -4% - 5%) 0.946
Fuzzy1 25.07 (3.7%) 25.13 (3.0%)
0.2% ( -6% - 7%) 0.835
OrNotHighMed 545.21 (4.1%) 546.86 (4.7%)
0.3% ( -8% - 9%) 0.829
HighTerm 849.08 (5.0%) 851.94 (4.9%)
0.3% ( -9% - 10%) 0.829
AndHighHigh 53.75 (3.2%) 53.94 (3.1%)
0.3% ( -5% - 6%) 0.728
OrHighNotMed 526.63 (3.9%) 529.57 (5.5%)
0.6% ( -8% - 10%) 0.711
HighTermDayOfYearSort 48.21 (12.6%) 48.64 (13.8%)
0.9% ( -22% - 31%) 0.832
MedTerm 887.00 (3.5%) 895.23 (3.1%)
0.9% ( -5% - 7%) 0.371
OrHighMed 127.09 (3.8%) 128.36 (3.2%)
1.0% ( -5% - 8%) 0.368
BrowseMonthSSDVFacets 12.41 (6.1%) 12.54 (3.5%)
1.1% ( -8% - 11%) 0.489
AndHighMed 207.20 (3.4%) 209.48 (2.9%)
1.1% ( -5% - 7%) 0.269
LowSpanNear 37.88 (1.5%) 38.31 (2.3%)
1.1% ( -2% - 4%) 0.062
LowPhrase 319.03 (3.0%) 322.98 (2.5%)
1.2% ( -4% - 6%) 0.153
HighSpanNear 2.48 (2.3%) 2.52 (1.7%)
1.5% ( -2% - 5%) 0.021
HighTermMonthSort 99.17 (11.3%) 100.72 (11.6%)
1.6% ( -19% - 27%) 0.666
BrowseDayOfYearSSDVFacets 11.44 (5.0%) 11.65 (6.4%)
1.8% ( -9% - 13%) 0.327
TermDTSort 113.75 (10.1%) 116.35 (10.6%)
2.3% ( -16% - 25%) 0.484
HighTermTitleBDVSort 119.18 (13.1%) 123.29 (18.2%)
3.4% ( -24% - 40%) 0.493
MedSpanNear 152.90 (2.3%) 160.02 (5.4%)
4.7% ( -3% - 12%) 0.000
{code}
So in the case of replacing FOR with PFOR (or comparing 0 exceptions to 3), we
seem to get ~16% savings in the blocks themselves, which translates to ~1.6%
savings in overall index size. To do so, there is a bit of a negative impact to
QPS, as shown above.
*With this in mind, it seems very reasonable to me to increase from 3
exceptions to 7 exceptions.* Going from 3 to 7 will get us another ~7.6%
savings in the blocks, translating to another ~0.5% overall index size savings.
Better yet, I don't see any significant impact to QPS in the benchmarks. As an
added bonus, the change is fully backwards compatible since we still use the
same 3 bits to encode the number of exceptions, and the decoding logic in PFOR
util will handle 7 exceptions out-of-the-box. What do folks think? Is there a
good reason to *not* move from 3 to 7 exceptions?
> Explore increasing the allowable exceptions in PForUtil
> -------------------------------------------------------
>
> Key: LUCENE-9877
> URL: https://issues.apache.org/jira/browse/LUCENE-9877
> Project: Lucene - Core
> Issue Type: Task
> Components: core/codecs
> Affects Versions: main (9.0)
> Reporter: Greg Miller
> Priority: Minor
>
> Piggybacking a little off of the investigation I was doing over in
> LUCENE-9850 I thought it might also be worth-while exploring the impact of
> increasing the number of allowable exceptions in PForUtil. The aim of this
> investigation is to see if we could reduce index size by allowing for more
> exceptions without significant negative impact to performance.
> PForUtil currently allows for up to 3 exceptions, and it only uses 3 bits to
> encode the number of exceptions (using the remaining 3 bits of the byte used
> to also encode the number of bits-per-value, which requires 5 bits). Each
> exception used is encoded with a two full bytes, using a maximum of 6 bytes
> per block.
> It seems to me like 7 might be a more ideal number of exceptions if index
> size is the driving motivation. My thought process is that, in the
> worst-case, 7 exceptions would be used to save only a single bit-per-value in
> the corresponding block. With 128 entries per block, this would save 16
> bytes. So with 14 bytes used to encode the exception values (7 x 2 bytes per
> exception), we would save a two bytes in total (just slightly better than
> breaking even). If we need fewer than the 7 exceptions, or if we're able to
> save more than 1 bit-per-value, it's all additional savings. I suppose the
> question is what kind of performance hit we might observe due to decoding
> more exceptions.
> Also note that 7 exceptions is the max we can encode with the 3 bits we
> currently have available for the number of exceptions. So moving to 8
> exceptions would not only take 16 bytes to encode the exceptions (if using
> all of them), but we'd need one more byte per block to encode the exception
> count. So in the worst case of using all 8 exceptions to save 1 bit per
> value, we'd actually be worse off.
> I'll post some results here for discussion or at least for public record of
> my work for future reference.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
