BlinkDB

BlinkDB is an approximate query engine built on top of Hive as well as Shark (Hive on Spark, the former Spark SQL). It allows users to trade-off query accuracy for response time, thus enabling interactive queries on big data. BlinkDB builds a couple of stratified samples on the original data and executes the queries on the samples instead of the original data to reduce query execution time. The number and sizes of the stratified samples are limited by the storage budget specified when importing the data. It has two major parts: one is the sample building engine that selects what stratified samples to build by considering historic workloads and the distribution of the data; the other part is a dynamic sample selection module that chooses appropriate sample files at runtime according to specific time/accuracy requirements specified by the query.

History

BlinkDB was built at Berkeley's AMPLab (now RISELab). It was proposed in BlinkDB: Queries with Bounded Errors and Bounded Response Times on Very Large Data, which is the best paper of Eurosys 2013.

BlinkDB is no longer maintained. The successor of BlinkDB is VerdictDB, which builds on the same idea with BlinkDB but supports more sample types, more accurate query run-time estimation and is platform independent.

Query Execution

Tuple-at-a-Time Model Vectorized Model

BlinkDB executes the query on one or more samples instead of the original data. It tries to select the most appropriate sample to execute the query at runtime. The sample selection involves two steps: first is to find a sample family, which is a set of columns on which BlinkDB has built the stratified samples; then is to select a sample resolution, that is, to find a sample in the sample family with the most appropriate size to satisfy the requirement of the query. For example, BlinkDB finds the smallest sample for an error bound constrained query to minimize its execution time, and it finds the largest sample for a time-constrained query to minimize its error bound. BlinkDB "probes" the smaller samples in a couple of sample families to estimate the query's selectivity, complexity, and the data distribution it specifies, then decides a sample family and a sample size to execute the query on.

Concurrency Control

Not Supported

BlinkDB leaves concurrency control to the base database system.

Indexes

Not Supported

Storage Architecture

Hybrid

BlinkDB stores its physical samples on the HDFS. A logical large sample actually consists of a collection of smaller samples, which are stored in consecutive blocks on the HDFS. This is beneficial to runtime sample selection because BlinkDB can simply read more blocks to construct a larger sample, which makes it easy to estimate the execution cost of a query on different sizes of samples.

Joins

Sort-Merge Join

BlinkDB supports two types of joins:

1) Arbitrary joins are supported if the join key is present in the columns set of one of the stratifies samples. In that way, BlinkDB can use one of the samples to join the other table even if it is not sampled.

2) If no samples contain the key columns, then the join is only allowed if one of the original tables is small enough to fit in the memory. Since BlinkDB does not sample data that fits in the memory, this can also guarantee that the result table is small enough to execute the query on.

Storage Organization

Heaps

Storage Model

Decomposition Storage Model (Columnar)

Samples are distinguished by their column sets. Samples which has the same column set belongs to a "sample family" and are stored together (actually is a series of consecutive blocks on the HDFS).

Query Interface

SQL

The query interface of BlinkDB is SQL-based aggregation queries along with response time of error bound constraints. Like:

SELECT avg(sessionTime) FROM Table WHERE city='San Francisco' WITHIN 2 SECONDS will return an estimated average of sessionTime of San Francisco with error bounds of default confidence level within 2 seconds.

SELECT avg(sessionTime) FROM Table WHERE city='San Francisco' ERROR 0.1 CONFIDENCE 95.0% will return the estimated average sessionTime until it has processed enough data so that the error is less than 10% with 95% confidence.

To support these SQL queries and sample maintenance, BlinkDB made a couple of changes to the HiveQL parser to:

1) support queries with response time and error bounds;

2) detect data modification inputs, which could trigger creating new samples or updating the existing samples;

3) support re-writing the original query to execute on samples, and iteratively assigning appropriately sized samples for this query to run on;

4) support returning error bounds and confidence for aggregation functions by modifying the implementation of aggregation functions.

Data Model

Relational

System Architecture

Shared-Nothing

BlinkDB Logo
Website

http://blinkdb.org/

Source Code

https://github.com/sameeragarwal/blinkdb

Developer

University of California-Berkeley, Massachusetts Institute of Technology

Country of Origin

US

Start Year

2012

End Year

2014

Project Type

Academic, Open Source

Derived From

Spark SQL

Operating Systems

All OS with Java VM

Licenses

Apache v2