DuckDB-VSS: LSH-Based VSS Join Optimization

April 17, 2026 · View on GitHub

This project has been forked from the duckdb-vss extension. It accelerates vector similarity search (VSS) joins using Locality Sensitive Hashing (LSH) index.

Problem Statement

The existing vss_join function performs top-k nearest neighbor joins by computing a cross-join between tables A and B. This has two key limitations:

Quadratic time complexity — O(|A| × |B|) distance computations, which becomes prohibitive at scale
No cost amortization — each row in A performs an independent full scan of B, causing cache thrashing

Solution

We implement lsh_join using random hyperplane LSH with multi-probe neighboring buckets:

Hash-based partitioning — vectors are hashed into buckets using K random hyperplanes; similar vectors tend to land in the same bucket
Cost amortization — hash tables are built once over the right table and reused for all queries in the left table
Near-linear complexity — only candidate vectors from matched buckets are distance-ranked, not the full right table
Multi-probe — 1-bit-flip neighbors are also probed to recover similar vectors that fall just across a boundary

Supported metrics: l2sq (Euclidean), cosine / cos (cosine distance), ip (inner product).

Function Signature

lsh_join(
    left_table  VARCHAR,   -- name of the query table
    right_table VARCHAR,   -- name of the corpus table
    left_col    VARCHAR,   -- vector column in left_table
    right_col   VARCHAR,   -- vector column in right_table
    k           INTEGER,   -- number of nearest neighbors to return
    metric      VARCHAR,   -- 'l2sq' | 'cosine' | 'cos' | 'ip'
    num_tables  INTEGER,   -- (optional) number of hash tables L; default 10
    num_bits    INTEGER    -- (optional) bits per hash K; default 10
)

Usage Example:

SELECT * FROM lsh_join('queries', 'corpus', 'vec', 'vec', 10, 'l2sq');

-- Override defaults
SELECT * FROM lsh_join('queries', 'corpus', 'vec', 'vec', 10, 'l2sq',
                       num_tables=20, num_bits=8);

Success Criteria

Metric	Target	Config
Recall@10	≥ 85%	K=8, L=10, 100K rows, l2sq
Recall@10	≥ 90%	K=8, L=20, 100K rows, l2sq
Speedup vs brute force	≥ 10×	K=8, L=10, 100K rows, l2sq

Code Changes

LSH-related code is newly added. The changes to existing codebase are the build system wiring and the extension registration.

New files

File	Description
`src/include/lsh/lsh.hpp`	Public header: `LSHIndex` class declaration
`src/lsh/lsh_index.hpp`	Internal header: distance functions, TopK, hyperplane layout
`src/lsh/lsh_index.cpp`	Index implementation: build, probe, topK; AVX-512/AVX2 distance kernels
`src/lsh/lsh_join.hpp`	Table function header: binds data and global state structs
`src/lsh/lsh_join.cpp`	DuckDB table function: bind, global init and execute pipeline
`src/lsh/CMakeLists.txt`	Build config: AVX-512 / AVX2+FMA flags scoped to `lsh_index.cpp`
`test/sql/lsh/test_lsh_join.test`	SQL regression tests
`benchmark/bench-lsh-join.sql`	Benchmark script
`benchmark/analyze-results.ipynb`	Notebook to analyze results
`scripts/download-datasets.sh`	Downloads SIFT1M and GloVe-100 datsets
`scripts/convert-to-parquet.py`	Converts dataset files to Parquet to work with DuckDB

Modified files

File	Change
`CMakeLists.txt`	Added `lsh` subdirectory
`src/vss_extension.cpp`	Registered `lsh_join` table function in the extension entry point

Step 1 — Build the Extension

make

This produces:

./build/release/duckdb                          # DuckDB shell with extension loaded
./build/release/test/unittest                   # test runner
./build/release/extension/vss/vss.duckdb_extension

Run the shell:

./build/release/duckdb

Run the SQL tests:

make test

Step 2 — Download Datasets

bash scripts/download_datasets.sh

Downloads:

Dataset	Size	Destination
SIFT1M (128-d geometric vectors)	~161 MB	`benchmark/data/sift/`
GloVe Twitter 27B 100d (text embeddings)	~1.4 GB	`benchmark/data/glove/`

Existing files are skipped automatically.

Step 3 — Convert to Parquet

Requires pyarrow:

pip install pyarrow

# SIFT1M base vectors (1M × 128)
python3 scripts/convert_to_parquet.py \
    --input  benchmark/data/sift/sift_base.fvecs \
    --output benchmark/data/sift/sift_base.parquet \
    --format fvecs

# SIFT1M query vectors (10K × 128)
python3 scripts/convert_to_parquet.py \
    --input  benchmark/data/sift/sift_query.fvecs \
    --output benchmark/data/sift/sift_query.parquet \
    --format fvecs

# SIFT1M ground truth (10K queries × 100 true neighbors)
python3 scripts/convert_to_parquet.py \
    --input  benchmark/data/sift/sift_groundtruth.ivecs \
    --output benchmark/data/sift/sift_groundtruth.parquet \
    --format ivecs

# GloVe-100 embeddings (1.2M × 100)
python3 scripts/convert_to_parquet.py \
    --input  benchmark/data/glove/glove.twitter.27B.100d.txt \
    --output benchmark/data/glove/glove_100d.parquet \
    --format glove_txt

Output schemas:

fvecs / glove_txt → id INT32, vec FLOAT[]
ivecs (ground truth) → query_id INT32, neighbors INT32[]

Step 4 — Run Benchmarks

mkdir -p benchmark/results
./build/release/duckdb -unsigned -init benchmark/bench_lsh_join.sql

File	Experiment
`exp1-speedup.csv`	Speedup vs brute force at 10K / 100K / 1M rows
`exp2-recall-vs-L.csv`	Recall@10 and query time vs number of hash tables L
`exp3-pareto.csv$	\text{Recall}@10 \text{vs} \text{QPS} \text{across} \text{K} \times \text{L} \text{grid}
$exp4-glove.csv`	Cross-dataset validation on GloVe-100 (cosine metric)

Note: The 1M-row brute-force run in Experiment 1 can take 10–30 minutes depending on hardware. Comment out the _bf_1m block in the SQL file to skip it.

Step 5 — Analyze Results

cd benchmark
jupyter notebook analyze_results.ipynb

Experiment	Figure
Exp 1	Grouped bar chart: BF vs LSH query time across table sizes
Exp 2	Bar chart: query time vs L (shows linear cost scaling)
Exp 3	Pareto scatter: Recall@10 vs QPS, colored by K
Exp 4a	Bar chart: BF vs LSH time on GloVe-100
Exp 4b	Line plot: Recall@10 vs L on GloVe-100
Summary	PASS / FAIL table for all success criteria