---
title: "vectra Engine Reference"
author: "Gilles Colling"
date: "`r Sys.Date()`"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{vectra Engine Reference}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r, include = FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)
```

This document defines vectra's public contract: which operations are supported,
how types and coercion work, what streams and what materializes, and where
guarantees stop. It is the reference for what vectra promises.

See `?tbl`, `?filter`, `?left_join`, and `?explain` for function-level
documentation.

## What vectra is

vectra is an R-native columnar query engine for datasets that don't fit in
memory. It provides dplyr-style verbs backed by a pure C11 pull-based execution
engine and a custom on-disk format (`.vtr`). All operations are lazy until
`collect()` materializes results as an R data.frame.

vectra is not a dplyr backend plugin. It defines its own S3 generics. The verbs
share names and semantics with dplyr, but do not depend on it.

## Execution model

### Pull-based pipeline

Every verb (`filter`, `select`, `mutate`, ...) builds a plan node. Nodes form a
tree. No data moves until `collect()` calls the root node's `next_batch()`
function, which pulls data through the tree one **row group** at a time.

A row group (internally: `VecBatch`) is a set of columnar arrays, typically
thousands to millions of rows. Each column is a typed array with a validity
bitmap for NA support.

```r
# Nothing executes here --- just builds a plan tree
plan <- tbl("data.vtr") |>
  filter(x > 0) |>
  select(id, x, y) |>
  mutate(z = x + y)

# Data flows when you call collect()
result <- collect(plan)

