xande commented on issue #16906:
URL: https://github.com/apache/lucene/issues/16906#issuecomment-6501571443
I reproduced the results on the same hardware class. I also tested the PR on
an internal dataset with 4096 dimensions.
**Setup.** m6gd.8xlarge (Graviton2, 32 cores, 32 MB L3), Corretto 25, this
PR at `8d19cdd0`, luceneutil `KnnGraphTester`. 1M docs, M=32, beamWidth 100,
`PipnnParams.DEFAULT` with alpha 1.13.
Without PiPNN, a normal `forceMerge` reuses the graph of the largest
segment. PiPNN always builds the graph from zero. Thus, to compare two full
builds, I merged the segments into a new index with
`IndexWriter.addIndexes(CodecReader...)`. A reader wrapper hid the HNSW graphs,
so the HNSW merger had to insert all vectors. I worked with a coding agent on
these harness changes.
<details>
<summary>Harness changes (luceneutil <code>KnnGraphTester</code>)</summary>
The wrapper. The HNSW mergers reuse a source graph only when the vectors
reader is an `HnswGraphProvider`. This reader serves the same vectors, but it
is not an `HnswGraphProvider`:
```java
final class GraphHidingCodecReader extends FilterCodecReader {
GraphHidingCodecReader(CodecReader in) {
super(in);
}
@Override
public KnnVectorsReader getVectorReader() {
KnnVectorsReader reader = super.getVectorReader();
return reader == null ? null : new GraphHidingVectorsReader(reader);
}
@Override
public CacheHelper getCoreCacheHelper() {
return null;
}
@Override
public CacheHelper getReaderCacheHelper() {
return null;
}
private static final class GraphHidingVectorsReader extends
KnnVectorsReader {
private final KnnVectorsReader in;
GraphHidingVectorsReader(KnnVectorsReader in) {
this.in = in;
}
@Override
public void checkIntegrity(MergePolicy.OneMerge merge) throws
IOException {
in.checkIntegrity(merge);
}
@Override
public FloatVectorValues getFloatVectorValues(String field) throws
IOException {
return in.getFloatVectorValues(field);
}
@Override
public FloatVectorValues getFloatVectorValues(String field,
DataAccessHint access)
throws IOException {
return in.getFloatVectorValues(field, access);
}
@Override
public ByteVectorValues getByteVectorValues(String field) throws
IOException {
return in.getByteVectorValues(field);
}
@Override
public Float16VectorValues getFloat16VectorValues(String field) throws
IOException {
return in.getFloat16VectorValues(field);
}
@Override
public void search(String field, float[] target, KnnCollector
knnCollector, AcceptDocs acceptDocs)
throws IOException {
in.search(field, target, knnCollector, acceptDocs);
}
@Override
public void search(String field, byte[] target, KnnCollector
knnCollector, AcceptDocs acceptDocs)
throws IOException {
in.search(field, target, knnCollector, acceptDocs);
}
@Override
public void search(String field, short[] target, KnnCollector
knnCollector, AcceptDocs acceptDocs)
throws IOException {
in.search(field, target, knnCollector, acceptDocs);
}
@Override
public KnnVectorsReader getMergeInstance() throws IOException {
return new GraphHidingVectorsReader(in.getMergeInstance());
}
@Override
public void finishMerge() throws IOException {
in.finishMerge();
}
@Override
public int getVectorCount(FieldInfo fieldInfo) throws IOException {
return in.getVectorCount(fieldInfo);
}
@Override
public Map<String, Long> getOffHeapByteSize(FieldInfo fieldInfo) {
return in.getOffHeapByteSize(fieldInfo);
}
@Override
public void close() {
// the wrapped reader belongs to the segment core and is closed with
the segment reader
}
}
}
```
The timed merge (`-rebuildMerge <newIndex>`). `addIndexes` puts all readers
into one merge, so it writes one new segment:
```java
private double rebuildMerge(Path sourcePath, Path destPath) throws
IOException {
IndexWriterConfig iwc = new
IndexWriterConfig().setOpenMode(IndexWriterConfig.OpenMode.CREATE);
iwc.setCodec(getCodec(maxConn, beamWidth, exec, numMergeWorker, quantize,
quantizeBits, indexType,
rerank, rerankQuantizeBits, pipnnParams));
iwc.setUseCompoundFile(false);
try (Directory sourceDir = FSDirectory.open(sourcePath);
DirectoryReader reader = DirectoryReader.open(sourceDir);
Directory destDir = FSDirectory.open(destPath)) {
CodecReader[] readers = new CodecReader[reader.leaves().size()];
for (int i = 0; i < readers.length; i++) {
readers[i] = new GraphHidingCodecReader((CodecReader)
reader.leaves().get(i).reader());
}
long startNS = System.nanoTime();
try (IndexWriter iw = new IndexWriter(destDir, iwc)) {
iw.addIndexes(readers);
iw.commit();
}
return nsToSec(System.nanoTime() - startNS);
}
}
```
The PiPNN switch (`-pipnn`, `-pipnnAlpha`, `-pipnnFanouts`, ...) in
`getCodec`:
```java
} else if (pipnnParams != null) {
knnVectorsFormat = new Lucene99HnswVectorsFormat(maxConn, beamWidth,
numMergeWorker, exec, pipnnParams);
} else {
knnVectorsFormat = new Lucene99HnswVectorsFormat(maxConn, beamWidth,
numMergeWorker, exec);
}
```
For 4096 dims, a small `KnnVectorsFormat` wrapper delegates `fieldsWriter`
and `fieldsReader` and returns 4096 from `getMaxDimensions`, because
`Lucene99HnswVectorsFormat` allows 1024.
</details>
**Cohere v3 1024d.** The results reproduce what you have seen:.
- 16 workers: HNSW 169.6 s, PiPNN 87.3 s, so 1.94× (you report 1.96×).
- The speedup increases from 1.64× at 1 worker to 2.61× at 32 workers.
- Recall@100 and nodes visited agree with your table to ±0.001 and ±10. The
level-0 degree is 42.1 against 39.5.
New data on **Internal 4096-dim dataset** (1M docs, 6K queries).
| Workers | HNSW | PiPNN 10:3 | PiPNN 6:2 |
|---|---|---|---|
| 16 | 188.8 s | 278.2 s (0.68×) | 131.6 s (1.43×) |
| 32 | 156.5 s | 158.3 s (0.99×) | 80.1 s (1.95×) |
- As on your VDBBench 4096d set, HNSW makes a sparse graph here (level-0
degree 18.2). With 10:3, PiPNN is slower to build.
- **But the PiPNN graph is better!** At about the same latency (2.1 ms,
fanout 0), recall@100 is 0.900 against 0.832 for HNSW. At fanout 200, it is
0.967 against 0.924.
- 6:2 is also better than HNSW on the recall/latency curve: 0.882 at 1.99 ms
against 0.832 at 2.06 ms. For high dimensions, 6:2 looks like a good default.
--
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]
