まわれるクエリによるPostGIS低速化の検討 #PostGIS

こんにちは。
今日のぶん、誰も手をあげないからつい出来心で。
記事タイトルで遊んだのでもう満足です。サンキュrutaさん!
したがってここから下に内容はないよぅ。

…すいませんすいません

おん祭りの行列は市内を左にくるりと回る

さて、きょうは春日若宮おん祭りの宵宮祭ですね。これをお読みのみなさんも明日のお渡り式に参加されることと思いますが、万一ご存じない方のためにどんなイベントかお話しておくと、明日はお馬やお侍さん、芸能民のみなさんが、若宮様の別荘にむけて奈良市中心部をぐるっと左回りに練り歩く、いわば県民とシカのクリスマスです。楽しいですよ。めっちゃ寒いけど。

ところで左回りって？

自分の右手と左手の区別ができるかすらあやしかったご近所でも評判のあほな子供のころ、おじいちゃんが「ひらがなの「ひ」の字を書く方向が左まわり、ひらがなの「み」の方向が右まわり」と教えてくれました。これならあほの子でもひらがなを忘れない限り忘れません。ヤッタネ日本語超便利！
では英語圏ではどうでしょうか。

英語で右回り左回りを表現するのに右手ルール、左手ルールって言い方があります。ここで強引にGISの話に寄せると、GIS的なポリゴンをつくるには、ポリゴンを構成する点を左巻きに並べても右巻きに並べても作れますが、ときどき回る向きをどちらかに統一したいことがあります。
PostGISには、点の並びを左回りに揃えるための関数ST_ForceLHR()ってのがあります。関数名の後ろの"LHR"ってのは何かというと「Left Hand Rule(左手ルール)」の略で、線のふちを歩いてポリゴンをくるりと一周したとき、左手があるほうが内側になる方向、てのが定義だそうです(´-ω-`)？
はるか昔に学校で習ったフレミングの「Left Hand Rule（左手の法則）」は、指を右回りにひねるんじゃなかったっけ？
わっけわかんねー

結局混乱するのはpoor japaneseだけじゃなかったようで、この秋にリリースされたPostGIS2.4からはST_ForceLHR()関数はST_ForcePolygonCCW()というわかりやすい名前に改名しました。"CCW" は「Counter ClockWise（反時計回り）」の略で、これなら間違えようがありません。右回り（時計回り）はST_ForcePolygonCW()です。
晴れて英語圏の人も右回りと左回りの違いがわかるようになりました。

清く正しい回転方向

さきほど、ポリゴンには点を左巻きに並べるやり方と右巻きに並べるやり方があるって言いました。実際、多くのGISツールはどっち向きで食わせてもだいたいよしなに扱ってくれます。とはいえ右回りが正か左回りが正かをはっきり仕様で決めとかないと、たとえば赤道の線をポリゴン化した場合にそれが北半球ポリゴンなのか南半球ポリゴンなのかの区別がつかなくって困ります。
実際の規格をみてみます。地理情報交換ではいまやデファクトスタンダードであろうGeoJSON、RFC-7946 の定義では、

3.1.6. Polygon
～略～
A linear ring MUST follow the right-hand rule with respect to the
area it bounds, i.e., exterior rings are counterclockwise, and
holes are clockwise.

なになに？right-hand rule は counterclockwise なの？？？わかんないやー（困惑）

試しに右巻き左巻きそれぞれのポリゴンをGeoJSON lint に食わせてみる。

右巻き：{"type":"Polygon","coordinates":[[[135,35],[136,36],[136,35],[135,35]]]}

左巻き：{"type":"Polygon","coordinates":[[[135,35],[136,35],[136,36],[135,35]]]}

GeoJSONの定義では左回りが正しい。間違いない。Geojsonlint.comもそういってる。
他の規格や製品はどうか。OGC Simple Feature では、

The exterior boundary LinearRing defines the “top” of the surface
which is the side of the surface from which the exterior boundary
appears to traverse the boundary in a counter clockwise direction.

このほか、SQL Server の Geography型も懐かしのKMLも WebGLも、若宮おん祭りの行列ですらみんな左回りをvalidとしてます（めんどくさいんで規格原文は各自で探してください）。もはや右回り勢力はいにしえのレガシーな ESRI Shape ファイル程度です。
地理データの世界ではいまや左巻きがジャスティスです。

ポリゴンを清く正しくしてみる

左回りが覇権、って現実を理解できたところで、おもむろにポリゴンを右まわり左まわりそれぞれに統一するクエリを実行して、処理時間を測ってみます。

-- クエリ元データとして,右巻き左巻き両方で同じ形状を作る。10万ポイントのポリゴン。
insert into wkpoly (geom) select st_multi(st_forcepolygonccw(st_buffer(ST_SetSRID(ST_MakePoint(135.0, 35.0),4326),0.1, 250000)));
insert into wkpoly (geom) select st_multi(st_forcepolygoncw( st_buffer(ST_SetSRID(ST_MakePoint(135.0, 35.0),4326),0.1, 250000)));
explain analyze select geom from wkpoly; -- 念のため空読み
-- 右巻き左巻きを交互に取り出して所要時間計測
explain analyze select st_forcepolygoncw(geom) from wkpoly;
explain analyze select st_forcepolygonccw(geom) from wkpoly;

各方向１０回（少なっ！）計測した結果は↓こんな感じ。

うーん・・・
左回りおっそｗｗｗ

結論

PostGISで速さを追求するときは左巻きは避ける方向で。
標準違反上等、規格は投げ捨てるもの。ルールに縛られずにのびのびと生きましょう。

では、おん祭りで会いましょう！

.
.
.
.
.
.

以下、本当に読む必要のない蛇足（速度差の原因）：
理由はかんたん。クエリが教えてくれたもの。

# select prosrc from pg_proc where proname = 'st_forcepolygoncw';
           prosrc
-----------------------------
 LWGEOM_force_clockwise_poly

# select prosrc from pg_proc where proname = 'st_forcepolygonccw';
                          prosrc
----------------------------------------------------------
  SELECT public.ST_Reverse(public.ST_ForcePolygonCW($1))

lwgeom.cとか見る限りポリゴンの裏表を面積の正負で判断して必要に応じて時計回りに揃えてるだけのコードっぽいので力技で改善するのは難しくはなさそうです。そこでこのAdvent Calendarの流れですよ。ディープラーニングだのライブラリ作りましただのクリスマスの雪だるまも砕け散りそうな暑苦しさです。「改善のプルリク出しました」ぐらい書いてると思うじゃないですか。しかし世の中そんなに甘くはありません。諸般の事情（＝豆腐メンタル）のためムリっす。
真面目に補足すると、リアルワールドのユースケースだとポリゴンの方向の差が応答時間の決定的な差にはならないことを教えられて終わりになる未来がみえるよララァ