Struct KeyMap

Source

pub struct KeyMap { /* private fields */ }

Expand description

A map from a parent key value to the rid of the row that holds it.

Implementations§

Source §

impl KeyMap

Source

pub fn build(keys: &[Option<i128>]) -> Result<Self>

Builds the cheapest correct form for these keys.

keys is the parent key column in rid order, with None for a null. The rid of a value is its index, which is what makes this the whole build: the caller has already read the column in append order, so the row ids are the positions and there is nothing to look up.

String keys arrive here as dictionary codes rather than as text, per section 2.2. That is not a convenience, it is the reason a sorted key map over a VARCHAR column never touches a byte of text: the codes of a file wide stable dictionary are integers with the column’s own order, so the search is over u32.

§Errors

If the column’s values span more than a u64, if it holds more rows than a u64 of rids, or if a bit packed payload cannot be written. A non-distinct column is not an error: it produces a key map whose Observed says so, and the caller is expected to ask before building a link on it.

Source

pub fn build_from<K: Keys + ?Sized>(keys: &K) -> Result<Self>

Builds the cheapest correct form by reading the column rather than by holding it.

The same build as KeyMap::build and the same decision, taken from a source that can be scanned twice instead of from a slice that is already in memory. That difference is the whole reason this exists. A parent key column at TPC-H SF10 is fifteen million rows of orders, and a Vec<Option<i128>> of those is four hundred and eighty megabytes held for the length of a build that does not need a single one of them twice. At SF100 it is four and a half gigabytes, which is not a slow build, it is a build that does not happen.

So the first scan observes and nothing else, and what the second scan does depends on what the first one found. The identity form, which is the form every TPC-H parent key takes, needs no second scan at all: the four observed facts are the whole map. The dense form fills a bitmap sized from the range, which is bounded by the table rather than by the scan. Only the sorted form has to hold the column, because sorting is what it is, and it says so here rather than surprising a caller with it.

§Errors

If the scan fails, or for any of the reasons KeyMap::build fails.

Source

pub fn form(&self) -> Form

Which form this map took.

Source

pub fn span(&self) -> Option<(i128, u64)>

The smallest key and how many key values from it the map spans, when the keys are compact.

The identity and dense forms are the two that exist because the keys fill most of a range, at most one hole in DENSE_THRESHOLD values, so a bitmap over that range is at most that many bits a parent row. That is what lets a join test a child’s key against a set of parents with one subtraction and one bit, and with no link at all. The sorted form is the one for keys spread over a range too wide for that, and answers None.

Source

pub fn observed(&self) -> &Observed

What the build saw, which is the cardinality verification.

Source

pub fn len(&self) -> u64

Keys this map resolves.

Source

pub fn is_empty(&self) -> bool

Whether this map resolves nothing.

Source

pub fn bytes(&self) -> usize

Bytes this map holds resident, for the budget of section 3.7 and the cache of section 4.4.

Identity is twenty four bytes and says so, which is the number that makes the budget livable on TPC-H.

Source

pub fn lookup(&self, key: i128) -> Result<Option<Rid>>

The rid of the row holding this key, or None when no row holds it.

None is the ordinary answer and not an exceptional one: a child key with no matching parent is what section 2.4 reserves no parent for, and a null child key never reaches here at all.