Idea for a reactive and faster alternative to Datascript

Just an idea

As someone pointed out (#130), a faster Datascript implementation is needed for applications with a lot of entities.

Moreover, it would be great to have a system that would offer reactive views (think auto-refreshed materialized views or live queries). This is not currently possible with Datascript (see #12).

Here is an idea for a reactive and faster alternative (or complement) to Datascript inspired by the Event Sourcing pattern.

The system would consist of:

• a datom store,
• indexes
• and views.

The datom store

The datom store could be a simple list of datoms ordered by transaction time.

The datom store would be the single source of truth. Datoms should only be deleted on rare cases, for memory-saving or confidentiality purposes. Thus the datom store could be used as a replayable audit trail for production debugging (together with view queries).

Nested map indexes

Indexes would be nested Clojure maps with three levels. For example, the AVE index: {:attributes {values {eids entities}}}.

They would be highly denormalized in order to minimize lookups: entities would be replicated as maps of {:attributes values} everywhere in the index, apart in type/ref which would only reference eids (to avoid infinite loops in joins). Eids would be referenced as an attribute in the AVE index.

Snapshots of indexes could be stored locally and on the server to speed-up application start-up, i.e. to avoid recomputing indexes from the datom store each time the application is started. They could also be used for an undo-redo feature.

Views

A view would hold the result of a live query run on indexes or on transaction datoms. It would be updated each time a tx-data datom matches a pattern. The default pattern could just be the :where clauses of the query.

Queries with entity joins would run on the indexes. Queries without entity joins might only need to run on entities referred to in the transaction datoms, and if the result could be merged into the corresponding view, it would be much faster than a query on the indexes. These could be called 'delta queries'.

Views could be declared in any part of the application. UI components could subscribe to any of these views and be updated automatically whenever they change.

Transactions history could be used in views for an undo/redo feature for example.

Faster?

The Datascript benchmark¹ includes a query (q4) that runs in 40 milliseconds for 20000 entities (see #130):

[:find ?e ?l ?a :where [?e :name "Ivan"]
                                     [?e :last-name ?l]
                                     [?e :age ?a]
                                     [?e :sex :male]]

Let's imagine how this query would run on map-based indexes:

1. In the AVE index, look for the :name attribute, then look for the "Ivan" value and return the map of entities.
2. In the AVE index, look for the :sex attribute, then look for the :male value and return the map of entities.
3. Intersect these two maps.
4. Keep only the selected attributes (eid, :last-name and :age) in the result.

This query would probably take no more than 4-40 microseconds, even on a large dataset (cf. benchmarks of CLJ and CLJS maps lookups).

What's more, this query (having no entity join) might be turned automatically into a live delta query that would just need to run on tx-data datoms before updating the view.

Comments are welcome!

I'm not experienced enough in Clojure to hack together a proof of concept (with Datalog and Pull queries) yet. I should be in a few weeks/months though. Please keep me in the loop if you're considering working on it.

I am quite new to this community and I don't even know if it is useful to present an idea like this as a suggestion without any code. I probably have overlooked things.

What do you think?

Vianney

Start by reading the benchmark query q4 in bench/src/datascript/bench.cljc around line 85, then review the issue's proposed datom store, nested indexes, and live-query views. There is no concrete implementation entry point or acceptance test named; done would require an agreed proof of concept and benchmark or query behavior defined by the maintainers.