iiinova — where your digital self keeps evolving

Frank McSherry @frankmcsherry.bsky.social · 10/06/2026

I think the tl;dr is "if you are moving this much data around, you have already paid a lot for it; this isn't what will kill you". The general principle is to avoid disproportionate work, e.g. scanning/copying more data than INPUT + OUTPUT. Copying the output isn't (presently) a source of stress.

000

Frank McSherry @frankmcsherry.bsky.social · 10/06/2026

Yeah, not sure what you are looking at, I'm afraid! If you apply a "filter" in the form of FactContainer::act_on() it definitely will copy, though .. intentionally. There are other approaches where you keep validity bits throughout to minimize copies; we don't worry about and memcpy instead.

100

Frank McSherry @frankmcsherry.bsky.social · 09/06/2026

Across the multiple paths, lines in your figure, there may be multiple orders that require alternate representations of the data. This costs, but also it's not clear that there are more efficient ways to perform the necessary look-ups. You could jointly optimize, for sure, but not unlike MQO (hard).

000

Frank McSherry @frankmcsherry.bsky.social · 09/06/2026

I think what usually happens is that there is one trie for input to each WCO join path (e.g. each line in that figure you have). The trie supports count and join/semijoin for each prefix of terms. For that path at least, you needn't have redundancy; just one representation.

100

Frank McSherry @frankmcsherry.bsky.social · 09/06/2026

There is no attempt at factorization, and afaict no moment where there will be bindings for { A, B } that then branch in two different directions. There could be, if there were common subexpressions identified, but this isn't done yet. In that case, the data would be reused, but not copied (Rc).

100

Frank McSherry @frankmcsherry.bsky.social · 09/06/2026

I'm not certain I follow, and .. if it helps we can do it as an issue on the datatoad repo instead. Datatoad has a list of Datalog rules, each of which are handled independently. If you have multiple rules with the same head, they are handled independently.

100

Frank McSherry @frankmcsherry.bsky.social · 09/06/2026

The datatoad book (www.frankmcsherry.org/datatoad/cha...) now comes with a WASM playground to try out some of the problematic Datalog it handles. The book is not fully revved to always have runnable examples, but I'll get on that!

frankmcsherry.org

Introduction

140

Frank McSherry @frankmcsherry.bsky.social · 08/05/2026

The worked example is a triangle query, though many joins would work, with an added `x + y = z` constraint. That constraint can become a relation, and in our example it reduces query time by 1000x. You don't have to enumerate x, y, z and then apply the predicate; you can just leap to the answers.

010

Frank McSherry @frankmcsherry.bsky.social · 08/05/2026

I wrote about "directional predicates" in datatoad. Treating predicates as relations can be much more powerful than predicates as .. predicates or even functions. Computation can go faster, because you reveal more to the computer about how to get work done. github.com/frankmcsherr...

github.com

120

Frank McSherry @frankmcsherry.bsky.social · 01/05/2026

I got Claude to help with a blog index refresh, surfacing about 1.5 years of posts to the front page that had been languishing: github.com/frankmcsherr.... It unintentionally included one unfinished post that I'll now have to get sorted out. :D

github.com

GitHub - frankmcsherry/blog: Some notes on things I find interesting and important.

Some notes on things I find interesting and important. - frankmcsherry/blog

030

Frank McSherry @frankmcsherry.bsky.social · 01/04/2026

We now have datatoad's mdbook section on joins. It covers the planning of joins of abstract directed relations, and their execution by a mix of binary and worst-case optimal join stages. It's pretty tight, but I don't think it's missing much except examples. www.frankmcsherry.org/datatoad/cha...

frankmcsherry.org

Joins

030

Frank McSherry @frankmcsherry.bsky.social · 29/03/2026

Creating demos is definitely a thing it has made easier. And mini benchmarks to find the moment where a point becomes true (or .. not if never). I'll certainly be using it for this, though .. I have had to lean on it a few times to make sure the comparisons were fair.

010

Frank McSherry @frankmcsherry.bsky.social · 29/03/2026

As part of an attempt to get Claude to help me communicate better, we have .. a Claude-assisted mdbook for datatoad: www.frankmcsherry.org/datatoad/int... Still a work in progress, but it came together much faster with help.

frankmcsherry.org

Datatoad

051

Frank McSherry @frankmcsherry.bsky.social · 28/03/2026

Totally innocent question: I've found Claude has made me rather productive, at a rate that outpaces what I can write about solo. I'm trying to figure out if there is value/space for an intentionally "slop" line of posts that explains work that has been done, minus the alleged charm and certain salt.

210

Frank McSherry @frankmcsherry.bsky.social · 26/03/2026

The classic example of this is if you build an index with a key that has type TEXT (in PostgreSQL say), but you need an index of type VARCHAR. Not the same type, but an identical physical representation that is all we need once we've done method resolution.

000

Frank McSherry @frankmcsherry.bsky.social · 26/03/2026

A very nice post out of @materialize.com about "representation types" which remove non-structural distinctions between types as they approach the dataflow rendering layer, unlocking physical optimizations across logically distinct types: materialize.com/blog/no-clas...

materialize.com

No Classification without Represention | Materialize

Learn how Materialize improves query performance by compiling SQL's type system to a simpler system of

150

Frank McSherry @frankmcsherry.bsky.social · 24/03/2026

Moreover, I hadn't realized that the collection it develops iteratively contains only negative records. Very unorthodox!

000

Frank McSherry @frankmcsherry.bsky.social · 23/03/2026