# Or inspect the plan without executing it
explain(plan)
```

### Selection vectors (zero-copy filtering)

`filter()` does not copy rows. It attaches a **selection vector** to the batch:
an integer array indexing which physical rows pass the predicate. Downstream
nodes read only the selected rows. This avoids memory allocation and copying for
selective filters.

### Columnar storage

Data is stored and processed column-by-column, not row-by-row. This means
operations that touch few columns (e.g. `select(id, x)` on a 100-column table)
only read the columns they need from disk.

## Data sources

| Function | Format | Streaming |
|:---------|:-------|:----------|
| `tbl(path)` | `.vtr` (vectra native) | yes, row-group-at-a-time |
| `tbl_csv(path)` | CSV | yes, batch-at-a-time |
| `tbl_parquet(path)` | Parquet (one file, several, or a directory) | yes, row-group-at-a-time |
| `tbl_sqlite(path, table)` | SQLite | yes, batch-at-a-time |
| `tbl_tiff(path)` | GeoTIFF | yes, row-strip-at-a-time |
| `tbl_fasta(path)`, `tbl_fastq(path)` | FASTA / FASTQ (plain or gzipped) | yes, batch-at-a-time |
| `tbl_bed(path)` | BED | yes, batch-at-a-time |
| `tbl_xlsx(path)` | Excel `.xlsx` | no, the sheet is read into memory via openxlsx2 |

All sources produce the same `vectra_node` object. The query engine does not
know or care which source is upstream.

### Output sinks

| Function | Format | Streaming |
|:---------|:-------|:----------|
| `collect()` | R data.frame | materializes full result in R memory |
| `write_vtr(df, path)` | `.vtr` | writes from data.frame |
| `write_csv(x, path)` | CSV | streams batch-by-batch |
| `write_sqlite(x, path, table)` | SQLite | streams batch-by-batch |
| `write_tiff(x, path, pixel_type)` | GeoTIFF | streams batch-by-batch; `pixel_type`: float64/float32/int16/int32/uint8/uint16 |

## Supported verbs

### Transformation verbs

| Verb | Streams | Notes |
|:-----|:--------|:------|
| `filter(...)` | yes | Zero-copy via selection vector |
| `select(...)` | yes | Full tidyselect: `starts_with()`, `where()`, `-col`, etc. |
| `mutate(...)` | yes | Arithmetic, comparison, boolean, `is.na()`, `nchar()`, `substr()`, `grepl()`, math (`abs`, `sqrt`, `log`, `exp`, `log1p`, `expm1`, `floor`, `ceiling`, `round`, `log2`, `log10`, `sign`, `trunc`, `^`), trigonometric and hyperbolic functions (`sin`, `cos`, `tan`, `asin`, `acos`, `atan`, `atan2`, `sinh`, `cosh`, `tanh`, `asinh`, `acosh`, `atanh`), the constant `pi`, `if_else()`, `between()`, `%in%`, type casting (`as.numeric`), `tolower()`, `toupper()`, `trimws()`, `paste0()`, `gsub()`, `sub()`, `startsWith()`, `endsWith()`, `pmin()`, `pmax()`, `year()`, `month()`, `day()`, `hour()`, `minute()`, `second()`, `as.Date()` |
| `transmute(...)` | yes | Like `mutate()` but drops unmentioned columns |
| `rename(...)` | yes | Full tidyselect rename support |
| `relocate(...)` | yes | Reorder columns with `.before` / `.after` |

### Aggregation verbs

| Verb | Streams | Notes |
|:-----|:--------|:------|
| `group_by(...)` | metadata only | Attaches grouping info; no data moves |
| `summarise(...)` | **materializes** | Hash aggregation; spills to disk when the groups outgrow the memory budget |
| `ungroup()` | metadata only | Removes grouping |
| `count(...)` | **materializes** | Sugar for `group_by() |> summarise(n = n())` |
| `tally(...)` | **materializes** | Like `count()` on existing groups |

Supported aggregation functions: `n()`, `sum()`, `mean()`, `min()`, `max()`, `sd()`, `var()`, `first()`, `last()`, `any()`, `all()`, `median()`, `n_distinct()`.
All accept `na.rm = TRUE`.

### Ordering verbs

| Verb | Streams | Notes |
|:-----|:--------|:------|
| `arrange(...)` | **materializes** | External merge sort; spills sorted runs past the memory budget |
| `slice_head(n)` | yes | Limit node, stops after n rows |
| `slice_tail(n)` | **materializes** | Must see all rows to take last n |
| `slice_min(order_by, n)` | partial | Heap-based top-N; `with_ties = TRUE` (default) includes ties |
| `slice_max(order_by, n)` | partial | Heap-based top-N; `with_ties = TRUE` (default) includes ties |
| `head(n)` | yes | Alias for `slice_head() |> collect()` |
| `slice(...)` | **materializes** | Select or exclude rows by position (positive or negative indices) |
| `distinct(...)` | **materializes** | Grouped aggregation with no aggregates, so the same hash path and spill |

### Join verbs

| Verb | Streams | Notes |
|:-----|:--------|:------|
| `inner_join(x, y)` | **build side buffered** | Hash join; left streams, right is the build side and spills past the budget |
| `left_join(x, y)` | **build side buffered** | Hash join; left streams |
| `right_join(x, y)` | **build side buffered** | Implemented as swapped left join |
| `full_join(x, y)` | **build side buffered** | Hash join + finalize pass |
| `semi_join(x, y)` | **build side buffered** | Hash join; returns left rows only |
| `anti_join(x, y)` | **build side buffered** | Hash join; returns non-matching left rows |
| `cross_join(x, y)` | **materializes** | Cartesian product; no key columns required |

All joins support: `by = "col"`, `by = c("a" = "b")`, `by = NULL` (natural
join), and `suffix = c(".x", ".y")`.

### Window functions

Available inside `mutate()`:

| Function | Description |
|:---------|:------------|
| `row_number()` | Sequential row number (respects groups) |
| `rank(col)` | Min rank with gaps for ties (like `dplyr::min_rank()`) |
| `dense_rank(col)` | Consecutive rank without gaps |
| `lag(col, n, default)` | Previous value |
| `lead(col, n, default)` | Next value |
| `cumsum(col)` | Cumulative sum |
| `cummean(col)` | Cumulative mean |
| `cummin(col)` | Cumulative minimum |
| `cummax(col)` | Cumulative maximum |
| `ntile(n)` | Divide rows into n roughly equal buckets |
| `percent_rank(col)` | Relative rank scaled to [0, 1] |
| `cume_dist(col)` | Cumulative distribution (proportion of values <= current) |

Window functions respect `group_by()` partitions. A grouped window sorts its
input by the group keys through the external sort and then processes one group
at a time, so its peak is the largest group. An ungrouped window streams the
table in one forward pass; when its functions need different orderings (for
example `lag()` next to `rank()`), it runs as a chain of single-function windows,
each of which streams.

### Other verbs

| Verb | Streams | Notes |
|:-----|:--------|:------|
| `pull(var)` | **materializes** | Collects one column as a vector |
| `bind_rows(...)` | yes | Streaming concat if schemas are compatible |
| `bind_cols(...)` | **materializes** | Collects all inputs, then `cbind()` |
| `across(...)` | n/a | Column expansion helper for `mutate()`/`summarise()` |
| `explain()` | n/a | Prints the plan tree |
| `glimpse()` | **materializes** (preview only) | Shows column types and first few values |

### tidyselect support

`select()`, `rename()`, `relocate()`, `distinct()`, and `across(.cols)` support
the full tidyselect vocabulary:

- `starts_with()`, `ends_with()`, `contains()`, `matches()`

- `everything()`, `last_col()`

- `all_of()`, `any_of()`

- `where()` predicates (e.g. `where(is.numeric)`)

- `-column` negation

`where()` works because vectra builds a 0-row typed proxy data.frame from the
schema, giving tidyselect enough type information to evaluate predicates.

### Programming with verbs

Every verb that takes expressions (`filter()`, `mutate()`, `transmute()`,
`summarise()`, `arrange()`, `group_by()`, `count()`, `pull()`, `slice_min()`,
`slice_max()`, and the others) captures its arguments with rlang, so the usual
injection tools work:

- `!!` and `!!!` inject a value, a symbol or a list of them
  (`group_by(!!sym(k))`, `summarise(!!!aggs)`)
- `{{ }}` forwards an argument from a wrapper function
- `!!name := expr` builds a column name
- `.data[[k]]` and `.data$k` refer to a column by name, `.env$x` to a variable
  in the calling environment

```r
k <- "species"
tbl("data.vtr") |> group_by(.data[[k]]) |> summarise(n = n())
```

## Supported types

### Base types

| C type | R input | R output (default) | R output (bit64 mode) |
|:-------|:--------|:-------------------|:----------------------|
| `int64` | integer | double | integer64 |
| `double` | double | double | double |
| `bool` | logical | logical | logical |
| `string` | character | character | character |

R's 32-bit `integer` is widened to 64-bit `int64` on write. On read, `int64` is
returned as `double` by default (R has no native 64-bit integer). Set
`options(vectra.int64 = "bit64")` to get `bit64::integer64` output instead.

### Annotated types

The `.vtr` schema stores a per-column annotation that preserves R type metadata
through the write/read cycle:

| R class | Annotation | Storage | Roundtrip |
|:--------|:-----------|:--------|:----------|
| Date | `"Date"` | double (days since epoch) | exact |
| POSIXct | `"POSIXct\|tz"` | double (seconds since epoch) | exact (tz preserved) |
| factor | `"factor\|lev1\|lev2\|..."` | string | exact (levels + order preserved) |

Annotations are metadata. The underlying C engine operates on the base types
only. Type restoration happens at `collect()` time.

Date and POSIXct columns support component extraction via `year()`, `month()`,
`day()`, `hour()`, `minute()`, `second()` in `mutate()` and `filter()`
expressions. Use `as.Date("2020-01-01")` as a literal in filter comparisons.
Date arithmetic (adding/subtracting days) works via standard `+` and `-`.

## Coercion rules

### Arithmetic and comparison expressions

The coercion hierarchy for numeric operations is:

```
bool < int64 < double
```

When an expression combines two different numeric types, the narrower type is
promoted to the wider type before evaluation. String columns cannot participate
in arithmetic or comparison with numeric columns; this is an error.

### Join key coercion

Join keys follow the same hierarchy. If the left key is `int64` and the right
key is `double`, the `int64` side is coerced to `double` for hashing and
comparison. The coercion happens internally; the output column retains the
original left-side type.

Joining a `string` key against a numeric key is an error.

### bind_rows coercion

When `bind_rows()` combines tables with different column types, it computes the
common type using the same `bool < int64 < double` hierarchy. Per-batch
coercion happens at the C level during streaming --- no R fallback needed.

If column names differ across inputs, the R fallback path is used: all inputs
are collected, aligned by column name, and combined with `rbind()`.

## NA semantics

### Storage

NAs are tracked by a per-column validity bitmap. Every column of every type
supports NA values. The bitmap is bit-packed (1 bit per row, 1 = valid).

### Propagation

- **Arithmetic**: `NA + x = NA`, `NA * x = NA`

- **Comparison**: `NA > x = NA`, `x == NA = NA`

- **Boolean**: `NA & FALSE = FALSE`, `NA & TRUE = NA`, `NA | TRUE = TRUE`, `NA | FALSE = NA`

- **Aggregation**: NAs are included by default; use `na.rm = TRUE` to exclude

- **Joins**: NA keys never match (same as SQL NULL semantics)

- **Window functions**: `cumsum()` and friends propagate NA forward

### is.na()

`is.na(col)` is supported in `filter()` and `mutate()` expressions. It returns
a boolean column based on the validity bitmap.

## Ordering guarantees

- `filter()`, `select()`, `mutate()`, `rename()`, `relocate()`: preserve input
  order
- `arrange()`: produces a total order (stable sort)

- `group_by() |> summarise()`: groups come out sorted by key, with `NA` keys
  last, whether or not the aggregation spilled
- `distinct()`: sorted by the distinct columns, `NA` last (it runs through the
  same aggregation)

- Joins: probe-side order is preserved within each batch; build-side order is
  not guaranteed
- `bind_rows()`: child order is preserved (first child's rows, then second's,
  etc.)

## Streaming vs materializing

### Streaming nodes (constant memory per batch)

- Scans (`.vtr`, Parquet, CSV, SQLite, TIFF, FASTA/FASTQ, BED)

- Filter

- Project (select / mutate / rename / relocate / transmute)

- Limit (slice_head, head)

- Concat (bind_rows)

- Ungrouped windows (see Window functions above)

### Materializing nodes

These nodes buffer data. Every one of them is bounded: it either holds a fixed
amount of state or spills to temporary files once its buffer reaches the memory
budget.

| Node | What it buffers | Bounded by |
|:-----|:----------------|:-----------|
| Sort (arrange) | Input rows | Memory budget, then sorted runs on disk |
| GroupAgg (summarise, distinct, count) | Hash tables of groups + accumulators | Memory budget, then hash partitions on disk |
| TopN (slice_min/max, `with_ties = FALSE`) | Heap of n rows | Requested n |
| Window, grouped | One group at a time, after the external sort | Largest group |
| Join (build side) | Right-side rows + hash table | Memory budget, then hash partitions on disk |

The memory budget is `vectra_mem()`, which defaults to half of physical RAM
(at least 1 GB) and is set with `options(vectra.memory = "4GB")`. It bounds the
whole query, not each node. Before execution the optimizer creates one pool of
`vectra_mem()` bytes for the plan and gives every buffering step (sort, join,
grouped aggregate, fuzzy join, k-mer count) a claim on it. A step reserves the
bytes it actually allocates as its buffers grow, releases them as it frees
them, and spills to disk when the pool refuses a reservation. A step that needs
little leaves the rest of the pool to the others. So that no step can be
starved, each is guaranteed a floor of 1/(4 x number of buffering steps) of the
budget; the other three quarters are shared, first come first served. The nodes
a step creates internally, such as a grouped aggregate's sorts or a grace-hash
join's sub-joins, draw on that step's claim.

Spill files (sort runs, join and aggregation partitions, fuzzy-join build runs,
and the temporary file `diff_vtr()` collects added rows in) are written
uncompressed, since each is written once and read once. They go to `tempdir()`
and are deleted when the node that wrote them is freed.

### External sort (spill-to-disk)

`arrange()` accumulates incoming batches into column builders. Before taking a
batch it reserves what the builders will hold after growing, plus 32 bytes per
buffered row for the sort's working space (the row permutation and the radix
sort's scratch). When the reservation is refused, the node sorts what it holds
and writes it to a temporary `.vtr` file as one sorted run, in row groups of
65,536 rows, then resets the builders and continues. Sorting in memory orders a
row-index permutation: a radix sort for a single numeric key, otherwise a
parallel merge sort (OpenMP tasks above 32,768 rows).

Once the input is consumed, the node merges the runs with a min-heap. The
number of runs merged at once (the fan-in) is capped: it is computed from the
measured width of the spilled rows so that the rows held by an open merge stay
within half the budget, and lies between 2 and 64. When there are more runs than
the fan-in, groups of runs are first merged into fewer, longer runs, in as many
passes as needed, before the final merge streams the result in batches of
65,536 rows. Merge memory therefore depends on the row width and the budget,
not on the number of rows sorted.

If the input fits within the budget, nothing is written to disk and the sort
runs in memory. It then keeps only the buffered columns and the permutation,
and emits the result in batches of 131,072 rows, gathering each batch's
fixed-width columns in one parallel pass.

### Grouped aggregation

`summarise()` of the scalar aggregates (`n()`, `sum()`, `mean()`, `min()`,
`max()`, `sd()`, `var()`, `first()`, `last()`, `any()`, `all()`) aggregates in
hash tables. The key space is split by hash into up to 64 shards, one hash table
per shard, and the shards run in parallel; a group lives in exactly one shard,
so nothing has to be merged afterwards. Hashing is FNV-1a on the key bytes,
multi-key hashes are combined by rotating and XOR-ing the per-key hashes.

When the tables reach their share of the budget they stop admitting new groups.
Rows of groups already held keep aggregating in place; rows of any other group
are written, by a salted hash of the key, to one of 64 temporary partition
files. Each partition is then aggregated on its own with a differently salted
hash, recursively, and a partition still too large after three levels takes the
sort-based path. Every group is either wholly in memory or wholly in one
partition, so no partial result is ever combined with another.

`median()` and `n_distinct()` need every value of a group. With either of them
in the `summarise()`, the input is sorted by the group keys through the external
sort and the groups are aggregated one at a time; each group's values go to a
buffer that spills to disk and is reduced by an external merge, so a single very
large group costs disk rather than memory.

Groups are emitted sorted by key, `NA` last. When nothing spilled, the result
table is sorted in memory; otherwise it passes through the external sort.

### Join memory model

Joins use a **build-right, probe-left** hash join:

1. **Build phase**: The right side is read into memory and indexed by a hash
   table. Key columns are hashed with FNV-1a; multi-key hashes are combined per
   key. Build-side hashing is OpenMP-parallelized above 32,768 rows.
2. **Probe phase**: Left-side batches stream through one at a time. For each
   left row the engine computes the key hash, looks up the table, and checks key
   equality, so hash collisions never produce a false match. Probe-side hashing
   is also parallelized.
3. **Finalize phase** (full join): unmatched right-side rows are emitted from a
   matched-row bitset.

When the build side outgrows the memory budget, the join switches to a grace
hash join: both sides are written by key hash into 64 partition files and the
partitions are joined one at a time. A partition that is itself still too large
is partitioned again with a hash salted by the recursion depth, so keys that
collided at one level split at the next. A single key value repeated more times
than fits in memory cannot be split by any hash; after three levels such a
partition is joined by a block nested loop, reading the build side in blocks
that fit the budget and rescanning the probe side once per block. At that level
the join holds one build block, one probe batch, and bitsets of one bit per
row.

When both inputs are already sorted on the join keys, the join merges them
instead of building a hash table. Which of the two it uses is decided before
the build, because it sets what the build reserves: a hash join reserves the
build columns plus the slot arrays (16 bytes per slot, with the slot count the
next power of two at or above twice the build rows), a chain array and a
temporary hash array (8 bytes per build row each), and for a full join a
one-bit-per-row matched bitset. A merge join reserves only the columns and the
bitset. The grace-hash partitions and block-nested-loop blocks check the same
figure.

The left side streams and does not accumulate, so put the smaller table on the
right. `right_join()` does this by swapping the sides internally and remapping
the output columns.

## The .vtr file format

The `.vtr` format is vectra's native binary columnar format, built on the tdc
container (typed dimensional compression, vendored in `src/tdc/`).

### Layout

```
tdc container:
  header (64 bytes): "TDC1" magic, flags, section offsets
  schema: per-column name, type and annotation
  blocks: one self-describing block record per column per row group
  row-group index: block offsets and sizes, plus per-column
                   min / max / null count for every row group
