mikemccand commented on code in PR #15979: URL: https://github.com/apache/lucene/pull/15979#discussion_r3665528522
########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/Lucene106DedupHnswVectorsFormat.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.codecs.lucene106.dedup; + +import static org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat.DEFAULT_BEAM_WIDTH; +import static org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat.DEFAULT_MAX_CONN; +import static org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat.DEFAULT_NUM_MERGE_WORKER; +import static org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat.HNSW_GRAPH_THRESHOLD; +import static org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat.MAXIMUM_BEAM_WIDTH; +import static org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat.MAXIMUM_MAX_CONN; + +import java.io.IOException; +import java.util.concurrent.ExecutorService; +import org.apache.lucene.codecs.KnnVectorsFormat; +import org.apache.lucene.codecs.KnnVectorsReader; +import org.apache.lucene.codecs.KnnVectorsWriter; +import org.apache.lucene.codecs.hnsw.FlatVectorsFormat; +import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsReader; +import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsWriter; +import org.apache.lucene.index.MergePolicy; +import org.apache.lucene.index.MergeScheduler; +import org.apache.lucene.index.SegmentReadState; +import org.apache.lucene.index.SegmentWriteState; +import org.apache.lucene.search.TaskExecutor; +import org.apache.lucene.util.hnsw.HnswGraph; + +/** + * An HNSW vector format that de-duplicates raw vectors. + * + * <p>Graph construction and search are identical to {@link + * org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat}. A {@link DedupFlatVectorsFormat} is + * used for the flat vector storage, which stores each distinct vector exactly once, shared across + * all documents that reference it. This trades a small amount of indexing work for reduced storage + * when vectors repeat, e.g. multiple fields derived from the same embedding or heavily duplicated + * content. + * + * @lucene.experimental + */ +public final class Lucene106DedupHnswVectorsFormat extends KnnVectorsFormat { Review Comment: Maybe we could build the HNSW graph in reverse cardinality order: field with most vectors is built first. For subsequent fields, we could consult prior HNSW graphs to extract a "subset graph", which might be highly disconnected, holding just nodes that also exist in this field, and likewise prune transitions. Then use this partial/degraded HNSW graph as a starting point / seeds for building the real HNSW graph for this field. Not sure it'd be worth the work ... for very restrictive fields, often that graph would be pointless (no nodes connect to any others). Just an idea... ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupFlatVectorsReader.java: ########## @@ -0,0 +1,359 @@ +/* + * 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.codecs.lucene106.dedup; + +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.META_CODEC_NAME; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.META_EXTENSION; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VECTOR_DATA_CODEC_NAME; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VECTOR_DATA_EXTENSION; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VERSION_CURRENT; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VERSION_START; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.loadDedupBytes; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.loadDedupFloat16s; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.loadDedupFloats; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.readFieldInfo; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.readGroupInfo; +import static org.apache.lucene.index.VectorEncoding.BYTE; +import static org.apache.lucene.index.VectorEncoding.FLOAT16; +import static org.apache.lucene.index.VectorEncoding.FLOAT32; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import org.apache.lucene.codecs.CodecUtil; +import org.apache.lucene.codecs.hnsw.FlatVectorsReader; +import org.apache.lucene.codecs.hnsw.FlatVectorsScorer; +import org.apache.lucene.codecs.lucene106.dedup.DedupUtil.GroupInfo; +import org.apache.lucene.codecs.lucene106.dedup.DedupUtil.ReadFieldInfo; +import org.apache.lucene.index.ByteVectorValues; +import org.apache.lucene.index.CorruptIndexException; +import org.apache.lucene.index.FieldInfo; +import org.apache.lucene.index.FieldInfos; +import org.apache.lucene.index.Float16VectorValues; +import org.apache.lucene.index.FloatVectorValues; +import org.apache.lucene.index.IndexFileNames; +import org.apache.lucene.index.MergePolicy; +import org.apache.lucene.index.SegmentReadState; +import org.apache.lucene.index.VectorEncoding; +import org.apache.lucene.store.ChecksumIndexInput; +import org.apache.lucene.store.DataAccessHint; +import org.apache.lucene.store.FileDataHint; +import org.apache.lucene.store.FileTypeHint; +import org.apache.lucene.store.IOContext; +import org.apache.lucene.store.IndexInput; +import org.apache.lucene.util.IOUtils; +import org.apache.lucene.util.RamUsageEstimator; +import org.apache.lucene.util.hnsw.RandomVectorScorer; + +/** + * Reads de-duplicated flat vectors written by {@link DedupFlatVectorsWriter}. Each field exposes a + * view backed by its group's shared vectors and an {@code ordToVecOrd} translation map. + * + * @lucene.experimental + */ +final class DedupFlatVectorsReader extends FlatVectorsReader { + private static final long SHALLOW_SIZE = + RamUsageEstimator.shallowSizeOfInstance(DedupFlatVectorsReader.class); + + private final FlatVectorsScorer vectorsScorer; + private final Map<String, FieldEntry> fields; + private final IndexInput vectorData; + + DedupFlatVectorsReader(SegmentReadState state, FlatVectorsScorer vectorsScorer) + throws IOException { + + this.vectorsScorer = vectorsScorer; + this.fields = new HashMap<>(); + + String metaFileName = + IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, META_EXTENSION); + + int versionMeta; + try (ChecksumIndexInput meta = state.directory.openChecksumInput(metaFileName)) { + Throwable priorE = null; + try { + versionMeta = + CodecUtil.checkIndexHeader( + meta, + META_CODEC_NAME, + VERSION_START, + VERSION_CURRENT, + state.segmentInfo.getId(), + state.segmentSuffix); + readMetaBody(meta, state.fieldInfos); + } catch (Throwable e) { + priorE = e; + throw e; + } finally { + CodecUtil.checkFooter(meta, priorE); + } + } + + this.vectorData = openDataInput(state, versionMeta); + } + + private void readMetaBody(ChecksumIndexInput meta, FieldInfos fieldInfos) throws IOException { + List<GroupInfo> groupInfos = new ArrayList<>(); + while (true) { + GroupInfo groupInfo = readGroupInfo(meta); + if (groupInfo == null) { + break; + } + groupInfos.add(groupInfo); + } + + while (true) { + ReadFieldInfo fieldInfo = readFieldInfo(meta); + if (fieldInfo == null) { + break; + } + + FieldInfo info = fieldInfos.fieldInfo(fieldInfo.fieldNumber()); + if (info == null) { + throw new CorruptIndexException("Invalid field number: " + fieldInfo.fieldNumber(), meta); + } else if (fieldInfo.function() != info.getVectorSimilarityFunction()) { + throw new CorruptIndexException( + "Invalid vector function: indexed=" Review Comment: Maybe `Inconsistent ...`? They are valid functions, just disagreeing with one another, surprisngly. ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupFlatVectorsReader.java: ########## @@ -0,0 +1,359 @@ +/* + * 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.codecs.lucene106.dedup; + +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.META_CODEC_NAME; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.META_EXTENSION; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VECTOR_DATA_CODEC_NAME; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VECTOR_DATA_EXTENSION; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VERSION_CURRENT; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VERSION_START; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.loadDedupBytes; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.loadDedupFloat16s; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.loadDedupFloats; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.readFieldInfo; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.readGroupInfo; +import static org.apache.lucene.index.VectorEncoding.BYTE; +import static org.apache.lucene.index.VectorEncoding.FLOAT16; +import static org.apache.lucene.index.VectorEncoding.FLOAT32; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import org.apache.lucene.codecs.CodecUtil; +import org.apache.lucene.codecs.hnsw.FlatVectorsReader; +import org.apache.lucene.codecs.hnsw.FlatVectorsScorer; +import org.apache.lucene.codecs.lucene106.dedup.DedupUtil.GroupInfo; +import org.apache.lucene.codecs.lucene106.dedup.DedupUtil.ReadFieldInfo; +import org.apache.lucene.index.ByteVectorValues; +import org.apache.lucene.index.CorruptIndexException; +import org.apache.lucene.index.FieldInfo; +import org.apache.lucene.index.FieldInfos; +import org.apache.lucene.index.Float16VectorValues; +import org.apache.lucene.index.FloatVectorValues; +import org.apache.lucene.index.IndexFileNames; +import org.apache.lucene.index.MergePolicy; +import org.apache.lucene.index.SegmentReadState; +import org.apache.lucene.index.VectorEncoding; +import org.apache.lucene.store.ChecksumIndexInput; +import org.apache.lucene.store.DataAccessHint; +import org.apache.lucene.store.FileDataHint; +import org.apache.lucene.store.FileTypeHint; +import org.apache.lucene.store.IOContext; +import org.apache.lucene.store.IndexInput; +import org.apache.lucene.util.IOUtils; +import org.apache.lucene.util.RamUsageEstimator; +import org.apache.lucene.util.hnsw.RandomVectorScorer; + +/** + * Reads de-duplicated flat vectors written by {@link DedupFlatVectorsWriter}. Each field exposes a + * view backed by its group's shared vectors and an {@code ordToVecOrd} translation map. + * + * @lucene.experimental + */ +final class DedupFlatVectorsReader extends FlatVectorsReader { + private static final long SHALLOW_SIZE = + RamUsageEstimator.shallowSizeOfInstance(DedupFlatVectorsReader.class); + + private final FlatVectorsScorer vectorsScorer; + private final Map<String, FieldEntry> fields; + private final IndexInput vectorData; + + DedupFlatVectorsReader(SegmentReadState state, FlatVectorsScorer vectorsScorer) + throws IOException { + + this.vectorsScorer = vectorsScorer; + this.fields = new HashMap<>(); + + String metaFileName = + IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, META_EXTENSION); + + int versionMeta; + try (ChecksumIndexInput meta = state.directory.openChecksumInput(metaFileName)) { + Throwable priorE = null; + try { + versionMeta = + CodecUtil.checkIndexHeader( + meta, + META_CODEC_NAME, + VERSION_START, + VERSION_CURRENT, + state.segmentInfo.getId(), + state.segmentSuffix); + readMetaBody(meta, state.fieldInfos); + } catch (Throwable e) { + priorE = e; + throw e; + } finally { + CodecUtil.checkFooter(meta, priorE); + } + } + + this.vectorData = openDataInput(state, versionMeta); + } + + private void readMetaBody(ChecksumIndexInput meta, FieldInfos fieldInfos) throws IOException { + List<GroupInfo> groupInfos = new ArrayList<>(); + while (true) { + GroupInfo groupInfo = readGroupInfo(meta); + if (groupInfo == null) { + break; + } + groupInfos.add(groupInfo); + } + + while (true) { + ReadFieldInfo fieldInfo = readFieldInfo(meta); + if (fieldInfo == null) { + break; + } + + FieldInfo info = fieldInfos.fieldInfo(fieldInfo.fieldNumber()); + if (info == null) { + throw new CorruptIndexException("Invalid field number: " + fieldInfo.fieldNumber(), meta); + } else if (fieldInfo.function() != info.getVectorSimilarityFunction()) { + throw new CorruptIndexException( + "Invalid vector function: indexed=" + + fieldInfo.function() + + ", actual=" + + info.getVectorSimilarityFunction(), + meta); + } else if (fieldInfo.dimension() != info.getVectorDimension()) { + throw new CorruptIndexException( + "Invalid vector dimension: indexed=" Review Comment: Also `Inconsistent`? ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupFlatVectorsFormat.java: ########## @@ -0,0 +1,133 @@ +/* + * 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.codecs.lucene106.dedup; + +import java.io.IOException; +import org.apache.lucene.codecs.hnsw.FlatVectorsFormat; +import org.apache.lucene.codecs.hnsw.FlatVectorsReader; +import org.apache.lucene.codecs.hnsw.FlatVectorsWriter; +import org.apache.lucene.index.SegmentReadState; +import org.apache.lucene.index.SegmentWriteState; + +/** + * Flat vector format that stores each distinct vector once. + * + * <p>Vectors that share the same dimension and encoding form a <i>group</i>. Within a group, an + * identical vector is stored a single time regardless of how many documents (across all fields that + * map to that group) reference it; each field then keeps a per-document {@code ordToVecOrd} map + * from its document ordinal to the group ordinal of the shared vector. This is well suited to + * indexes with repeated vectors, e.g. several fields derived from the same embedding, or heavily + * duplicated content. + * + * <h2>.vdd (vector de-dup data) file</h2> Review Comment: Are there use cases for flat vector formats without HNSW on top? E.g. exact (brute force) vector search, if I know my queries will only need to look at a very small number of vectors each time. This dedup format would also be helpful for such use cases, e.g. brute force vector search within specific (dedup'd) fields. Are flat vector readers `Iterable` (to step through all docs that have a vector for that field)? Hmm, there is [`iterator` method](https://github.com/apache/lucene/blob/61e22dd3e60e88640ad0d97e80a8ebb3f132be74/lucene/core/src/java/org/apache/lucene/index/KnnVectorValues.java#L94-L97) but `KnnVectorValues` doesn't impl `Iterable`? The flat vector writers seem to track `docsWithField`, I guess for assigning vector ordinals (`docid` -> `vecOrd` in the existing non-dedup flat writer) when at least one doc is missing the field. OK and `KnnVectorValues` has `createSparse/DenseIterator`. So such use cases could also efficiently iterate all docs that have a given vector field, nice! ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupUtil.java: ########## @@ -0,0 +1,699 @@ +/* + * 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.codecs.lucene106.dedup; + +import static org.apache.lucene.index.VectorEncoding.BYTE; +import static org.apache.lucene.index.VectorEncoding.FLOAT16; +import static org.apache.lucene.index.VectorEncoding.FLOAT32; +import static org.apache.lucene.util.StringHelper.GOOD_FAST_HASH_SEED; +import static org.apache.lucene.util.StringHelper.murmurhash3_x64_128; + +import java.io.IOException; +import org.apache.lucene.codecs.hnsw.FlatVectorsScorer; +import org.apache.lucene.codecs.lucene95.OffHeapByteVectorValues; +import org.apache.lucene.codecs.lucene95.OffHeapFloat16VectorValues; +import org.apache.lucene.codecs.lucene95.OffHeapFloatVectorValues; +import org.apache.lucene.codecs.lucene95.OrdToDocDISIReaderConfiguration; +import org.apache.lucene.index.ByteVectorValues; +import org.apache.lucene.index.DocsWithFieldSet; +import org.apache.lucene.index.FieldInfo; +import org.apache.lucene.index.Float16VectorValues; +import org.apache.lucene.index.FloatVectorValues; +import org.apache.lucene.index.KnnVectorValues; +import org.apache.lucene.index.VectorEncoding; +import org.apache.lucene.index.VectorSimilarityFunction; +import org.apache.lucene.internal.hppc.IntArrayList; +import org.apache.lucene.search.DocIdSetIterator; +import org.apache.lucene.search.VectorScorer; +import org.apache.lucene.store.IndexInput; +import org.apache.lucene.store.IndexOutput; +import org.apache.lucene.store.RandomAccessInput; +import org.apache.lucene.util.ArrayUtil; +import org.apache.lucene.util.LongValues; +import org.apache.lucene.util.hnsw.RandomVectorScorer; +import org.apache.lucene.util.packed.DirectReader; +import org.apache.lucene.util.packed.DirectWriter; + +/** + * Shared helpers for the de-duplicating flat format: reading / writing field and group metadata, + * vector hashing and alignment, and the {@link DedupVectorValues} views used on the read path. + * + * @lucene.experimental + */ +final class DedupUtil { + + private static final int DIRECT_MONOTONIC_BLOCK_SHIFT = 16; + + private static final int END_MARKER = -1; + + private static final int ORD_TO_VEC_ALIGN_BYTES = 4; + + // TODO: This is the number of bits used to write each group ordinal in the index-backed per-field + // OrdToVecOrd mapping. Evaluate using fewer bits to reduce index size, at the expense of + // costlier lookups. + private static final int ORD_TO_VEC_BITS_PER_VALUE = 32; + + static final int SCRATCH_SIZE = 16; Review Comment: Rename to `SCRATCH_INITIAL_SIZE` and add comment `// initial allocation size for internal re-used int[] scratch buffers` or so? ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupFlatVectorsReader.java: ########## @@ -0,0 +1,359 @@ +/* + * 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.codecs.lucene106.dedup; + +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.META_CODEC_NAME; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.META_EXTENSION; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VECTOR_DATA_CODEC_NAME; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VECTOR_DATA_EXTENSION; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VERSION_CURRENT; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VERSION_START; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.loadDedupBytes; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.loadDedupFloat16s; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.loadDedupFloats; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.readFieldInfo; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.readGroupInfo; +import static org.apache.lucene.index.VectorEncoding.BYTE; +import static org.apache.lucene.index.VectorEncoding.FLOAT16; +import static org.apache.lucene.index.VectorEncoding.FLOAT32; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import org.apache.lucene.codecs.CodecUtil; +import org.apache.lucene.codecs.hnsw.FlatVectorsReader; +import org.apache.lucene.codecs.hnsw.FlatVectorsScorer; +import org.apache.lucene.codecs.lucene106.dedup.DedupUtil.GroupInfo; +import org.apache.lucene.codecs.lucene106.dedup.DedupUtil.ReadFieldInfo; +import org.apache.lucene.index.ByteVectorValues; +import org.apache.lucene.index.CorruptIndexException; +import org.apache.lucene.index.FieldInfo; +import org.apache.lucene.index.FieldInfos; +import org.apache.lucene.index.Float16VectorValues; +import org.apache.lucene.index.FloatVectorValues; +import org.apache.lucene.index.IndexFileNames; +import org.apache.lucene.index.MergePolicy; +import org.apache.lucene.index.SegmentReadState; +import org.apache.lucene.index.VectorEncoding; +import org.apache.lucene.store.ChecksumIndexInput; +import org.apache.lucene.store.DataAccessHint; +import org.apache.lucene.store.FileDataHint; +import org.apache.lucene.store.FileTypeHint; +import org.apache.lucene.store.IOContext; +import org.apache.lucene.store.IndexInput; +import org.apache.lucene.util.IOUtils; +import org.apache.lucene.util.RamUsageEstimator; +import org.apache.lucene.util.hnsw.RandomVectorScorer; + +/** + * Reads de-duplicated flat vectors written by {@link DedupFlatVectorsWriter}. Each field exposes a + * view backed by its group's shared vectors and an {@code ordToVecOrd} translation map. + * + * @lucene.experimental + */ +final class DedupFlatVectorsReader extends FlatVectorsReader { + private static final long SHALLOW_SIZE = + RamUsageEstimator.shallowSizeOfInstance(DedupFlatVectorsReader.class); + + private final FlatVectorsScorer vectorsScorer; + private final Map<String, FieldEntry> fields; + private final IndexInput vectorData; + + DedupFlatVectorsReader(SegmentReadState state, FlatVectorsScorer vectorsScorer) + throws IOException { + + this.vectorsScorer = vectorsScorer; + this.fields = new HashMap<>(); + + String metaFileName = + IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, META_EXTENSION); + + int versionMeta; + try (ChecksumIndexInput meta = state.directory.openChecksumInput(metaFileName)) { + Throwable priorE = null; + try { + versionMeta = + CodecUtil.checkIndexHeader( + meta, + META_CODEC_NAME, + VERSION_START, + VERSION_CURRENT, + state.segmentInfo.getId(), + state.segmentSuffix); + readMetaBody(meta, state.fieldInfos); + } catch (Throwable e) { + priorE = e; + throw e; + } finally { + CodecUtil.checkFooter(meta, priorE); + } + } + + this.vectorData = openDataInput(state, versionMeta); + } + + private void readMetaBody(ChecksumIndexInput meta, FieldInfos fieldInfos) throws IOException { + List<GroupInfo> groupInfos = new ArrayList<>(); + while (true) { + GroupInfo groupInfo = readGroupInfo(meta); + if (groupInfo == null) { + break; + } + groupInfos.add(groupInfo); + } + + while (true) { + ReadFieldInfo fieldInfo = readFieldInfo(meta); + if (fieldInfo == null) { + break; + } + + FieldInfo info = fieldInfos.fieldInfo(fieldInfo.fieldNumber()); + if (info == null) { + throw new CorruptIndexException("Invalid field number: " + fieldInfo.fieldNumber(), meta); + } else if (fieldInfo.function() != info.getVectorSimilarityFunction()) { + throw new CorruptIndexException( + "Invalid vector function: indexed=" + + fieldInfo.function() + + ", actual=" + + info.getVectorSimilarityFunction(), + meta); + } else if (fieldInfo.dimension() != info.getVectorDimension()) { + throw new CorruptIndexException( + "Invalid vector dimension: indexed=" + + fieldInfo.dimension() + + ", actual=" + + info.getVectorDimension(), + meta); + } else if (fieldInfo.encoding() != info.getVectorEncoding()) { + throw new CorruptIndexException( + "Invalid vector encoding: indexed=" Review Comment: `Inconsistent`? ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupUtil.java: ########## @@ -0,0 +1,699 @@ +/* + * 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.codecs.lucene106.dedup; + +import static org.apache.lucene.index.VectorEncoding.BYTE; +import static org.apache.lucene.index.VectorEncoding.FLOAT16; +import static org.apache.lucene.index.VectorEncoding.FLOAT32; +import static org.apache.lucene.util.StringHelper.GOOD_FAST_HASH_SEED; +import static org.apache.lucene.util.StringHelper.murmurhash3_x64_128; + +import java.io.IOException; +import org.apache.lucene.codecs.hnsw.FlatVectorsScorer; +import org.apache.lucene.codecs.lucene95.OffHeapByteVectorValues; +import org.apache.lucene.codecs.lucene95.OffHeapFloat16VectorValues; +import org.apache.lucene.codecs.lucene95.OffHeapFloatVectorValues; +import org.apache.lucene.codecs.lucene95.OrdToDocDISIReaderConfiguration; +import org.apache.lucene.index.ByteVectorValues; +import org.apache.lucene.index.DocsWithFieldSet; +import org.apache.lucene.index.FieldInfo; +import org.apache.lucene.index.Float16VectorValues; +import org.apache.lucene.index.FloatVectorValues; +import org.apache.lucene.index.KnnVectorValues; +import org.apache.lucene.index.VectorEncoding; +import org.apache.lucene.index.VectorSimilarityFunction; +import org.apache.lucene.internal.hppc.IntArrayList; +import org.apache.lucene.search.DocIdSetIterator; +import org.apache.lucene.search.VectorScorer; +import org.apache.lucene.store.IndexInput; +import org.apache.lucene.store.IndexOutput; +import org.apache.lucene.store.RandomAccessInput; +import org.apache.lucene.util.ArrayUtil; +import org.apache.lucene.util.LongValues; +import org.apache.lucene.util.hnsw.RandomVectorScorer; +import org.apache.lucene.util.packed.DirectReader; +import org.apache.lucene.util.packed.DirectWriter; + +/** + * Shared helpers for the de-duplicating flat format: reading / writing field and group metadata, + * vector hashing and alignment, and the {@link DedupVectorValues} views used on the read path. + * + * @lucene.experimental + */ +final class DedupUtil { + + private static final int DIRECT_MONOTONIC_BLOCK_SHIFT = 16; + + private static final int END_MARKER = -1; + + private static final int ORD_TO_VEC_ALIGN_BYTES = 4; + + // TODO: This is the number of bits used to write each group ordinal in the index-backed per-field + // OrdToVecOrd mapping. Evaluate using fewer bits to reduce index size, at the expense of + // costlier lookups. + private static final int ORD_TO_VEC_BITS_PER_VALUE = 32; + + static final int SCRATCH_SIZE = 16; + + /** Key used to group vectors (dimension + encoding). */ + record GroupKey(int dimension, VectorEncoding encoding) { + GroupKey(FieldInfo fieldInfo) { + this(fieldInfo.getVectorDimension(), fieldInfo.getVectorEncoding()); + } + } + + /** + * Vector values that share a single copy of each distinct vector across the documents and fields + * that reference it. + * + * <p>Every instance is backed by two views: the {@code fieldView} maps ordinals to docs and + * drives iteration (one entry per document), while the {@code groupView} holds the de-duplicated + * vectors (one entry per distinct vector). {@code ordToVecOrd} translates a document ordinal into + * its group ordinal. + */ + sealed interface DedupVectorValues { + /** The dense view over distinct vectors, indexed by group ordinal. */ + KnnVectorValues getGroupView(); + + /** Maps a per-document ordinal to its group ordinal in {@link #getGroupView()}. */ + OrdToVecOrd getOrdToVecOrd(); + } + + /** + * Maps a field's per-document ordinal to the ordinal of its (shared) vector within the group. + * Backed on-heap while writing and off-heap while reading. + */ + sealed interface OrdToVecOrd { + int get(int ord); + + OrdToVecOrd copy() throws IOException; + } + + record GroupInfo( + int groupOrd, + int dimension, + VectorEncoding encoding, + int groupSize, + long vectorDataOffset, + long vectorDataSize) {} + + static void writeGroupInfo(IndexOutput meta, GroupInfo groupInfo) throws IOException { + meta.writeInt(groupInfo.groupOrd); + meta.writeInt(groupInfo.dimension); + meta.writeInt(groupInfo.encoding.ordinal()); + meta.writeInt(groupInfo.groupSize); + meta.writeLong(groupInfo.vectorDataOffset); + meta.writeLong(groupInfo.vectorDataSize); + } + + static void writeEndOfGroups(IndexOutput meta) throws IOException { + meta.writeInt(END_MARKER); + } + + static GroupInfo readGroupInfo(IndexInput meta) throws IOException { + int groupOrd = meta.readInt(); + if (groupOrd == END_MARKER) { + return null; + } + + int dimension = meta.readInt(); + VectorEncoding encoding = VectorEncoding.values()[meta.readInt()]; + int groupSize = meta.readInt(); + long vectorDataOffset = meta.readLong(); + long vectorDataSize = meta.readLong(); + + return new GroupInfo( + groupOrd, dimension, encoding, groupSize, vectorDataOffset, vectorDataSize); + } + + record WriteFieldInfo( + int fieldNumber, + VectorSimilarityFunction function, + int dimension, + VectorEncoding encoding, + int groupOrd, + int vectorCount, + int maxDoc, + DocsWithFieldSet docs, + OrdToVecOrd ordToVecOrd) {} + + static void writeFieldInfo(IndexOutput meta, IndexOutput vectorData, WriteFieldInfo fieldInfo) + throws IOException { + + meta.writeInt(fieldInfo.fieldNumber); + meta.writeInt(fieldInfo.function.ordinal()); + meta.writeInt(fieldInfo.dimension); + meta.writeInt(fieldInfo.encoding.ordinal()); + meta.writeInt(fieldInfo.groupOrd); + meta.writeInt(fieldInfo.vectorCount); + + // write ordToDoc + OrdToDocDISIReaderConfiguration.writeStoredMeta( + DIRECT_MONOTONIC_BLOCK_SHIFT, + meta, + vectorData, + fieldInfo.vectorCount, + fieldInfo.maxDoc, + fieldInfo.docs); + + // write ordToVec + long ordToVecOffset = vectorData.alignFilePointer(ORD_TO_VEC_ALIGN_BYTES); + DirectWriter writer = + DirectWriter.getInstance(vectorData, fieldInfo.vectorCount, ORD_TO_VEC_BITS_PER_VALUE); + for (int i = 0; i < fieldInfo.vectorCount; i++) { + writer.add(fieldInfo.ordToVecOrd.get(i)); + } + writer.finish(); + long ordToVecSize = vectorData.getFilePointer() - ordToVecOffset; + + meta.writeLong(ordToVecOffset); + meta.writeLong(ordToVecSize); + } + + static void writeEndOfFields(IndexOutput meta) throws IOException { + meta.writeInt(END_MARKER); + } + + record ReadFieldInfo( + int fieldNumber, + VectorSimilarityFunction function, + int dimension, + VectorEncoding encoding, + int groupOrd, + int vectorCount, + OrdToDocDISIReaderConfiguration ordToDoc, + long ordToVecOffset, + long ordToVecSize) {} + + static ReadFieldInfo readFieldInfo(IndexInput meta) throws IOException { + + int fieldNumber = meta.readInt(); + if (fieldNumber == END_MARKER) { + return null; + } + + VectorSimilarityFunction function = VectorSimilarityFunction.values()[meta.readInt()]; + int dimension = meta.readInt(); + VectorEncoding encoding = VectorEncoding.values()[meta.readInt()]; + int groupOrd = meta.readInt(); + int vectorCount = meta.readInt(); + OrdToDocDISIReaderConfiguration ordToDoc = + OrdToDocDISIReaderConfiguration.fromStoredMeta(meta, vectorCount); + long ordToVecOffset = meta.readLong(); + long ordToVecSize = meta.readLong(); + + return new ReadFieldInfo( + fieldNumber, + function, + dimension, + encoding, + groupOrd, + vectorCount, + ordToDoc, + ordToVecOffset, + ordToVecSize); + } + + static long hashBytes(byte[] bytes) { + return murmurhash3_x64_128(bytes, 0, bytes.length, GOOD_FAST_HASH_SEED)[0]; + } + + static long alignBytes(IndexOutput output, VectorEncoding encoding) throws IOException { + int alignBytes = + switch (encoding) { + case BYTE -> 4; + case FLOAT32, FLOAT16 -> 64; + }; + return output.alignFilePointer(alignBytes); + } + + /** On-heap map used during a flush, backed directly by the buffered ordinals. */ + record OrdToVecOrdArrayList(IntArrayList ordToVecOrd) implements OrdToVecOrd { + @Override + public int get(int ord) { + return ordToVecOrd.get(ord); + } + + @Override + public OrdToVecOrd copy() { + return new OrdToVecOrdArrayList(ordToVecOrd); + } + } + + /** On-heap map used during a sorted flush, indirecting through a new-to-old ordinal map. */ + record OrdToVecOrdMappedArrayList(int[] map, IntArrayList ordToVecOrd) implements OrdToVecOrd { + @Override + public int get(int ord) { + return ordToVecOrd.get(map[ord]); + } + + @Override + public OrdToVecOrd copy() { + return new OrdToVecOrdMappedArrayList(map, ordToVecOrd); + } + } + + /** Off-heap map used while reading, backed by a {@link DirectReader}. */ + static final class OrdToVecOrdOffHeap implements OrdToVecOrd { + private final IndexInput vectorData; + private final long ordToVecOffset; + private final long ordToVecSize; + private final LongValues values; + + OrdToVecOrdOffHeap(IndexInput vectorData, long ordToVecOffset, long ordToVecSize) + throws IOException { + this.vectorData = vectorData; + this.ordToVecOffset = ordToVecOffset; + this.ordToVecSize = ordToVecSize; + + RandomAccessInput slice = vectorData.randomAccessSlice(ordToVecOffset, ordToVecSize); + this.values = DirectReader.getInstance(slice, ORD_TO_VEC_BITS_PER_VALUE); + } + + @Override + public int get(int v) { + return (int) values.get(v); + } + + @Override + public OrdToVecOrd copy() throws IOException { + return new OrdToVecOrdOffHeap(vectorData, ordToVecOffset, ordToVecSize); + } + } + + static ByteVectorValues loadDedupBytes( + FlatVectorsScorer vectorsScorer, + VectorSimilarityFunction function, + OrdToDocDISIReaderConfiguration configuration, + int dimension, + int groupSize, + IndexInput vectorData, + long vectorDataOffset, + long vectorDataSize, + long ordToVecOffset, + long ordToVecSize) + throws IOException { + + final OffHeapByteVectorValues fieldView = + OffHeapByteVectorValues.load( + function, vectorsScorer, configuration, BYTE, dimension, 0, 0, vectorData); + + final OffHeapByteVectorValues groupView = + new OffHeapByteVectorValues.DenseOffHeapVectorValues( + dimension, + groupSize, + vectorData.slice("group-slice", vectorDataOffset, vectorDataSize), + fieldView.getVectorByteLength(), + vectorsScorer, + function); + + final OrdToVecOrd ordToVecOrd = + new OrdToVecOrdOffHeap(vectorData, ordToVecOffset, ordToVecSize); + + return new ByteImpl(vectorsScorer, function, fieldView, groupView, ordToVecOrd); + } + + /** {@link DedupVectorValues} over byte vectors. */ + private static final class ByteImpl extends ByteVectorValues implements DedupVectorValues { + private final FlatVectorsScorer vectorsScorer; + private final VectorSimilarityFunction function; + private final ByteVectorValues fieldView; + private final ByteVectorValues groupView; + private final OrdToVecOrd ordToVecOrd; + private int[] scratch; + + ByteImpl( + FlatVectorsScorer vectorsScorer, + VectorSimilarityFunction function, + ByteVectorValues fieldView, + ByteVectorValues groupView, + OrdToVecOrd ordToVecOrd) { + this.vectorsScorer = vectorsScorer; + this.function = function; + this.fieldView = fieldView; + this.groupView = groupView; + this.ordToVecOrd = ordToVecOrd; + this.scratch = new int[SCRATCH_SIZE]; + } + + @Override + public ByteVectorValues getGroupView() { + return groupView; + } + + @Override + public OrdToVecOrd getOrdToVecOrd() { + return ordToVecOrd; + } + + @Override + public int ordToDoc(int ord) { + return fieldView.ordToDoc(ord); + } + + @Override + public void prefetch(int[] ordsToPrefetch, int numOrds) throws IOException { + if (scratch.length < ordsToPrefetch.length) { // grow if needed + scratch = ArrayUtil.grow(scratch, ordsToPrefetch.length); + } + for (int i = 0; i < numOrds; i++) { + scratch[i] = ordToVecOrd.get(ordsToPrefetch[i]); + } + groupView.prefetch(scratch, numOrds); + } + + @Override + public byte[] vectorValue(int ord) throws IOException { + return groupView.vectorValue(ordToVecOrd.get(ord)); + } + + @Override + public int dimension() { + return fieldView.dimension(); + } + + @Override + public int size() { + return fieldView.size(); + } + + @Override + public ByteImpl copy() throws IOException { + return new ByteImpl( + vectorsScorer, function, fieldView.copy(), groupView.copy(), ordToVecOrd.copy()); + } + + @Override + public DocIndexIterator iterator() { + return fieldView.iterator(); + } + + @Override + public VectorScorer scorer(byte[] target) throws IOException { + if (size() == 0) { + return null; + } + ByteImpl copy = copy(); + DocIndexIterator iterator = copy.iterator(); + RandomVectorScorer vectorScorer = vectorsScorer.getRandomVectorScorer(function, copy, target); + return new VectorScorer() { + @Override + public float score() throws IOException { + return vectorScorer.score(iterator.index()); + } + + @Override + public DocIdSetIterator iterator() { + return iterator; + } + + @Override + public Bulk bulk(DocIdSetIterator matchingDocs) { + return Bulk.fromRandomScorerDense(vectorScorer, iterator, matchingDocs); + } + }; + } + } + + static FloatVectorValues loadDedupFloats( + FlatVectorsScorer vectorsScorer, + VectorSimilarityFunction function, + OrdToDocDISIReaderConfiguration configuration, + int dimension, + int groupSize, + IndexInput vectorData, + long vectorDataOffset, + long vectorDataSize, + long ordToVecOffset, + long ordToVecSize) + throws IOException { + + final OffHeapFloatVectorValues fieldView = + OffHeapFloatVectorValues.load( + function, vectorsScorer, configuration, FLOAT32, dimension, 0, 0, vectorData); + + final OffHeapFloatVectorValues groupView = + new OffHeapFloatVectorValues.DenseOffHeapVectorValues( + dimension, + groupSize, + vectorData.slice("group-slice", vectorDataOffset, vectorDataSize), + fieldView.getVectorByteLength(), + vectorsScorer, + function); + + final OrdToVecOrd ordToVecOrd = + new OrdToVecOrdOffHeap(vectorData, ordToVecOffset, ordToVecSize); + + return new FloatImpl(vectorsScorer, function, fieldView, groupView, ordToVecOrd); + } + + /** {@link DedupVectorValues} over float vectors. */ + private static final class FloatImpl extends FloatVectorValues implements DedupVectorValues { + private final FlatVectorsScorer vectorsScorer; + private final VectorSimilarityFunction function; + private final FloatVectorValues fieldView; + private final FloatVectorValues groupView; + private final OrdToVecOrd ordToVecOrd; + private int[] scratch; + + FloatImpl( + FlatVectorsScorer vectorsScorer, + VectorSimilarityFunction function, + FloatVectorValues fieldView, + FloatVectorValues groupView, + OrdToVecOrd ordToVecOrd) { + this.vectorsScorer = vectorsScorer; + this.function = function; + this.fieldView = fieldView; + this.groupView = groupView; + this.ordToVecOrd = ordToVecOrd; + this.scratch = new int[SCRATCH_SIZE]; + } + + @Override + public FloatVectorValues getGroupView() { + return groupView; + } + + @Override + public OrdToVecOrd getOrdToVecOrd() { + return ordToVecOrd; + } + + @Override + public int ordToDoc(int ord) { + return fieldView.ordToDoc(ord); + } + + @Override + public void prefetch(int[] ordsToPrefetch, int numOrds) throws IOException { + if (scratch.length < ordsToPrefetch.length) { // grow if needed + scratch = ArrayUtil.grow(scratch, ordsToPrefetch.length); + } + for (int i = 0; i < numOrds; i++) { + scratch[i] = ordToVecOrd.get(ordsToPrefetch[i]); + } + groupView.prefetch(scratch, numOrds); Review Comment: I'm glad we are implementing prefetch here (and in existting vector formats) -- this is vital for reranking use-case. ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupFlatVectorsFormat.java: ########## @@ -0,0 +1,133 @@ +/* + * 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.codecs.lucene106.dedup; + +import java.io.IOException; +import org.apache.lucene.codecs.hnsw.FlatVectorsFormat; +import org.apache.lucene.codecs.hnsw.FlatVectorsReader; +import org.apache.lucene.codecs.hnsw.FlatVectorsWriter; +import org.apache.lucene.index.SegmentReadState; +import org.apache.lucene.index.SegmentWriteState; + +/** + * Flat vector format that stores each distinct vector once. Review Comment: Can we add another sentence in this opening paragraph something like "Use this to create efficient and high recall index-time vector filters, especially for restrictive filters where pre-filter (passing `Filter` to XXX vector search API) will often show poor recall" or so? OK maybe one more sentence after that: "For example, if the index contains music, and you'd like to expose vector search filtered by music category ("Classic Rock", "Grunge", "Jazz", ...), you would index each song's embedding vector into both the primary vector field, and the same vector into a separate field(s) for each category that song belongs to, and the HNSW format on top of this will build a separate graph (sharing the vector storage). Searching by each of hose per-category fields will give high recall, better than (sometimes substantially so) passing a pre-filter when searching the main vector field". Also: "If you customize your Codec per-field, be sure to share a single index of this `Format` shared across your vector fields so that dedup can span all those vector fields". ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupFlatVectorsFormat.java: ########## @@ -0,0 +1,133 @@ +/* + * 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.codecs.lucene106.dedup; + +import java.io.IOException; +import org.apache.lucene.codecs.hnsw.FlatVectorsFormat; +import org.apache.lucene.codecs.hnsw.FlatVectorsReader; +import org.apache.lucene.codecs.hnsw.FlatVectorsWriter; +import org.apache.lucene.index.SegmentReadState; +import org.apache.lucene.index.SegmentWriteState; + +/** + * Flat vector format that stores each distinct vector once. + * + * <p>Vectors that share the same dimension and encoding form a <i>group</i>. Within a group, an + * identical vector is stored a single time regardless of how many documents (across all fields that + * map to that group) reference it; each field then keeps a per-document {@code ordToVecOrd} map Review Comment: Remove per-document? It sounds like each document has a map but rather it's the whole field (in each segment) that holds this map? Should we rename to `docToVecOrd`? It's mapping `docid` to vector ordinal? ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupGroup.java: ########## @@ -0,0 +1,105 @@ +/* + * 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.codecs.lucene106.dedup; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.List; +import org.apache.lucene.internal.hppc.LongIntHashMap; +import org.apache.lucene.internal.hppc.ObjectCursor; +import org.apache.lucene.util.Accountable; + +/** Review Comment: Can you open a spinoff to somehow expose stats of how many duplicate vectors across fields? Maybe just during `CheckIndex`, or maybe an experimental `public` API to retrieve stats. This can be important information when figuring out how to optimize / query plan high recall filtered vector search, but also for detecting unexpected heavy duplication within vectors you thought were unique. Edit: one simple stat/approximation (in lieu of/until finishing that spinoff) would be: get the total disk usage for the flat reader, divide by sum of total vectors counts for each dedup'd field, and you'll get a coarse "dedup factor" showing how much storage reduction you saw, i.e. on average how many times is each vector dup'd. ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupUtil.java: ########## @@ -0,0 +1,699 @@ +/* + * 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.codecs.lucene106.dedup; + +import static org.apache.lucene.index.VectorEncoding.BYTE; +import static org.apache.lucene.index.VectorEncoding.FLOAT16; +import static org.apache.lucene.index.VectorEncoding.FLOAT32; +import static org.apache.lucene.util.StringHelper.GOOD_FAST_HASH_SEED; +import static org.apache.lucene.util.StringHelper.murmurhash3_x64_128; + +import java.io.IOException; +import org.apache.lucene.codecs.hnsw.FlatVectorsScorer; +import org.apache.lucene.codecs.lucene95.OffHeapByteVectorValues; +import org.apache.lucene.codecs.lucene95.OffHeapFloat16VectorValues; +import org.apache.lucene.codecs.lucene95.OffHeapFloatVectorValues; +import org.apache.lucene.codecs.lucene95.OrdToDocDISIReaderConfiguration; +import org.apache.lucene.index.ByteVectorValues; +import org.apache.lucene.index.DocsWithFieldSet; +import org.apache.lucene.index.FieldInfo; +import org.apache.lucene.index.Float16VectorValues; +import org.apache.lucene.index.FloatVectorValues; +import org.apache.lucene.index.KnnVectorValues; +import org.apache.lucene.index.VectorEncoding; +import org.apache.lucene.index.VectorSimilarityFunction; +import org.apache.lucene.internal.hppc.IntArrayList; +import org.apache.lucene.search.DocIdSetIterator; +import org.apache.lucene.search.VectorScorer; +import org.apache.lucene.store.IndexInput; +import org.apache.lucene.store.IndexOutput; +import org.apache.lucene.store.RandomAccessInput; +import org.apache.lucene.util.ArrayUtil; +import org.apache.lucene.util.LongValues; +import org.apache.lucene.util.hnsw.RandomVectorScorer; +import org.apache.lucene.util.packed.DirectReader; +import org.apache.lucene.util.packed.DirectWriter; + +/** + * Shared helpers for the de-duplicating flat format: reading / writing field and group metadata, + * vector hashing and alignment, and the {@link DedupVectorValues} views used on the read path. + * + * @lucene.experimental + */ +final class DedupUtil { + + private static final int DIRECT_MONOTONIC_BLOCK_SHIFT = 16; + + private static final int END_MARKER = -1; + + private static final int ORD_TO_VEC_ALIGN_BYTES = 4; + + // TODO: This is the number of bits used to write each group ordinal in the index-backed per-field + // OrdToVecOrd mapping. Evaluate using fewer bits to reduce index size, at the expense of + // costlier lookups. + private static final int ORD_TO_VEC_BITS_PER_VALUE = 32; + + static final int SCRATCH_SIZE = 16; + + /** Key used to group vectors (dimension + encoding). */ + record GroupKey(int dimension, VectorEncoding encoding) { + GroupKey(FieldInfo fieldInfo) { + this(fieldInfo.getVectorDimension(), fieldInfo.getVectorEncoding()); + } + } + + /** + * Vector values that share a single copy of each distinct vector across the documents and fields + * that reference it. + * + * <p>Every instance is backed by two views: the {@code fieldView} maps ordinals to docs and + * drives iteration (one entry per document), while the {@code groupView} holds the de-duplicated + * vectors (one entry per distinct vector). {@code ordToVecOrd} translates a document ordinal into + * its group ordinal. + */ + sealed interface DedupVectorValues { + /** The dense view over distinct vectors, indexed by group ordinal. */ + KnnVectorValues getGroupView(); + + /** Maps a per-document ordinal to its group ordinal in {@link #getGroupView()}. */ + OrdToVecOrd getOrdToVecOrd(); + } + + /** + * Maps a field's per-document ordinal to the ordinal of its (shared) vector within the group. + * Backed on-heap while writing and off-heap while reading. + */ + sealed interface OrdToVecOrd { + int get(int ord); + + OrdToVecOrd copy() throws IOException; + } + + record GroupInfo( + int groupOrd, + int dimension, + VectorEncoding encoding, + int groupSize, + long vectorDataOffset, + long vectorDataSize) {} + + static void writeGroupInfo(IndexOutput meta, GroupInfo groupInfo) throws IOException { + meta.writeInt(groupInfo.groupOrd); + meta.writeInt(groupInfo.dimension); + meta.writeInt(groupInfo.encoding.ordinal()); + meta.writeInt(groupInfo.groupSize); + meta.writeLong(groupInfo.vectorDataOffset); + meta.writeLong(groupInfo.vectorDataSize); + } + + static void writeEndOfGroups(IndexOutput meta) throws IOException { + meta.writeInt(END_MARKER); + } + + static GroupInfo readGroupInfo(IndexInput meta) throws IOException { + int groupOrd = meta.readInt(); + if (groupOrd == END_MARKER) { + return null; + } + + int dimension = meta.readInt(); + VectorEncoding encoding = VectorEncoding.values()[meta.readInt()]; + int groupSize = meta.readInt(); + long vectorDataOffset = meta.readLong(); + long vectorDataSize = meta.readLong(); + + return new GroupInfo( + groupOrd, dimension, encoding, groupSize, vectorDataOffset, vectorDataSize); + } + + record WriteFieldInfo( + int fieldNumber, + VectorSimilarityFunction function, + int dimension, + VectorEncoding encoding, + int groupOrd, + int vectorCount, + int maxDoc, + DocsWithFieldSet docs, + OrdToVecOrd ordToVecOrd) {} + + static void writeFieldInfo(IndexOutput meta, IndexOutput vectorData, WriteFieldInfo fieldInfo) + throws IOException { + + meta.writeInt(fieldInfo.fieldNumber); + meta.writeInt(fieldInfo.function.ordinal()); + meta.writeInt(fieldInfo.dimension); + meta.writeInt(fieldInfo.encoding.ordinal()); + meta.writeInt(fieldInfo.groupOrd); + meta.writeInt(fieldInfo.vectorCount); + + // write ordToDoc + OrdToDocDISIReaderConfiguration.writeStoredMeta( + DIRECT_MONOTONIC_BLOCK_SHIFT, + meta, + vectorData, + fieldInfo.vectorCount, + fieldInfo.maxDoc, + fieldInfo.docs); + + // write ordToVec + long ordToVecOffset = vectorData.alignFilePointer(ORD_TO_VEC_ALIGN_BYTES); + DirectWriter writer = + DirectWriter.getInstance(vectorData, fieldInfo.vectorCount, ORD_TO_VEC_BITS_PER_VALUE); + for (int i = 0; i < fieldInfo.vectorCount; i++) { + writer.add(fieldInfo.ordToVecOrd.get(i)); + } + writer.finish(); + long ordToVecSize = vectorData.getFilePointer() - ordToVecOffset; + + meta.writeLong(ordToVecOffset); + meta.writeLong(ordToVecSize); + } + + static void writeEndOfFields(IndexOutput meta) throws IOException { + meta.writeInt(END_MARKER); + } + + record ReadFieldInfo( + int fieldNumber, + VectorSimilarityFunction function, + int dimension, + VectorEncoding encoding, + int groupOrd, + int vectorCount, + OrdToDocDISIReaderConfiguration ordToDoc, + long ordToVecOffset, + long ordToVecSize) {} + + static ReadFieldInfo readFieldInfo(IndexInput meta) throws IOException { + + int fieldNumber = meta.readInt(); + if (fieldNumber == END_MARKER) { + return null; + } + + VectorSimilarityFunction function = VectorSimilarityFunction.values()[meta.readInt()]; + int dimension = meta.readInt(); + VectorEncoding encoding = VectorEncoding.values()[meta.readInt()]; + int groupOrd = meta.readInt(); + int vectorCount = meta.readInt(); + OrdToDocDISIReaderConfiguration ordToDoc = + OrdToDocDISIReaderConfiguration.fromStoredMeta(meta, vectorCount); + long ordToVecOffset = meta.readLong(); + long ordToVecSize = meta.readLong(); + + return new ReadFieldInfo( + fieldNumber, + function, + dimension, + encoding, + groupOrd, + vectorCount, + ordToDoc, + ordToVecOffset, + ordToVecSize); + } + + static long hashBytes(byte[] bytes) { + return murmurhash3_x64_128(bytes, 0, bytes.length, GOOD_FAST_HASH_SEED)[0]; + } + + static long alignBytes(IndexOutput output, VectorEncoding encoding) throws IOException { Review Comment: Add comment why we align? And how this is "best effort" (nothing checks/warns if incoming length of serialized vectors is not 0 mod 64. Do we at least have this suggestion in javadoc for the format? ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupGroup.java: ########## @@ -0,0 +1,105 @@ +/* + * 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.codecs.lucene106.dedup; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.List; +import org.apache.lucene.internal.hppc.LongIntHashMap; +import org.apache.lucene.internal.hppc.ObjectCursor; +import org.apache.lucene.util.Accountable; + +/** + * Interns vectors so that each distinct value is stored once. {@link #addUnique} returns the group + * ordinal for a vector, adding it (via {@link #copy}) only if not already present. Callers with the + * same {@code (dimension, encoding)} share a group, so an identical vector across fields is stored + * a single time. + * + * <p>Not thread-safe; a group is confined to the writer that created it. + * + * @lucene.experimental + */ +abstract sealed class DedupGroup<T> implements Accountable + permits DedupFlushContext.ByteGroup, + DedupFlushContext.FloatGroup, + DedupFlushContext.Float16Group, + DedupMergeContext.DedupMergeGroup { + + /** + * Map for vector hash -> group ord. Only a hint and not the ground truth due to possibility of + * hash collisions, where a full equality check must be performed. + */ + private final LongIntHashMap hashToOrdHint; + + private final List<T> vectors; + + private final ObjectCursor<T> current; // reuse from addUnique + + DedupGroup() { + this.hashToOrdHint = new LongIntHashMap(); + this.vectors = new ArrayList<>(); + this.current = new ObjectCursor<>(); + } + + abstract long hash(T vector) throws IOException; Review Comment: Do we have a test case for the worst case "heat death of the universe" corpus (many documents AND fields all have the same "all 0s" vector)? Every insert is then a (true) hash collision.. ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupUtil.java: ########## @@ -0,0 +1,699 @@ +/* + * 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.codecs.lucene106.dedup; + +import static org.apache.lucene.index.VectorEncoding.BYTE; +import static org.apache.lucene.index.VectorEncoding.FLOAT16; +import static org.apache.lucene.index.VectorEncoding.FLOAT32; +import static org.apache.lucene.util.StringHelper.GOOD_FAST_HASH_SEED; +import static org.apache.lucene.util.StringHelper.murmurhash3_x64_128; + +import java.io.IOException; +import org.apache.lucene.codecs.hnsw.FlatVectorsScorer; +import org.apache.lucene.codecs.lucene95.OffHeapByteVectorValues; +import org.apache.lucene.codecs.lucene95.OffHeapFloat16VectorValues; +import org.apache.lucene.codecs.lucene95.OffHeapFloatVectorValues; +import org.apache.lucene.codecs.lucene95.OrdToDocDISIReaderConfiguration; +import org.apache.lucene.index.ByteVectorValues; +import org.apache.lucene.index.DocsWithFieldSet; +import org.apache.lucene.index.FieldInfo; +import org.apache.lucene.index.Float16VectorValues; +import org.apache.lucene.index.FloatVectorValues; +import org.apache.lucene.index.KnnVectorValues; +import org.apache.lucene.index.VectorEncoding; +import org.apache.lucene.index.VectorSimilarityFunction; +import org.apache.lucene.internal.hppc.IntArrayList; +import org.apache.lucene.search.DocIdSetIterator; +import org.apache.lucene.search.VectorScorer; +import org.apache.lucene.store.IndexInput; +import org.apache.lucene.store.IndexOutput; +import org.apache.lucene.store.RandomAccessInput; +import org.apache.lucene.util.ArrayUtil; +import org.apache.lucene.util.LongValues; +import org.apache.lucene.util.hnsw.RandomVectorScorer; +import org.apache.lucene.util.packed.DirectReader; +import org.apache.lucene.util.packed.DirectWriter; + +/** + * Shared helpers for the de-duplicating flat format: reading / writing field and group metadata, + * vector hashing and alignment, and the {@link DedupVectorValues} views used on the read path. + * + * @lucene.experimental + */ +final class DedupUtil { + + private static final int DIRECT_MONOTONIC_BLOCK_SHIFT = 16; Review Comment: Hmm rename to something descriptive maybe `ORD_TO_VEC_BLOCK_SHIFT` or so? And add comment `// block size (in log base 2) for encoding ord to vec ord` or so? ########## lucene/CHANGES.txt: ########## @@ -330,6 +330,9 @@ New Features * GITHUB#16383: Add fp16 vector encoding support. (Pulkit Gupta) +* GITHUB#15979: Add a de-duplicating HNSW vector format (Lucene106DedupHnswVectorsFormat) that stores + each distinct vector once, shared across all documents and fields that reference it. (Kaival Parikh) Review Comment: Maybe add `full-precision` i.e. `each distinct full-precision vector once`? We don't dedup in quantized space (yet)? ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupFlatVectorsReader.java: ########## @@ -0,0 +1,359 @@ +/* + * 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.codecs.lucene106.dedup; + +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.META_CODEC_NAME; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.META_EXTENSION; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VECTOR_DATA_CODEC_NAME; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VECTOR_DATA_EXTENSION; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VERSION_CURRENT; +import static org.apache.lucene.codecs.lucene106.dedup.DedupFlatVectorsFormat.VERSION_START; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.loadDedupBytes; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.loadDedupFloat16s; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.loadDedupFloats; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.readFieldInfo; +import static org.apache.lucene.codecs.lucene106.dedup.DedupUtil.readGroupInfo; +import static org.apache.lucene.index.VectorEncoding.BYTE; +import static org.apache.lucene.index.VectorEncoding.FLOAT16; +import static org.apache.lucene.index.VectorEncoding.FLOAT32; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import org.apache.lucene.codecs.CodecUtil; +import org.apache.lucene.codecs.hnsw.FlatVectorsReader; +import org.apache.lucene.codecs.hnsw.FlatVectorsScorer; +import org.apache.lucene.codecs.lucene106.dedup.DedupUtil.GroupInfo; +import org.apache.lucene.codecs.lucene106.dedup.DedupUtil.ReadFieldInfo; +import org.apache.lucene.index.ByteVectorValues; +import org.apache.lucene.index.CorruptIndexException; +import org.apache.lucene.index.FieldInfo; +import org.apache.lucene.index.FieldInfos; +import org.apache.lucene.index.Float16VectorValues; +import org.apache.lucene.index.FloatVectorValues; +import org.apache.lucene.index.IndexFileNames; +import org.apache.lucene.index.MergePolicy; +import org.apache.lucene.index.SegmentReadState; +import org.apache.lucene.index.VectorEncoding; +import org.apache.lucene.store.ChecksumIndexInput; +import org.apache.lucene.store.DataAccessHint; +import org.apache.lucene.store.FileDataHint; +import org.apache.lucene.store.FileTypeHint; +import org.apache.lucene.store.IOContext; +import org.apache.lucene.store.IndexInput; +import org.apache.lucene.util.IOUtils; +import org.apache.lucene.util.RamUsageEstimator; +import org.apache.lucene.util.hnsw.RandomVectorScorer; + +/** + * Reads de-duplicated flat vectors written by {@link DedupFlatVectorsWriter}. Each field exposes a + * view backed by its group's shared vectors and an {@code ordToVecOrd} translation map. + * + * @lucene.experimental + */ +final class DedupFlatVectorsReader extends FlatVectorsReader { + private static final long SHALLOW_SIZE = + RamUsageEstimator.shallowSizeOfInstance(DedupFlatVectorsReader.class); + + private final FlatVectorsScorer vectorsScorer; + private final Map<String, FieldEntry> fields; + private final IndexInput vectorData; + + DedupFlatVectorsReader(SegmentReadState state, FlatVectorsScorer vectorsScorer) + throws IOException { + + this.vectorsScorer = vectorsScorer; + this.fields = new HashMap<>(); + + String metaFileName = + IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, META_EXTENSION); + + int versionMeta; + try (ChecksumIndexInput meta = state.directory.openChecksumInput(metaFileName)) { + Throwable priorE = null; + try { + versionMeta = + CodecUtil.checkIndexHeader( + meta, + META_CODEC_NAME, + VERSION_START, + VERSION_CURRENT, + state.segmentInfo.getId(), + state.segmentSuffix); + readMetaBody(meta, state.fieldInfos); + } catch (Throwable e) { + priorE = e; + throw e; + } finally { + CodecUtil.checkFooter(meta, priorE); + } + } + + this.vectorData = openDataInput(state, versionMeta); + } + + private void readMetaBody(ChecksumIndexInput meta, FieldInfos fieldInfos) throws IOException { + List<GroupInfo> groupInfos = new ArrayList<>(); + while (true) { + GroupInfo groupInfo = readGroupInfo(meta); + if (groupInfo == null) { + break; + } + groupInfos.add(groupInfo); + } + + while (true) { + ReadFieldInfo fieldInfo = readFieldInfo(meta); + if (fieldInfo == null) { + break; + } + + FieldInfo info = fieldInfos.fieldInfo(fieldInfo.fieldNumber()); + if (info == null) { + throw new CorruptIndexException("Invalid field number: " + fieldInfo.fieldNumber(), meta); + } else if (fieldInfo.function() != info.getVectorSimilarityFunction()) { Review Comment: Does Lucene already prevent users from changing up the similarity function from one indexing run to the next? So this path should be impossible, hence `CorruptIndexException`? ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupUtil.java: ########## @@ -0,0 +1,699 @@ +/* + * 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.codecs.lucene106.dedup; + +import static org.apache.lucene.index.VectorEncoding.BYTE; +import static org.apache.lucene.index.VectorEncoding.FLOAT16; +import static org.apache.lucene.index.VectorEncoding.FLOAT32; +import static org.apache.lucene.util.StringHelper.GOOD_FAST_HASH_SEED; +import static org.apache.lucene.util.StringHelper.murmurhash3_x64_128; + +import java.io.IOException; +import org.apache.lucene.codecs.hnsw.FlatVectorsScorer; +import org.apache.lucene.codecs.lucene95.OffHeapByteVectorValues; +import org.apache.lucene.codecs.lucene95.OffHeapFloat16VectorValues; +import org.apache.lucene.codecs.lucene95.OffHeapFloatVectorValues; +import org.apache.lucene.codecs.lucene95.OrdToDocDISIReaderConfiguration; +import org.apache.lucene.index.ByteVectorValues; +import org.apache.lucene.index.DocsWithFieldSet; +import org.apache.lucene.index.FieldInfo; +import org.apache.lucene.index.Float16VectorValues; +import org.apache.lucene.index.FloatVectorValues; +import org.apache.lucene.index.KnnVectorValues; +import org.apache.lucene.index.VectorEncoding; +import org.apache.lucene.index.VectorSimilarityFunction; +import org.apache.lucene.internal.hppc.IntArrayList; +import org.apache.lucene.search.DocIdSetIterator; +import org.apache.lucene.search.VectorScorer; +import org.apache.lucene.store.IndexInput; +import org.apache.lucene.store.IndexOutput; +import org.apache.lucene.store.RandomAccessInput; +import org.apache.lucene.util.ArrayUtil; +import org.apache.lucene.util.LongValues; +import org.apache.lucene.util.hnsw.RandomVectorScorer; +import org.apache.lucene.util.packed.DirectReader; +import org.apache.lucene.util.packed.DirectWriter; + +/** + * Shared helpers for the de-duplicating flat format: reading / writing field and group metadata, + * vector hashing and alignment, and the {@link DedupVectorValues} views used on the read path. + * + * @lucene.experimental + */ +final class DedupUtil { + + private static final int DIRECT_MONOTONIC_BLOCK_SHIFT = 16; + + private static final int END_MARKER = -1; + + private static final int ORD_TO_VEC_ALIGN_BYTES = 4; + + // TODO: This is the number of bits used to write each group ordinal in the index-backed per-field Review Comment: Open spinoff and link to PR in the comment? And definitely +1 to do this in followon. PnP! This sets the on-disk cost and CPU cost of lookup for pure dup fields. These are also hot bytes if the field is used for searching (every lookup visits this monotonic block reader). ########## lucene/core/src/java/org/apache/lucene/codecs/lucene106/dedup/DedupGroup.java: ########## @@ -0,0 +1,105 @@ +/* + * 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.codecs.lucene106.dedup; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.List; +import org.apache.lucene.internal.hppc.LongIntHashMap; +import org.apache.lucene.internal.hppc.ObjectCursor; +import org.apache.lucene.util.Accountable; + +/** + * Interns vectors so that each distinct value is stored once. {@link #addUnique} returns the group + * ordinal for a vector, adding it (via {@link #copy}) only if not already present. Callers with the + * same {@code (dimension, encoding)} share a group, so an identical vector across fields is stored + * a single time. + * + * <p>Not thread-safe; a group is confined to the writer that created it. + * + * @lucene.experimental + */ +abstract sealed class DedupGroup<T> implements Accountable + permits DedupFlushContext.ByteGroup, + DedupFlushContext.FloatGroup, + DedupFlushContext.Float16Group, + DedupMergeContext.DedupMergeGroup { + + /** + * Map for vector hash -> group ord. Only a hint and not the ground truth due to possibility of + * hash collisions, where a full equality check must be performed. Review Comment: I'm curious how often you hit false hash collisions (same 64 bit hash but different vectors) in a "typical" data set. Hopefully we have a good hash function vs "typical" vectors encountered, but of course for any hash function there are by mathematical / set theory necessity many adversarial vector corpora that have high false collisions (just hopefully rare in practice). -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
