jimczi opened a new pull request, #16418:
URL: https://github.com/apache/lucene/pull/16418
# Incremental doc-values updates
When you update a doc-values field today, Lucene rewrites the whole column
for that field, even if you only touched a
few docs. So a tiny change writes a lot, and it gets worse as the segment
grows.
The idea is simple: when an update only sets values (no unset), write just
the changed docs as a sparse "delta"
generation, and stack the deltas on top of the base column at read time,
newest wins. Updating a field becomes
`O(changed docs)` instead of `O(column)`.
Deltas would pile up, so there's a small lifecycle per field:
- every flush writes a delta with only the changed docs
- too many deltas -> fold them into one sparse generation
- deltas end up covering the whole column -> fold back to a single dense
column
- a merge flattens everything back to a normal column
Numeric and binary only, set-only (a value unset falls back to the current
dense rewrite). No doc-values format
change, the deltas use the codec's existing sparse encoding.
An old Lucene can't read the overlay. So a commit that carries one is
written at a bumped segments version, and an old
reader rejects it instead of reading a delta as if it was the whole column.
A commit with no overlay is written
exactly like before, so it's safe to backport (off by default there; on
`main` it's on by default, disable with
`IndexWriterConfig#setIncrementalDocValuesUpdates(false)`).
This is a proposal, I'd like your opinion on the approach before polishing
it more. Two things I'm not sure about:
where the overlay bookkeeping should live (I put it on `SegmentCommitInfo`),
and the compaction, which right now
re-folds all the deltas every time. A size-tiered policy would be better,
left as a TODO.
## Numbers
There are three ways to change one field on a doc, so I compared them head
to head. The benchmark is in the last
commit, a plain `main`, not a test, run as a normal Java app (assertions
off, real JIT, mmap directory) so the JVM
behaves like production and not the test harness. It'll go before merge,
it's just there so you can reproduce. It
indexes 5M docs, each with an 8-byte field and a 512-dim vector,
force-merges to one segment, then applies updates in
random order (not ingestion order, so the overlay actually gets stressed)
from 4 threads, refreshing an NRT reader
every second. It reports update throughput, the bytes written during the
update phase, write amplification, and a scan
that reads the field back. All three arms end on the same values.
- full reindex: `updateDocument`, what you do today when the field isn't
doc-values-updatable. Rewrites the whole doc.
- dense update: what Lucene does now. Rewrites the whole column.
- sparse update: this PR. Only the changed docs.
The thing that matters is cadence. Write amplification isn't really a
property of the feature, it's a property of how
many docs you change between commits. So I ran every arm two ways: a batch
that updates as fast as it can (lots of docs
per refresh), and a throttled stream at 5k updates/s (a few thousand per
refresh, closer to a steady trickle on a live
index).
Numeric 8-byte field:
| regime | arm | updates/s | bytes/update | write amp | scan |
|---|---|---|---|---|---|
| batch | full reindex | 171,204 | 7,954 | 994× | 59 ms |
| batch | dense | 812,348 | 80 | 10× | 23 ms |
| batch | sparse | 544,070 | 8 | 1.0× | 100 ms |
| throttled 5k/s | full reindex | 4,991 | 9,229 | 1,153× | 88 ms |
| throttled 5k/s | dense | 4,991 | 7,200 | 900× | 18 ms |
| throttled 5k/s | sparse | 4,991 | 17 | 2.1× | 97 ms |
Amplification is bytes written over the 8 bytes actually changed. In batch,
dense amortizes: thousands of updated docs
share one full-column rewrite, so it lands at 10×. Throttle it and that same
full-column rewrite now covers only a few
thousand docs, so it jumps to 900×. Sparse doesn't care about cadence, it
writes the changed docs and nothing else, so
it stays flat: 2.1× vs 900× at 5k/s, about 400× less written.
32-byte binary field, same two runs:
| regime | arm | updates/s | bytes/update | write amp | scan |
|---|---|---|---|---|---|
| batch | full reindex | 63,796 | 7,969 | 249× | 139 ms |
| batch | dense | 949,668 | 640 | 20× | 29 ms |
| batch | sparse | 1,483,680 | 32 | 1.0× | 212 ms |
| throttled 5k/s | full reindex | 4,991 | 9,231 | 288× | 191 ms |
| throttled 5k/s | dense | 4,991 | 27,733 | 866× | 46 ms |
| throttled 5k/s | sparse | 4,991 | 53 | 1.6× | 183 ms |
Same shape, bigger column so dense costs more (27 KB/update throttled
against 53 bytes for sparse).
Soft deletes come along for free, because a soft delete is a numeric
doc-values update on the soft-deletes field, so it
takes the same path. The arms here are a hard delete (liveDocs, no column),
and the soft-delete mark with the feature
off (dense) and on (sparse):
| regime | arm | updates/s | bytes/update | scan |
|---|---|---|---|---|
| batch | hard delete | 1,818,182 | 0 | 27 ms |
| batch | dense soft | 1,851,852 | 2 | 50 ms |
| batch | sparse soft | 2,083,333 | 2 | 40 ms |
| throttled 5k/s | hard delete | 4,982 | 0 | 64 ms |
| throttled 5k/s | dense soft | 4,982 | 22 | 71 ms |
| throttled 5k/s | sparse soft | 4,982 | 4 | 77 ms |
The soft-delete column only holds the marked docs, so the absolute numbers
are small, but the shape is the same: batch
amortizes and both are basically free, throttle it and dense rewrites the
growing column every commit (22 bytes/update)
while sparse writes just the newly marked docs (4 bytes/update).
Reads are the tradeoff. The sparse scan merges the overlay at read time, so
it's a few times slower than a single
column (numeric 100 ms vs 23 ms, binary 212 ms vs 29 ms over 5M docs). It's
bounded by `setMaxDocValuesDeltaGenerations`
(default 16, more generations means cheaper writes but more layers to merge
on read), and a merge flattens it back to
single-column speed. I also ran the batch with 4 threads querying while the
updates landed and everything stayed
correct with the write numbers holding.
The benchmark is only here so you can look at the numbers for this review,
it isn't meant to land. Here's the line I
ran:
```
java -da -Xmx6g --enable-native-access=ALL-UNNAMED \
-Ddvbench.docs=5000000 -Ddvbench.dims=512 -Ddvbench.flatVectors=true
-Ddvbench.updates=1000000 -Ddvbench.threads=4 \
-cp
lucene/core/build/classes/java/main:lucene/core/build/resources/main:lucene/core/build/classes/java/test
\
org.apache.lucene.index.IncrementalDocValuesUpdatesBenchmark
```
(add `-Ddvbench.rate=5000` to throttle, `-Ddvbench.type=binary` or
`-Ddvbench.type=softdelete` for the other fields,
`-Ddvbench.queryThreads=4` to query under load.)
## Commits
Split so each piece is easy to look at on its own:
1. config options, the two settings
2. overlay iterators, the read side: merge the deltas over the base, unit
tested alone
3. SegmentCommitInfo, where the overlay generations are stored + the
segments-version fence
4. write path, write the delta, fold, fold-to-dense, thread the config
through
5. tests
6. the standalone benchmark (temporary, removed before merge)
--
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]
