[DB] 인덱스란? - (3) 인덱스 스캔 방식 [개념]

이전 글들에서 DB 인덱스의 개념과 장단점, 쓰는 이유와

 

인덱스를 구성하고 있는 구조 등에 대해 알아봤다.

 

(1편, 2편)

 

 

이번 글에서는 그러한 인덱스를 사용하여

 

원하는 데이터를 찾아가는 과정에서

 

어떠한 데이터 스캔 방식을 사용하는지에 대해 알아본다.

 

 

완전히 동일하지는 않지만 일맥상통한 비유를 들자면,

 

Searching Algorithm에서 Linear Search, Binary Search 등을

 

떠올리면 어느 정도 감이 잡힐 것이다.

 

 

이번 글은 아래 글들을 참고하여 작성했다.

 

• [Data On-AIR] 인덱스 기본 원리
• [지식 덤프] SQL Full table scan
• [Naver D2] 성능 향상을 위한 SQL 작성법

 

---

 

인덱스 스캔(Index Scan)이란?

이전 글들을 보면 알겠지만,

 

인덱스라는 녀석도 결국 하나의 Mapping 테이블,

 

정확히는 아래처럼 Tree 구조로 데이터가 저장되어있다.

 

 

(무슨 트리인지는 대충 넘기고 구조만 보자, 구조만)

 

(구조 관련 자세한 내용은 이전 2편 글을 참고)

 

출처) https://dataonair.or.kr/db-tech-reference/d-guide/sql/?uid=366&mod=document&pageid=1

 

그렇기 때문에 이러한 트리 구조에서

 

어떻게 하면 가장 효율적인 방법으로

 

원하는 인덱스를 찾을 수 있을 지에 대한 내용이 바로

 

인덱스 스캔(Index Scan)이다.

 

 

인덱스 스캔 방식들에 대해 자세히 알아보기 전에,

 

위 그림을 토대로 러프하게 핥아보고(?) 가자.

 

 

인덱스 탐색 과정은 크게 아래 두 가지로 나눌 수 있다.

 

'수직적 탐색'과 '수평적 탐색'.

 

 

먼저 '수평적 탐색'은 트리의 가장 아래에 있는

 

리프 노드끼리 연결된 순서에 따라

 

좌에서 우, 또는 우에서 좌로 스캔하기 때문에

 

'수평적'이라고 표현한다.

 

 

이러한 '수평적 탐색'을 위한 시작 지점을 찾는 과정을

 

'수직적 탐색'이라고 하며,

 

루트 노드에서 리프 노드까지 아래로 진행하기 때문에

 

'수직적'이라고 표현한다.

 

 

그럼 위 그림에서 키 값이 51인 레코드를 찾아보자.

 

 

1. 먼저 루트 블록에서 51(키 값)이 속한 블록을 찾는다.

 

2. 3번 블록에 속하므로 3번 블록으로 이동한다.

 

3. 3번 블록에서 다시 51(키 값)이 속한 블록을 찾는다.

 

4. 9번 블록에 속하므로 9번 블록으로 이동한다.

 

5. 9번 블록은 리프 블록이므로 여기서 원하는 값을 찾거나 못 찾거나 둘 중 하나다.

 

6. 다행히 첫 번째 레코드에 51(키 값)이 존재하므로 함께 저장된 RowID(value 값)을 분석한다.

 

이 RowID를 분해해 보면, Object 번호 / 데이터 파일 번호 / 블록 번호 / 블록 내 위치 정보

 

등을 알 수 있다.

 

7. 위에서 얻은 정보를 통해 실제 테이블에서 원하는 레코드를 찾아낸다.

 

 

사실 위 7번에서 끝은 아니다.

 

 

위 인덱스들이 Unique 한 인덱스가 아닌 이상,

 

키 값이 51인 레코드가 더 있을 수 있기 때문이다.

 

 

따라서 9번 블록 내에서 레코드 하나를 더 읽어

 

키 값이 51인 레코드가 또 있는지 확인하며,

 

51인 레코드가 더 이상 나오지 않을 때까지 스캔하며

 

