While I think the worst-case optimality is great to read about, it also results in performance that improves on what I've been able to do with conventional binary joins (now at around 11.9s, vs ~13s for the best binary join plan I found).

Yay database theory!

And now down to 14.2s (storing some data in 4 rather than 2 bytes to get an optimized implementation to kick in).

(( There's other recent work on join robustness, which I think dovetails with WCOJ, but may be technically distinct. I'm thinking of things like arxiv.org/abs/2502.15181 and arxiv.org/abs/2403.01631 ))

Wrt FreeJoin, I think the columnar approach makes it clearer that you can take the old and new behaviors a la carte, without needing custom datastructures and new papers. That's subject to verification from other folks working in the space, but it seems pretty easy to get the best of both worlds.

For example, when doing the graph motif tracking in www.vldb.org/pvldb/vol11/..., we found one of the nodes had degree ~45M. Any join implementation that investigates the 45M^2 possible pairs of neighbors would just be dead in the water.

My experience has been that the column-oriented "bfs generic join" has been plenty practical. If you are dealing with cyclic joins, don't wait to try out at least some flavor of WCOJ, though. When you need them, you really really need them.

And many thanks due to @dov.dev and @antiguru.bsky.social, who both asked questions and proposed good ideas.

One thing I like is that I stopped being a bad researcher and .. did some reading rather than only writing. There are some papers about columnar Datalog already (links at the end)! However, I don't think I fully understand them yet. More reading required!

The closest I've found is github.com/kparc/ksimple which I'll work through, but .. most of the write-ups seem to conflate the esoteria of monadic/dyadic glyphs with the implementation architecture you might use, and .. boy do I want to read about the latter without trudging through the former.