Concurrency Control[04]

Concurrency Control will be covered in their future work.

Data Model[04]

BigQuery/Dremel uses a variation of the complex value models and nested relational models. It supports strongly-typed nested records. Records consist of one or multiple fields. Each field is an key-value pair and the key can be repeated. Each fielded can be of type required or optional and must be defined in the schema. A required field must appear exactly once.

Indexes[04]

Indexes will be covered in their future work.

Joins[04]

Join will be covered in their future work.

Query Execution[04]

BigQuery/Dremel uses a multi-level serving tree for query execution. A root server receives the queries, fetches the metadata from the tables and sends the queries to the next level in the serving tree. Each serving level performs a query rewriting by partitioning the tablets into disjoint sets and sends the query on the partitioned tablets to the next level. Eventually, the queries will reach the leaf servers where the tablets will be scanned in parallel and results will be send back up. The intermediate servers will aggregate the partial results in parallel.

In a context of concurrent query execution, Dremel uses a query dispatcher to schedule queries based on the priorities and balances the load. The query dispatcher estimates the tablets processing time and if a tablet takes an unexpected long time to process, the dispatcher will schedule the tablet on another server.

Query Interface[04]

BigQuery/Dremel is based on SQL. The language supports nested subqueries, inter and intra-record aggregation, top-k selection, joins, regular expression matching and user-defined functions.

Storage Architecture[04]

All the data are assumed to be stored in disk or other storage layer can be piped in. In the multi-level serving tree for query execution, all the leaf servers are responsible for communication with the storage layer or access the data on local disk.

Storage Model[04]

BigQuery/Dremel uses a columnar storage for the nested records. Based on the schema, it will encode the record structure in a columnar format. Each column is stored as a set of blocks. Each block contains the compressed field values, repetition and definition levels. Repetition level indicates at what repeated field in the field's path the value has repeated. Definition level specifies how many fields in the path that could be optional or repeated are actually present. With these two levels and the schema, it can represent the record structure losslessly.

System Architecture[04]