vectra trailer (24 bytes):
  container length (u64), digest of the container bytes (u64),
  trailer version (u32), "VTRD"
```

Each column of each row group is one block record: a header naming how the
block was encoded, the encoded payload, and the column's validity bitmap. The
reader decodes each block from its own header, so files written with different
compression settings are read the same way.

The trailer records a digest of every byte written. `create_index()` stamps its
sidecar with a fingerprint built from it, which is how an index notices that
its store was replaced (see Hash indexes). A reader that does not know the
trailer ignores it, since tdc never reads past the row-group index.

`append_vtr()` grows a store in place in either direction: new row groups
(`along = "rows"`) or new columns (`along = "cols"`) are written after the old
index together with a rebuilt index, and the header is patched last, so an
interrupted append leaves the previous store readable.

The format is not compatible with `.vtr` files written before the tdc container
was adopted.

### Encoding and compression

`write_vtr(compress = )` picks the encoding per column chunk:

- `"fast"` (default): numeric columns are byte-shuffled (the bytes of each
  value are regrouped by position, which exposes the redundancy in exponent and
  high-order bytes) and compressed with LZ; a non-decreasing integer column is
  delta-encoded first. String columns are dictionary-encoded: the distinct
  values once, then an index per row. The LZ runs at tdc's fastest matching
  level.
- `"small"`: for each column chunk, tries a set of candidate encodings and
  keeps the smallest. Candidates vary the model (raw, delta, second-order delta,
  floating-point prediction, numeric dictionary, sparse-zero) and the entropy
  coder (LZ at several parser levels, FSE, Huffman, per-lane coding), and always
  include the `"fast"` encoding, so `"small"` is never larger than `"fast"`. The
  trial encodes run in parallel, and the choice does not depend on the thread
  count.
- `"none"`: no compression; strings are still stored as a dictionary.

Columns written with `write_vtr(quantize = )` or `write_vtr(spatial = )` use
tdc's quantizing and 2-D predictive models instead.

Because string columns are dictionary-encoded, `collect()` converts each
distinct string to an R string once and fills the column by index.

## Query optimizer

`explain()` runs the optimizer before printing so you see the actual execution
plan. The optimizer rewrites the plan so the order in which the verbs were
written does not change how much is read.

### Predicate pushdown

A filter stays where it was written and still checks every row. In addition,
the optimizer hands a copy of its predicate down to every scan it can reach,
where the copy is used only to skip row groups. The copy passes through
`mutate()`, `select()`, `rename()` (following renamed columns), other filters,
`arrange()`, and into every input of `bind_rows()` whose column types match.
A condition on a column computed or overwritten by a `mutate()` is dropped
from the copy, which is safe because the filter above still evaluates it. The
copy never passes a limit, top-n, window, aggregate or join, since removing rows
before those would change the result.

A `.vtr` scan applies up to three pruning strategies on its first batch:

1. **Hash index pushdown** (highest priority). If a `.vtri` sidecar index
   exists for the predicate column(s), the scan probes the index to build a
   row-group bitmap. Row groups not in the bitmap are skipped entirely. This
   handles `==` and `%in%` predicates. For composite indexes, AND-combined
   equality predicates on the indexed columns are matched and probed as a
   single composite key. See the Hash indexes section below for details.

2. **Binary search on sorted columns**. If a column's values are sorted across
   row groups and the predicate is a simple comparison (`==`, `<`, `<=`, `>`,
   `>=`) against a literal, the scan binary-searches the row-group statistics
   for the first and last row groups that could contain matching rows. For
   AND-combined predicates on the same sorted column (e.g.
   `x >= 10 & x < 100`), both bounds are applied. For OR-combined predicates,
   the union of both ranges is used.

3. **Zone-map pruning** (per row group). Each row group stores per-column
   min/max and null counts. Before reading a row group, the scan evaluates the
   predicate against these statistics and skips the row group when no row can
   match (e.g. `filter(x > 100)` where the row group's max(x) is 50). This
   covers comparisons, AND/OR combinations and `%in%` on numeric, logical and
   date columns. A comparison on a column that is entirely `NA` in a row group
   also skips it. String columns carry only the null count, so string
   predicates prune through a hash index rather than zone maps.

These strategies compose: hash index and binary search narrow the candidate
row groups, then zone maps are checked on each candidate before its bytes are
read. A Parquet scan uses the same zone-map check against the min/max and null
counts in the Parquet footer.

### Column pruning

The optimizer walks the plan top-down and determines which columns each node
needs from its child: the columns referenced in its own expressions (filter
predicates, mutate expressions, aggregation inputs, join keys) plus the columns
its parent needs. A `mutate()` drops the passed-through columns nothing above it
uses, so pruning continues below it. At scan nodes, unneeded columns are never
read, decompressed or decoded. For a 100-column `.vtr` file where 3 columns are
needed, this shows in `explain()` as `3/100 cols (pruned)`.

### Hidden mutate insertion

When `summarise()` contains nested expressions like `mean(x + y)`, the
optimizer auto-inserts a `ProjectNode` (visible as `hidden mutate` in
`explain()`) to compute the intermediate expression `x + y` before aggregation.
This is necessary because the C-level aggregation nodes (GroupAgg) operate on
single columns, not on expression trees. The hidden mutate computes the
intermediate column and gives it a generated name, which the aggregation node
then references. The same mechanism applies to `sum(log(x))`, `n_distinct(a +
b)`, and similar patterns. The inserted node is visible in `explain()` output
but invisible to the user's pipeline.

## explain() contract

`explain()` prints the optimized plan tree without executing it. The output
shows:

- Node types in execution order (leaf to root)

- Per-node annotations: streaming/materializing, column pruning, predicate
  pushdown, row-group statistics (`tdc stats`), a hash index when one will be
  used, hidden mutate
- Grouping columns if present

- Output schema (column names and types)

- For an offloaded node or partition (see `offload()`), its cost grade

```r
tbl("data.vtr") |>
  filter(x > 0) |>
  select(id, x) |>
  explain()
