Table of Contents
Mentat (and all other assertion stores, including Datomic) are set-oriented, meaning that an assertion [e a v] exists at most once in the store. That means that the transactor needs to ignore an entity like [:db/add e a v] if [e a v] is already present. It's easy to arrange for the underlying SQL to do that, but it's not so easy to efficiently prepare a transaction report listing exactly which new assertions were transacted and which entities were ignored. Further, the transactor needs to ignore an entity like [:db/retract e a v] if [e a v] is not present in the store. The cost of preparing a transaction report increases as we add more general entities like [:db/retractEntity ...] and [:db/retractAttribute ...].
Here's one approach to translating entities to SQL that allows to prepare transaction reports reasonably efficiently.
Temporary tables: "before search" and "after search"
Our approach is, at the start of each transaction, to create a temporary table that we term before_search that collects information about the assertions to transact, have SQLite do a single expensive join to fill a second temporary table that we term after_search, and then extract the transaction report from the after_search temporary table. This pushes SQLite to do as much of the expensive state querying internally. At the end of the transaction, the temporary tables are then dropped, ready to be re-created for the next transaction.
The before_search table looks roughly like:
| e0 | a0 | v0 | value_type_tag0 | added0 | search_type |
|---|---|---|---|---|---|
| datom to be transacted | search parameters | ||||
and the after search table looks roughly like:
| e0 | a0 | v0 | value_type_tag0 | added0 | search_type | result_rowid | result_v | result_value_type_tag |
|---|---|---|---|---|---|---|---|---|
| datom to be transacted | search parameters | search result | ||||||
It's worth noting that the search flag column in before_search may be 0, indicating that we don't need to search at all, and that the did_search result column in after_search corresponds to this.
Populating the "before search" table: translating entities
For now, let us ignore fulltext attributes entirely.
-
[:db/add e a v]whereais:db/cardinality :db.cardinality/many:We never need to retract existing datoms, so we simply insert into
before_searchand search for an existing exact match:e0 a0 v0 value_type_tag0 added0 search_type e a v value_type_tag ADDED EXACT MATCH -
[:db/add e a v]whereais:db/cardinality :db.cardinality/one:Recall that cardinality one assertions replace any existing
[e a v*]assertion. That means we may need to retract any existing datom, so we insert intobefore_searchand search for any existing inexact match:e0 a0 v0 value_type_tag0 added0 search_type e a v value_type_tag ADDED INEXACT MATCH -
[:db/retract e a v]: We expect to need to retract an existing datom, so we insert intobefore_searchand search for an existing exact match:e0 a0 v0 value_type_tag0 added0 search_type e a v value_type_tag RETRACTED EXACT MATCH
Populating the "after search" table: looking for matching assertions
We have SQLite look for exact matches:
INSERT INTO after_search
SELECT t.e0, t.a0, t.v0, t.tx0, t.added0, t.value_type_tag0, 1, d.rowid, d.v, d.value_type_tag
FROM before_search AS t
LEFT JOIN datoms AS d
ON t.exact_match = 1 AND
t.e0 = d.e AND
t.a0 = d.a AND
t.v0 = d.v AND
t.value_type_tag = d.value_type_tag
and for inexact matches:
INSERT INTO after_search
SELECT t.e0, t.a0, t.v0, t.tx0, t.added0, t.value_type_tag0, 0, d.rowid, d.v, d.value_type_tag
FROM before_search AS t
LEFT JOIN datoms AS d
ON t.exact_match = 0 AND
t.e0 = d.e AND
t.a0 = d.a
Augmenting the "after search" table: looking for matching assertions
We handle a few entity types specially.
[:db/retractAttribute e a]:
We have SQLite insert into after_search roughly as follows:
INSERT INTO after_search
SELECT e, a, v, value_type_tag, RETRACTED, EXACT_MATCH, rowid, v, value_type_tag
FROM datoms
WHERE e = :e AND a = :a
[:db/retractEntity e]:
We have SQLite insert into after_search as follows:
INSERT INTO after_search
SELECT e, a, v, value_type_tag, RETRACTED, EXACT_MATCH, rowid, v, value_type_tag
FROM datoms
WHERE e = :e OR (v = :e AND value_type_tag = REF)
It would be possible to generalize the search step above to do this search as part of the main search, but it's likely to be less efficient.
Updating the transactions and datoms tables
To follow.