【新機能】Amazon Redshift の Interleaved Sorting機能を試してみた

はじめに

2015年05月11日にAmazon Redshift の Interleaved Sorting機能のリリースが発表されました。 データ分析では複数の分析軸によるデータディスカバリーが求められますので、DWHは高速に異なるカラムの検索や集計が必要とされます。既存のソートキー(COMPOUND SORTKEY)は、ソートキーの定義に無いカラムでは全てのブロックのスキャンが発生するので相対的に早くないという課題がありました。今回の Interleaved Sortingのリリースによって、ソートキーに指定した複数のカラムに対して、クエリーのフィルタを柔軟かつ高速に行えるようになりました。

昨年のre:invent2014のSDD414 - Amazon Redshift Deep Dive and What’s Next の "Multidementional indexing with Space Filling curves"で紹介されています。その時は数週間後にリリースすると言われずっと待ち望んでいましたが、半年後ついにリリースされました。

Amazon Redshift のデータブロックの管理

既存のソートキー(COMPOUND SORTKEY)と新しいINTERLEAVED SORTKEYの違いを理解するにはAmazon Redshift のデータブロックの管理についてイメージを掴んでもらうことが近道です。

データはカラム毎に1MB単位の「データブロック」に格納します。テーブル作成時にソートキーを定義するとデータブロックをオンメモリで管理する「ゾーンマップ」が作成されます。ゾーンマップでは各ブロックの最小値と最大値をメタデータの一部として格納します。

Redshiftのパフォーマンス戦略ではデータブロックのI/Oの効率化が重要です。なのでソートキーを利用してデータを検索できるときはゾーンマップを参照して、データが格納されているブロックをピンポイントでメモリ上にロードすることでI/Oを効率化しています。

既存のソートキー：COMPOUND SORTKEY

COMPOUND SORTKEY(複合ソートキー)では、テーブルの作成時に1つ以上のカラムをソートキーとして定義することができます。 クエリプロセッサはオンメモリのゾーンマップと各ブロックの最小値と最大値を利用して、テーブルスキャン中にクエリーの条件に一致しない多数のブロックをすばやくスキップすることができます。これがソートキー指定したカラムのクエリーフィルタが高速である理由です。一方、ソートキー指定しないカラムは不要なブロックのスキップができず全てのブロックのスキャンが発生するので相対的に遅くなります。

以下の図では、このテーブル上に2つのCOMPOUND SORTKEY(cust_idとpage_id)があり、合計４ブロックに配置されているとします。COMPOUND SORTKEYを使う場合、最初にcust_idでソートされ、その後にpage_idでソートされてデータが格納されます。（[1, 1]という表記は、cust_idが「1」で、page_idが「1」である事を表しています）

• 第1ブロック：cust_id(最小:1、最大:1)、page_id(最小:1、最大:4)
• 第2ブロック：cust_id(最小:2、最大:2)、page_id(最小:1、最大:4)
• 第3ブロック：cust_id(最小:3、最大:3)、page_id(最小:1、最大:4)
• 第4ブロック：cust_id(最小:4、最大:4)、page_id(最小:1、最大:4)

上記の図を例にすると、cust_idが「1」のデータは1ブロックスキャンで済みますが、page_idが「1」のデータは１全てのブロックスキャンが必要です。

• ソートキー指定したカラム：O(log n)
• ソートキー指定しないカラム：O(n)

ソートキーの定義がない列でクエリをフィルタする方法として「プロジェクション」が考えられます。プロジェクションとは、異なるソートキーを指定したテーブルを作成・コピーして別に管理をするという手法です。しかし、プロジェクションを作成した数に応じて、データのロードやソートなどの処理には大きなオーバーヘッドが生じてしまいます。しかも、列の数が多くなると、プロジェクションの対象となる列の組み合わせも指数関数的に増加します。8つカラムを対象とした場合では、最大40,000個のプロジェクション対象の組み合わせが考えられるのです。また、この高速化の恩恵を得るには作成したプロジェクションテーブルを利用者が使い分ける必要がありました。

