You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2025/01/14 18:02:36 UTC
(lucene) branch main updated: Encode dense blocks of postings as bit sets. (#14133)
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 26e5a8d6c32 Encode dense blocks of postings as bit sets. (#14133)
26e5a8d6c32 is described below
commit 26e5a8d6c32eea0f1a4e54557c1da9b1c1cc0e49
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Tue Jan 14 19:02:29 2025 +0100
Encode dense blocks of postings as bit sets. (#14133)
Bit sets can be faster at advancing and more storage-efficient on dense blocks
of postings. This is not a new idea, @mkhludnev proposed something similar a
long time ago #6116.
@msokolov recently brought up (#14080) that such an encoding has become
especially appealing with the introduction of the
`DocIdSetIterator#loadIntoBitSet` API, and the fact that non-scoring
disjunctions and dense conjunctions now take advantage of it. Indeed, if
postings are stored in a bit set, `#loadIntoBitSet` would just need to OR the
postings bits into the bits that are used as an intermediate representation of
matches of the query.
---
.../generated/checksums/generateForDeltaUtil.json | 4 +-
.../lucene/codecs/lucene101/ForDeltaUtil.java | 74 ++++-----
.../codecs/lucene101/Lucene101PostingsFormat.java | 22 ++-
.../codecs/lucene101/Lucene101PostingsReader.java | 166 ++++++++++++++++++---
.../codecs/lucene101/Lucene101PostingsWriter.java | 67 +++++++--
.../lucene/codecs/lucene101/gen_ForDeltaUtil.py | 73 +++------
.../lucene/codecs/lucene101/TestForDeltaUtil.java | 7 +-
.../lucene101/TestLucene101PostingsFormatV0.java | 34 +++++
8 files changed, 315 insertions(+), 132 deletions(-)
diff --git a/lucene/core/src/generated/checksums/generateForDeltaUtil.json b/lucene/core/src/generated/checksums/generateForDeltaUtil.json
index 96f49fa81ff..85765bbd7cb 100644
--- a/lucene/core/src/generated/checksums/generateForDeltaUtil.json
+++ b/lucene/core/src/generated/checksums/generateForDeltaUtil.json
@@ -1,4 +1,4 @@
{
- "lucene/core/src/java/org/apache/lucene/codecs/lucene101/ForDeltaUtil.java": "e0bf6071bcdefaa297e0bb92f79615201777652d",
- "lucene/core/src/java/org/apache/lucene/codecs/lucene101/gen_ForDeltaUtil.py": "d7484ab18da33e5cb73faaf84b4e2bb832b62f9d"
+ "lucene/core/src/java/org/apache/lucene/codecs/lucene101/ForDeltaUtil.java": "87e4d19b5284fa39adf2c24328cae2076b6f7bb3",
+ "lucene/core/src/java/org/apache/lucene/codecs/lucene101/gen_ForDeltaUtil.py": "165586f801bef4d2f540521e81bc119880038b6c"
}
\ No newline at end of file
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene101/ForDeltaUtil.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene101/ForDeltaUtil.java
index 51b47a0a1f6..ceec3ce3342 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene101/ForDeltaUtil.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene101/ForDeltaUtil.java
@@ -37,23 +37,6 @@ public final class ForDeltaUtil {
private static final int TWO_BLOCK_SIZE_FOURTHS = BLOCK_SIZE / 2;
private static final int THREE_BLOCK_SIZE_FOURTHS = 3 * BLOCK_SIZE / 4;
- // IDENTITY_PLUS_ONE[i] == i+1
- private static final int[] IDENTITY_PLUS_ONE = new int[ForUtil.BLOCK_SIZE];
-
- static {
- for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
- IDENTITY_PLUS_ONE[i] = i + 1;
- }
- }
-
- private static void prefixSumOfOnes(int[] arr, int base) {
- System.arraycopy(IDENTITY_PLUS_ONE, 0, arr, 0, ForUtil.BLOCK_SIZE);
- // This loop gets auto-vectorized
- for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
- arr[i] += base;
- }
- }
-
private static void prefixSum8(int[] arr, int base) {
// When the number of bits per value is 4 or less, we can sum up all values in a block without
// risking overflowing an 8-bits integer. This allows computing the prefix sum by summing up 4
@@ -199,43 +182,35 @@ public final class ForDeltaUtil {
private final int[] tmp = new int[BLOCK_SIZE];
/**
- * Encode deltas of a strictly monotonically increasing sequence of integers. The provided {@code
- * ints} are expected to be deltas between consecutive values.
+ * Return the number of bits per value required to store the given array containing strictly
+ * positive numbers.
*/
- void encodeDeltas(int[] ints, DataOutput out) throws IOException {
- if (ints[0] == 1 && PForUtil.allEqual(ints)) { // happens with very dense postings
- out.writeByte((byte) 0);
- } else {
- int or = 0;
- for (int l : ints) {
- or |= l;
- }
- assert or != 0;
- final int bitsPerValue = PackedInts.bitsRequired(or);
- out.writeByte((byte) bitsPerValue);
-
- final int primitiveSize;
- if (bitsPerValue <= 3) {
- primitiveSize = 8;
- collapse8(ints);
- } else if (bitsPerValue <= 10) {
- primitiveSize = 16;
- collapse16(ints);
- } else {
- primitiveSize = 32;
- }
- encode(ints, bitsPerValue, primitiveSize, out, tmp);
+ int bitsRequired(int[] ints) {
+ int or = 0;
+ for (int l : ints) {
+ or |= l;
}
+ // Deltas should be strictly positive since the delta between consecutive doc IDs is at least 1
+ assert or != 0;
+ return PackedInts.bitsRequired(or);
}
- /** Decode deltas, compute the prefix sum and add {@code base} to all decoded ints. */
- void decodeAndPrefixSum(PostingDecodingUtil pdu, int base, int[] ints) throws IOException {
- final int bitsPerValue = Byte.toUnsignedInt(pdu.in.readByte());
- if (bitsPerValue == 0) {
- prefixSumOfOnes(ints, base);
+ /**
+ * Encode deltas of a strictly monotonically increasing sequence of integers. The provided {@code
+ * ints} are expected to be deltas between consecutive values.
+ */
+ void encodeDeltas(int bitsPerValue, int[] ints, DataOutput out) throws IOException {
+ final int primitiveSize;
+ if (bitsPerValue <= 3) {
+ primitiveSize = 8;
+ collapse8(ints);
+ } else if (bitsPerValue <= 10) {
+ primitiveSize = 16;
+ collapse16(ints);
} else {
- decodeAndPrefixSum(bitsPerValue, pdu, base, ints);
+ primitiveSize = 32;
}
+ encode(ints, bitsPerValue, primitiveSize, out, tmp);
}
/** Delta-decode 128 integers into {@code ints}. */
@@ -307,6 +282,9 @@ public final class ForDeltaUtil {
prefixSum32(ints, base);
break;
default:
+ if (bitsPerValue < 1 || bitsPerValue > Integer.SIZE) {
+ throw new IllegalStateException("Illegal number of bits per value: " + bitsPerValue);
+ }
decodeSlow(bitsPerValue, pdu, tmp, ints);
prefixSum32(ints, base);
break;
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsFormat.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsFormat.java
index e228f1090ab..d83111bb8fe 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsFormat.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsFormat.java
@@ -358,8 +358,17 @@ public final class Lucene101PostingsFormat extends PostingsFormat {
static final String PAY_CODEC = "Lucene101PostingsWriterPay";
static final int VERSION_START = 0;
- static final int VERSION_CURRENT = VERSION_START;
+ /**
+ * Version that started encoding dense blocks as bit sets. Note: the old format is a subset of the
+ * new format, so Lucene101PostingsReader is able to read the old format without checking the
+ * version.
+ */
+ static final int VERSION_DENSE_BLOCKS_AS_BITSETS = 1;
+
+ static final int VERSION_CURRENT = VERSION_DENSE_BLOCKS_AS_BITSETS;
+
+ private final int version;
private final int minTermBlockSize;
private final int maxTermBlockSize;
@@ -378,7 +387,16 @@ public final class Lucene101PostingsFormat extends PostingsFormat {
* Lucene90BlockTreeTermsWriter#Lucene90BlockTreeTermsWriter(SegmentWriteState,PostingsWriterBase,int,int)
*/
public Lucene101PostingsFormat(int minTermBlockSize, int maxTermBlockSize) {
+ this(minTermBlockSize, maxTermBlockSize, VERSION_CURRENT);
+ }
+
+ /** Expert constructor that allows setting the version. */
+ public Lucene101PostingsFormat(int minTermBlockSize, int maxTermBlockSize, int version) {
super("Lucene101");
+ if (version < VERSION_START || version > VERSION_CURRENT) {
+ throw new IllegalArgumentException("Version out of range: " + version);
+ }
+ this.version = version;
Lucene90BlockTreeTermsWriter.validateSettings(minTermBlockSize, maxTermBlockSize);
this.minTermBlockSize = minTermBlockSize;
this.maxTermBlockSize = maxTermBlockSize;
@@ -386,7 +404,7 @@ public final class Lucene101PostingsFormat extends PostingsFormat {
@Override
public FieldsConsumer fieldsConsumer(SegmentWriteState state) throws IOException {
- PostingsWriterBase postingsWriter = new Lucene101PostingsWriter(state);
+ PostingsWriterBase postingsWriter = new Lucene101PostingsWriter(state, version);
boolean success = false;
try {
FieldsConsumer ret =
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsReader.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsReader.java
index 68df7683b28..b4ccff69fed 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsReader.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsReader.java
@@ -295,12 +295,37 @@ public final class Lucene101PostingsReader extends PostingsReaderBase {
final class BlockPostingsEnum extends ImpactsEnum {
+ private enum DeltaEncoding {
+ /**
+ * Deltas between consecutive docs are stored as packed integers, ie. the block is encoded
+ * using Frame Of Reference (FOR).
+ */
+ PACKED,
+ /**
+ * Deltas between consecutive docs are stored using unary coding, ie. {@code delta-1} zero
+ * bits followed by a one bit, ie. the block is encoded as an offset plus a bit set.
+ */
+ UNARY
+ }
+
private ForDeltaUtil forDeltaUtil;
private PForUtil pforUtil;
+ /* Variables that store the content of a block and the current position within this block */
+ /* Shared variables */
+ private DeltaEncoding encoding;
+ private int doc; // doc we last read
+
+ /* Variables when the block is stored as packed deltas (Frame Of Reference) */
private final int[] docBuffer = new int[BLOCK_SIZE];
- private int doc; // doc we last read
+ /* Variables when the block is stored as a bit set */
+ // Since we use a bit set when it's more storage-efficient, the bit set cannot have more than
+ // BLOCK_SIZE*32 bits, which is the maximum possible storage requirement with FOR.
+ private final FixedBitSet docBitSet = new FixedBitSet(BLOCK_SIZE * Integer.SIZE);
+ private int docBitSetBase;
+ // Reuse docBuffer for cumulative pop counts of the words of the bit set.
+ private final int[] docCumulativeWordPopCounts = docBuffer;
// level 0 skip data
private int level0LastDocID;
@@ -572,7 +597,39 @@ public final class Lucene101PostingsReader extends PostingsReaderBase {
}
private void refillFullBlock() throws IOException {
- forDeltaUtil.decodeAndPrefixSum(docInUtil, prevDocID, docBuffer);
+ int bitsPerValue = docIn.readByte();
+ if (bitsPerValue > 0) {
+ // block is encoded as 128 packed integers that record the delta between doc IDs
+ forDeltaUtil.decodeAndPrefixSum(bitsPerValue, docInUtil, prevDocID, docBuffer);
+ encoding = DeltaEncoding.PACKED;
+ } else {
+ // block is encoded as a bit set
+ assert level0LastDocID != NO_MORE_DOCS;
+ docBitSetBase = prevDocID + 1;
+ int numLongs;
+ if (bitsPerValue == 0) {
+ // 0 is used to record that all 128 docs in the block are consecutive
+ numLongs = BLOCK_SIZE / Long.SIZE; // 2
+ docBitSet.set(0, BLOCK_SIZE);
+ } else {
+ numLongs = -bitsPerValue;
+ docIn.readLongs(docBitSet.getBits(), 0, numLongs);
+ }
+ // Note: we know that BLOCK_SIZE bits are set, so no need to compute the cumulative pop
+ // count at the last index, it will be BLOCK_SIZE.
+ // Note: this for loop auto-vectorizes
+ for (int i = 0; i < numLongs - 1; ++i) {
+ docCumulativeWordPopCounts[i] = Long.bitCount(docBitSet.getBits()[i]);
+ }
+ for (int i = 1; i < numLongs - 1; ++i) {
+ docCumulativeWordPopCounts[i] += docCumulativeWordPopCounts[i - 1];
+ }
+ docCumulativeWordPopCounts[numLongs - 1] = BLOCK_SIZE;
+ assert docCumulativeWordPopCounts[numLongs - 2]
+ + Long.bitCount(docBitSet.getBits()[numLongs - 1])
+ == BLOCK_SIZE;
+ encoding = DeltaEncoding.UNARY;
+ }
if (indexHasFreq) {
if (needsFreq) {
freqFP = docIn.getFilePointer();
@@ -607,6 +664,7 @@ public final class Lucene101PostingsReader extends PostingsReaderBase {
prevDocID = docBuffer[BLOCK_SIZE - 1];
docBufferUpto = 0;
posDocBufferUpto = 0;
+ encoding = DeltaEncoding.PACKED;
assert docBuffer[docBufferSize] == NO_MORE_DOCS;
}
@@ -727,9 +785,10 @@ public final class Lucene101PostingsReader extends PostingsReaderBase {
if (needsDocsAndFreqsOnly && docCountLeft >= BLOCK_SIZE) {
// Optimize the common path for exhaustive evaluation
long level0NumBytes = docIn.readVLong();
- docIn.skipBytes(level0NumBytes);
+ long level0End = docIn.getFilePointer() + level0NumBytes;
+ level0LastDocID += readVInt15(docIn);
+ docIn.seek(level0End);
refillFullBlock();
- level0LastDocID = docBuffer[BLOCK_SIZE - 1];
} else {
doMoveToNextLevel0Block();
}
@@ -857,7 +916,19 @@ public final class Lucene101PostingsReader extends PostingsReaderBase {
moveToNextLevel0Block();
}
- return this.doc = docBuffer[docBufferUpto++];
+ switch (encoding) {
+ case PACKED:
+ doc = docBuffer[docBufferUpto];
+ break;
+ case UNARY:
+ int next = docBitSet.nextSetBit(doc - docBitSetBase + 1);
+ assert next != NO_MORE_DOCS;
+ doc = docBitSetBase + next;
+ break;
+ }
+
+ ++docBufferUpto;
+ return this.doc;
}
@Override
@@ -870,9 +941,30 @@ public final class Lucene101PostingsReader extends PostingsReaderBase {
needsRefilling = false;
}
- int next = VectorUtil.findNextGEQ(docBuffer, target, docBufferUpto, docBufferSize);
- this.doc = docBuffer[next];
- docBufferUpto = next + 1;
+ switch (encoding) {
+ case PACKED:
+ {
+ int next = VectorUtil.findNextGEQ(docBuffer, target, docBufferUpto, docBufferSize);
+ this.doc = docBuffer[next];
+ docBufferUpto = next + 1;
+ }
+ break;
+ case UNARY:
+ {
+ int next = docBitSet.nextSetBit(target - docBitSetBase);
+ assert next != NO_MORE_DOCS;
+ this.doc = docBitSetBase + next;
+ int wordIndex = next >> 6;
+ // Take the cumulative pop count for the given word, and subtract bits on the left of
+ // the current doc.
+ docBufferUpto =
+ 1
+ + docCumulativeWordPopCounts[wordIndex]
+ - Long.bitCount(docBitSet.getBits()[wordIndex] >>> next);
+ }
+ break;
+ }
+
return doc;
}
@@ -891,19 +983,53 @@ public final class Lucene101PostingsReader extends PostingsReaderBase {
moveToNextLevel0Block();
}
- int start = docBufferUpto;
- int end = computeBufferEndBoundary(upTo);
- if (end != 0) {
- bufferIntoBitSet(start, end, bitSet, offset);
- doc = docBuffer[end - 1];
- }
- docBufferUpto = end;
+ switch (encoding) {
+ case PACKED:
+ {
+ int start = docBufferUpto;
+ int end = computeBufferEndBoundary(upTo);
+ if (end != 0) {
+ bufferIntoBitSet(start, end, bitSet, offset);
+ doc = docBuffer[end - 1];
+ }
+ docBufferUpto = end;
+ if (end != BLOCK_SIZE) {
+ // Either the block is a tail block, or the block did not fully match, we're done.
+ nextDoc();
+ assert doc >= upTo;
+ return;
+ }
+ }
+ break;
+ case UNARY:
+ {
+ int sourceFrom;
+ if (docBufferUpto == 0) {
+ // start from beginning
+ sourceFrom = 0;
+ } else {
+ // start after the current doc
+ sourceFrom = doc - docBitSetBase + 1;
+ }
- if (end != BLOCK_SIZE) {
- // Either the block is a tail block, or the block did not fully match, we're done.
- nextDoc();
- assert doc >= upTo;
- break;
+ int destFrom = docBitSetBase - offset + sourceFrom;
+
+ assert level0LastDocID != NO_MORE_DOCS;
+ int sourceTo = Math.min(upTo, level0LastDocID + 1) - docBitSetBase;
+
+ if (sourceTo > sourceFrom) {
+ FixedBitSet.orRange(docBitSet, sourceFrom, bitSet, destFrom, sourceTo - sourceFrom);
+ }
+ if (docBitSetBase + sourceTo <= level0LastDocID) {
+ // We stopped before the end of the current bit set, which means that we're done.
+ // Set the current doc before returning.
+ advance(docBitSetBase + sourceTo);
+ return;
+ }
+ doc = level0LastDocID;
+ docBufferUpto = BLOCK_SIZE;
+ }
+ break;
}
}
}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsWriter.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsWriter.java
index 788a5515f2d..1cabefe681e 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsWriter.java
@@ -16,16 +16,16 @@
*/
package org.apache.lucene.codecs.lucene101;
-import static org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat.BLOCK_SIZE;
+import static org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat.*;
import static org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat.DOC_CODEC;
import static org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat.LEVEL1_MASK;
import static org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat.META_CODEC;
import static org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat.PAY_CODEC;
import static org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat.POS_CODEC;
import static org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat.TERMS_CODEC;
-import static org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat.VERSION_CURRENT;
import java.io.IOException;
+import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import org.apache.lucene.codecs.BlockTermState;
@@ -46,6 +46,7 @@ import org.apache.lucene.store.IndexOutput;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.BitUtil;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.FixedBitSet;
import org.apache.lucene.util.IOUtils;
/** Writer for {@link Lucene101PostingsFormat}. */
@@ -53,6 +54,8 @@ public class Lucene101PostingsWriter extends PushPostingsWriterBase {
static final IntBlockTermState EMPTY_STATE = new IntBlockTermState();
+ private final int version;
+
IndexOutput metaOut;
IndexOutput docOut;
IndexOutput posOut;
@@ -124,8 +127,22 @@ public class Lucene101PostingsWriter extends PushPostingsWriterBase {
*/
private final ByteBuffersDataOutput level1Output = ByteBuffersDataOutput.newResettableInstance();
- /** Sole constructor. */
+ /**
+ * Reusable FixedBitSet, for dense blocks that are more efficiently stored by storing them as a
+ * bit set than as packed deltas.
+ */
+ // Since we use a bit set when it's more storage-efficient, the bit set cannot have more than
+ // BLOCK_SIZE*32 bits, which is the maximum possible storage requirement with FOR.
+ private final FixedBitSet spareBitSet = new FixedBitSet(BLOCK_SIZE * Integer.SIZE);
+
+ /** Sole public constructor. */
public Lucene101PostingsWriter(SegmentWriteState state) throws IOException {
+ this(state, Lucene101PostingsFormat.VERSION_CURRENT);
+ }
+
+ /** Constructor that takes a version. */
+ Lucene101PostingsWriter(SegmentWriteState state, int version) throws IOException {
+ this.version = version;
String metaFileName =
IndexFileNames.segmentFileName(
state.segmentInfo.name, state.segmentSuffix, Lucene101PostingsFormat.META_EXTENSION);
@@ -139,9 +156,9 @@ public class Lucene101PostingsWriter extends PushPostingsWriterBase {
try {
docOut = state.directory.createOutput(docFileName, state.context);
CodecUtil.writeIndexHeader(
- metaOut, META_CODEC, VERSION_CURRENT, state.segmentInfo.getId(), state.segmentSuffix);
+ metaOut, META_CODEC, version, state.segmentInfo.getId(), state.segmentSuffix);
CodecUtil.writeIndexHeader(
- docOut, DOC_CODEC, VERSION_CURRENT, state.segmentInfo.getId(), state.segmentSuffix);
+ docOut, DOC_CODEC, version, state.segmentInfo.getId(), state.segmentSuffix);
forDeltaUtil = new ForDeltaUtil();
pforUtil = new PForUtil();
if (state.fieldInfos.hasProx()) {
@@ -151,7 +168,7 @@ public class Lucene101PostingsWriter extends PushPostingsWriterBase {
state.segmentInfo.name, state.segmentSuffix, Lucene101PostingsFormat.POS_EXTENSION);
posOut = state.directory.createOutput(posFileName, state.context);
CodecUtil.writeIndexHeader(
- posOut, POS_CODEC, VERSION_CURRENT, state.segmentInfo.getId(), state.segmentSuffix);
+ posOut, POS_CODEC, version, state.segmentInfo.getId(), state.segmentSuffix);
if (state.fieldInfos.hasPayloads()) {
payloadBytes = new byte[128];
@@ -177,7 +194,7 @@ public class Lucene101PostingsWriter extends PushPostingsWriterBase {
Lucene101PostingsFormat.PAY_EXTENSION);
payOut = state.directory.createOutput(payFileName, state.context);
CodecUtil.writeIndexHeader(
- payOut, PAY_CODEC, VERSION_CURRENT, state.segmentInfo.getId(), state.segmentSuffix);
+ payOut, PAY_CODEC, version, state.segmentInfo.getId(), state.segmentSuffix);
}
} else {
posDeltaBuffer = null;
@@ -207,7 +224,7 @@ public class Lucene101PostingsWriter extends PushPostingsWriterBase {
@Override
public void init(IndexOutput termsOut, SegmentWriteState state) throws IOException {
CodecUtil.writeIndexHeader(
- termsOut, TERMS_CODEC, VERSION_CURRENT, state.segmentInfo.getId(), state.segmentSuffix);
+ termsOut, TERMS_CODEC, version, state.segmentInfo.getId(), state.segmentSuffix);
termsOut.writeVInt(BLOCK_SIZE);
}
@@ -405,7 +422,39 @@ public class Lucene101PostingsWriter extends PushPostingsWriterBase {
}
}
long numSkipBytes = level0Output.size();
- forDeltaUtil.encodeDeltas(docDeltaBuffer, level0Output);
+ // Now we need to decide whether to encode block deltas as packed integers (FOR) or unary
+ // codes (bit set). FOR makes #nextDoc() a bit faster while the bit set approach makes
+ // #advance() sometimes faster and #intoBitSet() much faster. Since the trade-off is not
+ // obvious, we make the decision purely based on storage efficiency, using the approach that
+ // requires fewer bits to encode the block.
+ int bitsPerValue = forDeltaUtil.bitsRequired(docDeltaBuffer);
+ int sum = Math.toIntExact(Arrays.stream(docDeltaBuffer).sum());
+ int numBitSetLongs = FixedBitSet.bits2words(sum);
+ if (sum == BLOCK_SIZE) {
+ level0Output.writeByte((byte) 0);
+ } else if (version < VERSION_DENSE_BLOCKS_AS_BITSETS || bitsPerValue * BLOCK_SIZE < sum) {
+ level0Output.writeByte((byte) bitsPerValue);
+ forDeltaUtil.encodeDeltas(bitsPerValue, docDeltaBuffer, level0Output);
+ } else {
+ // Storing doc deltas is more efficient using unary coding (ie. storing doc IDs as a bit
+ // set)
+ spareBitSet.clear(0, numBitSetLongs << 6);
+ int s = -1;
+ for (int i : docDeltaBuffer) {
+ s += i;
+ spareBitSet.set(s);
+ }
+ // Since we use the bit set encoding when it's more storage efficient than storing deltas,
+ // we know that each doc ID uses less than 32 bits, the maximum number of bits required to
+ // store a delta between consecutive doc IDs. So in the end, the bit set cannot have more
+ // than BLOCK_SIZE * Integer.SIZE / Long.SIZE = 64 longs, which fits on a byte.
+ assert numBitSetLongs <= BLOCK_SIZE / 2;
+ level0Output.writeByte((byte) -numBitSetLongs);
+ for (int i = 0; i < numBitSetLongs; ++i) {
+ level0Output.writeLong(spareBitSet.getBits()[i]);
+ }
+ }
+
if (writeFreqs) {
pforUtil.encode(freqBuffer, level0Output);
}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene101/gen_ForDeltaUtil.py b/lucene/core/src/java/org/apache/lucene/codecs/lucene101/gen_ForDeltaUtil.py
index 3214aa67100..b1b36db096a 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene101/gen_ForDeltaUtil.py
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene101/gen_ForDeltaUtil.py
@@ -63,23 +63,6 @@ public final class ForDeltaUtil {
private static final int TWO_BLOCK_SIZE_FOURTHS = BLOCK_SIZE / 2;
private static final int THREE_BLOCK_SIZE_FOURTHS = 3 * BLOCK_SIZE / 4;
- // IDENTITY_PLUS_ONE[i] == i+1
- private static final int[] IDENTITY_PLUS_ONE = new int[ForUtil.BLOCK_SIZE];
-
- static {
- for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
- IDENTITY_PLUS_ONE[i] = i + 1;
- }
- }
-
- private static void prefixSumOfOnes(int[] arr, int base) {
- System.arraycopy(IDENTITY_PLUS_ONE, 0, arr, 0, ForUtil.BLOCK_SIZE);
- // This loop gets auto-vectorized
- for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
- arr[i] += base;
- }
- }
-
private static void prefixSum8(int[] arr, int base) {
// When the number of bits per value is 4 or less, we can sum up all values in a block without
// risking overflowing an 8-bits integer. This allows computing the prefix sum by summing up 4
@@ -224,44 +207,33 @@ public final class ForDeltaUtil {
private final int[] tmp = new int[BLOCK_SIZE];
+ /** Return the number of bits per value required to store the given array containing strictly positive numbers. */
+ int bitsRequired(int[] ints) {
+ int or = 0;
+ for (int l : ints) {
+ or |= l;
+ }
+ // Deltas should be strictly positive since the delta between consecutive doc IDs is at least 1
+ assert or != 0;
+ return PackedInts.bitsRequired(or);
+ }
+
/**
* Encode deltas of a strictly monotonically increasing sequence of integers. The provided {@code
* ints} are expected to be deltas between consecutive values.
*/
- void encodeDeltas(int[] ints, DataOutput out) throws IOException {
- if (ints[0] == 1 && PForUtil.allEqual(ints)) { // happens with very dense postings
- out.writeByte((byte) 0);
- } else {
- int or = 0;
- for (int l : ints) {
- or |= l;
- }
- assert or != 0;
- final int bitsPerValue = PackedInts.bitsRequired(or);
- out.writeByte((byte) bitsPerValue);
-
- final int primitiveSize;
- if (bitsPerValue <= 3) {
- primitiveSize = 8;
- collapse8(ints);
- } else if (bitsPerValue <= 10) {
- primitiveSize = 16;
- collapse16(ints);
- } else {
- primitiveSize = 32;
- }
- encode(ints, bitsPerValue, primitiveSize, out, tmp);
- }
- }
-
- /** Decode deltas, compute the prefix sum and add {@code base} to all decoded ints. */
- void decodeAndPrefixSum(PostingDecodingUtil pdu, int base, int[] ints) throws IOException {
- final int bitsPerValue = Byte.toUnsignedInt(pdu.in.readByte());
- if (bitsPerValue == 0) {
- prefixSumOfOnes(ints, base);
+ void encodeDeltas(int bitsPerValue, int[] ints, DataOutput out) throws IOException {
+ final int primitiveSize;
+ if (bitsPerValue <= 3) {
+ primitiveSize = 8;
+ collapse8(ints);
+ } else if (bitsPerValue <= 10) {
+ primitiveSize = 16;
+ collapse16(ints);
} else {
- decodeAndPrefixSum(bitsPerValue, pdu, base, ints);
+ primitiveSize = 32;
}
+ encode(ints, bitsPerValue, primitiveSize, out, tmp);
}
"""
@@ -361,6 +333,9 @@ if __name__ == '__main__':
f.write(' prefixSum%d(ints, base);\n' %primitive_size)
f.write(' break;\n')
f.write(' default:\n')
+ f.write(' if (bitsPerValue < 1 || bitsPerValue > Integer.SIZE) {\n')
+ f.write(' throw new IllegalStateException("Illegal number of bits per value: " + bitsPerValue);\n')
+ f.write(' }\n')
f.write(' decodeSlow(bitsPerValue, pdu, tmp, ints);\n')
f.write(' prefixSum32(ints, base);\n')
f.write(' break;\n')
diff --git a/lucene/core/src/test/org/apache/lucene/codecs/lucene101/TestForDeltaUtil.java b/lucene/core/src/test/org/apache/lucene/codecs/lucene101/TestForDeltaUtil.java
index 3e346f3eb20..d41ab472ea6 100644
--- a/lucene/core/src/test/org/apache/lucene/codecs/lucene101/TestForDeltaUtil.java
+++ b/lucene/core/src/test/org/apache/lucene/codecs/lucene101/TestForDeltaUtil.java
@@ -56,7 +56,9 @@ public class TestForDeltaUtil extends LuceneTestCase {
for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
source[j] = values[i * ForUtil.BLOCK_SIZE + j];
}
- forDeltaUtil.encodeDeltas(source, out);
+ int bitsPerValue = forDeltaUtil.bitsRequired(source);
+ out.writeByte((byte) bitsPerValue);
+ forDeltaUtil.encodeDeltas(bitsPerValue, source, out);
}
endPointer = out.getFilePointer();
out.close();
@@ -71,7 +73,8 @@ public class TestForDeltaUtil extends LuceneTestCase {
for (int i = 0; i < iterations; ++i) {
int base = 0;
final int[] restored = new int[ForUtil.BLOCK_SIZE];
- forDeltaUtil.decodeAndPrefixSum(pdu, base, restored);
+ int bitsPerValue = pdu.in.readByte();
+ forDeltaUtil.decodeAndPrefixSum(bitsPerValue, pdu, base, restored);
final int[] expected = new int[ForUtil.BLOCK_SIZE];
for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
expected[j] = values[i * ForUtil.BLOCK_SIZE + j];
diff --git a/lucene/core/src/test/org/apache/lucene/codecs/lucene101/TestLucene101PostingsFormatV0.java b/lucene/core/src/test/org/apache/lucene/codecs/lucene101/TestLucene101PostingsFormatV0.java
new file mode 100644
index 00000000000..037527413ea
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/codecs/lucene101/TestLucene101PostingsFormatV0.java
@@ -0,0 +1,34 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene101;
+
+import org.apache.lucene.codecs.Codec;
+import org.apache.lucene.codecs.lucene90.blocktree.Lucene90BlockTreeTermsWriter;
+import org.apache.lucene.tests.index.BasePostingsFormatTestCase;
+import org.apache.lucene.tests.util.TestUtil;
+
+public class TestLucene101PostingsFormatV0 extends BasePostingsFormatTestCase {
+
+ @Override
+ protected Codec getCodec() {
+ return TestUtil.alwaysPostingsFormat(
+ new Lucene101PostingsFormat(
+ Lucene90BlockTreeTermsWriter.DEFAULT_MIN_BLOCK_SIZE,
+ Lucene90BlockTreeTermsWriter.DEFAULT_MAX_BLOCK_SIZE,
+ Lucene101PostingsFormat.VERSION_START));
+ }
+}