Hippo: Accelerating Transaction Processing for Approximate Query Processing Engine with Sampling Semantics

Approximate query processing provides an aggregated value of large-scale data or speeds up machine learning pre-processing through sampling operations. Existing work has assumed that all data is stored in storage, and it requires scanning the entire data space followed by sampling for the approximation. Our work changes this assumption. We present Hippo, a concurrency control protocol that invalidates unnecessary data items on insert operations. Our algorithm is naturally integrated with the deterministic concurrency control protocol, and it never aborts transactions, which is essentially different from optimistic or pessimistic protocols. In our evaluation, the proposed protocol demonstrated performance improvements of up to 235 times compared to the CLMD concurrency control protocol.