Module keymap 

Turning a parent key value into a Rid.

A link is built from an equality between a child column and a parent column, and to build it the parent column’s values have to become row ids. That map is the key map. It has the three physical forms of spec/graph/02-the-data-model.md section 2.2, chosen by measurement at build time rather than by declaration, and the form that was chosen is recorded in the header so that a reader does not have to guess.

The three exist because they are three different answers to the same question and the cheapest one is usually available:

• Form::Identity when the keys are exactly base .. base + n in order. Nothing is stored but two numbers, and TPC-H hits this on six of its eight tables.
• Form::Dense when the keys are distinct integers packed densely enough into a range that a bitmap plus a rank index beats storing them.
• Form::Permuted when the keys are dense in their range the way the second form needs, but the rows are not stored in key order. The same bitmap and rank, and then a permutation from rank to rid, because a rank is a rid only while the rows are in key order.
• Form::Sorted for everything else, including every string key, which arrives here as dictionary codes rather than as text.

The fourth exists because the stored order is a choice, and spec/graph/12-the-order-the-suite- asks-for.md section 12.5 makes it one. orders stored by date holds the same keys orders stored by key does, and a map that answered one in constant time and needed the budget four times over for the other would make the layer depend on the order it was supposed to be free to pick.

What is deliberately absent is a hash. A minimal perfect hash is faster to probe than the sorted form and much slower to build, and there is no measurement yet saying the probe is where the time goes. spec/graph/11-open-questions.md keeps it open, and adding it later costs nothing because the form is a tag in a header that a reader is already required to be able to not recognize.

Structs

KeyMap

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

Observed

What the build saw while it read the parent key column.

Enums

Form

Which of the three physical forms a key map took.

Constants

DENSE_THRESHOLD

How dense a range has to be before the bitmap form beats the sorted form.

Traits

Keys

A parent key column that can be read more than once, in rid order.