Crate rudb_native

Expand description

Rudb’s single-file columnar snapshot format.

A committed directory names independently readable column pages. It has two levels: a catalog directory naming every table in the file, which is what a footer slot points at and what opening a database reads, and one directory per table under it holding that table’s stripes, pages and statistics. One slot write publishes all of them, so a commit is atomic across tables.

This version handles scalar columns; the file header has two generation slots so an unfinished replacement directory cannot hide the last complete one. See spec/storage-v3/12-many-tables-in-one-file.md.

§Parts and stripes

A part is one appended chunk, which is a thousand rows, and it is the unit a scan decodes and hands to the pipeline. A stripe is sixty four parts, and it is the unit the directory describes and the unit the file is laid out in: one page per column per stripe, holding that column’s sixty four part payloads end to end.

The two are separate because they are sized by different pressures. A part wants to be small because it is a vector and vectors live in cache. A stripe wants to be large because everything the directory holds is per stripe and the directory is one buffer that has to be read and decoded before a single row can be answered. A hundred million rows of the hundred and five column ClickBench table is ninety seven thousand parts, and a directory with a page entry and a pair of bounds per part per column is several hundred megabytes, which is what made that load fail before this split existed. Sixty four parts to a stripe divides that by sixty four.

Where the parts of a page start is not in the directory either, for the same reason. Each stripe writes one index page holding a length and a checksum per part per column, and a reader preads the sixty four entries belonging to the column it wants. A scan reads the whole column page once and slices it; a sparse row fetch reads the index entries and then only the part it needs.

Re-exports§

pub use section::Section;

Modules§

grams: A word per row of a long text column, with a bit for each run of three bytes the value holds.
graph: Building a table’s graph sections from the table’s own columns.
host: A bounded, certified host grouping over one native string dictionary.
section: The section table: one general mechanism for carrying a graph structure in a rudb file.
stats: Building a table’s statistics sections from the table’s own columns.

Structs§

Building: A stripe that Preparer::start began and Preparer::feed is adding parts to.
Catalog: Every table a native file holds, without the directory of any of them.
CertifiedSums: Signed integer sums and non-null counts for selected columns, plus total table rows.
ColumnLayout: Where one column’s bytes went, taken from the directory rather than by reading pages.
Common: What a native table’s frequency synopsis says about one value, as the planner asks for it.
Constraints: A table’s primary, unique and foreign keys, as the file stores them.
ContentNamer: content_name of bytes that arrive in pieces, which gives the same name as the pieces joined.
FrequencyOccurrences: Sparse row ordinals covered by a numeric frequency candidate set.
FrequencyPrefix: The values one column’s frequency synopsis lists, with a bound on everything it left out.
LaneStart: Where replay of one lane starts.
Layout: Where a whole file’s bytes went.
LogAnchor: How much of the log a file holds.
Merged: A stripe that has been through Writer::merge and is waiting for Merged::pages.
Merger: Merges prepared stripes into a writer’s dictionaries and statistics without the writer.
Opening: What Reader::open read before it returned.
PagePool: The pages every reader of one database keeps, under one budget in bytes.
Paged: A stripe that has been through Merged::pages and is waiting for Writer::write.
Prepared: A stripe that has been through Preparer::prepare and is waiting for Writer::merge.
Preparer: Encodes stripes for one Writer without the writer.
Reader: Reads committed native column pages without holding the table in memory.
Reads: What a reader has read, while it was being opened and since.
RunProjectionPart
RunProjectionScan
StoredForeign: One FOREIGN KEY, as the file stores it.
StoredPart: How one part of one column is stored, which is one row of pragma_storage_info.
Stripe: One independently readable stripe of a table.
Stripes: The bounds of a committed native table, as the planner asks for them.
Table: The committed table directory.
ViewEntry: One view’s line in the catalog directory.
Writer: Appends pages and commits a new directory.

Enums§

IntegerExtremes: Exact ends of an integer or date column, including a certified all-null column.

Constants§

DICTIONARY_CAP_BYTES: What all of a table’s global dictionaries may hold at once before the fastest growing one is demoted, from section 5.5 of the encoding spec.
STRIPE_PARTS: Parts in one stripe.

Functions§

ascending: The columns whose values never go down in row order and hold no null, by name.
attach: Attaches graph sections to a table already committed in a file, without rewriting a page.
build_run_projection: Attach a row-preserving run projection to an existing native table.
build_sorted_projection: Build a row-valued, sorted, covering projection inside an existing native file.
content_name: A hundred and twenty eight bit name for bytes, as two xxHash64 walks under different seeds, with the format this build writes folded in so that a name made by one format is never taken for the name of a file in another.
distincts: How many distinct values each column of a native table holds, for the columns it can say.
facts: Everything distincts, ascending and widths say, gathered once per open table.
widths: How many bytes a value of each string column takes on average, by name.

Type Aliases§

NumericFrequencies: A complete numeric value-to-row-count synopsis; None represents SQL NULL.
PairFrequencyCounts: Exact grouped counts for a pair of values, in descending count order.