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

Sameer Agarwal; Aurojit Panda; Barzan Mozafari; Samuel Madden; Ion Stoica

Source-linked AI summary

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

Sameer Agarwal, Aurojit Panda, Barzan Mozafari, Samuel Madden, Ion Stoica

arXiv:1203.5485v2Mar 25, 2012cs.DBcs.DC

TL;DR

Large-scale ad-hoc analytics often require slow full-data scans, while users need rapid answers with controllable accuracy. BlinkDB addresses this with adaptive multi-dimensional, multi-resolution sampling and runtime sample selection. On workloads including Conviva data, it answers queries over 17 TB within 2 seconds at 90-98% accuracy on a 100-node cluster.

Problem
Full-data scans over multi-terabyte datasets can take minutes, limiting rapid diagnosis and exploratory analysis when query requirements are unpredictable.
Method
BlinkDB builds and maintains multi-dimensional, multi-resolution samples and dynamically selects samples to satisfy user-specified error or response-time constraints.
Results
17 TB of data can be queried within 2 seconds at 90-98% accuracy on a 100-node cluster across benchmark and real-world workloads.
Takeaways & Limitations
BlinkDB enables interactive SQL aggregation over massive data by trading query accuracy for response time and reporting meaningful error bounds.
Takeaways & Limitations
Offline sampling can produce unrepresentative samples, and sample construction assumes query-template columns remain fairly stable over time.

Abstract

from arXiv · show

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 analyzing 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 massive data by running queries on data samples and presenting results annotated with meaningful error bars. To achieve this, BlinkDB uses two key ideas that differentiate it from previous work in this area: (1) an adaptive optimization framework 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 appropriately 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 analytic workload derived from Conviva Inc. Our experiments 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\times faster than Hive), within an error of 2 - 10%.

1. INTRODUCTION

BlinkDB targets unpredictable analytics that require near-real-time answers despite multi-terabyte scans. It uses optimized stratified, multi-dimensional, multi-resolution sampling and runtime sample selection to trade accuracy for response time.

Motivation: 30−45 minutes on Hadoop, or 5−10 minutes with all data cached, can be required for a simple average over 10 TB.These full-data scan times are described as unacceptable for rapid diagnosis and frustrating for exploratory analysis.
Approach: BlinkDB answers SQL aggregation queries with user-specified response-time or error constraints and meaningful error bounds relative to full-data answers.It runs queries on selected samples rather than the complete dataset.
Approach: Multi-dimensional stratified samples are chosen using query-template history, data skew, and a storage threshold to cover past and future ad-hoc queries.Maintaining stratified samples over every attribute combination is impractical, motivating the optimization formulation.
Approach: Multi-resolution sample families let BlinkDB select sample sizes at runtime for different accuracy or response-time bounds while minimizing the corresponding cost.The system can refine samples as data distributions or query loads change.
Evaluation: 17 TB of data can be queried within 2 seconds at 90-98% accuracy on a 100-node cluster using BlinkDB’s sampling design.The reported evaluation uses TPC-H benchmarks and a real-world Conviva workload.

2. SYSTEM OVERVIEW

BlinkDB combines offline sample construction and maintenance with runtime selection of samples based on user error or response-time constraints. Its overview also states workload and join assumptions that bound supported use cases.

Query interface: BlinkDB accepts SQL aggregation queries annotated with either maximum error and confidence or a maximum execution time.For example, users can request ±10% error at 95% confidence or the most accurate result within 5 seconds.
Assumptions: Arbitrary joins require a suitable stratified sample containing the join key, unless one joined table fits in memory; query-template columns are assumed fairly stable over time.Specific predicate values need not be known in advance, and unseen query templates can still use available samples.
Offline sampling: The offline module creates uniform and stratified samples using data statistics and historical query templates, while maintenance updates them as data or workloads change.The optimization favors useful and skewed column sets and aims to avoid service interruption.
Runtime selection: The runtime module estimates selectivity, error, and response time on smaller samples, then extrapolates to choose a sample satisfying the query’s constraints.BlinkDB characterizes this behavior through an Error-Latency Profile.
Sample organization: Sample families contain multiple granularities, including uniform and column-biased stratified families selected according to workload templates and data distribution.The example describes families built under a storage budget and selected for each query’s columns and constraints.

3. SAMPLE CREATION

BlinkDB creates multi-dimensional, multi-resolution stratified sample families to support finer accuracy–response-time tradeoffs for ad-hoc queries. It selects column sets using data skew, workload characteristics, and sample-storage cost, while exploiting nested samples and controlled sample sizes to limit overhead and preserve query guarantees.

