Chapter 15: Index Architecture

Earlier chapters introduced the logical fact shape: a datom written as [entity attribute value]. This chapter asks the storage question: how should those facts be ordered so queries can find the relevant facts efficiently?

In Datalevin, the core indexes are not optional side structures added after the data. They are the database's primary representations of facts. Every datom is stored in sorted orders that make entity-local reads, attribute/value lookups, range scans, joins, and graph traversal efficient. The two workhorse indexes are EAV and AVE.

1. The Logic of Sorted Triples

To make searching efficient, Datalevin stores each datom in two different sorted orders within the underlying KV store (DLMDB).

1.1 The Full Datom Object

Most chapters write datoms as [e a v] because those are the three fields used by Datalog patterns and by the EAV/AVE index keys. That is the logical shape of a fact:

[101 :user/email "alice@example.com"]

The implementation of a datom in memory is a richer Datom object. A full Datom has five fields:

The :tx value is Datalevin's internal numeric transaction id for the transaction report. Datalevin maintains the latest transaction counter as store metadata (max-tx), but per-datom transaction ids are not stored in the persistent EAV/AVE indexes. A transaction id is also not a queryable transaction entity with automatically stored attributes. The optional tx-meta argument to transact! is returned in the transaction report and sent to listeners, but it is not stored as queryable transaction metadata unless your application explicitly transacts its own audit facts.

In a transaction report, the transaction fields are available on :tx-data.

(let [report (d/transact! conn [{:user/email "alice@example.com"}])
      datom  (first (:tx-data report))]
  {:e     (:e datom)
   :a     (:a datom)
   :v     (:v datom)
   :tx    (:tx datom)
   :added (:added datom)})
;=> {:e 101, :a :user/email, :v "alice@example.com", :tx 42, :added true}

Map<?, ?> report = conn.transact(Datalevin.tx()
    .entity(Tx.entity()
        .put(":user/email", "alice@example.com")));

Map<?, ?> datom = (Map<?, ?>) ((List<?>) report.get(
    Datalevin.kw(":tx-data"))).get(0);

Map<String, Object> fields = Map.of(
    "e", datom.get(Datalevin.kw(":e")),
    "a", datom.get(Datalevin.kw(":a")),
    "v", datom.get(Datalevin.kw(":v")),
    "tx", datom.get(Datalevin.kw(":tx")),
    "added", datom.get(Datalevin.kw(":added")));

report = conn.transact([
    {":user/email": "alice@example.com"}
])

datom = report[":tx-data"][0]
fields = {
    "e": datom[":e"],
    "a": datom[":a"],
    "v": datom[":v"],
    "tx": datom[":tx"],
    "added": datom[":added"],
}

const report = await conn.transact([
  { ":user/email": "alice@example.com" }
]);

const datom = report[":tx-data"][0];
const fields = {
  e: datom[":e"],
  a: datom[":a"],
  v: datom[":v"],
  tx: datom[":tx"],
  added: datom[":added"]
};

Datalevin's EAV/AVE indexes expose the facts present in the database state you are reading, so datoms returned from datoms, search-datoms, and index-range (see below) should be treated as [e a v] facts. Transaction reports are where :tx and :added false most often matter: a report's :tx-data can include datoms that were retracted by the transaction.

This distinction explains a recurring convention in this guide: [e a v] means "the logical fact used by a query or index key"; the full Datom object carries the extra transaction metadata needed by lower-level APIs and transaction reports.

1.2 Why Datalevin Is Not a History Database

Datalevin's persistent indexes are not history indexes. One way to support historical database values is to store the transaction dimension with every datom: keep each assertion and retraction with its transaction id, then answer historical queries by selecting the datoms whose transaction ids are visible at a chosen point in time. Datalevin deliberately does not make that per-datom transaction dimension part of the persistent EAV/AVE indexes.

Why not database-as-value history? Datalevin is designed first as an OLTP database: an operational store for current application state. For that workload, the ordinary developer mental model is that a database represents mutable state: users update profiles, orders change status, jobs move through queues, and the application asks questions about the current world. Automatically retaining every historical datom would make that model harder to explain and would make every application pay for a history feature that many operational systems do not need.

Keeping full transaction history is not free. It increases storage, widens the indexes the system must maintain, and makes reads and writes account for old states as well as current state. That tradeoff can be right for domains such as financial ledgers, audit stores, event logs, or analytical systems where history is the product. It is a poor default for an embedded or operational database whose common path is "store the latest state and query it efficiently."

