match-record.clj

(defn compile-where
  [record]
  (let [clause (apply list 'and (map #(list '= (key %) (val %)) record))]
    `(ql/where ~clause)))

(defn match-record
  [record]
  (eval (compile-where record)))

clojureql.core> (let [rec {:id 5 :name "Fred" :age 22}]
                   (reduce (fn [acc [k v]] (and* acc (=* k v))) (predicate) rec))
#:clojureql.predicates.APredicate{:stmt ["((( AND (id = ?)) AND (name = ?)) AND (age = ?))"], :env [5 "Fred" 22]}

I see that the Predicate protocol doesnt handle empty ANDs gracefully. But if that was fixed, wouldn't this approach be preferred?

Fixed in Master - The above code will generate a working predicate