Crate rudb_graph 

The graph layer’s structures: row ids, key maps and relationships.

This crate holds the data model of spec/graph/02-the-data-model.md and nothing else. It knows what a Rid is, how a KeyMap turns a parent key value into one, and what a Relationship declares. It deliberately does not know what a file, a page or a plan is: rudb-native at rank 6 is what puts a key map on disk and rudb-opt is what decides to use one, which is the right way round. A key map that could see the format would be a key map that could only be tested through one.

The invariant everything here is built on

Section 3.1: deleting every graph section from a rudb file must change no answer, only the time. That one sentence is what makes this layer safe to build incrementally, and it has four consequences worth stating where the code is rather than only in the specification.

A wrong index is a performance bug and not a wrong answer. Nothing in this crate is ever the only path to a row: a link join is a faster way to compute what a hash join computes, so a link that resolves the wrong rid shows up as a differential test failure against the same query with the graph sections turned off, which is a test that can exist because of the invariant.

Staleness is handled by ignoring. A section carries a generation stamp, and a section whose stamp does not match the table’s is dropped rather than repaired. There is no repair path in this crate, no incremental maintenance, and no way for a stale structure to produce an answer.

Every query has a reference execution, reachable by flipping a setting. That is the whole testing strategy for the milestones above G1.

The cost of all three is the rule that pays for them: no section may hold information that is not derivable from the table’s own columns. A key map is a restatement of a key column. A forward link is a restatement of a foreign key column. Neither adds a fact, which is exactly why neither can be missed when it is gone.

Re-exports

pub use adjacency::Adjacency;

pub use bits::BitVector;

pub use degree::BUCKETS;

pub use degree::Degrees;

pub use keymap::DENSE_THRESHOLD;

pub use keymap::Form;

pub use keymap::KeyMap;

pub use keymap::Keys;

pub use keymap::Observed;

pub use link::Bounds;

pub use link::Counts;

pub use link::Cursor;

pub use link::Link;

pub use rel::Cardinality;

pub use rel::Relationship;

pub use rel::Side;

pub use rel::parse_links;

pub use rid::NO_PARENT;

pub use rid::PART_ROWS;

pub use rid::Place;

pub use rid::Places;

pub use rid::Rid;

pub use rid::STRIPE_PARTS;

pub use rids::Pushed;

pub use rids::Rids;

pub use rids::SPARSE_RATIO;

pub use rids::STOP_AFTER;

pub use wire::Payload;

Modules

adjacency

The backward adjacency: for each parent row, the child rows that point at it.

bits

A bitmap, a rank index over it, and select in both directions.

degree

What a relationship knows about its own shape: the degree distribution, the certificates and the gather locality.

keymap

Turning a parent key value into a Rid.

link

The forward link: for each child row, the Rid of its parent.

rel

What a relationship is, and how one gets declared.

rid

The row id, and the structure that turns one into a physical position.

rids

A set of row ids of one table, and pushing one through a link.

wire

The bytes a key map takes in a section payload.