空間インデックスの概要

SQL Server 2008 以降のバージョンでは、空間データがサポートされています。これには、geometry データ型のサポートが含まれます。geometry は、ユークリッド座標系内の幾何データ (点、線、および多角形) をサポートする平面空間データ型です。一方、geography データ型は、地球の表面の領域上の地理オブジェクト (土地など) を表します。geography 列の空間インデックスは、地理データを 2 次元の非ユークリッド空間にマップします。

空間インデックスは、空間データを含むテーブル列 (空間列) で定義されます。各空間インデックスは、有限の空間を参照します。たとえば、geometry 列のインデックスは、ユーザーが指定した平面上の四角形の領域を参照します。

インデックスを作成する空間のグリッド階層への分解

SQL Server 2008 では、空間インデックスは B ツリーを使用して構築されます。したがって、インデックスでは、B ツリーの線形な順序で 2 次元の空間データを表現する必要があります。このため、SQL Server 2008 では、データを空間インデックスに読み取る前に、空間を階層に均一に分解します。このインデックス作成プロセスでは、空間が 4 つのレベルから成るグリッド階層に分解されます。これらのレベルはそれぞれ、レベル 1 (最上位レベル)、レベル 2、レベル 3、およびレベル 4 と呼ばれます。

各レベルでは、1 つ上のレベルがさらに分解されます。したがって、上のレベルのセルに次のレベルの完全なグリッドが含まれます。特定のレベルのすべてのグリッドは、両方の軸に沿って同じ数のセルを持ちます (4 × 4、8 × 8 など)。それらのセルのサイズはすべて同じです。

次の図では、グリッド階層の各レベルで右上のセルが 4 × 4 のグリッドに分解されています。実際にはすべてのセルがこのように分解されます。したがって、たとえば空間を 4 つのレベルの 4 × 4 のグリッドに分解すると、実際にはレベル 4 のセルが合計 65,536 個生成されます。

再帰的テセレーションの 4 つのレベル

注意

空間インデックスのための空間の分解は、アプリケーション データが使用する測定単位に依存しません。

グリッドのセルは、ヒルベルト空間充てん曲線のバリエーションを使用して直線的に番号付けされます。ただし、ここでは説明をわかりやすくするために、ヒルベルト曲線によって行われる実際の番号付けの代わりに単純な行方向の番号付けを使用します。次の図では、建物を表すいくつかの多角形と通りを表す線が、既に 4 × 4 のレベル 1 グリッドに配置されています。レベル 1 のセルには、左上のセルから順番に 1 ~ 16 の番号が付けられています。

4 × 4 のレベル 1 グリッド上の多角形と線

グリッド密度

グリッドの軸に沿ったセルの数により、グリッドの密度が決まります。この数が多いほど密度が高くなります。たとえば、8 × 8 のグリッド (64 個のセル) は、4 × 4 のグリッド (16 個のセル) より高密度です。グリッド密度はレベルごとに定義されます。

CREATE SPATIAL INDEX Transact-SQL ステートメントでサポートされている GRIDS 句を使用すると、レベルごとに異なるグリッド密度を指定できます。特定のレベルのグリッド密度を指定するには、次のいずれかのキーワードを使用します。

キーワード

グリッドの構成

セルの数

LOW

4 × 4

16

MEDIUM

8 × 8

64

HIGH

16 × 16

256

既定値はすべてのレベルで MEDIUM です。

既定以外のグリッド密度を指定することで分解プロセスを制御できます。たとえば、レベルごとに異なるグリッド密度を使用して、インデックスを作成する空間や空間列のオブジェクトのサイズに基づいてインデックスを微調整することができます。

注意

空間インデックスのグリッド密度は、sys.spatial_index_tessellations カタログ ビューの level_1_grid、level_2_grid、level_3_grid、および level_4_grid の各列で確認できます。

テセレーション

インデックスを作成する空間がグリッド階層に分解された後、空間列のデータが行単位で読み取られます。空間オブジェクト (インスタンス) のデータの読み取りが完了すると、そのオブジェクトに対してテセレーション プロセスが実行されます。テセレーション プロセスでは、オブジェクトを、そのオブジェクトが接する一連のグリッド セル (接するセル) に関連付けることによって、オブジェクトをグリッド階層に当てはめます。テセレーション プロセスはグリッド階層のレベル 1 で開始され、幅優先でレベル全体にわたって続けられます。このプロセスは、場合によっては 4 つのレベルすべてにわたって続けられます (一度に 1 レベルずつ処理されます)。

