Index Scan

인덱스 탐색

 

데이터베이스는 인덱스를 활용하여 빠르게 데이터를 찾을 수 있다. 인덱스 탐색에는 수직적 탐색과 수평적 탐색이 있는데, 수직적 탐색을 통해 먼저 찾고자 하는 데이터의 범위를 결정한 후, 수평적 탐색을 수행하여 실제 데이터를 검색한다.

 

1. 수직적 탐색

- 인덱스에서 데이터를 찾기 위해 트리 구조를 따라 내려가는 과정

- 대표적인 인덱스 구조인 B-Tree 인덱스에서 수직적 탐색은 루트 노드에서 시작하여, 찾고자 하는 데이터에 해당하는 리프 노드에 도달할 때까지 하위 노드로 이동하는 과정

- 트리의 깊이에 비례하는 시간이 소요

 

2. 수평적 탐색

- 인덱스에서 데이터를 찾기 위해 동일한 레벨의 노드들 사이를 이동하는 과정

- B-Tree 인덱스의 경우, 리프 노드들은 연결 리스트로 구성되어 있음

- 리프 노드들 사이를 이동하며 찾고자 하는 데이터의 범위에 해당하는 모든 데이터를 검색하는 과정

- 찾고자 하는 데이터의 범위에 따라 시간 소요

 

인덱스 스캔 종류

1. Index Range Scan(index)

- 인덱스 루트 블록에서 리프 블록까지 수직적으로 탐색한 후에 리프 블록을 필요한 범위만 스캔하는 방식

- B*Tree 인덱스의 가장 일반적이고 정상적인 엑세스 방식

- 인덱스를 스캔하는 범위(Range)를 얼마만큼 줄일 수 있느냐와 테이블로 엑세스하는 횟수를 얼마만큼 줄일 수 있느냐가 중요 포인트

- 인덱스를 구정하는 선두 컬럼이 조건절에 사용되어야 Index Range Scan 사용 가능

- Index Range Scan 과정을 거쳐 생성된 결과집합은 인덱스 컬럼 순으로 정렬(sort order by 연산을 생략하거나 min/max 값을 빠르게 추출할 수 있음)

 

 

[예시]
TEST_IDX01(ID, DATE)

SELECT * FROM TEST WHERE ID = ?;

 

2. Index Skip Scan(index_ss)

- 인덱스 선행 컬럼이 조건절에 존재하지 않아도 인덱스를 활용하는 방식

- 루트 또는 브랜치 블록에서 읽은 컬럼 값 정보를 이용해 조건에 부합하는 레코드를 포함할 가능성이 있는 하위 블록만 골라서 엑세스하는 방식

- Index Skip Scan 방식은 조건절에 빠진 인덱스 선행 컬러의 Distinct  Value 개수가 적고 후행 컬럼의 Distinct Value  개수가 많을 때 유용함

 

 

[예시]
TEST_IDX02(STATUS1, STATUS2, RESULT, ...)

SELECT * FROM TEST WHERE RESULT = 'test';

SELECT * FROM TEST WHERE RESULT = ?;

두 가지 경우에 나오는 Index Scan 방식이 다른 이유는 '?'(바인딩 변수)를 사용할 경우 변수의 값을 미리 알 수 없기 때문에 인덱스를 사용하는 것이 효율적인지 옵티마이저가 판단할 수 없음. 'test'처럼 실제 값을 넣었을 때는 옵티마이저가 값을 미리 알고있기 때문에 해당 값을 사용하여 인덱스를 최적화된 방법으로 검색할 수 있음.

일부 데이터베이스 시스템은 실행 게획 생성 시점에 바인딩 변수의 값을 고려하여 최적화를 수행할 수 있는데, 이것은 '바인딩 변수 피크(바인딩 피크)'라고 한다. 바인딩 피크를 지원하는 시스템에서는 RESULT = ? 대신 RESULT = 'test'와 같이 실제 값이 들어간 형태로 최적화를 수행할 수 있다.

 

