vaelii.impl.columnar — com.vaelii/vaelii 0.20.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 — (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.

Single-threaded, which is narrower than single-writer. The Trie fields are ^:unsynchronized-mutable, so a write publishes through no barrier: a second thread reading this index may see an array reference, a capacity or the CSR-mode flag from before a growth or a compaction, and there is no happens-before edge that would stop it. The atom- and lock-based backends give an incidental reader beside the writer a consistent view; this one does not, and it is the caller's job to keep its reads on the writer's thread or behind a synchronizer of its own. The fields are unsynchronized because the walk reads them at every frontier node, which is the index's hottest loop — a volatile read there is paid per node per lookup, to buy a guarantee the engine's own single writer never needs.

columnar-index-store clj

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

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.

drop-state-space! clj

(drop-state-space! space)

Forget the {dict, trie, roots} state held under space — the columnar twin of vaelii.impl.memory/drop-index-space!, core/close!'s release of the RAM index a disk-backed KB derived. A no-op for a space nothing holds; returns true when an entry was dropped.

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".