テセレーション プロセスが終了すると、そのオブジェクトについて、一連の接するセルが空間インデックスに記録されます。空間インデックスでは、記録されたそれらのセルを参照することにより、空間内のオブジェクトの場所を、同じくインデックスに格納されている空間列の他のオブジェクトを基準にして特定できます。

テセレーション ルール

オブジェクトについて記録される接するセルの数を制限するために、テセレーション プロセスではいくつかのテセレーション ルールが適用されます。これらのルールにより、テセレーション プロセスの深さと、接するセルのうちのどれがインデックスに記録されるかが決まります。

これらのルールを以下に示します。

  • カバリング ルール

    オブジェクトがセルを完全に覆っている場合、そのセルはオブジェクトに覆われていると言います。覆われているセルはカウントされますが、テセレーションはされません。このルールはグリッド階層のすべてのレベルで適用されます。これにより、テセレーション プロセスが簡略化され、空間インデックスに記録されるデータの量が減ります。

  • オブジェクトごとのセル数のルール

    このルールでは、オブジェクトごとのセル数の制限を適用します。オブジェクトごとのセル数の制限は、レベル 1 以外のレベルで各オブジェクトについてカウントできるセルの最大数を決定します。これにより、下位レベルでオブジェクトについて記録できる情報の量が制御されます。

  • 最下位のセルのルール

    このルールでは、オブジェクトに対してテセレーションされた最下位のセルのみを記録することにより、オブジェクトを最も近い形で再現できます。親のセルはオブジェクトごとのセル数に含まれず、インデックスにも記録されません。

これらのテセレーション ルールは、各グリッド レベルで再帰的に適用されます。以降では、テセレーション ルールについてさらに詳しく説明します。

カバリング ルール

オブジェクトがセルを完全に覆っている場合、そのセルはオブジェクトに覆われていると言います。たとえば次の図では、レベル 2 のセルの 1 つ (15.11) が八角形の中心部分に完全に覆われています。

カバリングによる最適化

覆われているセルはカウントされ、インデックスに記録されます。そのセルはそれ以上テセレーションされません。

オブジェクトごとのセル数のルール

各オブジェクトのテセレーションの範囲は、主に空間インデックスのオブジェクトごとのセル数の制限によって決まります。この制限は、テセレーションでオブジェクトごとにカウントできるセルの最大数を定義します。ただし、オブジェクトごとのセル数のルールはレベル 1 には適用されません。したがって、レベル 1 ではこの制限を超える可能性があります。レベル 1 のカウントがオブジェクトごとのセル数の制限に達したり、この制限を超えたりすると、下位レベルでそれ以上テセレーションが行われなくなります。

カウントがオブジェクトごとのセル数の制限に達していなければ、テセレーション プロセスは続行されます。接するセルの中で最も番号が小さいセル (たとえば前の図ではセル 15.6) から始めて各セルがテストされ、そのセルをカウントするかテセレーションするかが評価されます。テセレーションするとオブジェクトごとのセル数の制限を超えてしまう場合、セルはテセレーションされずにカウントされます。そうでない場合は、セルがテセレーションされ、オブジェクトが接している下位レベルのセルがカウントされます。このようにして、テセレーション プロセスが幅優先でレベル全体にわたって続けられます。このプロセスは、制限に達するか、カウントするセルがなくなるまで、テセレーションされたセルの下位レベルのグリッドに対して再帰的に繰り返されます。

たとえば先ほどの、八角形がレベル 1 グリッドのセル 15 に完全に収まっている図では、セル 15 がテセレーションされて、八角形がレベル 2 の 9 つのセルに分解されています。この例では、オブジェクトごとのセル数の制限が 9 以上と想定されています。オブジェクトごとのセル数の制限が 8 未満の場合は、セル 15 はテセレーションされず、セル 15 のみがオブジェクトに対してカウントされます。

既定では、オブジェクトごとのセル数の制限は 16 です。この値は、ほとんどの空間インデックスで、スペースと精度のバランスが取れた値になります。ただし、CREATE SPATIAL INDEXTransact-SQL ステートメントでサポートされている CELLS_PER_OBJECT**=**n 句を使用すると、オブジェクトごとのセル数の制限を 1 ~ 8192 の範囲で指定できます。

