vaelii.impl.columnar — com.vaelii/vaelii 0.1.0

The dense columnar trie index — the :memory-columnar backend, off by default.

The flat-map index (vaelii.impl.kv) stores each trie node as three entries keyed by a boxed vector of the full path prefix; a path's every prefix is a separate object, so the structure is redundant boxed keys + HAMT overhead — bench/…/densetrie.clj measured that at ~487 MB of the 592 MB index (300k real facts), and it is the index's dominant cost. The bench also found the win is the layout, not interning: a fastutil-map-per-node recovers only 1.28×, a columnar layout ~15–20×.

So here the trie is a real node graph, not a map of prefixes:

• nodes are int ids; node data lives in grow-on-demand parallel arrays indexed by id — counts (primitive int[]), toks/tgts (a node's child edges: a sorted int[] of tokens and the parallel int[] of child node ids while the node is narrow, one primitive Int2IntOpenHashMap once it is wide), leaves (an IntPostings, the same tiered int[]/Roaring set Phase 1 uses — this is where the two phases unify);
• edges carry interned int tokens from a vaelii.impl.tokens dictionary, not boxed symbols/markers/lists; the dictionary's inverse decodes them for children.

Mutable, not a static CSR. A compressed-sparse-row trie is the densest a trie gets, but it is static — the index mutates on every assert/retract. A per-node sorted int[] supports incremental add/remove (binary-search + array splice) while still dropping the boxed prefixes and the per-node hashmap slack; the node ids of a pruned subtree are recycled through a free list. Freezing the cold majority to a true CSR is a later compaction pass (the mutable-head / compacted-tail pattern the record store already uses), justified by measuring where this lands.

A node's child structure is tiered on its width, and that is a measurement. The splice above costs O(children already there), and nothing bounds a node's width: the level-2 node holds one child per distinct first argument of a predicate, so an array-only node structure loads one broad relation — (isa X T), (genl S T), any hot relation — in time quadratic in that relation's own extent. It is the node that is expensive, not the trie: holding 200k facts fixed and varying only the widest node's fan-out, an array-only structure reads 4.2 s at 2,000 children, 9.0 s at 20,000 and 18.2 s at 200,000. So past promote-at children a node's edges become one primitive Int2IntOpenHashMap (O(1) insert, no splice) and drop back to the array pair below half of it. Blanket maps are the wrong answer in the other direction — the bench found a fastutil map per node worth 1.28× against the columnar layout's ~15–20× — and the tiering is what takes both, since the overwhelming majority of nodes are narrow and never leave the dense pair.

Composition keeps the new surface small. Only the trie families (index/unindex/lookup/count-at/children) are native here; the secondary roots, the rule / exception indexes, the inverted term index, and the term roster beside it — all flat key → set maps — delegate to an embedded KvIndexStore over a Phase-1 TieredKvBackend (int-dense postings already). index-sentex writes those root/term keys straight to the shared backend with kv/root-keys / kv/sentex-terms (and the roster ops with kv/roster-adds), so both stores key identically and the delegated reads stay consistent.

Single-writer, like every index: the arrays are mutated in place; lookup/children /leaves materialize fresh Clojure collections at the boundary. Proven set-equal to KvIndexStore by columnar_index_oracle_test.

columnar-index-store clj

(columnar-index-store {:keys [space] :or {space 1}})

A dense columnar IndexStore. :space selects the shared {dict, trie, roots} state.

columnar? clj

(columnar? store)

compact! clj

(compact! store)

Freeze a columnar index store's trie into read-optimized CSR arrays — the mutable node-linked graph collapses to flat parallel int arrays with no per-node objects. A subsequent write transparently reverts it to mutable, so this is the after-a-bulk-load, before-the-query-phase move (the 100M workload). A no-op on a non-columnar store.

csr clj

(csr store)

The compacted trie's CSR sections (:nodes :counts :offsets :edge-tok :edge-tgt :leaf-off :handles), or nil when the trie is still mutable — the snapshot writer's read. compact! first.

init-cap clj

install-csr! clj

(install-csr! store sections)

Install CSR sections into a columnar store's trie, replacing whatever it held. The leaf pair (:leaf-off* :handles*) may be heap int[] or mapped IntBuffers; the skeleton is always heap.

mapped? clj

(mapped? store)

Is this store's trie reading its leaves out of an mmap'd snapshot? True exactly while nothing has been written since the image was installed — a write thaws — so it is also the answer to "is the image on disk still what this store holds".

promote-at clj

How many child edges a trie node holds as the sorted int[] pair before its edges become one primitive hash map — and, at half of this, drop back to the pair.

The pair is the better structure while a node is narrow: two primitive arrays, no object header between them and the data, and a binary search over a run short enough to sit in a cache line or two. What it cannot do is grow cheaply, since minting an edge splices both arrays. 64 is where the two costs cross — the splice is still one short arraycopy, and a hash map's tables (over-provisioned to a 0.75 load factor, plus the object) are still bulkier than the pair they would replace, which matters because nearly every node in a real trie is on this side of the line.

Dropping back at half rather than at the same width is hysteresis: a node sitting exactly on the boundary would otherwise rebuild its whole edge structure on every add/remove pair, and one rebuild per promote-at/2 operations is amortized O(1).

PTrie clj protocol

t-lookup clj

(t-lookup t pattern)

Handles whose full path matches pattern (variables fan out; markers skip).

t-install-csr! clj

(t-install-csr! t sections)

Install CSR sections read from a snapshot (leaves may be mapped buffers).

t-leaves-at clj

(t-leaves-at t prefix)

Leaf handles exactly at a prefix (a set, #{} if absent).

t-clear! clj

(t-clear! t)

Reset to a single empty root (the dict is wiped by the store).

t-count-at clj

(t-count-at t prefix)

Subtree leaf count at a path prefix (0 if absent).

t-remove! clj

(t-remove! t path handle)

Remove handle from path's leaf, pruning nodes that empty.

t-children clj

(t-children t prefix)

Decoded child edge tokens at a prefix (a vector, [] if absent).

t-mapped? clj

(t-mapped? t)

Are the leaf columns an mmap'd snapshot rather than heap arrays?

t-compact! clj

(t-compact! t)

Freeze the mutable trie into flat CSR arrays (read-optimized, dense).

t-insert! clj

(t-insert! t path handle)

Insert a sentex handle at the leaf of path (a token seq).

t-csr clj

(t-csr t)

The frozen CSR sections as a map, or nil while mutable.