1. 인덱스 구조
가. 인덱스 기본 구조(B*Tree)
- B*Tree 인덱스는 나뭇잎으로 무성한 나무를 뒤집어 놓은 듯한 모습
- Root 에서 Leaf 블록 까지 거리를 깊이(Height)라고 부르며, 인덱스의 반복적 탐색시 성능에 영향을 미침
- Root/Branch 블록은 각 하위 노드들의 데이터 값 범위를 나타내는 키 값과, 그 키 값에 해당하는 블록을 찾는 데 필요한 주소 정보를 가짐
- Leaf 블록은 인덱스 키 값고, 그 키 값에 해당하는 테이블 레코드를 찾아가는데 필요한 주소 정보(ROWID)를 가짐
- 같은 키 값일 때 ROWID 순으로 정렬 됨
- 인덱스 키(Key)값 순으로 정렬돼 있기 때문에 Range Scan 이 가능하고, 정방향/역방향(ASC/DESC) 스캔이 가능 하도록 양방향 연결 리스트 구조임
{tip:title=NULL}
- Oracle 은 인덱스 구성 칼럼이 모두 NULL 인 레코드는 인덱스에 저장 안함 (NULL 은 저장시 맨뒤)
- SQL Server 는 인덱스 구성 칼럼이 모두 NULL 인 레코드도 인덱스에 저장 (NULL 은 저장시 맨앞)
{tip}
나. 인덱스 탐색
- 수평적 탐색 - Leaf 블록에 젖아된 레코드끼리 연결된 순서에 따라 스캔
- 수직적 탐색 - 수평적 탐색을 위한 시작 지점을 찾는 과정 (Root 블록 → Branch 블록 → Leaf 블록)
- 값이 53인 레코드 찾기
- Root 블록에서 53이 속한 키 값을 찾음 (두번째 레코드 : 3번 블록)
- 3번 Branch 블록에서 다시 53이 속한 키 값을 찾음 (첫번째 레코드 : 9번 블록)
- 9번 Leaf 블록에서 값을 찾으며, 존재할 경우 해당 ROWID를 이용해 테이블 블록을 찾음
- 테이블 블록에서 레코드를 찾음 (Unique Index 가 아닌 경우 다음 레코드 까지 확인)
2. 다양한 인덱스 스캔 방식
가. Index Range Scan
- Index Root 블록에서 Leaf 블록 까지 수직 탐색 후, Leaf 블록을 필요한 범위(Range)만 스캔
- B*Tree 인덱스의 가장 일반적 액세스 방식, 항상 빠른 속도를 보장하지 않음 (Range 줄이기, Table 액세스 줄이기 필요)
- 인덱스를 구성하는 선두 칼럼이 조건절에 사용되어야 한다.
- 인덱스 칼럼 순으로 정렬된 특성을 이용하여, SORT ORDER BY 연산을 생략 하거나 MIN/MAX 값을 빠르게 추출 가능
SQL> create index emp_deptno_idx on emp(deptno);
SQL> set autotrace traceonly explain
SQL> select * from emp where deptno = 20;
Execution Plan ------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (TABLE)
2 1 INDEX (RANGE SCAN) OF 'EMP_DEPTNO_IDX' (INDEX)
StmtText
-------------------------------------------------------------
|--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000]))
|--Index Seek(OBJECT:([..].[dbo].[emp].[emp_deptno_idx]), SEEK:([deptno]=20) ORDERED FORWARD)
|--RID Lookup(OBJECT:([..].[dbo].[emp]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)
나. Index Full Scan
- 수직 탐색 없이 Index Leaf 블록을 처음부터 끝까지 수평 탐색 (사실은 첫 번째 Leaf 블록을 찾아가기 위한 수직 탐색 1회 발생)
- 데이터 검색을 위한 최적의 인덱스가 없을 때 차선으로 선택 됨
SQL> create index emp_idx on emp (ename, sal);
SQL> set autotrace traceonly exp
SQL> select * from emp 2 where sal > 2000 3 order by ename;
Execution Plan ----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (TABLE)
2 1 INDEX (FULL SCAN) OF 'EMP_IDX' (INDEX)
StmtText -------------------------------------------------------------
|--Filter(WHERE:([..].[dbo].[emp].[sal]>(2000.)))
|--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000]))
|--Index Scan(OBJECT:([..].[dbo].[emp].[emp_idx]), ORDERED FORWARD)
|--RID Lookup(OBJECT:([..].[dbo].[emp]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)
- 인덱스 스캔 단계에서 대부분 레코드를 필터링 하고 일부에 대해서 테이블 액세스가 발생하는 경우라면 Table Full Scan 대신 사용할 수 있음
SQL> select * from emp where sal > 5000 order by ename;
Execution Plan --------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (TABLE)
2 1 INDEX (FULL SCAN) OF 'EMP_IDX' (INDEX)
- Index Full Scan 은 Index Range Scan 과 마찬가지로 결과 집합이 인덱스 칼럼 순으로 정렬 됨
SQL> select /*+ first_rows */ * from emp
2 where sal > 1000
3 order by ename;
Execution Plan --------------------------------------------------
0 SELECT STATEMENT Optimizer=HINT: FIRST_ROWS
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (TABLE)
2 1 INDEX (FULL SCAN) OF 'EMP_IDX' (INDEX)
- first_rows(fastfirstrow) 힌트에 의해서 옵티마이저가 SORT ORDER BY 연산을 생략할 목적으로 Index Full Scan 선택
- 전체 집합 중 처음 일부만을 빠르게 리턴할 목적의 선택, 집합을 끝까지 Fetch 할 경우 Full Table Scan 보다 비효율이 됨
다. Index Unique Scan
- 수직 탐색만으로 데이터를 찾는 스캔, Unique Index 를 = 조건으로 탐색하는 경우에 작동
SQL> create unique index pk_emp on emp(empno);
SQL> alter table emp add 2 constraint pk_emp primary key(empno) using index pk_emp;
SQL> set autotrace traceonly explain
SQL> select empno, ename from emp where empno = 7788;
Execution Plan -----------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP'
2 1 INDEX (UNIQUE SCAN) OF 'PK_EMP' (UNIQUE)
StmtText
-------------------------------------------------------------
|--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000]))
|--Index Seek(OBJECT:([..].[dbo].[emp].[pk_emp]), SEEK:([empno]=7788) ORDERED FORWARD)
|--RID Lookup(OBJECT:([..].[dbo].[emp]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)
라. Index Skip Scan
- 인덱스 선두 칼럼이 조건절에 빠졌어도 인덱스를 활용하는 새로운 스캔 방식 (9i)
- Root 또는 Branch 블록에서 읽은 칼럼 값 정보를 이용해 조건에 부합하는 레코드를 포함할 "가능성이 있는" 하위 블록만 골라서 액세스
- 조건절에 빠진 인덱스 선두 칼럼의 Distinct Value 개수가 적고, 후행 칼럼의 Distinct Value 개수가 많을 때 유용 함
SQL> select * from 사원 where 연봉 between 2000 and 4000;
Execution Plan --------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS
1 0 TABLE ACCESS (BY INDEX ROWID) OF '사원' (TABLE)
2 1 INDEX (SKIP SCAN) OF '사원_IDX' (INDEX)
Index Skip Scan에 의존하는 대신, 아래와 같이 성별 값을 In-List로 제공해 주면 어떨까?
SQL> select * from 사원 2 where 연봉 between 2000 and 4000 3 and 성별 in ('남', '여')
Execution Plan --------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS 1 0 INLIST ITERATOR
2 1 TABLE ACCESS (BY INDEX ROWID) OF '사원' (TABLE)
3 2 INDEX (RANGE SCAN) OF '사원_IDX' (INDEX)
- INLIST ITERATOR : 조건절 In-List에 제공된 값의 종류만큼 인덱스 탐색을 반복 수행
- Index Skip Scan 대신 적용 가능
마. Index Fast Full Scan
- Index Full Scan 보다 빠름 (Multiblock Read 방식 스캔)
바. Index Range Scan Descending
- Index Range Scan 과 동일 (인덱스를 뒤에서 앞으로 스캔, 내림차순)
SQL> select * from emp 2 where empno is not null 3 order by empno desc
Execution Plan -------------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (TABLE)
2 1 INDEX (RANGE SCAN DESCENDING) OF 'PK_EMP' (INDEX (UNIQUE))
StmtText -------------------------------------------------------------
|--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000]))
|--Index Scan(OBJECT:([..].[dbo].[emp].[pk_emp]), ORDERED BACKWARD)
|--RID Lookup(OBJECT:([..].[dbo].[emp]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)
- MAX 값 구하기 : 인덱스를 뒤에서 부터 한 건만 읽고 멈춤
SQL> create index emp_x02 on emp(deptno, sal);
SQL> select deptno, dname, loc
2 ,(select max(sal) from emp where deptno = d.deptno)
3 from dept d
Execution Plan -------------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS
1 0 SORT (AGGREGATE)
2 1 FIRST ROW
3 2 INDEX (RANGE SCAN (MIN/MAX)) OF 'EMP_X02' (INDEX)
4 0 TABLE ACCESS (FULL) OF 'DEPT' (TABLE)
3. 인덱스 종류
가. B*Tree 인덱스
- Unbalanced Index
- 다른 Leaf 블록에 비해 Root 블록과의 거리가 더 멀거나 가까운 Leaf 블록은 생길 수 없음
- B*Tree 의 'B' 는 'Balanced' 의 약어
- 어떤 값으로 탐색 하더라도 읽는 블록 수가 같음 (Root ~ Leaf 의 높이(Height)가 동일)
- Index Skew
- Index Fragmentation에 의한 Index Skew 또는 Sparse 현상이 생길 수 있음 (인덱스 스캔 효율이 나빠 짐)
- Index Skew : 인덱스 엔트리가 왼쪽 또는 오른쪽에 치우치는 현상 (대량 Delete 작업 등)
- Oracle : 비워진 인덱스 블록에 해당하는 값이 들어오면 재사용 되지만, 다시 채워질 때까지 효율이 낮음
- SQL Server : 비동기 방식으로 빈 페이지를 정리하는 별도 쓰레드가 존재 (Ghost 레코드 마킹 → 레코드 제거 → 빈 페이지 제거)
- Index Sparse
- 인덱스 블록 전반에 걸쳐 밀도(density)가 떨어지는 현상
- 100만 건 중 50만 건을 지우고 나서도 스캔한 인덱스 블록 수가 똑같이 2,001개
SQL> create table t as select rownum no from big_table where rownum <= 1000000 ;
SQL> create index t_idx on t(no) ;
SQL> select /*+ index(t) */ count(*) from t where no > 0;
COUNT(*)
----------
1000000
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
2001 consistent gets ... ......
SQL> delete from t where mod(no, 10) < 5 ;
500000 행이 삭제되었습니다.
SQL> commit;
SQL> select /*+ index(t) */ count(*) from t where no > 0;
COUNT(*)
----------
500000
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
2001 consistent gets ... ......
- 지워진 자리에 해당하는 새로운 값이 입력되면 그 공간은 재사용 되지만, 인덱스 효율이 낮은 문제
- 지워진 자리에 새로운 값이 입력되지 않으면 영영 재사용되지 않을 수 있음, 인덱스 공간 사용량이 계속 커지는 현상
- 인덱스 재생성
- Fragmentation 때문에 인덱스 크기가 계속 증가하고 스캔 효율이 나빠지면 인덱스를 재생성 하거나 DBMS 기능을 이용해 빈 공간을 제거
- DML 성능 저하 유발 하는 인덱스 분할을 예방하기 위해 인덱스 블록에는 어느 정도 빈공간은 필요
- 어느 정도 빈공간도 언젠가 다 채워지므로, 적당한 시점마다 재생성 작업이 필요
- 인덱스 재생성 작업의 시간과 부하도 무시할 수 없으므로, 아래와 같은 예상 효과가 확실 할 때 시행
- 인덱스 분할에 의한 경합이 현저히 높을 때
- 자주 사용되는 인덱스 스캔 효율을 높이고자 할 때. (NL Join 에서 반복 액세스 되는 인덱스 높이가 증가 했을 때)
- 대량의 DELETE 작업을 수행한 이후 다시 레코드가 입력되기 까지 오랜 기간이 소요될 때
- 총 레코드 수가 일정한데도 인덱스가 계속 커질 때
나. 비트맵 인덱스
- 상품 테이블에 10개 레코드 존재, 색상은 RED, GREEN, BLUE 입력 (8번 상품에는 색상 미입력)
- 부정형 조건도 가능, NULL 조건도 가능
- Distinct Value 개수가 적을 때 저장효율이 매우 좋음
- Random 액세스 발생 측면에서는 B*Tree 인덱스와 같고, 단독 비트맵 인덱스는 쓰임새가 안좋음
- 여러 비트맵 인덱스 적용시 대용량 데이터 검색 성능 향상 (여러 개 비트맵 인덱스로 Bitwise 연산 수행)
select 지역, sum(판매량), sum(판매금액)
from 연도별지역별상품매출
where (크기 = 'SMALL' or 크기 is null)
and 색상 = 'GREEN'
and 출시연도 = '2010'
group by 지역
- 여러 인덱스를 동시에 활용할 수 있는 장점 때문에 정형화 되지 않은 임의 질의가 많은 환경에 적합 (대용량 DW, OLAP)
- Lock 에 의한 DML 부하가 높음 (레코드 1개 변경시 해당 비트맵 범위에 속한 코든 레코드에 Lock 걸림)
다. 함수기반 인덱스
- Function Based Index, FBI
- 칼럼에 특정 함수를 적용한 값으로 B*Tree 인덱스 생성
select * from 주문 where nvl(주문수량, 0) < 100
create index emp_x01 on emp( nvl(주문수량, 0) );
- 주문수량 칼럼에 인덱스가 있어도 칼럼가공으로 인해 정상적 인덱스 사용 불가능
- NVL(주문수량, 0) 로 FBI 생성하면 인덱스 사용 가능
- DML 시 함수 수행 부하가 있음
라. 리버스 키 인덱스
- 순차적으로 증가되는 일련번호나 주문일시 같은 칼럼의 인덱스는 가장 오른쪽 Leaf 블록에만 데이터가 쌓임
- Right Growing (Right Hand) 인덱스
- 동시 INSERT 가 심할 때 인덱스 블록 경합을 일으켜 TPS 를 감소 시킴, 이에 대한 해결책
create index 주문_x01 on 주문( reverse(주문일시) );
- 순차적 입력 값을 거꾸로 변환해서 저장하면, 데이터가 고르게 분포하게 됨 (인덱스 블록 경합 해소)
- '=' 조건 검색만 가능 ('!=', 'BETWEEN', 'LIKE' 같은 범위 검색 불가)
마. 클러스터 인덱스
- 클러스터 테이블 (인덱스 클러스터, 해시 클러스터) 중 인덱스 클러스터와 관련 있음
- 인덱스 클러스터 테이블은 클러스터 키(DEPTNO)값이 같은 레코드가 한 블록에 모이도록 저장 (혹은 블록을 클러스터 체인 연결)
- 여러 테이블 레코드가 물리적으로 같은 브록에 저장되도록 클러스터 할당 가능 (다중 테이블 인덱스 클러스터)
SQL> create cluster c_deptno# ( deptno number(2) ) index ;
SQL> create index i_deptno# on cluster c_deptno#;
SQL> create table emp 2 cluster c_deptno# (deptno) 3 as 4 select * from scott.emp;
- 클러스터 인덱스도 일반적인 B*Tree 인덱스 구조를 사용 (해당 키 값을 저장하는 첫 번째 데이터 블록만 가리킴)
- 클러스터 인덱스의 키 값은 항상 Unique 하며, 테이블 레코드와 1:M 관계임
- 클러스터 인덱스를 스캔하며 값을 찾을 때는 Random 액세스가 값 하나당 한 번씩만 발생 (클러스터 체인 스캔 제외)
- 클러스터에 도달 해서는 Sequential 방식 스캔 이므로 넓은 범위 검색에 유리)
- 새로운 값이 자주 입력 (새 클러스터 할당) 혹은 수정이 자주 발생하는 칼럼 (클러스터 이동) 은 클러스터 키로 부적합
바. 클러스터형 인덱스 / IOT
- SQL Server 에서 지원되는 인덱스 : 클러스터형 인덱스(Clustered Index), 비클러스터형 인덱스(Non-Clustered Index, B*Tree 와 같음)
- Clustered Index / IOT 구조
- 구조적으로 B*Tree 인덱스와 같은 형태, 모든 행 데이터를 인덱스 Leaf 페이지에 저장, 테이블 당 한개
- 힙 테이블에 데이터 삽입시, 정해진 순서 없이 Random 방식으로 이뤄짐, Clustered Index 는 정렬 상태를 유지하며 데이터를 삽입 (DML 성능 낮음)
- 넓은 범위 데이터 검색시 유리 : 정렬된 Leaf 페이지를 Sequential 방식으로 스캔하면서 테이블 Random 액세스 없이 값을 모두 찾을 수 있음
- Oracle 의 클러스터 인덱스와 다르며 오히려 IOT 와 유사 함 (Oracle Unique, SQL Server Unique/Non-Unique)
- Clustered Index / IOT 활용
- 유용한 테이블
- 넓은 범위를 주로 검색하는 테이블
- 크기가 작고 NL Join 으로 반복 룩업하는 테이블
- 칼럼 수가 적고 로우 수가 많은 테이블
- 데이터 입력과 조회 패턴이 서로 다른 테이블
- 100명의 영업사원, 일별 실적 집계 테이블, 한 페이지에 100개 레코드 담김 : 1년 : 365개 페이지
select substring(일자, 1, 6) 월도 , sum(판매금액) 총판매금액, avg(판매금액) 평균판매금액 from 영업실적 where 사번 = 'S1234' and 일자 between '20090101' and '20091231' group by substring(일자, 1, 6)
-- Non-Clustered Index : 사원마다 365개 데이터 페이지를 Random 액세스
create clustered index 영업실적_idx on 영업실적(사번, 일자);
-- Clustered Index : 사원마다 한개 데이터 페이지를 액세스
** Oracle IOT
create table 영업실적 ( 사번 varchar2(5), 일자 varchar2(8), ... , constraint 영업실적_PK primary key (사번, 일자) ) organization index;
- 2차 인덱스로부터 Clustered Index / IOT 참조하는 방식
- SQL Server : Non-Clustered Index = Clustered Index 를 가리키는 2차 인덱스
- 6.5 이전 : Non-Clustered Index 가 Clustered Index 레코드를 직접 가리키는 ROWID 를 갖음 (인덱스 분할에 따른 DML 부하)
- 7.0 이후 : Non-Clustered Index 가 Clustered Index 의 키 값을 갖음 (인덱스 분할에 따른 DML 해결, Clustered Index 수직 탐색 I/O 증가)
- Oracle : Secondary Index = IOT 를 가리키는 2차 인덱스
- SQL Server 6.5 이전, 7.0 이후 방식 모두 지원
- Logical Rowid = PK + physical guess (인덱스 생성 시점에 IOT 레코드가 위치했던 데이터 블록 주소(DBA), 갱신 되지 않음)
- 예) physical guess 로 블록을 찾고 없으면 PK 로 다시 탐색
