* Add ExpUnrolledLinkedList::iter_chunks
Adds an iterator over the chunks of an ExpUnrolledLinkedList, one slice
per block, in write order.
read_to_end now goes through ExpUnrolledLinkedListChunks::read_to_end,
which keeps the plain block loop instead of calling next() per chunk.
It also reserves the exact output length upfront, computed from the
block metadata.
* Export ExpUnrolledLinkedListChunks and make read_exact_into public
So callers can name the type returned by iter_chunks, and use
read_exact_into from outside the crate.
* Add the plain codec format to the columnar
Adds StrColumnCodec, the column key code of plain columns, the V3
columnar version, and the plain column storage: OnPair16 blocks of at
most 65,536 values and 1 MiB, block index, and reader.
The columnar writer does not produce plain columns yet.
* less result moar panic
* CR Comment. Making PlainColumn Inner type private
* CR comment: checked sorted index in block index.
`SnippetGenerator::set_max_num_chars` and `search_fragments` document the
limit as a number of chars (not bytes), but fragments were cut as soon as
their byte length went over it. For non-ASCII text, snippets were therefore
much shorter than requested: about half for Cyrillic or Greek, a third for
CJK.
Count the chars of the fragment instead. Since a char is at least one byte,
the chars only need counting once the byte length exceeds the limit, so ASCII
text does no extra work.
Co-authored-by: ybai08 <271969568+ybai08@users.noreply.github.com>
* Export PhraseScorer from tantivy::query
PhraseScorer already has a public constructor and the Postings trait is public, but the type was only reachable inside the crate. Exporting it lets a custom Query/Weight score a phrase over any Postings, for example a union of several terms at one position, without copying the phrase matching code.
Also documents the struct, the constructor and phrase_count.
* Document that PhraseScorer::new needs two postings
Intersection::new asserts at least two docsets, so a custom Weight whose phrase degenerates to one term must branch before building the scorer.
---------
Co-authored-by: KleiKodesh <211884665+KleiKodesh@users.noreply.github.com>
The metric reducers folded values one at a time through recurrences that
carry state across every iteration: Kahan compensated summation in
`collect_stats` (sum/avg/min/max/count/stats) and Welford's online variance
in `extended_stats`. These strict dependency chains block both CPU
pipelining and auto-vectorization.
`collect_stats` now reduces each block of values as a slice into 4
independent Kahan (sum, delta) lanes plus 4 min/max lanes, combined at the
end of the block.
`extended_stats` accumulates each block into 4 independent
`IntermediateExtendedStats` lanes and folds them into the bucket with the
existing `merge_fruits` (Chan parallel-variance combination), the same
operation used to merge segment results. The lanes carry the bucket's sigma,
since `merge_fruits` replaces an empty bucket with the incoming lane.
Blocks with fewer than two values per lane are collected value by value,
where setting up and combining lanes costs more than it saves.
Only the floating-point summation order changes, as it already does across
segment merges. All aggregation tests pass within the existing `2e-12`
tolerance, including the rounding-sensitive `test_aggregation_level1`, and a
new test covers sigma through the lane path.
The datetime hash map stores `ColumnWriter` values, but `sort_order`
read them as `NumericalColumnWriter`, a different and larger type.
`ArenaHashMap::get` reads raw bytes, so this read garbage and could read
past the end of the value. It is reachable through index sorting on a
date field.
Read a `ColumnWriter` and iterate its `NumericalValue` operations, as
`serialize` already does.
Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
`VecTermBuckets` and `LazyVecTermBuckets` used `get_unchecked_mut` on
the term id. The bucket vector is sized from the column's stored
`max_value`, which is read from disk and never checked against the
decoded values. A corrupt or crafted column could cause an
out-of-bounds write.
Use plain indexing instead. A corrupt column now panics, like
`PagedTermMap` already does.
agg_bench (terms without sub-aggregations, 4 index types, 2 rounds):
all differences vs main are within noise (-3.8% to +1.5%).
u32_to_i32_avx2, compact and compute_filter_bitset only use AVX2 intrinsics
on values, with no pointers. Since Rust 1.86, a #[target_feature] fn can be
safe, and calling it from a context with the same feature needs no unsafe
block. u32_to_i32_avx2 also gains its missing #[target_feature(enable = "avx2")].
The unsafe blocks in filter_vec_avx2_aux now only cover the pointer
load, store and offsets.
On 32-bit targets, the usize bound computation could wrap. The range check
then passed and the fast path read out of bounds. In u64, it cannot
overflow. On 64-bit targets, the generated code is the same.
Replace the `LAZY_BUCKET_ID_GENERATION` const bool on `VecTermBuckets`
with two focused types:
- `VecTermBuckets<B, const LANES: usize = 1>`: eager bucket-id assignment,
with `LANES` count lanes. `LANES == 1` is the former scalar-eager map;
`LANES == 8` (via the `VecTermBucketsWithLanes` alias) the lane map.
- `LazyVecTermBuckets<B>`: lazy bucket-id assignment on first occurrence,
single counter. Lazy only applies above
`LAZY_BUCKET_ID_GENERATION_THRESHOLD`, which never overlaps the very-low
cardinality lane regime, so it needs no lanes.
This removes the const bool and its awkward `LAZY && !B::ASSIGNS_ID`
edge case: each `term_entry` now does exactly one thing (eager rotates
across lanes; lazy assigns on first use), so both hot loops are simpler.
`VecTermBucketsWithLanes` is kept as a type alias
(`= VecTermBuckets<B, LANES>`) so the lane call site and the existing
lane unit test are unchanged. Dispatch in term_agg and multi_terms now
selects `LazyVecTermBuckets` for the lazy branch.
No behavior change: all term and multi-terms aggregation tests pass.
Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
add_page used to accept any length, leaving the page with a len larger than
its 1MB buffer. The module documentation already says that allocating more
than 1MB panics. The check is in add_page, which is off the hot path.
* Hardening unsafe in substring_count
* Remove unsafe in StrColumn::ord_to_str
ord_to_term may leave arbitrary bytes in the buffer when the term is not
found or on error, which left an invalid UTF-8 String behind.
The buffer is now only put back into the String after UTF-8 validation.
On not found or error, the output is left empty.
* Make CompactDoc::node_data crate private
extract_str relies on string values in node_data being valid UTF-8.
With a public field, safe code could break this invariant.
* Remove unsafe in Term::get_json_path
The public Term API (append_bytes, set_bytes, Term::wrap, serde, ...) can
put arbitrary bytes in the json path. Invalid UTF-8 sequences are now
replaced by U+FFFD.
* LZ4 doc store: never hand back a buffer with uninitialized bytes
compress/decompress now work on a local Vec while it contains
uninitialized bytes, and clear it on error. On error or panic, the
caller's buffer is left empty. Buffer reuse is preserved.
* Prepare ValueSource for computed text sources
- `ValueSource::term_dictionary()` lets a source resolve its own term
ords (`ValueSourceDictionary`, implemented by the sstable dictionary).
Terms and cardinality resolve ords through it; a registered name never
uses the physical dictionary of the same field.
- `ValueSourceProvider::for_segment` receives the column types the
aggregation accepts.
- composite and multi_terms reject registered sources explicitly.
* CR comment
* CR comment
* CR comment
---------
Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
* Faster lookups in sparse optional index blocks
- Branchless binary search in SparseBlock, using
std::hint::select_unpredictable. Indices are usize: with u16, LLVM
emits a branch on x86_64, even with the hint.
- SparseBlock::rank_if_exists_batch checks the next value first, then
uses an exponential search. The search is bounded by the doc id gap:
values are distinct and sorted, so vals[c + k] >= vals[c] + k.
- OptionalIndex::rank_if_exists_batch reserves its output vectors.
- MSRV 1.88, for select_unpredictable.
- Add a rank_if_exists_batch group to bench_optional_index, unit tests
and proptests.
* CR comments
---------
Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
`VersatileBuffer<A>` (tantivy-common) keeps an allocation and lends it
as an empty `Vec<T>`, for any `T` with the size and alignment of `A`.
The allocation goes back to the buffer when the guard is dropped,
including on panic. If the guard is leaked, the buffer starts again
from an empty `Vec`.
This makes it possible to reuse a buffer of values borrowing data with
a short lifetime, without self-referential structs.
The jitexpr predicate uses it for its argument slots. It replaces the
`ClearOnDrop` guard, which transmuted a `Vec<VariableValue<'static>>`
to a shorter lifetime.
Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
`Intersection::seek` used to build a `Vec<&mut dyn DocSet>` on every call
to reuse `go_to_first_doc`. It now shares the leapfrog loop of `advance`,
which uses `seek_danger` on the secondary docsets and does not allocate.
Added a proptest mixing `seek` and `advance` on a 3-way intersection.
* Add keyless streaming to the term dictionary streamers
The sstable streamer rebuilds the key of each entry it reads. It does
this also for the entries that the automaton rejects. Many callers do
not read the key. They only use term infos or term ordinals.
Add `without_keys()` to the streamer builders. The resulting streamer
does not rebuild keys. It gives term ordinals and values only.
- `KeyTracking` (in tantivy-common) is the buffer for the current key.
`Vec<u8>` keeps the key. `WithoutKeys` does nothing.
- The streamer types get a generic parameter `K = Vec<u8>`. Existing
type names keep the keyed behavior. `key()` and `next()` exist only
on the keyed streamer. The keyless streamer has `next_without_key()`.
- At the lower bound, the streamer does not know the previous key. It
uses the lower bound prefix that the comparator found as the
previous key. It then checks the upper bound on this prefix and the
suffix, with the new `DeltaKeyComparator::compare_prefix_and_suffix`.
- The FST streamer uses the same `KeyTracking`. Thus the
`TermDictionary` facade has `without_keys()` on both backends.
These callers now use `without_keys()`: AutomatonWeight,
InvertedIndexRangeWeight, the quickwit warmup paths and the terms
aggregation include/exclude regex.
* CR comment
---------
Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
Replace floating runner labels with the images they resolve to today
(`ubuntu-latest` -> `ubuntu-24.04`), so OS upgrades happen in an explicit
change instead of whenever GitHub moves a `-latest` label. GitHub moves
`ubuntu-latest` to Ubuntu 26.04 between Oct 19 and Nov 19, 2026.
* Make ValueSource::load_block take &mut self
Value sources were held as `Arc<dyn ValueSource>` and cloned into their
collector, so `load_block` could only take `&self`. A computed source
could not keep per-segment state (caches, scratch buffers) across blocks.
Collectors were built in two phases: `build_nodes` pushed each
`XxxAggReqData` into per-kind vectors of `AggregationsSegmentCtx`, and
each collector builder cloned its request data out of those vectors by
index. The ctx copy had to stay around for name lookups, memory
accounting, and for the collectors that read their data back by index.
Each request node is turned into exactly one collector, so nothing
actually shares a value source. This change makes that ownership
explicit:
- `ValueSource::load_block` takes `&mut self`,
`ValueSourceProvider::for_segment` returns `Box<dyn ValueSource>`.
- The request tree (`AggNode { data: AggNodeData, children }`) owns the
request data. Building collectors consumes the tree, moving the
request data into the collectors instead of cloning it.
- `AggregationsSegmentCtx` only keeps the shared collect-time state
(context and block accessor). `PerRequestAggSegCtx`, `AggKind`,
`idx_in_req_data` and the `push_*`/`get_*_req_data` helpers are gone.
- Cardinality, percentiles, top_hits and missing_term collectors own
their request data instead of reading it from the ctx by index.
- Histogram requests are normalized once, when building the tree. The
flattened terms x histogram path is split into a borrow-only plan step
and a consuming build step, and no longer clones the histogram request
at finalization.
- Request data memory is charged exactly once per node. Previously it
was charged at every nesting level, and range, histogram, filter and
composite builders charged their request data a second time.
- `FilterAggReqData::evaluator` no longer needs an `Rc`, and the
filter, composite and multi_terms request data no longer derive Clone.
* CR comment
* CR comment
---------
Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>