Order-dependence in not-join

[greglook]

We got a strange issue in one of our test suites after upgrading from Datascript 1.0.0 to the latest 1.7.3 release (yeah, I know...). The failure came from a query that was using a not-join clause to test whether an attribute value on an A entity matched an identifier on some other B entity in the database - effectively a referential integrity check. However, the test case that started failing did not include any entities of type B, and the query started returning an empty set after the upgrade.

A minimal example showing what this looks like:

(def db1
  (d/db-with
    (d/empty-db)
    [{:node/type :foo, :foo/bar 123}]))

(d/q '[:find ?foo ?id
       :where
       [?foo :foo/bar ?id]
       (not-join [?id]
                 [?bar :node/type :bar]
                 [?bar :bar/id ?id])])]
     db1)
=> #{}

Based on my reading of the Datomic query reference, this should return the node, since the not-join subquery returns no results as there are no "bar" entities. If there is at least one bar entity, the query works as expected:

(def db2
  (d/db-with
    (d/empty-db)
    [{:node/type :foo, :foo/bar 123}
     {:node/type :bar, :bar/id 456}]))

(d/q '[:find ?foo ?id
       :where
       [?foo :foo/bar ?id]
       (not-join [?id]
                 [?bar :node/type :bar]
                 [?bar :bar/id ?id])])]
     db2)
=> #{[1 123]}

However, reordering the clauses in the join fixes this on the original example:

(d/q '[:find ?foo ?id
       :where
       [?foo :foo/bar ?id]
       (not-join [?id]
                 [?bar :bar/id ?id]
                 [?bar :node/type :bar])])]
     db1)
=> #{[1 123]}

This seems like a bug? At least, I don't see anything about order dependence in any docs. The fact that it works correctly on a database that has unrelated entities that satisfy the leading predicate makes me suspect this is related to some empty-relation short circuiting somewhere that's not accounting for this being in a negation clause.

[tonsky]

Fixed in 1.7.4. Indeed, it was a bug. Thanks for reporting!

[greglook]

Thank you for the quick fix!