컴퓨토피아

Part 1: 오프라인, 직렬, 일반 인덱스(파티션 되지 않은)

Builder (write data to the in-build index)

                           |

                     Sort (order by index key)

                           |

                     Scan (read data from source)

b-tree 인덱스를 구성하기 위해서 우리는 먼저 원본 데이터를 정렬해야 한다. 작업 순서는 원본 데이터를 스캔하고, 정렬한 뒤(가능한 메모리에서*) 그리고 b-tree를 구성하는 것이다.

왜 b-tree를 바로 만들지 않고 먼저 정렬을 하는가? 이론적으로는 정렬할 필요가 없다, 일반적인 DML를 사용해서 바로 인덱스 구성 작업에 데이터를 추가해도 된다, 그러나 이 경우 추가하는 데이터가 랜덤하다면 결국 b-tree 상의 적합한 리프 노드를 먼저 검색한 뒤에 입력하게 된다. b-tree 검색이 빠르긴 하지만, 최적은 아니다. 따라서 인덱스 구성 작업은 인덱스에 필요한 정렬을 사용해서 데이터를 먼저 정렬하고, 인덱스 구성 작업으로 넘겨주는 것이다, 이는 그저 b-tree상에 추가 작업만 요구된다.

정렬에서 인덱스 구성자 사이에 데이터를 넘기는 동안 각 익스텐트 별로 모든 행이 복사되는 즉시 해당 익스텐트를 해제한다. 이를 통해 인덱스 구성 시 이론적으로 필요한 작업 공간인 3 x 인덱스 크기(원본 + 정렬 테이블 + b-tree)를 2.2 x Index Size(대략)로 줄여준다.

*메모리 상에서 정렬된다고 보장하지는 않는다. 메모리 정렬 여부는 가용 메모리와 실제 행 수에 따라 의존적이다. ‘메모리 상에서 정렬’은 원론적으로 디스크 상에 정렬 테이블을 할당할 필요가 없으므로 빠르다. 그러나 반드시 필요한 것은 아니다. 물론 메모리 상 정렬 보다는 더 느리지만 디스크에서 데이터를 처리할 수 있다.

각 정렬 테이블(매우 작은 데이터일지라도)은 실행하는데 필요한 최소 40페이지(3,200KB)를 필요로 한다 (뒤에서 다루겠지만 병렬 처리의 경우 동시의 하나 이상의 정렬 테이블을 소비한다). 정렬 메모리를 계산할 때, 메모리 정렬에 필요한 충분한 메모리를 할당하려고 한다. 인덱스 생성 작업 시 최소 40페이지를 제공할 수 없을 정도로 메모리가 부족한 경우 작업은 실패할 수 있다.

인덱스 구성 마지막 단계는 항상 통계 정보 구성 작업이다. 적절한 통계 정보는 쿼리 최적화 프로그램(Optimizer)이 더 좋은 쿼리 계획을 산출하는데 도움을 준다, 사용자가 직접 ‘create’ 및 ‘update’ 통계 명령을 이용해서 SQL Server가 특정 개체에 대한 통계 정보를 생성하거나 갱신하도록 강제할 수도 있다. 그러나 새로운 인덱스를 생성할 때, 모든 행을 처리하게 되므로 결국 이 때가 전체 데이터(100%)의 통계 정보를 구성할 수 있는 절호의 기회가 되는 것이다.

정리:

직렬 계획과 오프라인으로 일반 인덱스를 구성하기 위해서는 대략 2.2 x 인덱스 크기에 해당하는 디스크 공간과 쿼리 실행자가 절차를 시작하기 위해 필요한 최소 40페이지의 메모리를 요구한다.

Part 2: 오프라인, 병렬, 일반 인덱스(파티션 되지 않은)

병렬 인덱스 구성 방식은 필요한 통계 정보를 가진 히스토그램이 있는지 없는지에 따라서 달라진다. 즉, 병렬 인덱스 계획은 크게 두 가지 범주를 가진다:

-       히스토그램이 가용

-       히스토그램이 가용하지 않음

히스토그램이 가용한 경우(병렬 정렬 및 구성 작업)

              X (Exchange)

   |          \            \

         Builder… Build…  Build… (write data to the in-build index)

                           |           |            |

                      Sort…      Sort…  Sort … (order by index key)

                           |          /            /

                       Scan (read data from source)

통계 정보가 가용한 경우 병렬 인덱스 구성이 가능하다(파티션 범위 정보를 사용할 수 있고 데이터의 분포를 결정하는데 사용할 수 있기 때문).

이 경우 어떻게 데이터를 스캔할까? 첫 번째 키 칼럼에 대한 통계 정보가 필요하다, 따라서 해당 통계 정보가 없으면 샘플링 기반의 통계 정보를 생성하고 이를 통해 병렬 여부와 병렬 처리 방법을 결정하는데 사용한다. 만일 인덱싱 뷰(통계 계획이 없는)와 같이 샘플링 통계 정보를 구성할 수 없는 경우엔, 다른 인덱스 구성 계획이 생성된다. 통계 정보와 히스토그램을 사용해서 데이터 분포를 결정할 수 있다, 이를 통해 병렬 계획에서 적절한 작업 부하 분산을 결정할 수 있으며, 또한 시스템 자원에 대한 고도의 활용률을 위해 병렬 처리 수(DOP, Degree Of Parallelism)를 결정하는데 도움을 주게 된다. 히스토그램으로부터 데이터 분포 상의 각 버킷(bucket)에 대한 행 수를 예상함으로써, N(N = DOP)개의 범위로 작업 부하를 분리하며, 각 작업자(worker)당 하나씩의 범위를 처리하게 된다.

데이터를 스캔하기 위해 범위 파티션 스캔을 사용하며, 각 작업자는 해당 범위에 데이터를 이용해서 자신만의 정렬 테이블를 구성하고 그 데이터에 기반한 b-tree를 만들게 된다. 각 작업자는 결국 분리된 개별 정렬 테이블과 b-tree를 가지는 것이다. 이후 인덱스 구성 작업의 마지막 단계에서 이들을 조정하는 담당 스레드(thread)에 의해서 모두 짜집기를 하게 되며, 마지막으로 완성된 b-tree에 대해 전체 데이터 통계정보 구성을 완료하게 된다.

히스토그램을 사용한 병렬 인덱스 구성은 최적의 성능을 제공한다. 반면에 이로 이한 문제는 앞서 다루었던 대로 더 많은 메모리를 소비한다는 것이며 만일 충분한 가용 메모리가 없는 경우 작업이 실패할 수도 있다(각 작업자당 개별 정렬 테이블을 만들게 되므로). 필요 시 MAXOP) 옵션을 사용해서 이를 적절히 조정할 수 있다.

For example:

Create index idx_t on t(c1, c2)

WITH (MAXDOP = 2)

히스토그램이 가용하지 않은 경우

Build (serial) (write data to the in-build index)

                          |

                X (Merge exchange)

                           /          |           \

                      Sort…      Sort…  Sort …(order by index key)

                           |           |            |

                       Scan…    Scan… Scan…(read data from source)   

히스토그램을 사용할 수 없다면(예를 들어 뷰에 인덱스를 만드는 경우) 이전 글에서 다루었던 방법을 사용할 수 없다, 따라서 데이터 분포와는 무관하게 일반적인 병렬 스캔을 사용한다.

동작 방식

