【SQLite3】 ハイパフォーマンスなインデックスをつけるために覚えておくべきこと

flickrholdr_470_200_matrix_1
  • ????????????????????

(この記事は旧ブログからの転載です。)

「インデックスは付いているはずなのに検索速度が遅い!」

ということはありませんか?わたしは見事にハマりました。

私の場合、個人使いがほとんどでシビアな性能が要求される web アプリなどを作っているわけではありません。
そんなこともあって、あまり細かいことは気にせず

「データベース検索の際のキーとなるカラムには適当にインデックスをつけておけばいいよなー」

程度に考えて CREATE INDEX ~ をしていました。
ところが、インデックスのつけかたにはいくつかの抑えておくべき点があったのです。

ここではいろいろ実験してみてわかったことを書いてみようと思います。

例題

2000×2000のランダムな行列をデータベースに格納し、要素にアクセスするような簡単な例題を考えてみます。
データベースは tbl というテーブルをもち、tbl は row, col, val という三つのカラムを持ちます。つまり

 row| col| val
  0|   0|  10
  0|   1|   3
  0|   2|   1

  …(中略)…

  0|1999|  80
  1|   0|  19

  …(中略)…

1999|1998|  10
1999|1999|   0

のようなデータベースです。この行列に対して3種類の操作を考えてみましょう:

  1. i 行目を取り出す
  2. j 列目を取り出す
  3. i 行 j 列の要素を取り出す

このときの SQL はそれぞれ

select val from tbl where row=i; /* Get row i : test1 */
select val from tbl where col=j; /* Get column j : test2 */
select val from tbl where row=i and col=j;  /* Get (i,j) : test3 */

となります。

インデックスの付け方によって各操作のアクセススピードは異なる

さて、上のようなデータベースには row, col カラムにインデックスを付ける必要があります(そうしないとパフォーマンスは極端に落ちる)。ところがインデックスのつけ方はひと通りではなく、しかも付け方によって各操作のパフォーマンスは異なります。ここでは4つのインデクスのつけ方を考えます。

create index idxr on tbl(row);
create index idxc on tbl(col);
create index idxm on tbl(row,col);
create index idxm on tbl(row,col);
create index idxc on tbl(col);
create index idxc on tbl(col);
create index idxm on tbl(row,col);

さてさて、これらの Type1~4 までのインデックスのつけ方が速度にどの程度影響するのか見てみましょう。テストプログラムは ruby で書きました(長いのでエントリーの一番最後に添付しておきます)。

結果は次のようになりました。注目すべきはカッコの中の数値(実時間)です。特別長い時間がかかった部分をハイライトしています。

[Test for type1]
                          user     system      total        real
row constraint:       0.360000   0.050000   0.410000 (  0.506123)
col constraint:       0.680000   0.350000   1.030000 ( 15.484355)
row-col constraint:   0.100000   0.350000   0.450000 ( 15.010290)

[Test for type2]
                          user     system      total        real
row constraint:       0.370000   0.050000   0.420000 (  0.506146)
col constraint:       6.420000   1.390000   7.810000 ( 48.931735)
row-col constraint:   0.000000   0.000000   0.000000 (  0.049576)

[Test for type3]
                          user     system      total        real
row constraint:       0.360000   0.060000   0.420000 (  0.510151)
col constraint:       0.410000   0.130000   0.540000 (  7.212111)
row-col constraint:   0.000000   0.010000   0.010000 (  0.034044)

[Test for type4]
                          user     system      total        real
row constraint:       0.360000   0.040000   0.400000 (  0.508709)
col constraint:       0.300000   0.110000   0.410000 (  7.210956)
row-col constraint:   0.000000   0.000000   0.000000 (  0.033352)

見にくいですね。グラフにしてみましょう。

SQLite3 access time comparison (unit: second)

だいぶわかりやすくなりました。さて、この結果からわかる事実をもとに考察してみます(私は SQLite が内部的にどのように動いているかは知らないので、あくまでも推測ということにご注意ください)。

