apache / apache/lucene

Make HNSW merges cheaper on heap

Open
#14,208 13 comments 0 reactions 0 assignees View on GitHub
type:enhancement vector-based-search
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

I am not sure of other structures, but HNSW merges can allocate a pretty large chunk of memory on heap.

For example:

Let's have the max_conn set to 16. Thus connections on the bottom layer is 32.

We eagerly create the neighbor arrays, which means for 9 million vectors, the heap allocation balloons to over 2GB (and depending on the number of layers and other structures, is over 2.5GB of heap).

From what I can tell, merges don't really expose a "Here is how much heap I am estimated to use".

I wonder if we can do one of the following to help this scenario:

- Make HNSW merges cheaper when it comes to on-heap memory (e.g. merge off heap?!? make it cheaper??)
- Don't eagerly allocate all the memory required (complicates multi-threaded merging...and might not actually address the issue)

Note, this is tangential this other HNSW merging issue, and might actually be an antithesis, as sometimes reducing memory allocations then implies slower merging: https://github.com/apache/lucene/issues/12440

Contributor guide

Open the contributing guide

Research direction

No files, tests, or entry points are named. Start by tracing HNSW merge allocation behavior and compare the trade-offs with the linked issue 12440; done means reducing on-heap memory use without an unacceptable merge-performance regression.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
performance, search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.