[LUCENE-10375] Speed up HNSW merge by writing combined vector data

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 9.1
• Labels: vector-based-search
• Lucene Fields: New
• Assignee: Unassigned
• Reporter: Julie Tibshirani
• Created: 13/Jan/22 05:41
• Updated: 28/Aug/22 16:34
• Resolved: 24/Jan/22 00:40

Description

When merging segments together, the HNSW writer creates a VectorValues instance that gives a merged view of all the segments' VectorValues. This merged instance is used when constructing the new HNSW graph. Graph building needs random access, and the merged VectorValues support this by mapping from merged ordinals -> segments and segment ordinals.

This mapping seems to add overhead. The nightly indexing benchmarks sometimes show substantial time in Arrays.binarySearch (used to map an ordinal to a segment): https://blunders.io/jfr-demo/indexing-1kb-vectors-2022.01.09.18.03.19/top_down_cpu_samples.

Instead of using a merged VectorValues to create the graph, maybe we could first write all the segment vectors to a file, and use that file to build the graph.

Issue Links

• links to: GitHub Pull Request #601
• links to: GitHub Pull Request #617