Package org.apache.lucene.util

Class SparseLiveDocs

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

This implementation stores DELETED documents using SparseFixedBitSet, which provides:

  • O(1) random access via get(int)
  • O(deletedDocs) iteration via deletedDocsIterator()
  • Memory usage proportional to number of deleted documents, not total documents

This is most efficient when deletions are sparse. For denser deletions, DenseLiveDocs should be used instead.

Inverted semantics: Unlike typical live docs that store which documents are live, this stores which documents are DELETED. Therefore:

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

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

  • Method Details

    • builder

      public static SparseLiveDocs.Builder builder(SparseFixedBitSet deletedDocs, int maxDoc)
      Creates a builder for constructing SparseLiveDocs instances.
      Parameters:
      deletedDocs - bit set where set bits represent DELETED 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);
   }
 }

      Applying a mask may only ever clear bits, and the only bits it may clear are the deleted documents, so this is a word-level and-not of the deleted documents into the destination rather than the per-bit loop of the default implementation. It runs one word operation per non-zero word of the deleted documents in the window, that is at most one per 64 documents of the window, so its cost is bounded by the size of the window and does not depend on how many bits are set in the destination.

      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