7번의 실제 테이블 접근 단계를 반복한다.

 

 

만약 9번 블록을 다 읽었는데도 계속 51이 나온다면,

 

10번 블록으로 넘어가서 스캔을 계속한다.

 

 

간단하게 핥아보자고 해놓고 또 길어졌다.

 

Index Scan vs Full Table Scan

본격적으로 알아보기 전,

 

진짜 진짜 마지막으로 하나만 더 짚고 넘어가자.

 

 

잘 생각해보면 인덱스라는 녀석이 탄생하기 전에는

 

DB의 전체 테이블을 처음부터 쭈욱 읽어야 했을 것이다.

 

 

이것이 무조건 좋지 않은 방법일까?

 

답은 '아니요'다.

 

 

어떠한 테이블의 row의 개수가 10,000개이고,

 

테이블 내 1 block == 10 row 이면서

 

인덱스 column의 분포도는 10%,

 

인덱스 row에 대응하는 테이블의 row는

 

각 block에 하나씩만 존재(최악의 경우)한다고 가정해보자.

 

 

(여기서 '분포도'란, 테이블에 어떠한 컬럼이 평균적으로 분포되어 있는 정도,

 

즉, [데이터 별 평균 row 수] / [테이블의 총 row 수] * 100 = 1 / [column 값의 종류] * 100이다.

 

ex. 5개의 사업장을 가진 회사의 '사업장' column 값의 종류는 5이므로,

 

'사업장' 컬럼의 분포도는 1 / 5 * 100 = 20%이다)

 

 

먼저 아래와 같은 Full Table Scan의 수행 방식을 보자.

출처) http://jidum.com/jidums/view.do?jidumId=183

먼저, DB 테이블의 첫 번째 블록부터 순서대로 접근한다.

 

테이블의 전체 블록이 모두 접근될 때까지 계속 수행한다.

 

 

그렇기 때문에 접근하는 총 block의 수,

 

즉, Scan Cost는 아래와 같이 계산된다.

 

 

테이블의 총 row 수 / 블록 내의 row 수 = 10,000 / 10 = 1,000개

 

 

다음으로 Index Scan의 수행 방식을 보자.

출처) http://jidum.com/jidums/view.do?jidumId=183

먼저, 이전에 알아보았던 B-Tree 구조를 이용하여

 

특정 조건을 만족하는 첫 번째 인덱스 row에 접근한다.

 

 

해당 인덱스 row에 있는 RowID 정보를 이용하여

 

대응되는 실제 테이블의 row에 접근한다.

 

 

그다음, 인덱스 row가 끝날 때까지

 

인덱스 row를 차례대로 스캔하며

 

대응되는 실제 테이블의 row를 찾는 작업을 반복한다.

 

 

이 방식의 Scan Cost는 아래와 같이 계산된다.

 

 

(1) 총 인덱스 수 = 테이블의 총 row 수 * 인덱스 column 분포도 = 10,000 * 10% = 1,000개

 

(2) 인덱스에 대응하는 테이블의 row가 각 block 당 1개이므로, 1,000개의 블록 접근 필요

 

 

위의 계산을 통해, 두 경우 모두 1,000개의 블록 접근이 필요하기 때문에

 

인덱스 사용의 손익 분기점은 10% 임을 알 수 있고,

 

칼럼의 분포도가 10~15% 이상인 경우는

 

인덱스의 RowID를 통한 Random Access 비용 때문에

 

Table Full Scan이 더 좋은 것을 알 수 있다.

 

 

이러한 이유들 때문에 인덱스는 반드시

 

적은 양의 데이터를 조회할 때에 유리하고,

 

그 외에는 Full Scan이 더 유리하다.

 

 

위 내용 관련해서 아래 글을 참고하면 더욱 이해가 쉽다.

• [mysql] 조회, Index냐 Full Scan이냐

 

---

 

 

아.... 

 

글이 또 너무 길어졌다.

 

 

다음 글에서는 진짜 인덱스 스캔 종류에 대해 알아본다..

 

 

끝!