인덱스 구조 및 탐색

SQL 튜닝에서 사용되는 인덱스

인덱스 구조는 수평적 탐색과 수직적 탐색을 이룬다. 이것을 이해하고 나면 인덱스 구조에 대해 그림이 명확해진다.

인덱스를 우리가 중심적을 공부하는 이유는 SQL 튜닝에 초점이 맞쳐져있다. SQL 튜닝을 통해 원하고자 하는 데이터를 빠르게 얻기 위해서 인덱스에 대해 공부하는데 SQL을 사용하여 데이터를 찾는 방법은 이미 많이 알려진 두 가지 방식이 있다.

• 테이블 전체 스캔
• 인덱스를 이용

 

그럼 Table Full Scan 방식이 아닌 인덱스를 사용하기 위해 적절 한 튜닝의 핵심요소가 무엇인지 살펴보자.

만약 몸무게가 기재되어있는 학생 연명부가 있다고 가정해보자. 학생명과 몸무게로 정렬되어 있을때 학생을 찾기 위한 과정에서 학생을 찾고 몸무게 검색하는 과정이 거친다. 이런과정을 인덱스 스캔이라고 하는데, 이런 인덱스 스캔 과정에서 비용을 줄여야 한다.

그리고 만약 몸무게로만 정렬되어 있을 때 몸무게 접근 후 정렬되어 있지 않은 학생명을 찾기위해서 랜덤 I/O가 발생하는데 이런 랜덤 액세스를 최소화하도록 인덱스를 튜닝해야한다.

인덱스 스캔과 랜덤 액세스 두 가지 중 조금더 중요한 부분을 찾으라 한다면 랜덤 액세스 비용을 줄이는게 더 효율적이다.

위의 예에서 봤을때 시력을 찾아도 해당학생을 찾기위한 과정이 더 비용이 많이 들기 때문이다. 이처럼 SQL튜닝은 랜덤 I/O와의 전쟁이다.

이미지 출처 : http://www.dbguide.net/db.db?cmd=view&boardUid=148214&boardConfigUid=9&boardIdx=137&boardStep=1

 

인덱스 구조

인덱스는 대용량 테이블에서 필요한 데이터만 빠르고 효율적으로 액세스하기 위해 사용되는 오브젝트이다.

책에 주제에 대한 페이지 번호가 기재되어 있으면 필요한 내용을 빠르게 찾을 수 있는것처럼 인덱스를 이용하면 Range Scan을 사용하여 필요한 부분을 빠르게 읽을 수있다.

일반적으로 DBMS에서는 BTree 형태의 인덱스를 사용한다. 일반적으로 루트와 브랜치 블록에 있는 데이터는 하위 블록에 대한 주소값을 가지고 있으며, 이 것을 구분하는 키는 하위 블록에 저장된 키값의 범위를 나타낸다. 만약 사용자 ‘정철’ 데이터를 기준이라면 사용자 >= ‘정철’의 데이터는 우측 블록에 위치하는 것을 의미한다.

리프 블록에 저장된 각 레코드는 키값 순으로 정렬되어 있고, ROWID를 가지고 있다. 인덱스 키값이 동일할 경우 ROWID 순으로 정렬된다. ROWID는 데이터 블록주소와 로우 번호가 있기에 인덱스를 스캔하는 이유는 이 ROWID를 찾기 위해서이다. 왜냐하면 ROWID의 데이터 블록주소는 데이터 파일번호와 블록번호(데이터파일 내에서 부여한 상대적 순번)로 구성되어 있고, 로우번호(블록 내 순번)으로 구성되어 있기 때문에 데이터를 찾을 수 있기 때문이다.

 

인덱스 수직적 탐색

정렬된 인덱스 레코드 중 조건을 만족하는 첫 번째 레코드를 찾는 과정으로 인덱스 스캔 시작지점을 찾는 과정이다.

인덱스 수직적 탐색은 루트 블록에서 부터 시작한다. 각 브랜치 블록에 저장된 인덱스 레코드는 하위 블록에 대한 주소값을 가진다. 그 주소값을 이용하여 인덱스를 스캔한다.

인덱스 수직적 탐색은 찾고자 하는 값보다 크거나 같은 값을 만나면, 바로 직전 레코드가 가리키는 하위 블록으로 이동한다. 이 과정을 반복하면서 찾아가는 하위 블록에서 조건을 만족하는 첫 번째 블록을 찾아가는 과정이다.

 

인덱스 수평적 탐색

수직적 탐색을 통해 스캔 지점을 찾고나면 그 후 데이터가 더 안나타날 때까지 인덱스 리프 블록을 수평적으로 스캔한다. 즉 데이터를 찾는과정이다.

인덱스 리프 블록끼리는 서로 앞뒤 블록에 대해 주소값을 가지고 있기 때문에 수평적인 탐색이 가능하다. 이런 과정을 통해서 조건절에 만족하는 데이터를 모두 찾고 ROWID값을 얻는다.

결국 수직적 탐색은 수평적 탐색을 시작할 위치를 찾는것이고, 수평적탐색은 그렇게 찾은 위치에서 본격적으로 데이터를 찾는 작업을 시작한다.

 

결합 인덱스 구조와 탐색

두 개 이상의 컬럼을 결합해서 인덱스를 만들 수도 있다. 이런경우에도 찾고자 하는 값과 동일하거나 같은 값을 만나게 되었을 때, 하위 블록으로 이동하는 수직적 탐색을 먼저 진행한다.

만약 고객명과 성별을 하나의 인덱스로 묶어서 탐색한다고 하였을 때와 성별과 고객명으로 묶었을 때 서로 탐색하는 블록은 달라질 수 있다. 하지만 결국 블록을 탐색하는 개수는 동일하다. 서로 컬럼의 순서가 바뀔경우에 인덱스 탐색의 비용이 다를거라는 주장이 있으나 BTree의 경우 평면구조가 아니기 때문에 수직적, 수평적 탐색에서 발생하는 비용은 동일하다.