Approximate Query Processing under Updates

Query processing under updates (a.k.a. incremental view maintenance) has received increasing attention in recent years, from both theoretical and practical angles. While existing algorithms work well in handling reporting queries, they may incur a high cost on aggregation queries, which are the more important type of analytical workload. In this paper, we show that by allowing a small approximation error, aggregation queries can be processed efficiently under updates. Specifically, we design a new approximate query processing (AQP) algorithm that can maintain the result of any free-connex aggregation query in logarithmic time amortized per update over an insertion-only update sequence. For update sequences with both insertions and deletions, the logarithmic time bound does not hold, due to known lower bounds. Practically, our algorithm performs well on both insertion-only and fully dynamic update sequences. Our experimental results show that, with a 10% error guarantee, the algorithm achieves average speedups of 1.5x, 4.8x, and 13.4x over three exact solutions. Our algorithm works in a general semiring framework, which incorporates a variety of aggregations, including count, sum, avg, max, and count distinct, possibly with a group by.