[Database] 인덱스 자세히 알아보기

인덱스의 기본적인 목적은 검색 성능의 최적화이다. 즉, 검색 조건을 만족하는 데이터를 인덱스를 통해 효과적으로 찾을 수 있도록 돕는다. 그렇지만 Insert, Update, Delete 등과 같은 DML 작업은 테이블과 인덱스를 함께 변경해야 하기 때문에 오히려 느려질 수 있다는 단점이 존재한다.

인덱스 기능

인덱스는 어떤 종류의 검색 연산을 최적화하기 위해 데이터베이스상에 로우들의 정보를 구성하는 데이터 구조이다. 인덱스를 이용하면 전체 데이터를 검색하지 않고 데이터베이스에서 원하는 정보를 빠르게 검색할 수 있다. 

 

인덱스는 인덱스를 생성한 컬럼값으로 정렬되어 있고 테이블 내 값들이 저장된 위치를 갖고 있으므로 인덱스를 이용하면 전체 테이블을 읽지 않아도 찾으려는 데이터를 찾을 수 있다. 그래서 테이블에 데이터가 수천만 개로 증가해도 인덱스를 이용한 접근 경로와 검색 범위가 동일하다면 속도의 변화는 거의 발생하지 않는다. 그렇기 때문에 인덱스는 디스크I/O를 줄일 수 있는 좋은 수단이다. 

 

인덱스의 가장 중요한 기능은 접근 경로를 단축함으로써 데이터의 탐색 속도를 향상시키는 것이다. 데이터의 탐색은 데이터베이스에서 가장 중요하고 빈번한 연산이므로 DBMS는 인덱스를 활용하여 탐색시 발생하는 비용을 최소화하고자 한다.

 

DB 테이블의 모든 컬럼에 인덱스를 걸면 어떻게 될까?

- 인덱스를 생성하면 레코드가 추가/삭제/변경 될때마다 인덱스 값도 추가/삭제/변경해야 한다. 이는 Disk I/O를 유발하게 된다. 공간을 차지하게 된다.

- 인덱스는 보통 B+ Tree인데, Create, Update, Delete 할 때마다 Tree를 reorganization 해야한다. 이는 비용을 증가시킨다. Bulk loading이 대안이 될 수 있다.

- Bulk loading은 삭제할 때 reorganization 해야하는데, 그냥 표시만 해놓는다. 삭제는 안하고, 실 데이터보다 index크기가 더 커질수 있다.

인덱스 설계 절차

인덱스는 특정 응용 프로그램을 위해서 생성되는 것이 아니다. 최소의 인덱스 구성으로 모든 접근 경로를 제공할 수 있어야 전략적인 인덱스 설계가 된다. 따라서 인덱스 선정은 테이블에 접근하는 모든 경로를 수집하고 수집된 결과를 분석하여 종합적인 판단에 의해서 결정되는 것이 바람직하다. 인덱스는 특정 애플리케이션을 위해서 생성되는 것이 아니다. 최소의 인덱스 구성으로 모든 접근 경로를 제공할 수 있어야 전략적인 인덱스 설계가 된다. 따라서 인덱스 선정은 테이블에 접근하는 모든 경로를 수집하고 수집된 결과를 분석하여 종합적인 판단에 의해 결정하는 것이 바람직하다.

 

반복 수행되는 접근 경로

분포도가 양호한 칼럼

자주 결합되어 사용되는 칼럼

데이터 정렬 순서와 그룹핑 칼럼

일련번호를 부여한 칼럼

통계 자료 추출 조건

조회 조건이나 조인 조건 연산자

 

위에서 제시되는 칼럼들은 인덱스 생성이 필요한 칼럼들이다. 

 

분포도 조사에 의한 후보 칼럼 선정

수집된 접근 경로 칼럼들을 대상으로 분포도를 조사한다. 설계 단계에서는 실제 분포도를 예측할 수 없으므로 현재 시스템 데이터를 참고하거나 업무에서 예상한 상황을 고려하여 분포도를 예측한다.

 

