[lsuresh]

We use monotonicity detection for various things. I believe (can double check) that it's used for max as well. But you're correct that in the general case, max is non-linear, so will need to maintain state.

Update from Leonid on current implementation: each group is ordered by the column on which we compute max, so it's O(1) to pick the last value from the index.

[nikhilsimha]

So the writes are O(N) then - to keeps reads at O(1)?

[ryzhyk]

Both reads and writes are O(1) in time complexity. Writes additionally have the log(N) amortized cost of maintaining the LSM tree.

[nikhilsimha]

gotcha! thanks for the clarification