Commit Graph
2810 Commits
Author SHA1 Message Date
Pascal Seitz 333b0d4948 Inline short postings in SSTable term dictionaries 2026-10-27 08:56:57 +01:00
Pascal Seitz b9c4ed1c62 Rename encoded postings buffer to encoded terminfo 2026-10-23 17:11:03 +02:00
Pascal Seitz 85c15c83f8 Avoid rescanning terms during automaton bitset warmup 2026-10-23 17:11:03 +02:00
Pascal Seitz 9f2f1b2f6c Fix snippet panic with overlapping tokens 2026-10-22 15:10:02 +02:00
Adrien Guillo e1acb3e011 perf(aggregation): break serial Kahan/Welford chains with accumulator lanes (#3180)
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.
2026-10-15 10:20:13 -04:00
Paul Masurel 0f8f6c5a9f term_agg: use bounds-checked indexing in Vec term maps (#3182)
`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%).
2026-10-14 09:05: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 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 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 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 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
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
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
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
palmoni5 88a17da8e9 Expose the fragment byte range on Snippet (#3134)
Snippet only kept a copy of the fragment text, so callers that need to extend the fragment or map it back to the source (e.g. to keep punctuation that the tokenizer leaves outside the last token) had to search for it, which picks the wrong occurrence when the same text appears earlier.
2026-09-29 09:28:29 +02:00
palmoni5 1d294ea6dc Cache RegexPhraseQuery's compiled regexes in the query (#3137)
Following up on #3135, the regexes are compiled on first use and kept in the query, so a query reused across searchers, or cloned, determinizes each pattern once. RegexPhraseQuery::regexes exposes them for callers that inspect the patterns before searching, e.g. to count a phrase's per-segment expansions against max_expansions, instead of compiling them a second time.
2026-09-29 09:19:07 +02:00
Paul MasurelandPaul Masurel 047464cf92 Accelerating jitexpr conditions using necessary conditions (#3129)
* jitexpr

* Added possible necessary conditions to jitexpr.

A function makes it possible to infer a necessary query from an expression to match.
We can then accelerate queries involving a calculated field by not even evaluating the expression
on docs that trivially do not match.

* CR comment

* CR comment

* Fixing unit tests

---------

Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
2026-09-28 18:46:37 +02:00
palmoni5 b9125aad55 Compile RegexPhraseQuery regexes once per weight (#3135)
RegexPhraseWeight::phrase_scorer compiled every phrase term's regex again for each segment. Determinizing a wide pattern (e.g. an alternation of typo or morphology expansions) costs milliseconds to tens of milliseconds, so on a multi-segment index the query was dominated by recompiling the same automata. The regexes are now compiled in RegexPhraseQuery::regex_phrase_weight and shared through Arc.

An invalid pattern is now reported when the weight is built, instead of when the first segment is scored.
2026-09-28 11:37:50 +02:00
dayaffe 53e90ab192 Merge main into datasketches 0.5 update 2026-09-23 18:39:37 +00:00
Pascal Seitz e229de6db7 Collect decoded multi-term keys before assigning bucket positions 2026-09-22 19:53:52 +08:00
Pascal Seitz 7d3a3d6bfe Use unwrap_or(false) for missing bucket value check 2026-09-22 19:53:52 +08:00