3 ms·
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
by lsuresh 2y ago
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 2y agoSo the writes are O(N) then - to keeps reads at O(1)?
- ryzhyk 2y agoBoth reads and writes are O(1) in time complexity. Writes additionally have the log(N) amortized cost of maintaining the LSM tree.
- nikhilsimha 2y agogotcha! thanks for the clarification