Tracking: External Lance vector index — Phase 1 PRs filed

[sezruby]

Tracking: External Lance vector index — Phase 1 PRs filed

Tracker for the External Lance vector index delivery. RFC + design + cluster benchmark numbers + architecture deep-dive live in:

• RFC + benchmark: External Lance vector index over parquet — RFC #4

Phase 1 PRs (DRAFT, gated on RFC review)

Two parallel PRs implement Phase 1 end-to-end:

Repo	PR	What it ships
sezruby/lance	sezruby/lance#1	Rust core + JNI bindings + Java surface for ExternalIvfPqIndex
sezruby/lance-spark	#5	Scala wrapper, IndexedNearestJoinExternal, fused probe+materialize stage, benchmark vs temp-Lance / Lance-native-indexed

The lance-spark PR depends on the lance-core PR — lance.version is bumped from 6.0.0-beta.4 → 7.1.0-beta.1 to pull in the new external-index API. Both PRs need RFC review before becoming merge candidates.

Test status

• ✅ lance-core: 14 unit tests + 1 integration test (tests/external_index_phase1.rs) — build → open → search recall → fetchRows projection → RowFilter exclusion. All passing.
• ✅ JNI: 5 smoke tests (handle load, exception bridge, packed-rid round trip, params builder). All passing.
• ✅ lance-spark: IndexedNearestJoinExternalTest end-to-end (16 left vectors × 2 parquet files of 320 rows). Passing locally.
• ✅ Cluster benchmark on Spark 3.5 — passing, numbers in External Lance vector index over parquet — RFC #4.

Highlights from #4

