groonga/grnxx

部分式を使ったフィルタリングの速度を調べる

Closed this issue · 7 comments

s-yata commented

概要

#122 では部分式を含まないフィルタリングの速度を調べました．

今度は部分式を使ったフィルタリングの速度を調査します．

クエリとしては，以下のようなクエリを考えています．

  • 部分式を分ける方式
    • (Ref.A < X) && (Ref.B < X) && (Ref.C < X)
  • 部分式をまとめる方式
    • Ref.((A < X) && (B < X) && (C < X))

前者はカラムの値を取ってくるためだけに部分式を使います．
後者は条件式の評価に部分式を使います．
前者はレコードの一覧を削っていく方式になりますが，後者は評価結果を使ってレコードの一覧を一気に削ります．

s-yata commented

実験環境

  • CPU
    • Core i7 4558U 2.8GHz (up to 3.3GHz)
  • OS
    • Ubuntu 14.04 on VMWare Fusion 7

データ

  • Table: "To"
    • #rows: 100,000
    • Column: "A" (Int) - [0, 256)
    • Column: "B" (Int) - [0, 256)
    • Column: "C" (Int) - [0, 256)
  • Table: "From"
    • #rows: 10,000,000
    • Column: "Ref" (Int) - [0, 100000) - "To" への参照

クエリ

  • X: 16, 32, 64, 128, 192, 224, 240
    • (Ref.A < X) && (Ref.B < X) && (Ref.C < X)
    • (Ref.A < X) || (Ref.B < X) || (Ref.C < X)
    • Ref.((A < X) && (B < X) && (C < X))
    • Ref.((A < X) || (B < X) || (C < X))
s-yata commented

実行結果

まずは，単純に Ref.A < X と Ref.(A < X) によるフィルタを試してみました．
それから，ネイティブとの比較もおこないました．

  • Grnxx 1: Ref.A < X
  • Grnxx 2: Ref.(A < X)
X Grnxx 1 Grnxx 2 Native
16 0.081 0.101 0.034
32 0.091 0.113 0.045
64 0.111 0.141 0.063
128 0.138 0.188 0.096
192 0.128 0.159 0.080
224 0.118 0.138 0.072
240 0.115 0.129 0.068

Ref.A < X の方が Ref.(A < X) より速いことがわかります．
Grnxx と Native の比較では， #122 で得られた結果と同様の傾向が見られます．

s-yata commented

実行結果（AND）

次は以下に示すフィルタの比較です．

  • Grnxx 1: (Ref.A < X) && (Ref.B < X) && (Ref.C < X)
  • Grnxx 2: Ref.((A < X) && (B < X) && (C < X)
X Grnxx 1 Grnxx 2 Native
16 0.086 0.124 0.037
32 0.098 0.146 0.045
64 0.130 0.202 0.073
128 0.207 0.336 0.146
192 0.243 0.362 0.151
224 0.263 0.327 0.142
240 0.266 0.295 0.143

Grnxx 1 の方が Grnxx 2 より速いようです．
Native との差については，相変わらず似たような傾向が見られます．

s-yata commented

実行結果（OR）

次は以下に示すフィルタの比較です．
AND から OR になっただけです．

  • Grnxx 1: (Ref.A < X) || (Ref.B < X) || (Ref.C < X)
  • Grnxx 2: Ref.((A < X) || (B < X) || (C < X)
X Grnxx 1 Grnxx 2 Native
16 0.291 0.252 0.094
32 0.329 0.305 0.118
64 0.398 0.372 0.155
128 0.407 0.382 0.195
192 0.260 0.258 0.136
224 0.197 0.197 0.102
240 0.159 0.162 0.085

OR については Grnxx 2 の方が Grnxx 1 より速いようです．
Native との差については，相変わらず似たような傾向が見られます．

s-yata commented

追加

Grnxx 1 の方式では，参照用のレコード一覧を何度も作成することになるので，オーバーヘッドが大きいはずです．
一方， Grnxx の方式では，部分式での LOGICAL_AND が単純にレコードを削る実装にならず， LOGICAL_OR のような実装になっているため，効率が悪くなっているはずです．

以上のことを踏まえると，部分式では BITWISE_AND/OR を使うと無駄がなくて良いのではないかと思います．
試してみる価値がありそうです．

s-yata commented

実行結果（AND）

次は以下に示すフィルタの比較です．

  • Grnxx 1: (Ref.A < X) || (Ref.B < X) || (Ref.C < X)
  • Grnxx 2: Ref.((A < X) || (B < X) || (C < X)
  • L: LOGICAL_AND
  • B: BITWISE_AND
X Grnxx 1L Grnxx 1B Grnxx 2L Grnxx 2B Native
16 0.086 0.239 0.121 0.198 0.037
32 0.098 0.256 0.145 0.215 0.048
64 0.133 0.291 0.202 0.259 0.072
128 0.205 0.380 0.336 0.323 0.145
192 0.249 0.370 0.371 0.316 0.154
224 0.260 0.343 0.324 0.296 0.139
240 0.269 0.318 0.297 0.265 0.146

実行結果（OR）

次は以下に示すフィルタの比較です．

  • Grnxx 1: (Ref.A < X) || (Ref.B < X) || (Ref.C < X)
  • Grnxx 2: Ref.((A < X) || (B < X) || (C < X)
  • L: LOGICAL_OR
  • B: BITWISE_OR
X Grnxx 1L Grnxx 1B Grnxx 2L Grnxx 2B Native
16 0.294 0.268 0.252 0.223 0.097
32 0.329 0.314 0.304 0.269 0.117
64 0.398 0.384 0.364 0.338 0.155
128 0.401 0.418 0.375 0.377 0.193
192 0.255 0.360 0.253 0.340 0.133
224 0.198 0.317 0.196 0.284 0.098
240 0.158 0.298 0.161 0.263 0.083

まとめ

AND については 1L が一番良さそうです．
OR については X によって 2L が良かったり 2B が良かったりと変化します．
とはいえ， BITWISE_OR にすると意味が変わってしまうので，基本的には 2L ですかね．
劇的な差があるわけでもありませんし…．

そういえば， 1L について LOGICAL_NOT と LOGICAL_AND に変換する方式を入れ忘れていました．

s-yata commented

実行結果（LOGICAL_NOT + LOGICAL_AND）

Grnxx 3 を追加してみました．

  • Grnxx 3: !((Ref.A >= X) && (Ref.B >= X) && (Ref.C >= X))
X Grnxx 1L Grnxx 1B Grnxx 2L Grnxx 2B Grnxx 3 Native
16 0.294 0.268 0.252 0.223 0.257 0.097
32 0.329 0.314 0.304 0.269 0.282 0.117
64 0.398 0.384 0.364 0.338 0.308 0.155
128 0.401 0.418 0.375 0.377 0.270 0.193
192 0.255 0.360 0.253 0.340 0.183 0.133
224 0.198 0.317 0.196 0.284 0.147 0.098
240 0.158 0.298 0.161 0.263 0.134 0.083

X = 16, 32 のときは Grnxx 2B に負けているものの，それ以外では Grnxx 3 が一番良い結果を出しました．