注意

空間インデックスの cells_per_object の設定は、sys.spatial_index_tessellations カタログ ビューで確認できます。

最下位のセルのルール

最下位のセルのルールでは、下位レベルのセルはすべてその上のセルに属しているという事実が利用されています。レベル 4 のセルはレベル 3 のセルに、レベル 3 のセルはレベル 2 のセルに、レベル 2 のセルはレベル 1 のセルにそれぞれ属しています。たとえば、セル 1.1.1.1 に属しているオブジェクトは、セル 1.1.1、セル 1.1、およびセル 1 にも属しています。こうしたセルの階層関係の情報はクエリ プロセッサに組み込まれているため、インデックスに記録するのは最下位レベルのセルだけで済みます。これにより、インデックスに格納する情報を最小限に抑えられます。

次の図では、比較的小さな菱形の多角形がテセレーションされています。このインデックスで使用されているオブジェクトごとのセル数の制限は既定の 16 で、この小さなオブジェクトではその制限に達しないため、テセレーションはレベル 4 まで続けられます。この多角形は、4、4.4、および 4.4.10 と 4.4.14 というレベル 1 ~ 3 のセルにも存在していますが、最下位のセルのルールが使用されるため、テセレーションでカウントされるのはレベル 4 の 12 個のセル (4.4.10.13 ~ 15 と 4.4.14.1 ~ 3、4.4.14.5 ~ 7、および 4.4.14.9 ~ 11) だけです。

最下位のセルによる最適化

テセレーション スキーム

空間インデックスの動作の一部は、テセレーション スキームによって決まります。テセレーション スキームはデータ型固有です。SQL Server 2008 では、空間インデックスで次の 2 つのテセレーション スキームがサポートされています。

  • ジオメトリ グリッド テセレーション。geometry データ型用のスキームです。

  • 地理グリッド テセレーション スキーム。geography データ型の列に適用されます。

注意

空間インデックスの tessellation_scheme の設定は、sys.spatial_index_tessellations カタログ ビューで確認できます。

ジオメトリ グリッド テセレーション スキーム

ジオメトリ グリッド テセレーションは、geometry データ型用の既定の (SQL Server 2008 では唯一の) テセレーション スキームです。ここでは、空間インデックスの操作に関連するジオメトリ グリッド テセレーションの特徴 (サポートされるメソッドと境界ボックス) について説明します。

注意

このテセレーション スキームを明示的に指定するには、CREATE SPATIAL INDEXTransact-SQL ステートメントの USING GEOMETRY_GRID 句を使用します。

サポートされるジオメトリ メソッド

空間インデックスは、オブジェクトのフィルタとして働くことによって、セット指向のメソッドを空間列に適用する際のコストを縮小することを目的としています。geometry データ型には、幾何オブジェクトを表す geometry インスタンスを作成したり、それらのインスタンスを操作したりするための組み込みメソッドが用意されています。空間インデックスは、特定の条件下で、いくつかのセット指向のジオメトリ メソッドをサポートします (STIntersects()STTouches() など)。

空間インデックスによるジオメトリ メソッドのサポートの詳細については、「空間インデックスでサポートされるジオメトリ メソッド」を参照してください。

境界ボックス

幾何データで用いられる平面は無限に広がっていますが、SQL Server 2008 の空間インデックスは有限の空間を必要とします。ジオメトリ グリッド テセレーション スキームでは、分解のための有限の空間を確立するために、四角形の境界ボックスが必要になります。境界ボックスは 4 つの座標によって定義されます ((x-min,y-min) および (x-max,y-max))。これらの座標は、空間インデックスのプロパティとして格納されます。各座標の意味は次のとおりです。

  • x-min は、境界ボックスの左下隅の x 座標です。

  • y-min は、左下隅の y 座標です。

  • x-max は、右上隅の x 座標です。

  • y-max は、右上隅の y 座標です。

注意

これらの座標は、CREATE SPATIAL INDEXTransact-SQL ステートメントの BOUNDING_BOX 句で指定します。

座標 (x-min,y-min) および (x-max,y-max) により、境界ボックスの位置とサイズが決まります。境界ボックスの外側の空間は、番号 0 の 1 つのセルとして扱われます。

空間インデックスは、境界ボックスの内側の空間を分解します。境界ボックスがグリッド階層のレベル 1 のグリッドで満たされ、幾何オブジェクトをグリッド階層に配置するためにオブジェクトの座標が境界ボックスの座標と比較されます。

