using this pull gives me the result I want in ~8ms. Albeit, not pretty

(loop [obj (d/pull (d/db conn) '[* {[:list/_next :as :prev] ...}] some-ent-in-list)]
  (if-let [prev (some-> obj :prev first)]
    (recur prev)
    (dissoc obj :list/next)))

The first rule variant says [?head :list/head] but head is never bound when the rule is evaluated

So that realizes all head entities

Try [?x :list/head][(identity ?x) ?head]

Is so critical for perf to know what is bound so you can do clause ordering that it's nearly always unsafe to declare rules without that special “require bound variable” syntax

So I recommend something like (list-head [?x] ?head) in your definitions

reading up on that now. what query time would you say is to be expected here? roughly same magnitude as the pull or slower?

Roughly same

hmm, using

'[[(list-head [?x] ?head)
     [?x :list/head]
     [(identity ?x) ?head]]
    [(list-head [?x] ?head)
     [?y :list/next ?x]
     [list-head ?y ?head]]]

(d/q '[:find ?head .
        :in $ % ?elem
        :where
        [?head :list/head]
        [list-head ?elem ?head]]
      (d/db conn)
      list-head-rule
      item-99-in-list)

schema definition:

[#:db{:ident :list/head,
      :valueType :db.type/string,
      :cardinality :db.cardinality/one,
      :unique :db.unique/identity}
 #:db{:ident :list/next,
      :valueType :db.type/ref,
      :cardinality :db.cardinality/one}]

Is this db small enough to fit in memory?

yes, toy example

though currently using dev storage transactor

Do you see a difference if you def the query body? Perhaps there's some constant overhead

Otherwise idk. There is a tiny difference in index use (pull uses eavt for the first and last lookup; query generally uses aevt if a is static) but that's not a difference I'd expect t matter here

no difference if I def the query body. Here’s a complete example if you want to try: https://gist.github.com/handerpeder/d6db931cd8fceca629ea4b42102d6f05 either way, thanks for the help!

The gist still has the problem of a too-early [?head :list/head] (line 48, that should just be removed), but that doesn’t matter at this data size.

AFAIKT recursive rules are just really slow…

This is an equivalent rule:

(defn heads [db elem]
  ;; same thing as the list-head rule,
  ;; including no assumptions about number of matches
  ;; and fully evaluating each branch.
  (-> #{}
      (into (map :e) (d/datoms db :aevt :list/head elem))
      (into (mapcat #(heads db (:e %)))
            (d/datoms db :vaet elem :list/next))))

(def list-head
  ['[(list-head [?x] ?head)
     [?x :list/head]
     [(identity ?x) ?head]]
   '[(list-head [?x] ?head)
     [?y :list/next ?x]
     (list-head ?y ?head)]
   ;; function call instead to avoid recursion
   ['(list-head2 [?x] ?head)
    [(list `heads '$ '?x) '[?head ...]]]])

(time
 (d/q '[:find ?head
        :in $ % ?value
        :where
        [?elem :list/value ?value]
        (list-head ?elem ?head)]
      (d/db conn)
      list-head
      99))
"Elapsed time: 40.233292 msecs"
=> #{[17592186045418]}
(time
 (d/q '[:find ?head
        :in $ % ?value
        :where
        [?elem :list/value ?value]
        (list-head2 ?elem ?head)]
      (d/db conn)
      list-head
      99))
"Elapsed time: 1.5925 msecs"
=> #{[17592186045418]}

but the rule is probably stack overflow resistant, my fn is not

Thanks!