Package org.apache.lucene.util

Class DenseLiveDocs

java.lang.Object
org.apache.lucene.util.DenseLiveDocs
All Implemented Interfaces:
Bits, LiveDocs
public final class DenseLiveDocs extends Object implements LiveDocs
LiveDocs implementation optimized for dense deletions.

This implementation stores LIVE documents using FixedBitSet, which is the traditional approach used by Lucene. This provides:

  • O(1) random access via get(int)
  • Memory usage proportional to maxDoc
  • Efficient iteration over live documents

This is most efficient when deletions are dense. For sparser deletions, SparseLiveDocs should be used instead.

Standard semantics: Set bits represent LIVE documents, which is the traditional Lucene approach:

Immutability: This class is immutable once constructed. Instances are typically created using the DenseLiveDocs.Builder via builder(FixedBitSet, int).

WARNING: This API is experimental and might change in incompatible ways in the next release.

  • Method Details

    • builder

      public static DenseLiveDocs.Builder builder(FixedBitSet liveDocs, int maxDoc)
      Creates a builder for constructing DenseLiveDocs instances.
      Parameters:
      liveDocs - bit set where set bits represent LIVE documents
      maxDoc - the maximum document ID (exclusive)
      Returns:
      a new builder instance

    • get

      public boolean get(int index)
      Description copied from interface: Bits
      Returns the value of the bit with the specified index.
      Specified by:
      get in interface Bits
      Parameters:
      index - index, should be non-negative and < Bits.length(). The result of passing negative or out of bounds values is undefined by this interface, just don't do it!
      Returns:
      true if the bit is set, false otherwise.

    • length

      public int length()
      Description copied from interface: Bits
      Returns the number of bits in this set
      Specified by:
      length in interface Bits

    • applyMask

      public void applyMask(FixedBitSet bitSet, int offset)
      Apply this Bits instance to the given FixedBitSet, which starts at the given offset.

      offset must be non-negative. For each index i into bitSet, if bitSet.get(i) is set then offset + i must be less than Bits.length(): bits of bitSet whose corresponding index into this instance is out of range are not covered. Implementations that can detect such a bit cheaply -- FixedBitSet.applyMask(org.apache.lucene.util.FixedBitSet, int) and the LiveDocs implementations do -- throw IllegalArgumentException; the default implementation below reads Bits.get(int) out of bounds instead, which is undefined per Bits.get(int).

      Apart from that, this should behave the same way as the default implementation, which does the following: 

       for (int i = bitSet.nextSetBit(0);
     i != DocIdSetIterator.NO_MORE_DOCS;
     i = i + 1 >= bitSet.length() ? DocIdSetIterator.NO_MORE_DOCS : bitSet.nextSetBit(i + 1)) {
   if (get(offset + i) == false) {
     bitSet.clear(i);
   }
 }

      Live documents are stored in a FixedBitSet, so the mask is applied with a word-wise AND through FixedBitSet.andRange(org.apache.lucene.util.FixedBitSet, int, org.apache.lucene.util.FixedBitSet, int, int), which auto-vectorizes. Writing w for the number of bits of bitSet that this instance covers, this reads and writes w/64 words whatever bitSet contains. The default implementation walks bitSet with FixedBitSet.nextSetBit(int), which reads the same w/64 words one at a time, and additionally calls get(int) once per set bit. One vectorized word AND is roughly an order of magnitude cheaper than one get, so this implementation is the cheaper of the two from a handful of set bits per window upwards, and the gap grows linearly with the number of set bits from there. Callers therefore do not need to measure the density of bitSet first, and most do not: below the crossover the two are within a few tens of nanoseconds per window, and for a w of a few thousand bits FixedBitSet.cardinality() costs about as much as the mask itself.

      Same structure as FixedBitSet.applyMask(org.apache.lucene.util.FixedBitSet, int), bounded on maxDoc rather than liveDocs.length() when the backing bit set is padded.

      Specified by:
      applyMask in interface Bits
      Throws:
      IllegalArgumentException - unless every set bit of bitSet at index i satisfies offset + i < maxDoc

    • liveDocsIterator

      public DocIdSetIterator liveDocsIterator()
      Description copied from interface: LiveDocs
      Returns an iterator over live document IDs.

      The returned iterator provides sequential access to all live documents in ascending order. The iteration complexity depends on the implementation:

      • For sparse deletions: O(maxDoc) - may need to scan all documents
      • For dense deletions: O(liveDocs) - only visits live documents

      Callers can use DocIdSetIterator.cost() to determine the expected number of live documents.

      Specified by:
      liveDocsIterator in interface LiveDocs
      Returns:
      an iterator over live document IDs

    • deletedDocsIterator

      public DocIdSetIterator deletedDocsIterator()
      Description copied from interface: LiveDocs
      Returns an iterator over deleted document IDs.

      The returned iterator provides sequential access to all deleted documents in ascending order. The iteration complexity depends on the implementation:

      • For sparse deletions: O(deletedDocs) - only visits deleted documents
      • For dense deletions: O(maxDoc) - may need to scan all documents

      Callers can use DocIdSetIterator.cost() to determine if sparse iteration would be beneficial for their use case.

      Specified by:
      deletedDocsIterator in interface LiveDocs
      Returns:
      an iterator over deleted document IDs, or an empty iterator if no documents are deleted

    • deletedCount

      public int deletedCount()
      Description copied from interface: LiveDocs
      Returns the number of deleted documents.

      This can be used to determine deletion density and choose appropriate algorithms.

      Specified by:
      deletedCount in interface LiveDocs
      Returns:
      the number of deleted documents in this segment

    • ramBytesUsed

      public long ramBytesUsed()
      Returns the memory usage in bytes.
      Returns:
      estimated memory usage in bytes

    • toString

      public String toString()
      Overrides:
      toString in class Object