4

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

まず 国土地理院のサイト に国内の市区町村レベルの代表点のデータがあったので
CSVをダウンロードしてテーブルを作りました

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

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

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)

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

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

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

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

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

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


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

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)

サブクエリの

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)

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

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


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

2
  • 元データは何行ほどですか?約20万件で別の方法で試したところ20~30msで返ってきました
    – v..snow
    Commented 2020年12月25日 11:39
  • 1900 万ぐらいありました
    – user35303
    Commented 2021年1月5日 8:18

2 件の回答 2

2

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

-- 作成
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));
...
-- 検索
select * from address_locations
order by location <-> point(139.7,35.69)
limit 10;
-- プラン
-- インデックスが使用されていることの確認
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)

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


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

0

ボロノイセルのポリゴンを格納するカラムを用意して事前に計算しておけば、任意の座標に対する最近点の探索は座標が含まれるポリゴンの検索に置き換えることができます。(元のデータ量で現実的かどうかはわかりません)

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

またはGoogle Geocoding APIのような外部のサービスを利用する手もあります。


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

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

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

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

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

2
  • > ボロノイセル 調べたんですがnlognソートでさえかなり時間かかるので n2乗オーダーかかるデータ加工がまともな時間で終わるとは思えないですし、ポリゴンを持つということは頂点数分のデータを保持するのでテーブルサイズも膨れ上がりますよね…
    – user35303
    Commented 2020年10月23日 2:05
  • 代表点のデータだけでは近傍検索するのは不可能ということみたいなので、初めからポリゴンデータをインポートすることにしました。ポリゴンデータの方は丁目までのデータしか見つからず番地までのものが見つからなかったんですが仕方ないですね… できないことが分かっただけで、クエリを試行錯誤する時間の無駄が省けて別のアプローチに移行できるので助かりました
    – user35303
    Commented 2020年10月23日 2:08

この質問に回答するには、ログインする必要があります。