GIS PostGIS 重なり判定の高速化

目次

FrontPage
・Windows11
・Chromebook
・Random
・機械学習
・さくらVPS
・Fedora13
・SuSe10
・Docker
・Ansible
・Java
・Scala
・Python
・Ruby
・Lisp
・Computer
・GIS
・HTML
・Culture
・Link

訪問者

total: 12670
today: 1
yesterday: 1
now: 1

更新

最新の10件

人気の10件

MenuBar

実行環境 †

• データ : GIS PostGIS で Natural Earth からダウンロードした国データ
• マシン : Mac Book (Core2 2.4GHz / 8GB RAM / 240GB SSD)
• Posgtresql 9.2 + Postgis 2.1 (Mac Ports)
• geom 列には index を設定済み

"ST_Distance(a,b) = 0" 超遅い †

• ポリゴン同士の厳密な衝突判定では、ST_Distance(a,b) = 0 で a と b との距離を計算して、距離が 0 なら衝突していると判定できる
• ところがめっちゃ遅い

  demo=# \timing
  Timing is on.
  
  demo=# SELECT b.sovereignt FROM countries_table a, countries_table b 
  demo=# WHERE a.sovereignt = 'Brazil' AND ST_Distance(a.geom, b.geom) = 0;
   sovereignt
  ------------
   Argentina
   Bolivia
   Brazil
   Colombia
   France
   Guyana
   Peru
   Paraguay
   Suriname
   Uruguay
   Venezuela
  (11 rows)
  
  Time: 48905.483 ms
  

"a && b" 超早い †

• "&&" 演算子は、ポリゴン a と b を囲む矩形 (Bounding Box) 同士の比較
• 超速い

  demo=# SELECT b.sovereignt FROM countries_table a, countries_table b 
  demo=# WHERE a.sovereignt = 'Brazil' AND (a.geom && b.geom);
          sovereignt
  --------------------------
   Argentina
   Bolivia
   Brazil
   Chile
   Colombia
   Fiji
   France
   Guyana
   Kiribati
   New Zealand
   Peru
   Paraguay
   Suriname
   United States of America
   Uruguay
   Venezuela
  (16 rows)
  
  Time: 1.314 ms
  

• 超速い代わりに、厳密比較と結果が違う
• 矩形同士の比較のため

"a && b" で絞り込んでから "ST_Distance(a,b) = 0" をやる †

• 2倍くらい早くなった

  demo=# SELECT b.sovereignt FROM countries_table a, countries_table b
  demo=# WHERE a.sovereignt = 'Brazil' AND (a.geom && b.geom) AND ST_Distance(a.geom, b.geom) = 0;
   sovereignt
  ------------
   Argentina
   Bolivia
   Brazil
   Colombia
   France
   Guyana
   Peru
   Paraguay
   Suriname
   Uruguay
   Venezuela
  (11 rows)
  
  Time: 22130.168 ms
  

まとめ †

検索の実行順を厳密に指定したら、もうちょっと速くならない ? → ならなかった †