【新機能】Interleaved Sorting：INTERLEAVED SORTKEY

INTERLEAVED SORTKEYはソートキーを多次元空間データとして管理することで、指定した各カラムに等しい検索条件を提供します。異なるカラムによって様々なクエリをフィルタしたり、ソートキーをクエリのフィルタ条件により多く指定することで、一般にINTERLEAVED SORTKEYを使用するとクエリのパフォーマンスを向上させることができます。なお、ゾーンマップは多次元空間を1次元空間に写像する手法の一つである"Space Filling curves"を用いて一次元データ化しています。

以下の図では、このテーブル上は2つのINTERLEAVED SORTKEY(cust_idとpage_id)があり、合計４ブロックに配置されているとします。INTERLEAVED SORTKEYを使う場合、cust_idとpage_idの2つのキーを2次元データとしてソートして格納されます。（[1, 1]という表記は、cust_idが「1」で、page_idが「1」である事を表しています）

• 第1ブロック：cust_id(最小:1、最大:2)、page_id(最小:1、最大:2)
• 第2ブロック：cust_id(最小:1、最大:2)、page_id(最小:3、最大:4)
• 第3ブロック：cust_id(最小:3、最大:4)、page_id(最小:1、最大:2)
• 第4ブロック：cust_id(最小:3、最大:4)、page_id(最小:3、最大:4)

上記の図を例にすると、cust_idが「1」のデータは2ブロックスキャンで済み、page_idも「1」のデータは2ブロックスキャンが必要で済みます。全ブロックスキャンがなくなりましたね。さらにcust_idが「1」かつ page_idが「1」のデータは1ブロックスキャンで済みます。クエリのフィルタ条件にINTERLEAVED SORTKEYのカラムが多く含まれているほど、ブロックスキャンが少なくて済み、クエリが高速化します。INTERLEAVED SORTKEYに指定したカラムが3つなら3次元、4つなら4次元...8つなら8次元となります。

データブロックの含まれるデータ配置とゾーンマッピングを見直すことで実現されていることがイメージ出来たでしょうか。

INTERLEAVED SORTKEY の使い方

では、早速使ってみましょう。INTERLEAVED SORTKEYを指定するには、以下のようにCREATE TABLEでSORT KEYの前にINTERLEAVEDと追加指定するだけです。最大で8つまでのsort key列を指定できます。(INTERLEAVEDと指定しない場合はCOMPOUND SORTKEYとして生成されます)

新しい SORTKEY パラメータ

現状は英語サイトでマニュアルが公開されていませんので、勝手にマニュアル（非公認）を公開します。

[ [ COMPOUND | INTERLEAVED ] SORTKEY ( column_name [, ...]) ]

テーブルに対して 1 つ以上のソートキーを指定します。データをテーブルにロードすると、データはソートキーとして指定された列に従ってソートされます。列名の後に [ COMPOUND | INTERLEAVED ] SORTKEY キーワードを使用して 1 列のソートキーを指定することができます。または、[ [ COMPOUND | INTERLEAVED ] SORTKEY ( column_name [, ...]) ] 構文を使用して、テーブルのソートキーとして 1 つまたは数の列を指定することができます。

COMPOUND SORTKEY もしくは SORTKEY として指定した場合は複合ソートキーとなります、一方、INTERLEAVED SORTKEYと指定した場合はインターリーブドソートキーとなります。

ソートキーを指定しない場合、デフォルトでテーブルはソートされません。

例．CREATE TABLE - INTERLEAVED SORTKEYの定義

CREATE TABLE PageViews (cust_id INTEGER, page_id INTEGER, duration INTEGER)
INTERLEAVED SORTKEY (cust_id, page_id);

性能検証

パフォーマンスの計測条件

