BigQueryのclusterとpartitionカルトクイズ

BigQueryでは、他データベースのインデックスに相当する、データへのアクセス量を削減する手法として、

- clustering
- partitioning

の2つがある。これらの機能をなんとなく知っている人も以下のクエリで、trip_start_timestampに貼られたpartitionが機能するか自信を持って答えられるだろうか？

```sql
with constants as (
select
  TIMESTAMP_ADD(DATE("2014-04-13"), INTERVAL 1 DAY) as target_day,
)
SELECT 
  *
FROM `taxi_sample.partition_taxi_trips`, constants
WHERE DATE(trip_start_timestamp) = target_day
```

本稿では、partitioningとclusteringに関するクイズを通じて、その機能のイメージを強化する。
以下のクイズでは基本的に***trip_start_timestamp***にDAY単位でpartitionを作成する。
**ゆっくりスクロールして一度自分で問題を置いてみて欲しい**

なお、bigquery内部の最適化が絡むため動作確認を行った2021-04-05以降に動作が変更される可能性がある。

# partitioning 編

## 基礎知識

partitioningは、BigQueryのテーブルを**ユーザーが指定した粒度で**分割する機能である。
例えば、以下のクエリを実行する。これは、タクシーの運行データの中で特定の日に出発したもののみを抽出するクエリである。処理されたバイト数は70.7GBとなる。なお、テーブルサイズも70.7GBであり、すべてのデータにアクセスしてしまっている。

```sql
SELECT 
  *
FROM `bigquery-public-data.chicago_taxi_trips.taxi_trips` 
WHERE DATE(trip_start_timestamp) = "2014-04-13"
```

このテーブルに、partitionを作成する。

```sql
create or replace table taxi.partition_taxi_trips 
partition by TIMESTAMP_TRUNC(trip_start_timestamp, DAY) 
as
SELECT 
  *
FROM `bigquery-public-data.chicago_taxi_trips.taxi_trips`
```

partition by TIMESTAMP_TRUNC(trip_start_timestamp, DAY)で、trip_start_timestampの日付に応じてテーブルを分割している。
このテーブルに対して先ほどと同じクエリを実行すると、同じ結果だがアクセスするデータは35.6MBに激減する。これは、テーブルが日付単位に分割されており、その中で必要な部分にだけアクセスするためである。

## 定数による範囲指定

### Q. with節を用いた定数範囲指定
アクセス範囲を定数with節で渡した際に、アクセス量が削減されるか？

```sql
with constants as (
select
  DATE("2014-04-13") as target_day,
)
SELECT 
  *
FROM `taxi.partition_taxi_trips`, constants
WHERE DATE(trip_start_timestamp) = target_day
```



A. 削減される

### Q. with節を用いた定数範囲指定 + 簡単な演算

定数with節の定数に簡単な演算が入ったらどうだろう？

```sql
with constants as (
select
  DATE_ADD(DATE("2014-04-13"), INTERVAL 1 DAY) as target_day,
)
SELECT 
  *
FROM `taxi_sample.partition_taxi_trips`, constants
WHERE DATE(trip_start_timestamp) = target_day
```



A. 削減されない (フルアクセス)

おそらく、定数with節は内部的に特別扱いをされている。TIMESTAMP_ADD関数を挟むことで定数と認識されなくなり最適化の対象から外れるのだろう。

### Q. with節を用いた定数範囲指定 + 簡単な演算 その２

先ほどの演算を、with節側からwhere節に移動させたらどうだろう？

```sql
with constants as (
select
  DATE("2014-04-13") as target_day,
)
SELECT 
  *
FROM `taxi_sample.partition_taxi_trips`, constants
WHERE DATE(trip_start_timestamp) = date_add(target_day, interval 1 day)
```



A. 削減される

なんとなく、どのように定数が展開されるかのイメージが出来てきたのではないだろうか。

### Q. ちょっと複雑な演算

利用する関数の種類をちょっと変えてみよう。これらは削減されるか？

```sql
case 1. 
SELECT 
  *
FROM `taxi_sample.partition_taxi_trips`
WHERE EXTRACT(YEAR from trip_start_timestamp) = 2014

case 2.
SELECT 
  *
FROM `taxi_sample.partition_taxi_trips`
WHERE TIMESTAMP_ADD(trip_start_timestamp, interval 1 day)  = "2014-04-13"

case 3.
SELECT 
  *
FROM `taxi_sample.partition_taxi_trips`
WHERE PARSE_TIMESTAMP("%F", CONCAT(EXTRACT(YEAR from trip_start_timestamp), "-04-13")) = "2014-04-13"
```