demo=# SELECT b.sovereignt
demo-# FROM
demo-#   (
demo(#     SELECT t.geom AS geom
demo(#     FROM countries_table t
demo(#     WHERE t.sovereignt = 'Brazil'
demo(#   ) a,
demo-#   (
demo(#     SELECT q.sovereignt AS sovereignt, q.geom AS geom
demo(#     FROM countries_table p, countries_table q
demo(#     WHERE p.sovereignt = 'Brazil' AND (p.geom && q.geom)
demo(#   ) b
demo-# WHERE ST_Distance(a.geom, b.geom) = 0;
 sovereignt
------------
 Argentina
 Bolivia
 Brazil
 Colombia
 France
 Guyana
 Peru
 Paraguay
 Suriname
 Uruguay
 Venezuela
(11 rows)

Time: 22210.620 ms

• 速くならなかった
• Postgresql は、副問い合なんか使わなくても、意図したとおりに WHERE 句を実行してくれていたようだ

関数化する †

絞り込んでから距離の比較を関数化する †

CREATE FUNCTION ST_MyOverlap(a GEOMETRY, b GEOMETRY) RETURNS BOOLEAN AS $$
  BEGIN
    RETURN (a && b) AND ST_Distance(a, b) = 0;
  END;
$$ LANGUAGE plpgsql;

• 実行結果

  demo=# SELECT b.sovereignt from countries_table a, countries_table b
  demo=# WHERE a.sovereignt = 'Brazil' AND ST_MyOverlap(a.geom, b.geom);
   sovereignt
  ------------
   Argentina
   Bolivia
   Brazil
   Colombia
   France
   Guyana
   Peru
   Paraguay
   Suriname
   Uruguay
   Venezuela
  (11 rows)
  
  Time: 22233.657 ms
  

• 同じ結果、同じスピードで動いた

"&&" を関数化する1 (ちょっとだめ) †

CREATE FUNCTION ST_MyBoundingBoxOverlap(a GEOMETRY, b GEOMETRY) RETURNS BOOLEAN AS $$
  BEGIN
    RETURN (a && b);
  END;
$$ LANGUAGE plpgsql;

• JavaEE 7 / JPA 2.1 の JPQL からは、"&&" を使えない
• JPA 2.1 は、FUNCTION 句で、RDB 組み込みの関数を使えるので WHERE function( 'ST_MyBoundigBoxOverlap?', m.geom, :area ) で、"&&" を実行できる
• 実行結果

  demo=# SELECT b.sovereignt from countries_table a, countries_table b
  demo=# WHERE a.sovereignt = 'Brazil' AND ST_MyBoundingBoxOverlap(a.geom, b.geom);
          sovereignt
  --------------------------
   Argentina
   Bolivia
   Brazil
   Chile
   Colombia
   Fiji
   France
   Guyana
   Kiribati
   New Zealand
   Peru
   Paraguay
   Suriname
   United States of America
   Uruguay
   Venezuela
  (16 rows)
  
  Time: 31.893 ms
  

  • "&&" よりも 30 倍くらい遅い
  • さすがに "&&" が速すぎて、plpgsql の呼び出しがボトルネックになっている
  • 再挑戦

"&&" を関数化する2 (うまくいった) †

CREATE OR REPLACE FUNCTION ST_MyBoundingBoxOverlap(GEOMETRY, GEOMETRY) RETURNS BOOLEAN AS $$
  SELECT $1 && $2
$$ LANGUAGE SQL;

• JavaEE 7 / JPA 2.1 の JPQL からは、"&&" を使えない
• JPA 2.1 は、FUNCTION 句で、RDB 組み込みの関数を使えるので WHERE function( 'ST_MyBoundigBoxOverlap?', m.geom, :area ) で、"&&" を実行できる
• 実行結果

  demo=# SELECT b.sovereignt from countries_table a, countries_table b
  demo=# WHERE a.sovereignt = 'Brazil' AND ST_MyBoundingBoxOverlap(a.geom, b.geom);
          sovereignt
  --------------------------
   Argentina
   Bolivia
   Brazil
   Chile
   Colombia
   Fiji
   France
   Guyana
   Kiribati
   New Zealand
   Peru
   Paraguay
   Suriname
   United States of America
   Uruguay
   Venezuela
  (16 rows)
  
  Time: 1.591 ms
  

  • "&&" とほぼ同じ好了
• ST_MyOverlap? も plpgsql ではなく SQL でやったほうがいいかもね

考察 †

• geom の index は、矩形の B木になっている。つまり、矩形同士の比較演算 && は、B木をたどるだけで行える。数値演算はしなくていい → めちゃ速
• ST_Distance(a, b) は、a と b の頂点同士の距離を順列組み合わせで全て求めて、そのなかから最小のものを選ぶ → めちゃ遅
• めちゃ速の && で絞り込んでから、怪しそうな geom らだけ、めちゃ遅の ST_Distance(a, b) で厳密な比較をすると、計算量が半分くらいになる。

GIS