diff options
Diffstat (limited to 'docs/partial-bindings.org')
| -rw-r--r-- | docs/partial-bindings.org | 331 |
1 files changed, 331 insertions, 0 deletions
diff --git a/docs/partial-bindings.org b/docs/partial-bindings.org new file mode 100644 index 0000000..cf9cf32 --- /dev/null +++ b/docs/partial-bindings.org @@ -0,0 +1,331 @@ +#+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_=. |