Crate spg_storage 

In-memory storage primitives.

v0.3 is intentionally simple: a flat catalog of tables, each holding rows as Vec<Value> (positional, matching the table’s TableSchema). No MVCC, no on-disk format — those land in later milestones.

Re-exports

pub use self::bloom::BloomError;

pub use self::bloom::BloomFilter;

pub use self::row_locator::RowLocator;

pub use self::row_locator::RowLocatorError;

pub use self::segment::BRIN_SIDECAR_MAGIC;

pub use self::segment::BrinSummary;

pub use self::segment::OwnedSegment;

pub use self::segment::SEGMENT_COMPRESS_ALGO_LZSS;

pub use self::segment::SEGMENT_COMPRESS_ALGO_NONE;

pub use self::segment::SEGMENT_MAGIC;

pub use self::segment::SEGMENT_MAGIC_V2;

pub use self::segment::SEGMENT_PAGE_BYTES;

pub use self::segment::SegmentError;

pub use self::segment::SegmentMeta;

pub use self::segment::SegmentReader;

pub use self::segment::derive_brin_summaries;

pub use self::segment::encode_segment;

pub use self::segment::wrap_v2_envelope;

pub use self::segment::wrap_v2_envelope_with_brin;

Modules

bignum

v7.38 (read01, T3) — arbitrary-precision decimal for NUMERIC values that overflow i128 (PG’s NUMERIC is unbounded; SPG’s i128 fast path tops out near 38 digits). Clean-room schoolbook arithmetic on base-10^9 limbs (each limb holds 9 decimal digits, little-endian), a sign, and a decimal scale. This is phase C1: representation + add / sub / mul / cmp + the i128 bridge

bloom

v5.0 — BloomFilter, byte-keyed probabilistic set with a known false-positive ceiling. The v5 cold-tier segment files prefix a Bloom built over their PK column so a lookup(pk) that doesn’t exist in a segment is rejected without touching the page index or the data pages — gating ~99 % of cross-segment probes away from disk I/O.

fts_simple

v7.17.0 Phase 2.2 — lower-cased word tokenisation that mirrors to_tsvector('simple', text). Lives in storage (not engine) because the crate::IndexKind::GinFulltext posting-list build / rebuild / insert paths all run in storage and the engine crate can’t be a build-time dependency from here.

halfvec

v6.0.3 — halfvec: IEEE-754 binary16 (F16) per-element storage.

jsonb_gin

v7.37.8(sentori Epic 5 P2)— JSONB → GIN posting-list tokens.

persistent

Persistent (structural-sharing) vector — the v4.38 building block for the v4.39 cheap-Catalog::clone migration.

persistent_btree

Persistent (structural-sharing) B-tree map — the v4.40 building block for migrating Table::indices off alloc::collections::BTreeMap.

priv_bits

v7.39 (read01 round 57) — the table-privilege bits, in PG’s aclitem rendering order (arwdDxtm). The order matters: relacl output is byte-compared against PG.

quantize

v6.0.0 — SQ8 scalar quantization for vector columns.

row_header

v7.37.15 (Phase A) — per-row MVCC visibility header.

row_locator

v5.1 — two-tier row pointer. The PB secondary index used to map IndexKey → Vec<usize>, where each usize was a row position in Table::rows: PersistentVec<Row> (the hot tier). v5.1 widens that to Vec<RowLocator> so a single key can point to a mix of rows in the in-memory hot tier and rows that have been frozen to immutable cold-tier segment files (spg-storage::segment).

segment

v5.0 — cold-tier segment file codec. A Segment is an immutable, PK-sorted file of (u64_key, row_bytes) entries with three sidecar sections for fast probing: a BloomFilter over the keys, a page index, and the payload pages themselves. The v5 freezer (v5.2 work) writes one segment per “freeze batch”; the v5.1 two-tier catalog probes the bloom first, then the page index, then a single 4 KiB page read — so a missed cold-tier probe costs at most ~bloom.contains() time, and a hit costs one disk seek + page-internal binary search.

snapshot

v7.37.15 (Phase A) — per-statement / per-transaction snapshot.

