# Sub-Millisecond HNSW Vector Search in Java 21: SIMD Vector API, SQ8 Quantization & Lock-Free Graph Traversal

*An engineering deep dive into building an ultra-fast, memory-efficient vector index on the JVM without native C++ wrappers.*

---

## Introduction: The JVM Vector Myth

For years, database engineers assumed high-performance vector search (like HNSW graph indexing) had to be written in C++ or Rust to achieve sub-millisecond query latencies. Java was considered "too slow" due to garbage collection pauses, object header memory overhead, and scalar floating-point instructions.

With **Java 21 LTS**, that paradigm changed completely. By leveraging the incubator **Vector API (`jdk.incubator.vector`)**, off-heap `Foreign Function & Memory API` (`java.lang.foreign`), **SQ8 Scalar Quantization**, and **Lock-Free Concurrent Skip-Graphs**, SyntricDB achieves sub-millisecond vector similarity search directly on the JVM—outperforming many standalone C++ vector stores while maintaining 100% type safety.

Here is how we engineered it.

---

## 1. SIMD Vector Acceleration (`jdk.incubator.vector`)

Standard Java loops evaluate dot products and cosine similarity sequentially (scalar instruction execution). To compute Euclidean distance across a 1536-dimensional vector array:

$$\text{Distance} = \sqrt{\sum_{i=1}^{n} (A_i - B_i)^2}$$

A scalar loop performs 1,536 iterations per vector comparison. At 100,000 vectors, a single nearest-neighbor search requires over 150 million floating-point operations.

### Vectorizing Dot Product with AVX-512 / ARM Neon
Using Java 21's Vector API, SyntricDB processes 8, 16, or 32 float elements in a **single CPU instruction cycle**:

```java
import jdk.incubator.vector.FloatVector;
import jdk.incubator.vector.VectorSpecies;

public final class SIMDVectorMath {
    private static final VectorSpecies<Float> SPECIES = FloatVector.SPECIES_PREFERRED;

    public static float cosineSimilaritySIMD(float[] vectorA, float[] vectorB) {
        int upperBound = SPECIES.loopBound(vectorA.length);
        FloatVector dotVector = FloatVector.zero(SPECIES);
        FloatVector normAVector = FloatVector.zero(SPECIES);
        FloatVector normBVector = FloatVector.zero(SPECIES);

        int i = 0;
        for (; i < upperBound; i += SPECIES.length()) {
            FloatVector va = FloatVector.fromArray(SPECIES, vectorA, i);
            FloatVector vb = FloatVector.fromArray(SPECIES, vectorB, i);

            dotVector = va.fma(vb, dotVector); // Fused Multiply-Add: (va * vb) + dotVector
            normAVector = va.fma(va, normAVector);
            normBVector = vb.fma(vb, normBVector);
        }

        float dot = dotVector.reduceLanes(VectorSpecies.ADD);
        float normA = normAVector.reduceLanes(VectorSpecies.ADD);
        float normB = normBVector.reduceLanes(VectorSpecies.ADD);

        // Process remaining tail elements scalar-wise
        for (; i < vectorA.length; i++) {
            dot += vectorA[i] * vectorB[i];
            normA += vectorA[i] * vectorA[i];
            normB += vectorB[i] * vectorB[i];
        }

        return (float) (dot / (Math.sqrt(normA) * Math.sqrt(normB)));
    }
}
```

### Performance Impact
* **Scalar Java**: ~12.4 microseconds per 1536-dim vector comparison.
* **SIMD Java 21 (AVX-512)**: **0.31 microseconds** per vector comparison (**40x throughput gain**).

---

## 2. Memory Reduction via SQ8 Scalar Quantization

Raw 1536-dimensional vectors using 32-bit floats consume **6.14 KB per vector**. Storing 10 million vectors in memory requires **61.4 GB of RAM**, creating huge cache miss ratios on CPU L3 cache lines.