분포도(%) = 데이터별 평균 로우 수 / 테이블의 총 로우 수 * 100

 

일반적으로 분포도가 10 ~ 15% 정도이면 인덱스 칼럼 후보로 사용한다. 그런데 B 트리 인덱스의 특성상 분포도가 증가하게 되면 인덱스의 효율이 점차적으로 떨어져 어느 시점이 되면 오히려 인덱스를 통해 검색하는 것이 전체 데이터를 읽는 것보다 더 느리게 된다. 이러한 반환점을 인덱스의 손익 분기점이라 한다. 분포도가 나쁜 경우 인덱스를 경유하여 액세스하면 검색하는 로우의 수는 적지만 입출력 횟수는 테이블 스캔보다 훨씬 많아진다.

 

분포도는 단일 칼럼을 대상으로 조사한다.

단일 칼럼으로 만족하지 않는 경우 검색 조건을 좁히기 위해 결합 칼럼들에 대한 분포도 조사를 실시한다.

분포도 조사 결과를 만족하는 칼럼은 인덱스 후보로 선정하고 인덱스 후보 목록을 작성한다. 

빈번히 변경이 발생하는 칼럼은 인덱스 후보에서 제외한다.

 

칼럼 조합 및 순서 결정

단일 칼럼의 분포도가 양호하면 단일 칼럼 인덱스로 확정한다. 하지만 하나 이상의 칼럼 조합이 필 요한 경우는 아래와 같은 요소를 고려하여 인덱스 칼럼 순서를 결정한다.

 

항상 사용되는 칼럼을 선두 칼럼으로 한다.

등치( = )조건으로 사용되는 칼럼을 선행 칼럼으로 한다.

분포도가 좋은 칼럼을 선행 칼럼으로 한다.

ORDER BY, GROUP BY 순서를 적용 한다.

 

인덱스 구조

인덱스는 인덱스를 구성하는 구조나 특징에 따라 트리 기반 인덱스, 해쉬 기반 인덱스, 비트맵 인 덱스, 함수 기반 인덱스, 조인 인덱스, 도메인 인덱스 등으로 나눌 수 있다.

 

트리 기반 인덱스

대부분의 상용 DBMS에서는 트리 구조를 기반으로 하는 B+ 트리 인덱스를 주로 사용한다. B+ 트 리는 루트에서 리프 노드까지 모든 경로의 깊이가 같은 밸런스 트리(balanced tree) 형태로, 다른 인덱스에 비해 대용량 처리의 데이터 삽입과 삭제 등에 좋은 성능을 유지한다.

 

B 트리는 키 값이 트리상에 한 번만 나타나기 때문에 키 값을 순차적으로 액세스하고자 할 때 트리 를 탐색하는 데 많은 비용이 발생한다. 이러한 트리 탐색 비용을 최소화하기 위해 B+ 트리에서는 모든 키 값을 리프 노드에 내리고 양방향으로 연결(doubly linked list)해 놓았다. 이러한 구조로 인해 B+ 트리는 범위 검색 시에 아주 좋은 성능을 낸다.

Internal Structure of a B-tree Index

B+ 트리의 탐색 성능은 전체 로우 수보다 이분화해 가는 깊이에 더 많은 영향을 받는다. 그러므로 한 번 이분화를 했을 때 얼마나 처리할 범위를 줄여 주었느냐가 처리할 깊이에 영향을 주게 된다. 그런데 스캔은 랜덤 액세스보다 비용 측면에서 더 유리하기 때문에 몇 번의 이분화를 통해 어느 정도 처리 범위가 줄어들었다면 더 이상 이분화하지 않고 스캔을 통해 비교하는 것이 더 유리하다. 이러한 원리를 바탕으로 DBMS들은 몇 개의 칼럼까지만 이분화를 수행하고 그 이상의 칼럼은 인덱스 로우의 스캔을 통해 비교한다.

 