This point matters especially for the agent-memory use cases in Part VI. A useful agent memory is not an append-only transcript. It needs deletion, expiry, consolidation, summarization, and retraction. Human memory research treats forgetting as an adaptive feature of cognition: transience can reduce interference, support abstraction, and help a system stay responsive when the world changes [1]. An agent that can only accumulate memories will eventually retrieve stale, irrelevant, or harmful context. Datalevin's current-state model makes forgetting a normal database operation rather than an exception to the model.

When applications need temporal or provenance-aware data, the requirements are usually richer than "keep every transaction forever." A transaction id can tell you when a fact was asserted or retracted in the database, but it does not tell you why a rule fired, which source passages supported a RAG answer, how confidence should propagate through a derivation, which explanation justifies a query result, or how to maintain an annotated derived view incrementally.

Datalevin's direction is therefore not to make transaction history the one built-in answer. The more general plan is to implement support for the Green-Karvounarakis-Tannen semiring provenance framework [2]. In that model, facts carry annotations from a chosen semiring; joins combine annotations with the semiring's multiplication, and alternative derivations combine them with addition. Temporal history becomes one concrete instance, for example with an interval semiring, but the point is broader than as-of history. The same framework can also support count provenance, why-provenance, confidence or probability propagation, min-cost explanations, rule-application tracing, RAG source attribution, debugging, and incremental view maintenance [2,3].

This does not require changing Datalevin's datom storage format. The core fact remains [e a v]; provenance annotations are represented as additional datoms: source entities, derivation entities, intervals, confidence values, costs, rule identifiers, and links between derived facts and their supporting facts. Datalog can then query and propagate those annotations explicitly. In the meantime, model audit and provenance facts explicitly when the domain needs them, and keep the core EAV and AVE indexes optimized for current OLTP state.

1.3 Why Sorted Indexes Speed Up Queries

Sorted indexes are efficient because they avoid looking at unrelated facts. The basic idea is the same reason binary search is efficient compared with a scan: when data is ordered, the engine can jump toward the place where a key must be instead of checking every item.

LMDB stores each Datalevin index as a B+Tree [4]. A point lookup, such as "find the datom for entity 101 and attribute :user/email", starts at the root page, chooses the child page whose key range could contain the target, repeats that step through internal pages, and lands on the leaf page where the key is stored or would be stored. Because B+Tree pages have high fanout, this is usually only a few page hops even for a large database.

Range queries use the sorted order in a second way. To answer "find all users with age between 21 and 65", the engine first seeks to the lower bound in the AVE index. From there, it walks forward through neighboring leaf entries in sorted order until the upper bound is reached. It does not restart from the root for every matching datom, and it does not scan unrelated attributes. This is why the order of an index matters.

Datalevin's two core sorted orders are EAV and AVE.

EAV (Entity-Attribute-Value)

EAV makes facts for one entity contiguous.

• Primary Use Case: "Give me everything about Entity 101."
• Query Role: This index powers the Pull API and pivot scans in queries (see Chapter 21). In a query, the EAV index is scanned for attribute values when the entity is already known. Because all attributes for a single entity are stored contiguously in the B+Tree, retrieving a complete record for an entity is a single localized range scan.

AVE (Attribute-Value-Entity)

AVE makes facts for one attribute/value range contiguous.

• Primary Use Case: "Find all entities where the :user/age is 30."
• Query Role: This is the "search" index. It powers :where clauses that filter by a known attribute and value, or by a known attribute and value range.
• Universal Indexing: In Datalevin, every attribute is indexed in AVE.

DLMDB adds order statistics (Chapter 4): Datalevin can efficiently count how many entries fall in a value range without materializing the datoms. That inexpensive range count matters to the query optimizer. When a predicate such as [(> ?age 21)] can be pushed down to an AVE range, the engine can estimate the size of that candidate set and choose a better join order (Chapter 21). AVE is therefore both a scan path and a source of cardinality information.

Together, EAV and AVE make common Datalog patterns line up with sorted access paths. Figure 15.1 shows the mapping: entity-known patterns favor EAV, while attribute/value patterns and value ranges favor AVE.

2. Index-Level APIs: Direct Access

Datalevin exposes these indexes directly to application code. You are not limited to the Datalog query engine; you can choose a direct index API when the access path is already known.