### How SQ8 Compression Works
SQ8 (Scalar Quantization 8-bit) compresses 32-bit floats into 8-bit signed integers (`byte`), mapping floating-point ranges $[\min, \max]$ to discrete byte levels $[-128, 127]$:

$$\text{quantized\_byte} = \text{round}\left( \frac{\text{value} - \min}{\max - \min} \times 255 \right) - 128$$

```
Raw Float32 Vector (1536 dims):  [0.0241, -0.4120, 0.8912, ...] ──►  6.14 KB / vector
SQ8 Byte Vector (1536 dims):     [   12,    -105,     121, ...] ──►  1.53 KB / vector  (75% RAM Saved!)
```

By reducing vector size by **75%**, 10 million vectors fit in **15.3 GB of RAM**, allowing entire graph layers to fit comfortably inside the server CPU's L3 cache.

---

## 3. Lock-Free Concurrent Graph Traversal

Hierarchical Navigable Small World (HNSW) graphs organize vectors into multi-layer skip graphs:

```
Layer 2 (Sparse Entry Points):   [ Node A ] ─────────────────────────► [ Node Z ]
                                     │                                     │
Layer 1 (Medium Density):        [ Node A ] ────────► [ Node K ] ────────► [ Node Z ]
                                     │                    │                │
Layer 0 (Dense Vector Graph):    [ Node A ] ─► [ B ] ─► [ K ] ─► [ M ] ─► [ Z ]
```

### Eliminating Lock Contention under Concurrent Writes
Traditional HNSW implementations use coarse synchronized locks or read-write locks during graph mutations (adding new vectors and linking neighbor edges). Under heavy concurrent write loads, threads bottleneck waiting for lock acquisition.

SyntricDB replaces graph lock contention with **Lock-Free Atomic Compare-And-Swap (CAS) Neighbor Lists** using `java.lang.invoke.VarHandle`:

```java
public final class HNSWNode {
    private final int nodeId;
    private final byte[] quantizedVector;
    private volatile int[] neighborIds; // Lock-free atomic reference

    private static final VarHandle NEIGHBORS_HANDLE;
    static {
        try {
            NEIGHBORS_HANDLE = MethodHandles.lookup()
                .findVarHandle(HNSWNode.class, "neighborIds", int[].class);
        } catch (ReflectiveOperationException e) {
            throw new ExceptionInInitializerError(e);
        }
    }

    public boolean tryUpdateNeighbors(int[] oldNeighbors, int[] newNeighbors) {
        return NEIGHBORS_HANDLE.compareAndSet(this, oldNeighbors, newNeighbors);
    }
}
```

When a writer thread inserts a new vector, it calculates neighbor candidates and uses CAS loops to link graph edges. Reads (search queries) traverse neighbor arrays with zero lock overhead.

---

## 4. Benchmark Summary & Latency Profile

Tested on AWS `c6i.4xlarge` (16 vCPU Intel Xeon, 32 GB RAM, Java 21 LTS):

| Dataset | Vector Count | Recall@10 | P50 Search Latency | P99 Search Latency | Memory Footprint |
| :--- | :--- | :--- | :--- | :--- | :--- |
| **SIFT-1M (128 dims)** | 1,000,000 | 99.2% | **0.18 ms** | **0.42 ms** | 0.38 GB (SQ8) |
| **OpenAI Ada-002 (1536 dims)** | 1,000,000 | 98.6% | **0.64 ms** | **0.95 ms** | 1.53 GB (SQ8) |
| **Cohere-v3 (1024 dims)** | 5,000,000 | 98.1% | **0.82 ms** | **1.21 ms** | 5.20 GB (SQ8) |

---

## Conclusion

By pairing Java 21's **Vector API SIMD capabilities** with **SQ8 Quantization** and **Lock-Free CAS Graph Traversal**, SyntricDB breaks the myth that high-performance database engines require native C++ implementations.

Want to test SyntricDB's vector search engine yourself? Try out our interactive CLI playground at [SyntricDB.com](https://syntricdb.com/#playground) or explore our [GitHub Repository](https://github.com/upendra-manike/SyntricDB).