원본 데이터는 병렬로 스캔한다. 그러나 b-tree 구성은 직렬 작업이다. 병렬 처리를 수행하는 각 작업자를 이전에 병렬 스캔 방법과 같이 동일한 방법으로 힙으로부터 특정 페이지를 스캔한다. 스캔 후는 각 작업자 별로 정렬 테이블을 가지고 데이터를 구성하며, 나중에 병합(Merge)을 통해서 데이터를 결합시키게 된다(이전과 같은 개별 b-tree 구조와 짜집기 방식은 사용하지 못한다). 최종 정렬 데이터가 만들어지면 이를 통해 직렬로 인덱스 구성 작업을 수행하게 된다. 왜 이 계획이 상대적으로 느린 걸까? 이는 직렬로 수행되는 인덱스 구성작업과 ‘Merge exchange’에 의해서 발생하는 추가 오버헤드 때문이다.

메모리 고려 사항

병렬 인덱스 구성은 동시에 여러 정렬 테이블을 구성하므로 기본 메모리 요구가 더 크며 계산식 또한 약간 달라진다. 메모리 계산식은 1) 필요 메모리, 2) 추가 메모리를 가진다. 필요 메모리를 각 정렬 당 40페이지를 요구했다. 그런데 예를 들어 DOP = 2라고 한다면, 2개의 정렬 테이블에 대해 총 80페이지가 필요 메모리가 되는 것이다. 그러나 추가 메모리는 DOP 설정과 무관하게 동일하다. 이는 전체 행 수가 DOP 설정과 무관하게 동일한 값이기 때문이다. 예를 들어 직렬 계획으로 추가 메모리 500페이지가 필요하다면 병렬 계획도 동일한 요구를 가지는 것이다. 각 작업자는 500/DOP 페이지 만큼의 추가 메모리에 + 40 페이지 필요 메모리를 가질 것이다.

다음 주제는,

Part 4: 오프라인, 직렬/병렬 파티셔닝(정렬되지 않은 파티션 인덱스 구성)

정렬되지 않은 경우는 힙과 인덱스가 서로 다른 파티션 스킴을 사용하거나, 힙이 파티션되지 않은 경우이다.

이번 글에서 원본 데이터가 파티션 된 경우와 그렇지 않은 2가지 경우의 정렬되지 않은 파티션 인덱스 구성에 대해 다룰 것이다.

원본이 파티션 되지 않은 경우

다음 쿼리를 보자.

Create Partition Function pf (int) as range right for values (1, 100, 1000)

Create Partition Scheme ps as Partition pf
ALL TO ([PRIMARY])

Create table t (c1 int, c2 int) – 테이블은 디폴트로 PRIMARY 파일 그룹에 생성

Create clustered Index idx_t on t(c1) on ps(c1)  -– 정렬되지 않은 인덱스 구성

직렬 계획은 간단하다,

 Index Insert (write data to the in-build index)
   |
 Sort (order by index key)
   |
 Scan (read data from source)

Sort 반복연산자(iterator)는 각 파티션당 하나의 정렬 테이블을 만든다(예제에서는 4개의 파티션이 존재하므로 동시의 4개의 정렬 테이블이 만들 것이다). 디폴트로, 데이터 정렬을 위해 사용자 데이터베이스를 사용한다. 이전에 언급한대로, 정렬 데이터에서 모든 데이터를 복사하고 나면 각각의 익스텐트를 해제한다. 이 동작을 통해서 각 파티션 별로 필요한 디스크 공간을 3 x 파티션크기에서 2.2 x 파티션 크기로 줄일 수 있다. 따라서 각 파일 그룹은 2.2 x (해당 파일 그룹에 속한 전체 파티션 크기)만큼의 디스크 공간을 요구한다. SORT_IN_TEMPDB 옵션을 지정한다면, 모든 정렬 테이블은 tempdb에서 다루어질 것이고, 2.2 x (인덱스 전체 크기)만큼의 여유 공간을 tempdb에 요구할 것이다.

Index Insert 반복연산자는 sort 반복연산자가 정렬을 완료하고 나면 인덱스 구성을 시작한다. 파티션 수 만큼의 정렬 테이블이 필요하므로, 각 정렬 테이블 당 최소 40페이지가 필요함을 상기한다면, 최소 필요 메모리는 파티션 수 x 40페이지가 될 것이다.