Admittedly, its first version was worse, but this version that it got to was great. My version starts from all edges and removes failed proposals, but Claude realized that starting from non-empty collections requires a gadget that does work, and better to start from no rejections and build up.

100

Frank McSherry @frankmcsherry.bsky.social · 23/03/2026

Fun experiment du jour: can Claude write stable matching in differential dataflow using a simplified language that hides any of details of DD. Yes, it turns out! Correct out of the box, and with a bit of nudging it got something better than I have written:

A program that performs Gale-Shapely using a small language for differential dataflow.

160

Frank McSherry @frankmcsherry.bsky.social · 21/03/2026

Here's an example, of label propagation on a graph. Salmon is feedback operators, purple are arrangements. The teal boundary is of an iterative scope.

A graph, with edges and differently colored operators, describing their function.

010

Frank McSherry @frankmcsherry.bsky.social · 21/03/2026

Now with arrangement sizes, and due to go out with the next release of the crate.

100

Frank McSherry @frankmcsherry.bsky.social · 20/03/2026

With Claude, and a few lines of Rust, you can add a live timely dataflow visualizer to your programs, giving you visibility into where the time goes, and soon (surely) arrangement record counts as well!

130

Frank McSherry @frankmcsherry.bsky.social · 19/03/2026

The headline numbers are about ticking dataflows comprising 1,000,000 operators at ~4ms / iteration, rather than 350ms /iteration. If that sounds like a lot of dataflow operators, have I got news for you about SQL. :D But also, it's an extreme number to highlight the problem, and distinct solution.

000

Frank McSherry @frankmcsherry.bsky.social · 19/03/2026

A new blog post about accelerating timely dataflow by 100x. Part of the story is how timely is able to do this, and .. seemingly .. other stream processor are not. It comes down to a fundamentally different approach to tracking time: globally rather than locally. github.com/frankmcsherr...

github.com

130

Frank McSherry @frankmcsherry.bsky.social · 15/03/2026

Totally. It's not hyperbole at all. I feel like a whole team of principal engineers. Tbh on whether I produce work like them, or just feel that way, but .. yeah. :D

121

Frank McSherry @frankmcsherry.bsky.social · 14/03/2026

This was not as reassuring as I hoped.

Claude declines to say that there is no planned biomass mulcher.

240

Frank McSherry @frankmcsherry.bsky.social · 14/03/2026

Re-reading it, while Claude did find typos in the post, it didn't notice the grammatical error in the first sentence (racing to fix, in case you don't see it either by the time you read the post). Next step is to tell it that grammatical errors count as typos, because how could I make mistakes?

100

Frank McSherry @frankmcsherry.bsky.social · 14/03/2026

I used Claude for the first time this month, having only ever used copilot before (and .. stopped immediately afterwards). It turns out .. I am maybe obsolete? We improved `columnar` together, and each wrote a post about it. (linked within my post).

github.com

1110

Frank McSherry @frankmcsherry.bsky.social · 05/03/2026

A recent post by @dov.dev about Materialize's new Iceberg sink, and generally about connecting live operational data to analytics stores. Some interesting detail about (overcome) streaming-batch friction, and turning pristine CDC streams into .. Iceberg! materialize.com/blog/making-...

materialize.com

Making Iceberg Work for Operational Data | Materialize

Apache Iceberg was built for batch analytics — but operational data changes continuously. Learn how Materialize streams live, transactionally consistent data into Iceberg without the memory and latenc...

082

Frank McSherry @frankmcsherry.bsky.social · 04/03/2026

Worlds collide: pretty sure someone at the MTA plays FFXIV:

000

Frank McSherry @frankmcsherry.bsky.social · 01/03/2026

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

github.com

092

Frank McSherry @frankmcsherry.bsky.social · 26/02/2026

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

materialize.com

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.

020

Frank McSherry @frankmcsherry.bsky.social · 07/02/2026

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

pages.cs.wisc.edu

110

Frank McSherry @frankmcsherry.bsky.social · 07/02/2026

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.

100

Frank McSherry @frankmcsherry.bsky.social · 05/01/2026

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.

100

Frank McSherry @frankmcsherry.bsky.social · 05/01/2026

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.

100

Frank McSherry @frankmcsherry.bsky.social · 05/01/2026

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.

github.com

120

Frank McSherry @frankmcsherry.bsky.social · 27/12/2025

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!

A Datalog program for determining iterates of the Collatz conjecture.

010

Frank McSherry @frankmcsherry.bsky.social · 25/12/2025

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.

000

Frank McSherry @frankmcsherry.bsky.social · 25/12/2025

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.

100

Frank McSherry @frankmcsherry.bsky.social · 25/12/2025

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

github.com

130

Frank McSherry @frankmcsherry.bsky.social · 23/12/2025

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.

000

Frank McSherry @frankmcsherry.bsky.social · 23/12/2025

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.

github.com

120

Frank McSherry @frankmcsherry.bsky.social · 16/12/2025

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

en.wikipedia.org

AoS and SoA - Wikipedia

010

Frank McSherry @frankmcsherry.bsky.social · 16/12/2025

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

100

Frank McSherry @frankmcsherry.bsky.social · 16/12/2025

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.

100

Frank McSherry @frankmcsherry.bsky.social · 16/12/2025

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.

vldb.org

010

Frank McSherry @frankmcsherry.bsky.social · 16/12/2025

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

finnvolkel.com

WCOJ - Graph-Join correspondence · Finn Völkel

110

Frank McSherry @frankmcsherry.bsky.social · 16/12/2025

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 ))

210