BlinkDB: Queries with Bounded Errors and Bounded Response Times on Very Large Data

In this paper, we present BlinkDB, a massively parallel, sampling-based approximate query engine for running ad-hoc, interactive SQL queries on large volumes of data. The key insight that BlinkDB builds on is that one can often make reasonable decisions in the absence of perfect answers. For example, reliably detecting a malfunctioning server using a distributed collection of system logs does not require ana-lyzing every request processed by the system. Based on this insight, BlinkDB allows one to trade-off query accuracy for response time, enabling interactive queries over mas-sive data by running queries on data samples and present-ing results annotated with meaningful error bars. To achieve this, BlinkDB uses two key ideas that differentiate it from pre-vious work in this area: (1) an adaptive optimization frame-work that builds and maintains a set of multi-dimensional, multi-resolution samples from original data over time, and (2) a dynamic sample selection strategy that selects an ap-propriately sized sample based on a query’s accuracy and/or response time requirements. We have built an open-source version of BlinkDB and validated its effectiveness using the well-known TPC-H benchmark as well as a real-world an-alytic workload derived from Conviva Inc [3]. Our experi-ments on a 100 node cluster show that BlinkDB can answer a wide range of queries from a real-world query trace on up to 17 TBs of data in less than 2 seconds (over 100 × faster than Hive), within an error of 2 − 10%. 1