#> vectra execution plan
#>
#> ProjectNode [streaming]
#>   FilterNode [streaming]
#>     ScanNode [streaming, 2/5 cols (pruned), predicate pushdown, tdc stats]
#>
#> Output columns (2):
#>   id <int64>
#>   x <double>
```

The plan tree is a description of what will happen, not a guarantee of how it
will happen internally. Node ordering and naming may change between versions.

## Hash indexes (.vtri)

vectra supports persistent on-disk hash indexes stored as `.vtri` sidecar files
alongside `.vtr` data files. An index names the row groups that may hold a key,
so an equality predicate reads those groups and skips the rest.

### Creating indexes

Both functions take the path of the `.vtr` file:

```r
# Single-column index
create_index("data.vtr", "species")

# Case-insensitive index
create_index("data.vtr", "species", ci = TRUE)

# Composite (multi-column) index
create_index("data.vtr", c("country", "year"))

# Check whether a usable index exists
has_index("data.vtr", "species")
```

`create_index()` reads the indexed column(s) of the `.vtr` file one row group at
a time and writes a `.vtri` file holding one entry per distinct key per row
group. The file name encodes the indexed columns: `data.species.vtri` for a
single-column index, `data.country_year.vtri` for a composite. Composite columns
are canonicalized to schema order, so they may be named in any order.

### Index format

The `.vtri` format is a sorted array of (key hash, row group) entries. One
layout covers both cases: a header with the indexed column indices, a
case-insensitive flag, and the row count, row-group count and fingerprint of the
store at build time, followed by the entries in ascending hash order and a
directory giving the first entry for each range of leading hash bits.

Sorting the entries rather than chaining them is what lets an index be built in
one forward pass through a fixed memory budget, since a chained table has to
know every entry's bucket before it can write the first one. It also drops the
per-entry chain pointer and the bucket array: 12 bytes an entry rather than
about 36.

Hashing uses FNV-1a on the raw column bytes; a case-insensitive index folds
ASCII uppercase to lowercase before hashing. A composite key combines the
per-column FNV-1a hashes by XOR and multiplication with the FNV prime, giving
one 64-bit hash per entry.

The stored stamp is what makes an index safe to leave on disk. `vtri_open()`
compares it with the store being queried and reports no index when any part
disagrees, so an index that no longer describes its store is ignored rather than
used to prune row groups that have moved or now hold other keys. The counts
catch an append; the fingerprint catches a store replaced by another of the same
shape, whether by `write_vtr()`, a download or a rename. It digests the store's
row-group index together with a digest of the store's bytes, which the writers
compute as they write and record in a 24-byte trailer after the container, so
checking it costs the store's metadata rather than its data. A store written
before 0.12.4 has no trailer, and its fingerprint covers its layout only.
Index formats written before 0.12.4 lack the fingerprint and read as absent;
`create_index()` rebuilds them.

### How the scan uses indexes

On its first batch, a `ScanNode` looks at its pushed-down predicate, picks the
column an equality or `%in%` clause offers, and opens that column's `.vtri` if
there is one. For composite indexes it collects the AND-combined equality
clauses and opens the sidecar covering exactly those columns. Opening is
deferred to this point, so a query reads an index only for the column it
filters on.

On match, the scan probes the index to produce a row-group bitmap. For `%in%`
predicates, the scan probes once per set element and ORs the bitmaps together.
Row groups with a 0 bit in the bitmap are never read from disk. This is the
first pruning step, applied before binary search and zone-map checks.

### Performance characteristics

A probe is a hash computation, one directory lookup, and a binary search over
the few entries that directory slot covers (the directory holds one slot per
four entries, up to 2^22 slots), repeated per query key (once for `==`, n times
for `%in%`). A sidecar of up to 4 MB is read into memory when the scan opens it;
a larger one is memory-mapped read-only and probed in place, so opening it does
not read the whole file. An index over a column of few distinct values stays the
same size as the store grows, so the cost of a lookup does not follow the size
of the store. For tables with many row groups and selective equality predicates, index
pushdown can reduce I/O by orders of magnitude compared to zone-map pruning
alone.

## Materialized blocks

`materialize()` consumes a vectra node and stores the result as a persistent
in-memory columnar block. Unlike nodes, which are consumed on `collect()` and
cannot be reused, blocks persist and support repeated lookups.

```r
blk <- tbl("backbone.vtr") |>
  select(taxonID, canonicalName, genus) |>
  materialize()
