rudb_graph/lib.rs
1//! The graph layer's structures: row ids, key maps and relationships.
2//!
3//! This crate holds the data model of spec/graph/02-the-data-model.md and nothing else. It knows
4//! what a [`Rid`] is, how a [`KeyMap`] turns a parent key value into one, and what a
5//! [`Relationship`] declares. It deliberately does not know what a file, a page or a plan is:
6//! `rudb-native` at rank 6 is what puts a key map on disk and `rudb-opt` is what decides to use
7//! one, which is the right way round. A key map that could see the format would be a key map that
8//! could only be tested through one.
9//!
10//! # The invariant everything here is built on
11//!
12//! Section 3.1: deleting every graph section from a rudb file must change no answer, only the time.
13//! That one sentence is what makes this layer safe to build incrementally, and it has four
14//! consequences worth stating where the code is rather than only in the specification.
15//!
16//! A wrong index is a performance bug and not a wrong answer. Nothing in this crate is ever the
17//! only path to a row: a link join is a faster way to compute what a hash join computes, so a link
18//! that resolves the wrong `rid` shows up as a differential test failure against the same query
19//! with the graph sections turned off, which is a test that can exist because of the invariant.
20//!
21//! Staleness is handled by ignoring. A section carries a generation stamp, and a section whose
22//! stamp does not match the table's is dropped rather than repaired. There is no repair path in
23//! this crate, no incremental maintenance, and no way for a stale structure to produce an answer.
24//!
25//! Every query has a reference execution, reachable by flipping a setting. That is the whole
26//! testing strategy for the milestones above G1.
27//!
28//! The cost of all three is the rule that pays for them: no section may hold information that is
29//! not derivable from the table's own columns. A key map is a restatement of a key column. A
30//! forward link is a restatement of a foreign key column. Neither adds a fact, which is exactly why
31//! neither can be missed when it is gone.
32
33pub mod adjacency;
34pub mod bits;
35pub mod degree;
36pub mod keymap;
37pub mod link;
38pub mod rel;
39pub mod rid;
40pub mod rids;
41mod tail;
42pub mod wire;
43
44pub use adjacency::Adjacency;
45pub use bits::BitVector;
46pub use degree::{BUCKETS, Degrees};
47pub use keymap::{DENSE_THRESHOLD, Form, KeyMap, Keys, Observed};
48pub use link::{Bounds, Counts, Cursor, Link};
49pub use rel::{Cardinality, Relationship, Side, parse_links};
50pub use rid::{NO_PARENT, PART_ROWS, Place, Places, Rid, STRIPE_PARTS};
51pub use rids::{Pushed, Rids, SPARSE_RATIO, STOP_AFTER};
52pub use wire::Payload;