[FEATURE] Making a Single Segment Hold All of MS MARCO V2 (138.36M docs / 28.71B nnz)

[zirui-song-18]

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:254 is marked PARTIAL ("guarded by read_csr") while the identical construct brutal_index.cpp:33 is CONFIRMED (reachable via the JNI add_with_ids route, which has no nnz cap). Both are Index::add overrides reachable from add_with_ids; the read_csr cap only guards the file route. Either upgrade inverted_index.cpp:254 to match, or document that InvertedIndex is only ever built via read_csr in the plugin. Both need the same const 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() and SparseVectorsData.indptr_data → const offset_t*.
• API params: the indptr parameter on Index::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/j that is = indptr[...] or iterates a CSR range — all sites in §2b/2c/2d/2e (~20 loops). Byte-offset multiplies like i * element_size / start * sizeof(T) are already promoted to 64-bit; they become correct automatically once the operand is offset_t.
• Serialization reads: sparse_vectors.cpp:222,247,277; csr_layout.cpp:113 (narrow<offset_t>); index.cpp:122 (keep as std::vector<offset_t>, no narrowing); mmap_deserialize read_array<offset_t>.
• On-disk format (pre-GA, no back-compat): indptr word width 4→8 bytes in the native .mcsr layout (csr_layout), the SparseVectors serialize/mmap format, and the plugin .csr file (CsrSparseVectorsFile.java:238 writeInt→writeLong). Bump format_version. Header nnz is already 64-bit (writeLong at :236).
• Java writer: CsrSparseVectorsFile.java:93 int[] indptr → long[] indptr (grow via Arrays.copyOf); drop the (int) nnz cast at :195; remove/raise the :189 cap.
• JNI adopt/cast: jni/src/common.h:39 std::vector<int64_t>; nsparse_wrapper.cpp:294-295 std::vector<int64_t>; :318 cast to const offset_t*. The ids reinterpret_cast at :318 stays idx_t* (doc-scale).

Stays 32-bit (do NOT change):

• Doc-ids, doc counts, n, numIds, n+1 array lengths, id_map vectors, 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 (already size_t), checked_mul (already size_t), Buf capacity (size_t), mmap_cursor::read_array count (size_t), align.h counts (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.h accumulator, nsparse_wrapper cast, and Java long[] 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 the inverted_index.cpp:254 vs brutal_index.cpp:33 reachability question (§2f) so no add_with_ids path is left on int32.

5. Open questions / risks

• Memory cost of the wider indptr. indptr_ has num_docs + 1 entries. 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. (The indices_/values_ streams are unchanged — 28.7B × 2B and 28.7B × element_size.)
• Per-block offsets that should stay 32-bit. inline_forward_index_io.cpp deliberately keeps the on-wire off[] as uint32_t and caps per-block total_nnz at 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_*.h headers (distance.h:72-78, plus distance_avx2.h, distance_avx512.h, distance_neon.h, distance_sve.h — 15 dot_product_*_vectors_dense functions total) contain the exact const 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-filled score_scratch via compute_similarity), so they are effectively dead code today and would only see the cluster-summary set, not the corpus. They must be widened when idx_t/offset_t is split, or they become a live overflow the instant calculate_summary_scores is wired to the corpus. Include them in the retype sweep to avoid a re-introduced landmine.
• Signed vs unsigned offset_t. int64_t is proposed (matches the on-disk int64 file indptr and the existing monotonicity/narrow logic). uint64_t would give 2× headroom but complicates the indptr[i] < indptr[i-1] monotonic check and the narrow/sign handling. int64_t is more than sufficient (28.7B is 0.0000000031× INT64_MAX) and lower-risk; recommend keeping it signed.

[zirui-song-18]

Close now, as this issue is solved in #54