The key-value substrate the index rests on, and the one IndexStore
implementation written over it.
The index — the trie, the secondary roots, the rule predicate index, the exception
re-check index, and the inverted term index — is all sets and counters keyed
by structured vectors. KvIndexStore encodes that structure once, in terms of a
small KvBackend protocol; a backend is then just an adapter that says how a
scalar, a counter, and a set live in some store. An in-memory map
(vaelii.impl.memory) and an on-disk WAL (vaelii.impl.disk.kv) are two such
adapters; a SQL or overlay backend is another.
A sentex is indexed by its trie path. The trie is flattened — every node, identified by its path prefix, is exactly three keys:
count-key [:trie :count prefix] -> integer: how many sentexes live at the leaves under this prefix (selectivity without walking). set-key [:trie :children prefix] -> a SET: the next possible token labels (the node's child edges). leaf-key [:trie :handles prefix] -> a SET: the handles of the sentexes whose path ends exactly here.
Child edges and leaf handles are separate keys because the trie is ragged.
Paths differ in length with arity, so one sentex's full path can be a proper
prefix of another's: (rel A B) in CeeContext keys as [rel A B CeeContext],
and (rel A B CeeContext X) in DeeContext keys as [rel A B CeeContext X DeeContext] — the first path is an interior node of the second. Storing both
handles and child labels in one set therefore mixed them, and a caller could not
tell them apart by type (a handle is an integer, and so is the token 1970). Two
keys make the distinction structural: lookup reads only the leaf key at its
terminus, so it can never return a token as a handle, and children reads only
the child set, so plan's fan-out divisor can never count a handle as a branch.
Alongside the trie sit the secondary roots, the rule predicate index, the
exception re-check index, and the inverted term index — all flat sets whose
cardinality is their own size. One more flat set, the term roster
[:term-roster], holds the term index's names rather than handles, so the
vocabulary can be listed and counted in O(terms) instead of a walk over every record.
Contract: lookup expects a full path (sentence tokens + a context slot; the context may itself be a variable). A short pattern terminates on an interior node, whose leaf key is empty, so it yields nothing rather than that node's child labels dressed up as handles.
KvBackendLogical keys are structured vectors and set members are bare values; a backend
turns those into whatever its store wants (an in-memory map uses them directly; the
on-disk backend nippy-frames them into its log). The load-bearing ops are
kv-batch (the whole index write for one sentex lands as one unit — one batched
write) and kv-intersect (the multi-column narrowing sentexes-with-args needs, one
set intersection rather than N fetch-and-filter reads). A batch op is a vector
[op key & args] with op one of :put, :delete, :increment,
:decrement, :add-to-set, :remove-from-set; kv-batch
returns one reply per op in order (only :increment/:decrement replies — the post-op
counter value — are read; the rest are placeholders that keep the vector aligned).
kv-member? is a membership test, not a fetch, and it is its own op because on
several backends those cost different orders. exception-rule? is the gate
chain/rule-view-of takes once per candidate rule per new datum, so answering it by
materializing the roster and testing the result makes forward chaining a product of
two KB-sized quantities. A flat-map backend hands the stored set back by reference
and hides the distinction entirely; a dense one holds the roster as an IntPostings,
where 1e5 gate calls against a roster of 1,000 cost 15,926 ms built-then-tested
against 87 ms on the flat map — so the op exists to let each backend answer with the
probe it already has (a hash lookup, a binary search, a bitmap test).
The key-value substrate the index rests on, and the one `IndexStore`
implementation written over it.
The index — the trie, the secondary roots, the rule predicate index, the exception
re-check index, and the inverted term index — is *all* sets and counters keyed
by structured vectors. `KvIndexStore` encodes that structure once, in terms of a
small `KvBackend` protocol; a backend is then just an adapter that says how a
scalar, a counter, and a set live in some store. An in-memory map
(`vaelii.impl.memory`) and an on-disk WAL (`vaelii.impl.disk.kv`) are two such
adapters; a SQL or overlay backend is another.
## The flattened count-aware trie
A sentex is indexed by its trie path. The trie is flattened — every node,
identified by its path prefix, is exactly three keys:
count-key [:trie :count prefix] -> integer: how many sentexes live at the leaves
under this prefix (selectivity without walking).
set-key [:trie :children prefix] -> a SET: the next possible token labels (the
node's child edges).
leaf-key [:trie :handles prefix] -> a SET: the handles of the sentexes whose path
ends exactly here.
**Child edges and leaf handles are separate keys because the trie is ragged.**
Paths differ in length with arity, so one sentex's *full* path can be a proper
prefix of another's: `(rel A B)` in `CeeContext` keys as `[rel A B CeeContext]`,
and `(rel A B CeeContext X)` in `DeeContext` keys as `[rel A B CeeContext X
DeeContext]` — the first path is an interior node of the second. Storing both
handles and child labels in one set therefore mixed them, and a caller could not
tell them apart by type (a handle is an integer, and so is the token `1970`). Two
keys make the distinction structural: `lookup` reads only the leaf key at its
terminus, so it can never return a token as a handle, and `children` reads only
the child set, so `plan`'s fan-out divisor can never count a handle as a branch.
Alongside the trie sit the secondary roots, the rule predicate index, the
exception re-check index, and the inverted term index — all flat sets whose
cardinality is their own size. One more flat set, the **term roster**
`[:term-roster]`, holds the term index's *names* rather than handles, so the
vocabulary can be listed and counted in O(terms) instead of a walk over every record.
Contract: lookup expects a *full* path (sentence tokens + a context slot; the
context may itself be a variable). A short pattern terminates on an interior
node, whose leaf key is empty, so it yields nothing rather than that node's child
labels dressed up as handles.
## The `KvBackend`
Logical keys are structured vectors and set members are bare values; a backend
turns those into whatever its store wants (an in-memory map uses them directly; the
on-disk backend nippy-frames them into its log). The load-bearing ops are
`kv-batch` (the whole index write for one sentex lands as one unit — one batched
write) and `kv-intersect` (the multi-column narrowing `sentexes-with-args` needs, one
set intersection rather than N fetch-and-filter reads). A batch op is a vector
`[op key & args]` with `op` one of `:put`, `:delete`, `:increment`,
`:decrement`, `:add-to-set`, `:remove-from-set`; `kv-batch`
returns one reply per op in order (only `:increment`/`:decrement` replies — the post-op
counter value — are read; the rest are placeholders that keep the vector aligned).
**`kv-member?` is a membership test, not a fetch**, and it is its own op because on
several backends those cost different orders. `exception-rule?` is the gate
`chain/rule-view-of` takes once per candidate rule per new datum, so answering it by
materializing the roster and testing the result makes forward chaining a product of
two KB-sized quantities. A flat-map backend hands the stored set back by reference
and hides the distinction entirely; a dense one holds the roster as an `IntPostings`,
where 1e5 gate calls against a roster of 1,000 cost 15,926 ms built-then-tested
against 87 ms on the flat map — so the op exists to let each backend answer with the
probe it already has (a hash lookup, a binary search, a bitmap test).Which key shapes this build's index is written in.
The key families below — [:trie :count|:children|:handles prefix], the roots, the
rule / exception indexes, the term index and the roster — are the index's portable
form, so a dump of them is only readable by a build that agrees on them. An index
written in a layout this build does not use reads as empty rather than as wrong
(a lookup finds no key and answers nothing), which is fail-safe and undiagnosable —
so the layout is stated as a number and checked, rather than discovered by a KB that
quietly stopped answering.
Bump it whenever a key shape changes: a new family, a renamed tag, a different arity, or a different value type at an existing key.
Which key shapes this build's index is written in. The key families below — `[:trie :count|:children|:handles prefix]`, the roots, the rule / exception indexes, the term index and the roster — *are* the index's portable form, so a dump of them is only readable by a build that agrees on them. An index written in a layout this build does not use reads as **empty** rather than as wrong (a lookup finds no key and answers nothing), which is fail-safe and undiagnosable — so the layout is stated as a number and checked, rather than discovered by a KB that quietly stopped answering. **Bump it whenever a key shape changes**: a new family, a renamed tag, a different arity, or a different value type at an existing key.
The key-value operations KvIndexStore bottoms out on. Keys are structured
vectors; set members are bare values. Each adapter maps those onto its store.
The key-value operations `KvIndexStore` bottoms out on. Keys are structured vectors; set members are bare values. Each adapter maps those onto its store.
(kv-add-to-set b k member)Add member to the set at k.
Add `member` to the set at `k`.
(kv-batch b ops)Apply the write ops [op key & args] as one unit; return the replies in order.
Apply the write ops `[op key & args]` as one unit; return the replies in order.
(kv-intersect b ks)The intersection of the sets at ks, as a set.
The intersection of the sets at `ks`, as a set.
(kv-clear! b)Remove every entry.
Remove every entry.
(kv-entries b)Every entry as a lazy [key value] seq; set values as Clojure sets, counters as longs.
Every entry as a lazy `[key value]` seq; set values as Clojure sets, counters as longs.
(kv-get b k)The value at k, or nil.
The value at `k`, or nil.
(kv-member? b k member)Is member in the set at k? — answered without building the set.
Is `member` in the set at `k`? — answered without building the set.
(kv-decrement b k)Decrement the counter at k; return the new value.
Decrement the counter at `k`; return the new value.
(kv-put b k v)Set k to v.
Set `k` to `v`.
(kv-count b k)The cardinality of the set at k (0 when absent).
The cardinality of the set at `k` (0 when absent).
(kv-delete b k)Delete k.
Delete `k`.
(kv-members b k)The members of the set at k, as a set (empty when absent).
The members of the set at `k`, as a set (empty when absent).
(kv-increment b k)Increment the counter at k; return the new value.
Increment the counter at `k`; return the new value.
(kv-load b entries)Install [key value] entries into an empty backend, in this backend's representation.
Install `[key value]` entries into an empty backend, in this backend's representation.
(kv-remove-from-set b k member)Remove member from the set at k (dropping the key when it empties).
Remove `member` from the set at `k` (dropping the key when it empties).
(root-keys sentex)The secondary-root keys a sentex belongs to: its context always, plus — for a
fact — its functor and each indexable top-level argument by 1-based position.
A negative fact roots under its positive body's functor (polarity lives in the
record), so sentexes-with-functor covers both polarities. A rule contributes
only its context; its predicates live in the rule index instead.
The secondary-root keys a sentex belongs to: its context always, plus — for a *fact* — its functor and each indexable top-level argument by 1-based position. A negative fact roots under its positive body's functor (polarity lives in the record), so `sentexes-with-functor` covers both polarities. A rule contributes only its context; its predicates live in the rule index instead.
(roster-adds backend terms)The write ops entering terms (one sentex's, from sentex-terms) in the roster —
read BEFORE their postings are written, so a name is entered exactly by the first
sentex to mention it.
The write ops entering `terms` (one sentex's, from `sentex-terms`) in the roster — read BEFORE their postings are written, so a name is entered exactly by the first sentex to mention it.
(roster-retires backend terms handle)The write ops retiring the names in terms that handle is the last mention of —
read BEFORE their postings are removed, so a name dies exactly when its posting is
#{handle}.
The write ops retiring the names in `terms` that `handle` is the last mention of —
read BEFORE their postings are removed, so a name dies exactly when its posting is
`#{handle}`.(sentex-terms sentex)The distinct terms that make a sentex findable: its indexable content terms (see sentex/index-terms — connective-free, no numbers/strings/variables) plus its context.
The distinct terms that make a sentex findable: its indexable content terms (see sentex/index-terms — connective-free, no numbers/strings/variables) plus its context.
(term-key term)cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |