はじめに
データベースを真面目に勉強し始めました。
今回は気軽に使えるSQLiteを用いて、indexを作った時の浮動点小数型の検索速度について検証を行いましたので、結果を掲載いたします。
前提
今回はOpenStreetMapのデータをParseしてSQLite DBに突っ込んだものを用意しました。
使用するデータは、ある地点のIDを示した型のNodeと、そのNodeに対応する緯度経度(Double型)lat,lonをDBに入れました。Table名はnodesです。
create table nodes into (node integer primary key, lat real, lon real);
このDBに対し、緯度経度をNodeに変換するための検索をかけます。使用領域は関東地方に限定しました。レコード数を数えると
select count(*) from nodes;
30097243
30097243です
使用言語はKotlin 1.3.61で、データベースAPIはJDBC 3.7.2を使用します。開発環境はIntelliJ IDEA 2019.3.1です。また、実行環境はSurface Pro 5(Core i7-7660U (2.50 GHz), メモリ16 GB, SSD SAMSUNG KUS040202M-B000)です。
下準備
結果のみ知りたい方は次のセクションまで読み飛ばしてください。
sqlite:JDBCを使えるようにするため、Projectのbuild.gradleに以下を追加します。
repositories {
jcenter()
}
dependencies {
implementation 'org.jetbrains.kotlin:kotlin-stdlib-jdk8'
implementation 'org.xerial:sqlite-jdbc:3.7.2'
}
今回は、日本橋付近のNodeを、緯度経度それぞれプラスマイナス0.0005度の範囲で検索をかけます。
検証に使用したソースコードがこちらです。
fun main() {
val time = measureTimeMillis {
val lat = 35.68
val lon = 139.77
val err = 0.0005
Class.forName("org.sqlite.JDBC")
val url = "jdbc:sqlite:(DBのディレクトリ)\\node-kanto.db"
val connection = DriverManager.getConnection(url)
val sql = "select * from nodes where lat > ? and lat < ? and lon > ? and lon < ? order by lat,lon"
val preparedStatement = connection.prepareStatement(sql)
with(preparedStatement) {
setDouble(1, lat - err)
setDouble(2, lat + err)
setDouble(3, lon - err)
setDouble(4, lon + err)
}
val result = preparedStatement.executeQuery()
while (result.next()) {
println("node = ${result.getLong("node")}, lat = ${result.getDouble("lat")}, lon = ${result.getDouble("lon")}")
}
preparedStatement.close()
connection.close()
}
println("Time Cost = $time ms")
}
SQL文にて、緯度経度それぞれにて検索元の値 $L$ とDBにある値 $l_i$ との差が $\varepsilon = 0.0005$ となるように、つまり
|L-l_i| < \varepsilon
となるようにwhere文を書きました。
また、時間の計測には
https://maku77.github.io/kotlin/misc/measure-time.html
を参考にさせていただきました。
実験
このプログラムを
- indexなし
-
latのみのindex -
latとlon両方のindex
の三通りで試してみました。また、ORDER BYをそれぞれ
- なし
latlonlat, lon
の4通りで検証してみました。
これらを3回計算させ、平均値を取ります。
結果
indexなし
この時のDBのデータ容量は 982.794 MBでした。
| ORDER BY | 3回の平均(ms) |
|---|---|
| なし | 7265 |
| lat | 7159 |
| lon | 7226 |
| lat,lon | 7228 |
緯度のみの1次元index
緯度latの1次元indexを
create index lat_index on nodes (lat);
として作りました。
この時のDBのデータ容量は 1,561.648 MBでした。
| ORDER BY | 3回の平均(ms) |
|---|---|
| なし | 279 |
| lat | 286 |
| lon | 292 |
| lat,lon | 257 |
緯度経度の2次元index
緯度経度lat, lonの2次元indexを
create index latlon_index on nodes (lat, lon);
として作りました。
この時のDBのデータ容量は 1,835.961 MBでした。
| ORDER BY | 3回の平均(ms) |
|---|---|
| なし | 174 |
| lat | 157 |
| lon | 171 |
| lat,lon | 159 |
(おまけ)Primary keyであるNodeから緯度経度を求める速さ
select * from nodes where node = ?;
として、ある程度Nodeの値をバラけさせた3点での速さを見てみます。
| Node | 3回の平均(ms) |
|---|---|
| 256,389,161 | 146 |
| 1,304,353,022 | 123 |
| 6,539,506,106 | 142 |
まとめ
- 1次元Indexを作るとDBのサイズは元の1.59倍になるが、速度は約26倍向上した。
- 2次元Indexを作るとDBのサイズは元の1.87倍になるが、速度は約41倍向上した。
- 2次元Indexまで作ると、Primary keyでの検索と遜色ない速度になる
-
ORDER BYによる依存性はあまりない