3.1 Multi-resolution Stratified Samples: Stratified sampling improves convergence and reduces missing rare subgroups in highly skewed datasets, where uniform samples can require scanning much more data.Rare values are deliberately represented sufficiently in the sample, improving estimates for infrequent groups.
3.1 Multi-resolution Stratified Samples: A sample family is a sequence of stratified samples over one column set, with multiple sizes that provide finer accuracy–response-time tradeoffs.The family is defined for a column set φ and contains m samples.
3.1 Multi-resolution Stratified Samples: Each stratified sample caps every value’s frequency at K_i, retaining all rows when the frequency is at most K_i and K_i random rows otherwise.The stored sample contains all original-table columns even though stratification is performed on φ.
3.1 Multi-resolution Stratified Samples: Nested samples allow smaller samples to be constructed from the largest sample, reducing storage to approximately that required for the largest sample plus metadata.The samples are sequentially sorted by the columns in φ to facilitate query processing.
3.1 Multi-resolution Stratified Samples: Exponentially decreasing sample caps provide bounded approximation to the optimal sample: response time is within c, while standard deviation is within √c under the stated conditions.The sample caps decrease by factor c, with K_i = ⌊K_1/c^i⌋ and m = ⌊log_c K_1⌋.
3.2 Sample-Set Selection: BlinkDB chooses candidate column sets for stratified samples by combining a skew metric, query-template workload weights, and sample-storage costs in an optimization problem.The skew metric counts distinct values whose frequencies are below the largest sample’s cap; workload weights represent query-template frequency or importance.

4. BLINKDB RUNTIME

BlinkDB selects samples at runtime to satisfy query error or response-time constraints, using probes and error-latency estimates rather than fixed selectivity or latency models. It supports conjunctive and disjunctive predicates while correcting estimates from stratified samples.

Online sample selection: BlinkDB selects a sample family from query filtering and grouping columns, then chooses a resolution within that family.If no family covers the query columns, it probes the smallest samples across families and favors the best selected-row-to-read-row ratio.
Online sample selection: BlinkDB probes smaller samples to estimate selectivity, query complexity, and input distributions before selecting a runtime sample.This avoids directly modeling highly variable selectivity and distributed response times.
Sample-size selection: The Error-Latency Profile estimates how error decreases and response time increases as sample size grows.BlinkDB builds the profile by running the query on smaller samples and projecting performance for larger ones.
Sample-size selection: For error constraints, BlinkDB estimates the required selected-row count and chooses the smallest maintained sample expected to meet that constraint.The selected sample uses estimates of selectivity, variance, or input distribution and is chosen from the available sample family resolutions.
Sample-size selection: For response-time constraints, BlinkDB estimates the maximum readable input size and assumes latency scales linearly with input size.The estimate depends on data placement, query complexity, and available parallelism; smaller samples are run to avoid in-memory nonlinearities.
Stratified samples: Stratified samples require correction because directly scaling their aggregates can produce biased estimates.BlinkDB applies a corresponding query-processor correction when operating on stratified samples.

5. IMPLEMENTATION

BlinkDB extends Hive’s query, sampling, metadata, and execution components to support bounded-error and bounded-response-time queries over distributed samples. Its implementation runs across Hadoop MapReduce or Spark and stores samples in HDFS.

System architecture: The implementation stack uses Hive on top, Hadoop MapReduce or Spark at execution, and HDFS for storage.Spark support is provided through Shark.
Query integration: BlinkDB adds a query-interface shim and parser extensions so HiveQL queries can specify response-time and error bounds.The parser also detects data input and invokes sample creation or maintenance as needed.
Sampling infrastructure: BlinkDB’s sample-creation module maintains random and multi-dimensional samples at multiple granularities.It also optimizes sample block size and placement in HDFS for distributed creation and processing.
Sampling infrastructure: Uniform samples are generally created in a few hundred seconds, while stratified samples take 5 - 30 minutes depending on stratification cardinality and shuffling.Stratified-sample creation time depends on the number of unique values, reducers, and shuffled data volume.

6. EVALUATION

BlinkDB was evaluated on Conviva and TPC-H workloads using a 100-node cluster, comparing approximate sampling against full-data execution and alternative sample designs. It substantially reduced response times while maintaining controlled error and convergence, and selected samples to meet requested time or error bounds.

