You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by gu...@apache.org on 2025/05/09 17:33:55 UTC
(lucene) branch branch_10x updated: Speed up flush of softdelete by intoBitset (#14552)
This is an automated email from the ASF dual-hosted git repository.
guofeng pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/branch_10x by this push:
new e10288fce3c Speed up flush of softdelete by intoBitset (#14552)
e10288fce3c is described below
commit e10288fce3c8cea19dd61bad0fc79ec8a485a613
Author: Guo Feng <52...@users.noreply.github.com>
AuthorDate: Sat May 10 01:12:47 2025 +0800
Speed up flush of softdelete by intoBitset (#14552)
---
lucene/CHANGES.txt | 2 +
.../apache/lucene/codecs/lucene90/IndexedDISI.java | 51 +++++-----------
.../org/apache/lucene/index/ReadersAndUpdates.java | 69 ++++++++++++++++++++++
.../java/org/apache/lucene/util/FixedBitSet.java | 5 +-
.../lucene/index/TestMixedDocValuesUpdates.java | 27 +++++++++
5 files changed, 116 insertions(+), 38 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 4b1334e762c..9f5e5fa5e91 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -47,6 +47,8 @@ Optimizations
* GITHUB#14529, GITHUB#14555, GITHUB#14618: Impl intoBitset for IndexedDISI and Docvalues. (Guo Feng)
+* GITHUB#14552: Speed up flush of softdelete by intoBitset. (Guo Feng)
+
Bug Fixes
---------------------
(No changes)
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java
index e216d54f214..f9c14484cec 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java
@@ -204,49 +204,28 @@ public final class IndexedDISI extends AbstractDocIdSetIterator {
int blockCardinality = 0;
final FixedBitSet buffer = new FixedBitSet(1 << 16);
int[] jumps = new int[ArrayUtil.oversize(1, Integer.BYTES * 2)];
- int prevBlock = -1;
- int jumpBlockIndex = 0;
+ int lastBlock = 0;
- for (int doc = it.nextDoc(); doc != DocIdSetIterator.NO_MORE_DOCS; doc = it.nextDoc()) {
+ for (int doc = it.nextDoc(); doc != DocIdSetIterator.NO_MORE_DOCS; doc = it.docID()) {
final int block = doc >>> 16;
- if (prevBlock != -1 && block != prevBlock) {
- // Track offset+index from previous block up to current
- jumps =
- addJumps(
- jumps,
- out.getFilePointer() - origo,
- totalCardinality,
- jumpBlockIndex,
- prevBlock + 1);
- jumpBlockIndex = prevBlock + 1;
- // Flush block
- flush(prevBlock, buffer, blockCardinality, denseRankPower, out);
- // Reset for next block
- buffer.clear();
- totalCardinality += blockCardinality;
- blockCardinality = 0;
- }
- buffer.set(doc & 0xFFFF);
- blockCardinality++;
- prevBlock = block;
- }
- if (blockCardinality > 0) {
- jumps =
- addJumps(
- jumps, out.getFilePointer() - origo, totalCardinality, jumpBlockIndex, prevBlock + 1);
- totalCardinality += blockCardinality;
- flush(prevBlock, buffer, blockCardinality, denseRankPower, out);
+ final int upTo = (int) Math.min(Integer.MAX_VALUE, (doc | 0xFFFF) + 1L);
+ it.intoBitSet(upTo, buffer, doc & 0xFFFF0000);
+ blockCardinality = buffer.cardinality();
+ jumps = addJumps(jumps, out.getFilePointer() - origo, totalCardinality, lastBlock, block + 1);
+ lastBlock = block + 1;
+ // Flush block
+ flush(block, buffer, blockCardinality, denseRankPower, out);
+ // Reset for next block
buffer.clear();
- prevBlock++;
+ totalCardinality += blockCardinality;
}
- final int lastBlock =
- prevBlock == -1 ? 0 : prevBlock; // There will always be at least 1 block (NO_MORE_DOCS)
+
+ // There will always be at least 1 block (NO_MORE_DOCS)
// Last entry is a SPARSE with blockIndex == 32767 and the single entry 65535, which becomes the
// docID NO_MORE_DOCS
// To avoid creating 65K jump-table entries, only a single entry is created pointing to the
- // offset of the
- // NO_MORE_DOCS block, with the jumpBlockIndex set to the logical EMPTY block after all real
- // blocks.
+ // offset of the NO_MORE_DOCS block, with the jumpBlockIndex set to the logical EMPTY block
+ // after all real blocks.
jumps =
addJumps(jumps, out.getFilePointer() - origo, totalCardinality, lastBlock, lastBlock + 1);
buffer.set(DocIdSetIterator.NO_MORE_DOCS & 0xFFFF);
diff --git a/lucene/core/src/java/org/apache/lucene/index/ReadersAndUpdates.java b/lucene/core/src/java/org/apache/lucene/index/ReadersAndUpdates.java
index 8c492c54618..ec1db2dd239 100644
--- a/lucene/core/src/java/org/apache/lucene/index/ReadersAndUpdates.java
+++ b/lucene/core/src/java/org/apache/lucene/index/ReadersAndUpdates.java
@@ -39,6 +39,7 @@ import org.apache.lucene.store.IOContext;
import org.apache.lucene.store.TrackingDirectoryWrapper;
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.FixedBitSet;
import org.apache.lucene.util.IOConsumer;
import org.apache.lucene.util.IOUtils;
import org.apache.lucene.util.InfoStream;
@@ -385,6 +386,12 @@ final class ReadersAndUpdates {
return mergedDocValues.advance(target);
}
+ @Override
+ public void intoBitSet(int upTo, FixedBitSet bitSet, int offset)
+ throws IOException {
+ mergedDocValues.intoBitSet(upTo, bitSet, offset);
+ }
+
@Override
public long cost() {
return mergedDocValues.cost();
@@ -432,6 +439,12 @@ final class ReadersAndUpdates {
return mergedDocValues.advance(target);
}
+ @Override
+ public void intoBitSet(int upTo, FixedBitSet bitSet, int offset)
+ throws IOException {
+ mergedDocValues.intoBitSet(upTo, bitSet, offset);
+ }
+
@Override
public long cost() {
return mergedDocValues.cost();
@@ -461,6 +474,7 @@ final class ReadersAndUpdates {
private int docIDOnDisk = -1;
// docID from our updates
private int updateDocID = -1;
+ private FixedBitSet scratch;
private final DocValuesInstance onDiskDocValues;
private final DocValuesInstance updateDocValues;
@@ -526,6 +540,61 @@ final class ReadersAndUpdates {
} while (hasValue == false);
return docIDOut;
}
+
+ @Override
+ public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
+ if (onDiskDocValues == null) {
+ super.intoBitSet(upTo, bitSet, offset);
+ return;
+ }
+
+ // we need a scratch bitset because the param bitset doesn't allow bits to be cleared.
+ if (scratch == null) {
+ scratch = new FixedBitSet(bitSet.length());
+ } else {
+ // It's OK even if bitset.length() == 0 according the contract.
+ scratch = FixedBitSet.ensureCapacity(scratch, bitSet.length() - 1);
+ scratch.clear();
+ }
+
+ onDiskDocValues.intoBitSet(upTo, scratch, offset);
+ docIDOnDisk = onDiskDocValues.docID();
+
+ for (int doc = updateDocValues.docID(); doc < upTo; doc = updateDocValues.nextDoc()) {
+ if (updateIterator.hasValue()) {
+ scratch.set(doc - offset);
+ } else {
+ scratch.clear(doc - offset);
+ }
+ }
+
+ FixedBitSet.orRange(scratch, 0, bitSet, 0, bitSet.length());
+
+ // Iterate to find out current doc.
+ while (true) {
+ while (updateDocValues.docID() < docIDOnDisk && updateIterator.hasValue() == false) {
+ updateDocValues.nextDoc();
+ }
+ if (docIDOnDisk != NO_MORE_DOCS
+ && updateDocValues.docID() == docIDOnDisk
+ && updateIterator.hasValue() == false) {
+ // value of docIDOnDisk removed
+ docIDOnDisk = onDiskDocValues.nextDoc();
+ } else {
+ break;
+ }
+ }
+
+ // update docIDOut and currentValuesSupplier
+ updateDocID = updateDocValues.docID();
+ if (docIDOnDisk < updateDocID) {
+ docIDOut = docIDOnDisk;
+ currentValuesSupplier = onDiskDocValues;
+ } else {
+ docIDOut = updateDocID;
+ currentValuesSupplier = updateDocValues;
+ }
+ }
}
private synchronized Set<String> writeFieldInfosGen(
diff --git a/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java b/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java
index 22ef8032d2c..1d8b4d16ecd 100644
--- a/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java
+++ b/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java
@@ -45,11 +45,12 @@ public final class FixedBitSet extends BitSet {
/**
* If the given {@link FixedBitSet} is large enough to hold {@code numBits+1}, returns the given
- * bits, otherwise returns a new {@link FixedBitSet} which can hold the requested number of bits.
+ * bits, otherwise returns a new {@link FixedBitSet} which can hold {@code numBits+1} bits. That
+ * means the bitset returned by this method can be safely called with {@code bits.set(numBits)}
*
* <p><b>NOTE:</b> the returned bitset reuses the underlying {@code long[]} of the given {@code
* bits} if possible. Also, calling {@link #length()} on the returned bits may return a value
- * greater than {@code numBits}.
+ * greater than {@code numBits+1}.
*/
public static FixedBitSet ensureCapacity(FixedBitSet bits, int numBits) {
if (numBits < bits.numBits) {
diff --git a/lucene/core/src/test/org/apache/lucene/index/TestMixedDocValuesUpdates.java b/lucene/core/src/test/org/apache/lucene/index/TestMixedDocValuesUpdates.java
index a5f8021bb58..091c9493160 100644
--- a/lucene/core/src/test/org/apache/lucene/index/TestMixedDocValuesUpdates.java
+++ b/lucene/core/src/test/org/apache/lucene/index/TestMixedDocValuesUpdates.java
@@ -752,4 +752,31 @@ public class TestMixedDocValuesUpdates extends LuceneTestCase {
exception.getMessage());
}
}
+
+ public void testLongRunValuesReset() throws Exception {
+ Directory dir = newDirectory();
+ IndexWriter writer = new IndexWriter(dir, new IndexWriterConfig());
+ int numDocs = atLeast(65536);
+ for (int i = 0; i < numDocs; i++) {
+ Document doc = new Document();
+ doc.add(new StringField("id", String.valueOf(i), Store.NO));
+ if (i == 0 || i == numDocs - 1 || random().nextBoolean()) {
+ doc.add(new NumericDocValuesField("numeric", 1));
+ }
+ writer.addDocument(doc);
+ }
+ writer.flush();
+
+ for (int i = 1; i < numDocs - 1; i++) {
+ writer.updateDocValues(
+ new Term("id", String.valueOf(i)), new NumericDocValuesField("numeric", null));
+ }
+
+ try (IndexReader reader = writer.getReader(true, true)) {
+ IndexSearcher searcher = new IndexSearcher(reader);
+ assertEquals(2, searcher.count(new FieldExistsQuery("numeric")));
+ }
+
+ IOUtils.close(writer, dir);
+ }
}