feat: LSM_SPARSE_VECTOR index for sparse embedding retrieval

[lvca]

Feature Request: Sparse Vector Index (LSM_SPARSE_VECTOR)

Originated from discussion #4044 (Qdrant to ArcadeDB migration).

Overview

Add a native sparse vector index type, LSM_SPARSE_VECTOR, that persists sparse embedding vectors and serves top-K dot-product retrieval. The index reuses the LSM-Tree storage backbone already used by FULL_TEXT and LSM_VECTOR, so it inherits ACID, WAL, HA, and compaction without introducing a separate storage engine.

ArcadeDB already ships the in-memory primitives (SparseVector class and the vector.sparseCreate, vector.sparseDot, vector.denseToSparse, vector.sparseToDense SQL functions) but has no persistent index backing them. This issue adds the missing piece.

Use cases (intentionally generic, not tied to one model):

• SPLADE-style learned sparse retrieval (e.g. opensearch-neural-sparse-encoding-multilingual-v1).
• BM25-as-sparse-vector pipelines.
• LDA topic vectors, multi-hot categorical embeddings, generic sparse ML features.
• Hybrid dense+sparse retrieval where dense alone collapses semantically distinct queries (the case in Migrating from Qdrant to ArcadeDB — stuck on sparse vector indexing and server-side hybrid search #4044, e.g. «начисление процентов» vs «начисление баллов», "freeze card after theft" vs "unfreeze card after travel").

Design

Storage layout

Posting-list inverted index, keyed by sparse dimension id. The composite key {int dim_id, RID rid, float weight} sorts postings within a dim by RID ascending, which is the order required by WAND-style document-at-a-time scoring.

key:   (int dim_id, RID rid, float weight)
value: rid

• Per-dim max_weight upper bound is maintained as a sidecar map (lazily populated on first WAND query, then kept monotone via put; deletes leave it conservatively high, still a valid upper bound).
• Mutable LSM segments accept inserts; compaction produces immutable RID-sorted segments naturally because the LSM-Tree backbone already does this.
• Optional IDF statistics in the index metadata enable the IDF modifier.

The tighter per-entry max_next_weight (BlockMax-WAND) is intentionally deferred to #4068 along with weight quantization and parallel per-segment scoring; those are the steps that scale the index from the 2-3K-vector use case in #4044 to the 100M+ regime.

Property persistence

Two parallel properties on the indexed type, using the existing Type.ARRAY_OF_INTEGERS and Type.ARRAY_OF_FLOATS:

• <name>_indices of type ARRAY_OF_INTEGERS
• <name>_values of type ARRAY_OF_FLOATS

This avoids introducing a new Type.SPARSE_VECTOR and matches how LSM_VECTOR already operates on ARRAY_OF_FLOATS.

Schema API

SQL (keyword is LSM_SPARSE_VECTOR, matching the LSM_VECTOR precedent and the enum name):

CREATE PROPERTY Document.tokens ARRAY_OF_INTEGERS;
CREATE PROPERTY Document.weights ARRAY_OF_FLOATS;

CREATE INDEX ON Document (tokens, weights) LSM_SPARSE_VECTOR
  METADATA { "dimensions": 105000, "modifier": "IDF" };

Java:

schema.buildTypeIndex("Document", new String[]{"tokens", "weights"})
    .withSparseVectorType()
    .withDimensions(105000)
    .withModifier("IDF")        // optional, default = NONE
    .create();

Query API

New SQL function vector.sparseNeighbors, mirroring vector.neighbors:

SELECT expand(`vector.sparseNeighbors`(
    'Document[tokens,weights]',
    $queryIndices, $queryValues,
    50,
    { filter: [<rid>, ...] }
))

Options map (forward-compatible with the groupBy and fusion issues below):

• filter: list of allowed RIDs (post-filter).
• groupBy, groupSize: see feat: groupBy/groupSize options on vector.neighbors for diversified retrieval #4067.

Top-K algorithm

Document-at-a-time min-heap with WAND pivot-based skipping. Per-dim cursor sorted by current RID; pivot is the smallest cursor index where the prefix sum of upper bounds exceeds the K-th best score so far. Cursors below the pivot seek forward to the pivot's RID; aligned cursors at the pivot score the doc and advance.

Only dot-product similarity is supported (Qdrant carries the same restriction; cosine on sparse is handled by L2-normalizing both query and stored vectors at insert time).

Acceptance criteria

• New Schema.INDEX_TYPE.LSM_SPARSE_VECTOR enum entry.
• SQL CREATE INDEX ... LSM_SPARSE_VECTOR syntax (with METADATA { dimensions, modifier }).
• Java schema builder withSparseVectorType() + .withDimensions() + .withModifier().
• LSM-Tree-backed posting-list storage with per-dim max_weight upper bound. (Tighter per-entry max_next_weight deferred to feat: WAND/BlockMax-WAND dynamic pruning for LSM_SPARSE_VECTOR (scale to 100M+) #4068 Step 3.)
• Top-K dot-product retrieval with WAND-style pruning.
• SQL function vector.sparseNeighbors(indexSpec, indices, values, K, options).
• Optional IDF modifier.
• Persistence test (persistAcrossReopenAndQueryStillWorks).
• Concurrency test (LSMSparseVectorIndexConcurrencyTest, @Tag("slow")).
• Correctness test: results match brute-force vector.sparseDot baseline (createIndexViaJavaApiAndQueryTopK + wandResultsMatchBruteForceOnLargerCorpus).
• Benchmark vs. brute-force on 100k+ vectors (LSMSparseVectorIndexBenchmark, @Tag("benchmark")). The MVP WAND with only dim-level upper bounds does not yet beat plain scan at 100k with skewed query distributions; the BlockMax-WAND step in feat: WAND/BlockMax-WAND dynamic pruning for LSM_SPARSE_VECTOR (scale to 100M+) #4068 is what closes the gap at this scale.

Out of scope (future work)

• L2 / cosine for sparse (use pre-normalized vectors instead).
• Dimension-id remapping at index time.
• Cross-segment IDF rebalancing during compaction (initial version recomputes df per query; feat: WAND/BlockMax-WAND dynamic pruning for LSM_SPARSE_VECTOR (scale to 100M+) #4068 will maintain it incrementally).
• BlockMax-WAND, weight quantization, parallel per-segment scoring -> tracked in feat: WAND/BlockMax-WAND dynamic pruning for LSM_SPARSE_VECTOR (scale to 100M+) #4068.

Related

• Discussion: Migrating from Qdrant to ArcadeDB — stuck on sparse vector indexing and server-side hybrid search #4044
• Follow-up: feat: WAND/BlockMax-WAND dynamic pruning for LSM_SPARSE_VECTOR (scale to 100M+) #4068 (WAND/BlockMax-WAND scaling work, max_next_weight, quantization, parallel segments)
• Companion issues: feat: server-side hybrid retrieval fusion (vector.fuse with RRF/DBSF/LINEAR) #4066 (hybrid fusion vector.fuse), feat: groupBy/groupSize options on vector.neighbors for diversified retrieval #4067 (groupBy on vector.neighbors).

cc @astarso

[lvca]

All acceptance criteria are now closed out (see updated body). Working on the sparse-vector-index branch.

Summary of what landed:

• Storage: LSM_SPARSE_VECTOR index with composite key (int dim_id, RID rid, float weight) on the LSM-Tree backbone. Postings within a dim are sorted by RID ascending, which is what WAND requires.
• Schema: Schema.INDEX_TYPE.LSM_SPARSE_VECTOR enum entry, Java .withSparseVectorType().withDimensions(N).withModifier("IDF") builder, SQL CREATE INDEX ON T (a,b) LSM_SPARSE_VECTOR METADATA { "dimensions": N, "modifier": "IDF" }.
• Retrieval: vector.sparseNeighbors(indexSpec, indices, values, K [, options]) SQL function with filter option. WAND DAAT scorer with min-heap of size K, per-dim max_weight upper bound (lazily populated, kept monotone), seekTo(rid) cursor primitive for pivot-based skipping. Results identical to brute-force vector.sparseDot baseline within numerical tolerance.
• Modifier: IDF (Robertson-Sparck-Jones formula) folds into query weights at scoring time.
• Tests: 7 sparse-vector tests pass (correctness, persistence, removal, IDF semantics, large-corpus brute-force agreement at K=1/5/25/100, parallel writers+readers, 100k benchmark). 470 broader regression tests pass with no failures.

Honest benchmark observation: at 100k docs / 30 nnz per doc / 5K-dim vocabulary / skewed query distribution, the MVP WAND (dim-level upper bound only) is slower than plain brute-force vector.sparseDot (avg 1213ms vs 730ms per query). This is the regime where dim-level upper bounds are too loose to enable enough skipping; it's exactly what BlockMax-WAND in #4068 Step 3 is designed to fix (per-page upper bounds, much tighter pruning).

For astarso's actual use case in #4044 (~2-3K sparse vectors), the index is well below the crossover point where WAND would even matter; the MVP works fine there.

Closing out #4065 in favor of #4068 for the scaling work.

[lvca]

All 11 acceptance criteria green