73095


フレームワーク側で緯度経度を配列で持っていて  
そこから住所情報を取得したいです

まず [国土地理院のサイト](https://nlftp.mlit.go.jp/isj/index.html)
に国内の市区町村レベルの代表点のデータがあったので  
CSVをダウンロードしてテーブルを作りました

geo という geometry point 型カラムと  
address 情報の string カラム  
２カラムのテーブルを作り geo にはインデックスを貼りました

以下のような定数座標との距離でソートして１個目を取り出すようなクエリを投げたのですが  
結果が返ってくるのに数十秒かかってしまいます

[code]

    SELECT address FROM tests
    ORDER BY st_Distance(ST_GeomFromText('POINT(139.7 35.69)'),geo)
    LIMIT 1;
              address
    ---------------------------
     東京都新宿区西新宿一丁目1
    (1 row)
    
    Time: 58566.859 ms (00:58.567)
    
[/code]

次に where 文で距離が 1km 以内のものに絞ってからソートを行うと一瞬で結果が返ってきます

[code]

    SELECT address FROM tests
    WHERE st_Dwithin(ST_GeomFromText('POINT(139.7 35.69)'),geo,1000)
    ORDER BY st_Distance(ST_GeomFromText('POINT(139.7 35.69)'),geo)
    LIMIT 1;
              address
    ---------------------------
     東京都新宿区西新宿一丁目1
    (1 row)
    
    Time: 12.073 ms
    
[/code]

理由はおそらく st_Dwithin にはインデックスが効いているのに対して  
st_Distance を取ってしまった小数値にはインデックスが効かないために  
その値で全国市区町村数の膨大なデータ数でソートしてしまうせいかと思っています

ただ距離で絞るにしても全国で一番大きな市区町村サイズで絞らなければならず  
その値が分からないので困っています

st_Distanceを取った後の中間テーブルのカラムに  
インデックスを貼ることができればいいのですが  
そのようなことってできないでしょうか

他にも何かいいクエリ方法はないでしょうか

* * *

最小値が欲しいだけなのにソートでO(n・logn)かけてから１個だけ取得と言うのが無駄な気がして  
サブクエリで最小距離を計算(O(n)?) → 最小距離でフィルタ(インデックスがきくはず)  
と言うロジックも試してみたんですが多少早くなりましたがやはり取得に数十秒かかってしまいます

[code]

    SELECT address FROM (
      SELECT MIN(st_Distance(ST_GeomFromText('POINT(139.7 35.69)'),geo)) AS d 
      FROM tests
    ) AS tmp
    JOIN tests ON st_Dwithin(ST_GeomFromText('POINT(139.7 35.69)'),geo,d)
              address
    ---------------------------
     東京都新宿区西新宿一丁目1
    (1 row)
    
    Time: 47973.601 ms (00:47.974)
    
[/code]

サブクエリの

[code]

    SELECT MIN(st_Distance(ST_GeomFromText('POINT(139.7 35.69)'),geo)) AS d FROM tests
          d
    -------------
     72.04043634
    (1 row)
    
    Time: 48631.504 ms (00:48.632)
    
[/code]

これだけを実行しても同じぐらいの時間がかかってしまいます

一番近いレコードを取得したいと言うのは割とよくやりそうなことだと思うんですが  
決めうちで範囲制限する以外にインデックスを効かせる方法は存在しないんでしょうか

* * *

なんとなく GIS データを扱うのに postgreSQL がいいのかなと思って選択しましたが  
やりたいことは緯度経度から住所が引きたいだけなので  
他に適したデータベースシステムがあれば教えていただけるとありがたいです


CC BY-SA 4.0
2020-10-15T12:14:29.590
71228
2021-01-05T10:49:04.823
2020-10-16T03:18:04.150
question
sql postgresql
SQLで高速に近傍検索をしたい


[ボロノイセル](https://ja.wikipedia.org/wiki/%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3)のポリゴンを格納するカラムを用意して事前に計算しておけば、任意の座標に対する最近点の探索は座標が含まれるポリゴンの検索に置き換えることができます。(元のデータ量で現実的かどうかはわかりません)

いきなり細かいデータでやるのではなく、都道府県→市町村、のように絞り込む方法も考えられます。

または[Google Geocoding
API](https://developers.google.com/maps/documentation/geocoding/overview)のような外部のサービスを利用する手もあります。

* * *

インデックスというのは「使えばクエリが速くなる魔法」ではなく単なる「事前に作っておいた索引」です。本の索引で考えてみると、

> 理由はおそらく st_Dwithin にはインデックスが効いているのに対して st_Distance  
>  を取ってしまった小数値にはインデックスが効かないために

任意に指定される文字位置で項目を検索しようとしているようなものです。それに使える索引はありません。3番目の文字を基準にした索引を作っておけばパラメータが「3文字目」の時には役に立ちますが、ほかのパラメータには対応できません。

> st_Distanceを取った後の中間テーブルのカラムにインデックスを貼ることができればいいのですがそのようなことってできないでしょうか

文字位置が指定されたらそれに対応する索引を作って検索する、というような話です。コストがかかる場所が移動するだけで無意味です。


CC BY-SA 4.0
2020-10-18T08:10:06.790
71303
2020-10-18T08:10:06.790
5793
71228
answer


調べてみたところ、postgresql は標準で二次元データを扱うことが出来、また、GiSTインデックスというもので二次元座標の近傍検索を行えるようです。  
（具体的な実装はR木? 勉強不足で詳細不明）

[code]

    -- 作成
    create table address_locations (address text, location point);
    create index ix_location on address_locations using gist(location);
    
    insert into address_locations(address, location)
    values('北海道札幌市中央区旭ケ丘一丁目', point(141.319722, 43.042230));
    ...
    
[/code]

[code]

    -- 検索
    select * from address_locations
    order by location <-> point(139.7,35.69)
    limit 10;
    
[/code]

[code]

    -- プラン
    -- インデックスが使用されていることの確認
    explain select * from address_locations
    order by location <-> point(139.7,35.69)
    limit 10;
                                                   QUERY PLAN
    ---------------------------------------------------------------------------------------------------------
     Limit  (cost=0.42..1.40 rows=10 width=61)
       ->  Index Scan using ix_location on address_locations  (cost=0.42..1874508.42 rows=19001600 width=61)
             Order By: (location <-> '(139.7,35.69)'::point)
    (3 rows)
    
[/code]

私の環境で約2000万件のエントリからインデックスなしで1,300ms、インデックスありで 1.0ms未満で上位10件を取得することが出来ました。  
インデックスをデータ挿入後に作成した場合、作成には3分ほどかかりました。

* * *

メルカトル図法の図上で計算するような方法になっていて、正確な近傍点ではないことがあり得るので注意してください。  
経度に0.8倍した値を入れたりすると少しは改善すると思います。  
厳密な近傍点を取得したい場合、まず上記の方法で近傍点への距離を取得し、いくらかのマージンを掛け算した上でそれ以内にフィルタし、最後に厳密な距離を計算してソートする、という方法が考えられます。


CC BY-SA 4.0
2021-01-05T10:49:04.823
73095
2021-01-05T10:49:04.823
20885
71228
answer