AQapprox: Aggregation Queries Approximation with Distribution-Aware Online Sampling

Approximate query processing (AQP) is an effective way to provide approximate results for SQL queries, which relaxing accuracy in exchange for higher processing speed. In sampling-based AQP techniques, random sampling works well for uniformly distributed data but performs poorly on skewed data. To address this problem, we propose a distribution-aware approximation framework called AQapprox (aggregation queries approximation), to approximate queries more efficiently and accurately by extending Sapprox. We construct a probabilistic Map, which records the occurrences of sub-datasets on categorical columns and related statistics on numerical columns at each segment of the whole dataset. When a query arrives, AQapprox will combine Map and adaptively use different sampling methods based on the distribution. Experimental results on both real and synthetic datasets show that AQapprox can achieve a speedup by up to 5.9 for skewed data, 64 for uniform data over Sapprox, and has higher accuracy on multi-column queries.