A. 

case 1, 2は削減される。case 3は削減されない。





### Q. 別テーブルによる定数定義

ここまではwith節で定数を指定していたが、別テーブルになるとどうだろう。

```sql
create temp table constants as
select
  DATE("2014-04-13") as target_day,
;

SELECT 
  *
FROM `taxi.partition_taxi_trips`, constants
WHERE DATE(trip_start_timestamp) = target_day
```



A. 削減されない



### Q. declareによる定数定義

ここまではwith 節で定数を定義していたが、DECLAREを使うとどうだろう？

```sql
DECLARE target_day DATE DEFAULT date_add(DATE("2014-04-13"), interval 1 day);

SELECT 
  *
FROM `taxi_sample.partition_taxi_trips`
WHERE DATE(trip_start_timestamp) = target_day
```



A. 削減される



## JOIN時の条件

### Q. ON節での条件指定

JOIN時にON節の中で、partition列に条件をつけるとpartitionは機能するだろうか？

```sql
create temp table pay as 
select distinct
  payment_type,
  length(payment_type) as len_pay,
from `taxi_sample.partition_taxi_trips`  
;

SELECT 
  *
FROM `taxi_sample.partition_taxi_trips` as l
JOIN pay as r ON
   DATE(trip_start_timestamp) = "2014-04-13"
   AND l.payment_type = r.payment_type
```



A. 削減される



### Q. WHERE節での条件指定

では、JOIN時のwhere節はどうだろう。原理的にはWHERE節はJOIN後に適用される。以下の状況でpartitionは機能するか？

```sql
create temp table pay as 
select distinct
  payment_type,
  length(payment_type) as len_pay,
FROM `taxi_sample.partition_taxi_trips`  
;

SELECT 
  *
FROM `taxi_sample.partition_taxi_trips`
JOIN pay using(payment_type)
where DATE(trip_start_timestamp) = "2014-04-13"
```



A. 削減される



### Q. JOINで結果的にアクセス先が特定日に収まる

partition_taxi_tripsには、各行にunique_keyというユニークな値が割り振られている。
よって、以下のクエリではアクセスされるデータは、特定の日付のものになる。この時、パーティションは機能するか？

```sql
with keys as (
select distinct
  unique_key,
from `taxi_sample.partition_taxi_trips`
where DATE(trip_start_timestamp)="2014-04-13"
)
select
  *
from`taxi_sample.partition_taxi_trips`
join keys using(unique_key)
```



A. 削減されない (フルアクセス)

bqはどのunique_keyがどの日付に対応するか知らないため、これがフルアクセスになるのは当然に見える。

### Q. JOINで結果的にアクセス先が特定日に収まる (where節適用先がpartition列)

では、露骨にtrip_start_timestampの日付を制限するとどうだろう？

```sql
with keys as (
select distinct
  trip_start_timestamp
from `taxi_sample.partition_taxi_trips`
where DATE(trip_start_timestamp)="2014-04-13"
)
select
  *
from `taxi_sample.partition_taxi_trips`
join keys using(trip_start_timestamp)
```



A. 削減される

これが出来るのはかなり賢い。keys with節のtrip_start_timestampがどの範囲になるかをちゃんと判定しているように見える。
なお、with節でアクセスするテーブルを別テーブルに切り替えても削減されるため、where節の内容が伝搬しているものと思われる。

```sql
create temp table cp_table 
partition by DATE(trip_start_timestamp)
as (
select 
  *
from `taxi_sample.partition_taxi_trips`
);

with keys_base as (
select distinct
  trip_start_timestamp
from cp_table
where DATE(trip_start_timestamp) =  "2014-04-13"
)
select
  *
from `taxi_sample.partition_taxi_trips`
join keys_base using(trip_start_timestamp)
```



### Q. where節伝搬の上書き (難問)

TIMESTAMP_ADDを適用してしまうと、範囲情報が消失するらしきことは、「with節を用いた定数範囲指定 + 簡単な演算」から伺うことが出来る。一度消失した範囲情報を別のwhere句で復活させることは出来るだろうか？

以下ではアクセスデータ量は削減されるか？

```sql
with keys as (
select distinct
  TIMESTAMP_ADD(trip_start_timestamp, INTERVAL 1 DAY) as trip_start_timestamp,
from `taxi_sample.partition_taxi_trips`
where DATE(trip_start_timestamp)="2014-04-13"
),
keys2 as (
select
  trip_start_timestamp
from keys
where DATE(trip_start_timestamp ) = "2014-04-14"
)
select
  *
from `taxi_sample.partition_taxi_trips`
join keys2 using(trip_start_timestamp)
```



