You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2022/12/08 07:52:17 UTC
[lucene] branch branch_9x updated (d9a331c85bc -> ca0abc4de6f)
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a change to branch branch_9x
in repository https://gitbox.apache.org/repos/asf/lucene.git
from d9a331c85bc GITHUB-11830 Better optimize storage for vector connections (#11860)
new 6e7b99189d5 Generalize range query optimization on sorted indexes to descending sorts. (#11972)
new ca0abc4de6f Make RandomAccessVectorValues an implementation detail of HNSW implementations rather than a proper API. (#11964)
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
lucene/CHANGES.txt | 3 +
.../lucene90/Lucene90HnswGraphBuilder.java | 2 +-
.../lucene90/Lucene90HnswVectorsReader.java | 2 +-
.../lucene90/Lucene90OnHeapHnswGraph.java | 2 +-
.../lucene91/Lucene91HnswVectorsReader.java | 2 +-
.../lucene92/OffHeapVectorValues.java | 2 +-
.../lucene94/Lucene94HnswVectorsWriter.java | 2 +-
.../lucene94/OffHeapVectorValues.java | 2 +-
.../lucene90/Lucene90HnswVectorsWriter.java | 4 +-
.../lucene91/Lucene91HnswGraphBuilder.java | 2 +-
.../lucene91/Lucene91HnswVectorsWriter.java | 4 +-
.../lucene92/Lucene92HnswVectorsWriter.java | 4 +-
.../simpletext/SimpleTextKnnVectorsReader.java | 2 +-
.../simpletext/SimpleTextKnnVectorsWriter.java | 2 +-
.../BufferingKnnVectorsWriter.java | 83 +++++-
.../codecs/lucene95/Lucene95HnswVectorsWriter.java | 1 +
.../codecs/lucene95/OffHeapVectorValues.java | 2 +-
.../apache/lucene/index/SortingCodecReader.java | 89 ++++++-
.../java/org/apache/lucene/index/VectorValues.java | 61 -----
.../apache/lucene/util/hnsw/HnswGraphBuilder.java | 1 -
.../apache/lucene/util/hnsw/HnswGraphSearcher.java | 1 -
.../hnsw}/RandomAccessVectorValues.java | 5 +-
.../apache/lucene/util/hnsw/MockVectorValues.java | 1 -
.../org/apache/lucene/util/hnsw/TestHnswGraph.java | 1 -
.../IndexSortSortedNumericDocValuesRangeQuery.java | 278 ++++++++++++++++-----
...tIndexSortSortedNumericDocValuesRangeQuery.java | 109 ++++++--
26 files changed, 478 insertions(+), 189 deletions(-)
rename lucene/core/src/java/org/apache/lucene/{index => codecs}/BufferingKnnVectorsWriter.java (80%)
rename lucene/core/src/java/org/apache/lucene/{index => util/hnsw}/RandomAccessVectorValues.java (93%)
[lucene] 02/02: Make RandomAccessVectorValues an implementation detail of HNSW implementations rather than a proper API. (#11964)
Posted by jp...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a commit to branch branch_9x
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit ca0abc4de6f5a79a00f07c79559eb8cc91202f18
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Thu Dec 8 08:49:37 2022 +0100
Make RandomAccessVectorValues an implementation detail of HNSW implementations rather than a proper API. (#11964)
`RandomAccessVectorValues` is internally used in our HNSW implementation to
provide random access to vectors, both at index and search time. In order to
better reflect this, this change does the following:
- `RandomAccessVectorValues` moves to `org.apache.lucene.util.hnsw`.
- `BufferingKnnVectorsWriter` no longer has a dependency on
`RandomAccessVectorValues` and moves to `org.apache.lucene.codecs` since
it's more of a utility class for KNN vector file formats than an index API.
Maybe we should think of moving it near each file format that uses it
instead.
- `SortingCodecReader` no longer has a dependency on
`RandomAccessVectorValues`.
Closes #10623
---
.../lucene90/Lucene90HnswGraphBuilder.java | 2 +-
.../lucene90/Lucene90HnswVectorsReader.java | 2 +-
.../lucene90/Lucene90OnHeapHnswGraph.java | 2 +-
.../lucene91/Lucene91HnswVectorsReader.java | 2 +-
.../lucene92/OffHeapVectorValues.java | 2 +-
.../lucene94/Lucene94HnswVectorsWriter.java | 2 +-
.../lucene94/OffHeapVectorValues.java | 2 +-
.../lucene90/Lucene90HnswVectorsWriter.java | 4 +-
.../lucene91/Lucene91HnswGraphBuilder.java | 2 +-
.../lucene91/Lucene91HnswVectorsWriter.java | 4 +-
.../lucene92/Lucene92HnswVectorsWriter.java | 4 +-
.../simpletext/SimpleTextKnnVectorsReader.java | 2 +-
.../simpletext/SimpleTextKnnVectorsWriter.java | 2 +-
.../BufferingKnnVectorsWriter.java | 83 +++++++++++++++++---
.../codecs/lucene95/Lucene95HnswVectorsWriter.java | 1 +
.../codecs/lucene95/OffHeapVectorValues.java | 2 +-
.../apache/lucene/index/SortingCodecReader.java | 89 +++++++++++++++++++++-
.../java/org/apache/lucene/index/VectorValues.java | 61 ---------------
.../apache/lucene/util/hnsw/HnswGraphBuilder.java | 1 -
.../apache/lucene/util/hnsw/HnswGraphSearcher.java | 1 -
.../hnsw}/RandomAccessVectorValues.java | 5 +-
.../apache/lucene/util/hnsw/MockVectorValues.java | 1 -
.../org/apache/lucene/util/hnsw/TestHnswGraph.java | 1 -
23 files changed, 180 insertions(+), 97 deletions(-)
diff --git a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswGraphBuilder.java b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswGraphBuilder.java
index 81327fbfcd5..d17b4019364 100644
--- a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswGraphBuilder.java
+++ b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswGraphBuilder.java
@@ -22,10 +22,10 @@ import java.util.Locale;
import java.util.Objects;
import java.util.SplittableRandom;
import java.util.concurrent.TimeUnit;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.util.InfoStream;
import org.apache.lucene.util.hnsw.NeighborQueue;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
/**
* Builder for HNSW graph. See {@link Lucene90OnHeapHnswGraph} for a gloss on the algorithm and the
diff --git a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswVectorsReader.java b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswVectorsReader.java
index 83a3b090bdb..8377072a07f 100644
--- a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswVectorsReader.java
+++ b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswVectorsReader.java
@@ -31,7 +31,6 @@ import org.apache.lucene.index.CorruptIndexException;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.FieldInfos;
import org.apache.lucene.index.IndexFileNames;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.SegmentReadState;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.index.VectorValues;
@@ -47,6 +46,7 @@ import org.apache.lucene.util.IOUtils;
import org.apache.lucene.util.RamUsageEstimator;
import org.apache.lucene.util.hnsw.HnswGraph;
import org.apache.lucene.util.hnsw.NeighborQueue;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
/**
* Reads vectors from the index segments along with index data structures supporting KNN search.
diff --git a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90OnHeapHnswGraph.java b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90OnHeapHnswGraph.java
index aeffedcc287..e3b15bf22b1 100644
--- a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90OnHeapHnswGraph.java
+++ b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90OnHeapHnswGraph.java
@@ -23,12 +23,12 @@ import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.SplittableRandom;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.SparseFixedBitSet;
import org.apache.lucene.util.hnsw.HnswGraph;
import org.apache.lucene.util.hnsw.NeighborQueue;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
/**
* An {@link HnswGraph} where all nodes and connections are held in memory. This class is used to
diff --git a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene91/Lucene91HnswVectorsReader.java b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene91/Lucene91HnswVectorsReader.java
index d889ff4fbda..752b87d0179 100644
--- a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene91/Lucene91HnswVectorsReader.java
+++ b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene91/Lucene91HnswVectorsReader.java
@@ -31,7 +31,6 @@ import org.apache.lucene.index.CorruptIndexException;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.FieldInfos;
import org.apache.lucene.index.IndexFileNames;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.SegmentReadState;
import org.apache.lucene.index.VectorEncoding;
import org.apache.lucene.index.VectorSimilarityFunction;
@@ -49,6 +48,7 @@ import org.apache.lucene.util.RamUsageEstimator;
import org.apache.lucene.util.hnsw.HnswGraph;
import org.apache.lucene.util.hnsw.HnswGraphSearcher;
import org.apache.lucene.util.hnsw.NeighborQueue;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
/**
* Reads vectors from the index segments along with index data structures supporting KNN search.
diff --git a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene92/OffHeapVectorValues.java b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene92/OffHeapVectorValues.java
index 88968e42238..b1a0eb5b5ea 100644
--- a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene92/OffHeapVectorValues.java
+++ b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene92/OffHeapVectorValues.java
@@ -20,12 +20,12 @@ package org.apache.lucene.backward_codecs.lucene92;
import java.io.IOException;
import java.nio.ByteBuffer;
import org.apache.lucene.codecs.lucene90.IndexedDISI;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.VectorValues;
import org.apache.lucene.store.IndexInput;
import org.apache.lucene.store.RandomAccessInput;
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
import org.apache.lucene.util.packed.DirectMonotonicReader;
/** Read the vector values from the index input. This supports both iterated and random access. */
diff --git a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene94/Lucene94HnswVectorsWriter.java b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene94/Lucene94HnswVectorsWriter.java
index 052046b9e93..3cb7c235db1 100644
--- a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene94/Lucene94HnswVectorsWriter.java
+++ b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene94/Lucene94HnswVectorsWriter.java
@@ -34,7 +34,6 @@ import org.apache.lucene.index.DocsWithFieldSet;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.IndexFileNames;
import org.apache.lucene.index.MergeState;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.SegmentWriteState;
import org.apache.lucene.index.Sorter;
import org.apache.lucene.index.VectorValues;
@@ -51,6 +50,7 @@ import org.apache.lucene.util.hnsw.HnswGraph.NodesIterator;
import org.apache.lucene.util.hnsw.HnswGraphBuilder;
import org.apache.lucene.util.hnsw.NeighborArray;
import org.apache.lucene.util.hnsw.OnHeapHnswGraph;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
import org.apache.lucene.util.packed.DirectMonotonicWriter;
/**
diff --git a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene94/OffHeapVectorValues.java b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene94/OffHeapVectorValues.java
index c0e52e7c809..0705f8cf512 100644
--- a/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene94/OffHeapVectorValues.java
+++ b/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene94/OffHeapVectorValues.java
@@ -20,12 +20,12 @@ package org.apache.lucene.backward_codecs.lucene94;
import java.io.IOException;
import java.nio.ByteBuffer;
import org.apache.lucene.codecs.lucene90.IndexedDISI;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.VectorValues;
import org.apache.lucene.store.IndexInput;
import org.apache.lucene.store.RandomAccessInput;
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
import org.apache.lucene.util.packed.DirectMonotonicReader;
/** Read the vector values from the index input. This supports both iterated and random access. */
diff --git a/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswVectorsWriter.java b/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswVectorsWriter.java
index 489db7f310e..6478152e104 100644
--- a/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswVectorsWriter.java
+++ b/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswVectorsWriter.java
@@ -21,12 +21,11 @@ import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
import java.io.IOException;
import java.util.Arrays;
+import org.apache.lucene.codecs.BufferingKnnVectorsWriter;
import org.apache.lucene.codecs.CodecUtil;
import org.apache.lucene.codecs.KnnVectorsReader;
-import org.apache.lucene.index.BufferingKnnVectorsWriter;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.IndexFileNames;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.SegmentWriteState;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.index.VectorValues;
@@ -35,6 +34,7 @@ import org.apache.lucene.store.IndexOutput;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.IOUtils;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
/**
* Writes vector values and knn graphs to index segments.
diff --git a/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene91/Lucene91HnswGraphBuilder.java b/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene91/Lucene91HnswGraphBuilder.java
index 344c01ab085..5f37e905e2f 100644
--- a/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene91/Lucene91HnswGraphBuilder.java
+++ b/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene91/Lucene91HnswGraphBuilder.java
@@ -24,7 +24,6 @@ import java.util.Locale;
import java.util.Objects;
import java.util.SplittableRandom;
import java.util.concurrent.TimeUnit;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.VectorEncoding;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.util.FixedBitSet;
@@ -32,6 +31,7 @@ import org.apache.lucene.util.InfoStream;
import org.apache.lucene.util.hnsw.HnswGraph;
import org.apache.lucene.util.hnsw.HnswGraphSearcher;
import org.apache.lucene.util.hnsw.NeighborQueue;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
/**
* Builder for HNSW graph. See {@link HnswGraph} for a gloss on the algorithm and the meaning of the
diff --git a/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene91/Lucene91HnswVectorsWriter.java b/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene91/Lucene91HnswVectorsWriter.java
index 855f469f174..5e9b62c8dd7 100644
--- a/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene91/Lucene91HnswVectorsWriter.java
+++ b/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene91/Lucene91HnswVectorsWriter.java
@@ -21,13 +21,12 @@ import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
import java.io.IOException;
import java.util.Arrays;
+import org.apache.lucene.codecs.BufferingKnnVectorsWriter;
import org.apache.lucene.codecs.CodecUtil;
import org.apache.lucene.codecs.KnnVectorsReader;
-import org.apache.lucene.index.BufferingKnnVectorsWriter;
import org.apache.lucene.index.DocsWithFieldSet;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.IndexFileNames;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.SegmentWriteState;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.index.VectorValues;
@@ -37,6 +36,7 @@ import org.apache.lucene.store.IndexOutput;
import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.IOUtils;
import org.apache.lucene.util.hnsw.HnswGraph.NodesIterator;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
/**
* Writes vector values and knn graphs to index segments.
diff --git a/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene92/Lucene92HnswVectorsWriter.java b/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene92/Lucene92HnswVectorsWriter.java
index 0cf6aa817ca..0e6c72186c7 100644
--- a/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene92/Lucene92HnswVectorsWriter.java
+++ b/lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene92/Lucene92HnswVectorsWriter.java
@@ -22,14 +22,13 @@ import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
import java.io.IOException;
import java.util.Arrays;
+import org.apache.lucene.codecs.BufferingKnnVectorsWriter;
import org.apache.lucene.codecs.CodecUtil;
import org.apache.lucene.codecs.KnnVectorsReader;
import org.apache.lucene.codecs.lucene90.IndexedDISI;
-import org.apache.lucene.index.BufferingKnnVectorsWriter;
import org.apache.lucene.index.DocsWithFieldSet;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.IndexFileNames;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.SegmentWriteState;
import org.apache.lucene.index.VectorEncoding;
import org.apache.lucene.index.VectorSimilarityFunction;
@@ -43,6 +42,7 @@ import org.apache.lucene.util.hnsw.HnswGraph.NodesIterator;
import org.apache.lucene.util.hnsw.HnswGraphBuilder;
import org.apache.lucene.util.hnsw.NeighborArray;
import org.apache.lucene.util.hnsw.OnHeapHnswGraph;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
import org.apache.lucene.util.packed.DirectMonotonicWriter;
/**
diff --git a/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextKnnVectorsReader.java b/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextKnnVectorsReader.java
index 4b29ce942d3..a3d7753871b 100644
--- a/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextKnnVectorsReader.java
+++ b/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextKnnVectorsReader.java
@@ -28,7 +28,6 @@ import org.apache.lucene.codecs.KnnVectorsReader;
import org.apache.lucene.index.CorruptIndexException;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.IndexFileNames;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.SegmentReadState;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.index.VectorValues;
@@ -47,6 +46,7 @@ import org.apache.lucene.util.BytesRefBuilder;
import org.apache.lucene.util.IOUtils;
import org.apache.lucene.util.RamUsageEstimator;
import org.apache.lucene.util.StringHelper;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
/**
* Reads vector values from a simple text format. All vectors are read up front and cached in RAM in
diff --git a/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextKnnVectorsWriter.java b/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextKnnVectorsWriter.java
index 4992e524938..18a310d46ed 100644
--- a/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextKnnVectorsWriter.java
+++ b/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextKnnVectorsWriter.java
@@ -23,8 +23,8 @@ import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
+import org.apache.lucene.codecs.BufferingKnnVectorsWriter;
import org.apache.lucene.codecs.KnnVectorsReader;
-import org.apache.lucene.index.BufferingKnnVectorsWriter;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.IndexFileNames;
import org.apache.lucene.index.SegmentWriteState;
diff --git a/lucene/core/src/java/org/apache/lucene/index/BufferingKnnVectorsWriter.java b/lucene/core/src/java/org/apache/lucene/codecs/BufferingKnnVectorsWriter.java
similarity index 80%
rename from lucene/core/src/java/org/apache/lucene/index/BufferingKnnVectorsWriter.java
rename to lucene/core/src/java/org/apache/lucene/codecs/BufferingKnnVectorsWriter.java
index 8b70ebcfd30..59288b127a6 100644
--- a/lucene/core/src/java/org/apache/lucene/index/BufferingKnnVectorsWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/BufferingKnnVectorsWriter.java
@@ -15,16 +15,18 @@
* limitations under the License.
*/
-package org.apache.lucene.index;
+package org.apache.lucene.codecs;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.util.ArrayList;
import java.util.List;
-import org.apache.lucene.codecs.KnnFieldVectorsWriter;
-import org.apache.lucene.codecs.KnnVectorsReader;
-import org.apache.lucene.codecs.KnnVectorsWriter;
+import org.apache.lucene.index.DocsWithFieldSet;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.MergeState;
+import org.apache.lucene.index.Sorter;
+import org.apache.lucene.index.VectorValues;
import org.apache.lucene.search.DocIdSetIterator;
import org.apache.lucene.search.TopDocs;
import org.apache.lucene.util.ArrayUtil;
@@ -73,13 +75,13 @@ public abstract class BufferingKnnVectorsWriter extends KnnVectorsWriter {
@Override
public VectorValues getVectorValues(String field) throws IOException {
- VectorValues vectorValues =
+ BufferedVectorValues vectorValues =
new BufferedVectorValues(
fieldData.docsWithField,
fieldData.vectors,
fieldData.fieldInfo.getVectorDimension());
return sortMap != null
- ? new VectorValues.SortingVectorValues(vectorValues, sortMap)
+ ? new SortingVectorValues(vectorValues, sortMap)
: vectorValues;
}
@@ -94,6 +96,67 @@ public abstract class BufferingKnnVectorsWriter extends KnnVectorsWriter {
}
}
+ /** Sorting VectorValues that iterate over documents in the order of the provided sortMap */
+ private static class SortingVectorValues extends VectorValues {
+ private final BufferedVectorValues randomAccess;
+ private final int[] docIdOffsets;
+ private int docId = -1;
+
+ SortingVectorValues(BufferedVectorValues delegate, Sorter.DocMap sortMap) throws IOException {
+ this.randomAccess = delegate.copy();
+ this.docIdOffsets = new int[sortMap.size()];
+
+ int offset = 1; // 0 means no vector for this (field, document)
+ int docID;
+ while ((docID = delegate.nextDoc()) != NO_MORE_DOCS) {
+ int newDocID = sortMap.oldToNew(docID);
+ docIdOffsets[newDocID] = offset++;
+ }
+ }
+
+ @Override
+ public int docID() {
+ return docId;
+ }
+
+ @Override
+ public int nextDoc() throws IOException {
+ while (docId < docIdOffsets.length - 1) {
+ ++docId;
+ if (docIdOffsets[docId] != 0) {
+ return docId;
+ }
+ }
+ docId = NO_MORE_DOCS;
+ return docId;
+ }
+
+ @Override
+ public BytesRef binaryValue() throws IOException {
+ return randomAccess.binaryValue(docIdOffsets[docId] - 1);
+ }
+
+ @Override
+ public float[] vectorValue() throws IOException {
+ return randomAccess.vectorValue(docIdOffsets[docId] - 1);
+ }
+
+ @Override
+ public int dimension() {
+ return randomAccess.dimension();
+ }
+
+ @Override
+ public int size() {
+ return randomAccess.size();
+ }
+
+ @Override
+ public int advance(int target) throws IOException {
+ throw new UnsupportedOperationException();
+ }
+ }
+
@Override
public long ramBytesUsed() {
long total = 0;
@@ -203,8 +266,7 @@ public abstract class BufferingKnnVectorsWriter extends KnnVectorsWriter {
}
}
- private static class BufferedVectorValues extends VectorValues
- implements RandomAccessVectorValues {
+ private static class BufferedVectorValues extends VectorValues {
final DocsWithFieldSet docsWithField;
@@ -231,8 +293,7 @@ public abstract class BufferingKnnVectorsWriter extends KnnVectorsWriter {
docsWithFieldIter = docsWithField.iterator();
}
- @Override
- public RandomAccessVectorValues copy() {
+ public BufferedVectorValues copy() {
return new BufferedVectorValues(docsWithField, vectors, dimension);
}
@@ -252,7 +313,6 @@ public abstract class BufferingKnnVectorsWriter extends KnnVectorsWriter {
return binaryValue;
}
- @Override
public BytesRef binaryValue(int targetOrd) {
raBuffer.asFloatBuffer().put(vectors.get(targetOrd));
return raBinaryValue;
@@ -263,7 +323,6 @@ public abstract class BufferingKnnVectorsWriter extends KnnVectorsWriter {
return vectors.get(ord);
}
- @Override
public float[] vectorValue(int targetOrd) {
return vectors.get(targetOrd);
}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene95/Lucene95HnswVectorsWriter.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene95/Lucene95HnswVectorsWriter.java
index 8c53f9768fb..12e0f0bd73e 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene95/Lucene95HnswVectorsWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene95/Lucene95HnswVectorsWriter.java
@@ -41,6 +41,7 @@ import org.apache.lucene.util.hnsw.HnswGraph.NodesIterator;
import org.apache.lucene.util.hnsw.HnswGraphBuilder;
import org.apache.lucene.util.hnsw.NeighborArray;
import org.apache.lucene.util.hnsw.OnHeapHnswGraph;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
import org.apache.lucene.util.packed.DirectMonotonicWriter;
/**
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene95/OffHeapVectorValues.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene95/OffHeapVectorValues.java
index b1a90295e18..124430bceb4 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene95/OffHeapVectorValues.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene95/OffHeapVectorValues.java
@@ -20,12 +20,12 @@ package org.apache.lucene.codecs.lucene95;
import java.io.IOException;
import java.nio.ByteBuffer;
import org.apache.lucene.codecs.lucene90.IndexedDISI;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.VectorValues;
import org.apache.lucene.store.IndexInput;
import org.apache.lucene.store.RandomAccessInput;
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
import org.apache.lucene.util.packed.DirectMonotonicReader;
/** Read the vector values from the index input. This supports both iterated and random access. */
diff --git a/lucene/core/src/java/org/apache/lucene/index/SortingCodecReader.java b/lucene/core/src/java/org/apache/lucene/index/SortingCodecReader.java
index 7fb91bf6621..320c89d9690 100644
--- a/lucene/core/src/java/org/apache/lucene/index/SortingCodecReader.java
+++ b/lucene/core/src/java/org/apache/lucene/index/SortingCodecReader.java
@@ -20,6 +20,8 @@ package org.apache.lucene.index;
import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
@@ -35,6 +37,7 @@ import org.apache.lucene.search.Sort;
import org.apache.lucene.search.SortField;
import org.apache.lucene.search.TopDocs;
import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.FixedBitSet;
import org.apache.lucene.util.IOSupplier;
import org.apache.lucene.util.packed.PackedInts;
@@ -212,6 +215,88 @@ public final class SortingCodecReader extends FilterCodecReader {
}
}
+ /** Sorting VectorValues that iterate over documents in the order of the provided sortMap */
+ private static class SortingVectorValues extends VectorValues {
+ final int size;
+ final int dimension;
+ final FixedBitSet docsWithField;
+ final float[][] vectors;
+ final ByteBuffer vectorAsBytes;
+ final BytesRef[] binaryVectors;
+
+ private int docId = -1;
+
+ SortingVectorValues(VectorValues delegate, Sorter.DocMap sortMap, VectorEncoding encoding)
+ throws IOException {
+ this.size = delegate.size();
+ this.dimension = delegate.dimension();
+ docsWithField = new FixedBitSet(sortMap.size());
+ if (encoding == VectorEncoding.BYTE) {
+ vectors = null;
+ binaryVectors = new BytesRef[sortMap.size()];
+ vectorAsBytes = null;
+ } else {
+ vectors = new float[sortMap.size()][];
+ binaryVectors = null;
+ vectorAsBytes =
+ ByteBuffer.allocate(delegate.dimension() * encoding.byteSize)
+ .order(ByteOrder.LITTLE_ENDIAN);
+ }
+ for (int doc = delegate.nextDoc(); doc != NO_MORE_DOCS; doc = delegate.nextDoc()) {
+ int newDocID = sortMap.oldToNew(doc);
+ docsWithField.set(newDocID);
+ if (encoding == VectorEncoding.BYTE) {
+ binaryVectors[newDocID] = BytesRef.deepCopyOf(delegate.binaryValue());
+ } else {
+ vectors[newDocID] = delegate.vectorValue().clone();
+ }
+ }
+ }
+
+ @Override
+ public int docID() {
+ return docId;
+ }
+
+ @Override
+ public int nextDoc() throws IOException {
+ return advance(docId + 1);
+ }
+
+ @Override
+ public BytesRef binaryValue() throws IOException {
+ if (binaryVectors != null) {
+ return binaryVectors[docId];
+ } else {
+ vectorAsBytes.asFloatBuffer().put(vectors[docId]);
+ return new BytesRef(vectorAsBytes.array());
+ }
+ }
+
+ @Override
+ public float[] vectorValue() throws IOException {
+ return vectors[docId];
+ }
+
+ @Override
+ public int dimension() {
+ return dimension;
+ }
+
+ @Override
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public int advance(int target) throws IOException {
+ if (target >= docsWithField.length()) {
+ return NO_MORE_DOCS;
+ }
+ return docId = docsWithField.nextSetBit(target);
+ }
+ }
+
/**
* Return a sorted view of <code>reader</code> according to the order defined by <code>sort</code>
* . If the reader is already sorted, this method might return the reader as-is.
@@ -380,7 +465,9 @@ public final class SortingCodecReader extends FilterCodecReader {
@Override
public VectorValues getVectorValues(String field) throws IOException {
- return new VectorValues.SortingVectorValues(delegate.getVectorValues(field), docMap);
+ FieldInfo fi = in.getFieldInfos().fieldInfo(field);
+ return new SortingVectorValues(
+ delegate.getVectorValues(field), docMap, fi.getVectorEncoding());
}
@Override
diff --git a/lucene/core/src/java/org/apache/lucene/index/VectorValues.java b/lucene/core/src/java/org/apache/lucene/index/VectorValues.java
index 21945e888e9..79b1033b4aa 100644
--- a/lucene/core/src/java/org/apache/lucene/index/VectorValues.java
+++ b/lucene/core/src/java/org/apache/lucene/index/VectorValues.java
@@ -70,65 +70,4 @@ public abstract class VectorValues extends DocIdSetIterator {
public BytesRef binaryValue() throws IOException {
throw new UnsupportedOperationException();
}
-
- /** Sorting VectorValues that iterate over documents in the order of the provided sortMap */
- public static class SortingVectorValues extends VectorValues {
- private final RandomAccessVectorValues randomAccess;
- private final int[] docIdOffsets;
- private int docId = -1;
-
- SortingVectorValues(VectorValues delegate, Sorter.DocMap sortMap) throws IOException {
- this.randomAccess = ((RandomAccessVectorValues) delegate).copy();
- this.docIdOffsets = new int[sortMap.size()];
-
- int offset = 1; // 0 means no vector for this (field, document)
- int docID;
- while ((docID = delegate.nextDoc()) != NO_MORE_DOCS) {
- int newDocID = sortMap.oldToNew(docID);
- docIdOffsets[newDocID] = offset++;
- }
- }
-
- @Override
- public int docID() {
- return docId;
- }
-
- @Override
- public int nextDoc() throws IOException {
- while (docId < docIdOffsets.length - 1) {
- ++docId;
- if (docIdOffsets[docId] != 0) {
- return docId;
- }
- }
- docId = NO_MORE_DOCS;
- return docId;
- }
-
- @Override
- public BytesRef binaryValue() throws IOException {
- return randomAccess.binaryValue(docIdOffsets[docId] - 1);
- }
-
- @Override
- public float[] vectorValue() throws IOException {
- return randomAccess.vectorValue(docIdOffsets[docId] - 1);
- }
-
- @Override
- public int dimension() {
- return randomAccess.dimension();
- }
-
- @Override
- public int size() {
- return randomAccess.size();
- }
-
- @Override
- public int advance(int target) throws IOException {
- throw new UnsupportedOperationException();
- }
- }
}
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
index aa90e65400c..d69c7f6b31b 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
@@ -24,7 +24,6 @@ import java.util.Locale;
import java.util.Objects;
import java.util.SplittableRandom;
import java.util.concurrent.TimeUnit;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.VectorEncoding;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.util.BytesRef;
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java
index ce0022d5196..db71d19f458 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java
@@ -21,7 +21,6 @@ import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
import static org.apache.lucene.util.VectorUtil.toBytesRef;
import java.io.IOException;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.VectorEncoding;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.util.BitSet;
diff --git a/lucene/core/src/java/org/apache/lucene/index/RandomAccessVectorValues.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/RandomAccessVectorValues.java
similarity index 93%
rename from lucene/core/src/java/org/apache/lucene/index/RandomAccessVectorValues.java
rename to lucene/core/src/java/org/apache/lucene/util/hnsw/RandomAccessVectorValues.java
index a18535ee567..4c220518a2e 100644
--- a/lucene/core/src/java/org/apache/lucene/index/RandomAccessVectorValues.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/RandomAccessVectorValues.java
@@ -15,13 +15,14 @@
* limitations under the License.
*/
-package org.apache.lucene.index;
+package org.apache.lucene.util.hnsw;
import java.io.IOException;
import org.apache.lucene.util.BytesRef;
/**
- * Provides random access to vectors by dense ordinal.
+ * Provides random access to vectors by dense ordinal. This interface is used by HNSW-based
+ * implementations of KNN search.
*
* @lucene.experimental
*/
diff --git a/lucene/core/src/test/org/apache/lucene/util/hnsw/MockVectorValues.java b/lucene/core/src/test/org/apache/lucene/util/hnsw/MockVectorValues.java
index 2ae264fe8ce..299d27857da 100644
--- a/lucene/core/src/test/org/apache/lucene/util/hnsw/MockVectorValues.java
+++ b/lucene/core/src/test/org/apache/lucene/util/hnsw/MockVectorValues.java
@@ -17,7 +17,6 @@
package org.apache.lucene.util.hnsw;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.VectorValues;
import org.apache.lucene.tests.util.LuceneTestCase;
import org.apache.lucene.util.BytesRef;
diff --git a/lucene/core/src/test/org/apache/lucene/util/hnsw/TestHnswGraph.java b/lucene/core/src/test/org/apache/lucene/util/hnsw/TestHnswGraph.java
index 543a6dc5949..ad785d6fe02 100644
--- a/lucene/core/src/test/org/apache/lucene/util/hnsw/TestHnswGraph.java
+++ b/lucene/core/src/test/org/apache/lucene/util/hnsw/TestHnswGraph.java
@@ -45,7 +45,6 @@ import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.index.LeafReaderContext;
-import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.VectorEncoding;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.index.VectorValues;
[lucene] 01/02: Generalize range query optimization on sorted indexes to descending sorts. (#11972)
Posted by jp...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a commit to branch branch_9x
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit 6e7b99189d5f6623466df7d27f9b8da747f3411a
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Thu Dec 8 08:38:53 2022 +0100
Generalize range query optimization on sorted indexes to descending sorts. (#11972)
This generalizes #687 to indexes that are sorted in descending order. The main
challenge with descending sorts is that they require being able to compute the
last doc ID that matches a value, which would ideally require walking the BKD
tree in reverse order, but the API only support moving forward. This is worked
around by maintaining a stack of `PointTree` clones to perform the search.
---
lucene/CHANGES.txt | 3 +
.../IndexSortSortedNumericDocValuesRangeQuery.java | 278 ++++++++++++++++-----
...tIndexSortSortedNumericDocValuesRangeQuery.java | 109 ++++++--
3 files changed, 298 insertions(+), 92 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 182b12b9021..d037a535177 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -107,6 +107,9 @@ Optimizations
* GITHUB#11895: count() in BooleanQuery could be early quit. (Lu Xugang)
+* GITHUB#11972: `IndexSortSortedNumericDocValuesRangeQuery` can now also
+ optimize query execution with points for descending sorts. (Adrien Grand)
+
Other
---------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/IndexSortSortedNumericDocValuesRangeQuery.java b/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/IndexSortSortedNumericDocValuesRangeQuery.java
index 2d6c0384e96..360e11652cb 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/IndexSortSortedNumericDocValuesRangeQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/IndexSortSortedNumericDocValuesRangeQuery.java
@@ -17,8 +17,9 @@
package org.apache.lucene.sandbox.search;
import java.io.IOException;
+import java.util.ArrayDeque;
+import java.util.Deque;
import java.util.Objects;
-import java.util.function.Predicate;
import org.apache.lucene.document.IntPoint;
import org.apache.lucene.document.LongPoint;
import org.apache.lucene.index.DocValues;
@@ -28,6 +29,7 @@ import org.apache.lucene.index.LeafReaderContext;
import org.apache.lucene.index.NumericDocValues;
import org.apache.lucene.index.PointValues;
import org.apache.lucene.index.PointValues.IntersectVisitor;
+import org.apache.lucene.index.PointValues.PointTree;
import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.index.SortedNumericDocValues;
import org.apache.lucene.search.ConstantScoreScorer;
@@ -221,53 +223,55 @@ public class IndexSortSortedNumericDocValuesRangeQuery extends Query {
};
}
- /**
- * Returns the first document whose packed value is greater than or equal (if allowEqual is true)
- * to the provided packed value or -1 if all packed values are smaller than the provided one,
- */
- public final int nextDoc(PointValues values, byte[] packedValue, boolean allowEqual)
- throws IOException {
- assert values.getNumDimensions() == 1;
- final int bytesPerDim = values.getBytesPerDimension();
- final ByteArrayComparator comparator = ArrayUtil.getUnsignedComparator(bytesPerDim);
- final Predicate<byte[]> biggerThan =
- testPackedValue -> {
- int cmp = comparator.compare(testPackedValue, 0, packedValue, 0);
- return cmp > 0 || (cmp == 0 && allowEqual);
- };
- return nextDoc(values.getPointTree(), biggerThan);
+ private static class ValueAndDoc {
+ byte[] value;
+ int docID;
+ boolean done;
}
- private int nextDoc(PointValues.PointTree pointTree, Predicate<byte[]> biggerThan)
+ /**
+ * Move to the minimum leaf node that has at least one value that is greater than (or equal to if
+ * {@code allowEqual}) {@code value}, and return the next greater value on this block. Upon
+ * returning, the {@code pointTree} must be on the leaf node where the value was found.
+ */
+ private static ValueAndDoc findNextValue(
+ PointTree pointTree,
+ byte[] value,
+ boolean allowEqual,
+ ByteArrayComparator comparator,
+ boolean lastDoc)
throws IOException {
- if (biggerThan.test(pointTree.getMaxPackedValue()) == false) {
- // doc is before us
- return -1;
- } else if (pointTree.moveToChild()) {
- // navigate down
- do {
- final int doc = nextDoc(pointTree, biggerThan);
- if (doc != -1) {
- return doc;
- }
- } while (pointTree.moveToSibling());
- pointTree.moveToParent();
- return -1;
- } else {
- // doc is in this leaf
- final int[] doc = {-1};
+ int cmp = comparator.compare(pointTree.getMaxPackedValue(), 0, value, 0);
+ if (cmp < 0 || (cmp == 0 && allowEqual == false)) {
+ return null;
+ }
+ if (pointTree.moveToChild() == false) {
+ ValueAndDoc vd = new ValueAndDoc();
pointTree.visitDocValues(
new IntersectVisitor() {
+
@Override
- public void visit(int docID) {
- throw new AssertionError("Invalid call to visit(docID)");
+ public void visit(int docID, byte[] packedValue) throws IOException {
+ if (vd.value == null) {
+ int cmp = comparator.compare(packedValue, 0, value, 0);
+ if (cmp > 0 || (cmp == 0 && allowEqual)) {
+ vd.value = packedValue.clone();
+ vd.docID = docID;
+ }
+ } else if (lastDoc && vd.done == false) {
+ int cmp = comparator.compare(packedValue, 0, vd.value, 0);
+ assert cmp >= 0;
+ if (cmp > 0) {
+ vd.done = true;
+ } else {
+ vd.docID = docID;
+ }
+ }
}
@Override
- public void visit(int docID, byte[] packedValue) {
- if (doc[0] == -1 && biggerThan.test(packedValue)) {
- doc[0] = docID;
- }
+ public void visit(int docID) throws IOException {
+ throw new UnsupportedOperationException();
}
@Override
@@ -275,10 +279,132 @@ public class IndexSortSortedNumericDocValuesRangeQuery extends Query {
return Relation.CELL_CROSSES_QUERY;
}
});
- return doc[0];
+ if (vd.value != null) {
+ return vd;
+ } else {
+ return null;
+ }
+ }
+
+ // Recurse
+ do {
+ ValueAndDoc vd = findNextValue(pointTree, value, allowEqual, comparator, lastDoc);
+ if (vd != null) {
+ return vd;
+ }
+ } while (pointTree.moveToSibling());
+
+ boolean moved = pointTree.moveToParent();
+ assert moved;
+ return null;
+ }
+
+ /**
+ * Find the next value that is greater than (or equal to if {@code allowEqual}) and return either
+ * its first doc ID or last doc ID depending on {@code lastDoc}. This method returns -1 if there
+ * is no greater value in the dataset.
+ */
+ private static int nextDoc(
+ PointTree pointTree,
+ byte[] value,
+ boolean allowEqual,
+ ByteArrayComparator comparator,
+ boolean lastDoc)
+ throws IOException {
+ ValueAndDoc vd = findNextValue(pointTree, value, allowEqual, comparator, lastDoc);
+ if (vd == null) {
+ return -1;
+ }
+ if (lastDoc == false || vd.done) {
+ return vd.docID;
+ }
+
+ // We found the next value, now we need the last doc ID.
+ int doc = lastDoc(pointTree, vd.value, comparator);
+ if (doc == -1) {
+ // vd.docID was actually the last doc ID
+ return vd.docID;
+ } else {
+ return doc;
}
}
+ /**
+ * Compute the last doc ID that matches the given value and is stored on a leaf node that compares
+ * greater than the current leaf node that the provided {@link PointTree} is positioned on. This
+ * returns -1 if no other leaf node contains the provided {@code value}.
+ */
+ private static int lastDoc(PointTree pointTree, byte[] value, ByteArrayComparator comparator)
+ throws IOException {
+ // Create a stack of nodes that may contain value that we'll use to search for the last leaf
+ // node that contains `value`.
+ // While the logic looks a bit complicated due to the fact that the PointTree API doesn't allow
+ // moving back to previous siblings, this effectively performs a binary search.
+ Deque<PointTree> stack = new ArrayDeque<>();
+
+ outer:
+ while (true) {
+
+ // Move to the next node
+ while (pointTree.moveToSibling() == false) {
+ if (pointTree.moveToParent() == false) {
+ // No next node
+ break outer;
+ }
+ }
+
+ int cmp = comparator.compare(pointTree.getMinPackedValue(), 0, value, 0);
+ if (cmp > 0) {
+ // This node doesn't have `value`, so next nodes can't either
+ break;
+ }
+
+ stack.push(pointTree.clone());
+ }
+
+ while (stack.isEmpty() == false) {
+ PointTree next = stack.pop();
+ if (next.moveToChild() == false) {
+ int[] lastDoc = {-1};
+ next.visitDocValues(
+ new IntersectVisitor() {
+
+ @Override
+ public void visit(int docID) throws IOException {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void visit(int docID, byte[] packedValue) throws IOException {
+ int cmp = comparator.compare(value, 0, packedValue, 0);
+ if (cmp == 0) {
+ lastDoc[0] = docID;
+ }
+ }
+
+ @Override
+ public Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+ });
+ if (lastDoc[0] != -1) {
+ return lastDoc[0];
+ }
+ } else {
+ do {
+ int cmp = comparator.compare(next.getMinPackedValue(), 0, value, 0);
+ if (cmp > 0) {
+ // This node doesn't have `value`, so next nodes can't either
+ break;
+ }
+ stack.push(next.clone());
+ } while (next.moveToSibling());
+ }
+ }
+
+ return -1;
+ }
+
private boolean matchNone(PointValues points, byte[] queryLowerPoint, byte[] queryUpperPoint)
throws IOException {
final ByteArrayComparator comparator =
@@ -312,8 +438,8 @@ public class IndexSortSortedNumericDocValuesRangeQuery extends Query {
Sort indexSort = context.reader().getMetaData().getSort();
if (indexSort != null
&& indexSort.getSort().length > 0
- && indexSort.getSort()[0].getField().equals(field)
- && indexSort.getSort()[0].getReverse() == false) {
+ && indexSort.getSort()[0].getField().equals(field)) {
+ final boolean reverse = indexSort.getSort()[0].getReverse();
PointValues points = context.reader().getPointValues(field);
if (points == null) {
return null;
@@ -328,44 +454,58 @@ public class IndexSortSortedNumericDocValuesRangeQuery extends Query {
return null;
}
- // Each doc that has points has exactly one point.
- if (points.size() == points.getDocCount()) {
+ if (points.size() != points.getDocCount()) {
+ return null;
+ }
- byte[] queryLowerPoint;
- byte[] queryUpperPoint;
- if (points.getBytesPerDimension() == Integer.BYTES) {
- queryLowerPoint = IntPoint.pack((int) lowerValue).bytes;
- queryUpperPoint = IntPoint.pack((int) upperValue).bytes;
+ byte[] queryLowerPoint;
+ byte[] queryUpperPoint;
+ if (points.getBytesPerDimension() == Integer.BYTES) {
+ queryLowerPoint = IntPoint.pack((int) lowerValue).bytes;
+ queryUpperPoint = IntPoint.pack((int) upperValue).bytes;
+ } else {
+ queryLowerPoint = LongPoint.pack(lowerValue).bytes;
+ queryUpperPoint = LongPoint.pack(upperValue).bytes;
+ }
+ if (lowerValue > upperValue || matchNone(points, queryLowerPoint, queryUpperPoint)) {
+ return new BoundedDocIdSetIterator(0, 0, null);
+ }
+ int minDocId, maxDocId;
+ if (matchAll(points, queryLowerPoint, queryUpperPoint)) {
+ minDocId = 0;
+ maxDocId = context.reader().maxDoc();
+ } else {
+ final ByteArrayComparator comparator =
+ ArrayUtil.getUnsignedComparator(points.getBytesPerDimension());
+
+ if (reverse) {
+ minDocId = nextDoc(points.getPointTree(), queryUpperPoint, false, comparator, true) + 1;
} else {
- queryLowerPoint = LongPoint.pack(lowerValue).bytes;
- queryUpperPoint = LongPoint.pack(upperValue).bytes;
- }
- if (lowerValue > upperValue || matchNone(points, queryLowerPoint, queryUpperPoint)) {
- return new BoundedDocIdSetIterator(0, 0, null);
+ minDocId = nextDoc(points.getPointTree(), queryLowerPoint, true, comparator, false);
+ if (minDocId == -1) {
+ // No matches
+ return new BoundedDocIdSetIterator(0, 0, null);
+ }
}
- int minDocId, maxDocId;
- if (matchAll(points, queryLowerPoint, queryUpperPoint)) {
- minDocId = 0;
- maxDocId = context.reader().maxDoc();
- } else {
- // >=queryLowerPoint
- minDocId = nextDoc(points, queryLowerPoint, true);
- if (minDocId == -1) {
+ if (reverse) {
+ maxDocId = nextDoc(points.getPointTree(), queryLowerPoint, true, comparator, true) + 1;
+ if (maxDocId == 0) {
+ // No matches
return new BoundedDocIdSetIterator(0, 0, null);
}
- // >queryUpperPoint,
- maxDocId = nextDoc(points, queryUpperPoint, false);
+ } else {
+ maxDocId = nextDoc(points.getPointTree(), queryUpperPoint, false, comparator, false);
if (maxDocId == -1) {
maxDocId = context.reader().maxDoc();
}
}
+ }
- if ((points.getDocCount() == context.reader().maxDoc())) {
- return new BoundedDocIdSetIterator(minDocId, maxDocId, null);
- } else {
- return new BoundedDocIdSetIterator(minDocId, maxDocId, delegate);
- }
+ if ((points.getDocCount() == context.reader().maxDoc())) {
+ return new BoundedDocIdSetIterator(minDocId, maxDocId, null);
+ } else {
+ return new BoundedDocIdSetIterator(minDocId, maxDocId, delegate);
}
}
return null;
diff --git a/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestIndexSortSortedNumericDocValuesRangeQuery.java b/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestIndexSortSortedNumericDocValuesRangeQuery.java
index 8f1d591b3e2..fd0e5cf3ebf 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestIndexSortSortedNumericDocValuesRangeQuery.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestIndexSortSortedNumericDocValuesRangeQuery.java
@@ -643,58 +643,112 @@ public class TestIndexSortSortedNumericDocValuesRangeQuery extends LuceneTestCas
field, lowerValue, upperValue, fallbackQuery);
}
- public void testCountWithBkd() throws IOException {
+ public void testCountWithBkdAsc() throws Exception {
+ doTestCountWithBkd(false);
+ }
+
+ public void testCountWithBkdDesc() throws Exception {
+ doTestCountWithBkd(true);
+ }
+
+ public void doTestCountWithBkd(boolean reverse) throws Exception {
String filedName = "field";
Directory dir = newDirectory();
IndexWriterConfig iwc = new IndexWriterConfig(new MockAnalyzer(random()));
- Sort indexSort = new Sort(new SortedNumericSortField(filedName, SortField.Type.LONG, false));
+ Sort indexSort = new Sort(new SortedNumericSortField(filedName, SortField.Type.LONG, reverse));
iwc.setIndexSort(indexSort);
RandomIndexWriter writer = new RandomIndexWriter(random(), dir, iwc);
- addDocWithBkd(writer, filedName, 6, 500);
- addDocWithBkd(writer, filedName, 5, 500);
- addDocWithBkd(writer, filedName, 8, 500);
- addDocWithBkd(writer, filedName, 9, 500);
addDocWithBkd(writer, filedName, 7, 500);
+ addDocWithBkd(writer, filedName, 5, 600);
+ addDocWithBkd(writer, filedName, 11, 700);
+ addDocWithBkd(writer, filedName, 13, 800);
+ addDocWithBkd(writer, filedName, 9, 900);
writer.flush();
writer.forceMerge(1);
IndexReader reader = writer.getReader();
IndexSearcher searcher = newSearcher(reader);
- Query fallbackQuery = LongPoint.newRangeQuery(filedName, 6, 8);
- Query query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 6, 8, fallbackQuery);
+ // Both bounds exist in the dataset
+ Query fallbackQuery = LongPoint.newRangeQuery(filedName, 7, 9);
+ Query query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 7, 9, fallbackQuery);
Weight weight = query.createWeight(searcher, ScoreMode.COMPLETE, 1.0f);
for (LeafReaderContext context : searcher.getLeafContexts()) {
- assertEquals(1500, weight.count(context));
+ assertEquals(1400, weight.count(context));
}
+ // Both bounds do not exist in the dataset
fallbackQuery = LongPoint.newRangeQuery(filedName, 6, 10);
query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 6, 10, fallbackQuery);
weight = query.createWeight(searcher, ScoreMode.COMPLETE, 1.0f);
for (LeafReaderContext context : searcher.getLeafContexts()) {
- assertEquals(2000, weight.count(context));
+ assertEquals(1400, weight.count(context));
+ }
+
+ // Min bound exists in the dataset, not the max
+ fallbackQuery = LongPoint.newRangeQuery(filedName, 7, 10);
+ query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 7, 10, fallbackQuery);
+ weight = query.createWeight(searcher, ScoreMode.COMPLETE, 1.0f);
+ for (LeafReaderContext context : searcher.getLeafContexts()) {
+ assertEquals(1400, weight.count(context));
+ }
+
+ // Min bound doesn't exist in the dataset, max does
+ fallbackQuery = LongPoint.newRangeQuery(filedName, 6, 9);
+ query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 7, 10, fallbackQuery);
+ weight = query.createWeight(searcher, ScoreMode.COMPLETE, 1.0f);
+ for (LeafReaderContext context : searcher.getLeafContexts()) {
+ assertEquals(1400, weight.count(context));
}
- fallbackQuery = LongPoint.newRangeQuery(filedName, 4, 6);
- query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 4, 6, fallbackQuery);
+ // Min bound is the min value of the dataset
+ fallbackQuery = LongPoint.newRangeQuery(filedName, 5, 8);
+ query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 4, 8, fallbackQuery);
weight = query.createWeight(searcher, ScoreMode.COMPLETE, 1.0f);
for (LeafReaderContext context : searcher.getLeafContexts()) {
- assertEquals(1000, weight.count(context));
+ assertEquals(1100, weight.count(context));
}
- fallbackQuery = LongPoint.newRangeQuery(filedName, 2, 10);
- query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 2, 10, fallbackQuery);
+ // Min bound is less than min value of the dataset
+ fallbackQuery = LongPoint.newRangeQuery(filedName, 4, 8);
+ query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 4, 8, fallbackQuery);
weight = query.createWeight(searcher, ScoreMode.COMPLETE, 1.0f);
for (LeafReaderContext context : searcher.getLeafContexts()) {
- assertEquals(2500, weight.count(context));
+ assertEquals(1100, weight.count(context));
}
- fallbackQuery = LongPoint.newRangeQuery(filedName, 5, 9);
- query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 2, 10, fallbackQuery);
+ // Max bound is the max value of the dataset
+ fallbackQuery = LongPoint.newRangeQuery(filedName, 10, 13);
+ query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 10, 13, fallbackQuery);
weight = query.createWeight(searcher, ScoreMode.COMPLETE, 1.0f);
for (LeafReaderContext context : searcher.getLeafContexts()) {
- assertEquals(2500, weight.count(context));
+ assertEquals(1500, weight.count(context));
}
+ // Max bound is greater than max value of the dataset
+ fallbackQuery = LongPoint.newRangeQuery(filedName, 10, 14);
+ query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 10, 14, fallbackQuery);
+ weight = query.createWeight(searcher, ScoreMode.COMPLETE, 1.0f);
+ for (LeafReaderContext context : searcher.getLeafContexts()) {
+ assertEquals(1500, weight.count(context));
+ }
+
+ // Everything matches
+ fallbackQuery = LongPoint.newRangeQuery(filedName, 2, 14);
+ query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 2, 14, fallbackQuery);
+ weight = query.createWeight(searcher, ScoreMode.COMPLETE, 1.0f);
+ for (LeafReaderContext context : searcher.getLeafContexts()) {
+ assertEquals(3500, weight.count(context));
+ }
+
+ // Bounds equal to min/max values of the dataset, everything matches
+ fallbackQuery = LongPoint.newRangeQuery(filedName, 2, 14);
+ query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 2, 14, fallbackQuery);
+ weight = query.createWeight(searcher, ScoreMode.COMPLETE, 1.0f);
+ for (LeafReaderContext context : searcher.getLeafContexts()) {
+ assertEquals(3500, weight.count(context));
+ }
+
+ // Bounds are less than the min value of the dataset
fallbackQuery = LongPoint.newRangeQuery(filedName, 2, 3);
query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 2, 3, fallbackQuery);
weight = query.createWeight(searcher, ScoreMode.COMPLETE, 1.0f);
@@ -702,8 +756,9 @@ public class TestIndexSortSortedNumericDocValuesRangeQuery extends LuceneTestCas
assertEquals(0, weight.count(context));
}
- fallbackQuery = LongPoint.newRangeQuery(filedName, 10, 11);
- query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 10, 11, fallbackQuery);
+ // Bounds are greater than the max value of the dataset
+ fallbackQuery = LongPoint.newRangeQuery(filedName, 14, 15);
+ query = new IndexSortSortedNumericDocValuesRangeQuery(filedName, 14, 15, fallbackQuery);
weight = query.createWeight(searcher, ScoreMode.COMPLETE, 1.0f);
for (LeafReaderContext context : searcher.getLeafContexts()) {
assertEquals(0, weight.count(context));
@@ -714,11 +769,19 @@ public class TestIndexSortSortedNumericDocValuesRangeQuery extends LuceneTestCas
dir.close();
}
- public void testRandomCountWithBkd() throws IOException {
+ public void testRandomCountWithBkdAsc() throws Exception {
+ doTestRandomCountWithBkd(false);
+ }
+
+ public void testRandomCountWithBkdDesc() throws Exception {
+ doTestRandomCountWithBkd(true);
+ }
+
+ private void doTestRandomCountWithBkd(boolean reverse) throws Exception {
String filedName = "field";
Directory dir = newDirectory();
IndexWriterConfig iwc = new IndexWriterConfig(new MockAnalyzer(random()));
- Sort indexSort = new Sort(new SortedNumericSortField(filedName, SortField.Type.LONG, false));
+ Sort indexSort = new Sort(new SortedNumericSortField(filedName, SortField.Type.LONG, reverse));
iwc.setIndexSort(indexSort);
RandomIndexWriter writer = new RandomIndexWriter(random(), dir, iwc);
Random random = random();