In this paper, we present BlinkDB, a massively parallel, approximate query engine for running interactive SQL queries on large volumes of data. BlinkDB allows users to tradeo query accuracy for response time, enabling interactive queries over massive data by running queries on data samples and presenting results annotated with meaningful error bars. To achieve this, BlinkDB uses two key ideas: ( ) an adaptive optimization framework that builds and maintains a set of multi-dimensional strati ed samples from original data over time, and ( ) a dynamic sample selection strategy that selects an appropriately sized sample based on a query's accuracy or response time requirements. We evaluate BlinkDB against the well-known TPC-H benchmarks and a real-world analytic workload derived from Conviva Inc., a company that manages video distribution over the Internet. Our experiments on a node cluster show that BlinkDB can answer queries on up to TBs of data in less than seconds (over × faster than Hive), within an error of -. Modern data analytics applications involve computing aggregates over a large number of records to roll-up web clicks, online transactions, content downloads, and other features along a variety of di erent dimensions, including demographics, content type, region, and so on. Traditionally, such queries have been executed using sequential scans over a large fraction of a database. Increasingly, new applications demand near real-time response rates. Examples may include applications that (i) update ads on a website based on trends in social networks like Facebook and Twitter, or (ii) determine the subset of users experiencing poor performance based on their service provider and/or geographic location. Over the past two decades a large number of approximation techniques have been proposed, which allow for fast pro-Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. April -, Czech Republic Copyright © ACM ----/ / . . . . cessing of large amounts of data by trading result accuracy for response time and space. ese techniques include sampling [ , ], sketches [ ], and on-line aggregation [ ]. To illustrate the utility of such techniques, consider the following simple query that computes the average SessionTime over all users originating in New York: SELECT AVG(SessionTime) FROM Sessions WHERE City = 'New York' Suppose the Sessions table contains million tuples for New York, and cannot t in memory. In that case, the above query may take a long time to execute, since disk reads are expensive, and such a query would need multiple disk accesses to stream through all the tuples. Suppose we instead executed the same query on a sample containing only , New York tuples, such that the entire sample ts in memory. is would be orders of magnitude faster, while still providing an approximate result within a few percent of the actual value, an accuracy good enough for many practical purposes. Using sampling theory we could even provide condence bounds on the accuracy of the answer [ ]. Previously described approximation techniques make different trade-o s between e ciency and the generality of the queries they support. At one end of the spectrum, existing sampling and sketch based solutions exhibit low space and time complexity, but typically make strong assumptions about the query workload (e.g., they assume they know the set of tuples accessed by future queries and aggregation functions used in queries). As an example, if we know all future queries are on large cities, we could simply maintain random samples that omit data about smaller cities. At the other end of the spectrum, systems like online aggregation (OLA) [ ] make fewer assumptions about the query workload, at the expense of highly variable performance. Using OLA, the above query will likely nish much faster for sessions in New York (i.e., the user might be satis ed with the result accuracy, once the query sees the rst , sessions from New York) than for sessions in Galena, IL, a town with fewer than , people. In fact, for such a small town, OLA may need to read the entire table to compute a result with satisfactory error bounds. In this paper, we argue that none of the previous solutions are a good t for today's big data analytics workloads. OLA
Distributed approximation systems The authors in REF present an approximate query processing system that provides an efficient strategy to get a sample from the dataset.
BlinkDB: queries with bounded errors and bounded response times on very large data
EuroSys '13
Computer Science