SQLiteの多次元indexによるREAL型の検索速度の検証

# はじめに

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

今回は気軽に使えるSQLiteを用いて、indexを作った時の浮動点小数型の検索速度について検証を行いましたので、結果を掲載いたします。

# 前提

今回は[OpenStreetMap](https://www.openstreetmap.org)のデータをParseしてSQLite DBに突っ込んだものを用意しました。
使用するデータは、ある地点のIDを示した型の`Node`と、その`Node`に対応する緯度経度(Double型)`lat`,`lon`をDBに入れました。Table名は`nodes`です。

```sql
create table nodes into (node integer primary key, lat real, lon real);
```
このDBに対し、緯度経度を`Node`に変換するための検索をかけます。使用領域は関東地方に限定しました。レコード数を数えると

```sql
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)です。

# 下準備
結果のみ知りたい方は[次のセクション](https://qiita.com/drafts/372ef22354d187e2df82/edit#%E7%B5%90%E6%9E%9C)まで読み飛ばしてください。

`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$ となるように、つまり

```math
|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を

```sql
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を

```sql
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から緯度経度を求める速さ

```sql
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`による依存性はあまりない

# 参考

- https://www.dbonline.jp/sqlite/select/index3.html
- http://itdoc.hitachi.co.jp/manuals/3000/30003F5500/EEXD0043.HTM
- https://www.javadrive.jp/servlet/database/index6.html
- https://www.javadrive.jp/servlet/database/index6.html