trgm

v7.15.0 — trigram extraction for pg_trgm-compatible GIN indexes. Mirrors PG’s pg_trgm extension closely enough that gin_trgm_ops indexes built on the same source produce the same trigram set and similarity(a, b) returns the same Jaccard ratio.

vacuum

v7.37.15 (Phase D) — vacuum primitives.

Structs

AclItem

v7.39 (read01 round 57) — one PG aclitem: what grantee may do to a table, and who granted it. Renders as grantee=privs/grantor, with an EMPTY grantee meaning PUBLIC (=r/owner).

Catalog

CheckConstraint

v7.9.19 — composite UNIQUE / PRIMARY KEY constraint persisted on the table schema. The leading column always has a BTree index (created at CREATE TABLE time); INSERT enforcement scans that index for collisions on the full column tuple. v7.39 (read01 round 48) — a CHECK constraint: the SQL name the user gave it (via ADD CONSTRAINT <name> CHECK (...) or the inline CONSTRAINT <name> CHECK (...) form) plus the predicate source. None name = unnamed, in which case pg_constraint synthesises PG’s <table>_<col>_check form. Names are persisted in the constraint-name appendix (FILE_VERSION 60+); older catalogs deserialise with None.

ColdReadStats

Catalog: insertion-ordered Vec<Table> for stable iter / serialize, plus a BTreeMap<String, usize> sidecar index so get / get_mut run in O(log n) instead of the old linear scan with per-element string compares.

ColumnSchema

Each bool is an independent, separately-persisted column attribute (nullable, auto_increment, is_unsigned, identity_always) that the catalog appendix reads and writes by name. Packing them into a bitflags word would buy nothing and would put a decoding step between the on-disk format and every reader of the schema.

CompactReport

v6.7.3 — outcome of a Catalog::compact_cold_segments call. The catalog state has already been mutated when this is returned: the merged segment is loaded into cold_segments, the source segment slots are tombstoned (None), and every BTree-index RowLocator::Cold that previously pointed at a source now points at the merged segment. The caller’s remaining job is to persist merged_segment_bytes under <db>.spg/segments/seg_<merged_segment_id>.spg and update the in-memory segment_id → path map (remove the source ids, add the merged id) so the next CHECKPOINT writes a manifest that no longer lists the retired sources.

CompositeDef

v7.37.42-T2 ζ-B — catalogued user-defined COMPOSITE type (CREATE TYPE name AS (field_name field_type, ...)). Order matters: PG composite literals are positional, and SPG mirrors that. Stored as ordered (name, DataType) pairs to keep the codec straightforward and to allow eventual Value::Composite bodies to encode positionally. Persisted in catalog FILE_VERSION 52+; older catalogs deserialise with an empty composite_types map. Composite types can be used as a column type by spelling the composite’s name; the resolution from ColumnSchema.user_composite_type = Some(name) happens at the engine boundary (parallel to user_enum_type / user_domain_type). The dense storage shape — JSON-text body keyed by the composite’s field list — keeps the codec free of recursive Value bodies until the full Value::Composite arena migration in a later phase.

DomainCheck

v7.39 (round 260) — one named CHECK on a domain. PG auto-names an unnamed one <domain>_check, then _check1, _check2, … (probed).

DomainDef

default / checks are stored as Display-form source so spg-storage stays free of spg-sql dependency — same pattern as FunctionDef / ViewDef.

EnumDef

v7.17.0 Phase 1.4 — catalogued user-defined ENUM type. The label vector is order-preserving (PG enum ordering follows the declared order). At INSERT/UPDATE on a column bound to this enum, the engine looks up the value against labels and rejects non-members.

ExclRangeIndex

v7.39 (round 215) — a per-table range-exclusion index: an incrementally maintained map from a range column’s lower-bound key (range_excl_index_key) to the physical row locators carrying that bound. Lets EXCLUDE enforcement find the few candidate rows a new range might overlap in O(log n) instead of scanning every row (measured O(N²), r213). Because the stored ranges under a valid EXCLUDE (col WITH &&) are pairwise disjoint, a candidate overlaps only its predecessor or the successors whose lower bound precedes its upper — a handful of probes.

