---
# System prepended metadata

title: Dremel - Interactive Analysis of Web-Scale Datasets
tags: [Published]

---

---
title: Dremel - Interactive Analysis of Web-Scale Datasets
tags: Published
description: Dremel - Intractive Analysis of Web-Scale Datasets
---

# Dremel: Interactive Analysis of Web-Scale Datasets
[REFERENCE](https://static.googleusercontent.com/media/research.google.com/ja//pubs/archive/36632.pdf)

## Introduction :pushpin:

### What's Dremel?
- [Google BigQuery](https://cloud.google.com/bigquery/?hl=ja&utm_source=google&utm_medium=cpc&utm_campaign=japac-JP-all-ja-dr-bkws-all-super-trial-e-dr-1008074&utm_content=text-ad-none-none-DEV_c-CRE_314712311214-ADGP_Hybrid+%7C+AW+SEM+%7C+BKWS+~+T1+%7C+EXA+%7C+Big+Data+%7C+1:1+%7C+JP+%7C+ja+%7C+big+query+%7C+google+bigquery+%7C+en-KWID_43700030990911712-kwd-63326440124&userloc_1009310&utm_term=KW_google%20bigquery&gclid=EAIaIQobChMIlqbR56bW6AIVh6uWCh0KjACIEAAYASAAEgJ2q_D_BwE)のプロジェクト名
- [Apache Parquet](https://parquet.apache.org/)といったOSSの元ネタ

## Features :beers:
- [カラムナ：列指向DBMS](https://ja.wikipedia.org/wiki/%E5%88%97%E6%8C%87%E5%90%91%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9%E7%AE%A1%E7%90%86%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0)
	- 膨大なレコード数のデータセットに対する「列」方向の集計演算において優れたパフォーマンスを発揮する
	- ネストした（JSONのような）構造体を効率的に圧縮・問合せすることができる
- 優れた垂直方向へのスケーラビリティ
    - > We present experiments on trillion-record, multi-terabyte datasets, conducted on system instances running on 1000-4000 nodes.

## Usecase :sandwich:

### Google

正規化の是非を問わず様々な用途に対応

様々なドメインのデータの永続化・**分析**で利用：

- Analysis of crawled web documents
- Tracking install data for applications on Android Market
- Crash reporting for Google products
- OCR results from Google Books
- etc...

---

### Apache Parquet (OSS)

{%youtube MZNjmfx4LMc %}

> Apache Parquet is a **columnar storage** format available to any project in the Hadoop ecosystem, regardless of the choice of data processing framework, data model or programming language.

## Background :baby_chick:

### Motivation
分散処理系に大量に蓄積されるデータを**インタラクティブ**に分析できる環境が欲しい

### Senario
> Googleで働くアリスというエンジニアは、webページから送られる様々な新しい信号（シグナル）を抽出（分析）するための革新的なアイディアを思いついたとします

> 入力データをかき集め、該当する新しい信号を含むデータセットを生成し、数十億ものレコードを分散処理系に保存するジョブを彼女は実行しました

> 実験結果を分析するために、彼女はDremelを立ち上げ、いくつかの対話的なコマンドを実行しました：

> ```SQL
> DEFINE TABLE t AS /path/to/data/*
> SELECT TOP(signal1, 100), COUNT(*) FROM t
> ```

> コマンドの実行は数秒で完了しました。彼女はアルゴリズムが思ったとおりに動作することを確認するためにその他にもいくつかクエリを実行してみました

> そして`signal1`の異常を発見し、生成したデータセットに対して`FlumeJava`を利用したより詳細な調査を行うためのプログラムを書きました

> 問題点を洗い出した後に、生成され続ける信号を継続的に処理するためのパイプラインを立ち上げました

> 様々な観点から構成されるパイプラインの出力を集計するためのひとまとまりのSQLを書き、対話的なダッシュボードツールに連携しました

> 最後に、新しく作成されるようになったデータセットをダッシュボードのカタログに登録し、他のエンジニアが素早く参照し、分析するための環境を作り上げました

BigQueryの機能そのものですね :thinking_face:

### System Components

==WIP==

- クエリ処理

## Data Model :mag_right:
> meets [Protocol Buffers](https://developers.google.com/protocol-buffers) :call_me_hand:

### 分散処理系に適したデータ形式

$$
\tau = \text{dom} | \langle A_{1} : \tau \left[ \ast | \text{?} \right], \ldots, A_{n} : \tau \left[ \ast | \text{?} \right] \rangle
$$

- $\tau$ : レコード
- $\text{dom}$ : Atomic Types (int, float, number, strings, etc...)
- $A_{i}$ : レコードの$i$番目のフィールド名
- $\left[ \ast | \text{?} \right]$ : 各フィールドはその多重度（重複性）についての修飾子
    - $\ast$ : _repeated_ （そのフィールドは複数個含まれうる）
    - $\text{?}$ : _optional_ （そのフィールドは存在しない場合もある）
    - 修飾子が振られていないフィールドは必ず１つだけフィールドを持つ

#### Figure 1 Record-wise vs. columnar representation of nested data

![](https://i.imgur.com/SzvhUNT.png)

#### Figure 2 Two sample nested records and their schema

##### Schema

```proto=
message Document {
  required int64 DocId;

  optional group Links {        // (1) Linksは
    repeated int64 Backward;    // Backwardというdomがint64のフィールドと
    repeated int64 Forward;     // Forwardというdomがint64のフィールドの
  }                             // 繰り返しを束ねた「任意」のフィールド

  repeated group Name {         // (2) Nameフィールドは複数（０以上）

    repeated group Language {   // (3) Languageレコードが存在するときは
      required string Code;     // Codeはdomがstringの必須のフィールド
      optional string Country;
    }

    optional string Url;
  }
}
```

##### Document $r_{1}$, $r_{2}$ and $r_{3}$

<div style='display: flex;'>

<div style='width: 100%; margin-right: 5px;'>

```yaml=
DocId: 10

Links:
  Forward: 20  # (1) Forwardが
  Forward: 40  # Linksレコードで
  Forward: 60  # 重複してOK

Name:  # (2)
  Language:
    Code: 'en-us'  # (3)
    Country: 'us'
  Language:
    Code: 'en'     # (3)
  Url: 'http://A'
Name:  # (2)
  Url: 'http://B'
Name:  # (2)
  Language:
    Code: 'en-gb'  # (3)
    Country: 'gb'
```
</div>

<div style='width: 100%; margin-left: 5px;'>

```yaml=
DocId: 20

Links:
  Backward: 10
  Backward: 30
  Forward: 80

Name:
  Url: 'http://C'
```

```yaml=
# 問題１
# これは正しいレコードでしょうか？
DocId: 30
```

```yaml=
# 問題２
# これは？（represented as is.）

```

</div>

</div>

#### Figure 3 Colimn-striped representation of the sample data in Figure 2, showing repetition levels (r) and definition levels (d)
