２次元座標の距離のSQL

遅いっていって見せてもらったSQLがSQL1のもの、
(px,py)からの距離がdistanceの間にあるものを近場から最大100件表示するって言うもの。
Where区が列の計算式となっているためインデックスが聞かない。
距離を測るには、いきなり範囲円内で比較するのではなく、対称点を中心とした正方形の範囲内でまず絞ってから、次に範囲円内にあるかを調べたほうがいいんじゃないかなという記事です。
（ちなみに、3次元なら立方体→球ってな感じで。）


まずは、テーブル準備。こんな感じなテーブルにして見ます。

CREATE TABLE GeoData(
Id int IDENTITY(1,1) NOT NULL,
Name nchar(10) NULL,
X real NOT NULL,
Y real NOT NULL,
CONSTRAINT PK_GeoData
PRIMARY KEY CLUSTERED ( Id ASC) ON PRIMARY)
ON PRIMARY

で、テーブルデータ投入。満遍なく10万の点を投入したあと、x座標が300～310の範囲に満遍なく10万の点を投入し、最後にy座標が300～310の範囲に満遍なく10万の点を投入してみる。

declare @i as int
set @i=0
while @i < 100000
begin
insert GeoData(Name,X,Y)values(@i,rand()*10000,rand()*10000)
set @i=@i+1
end

set @i=0
while @i < 100000
begin
insert GeoData(Name,X,Y)values(@i,300+rand()*10,rand()*10000)
set @i=@i+1
end
while @i < 100000
begin
insert GeoData(Name,X,Y)values(@i,rand()*10000,300+rand()*10)
set @i=@i+1
end

このテーブルにインデックスをはります。

create index GeoData_X on GeoData(X)
create index GeoData_Y on GeoData(Y)


このテーブルについて、結果が同じSQL3つ(SQL1:元のSQL,SQL2:高速化を期待して作ったSQL文,SQL3:SQL2について最適なインデックスを使うように、毎回実行プランを再作成することを指定したSQL文。

流すSQLはこんな感じ。
DECLARE @SQL1 nvarchar(MAX),@SQL2 nvarchar(MAX),@SQL3 nvarchar(MAX),@ParmDefinition nvarchar(MAX)
SET @ParmDefinition = N'@px real,@py real,@distance real'

SET @SQL1 =N'select top(100) Id,Name,X,Y,distance from
(select Id,Name,X,Y,SQRT(SQUARE(X-@px)+SQUARE(Y-@py)) as distance
from GeoData) as Tab where distance< @distance
order by distance'

SET @SQL2 =N'select top(100) Id,Name,X,Y,SQRT(distance2) as distance from
(select Id,Name,X,Y,(X-@px)*(X-@px)+(Y-@py)*(Y-@py) as distance2
from GeoData where X > @px-@distance and X < @px + @distance
and Y > @py-@distance and Y < @py + @distance ) as Tab where distance2< @distance*@distance
order by distance'

SET @SQL3 = @SQL2 + N' option(recompile)'


exec sp_executesql @SQL1,@ParmDefinition,1000,1000,150
exec sp_executesql @SQL2,@ParmDefinition,1000,1000,150
exec sp_executesql @SQL3,@ParmDefinition,1000,1000,150

exec sp_executesql @SQL1,@ParmDefinition,305,1000,10
exec sp_executesql @SQL2,@ParmDefinition,305,1000,10
exec sp_executesql @SQL3,@ParmDefinition,305,1000,10

exec sp_executesql @SQL1,@ParmDefinition,1000,305,10
exec sp_executesql @SQL2,@ParmDefinition,1000,305,10
exec sp_executesql @SQL3,@ParmDefinition,1000,305,10


この結果が下の画像。（今回は厳密さよりも見易さのため、XMLではなく、グラフィカルな実行プランを貼り付けます。）




この結果からだと、SQL1よりもSQL2のほうが20倍ぐらい早くて、SQL2とSQL3の違いはほとんどない。
SQL2,3が同じ実行プランを返すみたいなので、結局はSQL2がいいみたいです。
それでは。