Impl intoBitset for IndexedDISI and Docvalues by gf2121 · Pull Request #14529 · apache/lucene

gf2121 · 2025-04-21T14:04:51Z

Implement intoBitset for IndexedDISI and Docvalues.

intoBitset of Docvalues has already been called in competitive iterators, and can also be used to speed up soft delete operations.

Logic of this impl is different from default impl when calling intoBitset after advanceExact return false, where default impl starts from a not-existing doc but this impl starts from the next doc. I do not know which one is intended, maybe this should just be undefined.

relates: #14521

jpountz · 2025-04-22T08:07:53Z

To keep things as simple as possible, I'm wondering about:

Using a very simple/robust impl in the SPARSE case that moves to the next doc in a loop until either the end of block or upTo, since it should never be a bottleneck (especially as DenseConjunctionBulkScorer is only used on dense iterators)?
Refactoring DENSE to load doc IDs into an in-memory bit set all the time, so that intoBitSet could directly reuse FixedBitSet.orRange.

gf2121 · 2025-04-22T08:31:21Z

Thanks for feedback,

Using a very simple/robust impl in the SPARSE case that moves to the next doc in a loop until either the end of block or upTo, since it should never be a bottleneck (especially as DenseConjunctionBulkScorer is only used on dense iterators)?

I won't assume intoBitset will only be called by DenseConjunctionBulkScorer. I was also thinking about using it for soft delete (#14521) or docvalues' merge. IndexedDISI#writeBitset will always load the whole block of docs into a bitset.

But I'm not sure how much performance this approach gains, i agree to keep it simple as a first step.

Refactoring DENSE to load doc IDs into an in-memory bit set all the time, so that intoBitSet could directly reuse FixedBitSet.orRange.

I'm a bit confused on this, current patch has already been loading docs into a in-memory bitset and reuse orRange, could you be more specific?

jpountz · 2025-04-22T20:22:55Z

I'm a bit confused on this, current patch has already been loading docs into a in-memory bitset and reuse orRange, could you be more specific?

I was wondering if we should go one step further and load the bitset into heap eagerly just after reading the block header, and then using it for nextDoc/advance too, instead of doing it lazily and just for intoBitSet.

gf2121 · 2025-04-23T04:11:44Z

I'm not sure, would this cause heavy overreading in scenarios where only advance/advanceExact is required a few times in this block? E.g. we saw aggregation on hundreds of metrics with small total hits, which could be the case harmed by the overreading.

gf2121 · 2025-04-23T16:59:00Z

I personally prefer not to eagerly load docs for advance/advanceExact, or maybe leave it to another issue/PR.

I update code to one of the version during my local iteration, which reduces the complexity by using a single orRange instead of multiple round of orRange. I wonder if this will make sense to you.

jpountz · 2025-04-23T14:20:50Z

lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java

      method = Method.SPARSE;
      blockEnd = slice.getFilePointer() + (numValues << 1);
      nextExistDocInBlock = -1;
+      exists = false;


Is this a pre-existing bug?

This is to make intoBitset work with advanceExact, which is not really needed. I removed this.

jpountz · 2025-04-23T14:26:15Z

lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java

