Permuted grouped aggregate

[MMcM]

Consider a query along the lines of

SELECT zip, MAX(value) FROM properties WHERE state = 'MA' GROUP BY zip ORDER BY 2 DESC

that aims to return some grouping keys ordered by an aggregate.

An ordinary plan requires unbounded storage of the intermediate aggregates and then a sort of that temporary table.

Some dialects support an interesting twist using the (relationally suspect)

SELECT DISTINCT zip FROM properties WHERE state = 'MA' ORDER BY value DESC

which can use an index on state, value. It produces results right away and needs space for tracking zips already seen.

To do this with precomputed aggregates, two B-trees are needed:

• An ordinary index on all the group keys and the value (so, state, zip, value).

• A permuted MAX index with state, MAX(value), zip.

Then for maintenance:

• An index insert needs to ascertain whether its value is the new maximum and update the permuted entry if so.

  • Assume the ordinary index has not yet been updated (we have no entry there).
  • Read ordinary (state, zip) reverse, limit 1. This is the maximum from another record for the same group and so the current maximum.
  • If this is absent or less than the value to be inserted: if not absent, remove permuted (state, that_value, zip) and insert permuted (state, value, zip).

• An index remove needs to determine whether its value is the current maximum and update the permuted entry if so.

  • Assume that the ordinary has been updated already (our entry is not there).
  • Read permuted (state, value, zip).
  • If not present, we are not it, stop.
  • Read ordinary (state, zip) reverse, limit 1. This is the maximum from another record for the same group and so the replacement maximum.
  • If this is absent or less than value (it might be equal): remove permuted (state, value, zip) and, if not absent, insert permuted (state, that_value, zip).