You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "benwtrent (via GitHub)" <gi...@apache.org> on 2025/02/07 12:19:29 UTC
[I] HNSW connect components can take an inordinate amount of time [lucene]
benwtrent opened a new issue, #14214:
URL: https://github.com/apache/lucene/issues/14214
### Description
Connect components on Flush or merge, while good for graphs that are "almost OK" but need to be better connected, can just destroy performance if the vector distribution is poor.
I don't readily have test data, but if you have tightly clustered, or many duplicate vectors, it can take until the "heat death of the universe" to complete.
It seems to me that since connect Components is a "best effort fix up" of the graph, we should add a "cap" on the amount of work this does.
Marking as a bug as I have seen this for real users and it effectively takes a CPU hostage for hours (maybe days).
### Version and environment details
_No response_
--
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: issues-unsubscribe@lucene.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "tteofili (via GitHub)" <gi...@apache.org>.
tteofili commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2642779168
this can be reproduced with either of the following tests
```java
public void testSameVectorIndexedMultipleTimes() throws IOException {
try (Directory d = newDirectory()) {
try (IndexWriter w = new IndexWriter(d, new IndexWriterConfig())) {
for (int j = 1; j <= 1_000_000; j++) {
Document doc = new Document();
doc.add(
getKnnVectorField(
"field", randomVector(16), DOT_PRODUCT));
w.addDocument(doc);
if (j % 100 == 0) {
w.flush();
}
}
w.commit();
}
}
}
public void testFewDistinctVectors() throws IOException {
try (Directory d = newDirectory()) {
try (IndexWriter w = new IndexWriter(d, new IndexWriterConfig())) {
float[][] f = new float[16][];
for (int i = 0; i < 16; i++) {
f[i] = new float[16];
Arrays.fill(f[i], (float) i);
}
for (int i =0; i < 1_000_000; i++) {
Document doc = new Document();
doc.add(getKnnVectorField("field", f[random().nextInt(16)], DOT_PRODUCT));
w.addDocument(doc);
}
}
}
}
```
they take tens of minutes and thread dump shows thread stuck at `hnsw.HnswGraphBuilder.connectComponents`
whereas a similar test even with random vectors takes 10x less time to finish.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2671796667
So, these adverse scenarios where connect components has to do a ton of work all stem from us keeping the graph very sparse (e.g. only connecting diverse nodes).
I wonder if we can augment our building algorithm per node, meaning when we detect a highly clustered area for a node (e.g. majority/all the scores of beam_width candidates are within 1e-7 or something). When we detect very clustered areas, we force MORE connections, by passing the typical diversity forcing on forward connections.
I am not sure we need to change the backlink behavior, but maybe we need to do that well?
The idea I have in mind is basically similar to "delauney" type things here: https://github.com/nmslib/nmslib/blob/2ae5378027a107474a952edae1e1c2dc2df941d2/similarity_search/src/method/hnsw.cc
However, we don't allow it to be configured and we just pick the right one (per node) based on the score distributions.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2698456606
Maybe as a short-term mitigation we should revert or disable the `connectComponents` impl since its supposed improvements are kind of theoretical and it comes with a deadly vulnerability. Then we can think about improvements as described here.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-3916934170
@mikemccand if you mean that its fixed by just disabling connected components, then yes, this is fixed.
We should open a separate issue if we want to fix connected components or tackle the disconnected graph issue some other way.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "Vikasht34 (via GitHub)" <gi...@apache.org>.
Vikasht34 commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2675065270
@benwtrent As far as I understand from your idea is to use Delaunay Triangulation and skip connectComponents() ?
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2698475184
The goal of connectComponents is to help graphs that have gaps in their connectivity. However, when its needed most (e.g. tons of gaps and poor connectivity), it does more harm than good.
I do think adjust diversity criterion dynamically based on score statistics can likely give us better gains here. Though, I have no numbers to back this hunch up.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2674487026
In the original diversity impl we had allowed the neighbors array to fill without regard to any diversity criterion, and only started imposing it once the array was full. This means we have to sort at that point IIRC, but it might be a better, more robust choice?
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2674533124
> This means we have to sort at that point IIRC, but it might be a better, more robust choice?
I am not sure if its "better" I would assume it makes search slower on well distributed and distinguished vectors :/
We should be able to automatically do the right thing as we know the distribution of the beam-width scores. Meaning, keeping well distinguished sparsity & handling silly (clustered/duplicate) data.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2674568528
> I am not sure if its "better" I would assume it makes search slower on well distributed and distinguished vectors :/
Sorry I didn't understand this. In the normal case, we'd populate the neighbors with non-diverse elements, and then once full, we impose the diversity criterion when adding new neighbors. That is: if an existing neighbor is non-diverse, we prefer a new neighbor that is diverse even if its score is more "distant"
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2757791987
> Can we expose a graph construction parameter in Lucene99HnswVectorsFormat to gate the connectComponents() call? This would allow us to mitigate this issue while a more comprehensive fix is developed.
I would argue not. We do not want more knobs to tune. We should instead fix the diversity & connection checks to be dynamic (e.g. fills connections when distribution of scores is poor, etc.).
As for reverting the change, I am on the fence about it. Maybe that is the right thing.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2698452319
I tried indexing some [NOAA climate data](https://www.ncei.noaa.gov/products/land-based-station/noaa-global-temp) that is four-dimensional (temperature over last 150 years for every 5 degree lat-long patch - 5MM docs) and reproduced this problem - it would just take a very long time indexing and then even longer in connectComponents. As an experiment, I tried relaxing our diversity constraint with a simple patch and found it enabled the indexing to complete in a reasonable time for some HNSW graph parameter choices, but could still get into the adversarial connectComponent in some other cases.
```
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
index 2fa7fed2a0d..0aebeb3236c 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
@@ -381,6 +381,16 @@ public class HnswGraphBuilder implements HnswBuilder {
neighbors.addInOrder(cNode, cScore);
}
}
+ // populate any remaining spots with non-diverse neighbors
+ for (int i = candidates.size() - 1; neighbors.size() < maxConnOnLevel && i >= 0; i--) {
+ if (mask[i] == false) {
+ int cNode = candidates.nodes()[i];
+ float cScore = candidates.scores()[i];
+ assert cNode <= hnsw.maxNodeId();
+ mask[i] = true;
+ neighbors.addOutOfOrder(cNode, cScore);
+ }
+ }
return mask;
}
```
A few conclusions:
1. HNSW is not the best indexing data structure for every numerical vector data set. Probably Points (ie kd-tree) would be better for low-dimensional data (< ~12dim) ?
2. Our connectComponents implementation has a horrible worst case that we need to fix.
3. We might want to fiddle with our diversity criterion, but it isn't a solution for (2).
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "Vikasht34 (via GitHub)" <gi...@apache.org>.
Vikasht34 commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2646005402
```
private void connectComponents() {
BitSet visited = new BitSet(graph.size());
List<Integer> entryPoints = new ArrayList<>();
for (int node = 0; node < graph.size(); node++) {
if (!visited.get(node)) {
List<Integer> component = new ArrayList<>();
exploreComponent(node, visited, component);
if (!entryPoints.isEmpty()) {
int bestCandidate = findBestCandidate(entryPoints, component);
connectNodes(entryPoints.get(0), bestCandidate);
}
entryPoints.add(component.get(0)); // Add first node as entry
}
}
}
```
I see 3 problems why it could be if it is poor
#### ** Inefficient Component Exploration (`exploreComponent`)**
- Recursively visits **every unconnected node**, leading to **O(N²) complexity** in worst-case scenarios.
- Causes excessive CPU utilization when dealing with **large numbers of unconnected components**.
#### ** Unbounded Connection Attempts (`findBestCandidate`)**
- The method **tries to optimally connect every component**, which becomes **extremely expensive for highly similar vectors**.
- Leads to **exponential slowdowns** when vector clusters are densely packed or contain duplicates.
#### ** Repeated Work (`connectNodes`)**
- If **multiple small components exist**, the function **makes too many unnecessary connections**.
- This results in **high CPU overhead** as the method attempts to fully optimize the graph, even when minimal connectivity is sufficient.
---
Idea of CAP is as a quick fix to prevent infinite execution in connectComponents(), but it does not solve the root problem and remains computationally expensive. The function still performs O(N²) connectivity checks but gets forcefully terminated instead of completing properly.This means that most of the CPU time is still wasted on redundant checks, and the graph may remain unoptimized or disconnected.
### What do u think of union find to solve this ?
We replace the **brute-force merging** with **Union-Find**, which **tracks components dynamically**:
1. **Reduces Complexity to O(N log N)**
- Union-Find **efficiently tracks connected components**, avoiding **repeated work**.
2. **Eliminates Unnecessary Checks**
- Instead of checking **every node again**, we **only merge truly disconnected components**.
3. **Stops Early When Graph is Mostly Connected**
- We **stop merging early** if **95% of the graph is already connected**, preventing **wasted work**.
---
Some Sudo code
```
public class HnswGraphConnectivity {
private final int[] parent;
private final int[] rank;
private final int size;
public HnswGraphConnectivity(int size) {
this.size = size;
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) parent[i] = i; // Each node starts in its own component
}
// Path compression: Makes find() O(1) amortized
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
// Union by rank: Ensures efficient merging
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
else if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
// Returns size of the largest connected component
public int largestComponentSize() {
Map<Integer, Integer> componentSize = new HashMap<>();
for (int i = 0; i < size; i++) {
int root = find(i);
componentSize.put(root, componentSize.getOrDefault(root, 0) + 1);
}
return Collections.max(componentSize.values());
}
}
```
```
private boolean connectComponents(int level) throws IOException {
int graphSize = hnsw.size();
HnswGraphConnectivity connectivity = new HnswGraphConnectivity(graphSize);
// Step 1: Initialize connectivity tracking
FixedBitSet notFullyConnected = new FixedBitSet(graphSize);
int maxConn = (level == 0) ? M * 2 : M;
List<Component> components = HnswUtil.components(hnsw, level, notFullyConnected, maxConn);
if (infoStream.isEnabled("HNSW")) {
infoStream.message("HNSW", "Found " + components.size() + " components on level=" + level);
}
// Step 2: Use parallel stream to process connections efficiently
IntStream.range(0, components.size()).parallel().forEach(i -> {
Component c = components.get(i);
for (int neighbor : c.nodes()) {
if (neighbor != c.start()) {
connectivity.union(c.start(), neighbor);
}
}
});
// Step 3: Stop early if graph is sufficiently connected (~95%)
if (connectivity.largestComponentSize() > (CONNECTIVITY_THRESHOLD_PERCENT / 100.0) * graphSize) {
if (infoStream.isEnabled("HNSW")) {
infoStream.message("HNSW", "Early stopping: " + CONNECTIVITY_THRESHOLD_PERCENT + "% of components are connected.");
}
return true;
}
// Step 4: Connect remaining components intelligently
GraphBuilderKnnCollector beam = new GraphBuilderKnnCollector(2);
int[] eps = new int[1];
UpdateableRandomVectorScorer scorer = scorerSupplier.scorer();
for (Component c : components) {
if (!connectivity.isConnected(c.start(), eps[0])) {
beam.clear();
eps[0] = c.start();
scorer.setScoringOrdinal(eps[0]);
// Find the best connection candidate
try {
graphSearcher.searchLevel(beam, scorer, level, eps, hnsw, notFullyConnected);
int bestNode = beam.popNode();
float score = beam.minimumScore();
link(level, bestNode, c.start(), score, notFullyConnected);
connectivity.union(bestNode, c.start());
} catch (Exception e) {
if (infoStream.isEnabled("HNSW")) {
infoStream.message("HNSW", "Failed to connect component: " + c.start());
}
}
}
}
return true;
}
```
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2675053049
> Sorry I didn't understand this.
@msokolov I mean that during search, we would by default have more neighbors to look at. Ensuring diversity eagerly means that its possible to have fewer than 32 connections (with m==16), thus allowing for faster search.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-3935999376
I guess the connected components thing is hard to fix and doesn't seem to affect us too badly in practice. It's mostly annoying from a theoretical / anal perspective -- there can be indexed documents that are impossible to return for any query! But statistically speaking, it's not a problem.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-3890795139
Is this issue resolved? Were we able to merge those adversarial (index identical vector N times) test cases and they pass? Or we still know of adversarial cases that are not resolved yet? (I scanned the comments above and was unsure...).
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "Vikasht34 (via GitHub)" <gi...@apache.org>.
Vikasht34 commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2657428175
Interesting , let me quickly run those tests my self also to see what would be impact!! Thanks for logs ..
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2654755040
So, verifying the "fewDistinct" slowness, here is how connect components works in this adverse case:
```
1> HNSW 1 [2025-02-12T20:14:45.641640Z; TEST-TestKnnFloatVectorQuery.testFewDistinctVectors-seed#[29F3C0E3B32A8A0D]]: connect 36597 max component size=2543 min component_size=1 avg component size=1.06945924529333 components on level=0 notFullyConnected=39137 numNodesOnLevel=39139
1> HNSW 1 [2025-02-12T20:15:00.406824Z; TEST-TestKnnFloatVectorQuery.testFewDistinctVectors-seed#[29F3C0E3B32A8A0D]]: vectorOps: max=18056 min=4 std=5352.391988634614 avg=9055.092
1> HNSW 1 [2025-02-12T20:15:00.408499Z; TEST-TestKnnFloatVectorQuery.testFewDistinctVectors-seed#[29F3C0E3B32A8A0D]]: connect 2294 max component size=189 min component size=1 avg component size=1.0819529206625982 components on level=1 notFullyConnected=2480 numNodesOnLevel=2482
1> HNSW 1 [2025-02-12T20:15:00.515135Z; TEST-TestKnnFloatVectorQuery.testFewDistinctVectors-seed#[29F3C0E3B32A8A0D]]: vectorOps: max=1677 min=11 std=517.4268668130792 avg=871.3201
1> HNSW 1 [2025-02-12T20:15:00.515518Z; TEST-TestKnnFloatVectorQuery.testFewDistinctVectors-seed#[29F3C0E3B32A8A0D]]: connect 117 max component size=35 min component size=1 avg component size=1.2905982905982907 components on level=2 notFullyConnected=150 numNodesOnLevel=151
1> HNSW 1 [2025-02-12T20:15:00.516252Z; TEST-TestKnnFloatVectorQuery.testFewDistinctVectors-seed#[29F3C0E3B32A8A0D]]: vectorOps: max=116 min=26 std=42.01213116516541 avg=56.77587
1> HNSW 1 [2025-02-12T20:15:00.516475Z; TEST-TestKnnFloatVectorQuery.testFewDistinctVectors-seed#[29F3C0E3B32A8A0D]]: connect 1 max component size=8 min component size=8 avg component size=8.0 components on level=3 notFullyConnected=8 numNodesOnLevel=8
```
So, for a total of 39139 vectors, we end up with 36597 components to connect (so, almost every node is its own component). This then requires on average 9k vector ops to connect each component (worst case was 18056).
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2675147250
> I mean that during search, we would by default have more neighbors to look at.
I see, yes, that's true.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] HNSW connect components can take an inordinate amount of time [lucene]
Posted by "txwei (via GitHub)" <gi...@apache.org>.
txwei commented on issue #14214:
URL: https://github.com/apache/lucene/issues/14214#issuecomment-2749658069
Can we expose a graph construction parameter in `Lucene99HnswVectorsFormat` to gate the `connectComponents()` call? This would allow us to mitigate this issue while a more comprehensive fix is developed.
Additionally, would this (or a similar) fix be considered for backporting to a potential `9.12.2` release?
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org