Page History

...

With a tumbling window length of NM, and an advance step of N << M << N, each window aggregation update involves the following: for each window of the M / N windows this record falls into, issue a we would update (get, aggregate, and then put) each of the window this record falls into; and on average this record would fall into a total of M / N windows.

The total cost of it:

 Read:   M / N
Write:   M / N

...

Instead, we can aggregate per overlapping advance step (let's call it sub-window), and then return the aggregated value across all the overlapping period that this window covers. More specifically, we would only do an update on one sub-window, and then we would return the value by further aggregating the values of all sub-windows. This is a very common window aggregation techniques (see references below). The update is a single read plus a single write, but the further aggregation involves since a total of M / N windows would be updated, and we need to read the neighboring all the relevant sub-windows plus the sub-window that gets updated in order to emit the updated results.

For the total of M / N overlapping windows to be emitted, we would need to access neighboring 2 * (M / N - 1) reads:The plus the one sub-window that gets updated, so the total cost of it:

 Read:   2 * (M / N - 1)  + 1 = 2 * M / N - 1
Write:   1

...

1. We do not necessarily need to emit the result on each update when suppression is enabled; when we suppress the emission, we only pay one write and one read. As long as we can suppress more than one emission that requires reading M / N sub-windows, this approach would be preferred.
2. We can further optimize our implementation by buffering the partial sub-window aggregations to reduce repeating fetches on the latest sub-windows to reduce reads from the underlying state store: this is similar to the window-slicing / pre-aggregation techniques.
3. If the distribution of records falling into the sub-windows is sparse (i.e. a given window would only have records in a very small number of its sub-windows), then the underlying store's get calls could be more efficient to return empty results (e.g. RocksDB's bloom-filter).

...