Repository navigation
Description
1. Summary
Yes — a single 138,364,198-doc / 28,705,961,023-nnz segment is achievable, but only by widening the CSR nnz-offset type from 32-bit to 64-bit end-to-end. The blocker is a single overloaded typedef, using idx_t = int32_t; (nsparse/types.h:18), which is used for two semantically different things: (a) doc-ids — 138,364,198 fits comfortably in int32 (INT32_MAX = 2,147,483,647, i.e. doc count is 0.064× the limit — no change needed); and (b) CSR indptr offsets over the flat nnz stream — the final offset equals total nnz = 28,705,961,023, which is 13.37× INT32_MAX (and 6.68× UINT32_MAX). The nnz-offset use wraps once the cumulative offset first crosses INT32_MAX at document ~10.35M (7.5% into the corpus at ~207.5 nnz/doc), so ~92.5% of all docs get a corrupt/negative offset. The fix is mechanical in shape but touches many files: introduce a distinct offset_t = int64_t for nnz-offsets, retype the one storage array (SparseVectors::indptr_), the Index virtual API's indptr params, every idx_t start/end/i/nnz = indptr[...] consumer/loop across scoring and build, the on-disk indptr word width (4→8 bytes, pre-GA so no back-compat), and the Java CSR writer's int[] indptr / (int) nnz cast. Doc-id and per-block-local machinery stay 32-bit. Estimated ~30 confirmed sites across ~20 files, all the same class of change.
2. The overflow points
All rows are CONFIRMED_OVERFLOWS or PARTIAL (real defect, sometimes with the arithmetic one line up from the cited symbol). Target values: total nnz 28,705,961,023; INT32_MAX 2,147,483,647; ratio 13.37×.
2a. Forward-index storage (the root — SparseVectors CSR)
| file:line | symbol | current type | holds | reaches vs type-max | change |
|---|---|---|---|---|---|
nsparse/types.h:18 |
using idx_t = int32_t; |
int32_t |
dual-use: doc-id (safe) AND nnz-offset (overflows) | 28.7B vs 2.147B = 13.37× | split: keep idx_t=int32 for doc-ids; add offset_t=int64_t for offsets |
nsparse/sparse_vectors.h:107 |
Buf<idx_t> indptr_; |
Buf<int32_t> |
global CSR indptr; last elem = total nnz | 28.7B | Buf<offset_t> |
nsparse/sparse_vectors.h:31,83 |
SparseVectorsData.indptr_data / indptr_data() |
const idx_t* |
offset array pointer | 28.7B | const offset_t* |
nsparse/sparse_vectors.cpp:105,118-121 |
std::vector<idx_t> indptr_vec / idx_t offset=back(); push_back(indptr[i]+offset) |
int32_t |
build accumulator (silent signed-overflow UB, no guard) | 28.7B | std::vector<offset_t>, offset_t offset |
nsparse/sparse_vectors.cpp:141,150 |
idx_t offset=...back(); push_back(offset+static_cast<idx_t>(indices_size)) |
int32_t |
incremental build accumulator | 28.7B | offset_t offset, static_cast<offset_t> |
nsparse/sparse_vectors.cpp:163-169 |
idx_t start/end; for(idx_t i=start;i<end;++i); values_.data()+(i*element_size) |
int32_t |
offset reads + nnz-loop var (i*element_size is 64-bit, but i already wrapped) |
28.7B | offset_t start/end/i |
nsparse/sparse_vectors.cpp:187-195 |
idx_t start/end; for(idx_t i=...); values_[i*element_size+j] |
int32_t |
offset reads + nnz-loop var | 28.7B | offset_t start/end/i |
nsparse/sparse_vectors.cpp:222,227 |
size_t indices_size=indptr_[vector_count]; value_size=indices_size*element_size |
int32_t→size_t (sign-extend) |
serialize total-nnz read (wrapped→huge) | 28.7B | source from offset_t indptr |
nsparse/sparse_vectors.cpp:247 |
size_t indices_size = indptr_[vector_count]; |
int32_t→size_t |
deserialize total-nnz read | 28.7B | read from offset_t indptr |
nsparse/sparse_vectors.cpp:275,277 |
const idx_t* indptr = cursor->read_array<idx_t>(...); indices_size=static_cast<size_t>(indptr[vector_count]) |
const int32_t* |
mmap total-nnz read (8-byte on-disk) | 28.7B | read_array<offset_t> |
nsparse/sparse_vectors.cpp:69-72 |
for(...) if(indptr[i]<indptr[i-1]) |
int32_t cmp |
monotonicity check trips on wrap-to-negative | offset > 2.147B | offset_t elements |
nsparse/sparse_vectors.cpp:74 (PARTIAL) |
static_cast<size_t>(indptr[indptr_size-1]) != indices_size |
int32_t→size_t |
terminal-offset validation (monotonic check at :70 fires first) | 28.7B | offset_t indptr param |
2b. Scoring & build loops (seismic_*, cluster, invlists)
| file:line | symbol | current type | holds | reaches vs type-max | change |
|---|---|---|---|---|---|
nsparse/seismic_common.h:102-106,110 |
const idx_t start=indptr[doc_id]; ...; values+start*sizeof(float) |
int32_t start, const idx_t* |
doc offset into flat stream (compute_similarity) |
28.7B | offset_t start, const offset_t* indptr |
nsparse/seismic_common.cpp:117-120 |
const idx_t nnz=indptr[num_vectors()]; for(idx_t j=0;j<nnz;++j) |
int32_t |
total-nnz + nnz-loop var (wraps negative → loop body never runs) | 28.7B | offset_t nnz, for(offset_t j...) |
nsparse/seismic_common.cpp:206-212 |
for(idx_t j=indptr[doc];j<indptr[doc+1];++j); codes+static_cast<size_t>(j)*element_size |
int32_t j, const idx_t* |
offset loop (fill_from_corpus) |
28.7B | const offset_t*, offset_t j |
nsparse/seismic_index.cpp:98-102 |
const idx_t next_start=indptr[next_doc]; next_len=indptr[next_doc+1]-next_start |
int32_t |
prefetch offset (query_single_inverted_list) | 28.7B | offset_t next_start, const offset_t* |
nsparse/seismic_index.cpp:111-114 |
const idx_t start=indptr[doc_id]; len=indptr[doc_id+1]-start; indices+start |
int32_t start |
scoring offset | 28.7B | offset_t start |
nsparse/seismic_index.cpp:133 |
size_t nnz = indptr[n]; |
int32_t→size_t |
total-nnz read in add() |
28.7B | const offset_t* indptr |
nsparse/seismic_scalar_quantized_index.cpp:93,116-118 |
indptr=vectors->indptr_data(); next_start=indptr[next_doc] |
int32_t, const idx_t* |
prefetch offset (SQ path) | 28.7B | offset_t, const offset_t* |
nsparse/seismic_scalar_quantized_index.cpp:130-131 |
compute_similarity(doc_id, indptr, ...) |
const idx_t* |
offset array into scoring | 28.7B | const offset_t* |
nsparse/seismic_scalar_quantized_index.cpp:156-166 |
size_t nnz=indptr[n]; codes(nnz*element_size); add_vectors(...,nnz*element_size) |
int32_t→size_t |
total-nnz read in SQ add() |
28.7B | const offset_t* indptr |
nsparse/invlists/inverted_lists.cpp:235-237 |
for(idx_t j=indptr_data[i];j<indptr_data[i+1];++j); indices_data[j] |
int32_t j |
offset loop | 28.7B | offset_t j, const offset_t* |
nsparse/invlists/inverted_lists.cpp:253-257 (PARTIAL) |
for(idx_t j=indptr_data[i];...); values_data+(j*element_size) |
int32_t j |
offset loop (j*element_size is 64-bit; j wrapped) |
28.7B | offset_t j |
nsparse/cluster/inverted_list_clusters.cpp:96-98 |
int start=indptr_data[doc_id]; int end=indptr_data[doc_id+1]; for(size_t j=start;...) |
int (not idx_t) |
offset reads (summarize build path) | 28.7B | int64_t start/end |
nsparse/cluster/inverted_list_clusters.cpp:100-102 (PARTIAL) |
values_data+j*sizeof(T) |
int start (upstream) |
byte offset (j*sizeof(T) 64-bit; start wrapped) |
28.7B | fix start/end above |
nsparse/cluster/kmeans_utils.cpp:55,66,77,90 |
const idx_t* indptr=...; for(idx_t j=indptr[centroid];j<indptr[centroid+1];++j) |
int32_t j, const idx_t* |
3 offset loops | 28.7B | const offset_t*, offset_t j |
nsparse/cluster/kmeans_utils.cpp:111,134 |
const idx_t* indptr=...; for(idx_t j=indptr[doc_id];...) |
int32_t j, const idx_t* |
offset loop | 28.7B | const offset_t*, offset_t j |
2c. Other index implementations (brutal, inverted, id_map, Index API)
| file:line | symbol | current type | holds | reaches vs type-max | change |
|---|---|---|---|---|---|
nsparse/index.h:35,39,53,62 |
add/search/add_with_ids(..., const idx_t* indptr, ...) |
const int32_t* |
offset param on the virtual API | 28.7B | const offset_t* (all overrides) |
nsparse/brutal_index.cpp:33 |
size_t nnz = indptr[n]; |
int32_t→size_t |
total-nnz read in add() |
28.7B | const offset_t* indptr |
nsparse/brutal_index.cpp:87-90 |
const idx_t start=indptr[i]; len=indptr[i+1]-start; indices+start |
int32_t start |
scoring offset | 28.7B | offset_t start |
nsparse/inverted_index.cpp:254,262 (PARTIAL) |
size_t nnz=indptr[n]; nnz*kElementSize |
int32_t→size_t |
total-nnz read in add() (guarded by read_csr cap; see §2f note) |
28.7B | const offset_t* indptr |
nsparse/id_map_index.cpp:30-33 |
add(idx_t n, const idx_t* indptr, ...) forwards to delegate |
const int32_t* |
offset param passthrough (id-map vector stays idx_t) |
28.7B | const offset_t* indptr |
2d. Disk inline-forward (disk_seismic_*)
| file:line | symbol | current type | holds | reaches vs type-max | change |
|---|---|---|---|---|---|
nsparse/disk_seismic_index_base.cpp:47/50 |
const size_t nnz = indptr[n]; |
int32_t→size_t |
total-nnz read in add() |
28.7B | const offset_t* indptr |
nsparse/disk_seismic_index_base.cpp:262-268 |
const idx_t start=indptr[doc_id]; nnz=indptr[doc_id+1]-start; values+static_cast<size_t>(start)*element_size |
int32_t start |
whole-corpus doc offset (doc-directory write) | 28.7B | offset_t start, const offset_t* |
nsparse/disk_seismic_search.cpp:84-88 |
const idx_t start=indptr[doc_id]; len=indptr[doc_id+1]-start; values+static_cast<size_t>(start)*element_size |
int32_t start |
in-RAM score_block doc offset |
28.7B | offset_t start |
nsparse/disk_seismic_index_base.cpp:341-342 (PARTIAL, conditional) |
const idx_t r_start=r_indptr[loc.block]; ...static_cast<size_t>(r_start)*element_size |
int32_t r_start |
remainder_ CSR offset — overflows iff remainder nnz > INT32_MAX (>~7.5% of docs pruned everywhere) |
conditional | offset_t r_start, const offset_t* |
2e. IO & serialization (csr_layout, inline_forward_index_io)
| file:line | symbol | current type | holds | reaches vs type-max | change |
|---|---|---|---|---|---|
nsparse/io/csr_layout.cpp:113 |
const auto indptr = narrow<idx_t>(wide_indptr, ...) |
narrow<int32_t> (throws) |
native-CSR conversion narrows int64 file offsets → int32; throws invalid_argument at first offset > INT32_MAX |
28.7B | narrow<offset_t>; on-disk native indptr → 8-byte |
nsparse/index.cpp:122 (PARTIAL, latent) |
std::vector<idx_t> indptr(file_indptr.begin(), file_indptr.end()) |
int32_t (gated by :95-98 cap) |
narrows int64 file indptr → int32 (would truncate; masked by the throw at :95) | 28.7B | keep as std::vector<offset_t> |
nsparse/io/inline_forward_index_io.cpp:115 (PARTIAL) |
total_nnz += static_cast<uint64_t>(indptr[doc_id+1]-indptr[doc_id]) |
int32 subtraction | per-doc diff (~207, safe) but operands are wrapped int32 at whole-corpus scale | operands wrap | do the diff in offset_t |
nsparse/io/inline_forward_index_io.cpp:254-255 |
running += static_cast<uint64_t>(indptr[doc_id+1]-indptr[doc_id]) |
int32 subtraction | write_body per-doc diff; wrapped operands | operands wrap | diff in offset_t |
nsparse/io/inline_forward_index_io.cpp:271-273 / 286-288 |
const idx_t start=indptr[doc_id]; nnz=indptr[doc_id+1]-start |
int32_t start |
whole-corpus base offset into indices/values (static_cast<size_t>(start) at :292 too late) |
28.7B | offset_t start |
nsparse/io/inline_forward_index_io.cpp:275-277 / 290-293 |
indices+start / values+static_cast<size_t>(start)*element_size (write count args are safe size_t) |
int32_t start base |
wrong-region write base pointer | 28.7B | offset_t start |
2f. Plugin + JNI CSR writer
| file:line | symbol | current type | holds | reaches vs type-max | change |
|---|---|---|---|---|---|
CsrSparseVectorsFile.java:93 (PARTIAL) |
private int[] indptr = new int[1024]; |
int[] |
heap CSR offset array; element values would need 28.7B (guarded by :189 cap) | 28.7B | long[] indptr |
CsrSparseVectorsFile.java:189 |
if (nnz > Integer.MAX_VALUE) throw new IllegalStateException(...) |
long vs int |
hard cap — asserts at target (see §3) | 28.7B | remove/raise once offsets are 64-bit |
CsrSparseVectorsFile.java:195 (PARTIAL) |
indptr[++rows] = (int) nnz; |
(int) narrowing |
truncating cast (unreachable only because :189 throws first) | 28.7B | drop cast; indptr is long[] |
CsrSparseVectorsFile.java:237-239 |
for(...) csrOutput.writeInt(indptr[row]); |
on-disk int32 (writeInt) | on-disk indptr word (header nnz already writeLong) | 28.7B | writeLong; 8-byte on-disk indptr |
jni/src/common.h:39 |
std::vector<int32_t>* indicesVec; (the CSR indptr accumulator) |
std::vector<int32_t> |
whole-segment offset accumulator | 28.7B | std::vector<int64_t> |
jni/src/common.h:53 |
const int32_t offset = indicesVec->back(); |
int32_t |
running cumulative nnz | 28.7B | int64_t offset |
jni/src/common.h:55-57 |
for(int i=1;i<indicesLen;++i) indicesVec->push_back(indices[i]+offset); |
int32 add | offset accumulation (int32+int32, no promotion) | 28.7B | static_cast<int64_t>(indices[i])+offset |
jni/src/nsparse_wrapper.cpp:294-295 |
unique_ptr<vector<int32_t>> indptr(reinterpret_cast<vector<int32_t>*>(indicesAddress)); |
vector<int32_t> |
adopts the int32 offset vector | 28.7B | vector<int64_t> |
jni/src/nsparse_wrapper.cpp:318-320 |
add_with_ids(..., reinterpret_cast<const nsparse::idx_t*>(indptr->data()), ...) |
const int32_t* |
hands offsets to native (the ids cast is doc-scale, stays int32) |
28.7B | cast to const offset_t* |
§2f consistency note:
inverted_index.cpp:254is marked PARTIAL ("guarded byread_csr") while the identical constructbrutal_index.cpp:33is CONFIRMED (reachable via the JNIadd_with_idsroute, which has no nnz cap). Both areIndex::addoverrides reachable fromadd_with_ids; theread_csrcap only guards the file route. Either upgradeinverted_index.cpp:254to match, or document thatInvertedIndexis only ever built viaread_csrin the plugin. Both need the sameconst offset_t*change regardless.
3. Explicit hard caps that reject outright
These throw at the target scale and must be removed or re-targeted at INT64_MAX once offsets are 64-bit:
nsparse/index.cpp:95-99 (and the identical copy at nsparse/mmap_index.h:114-118) — the CSR-file load cap. nnz is read as int64_t from the header, so the compare is exact; 28.7B > INT32_MAX fires:
if (num_rows > std::numeric_limits<idx_t>::max() ||
nnz > std::numeric_limits<idx_t>::max()) {
throw std::invalid_argument(std::string("CSR file too large for ") +
"32-bit offsets: " + file_path);
}Keep the num_rows (doc-count) branch only if you retain a doc-id idx_t=int32 ceiling; drop the nnz branch.
nsparse/io/csr_layout.cpp:52-59 (the narrow<idx_t>() used at :113) — throws per-element:
if (source[i] < 0 || (uint64_t)source[i] > (uint64_t)std::numeric_limits<Narrow>::max())
throw std::invalid_argument(... "does not fit the native CSR width" ...);Once the narrow target is offset_t=int64_t, this becomes a no-op widening.
nsparse/io/inline_forward_index_io.cpp:119-122 — per-block cap. Confirmed present:
if (total_nnz > static_cast<uint64_t>(INT32_MAX)) {
throw std::length_error("InlineForwardIndex: block total nnz exceeds INT32_MAX");
}This one is per-block and legitimately protects the on-wire uint32_t off[] array (see §5). A single block is unlikely to exceed INT32_MAX nnz even at 138M docs, so this cap can stay — but re-examine it if block sizing changes. The docs.size() > UINT32_MAX cap at :102 is doc-count-scale and safe (138M < 4.29B).
CsrSparseVectorsFile.java:189-193 — the Java-side per-row cap, which is what actually blocks staging today (it throws at doc ~10.37M, mid-ingest):
if (nnz > Integer.MAX_VALUE) {
throw new IllegalStateException(
"sparse segment has " + nnz + " non-zeros, more than the native engine's 32-bit CSR offsets hold");
}Remove or re-target at Long.MAX_VALUE once indptr is long[] and the on-disk word is 8-byte.
4. Recommended change
Introduce a dedicated 64-bit offset type for nnz-offsets only. Do NOT widen doc-ids.
// types.h
using idx_t = int32_t; // doc-ids, labels, doc-COUNT — 138.36M fits (0.064× INT32_MAX). UNCHANGED.
using offset_t = int64_t; // CSR indptr / cumulative-nnz offsets — must hold 28.7B.Flip to offset_t (int64):
- Storage (1 array):
SparseVectors::indptr_→Buf<offset_t>;indptr_data()andSparseVectorsData.indptr_data→const offset_t*. - API params: the
indptrparameter onIndex::add,search,add_with_ids(index.h) and all overrides (brutal,inverted,id_map,seismic,seismic_scalar_quantized,disk_seismic_index_base). - Build accumulators:
sparse_vectors.cpp:118-121,141,150;jni/src/common.h:53,55-57. - Consumer offset vars & loop induction vars: every
idx_t start/end/next_start/nnz/jthat is= indptr[...]or iterates a CSR range — all sites in §2b/2c/2d/2e (~20 loops). Byte-offset multiplies likei * element_size/start * sizeof(T)are already promoted to 64-bit; they become correct automatically once the operand isoffset_t. - Serialization reads:
sparse_vectors.cpp:222,247,277;csr_layout.cpp:113(narrow<offset_t>);index.cpp:122(keep asstd::vector<offset_t>, no narrowing);mmap_deserializeread_array<offset_t>. - On-disk format (pre-GA, no back-compat): indptr word width 4→8 bytes in the native
.mcsrlayout (csr_layout), the SparseVectors serialize/mmap format, and the plugin.csrfile (CsrSparseVectorsFile.java:238writeInt→writeLong). Bumpformat_version. Headernnzis already 64-bit (writeLongat:236). - Java writer:
CsrSparseVectorsFile.java:93int[] indptr→long[] indptr(grow viaArrays.copyOf); drop the(int) nnzcast at:195; remove/raise the:189cap. - JNI adopt/cast:
jni/src/common.h:39std::vector<int64_t>;nsparse_wrapper.cpp:294-295std::vector<int64_t>;:318cast toconst offset_t*. Theidsreinterpret_cast at:318staysidx_t*(doc-scale).
Stays 32-bit (do NOT change):
- Doc-ids, doc counts,
n,numIds,n+1array lengths,id_mapvectors,set_id_map— all < INT32_MAX at 138M. - Per-block-local
off[](uint32) and its per-block cap (see §5). - Query-side indptr reads (
disk_seismic_index_base.cpp:146,177-178,360,377-379;inverted_index.cpp:326-327;brutal_index.cpp:53-54) — indexed over query vectors, tiny nnz. term_t=uint16_t(dimension ids),element_size/value_size(alreadysize_t),checked_mul(alreadysize_t),Bufcapacity (size_t),mmap_cursor::read_arraycount (size_t),align.hcounts (size_t).
Mechanical vs. needs-care:
- Mechanical: loop-var / local-offset retyping, param retyping (the compiler will chase most of it once
indptr_and the API params flip). - Needs care: (1) the on-disk format bump — every writer and every reader (serialize, mmap, native
.mcsr, plugin.csr) must agree on 8-byte indptr in lockstep; (2) the JNI/Java boundary —common.haccumulator,nsparse_wrappercast, and Javalong[]must all widen together or the reinterpret_cast silently mis-reads; (3) removing the caps in §3 must happen after the storage is widened, not before, or you convert an assert into a silent corruption; (4) confirm theinverted_index.cpp:254vsbrutal_index.cpp:33reachability question (§2f) so noadd_with_idspath is left on int32.
5. Open questions / risks
- Memory cost of the wider indptr.
indptr_hasnum_docs + 1entries. At 138.36M docs, 4→8 bytes doubles it from ~553 MB to ~1.11 GB of resident/mapped memory for the row-pointer array alone. This is per-segment and unavoidable if a single segment must hold the whole corpus; worth stating explicitly in capacity planning. (Theindices_/values_streams are unchanged — 28.7B × 2B and 28.7B × element_size.) - Per-block offsets that should stay 32-bit.
inline_forward_index_io.cppdeliberately keeps the on-wireoff[]asuint32_tand caps per-blocktotal_nnzat INT32_MAX (:116-122). These are per-block-local offsets and are correct as-is provided no single cluster block exceeds INT32_MAX nnz. If block sizing is ever allowed to grow past that, this becomes a real limit; verify the max block nnz at 138M scale. - Un-audited SIMD kernel family (latent, not a live blocker). The
nsparse/utils/distance_*.hheaders (distance.h:72-78, plusdistance_avx2.h,distance_avx512.h,distance_neon.h,distance_sve.h— 15dot_product_*_vectors_densefunctions total) contain the exactconst idx_t start=indptr[i]; end=indptr[i+1]corpus-offset pattern. Their only caller,detail::calculate_summary_scores(seismic_common.h:85), has no live callers (active scoring uses pre-filledscore_scratchviacompute_similarity), so they are effectively dead code today and would only see the cluster-summary set, not the corpus. They must be widened whenidx_t/offset_tis split, or they become a live overflow the instantcalculate_summary_scoresis wired to the corpus. Include them in the retype sweep to avoid a re-introduced landmine. - Signed vs unsigned offset_t.
int64_tis proposed (matches the on-diskint64file indptr and the existing monotonicity/narrowlogic).uint64_twould give 2× headroom but complicates theindptr[i] < indptr[i-1]monotonic check and thenarrow/sign handling.int64_tis more than sufficient (28.7B is 0.0000000031× INT64_MAX) and lower-risk; recommend keeping it signed.
Activity
zirui-song-18 commentedon Sep 15, 2026
Close now, as this issue is solved in #54