kaivalnp commented on code in PR #15979: URL: https://github.com/apache/lucene/pull/15979#discussion_r3475476903
########## lucene/core/src/java/org/apache/lucene/codecs/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.dedup; + +import java.io.IOException; +import org.apache.lucene.codecs.hnsw.FlatVectorScorerUtil; +import org.apache.lucene.codecs.hnsw.FlatVectorsFormat; +import org.apache.lucene.codecs.hnsw.FlatVectorsReader; +import org.apache.lucene.codecs.hnsw.FlatVectorsScorer; +import org.apache.lucene.codecs.hnsw.FlatVectorsWriter; +import org.apache.lucene.codecs.lucene90.IndexedDISI; +import org.apache.lucene.index.SegmentReadState; +import org.apache.lucene.index.SegmentWriteState; +import org.apache.lucene.search.DocIdSetIterator; +import org.apache.lucene.store.IndexOutput; + +/** + * Flat vector format that stores each unique vector exactly once per segment. Multiple documents + * (within the same field, and across fields with matching {@code (dimension, encoding)}) may share + * the same physical vector, dramatically reducing on-disk size when many docs/fields point at the + * same vector data. + * + * <p>The format groups fields into "pools" keyed by {@code (dimension, encoding)}. All fields in + * the same pool share unique-vector storage; per-field metadata records how each doc-ord maps to a + * vector-ord within the pool. + * Review Comment: Makes sense! > Does it store every vector in heap during indexing ... In the flat version, Lucene already [stores vectors on-heap](https://github.com/apache/lucene/blob/f3d493be97174bba4dcafc0bde23565091b8da04/lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99FlatVectorsWriter.java#L398-L414) (which is used to build HNSW graphs for the first time). This PR [stores](https://github.com/kaivalnp/lucene/blob/6b6b12d2500c24a2f32a3fe15dcf81308e57abd6/lucene/core/src/java/org/apache/lucene/codecs/dedup/DedupFlatVectorsWriter.java#L500) an additional copy of all vectors (as a `byte[]` array), mostly to compute the hash using Murmurhash3, which is admittedly wasteful. Note that each `float[]` is eventually converted to `byte[]` to efficiently write it to disk, but this can be done one-by-one instead of holding two copies of everything all the time. I'll try to get it to compute hashes on original vectors, and only serialize one-at-a-time during flush. > Also explain how merging works ... During merge: we go over live vectors one-by-one, and store a map of hash-to-{ord in group + original segment + original ord in segment}. If we see a new hash -- the vector is guaranteed to be unique and is directly written to the index. If there is a hash collision, we first check if the collided vectors came from the same de-duplicated segment. - If yes, they are known to be different (already de-duplicated), and we do not read the vector back from disk. - If the segments are different or written using a non-deduplicating format, we read the vector back from disk to perform an equality check. I think this^ is the long pole of merging (random-access of vectors from disk, which is much slower than sequentially reading them). However -- the read-back is limited to cases of duplicate vectors across documents. I'll try to add comments explaining all this. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [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]
