Redshiftで100TBのテーブルをソートする

Redshiftを運用していると、稀に巨大なテーブルを手動でソートしたいという場面に遭遇することがある。この記事では、テーブルを高速にソートする手段として[ディープコピー](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/performing-a-deep-copy.html)を使ったテーブルのソート方法と性能検証結果を共有する。

## テーブルのソートとは？

テーブルのソートはクエリの絞り込み条件 (WHERE句やBETWEEN句) を効率的に処理するために使用される。各テーブルには[ソートキー](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/t_Sorting_data.html)列を指定でき、ソートキー列をクエリの絞り込み条件に指定することでディスクからスキャンする[ブロック](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/c_columnar_storage_disk_mem_mgmnt.html)数を最小化することができる。これによりテーブルから必要なデータだけを読み出すことができるようになる。

ソートの効果を引き出すには以下の2点が重要となる。

1. クエリに合わせて適切なソートキーを設定する
2. テーブルがソートされた状態を維持する

Redshiftでは1・2のいずれも[自動ソートキー](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/c_ato-enabling-disabling-monitoring.html)・[自動VACUUM](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/t_Reclaiming_storage_space202.html)機能によりバックグラウンドで面倒を見てくれるので、基本的にはユーザが頑張ってメンテナンスする必要はない。一方、テーブルのソートはクエリのパフォーマンスに影響する重要なポイントの一つなので定期的に状態を確認するとよいと思われる。

## テーブルのソート状態を管理する

Redshiftにおけるテーブルの未ソート領域の割合は[SVV_TABLE_INFO](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/r_SVV_TABLE_INFO.html)システムテーブルの`unsorted`列で確認できる。`unsorted`は0~100%の値を取り、0%に近いほど理想的となる。

```sql:SVV_TABLE_INFOの例
select database, schema, "table", diststyle, sortkey1, unsorted
from SVV_TABLE_INFO;
```

```
| database | schema | table    | diststyle        | sortkey1    | unsorted |
|----------|--------|----------|------------------|-------------|----------|
| dev      | tpch   | lineitem | KEY(l_orderkey)  | l_shipdate  | 0        |
| dev      | tpch   | nation   | KEY(n_nationkey) | n_nationkey | 100      |  -- nationテーブルは全ての行が未ソート
| dev      | tpch   | orders   | KEY(o_orderkey)  | o_orderdate | 0        |
```

Redshiftの[VACUUMコマンドはデフォルトでテーブルの行の95%以上がソート済みの場合はソート処理をスキップ](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/r_VACUUM_command.html)するため、`unsorted`は5%以下を目指すのが1つの目安となる。