Workloads and setup: 17 TB and 1 TB datasets were evaluated on Conviva and TPC-H workloads, respectively, using a 100-node cluster.The default experimental configuration used a 50% additional storage budget.
BlinkDB vs. no sampling: 10–100× faster response times were achieved by BlinkDB than Hive and Shark for a filtered, grouped average query with a 1% error bound at 95% confidence.The comparison used Conviva subsets of 7.5 TB and 2.5 TB, with each query repeated 10 times.
Error properties: Multi-dimensional stratified samples produced smaller statistical errors than one-dimensional or uniform samples for common query templates.The optimization framework minimized expected error, so single-dimensional samples performed better for some specific templates.
Convergence properties: Error bars from multi-dimensional samples converged orders of magnitude faster than random samples and significantly faster than single-dimensional stratified samples.The convergence experiment used 17 TB of Conviva data and measured latency to reach an error bound at 95% confidence.
Time and accuracy guarantees: BlinkDB accurately selected samples to satisfy target response times, while measured errors were almost always at or below requested bounds ranging from 2% to 32%.At higher requested error rates, measured error approached the bound because smaller samples produced wider error bounds.
Scaling up: Scalability was evaluated with selective and bulk Conviva query suites, each containing 40 unique queries, across cluster sizes.Each query operated on 100n GB of data for a cluster of n nodes.

7. RELATED WORK

Related systems reduce query latency through specialized structures, extra resources, approximate processing, or sampling. BlinkDB differs by combining reusable multi-dimensional samples with runtime sample selection for ad-hoc queries and both time and error constraints.

Resource-based approaches: Systems such as Spark, Dremel, and Shark provide low latency when data fits aggregate memory but slow as data grows without proportionally added resources.Their performance depends on processing relatively small amounts of data per node.
Approximate query processing: Approximate query processing uses sampling or non-sampling methods to provide low-latency answers for decision-support workloads.The related work includes both database sampling techniques and specialized structures.
Sampling approaches: STRAT chooses a single stratified sample from exact query tuples, whereas BlinkDB uses samples computed from query templates for ad-hoc queries.BlinkDB’s template-based sample set is designed to support queries not known exactly in advance.
Sampling approaches: SciBORQ supports time-based constraints but provides no error-margin guarantees, unlike BlinkDB’s support for error and response-time constraints.SciBORQ targets exploratory scientific analysis using biased samples called impressions.
Sampling approaches: Unlike single-column biased-sample methods that union results from multiple samples, BlinkDB selects a single sample based on the current query.BlinkDB’s approach uses multi-column sampling.
Online aggregation: Online aggregation continually refines answers but requires data to be streamed in random order, which can be impractical in distributed systems.BlinkDB instead relies on precomputed samples maintained for efficient processing.
Non-sampling approaches: Non-sampling systems such as synopses, materialized views, and data cubes can answer specialized query types efficiently but are impractical for arbitrary queries.These approaches require structures tailored to operators or query types.

8. CONCLUSION

The paper concludes that BlinkDB supports ad-hoc SQL queries with explicit error and response-time constraints through multi-dimensional samples and runtime sample selection. Evaluations on real datasets and deployments of up to 100 nodes demonstrate query answering within 2 seconds on 17 TB with 90–98% accuracy.

BlinkDB is a parallel, sampling-based approximate query engine for ad-hoc queries with error and response-time constraints.
Its two key ideas are multi-dimensional, multi-granularity sampling and runtime selection of samples sized to satisfy query constraints.Smaller samples estimate query selectivity before the best samples are chosen.
2 seconds on 17 TB with 90–98% accuracy was achieved across evaluations on real datasets and deployments of up to 100 nodes.

A. STRATIFIED SAMPLING PROPERTIES AND STORAGE OVERHEAD

The appendix analyzes the performance and storage properties of stratified sample families. It bounds the overhead of choosing a nearby sample and evaluates storage requirements under a Zipf distribution.

The appendix proves properties of sample-family selection and gives storage overhead for Zipf-distributed data.
Performance properties: For an I/O-bound query with an error constraint, using a stratified sample family increases response time by at most c + 1/Kopt times relative to the optimal-sized sample.
Performance properties: For a response-time-constrained query with standard deviation proportional to 1/√n, the sample family increases standard deviation by at most the bound stated in Lemma A.2.Here n is the number of tuples selected by the query from the optimal sample.
Storage overhead: Storage overhead is evaluated for stratified samples under a Zipf distribution, with sample size reported as a fraction of the original table size.The analysis assumes exponent s ≥ 1 and maximum frequency M = 10^9.