```

### Exact lookups

`block_lookup()` performs hash-based lookups on a string column. Hash indices
are built lazily on first use and cached for subsequent calls. The return value
is a data.frame with a `query_idx` column (1-based position in the input keys
vector) plus all columns from the block.

```r
hits <- block_lookup(blk, "canonicalName",
                     c("Quercus robur", "Pinus sylvestris"))

# Case-insensitive
hits <- block_lookup(blk, "canonicalName",
                     c("quercus robur"), ci = TRUE)
```

### Fuzzy lookups

`block_fuzzy_lookup()` computes string distances between query keys and a
block column. Three distance methods are available: Damerau-Levenshtein
(`"dl"`, default), Levenshtein (`"levenshtein"`), and Jaro-Winkler (`"jw"`).
Results are filtered by a maximum normalized distance threshold (default 0.2).

```r
fuzzy <- block_fuzzy_lookup(blk, "canonicalName",
                            c("Quercus robar", "Pinus silvestris"),
                            method = "dl", max_dist = 0.2)
```

An optional blocking column reduces the search space by requiring exact matches
on a second column before computing distances. This is useful for taxonomic
lookups where genus is known:

```r
fuzzy <- block_fuzzy_lookup(blk, "canonicalName",
                            c("Quercus robar"),
                            block_col = "genus",
                            block_keys = c("Quercus"),
                            n_threads = 4L)
