shbhar opened a new pull request, #16859:
URL: https://github.com/apache/lucene/pull/16859
## Summary
I work in Amazon advertising, where we have some low latency use cases for
exact primary key ID lookups as part of other querying. For many types of IDs
like UUIDs or ASINs which are mostly random and dont share prefixes/suffixes,
standard block tree based lookup within `TermQuery` or `TermInSetQuery` pays
extra overhead over just a normal hash table without the benefits, so in this
POC I tried to make `PrimaryKeyHashPostingsFormat` as a wrapper format (similar
to `BloomFilteringPostingsFormat` design) where `prepareSeekExact`/`seekExact`
goes through a hash table path instead of the wrapped one (default of
Lucene104PostingsFormat with block tree), but all other behavior like for
seekCeil, prefix query, etc is still delegated.
A quick summary of results for UUID16 ids is below and full details with
more ids are later. The UUID16 & batch querying are new tasks I added for this
work in luceneutil. Bloom is the `BloomFilteringPostingsFormat` wrapped over
default.
| luceneutil task (wikimedium10m, 15 segments, uuid16 IDs) | host | QPS
default | QPS Bloom | QPS PrimaryKeyHash | Bloom vs default | PrimaryKeyHash vs
default |
|---|---|---|---|---|---|---|
| PKLookup (4,000 IDs per task) | c8g.4xlarge | 116.6 | 193.6 | 618.2 |
+65.7% | +425.9% |
| | c8i.4xlarge | 156.1 | 294.4 | 896.6 | +89.3% | +474.4% |
| PKLookupBatch (the same 4,000 IDs as one query: TermInSetQuery /
PrimaryKeyHashInSetQuery) | c8g.4xlarge | 62.2 | 58.5 | 821.2 | -5.2% |
+1220.2% |
| | c8i.4xlarge | 76.2 | 75.0 | 1,182.4 | -1.7% | +1454.2% |
| Index size | | 4.88 GB | 4.89 GB | 5.17 GB | +0.21% | +5.97% |
## Key Design Details
### Hash Table Design
This is mostly a typical open adressing hash table design (1 hash table per
segment per field) with the records/control bytes and linear probing. The
lucene specific twists are that the table is also partitioned to control memory
usage during writes/merges and it has an integrated bloom filter to make misses
a lot cheaper with multiple segments. Miss performance is quite important
because in realistic indexes with many segments, most lookups will be misses
even if the key is in the index.
The record layout is of two types mentioned below and since we know all the
keys at hash table construction time, we choose the appropriate one per segment.
Note: ASCII diagram below generated with AI but looks correct to me
> ```
> Inline layout (all keys of the field have one length L <= 31): a hit = 2
dependent reads
>
> slot: 8 9 10 11 12 13 14 15
> control bytes: [a9] [ba] [a7] [ab] [00] [f8] [ff] [cb]
1 byte per slot, 8 read at once
> | | | | | | | |
> records: [LHR] [LAX] [HKG] [NRT] [ 0 ] [ORD] [ZRH] [YYZ]
record i belongs to slot i
> DocID(32 bits) | key bytes (8 x L bits)
position = slot x (4 + L)
>
>
---------------------------------------------------------------------------------------------------------------------
> Term-order layout (variable lengths, or L > 31): a hit = 3
dependent reads
>
> control bytes: [a9] [ba] [a7] ...
1 byte per slot
> slot words: [ptr|dist|tag] [ptr|dist|tag] ...
8 bytes per slot (0 = empty)
> \ \
> records (sorted): [DocID | len (VInt) | key bytes][DocID | len | key
bytes] ... back to back, in term order
>
> control byte: 0x00 = empty slot (ends a miss); else 0x80 | 7 fingerprint
bits of the hash
> ```
The extra complexity of these 2 layouts is to optimize for what I assume is
the most common case of primary key which are fixed length and <=31 bytes. In
benchmarks for index of 10 million UUID16 keys across 15 segments, single key
hits were almost 25-40% faster on both graviton & intel hosts with inline
layout compared to term order layout so I think it is worth it.
### Hash Function and bit distribution
The current implementation uses a ported XXHash3-64 implementation instead
of the Murmur3 implementation already in Lucene, since in benchmarks it is 2-3
times faster for hashing alone on 16 byte keys, and hashing speed/throughput is
very important in this design.
Below table shows how the 64-bit hash is used (from the top bit; PB =
partition bits, 0-10 depending on the number of keys):
| bits of h | width | use |
|---|---|---|
| 63 … 64-PB | PB (0-10) | partition |
| 63-PB … 33-PB | 31 | home slot |
| 32-PB … 23 | 10-PB | unused |
| 22 … 16 | 7 | control byte = `0x80 \| these 7 bits` |
| 15 … 0 | 16 | tag in the slot word (used for term-order layout only) |
### Batch key lookups
This is the TermInSetQuery replacement for this use case since the
underlying implementation would use seekCeil and therefore not the hash table
implementation. It sorts, dedupes and then hashes the keys but then works on 32
key chunks in stages (bloom filter, control batch then record batch) and not
one by one to exploit hardware's memory level parallelism by having multiple
reads in flight. This staged & batched implementation was 2-5x faster for 4096
batch lookups vs one at a time for the same depending on key lengths and number
of segments (faster when there are more segments and more misses)
### Bloom filtering
Similar to bloom filtering postings format but integated into this format
directly to quickly reject (key, segment) pairs that definitely dont exist than
what would be possible with control bytes alone because there is no
slot/probing etc cost for bloom filter. This variation is a [register blocked
bloom filter](https://dl.acm.org/doi/abs/10.14778/3303753.3303757) which trades
more false positive rate at the same bits for fewer reads (exactly 1) compared
to a classic bloom filter, which is important because it has to be much cheaper
than checking the control bytes itself otherwise it wont be useful. While it
adds 10 bits per key, it was 2-3x faster than without it on batched key lookups
(4096 batch) and 15 segment index of uuid16 keys.
### Index writing
Hash tables are only built at flush and merge, and for merge we rebuild from
scratch. We partition hash tables (upto 1024 default) to control the memory
requirements during build (writers make the table one partition at a time) and
that way it is bounded by the largest partition.
## Results
### Index size & Indexing time
Since this is a wrapper format, we do expect increase in indexing time and
index size, but the assumption is that ID fields would usually be a small part
of the index and the size/time would be dominated by other fields.
ID field size (id-only index, 10M docs, bytes per document). Bloom means the
bloom filtering format wrapping default.
| key shape | layout | default | Bloom | PrimaryKeyHash (10-bit filter) |
PrimaryKeyHash / default |
|---|---|---|---|---|---|
| seq6 (6-byte sequential) from luceneutil's PKLookup | inline | 2.58 | 3.39
| 18.49 | 7.2x |
| asin (10-byte) | inline | 9.35 | 10.22 | 30.60 | 3.3x |
| uuid16 (16-byte binary) | inline | 18.46 | 19.28 | 47.71 | 2.6x |
| uuid36 (36-char string) | term order | 28.41 | 29.28 | 82.66 | 2.9x |
Whole index, luceneutil wikimedium10m: +3.45% with its sequential IDs
(+157.8 MB; Bloom +0.22%), +5.97% with uuid16 IDs (+291.4 MB; Bloom +0.21%),
+10.48% with uuid36 IDs (+541.5 MB; Bloom +0.20%). A 50M uuid16 field's hash
data is 1.46 GB.
ID-only index build time (worst case: the documents have nothing but the ID):
| index | host | default | Bloom | PrimaryKeyHash | PrimaryKeyHash / default
|
|---|---|---|---|---|---|
| uuid16 50M, 2 segments | c8g | 63.0 / 66.5 s | 78.5 s | 88.4 / 89.1 s |
1.34-1.40 |
| uuid16 10M, 15 flushes | c8g | 9.11 / 9.21 s | 10.65 s | 13.70 / 13.65 s |
1.48-1.50 |
| uuid16 10M, 15 flushes | c8i | 7.07 / 7.03 s | 7.95 s | 10.63 / 10.62 s |
1.50-1.51 |
| seq6 10M, 15 flushes | c8g | 7.27 / 7.70 s | 10.50 s | 8.84 / 9.11 s |
1.18-1.22 |
| asin 10M, 1 segment | c8g | 13.23 s | 14.72 s | 15.86 s | 1.20 |
| asin 10M, 1 segment | c8i | 9.89 s | 11.86 s | 12.78 s | 1.29 |
| uuid36 string 10M, 1 segment | c8g | 19.77 s | 23.05 s | 27.25 s | 1.38 |
luceneutil full indexing (whole documents, one sample each): 836.2 -> 877.4
s (+4.9%) on c8g.24xlarge; 1,043.4 -> 983.4 s
(-5.8%) on c8g.4xlarge, so within noise.
### LuceneUtil
#### PKLookup wikimedium10m
wikimedium10m, 15 segments, 20 JVMs per comparison. `pkhash` is the run
label for PrimaryKeyHashPostingsFormat.
c8g (c8g.24xlarge, Graviton4), PK tasks only, 3 independent runs:
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
<b> PKLookup 625.29 (0.2%) 2014.47
(14.1%) 222.2% ( 207% - 237%) 0.000</b>
<b> PKLookup 621.49 (0.4%) 2111.25
(6.1%) 239.7% ( 232% - 247%) 0.000</b>
<b> PKLookup 623.17 (0.5%) 2078.62
(12.8%) 233.6% ( 219% - 248%) 0.000</b>
</pre>
c8g.4xlarge, PK tasks only (default vs pkhash, then default vs Bloom):
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
<b> PKLookup 430.76 (0.6%) 903.18
(9.4%) 109.7% ( 99% - 120%) 0.000</b>
</pre>
<pre>
Task QPS default StdDev QPS bloom
StdDev Pct diff p-value
<b> PKLookup 431.69 (0.6%) 228.25
(0.4%) -47.1% ( -47% - -46%) 0.000</b>
</pre>
c8g.4xlarge, full task set (PKLookup mixed with the other tasks):
<details><summary>all tasks</summary>
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
BrowseMonthTaxoFacets 41.20 (5.7%) 40.63
(6.4%) -1.4% ( -12% - 11%) 0.461
OrHighNotMed 856.31 (7.9%) 845.76
(8.7%) -1.2% ( -16% - 16%) 0.640
OrHighNotLow 809.99 (8.4%) 800.16
(9.6%) -1.2% ( -17% - 18%) 0.671
range 8044.27 (2.8%) 7956.12
(3.3%) -1.1% ( -6% - 5%) 0.257
OrHighNotHigh 711.81 (7.4%) 704.23
(8.3%) -1.1% ( -15% - 15%) 0.668
BM25MSM2 12.74 (2.9%) 12.63
(2.1%) -0.9% ( -5% - 4%) 0.258
OrNotHighHigh 619.51 (6.9%) 614.11
(7.7%) -0.9% ( -14% - 14%) 0.705
BrowseMonthSSDVFacets 19.25 (5.9%) 19.09
(6.2%) -0.8% ( -12% - 11%) 0.668
BrowseDayOfYearSSDVFacets 19.48 (8.8%) 19.34
(9.1%) -0.7% ( -17% - 18%) 0.797
HighPhrase 24.07 (1.3%) 23.94
(2.5%) -0.6% ( -4% - 3%) 0.377
BrowseRandomLabelTaxoFacets 16.27 (2.4%) 16.18
(2.4%) -0.5% ( -5% - 4%) 0.487
HighTerm 1231.46 (4.9%) 1225.32
(4.3%) -0.5% ( -9% - 9%) 0.732
OrNotHighMed 594.01 (4.2%) 591.41
(4.6%) -0.4% ( -8% - 8%) 0.753
LowTerm 2097.85 (3.1%) 2089.36
(2.9%) -0.4% ( -6% - 5%) 0.670
HighTermTitleBDVSort 25.67 (0.8%) 25.57
(1.2%) -0.4% ( -2% - 1%) 0.236
AndHighLow 2012.08 (1.8%) 2004.66
(2.0%) -0.4% ( -4% - 3%) 0.541
OrHighLow 1150.17 (1.3%) 1146.29
(1.5%) -0.3% ( -3% - 2%) 0.440
AndHighMedDayTaxoFacets 88.14 (0.8%) 87.85
(1.0%) -0.3% ( -2% - 1%) 0.260
BrowseDayOfYearTaxoFacets 18.80 (1.8%) 18.74
(1.9%) -0.3% ( -3% - 3%) 0.595
Fuzzy2 100.53 (1.1%) 100.22
(1.1%) -0.3% ( -2% - 1%) 0.397
OrHighMed 422.30 (1.4%) 421.02
(1.4%) -0.3% ( -3% - 2%) 0.495
OrNotHighLow 1296.88 (1.3%) 1293.09
(1.5%) -0.3% ( -3% - 2%) 0.506
BrowseDateTaxoFacets 18.61 (1.7%) 18.55
(1.9%) -0.3% ( -3% - 3%) 0.619
IntSet 658.86 (3.1%) 656.99
(3.2%) -0.3% ( -6% - 6%) 0.778
Fuzzy1 116.09 (1.1%) 115.80
(1.2%) -0.2% ( -2% - 2%) 0.496
MedPhrase 131.10 (1.2%) 130.81
(2.1%) -0.2% ( -3% - 3%) 0.672
OrHighHigh 167.85 (3.0%) 167.47
(2.7%) -0.2% ( -5% - 5%) 0.804
AndHighHighDayTaxoFacets 18.29 (0.7%) 18.25
(0.8%) -0.2% ( -1% - 1%) 0.384
HighTermMonthSort 3561.67 (1.9%) 3556.29
(2.0%) -0.2% ( -3% - 3%) 0.805
LowPhrase 129.10 (1.7%) 128.91
(2.0%) -0.1% ( -3% - 3%) 0.809
MedTerm 1503.10 (4.0%) 1501.77
(3.5%) -0.1% ( -7% - 7%) 0.941
AndHighMed 405.74 (1.4%) 405.46
(1.3%) -0.1% ( -2% - 2%) 0.872
TermDTSort 413.20 (0.9%) 412.98
(1.3%) -0.1% ( -2% - 2%) 0.883
ConstMSM2 2224.17 (1.4%) 2222.98
(1.9%) -0.1% ( -3% - 3%) 0.919
BrowseDateSSDVFacets 3.67 (0.7%) 3.67
(0.7%) -0.0% ( -1% - 1%) 0.824
AndHighHigh 162.24 (1.9%) 162.24
(1.9%) -0.0% ( -3% - 3%) 0.999
MustNotIODVRange 317.75 (1.7%) 317.76
(1.8%) 0.0% ( -3% - 3%) 0.993
IntNRQ 147.11 (2.0%) 147.14
(2.2%) 0.0% ( -4% - 4%) 0.974
LowSloppyPhrase 45.14 (1.2%) 45.15
(1.3%) 0.0% ( -2% - 2%) 0.945
MedTermDayTaxoFacets 72.75 (3.1%) 72.88
(3.0%) 0.2% ( -5% - 6%) 0.863
MedSloppyPhrase 37.44 (1.3%) 37.51
(1.5%) 0.2% ( -2% - 3%) 0.696
HighTermDayOfYearSort 599.42 (1.8%) 600.53
(2.0%) 0.2% ( -3% - 4%) 0.756
MedSpanNear 39.51 (2.2%) 39.59
(2.5%) 0.2% ( -4% - 5%) 0.771
HighSpanNear 8.80 (4.8%) 8.82
(5.1%) 0.3% ( -9% - 10%) 0.866
LowIntervalsOrdered 51.97 (1.4%) 52.12
(1.3%) 0.3% ( -2% - 3%) 0.496
LowSpanNear 43.50 (1.8%) 43.63
(1.9%) 0.3% ( -3% - 4%) 0.619
MedIntervalsOrdered 50.72 (1.5%) 50.89
(1.3%) 0.3% ( -2% - 3%) 0.451
HighSloppyPhrase 21.10 (1.4%) 21.19
(1.7%) 0.4% ( -2% - 3%) 0.421
OrHighMedDayTaxoFacets 17.93 (2.2%) 18.01
(2.1%) 0.5% ( -3% - 4%) 0.505
HighIntervalsOrdered 23.27 (1.7%) 23.38
(1.3%) 0.5% ( -2% - 3%) 0.312
HighTermTitleSort 193.53 (2.3%) 194.57
(2.1%) 0.5% ( -3% - 5%) 0.445
Respell 94.77 (1.6%) 95.29
(1.4%) 0.5% ( -2% - 3%) 0.259
AndMissingHigh 4917.06 (4.7%) 4953.71
(5.9%) 0.7% ( -9% - 11%) 0.659
Prefix3 464.76 (1.9%) 468.82
(1.3%) 0.9% ( -2% - 4%) 0.097
BrowseRandomLabelSSDVFacets 14.96 (10.0%) 15.09
(10.4%) 0.9% ( -17% - 23%) 0.781
<b> Wildcard 157.53 (1.8%) 159.33
(0.9%) 1.1% ( -1% - 3%) 0.011</b>
<b> PKLookup 451.26 (1.3%) 720.23
(1.7%) 59.6% ( 55% - 63%) 0.000</b>
</pre>
</details>
##### PKLookupBatch (sequential IDs)
PKLookupBatch: the same batches of 4,000 IDs (10% misses) as PKLookup, but
each batch is one query: TermInSetQuery for default and Bloom,
PrimaryKeyHashInSetQuery for PrimaryKeyHash (`pkhash`); 20 JVMs per comparison;
bold = p < 0.05. QPS is directly comparable with the PKLookup rows (same
batches, batches per second).
c8g.4xlarge (Graviton4)
default vs PrimaryKeyHash, 3 runs:
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
<b> PKLookupBatch 232.51 (2.9%) 1399.26
(22.2%) 501.8% ( 463% - 542%) 0.000</b>
<b> PKLookupBatch 242.56 (1.5%) 1500.53
(27.5%) 518.6% ( 482% - 556%) 0.000</b>
<b> PKLookupBatch 242.88 (3.8%) 1610.90
(96.8%) 563.2% ( 445% - 690%) 0.000</b>
</pre>
default vs Bloom, 3 runs:
<pre>
Task QPS default StdDev QPS bloom
StdDev Pct diff p-value
<b> PKLookupBatch 232.17 (2.2%) 226.05
(3.4%) -2.6% ( -8% - 3%) 0.004</b>
<b> PKLookupBatch 243.97 (2.6%) 236.64
(1.9%) -3.0% ( -7% - 1%) 0.000</b>
<b> PKLookupBatch 240.86 (2.8%) 235.61
(2.8%) -2.2% ( -7% - 3%) 0.014</b>
</pre>
c8i.4xlarge (Intel Xeon 6)
default vs PrimaryKeyHash, 3 runs:
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
<b> PKLookupBatch 267.56 (1.6%) 2083.17
(66.8%) 678.6% ( 600% - 758%) 0.000</b>
<b> PKLookupBatch 267.55 (1.5%) 2015.82
(73.1%) 653.4% ( 570% - 738%) 0.000</b>
<b> PKLookupBatch 267.80 (2.0%) 2196.34
(47.9%) 720.1% ( 657% - 785%) 0.000</b>
</pre>
default vs Bloom, 3 runs:
<pre>
Task QPS default StdDev QPS bloom
StdDev Pct diff p-value
<b> PKLookupBatch 267.67 (1.3%) 258.44
(1.8%) -3.4% ( -6% - 0%) 0.000</b>
<b> PKLookupBatch 270.43 (2.0%) 261.51
(1.6%) -3.3% ( -6% - 0%) 0.000</b>
<b> PKLookupBatch 268.06 (1.7%) 259.25
(1.6%) -3.3% ( -6% - 0%) 0.000</b>
</pre>
#### UUID 16
luceneutil PKLookup on wikimedium10m with `-idFormat uuid16` (quick
luceneutil addition for UUIDs as 16-byte binary terms); 20 JVMs per comparison
c8g.4xlarge (Graviton4)
default vs PrimaryKeyHash (`pkhash`), 3 runs:
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
<b> PKLookup 117.67 (2.0%) 618.81
(91.4%) 425.9% ( 325% - 530%) 0.000</b>
<b> PKLookup 116.59 (2.1%) 618.16
(100.7%) 430.2% ( 320% - 544%) 0.000</b>
<b> PKLookup 115.67 (2.7%) 516.70
(39.9%) 346.7% ( 295% - 400%) 0.000</b>
</pre>
default vs Bloom, 3 runs:
<pre>
Task QPS default StdDev QPS bloom
StdDev Pct diff p-value
<b> PKLookup 116.55 (2.3%) 197.31
(9.6%) 69.3% ( 56% - 83%) 0.000</b>
<b> PKLookup 116.88 (1.9%) 191.98
(8.4%) 64.2% ( 52% - 76%) 0.000</b>
<b> PKLookup 116.84 (2.1%) 193.58
(8.6%) 65.7% ( 53% - 77%) 0.000</b>
</pre>
c8i.4xlarge (Intel Xeon 6)
default vs PrimaryKeyHash (`pkhash`), 3 runs:
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
<b> PKLookup 156.49 (1.0%) 897.90
(12.4%) 473.8% ( 455% - 492%) 0.000</b>
<b> PKLookup 155.78 (1.0%) 896.25
(11.6%) 475.3% ( 458% - 492%) 0.000</b>
<b> PKLookup 156.10 (1.1%) 896.60
(12.5%) 474.4% ( 455% - 493%) 0.000</b>
</pre>
default vs Bloom, 3 runs:
<pre>
Task QPS default StdDev QPS bloom
StdDev Pct diff p-value
<b> PKLookup 155.51 (1.2%) 294.33
(2.1%) 89.3% ( 84% - 93%) 0.000</b>
<b> PKLookup 156.83 (0.8%) 295.25
(2.5%) 88.3% ( 84% - 92%) 0.000</b>
<b> PKLookup 155.30 (1.2%) 294.37
(2.4%) 89.5% ( 84% - 94%) 0.000</b>
</pre>
##### PKLookupBatch (uuid16)
PKLookupBatch: the same batches of 4,000 IDs (10% misses) as PKLookup, but
each batch is one query: TermInSetQuery for default and Bloom,
PrimaryKeyHashInSetQuery for PrimaryKeyHash (`pkhash`); 20 JVMs per comparison;
bold = p < 0.05. QPS is directly comparable with the PKLookup rows (same
batches, batches per second).
c8g.4xlarge (Graviton4)
default vs PrimaryKeyHash, 3 runs:
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
<b> PKLookupBatch 61.53 (0.8%) 802.91
(23.3%) 1205.0% (1171% - 1238%) 0.000</b>
<b> PKLookupBatch 62.20 (0.5%) 821.16
(25.5%) 1220.2% (1188% - 1252%) 0.000</b>
<b> PKLookupBatch 62.30 (0.9%) 827.13
(16.6%) 1227.7% (1199% - 1256%) 0.000</b>
</pre>
default vs Bloom, 3 runs:
<pre>
Task QPS default StdDev QPS bloom
StdDev Pct diff p-value
<b> PKLookupBatch 61.45 (1.8%) 58.54
(0.3%) -4.7% ( -6% - -2%) 0.000</b>
<b> PKLookupBatch 61.75 (0.7%) 58.51
(0.6%) -5.2% ( -6% - -3%) 0.000</b>
<b> PKLookupBatch 62.14 (0.8%) 58.77
(0.7%) -5.4% ( -6% - -3%) 0.000</b>
</pre>
c8i.4xlarge (Intel Xeon 6)
default vs PrimaryKeyHash, 3 runs:
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
<b> PKLookupBatch 76.16 (0.6%) 1179.73
(72.0%) 1449.1% (1368% - 1530%) 0.000</b>
<b> PKLookupBatch 76.08 (0.5%) 1182.43
(78.4%) 1454.2% (1368% - 1540%) 0.000</b>
<b> PKLookupBatch 76.46 (0.9%) 1192.71
(34.0%) 1459.9% (1412% - 1508%) 0.000</b>
</pre>
default vs Bloom, 3 runs:
<pre>
Task QPS default StdDev QPS bloom
StdDev Pct diff p-value
<b> PKLookupBatch 76.30 (0.7%) 75.03
(0.8%) -1.7% ( -3% - 0%) 0.000</b>
<b> PKLookupBatch 76.69 (0.5%) 75.55
(1.0%) -1.5% ( -2% - 0%) 0.000</b>
<b> PKLookupBatch 76.37 (0.6%) 74.94
(0.8%) -1.9% ( -3% - 0%) 0.000</b>
</pre>
#### UUID 36
luceneutil PKLookup on wikimedium10m with `-idFormat uuid36` (the same UUIDs
as 36-char strings); 20 JVMs per comparison; bold = p < 0.05.
c8g.4xlarge (Graviton4)
default vs PrimaryKeyHash (`pkhash`), 3 runs:
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
<b> PKLookup 69.09 (0.6%) 243.87
(4.5%) 253.0% ( 246% - 259%) 0.000</b>
<b> PKLookup 68.81 (0.3%) 245.08
(5.2%) 256.1% ( 249% - 262%) 0.000</b>
<b> PKLookup 68.98 (0.5%) 246.86
(5.2%) 257.9% ( 250% - 264%) 0.000</b>
</pre>
default vs Bloom, 3 runs:
<pre>
Task QPS default StdDev QPS bloom
StdDev Pct diff p-value
<b> PKLookup 68.87 (0.5%) 135.46
(1.1%) 96.7% ( 94% - 98%) 0.000</b>
<b> PKLookup 69.15 (0.3%) 136.33
(1.7%) 97.2% ( 94% - 99%) 0.000</b>
<b> PKLookup 68.66 (0.6%) 136.56
(1.9%) 98.9% ( 95% - 102%) 0.000</b>
</pre>
c8i.4xlarge (Intel Xeon 6)
default vs PrimaryKeyHash (`pkhash`), 3 runs:
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
<b> PKLookup 64.35 (1.3%) 561.23
(51.4%) 772.2% ( 710% - 835%) 0.000</b>
<b> PKLookup 64.60 (1.3%) 585.49
(45.6%) 806.4% ( 749% - 864%) 0.000</b>
<b> PKLookup 65.43 (4.1%) 610.29
(55.9%) 832.7% ( 741% - 931%) 0.000</b>
</pre>
default vs Bloom, 3 runs:
<pre>
Task QPS default StdDev QPS bloom
StdDev Pct diff p-value
<b> PKLookup 64.01 (1.3%) 150.43
(3.0%) 135.0% ( 129% - 141%) 0.000</b>
<b> PKLookup 64.26 (1.6%) 151.12
(3.7%) 135.2% ( 127% - 142%) 0.000</b>
<b> PKLookup 68.01 (4.5%) 170.25
(29.5%) 150.3% ( 111% - 192%) 0.000</b>
</pre>
##### PKLookupBatch (uuid36)
PKLookupBatch: the same batches of 4,000 IDs (10% misses) as PKLookup, but
each batch is one query: TermInSetQuery for default and Bloom,
PrimaryKeyHashInSetQuery for PrimaryKeyHash (`pkhash`); 20 JVMs per comparison;
bold = p < 0.05. QPS is directly comparable with the PKLookup rows (same
batches, batches per second).
c8g.4xlarge (Graviton4)
default vs PrimaryKeyHash, 3 runs:
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
<b> PKLookupBatch 34.34 (0.5%) 658.35
(30.7%) 1816.9% (1777% - 1856%) 0.000</b>
<b> PKLookupBatch 34.55 (0.6%) 668.98
(28.0%) 1836.0% (1796% - 1876%) 0.000</b>
<b> PKLookupBatch 34.71 (0.5%) 664.03
(42.5%) 1813.0% (1761% - 1865%) 0.000</b>
</pre>
default vs Bloom, 3 runs:
<pre>
Task QPS default StdDev QPS bloom
StdDev Pct diff p-value
<b> PKLookupBatch 34.56 (0.5%) 33.34
(0.4%) -3.5% ( -4% - -2%) 0.000</b>
<b> PKLookupBatch 34.55 (0.6%) 33.16
(0.6%) -4.0% ( -5% - -2%) 0.000</b>
<b> PKLookupBatch 34.80 (0.5%) 33.34
(0.6%) -4.2% ( -5% - -3%) 0.000</b>
</pre>
c8i.4xlarge (Intel Xeon 6)
default vs PrimaryKeyHash, 3 runs:
<pre>
Task QPS default StdDev QPS pkhash
StdDev Pct diff p-value
<b> PKLookupBatch 39.01 (1.5%) 1008.73
(39.8%) 2485.7% (2408% - 2564%) 0.000</b>
<b> PKLookupBatch 38.80 (1.4%) 1003.80
(44.2%) 2487.0% (2408% - 2567%) 0.000</b>
<b> PKLookupBatch 38.88 (1.3%) 1007.95
(38.6%) 2492.4% (2420% - 2566%) 0.000</b>
</pre>
default vs Bloom, 3 runs:
<pre>
Task QPS default StdDev QPS bloom
StdDev Pct diff p-value
<b> PKLookupBatch 39.15 (1.5%) 38.78
(1.1%) -0.9% ( -3% - 1%) 0.023</b>
PKLookupBatch 38.81 (1.2%) 38.52
(1.4%) -0.7% ( -3% - 1%) 0.071
<b> PKLookupBatch 38.95 (1.2%) 38.60
(1.0%) -0.9% ( -3% - 1%) 0.013</b>
</pre>
#### ASINs
Standalone harness only (luceneutil has no ASIN-style ID format):
| index | host | single-key hits | single-key 90% misses | batch 4,096 hits
| batch 4,096 90% misses |
|---|---|---|---|---|---|
| asin 10M, 1 segment | c8g | 1,551 → 5,051 (3.26x) | 4,322 → 5,926 (1.37x)
| 1,360 → 8,771 (6.45x) | 2,231 → 15,422 (6.91x) |
| asin 10M, 1 segment | c8i | 2,128 → 3,602 (1.69x) | 3,473 → 5,690 (1.64x)
| 2,057 → 10,179 (4.95x) | 1,960 → 16,157 (8.24x) |
## Previous related discussions
Found the following related discussions (summaries by AI):
> Related issues/PRs to link (all apache/lucene):
> - [#15520](https://github.com/apache/lucene/issues/15520): should Lucene
offer a helper for primary-key lookups (mikemccand).
> - [#16128](https://github.com/apache/lucene/issues/16128): promote
PerThreadPKLookup to core as PrimaryKeyLookup. Open, approved by epotyom,
waiting on its author. Same API space as PrimaryKeyHashLookup.
> - [#15820](https://github.com/apache/lucene/issues/15820) /
[#15824](https://github.com/apache/lucene/issues/15824): trie `seekExact` 4x
slower for UUID `_id` lookups vs the old FST (open).
> - [#12513](https://github.com/apache/lucene/issues/12513) /
[#12688](https://github.com/apache/lucene/issues/12688): tantivy-style terms
dictionary; mikemccand: "The PKLookup gains are astounding!"
> - [#5141](https://github.com/apache/lucene/issues/5141) (LUCENE-4069) and
[#12986](https://github.com/apache/lucene/issues/12986): Bloom postings format
history; heap at write time (jpountz), back-compat (rmuir).
> - MemoryPostingsFormat removal and the nightly PKLookup drop, with FST50
as the answer:
[luceneutil#22](https://github.com/mikemccand/luceneutil/issues/22).
> - [#16051](https://github.com/apache/lucene/issues/16051) + dev@ thread
"TermInSetQuery storage": sandbox TermInSetQuery alternative; uschindler on
implementation-named query classes.
> - [#16780](https://github.com/apache/lucene/issues/16780) /
[#16843](https://github.com/apache/lucene/issues/16843): binary fuse filters to
replace the Bloom filter (overlaps only our optional filter).
> - IDVersionPostingsFormat (sandbox): precedent for an ID-specific sandbox
postings format.
This is just an initial POC implementation with lots of experiments &
results for various options. Curious to know what the community thinks of this
general direction and if its worth putting more effort into it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