병렬 계획이 된다면,

X (Exchange)
   |
 Index Insert
   |
 Sort
   |
 Scan

각 작업자 스레드가 병렬 처리 수와 해당 파티션 수만큼 계산되어 할당된다 (예를 들어, 4개의 파티션에 4개의 작업자 스레드이면 각 스레드 당 1개의 파티션). Sort 반복연산자를 할당된 각 파티션에 대해 하나의 정렬 테이블을 생성한다. 각 작업자는 원본 데이터를 한 번 스캔하고 그 파티션에 속한 행들을 처리한다, 처리된 행들은 소속된 파티션에 따라 해당 정렬 테이블에 입력된다.

모든 정렬 테이블이 완성되면, 인덱스 구성자가 정렬 테이블을 하나씩 처리하며, 각 파티션의 파일 그룹별로 b-tree를 구성하게 된다.

디스크 공간 및 메모리 필요 사항은 이전의 직렬 계획과 동일하다. 두 경우 모드, 모든 정렬 테이블이 완성되기 전까지 인덱스 구성을 시작할 수 없기 때문이다.

원본이 파티션된 경우

원본 테이블이 이미 파티션된 경우엔, 파티션 인덱스를 구성할 때 그 방법을 바꿀 수 있다.

예를 들어, 원본 테이블과 동일한 파티션 함수와 스킴을 사용하되, 새로운 인덱스는 다른 칼럼으로 파티션될 수 있다.

CREATE TABLE t (c1 int, c2 int) ON ps (c2)

……

CREATE CLUSTERED INDEX idx_t ON t(c1) ON ps(c1)

직렬 계획은 다음과 같다,

    Index Insert
       |
     Sort
       |
      NL (Nested Loop)
     /    \
 CTS   Scan

Constant Table Scan 연산자에 의해 파티션 ID를 하나씩 넘겨주면, NL 연산자에 의해서 해당 파티션 데이터를 스캔하고 결과를 Sort 반복연산자에 넘겨준다. 여기서부터 원본이 정렬되지 않은 시나리오와 동일하다. 메모리와 디스크 요구 사항 또한 같다.

병렬 계획의 경우는,

X (Distribute Streams)
       |
     Index Insert
       |
     Sort
       |
       X (Repartition Streams)
       |
      NL
     /   \
   X    Scan
  /
CTS

CTS위에 있는 연산자가 Gather Streams 연산자이다, 그 말은 생성자 하나의 다중 소비자를 가진다는 뜻이다 (역주: Gather Stream연산자에 다중 입력 처리를 통해 병렬 처리를 수행하고 이를 단일 출력으로 제공하는 연산자이다). Gather Streams와 Repartition Streams 연산자 사이에, 원본 파티션 수에 병렬 처리 수를 나눈 만큼의 작업자가 할당된다. 원본은 한 번만 스캔한다.

Repartition Streams 연산자는 쿼리 계획을 두 개의 병렬 처리 영역으로 분리한다. 최상위에 있는 Distribute Streams 연산자와 Repartition Streams 연산자 사이에서는 앞서 Repartition Streams 아래에서 만들어진 작업자 집합과는 또 다른 집합을 가진다. 각 작업자가 대상 파티션에 할당되는데 그 수는 대상 인덱스 파티션 수를 병렬 처리 수로 나눈 만큼 할당된다. 나머지 정렬 및 인덱스 구성 작업은 이전의 원본이 파티션되지 않은 경우의 병렬 처리와 동일하며, 메모리 및 디스크 공간 또한 동일하다.

여기까지입니다.

계속 살펴봐 주신 분들에게 감사드립니다.

더불어 원본에서 다음 문서가 또 올라오면 이어서 계속 소개해 드리도록 하겠습니다.

그럼, 일단 이 시리즈 문서는 접구요,

다음에 또 다른 재미있는 자료를 번역해서 공유하도록 하겠습니다.

행복한 하루 되세요~~~