```

Fuzzy lookups are OpenMP-parallelized. The `n_threads` parameter controls the
thread count (default 4).

### Use case

Materialized blocks are designed for repeated lookups against a reference table.
The typical pattern is: load a backbone or codelist once with `materialize()`,
then probe it many times with different query vectors. The block stays in memory
across calls, and its internal hash index (for exact lookups) is built once and
reused.

## OpenMP parallelization

The C engine uses OpenMP for CPU-bound operations where the per-element cost is
high enough to justify thread management overhead. Parallelism is conditional:
operations fall back to single-threaded execution when the batch size is below a
threshold or when the platform does not support OpenMP.

### Which operations parallelize

| Operation | Threshold | Schedule | Notes |
|:----------|:----------|:---------|:------|
| `filter()` (selection vector build) | 32,768 rows | parallel prefix sum | Two-phase: count matches per thread, then write at offsets |
| `grepl()` with regex | 1,000 rows | `dynamic, 64` | Per-thread regex compilation for thread safety |
| `levenshtein()`, `dl_dist()`, `jaro_winkler()` | 1,000 rows | `dynamic, 64` | Fuzzy string distance in mutate expressions |
| Sort (merge sort) | 32,768 rows | `task` | Recursive task spawning for parallel merge sort; a single numeric key uses a radix sort instead |
| Sort (emit gather) | 32,768 rows x columns | `static` | Fixed-width columns of each emitted batch gathered in one parallel loop |
| Join (build-side hashing) | 32,768 rows | `static` | Parallel hash computation for build-side keys |
| Join (probe-side hashing) | 32,768 rows | `static` | Parallel hash computation for probe-side keys |
| Grouped aggregation (key hashing) | 32,768 rows | `static` | Hash and shard assignment per row |
| Grouped aggregation (shards) | 32,768 rows | `dynamic, 1` | One hash-table shard per thread |
| Window (data copy) | 32,768 rows | `static` | Parallel copy of partition data |
| Window (group dispatch) | 64 groups | `dynamic` | Parallel window computation across groups |
| Collect (column append) | 8 columns | `static` | Parallel column-by-column append to R vectors |
| `collect()` of a plain `.vtr` scan | always | `dynamic` | Row groups decoded in parallel straight into the R vectors |
| `write_vtr(compress = "small")` | 32,768 values | `dynamic` | Candidate encodings tried in parallel |
| Parquet read (columns) | 32,768 values | `dynamic, 1` | Column chunks of a row group decoded in parallel |
| Block fuzzy lookup | always (if > 0 keys) | `dynamic, 1` per key / `dynamic, 16` per row | Parallelized by query key and by block row |
| Literal fill (broadcast) | 32,768 rows | `static` | Parallel fill for constant columns |

The general-purpose threshold is 32,768 rows (`VEC_OMP_THRESHOLD`). String
operations use a lower threshold of 1,000 rows because their per-element cost
(regex compilation, edit distance matrices) is much higher than arithmetic.

### Thread safety

Regex operations (`grepl` with regex patterns) compile the POSIX regex once per
thread. Each thread owns its own `regex_t` instance, allocated in thread-local
scope inside the `#pragma omp parallel` block. This avoids both contention and
the overhead of recompiling the regex per row.