Direct index APIs return datoms in index order. They are best for simple, known access paths where you want the index itself, not the query planner, to be the API boundary.

2.1 Prefix Scans with datoms

Use datoms when you already know whether the lookup is entity-local (:eav) or value-local (:ave).

;; All datoms for entity 101, ordered by attribute and value.
(d/datoms db :eav 101)

;; A single attribute on entity 101.
(d/datoms db :eav 101 :user/email)

;; All entities whose :user/age value is 30.
(d/datoms db :ave :user/age 30)

// All datoms for entity 101, ordered by attribute and value.
conn.datoms(":eav", 101);

// A single attribute on entity 101.
conn.datoms(":eav", 101, ":user/email");

// All entities whose :user/age value is 30.
conn.datoms(":ave", ":user/age", 30);

# All datoms for entity 101, ordered by attribute and value.
conn.datoms(":eav", 101)

# A single attribute on entity 101.
conn.datoms(":eav", 101, ":user/email")

# All entities whose :user/age value is 30.
conn.datoms(":ave", ":user/age", 30)

// All datoms for entity 101, ordered by attribute and value.
await conn.datoms(':eav', { c1: 101 });

// A single attribute on entity 101.
await conn.datoms(':eav', { c1: 101, c2: ':user/email' });

// All entities whose :user/age value is 30.
await conn.datoms(':ave', { c1: ':user/age', c2: 30 });

2.2 Wildcard Lookup with search-datoms

Use search-datoms when you want to describe the logical datom pattern as (e, a, v) and let Datalevin choose the index. A nil / None / null component is a wildcard. In JavaScript calls, omit a wildcard key from the argument object or leave it null.

;; All attributes and values for entity 101.
(d/search-datoms db 101 nil nil)

;; All entities whose :user/age value is 30.
(d/search-datoms db nil :user/age 30)

;; The exact datom, if present.
(d/search-datoms db 101 :user/email "ada@example.com")

// All attributes and values for entity 101.
conn.searchDatoms(101, null, null);

// All entities whose :user/age value is 30.
conn.searchDatoms(null, ":user/age", 30);

// The exact datom, if present.
conn.searchDatoms(101, ":user/email", "ada@example.com");

# All attributes and values for entity 101.
conn.search_datoms(e=101)

# All entities whose :user/age value is 30.
conn.search_datoms(attr=":user/age", value=30)

# The exact datom, if present.
conn.search_datoms(e=101, attr=":user/email", value="ada@example.com")

// All attributes and values for entity 101.
await conn.searchDatoms({ e: 101 });

// All entities whose :user/age value is 30.
await conn.searchDatoms({ attr: ':user/age', value: 30 });

// The exact datom, if present.
await conn.searchDatoms({
  e: 101,
  attr: ':user/email',
  value: 'ada@example.com'
});

2.3 Counting with count-datoms

Use count-datoms when a query path needs selectivity, pagination totals, or an inexpensive existence check.

;; How many datoms are attached to entity 101?
(d/count-datoms db 101 nil nil)

;; How many users have age 30?
(d/count-datoms db nil :user/age 30)

// How many datoms are attached to entity 101?
conn.countDatoms(101, null, null);

// How many users have age 30?
conn.countDatoms(null, ":user/age", 30);

# How many datoms are attached to entity 101?
conn.count_datoms(101, None, None)

# How many users have age 30?
conn.count_datoms(None, ":user/age", 30)

// How many datoms are attached to entity 101?
await conn.countDatoms({ e: 101 });

// How many users have age 30?
await conn.countDatoms({ attr: ':user/age', value: 30 });

count-datoms is faster than (count (search-datoms ...)) because it leverages DLMDB's order statistics and does not have to allocate the matching datoms.

2.4 cardinality and analyze

Use cardinality when you need the number of distinct values currently present for one attribute. Do not confuse this with the schema property :db/cardinality, which says whether an attribute is single-valued or multi-valued. d/cardinality is a data statistic.

;; How many distinct ages exist?
(d/cardinality db :user/age)

;; How many datoms use :user/age at all?
(d/count-datoms db nil :user/age nil)

;; How many datoms say :user/age is 30?
(d/count-datoms db nil :user/age 30)

// How many distinct ages exist?
conn.cardinality(":user/age");

// How many datoms use :user/age at all?
conn.countDatoms(null, ":user/age", null);

// How many datoms say :user/age is 30?
conn.countDatoms(null, ":user/age", 30);