A. 削減されない

なんとこれはフルアクセスになる。keys2 with節を見れば、アクセス範囲は明瞭なのだが、一度アクセス範囲情報が消失すると回復しないようだ。このことから、アクセス範囲情報は必要となる地点からの逆伝搬ではなく、順伝搬であろうことが推測される。



### Q. JOINで結果的にアクセス先が特定日に収まる (別テーブル版)

先ほどのwith節を別テーブルに分離するとどうだろう。

```sql
create temp table keys as (
select distinct
  trip_start_timestamp
from `taxi_sample.partition_taxi_trips`
where DATE(trip_start_timestamp)="2014-04-13"
);

select
  *
from `taxi_sample.partition_taxi_trips`
join keys using(trip_start_timestamp)
```



A. 削減されない

where節の情報が別テーブルにすると伝搬しないのが伺える。そもそもこれが出来るのであれば、「別テーブルによる定数定義」が成功するだろう。



### Q. JOINで結果的にアクセス先が特定日に収まる (別の列版)

特定日付に集中するunique_keyを条件に持たせたらどうだろう？ 以下のクエリでは1行にのみアクセスする。

```sql
with keys as (
select distinct
  trip_start_timestamp
from `taxi_sample.partition_taxi_trips`
where unique_key = "cabcd5d54cf0230d04a59ae8849a3d6b269c5313"
)
select
  *
from`taxi_sample.partition_taxi_trips`
join keys using(trip_start_timestamp)
```



A. 削減されない
やはりwith節の結果ではなく、where節の情報を使ってアクセス量を削っているのが伺える。

## partitioning まとめ

実験結果をまとめると、以下のような挙動になっていると思われる。

1. partitionによるアクセス量削減には、データのアクセス範囲がクエリ実行前に特定できる必要がある
2. 定数with節の情報は、実行前に利用可能
3. 関数の使い方によっては定数情報は消失する
4. partitionはwhere節の情報を使ってアクセス量を削減している
5. where節の情報は、with節を跨いで伝搬する
6. where節の情報は、テーブルを跨いで伝搬しない
7. where節の情報は列を跨いで伝搬しない



# clustering 編

## 基礎知識

clusteringは、BigQueryのテーブルをユーザーが指定した列で**ソートして格納する**機能である。(注：正確ではない)
以下のように、clusterを作成する。

```sql
create or replace table taxi_sample.cluster_taxi_trips 
cluster by trip_start_timestamp
as
SELECT 
  *
FROM `bigquery-public-data.chicago_taxi_trips.taxi_trips`
```

これに対して以下のようにアクセスしてみよう。

```sql
SELECT 
  *
FROM `taxi_sample.cluster_taxi_trips` 
WHERE DATE(trip_start_timestamp) = "2014-04-13"
```

そうすると、アクセスするデータサイズは削減される。



### Q. partitionとclusterでアクセスされるデータサイズはどちらが小さい？

同じ2014-04-13のデータにアクセスする際、partition_taxi_tripsとcluster_taxi_tripsでアクセスされるデータサイズはどちらが小さいだろうか？



A. (今回は) partitionの方が小さい

アクセスされるデータ量は下のテーブルのようになる。

| そのまま | partition | cluster |
| -------- | --------- | ------- |
| 70.7GB   | 35.6MB    | 122.4MB |