ExclusionConstraint

v7.39 (round 210) — an EXCLUDE constraint. Forbids two distinct live rows from satisfying, for EVERY element, new.col <op> existing.col (e.g. EXCLUDE USING gist (during WITH &&) = no two during ranges overlap). Unlike a uniqueness constraint the operator is not equality, so enforcement is a full live-row scan re-checking the operator (a real GiST index that answers overlap in O(log n) is a later perf phase). A NULL in any element column exempts the row (matching PG / UNIQUE NULL semantics). Persisted in catalog FILE_VERSION 72+.

ForeignKeyConstraint

v7.6.1 — Storage-layer mirror of spg_sql::ast::ForeignKeyConstraint. The engine’s CREATE TABLE path translates between the two; keeping them separate preserves the no-deps boundary between spg-storage and spg-sql.

FreezeReport

v5.2.2: outcome of a successful Catalog::freeze_oldest_to_cold call. The catalog state has already been mutated by the time this is returned (hot rows dropped + segment registered + Cold locators flipped). The caller’s only remaining concern is segment_bytes — persist them to disk under <db>.spg/segments/seg_<id>.spg so a future restart can reload via the v5.1 SPG_PRELOAD_COLD_SEGMENT path. (v5.3’s manifest will subsume this manual step.)

FreezeSlice

v6.7.4 — read-only output of Catalog::prepare_freeze_slice. Carries every row body + key in a contiguous hot-row range, already encoded and sorted by PK so the coordinator’s merge step is a k-way merge over already-sorted streams.

FunctionDef

v7.12.4 — catalogued user-defined function. body is the raw source text between $$ ... $$; the engine re-parses it on invocation. This keeps the storage codec stable when the PL/pgSQL surface grows (no breaking-change risk on the disk format).

Index

A single-column secondary index. v2.0 carries either a B-tree map (the default — used for equality / range lookups on scalar columns) or a navigable-small-world graph (used for kNN over vector columns).

IntervalSpan

v7.37.5 β-P4 — element type for Value::IntervalArray. Mirrors the {months, days, micros} shape of scalar Value::Interval, broken out as a named struct so IntervalArray’s element type is concrete (24 bytes, packed) instead of an enum-boxed Value. All three dimensions are independent — IntervalSpan { days: 1, .. } is distinct from IntervalSpan { micros: 86_400_000_000, .. } per PG byte-equal.

NswGraph

Multi-layer HNSW graph (v2.13). Each node is assigned a top_level; it appears in layers 0..=top_level. Higher layers are sparser, so search starts from the entry at the top layer, greedy-descends to layer 0, and beam-searches there. Layer 0 keeps a larger neighbour budget (m_max_0 = 2 * m per the HNSW paper); upper layers cap at m. The struct name stays NswGraph so external users / on-disk callers don’t have to track a rename — the algorithm changed, the data slot didn’t.

Point2D

v7.37.5 ε — PG point building block. Shared by every other geometric type (lseg / path / box / polygon / circle all reduce to compositions of Point2D). Packed {x: f64, y: f64}, 16 B, on-disk LE field order matches the PG binary point format byte-for-byte (so a future binary BIND path lands without rearrangement).

PolicyDef

v7.39 (RLS) — one CREATE POLICY object, stored per table. The using_expr / with_check_expr hold the qualifying expression’s Display form (re-parsed and evaluated per row at enforcement time, exactly like TableSchema.checks); None means the clause was absent. roles empty = PUBLIC. Persisted in the policy appendix (FILE_VERSION 59+).

RangeSpan

v7.37.5 δ — single-range bounds without the kind tag. Used as the element type of Value::Multirange { kind, ranges } so a multirange carries one shared RangeKind plus N bounds-only spans (saves 1 byte/elem vs duplicating the kind). The five other fields mirror Value::Range exactly.

Row

One table row — values are positional and must match TableSchema.columns in length and (modulo NULL) in DataType.

RuleDef

