Frank McSherry

I wrote a tiny vectorized interpreter last night, and .. thought I'd write up a post describing it. Nothing earth shattering here, but if you haven't seen one of these before it could be interesting! Probably easier to read than the J Incunabulum, but also less .. wow.

github.com/frankmcsherr...

Self-Correcting Materialized Views | Materialize Learn how Materialize uses self-correction to prevent output drift in materialized views, ensure consistency across upgrades, and enable in-place view replacement.

We have a recent @materialize.com post from Jan Teske about how MZ's self-correcting materialized views work. It's imo a very cool thing that unpacks some of the magic about how this could possibly work as the underlying system evolves.

materialize.com/blog/self-co...

As examples: 1. path queries, which follow edges repeatedly, are recursive but acyclic; 2. triangle queries, which find triples where each pair has an edge, are cyclic but not recursive.

I don't have super-clear words to describe acyclicity, but this might help: pages.cs.wisc.edu/~paris/cs784...

Ah so the good news is that in this context "cyclic" and "recursive" are different, and recursive queries can be fine, unless they are cyclic. Recursive-but-acyclic queries should still work out great with the demand transform.

The transform is also very similar to Yannakakis's algorithm, which also restricts data down to those values that could possibly produce outputs. Except it also applies to recursive queries. Also like Yannakakis's algorithm, it can get tripped up by cyclic (distinct from recursive) joins patterns.

The transform can be incredibly powerful, especially in declarative languages where you are taught to state everything, even if you only need some of it. Many bottom-up engines will produce all of the facts of all relations you define, even if you could have done less to get specific outputs.

I wrote a bit about the "demand transform" for Datalog (and other similar languages): github.com/frankmcsherr...

The idea of the transform is that rather than eagerly produce all the data you might ever need, you can start from the seed crystals of concrete values and data that might yield output.

A Datalog program for determining iterates of the Collatz conjecture.

If anyone ever told you Datalog is elegant, they probably haven't used datatoad yet. The evenness condition is an interesting example of relation-rather-than-function, though!

Ooo, also we got a version of the Polonius rules (Rust borrowing) running and validated as well. It's in the same ballpark as the best four-worker configurations, but it does seem to be a bit slower than datafrog on the "naive" Polonius rules from seven years ago.

One interesting-to-me observation is that the M2 seems faster than the EPYC 7543, at least on four cores. About 3:2 faster, so some amount of the datatoad "speed-up" is potentially attributable to this.

I went through and validated the output counts (numbers of facts) for most of the datatoad outputs. Some were hard to validate because datatoad sneaked in on my laptop but the other systems paged too hard, but everything seems correct.

github.com/frankmcsherr...

I'm still typing on a lot of the related code, but the neat thing is that (famous last words) it doesn't feel all that complicated. Yes, if you arrive through the theory of worst-case optimality, but not so much if you show up through relational programming, and just want a reasonable evaluator.

I put up a new post about work that I am perhaps irrationally excited about: the combination of worst-case optimal joins with relational programming.

github.com/frankmcsherr...

The high-order bits are that relational programming is very neat, and it fits great with modern (WCO) relational joins.

I think you end up with something like AoSoA (en.wikipedia.org/wiki/AoS_and...), where rather than full columnarization (SoA) you still want to chunk things, to play nice with the memory hierarchy (usually caches for AoSoA, but main memory in this case).

Without wanting to trivialize it, many of these are some form of defunctionalization, writing down as data the contents of the stacks you would expect to see, and then just choosing to move through the computations in different orders (less "depth-first" with datatoad than LFTJ).

I think the answer is "datatoad does nothing clever", but there are things you could do, most of which follow the scheme from the paper: produce as many A values as you can afford to, then pause and start to work on the B values, in chunks as large as you can afford to, for each chunk the C values.

And if it is (2.), there's a more extensive description about how to maintain bounded memory here: www.vldb.org/pvldb/vol11/....

We didn't implement that proposal though: "streaming" covered for us, and meant that the last join stage didn't get materialized, and the 2nd to last was small-er enough.

And thank you, by the way!

I took a quick peek at the content you are writing, and it's similarly great to see others thinking and writing about WCOJ. For others' benefit: finnvolkel.com/wcoj-graph-j...

I had a third, but having typed these out I'm guessing it's (2.) and will await confirmation and then unpack if so! (( tl;dr: it's not trivial, but possible; at the moment datatoad only "suspends" at key boundaries, so e.g. a cross join would still blow your memory budget ))

2. "How to suspend computation to avoid resource exhaustion"

LFTJ is "depth first" and forms whole tuples at a time, with all of its context on the stack, and is easy-ish to suspend. With a columnar approach is it easy to suspend between columns, and harder (but possible) within a column.

1. "How to introduce the bound GJ requires on tuples produced"

LeapFrog naturally does work proportional to the minimum number of tuples through its priority queue and galloping search. The "columnar" flavor explicitly forms the counts for each (key, atom), picks the minimum, and shards the data.

Ah, unfortunately I'm not sure I follow the question. I came up with a few things it could be asking, but I couldn't fully disambiguate "the limit on the tuples". I'll attempt a few answers, but feel free to re-ask slightly differently.

I wrote a post evaluating datatoad using the framework from the recent FlowLog paper: github.com/frankmcsherr....

It turns out it does well in some cases, worse in others, and has already improved by having other folks shine a light on its limitations by choosing problems and datasets I ignored!

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!

I wrote about datatoad as a "worst-case optimal Datalog", which .. perhaps doesn't typecheck. A previous result on streaming worst-case optimal joins seems to connect, and swapping "streaming" for "iterative" gives something that may be syntactically correct catnip.

github.com/frankmcsherr...

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

Getting crisper; now within ~1s (14.8s v 13.7s) of my hand-optimized plan that uses only binary joins, but without any plan hints. Erm, mostly. Hoping to bypass it, as a win for WCO joins. :D

Debunking the Myth of Join Ordering: Toward Robust SQL Analytics Join order optimization is critical in achieving good query performance. Despite decades of research and practice, modern query optimizers could still generate inferior join plans that are orders of m...

(( 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.