となる。partitionとclusterでどちらがアクセス量が小さくなるかは状況によるとしか言えない。
しかし、partitionあたりの容量が小さい場合は、clusterが不利になりやすい。これは、[clusterには最小サイズがある](https://stackoverflow.com/a/58175053)からである。最小サイズは公開されていないが、数十MBっぽい気配を感じる。(ex-Googlerが[100MB以下だとclusterあんまり意味ないよ](https://stackoverflow.com/a/52674573)的なアドバイスをしている)


## 定数による範囲指定

### Q. partitionとの差異はどれか？

partitionで行った定数指定の実験のうち、clusterで結果に差異が出るのはどれだろう？



a1. with節を用いた定数範囲指定 (partitionは削減される)

```sql
with constants as (
select
  DATE("2014-04-13") as target_day,
)
SELECT 
  *
FROM `taxi.partition_taxi_trips`, constants
WHERE DATE(trip_start_timestamp) = target_day
```

a2. with節を用いた定数範囲指定 + 簡単な演算 (partitionは削減されない)

```sql
with constants as (
select
  DATE_ADD(DATE("2014-04-13"), INTERVAL 1 DAY) as target_day,
) 略
```

a3. with節を用いた定数範囲指定 + 簡単な演算 その２ (partitionは削減される)

```sql
with constants as (
select
  DATE("2014-04-13") as target_day,
)
SELECT 
  *
FROM `taxi_sample.partition_taxi_trips`, constants
WHERE DATE(trip_start_timestamp) = date_add(target_day, interval 1 day)
```

a4. 別テーブルによる定数定義 (partitionは削減されない)

```sql
create temp table constants as
select
  DATE("2014-04-13") as target_day,
略
```

a5. declareによる定数定義 (partitionは削減される)

```sql
DECLARE target_day DATE DEFAULT date_add(DATE("2014-04-13"), interval 1 day);
略
```



A. clusterでは全て削減される
partitionでは2と4のケースではアクセス量が削減されなかったが、clusterでは削減される。
このことから、partitionとclusterでは最適化の働きが明らかに違うことがわかる。



### Q. 細粒度アクセスは有効か？

以下の2つでアクセス量は変わるだろうか？

```sql
SELECT 
  *
FROM taxi_sample.cluster_taxi_trips
WHERE DATE(trip_start_timestamp) = "2014-04-13"
```

```sql
SELECT 
  *
FROM taxi_sample.cluster_taxi_trips
WHERE trip_start_timestamp = "2014-04-13 03:00:00"
```



A. 変わる

前者は122.4MB, 後者は62.7MBである。減少はしたものの後者のアクセスデータ量は明らかに必要なデータより多い。
これは特定のclusterにアクセスした場合、そのclusterに属する全ての要素を読み込むためである。



## JOIN時の条件

### Q. ON節での条件指定 & WHERE節での条件指定
もはや自明なのでクエリ例は省略するが、削減される。

### Q. JOINで結果的にアクセス先が特定日に収まる

ここからが面白い。partitionと同様に、各行にunique_keyというユニークな値が割り振られている。
よって、以下のクエリではアクセスされるデータは、特定の日付のものになる。
この時、clusterは機能するか？

```sql
with keys as (
select distinct
  unique_key,
from `taxi_sample.cluster_taxi_trips`
where DATE(trip_start_timestamp)="2014-04-13"
)
select
  *
from`taxi_sample.cluster_taxi_trips`
join keys using(unique_key)
```



A. 削減されない (フルアクセス)

clusterならひょっとしてやってくれるかもしれない・・・、と思わせるが実際は全くやってくれない。(joinでなくwhere existsでアクセス対象を絞っても同様)
アクセス先は単一の日付なので特定のcluster群にアクセスは集中している筈だが、フルアクセスとなる。
このことから、**clusterは結果的にアクセス先が固まれば機能する訳ではない**ということがわかる。

### Q. JOINで結果的にアクセス先が特定日に収まる (相関のある列)

unique_keyはランダムな文字列だったが、trip_start_timestampと相関があるtrip_end_timestampでjoinしてみてはどうだろう？

```sql
with keys as (
select distinct
  trip_end_timestamp,
from `taxi_sample.cluster_taxi_trips`
where DATE(trip_start_timestamp)="2014-04-13"
)
select
  *
from`taxi_sample.cluster_taxi_trips`
join keys using(trip_end_timestamp)
```

A. 削減される
こちらは削減される！



### Q. 相関のある列の指定はpartitionでも通用するか？
上記の例をpartitionに適用するとデータサイズは削減されるだろうか？

A. 削減されない
partitionでは削減されないようだ。



### Q. アクセス先の範囲が分割されていてもclusterは機能するか？

今までは単一の日付で条件を指定していたが、もう少し複雑でも機能するか？

```sql
with keys as (
select distinct
  trip_end_timestamp,
from `taxi_sample.cluster_taxi_trips`
where 
  DATE(trip_start_timestamp) between "2014-04-13" and "2014-04-15"
  or   DATE(trip_start_timestamp) between "2014-05-21" and "2014-05-23"
)
select  
  *
from`taxi_sample.cluster_taxi_trips`
join keys using(trip_end_timestamp) 
```

A. 削減される

### Q. cluster以外とのjoinでもclusterは機能するか？

これまではclusterテーブル同士のjoinを行っていた。では、joinするテーブルをpartitionも何も指定していないテーブルにするとどうだろうか？

```sql
with keys as (
select distinct
  trip_end_timestamp,
from `taxi_sample.taxi_trips`
where DATE(trip_start_timestamp)="2014-04-13"
)
select
  *
from`taxi_sample.cluster_taxi_trips`
join keys using(trip_end_timestamp) 
```



A. 削減される

このケースも削減される！
これによって、clusterの最適化はクエリ実行前だけで行われるものでないことがわかる。（後述）

## clusteringの原則考察

clusteringのアクセス量削減アルゴリズムはpartitioningの上位互換のようである。
しかし、「 Q.JOINで結果的にアクセス先が特定日に収まる」の結果から、最終的に利用されるclusterに限定してアクセスするだけの能力はない。

Google BigQuery: The Definitive Guideによると、bigqueryのテーブルを構成するファイルはメタファイルを持ち、メタファイルにはそのファイルが持つ各フィールドの値の範囲が記載されている。
各ファイルごとに以下のようなメタファイルを持つ。clustering適用時は、ファイルに分割する際に指定した列の値が近いものが、同じファイルに格納されるようになる。

| field                | min              | max              |
| -------------------- | ---------------- | ---------------- |
| trip_start_timestamp | 2014-04-01 12:00 | 2014-04-03 18:00 |
| unique_keys          | 782ea949ea       | 9daece52fe2      |
| trip_end_timestamp   | 2014-04-01 12:12 | 2014-04-03 21:00 |



おそらく、clusteringが設定されたテーブルへアクセスするクエリが発行された際に、このメタ情報を使って事前にアクセスするファイルを決定する。例えば以下のクエリが発行された際は、

```sql
with keys as (
select distinct
  trip_end_timestamp,
from `taxi_sample.cluster_taxi_trips2` # これはcluster_taxi_tripsと同様のテーブル 
where DATE(trip_start_timestamp)="2014-04-13"
)
select
  *
from`taxi_sample.cluster_taxi_trips`
join keys using(trip_end_timestamp)
```

1. keys with節を実行し、trip_end_timestampの範囲情報を取得する
2. 1で取得したtrip_end_timestampを範囲に含むファイル群をメタファイルを使って列挙する
3. 列挙されたファイルにアクセスする

という手順になっていると予想している。

trip_end_timestampの範囲情報の取得を実行結果ではなく、メタファイルから取得している説もあったが、

1. 「Q. cluster以外とのjoinでもclusterは機能するか？」から、trip_end_timestampの範囲がメタファイルから取れないケースでも機能していることがわかる
2. clusterテーブルは実行前にアクセスするデータ量が算出できない点と整合する

の2点から、trip_end_timestampの範囲情報は実行時に取得されると思われる。


アクセス量が減らなかったクエリを思い出してみよう。

```sql
with keys as (
select distinct
  unique_key,
from `taxi_sample.cluster_taxi_trips`
where DATE(trip_start_timestamp)="2014-04-13"
)
select
  *
from`taxi_sample.cluster_taxi_trips`
join keys using(unique_key)
```

このケースでは、

1. keys with節を実行し、**unique_key**の範囲情報を取得する
2. 1で取得したunique_keyを範囲に含むファイル群をメタファイルを使って列挙する
3. 列挙されたファイルにアクセスする

となるが、1で取得したunique_keyの範囲が広大になってしまうため、全てのファイルにアクセスする必要が生じると思われる。



### もうちょっと詳しい考察 (The Definitive Guide既読者向け)

clusteringの実行手順として、以下のようにした。

1. keys with節を実行し、trip_end_timestampの範囲情報を取得する
2. 1で取得したtrip_end_timestampを範囲に含むファイル群をメタファイルを使って列挙する
3. 列挙されたファイルにアクセスする

しかし、厳密には1のtrip_end_timestamp範囲情報の取得は、with節の実行が終わったタイミングで行われていない。
with節の実行が終わったタイミングの取得としてしまうと、with節の実行が終わるまで後続処理がストップしてしまい、並列処理が行われないためである。おそらく、各shardの実行が始まるタイミングで、それぞれのshardが必要なデータの範囲を抽出し、メタファイルから必要なファイルを列挙していると思われる。


# まとめ

partitioningとclusteringの最大の違いが、静的な（事前の）アクセス範囲の決定と動的な（実行中の）アクセス範囲の決定というのが、イメージできたのではないだろうか。

これらの使い分けは[公式ドキュメント](https://cloud.google.com/bigquery/docs/clustered-tables?hl=ja) にガイドラインがあるが、データ削減を目的にするのであれば、とりあえずclusteringを使えば良さそう。partitionの方がデータアクセス量が減る実例も示したが、bigqueryの尺度で言えば小さいメリットだろう（頻繁にアクセスする場合のぞく）。



[複数列へのclusteringの適用、partitioningとclusteringの併用編](https://qiita.com/jack_ama/items/d17ff528b81bb882a12a)に続く。