Concurrency Control

Not Supported

Data Model

Relational

The samples in BlinkDB are essentially Hive tables.

BlinkDB does not maintain large physical samples. A large sample in BlinkDB 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

Broadcast Join

BlinkDB does not build online samples, so it does not build samples for the joined tables. Therefore, 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.

Joining sample tables is identical to normal table joins, and it is left to underlying DBMS.

Instead of using closed-form error bound computation, BlinkDB uses statistical bootstrapping method for estimating query error bounds on joined tables.

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.

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.

However, the open-source version does not support the WITHIN xx SECONDS statement. It only supports APPROX_SUM, APPROX_AVG and APPROX_COUNT aggregation operators that return the estimated sum, average or count with error bars of 99% confidence.

Storage Architecture

Hybrid

BlinkDB stores its physical samples on the HDFS, and stores its metadata in Hive Metastore. The metadata maps the logical samples to the physical blocks on the HDFS. It can also directly read the Hive Metastore to access the native tables in Hive.

Storage Model

Decomposition Storage Model (Columnar)

BlinkDB is built on Shark which uses columnar storage model. In the Github version, samples are saved as Hive tables and can be cached in the memory by Shark like other Hive tables.

System Architecture

Shared-Disk