v7.39 (round 139) — a catalogued query-rewrite RULE. Stored flat like TriggerDef, keyed by (name, table). Command / WHEN text is deparsed SQL re-parsed at rewrite time (the same round-trip trick as TriggerDef.when_condition). Persisted from FILE_VERSION 71.

ScanStats

v7.39 (pg_stat knife B) — per-table scan counters, bumped from &self read paths. Clone (tx shadow catalogs clone tables) copies the current values; the counters are volatile like PG’s cumulative stats.

SequenceDef

v7.17.0 — catalogued SEQUENCE. PG semantics: a counter object returning monotonically increasing values via nextval(name). last_value is the most recent value handed out; is_called is false until the first nextval/setval. Stored separately from tables in the catalog.

StatisticsExtDef

v7.39 (round 280) — one CREATE STATISTICS object.

Table

TableSchema

TriggerDef

v7.12.4 — catalogued trigger. References its function by name; the function must exist at TRIGGER creation time (forward references are deferred to v7.12.5+).

TsLexeme

v7.12.0 — one entry in a Value::TsVector. The lexeme is the (already-tokenised + stemmed in v7.12.1+) word; positions is a strictly-ascending list of 1-based positions; weight is the PG weight letter (A=3, B=2, C=1, D=0) — v7.12.0 defaults every lexeme to D, the v7.12.2 ranking path consumes the weight.

TxWriteSet

v7.17.0 Phase 1.5 — catalogued user-defined DOMAIN. A domain is a named CHECK-constrained alias over a built-in type; columns bound to it inherit the base type plus the CHECK predicates + NOT NULL + DEFAULT at INSERT/UPDATE time. v7.37.17 (Phase E RC rebase) — the write-set one writer version left on a table, addressed by stable row_header::RowIds so it can be replayed onto a fresher clone of the relation whose physical slots differ. Produced by Table::extract_tx_writeset, consumed by Table::replay_tx_writeset.

UniquenessConstraint

ViewDef

v7.17.0 Phase 1.2 — catalogued VIEW. The body is stored as the raw source text the parser saw between AS and the statement terminator; the engine re-parses on each invocation. Same pattern as FunctionDef — keeps spg-storage free of spg-sql dependency.

Enums

Collation

v7.17.0 Phase 2.5 — column-level text collation. Drives the engine’s WHERE / GROUP BY equality routing for Value::Text. Only two variants are modelled in v7.17:

DataType

Runtime type tags. Vector { dim, encoding } / Varchar(max) / Char(size) are parameterised; the parameter travels with both the column schema and the on-wire serialised representation.

FkAction

v7.6.1 — referential action tag. Mirrors spg_sql::ast::FkAction.

IndexKey

Key type accepted by secondary indices. Float / NULL / Vector values can’t participate in a B-tree index — f64 is only PartialOrd, NULL has SQL-three-valued semantics, and Vector belongs to the (future) HNSW path. Index lookups on those columns fall back to full scan.

IndexKind

MatchType

v7.38 (read01, T29) — FK MATCH type. Mirrors spg_sql::ast::MatchType.

MysqlIntWidth

v7.39 (round 386, type-fidelity epic P1) — the declared MySQL narrow integer type for a column whose storage DataType cannot express it. MySQL TINYINT (i8, -128..127) collapses to DataType::SmallInt (i16) and MEDIUMINT (24-bit) to DataType::Int (i32) — both wider than the declared type, so a range check against ty alone accepts out-of-range values (INSERT 128 INTO TINYINT is stored silently where MariaDB strict raises ERROR 1264). This annotation records the lost width so the write path (epic P2) can enforce the real bounds. SMALLINT / INT / BIGINT need no marker — their storage DataType is already faithful. Sparse: only TINYINT / MEDIUMINT columns carry it; persisted in the FILE_VERSION 81+ appendix, older catalogs deserialise as None.

NswMetric

Distance metric used at NSW search time. The graph topology is always built with L2; querying with InnerProduct / Cosine reuses the same edges but ranks candidates by the chosen metric. For the corpus-sized graphs this loses negligible recall vs building separate per-metric graphs.

NumericKind