The headline finding from the cluster benchmark (full table + methodology in #4):

At wide-medium (|R|=1M, dim=128, 16 string payload columns, K=10, |L|=100), the external-index path's warm per-query latency is 570 ms vs the temp-Lance path's 18,128 ms — a 31.8× speedup. The external-index pays a one-time 30-second index build that amortizes after ~2 queries at this scale.

External-index is the right answer when:

1. R is a stable parquet/Delta table on storage (sidecar pattern).
2. The same R is queried many times — index build amortizes immediately.
3. Wide payload columns — temp-Lance write cost grows linearly with width; external-index reads only top_K × |L| × projection_cols from source parquet.

Temp-Lance (#3) stays the right answer when R is an arbitrary subplan — joins, projections, computed columns. The two paths are additive, not competing.

Phase 1.6 — cloud-storage perf optimizations: ✅ shipped

Optimization layer on top of Phase 1.5. Same external-index API, same recall, abfss/cloud-storage path now ~75% faster (12s → 3s warm at wide-tiny on a 2-worker × 4-core DBR cluster). See #7 §7.4 and #4 "Cloud-storage (abfss) — Phase 1.6 follow-up" for the timeline + per-batch breakdown.

Surface changes:

• ExternalIvfPqIndex.search_batch (Rust core) / nativeSearchBatch (JNI) / searchBatch(float[][], ...) (Java) / probeBatch(Array[Array[Float]], ...) (Scala wrapper)
• ExternalFusedStage.fusedPartition issues one batched probe call per Spark task instead of N per-query calls
• ParquetMetaCache on OpenedExternalIndex reuses footer + page-index across queries within a task
• CoalescingParquetReader wraps ParquetObjectReader with a tunable coalesce gap + parallelism
• Per-batch timing diagnostics gated on LANCE_LOG=lance::index::vector::external=info

The headline 570 ms wide-medium / 8.6 sec mega-medium numbers above are local-fs uniform-pool measurements. Cloud-storage is a different operating point — see the linked sections for those numbers.

What's NOT in Phase 1

Tracked for follow-up; covered in #4:

• Persistent index across Spark sessions (Phase 2). Phase 1 has an in-process driver-side cache; cross-application reuse needs manifest fingerprint validation (mtime/size/footer-hash) at open() to detect stale indexes after parquet rewrites.
• SQL Catalyst integration (Phase 3 in the lance-spark side). Phase 1 ships the DataFrame API entry point only.
• HNSW / IVF-FLAT external builds (Phase 2/3 lance-core). Same shape as IVF-PQ, separate work.
• append() / compact() for incremental index updates (Phase 4 lance-core).

Cross-compile notes for contributors

Cluster runs require nativelib/linux-x86-64/liblance_jni.so. Local cargo build on macOS arm64 produces only darwin-aarch64/liblance_jni.dylib. Workflow that works:

brew install zig
cargo install cargo-zigbuild
rustup target add x86_64-unknown-linux-gnu

cd $LANCE_REPO/java/lance-jni
cargo zigbuild --target x86_64-unknown-linux-gnu --release

# Graft into the lance-core JAR before building the lance-spark fat JAR:
cd /tmp/jar-patch
mkdir -p nativelib/linux-x86-64
cp $LANCE_REPO/java/lance-jni/target/x86_64-unknown-linux-gnu/release/liblance_jni.so \
   nativelib/linux-x86-64/
jar uf ~/.m2/repository/org/lance/lance-core/$VERSION/lance-core-$VERSION.jar \
   nativelib/linux-x86-64/liblance_jni.so

cross (Docker) hits the aws-lc-sys GCC blocklist on its default image; centos image has GCC 10 but its bundled Rust toolchain is too old for the workspace's edition = "2024". cargo zigbuild sidesteps both: uses host's rustup toolchain + zig-supplied glibc-targeted clang.

Update (Phase 1.6): cross also works with the Ubuntu-based ghcr.io/cross-rs/x86_64-unknown-linux-gnu:main image plus a small Cross.toml that pre-installs protoc 25.1, plus a [patch.crates-io] to a vendored copy of aws-lc-sys 0.41.0 with the gcc-bug-95189 self-check assertion stripped (assertion mis-fires under QEMU emulation on darwin-arm64; the actual crypto code is fine). Either path produces an equivalent linux .so.

Upstream lance-core CI cross-builds for all 3 architectures and publishes the multi-arch JAR; this workflow is only needed for in-flight branches not yet published.

---

Update — rerank stores + distributed build landed (measured)

Two capabilities added since the Phase-1 filing, both measured on a uniform-pool cluster (CPU-gated) at real Cohere-wiki dim=1024, |R|=10M. Full numbers + method in RFC #4 (see the "rerank stores + distributed build" update section); summary:

• Co-located rerank stores (SQ8 / Flat), opt-in. Refine reads a contiguous byte-range copy of the vector beside the index instead of page-decoding the wide parquet column. SQ8 ≈ 2× faster end-to-end at |L|=5000 (226 s vs 464 s join), equal recall (~72%). SQ8 and Flat are a dead heat on recall+latency; SQ8 is the default at ¼ the storage.
• Distributed build. Driver trains on a sample + broadcasts quantizers; executors shard-encode the corpus (index + sidecar in one scan); driver merges (only PQ codes cross back). 6.40× (index) / 10.28× (index + SQ8 sidecar) at |R|=20M on 8 executors. Search latency is |R|-independent (flat 10M→20M), so build grows with |R| and search does not.

Proven correct at the lance-rs layer (sharded build ≡ whole-corpus build). Code on the external-index-rerank-store branches (lance + lance-spark).

[sezruby]

Cluster benchmark refreshed — corrected baselines

Updated cluster numbers and methodology — see #4 (comment) for the full update. Key changes:

• C-indexed comparison fixed — earlier "C" was un-indexed Lance-native R (brute-force scan). Now properly compares to Lance-native + IVF-PQ index, which is the apples-to-apples reference.
• Parallelism heuristic added to IndexedNearestJoinExternal — sizes target tasks from numL / TargetRowsPerTask, capped at defaultParallelism. Brought E warm from ~4,300ms to ~600ms at wide-medium.
• Stable headline: at wide-medium, E warm (≈600ms) is comparable to C-indexed-narrow (≈545ms) — both sub-second, within cluster noise. E warm is ~27× faster than B-narrow (≈16,500ms).

The PRs (sezruby/lance#1, #5) carry the parallelism fix + cleanup helpers; bench numbers in their descriptions are still the older (single-run) numbers and need a refresh too.

[sezruby]

Distributed-build internals — decomposition + two negative findings

Follow-up profiling on the Phase 1.6 distributed build (|R|=100M, dim=1024), split into its three phases — train / encode / merge.

Sample-read for training — off-heap gather. Pulling the training sample corpus-wide through the JVM heap both OOM'd at scale and dominated wall-clock. Reworked so each worker writes a compact pre-sampled parquet for its shard and the driver reads those off-heap and trains fully native (no per-iteration stages, no JVM-heap collect):

• train 338s → 65.6s (5.15×); within train, sample-read 240s → 8.8s and row-count 55s → 2.6s (~26× on the I/O)

Merge — parallel shard pre-read. Shards were read one at a time ahead of the serial heap-merge writer; pre-reading all shards concurrently (bounded) before the writer: merge 194s → 34s (5.72×). (A lazy/streaming merge was prototyped and rejected — the writer seeds its merge heap by peeking every stream serially, which would re-serialize the reads.)

After both, the breakdown is train 65.6s / encode 119.4s / merge 34s — encode is now the dominant phase, and it's compute-bound (near-linear in worker cores, ~61-way parallel efficiency measured), not I/O-bound. End-to-end the 100M build went ~652s → ~220s.

Negative finding 1 — GEMM encode-assignment: no win

Encode's inner loop is nearest-centroid assignment. Reformulating it as a blocked GEMM (‖x−c‖² tiled in cache, argmin-preserving) measured 0.95× — marginally slower. The centroid table is cache-resident, so the existing per-vector SIMD kernel is already near-optimal, and the GEMM path uses its own thread pool so it can't compose with the concurrent per-shard pipeline. Implemented, correctness-proven recall-neutral, then reverted. The remaining recall-neutral encode lever is wiring the already-trained approximate membership index into the encode path (the machinery exists but is training-only today); otherwise nlist and core count are the tuning levers.

Negative finding 2 — distributing centroid training is completeness, not perf

Built a distributed centroid-training primitive (partial-stats E-step on workers, M-step on the driver). Then measured native single-box training at the operating point (dim=1024, nlist=4096, ~1M sample): ~2.5s — hierarchical k-means + graph membership auto-engage above a few hundred centroids, so training is ~linear in nlist, not quadratic. Distributing it saves single-digit seconds — a robustness item for very large sample/nlist, off the critical path. Primitive kept, not wired into the default build.

Code

Organized + pushed: sezruby/lance branch indexed-merge-scalar-index — distributed build (off-heap sample-read + parallel merge) + the distributed-kmeans primitive + JNI/Java surface. lance-jni compiles clean.