Evaluation: sparsemap for mentat’s entity-id sets

Status: evaluated 2026-10-15; not adopted. No dependency added.

The TODO (docs/RESUME-CHECKPOINT.md, 2026-09-27) asked whether sparsemap — the maintainer’s run-length-compressed bitmap, now 5.8.2 on crates.io as a 100% safe, no_std, dependency-free Rust port that is wire-compatible with the C library — would help mentat’s entid sets. It also asked for a benchmark on a real hot path before adding any dependency.

Where mentat holds sets of entity ids

rg 'BTreeSet<Entid>|HashSet<i64>' over the engine (tests excluded) finds 46. By role:

Site Typical size Hot? What it costs today
Query :in [?x ...] collections 1–10k per query Not a Rust set: SQLite gets a VALUES table, pg an = ANY($n) array. A bitmap can’t be passed to either.
as-of / since retraction filters log-sized per query Not a Rust set: a correlated NOT EXISTS on transactions (SQL).
Attribute cache v_es (non-unique reverse cache: value → entities) 1–100s per value read on cache hits BTreeSet<Entid> per value. Most values have a handful of entities.
pull / retractEntity visited sets (cycle guard) 1–100s per pull HashSet<i64>, a few inserts.
Schema/attribute sets (AttributeSet, auto-index indexed/rejected, value-filtered attrs) 10s per tx / query BTreeSet<Entid> of attribute ids.
pg_mentat history / as-of — per query SQL over B-tree indexes; no in-memory bitmap.

The two places the TODO hoped bitmaps would pay — the :in collections and the as-of retraction sets — are expressed in SQL and executed by SQLite/DuckDB/Postgres. They never exist as Rust sets, so a Rust bitmap has nothing to replace. What is left are small sets: cycle guards, per-value cache entries and attribute lists.

Benchmark

benchmarks/results/sparsemap-eval-2026-10-15/smbench.rs (release build; BTreeSet<u64> vs sparsemap::SparseMap 5.8.2). The four shapes mentat produces:

  • tiny: a visited set or cache entry;
  • dense: entids from one bulk transaction, contiguous in :db.part/user;
  • mixed: several transactions over time, long runs with gaps;
  • sparse: what a selective query touches across a large partition.

Measurements: build from a sorted id list; 1000 membership probes (half hits); intersection with every 3rd element. Memory: BTreeSet estimated at 24 B per element; SparseMap is its serialized size.

shape n bytes BTreeSet bytes SparseMap build bt / sm probe bt / sm and bt / sm
tiny 8 192 80 143ns / 234ns 9ns / 14ns 256ns / 97ns
tiny 64 1,536 352 534ns / 1.5us 16ns / 21ns 872ns / 275ns
dense 100k 2.4 MB 88 B 1.9ms / 3.4ms 90ns / 22ns 1.9ms / 4.9us
dense 1M 24 MB 88 B 27ms / 31ms 112ns / 11ns 12ms / 177us
mixed 100k 2.4 MB 10 KB 1.0ms / 5.1ms 51ns / 34ns 0.93ms / 47us
mixed 1M 24 MB 102 KB 15ms / 64ms 116ns / 46ns 11ms / 2.7ms
sparse 10k 240 KB 210 KB 154us / 2.8ms 50ns / 106ns 99us / 726us
sparse 100k 2.4 MB 1.1 MB 1.0ms / 19ms 201ns / 109ns 1.4ms / 12.5ms

What the numbers say:

  • Where sparsemap shines is dense and mixed sets of 100k+ ids. They are 20–270,000x smaller, probes are 2–10x faster, and intersections are 4–2400x faster. That’s exactly the shape of a bulk-loaded partition.
  • For the sets mentat actually keeps in Rust (tiny cycle guards and cache entries), it is a wash. Probes are within a few ns of BTreeSet; building is 1.5–3x slower; memory is smaller, but a few hundred bytes either way doesn’t matter.
  • On sparse sets it is worse: building is 10–20x slower, and intersection 5–9x slower. Random ids across a big partition are its worst case, and they’re the shape a selective query produces.

Decision

Don’t adopt it now (YAGNI):

  1. mentat has no large in-memory entid set on a hot path. The large sets are SQL, where the database’s own indexes and hash joins do the work.
  2. The small sets it does have see no gain on probes (the cache-hit path) and lose on builds (the per-query path).
  3. A dependency in mentat_core / mentat_db would reach every backend and every crates.io consumer for no measured win.

When to revisit

Adopt sparsemap if mentat grows an in-memory set of 100k+ entids that is dense or clustered. Candidates, none of which exist today:

  • an in-process entity-membership cache for a large attribute (e.g. “all entities with :x/kind :order”), used to prune joins before SQL;
  • a client-side as-of visibility bitmap materialized once per basis and reused across queries (the embedded engine re-derives visibility with NOT EXISTS on every query);
  • shipping a set of entids over the wire (mentatd / Quack), where the 88-byte encoding of a million-id run beats any list.

At that point, take the crates.io crate (sparsemap = "5.8", pure Rust, no -sys needed) behind a feature, and benchmark the specific path.