I work on Crux so can share a few details about our implementation of Datalog. The query is compiled into a kind of Worst-Case Optimal Join algorithm [0] which means that certain types of queries (e.g. cyclic graph-analytical queries, like counting triangles) are generally more efficient than what is possible with a non-WCOJ query execution strategy. However, the potency of this approach relies on the query planner calculating a good ordering of variables for the join order, and this is a hard problem in itself.

Crux is usually quite competent at selecting a sensible variable ordering but when it makes a bad choice your query will take an unnecessary performance hit. The workaround for these situations is to break your query into smaller queries (since we don't wish to support any kind of hinting). Over the longer term we will be continuing to build more intelligent heuristics that make use of advanced population statistics. For instance we are about to merge a PR that uses HyperLogLog to inform attribute selectivity: https://github.com/juxt/crux/pull/1472

EDIT: it's also worth pointing out that the workaround of splitting queries apart is only plausible because of the "database as a value" semantics that make it possible to query repeatedly against a fixed transaction-time snapshot. This is useful for composition more generally and makes it much simpler to write compile-to-Datalog query translation layers on top, such as for SQL: https://opencrux.com/blog/crux-sql.html

[0] https://cs.stanford.edu/people/chrismre/papers/paper49.Ngo.p...