[데이터베이스] 9. 인덱스와 인덱스 구조별 비용 추정

인덱스

인덱스란 검색키를 기반으로 효율적인 질의를 돕는 메커니즘이다. 한 테이블의 특정 필드를 인덱스로 설정할 경우 전체 테이블을 full scan하는 것이 아닌 인덱스의 검색키 만으로 스캔하여 빠르다. 다만, 인덱스를 사용할 경우 공간적인 오버헤드가 약간 증가한다. 그리고, 갱신 작업 또한 약간의 시간적 오버헤드가 발생한다. 기존의 경우 해당 테이블의 실제 데이터만 수정하면 되지만, 인덱스가 있을 경우 인덱스의 검색키 또한 바꿔야 하며 그에 따라 인덱스의 구조가 변경될 수 있기 때문이다.

 

파일 구조에 따른 인덱스의 종류

B 트리 인덱스

B 트리의 구조를 띄는 인덱스로 하나의 노드에 2개 이상의 엔트리가 존재한다. 해당 구조의 특징은 아래와 같다.

• 범위 탐색에 유리하다.
• 성능은 트리의 높이에 따라 결정된다. (낮을 수록 유리)
• 리프 페이지는 앞, 뒤 리프 페이지와 연결되어 있다.

 

해시 인덱스

인덱스 파일을 해시 구조로 관리하는 방식이다. 특징은 다음과 같다.

• Equality 검색에 유리하다. (column = 'value')
• <,>,like, in과 같은 범위 탐색 같은 연산은 매우 느리다.

 

 

 

데이터 레코드 정렬에 따른 인덱스의 종류 - 클러스터 인덱스와 넌클러스터 인덱스

우선 인덱스를 설정할 경우, 데이터 엔트리는 인덱스의 키 중심으로 정렬된다. 그리고 클러스터, 넌클러스터는 데이터 레코드의 정렬과 관계있다. 클러스터 인덱스의 경우 데이터 레코드의 저장 순서가 정렬된다. 반대로 넌클러스터 인덱스의 경우 데이터 레코드의 정렬 과정이 없다.

트리 구조의 클러스터, 넌클러스터 인덱스

보통 상용 DB에서 기본키는 자동적으로 클러스터 인덱스로 설정된다.

 

---

비용 추정: 파일 구조별 연산 비용

 

아래는 비용 추정을 위한 기본적인 용어와 가정이다.

 

데이터 엔트리의 종류

• Alternative 1. 데이터 엔트리 == 데이터 레코드
• Alternative 2. 데이터 엔트리 == (key, record id)
• Alternative 3. 데이터 엔트리 == (key, List<record id>)

기본 용어

• B: 데이터 페이지의 수
• R: 페이지 내 존재하는 레코드의 수
• D: 디스크 페이지 I/O 평균 비용

파일 구조별 가정

• Heap file: 가장 기본적인 파일 구조로, 같은 값은 한개만 갖는다고 가정한다.
• Sorted file: 정렬된 파일 구조로 특정 레코드 삭제 후 파일 컴팩션 작업이 이루어진다.
• Hash: 전체 버킷(페이지)의 0.8의 점유율을 유지한다. (오버플로우 방지)
• Tree: 전체 중 0.67의 점유율을 유지한다. (트리 구조 변경 방지)
• Alt 2, Alt 3에서 데이터 엔트리의 수는 데이터 레코드 수의 0.1이다. 

 

위로 인한 파일 구조별 특징

• Heap file: 전체 데이터 페이지 수는 B이다.
• Clustered tree index: 전체 데이터 페이지 수는 1.5B이다. 
• Non-clustered tree index: 실제 데이터가 존재하는 데이터 엔트리, 레코드의 수는 B*R이다. 전체 데이터 엔트리 페이지의 수는 1.5*B*0.1=0.15B 이다.
• Hash: 실제 데이터가 존재하는 데이터 엔트리, 레코드의 수는 B*R이다. 전체 데이터 엔트리 페이지의 수는 1.25*B*0.1=0.125B 이다.

파일 구조 별 특정 연산에 대한 처리 비용

위로 인해 알 수 있는 점

• 클러스터 트리 인덱스는 범위 탐색과 스캔에 다른 인덱스 보다 유리하다.
• 넌클러스터 트리 인덱스는 동일성 검색에 유리하고, 범위 탐색에는 매우 나쁜 성능을 보인다.
• 넌클러스터 해시 인덱스는 동일성 검색에 매우 유리하다.

기본적으로 넌클러스터 구조의 경우 같은 페이지 내에 비슷한 값, 근처 값들이 존재할 확률이 거의 없으므로 엔트리마다 새로운 페이지를 접근해야 하므로 범위 탐색 시 디스크 IO 비용이 매우 크다.

 

---

Index-Only Plans

특정 필드를 검색키로 사용할 경우 일부 질의는 실제 데이터 페이지의 접근 없이 인덱스만 조회하여 결과를 도출할 수 있다.

 

예시 1.

SELECT D.mgr FROM Dept D, Emp E
WHERE D.dno = E.dno

예를 들어, 위 쿼리에서 E.dno 인덱스가 존재할 경우 Employee 테이블에 대해선 실제 다른 필드의 내용이 필요 없으므로 Employee 테이블의 데이터 레코드의 접근 없어 매우 빠른 조회가 가능하다.

 

예시 2.

SELECT AVG(E.sal) FROM Emp E
WHERE (E.age = 25) AND (E.sal BETWEEN 3000 AND 5000)

위에는 <E.age, E.sal> 혹은 <E.sal, E.age> 인덱스가 존재할 경우 마찬가지로 데이터 레코드의 접근이 없어 매우 빠르다. 하지만, 여기서 성능을 더 높이기 위해서는 <E.age, E.sal> 인덱스를 사용하는게 좋다. 이렇게 될 경우 age, sal 순으로 정렬되어 나이가 25인 페이지에서 3000~4000을 연속적으로 읽으면 된다.

 

만약, <E.sal, E.age>로 설정했다면, 월급이 3000~4000인 레코드를 전부 읽고 이중 나이가 25인 부분만 다시 한번 더 추출해야 한다. 이는 더 많은 페이지 접근이 요구될 수도 있다.

 

 

인덱스 설계 가이드

위의 내용을 기반으로 인덱스를 설계하는 대략적인 가이드는 아래와 같다.

• WHERE 절에 존재하는 필드는 인덱스의 후보이다.
• "=" 조건은 해시 혹은 넌클러스터 트리 인덱스가 유리하다.
• 범위 탐색은 클러스터 트리 인덱스가 유리하다.
• WHERE 절에 여러 필드에 대한 조건이 존재할 경우 복합 검색키가 고려 대상이다.
• 중요한 쿼리에 대해 Index-only 플랜을 사용하는 것도 하나의 방법이다.
• 최대한 많은 쿼리, 자주 쓰이는 쿼리에 인덱스, 특히 클러스터 인덱스를 설정하는게 매우 중요하다.
• 중복이 적고, selectivity가 낮을 수록 인덱스에 적합한 필드이다.

selectivity란 데이터에서 특정 값을 얼마나 잘 선택할 수 있는지를 의미한다. 예를 들어, 학생 테이블에 10명의 학생이 존재하고 남녀 성비는 5:5이며 모두 고유한 학번이 존재할 경우 selectivity는 아래와 같다.

• SELECT * FROM STUDENTS WHERE '성별' LIKE '남성' : 5/10 * 100 = 50%
• SELECT * FROM STUDENTS WHERE '학번' LIKE '1234' : 1/10 * 100 = 10%