はじめに

データベースを真面目に勉強し始めました。

今回は気軽に使える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に以下を追加します。

build.gradle

repositories {
    jcenter()
}
dependencies {
    implementation 'org.jetbrains.kotlin:kotlin-stdlib-jdk8'
    implementation 'org.xerial:sqlite-jdbc:3.7.2'
}

今回は、日本橋付近のNodeを、緯度経度それぞれプラスマイナス0.0005度の範囲で検索をかけます。

検証に使用したソースコードがこちらです。

main.kt

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をそれぞれ

なし
lat
lon
lat, 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による依存性はあまりない

参考