Arrangement batch formation costs in proportion to outstanding updates about differential-dataflow HOT 3 OPEN

Nonetheless, seems like a good idea to build the partially robust operator, which orders by times and if we want to support partially ordered times probably maintains runs of less_equal times which do admit binary search (but all of our updates may be an arbitrarily large number of runs).

I implemented this idea as part of MaterializeInc/materialize#25720 and also studied the linked paper out of interest. I noticed an interesting property that I thought I'd share.

In the paper the authors talk about whether a chain decomposition of a poset is optimal, with the lower bound being w chains where w is the width of the widest antichain. What I observed is that for the types we are mostly concerned with (arbitrarily nested Product<_, _>s) we can always get the optimal decomposition if we extract chains after having sorted the data with the linear extension of the poset.

As an example, if we take Product<u8, u8> we can see that the widest antichain that can be constructed has width 256 and is the following: {(255, 0), (254, 1), ..., (0, 255)}. Because the linear extension order will sort things lexicographically the maximum number of chains we can ever end up with is 256, since each update will be grouped to the chain corresponding to its first coordinate. This seems to generalize to additional levels of nesting.

from differential-dataflow.