# How many distinct ages exist?
conn.cardinality(":user/age")

# How many datoms use :user/age at all?
conn.count_datoms(None, ":user/age", None)

# How many datoms say :user/age is 30?
conn.count_datoms(None, ":user/age", 30)

// How many distinct ages exist?
await conn.cardinality(':user/age');

// How many datoms use :user/age at all?
await conn.countDatoms({ attr: ':user/age' });

// How many datoms say :user/age is 30?
await conn.countDatoms({ attr: ':user/age', value: 30 });

Datalevin periodically refreshes eid samples and attribute cardinality counts in the background for the query planner. After a bulk load or substantial reshape, analyze can refresh these statistics for one attribute or all attributes:

(d/analyze db :user/age)
(d/analyze db)

conn.analyze(":user/age");
conn.analyze();

conn.analyze(":user/age")
conn.analyze()

await conn.analyze(':user/age');
await conn.analyze();

2.5 Cursor Scans with seek-datoms and rseek-datoms

Use seek-datoms when you want to start at an index key and continue forward. If no datom exactly matches the supplied components, Datalevin starts at the first datom that is greater in that index order. rseek-datoms uses the same idea in reverse.

The arguments after db/connection are the index name, up to three components in that index order, and an optional result limit:

For example, (seek-datoms db :ave :user/age 30 nil 10) starts in AVE order at attribute :user/age, value 30, leaves the entity-id component open, and returns at most 10 datoms. In Clojure and Java, pass nil/null for skipped later components when you need to supply the final limit. Python and JavaScript use named limit options instead.

;; Start a forward scan at :user/age 30 in AVE order.
(d/seek-datoms db :ave :user/age 30 nil 10)

;; Start a reverse scan near the high end of :user/created-at.
(d/rseek-datoms db :ave :user/created-at 4102444800000 nil 5)

;; Start at the :user/email position inside entity 101.
(d/seek-datoms db :eav 101 :user/email)

// Start a forward scan at :user/age 30 in AVE order.
conn.seekDatoms(":ave", ":user/age", 30, null, 10);

// Start a reverse scan near the high end of :user/created-at.
conn.rseekDatoms(":ave", ":user/created-at", 4102444800000L, null, 5);

// Start at the :user/email position inside entity 101.
conn.seekDatoms(":eav", 101, ":user/email");

# Start a forward scan at :user/age 30 in AVE order.
conn.seek_datoms(":ave", ":user/age", 30, limit=10)

# Start a reverse scan near the high end of :user/created-at.
conn.rseek_datoms(":ave", ":user/created-at", 4102444800000, limit=5)

# Start at the :user/email position inside entity 101.
conn.seek_datoms(":eav", 101, ":user/email")

// Start a forward scan at :user/age 30 in AVE order.
await conn.seekDatoms(':ave', {
  c1: ':user/age',
  c2: 30,
  limit: 10
});

// Start a reverse scan near the high end of :user/created-at.
await conn.rseekDatoms(':ave', {
  c1: ':user/created-at',
  c2: 4102444800000,
  limit: 5
});

// Start at the :user/email position inside entity 101.
await conn.seekDatoms(':eav', { c1: 101, c2: ':user/email' });

Without the result limit, the cursor keeps walking to the end of that index direction. That is occasionally useful for low-level scans, but it is often broader than application code intends.

2.6 Range Scans with index-range

Use index-range for the most common AVE range pattern: one attribute, lower bound, upper bound.

;; Find users with age between 20 and 30, inclusive.
(d/index-range db :user/age 20 30)

;; Return just the matching entity ids.
(map :e (d/index-range db :user/age 20 30))

// Find users with age between 20 and 30, inclusive.
conn.indexRange(":user/age", 20, 30);

// Return just the matching entity ids.
List<?> datoms = conn.indexRange(":user/age", 20, 30);
List<?> entityIds = datoms.stream()
    .map((datom) -> ((Map<?, ?>) datom).get(Datalevin.kw(":e")))
    .toList();

# Find users with age between 20 and 30, inclusive.
datoms = conn.index_range(":user/age", 20, 30)

# Return just the matching entity ids.
entity_ids = [datom[":e"] for datom in datoms]

// Find users with age between 20 and 30, inclusive.
const datoms = await conn.indexRange(':user/age', 20, 30);

// Return just the matching entity ids.
const entityIds = datoms.map((datom) => datom[':e']);