+          bitSet.set(disi.doc - offset);
+        }
+
+        for (int i = disi.index, to = disi.nextBlockIndex; i < to; i++) {


I am a bit surprised that this loop starts at disi.index instead of disi.index + 1 since the doc at disi.index was already handled above?

I changed this to make it clearer.

jpountz · 2025-04-23T20:15:32Z

lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java


+  @Override
+  public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
+    assert doc >= offset;


Can you also assert something like doc == NOT_MORE_DOCS || advanceExact(doc)? It shouldn't be legal to call intoBitSet after advanceExact returns false (or maybe a better place for this would be asserting doc values).

It looks like some implementations of intoBitsetWithinBlock try to cover the case when the current doc doesn't exist, maybe they can be simplified?

(or maybe a better place for this would be asserting doc values

+1

It looks like some implementations of intoBitsetWithinBlock try to cover the case when the current doc doesn't exist, maybe they can be simplified?

Done :)

jpountz · 2025-04-24T06:39:20Z

lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java

+        }
+        bitSet.set(disi.doc - offset);
+
+        for (int i = disi.index + 1, to = disi.nextBlockIndex; i <= to; i++) {


I'm still a bit confused, why is disi.nextBlockIndex included in the loop when it's excluded in advanceWithinBlock?

In advanceWithinBlock, disi.index++ is executed in the loop body before if (doc >= targetInBlock) so it is not actually excluded. advanceWithinBlock can return true when disi.index equals disi.nextBlockIndex.

I update to the pattern like advanceWithinBlock

jpountz · 2025-04-24T06:45:53Z

lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java

+  public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
+    assert doc >= offset;
+    while (method.intoBitsetWithinBlock(this, upTo, bitSet, offset) == false) {
+      readBlockHeader();


I wonder if we should call something like below after reading the block header (similar to what advance(target) does):

boolean found = method.advanceWithinBlock(this, block); assert found;

This would guarantee that disi.doc is always a doc ID of the block when intoBitsetWithinBlock is called, which could help simplify some implementations of intoBitsetWithinBlock? (I'm looking at DENSE in particular)

I like the simplification!

jpountz · 2025-04-24T06:46:51Z

lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java

+     * false return, fp of disi#slice is at blockEnd and disi#index is correct but other status vars
+     * are undefined. Caller should decode the header of next block by {@link #readBlockHeader()}.
+     */
+    abstract boolean intoBitsetWithinBlock(


Nit: for consistency with how it's called on DocIdSetIterator.

Suggested change

abstract boolean intoBitsetWithinBlock(

abstract boolean intoBitSetWithinBlock(

jpountz

I left some minor comments, other than that it looks good to me!

jpountz · 2025-04-24T07:26:11Z

lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java

+      boolean intoBitSetWithinBlock(IndexedDISI disi, int upTo, FixedBitSet bitSet, int offset)
+          throws IOException {
+        if (disi.doc >= upTo) {
+          advanceWithinBlock(disi, disi.doc);


Do we really need to call advanceWithinBlock? If disi.doc is already >= upTo, there shouldn't be anything to do?

This was useful before we advancing disi.block, but not now. I like the simplification more :)

jpountz · 2025-04-24T07:27:49Z

lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java

+        int sourceTo = Math.min(upTo - disi.block, BLOCK_SIZE);
+        int numWords = FixedBitSet.bits2words(sourceTo) - sourceStartWord;
+
+        if (disi.bitSet == null || disi.bitSet.getBits().length < numWords) {


Should we always create a bit set of size BLOCK_SIZE when it's null for simplicity? This is what users will get in the worst-case scenario anyway, and it's not crazy (65k bits = 8kB)?

jpountz · 2025-04-24T07:29:47Z

lucene/core/src/test/org/apache/lucene/codecs/lucene90/TestIndexedDISI.java

+      }
+      assertEquals(DocIdSetIterator.NO_MORE_DOCS, actual.nextDoc());
+      set1.clear();
+      set2.clear();


Can you also check that nextDoc() returns the expected value after intoBitSet returns? To make sure that all required state is set correctly?

This helps me find a bug: upTo could be a number in last block when RANGE do intoBitSetWithinBlock, i'm missing a doc > upTo check there.

jpountz · 2025-04-24T11:43:23Z

lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java

+
+        int sourceFrom = disi.doc & 0xFFFF;
+        int sourceTo = Math.min(upTo - disi.block, BLOCK_SIZE);
+        int destFrom = disi.block - offset + sourceFrom;


Is this the same as disi.doc - offset?

jpountz · 2025-04-24T11:44:46Z

lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java

+        int destFrom = disi.block - offset + sourceFrom;
+
+        long fp = disi.slice.getFilePointer();
+        disi.slice.seek(fp - Long.BYTES);


nit: maybe leave a small comment explaining why we're seeking backwards, I believe that it's to include the word that contains the current doc, right?

Apply changes made between 10.2.2 and 10.3.1 versions: ``` $ g log --oneline releases/lucene/10.2.2..releases/lucene/10.3.1 lucene/core/src/java/org/apache/lucene/codecs/lucene90/{Lucene90DocValuesProducer.java,Lucene90DocValuesConsumer.java,Lucene90DocValuesFormat.java} d176a42b659 Implement IndexedDISI#docIDRunEnd (#14753) 223d7a41e3c [10.x] Change uses of withReadAdvice to use hints instead (#14629) (#14510) bb3167e57c6 Impl intoBitset for IndexedDISI and Docvalues (#14529) ``` Relevant PRs: apache/lucene#14753 apache/lucene#14510 apache/lucene#14529 Follows: #18545

gf2121 added 2 commits April 21, 2025 21:49

impl IndexedDISI intoBitset

ca5c763

Lucene90DocValuesProducer

99bc636

github-project-automation bot added this to OpenSearch Lucene & Core Performance Tracking Apr 21, 2025

github-project-automation bot moved this to Open in OpenSearch Lucene & Core Performance Tracking Apr 21, 2025

github-actions bot added the module:core/codecs label Apr 21, 2025

gf2121 mentioned this pull request Apr 21, 2025

Speed up soft delete #14521

Open

3 tasks

fix

52213f7

gf2121 added 6 commits April 22, 2025 17:05

make sparse simple

bda244a

clear sparse buffer

c30ddb7

unused var

52eba98

clean some more unnecessary diff

ae6d2c2

iter

3a57520

iter

00733fb

simplify dense

0addf45

gf2121 added 2 commits April 24, 2025 01:04

fit contract of ensureCapacity

f28e4e4

better grow

84ca0b8

jpountz reviewed Apr 23, 2025

View reviewed changes

review iter

4b2b347

github-actions bot added module:core/index module:test-framework labels Apr 24, 2025

unnecessay diff

b8e4e79

jpountz reviewed Apr 24, 2025

View reviewed changes

gf2121 added 2 commits April 24, 2025 15:20

iter

a9d322b

doc

10c3844

jpountz approved these changes Apr 24, 2025

View reviewed changes

gf2121 added 2 commits April 24, 2025 18:50

review iter

dc3bfa5

incorrect diff

ee6f036

gf2121 requested a review from jpountz April 24, 2025 11:28

jpountz approved these changes Apr 24, 2025

View reviewed changes

review iter

a65d068

jpountz approved these changes Apr 24, 2025

View reviewed changes

gf2121 merged commit e2e44bc into apache:main Apr 24, 2025
7 checks passed

github-project-automation bot moved this from Open to Merged in OpenSearch Lucene & Core Performance Tracking Apr 24, 2025

asfgit pushed a commit that referenced this pull request Apr 24, 2025

Impl intoBitset for IndexedDISI and Docvalues (#14529)

bb3167e

matriv mentioned this pull request Oct 21, 2025

Apply Lucene changes to CrateDB's CustomLucene90DocValuesProducer crate/crate#18554

Merged

	abstract boolean intoBitsetWithinBlock(
	abstract boolean intoBitSetWithinBlock(

Conversation

gf2121 commented Apr 21, 2025

Uh oh!

jpountz commented Apr 22, 2025

Uh oh!

gf2121 commented Apr 22, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jpountz commented Apr 22, 2025

Uh oh!

gf2121 commented Apr 23, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

gf2121 commented Apr 23, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

gf2121 Apr 24, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jpountz left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

gf2121 commented Apr 22, 2025 •

edited

Loading

gf2121 commented Apr 23, 2025 •

edited

Loading

gf2121 Apr 24, 2025 •

edited

Loading