グラフからわかる事実

  • 行の取得(青色:Test1)はどのインデックス付けでも高速
  • 列の取得(緑色:Test2)はどのインデックス付けでも低速、特に Type2(同時インデックスのみ)は最悪
  • 行列の成分取得(オレンジ色:Test3)は Type1 のインデックス(行、列に別のインデックス)のみ低速
  • インデックをつける順序には依存しない(Type3 & Type4)

考察(推察)

  • col に関する検索がいつも遅いのは row に比べて同じ col の値をもつレコードがHDD上のとびとびの位置に存在するため、HDD のヘッドの物理的なスピードがボトルネックになっている。
  • 同時インデックス付けをしないと AND 検索 (Test3) のときにパフォーマンスが出ない。
  • (a, b, c, …) という同時インデックスのみだと最初の要素 a についてはパフォーマンスが出るが、残りの b, c, … の検索のときにパフォーマンスが出ない。

実験に使った ruby スクリプト

初回の実行はデータベースを作成するため遅いです。ディスク容量は 1GB くらい必要です。

#!ruby
require 'sqlite3'
require 'benchmark'

def make_dummy_db dbname, size
  db=SQLite3::Database.new(dbname)
  db.execute("create table tbl (row integer, col integer, val integer);")
  db.transaction {
    sql = "insert into tbl values (?, ?, ?);"
    1.upto(size) { |i|
      1.upto(size) { |j|
        db.execute(sql, i, j, (rand()*100).floor)
      }
    }
  }
  db
end

def db_test db
  queries = [1,2,4,8,128,256,512,1024,1999]
  Benchmark.bmbm { |x|
    x.report("row constraint:"){
      a=0
      sql="select val from tbl where row=?;"
      for q in queries
        db.execute(sql,q){ |row|
          a+=row[0].to_i
        }
      end
    }
    x.report("col constraint:"){
      a=0
      sql="select val from tbl where col=?;"
      for q in queries
        db.execute(sql,q){ |row|
          a+=row[0].to_i
        }
      end
    }
    x.report("row-col constraint:"){
      a=0
      sql="select val from tbl where row=? and col=1024;"
      for q in queries
        db.execute(sql,q){ |row|
          a+=row[0].to_i
        }
      end
    }
  }
end

###############
# main routine
if( not File.exist?("type1.db") )
  db1 = make_dummy_db "type1.db", 2000
  db1.execute("create index idxr on tbl(row);")
  db1.execute("create index idxc on tbl(col);")
else
  db1 = SQLite3::Database.new("type1.db")
end
puts "[Test for type1]"
db_test db1
puts

if( not File.exist?("type2.db") )
  db2 = make_dummy_db "type2.db", 2000
  db2.execute("create index idxm on tbl(row,col);")
else
  db2 = SQLite3::Database.new("type2.db")
end
puts "[Test for type2]"
db_test db2
puts

if( not File.exist?("type3.db"))
  db3 = make_dummy_db "type3.db", 2000
  db3.execute("create index idxm on tbl(row,col);")
  db3.execute("create index idxc on tbl(col);")
else
  db3 = SQLite3::Database.new("type3.db")
end
puts "[Test for type3]"
db_test db3
puts

if( not File.exist?("type4.db"))
  db4 = make_dummy_db "type4.db", 2000
  db4.execute("create index idxc on tbl(col);")
  db4.execute("create index idxm on tbl(row,col);")
else
  db4 = SQLite3::Database.new("type4.db")
end
puts "[Test for type4]"
db_test db4
puts

まとめ

どうやら同時インデックスのみだと対応できない検索パターンが存在するようです。たくさんインデックスを張れば基本的にはあらゆる検索パターンに対応できるかもしれませんが、その分ファイルサイズも巨大になるので注意。あとはもっとも頻繁に使う検索パターンに最適化されたディスク上の配置を心がける、ということでしょうか。

はてなブックマーク - 【SQLite3】 ハイパフォーマンスなインデックスをつけるために覚えておくべきこと
Pocket