[DB] Index Scan의 종류

해당 포스팅은 오라클 성능 고도화 원리와 해법2의 내용을 기반으로 작성되었습니다.

1. Index의 구조

Index의 Scan에 대해 언급하기 전에, 기본적인 Index의 구조에 대해 알아봅시다.

• root block, branch block, leaf block으로 구분
• root, branch block
  • key value와 하단 노드의 data block address를 가짐
• leaf block
  • 인덱스 key col과 실제 테이블의 레코드 주소인 rowid를 가짐
  • 항상 key col을 기준으로 정렬되어 있음 → range scan 가능
  • key col이 동일할 경우 rowid를 기준으로 정렬됨

위의 구조에 나타난 lmc는 key value를 가지지 않는 특별한 엔트리로, 가장 왼쪽에 위치한 블럭을 뜻합니다.

또한, 인덱스를 탐색하기 위해서는, 수직적 탐색과 수평적 탐색 단계가 필요합니다.

인덱스의 root block에서부터 시작해, branch block를 거쳐 탐색에 적절한 leaf block을 찾아 내려가는 과정을 수직적 탐색, 해당 leaf block을 시작으로 좌우로 스캔해 적절한 record를 찾는 과정을 수평적 탐색이라고 칭합니다.

2. Index Range Scan

• root block에서 leaf block까지 수직적으로 탐색한 후 leaf block을 필요한 범위만 스캔하는 방식
• B*Tree index의 가장 일반적이고 정상적인 액세스 방식
• Range를 얼마나 줄이는지, table access 횟수를 얼마나 줄일 수 있는지가 튜닝의 핵심임
• 인덱스를 구성하는 선두 컬럼이 조건절에 사용되어야 함
  • 그렇지 않다면 옵티마이저는 Table full scan을 선택함
  • 정렬을 생략하거나 I/O를 보다 줄일 수 있다면 Index full scan을 사용함
• 결과집합은 인덱스 컬럼 순으로 정렬된 상태임
  • order by 처리 생략하거나 min, max 값을 빠르게 가져올 수 있음

3. Index Full Scan

• 수직적 탐색없이 leaf block을 처음부터 끝까지 수평적으로 스캔하는 방식
• 보통 최적의 인덱스가 없을 경우 선택됨
• 실제로는 첫 번째 leaf block으로 찾아가기 위한 수직적 탐색이 일어남 (실질적인 탐색은 X)

4. Index Unique Scan

• 수직적 탐색만으로 데이터를 찾는 스캔 방식
• unique index를 이용해 = 조건으로 탐색하는 경우 작동함
• unique index가 존재하는 칼럼에 대해서는 DBMS 차원에서 정합성이 관리됨
  • 따라서 =을 이용해 데이터를 찾으면 그 뒤에는 데이터가 없음이 보장됨으로 바로 스캔을 멈출 수 있음
• Range Scan으로 처리되는 경우
  • =이 아닌 범위검색 조건(between, 부등호, like)일 경우
  • unique index가 결합 인덱스인데 일부 컬럼에 대해서만 검색할 경우

보통 index를 제대로 타기 위해서는 index를 구성하는 선두 컬럼이 조건절에 명시되어야 효과적으로 범위가 필터링되어 제 성능을 발휘합니다. 선두 컬럼이 명시되지 않을 경우 옵티마이저는 인덱스 대신 풀스캔을 택하곤 하죠.

하지만 오라클에서 선두 컬럼이 조건절에 사용되지 않았을 때도 인덱스를 활용할 수 있도록 새로운 방법을 선보였습니다.

5. Index Skip Scan

• 인덱스를 구성하는 선두 컬럼이 조건절에 사용되지않았을 때도 인덱스를 활용하는 스캔 방식
• root, branch block에서 읽은 컬럼 정보를 이용해 해당 레코드를 포함할 가능성이 있는 leaf block을 골라서 access함
• 조건절에 빠진 인덱스 선두 컬럼의 Distinct value 개수가 적고 후행 컬럼의 Distinct value 개수가 많을 때 유용함

