The current datascript query processing is very simple. It does things the following way: 1. turn each binding in :in into a relation 2. join clauses one by one, by first make a Cartesian product with existing relations That's it. That's why.

Ahh that makes complete sense. No wonder it’s slower.

the join method is hash-join, and tonsky refuse to merge my optimization for it too

he doesn't like inelegant code I guess, but for performance, you cannot have all elegant code

So that also explains why pull is so much faster

(time
    (d/q
      '[:find [?address ...]
        :where
        [?a :account/owner [:account/address
                            "meRjbQXFNf5En86FXT2YPz1dQzLj4Yb3xK8u1MVgqpb"]]
        [?a :account/address ?address]]
      @d/db))
  ;; "Elapsed time: 2225.817526 msecs"

  (time
    (d/q
      '[:find (pull ?a [:account/address])
        :where
        [?a :account/owner [:account/address
                            "meRjbQXFNf5En86FXT2YPz1dQzLj4Yb3xK8u1MVgqpb"]]]
      @d/db))
  ;; "Elapsed time: 266.901356 msecs"

I guess, if you are using datascript on the client in mem you are not dealing with large datasets

In the new query engine, pull will likely slower than query

so it matters less

Yeah, I expected pull to be slower.

basically, the new query engine doesn't do join, just do table scan.

Does that also mean passing in a collection [:id1 :id2 :id3] SQL equivalent of IN won’t lead to a crazy Cartesian product? I know datomic does an optimisation for this, I think it might get rewritten as an (or.

right now, I am not handling collection bindings

ahh, I must have missed that update. I’ve been avoiding collection bindings.

in the future, yes, we will gradually move these features over

For initial rewrite, the planner is handling "normal" cases, additional features can be moved to it gradually.

I need to get the basis right first.

the planner is a classic Selinger query planner, same as those in Postgres etc. The advantage of a triple store is better cardinality estimation, so we likely will generate better plan.

I am relying on LMDB's performance for raw table scan performance. The hope is to perform on par with sqlite, Postgres etc on complex queries. When that is done, I will call it a success.

at that point, there's really no point using SQL, which I intent to replace

So the whole idea is really about ergonomics.

the reason pull will be slower than query in the new query engine is this: pull returns diatoms, here's a cost of converting values to datoms, where as in new engine, we don't do this conversion, values are directly poured into relations.

we rewrite as much operations as possible into range scan routines. Four range scan routines cover most of work, then, the remaining work is done afterwards with hash-join.

The order of these range scans is planned using the classic query planner with dynamic programming. My hope of beating RDBMS is to have more accurate cardinality estimation. In fact, we will count as much as possible, so the estimates are more accurate. Range count in triple store is cheap.

With the new storage format, i.e. dupsort, obtaining most counts is O(1), e.g. the number of datoms matching [?e :attribute ?v] is a single read on LMDB cursor's count field

Thank you for the explanation, this is brilliant. Honestly, I’m amazed how performant datalevin already is even with the simple datascript query engine.

The current engine does have some obvious optimizations, e.g. reorder the clauses based on sizes, hash-join does the right thing, etc

These don’t exist in datascript