These functions are intentionally low-level. Prefer Datalog for joins, rules, result shaping, and complex predicates. Reach for direct index access when the shape is simple enough that the index order itself is the query plan.

2.7 Choosing an Index Access Function

After seeing the individual APIs, the choice can be summarized as a question about which parts of the datom are known and whether you need values or only a count. Figure 15.2 lays this out as a decision chart; it is about API choice, not query planning.

Most rows in the table below are direct read paths. analyze is the exception: it refreshes planner statistics after data shape changes.

The two attribute-scoped value lookups are both range scans for the same reason. Fixing the attribute pins the leading bytes of the AVE key, so LMDB has a known lower and upper byte bound to scan between. Reading every value of an attribute walks from that attribute's minimum encoded value to its maximum; a bounded predicate such as [(< 20 ?age 30)] just tightens those bounds. Neither case scans the whole index.

3. Physical Representation and DUPSORT

Physically, these indexes are implemented using LMDB's DUPSORT feature (see Chapter 10). This allows Datalevin to store many values for a single key efficiently.

• In EAV: The key is E, and the values are (A, V) pairs.
• In AVE: The key is (A, V), and the values are E (entity ids).

Figures 15.3 and 15.4 show this nesting for each index.

Thinking in terms of traditional database storage models:

• EAV is a row store: Each entity id (key) maps to a list of attribute-value pairs, analogous to a row where all column values are stored together. Retrieving an entity is a single key lookup.
• AVE is a column store: Each (A, V) combination (key) maps to a tightly packed list of entity ids, the "row IDs" that share that column value. This is ideal for analytical queries that scan a column.

This nested storage eliminates redundant prefixes. In EAV, an entity with 10 attributes stores the entity id once as the key, with 10 (A, V) pairs as values. In AVE, each (A, V) combination is stored once as the key, with all matching entity ids as values, so finding all entities where :user/age is 30 is a single key lookup.

This storage shape also explains the performance tax of using :db.cardinality/many for large relationship sets. In EAV, the owner entity carries one (A, V) duplicate value for every member, so scanning that attribute under the entity has to walk a long group instead of reading one cardinality-one value. In AVE, the cost is often larger. A normalized many-side reference such as [?comment :comment/post ?post] groups all comments for one post under the single (A, V) key (:comment/post, ?post), so the lookup is one contiguous duplicate scan. If the same relationship is stored as [:post/comments ?comment] on the parent, each comment value has a different (A, V) key; value-oriented access over the collection becomes many seeks or short scans that jump around AVE. That is why Chapter 11 recommends cardinality-many only for small, bounded sets read with their owner, and recommends a cardinality-one ref on the many side or a join entity for larger relationships.

In the Join Order Benchmark database, this DUPSORT nesting reduced index space by roughly 20%. Treat that number as an anecdotal workload observation, not a general guarantee: the savings depend on the number of repeated entity ids in EAV and repeated (A, V) prefixes in AVE. This is separate from DLMDB's page-level prefix compression, which can provide additional savings depending on how much of neighboring encoded keys is actually shared.

Summary: Indexes as Capabilities

By indexing every attribute by default and exposing direct index APIs, Datalevin lets application code use the same access paths the query engine plans against.

• EAV provides locality for entities and documents.
• AVE provides indexed lookups and range scans for values.
• Direct Access gives you datoms, search-datoms, count-datoms, cardinality, seek-datoms, rseek-datoms, index-range, and analyze for custom traversal and statistics logic when the access pattern is already known.

Understanding these indexes makes the later chapters on full-text search, vector similarity, and query optimization easier to reason about.

References

[1] Blake A. Richards and Paul W. Frankland, "The Persistence and Transience of Memory," Neuron 94(6):1071-1084, 2017. DOI: https://doi.org/10.1016/j.neuron.2017.04.037.

[2] Todd J. Green, Grigoris Karvounarakis, and Val Tannen, "Provenance Semirings," in Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS '07), 2007, pp. 31-40. DOI: https://doi.org/10.1145/1265530.1265535.

[3] Camille Bourgaux, Pierre Bourhis, Liat Peterfreund, and Michael Thomazo, "Revisiting Semiring Provenance for Datalog," arXiv:2202.10766, 2022. URL: https://arxiv.org/abs/2202.10766.

[4] Douglas Comer, "The Ubiquitous B-Tree," ACM Computing Surveys 11(2):121-137, 1979. DOI: https://doi.org/10.1145/356770.356776.