ユーザー検索処理(あるいは配列マージ性能の言語比較) 補足

ユーザー検索処理(あるいは配列マージ性能の言語比較) 補足


前回、HHVMを使って100万ユーザを20個の条件でフィルタする処理が0.25秒となりましたが、今回はその補足です。

  1. JavaのTreeSetがなぜか遅い件
  2. 分散クエリを使うと?(AWS-Redshift)

などを調べました。

TreeSet

前回のJavaのソース(こちら)で、HashSetを使っていますが、本来はソート済みのためTreeSetがよいと思いましたが、なぜか後者の方が1.5倍ほど遅かったです。これはReatainAllの実装がイケてない今回のデータと合わないようです。(Java1.8、TreeSetはソート済みにもかかわらず、ReatainAllの実装はAbstructCollectionのコード)

ちょっとGOで書いてみました。ソースはこれ(2Nとなるようなロジックです)

r := make([]int, cnt)
k := 0
j2 := 0
for i := 0; i < len(a1); i++ {
for j := j2; j < len(a2); j++ {
if a1[i] < a2[j] {
break
}
j2++
if a1[i] == a2[j] {
// find
r[k] = i
k++
break
}
}

 

go run 05_go/hoge.go
887ms in create List
37ms in arrayintersect

メモリも300MB弱しか使ってないように見えます(ちゃんと測っていないですが)。なお、この実装はデータの特性によっては、遅くなることもあると思いますが、今回の前提のデータ(8割は重複するAND)では効率がよいですね。

Redshift

100万ユーザー× 100属性 の1億レコード入れて、フルスキャンの処理速度をみてみました。想定ケースとしては、任意の属性番号8個をもつユーザのリストを取得するSQLを実行してみました。

create table user_att(
id int not null auto_increment ,
user_id int not null ,
att_id int not null ,
att_value int not null ,
PRIMARY KEY (`id`) ,
KEY att(att_id,att_value,user_id)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
;

insert into user_att values(null,1,1,1)(null,1,1,2);

A.
insert into user_att select null id, ceil(r * 500000 + 1) user_id, case when r2 <= 0.8 then ceil(r2 * 1.25 * 400 + 1) else ceil((r2 -0.8) * 5 * 1600 + 401) end att_id, ceil(r3 * 9 +1) att_value from( select @i := @i + 1 as seq,rand() r,rand() r2 , rand() r3 from user_att a1 ,user_att a2 , (select @i:=(select case when max(id) is null then 1 else max(id) end from user_att)) as dummy ) a;

ローカルのMysqlでは返ってこなかった一億件インサートもあっという間。
Execution time: 56.86s

select user_id,count(*) c from user_att where att_id in (100,102,103,104,105,106,210,212,314,377,888)
group by user_id having count(*) > 8 order by c

Execution time: 3.63s
awsのコンソール上では、2秒ちょっと。

4ノードにして、同じSQLを実行

Execution time: 1.39s
awsのコンソール上では、0.4秒

こっちなら余計な前処理はいらないし、スケールもする。。

まとめ

Redshiftスゴイ。