  Aggregating data is fundamental to data analytics, data exploration, and
OLAP. Approximate query processing (AQP) techniques are often used to
accelerate computation of aggregates using samples, for which confidence
intervals (CIs) are widely used to quantify the associated error. CIs used in
practice fall into two categories: techniques that are tight but not correct,
i.e., they yield tight intervals but only offer asymptotic guarantees, making
them unreliable, or techniques that are correct but not tight, i.e., they offer
rigorous guarantees, but are overly conservative, leading to confidence
intervals that are too loose to be useful. In this paper, we develop a CI
technique that is both correct and tighter than traditional approaches.
Starting from conservative CIs, we identify two issues they often face:
pessimistic mass allocation (PMA) and phantom outlier sensitivity (PHOS). By
developing a novel range-trimming technique for eliminating PHOS and pairing it
with known CI techniques without PMA, we develop a technique for computing CIs
with strong guarantees that requires fewer samples for the same width. We
implement our techniques underneath a sampling-optimized in-memory column store
and show how to accelerate queries involving aggregates on a real dataset with
speedups of up to 124x over traditional AQP-with-guarantees and more than 1000x
over exact methods.
