Commit Graph
192 Commits
Author SHA1 Message Date
Paul Masurel 67889269ca Version bump and changelog for tantivy 0.27 (#3197) 2026-10-17 08:32:20 +02:00
Paul MasurelandPaul Masurel 7fea2ab8d8 columnar: read datetime columns with the right type in sort_order (#3185)
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>
2026-10-14 12:40:04 +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
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 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
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 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
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
Luca Cominardi a68b80ea94 Draw tie-breaker starts from the full u64 range 2026-10-01 16:25:38 +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
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
Pascal Seitz 21a6913217 Simplify bitpacked range decoding
Use scalar decoding for ranges overlapping the final partial load.
Clarify the 64-value aggregation block specialization and name the
generic decoding chunk size.

Apply nightly formatting to the touched benchmark and columnar code.
2026-09-23 20:21:08 +08:00
Pascal Seitz 4ede8d64f2 Optimize low-bit-width block decoding
Decode eight values per load for 64-value blocks and specialize bit
widths 1 through 7 to enable constant folding in the hot path.
2026-09-23 20:21:08 +08:00
Pascal Seitz 4a660f59d2 Faster columnar data fetching 2026-09-23 20:21:08 +08:00
Pascal Seitz bbc1b9e1d1 Restore TerminatingWrite API 2026-09-16 23:39:47 +08:00
Pascal Seitz 98d91f0436 Remove intermediate flush from directory contract
Intermediate writes are an implementation detail. From Tantivy side we only decide when a file is finished. This change is done to remove flush overhead for VecWriter. On finalization we just move the Vec to the directory.

Rename TerminatingWrite to FinishableWrite to reflect these semantics.
2026-09-16 23:39:47 +08:00
Pascal Seitz 4dddea5a5f Preserve tie breakers during columnar merges
Generate one random-offset linear tie-breaker sequence per segment and
preserve its values through normal columnar merging. Enable the linear
codec to keep initial segments compact.
2026-09-15 17:55:32 +02:00
Pascal Seitz a4cde3a22c Classify tie breakers during columnar merge
Represent generated tie breakers as a merge column category so existing
values are skipped and regenerated without being loaded. Test grouping,
block linearity, and compact merged output.
2026-09-15 09:45:58 +02:00
Pascal Seitz e7ba845037 add FieldType::TieBreaker 2026-09-14 19:18:22 +02:00
Pascal Seitz 46ee982b52 add tie_breaker option 2026-09-14 17:26:01 +02:00
Pascal Seitz a03870d41b Up to 500x Faster exists queries on columns (hehe)
Use specialized optional and multivalued column indexes for single-column
exists queries, while retaining a generic fallback for dynamic column unions.
Implement seek_danger with direct value checks to avoid unnecessary scans.

```
exists
column populated in 0.1% of docs (sparse blocks)
optional           Avg: 0.0406ms (-99.83%)    Median: 0.0395ms (-99.84%)    [0.0367ms .. 0.0496ms]    Output: 4_836
multivalued        Avg: 0.0432ms (-99.85%)    Median: 0.0424ms (-99.86%)    [0.0401ms .. 0.0503ms]    Output: 4_836
column populated in 10% of docs (dense blocks)
optional           Avg: 6.1052ms (-52.67%)    Median: 6.1089ms (-51.50%)    [5.9257ms .. 6.2702ms]    Output: 499_966
multivalued        Avg: 6.5485ms (-64.36%)    Median: 6.4573ms (-64.12%)    [6.3324ms .. 8.0991ms]    Output: 499_966
column populated in 90% of docs (dense blocks)
optional           Avg: 12.9950ms (+14.89%)    Median: 12.8676ms (+14.74%)    [12.6985ms .. 14.3235ms]    Output: 4_498_850
multivalued        Avg: 15.7813ms (-39.05%)    Median: 15.6722ms (-39.20%)    [15.5501ms .. 16.6724ms]    Output: 4_498_850
term_AND_exists
term matches 0.01% of docs, column populated in 0.1% (sparse blocks)
optional           Avg: 7381ns (-99.70%)    Median: 7030ns (-99.72%)    [6798ns .. 0.0144ms]    Output: 1
multivalued        Avg: 8435ns (-99.74%)    Median: 7372ns (-99.75%)    [7152ns .. 0.0313ms]    Output: 1
term matches 1% of docs, column populated in 0.1% (sparse blocks)
optional           Avg: 0.1047ms (-99.52%)    Median: 0.1045ms (-99.52%)    [0.1040ms .. 0.1072ms]    Output: 51
multivalued        Avg: 0.1070ms (-99.59%)    Median: 0.1069ms (-99.58%)    [0.1063ms .. 0.1097ms]    Output: 51
term matches 50% of docs, column populated in 0.1% (sparse blocks)
optional           Avg: 0.2970ms (-98.72%)    Median: 0.2839ms (-98.76%)    [0.2648ms .. 0.3446ms]    Output: 2_405
multivalued        Avg: 0.2952ms (-98.95%)    Median: 0.2923ms (-98.96%)    [0.2641ms .. 0.3283ms]    Output: 2_405
term matches 0.01% of docs, column populated in 10% (dense blocks)
optional           Avg: 0.0124ms (-48.17%)    Median: 0.0124ms (-47.62%)    [0.0120ms .. 0.0131ms]    Output: 50
multivalued        Avg: 0.0196ms (-46.61%)    Median: 0.0197ms (-46.21%)    [0.0184ms .. 0.0205ms]    Output: 50
term matches 1% of docs, column populated in 10% (dense blocks)
optional           Avg: 0.8094ms (-44.69%)    Median: 0.8021ms (-44.60%)    [0.7787ms .. 0.9247ms]    Output: 5_023
multivalued        Avg: 0.8439ms (-58.79%)    Median: 0.8325ms (-58.70%)    [0.8099ms .. 0.9976ms]    Output: 5_023
term matches 50% of docs, column populated in 10% (dense blocks)
optional           Avg: 12.3175ms (-32.65%)    Median: 12.3049ms (-32.54%)    [12.1053ms .. 12.8036ms]    Output: 249_853
multivalued        Avg: 12.7152ms (-46.31%)    Median: 12.6789ms (-46.23%)    [12.5517ms .. 13.0544ms]    Output: 249_853
term matches 0.01% of docs, column populated in 90% (dense blocks)
optional           Avg: 0.0627ms (+3.59%)    Median: 0.0640ms (+5.17%)    [0.0557ms .. 0.0680ms]    Output: 439
multivalued        Avg: 0.1168ms (+1.16%)    Median: 0.1173ms (+1.90%)    [0.1050ms .. 0.1226ms]    Output: 439
term matches 1% of docs, column populated in 90% (dense blocks)
optional           Avg: 0.5377ms (-0.19%)     Median: 0.5346ms (-0.26%)     [0.5308ms .. 0.5550ms]    Output: 45_342
multivalued        Avg: 0.6365ms (-31.29%)    Median: 0.6351ms (-30.75%)    [0.6245ms .. 0.6572ms]    Output: 45_342
term matches 50% of docs, column populated in 90% (dense blocks)
optional           Avg: 27.3888ms (-1.86%)     Median: 27.3356ms (-1.48%)     [27.1377ms .. 28.7410ms]    Output: 2_249_485
multivalued        Avg: 29.4214ms (-25.34%)    Median: 29.3960ms (-25.17%)    [29.2107ms .. 30.2541ms]    Output: 2_249_485
```
2026-09-02 14:14:45 +08:00
Paul MasurelandPaul Masurel 21ae09c0b4 Refactoring to introduce calculated fields. (#3066)
* Make aggregation column block accessor private

Move ColumnBlockAccessor out of tantivy-columnar and into the aggregation implementation. Keep its behavior and tests intact while removing it from the public columnar API.

* Refactor aggregation value block access

* Following comment

Removing Fused from the element that are private to the module.
Re-added optimization in stats for single doc requests to avoid perf regression
Renamed Fused -> Flattened

---------

Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
2026-09-01 15:10:19 +02:00
Paul MasurelandPaul Masurel fa904b3a72 Minor refactoring of find_missing_docs (#3049)
Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
2026-08-19 18:11:14 +02:00
Pascal Seitz 7373d54c2d fix clippy 2026-08-12 21:08:06 +08:00
Ming 0401b45781 feat: Extensible segment components via plugin trait (#2993)
## Motivation

Today every segment component — postings, fast fields, field norms, store — is hardcoded into several places. Adding a new per-segment data structure means forking Tantivy and editing each of those sites.

This PR introduces a `SegmentPlugin` trait that lets a custom component participate in the full segment lifecycle — write, serialize, merge, garbage collection, space usage — through the same interface the built-ins use, without touching Tantivy internals. The four built-in components are themselves reimplemented as plugins.

We (ParadeDB) plan on using this trait for 1) additional segment metadata for partitioning 2) custom vector index.

## Plugin Trait

Two traits. The first is the `SegmentPlugin` factory:

```rust
pub trait SegmentPlugin: Send + Sync + 'static {
    /// File extensions this component owns, e.g. ["idx", "pos", "term"] for postings.
    fn extensions(&self) -> &[&str];

    /// Create a writer for the indexing path.
    fn create_writer(&self, ctx: &PluginWriterContext) -> crate::Result<Box<dyn PluginWriter>>;

    /// Merge this component across several source segments into the target segment.
    fn merge(&self, ctx: PluginMergeContext) -> crate::Result<()>;

    /// Report on-disk space usage, keyed by component name. Has a default impl.
    fn space_usage(&self, reader: &SegmentReader)
        -> crate::Result<BTreeMap<String, ComponentSpaceUsage>>;
}
```

A `SegmentPlugin` owns one or more file extensions and knows how to (a) build a writer for the indexing path and (b) merge itself across segments.

The second trait is the segment writer:

```rust
pub trait PluginWriter: Send + Any {
    /// Called once per document, in doc-id order, for every plugin writer.
    fn add_document(&mut self, doc_id: DocId, doc: &TantivyDocument, schema: &Schema)
        -> crate::Result<()> { Ok(()) }

    /// Serialize accumulated data to segment files (honoring an optional doc-id remap).
    fn serialize(&mut self, segment: &Segment, doc_id_map: Option<&DocIdMapping>) -> crate::Result<()>;

    fn close(self: Box<Self>) -> crate::Result<()>;
    fn mem_usage(&self) -> usize;

    fn as_any(&self) -> &dyn Any;       // downcast support, Rust 1.86
    fn as_any_mut(&mut self) -> &mut dyn Any;
}
```

The write path no longer has any by-name wiring: `SegmentWriter` hands every document to every plugin writer's `add_document`, and `finalize()` calls `serialize` then close on each. 

## Key Design Decisions

1. The index — not the segment — owns the plugin set. The set of custom plugins is recorded once, at index creation, in `IndexMeta`. `#[serde(default)]` makes this backward compatible.

2. Plugins are registered, like tokenizers — and re-registration is enforced fail-closed. Plugins are not serialized; they're re-attached on every `Index::open` via `register_plugin`, exactly like custom tokenizers. To prevent consumers from accidentally forgetting to register a plugin, we validate the registered plugin set against the persisted set when the index is first used for a write/merge/GC operation.

3. Registration order is the write/merge order. Built-ins come first (field norms → postings → fast fields → store), then custom plugins.

4. The read side needs no plugin hook. Custom component data is read back through the existing public surface `SegmentReader::open_read`.

5. Backwards compatibility — behavior for existing indexes is unchanged.
2026-08-10 16:06:11 -07:00
Pascal Seitz e77c256f01 simpler missing algorithm 2026-08-04 13:23:19 +02:00
Pascal Seitz 1bfdf14415 restore TODO 2026-08-04 13:23:19 +02:00
Pascal Seitz 17de33d8f0 merge multi-terms code 2026-08-04 13:23:19 +02:00
Pascal Seitz 3010dbb8ea Optimize sparse multi-terms collection
Filter documents without values after each single-valued field so later
decoding and key construction only process viable documents. Use exact
block lengths to validate aligned results and keep unsupported missing-value
combinations on the general path.
2026-08-04 13:23:19 +02:00
Pascal Seitz 864a1d4b2d improve missing performance 2026-08-04 13:23:19 +02:00
Pascal Seitz 3e4cb34bfd add missing to benchmark 2026-08-04 13:23:19 +02:00
Pascal Seitz 95e8760050 columnar storage - add batched rank 2026-08-04 13:23:19 +02:00
Paul MasurelandPaul Masurel 3bb9a430dd Refactoring TextFastFieldOptions (#3020)
Co-authored-by: Paul Masurel <paul.masurel@datadoghq.com>
2026-08-02 17:17:02 +02:00
Pascal Seitz 7152d53182 clippy 2026-07-10 12:33:33 +02:00
trinity-1686a 02e34508e2 Merge pull request #2971 from quickwit-oss/trinity.pointard/fix-slop-overflow
fix overflow on large jumps in linear sequence
2026-06-23 10:18:29 +02:00
trinity-1686a 4031d97bac fix overflow on large jumps in linear sequence
new limit prevent an overflow in eval which caused the residual to be 64b when a slop of zero would give a smaller one
2026-06-23 00:13:27 +02:00
Ming 384f31d350 feat: Restore index sorting (#2959)
We ([ParadeDB](https://github.com/paradedb/paradedb)) have restored and been using the removed [index sorting](https://github.com/quickwit-oss/tantivy/issues/2352) feature in our Tantivy fork.

Our use case is sorting the index by Postgres' internal `ctid` identifier. Results returned from Tantivy must be checked against Postgres' visibility map, and checking them in ctid order is much more cache friendly, resulting in up to 80% speedups for certain queries.

This PR is split into 5 commits, corresponding to the index sorting reversal plus bug fixes we uncovered during our usage of index sorting.

| Commit | Maps to | What it does |
|---|---|---|
| `2aea0ad9f` | foundation ([#104](https://github.com/paradedb/tantivy/pull/104)) | Restore `SegmentComponent::TempStore` (revert of upstream #2815). Subsumes fork PR [#104](https://github.com/paradedb/tantivy/pull/104)'s CI fix. |
| `9205bcb0c` | [#92](https://github.com/paradedb/tantivy/pull/92) | Restore sort-by-field (single-segment + merge paths). |
| `39c790f0f` | [#101](https://github.com/paradedb/tantivy/pull/101) | Enable `sort_by` for `Str`/`Bytes` fast fields. |
| `9c4341a87` | [#105](https://github.com/paradedb/tantivy/pull/105) | Native typed numeric sort-key comparison (precision/NULL fix). |
| `2d9ba2418` | [#106](https://github.com/paradedb/tantivy/pull/106) | Preserve NULL ordering in numeric segment merges. |

We have discussed with the Tantivy maintainers and they indicated they would be open to this PR. Another motivation for landing this PR is we are planning on contributing a significant refactor that makes Tantivy's segment components extensible, and landing that without index sorting leads to too many conflicts.
2026-06-22 11:22:25 -07:00
Pascal Seitz ac7a3d347c add comment, hoist variables 2026-06-16 21:23:23 +08:00
Pascal Seitz 8f9846ac80 use get_range when possible 2026-06-16 21:23:23 +08:00
dependabot[bot] 4305e4029e Update binggan requirement from 0.16.1 to 0.17.0
Updates the requirements on [binggan](https://github.com/pseitz/binggan) to permit the latest version.
- [Changelog](https://github.com/PSeitz/binggan/blob/main/CHANGELOG.md)
- [Commits](https://github.com/pseitz/binggan/commits)

---
updated-dependencies:
- dependency-name: binggan
  dependency-version: 0.17.0
  dependency-type: direct:production
...

Signed-off-by: dependabot[bot] <support@github.com>
2026-05-12 15:10:20 +08:00
Paul Masurel 13d74c3c20 Update binggan requirement from 0.16.0 to 0.16.1 (#2899) 2026-04-20 11:59:47 +02:00
dependabot[bot] 058afff8b7 Update binggan requirement from 0.15.3 to 0.16.0
Updates the requirements on [binggan](https://github.com/pseitz/binggan) to permit the latest version.
- [Changelog](https://github.com/PSeitz/binggan/blob/main/CHANGELOG.md)
- [Commits](https://github.com/pseitz/binggan/commits)

---
updated-dependencies:
- dependency-name: binggan
  dependency-version: 0.16.0
  dependency-type: direct:production
...

Signed-off-by: dependabot[bot] <support@github.com>
2026-04-15 08:58:03 +02:00
Paul Masurel 04beab3b29 Performance improvement for nested cardinality aggregation
When a string cardinality aggregation is nested it end up being applied to different buckets.
Dictionary encoding relies on a different dictionaries for each segment.

As a result, during segment collection, we only collect term ordinals in a HashSet, and decode them in the
term dictionary at the end of collection.

Before this PR, this decoding phase was done once for each bucket, causing the same work to be done over and over. This PR introduce a coupon cache. The HLL sketch relies on a hash of the string values.

We populate the cache before bucket collection, and get our values from it.

This PR also rename "caching" "buffering" in aggregation (it was never caching), and does several cleanups.
2026-04-10 14:51:00 +02:00
Pascal Seitz 5c344db1bf chore: Release 2026-03-31 17:15:34 +08:00