BlinkDB: queries with bounded errors and bounded response times on very large data

By Sameer Agarwal, Barzan Mozafari, Aurojit Panda, Henry Milner, Samuel Madden, Ion Stoica. European Conference on Computer Systems, 2012

807 citations recorded by the source corpus.

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 trade-off 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: (1) an adaptive optimization framework that builds and maintains a set of multi-dimensional stratified samples from original data over time, and (2) 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 100 node cluster show that BlinkDB can answer queries on up to 17 TBs of data in less than 2 seconds (over 200 x faster than Hive), within an error of 2-10%.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/39c900c365f9d42e288f94cd48b4ceac33372799

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Analysis of Large-Scale Multi-Tenant GPU Clusters for DNN Training Workloads (2019, methodology): “More recently, approximation is used in batch processing [7,9,47] and live video analytics [54].”
A Berkeley View of Systems Challenges for AI (2017, methodology): “Examples of such methods include sampling and sketching, which have already been successfully employed for analytics workloads [4, 10, 28, 51, 81].”
Fides: Towards a Platform for Responsible Data Science (2017, background): “Sampling procedures for relational databases have been studied for decades [1, 11, 28], often focused on how sampling operators can be designed to commute with relational algebra operators to improve performance while maintaining”
A survey on platforms for big data analytics (2014, neutral): “On the top of the stack are many Spark wrappers such as Spark Streaming (Large Scale real-time stream processing), Blink DB (queries with bounded errors and bounded response times on very large data) [23], GraphX (Resilient distributed Graph System on Spark) [24] and MLBase (distributed machine lear”
Big data analytics on Apache Spark (2016, background): “In addition, the DataFrame and Dataset APIs of Spark SQL provide a higher level of abstraction for structured data.”
PrivateClean: Data Cleaning and Differential Privacy (2016, methodology): “Approximate Query Processing: Approximate query processing (AQP) is a well studied problem [3,14,35] in which results of aggregate queries are approximated from samples, wavelets, or sketches.”
Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views (2015, methodology): “Refer to [4,41] for a detailed discussion on the scaling factors.”
Low Latency Geo-distributed Data Analytics (2015, methodology): “Further, Iridium is complementary to approximation techniques [15, 18].”
PrivateSQL: A Differentially Private SQL Query Engine (2019, methodology): “A synopsis captures important statistical information about the database – analogous to pre-computed samples in approximate query processing [4].”
The Effects of Interactive Latency on Exploratory Visual Analysis (2014, background): “Latencies in state-of-the-art systems can range from 20 milliseconds up to multiple seconds for a unit task [2, 28, 29].”
Live Video Analytics at Scale with Approximation and Delay-Tolerance (2017, methodology): “Approximation is also used by recent [20, 23, 84] and older [47, 53] batch querying systems using statistical models for SQL operators [38].”
A Data Quality Metric (DQM): How to Estimate the Number of Undetected Errors in Data Sets (2016, background): “This is related to the known problem of query selectivity in approximate query processing [17, 2].”
Handbook of Big Data (2016, background): “In the context of general interactive query engines, BlinkDB is the best known and current state of the art [1].”
SampleClean: Fast and Reliable Analytics on Dirty Data (2015, methodology): “It has been well studied in the database community since the 1990s [27, 5, 36, 35], and methods such as BlinkDB [6] have drawn renewed attention in recent big data research.”