Add support for keeping the graph structure for HNSW in off heap during merges

[navneet1v]

Description

Based on my reading of the code in Lucene, what I can see is we keep the graph structure OnHeap which not only puts additional pressure on JVM but also creates a bottleneck where we cannot create larger graphs.

One solution I was thinking is to move the graph structure during merge time to offheap, and also during write write it directly through off heap.

I am not sure if we have tried this in past, but I was going to put a POC around this. If anyone has some thoughts or ideas please share.

[msokolov]

The original argument we had for keeping it on heap today is to support random access and modification. Lucene's index files are write-once so we can't use them while building the graph. But there's no reason we couldn't create a temporary memory-mapped or other file to store the graph. One idea could be to create a space for a full set of neighbors (max-conn of them) for each node as it is appended. This will make the file bigger than it will ultimately need to be since the average out-degree of our graphs seems to be about maxconn/2. Maybe that's worth it though. Certainly it could enable graphs bigger than RAM.

[navneet1v]

Thanks @msokolov for your input. The way I was thinking was to avoid the intermediate file altogether, directly create a memory region(with Memory Segment) in the off heap and use that directly build the graph. The reason for not using file temporarily is to avoid IO altogether. But may be I am not thinking too far ahead where you are already. Will try to see if I can come up with a intermediate file approach too.

[benwtrent]

Is the only reason we need random writing because of the back links?

If we searched all segment graphs (and thus compared against all nodes) instead of just the new one, we could remove the need for back linking and possibly just write the graph as it's built.

I suppose it would be a different temporary file for each layer? And then at the end, consolidate and compress.

[msokolov]

Is the only reason we need random writing because of the back links?

Yes, I think so. I don't understand your idea about searching all segment graphs -- would we create links to nodes in other segments then? First I don't really see how this obviates the need for bidirectional linking, and this cuts against a pretty fundamental assumption that Lucene index data structures are per-segment so each segment can be searched independently of every other one ... so I assume I'm just not understanding what you meant

[benwtrent]

@msokolov the reason for backlinks is because nodes didn't find its nearest neighbors from ALL the vectors that will be in the index (e.g. an already indexed node didn't know about the new node...).

If we searched all the other segments (of course, we would need to translate ordinals), the vector can find its nearest neighbors given the entire corpus. Meaning back-linking is no longer necessary, as it already considered the entire corpus.

[msokolov]

hmm -- if doc A and doc B are both each others' nearest neighbor, considering all the docs in the index now or that ever will be in the index, and doc A is in segment 0, and then doc B gets added to segment N, we could maybe somehow link doc B to doc A (although how? what if segment 0 gets merged and the ordinals all change?), but even still how does doc A get linked to doc B?

[benwtrent]

hmm -- if doc A and doc B are both each others' nearest neighbor, considering all the docs in the index now or that ever will be in the index, and doc A is in segment 0, and then doc B gets added to segment N, we could maybe somehow link doc B to doc A (although how? what if segment 0 gets merged and the ordinals all change?), but even still how does doc A get linked to doc B?

I am talking about how we merge things, not how we search things.

During merge, we are building a new graph, Doc A searches graphs in segments 0..N, finds its nearest neighbors, one of which might be doc B in segment 2. Then we know the connections for Doc A, we just need to fix the ordinals knowing that doc B was in segment 2.

[msokolov]

I see, that makes sense. But we still do need to create a graph when flushing. I guess your proposal would be to postpone doing that until we actually flush? That is how we used to do it. I never really understood why we switched to
"incremental mode"

[benwtrent]

@msokolov yeah, I am not sure. Flush could still be incremental and on-heap.

Merge is the real heap cost (way larger graphs and way more expensive), I think this searching all the segment graphs approach during merge has many other benefits:

• Removing backlink locking, now parallelism is naive
• For asymmetric scoring, we no longer need to write temporary query vectors as we only ever score "query side" with a vector once
• May allow us to move HNSW graph building off heap (each layer gets a temporary file that is just appended to)