The filter node uses a parallel prefix sum to build the selection vector without
locking. Each thread counts matches in its chunk, a sequential scan computes
prefix offsets, then each thread writes selected indices at its computed offset.

## Current limitations

- **slice_tail materializes**: There is no reverse-scan optimization.

- **distinct with .keep_all**: Falls back to R when `.keep_all = TRUE` with a
  column subset.

- **Predicate pushdown covers .vtr and Parquet only**: CSV, SQLite, TIFF,
  FASTA/FASTQ and BED scans do not benefit from predicate pushdown, column
  pruning, or hash index acceleration. Parquet scans get column pruning and
  row-group pruning from footer statistics, but no hash indexes.

- **Joins are not rewritten by the optimizer**: a join reads every column of
  both inputs, and filters above a join are not pushed into its inputs. Filter
  and select before the join to limit what it reads.

- **No SIMD**: Arithmetic and comparison operations use scalar loops. The
  compiler may auto-vectorize some patterns, but there are no explicit SIMD
  intrinsics.

- **OpenMP availability varies**: when vectra is built from source,
  `configure` compiles, loads and runs a small OpenMP test for each candidate
  set of compiler flags and uses the first that works. On macOS it tries the
  OpenMP runtime that CRAN's R ships in `R_HOME/lib` first, then a Homebrew
  `libomp`. If none works, vectra is built single-threaded, which changes speed
  but not results. On Windows (Rtools) and Linux, OpenMP is typically available
  out of the box.

