...
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:
Code Block |
---|
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:
Code Block |
---|
Read: 2 * (M / N - 1) + 1 = 2 * M / N - 1 Write: 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.
- 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.
- 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).
...