Spatial Indexing 개요 (공간 인덱스)

Spatial Indexing 개요 (공간 인덱스) 

   

-       Version : SQL Server 2008, 2008R2, 2012 

   

SQL Server 2008부터 지원되는 공간인덱스는 공간 열을 인덱싱할 수 있는 확장된 인덱스의 유형이다. 공간 열은 geometry 또는 geography와 같은 공간 데이터 형식의 데이터를 포함하는 테이블 열이다. 

   

SQL Server에서 공간 인덱스는 B-tree를 사용하여 구성된다. 즉 인덱스가 2차원 공간 데이터를 B-tree의 선형 순서로 나타내야 한다는 뜻이다. 따라서 데이터를 공간 인덱스로 읽기 전에 SQL Server에서는 공간을 계층적으로 균일하게 분해하는 작업을 구현해야 한다. 인덱스 생성 프로세스에서는 공간을 계층 구조로 분해한다. 이러한 수준을 최상 위부터 수준1, 수준2, 수준3, 수준4 라고 한다. 

   

각 연속되는 수준이 이전의 수준을 더 분해하므로 각 상위 수준의 셀은 다음 수준에서 완전한 표를 포함하게 된다. 셀의 크기는 모두 같다. 다음 그림은 4X4 공간을 수준 4로 분해하면 65536 수준의 셀 4개가 생성되는 모습이다. 

 

   

   

   

표 계층 구조 셀은 할베르트 공간 채움 곡선의 변형을 사용하여 선형으로 번호가 매겨진다. 아래 그림은 이해하기 쉽도록 할베르트 곡선에 따라 실제로 생성되는 번호를 행 단위 번호로 표현한 모습이다. 건물을 나타내는 여러가지 다각형(회색)과 도로를 나타내는 선이 4X4, 수준 1로 배치되어 있다.  

 

   

   

표의 축에 따른 셀 수로 표의 밀도가 결정되며 셀 수가 많을수록 표의 밀도가 높다. 예를 들어 8X8 은 4X4 보다 밀도가 높다. 표 밀도는 수준별 기준으로 정의된다. 

   

다음 표는 각 수준별로 표 밀도이다. SQL Server에서 데이터베이스 호환성 수준이 100 이하로 설정경우 모든 수준의 기본값은 MEDIUM이다. 데이터베이스 호환성 수준이 110 이상으로 설정된 경우 기본값이 자동 표 구성이다.  

키워드	표 구성	셀 개수
LOW	4X4	16
MEDIUM	8X8	64
HIGH	16X16	256

   

기본값이 아닌 표 밀도를 지정하여 분해 프로세스를 제어할 수 있다. 각 수준별로 서로 다른 표 밀도는 인덱싱 공간의 크기와 공간 열의 개체를 기준으로 인덱스를 미세하게 조정하는데 유용할 수도 있다. 

   

인덱싱된 공간을 표 게층 구조로 분해한 후 공간 인덱스는 공간 열에서 데이터를 한 번에 한 행씩 읽는다. 공간 개체나 인스턴스의 데이터를 읽은 후 공간 인덱스는 해당 개체에 대해 공간 분할 프로세스를 수행 한다. 공간 분할 프로세스는 개체를 표 형태의 셀의 집합과 연결하여(연결 된 셀)개체를 표 계층 구조에 맞게 조정하며 수준 1에서 시작하면 프로세스는 전체 수준에서 너비우선으로 진행된다. 이 프로세스는 한번에 한 수준씩 수준4 전체에서 계속 진행될 수도 있다. 

   

개체에 대한 기록된 연결된 셀 개수를 제한하기 위해 공간 분할 프로세스는 다음과 같은 공간 분할 규칙을 적용한다. 

l  포함 규칙 : 개체가 한 셀을 완전히 포함할 경우 해당 셀은 개체에 의해 포함되어 있다고 한다. 포함된 셀은 개수가 계산되지만 공간 분할이 수행되지는 않는다. 

 

   

l  개체당 셀 수 규칙 : 개체당 셀 수 제한을 적용하여 각 개체에 대해 계산될 수 있는 최대 셀 수를 결정 한다. 

 

   

l  최하위 셀 규칙 : 개체에 대해 공간 분할된 최하위 셀만 기록하여 최적의 개체 근사값을 생성한다. 부모 셀은 개체당 셀에 영향을 주지 않으며 인덱스에 기록되지 않는다. 다음 그림에서는 비교적 작은 다이아몬드형 다각형이 공간 분할되어 있다. 인덱스는 개체당 셀 수로 기본값 16을 사용하며 이 값은 이러한 작은 개체로는 도달되지 않는 값이다. 따라서 공간 분할은 수준 4까지 계속되며, 다각형은 수준-1에서 수준-3 셀까지 4, 4.4, 4.4.10 및 4.4.14에 위치한다. 그러나 최하위 셀 규칙을 사용하면 공간 분할에서는 수준-4 셀 12개만(4.4.10.13-15, 4.4.14.1-3, 4.4.14.5-7, 4.4.14.9-11 등) 계산한다. 

 

   

   

기하학 데이터는 무한할 수 있는 평면을 차지한다. 그러나 SQL Server에서 공간 인덱스는 제한된 공간을 필요로 한다. 분해를 위한 제한된 공간을 설정하려면 기하 도형 표 공간 분할 구성표에는 사각형 경계상자가 필요하다. 다음 그림은 경계 상자의 (x-min, y-min), (x-max, y-max) 좌료로 정의되는 지점을 보여준다. 경계 상자 외부의 공간은 0으로 표시된다. 

   

   

경계 상자는 응용 프로그램 공간 데이터의 일부분에 해당한다. 인덱스의 경계 상자가 공간 열에 저장된 데이터를 완전히 포함하거나 일부만 포함하는지는 응용 프로그램에 따라 좌우 된다. 전체적으로 경계 상자 내부에 있는 개체에서 처리되는 작업만 공간 인덱스의 이점을 활용한다. 

   

[참고자료] 

http://technet.microsoft.com/ko-kr/library/bb895265.aspx 

   

   

   

   

2013-11-20 / 강성욱 / http://sqlmvp.kr