Order Statistics

Because every fact is stored as a fixed-width u32 big-endian key, the numeric order of keys is exactly their lexicographic order. That single fact makes positional queries — rank, select, range count, and an ordered enumeration — natural and cheap over a DAFSA’s sorted structure. Order statistics are available through the C API only; there is no Datalog syntax and no CLI command for them.

rank / select / range_count / count

The core four functions operate on the leading column order (the natural key order):

uint64_t dl_rank(db, "r", cols, arity);          /* # tuples strictly < cols */
int      dl_select(db, "r", k, cols_out, arity); /* k-th tuple (0-indexed, lex) */
uint64_t dl_range_count(db, "r", lo, hi, arity); /* # tuples in [lo, hi) */
uint64_t dl_count(db, "r");                      /* O(1) distinct-tuple count */

dl_rank counts distinct tuples strictly lexicographically smaller than cols. An absent key ranks at its insertion position (between neighbours, below the minimum, or at the count).
dl_select writes the k-th tuple (0-indexed, lex order); returns -1 if k is out of range.
dl_range_count returns rank(hi) − rank(lo) for the half-open range [lo, hi).
dl_count is an O(1) distinct-tuple count backed by a memoized subtree array.

When a snapshot has been published (db->snap_version > 0), these read the mmap snapshot view, so they reflect the published state even if the live in-memory relation has since been mutated; otherwise they read the in-memory relation.

Bound variants

The _bound family restricts to tuples whose first k columns equal a leading bound, then applies rank / select / range_count to the suffix (the remaining arity-k columns). The cols/lo/hi are full arity-length tuples whose first k entries must equal leading. k==0 means no bound (degenerates to the base family).

uint64_t dl_rank_bound(db, "r", leading, k, cols, arity);
int      dl_select_bound(db, "r", leading, k, idx, cols_out, arity);
uint64_t dl_range_count_bound(db, "r", leading, k, lo, hi, arity);

Permuted order statistics

The _perm family evaluates order statistics over a permuted view — an order-by on a non-leading column. A permutation index is declared with dl_db_declare_perm (an exported helper in the internal permindex.h, not part of the public dl.h surface); then perm[j] is the original column that appears at permuted position j. For example perm = {1, 0} over an arity-2 relation orders tuples by column 1, then column 0 as the tiebreaker.

cols/lo/hi are full tuples in the original column order. Rank and range-count forward-map the input to permuted order before ranking; select inverse-maps its permuted-order result back to original order, so a select→rank round-trip over the same perm is the identity. The permuted relation is built on demand and rebuilt if dirty — a stale index is never silently used.

uint64_t dl_rank_perm(db, rel, perm_id, cols, arity);
int      dl_select_perm(db, rel, perm_id, k, cols_out, arity);
uint64_t dl_range_count_perm(db, rel, perm_id, lo, hi, arity);
int      dl_db_perm_count(db);   /* number of declared perm indices */

The compiler also selects permutation indices automatically for non-leading-column joins (see Architecture).

Pull-iterator + merge-join

dl_iter_* is a resumable pull-based cursor over a relation in ascending key order. It reads from the mmap snapshot view when a snapshot is current, else the in-memory relation. Because a DAFSA is a minimal acyclic DFA with per-state transitions sorted by symbol, pre-order DFS == byte/lex == u32BE numeric order; from a bound state every final state sits at the same fixed depth, so emit-then-backtrack yields exactly one tuple per dl_iter_next.

dl_iter *it = dl_iter_open(db, "r", leading, k);   /* k==0: all tuples */
uint32_t row[MAXA];
while (dl_iter_next(it, row) == 1) { /* consume ascending tuple */ }
dl_iter_close(it);

dl_merge_join equi-joins two sorted iterators on their first jcols columns, streaming matching pairs in sorted order with cross-product semantics (duplicates preserved). Both iterators are left exhausted on return; a non-zero callback return stops the join early.

long n = dl_merge_join(left, right, jcols, join_cb, user);

Lazy `OP_RANGE`

The Datalog range(X, Rel, Lo, Hi) builtin (see the Language Reference) is backed by a lazy resumable generator over the pull-iterator. It:

opens a k=0 cursor and skips leading-column values below the lower bound;
deduplicates consecutive equal leading-column values (yielding distinct col0 values, not every tuple);
stops at the upper bound;
can be short-circuited by an early-stopping consumer.