#+TITLE: Partial bindings
* Purpose
A partial binding gives values to some attributes of a relation and
leaves the rest free. Asking =shelved= for the tuples where
=title = "Codd"=, with the shelf free, is one. Both [[file:denial.org::*Incremental checking][incremental denial
checking]] and [[file:maintenance.org][incremental maintenance]] are built from such questions.
This document says why answering a partial binding well takes indexes,
where the binding itself belongs, how RNT stores and reads its indexes,
and what is still missing, including builds that do not fit in memory.
* Why a partial binding needs an index
A [[file:../lib/kernel/SubstantialRelation.ml][substantial relation]] keeps its tuples in a tree keyed by the hash of
each whole tuple.
- With every attribute bound, the hash can be computed, and the answer
is one path down the tree. That is =contains=, and it costs the depth
of the tree.
- With some attribute free, there is no hash to compute. The hash
scatters tuples uniformly, so the tuples that agree with the binding
sit in arbitrary leaves, and every leaf has to be read.
Correctness does not need an index. Filtering a scan answers any
binding, at the cost of reading the whole relation, and two questions
show what that costs.
- An incremental check on the denial of a book shelved twice turns the
insertion of =shelved("Codd", "A")= into =shelved(title="Codd", shelf=_)=.
Without an index, every commit that shelves a book scans all of
=shelved=.
- Asking whether ={title: "Codd"}= belongs to =book= projected on =title=
reads all of =book=, as [[file:modes.org::*Modes of a FOL plan][the modes of a FOL plan]] describe.
An index holds the same tuples ordered by the value of one attribute.
All the tuples with =a = v= are then contiguous, and answering the
binding means seeking to the first of them and walking until the value
changes. That costs the depth of the tree plus the number of matches.
* Where a binding belongs
A binding is an equality condition on some attributes, and a condition
on tuples belongs to a query language. RNT does not ask every relation
to answer one. [[file:../lib/evaluators/FOL.ml][FOL]] states it with a term of its own, and a stored
relation offers its indexes to whoever reads it.
An earlier design had every relation answer a binding-aware read, so
that the kernel could ask a denial in any language for its tuples under
a binding. That buys nothing. The rules that turn a change into
bindings are written operator by operator for each language, as
[[file:maintenance.org::*Deltas][maintenance]] shows, and the kernel cannot derive them for a program it
cannot read. Incremental checking is therefore something an evaluator
offers, and an evaluator that knows its own plans passes a binding
through them without the kernel's help.
* Indexing every attribute
Every attribute of a substantial relation gets an index. Three reasons
make that the right default rather than a choice per relation.
- The indexes of a relation are then a function of its tuples and its
heading alone. Their roots sit in the relation's record, and so in
its address, without changing what the address means, since two
relations with the same tuples have the same indexes. That holds
only while the shape of a tree depends on its keys alone, which
[[file:maintenance.org::*Checking it][Merkle does not promise yet]].
- Each index adds the mode ={a; Finite}=, and a FOL projection keeps it
whenever it keeps =a=.
- A binding over several attributes reads the index of one of them and
filters on the rest, so indexes on combinations are not needed yet.
RNT has no NULLs, so every tuple appears in every index, and no index
is sparse.
** Equality only
A mode binds attributes to values. It cannot say that an attribute lies
in a range, and [[file:../lib/concepts/Value.mli][Value]] has only =equal=, with no order, least of all
between strings and integers. An index therefore answers equality
alone, and its key holds a hash of the value rather than the value
itself. Every key then has the same length, however long the value,
which keeps both the nodes and their [[file:../lib/kernel/Merkle.ml][chunking]] cheap. Ranges would need
another index, keyed by an encoding that sorts in value order, and
modes that can state a range.
** Inside the relation
An index is not an object of its own in the kernel. It is derived from
the tuples, and an index that could be published or removed at a path
could disagree with them, which only access checks could prevent. The
relation keeps its indexes and reads them on request.
** Selectivity
Modes carry no cost. An index on a boolean attribute declares the same
={a; Finite}= as one on a key, and nothing can prefer the selective one.
A restriction on several attributes reads the index of whichever bound
attribute the relation lists first. Counts of entries kept in the nodes
of each tree would give estimates later.
* What RNT has
** Walking a range of a tree
[[file:../lib/kernel/Merkle.ml][Merkle]] walks a tree with =foldm_left=, which takes an optional start
and stop.
#+begin_src ocaml
val foldm_left :
?from:K.t ->
?until:(K.t -> bool) ->
S.transaction ->
('c -> K.t -> address -> ('c, Concepts.Condition.condition) result) ->
'c ->
node ->
('c, Concepts.Condition.condition) result
#+end_src
The walk starts at the first key not below =from= and stops before the
first key =until= accepts, or at the first error. In a trunk it descends
only into the child that holds =from=, using the same rule as =lookup=,
and once it stops it fetches no further children. Without either, it is
the whole walk it always was. =fold_left= is the same walk with a step
that cannot fail, and the =fold_left= of =Merkle.Interface= takes the same
range and reads the value at each address it passes.
** Index trees
The index on an attribute =a= is a tree whose key is the raw hash of the
encoded value of =a= followed by the raw hash of the tuple, and whose
value is the hash of the tuple.
#+begin_example
book(title, author), index on title
hash("Codd") ++ hash(t₁) → hash(t₁)
hash("Codd") ++ hash(t₂) → hash(t₂)
hash("Date") ++ hash(t₃) → hash(t₃)
#+end_example
- The value is encoded as a tuple encodes its values, with
=Tuple.bencode_of_value=, and hashed. Every key is two hashes long, so
the keys of one value are contiguous, and the index is a
=Merkle.Interface= over =StringKey=, which compares strings byte by
byte, and over tuples.
- The hash of a tuple is the address under which the tuple set stored
it, so an index entry points at the stored tuple, and no tuple is
stored twice. The index is built over those addresses, with the
=of_list= of its =Tree=, so that building it stores nothing but nodes.
- The record of a substantial relation holds one root per attribute
beside the tuple set.
#+begin_src ocaml
type t =
{ schematics: Concepts.Hash.hash;
tuples: TupleSet.address;
indexes: Index.address BatMap.String.t }
#+end_src
- =store= first checks every tuple against the heading. A tuple with no
value for some attribute is refused with =missing-attribute=, and one
with an attribute the heading lacks with =unexpected-attribute=, before
anything is written. It then hashes each tuple once, builds the tuple
set, and one index per attribute of the heading.
- =instantiate= stores no tuples under the heading its schema
describes, so an empty relation has empty indexes.
- =modes= adds ={a; Finite}= for each index the record holds.
A relation stored before indexes has no =indexes= field and does not
load, as [[file:denial.org::*Multigroups from before denials][multigroups from before denials]] do not.
** Reading an index
A substantial relation offers the [[file:../lib/protocols/Indexed.mli][Indexed]] protocol.
#+begin_src ocaml
class type implementation = object
method indexes : string list
method lookup : string -> Concepts.Value.value -> (Handle.t, Concepts.Condition.condition) result
end
#+end_src
=lookup a v= returns a cursor over the tuples whose =a= is =v=. It walks
the index on =a= from the hash of =v= until a key no longer starts with
it, and reads each tuple at the address its entry holds. An attribute
with no index is refused with =unindexed-attribute=. =indexes= names the
attributes that have one, so that a reader can choose without asking.
** Restriction in FOL
FOL has a term that restricts a plan to the tuples agreeing with a
binding, named after the =WHERE= of Tutorial D.
#+begin_src ocaml
type binding = Concepts.Value.value BatMap.String.t
type 'r term =
| Base of 'r
| Project of 'r term * string BatFingerTree.t
| Where of 'r term * binding
#+end_src
- A binding may name only attributes of the heading it restricts, and
=describe= refuses any other with =unknown-attribute=.
- =instantiate= pushes each =Where= below a =Project= that keeps every
attribute it binds, once stored programs are expanded, and merges it
into a =Where= it meets when their bindings agree. A restriction asked
of a stored program therefore reaches the stored relations the
program reads as one binding. A =Where= that binds an attribute the
projection drops stays where it is and is refused.
- A =Where= over a =Base= reads the base relation itself. If it offers an
index on a bound attribute, the restriction looks that value up.
Otherwise it enumerates. Either way it keeps only the tuples that
agree with the whole binding.
- Its membership test checks the binding, then asks its input.
- Through an index, its modes are those of the base with the attribute
the index reads taken out of each =bound=, by =Mode.given=, since the
binding supplies its value and the index produces the tuples.
={a; Finite}= becomes ={∅; Finite}=. The other bound attributes stay in
each =bound=, because they only filter what the index produces and
cannot make it end. Without an index, it keeps the modes of its input,
since it can only filter what that input enumerates.
A denial written as =Where (Base book, {title: "Codd"})= is therefore
exhaustible with nothing bound, and judging it reads only the index
entries for ="Codd"=.
* Memory
** Reading
An index is a tree in storage like the tuple set, and LMDB maps it in
as it is read. A lookup holds one path and the leaf it is in, a few
nodes of some kilobytes each, whatever the size of the index. A value
that matches half the relation streams through the cursor rather than
being collected. Its cost is a matter of [[*Selectivity][selectivity]], not of memory.
** Building today
=store= receives its tuples as a list, so the relation is in memory
before any index is built. =TupleSet.of_list= and =Index.Tree.of_list= then
insert one entry at a time inside =with_batch=. Each insert persists the
whole path to its leaf, and the batch keeps every version of every node
until it flushes, so a build holds about =N × depth= nodes of some 64
entries each rather than =N= entries. The indexes are built one after
another, so the peak is the tuple list, the entries of one index, and
one batch.
** Steady state
With [[file:roadmap.org::*2. Tuple deltas][tuple deltas]], a commit would insert and remove its changed tuples
in the tuple set and in each index, touching about the size of the
change times the depth of the tree in each. Nothing would be rebuilt.
** Builds that do not fit
Some builds start from nothing: an import, a relation materialized for
the first time, a relation stored before indexes, or a new kind of index
added later. Three things in them outgrow memory, and RNT handles none of
them yet.
| What grows | Why | What to do |
|-------------------------------+-------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------|
| The input to sort | entries arrive in the order of the tuple hash, and each index needs them in the order of its own key | sort externally: write sorted runs to scratch storage and merge them into the builder; a scratch LMDB database can do the sort at first |
| The builder | building by repeated =insert= copies a path on each insert and keeps every version | build bottom-up from the sorted stream, holding one node per level |
| The batch and the transaction | =with_batch= keeps every node it makes until the end, and one transaction holds every page it writes | write nodes directly, in short transactions of a bounded number of entries |
Writing outside the commit's own transaction is safe because nodes are
content addressed. Nothing reaches a node until the head moves to a
state that holds it, and the head moves atomically. A build that fails
leaves nodes nothing reaches, which a garbage collector has to reclaim.
A publish that fails already leaves such nodes today, since each level
of a commit writes in its own transaction.
A bottom-up build must make the same tree that inserting the same keys
would, or the address of a relation would depend on how it was built.
** What storing a relation reads
=Multigroup= stores a relation by reading it whole, and that read is
easy to misjudge.
- A relation with an address never reaches the read. Its admission
stores it as that address.
- A program is stored as its source, and is not read either.
- What is read is a relation with neither: a literal, whose tuples are
already in memory, or a lazy relation, such as the result of a query,
read for the first time.
The large read is the caller's. [[file:../lib/kernel/Scope.mli][Scope.publish]] binds whole relations and
FOL has no union, so adding one tuple to a stored relation means
reading all of it into a literal first.
** Delta relations
A delta relation would be a stored relation, its base, together with
the tuples to insert, =I=, and the tuples to delete, =D=.
#+begin_example
t ∈ delta ⇔ t ∈ I ∨ (t ∈ base ∧ t ∉ D)
#+end_example
Its membership is decided by lookups, without reading the extension.
Admission would store it by applying =I= and =D= to the tree of the base
and to each of its indexes, reading only the change, and =publish= would
take one in place of a whole relation.
* Reuse for maintenance and checking
Views in RNT are [[file:../lib/kernel/EphemeralRelation.ml][ephemeral relations]], and [[file:maintenance.org][incremental maintenance]]
would materialize them. Each piece above is one that maintenance and
incremental checking need.
- Delta rules are restrictions. =ΔR⁺ ⋈ S= asks =S= for the tuples that
agree with each inserted tuple of =R= on the join attributes, which is
a =Where= on =S=, answered from its index.
- A denial check for an inserted tuple is the denial restricted by the
binding that tuple implies, stopped at its first tuple. For a FOL
denial, the restriction passes through its plan to the stored
relations it reads.
- Applying a change to a materialized view would be admitting a delta
relation, with =ΔV⁺= and =ΔV⁻= as =I= and =D=.
- A materialized view stored as a substantial relation has indexes of
its own, maintained by the same change, so a view over a view stays
incremental.
- Deleting through a projection asks how many tuples of the input
produce a tuple of the view. That binds every attribute of the view,
so it is a lookup by hash.
- With the index roots in the address, comparing a maintained view
with the same view recomputed from scratch, as [[file:maintenance.org::*Checking it][checking it]] proposes,
tests the maintenance of its indexes too.
A view that is not materialized needs none of this. A restriction
passes through its plan, and it pays for the computation on each read.
* What is missing
1. Read sets, so that RNT knows which denials a commit can break and
how an inserted tuple binds each of them.
2. Tuple deltas, and delta relations to carry them in a commit.
3. A check offered by the evaluator: given the tuples a commit inserted
into the relations a denial reads, restrict the denial by each and
read its first tuple.
4. Joins in FOL. Most rules worth checking incrementally join two
relations, and a restriction through a join binds both sides on the
join attributes.
5. Builds that do not fit in memory, once there is a large or lazy
source to build from.
* Open questions
- Where a materialized view keeps its counts. If a count lives in the
record a tuple set points to, a change of count changes that address.
Index entries should point to the tuple itself, so that a count can
change without touching any index.
- When indexes on combinations of attributes earn their place.
- What collects the nodes that failed builds and failed publishes leave
behind.
- A tuple's =type_= is part of its hash and not of its heading. Two
tuples that differ only in =type_= agree with every binding, so
={all; Bounded 1}= holds only while the tuples of a relation share
one =type_=.
