Repository navigation
LSMVectorIndex.remove() scans all vector ids per call: any record update on a vector-indexed type is O(index size), bulk edge-connect degrades quadratically #5318
Description
Summary
LSMVectorIndex.remove(Object[], Identifiable) is O(index size): it materializes all vector ids and linearly scans them to find the entries matching one RID. Because DocumentIndexer.updateDocument() fires this on every record update of a vector-indexed type (even when the indexed embedding property is unchanged), any bulk operation that rewrites vertex records of such a type degrades quadratically.
I hit it with GraphBatch bidirectional edges: the deferred incoming-edge connect updates each destination vertex once to attach the IN chunk pointer. With ~213k vectors in the index and ~210k vertex updates, the connect phase ran for hours at ~10-60 edges/sec (measured both contended and solo), fully CPU-bound. The identical graph without a vector index on the vertex type connects at >500k edges/sec.
Environment
- 26.8.1-SNAPSHOT (current dev line, post OpenCypher silently returns empty results on multi-hop patterns with IN-list or mid-pattern filters (config-dependent: unidirectional edges, GAV); SQL MATCH correct in all cases #5306/ArcadeGraphManager caches stale ArcadeGraph after underlying LocalDatabase is closed and reopened — remote Gremlin traversals fail with DatabaseIsClosedException: <dbname> #5307), embedded, Java 25 (bundled JRE)
- Corpus: 213,761 vertices of type
Questionwithembedding float[384]+LSM_VECTORindex (M=16, efC=100), plusAnswer/Usertypes; 210,226 edges connected intoQuestionviaGraphBatchwith bidirectional (default) edges
Evidence
Log line from the connect phase (earlier, contended run that did complete):
GraphBatch: Connecting 210226 deferred incoming edges...
GraphBatch: Incoming edges connected: 210226 edges in 20068592.8 ms (10 edges/sec)
Thread dump captured mid-crawl on a solo run (one async slot shown; several identical; the thread had >20 minutes of CPU):
"AsyncExecutor-db-1" RUNNABLE cpu=1210211.33ms
at java.util.stream.IntPipeline.toArray
at com.arcadedb.index.vector.LSMVectorIndex.remove(LSMVectorIndex.java:3660)
at com.arcadedb.database.DocumentIndexer.updateDocument(DocumentIndexer.java:635)
at com.arcadedb.database.LocalDatabase.updateRecordNoLock(LocalDatabase.java:1154)
at com.arcadedb.database.TransactionContext.commit1stPhase(TransactionContext.java:980)
...
at com.arcadedb.database.async.DatabaseAsyncExecutorImpl$AsyncThread.run
The hot code (LSMVectorIndex.remove, non-BEGUN branch):
final List<Integer> deletedIds = new ArrayList<>();
for (int vectorId : vectorIndex.getAllVectorIds().toArray()) { // O(index size) per call
final VectorLocationIndex.VectorLocation loc = vectorIndex.getLocation(vectorId);
if (loc != null && loc.rid.equals(rid) && !loc.deleted) { ... }
}210k updates x 213k ids scanned/materialized each = ~4.5e10 operations. The IntStream.toArray allocation per call also explains the multi-core burn (parallel async slots all copying).
Minimal reproduction (pure Java)
- Create a vertex type with
embedding float[384]and anLSM_VECTORindex; insert 200k vertices with random vectors. - In a second pass, update an unrelated scalar property on every vertex (or create bidirectional edges into them with
GraphBatch). - Pass 2 is quadratic; with the vector index dropped, it is linear. Happy to attach a runnable class if useful.
Suggested directions
- Keep a RID-to-vectorId reverse map in
VectorLocationIndexsoremove()is O(k) for a RID with k vectors instead of O(index size). - Independently,
DocumentIndexer.updateDocument()could skip vector-index maintenance when the indexed property is unchanged between the old and new record image. Most updates of real workloads (edge pointers, counters, timestamps) never touch the embedding, so this likely removes the entire class of problem.
Found while benchmarking the Python bindings' hybrid workload (vector + SQL + Cypher over one Q&A corpus) for the SciPy paper; the workaround there is unidirectional edges for the vector-indexed type, which avoids the IN-pointer rewrites entirely.
Activity
fix(#5318): vector-indexed record updates were O(index size), bulk ed…
Merge #5318: vector-indexed record updates were O(index size), bulk e…
lvca commentedon Jul 18, 2026
Confirmed and fixed in
main.There were actually two problems compounding each other:
When a record on a vector-indexed type was updated, ArcadeDB compared the old and new embedding to decide whether to touch the index. Because embeddings are
float[], that comparison was by reference, not by content, so an unchanged embedding always looked "changed" and triggered a pointless remove + re-insert into the vector index on every update. Now the comparison is content-aware, so updates that don't touch the embedding (edge pointers, counters, timestamps) skip the vector index entirely.The vector index
removescanned every vector in the index to find the one belonging to a record (O(index size) per call). It now uses a RID lookup, so removing/replacing a single vector is O(1)-ish regardless of index size. This keeps genuine bulk re-embedding fast too.Net effect: bulk operations that rewrite records of a vector-indexed type (including
GraphBatchbidirectional edges) are back to linear instead of degrading quadratically. Will ship in the next release.❤️ Thanks for helping make ArcadeDB better! ArcadeDB is free and open source, sustained by its community. If it's useful to you or your company, please consider becoming a sponsor to keep development going.
paper-icde: pin arcadedb-embedded 26.8.1.dev3 (post-ArcadeData#5318) …
tae898 commentedon Jul 18, 2026
Verified on current
main(ce9dc7c via my fork sync): the exact pathological shape — 50k vertices with a 384-dim LSM_VECTOR index, then 200k bidirectional edges connected into them via GraphBatch — now completes the deferred incoming-edge connect as part of a 4.4s edge phase (~46k edges/s end-to-end). Before the fix the same shape ran at 10-60 edges/sec (my 210k-edge corpus took 5.6h). Linear behavior restored; the content-aware embedding comparison also means plain property updates on vector-indexed types no longer touch the index at all in my traces. Thanks for the fast turnaround — both fixes land in my 26.8.1.dev3 bindings release today.lvca commentedon Jul 18, 2026
Thanks @tae898 for all these reports, without them it would take months to tune and fix our vector index!
fix(#5318): vector-indexed record updates were O(index size), bulk ed…
fix(ArcadeData#7109,ArcadeData#7110,ArcadeData#7111,ArcadeData#7112):…