• クエリ性能検証 リージョン：東京リージョン（ap-northeast-1）
• クラスタ：dw2.large x 2
• データ：AWSが提供しているサンプルデータ（s3://awssampledbapnortheast1/ssbgz/lineorder）
• レコード数：5.7億レコード
• テーブル：lineorder
• テーブル定義（抜粋）
  • SORTKEY無し：なし
  • COMPOUND SORTKEY：sortkey(lo_orderdate, lo_custkey);
  • INTERLEAVED SORTKEY：interleaved sortkey(lo_orderdate, lo_custkey);
• 検索時間の計測値は２回目とする（クエリプラン生成とコンパイルに要する時間は測定しないため）

データロード時間の計測

COPY lineorder FROM 's3://awssampledbapnortheast1/ssbgz/lineorder' CREDENTIALS 'aws_access_key_id=xxx;aws_secret_access_key=yyy' GZIP;

• SORTKEY無し：16分 52.71秒
• COMPOUND SORTKEY：28分 41.22秒
• INTERLEAVED SORTKEY：29分 20.04秒

COMPOUND SORTKEYとINTERLEAVED SORTKEYでは大きな違いが見られませんでした。INTERLEAVED SORTKEY指定のテーブルへのロード時間はこれまでと大きく変わらないと見られます。

第１ソートキーによる検索時間の計測

SELECT COUNT(*) FROM lineorder WHERE lo_orderdate = 19971025;

• SORTKEY無し：1382.173 ms
• COMPOUND SORTKEY：87.663 ms
• INTERLEAVED SORTKEY：306.379 ms

COMPOUND SORTKEYが最も早い結果になりました。ソートキー順にデータブロックに格納されているので最も効率よくブロックスキャンできたことが理由として考えられます。しかし、INTERLEAVED SORTKEYもSORTKEY無しに比べ５倍近い性能向上が確認できました。

第２ソートキーによる検索時間の計測

SELECT COUNT(*) FROM lineorder WHERE lo_custkey = 2965006;

• SORTKEY無し：2612.694 ms
• COMPOUND SORTKEY：2635.162 ms
• INTERLEAVED SORTKEY：316.931 ms

INTERLEAVED SORTKEYが最も早い結果となりました。これはINTERLEAVED SORTKEYが指定した全てのソートキーに対して同じ重み付けでソートすることを表しています。一方、COMPOUND SORTKEYは第２ソートキーの順にデータが格納されていないため全てのブロックスキャンが発生して、SORTKEY無しとほぼ同じ結果になったと考えられます。

第１と第２ソートキーによる検索時間の計測

SELECT COUNT(*) FROM lineorder WHERE lo_orderdate = 19971025 and lo_custkey = 1717;

• SORTKEY無し：5272.099 ms
• COMPOUND SORTKEY：88.077 ms
• INTERLEAVED SORTKEY：90.507 ms

今回はCOMPOUND SORTKEYとINTERLEAVED SORTKEYはほぼ同じ結果となりました。COMPOUND SORTKEYは第１と第２ソートキー順にデータブロックに格納されているので最も効率よくブロックスキャンできたことが考えられますのでこれよりも速くなることは考えられません。なのでINTERLEAVED SORTKEYがその計測時間にかなり近いという結果は大健闘だといえるでしょう。（エライぞ！、INTERLEAVED SORTKEY）

INTERLEAVED SORTKEYのポイント

効果的なINTERLEAVED SORTKEY

例えば、以下のようにソートキーを指定したとします。

INTERLEAVED SORTKEY(customer, item, age)

INTERLEAVED SORTKEYは各カラムまたはカラムのサブセットに対して等しい効果があります。クエリ毎にフィルタするカラムが異なる場合、INTERLEAVED SORTKEYを使用することでクエリのパフォーマンスを向上させることができます。条件に指定したカラムが、第２ソートキーの場合などはCOMPUND SORTKEYよりも、クエリのパフォーマンスを大幅に向上します。 上記の例の場合、customer、item、ageのどれで検索しても等しい効果があります。

さらに、INTERLEAVED SORTKEYは、WHERE句に１つ以上のより多くのソートキーカラムを指定する時に最も効果的です。 上記の例の場合、複数カラム組み合わせではより高速化し、customerとitem、itemとage、ageとcustomer の組み合わせで検索しても等しい効果が得られます。

