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>
* 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.
* 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>
* 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>
* 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.
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.
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.
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.
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.
* 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>
## 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.
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.
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.
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.