https://gist.github.com/bsless/632b4040a2b2ad7469369f52cd610c06 Something like this as a starting point for a parser

the thing I'm stuck on right now is the specifics of how to chain patterns

take something like:

[:find ?id
 :where
 [?e :foo/id ?id]
 [?e ?a "bar"]]

[1 ?a "bar"]
[4 ?a "bar"]

Filtering is A way to do it

I've been thinking of a way to model/phrase it without tying it to a specific implementation

But the more efficient way is usually to: 1. Resolve [?e :foo/id ?id] to find the matching entries 2. Iterate over the bindings from 1 (bindings of ?e and ?id) and use these to rewrite the second constraint. This means updating ?e. Do a lookup for each rewrite. 3. Concatenate the results of 2

btw, how do you handle binding? do you just maintain a replacements map?

Because you’re iterating over the LHS but not the RHS, you want to keep the pattern with the smallest resolution to the left

I don’t. I have a vector that describes the variables [?e ?a] and then each binding is a vector of values that aligns with those column positions

perhaps my terminology was confusing, but I think that's very similar to what I wrote above, assuming "lookup" is basically what I meant by "filtering", right?

I'm doing these queries on nested EDN, rather than indexes, so a "lookup" of a tuple ends up doing a scan of a bunch of data but I'm not too worried about that rn

Yes, a resolution can be done via filtering

The API will look identical, but it’s just slower

Jena started life doing exactly this (which is why it sucked at the time :rolling_on_the_floor_laughing: )

> Because you’re iterating over the LHS but not the RHS, you want to keep the pattern with the smallest resolution to the left I think this is the part I've been getting hung up on. this is essentially handled by keeping an updated value of ?e that you pass to the next pattern, right?

how do you handle something like:

[:find ?movie ?person
 :where
 [_ :move/name ?movie]
 [_ :person/name ?person]]

That’s an outer product

So, [_ :move/name ?movie] resolves to: [["Gone with the Wind"] ["Romeo and Juliet"]] and [_ :person/name ?person] resolves to: [["Robert Downey Jr"] ["Cate Blanchett"]] So the result is: columns: [?movie ?person] [["Gone with the Wind" "Robert Downey Jr"] ["Gone with the Wind" "Cate Blanchett"] ["Romeo and Juliet" "Robert Downey Jr"] ["Romeo and Juliet" "Cate Blanchett"]]

This works, because if you were to bring in a constraint that bound ?movie and ?person then it would filter those down to the matches

This is why query planning matters. It: a) reduces the number of bindings to iterate over b) reduces memory consumption for intermediate results

Although, to be fair, when doing this in Clojure (b) isn’t as big an issue because your results are usually lazy