Commit Graph
3829 Commits
Author SHA1 Message Date
Adrien GuilloandClaude Opus 4.8 a0a7ad549c perf(query): gallop sorted-array intersections in phrase scorer
The phrase scorer intersects sorted position lists with a linear
two-pointer merge (O(n+m)). When the two lists differ greatly in size
(e.g. a rare term and a frequent one in a phrase), this walks the long
list element by element to find a handful of matches.

Add a galloping (exponential + binary search) variant, shared via a
`gallop_find` helper, and route `intersection_count` / `intersection`
to it behind a size guard (`GALLOP_RATIO = 64`): gallop only when one
list is >=64x the other, otherwise keep the cache-friendly two-pointer.
This avoids the known galloping regression on balanced/dense inputs.

Equivalence with the linear reference is checked by a proptest over a
wide range of sizes (both small/large branches). Slop variants are left
on the two-pointer (range-match + best-match bookkeeping make galloping
correctness-risky, and slop>0 phrases are less common).

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
2026-10-14 16:10:25 -04:00
Adrien GuilloandClaude Opus 4.8 5eaa6c5fd7 chore(bench): fix stale rand import in fst_termdict bench
The `unstable` bench module used `rand::distributions::Alphanumeric`,
which moved to `rand::distr` in rand 0.9, breaking compilation of the
nightly benches. Required to run the benchmarks in the following commits.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
2026-10-13 16:46:41 -04:00
Paul Masurel 881fb3e02c filter_vec avx2: make target_feature helpers safe (#3178)
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.
2026-10-13 15:39:12 +02:00
Raphaël Cohen a32be82a9e fix: Fall back to string for dates that don't fit in i64 nanoseconds (#3156)
Signed-off-by: Darkheir <raphael.cohen@sekoia.io>
2026-10-13 15:32:18 +02:00
Paul Masurel c6dc5cb90e BitUnpacker::get_range: compute range bounds in u64 (#3177)
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.
2026-10-13 15:31:50 +02:00
Paul MasurelandPaul Masurel 59daaef723 Split term bucket maps into eager (lanes) and lazy variants (#3174)
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>
2026-10-13 15:31:02 +02:00
Paul Masurel 3ecca8151a MemoryArena: panic when allocating more than a page (#3176)
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.
2026-10-13 15:21:22 +02:00
Paul Masurel 6fc5a7d9b0 Unsafe hardening: fix unsound unsafe sites (#3175)
* 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.
2026-10-13 14:52:34 +02:00
Paul MasurelandPaul Masurel 9f9030a5fa Adding a Jitexpr ValueSource to allow jitexpr in aggregations. (#3162)
* Adding a jitexpr ValueSource

* CR comments

* Bugfix

---------

Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
2026-10-13 10:59:52 +02:00
Paul MasurelandPaul Masurel 0ae0df6b8c Rename ValueSource::as_column into as_physical_column (#3171)
Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
2026-10-12 11:08:16 +02:00
nadav-govari 6783439906 Oversized dictionaries return error (#3169)
* Oversized dictionaries return error

* Preexisting test fixes
2026-10-09 17:20:45 -04:00
Paul MasurelandPaul Masurel d6f0e2c320 Prepare ValueSource for computed text sources (#3160)
* 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>
2026-10-09 18:07:04 +02:00
Paul MasurelandPaul Masurel 17ddaa08c5 Better rank for sparse columns (#3159)
* 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>
2026-10-09 10:11:56 +02:00
Paul MasurelandPaul Masurel c12cc2d54b Add VersatileBuffer, a reusable allocation lent as a Vec (#3166)
`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>
2026-10-08 18:47:36 +02:00
Paul Masurel fc5770124e Fix clippy warnings (#3165)
* Fix clippy warnings
2026-10-08 18:23:57 +02:00
Paul Masurel c091be8597 Remove allocation in Intersection::seek (#3164)
`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.
2026-10-08 18:15:40 +02:00
Pascal Seitz 83a1faaca2 Preserve document ordering for nested aggregations 2026-10-08 17:48:01 +02:00
Pascal Seitz ef8e047db0 Return matching document bitset from automaton warmup 2026-10-08 17:21:43 +02:00
Pascal Seitz 4dfcac7628 Return matching term infos from automaton warmup 2026-10-08 17:21:43 +02:00
Paul MasurelandPaul Masurel e988ecb7a1 Add without_keys() to term dictionary streamers (#3155)
* 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>
2026-10-07 14:54:51 +02:00
Luca Cominardi 2e87c2eb0c fix: make fmt 2026-10-07 11:47:25 +02:00
Luca Cominardi 7daaa5dfec chore: tiebreaker cleanup 2026-10-07 11:47:25 +02:00
Luca Cominardi c3e40c63f7 chore: tiebreaker tests cleanup 2026-10-07 11:47:25 +02:00
Luca Cominardi 042a1b3ed8 Generate tie-breakers directly in i32 range 2026-10-07 11:47:25 +02:00
Luca Cominardi 224f16b60c Generate tie-breakers as i64 values 2026-10-07 11:47:25 +02:00
David Yaffe 1783018f9e Pin GitHub Actions runner images (#3153)
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.
2026-10-05 16:19:24 -04:00
Paul MasurelandPaul Masurel 45bbb16542 Refactoring to make ValueSource::load_block take &mut self (#3147)
* 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>
2026-10-05 15:13:44 +02:00
Pascal Seitz 3db020e707 Clarify write position when tracking multivalued documents 2026-10-05 14:21:30 +02:00
Pascal Seitz 98fba246db Extract per-document sorting for deduplication 2026-10-05 14:21:30 +02:00
Pascal Seitz f18eb5df53 Use shared value fetching entry point for bucket collectors 2026-10-05 14:21:30 +02:00
Pascal Seitz 36884928c5 Cache block multivalued state during collection 2026-10-05 14:21:30 +02:00
Pascal Seitz 045b210e3b Deduplicate multivalued documents within histogram buckets 2026-10-05 14:21:30 +02:00
Pascal Seitz 7122be03e6 Deduplicate multivalued documents within range buckets 2026-10-05 14:21:30 +02:00
Pascal Seitz 8e5f1cef03 Document aggregation collector call contracts 2026-10-05 14:21:30 +02:00
François Massot 4abc20f924 Merge pull request #3143 from quickwit-oss/mallets/tiebreaker
feat: add generated tie-breaker fast fields
2026-10-02 10:58:50 +02:00
PSeitz-dd dcd4d4b6d2 Merge pull request #3144 from PSeitz/export-seek-danger-result
Export SeekDangerResult for downstream DocSet implementations
2026-10-02 10:07:10 +02:00
Luca Cominardi ef0bed7ea3 Simplify tie-breaker start bound and doc comment 2026-10-02 09:18:57 +02:00
Luca Cominardi 547524adbe fix: keep tiebreaker values u32-compatible for now 2026-10-02 09:08:06 +02:00
Pascal Seitz d69d570c7d Export SeekDangerResult for downstream DocSet implementations 2026-10-01 18:27:07 +02:00
Luca Cominardi a68b80ea94 Draw tie-breaker starts from the full u64 range 2026-10-01 16:25:38 +02:00
Luca Cominardi af3ad76251 Reject tie-breaker fields as index sort fields 2026-10-01 14:30:35 +02:00
Luca Cominardi 6a6378fa1f feat: add generated tie-breaker fast fields 2026-10-01 14:24:04 +02:00
Luca Cominardi a102eed940 Merge remote-tracking branch 'origin/main' into mallets/seqnum-field 2026-10-01 11:40:33 +02:00
Paul MasurelandPaul Masurel 1f9e49da6b Abstracting columnar from aggregation. (#3112)
* Changing the way aggregation access their value.

They now get values via a ValueSource abstraction.
The aggregation collector also gets the possibility to
register ValueSourceProvider describing value columns that are computed
on the fly.

Finally, segment aggregation that require a full column
now manipulates a Arc<dyn ColumnValue> directly.

* CR comments

* Clippy

* Fixing regression

---------

Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
2026-09-30 19:12:20 +02:00
Walter Woodall d5e2842575 fix: stream positions during sorted segment merges (#3116)
Sorted segment merges copied every document's positions for a term into a vector before sorting by mapped document ID. Common terms with many positions therefore consumed memory proportional to documents × positions, outside the indexing writer budget.

Stream shuffled postings through a min-heap with one cursor per input segment and one reusable positions buffer. The mapping preserves each segment's document order; deleted/filtered postings are skipped. The stacked path continues to stream directly.
2026-09-29 16:55:20 -07:00
trinity-1686a 3b5ab82e20 Merge pull request #3126 from quickwit-oss/trinity.pointard/sstable-perf
improve Streamer::advance perf
2026-09-29 12:12:03 +02:00
trinity-1686a 171340677f address cr 2026-09-29 12:04:38 +02:00
palmoni5 637803de99 Add RegexPhraseQuery::from_regexes (#3138)
RegexQuery can be built from a compiled Regex, but RegexPhraseQuery always compiled its patterns with Regex::new and its default DFA state limit. from_regexes takes the compiled regexes directly, so a caller can build them with its own limits, or reuse ones it already compiled.
2026-09-29 11:45:00 +02:00
palmoni5 9e1b0de23a Expose the Levenshtein automaton of FuzzyTermQuery (#3136)
* Expose the Levenshtein automaton of FuzzyTermQuery

Callers that need the terms a fuzzy query expands to (e.g. to highlight them) had to copy the private DfaWrapper and depend on the same levenshtein_automata version as tantivy, or their expansion could silently diverge from the query's. FuzzyTermQuery::automaton returns the automaton the query matches with, built from the same cached LevenshteinAutomatonBuilder.

* Export DfaWrapper outside of tests

The re-export was still behind #[cfg(test)], so FuzzyTermQuery::automaton returned a type other crates could not name. A doctest now uses it from outside the crate.
2026-09-29 09:50:24 +02:00
omerb-vega 93280f56fb Map multivalued doc ranks to doc ids with a select cursor (#3133)
* columnar: bench row id to doc id conversion on multivalued columns

* columnar: map multivalued doc ranks to doc ids with a select cursor

MultiValueIndexV2::select_batch_in_place ended with one
OptionalIndex::select call per matched doc, each locating its block from
scratch. The ranks are sorted and deduplicated at that point, so
OptionalIndex::select_batch converts them in one sequential pass with a
select cursor.

Every Column::get_docids_for_value_range call on a multivalued column goes
through here, e.g. fast field range queries.
2026-09-29 09:31:00 +02:00