次の図には、境界ボックスの座標 (x-min,y-min) および (x-max,y-max) によって定義される点が示されています。また、グリッド階層の最上位レベルが 4 × 4 のグリッドとして示されています。下位のレベルはわかりやすくするために省略されています。境界ボックスの外側の空間はゼロ (0) によって示されています。オブジェクト A はボックスから一部はみ出しており、オブジェクト B は完全にボックスの外側 (セル 0) にあります。

座標とセル 0 を表示している境界ボックス。

境界ボックスは、アプリケーションの空間データの一部分に対応します。空間列に格納されているデータがインデックスの境界ボックスに完全に含まれるか、一部のみが含まれるかは、アプリケーションによって異なります。空間インデックスの恩恵を受けることができるのは、完全に境界ボックスの内側にあるオブジェクトに対して計算される操作だけです。したがって、geometry 列の空間インデックスの利点を最大限に活用するためには、ほとんどすべてのオブジェクトが含まれるように境界ボックスを指定する必要があります。

注意

空間インデックスのグリッド密度は、sys.spatial_index_tessellations カタログ ビューの bounding_box_xmin、bounding_box_ymin、bounding_box_xmax、および bounding_box_ymax columns の各列で確認できます。

地理グリッド テセレーション スキーム

このテセレーション スキームは、geography 列のみに適用されます。ここでは、地理グリッド テセレーションによってサポートされるメソッドの概要と、測地空間が平面に投影されてグリッド階層に分解されるしくみを説明します。

注意

このテセレーション スキームを明示的に指定するには、CREATE SPATIAL INDEXTransact-SQL ステートメントの USING GEOGRAPHY_GRID 句を使用します。

サポートされる地理メソッド

geography データ型には、地理オブジェクトを表す geographyインスタンスを作成および操作するための組み込みメソッドが用意されています。空間インデックスは、特定の条件下で、STIntersects()STEquals()、および STDistance() のセット指向の地理メソッドをサポートします。geography データ型列の空間インデックスは、オブジェクトにフィルタを適用して、これらのメソッドを空間データに適用する際のパフォーマンス コストとクエリ コストを削減します。

空間インデックスによる地理メソッドのサポートの詳細については、「空間インデックスでサポートされる地理メソッド」を参照してください。

測地空間の平面への投影

geography インスタンス (オブジェクト) の計算では、オブジェクトを含む空間を測地の楕円体として扱います。地理グリッド テセレーション スキームでは、この空間を分解するために、まず、楕円体の表面が上下の半球に分割されます。その後、次の手順が実行されます。

  1. 各半球を四角錐の面に投影します。

  2. 2 つの四角錐を平面化します。

  3. 平面化された四角錐を結合して、非ユークリッド平面を形成します。

次の図は、この 3 つの手順による分解プロセスの概略図です。四角錐の点線は、各四角錐の 4 つの面の境界を表しています。手順 1. と 2. は、測地の楕円体を表しています。緑の横線は赤道の経線を表し、一連の緑の縦線は緯線を表します。手順 1. では、2 つの半球が四角錐に投影されています。手順 2. では、四角錐が平面化されています。手順 3. は、平面を形成するために結合された後の平面化された四角錐を表しています。いくつかの緯線が投影されているのがわかります。これらの投影された線は直線化されていて、四角錐のどこに投影されたかによって長さが異なっています。

楕円体の平面への投影

空間が平面に投影されたら、今度はその平面が 4 つのレベルから成るグリッド階層に分解されます。レベルごとに異なるグリッド密度を使用できます。次の図は、4 × 4 のレベル 1 グリッドに分解された後の平面を示しています。グリッド階層の下位レベルはわかりやすくするために省略されています。実際には、平面は 4 つのレベルから成るグリッド階層に完全に分解されます。分解のプロセスが完了すると、geography 列の地理データが行単位で読み取られ、各オブジェクトに対して順番にテセレーション プロセスが実行されます。

レベル 1 地理グリッド

空間インデックスのサポート

空間インデックスを作成できるのは空間列だけです。空間インデックスをサポートしているテーブルの任意の空間列に空間インデックスを作成できます。1 つの空間列に複数の空間インデックスを作成することもできます。空間インデックスの制限の詳細については、「空間インデックスに関する制限」を参照してください。