(성별, 연봉)으로 구성된 인덱스가 다음과 같이 구성되어있다고 가정해봅시다.

먼저, 아래 쿼리와 같이 인덱스에 나타나는 모든 칼럼이 조건절에 존재했을 때를 가정해봅시다.

select * from 사원 where 성별 = '남' and 연봉 between 2000 and 4000;

위와 같은 쿼리를 수행하기 위해, Index Range Scan이 아래 순서대로 진행될 것입니다.

1. root block의 레코드를 확인해 성별이 남이고 연봉이 조건을 만족하는 첫 번째 레코드를 찾음
2. 3번 레코드의 DBA를 이용해 3번 leaf block으로 이동함
3. Range Scan을 하며 leaf block을 순회하다가, 조건이 만족하지 않는 레코드를 만나면 스캔을 멈춤

두 번째로, 아래 쿼리와 같이 인덱스를 구성하는 선두 컬럼이 조건절에 존재하지 않을 때를 가정해봅시다.

select * from 사원 where 연봉 between 2000 and 4000;

1. 1번 leaf block을 방문함
   연봉 조건은 부합하지 않으나, ‘남’보다 작은 성별이 존재할 가능성이 있기 때문
2. 3번 leaf block을 방문함
   연봉 조건이 부합함
3. 5번 leaf block을 방문함
   연봉 조건은 부합하지 않으나, ‘남’과 ‘여’ 사이에 다른 성별이 존재할 가능성이 있기 때문
4. 6번 leaf block을 방문함
   연봉 조건이 부합함
5. 9번 leaf block을 방문함
   연봉 조건은 부합하지 않으나, ‘여’보다 큰 성별이 존재할 가능성이 있기 때문

이렇듯, Index Skip Scan은 다른 Scan방식처럼 수평적 탐색을 하지 않고, 상위 block에서 다음으로 이동할 leaf block을 결정합니다. 이 때, 첫 번째, 마지막 leaf block은 반드시 방문합니다.

6. Index Fast Full Scan

• 인덱스 트리 구조를 무시하고 segment 전체를 multiblock read 방식으로 스캔하는 방식
• Index Full Scan보다 빠름

아래는 논리적 순서로 배치된 블록 구조입니다. Index Full Scan의 경우, root → branch1 → leaf1 → … → leaf8 순서대로 블록을 읽어들입니다.

위의 구조를 물리적 순서로 다시 배치한 블록 구조입니다. Index Fast Full Scan의 경우, leaf1 → leaf2 → leaf8 → leaf3 → leaf7 → leaf6 → leaf4 → leaf5 순서대로 블록을 읽어들입니다.

이 과정에서 root, branch1도 읽어들이나, 결과적으로 필요하지 않은 블록이므로 버리게 됩니다.

• 디스크로부터 대량의 인덱스 블록을 읽어야 하는 경우 유용함
• leaf node의 양방향 연결 리스트를 이용하지 않기 때문에 결과값이 정렬되어 있지 않음
• 사용되는 모든 컬럼이 인덱스 컬럼에 포함되어 있을 때만 사용 가능
• 인덱스가 파티션 되어 있지 않더라도 병렬 쿼리가 가능함
• 버퍼 캐시 히트율이 낮아 디스크 I/O가 많이 발생할 때 유리함
• 컬럼 개수가 많아 테이블보다 인덱스 크기가 현저히 작은 상황에서 유리함

	Index Full Scan	Index Fast Full Scan
스캔 범위	인덱스 구조 따라 스캔	세그먼트 전체 스캔
결과집합 순서 보장	O	X
Block I/O	Single Block	Multiblock
병렬스캔	X (파티션 되어 있지 않다면)	O
인덱스에 포함되지 않은 컬럼 조회	사용 가능	사용 불가

7. Index Range Scan Descending

• Index Range Scan과 동일하나, 뒤에서부터 탐색해 내림차순으로 정렬된 결과를 얻는 스캔 방식
• 옵티마이저가 알아서 인덱스를 거꾸로 읽는 plan을 수립함
• max 값을 구하는 경우에도 이용함