## Fallback behavior

vectra has these fallback paths to base R:

1. **bind_rows with mismatched column names**: If column names differ across
   inputs, all tables are collected and combined via `rbind()` in R.
2. **distinct with .keep_all and column subset**: Falls back to `duplicated()`
   in R (emits a message).
3. **slice_tail**: Must see all rows to take the last n; returns a data.frame.

4. **slice_min/slice_max with `with_ties = TRUE`** (the default): Collects all
   data to identify ties at the boundary; returns a data.frame.
5. **reframe**: Always collects and evaluates in R; returns a data.frame.

All other operations execute entirely in C. There is no silent fallback to dplyr
or any other package.

## Grouping preservation

All verbs preserve `group_by()` metadata: `filter()`, `select()`, `mutate()`,
`rename()`, `relocate()`, `arrange()`, and `transmute()` pass grouping through.
`rename()` additionally updates group column names to match the rename.
`summarise()` drops grouping according to its `.groups` argument.

## Package conflicts

vectra defines its own S3 generics for dplyr-like verbs (`filter`, `select`,
`mutate`, etc.) and utility functions (`glimpse`, `collect`). If dplyr is also
loaded, whichever package was attached last will mask the other's generics.
vectra's methods will still dispatch correctly on `vectra_node` objects
regardless of masking order.