データが主食

データエンジニアの備忘録。分析だったり、読んだ本のメモだったり。

URL前方一致クエリを高速に実行するためにhttp://を除外してみた

アクセスログを分析していると、URLを条件とするクエリを書くことが多いと思います。特に、計測用のパラメータを使った分析などでは、前方一致を使ったクエリが多くなると思います。

SQLで書くとこんな感じですね。

select uid, url
from accesslog
where regexp_like(url "^http://1.example.com/.*$")

ふと疑問に思いました。 アクセスログの場合全行のurlカラムは http:// または https:// で始まります。 ということは前方一致でcharを比較してくときに、先頭7または8byteは確実に一致するため、比較演算が無駄になっているのでないだろうか。

例えば、http://https:// を別カラムとして格納するテーブル設計にした場合、高速化できる可能性があるのではないだろうか。 特に、数億行と文字列比較するなどのシチュエーションだと、それなりに違いが出てくるのではないだろうか。

Scalaでの実験

Sparkの裏側を妄想して、Scalaで同じような状況を再現し実験してみました。

100万行のアクセスログから、前方一致に該当する行を全て取り出すという計算をしてみます。片方のアクセスログは、http://を除外してあります。

アクセスログの中身

URLそのままログ

http://0.example.com
http://1.example.com
...
http://999999.example.com

http://除外ログ

0.example.com
1.example.com
...
999999.example.com

仮説

URLそのままログの場合、8 or 9 byte目で前方一致する/しないの判断が可能で、http://除外ログの場合、1 or 2 byte目で判断が可能です。 そのため、もろもろのオーバーヘッド等を忘れれば、4倍くらい早くなるのではないでしょうか。

実験スクリプト

各ログファイルから前方一致で検索する処理を10回おこない、平均時間を計測します。JVMのキャッシュなどを想定し、scalameterを利用して計測します。

import org.scalameter._
object main extends App{

  val rmSchemes = {
    for{
      i <- 0 until 1000000
    } yield i.toString + ".example.com"
  }.toList

  val allUrls = rmSchemes.map(i => "http://" + i)


  val standardConfig = config(
    Key.exec.minWarmupRuns -> 5,
    Key.exec.maxWarmupRuns -> 20,
    Key.exec.benchRuns -> 10,
    Key.verbose -> false
  ) withWarmer(new Warmer.Default)

  val time1 = standardConfig measure {
    allUrls.filter(url => url matches ("^http://1.example.com.*"))
  }
  println(time1)


  val time2 = standardConfig measure {
    rmSchemes.filter(url => url matches ("^1.example.com.*"))
  }
  println(time2)
}
sbt:compare> run
[info] Compiling 1 Scala source to /home/ec2-user/environment/compare/target/scala-2.12/classes ...
[info] Done compiling.
[info] Packaging /home/ec2-user/environment/compare/target/scala-2.12/compare_2.12-0.1.0-SNAPSHOT.jar ...
[info] Done packaging.
[info] Running main 
3706.5724933000006 ms
3387.8245134 ms

実験結果

ログの種類 平均時間
URLそのまま 3706 ms
http://除外 3387ms
  • 期待するほどは高速化できなかった。
  • hiveでも実験してみたい。

関連

ktr89.hateblo.jp