You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "shubhamvishu (via GitHub)" <gi...@apache.org> on 2025/07/30 13:40:44 UTC

[PR] Add AcceptDocs interface for accepted KNN docs [lucene]

shubhamvishu opened a new pull request, #15011:
URL: https://github.com/apache/lucene/pull/15011

   ### Description
   
   
   Addresses [this comment](https://github.com/apache/lucene/pull/14963#issuecomment-3092568029) on the PR #14963 to allow both sequential and random access consumption for accepted docs in KNN search.
   
   <!--
   If this is your first contribution to Lucene, please make sure you have reviewed the contribution guide.
   https://github.com/apache/lucene/blob/main/CONTRIBUTING.md
   -->
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2296348156


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,215 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.Objects;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.IOSupplier;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if all documents are accepted
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Create a new iterator of accepted docs. There accepted docs already ignore deleted docs.
+   *
+   * <p><b>NOTE</b>: If you also plan on calling {@link #bits()} or {@link #cost()}, it is
+   * recommended to call these methods before {@link #iterator()} for better performance.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents. This is typically useful to decide
+   * whether to consume these accept docs using random access ({@link #bits()}) or sequential access
+   * ({@link #iterator()}).
+   *
+   * <p><b>NOTE</b>: This must not be called after {@link #iterator()}.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost() throws IOException;
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from an {@link IOSupplier} of {@link DocIdSetIterator}, optionally filtered
+   * by live documents.
+   *
+   * @param iteratorSupplier a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if no deleted docs.
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIteratorSupplier(
+      IOSupplier<DocIdSetIterator> iteratorSupplier, Bits liveDocs, int maxDoc) {
+    return new DocIdSetIteratorAcceptDocs(iteratorSupplier, liveDocs, maxDoc);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        return BitSet.of(
+            AcceptDocs.getFilteredDocIdSetIterator(iterator, liveDocs),
+            maxDoc); // create a sparse bitset
+      }
+    }
+  }
+
+  /**
+   * Impl backed by Bits, expected to be somewhat dense, except when a {@link BitSet} is provided,
+   * in which case it's not necessarily dense.
+   */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private final DocIdSetIterator iterator;
+    private final int maxDoc;
+
+    BitsAcceptDocs(Bits bits, int maxDoc) {
+      this.bits = bits;
+      if (bits instanceof BitSet bitSet) {
+        Objects.requireNonNull(bitSet);
+        this.maxDoc = bitSet.cardinality();
+        this.iterator = new BitSetIterator(bitSet, this.maxDoc);
+      } else {
+        this.maxDoc = maxDoc;
+        this.iterator = AcceptDocs.getFilteredDocIdSetIterator(DocIdSetIterator.all(maxDoc), bits);
+      }
+    }
+
+    @Override
+    public Bits bits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() {
+      return iterator;

Review Comment:
   I kept it as-is as we are not creating in the case of BitsAcceptDocs in the commit. But makes sense to return a new iterator irrespective.
   



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2274711784


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,221 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * <p><b>NOTE</b>: This must not be called if the {@link #iterator()} has already been used.
+   *
+   * @return Bits instance for random access, or null if all documents are accepted
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * <p><b>NOTE</b>: This method doesn't return a new iterator, but a reference to a shared
+   * instance.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents. This is typically useful to decide
+   * whether to consume these accept docs using random access ({@link #bits()}) or sequential access
+   * ({@link #iterator()}).
+   *
+   * <p><b>NOTE</b>: This must not be called if the {@link #iterator()} has already been used.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost() throws IOException;
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    if (bits instanceof BitSet bitSet) {
+      DocIdSetIterator iterator = new BitSetIterator(bitSet, bitSet.approximateCardinality());
+      return new DocIdSetIteratorAcceptDocs(iterator, null, maxDoc);
+    }
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator, optionally filtered by live documents.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if no deleted docs
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    return new DocIdSetIteratorAcceptDocs(iterator, liveDocs, maxDoc);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        if (liveDocs != null) {
+          iterator =
+              new FilteredDocIdSetIterator(iterator) {
+                @Override
+                protected boolean match(int doc) {
+                  return liveDocs.get(doc);
+                }
+              };
+        }
+        return BitSet.of(iterator, maxDoc); // create a sparse bitset
+      }
+    }
+  }
+
+  /** Impl backed by Bits, expected to be somewhat dense. */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private final DocIdSetIterator iterator;
+    private final int maxDoc;
+
+    BitsAcceptDocs(Bits bits, int maxDoc) {
+      this.bits = bits;
+      this.maxDoc = maxDoc;
+      DocIdSetIterator iterator = DocIdSetIterator.all(maxDoc);
+      if (bits != null) {
+        iterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return bits.get(doc);
+              }
+            };
+      }
+      this.iterator = iterator;
+    }
+
+    @Override
+    public Bits bits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() {
+      return iterator;
+    }
+
+    @Override
+    public int cost() {
+      // We have no better estimate. This should be ok in practice since background merges should
+      // keep the number of deletes under control (< 20% by default).
+      return maxDoc;
+    }
+  }
+
+  /** Impl backed by a {@link DocIdSetIterator} */
+  private static class DocIdSetIteratorAcceptDocs extends AcceptDocs {
+
+    private final Bits liveDocs;
+    private final int maxDoc;
+
+    private DocIdSetIterator iterator;
+    private BitSet bitSet = null;
+    private int cardinality = -1;
+
+    DocIdSetIteratorAcceptDocs(DocIdSetIterator iterator, Bits liveDocs, int maxDoc) {
+      this.iterator = iterator;
+      this.liveDocs = liveDocs;
+      this.maxDoc = maxDoc;
+      if (iterator.docID() != -1) {
+        throw new IllegalArgumentException(
+            "Iterator must be unpositioned, but got current doc ID: " + iterator.docID());
+      }
+    }
+
+    /**
+     * The {@link BitSet} is computed lazily so that it is never created in case only the {@link
+     * #iterator} is needed
+     */
+    private void loadIntoBitSetIfNecessary() throws IOException {
+      // Usage of AcceptDocs should be confined to a single thread, so this doesn't need
+      // synchronization.
+      if (bitSet == null) {
+        if (iterator.docID() != -1) {

Review Comment:
   should we check this even if bitSet is not null, for consistency with  the API contract??  As it is we are exposing some internal details -- it's OK to call bits(), then iterator(), consume some of the iterator, and then call bits() again ...



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "ChrisHegarty (via GitHub)" <gi...@apache.org>.
ChrisHegarty commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2272744054


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,181 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost();
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    if (bits instanceof BitSet bitSet) {
+      return new BitSetAcceptDocs(bitSet);
+    }
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator, optionally filtered by live documents.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if no deleted docs
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    BitSet bitSet = createBitSet(iterator, liveDocs, maxDoc);
+    return new BitSetAcceptDocs(bitSet);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        FilteredDocIdSetIterator filterIterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return liveDocs == null || liveDocs.get(doc);
+              }
+            };
+        return BitSet.of(filterIterator, maxDoc); // create a sparse bitset
+      }
+    }
+  }
+
+  /** Impl backed by Bits, expected to be somewhat dense. */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private final int maxDoc;
+
+    BitsAcceptDocs(Bits bits, int maxDoc) {
+      this.bits = bits;
+      this.maxDoc = maxDoc;
+    }
+
+    @Override
+    public Bits bits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() {
+      DocIdSetIterator iterator = DocIdSetIterator.all(maxDoc);
+      if (bits != null) {
+        iterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return bits.get(doc);
+              }
+            };
+      }
+      return iterator;
+    }
+
+    @Override
+    public int cost() {
+      // We have no better estimate. This should be ok in practice since background merges should
+      // keep the number of deletes under control (< 20% by default).
+      return maxDoc;
+    }
+  }
+
+  /** Impl backed by a {@link BitSet} */
+  private static class BitSetAcceptDocs extends AcceptDocs {
+
+    private final BitSet bitSet;
+    private int cardinality = -1;
+
+    BitSetAcceptDocs(BitSet bitSet) {
+      this.bitSet = bitSet;
+    }
+
+    @Override
+    public Bits bits() throws IOException {
+      return bitSet;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() throws IOException {
+      return new BitSetIterator(bitSet, cost());
+    }
+
+    @Override
+    public synchronized int cost() {

Review Comment:
   why is this `synchronized`?  I there any expectation of thread-safety of AcceptedDocs ?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz merged PR #15011:
URL: https://github.com/apache/lucene/pull/15011


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2270727974


##########
lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsReader.java:
##########
@@ -332,20 +332,19 @@ private void search(
     final RandomVectorScorer scorer = scorerSupplier.get();
     final KnnCollector collector =
         new OrdinalTranslatedKnnCollector(knnCollector, scorer::ordToDoc);
-    final Bits acceptedOrds = scorer.getAcceptOrds(acceptDocs);
+    Bits accepted = acceptDocs.bits();
+    final Bits acceptedOrds = scorer.getAcceptOrds(accepted);
     HnswGraph graph = getGraph(fieldEntry);
     boolean doHnsw = knnCollector.k() < scorer.maxOrd();
     // Take into account if quantized? E.g. some scorer cost?
     int filteredDocCount = 0;
     // The approximate number of vectors that would be visited if we did not filter
     int unfilteredVisit = HnswGraphSearcher.expectedVisitedNodes(knnCollector.k(), graph.size());
-    if (acceptDocs instanceof BitSet bitSet) {
-      // Use approximate cardinality as this is good enough, but ensure we don't exceed the graph
-      // size as that is illogical
-      filteredDocCount = Math.min(bitSet.approximateCardinality(), graph.size());
-      if (unfilteredVisit >= filteredDocCount) {
-        doHnsw = false;
-      }
+    // Use approximate cardinality as this is good enough, but ensure we don't exceed the graph
+    // size as that is illogical
+    filteredDocCount = Math.min(acceptDocs.cost(), graph.size());
+    if (unfilteredVisit >= filteredDocCount) {
+      doHnsw = false;

Review Comment:
   ❤️ 



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2296344655


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,215 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.Objects;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.IOSupplier;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if all documents are accepted
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Create a new iterator of accepted docs. There accepted docs already ignore deleted docs.
+   *
+   * <p><b>NOTE</b>: If you also plan on calling {@link #bits()} or {@link #cost()}, it is
+   * recommended to call these methods before {@link #iterator()} for better performance.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents. This is typically useful to decide
+   * whether to consume these accept docs using random access ({@link #bits()}) or sequential access
+   * ({@link #iterator()}).
+   *
+   * <p><b>NOTE</b>: This must not be called after {@link #iterator()}.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost() throws IOException;
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from an {@link IOSupplier} of {@link DocIdSetIterator}, optionally filtered
+   * by live documents.
+   *
+   * @param iteratorSupplier a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if no deleted docs.
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIteratorSupplier(
+      IOSupplier<DocIdSetIterator> iteratorSupplier, Bits liveDocs, int maxDoc) {
+    return new DocIdSetIteratorAcceptDocs(iteratorSupplier, liveDocs, maxDoc);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        return BitSet.of(
+            AcceptDocs.getFilteredDocIdSetIterator(iterator, liveDocs),
+            maxDoc); // create a sparse bitset
+      }
+    }
+  }
+
+  /**
+   * Impl backed by Bits, expected to be somewhat dense, except when a {@link BitSet} is provided,
+   * in which case it's not necessarily dense.
+   */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private final DocIdSetIterator iterator;
+    private final int maxDoc;
+
+    BitsAcceptDocs(Bits bits, int maxDoc) {
+      this.bits = bits;
+      if (bits instanceof BitSet bitSet) {
+        Objects.requireNonNull(bitSet);
+        this.maxDoc = bitSet.cardinality();
+        this.iterator = new BitSetIterator(bitSet, this.maxDoc);
+      } else {
+        this.maxDoc = maxDoc;
+        this.iterator = AcceptDocs.getFilteredDocIdSetIterator(DocIdSetIterator.all(maxDoc), bits);
+      }
+    }
+
+    @Override
+    public Bits bits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() {
+      return iterator;

Review Comment:
   Hmm, we also need to create a new iterator in the case when it's backed by DocIdSetIterator#all?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2283075317


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,221 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * <p><b>NOTE</b>: This must not be called if the {@link #iterator()} has already been used.

Review Comment:
   I understand from your above main comment that we don't want to load the matches in the bitset incase of flat scorer but it seems to me that allowing would make the api contract simple(but at the cost of doing unneccessary work)....Is that correct? If yes, could we somehow avoid only undesirable loading at the same time keeping the contract simple(with no restrictions)?
   
   Basically I was considering that if user doesn't call `bits()` or `cost()` before calling `iterator()`, we return the same iterator(without loading or creating  the BitSet), and the iterator wouldn't filter out the deletes i.e. the iterator wouldn't be a conjunction over live docs, as we previously decided. So was thinking if we could allow the caller to access both `bits` and `iterator` as needed? maybe its not that simple or the extra cost to pay if not worth?
   



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2243394074


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,194 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.List;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available

Review Comment:
   I think we should apply the usual contract that a `null` Bits instance means that all docs are accepted?
   
   ```suggestion
      * @return Bits instance for random access, or null if all documents are accepted
   ```



##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,194 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.List;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits getBits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator getIterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract long cost();
+
+  /**
+   * Create AcceptDocs from a Bits instance.
+   *
+   * @param bits the Bits instance for random access
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromBits(Bits bits) {
+    if (bits == null) {
+      return new AcceptAllDocs();
+    }
+    return new BitsAcceptDocs(bits);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, int maxDoc) {
+    if (iterator == null) {
+      return new AcceptAllDocs();
+    }
+    return new IteratorAcceptDocs(iterator, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a conjunction of DocIdSetIterators
+   *
+   * @param disiList list of required iterators
+   * @return AcceptDocs wrapping the conjunction
+   */
+  public static AcceptDocs fromConjunction(List<DocIdSetIterator> disiList, int maxDoc) {
+    if (disiList.isEmpty()) {
+      return new AcceptAllDocs();
+    }
+    if (disiList.size() == 1) {
+      return new IteratorAcceptDocs(disiList.getFirst(), maxDoc);
+    }
+    return new IteratorAcceptDocs(ConjunctionDISI.createConjunction(disiList, List.of()), maxDoc);
+  }
+
+  /** Impl that accepts all documents. */
+  private static class AcceptAllDocs extends AcceptDocs {
+    @Override
+    public Bits getBits() {
+      return null;
+    }
+
+    @Override
+    public DocIdSetIterator getIterator() {
+      return DocIdSetIterator.all(Integer.MAX_VALUE);
+    }
+
+    @Override
+    public long cost() {
+      return Integer.MAX_VALUE;
+    }
+  }
+
+  /** Impl backed by Bits */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private DocIdSetIterator iterator;
+    private final long cost;
+
+    BitsAcceptDocs(Bits bits) {
+      this.bits = bits;
+      // estimated cost
+      if (bits instanceof BitSet bitSet) {
+        this.cost = bitSet.cardinality();
+      } else {
+        this.cost = bits.length();
+      }
+    }
+
+    @Override
+    public Bits getBits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator getIterator() {
+      if (iterator == null) {
+        if (bits instanceof BitSet bitSet) {
+          iterator = new BitSetIterator(bitSet, cost);
+        } else {
+          FixedBitSet bitSet = new FixedBitSet(bits.length());
+          for (int i = 0; i < bits.length(); i++) {
+            if (bits.get(i)) {
+              bitSet.set(i);
+            }
+          }
+          iterator = new BitSetIterator(bitSet, bitSet.cardinality());

Review Comment:
   I wouldn't materlialize a `FixedBitSet`. Let's return a `FilteredDocIdSetIterator` on top of a `DocIdSetIteartor.all(bits.length())` that excludes non-matching docs?



##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,194 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.List;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits getBits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator getIterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract long cost();
+
+  /**
+   * Create AcceptDocs from a Bits instance.
+   *
+   * @param bits the Bits instance for random access
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromBits(Bits bits) {
+    if (bits == null) {
+      return new AcceptAllDocs();
+    }
+    return new BitsAcceptDocs(bits);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, int maxDoc) {
+    if (iterator == null) {
+      return new AcceptAllDocs();

Review Comment:
   In other places (e.g. `Weight#scorer`), a `null` `DocIdSetIterator` means that there are no matches. I think we should either reject null iterators or treat it as an `AcceptNoDocs` 



##########
lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswVectorsReader.java:
##########
@@ -260,7 +261,7 @@ public void search(String field, float[] target, KnnCollector knnCollector, Bits
             vectorValues,
             fieldEntry.similarityFunction,
             getGraphValues(fieldEntry),
-            getAcceptOrds(acceptDocs, fieldEntry),
+            getAcceptOrds(acceptDocs != null ? acceptDocs.getBits() : null, fieldEntry),

Review Comment:
   Should we set the contract of this method so that `acceptDocs` is not allowed to be `null`? This would help save all these (annoying) null checks, and it wouldn't be a great burden on the caller side?



##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,194 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.List;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits getBits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator getIterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract long cost();
+
+  /**
+   * Create AcceptDocs from a Bits instance.
+   *
+   * @param bits the Bits instance for random access
+   * @return AcceptDocs wrapping the Bits
+   */

Review Comment:
   Can you say in the javadocs that if the bits are null then this will match all docs?



##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,194 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.List;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits getBits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator getIterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract long cost();
+
+  /**
+   * Create AcceptDocs from a Bits instance.
+   *
+   * @param bits the Bits instance for random access
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromBits(Bits bits) {
+    if (bits == null) {
+      return new AcceptAllDocs();
+    }
+    return new BitsAcceptDocs(bits);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, int maxDoc) {
+    if (iterator == null) {
+      return new AcceptAllDocs();
+    }
+    return new IteratorAcceptDocs(iterator, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a conjunction of DocIdSetIterators
+   *
+   * @param disiList list of required iterators
+   * @return AcceptDocs wrapping the conjunction
+   */
+  public static AcceptDocs fromConjunction(List<DocIdSetIterator> disiList, int maxDoc) {
+    if (disiList.isEmpty()) {
+      return new AcceptAllDocs();
+    }
+    if (disiList.size() == 1) {
+      return new IteratorAcceptDocs(disiList.getFirst(), maxDoc);
+    }
+    return new IteratorAcceptDocs(ConjunctionDISI.createConjunction(disiList, List.of()), maxDoc);
+  }
+
+  /** Impl that accepts all documents. */
+  private static class AcceptAllDocs extends AcceptDocs {
+    @Override
+    public Bits getBits() {
+      return null;
+    }
+
+    @Override
+    public DocIdSetIterator getIterator() {
+      return DocIdSetIterator.all(Integer.MAX_VALUE);
+    }
+
+    @Override
+    public long cost() {
+      return Integer.MAX_VALUE;

Review Comment:
   Maybe the constructor should take a `maxDoc` argument like the iterator-based impl so that we could return it here?



##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,194 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.List;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits getBits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator getIterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract long cost();
+
+  /**
+   * Create AcceptDocs from a Bits instance.
+   *
+   * @param bits the Bits instance for random access
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromBits(Bits bits) {
+    if (bits == null) {
+      return new AcceptAllDocs();
+    }
+    return new BitsAcceptDocs(bits);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, int maxDoc) {
+    if (iterator == null) {
+      return new AcceptAllDocs();
+    }
+    return new IteratorAcceptDocs(iterator, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a conjunction of DocIdSetIterators
+   *
+   * @param disiList list of required iterators
+   * @return AcceptDocs wrapping the conjunction
+   */
+  public static AcceptDocs fromConjunction(List<DocIdSetIterator> disiList, int maxDoc) {
+    if (disiList.isEmpty()) {
+      return new AcceptAllDocs();
+    }
+    if (disiList.size() == 1) {
+      return new IteratorAcceptDocs(disiList.getFirst(), maxDoc);
+    }
+    return new IteratorAcceptDocs(ConjunctionDISI.createConjunction(disiList, List.of()), maxDoc);
+  }

Review Comment:
   The only call site of this factory method calls it with exactly two iterators. For simplicity, I'd rather remove this factory method and change the call site to call `fromIterator` with a `ConjunctionDISI`?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3172054358

   This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3166619513

   @shubhamvishu I hope you don't mind, I addressed my feedback directly on your branch.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2290846557


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,221 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * <p><b>NOTE</b>: This must not be called if the {@link #iterator()} has already been used.

Review Comment:
   > it seems to me that allowing would make the api contract simple(but at the cost of doing unneccessary work)....Is that correct?
   
   This is correct! I agree with your sentiment, I got there because I wanted to avoid some performance traps, but it has gone too far, the API contract is too complex. I pushed a change so that it's legal to call the methods in any order, it just happens to be a bit more efficient to call bits() before iterator() than iterator() before bits().



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3166636057

   We will also need to move the decision between approximate and exact to the codec, but it's probably best done as a follow-up PR? I think that this change is good as-is.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2270139493


##########
lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsReader.java:
##########
@@ -332,14 +333,15 @@ private void search(
     final RandomVectorScorer scorer = scorerSupplier.get();
     final KnnCollector collector =
         new OrdinalTranslatedKnnCollector(knnCollector, scorer::ordToDoc);
-    final Bits acceptedOrds = scorer.getAcceptOrds(acceptDocs);
+    Bits accepted = acceptDocs.bits();
+    final Bits acceptedOrds = scorer.getAcceptOrds(accepted);
     HnswGraph graph = getGraph(fieldEntry);
     boolean doHnsw = knnCollector.k() < scorer.maxOrd();
     // Take into account if quantized? E.g. some scorer cost?
     int filteredDocCount = 0;
     // The approximate number of vectors that would be visited if we did not filter
     int unfilteredVisit = HnswGraphSearcher.expectedVisitedNodes(knnCollector.k(), graph.size());
-    if (acceptDocs instanceof BitSet bitSet) {
+    if (accepted instanceof BitSet bitSet) {

Review Comment:
   I agree it's better to do this in this PR than in a follow-up. @shubhamvishu would you like to fix this?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2265169581


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,181 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost();
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    if (bits instanceof BitSet bitSet) {
+      return new BitSetAcceptDocs(bitSet);
+    }
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator, optionally filtered by live documents.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    BitSet bitSet = createBitSet(iterator, liveDocs, maxDoc);
+    return new BitSetAcceptDocs(bitSet);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        FilteredDocIdSetIterator filterIterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return liveDocs == null || liveDocs.get(doc);
+              }
+            };
+        return BitSet.of(filterIterator, maxDoc); // create a sparse bitset
+      }
+    }
+  }
+
+  /** Impl backed by Bits, expected to be somewhat dense. */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private final int maxDoc;
+
+    BitsAcceptDocs(Bits bits, int maxDoc) {
+      this.bits = bits;
+      this.maxDoc = maxDoc;
+    }
+
+    @Override
+    public Bits bits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() {
+      DocIdSetIterator iterator = DocIdSetIterator.all(maxDoc);
+      if (bits != null) {
+        iterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return bits.get(doc);
+              }
+            };
+      }
+      return iterator;
+    }
+
+    @Override
+    public int cost() {
+      // We have no better estimate. This should be ok in practice since background merges should
+      // keep the number of deletes under control (< 20% by default).
+      return maxDoc;
+    }
+  }
+
+  /** Impl backed by a {@link BitSet} */
+  private static class BitSetAcceptDocs extends AcceptDocs {
+
+    private final BitSet bitSet;
+    private int cardinality = -1;
+
+    BitSetAcceptDocs(BitSet bitSet) {
+      this.bitSet = bitSet;
+    }
+
+    @Override
+    public Bits bits() throws IOException {
+      return bitSet;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() throws IOException {
+      return new BitSetIterator(bitSet, cost());
+    }
+
+    @Override
+    public synchronized int cost() {
+      if (cardinality == -1) {
+        cardinality = bitSet.cardinality();

Review Comment:
   Oh, that's correct. I missed that.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "ChrisHegarty (via GitHub)" <gi...@apache.org>.
ChrisHegarty commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2272779350


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,181 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost();
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    if (bits instanceof BitSet bitSet) {
+      return new BitSetAcceptDocs(bitSet);
+    }
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator, optionally filtered by live documents.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if no deleted docs
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    BitSet bitSet = createBitSet(iterator, liveDocs, maxDoc);
+    return new BitSetAcceptDocs(bitSet);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        FilteredDocIdSetIterator filterIterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return liveDocs == null || liveDocs.get(doc);
+              }
+            };
+        return BitSet.of(filterIterator, maxDoc); // create a sparse bitset

Review Comment:
   ```suggestion
           if (liveDocs != null) {
             iterator =
                 new FilteredDocIdSetIterator(iterator) {
                   @Override
                   protected boolean match(int doc) {
                     return liveDocs.get(doc);
                   }
                 };
           }
           return BitSet.of(iterator, maxDoc); // create a sparse bitset
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3166619703

   This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3166631527

   This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2274724679


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,221 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * <p><b>NOTE</b>: This must not be called if the {@link #iterator()} has already been used.

Review Comment:
   You are right. The original iterator will be consumed to create the bit set and replaced with an iterator over the bit set.
   
   So we should disallow calling bits() or cardinality() after iterator()?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2296303704


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,215 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.Objects;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.IOSupplier;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if all documents are accepted
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Create a new iterator of accepted docs. There accepted docs already ignore deleted docs.
+   *
+   * <p><b>NOTE</b>: If you also plan on calling {@link #bits()} or {@link #cost()}, it is
+   * recommended to call these methods before {@link #iterator()} for better performance.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents. This is typically useful to decide
+   * whether to consume these accept docs using random access ({@link #bits()}) or sequential access
+   * ({@link #iterator()}).
+   *
+   * <p><b>NOTE</b>: This must not be called after {@link #iterator()}.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost() throws IOException;
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from an {@link IOSupplier} of {@link DocIdSetIterator}, optionally filtered
+   * by live documents.
+   *
+   * @param iteratorSupplier a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if no deleted docs.
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIteratorSupplier(
+      IOSupplier<DocIdSetIterator> iteratorSupplier, Bits liveDocs, int maxDoc) {
+    return new DocIdSetIteratorAcceptDocs(iteratorSupplier, liveDocs, maxDoc);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        return BitSet.of(
+            AcceptDocs.getFilteredDocIdSetIterator(iterator, liveDocs),
+            maxDoc); // create a sparse bitset
+      }
+    }
+  }
+
+  /**
+   * Impl backed by Bits, expected to be somewhat dense, except when a {@link BitSet} is provided,
+   * in which case it's not necessarily dense.
+   */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private final DocIdSetIterator iterator;
+    private final int maxDoc;
+
+    BitsAcceptDocs(Bits bits, int maxDoc) {
+      this.bits = bits;
+      if (bits instanceof BitSet bitSet) {
+        Objects.requireNonNull(bitSet);
+        this.maxDoc = bitSet.cardinality();
+        this.iterator = new BitSetIterator(bitSet, this.maxDoc);
+      } else {
+        this.maxDoc = maxDoc;
+        this.iterator = AcceptDocs.getFilteredDocIdSetIterator(DocIdSetIterator.all(maxDoc), bits);
+      }
+    }
+
+    @Override
+    public Bits bits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() {
+      return iterator;

Review Comment:
   With my most recent commit, this is now supposed to return a new iterator, so we need to move the iterator instantiation from the ctor to here?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2273694892


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,181 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;

Review Comment:
   I guess I was thinking of lazily creating the bitset in this method at first, so it would need the `IOException`. But actually we always need the cardinality of the bitset to decide between random access and sequential access now, so maybe we could simplify things and make `AcceptDocs` a record around `Bits` and a `DocIdSetIterator`. So no exception, no lazy computation of `cost()` (to you other comment).



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2281029935


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,221 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * <p><b>NOTE</b>: This must not be called if the {@link #iterator()} has already been used.

Review Comment:
   It looks like forbidding `#cost()` or `#bits()` to be called after `#iterator()` works with current impls, so I pushed this change.
   
   If you call `#iterator()` first, you will get the original iterator, if you call it after one of the two other methods, the original iterator will be loaded into a bit set and `#iterator()` will return an iterator over the bit set.
   
   @shubhamvishu Sorry, I don't get your point?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2264622889


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,181 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost();
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    if (bits instanceof BitSet bitSet) {
+      return new BitSetAcceptDocs(bitSet);
+    }
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator, optionally filtered by live documents.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    BitSet bitSet = createBitSet(iterator, liveDocs, maxDoc);
+    return new BitSetAcceptDocs(bitSet);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        FilteredDocIdSetIterator filterIterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return liveDocs == null || liveDocs.get(doc);
+              }
+            };
+        return BitSet.of(filterIterator, maxDoc); // create a sparse bitset
+      }
+    }
+  }
+
+  /** Impl backed by Bits, expected to be somewhat dense. */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private final int maxDoc;
+
+    BitsAcceptDocs(Bits bits, int maxDoc) {
+      this.bits = bits;
+      this.maxDoc = maxDoc;
+    }
+
+    @Override
+    public Bits bits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() {
+      DocIdSetIterator iterator = DocIdSetIterator.all(maxDoc);
+      if (bits != null) {
+        iterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return bits.get(doc);
+              }
+            };
+      }
+      return iterator;
+    }
+
+    @Override
+    public int cost() {
+      // We have no better estimate. This should be ok in practice since background merges should
+      // keep the number of deletes under control (< 20% by default).
+      return maxDoc;
+    }
+  }
+
+  /** Impl backed by a {@link BitSet} */
+  private static class BitSetAcceptDocs extends AcceptDocs {
+
+    private final BitSet bitSet;
+    private int cardinality = -1;
+
+    BitSetAcceptDocs(BitSet bitSet) {
+      this.bitSet = bitSet;
+    }
+
+    @Override
+    public Bits bits() throws IOException {
+      return bitSet;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() throws IOException {
+      return new BitSetIterator(bitSet, cost());
+    }
+
+    @Override
+    public synchronized int cost() {
+      if (cardinality == -1) {
+        cardinality = bitSet.cardinality();

Review Comment:
   Do we need this check since we never seem to update `cardinality` value from -1?



##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,194 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.List;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits getBits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator getIterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract long cost();
+
+  /**
+   * Create AcceptDocs from a Bits instance.
+   *
+   * @param bits the Bits instance for random access
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromBits(Bits bits) {
+    if (bits == null) {
+      return new AcceptAllDocs();
+    }
+    return new BitsAcceptDocs(bits);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, int maxDoc) {
+    if (iterator == null) {
+      return new AcceptAllDocs();
+    }
+    return new IteratorAcceptDocs(iterator, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a conjunction of DocIdSetIterators
+   *
+   * @param disiList list of required iterators
+   * @return AcceptDocs wrapping the conjunction
+   */
+  public static AcceptDocs fromConjunction(List<DocIdSetIterator> disiList, int maxDoc) {
+    if (disiList.isEmpty()) {
+      return new AcceptAllDocs();
+    }
+    if (disiList.size() == 1) {
+      return new IteratorAcceptDocs(disiList.getFirst(), maxDoc);
+    }
+    return new IteratorAcceptDocs(ConjunctionDISI.createConjunction(disiList, List.of()), maxDoc);
+  }

Review Comment:
   I like this simplification! <3



##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,181 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost();
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    if (bits instanceof BitSet bitSet) {
+      return new BitSetAcceptDocs(bitSet);
+    }
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator, optionally filtered by live documents.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if

Review Comment:
   ```suggestion
      * @param liveDocs Bits representing live documents, or {@code null} if no deleted docs
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2293862761


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,221 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * <p><b>NOTE</b>: This must not be called if the {@link #iterator()} has already been used.

Review Comment:
   This looks good to me!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3407645119

   > We will also need to move the decision between approximate and exact to the codec
   
   @jpountz do you mean moving the [`exactSearch`](https://github.com/apache/lucene/blob/8e8e37d9e94c290cf8d02e9f318e601baedf28bc/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java#L302) functionality down to the codec?
   
   If so, I think it could be useful in optimizations like #12820 too, where the main overhead is passing / re-creating information from ordinal-space to docid-space (i.e. the "visited" `BitSet` in our case) -- which could be avoided if exact search was done in ordinal-space..


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2281033550


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,221 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * <p><b>NOTE</b>: This must not be called if the {@link #iterator()} has already been used.
+   *
+   * @return Bits instance for random access, or null if all documents are accepted
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * <p><b>NOTE</b>: This method doesn't return a new iterator, but a reference to a shared
+   * instance.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents. This is typically useful to decide
+   * whether to consume these accept docs using random access ({@link #bits()}) or sequential access
+   * ({@link #iterator()}).
+   *
+   * <p><b>NOTE</b>: This must not be called if the {@link #iterator()} has already been used.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost() throws IOException;
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    if (bits instanceof BitSet bitSet) {
+      DocIdSetIterator iterator = new BitSetIterator(bitSet, bitSet.approximateCardinality());
+      return new DocIdSetIteratorAcceptDocs(iterator, null, maxDoc);
+    }
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator, optionally filtered by live documents.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if no deleted docs
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    return new DocIdSetIteratorAcceptDocs(iterator, liveDocs, maxDoc);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        if (liveDocs != null) {
+          iterator =
+              new FilteredDocIdSetIterator(iterator) {
+                @Override
+                protected boolean match(int doc) {
+                  return liveDocs.get(doc);
+                }
+              };
+        }
+        return BitSet.of(iterator, maxDoc); // create a sparse bitset
+      }
+    }
+  }
+
+  /** Impl backed by Bits, expected to be somewhat dense. */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private final DocIdSetIterator iterator;
+    private final int maxDoc;
+
+    BitsAcceptDocs(Bits bits, int maxDoc) {
+      this.bits = bits;
+      this.maxDoc = maxDoc;
+      DocIdSetIterator iterator = DocIdSetIterator.all(maxDoc);
+      if (bits != null) {
+        iterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return bits.get(doc);
+              }
+            };
+      }
+      this.iterator = iterator;
+    }
+
+    @Override
+    public Bits bits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() {
+      return iterator;
+    }
+
+    @Override
+    public int cost() {
+      // We have no better estimate. This should be ok in practice since background merges should
+      // keep the number of deletes under control (< 20% by default).
+      return maxDoc;
+    }
+  }
+
+  /** Impl backed by a {@link DocIdSetIterator} */
+  private static class DocIdSetIteratorAcceptDocs extends AcceptDocs {
+
+    private final Bits liveDocs;
+    private final int maxDoc;
+
+    private DocIdSetIterator iterator;
+    private BitSet bitSet = null;
+    private int cardinality = -1;
+
+    DocIdSetIteratorAcceptDocs(DocIdSetIterator iterator, Bits liveDocs, int maxDoc) {
+      this.iterator = iterator;
+      this.liveDocs = liveDocs;
+      this.maxDoc = maxDoc;
+      if (iterator.docID() != -1) {
+        throw new IllegalArgumentException(
+            "Iterator must be unpositioned, but got current doc ID: " + iterator.docID());
+      }
+    }
+
+    /**
+     * The {@link BitSet} is computed lazily so that it is never created in case only the {@link
+     * #iterator} is needed
+     */
+    private void loadIntoBitSetIfNecessary() throws IOException {
+      // Usage of AcceptDocs should be confined to a single thread, so this doesn't need
+      // synchronization.
+      if (bitSet == null) {
+        if (iterator.docID() != -1) {

Review Comment:
   It's not checked all the time.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3182671084

   @benwtrent I opened #15057 with the details of the test failure


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3185884131

   One of Chris' comment helped me realize that we would still load filter matches into a `BitSet` with a flat scorer, which is undesirable. So I pushed a change that makes the loading into a bitset lazy, so that if a flat `KnnVectorsReader` only calls `AcceptDocs#iterator` but neither `#cost()` nor `#bits()` then we'd never load matches into a bitset. I had to restrict the contract of `AcceptDocs` so that it's illegal ta call `#cost()` nor `#bits()` after the iterator has advanced.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2264938839


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,181 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost();
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    if (bits instanceof BitSet bitSet) {
+      return new BitSetAcceptDocs(bitSet);
+    }
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator, optionally filtered by live documents.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    BitSet bitSet = createBitSet(iterator, liveDocs, maxDoc);
+    return new BitSetAcceptDocs(bitSet);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        FilteredDocIdSetIterator filterIterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return liveDocs == null || liveDocs.get(doc);
+              }
+            };
+        return BitSet.of(filterIterator, maxDoc); // create a sparse bitset
+      }
+    }
+  }
+
+  /** Impl backed by Bits, expected to be somewhat dense. */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private final int maxDoc;
+
+    BitsAcceptDocs(Bits bits, int maxDoc) {
+      this.bits = bits;
+      this.maxDoc = maxDoc;
+    }
+
+    @Override
+    public Bits bits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() {
+      DocIdSetIterator iterator = DocIdSetIterator.all(maxDoc);
+      if (bits != null) {
+        iterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return bits.get(doc);
+              }
+            };
+      }
+      return iterator;
+    }
+
+    @Override
+    public int cost() {
+      // We have no better estimate. This should be ok in practice since background merges should
+      // keep the number of deletes under control (< 20% by default).
+      return maxDoc;
+    }
+  }
+
+  /** Impl backed by a {@link BitSet} */
+  private static class BitSetAcceptDocs extends AcceptDocs {
+
+    private final BitSet bitSet;
+    private int cardinality = -1;
+
+    BitSetAcceptDocs(BitSet bitSet) {
+      this.bitSet = bitSet;
+    }
+
+    @Override
+    public Bits bits() throws IOException {
+      return bitSet;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() throws IOException {
+      return new BitSetIterator(bitSet, cost());
+    }
+
+    @Override
+    public synchronized int cost() {
+      if (cardinality == -1) {
+        cardinality = bitSet.cardinality();

Review Comment:
   We do it in AbstractKnnVectorQuery when deciding between exact search and approximate search, don't we?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2296350692


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,215 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.Objects;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.IOSupplier;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if all documents are accepted
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Create a new iterator of accepted docs. There accepted docs already ignore deleted docs.
+   *
+   * <p><b>NOTE</b>: If you also plan on calling {@link #bits()} or {@link #cost()}, it is
+   * recommended to call these methods before {@link #iterator()} for better performance.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents. This is typically useful to decide
+   * whether to consume these accept docs using random access ({@link #bits()}) or sequential access
+   * ({@link #iterator()}).
+   *
+   * <p><b>NOTE</b>: This must not be called after {@link #iterator()}.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost() throws IOException;
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from an {@link IOSupplier} of {@link DocIdSetIterator}, optionally filtered
+   * by live documents.
+   *
+   * @param iteratorSupplier a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if no deleted docs.
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIteratorSupplier(
+      IOSupplier<DocIdSetIterator> iteratorSupplier, Bits liveDocs, int maxDoc) {
+    return new DocIdSetIteratorAcceptDocs(iteratorSupplier, liveDocs, maxDoc);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        return BitSet.of(
+            AcceptDocs.getFilteredDocIdSetIterator(iterator, liveDocs),
+            maxDoc); // create a sparse bitset
+      }
+    }
+  }
+
+  /**
+   * Impl backed by Bits, expected to be somewhat dense, except when a {@link BitSet} is provided,
+   * in which case it's not necessarily dense.
+   */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private final DocIdSetIterator iterator;
+    private final int maxDoc;
+
+    BitsAcceptDocs(Bits bits, int maxDoc) {
+      this.bits = bits;
+      if (bits instanceof BitSet bitSet) {
+        Objects.requireNonNull(bitSet);
+        this.maxDoc = bitSet.cardinality();
+        this.iterator = new BitSetIterator(bitSet, this.maxDoc);
+      } else {
+        this.maxDoc = maxDoc;
+        this.iterator = AcceptDocs.getFilteredDocIdSetIterator(DocIdSetIterator.all(maxDoc), bits);
+      }
+    }
+
+    @Override
+    public Bits bits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() {
+      return iterator;

Review Comment:
   Okay, I updated it. We always return a fresh iterator now with both APIs..



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2296336633


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,215 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.Objects;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.IOSupplier;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if all documents are accepted
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Create a new iterator of accepted docs. There accepted docs already ignore deleted docs.
+   *
+   * <p><b>NOTE</b>: If you also plan on calling {@link #bits()} or {@link #cost()}, it is
+   * recommended to call these methods before {@link #iterator()} for better performance.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents. This is typically useful to decide
+   * whether to consume these accept docs using random access ({@link #bits()}) or sequential access
+   * ({@link #iterator()}).
+   *
+   * <p><b>NOTE</b>: This must not be called after {@link #iterator()}.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost() throws IOException;
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from an {@link IOSupplier} of {@link DocIdSetIterator}, optionally filtered
+   * by live documents.
+   *
+   * @param iteratorSupplier a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if no deleted docs.
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIteratorSupplier(
+      IOSupplier<DocIdSetIterator> iteratorSupplier, Bits liveDocs, int maxDoc) {
+    return new DocIdSetIteratorAcceptDocs(iteratorSupplier, liveDocs, maxDoc);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        return BitSet.of(
+            AcceptDocs.getFilteredDocIdSetIterator(iterator, liveDocs),
+            maxDoc); // create a sparse bitset
+      }
+    }
+  }
+
+  /**
+   * Impl backed by Bits, expected to be somewhat dense, except when a {@link BitSet} is provided,
+   * in which case it's not necessarily dense.
+   */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private final DocIdSetIterator iterator;
+    private final int maxDoc;
+
+    BitsAcceptDocs(Bits bits, int maxDoc) {
+      this.bits = bits;
+      if (bits instanceof BitSet bitSet) {
+        Objects.requireNonNull(bitSet);
+        this.maxDoc = bitSet.cardinality();
+        this.iterator = new BitSetIterator(bitSet, this.maxDoc);
+      } else {
+        this.maxDoc = maxDoc;
+        this.iterator = AcceptDocs.getFilteredDocIdSetIterator(DocIdSetIterator.all(maxDoc), bits);
+      }
+    }
+
+    @Override
+    public Bits bits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() {
+      return iterator;

Review Comment:
   Done. Thanks!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3172624440

   This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3172624106

   This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2269584392


##########
lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsReader.java:
##########
@@ -332,14 +333,15 @@ private void search(
     final RandomVectorScorer scorer = scorerSupplier.get();
     final KnnCollector collector =
         new OrdinalTranslatedKnnCollector(knnCollector, scorer::ordToDoc);
-    final Bits acceptedOrds = scorer.getAcceptOrds(acceptDocs);
+    Bits accepted = acceptDocs.bits();
+    final Bits acceptedOrds = scorer.getAcceptOrds(accepted);
     HnswGraph graph = getGraph(fieldEntry);
     boolean doHnsw = knnCollector.k() < scorer.maxOrd();
     // Take into account if quantized? E.g. some scorer cost?
     int filteredDocCount = 0;
     // The approximate number of vectors that would be visited if we did not filter
     int unfilteredVisit = HnswGraphSearcher.expectedVisitedNodes(knnCollector.k(), graph.size());
-    if (acceptDocs instanceof BitSet bitSet) {
+    if (accepted instanceof BitSet bitSet) {

Review Comment:
   Shouldn't we use `acceptDocs.cost()` instead of casting here?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "ChrisHegarty (via GitHub)" <gi...@apache.org>.
ChrisHegarty commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2272687176


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,181 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;

Review Comment:
   I don't see any requirement for either this `bits` or `iterator` to throw IOException. It can be removed unless there is some other usage not currently in this PR that needs it?



##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,194 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import java.util.List;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available

Review Comment:
   Was this resolved? I do think that "or null if all documents are accepted" is more clear.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2273697477


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,181 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;
+
+  /**
+   * Get an iterator of accepted docs.
+   *
+   * @return DocIdSetIterator for sequential access
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract DocIdSetIterator iterator() throws IOException;
+
+  /**
+   * Return an approximation of the number of accepted documents.
+   *
+   * @return approximate cost
+   */
+  public abstract int cost();
+
+  /**
+   * Create AcceptDocs from a {@link Bits} instance representing live documents. A {@code null}
+   * instance is interpreted as matching all documents, like in {@link LeafReader#getLiveDocs()}.
+   *
+   * @param bits the Bits instance for random access
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the Bits
+   */
+  public static AcceptDocs fromLiveDocs(Bits bits, int maxDoc) {
+    if (bits instanceof BitSet bitSet) {
+      return new BitSetAcceptDocs(bitSet);
+    }
+    return new BitsAcceptDocs(bits, maxDoc);
+  }
+
+  /**
+   * Create AcceptDocs from a DocIdSetIterator, optionally filtered by live documents.
+   *
+   * @param iterator a DocIdSetIterator iterator
+   * @param liveDocs Bits representing live documents, or {@code null} if no deleted docs
+   * @param maxDoc the number of documents in the reader
+   * @return AcceptDocs wrapping the iterator
+   */
+  public static AcceptDocs fromIterator(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    BitSet bitSet = createBitSet(iterator, liveDocs, maxDoc);
+    return new BitSetAcceptDocs(bitSet);
+  }
+
+  private static BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
+      throws IOException {
+    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+      // If we already have a BitSet and no deletions, reuse the BitSet
+      return bitSetIterator.getBitSet();
+    } else {
+      int threshold = maxDoc >> 7; // same as BitSet#of
+      if (iterator.cost() >= threshold) {
+        // take advantage of Disi#intoBitset and Bits#applyMask
+        FixedBitSet bitSet = new FixedBitSet(maxDoc);
+        bitSet.or(iterator);
+        if (liveDocs != null) {
+          liveDocs.applyMask(bitSet, 0);
+        }
+        return bitSet;
+      } else {
+        FilteredDocIdSetIterator filterIterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return liveDocs == null || liveDocs.get(doc);
+              }
+            };
+        return BitSet.of(filterIterator, maxDoc); // create a sparse bitset
+      }
+    }
+  }
+
+  /** Impl backed by Bits, expected to be somewhat dense. */
+  private static class BitsAcceptDocs extends AcceptDocs {
+    private final Bits bits;
+    private final int maxDoc;
+
+    BitsAcceptDocs(Bits bits, int maxDoc) {
+      this.bits = bits;
+      this.maxDoc = maxDoc;
+    }
+
+    @Override
+    public Bits bits() {
+      return bits;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() {
+      DocIdSetIterator iterator = DocIdSetIterator.all(maxDoc);
+      if (bits != null) {
+        iterator =
+            new FilteredDocIdSetIterator(iterator) {
+              @Override
+              protected boolean match(int doc) {
+                return bits.get(doc);
+              }
+            };
+      }
+      return iterator;
+    }
+
+    @Override
+    public int cost() {
+      // We have no better estimate. This should be ok in practice since background merges should
+      // keep the number of deletes under control (< 20% by default).
+      return maxDoc;
+    }
+  }
+
+  /** Impl backed by a {@link BitSet} */
+  private static class BitSetAcceptDocs extends AcceptDocs {
+
+    private final BitSet bitSet;
+    private int cardinality = -1;
+
+    BitSetAcceptDocs(BitSet bitSet) {
+      this.bitSet = bitSet;
+    }
+
+    @Override
+    public Bits bits() throws IOException {
+      return bitSet;
+    }
+
+    @Override
+    public DocIdSetIterator iterator() throws IOException {
+      return new BitSetIterator(bitSet, cost());
+    }
+
+    @Override
+    public synchronized int cost() {

Review Comment:
   AcceptDocs should be confined to a single thread so synchronized shouldn't be required indeed.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3180510392

   @jpountz @benwtrent The test failures seems is unrelated to this change and a side effect of [bulk scoring change](https://github.com/apache/lucene/pull/14978). The test fails on main also when HNSW is disabled to force exhaustive search and we score bulk score 64 docs now. I wonder if we still want to respect the visitedLimit with bulk scoring? If yes, then it seems like a existing bug which we should fix separately?. Otherwise if not, we could only fix the assertion here. Let me know what you think?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2274571663


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,181 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * @return Bits instance for random access, or null if not available
+   * @throws IOException if an I/O error occurs
+   */
+  public abstract Bits bits() throws IOException;

Review Comment:
   Hmm, I spoke too quickly. A flat scorer should never compute the `cost()` or use the `Bits`. So we need to both compute the cost and the `Bits` lazily.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2274706633


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,221 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * <p><b>NOTE</b>: This must not be called if the {@link #iterator()} has already been used.

Review Comment:
   what's the contract if `bits()` is called first, and then `iterator()`?  Is it possible the iterator will have been consumed in the process of creating the `Bits`?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2276313662


##########
lucene/core/src/java/org/apache/lucene/search/AcceptDocs.java:
##########
@@ -0,0 +1,221 @@
+/*
+ * 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.search;
+
+import java.io.IOException;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.BitSetIterator;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+
+/**
+ * Higher-level abstraction for document acceptance filtering. Can be consumed in either
+ * random-access (Bits) or sequential (DocIdSetIterator) pattern.
+ *
+ * @lucene.experimental
+ */
+public abstract class AcceptDocs {
+
+  /**
+   * Random access to the accepted documents.
+   *
+   * <p><b>NOTE</b>: This must not be called if the {@link #iterator()} has already been used.

Review Comment:
   Also if we first call the `iterator()` then we directly pass the input iterator as-is in `DocIdSetIteratorAcceptDocs` unless the `bits()` is called which then updates it to a `BitSetIterator`. How will we do that if we disallow bits() after iterator()?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs interface for accepted KNN docs [lucene]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3136408257

   This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3214553506

   @jpountz Thanks for the changes. It looks overall good to me. I just made 2 simple refactoring changes on top :
   1) Moved `FilteredDocIdSetIterator` creation to a separate fn
   2) Removed `BitSetAcceptDocs` to further simplify and merged it with `BitSetAcceptDocs`(with no overhead added and since it was not doing any actual work-more of a record kind). 
   
   Let me know if looks good or feel free to revert any changes. I think this looks in good shape to be merged soon (if nobody has concerns)?.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3407820878

   @kaivalnp Yes, we want to move it down to the Codec. I'll soon post a PR for this change.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3408201269

   FYI, for exact search to be fast, it would also be good to have AcceptDocs be able to provide you a "size estimate" that doesn't require evaluating the entire iterator. Right now I think it does that and pretty much defeats the purpose of lazy evaluation of the iterator.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3180983982

   @shubhamvishu could you open a test failure issue?
   
   @ChrisHegarty what do you think?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on code in PR #15011:
URL: https://github.com/apache/lucene/pull/15011#discussion_r2270502489


##########
lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsReader.java:
##########
@@ -332,14 +333,15 @@ private void search(
     final RandomVectorScorer scorer = scorerSupplier.get();
     final KnnCollector collector =
         new OrdinalTranslatedKnnCollector(knnCollector, scorer::ordToDoc);
-    final Bits acceptedOrds = scorer.getAcceptOrds(acceptDocs);
+    Bits accepted = acceptDocs.bits();
+    final Bits acceptedOrds = scorer.getAcceptOrds(accepted);
     HnswGraph graph = getGraph(fieldEntry);
     boolean doHnsw = knnCollector.k() < scorer.maxOrd();
     // Take into account if quantized? E.g. some scorer cost?
     int filteredDocCount = 0;
     // The approximate number of vectors that would be visited if we did not filter
     int unfilteredVisit = HnswGraphSearcher.expectedVisitedNodes(knnCollector.k(), graph.size());
-    if (acceptDocs instanceof BitSet bitSet) {
+    if (accepted instanceof BitSet bitSet) {

Review Comment:
   Sure, I'll fix this



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add AcceptDocs abstraction for accepted KNN docs [lucene]

Posted by "shubhamvishu (via GitHub)" <gi...@apache.org>.
shubhamvishu commented on PR #15011:
URL: https://github.com/apache/lucene/pull/15011#issuecomment-3170523329

   > I hope you don't mind, I addressed my feedback directly on your branch.
   
   @jpountz Not at all, thank you so much for taking care of it! Sorry I couldn’t get to it sooner. I really appreciate the assist.
   
   &nbsp;
   > We will also need to move the decision between approximate and exact to the codec, but it's probably best done as a follow-up PR? I think that this change is good as-is.
   
   I agree completely , that is unrelated to this specific change and better to keep as separate PR.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org