Architecture

This page explains the storage thesis and the join / evaluation strategies. It is a qualitative description; see tests/bench.c for the demonstration benchmark harness rather than this site for numbers.

The storage thesis: fixed-width big-endian keys

The linchpin of the engine is that every fact of arity a is encoded as one fixed-width key of 4*a bytes — each column a u32 in big-endian byte order, laid out in column order with no inter-column separator, plus a trailing \0 guard.

Because the columns sit at known byte offsets, “bind the first k columns to constants and enumerate the rest” becomes exactly a byte-prefix lookup on the relation’s DAFSA. The DAFSA’s two strongest primitives — exact-key lookup and prefix enumeration — are precisely the two most common join access patterns.

One DAFSA per relation

Each relation R of arity a_R has its own DAFSA, plus its own write-ahead log. Per-relation DAFSAs preserve prefix-enum selectivity, isolate compaction, and keep schema / arity / permutation-index metadata clean.

A separate symbol DAFSA maps interned strings to u32 symbol ids — a forward str→sym DAFSA plus a reverse sym→str array.

Why the DAFSA makes the store compact

The DAFSA is a minimized acyclic DFA: during construction, states with identical outgoing transition structures are merged into one shared state. Because every fact is a fixed-width key ending in a common \0 guard, the tails of keys that share a suffix collapse into a single path. A relation of N facts whose keys share long common suffixes stores those suffixes once, not N times.

Concretely: a store with thousands of edge(a,b) tuples that all fan out over the same few destination columns keeps the shared tail states exactly once. The whole database is the sum of these per-relation DAFSAs (plus the interner), and the read path is mmap’d zero-copy — there is no secondary index to maintain and no deserialization; the DAFSA bytes on disk are the queryable structure. This is what lets the engine serve reads as fast as a fact store can, from a footprint that is a fraction of a raw row store for suffix-heavy data.

The trade-off: a minimized DAG is not a B-tree. It gives exact-key lookup and prefix enumeration at O(key length), and (via the order-statistics subtree arrays) rank / select / range in time logarithmic in the number of distinct tuples — but it deliberately does not provide arbitrary-value random access. Order statistics and the sorted iterator close most of that gap; see Order Statistics.

Lifecycle: load → compile → publish → serve

1. Load facts into a database directory (dl_load_facts bulk CSV, or incremental dl_add_fact / dl_delete_fact).
2. Declare relations and compile rules (dl_load_rules + dl_compile), running the semi-naive fixpoint VM to materialize derived relations.
3. Publish a versioned snapshot atomically (dl_publish_snapshot: save the interner + all relations, flip the CURRENT pointer).
4. Serve reads from mmap’d read-only views (dl_query / dl_query_bound / dl_pattern) instead of running the VM.

This is a single-writer / multiple-reader model: one writer, readers on mmap.

Durability

dl_add_fact / dl_delete_fact append to a per-relation WAL and fsync before committing in memory. A fcntl single-writer lock guards the database. The interner is saved durably, and it is ordered before WAL records so crash recovery can decode symbol ids. WAL compaction triggers at 25% of the relation size.

Join & evaluation strategies

Prefix enumeration = index-nested-loop join

The VM implements joins as index-nested-loop: for each tuple, bind the shared leading columns to constants and prefix-enumerate the next relation (via relation.c’s prefix walker, which DFS-traverses the DAFSA from the prefix state). Non-leading-column joins are handled by per-relation permutation indices — a permuted DAFSA for every column-prefix the compiler sees used as a join key — plus a hash-join fallback for the rest. min/max aggregates fall out of the big-endian encoding (extreme prefix = extreme key).

Semi-naive fixpoint + stratification

Recursive rules are evaluated with a semi-naive fixpoint (only the delta is propagated each round). A stratification pass assigns strata and rejects unstratifiable programs (negation through recursion, or a strict cycle through range). Derived relations in a recursive SCC are materialized before any same-stratum dependent reads them.

Bushy joins

Negation-free rules optionally take a binary-tree (bushy) join plan when a natural 2-partition with a low cut width exists (compiled-time toggle, default on). Otherwise a greedy left-deep join reorders the body atoms by ascending estimated cardinality.

Permutation-index selection

For a non-leading-column join, the compiler picks between a permuted DAFSA (OP_LOOKUP_PERM) and a slot-free hash join (OP_HASH_JOIN) using a cardinality cost gate. A recursive body atom is always served by a permutation index (never a hash join, which would read a stale DAFSA), and a hash-join fallback is used when no index is worth building. See Order Statistics.

Magic-sets / QSQ top-down

The dl_query_magic family re-evaluates a scoped fixpoint seeded by the bound goal arguments, materializing only the reachable IDB slice — the result is byte-identical to a bound query over the fully materialized relation. The top-down / QSQ path evaluates the same adorned + magic program but schedules it demand-driven (an SLG worklist over subqueries) instead of as a forward fixpoint. Both are opt-in per-query paths and are available through the C API only.

Incremental view maintenance (IVM)

After rules are compiled and a snapshot is published, subsequent fact insertions (and deletions) are maintained incrementally where eligible (delta propagation, DRed for deletions, aggregate maintenance, bulk) instead of re-running the full fixpoint. Programs using list builtins or variadics are excluded from the incremental paths and always evaluate via the full fixpoint — never silently mis-evaluated.

Pull-iterator + merge-join

A resumable pull-based sorted iterator (dl_iter_*) exposes each relation in ascending key order, and dl_merge_join equi-joins two sorted iterators on a shared leading prefix, streaming pairs in sorted order. See Order Statistics.

Lazy OP_RANGE

The range(X, Rel, Lo, Hi) generator is a lazy resumable generator over the pull-iterator (not an eager materialization): it skips to the lower bound, deduplicates consecutive leading-column values, stops at the upper bound, and can be short-circuited by an early-stopping consumer. It reads the live relation (never a stale snapshot view). See Order Statistics.

Performance

The engine is built around the DAFSA’s exact-lookup and prefix-walk primitives, giving index-nested-loop joins whose cost tracks the size of the bound prefix rather than a full scan, and order statistics (rank / select / range / count) that run in time logarithmic in the number of distinct tuples via the DAFSA’s subtree arrays. The exact-characterizing benchmark is tests/bench.c (make bench); this site deliberately does not quote specific numbers.