B+ 트리는 삽입과 삭제 시의 성능이 노드의 분할과 머지의 횟수에 따라 결정되기 때문에 노드가 분할될 확률을 줄이기 위해 “각 노드는 최소한 반 이상 차 있어야 한다”라는 제약 조건을 가지고 있다.

 

그런데 데이터 량이 대용량화되면서 이러한 제약 조건만으로는 분할을 최소화하는 데 한계가 있어 이 제약 조건을 “각 노드는 최소한 2/3 이상 차 있어야 한다”라는 제약 조건으로 변경되었다. 이러한 제약 조건을 가진 트리를 B* 트리 라고 한다. 현재 대부분의 상용 DBMS에서 사용하고 있는 B 트리 인덱스는 B+ 트리와 B* 트리의 구조와 특징을 모두 포함하고 있는 인덱스를 지원한다.

 

B+ 트리에서 노드를 가득 채우는 방법은 데이터 삽입 시 발생하는 분할의 횟수를 줄여 삽입 시의 성능은 향상되지만 삭제 시에는 머지가 발생할 가능성이 더 높아지기 때문에 삭제가 빈번하게 발생하는 경우에는 더 치명적인 문제를 야기한다. 이러한 부분을 피하는 방법은 삭제 시에 제약 조건을 완화하는 방법이다. 실제로 대부분의 상용 DBMS에서는 삭제 시에 발생할 수 있는 머지에 대한 성능상의 저하를 막기 위해 삭제 시에 머지 자체가 발생하지 않도록 하는 방법을 사용하고 있다. 예를 들어, 오라클의 경우도 전체 데이터를 전부 삭제하더라도 머지가 발생하지 않고 삽입 시에 확장된 구 조와 스토리지를 계속 유지하도록 설계되어 있다. 때문에 삭제가 빈번하게 발생하는 테이블의 경우 인덱스 사이즈가 지속적으로 증가할 수 있으므로 저장 공간 낭비를 막기 위해서는 인덱스를 주기적 으로 재생성해 주어야 한다ass="text">해쉬 인덱스의 기본 개념은 키 값에 해쉬 함수를 적용하여 해당 키 값에 대응하는 버켓을 식별하고 탐색한다는 것이다. 버켓은 처음에는 하나의 기본 페이지로 구성되지만 해당 버켓에 새로운 데이터 엔트리를 위한 저장 공간이 없을 때에는 새로운 오버플로우 페이지를 하나 할당하고 그 페이지에 데 이터를 삽입하여 해당 버켓과 연결한다. 그런데 오버플로우 체인이 길어지면 버켓을 탐색하는 성능 이 저하되므로 초기 생성 시 80% 정도만 채우고, 또한 주기적으로 다시 해싱해 오버플로우 페이지를 제거한다.

 

비트맵 인덱스

인덱스의 목적은 주어진 키 값을 포함하고 있는 로우에 대한 주소 정보를 제공하는 것이다. B+ 트리 인덱스의 경우는 각각의 키 값에 Rowid 리스트를 저장함으로써 이러한 목적을 달성하고 있지만, 비트맵 인덱스의 경우는 B+ 트리 인덱스와는 약간 다른 방식으로 로우에 대한 주소 정보를 제공한다.

 

비트맵 인덱스는 ‘0’ 혹은 ‘1’로 이루어진 비트맵만 가지고 있기 때문에 이 정보로부터 실제 로우가 저장되어 있는 물리적인 위치를 아는 것은 불가능해 보인다. 그러나 비트맵에서 비트의 위치는 테이블에서 로우의 상대적인 위치를 의미하므로 해당 테이블이 시작되는 물리적인 주소만 알면 실제 로우의 물리적인 위치를 계산해 낼 수 있다. DBMS는 내부적으로 비트의 위치를 가지고 로우의 물리적인 위치를 계산하는 함수를 지원한다.

 