A row-cell value, including SQL NULL. Float uses f64; NaN compares non-equal to itself (PG behaviour) — PartialEq is derived so callers must opt into NaN-aware comparison if they need stronger guarantees.

PartitionBound

v7.37.6-B — partition 边界 literal。

PartitionKind

v7.37.6-B — 分区策略。

PartitionRole

v7.37.6-B — partition 三态(parent / range child / default child)。

PolicyCmd

v7.39 (RLS) — the command a policy applies to. ALL is the default and covers every command; the others scope the policy to one statement kind. Persisted as a single byte in the policy appendix (FILE_VERSION 59+).

RangeKind

v7.17.0 Phase 3.P0-38 — pins the element type of a range value or column. Wire OIDs: Int4=3904, Int8=3926, Num=3906, Ts=3908, TsTz=3910, Date=3912.

RowChange

In-memory table: schema + a persistent row vector + secondary indices.

SequenceDataType

v7.17.0 — sequence integer width.

StorageError

TsQueryAst

v7.12.0 — parse tree for a PG tsquery. v7.12.0 ships the type + codec only; the to_tsquery / plainto_tsquery lexer lands in v7.12.1 and the @@ evaluator in v7.12.2.

Value

VecEncoding

In-cell encoding for DataType::Vector. Mirrors spg_sql::ast::VecEncoding — kept here so storage stays dep-free of spg-sql. The engine bridges between the two at DDL-execution time.

Constants

CURRENT_ROW_CODEC_VERSION

v7.37 (round 833) — the codec version to decode a row that encode_row_body_dense has just produced.

FN_IMMUTABLE

FN_PARALLEL_RESTRICTED

FN_PARALLEL_SAFE

FN_PARALLEL_UNSAFE

v7.39 (round 322, V46) — FunctionDef.parallel codes: PG’s pg_proc.proparallel letters.

FN_STABLE

FN_VOLATILE

v7.39 (round 322, V46) — FunctionDef.volatility codes: PG’s pg_proc.provolatile letters.

NSW_DEFAULT_M

Default neighbor degree (M) for the NSW graph. Picked at construction time and persisted with the index.

Functions

decode_redo_log

v7.34, extended v7.37.15 (Epic W slice 1) — decode a row-level redo log written by encode_redo_log.

decode_row_body_dense

decode_row_body_dense_pruned

Inverse of encode_row_body_dense. Reads one row’s body from bytes and returns it plus the number of bytes consumed (so a caller decoding a back-to-back stream of rows can advance its cursor). Returns StorageError::Corrupt on truncation, bad UTF-8, or unknown cell tags. v7.37 (round 923) — decode_row_body_dense that does not build the columns the caller will not read.

encode_redo_log