:::note info
空のテーブルにレコードをCOPYもしくはINSERTするとソートキーの順序でデータがロードされる。
- COPY: 
  - [COPY により入ってくるデータの各バッチがロード時にソートされる](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/c_best-practices-sort-key-order.html#:~:text=COPY%20%E3%81%AB%E3%82%88%E3%82%8A%E5%85%A5%E3%81%A3%E3%81%A6%E3%81%8F%E3%82%8B%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E5%90%84%E3%83%90%E3%83%83%E3%83%81%E3%81%8C%E3%83%AD%E3%83%BC%E3%83%89%E6%99%82%E3%81%AB%E3%82%BD%E3%83%BC%E3%83%88)ことを利用
  - 前提条件としてソートキーが1つのみ・複合ソートキー（インターリーブソートキーは不可）・テーブルが100%ソート済みもしくは空、などを満たしている必要がある。詳細は[ソートキー順序でデータをロードする](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/vacuum-managing-vacuum-times.html#vacuum-load-in-sort-key-order)を参照
- INSERT:
  - [データが空のテーブルに最初にロードされると、行がディスク上にソート順に格納される](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/t_Sorting_data.html#:~:text=%E3%83%87%E3%83%BC%E3%82%BF%E3%81%8C%E7%A9%BA%E3%81%AE%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB%E3%81%AB%E6%9C%80%E5%88%9D%E3%81%AB%E3%83%AD%E3%83%BC%E3%83%89%E3%81%95%E3%82%8C%E3%82%8B%E3%81%A8%E3%80%81%E8%A1%8C%E3%81%8C%E3%83%87%E3%82%A3%E3%82%B9%E3%82%AF%E4%B8%8A%E3%81%AB%E3%82%BD%E3%83%BC%E3%83%88%E9%A0%86%E3%81%AB%E6%A0%BC%E7%B4%8D%E3%81%95%E3%82%8C)ことを利用
  - 後述のディープコピーで詳細解説
:::

:::note info
空ではないテーブルにレコードを追加・更新した直後はそのレコードはディスク上の未ソート領域に格納される。未ソート領域が増えるとSVV_TABLE_INFO上の`unsorted`の値が増加する。VACUUMを行うことで未ソート領域のレコードがソート済領域へマージされ、`unsorted`の値が減少する。
※COPYでデータをロードすると未ソート領域内はソートキーに基づいてソートされるが、ソート済領域とはマージされず、基本的には`unsorted`が増加するためVACUUMが必要となる。詳細は[マージ済みの行のボリューム管理](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/vacuum-managing-vacuum-times.html#vacuum-managing-volume-of-unmerged-rows)を参照

以下の方法を使うと、空ではないテーブルにレコードを追加する場合であってもテーブルのソート状態を維持することができる。

- COPYコマンド毎にソートキー順序でデータをロードする場合: 
  - [COPY により入ってくるデータの各バッチがロード時にソートされる](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/c_best-practices-sort-key-order.html#:~:text=COPY%20%E3%81%AB%E3%82%88%E3%82%8A%E5%85%A5%E3%81%A3%E3%81%A6%E3%81%8F%E3%82%8B%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E5%90%84%E3%83%90%E3%83%83%E3%83%81%E3%81%8C%E3%83%AD%E3%83%BC%E3%83%89%E6%99%82%E3%81%AB%E3%82%BD%E3%83%BC%E3%83%88)ことを利用。COPYコマンド間でキーの範囲に重複がない場合（例えば1月分・2月分・3月分・・・に分けて3回COPY）、データがソート済み領域に追加される
  - 前提条件としてソートキーが1つのみ・複合ソートキー（インターリーブソートキーは不可）・テーブルが100%ソート済みもしくは空、などを満たしている必要がある。詳細は[ソートキー順序でデータをロードする](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/vacuum-managing-vacuum-times.html#vacuum-load-in-sort-key-order)を参照
- INSERT時にソートキーでORDER BYする場合: 
  - 追加したレコードは**未ソート領域に入り、未ソート領域内のレコードの順序はテーブルのソートキーと一致する**。この場合メタデータである`unsorted`の値は増加することがあるものの、ディスク上のレコードは未ソート領域内で実質にソート済みとなるため、範囲限定スキャンが効く（つまりVACUUM不要）
  - 少々トリッキーな方法。後述の分割ディープコピーで詳細解説
:::

## 手動ソート方法の選択肢

前述の通り基本的にソートは自動VACUUMに任せればよいが、稀にテーブルを手動でソートしたいケースがある。

- 例1. クラスターを高負荷な状態で長期間運用しているケース。自動VACUUMはクラスターのリソースの空きを見て実行されるため、リソースに余裕がない場合はユーザクエリが優先され自動VACUUMが十分に実行されない場合がある
- 例2. Redshiftへの移行時に大量のデータを取り込むケース。[COPY元のデータファイルがソート](https://docs.aws.amazon.com/redshift/latest/dg/c_best-practices-sort-key-order.html)されていない限りテーブルのソートが必要になる

Redshiftでは手動でソートを行う場合、以下示すようにいくつかの選択肢がある。

### VACUUMを行う

テーブルの更新直後などにVACUUMコマンドを直接実行する。BOOSTオプションにより追加のリソースを割り当てることも可能（テーブルロック等の制約に注意）
```sql: VACUUM実行例
VACUUM;  -- 現在のデータベース内の全てのテーブルのVACUUMを実行

VACUUM my_table1; -- 特定のテーブルのVACUUM

VACUUM my_table2 BOOST; -- 追加のリソースを割り当て
```

ポイント

- 手軽に実行できる
- 巨大なテーブルの場合はディープコピーの方が速い
- 途中で[CANCEL](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/r_CANCEL.html)しても進捗は維持される

### ディープコピーを行う

[ディープコピー](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/performing-a-deep-copy.html)は巨大なテーブルを高速にソートする方法の一つ。元のテーブルとは別のテーブルを新たに作成し、元テーブルから新テーブルへINSERTする。[データが空のテーブルに最初にロードされると、行がディスク上にソート順に格納される](https://docs.aws.amazon.com/ja_jp/redshift/latest/dg/t_Sorting_data.html)ことを利用する。

```sql:ディープコピー例
create table my_table_sorted (...);  -- 新しく空のテーブルを作成

insert into my_table_sorted (select * from my_table);  -- 元テーブルから新テーブルへINSERT

drop table my_table;  -- 元テーブルをDROP

alter table my_table_sorted rename to my_table;  -- 新テーブル名を変更
```

ポイント

- 特に未ソート領域が大きい場合はVACUUMよりも高速に実行できる
- VACUUMでは十分な性能が出ない (`unsorted`の値が下がらない) 場合やテーブルの新規作成・初期ロード時に使用
- 新しく別のテーブルを作るため、依存するビューなどがある場合は作り直しが必要となる点に注意が必要
- 1回で全てのデータをINSERTする必要があるため、Redshiftの最大クエリ実行時間である24時間を超えてしまう場合は使用できない

### 分割ディープコピーを行う

通常のディープコピーでは1回のINSERTで処理が終わらないほどテーブルが大きい場合に、INSERTを小分けにする方法。

```sql:分割ディープコピー例
create table my_table_sorted (...);  -- 新しく空のテーブルを作成

-- 元テーブルから新テーブルへN回に分けてINSERT (skeyはソートキー)
insert into my_table_sorted (select * from my_table where skey <= 0 and skey < 100 order by skey);  -- 範囲1
insert into my_table_sorted (select * from my_table where skey <= 100 and skey < 200 order by skey);  -- 範囲2
...
insert into my_table_sorted (select * from my_table where skey <= 200 and skey < 300 order by skey);  -- 範囲N

drop table my_table;  -- 元テーブルをDROP

alter table my_table_sorted rename to my_table;  -- 新テーブル名を変更
```

ポイント

- 小分けにしてINSERTすることで処理時間が予測しやすくなる
- **INSERT間でソート範囲が重複しないよう、WHERE句の条件列はソートキー列を使用する**
- **1回のINSERTが適切なデータサイズとなるよう、WHERE句で指定する範囲を調整する必要がある**
- この方法を使うとSVV_TABLE_INFO上は`unsorted`の値が増加するように見えるが（ANALYZEしても`unsorted`が大きいまま）、ディスク上のデータは実質的にソート済み状態となるため問題ない

ソートの実行はテーブルのスキャン→メモリ上でソート→テーブルへ書き込みが必要なため、大量のディスクIO及びメモリを消費する。従って数十TBを超えるような巨大なテーブルでは効率的なソート方法を選択することで数時間〜数日の時間を節約できる場合がある（クラスターサイズにも依る）。

## 分割ディープコピーの検証

今回はRedshift Serverlessで分割ディープコピーによるINSERT性能を検証した。データセットは[TPCH30TB](https://github.com/awslabs/amazon-redshift-utils/tree/master/src/CloudDataWarehouseBenchmark/Cloud-DWB-Derived-from-TPCH)のlineitemテーブルを増幅し6400億件 (100TB) のテーブルを用意した。

```sql: lineitemのDDL
create table lineitem (
  l_orderkey int8 not null ,
  l_partkey int8 not null,
  l_suppkey int4 not null,
  l_linenumber int4 not null,
  l_quantity numeric(12,2) not null,
  l_extendedprice numeric(12,2) not null,
  l_discount numeric(12,2) not null,
  l_tax numeric(12,2) not null,
  l_returnflag char(1) not null,
  l_linestatus char(1) not null,
  l_shipdate date not null ,
  l_commitdate date not null,
  l_receiptdate date not null,
  l_shipinstruct char(25) not null,
  l_shipmode char(10) not null,
  l_comment varchar(44) not null,
  Primary Key(L_ORDERKEY, L_LINENUMBER)
) distkey(l_orderkey) sortkey(l_shipdate,l_orderkey);
```

実行クエリは以下の通り。

```sql
create table lineitem_sorted (...);  -- 新しく空のテーブルを作成

-- 適切な件数となるようyyyy-mm-ddを調整
insert into lineitem_sorted (
    select * from lineitem 
    where l_shipdate <= 'yyyy-mm-dd' and l_shipdate < 'yyyy-mm-dd'
    order by l_shipdate, l_orderkey
);
```

今回はRPU及び1回のディープコピーで処理する件数を変えて計4パターンの実行時間を計測した。また比較のためテーブル全件に対する比率から割り戻すことで、テーブル全件に対し繰り返しディープコピーを実行した時の実行時間、コスト及び時間単価 (=コスト/実行時間) を計算した。結果は以下の通りとなる。

| No | 処理件数 | 対全件比率 | サイズ概算 | RPU | 実行時間 [min] | 実行時間 (全件換算) [min] | コスト (全件換算) | 時間単価 [$/min] |
|---|-----------------|-------|---------|-----|-----|------|------|------|
| 1 | 33,889,979,946  | 5.2%  | 5.2 TB  | 128 | 54  | 1038 | 1094 | 1.05 |
| 2 | 33,889,979,946  | 5.2%  | 5.2 TB  | 256 | 41  | 788  | 1661 | 2.11 |
| 3 | 167,260,817,751 | 26.1% | 26.1 TB | 128 | 157 | 601  | 633  | 1.05 |
| 4 | 167,260,817,751 | 26.1% | 26.1 TB | 256 | 84  | **321**  | **626**  | 1.95 |

:::note
注目すべき点は以下の3点。
- 実行時間 (全件換算)  - 短いほどよい
- コスト (全件換算)  - 低いほどよい
- 時間単価 - 低いほどよい
:::

今回のデータセットと検証パターンの中ではNo4のセットアップ（1回のディープコピーでより多くの行を大きなRPUで処理）が最も高速で、かつコストも安い結果となった。要因については分割回数を減らすことでオーバーヘッドが減った、またRPUに対し性能が線形にスケールしている点が推測される。

このことから、**ディープコピーを行う場合はできるだけ分割数を小さくし、かつ大きなRPUを割り当て**た方が高いコストパフォーマンスを得られることが示唆される。

その他
- ディープコピーはディスクI/Oやメモリ上でのソート処理がボトルネックになるため、Redshift ServerlessではRPU・Provisionedの場合はインスタンスタイプ及びノード数を大きくすることが性能向上に寄与すると思われる
- 今回のデータセットであれば、より大きいRPUを使用することで1回のディープコピーで完了できるなる可能性がある
- 今回は16カラム x 6400億行のテーブルに対し分割ディープコピーを実行したが、テーブルサイズが同じでもカラム数の多いワイドテーブルに対する性能特性は異なる可能性がある

## まとめ

Redshiftにおいて巨大なテーブルを手動でソートする方法として、分割ディープコピーを行う手段を紹介した。基本的には自動VACUUMに頼り、定期的にSVV_TABLE_INFOでテーブルのソート状態 (`unsorted`) を確認し、ソートに関する問題を早期に発見する運用とするのがよい。

その上で、巨大なテーブルをソートする必要が出てきた場合は以下の手順で検討する。

1. VACUUMの検討
    1. VACUUMを数時間実行しSVV_TABLE_INFOの`unsorted`の減る速度を監視する
    1. VACUUMの実行速度が問題なければ終わるまでそのまま継続
    1. 進捗が遅い場合はVACUUMをCANCELしてディープコピーを検討する
2. ディープコピーの検討
    1. テーブルの一部を使用して分割ディープコピーを1回だけ実行し実行時間を計測する
    1. 実行時間、対象件数をテーブル全件で割り戻し、テーブル全件のディープコピーに必要な実行時間を見積もる
    1. ディープコピーの分割が必要かを判断。できるだけ少ない回数にまとめる