비트맵 인덱스는 다중 조건을 만족하는 튜플의 개수를 계산하는 데 아주 적합하다. 이러한 현상은 비트맵 인덱스가 B+ 트리 인덱스에 비해 저장 공간이 획기적으로 줄고 키 값의 비교를 비트 연산으로 처리하므로 비교 연산도 획기적으로 줄어들기 때문이다. 그 외에 비트맵 인덱스가 가지는 장점으로 압축을 들 수 있다. 비트맵은 키 값 단위로 생성되므로 동일한 값이 반복될 확률이 높아 압축 효율도 매우 좋아진다.

 

 

B-tree와 Bitmap 구조 비교

함수 기반 인덱스

사원 테이블에서 이름이‘MIKE’로 시작하는 자료를 찾는 전형적인 방법은 Where절에 “like name='MIKE'”처럼 사용하는 것이다. NAME이라는 칼럼에 인덱스가 생성되어 있다면 옵티마이저 는 해당 인덱스를 사용해 자료를 찾을 것이다. 그런데 “like Upper(name) = 'MIKE'”처럼 조건절을 기술한다면 인덱스 칼럼에 변형이 일어나므로 옵티마이저는 인덱스를 사용하지 않고 Full Table Scan을 하게 된다.

 

그러나 함수 기반 인덱스(Function-based indexes)는 함수(function)나 수식(expression)으 로 계산된 결과에 대해 B+ 트리 인덱스나 Bit-Map Index를 생성, 사용할 수 있는 기능을 제공한 다. 함수 기반 인덱스에서 사용되는 함수는 산술식(Arithmetic expression), PL/SQL Function, SQL Function, Package, C callout이 가능하지만 동일한 입력 값에 대해 시간의 흐름에 결과 값 이 변경되는 함수에는 적용이 불가능하다. 또한 Object Type도 해당 칼럼에 정의된 method에 대 해 함수 기반 인덱스의 생성이 가능하지만 LOB, REF Type, Nested Table Column 또는 이들을 포함하고 있는 Object type에 대해서는 함수 기반 인덱스의 생성이 불가능하다.

 

비트맵 조인 인덱스

비트맵 조인 인덱스는 단일 객체로만 구성되었던 기존 인덱스와 달리 여러 객체의 구성 요소(칼럼)로 인덱스 생성이 이뤄지므로 기존의 인덱스와 테이블 액세스 방법과는 구조가 다르다.

 

비트맵 조인 인덱스의 물리적인 구조는 비트맵 인덱스와 완전히 동일하다. 단지 인덱스의 구성 칼 럼이 베이스 테이블의 칼럼 값이 아니라 조인된 테이블의 칼럼 값이라는 차이만 존재할 뿐이다. 즉, 비트맵 조인 인덱스는 기본 테이블을 기준으로 조인된 결과를 기존의 비트맵 인덱스와 같은 구조로 저장하여 카디날리티가 낮은 데이터의 액세스에 좋은 성능을 얻을 수 있게 하는 방법이다.

 

도메인 인덱스

도메인 인덱스는 오라클8i에서부터 새롭게 도입된 개념으로 개발자가 자신이 원하는 인덱스 타입을 생성할 수 있게 함으로써 인덱스 시스템에 많은 확장을 가져다주었다.

 

즉, 데이터베이스에는 아직 존재하지도 않는 새로운 구조의 인덱스 타입을 자신이 스스로 정의하여 DBMS에서 지원하는 인덱스처럼 사용할 수 있다. InterMedia text index나 오라클 9i부터 지원 되는 Context 타입 인덱스와 Catalog 타입 인덱스 등은 모두 비정형 테스트를 빠르게 검색하려고 새롭게 도입된 도메인 인덱스이다.

 

references :

- https://joosjuliet.github.io/index_guidline/ 

- http://www.dbguide.net/db.db?cmd=view&boardUid=13856&boardConfigUid=9&categoryUid=216&boardIdx=80&boardStep=1

- https://docs.oracle.com/cd/E11882_01/server.112/e40540/indexiot.htm#CNCPT1895