Implement aggregate reversals for MAX/MIN aggregate functions

[purplefox]

If a delete arrives at an push aggregator then the value needs to be reversed out of the current aggregation. In the case of some aggregations such as sum or count, this is trivial. However for others as max/min it is much more difficult.

Consider the case for MIN, the current aggregate value (the current minimum) is 10, and we get a reversal for the value 10. In order to reverse the MIN we need to know what was the next lowest value before 10, which requires us to keep a history of all changes to the aggregation and efficiently find the next smallest value.

We can use something similar to a "hierarchical reduce" to implement this.

We arrange previous values in a max/min heap structure???

Copied from my notes:

---

tree, leaves are groups of records and a max on each node

if a record is removed only the max of that group changes, so to compute the total max we only need to walk up the levels of the tree, not through every group.

so max customer age group by village, lots of villages.

we maintain a table with

level, max, village

0, 23, bayford 0, 12, wincanton 0, 56, castle cary

next level

1, 56, blank

so basically we maintain a tree in a table,

to recalculate the max we only need to do log(N) lookups, we also need to make log(n) writes

for small tables it would be quicker to scan