Package org.apache.lucene.search

Class PatienceKnnVectorQuery

java.lang.Object
org.apache.lucene.search.Query
org.apache.lucene.search.PatienceKnnVectorQuery
public class PatienceKnnVectorQuery extends Query
This is a version of knn vector query that exits early when HNSW queue saturates over a #saturationThreshold for more than #patience times.

See "Patience in Proximity: A Simple Early Termination Strategy for HNSW Graph Traversal in Approximate k-Nearest Neighbor Search" (Teofili and Lin). In ECIR '25: Proceedings of the 47th European Conference on Information Retrieval.

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

  • Field Details

    • field

      protected final String field

    • k

      protected final int k

    • filter

      protected final Query filter

    • searchStrategy

      protected final KnnSearchStrategy searchStrategy

  • Method Details

    • fromFloatQuery

      public static PatienceKnnVectorQuery fromFloatQuery(KnnFloatVectorQuery knnQuery, double saturationThreshold, int patience)
      Construct a new PatienceKnnVectorQuery instance for a float vector field
      Parameters:
      knnQuery - the knn query to be seeded
      saturationThreshold - the early exit saturation threshold
      patience - the patience parameter
      Returns:
      a new PatienceKnnVectorQuery instance
      WARNING: This API is experimental and might change in incompatible ways in the next release.

    • fromFloatQuery

      public static PatienceKnnVectorQuery fromFloatQuery(KnnFloatVectorQuery knnQuery)
      Construct a new PatienceKnnVectorQuery instance for a float vector field
      Parameters:
      knnQuery - the knn query to be seeded
      Returns:
      a new PatienceKnnVectorQuery instance
      WARNING: This API is experimental and might change in incompatible ways in the next release.

    • fromByteQuery

      public static PatienceKnnVectorQuery fromByteQuery(KnnByteVectorQuery knnQuery, double saturationThreshold, int patience)
      Construct a new PatienceKnnVectorQuery instance for a byte vector field
      Parameters:
      knnQuery - the knn query to be seeded
      saturationThreshold - the early exit saturation threshold
      patience - the patience parameter
      Returns:
      a new PatienceKnnVectorQuery instance
      WARNING: This API is experimental and might change in incompatible ways in the next release.

    • fromByteQuery

      public static PatienceKnnVectorQuery fromByteQuery(KnnByteVectorQuery knnQuery)
      Construct a new PatienceKnnVectorQuery instance for a byte vector field
      Parameters:
      knnQuery - the knn query to be seeded
      Returns:
      a new PatienceKnnVectorQuery instance
      WARNING: This API is experimental and might change in incompatible ways in the next release.

    • fromSeededQuery

      public static PatienceKnnVectorQuery fromSeededQuery(SeededKnnVectorQuery knnQuery, double saturationThreshold, int patience)
      Construct a new PatienceKnnVectorQuery instance for seeded vector field
      Parameters:
      knnQuery - the knn query to be seeded
      saturationThreshold - the early exit saturation threshold
      patience - the patience parameter
      Returns:
      a new PatienceKnnVectorQuery instance
      WARNING: This API is experimental and might change in incompatible ways in the next release.

    • fromSeededQuery

      public static PatienceKnnVectorQuery fromSeededQuery(SeededKnnVectorQuery knnQuery)
      Construct a new PatienceKnnVectorQuery instance for seeded vector field
      Parameters:
      knnQuery - the knn query to be seeded
      Returns:
      a new PatienceKnnVectorQuery instance
      WARNING: This API is experimental and might change in incompatible ways in the next release.

    • toString

      public String toString(String field)
      Description copied from class: Query
      Prints a query to a string, with field assumed to be the default field and omitted.
      Specified by:
      toString in class Query

    • getKnnCollectorManager

      protected KnnCollectorManager getKnnCollectorManager(int k, IndexSearcher searcher)

    • approximateSearch

      protected TopDocs approximateSearch(LeafReaderContext context, Bits acceptDocs, int visitedLimit, KnnCollectorManager knnCollectorManager) throws IOException
      Throws:
      IOException

    • exactSearch

      protected TopDocs exactSearch(LeafReaderContext context, DocIdSetIterator acceptIterator, QueryTimeout queryTimeout) throws IOException
      Throws:
      IOException

    • mergeLeafResults

      protected TopDocs mergeLeafResults(TopDocs[] perLeafResults)
      Merges all segment-level kNN results to get the index-level kNN results.

      The default implementation delegates to TopDocs.merge(int, TopDocs[]) to find the overall top k, which requires input results to be sorted.

      This method is useful for reading and / or modifying the final results as needed.

      Parameters:
      perLeafResults - array of segment-level kNN results.
      Returns:
      index-level kNN results (no constraint on their ordering).

    • visit

      public void visit(QueryVisitor visitor)
      Description copied from class: Query
      Recurse through the query tree, visiting any child queries.
      Parameters:
      visitor - a QueryVisitor to be called by each query in the tree

    • equals

      public boolean equals(Object o)
      Description copied from class: Query
      Override and implement query instance equivalence properly in a subclass. This is required so that QueryCache works properly.

      Typically a query will be equal to another only if it's an instance of the same class and its document-filtering properties are identical to those of the other instance. Utility methods are provided for certain repetitive code.

      See Also:

    • hashCode

      public int hashCode()
      Description copied from class: Query
      Override and implement query hash code properly in a subclass. This is required so that QueryCache works properly.
      See Also:

    • getField

      public String getField()
      Returns:
      the knn vector field where the knn vector search happens.

    • getK

      public int getK()
      Returns:
      the max number of results the KnnVector search returns.

    • getFilter

      public Query getFilter()
      Returns:
      the filter that is executed before the KnnVector search happens. Only the results accepted by this filter are returned by the KnnVector search.

    • rewrite

      public Query rewrite(IndexSearcher indexSearcher) throws IOException
      Description copied from class: Query
      Expert: called to re-write queries into primitive queries. For example, a PrefixQuery will be rewritten into a BooleanQuery that consists of TermQuerys.

      Callers are expected to call rewrite multiple times if necessary, until the rewritten query is the same as the original query.

      The rewrite process may be able to make use of IndexSearcher's executor and be executed in parallel if the executor is provided.

      Overrides:
      rewrite in class Query
      Throws:
      IOException
      See Also: