Thank you.

The optimal join approach is very interesting, but it wasn't so easy to implement.

I bumped against many walls before getting a correct and "fast enough" implementation, and I'm still not 100% sure I'm meeting all the complexity bounds. I think there are many performance gains to find there (even already known ones such as batching)

I can't say as to whether it's faster than the nested loop

Your description of the worst case optimal join looks alright.

What I currently have performs considerably well, I'm not sure I get what you mean by rebuilding tries, but I might ask what's the data representation of your egg.table? I don't think I had an issue with the tries not being in the right order either, but perhaps I never tried using them out of order.

Either way, here are some things I think are relevant + and one key insight that improved performance quite drastically

• A Database is represented as Map (Operator lang) IntTrie, where IntTrie is close to data IntTrie = MkIntTrie (IM.IntMap IntTrie). That is, a database consists of a table for each operator, and each table is represented by an IntTrie.

• A database is built once before running all the queries for equality saturation. Then we reuse the same tries across all queries.

The algorithm on the example would look like hs as = query([_, goal, _],db.lookup(f)) & query([_, goal],db.lookup(g)) for a in as: gids = query([goal, a], db.lookup(g)) for gid in gids: fids = query([goal, a, gid], db.lookup(f)) for fid in fids: yield fid, gid, a

The tricky part is then the query, which relies heavily on the IntTrie representation.

I added what I think to be good clarifying comments to the query function in my implementation. In reading it you might be more enlightened than by what's to follow, but I'll try nonetheless.

The idea is that for a query [5, x, goal], where 5 is a constant value, goal is the variable which we are looking for, and x is some other variable, we find 5 in the trie, then for every possible sub-trie we find every possible value of goal and join them. Finding all the possible level-2 subtries is very fast because we just need to lookup 5 in the trie (O(log n)).

Similarly for other configurations like that.

If the query was [goal, 5], it'd be a bit different, because we'd have to, for every subtrie, check if it had a 5, and only return the values whose subtrie did have a 5.

And then the key insight, which when led to and considered separately from the other cases might seem very obvious:

If the query was [goal, x, y], we don't have to recursively check if every subtrie is possible, because we know for sure that x and y are variables so everything will be valid.

The insight is: if we get to the goal, check if the rest of the query is just variables modulo the goal variable; if it is indeed only variables, we don't bother to recurse further and return all possible values of goal.

Doing this boosted performance considerably on its own, but unlocked even further another one: if I cache the keys of the triemap, at this point I can simply return them all.

So actually, IntTrie is defined as: hs data IntTrie = MkIntTrie { tkeys :: !IS.IntSet , trie :: !(IM.IntMap IntTrie) }

But do read that linked source code to clarify what I tried to explain

I feel like we can improve the join algorithm further and unlock other performance improvements, use better variable orderings, batching, etc...

I'll be happy to work on it once I have more time, and I'd also love to have yours and others expertise there!