Redshiftで遊ぼう~アソシエーション分析~(前編)

まえがき

弊社のsmarticA! DMPでは、 DWHとしてAmazon Redshiftを使用しています。
RedshiftはPostgreSQL 8.0.2をベースに開発されており、SQLを使った柔軟な分析が可能です。
今回のエントリでは、Redshiftに蓄積されたログデータを用いて共起分析をやってみようということで、 共起性の指標となるさまざまな係数を計算してみます。

その上で、Redshiftを使うときの注意点をまとめてみます。

環境

Redshift (dw2.large) を2ノード使用しています。8xlargeでごり押しできる日を夢見ながら質素に生きています。

共起性の指標について

今回は適当な大きさのログを使って以下の4種類の指標を求めてみようと思います。

  • Dice 係数
  • Jaccard 係数
  • Simpson 係数
  • Cosine 係数

各係数については、 弊社テクノロジー解説ページ内 データマイニング/6.商品分析の手法(ABC分析、アソシエーション分析) にて解説されておりますので、よろしければご参照ください。

使用したもの

適当なログ(3500万レコード程度)と、以下のテストデータ

余談ですが、Redshiftで create table するときは必ずカラムのエンコードを付けるようにしましょう。
テスト用だからって適当にやっているとすぐに容量不足になってしまいます。

計算してみよう

手計算

上で用意したテスト用データを、Excelを使って計算してみます。1
ログに出現する item_idの全ての2つの組み合わせを (ITEM-X, ITEM-Y)として、必要な数値を出していきます。
※説明の都合上、テストデータを購買ログとして扱います。

ITEM-X ITEM-Y Xを購入したUU数 Yを購入したUU数 共起頻度 Dice 係数 Jaccard 係数 Simpson 係数 Cosine 係数
1 2 3 3 3 1 1 1 1
1 3 3 2 2 0.8 0.666666667 1 0.816496581
1 10 3 1 1 0.5 0.333333333 1 0.577350269
2 1 3 3 3 1 1 1 1
2 3 3 2 2 0.8 0.666666667 1 0.816496581
2 10 3 1 1 0.5 0.333333333 1 0.577350269
3 1 2 3 2 0.8 0.666666667 1 0.816496581
3 2 2 3 2 0.8 0.666666667 1 0.816496581
3 10 2 1 1 0.666666667 0.5 1 0.707106781
10 1 1 3 1 0.5 0.333333333 1 0.577350269
10 2 1 3 1 0.5 0.333333333 1 0.577350269
10 3 1 2 1 0.666666667 0.5 1 0.707106781

初版

クエリ1発でできたら良いよねっ!というわけでできたのがこちら

テストデータで実行すると手計算と同様の結果になったので、いざ突撃・・・9分20秒ほどで完了しました。

これは早いのか?それとも遅いのか?実行計画を見てみます。

cost がすごい感じになりました。cost の大小がそのままパフォーマンスを表すわけではありませんが、 DS_BCAST_INNER が3回も登場するなど見るからに重そうです。

DS_BCAST_INNER は、クエリの実行中(主にテーブル結合時)にノード間でデータの移動があることを示しています。当然移動にもそれなりのコストがかかってきますので、その分クエリは遅くなっていると考えられます。
Redshiftの実行計画の見方においても、 DS_BCAST_INNER は避けるべきであると明記されています。

上記実行計画の L.1,16,20 に DS_BCAST_INNERがありますが、L.20 の cost が桁違いに大きいです。 まずはこれが解消できないか考えてみます。

改訂その1

初版では、物理テーブル log_0001から item_id, user_idをSELECTしたものを target_log というtemp領域に入れていました。
これによって、例えば別のログテーブルで user_iduidなどとなっている場合でも、 target_log内でエイリアスを付けてやれば続きの計算には影響がでなくなります。 ただ、続きの計算で結合に使われる事も考えると、 user_idDISTKEY が付いていたほうがよさそうです。

もともと user_idDISTKEYの場合は1発で/そうでない場合は計算用ログテーブルを作って準備してから!というのがこちら

いざ突撃・・・8分50秒程度となりました。実行計画を見てみます。

まず、もともと3500万行ほど読み込まなければならなかったところが、837万行程度まで減っています。 次にL.14を見てみると、 DS_DIST_NONE が出てきています。つまり、この部分の実行(テーブル結合)においてはノード間でデータの移動が発生しなかったということです。

今回のデータセットだと初版から30秒ほどの短縮にしかなりませんでしたが、対象とするデータによってはもっと明確な差が出てくるのではないかと思います。また、データの移動が発生すると、移動先のために裏で一時テーブルを作っているようなので、その分の容量も必要になってきます2

ところでまだ DS_BCAST_INNER が発生しているのが気になります。 これは改訂1のクエリの LL.35-36 のせいですが、ここはどうしても2列が結合に使われてしまうために、 DISTKEYを付けられないのです3。 この件の対策ついてはまた後日・・・。

まとめ

  • Redshiftで共起分析してみた
  • クエリ1発でやろうとしない
  • DISTKEY重要
  • 実行計画を確認して DS_BCAST_INNERを回避できないか考えよう

長くなってしまいましたのでいったんここまでにさせていただきます。


  1. テスト用データがあんまりよくないので全部1になってるものがありますがご容赦ください。 

  2. 実行途中でも容量オーバーすると容赦なく DISK FULL となって死亡します。 

  3. Redshiftの仕様として、DISTKEYは1テーブルに1つしか付けられません。