A dense in-memory KvBackend (vaelii.impl.kv) — the :dense index axis, under either
record store (:memory-dense, :disk-dense).
The index's handle-set families (trie leaves, the context / functor / argument roots, the
rule and exception indexes) are the bulk of its RAM, and a bake-off across candidate
encodings found a packed sorted int[] ~5.6× denser than the
PersistentHashSet<Long> the memory backend stores, with RoaringBitmap winning only the
few large/hot postings. So a handle set here is an IntPostings: an exact sorted int[]
while small, promoted to a RoaringBitmap once it crosses a threshold (dense for large,
O(log) add, fast intersect). The trie's child-label set ([:trie :children …]) holds tokens —
including numbers — not handles, so it stays an ordinary set; counters stay Longs. The
backend dispatches on the key tag.
kv-intersect narrows in that representation rather than in the sets it would make:
RoaringBitmap/and where both sides are hot, a sorted merge where both are cold, and a
probe of the cold side into the bitmap where the tiers differ, and a binary search of the
short run into the long one where neither is a bitmap. Smallest posting first, and one
Clojure set built at the end at the size of the answer. What that buys is not mainly
speed on the big case (hot ∩ hot at 32k: 29.2 → 0.56 ms) but the shape of the common
one: a query binds a rare argument on a hot predicate, and 4 handles against a root of n
went from 4.73 ms at n=32,000 to 0.0015 ms at any n — flat in the extent the argument
roots exist to avoid scanning. lein perf --only intersect-selectivity is the perf check
that enforces that, and what cost is left tracks the answer rather than the columns, which is the
boundary contract and not the narrowing.
Off by default (:index :dense); proven set-equal to MemoryKvBackend by
dense_kv_oracle_test. Single-writer: the int structures are mutated in place, and
kv-members / kv-intersect materialize a fresh Clojure set at the boundary so a caller
never holds the mutable structure. Handles fit int through 2³¹ (≫ 100M).
A dense in-memory `KvBackend` (`vaelii.impl.kv`) — the `:dense` index axis, under either record store (`:memory-dense`, `:disk-dense`). The index's handle-set families (trie leaves, the context / functor / argument roots, the rule and exception indexes) are the bulk of its RAM, and a bake-off across candidate encodings found a **packed sorted `int[]`** ~5.6× denser than the `PersistentHashSet<Long>` the memory backend stores, with `RoaringBitmap` winning only the few large/hot postings. So a handle set here is an `IntPostings`: an exact sorted `int[]` while small, promoted to a `RoaringBitmap` once it crosses a threshold (dense for large, O(log) add, fast intersect). The trie's child-*label* set (`[:trie :children …]`) holds tokens — including numbers — not handles, so it stays an ordinary set; counters stay `Long`s. The backend dispatches on the key tag. `kv-intersect` narrows **in that representation** rather than in the sets it would make: `RoaringBitmap/and` where both sides are hot, a sorted merge where both are cold, and a probe of the cold side into the bitmap where the tiers differ, and a binary search of the short run into the long one where neither is a bitmap. Smallest posting first, and one Clojure set built at the end at the size of the answer. What that buys is not mainly speed on the big case (hot ∩ hot at 32k: 29.2 → 0.56 ms) but the *shape* of the common one: a query binds a rare argument on a hot predicate, and 4 handles against a root of n went from 4.73 ms at n=32,000 to 0.0015 ms at any n — flat in the extent the argument roots exist to avoid scanning. `lein perf --only intersect-selectivity` is the perf check that enforces that, and what cost is left tracks the answer rather than the columns, which is the boundary contract and not the narrowing. Off by default (`:index :dense`); proven set-equal to `MemoryKvBackend` by `dense_kv_oracle_test`. Single-writer: the int structures are mutated in place, and `kv-members` / `kv-intersect` materialize a fresh Clojure set at the boundary so a caller never holds the mutable structure. Handles fit `int` through 2³¹ (≫ 100M).
(dense-index-store opts)A dense in-memory IndexStore — KvIndexStore over a TieredKvBackend.
A dense in-memory `IndexStore` — `KvIndexStore` over a `TieredKvBackend`.
(dense-kv-backend {:keys [space] :or {space 0}})A dense in-memory KvBackend. Only :space matters (selects the shared state atom).
A dense in-memory `KvBackend`. Only `:space` matters (selects the shared state atom).
(drop-index-space! space)Forget the derived index state held under space — the dense 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.
Forget the derived index state held under `space` — the dense 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.
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 |