3. Index Unique Scan(index)

- 수직적 탐색만으로 데이터를 찾는 스캔 방식

- unique 인덱스를 통해 "=" 조건으로 탐색하는 경우

- 중복되지 않은 unique한 값을 "=" 조건으로 검색할 경우 해당 데이터 한 건을 찾는 순간 더 이상 탐색하지 않음

- 단 BETWEEN, LIKE, 부등호 조건으로 검색하거나 결합인덱스에 대해 일부 컬럼만으로 검색할 경우, Index Range Scan으로 처리됨

 

 

[예시]
TEST_2_PK(ID, DATE)

SELECT * FROM TEST_2 WHERE ID = ? AND DATE = ?;

SELECT * FROM TEST_2 WHERE ID = ?;

 

4. Index Full Scan(index_fs)

- 수직적 탐색 없이 인텍스 리프 블록을 처음부터 끝까지 수평적으로 탐색하는 방식

-  최적의 인덱스가 없을 때 차선으로 선택

- 인덱스 선두 컬럼이 조건절에 없으면 Table Full Scan을 고려하나, Table Full Scan보다 I/O를 줄일 수 있거나 정렬된 결과를 쉽게 얻을 수 있는 경우 Index Full Scan 선택

 

 

5. Index Fast Full Scan(index_ffs)

- Index Full Scan보다 속도가 더 향상된 것으로, 싱글 I/O 방식이 아닌 Multiblock I/O 방식으로 한번에 많은 데이터를 조회하는 방식

- 꼭 인덱스에 NOT NULL 제약이 있어야 하고, 정렬을 보장하지 않음.

 

 

6. Index Range Scan Descenging(index_desx)

- Index Range Scan과 동일한 스캔 방식으로, 인덱스를 뒤에서부터 앞쪽으로 스캔하기 때문에 내림차순으로 정렬된 결과를 얻음.

 

[예시]
TEST_IDX03(CUSTOMER_ID, DATE)

SELECT * FROM TEST WHERE CUSTOMER_ID = ? AND DATE > ? ORDER BY DATE DESC;

 

7. Index Bitmap Merge Scan(index_combine)

- 비트맵 인덱스를 사용하는 쿼리 최적화 방법으로, 여러 비트맵 인덱스를 결합하여 한 번의 쿼리에 대한 검색을 수행할 때 사용

- 주로 비트맵 인덱스가 존재하며, WHERE 절에 두 개 이상의 인덱스를 사용하는 조건이 있는 경우에 적용

- 수행 과정

• 각 비트맵 인덱스를 개별적으로 스캔하여 각가의 비트맵 결과 집합을 생성
• 각 비트맵 결과 집합에 대해 적절한 비트 연산(AND, OR..)을 수행하여 최종 비트맵 결과 집합을 생성
• 최종 비트맵 결과 집합을 기반으로 데이터를 검색하고 필요한 경우 추가적인 조건을 적용

 

---

 

Index Join

- 두 테이블을 결합할 때 인덱스를 사용하여 조인 연산을 수행하는 방법

- 힌 테이블의 행을 참조하면서 다른 테이블과의 조인 조건에 맞는 행을 찾을 때 인덱스를 사용하여 효율적으로 검색

- 조인 조건이 인덱스가 있는 컬럼에 적용되고, 인덱스를 사용할 때 성능상 이점이 있는 경우에 유용

- 수행 과정

• Nested Loop Join 알고리즘 사용 : Index Join은 기본적으로 Nested Loop Join 알고리즘을 사용
• 드라이빙 테이블 결정 : 드라이빙 테이블은 주로 작은 테이블이나 인덱스를 가장 효율적으로 사용할 수 있는 테이블로 선택
• 드라이빙 테이블에서 행 읽기
• 인덱스를 사용하여 드리븐 테이블의 관련 행 찾기
• 드리븐 테이블의 데이터 엑세스
• 결과 생성

 

 

참고

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