v7.34 (crash-recovery P0 #2), extended v7.37.15 (Epic W slice 1) — encode a row-level redo log to bytes for a WAL record.

encode_row_body_dense

Encode one row’s body in the v3.0.2 dense format (FILE_VERSION 8): per-row NULL bitmap (1 bit/col, ceil(cols/8) bytes), then each non-NULL cell as write_value_body. Same wire shape the catalog snapshot writes per row inside its rows-block. Exposed pub so v5.1+ cold-tier segment writers can produce row payloads that the catalog decode_row_body_dense decodes 1:1.

encode_row_body_dense_into

v7.37 (round 883) — encode_row_body_dense appending to a buffer the caller owns.

encode_row_body_dense_masked_into

v7.37 (round 995) — encode_row_body_dense_into that does not STORE the columns the caller will not read.

format_uuid

v7.17.0 — render a Value::Uuid payload as the canonical lowercase 8-4-4-4-12 hyphenated form PG text cast surfaces.

function_arg_names

v7.39 (read01 round 65) — the declared argument NAMES of a function ("" for a bare type with no name).

function_arg_types

The declared argument TYPES of a function, out of its args_repr ("(x INT, y DOUBLE PRECISION)" → ["int", "float"]). An entry may be a bare type with no name ("(INT)").

function_signature_key

function_signature_key_legacy

v7.39 (round 315, V19) — the signature key as computed BEFORE the multi-word fix, used only to recognise what an older image wrote.

is_builtin_schema

v7.17.0 Phase 1.6 — built-in schema names that every Catalog understands without an explicit CREATE SCHEMA. Used by Catalog::schema_exists and the engine’s schema-qualified lookup path.

is_multiword_type_phrase

v7.39 (round 344, V49) — re-exported from spg_sql, which owns the SQL type spellings. This crate carried a byte-identical copy because the two were siblings that did not depend on each other; spg-sql is a dependency-free leaf, so the dependency is acyclic and the publish order already puts it first. One list, one place to keep it right. v7.12.4 — map a bare type-name identifier (the form that appears in a function arg list or RETURNS clause) to a ColumnTypeName. Returns None for unknown / extension types so the caller can preserve them as FunctionArgType::Raw / FunctionReturn::Other.

mysql_ci_fold

v7.39 (round 363, M4 P1) — MySQL’s default accent- and case-insensitive fold (utf8mb4_uca1400_ai_ci).

mysql_compare_fold

v7.39 (round 375) — the fold used to COMPARE / GROUP / de-dup text on the MySQL dialect. Its default collation is PAD SPACE: trailing spaces do not affect a comparison ('a' = 'a ', '' = ' ', measured on MariaDB 11), so they are stripped before the case/accent fold. Only literal spaces pad — a tab or other whitespace is significant — and this is NOT used by LIKE, whose pattern treats a trailing space literally.

normalize_type_name

Fold PG’s type aliases so a signature key is stable across spellings. Unknown names pass through lower-cased — consistency is what the key needs.

nsw_assign_level

Deterministic level assignment, seeded on the row index so the same insert order reproduces the same topology. Distribution is roughly HNSW-flavoured with mL ≈ 1/ln(M) ≈ 0.36 for M=16: each 4-bit chunk that comes up zero promotes the node one layer (so P(level ≥ L) ≈ (1/16)^L).

nsw_index_on

Find any NSW index on a column. Used by the planner to decide whether an ORDER BY col <-> literal LIMIT k query can skip the brute-force scan.

nsw_query

Public wrapper: run an NSW kNN search and return the top-k row indices ordered by ascending distance under the given metric.

parse_uuid_str

v7.17.0 — parse a PG-canonical UUID text representation into the 16-byte network-order layout used by Value::Uuid. Accepted input shapes (all case-insensitive):

range_excl_index_key

v7.39 (round 215) — the lower-bound sort key for a range value, used by the range-exclusion index. The bound as an i128 (unbounded lower = i128::MIN, sorting first) plus an inclusivity rank (inclusive lower sorts before exclusive at the same value, [3 before (3). Returns None for range kinds whose bound isn’t an integer scalar (numrange’s numeric/bignum), for empty ranges, and for non-range values — the caller then keeps the O(n) scan rather than risk an unsound order. Int4/Int8/ Date/Ts/TsTz all reduce here (tstzrange bounds are Value::Timestamp). Maintenance (index build) and query (overlap probe) MUST agree on this key, so both sides call exactly this function.

resolve_stored_function_key

v7.39 (round 315, V19) — which catalogued function does a persisted ACL key refer to?

row_body_encoded_len

Fast computation of the byte length encode_row_body_dense would produce, without allocating the output buffer. Mirrors the encoder’s per-column body sizing so the v5.2.1 Table::hot_bytes incremental counter doesn’t pay an alloc-per-insert tax. Returns the exact same usize as encode_row_body_dense(row, schema).len().

unresolved_tombstone_count

v7.37.15 (Epic W durable-tombstone slice) — read the process-wide count of redo tombstones that could not be resolved to a row by RowId during apply_redo. See [UNRESOLVED_TOMBSTONES].

unresolved_tombstones

v7.39 (flip crash-replay P0) — observability read for the replay tombstones that could not be resolved to a row (each one is a resurrected delete).

Type Aliases

RowOwned

Owned Row — values are Value<'static>. Used everywhere a row must outlive a query-scoped arena.

ValueOwned

Owned Value — heap-bearing variants are Cow::Owned. Used everywhere a Value must outlive a query-scoped arena (catalog defaults, persistent storage, public APIs).