Abstract

The goal of deterministic approximation is to produce guaranteed bounds for aggregates in SQL queries (i.e., the exact value is guaranteed to be contained within those bounds). We present our ongoing work on BitGourmet, a novel system for deterministic approximation, and first experimental results. BitGourmet reduces processing time, compared to standard processing, by considering only a subset of bit positions in every column. It stores the entire database as a collection of bit vectors. Given user-specified constraints on approximation precision, BitGourmet selects an optimal subset of bit vectors to generate a result of the desired precision with minimal processing overheads. BitGourmet features a specialized processing engine with scenario-specific operators. It uses a multi-objective, cost-based optimizer that employs cardinality, cost, and error models based on bit-level data statistics. Furthermore, it uses a proactive buffer management strategy based on query predictions to fill its buffer with bit vectors that are likely to be relevant for future queries. We provide first experimental results, demonstrating significant speedups over state-of-the-art exact processing engines and increased result precision, compared to sampling-based approximation engines.