2件の投稿件の投稿が「geometry」タグ付き

この記事では、既存の非効率な実装について議論し、それを改善するために試みた方法を記録します。

既存の問題点​

複数のデータベースに分散されたテーブルを単一のクエリで結合することは不可能ではなかったが、困難だった...

1. 特定の座標がエリア「a」に含まれているか？
2. テーブルが物理的に異なるサーバーに存在するため、結合クエリの記述が難しかった
   1. なぜ単一のクエリが必要なのか？クエリ対象のデータが大規模であるため、アプリケーションメモリに読み込む量を最小限に抑えたかったからです。
3. データベース結合が不可能だったため、アプリケーション結合が必要となり、約240億回のループ（60000 * 40000）が発生した
   1. パーティショニングによって処理時間は最小限に抑えられたが、ループによるCPU負荷は依然として高かった。
4. 物理的に異なるデータベースを1つに統合する移行プロセスを通じて、結合が可能になったため、クエリの最適化の機会が得られた。

アプローチ​

データベース結合ができなかった主な理由が解決されたため、ジオメトリ処理にインデックススキャンを活用することを積極的に検討しました。

• PostGISのGISTインデックスを使用すると、R-treeに似た空間インデックスを作成でき、インデックススキャンを通じて直接クエリが可能です。
• 空間インデックスを使用するには、ジオメトリ型のカラムが必要です。
• 緯度と経度の座標は利用可能でしたが、ジオメトリ型がなかったため、まず座標を使用してジオメトリPOINT値を作成する必要がありました。

このプロセスをシミュレートするために、本番DBと同じデータを用意し、実験を行いました。

まず、インデックスを作成しました：

CREATE INDEX idx_port_geom ON port USING GIST (geom);

次に、PostGISのcontains関数を実行しました：

SELECT *
FROM ais AS a
JOIN port AS p ON st_contains(p.geom, a.geom);

素晴らしい...

結果​

空間インデックス適用前​

1分47秒から2分30秒

空間インデックス適用後​

0.23ミリ秒から0.243ミリ秒

キャプチャは用意していませんが、インデックス適用前のクエリは1分30秒以上かかっていました。

結論から始めて、なぜこれらの結果が得られたのかを掘り下げていきましょう。

GiST（Generalized Search Tree）​

複雑なジオメトリデータのクエリに非常に有用なインデックスで、その内部構造は以下の通りです。

R-treeのアイデアは、平面を長方形に分割してすべてのインデックスされたポイントを包含することです。インデックス行は長方形を格納し、次のように定義できます：

"探しているポイントは指定された長方形の中にある。"

R-treeのルートには、いくつかの最大の長方形（交差することもある）が含まれます。子ノードには、親ノードに含まれる小さな長方形が含まれ、すべての基本ポイントを包含します。

理論的には、リーフノードにはインデックスされたポイントが含まれるべきですが、すべてのインデックス行は同じデータ型を持つ必要があるため、ポイントに縮小された長方形が繰り返し格納されます。

この構造を視覚化するために、R-treeの3つのレベルの画像を見てみましょう。ポイントは空港の座標を表しています。

レベル1：2つの大きな交差する長方形が見えます。

2つの交差する長方形が表示されています。

レベル2：大きな長方形が小さなエリアに分割されています。

大きな長方形が小さなエリアに分割されています。

レベル3：各長方形には1つのインデックスページに収まるだけのポイントが含まれています。

各長方形には1つのインデックスページに収まるポイントが含まれています。

これらのエリアはツリー構造になっており、クエリ中にスキャンされます。詳細な情報については、次の記事を参照することをお勧めします。

結論​

この記事では、具体的な条件、遭遇した問題、それを解決するために行った努力、およびこれらの問題に対処するために必要な基本概念を簡単に紹介しました。要約すると：

• 物理的に分離されたデータベースでは、インデックスを使用した効率的な結合ができなかった。
• 移行によって物理的な結合が可能になり、パフォーマンスが大幅に向上した。
• インデックススキャンを活用することで、全体的なパフォーマンスが大幅に向上した。
• アプリケーションメモリにデータを不必要に読み込む必要がなくなった。
• ループによるCPU負荷が軽減された。

参考文献​

• 空間インデックス
• https://dbknowledge.tistory.com/48
• https://medium.com/postgres-professional/indexes-in-postgresql-5-gist-86e19781b5db

背景​

画像の参照¹

地球が平らでも完全な球体でもなく、不規則な楕円体であることを考えると、異なる経度と緯度の2点間の距離を迅速かつ正確に計算するための完璧な公式は存在しません。

しかし、geotoolsライブラリを使用することで、数学的に補正された近似値を簡単に取得することができます。

依存関係の追加​

geotoolsで地球の楕円体を使用するには、関連するライブラリの依存関係を追加する必要があります。

repositories {
    maven { url "https://repo.osgeo.org/repository/release/" }
    maven { url "https://download.osgeo.org/webdav/geotools/" }
    mavenCentral()
}

dependencies {
    ...
    implementation 'org.geotools:gt-referencing:26.2'
    ...
}

コードの記述​

まず、ソウルと釜山の座標をenumクラスとして定義します。

enum class City(val latitude: Double, val longitude: Double) {
    SEOUL(37.5642135, 127.0016985),
    BUSAN(35.1104, 129.0431);
}

次に、テストコードを通じて簡単な使用例を見てみましょう。

class EllipsoidTest {

    @Test
    internal fun createEllipsoid() {
        val ellipsoid = DefaultEllipsoid.WGS84  // GPSで使用されるWGS84測地系を使用して、地球に最も近い楕円体を作成

        val isSphere = ellipsoid.isSphere  // 球体か楕円体かを判定
        val semiMajorAxis = ellipsoid.semiMajorAxis  // 赤道半径、楕円体の長い半径
        val semiMinorAxis = ellipsoid.semiMinorAxis  // 極半径、楕円体の短い半径
        val eccentricity = ellipsoid.eccentricity  // 離心率、楕円体が球体にどれだけ近いかを示す
        val inverseFlattening = ellipsoid.inverseFlattening  // 逆扁平率の値
        val ivfDefinitive = ellipsoid.isIvfDefinitive // この楕円体に対して逆扁平率が決定的かどうかを示す

        // 大円距離
        val orthodromicDistance = ellipsoid.orthodromicDistance(
            City.SEOUL.longitude,
            City.SEOUL.latitude,
            City.BUSAN.longitude,
            City.BUSAN.latitude
        )

        println("isSphere = $isSphere")
        println("semiMajorAxis = $semiMajorAxis")
        println("semiMinorAxis = $semiMinorAxis")
        println("eccentricity = $eccentricity")
        println("inverseFlattening = $inverseFlattening")
        println("ivfDefinitive = $ivfDefinitive")
        println("orthodromicDistance = $orthodromicDistance")
    }
}

isSphere = false
semiMajorAxis = 6378137.0
semiMinorAxis = 6356752.314245179
eccentricity = 0.08181919084262128
inverseFlattening = 298.257223563
ivfDefinitive = true
orthodromicDistance = 328199.9794919944

DefaultEllipsoid.WGS84を使用して地球の楕円体を作成できます。WGS84の代わりにSPHEREを使用すると、半径6371kmの球体が作成されます。

距離の結果はメートル（m）で表示されるため、キロメートルに変換すると約328kmになります。Googleで検索すると325kmと表示されるかもしれませんが、私が選んだ座標とGoogleが選んだ座標の違いを考慮すると、これは悪くない数字です。

他にも多くの機能がありますが、すべてをこの投稿でカバーするのは難しいため、必要に応じて別の投稿で取り上げます。