#+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. Its key keeps the encoded value rather than a hash of it, so that
ranges stay possible later, given 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]]'s =fold_left= takes an optional start and stop.

#+begin_src ocaml
val fold_left :
  ?from:K.t ->
  ?until:(K.t -> bool) ->
  S.transaction ->
  ('c -> K.t -> address -> 'c) ->
  '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. 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.

** Index trees
The index on an attribute =a= is a tree whose key is the encoded value
of =a= followed by the raw hash of the tuple, and whose value is that
hash.

#+begin_example
book(title, author), index on title

ts4:Codd ++ hash(t₁)   →  hash(t₁)
ts4:Codd ++ hash(t₂)   →  hash(t₂)
ts4:Date ++ hash(t₃)   →  hash(t₃)
#+end_example

- The value is encoded as a tuple encodes its values, with
  =Tuple.bencode_of_value=. Bencode is injective and no encoding is a
  prefix of another, so the keys of one value are contiguous, and the
  index is a =Merkle.Make= over =StringKey=, which compares strings byte
  by byte.
- 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 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= hashes each tuple once, builds the tuple set, and then one
  index per attribute of the heading. A tuple with no value for some
  attribute is refused with =missing-attribute=.
- =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 encoded =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. A restriction
  asked of a stored program therefore reaches the stored relations the
  program reads. 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 bound
  attributes taken out of each =bound=, by =Mode.given=, since the binding
  supplies their values and the index produces the tuples. ={a; Finite}=
  becomes ={∅; Finite}=. Otherwise 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.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_=.