INTERLEAVED SORTKEYはスライス毎にソートが適用され、テーブルはスライス毎に複数の1メガバイトのブロックを必要とするのに十分な大きさあり、かつ、クエリプロセッサはブロックのフィルタ条件を使用してかなりの部分をスキップすることができた時に最も効果が現れます。テーブルが使用するブロックの数を表示するには、STV_BLOCKLISTシステムビューで参照できます。

ソートキーのプレフィックス重複の改善

単一カラムのソート時にカラムの値が長い共通のプレフィックスを持っている場合、INTERLEAVED SORTKEYはCOMPOUND SORTKEYよりも優れた性能を与える可能性があります。

例えば、URLは一般に「http://www」で始まります。

COMPOUND SORTKEYは、ソートキーにプレフィックス文字の限られた数(8バイト)を使用するので、上記の例の場合はキーの重複の多く生じてしまいます。

INTERLEAVED SORTKEYは、ゾーンマップのキーの値に対して内部圧縮方式を使用していますので、より長い共通のプレフィックスを持つカラムのキーをCOMPOUND SORTKEYよりも区別することができます。

VACUUMのREINDEXの必要性

INTERLEAVED SORTKEYを設定することで得るパフォーマンスの維持・向上には、VACUUMによる負荷や処理時間の増加を考慮する必要があります。

INTERLEAVED SORTKEY のリリースに伴い、VACUUMコマンドにREINDEXオプションが追加されています。（執筆時点は英語マニュアルのみ）

VACUUM [ FULL | SORT ONLY | DELETE ONLY | REINDEX ] [ table_name ]

VACUUM(英語サイト)

INTERLEAVED SORTKEYを設定したテーブルの場合、すでにデータが含まれてソートされたテーブルに行を追加すると、パフォーマンスが時間の経過とともに劣化する可能性があります。この劣化は、COMPOUND SORTKEYとINTERLEAVED SORTKEYの両方で発生しますが、INTERLEAVED SORTKEYのテーブルの方がより大きな影響があります。 VACUUMはソート順が回復しますが、新たにインターリーブされたデータをマージするとすべてのデータ·ブロックを変更することがあるので、インターリーブのテーブルは時間がよりかかる場合があります。（データにもよりますが、10〜50%が目安です）テーブルが最初にロードされると、Redshiftはソートキーカラムの値の分布をANALYZEして、ソートキーカラムの最適なインタリーブに使用します。 テーブルが大きくなると、ソートキーカラムの値の分布に変化やスキュー(特定のカラム検索の性能劣化)が生じ、特に日付またはタイムスタンプ列が顕著です。スキューが大きくなりすぎるとパフォーマンスが影響を受ける可能性があります。ソートキーの再分析やパフォーマンスを復元するためにはVACUUMコマンドにREINDEXキーワードを指定して実行します。VACUUM操作はデータ上の余分な解析パスを取る必要があるため、VACUUMのREINDEXは標準的なVACUUMよりも長くかかることがあります。VACUUM REINDEXを実行する頻度を判断するにはVacuuming Tablesを参照してください。

最後に

既存のソートキー(COMPOUND SORTKEY)と新しいINTERLEAVED SORTKEYのアーキテクチャと性能計測、ポイントについて解説しました。アーキテクチャを理解すると今回のアップデートがデータ管理から実行ブランの生成に至る広範囲な機能追加であることがイメージ出来たと思います。

他のデータソースからのRedshiftにインポート（COPY）するデータは既存のソートキー(COMPOUND SORTKEY)でも構いませんが、BIツール（Tableau等）から参照対象となるテーブルにはINTERLEAVED SORTKEY一択と言って過言ではないと考えています。

なぜなら、データマートのテーブルにINTERLEAVED SORTKEYを指定することで、M-OLAP(Multi Dementional OLAP)ほどの重い事前集計が不要で、M-OLAPのような高速かつ柔軟なデータディスカバリが実現できるからです。