01. 인덱스 원리와 활용

01. 인덱스 구조

(1) 범위 스캔

• 범위(Range)스캔 : 인덱스는 키 컬럼 순으로 정렬돼 있기 때문에 특정 위치에서 스캔을 시작해 검색 조건에 일치하지 않는 값을
  만나는 순간 멈추는 것.
  (IOT(index-organized table)는 특정 컬럼 순으로 정렬 상태를 유지하며 값을 입력하므로 범위스캔가능)

(2) 인덱스 기본 구조

• p.17 그림 1-1 참조
• 루트(Root)를 포함한 브랜치(Branch)블록 각 엔트리에는 하위 노드 블록을 찾아가기 위한 DBA(Data Block Address) 정보를 저장.
• lmc(LeftMost Child)는 키 값을 가진 첫 번째 엔트리보다 작은 값의 의미.
• 다른 엔트리는 자신의 키 값과 같거나 큰 값을 담은 자식 노드 블록을 가르킨다.

• 리프(Leaf)블록에는 인덱스 키 컬럼과 함께 해당 테이블 레코드를 찾아가기 위한 주소정보(rowed)를 저장. 항상 키 컬럼 순으로 정렬.
  키 값이 같을 때는 rowid순으로 정렬.
• 인덱스 구성 컬럼이 모두 null인 레코드는 저장하지 않는다.
• 인덱스와 테이블 레코드는 1:1 대응 관계
• 클러스터 인덱스(Cluster Index)는 1:M 관계
• 브랜치에 저장된 레코드 개수는 바로 하위 레벨 블록 개수와 일치(lmc 포함)
• 테이블 레코드에 값이 갱신되면 리프 노드 인덱스 키 값도 같이 갱신(delete & insert)
• 브랜치 노드는 인덱스 분할(Split)에 의해 새로운 블록이 추가 되거나 삭제 될 때만 갱신.
• 브랜치 노드상의 키 값은 하위 노드가 갖는 값의 범위를 의미

(3) 인덱스 탐색

• 수평적 탐색 : 범위 스캔, 리프블록을 인덱스 레코드 간 논리적 순서에 따라 스캔
• 수직적 탐색 : 수평적 탐색을 위한 시작 지점을 찾는 과정. 루트에서 리프 블록까지 아래로 진행.

• p.17 그림 1-1 에서 'CLARK'을 찾는 과정
  1. 루트 블록 스캔 (lmc는 'KI'보다 작은 모든 값을 의미, 'KI'는 'KI'보다 크거나 같은 모든 값을 의미) -> 왼쪽 브랜치 블록으로 이동
  2. 찾아간 브랜치 블록을 스캔하면서 그 다음 찾아갈 인덱스 블록을 탐색.
  ('CLARK'이 'BER' 보다 크고 'FO' 보다 작다) -> 두번째 레코드가 가리키는 블록 주소로 이동
  3. 리프 블록에서 찾으면 수평적 탐색과정, 못 찾으면 거기서 인덱스 탐색을 마친다.
  4. 인덱스 리프 블록을 스캔하면서 값이 'CLARK'인지 확인
  5. 'CLARK'이면 거기서 얻은 rowid를 이용해 해당 테이블 레코드를 찾아가 필요한 다른 컬럼 값을 읽는다.
  (쿼리에서 인덱스 컬럼만 필요로 한다면 이 과정은 생략)
  6. 4번과 5번을 반복하다가 검색조건을 만족하지 못하는 레코드를 만나는 순간 멈춘ㄴ다.

브랜치 블록 스캔

• 브랜치 블록을 스캔할 때는 뒤에서부터 스캔하는 방식이 유리하다.
• 뒤에서부터 스캔할 때는 검색하고자 하는 값보다 작은 첫 번째 레코드를 만나는 순간 바로 하위 블록으로 내려가면 되지만,
  앞에서부터 스캔시에는 검색하고자 하는 값보다 크거나 같은 첫번째 레코드를 만나는 순간 멈춰서 한 칸 뒤로 이동해야 하기 때문
• 브랜치 블록을 따라 수직적 탐색을 진행할 때는 찾고자 하는 값보다 키 값이 작은 엔트리를 따라 내려간다.

• p.20 그림 1-2 인덱스를 통해 값이 3인 레코드를 찾을 경우
  1. 1번 루트 블록에서 lmc가 가리키는 2번 브랜치 노드로 따라 내려가야 한다.
  (같은 값인 3을 따라 3번 브랜치로 내려가면 2번 브랜치 끝에 놓인 3을 놓치게 된다)
  2. 2번 브랜치에서 맨 뒤쪽 3부터 거꾸로 스캔하다가 2를 만나는 순간 리프 블록으로 내려간다.
  3. 키 값이 3인 첫 번째 레코드를 찾아 오른쪽으로 리프 블록을 스캔해 나간다.

결함 인덱스 구조와 탐색

• p.21 그림 1-3 'deptno = 20 and sal >= 2000' 조건 검색
• deptno가 20인 첫 번째 레코드가 스캔 시작점이라고 생각하기 쉽다. 하지만 두 번째 리프 블록, 그 중에서도
  두 번째 레코드부터 스캔이 시작된다.
• 수직적 탐색 과정에서 deptno 뿐만 아니라 sal 값에 대한 필터링도 같이 이루어지기 때문.
  (개인 의견 : 랜덤엑세스가 필요한 경우는 해당되는 리프 블록의 처음부터 스캔하지만 랜덤엑세스는 두번째 레코드 부터 시작된다.
  인덱스만을 읽는다면 리프 블록 처음부터 조건이 해당되지 않는 레코드까지 스켄이 이루어 진다)

(4) ROWID 포맷

• 테이블자체에 저장되는 것이 아니라 인덱스에 저장
• 오라클 7 이하 버전 6 byte
• 오라클 8 이후 버전 중 파티션되지 않은 일반 테이블에 생성한 인덱스, 파티션된 테이블에 생성한 로컬 파티션 인덱스 6 byte
• 오라클 8 이후 버전 중 파티션 테이블에 생성한 글로벌 파티션 인덱스, 파티션 테이블에 생성한 비파티션 인덱스. 10 byte

제한 rowed 포맷

• 오라클 7 이하 버전
• 데이터파일 번호(4자리) : 로우가 속한 데이터파일 번호, 데이터베이스내에서 유일 값.
• 블록번호(8자리) : 로우가 저장된 데이터 블록 번호, 데이터파일 내에서의 상대적 번호
• 로우번호(4자리) : 블록 내에서 각 로우에 붙여진 일련번호, 0부터 시작
• 구분자 '.(dot)' 기호를 포함해 18자리 문자열.
• 순서는 블록, 로우, 데이터파일 (00000DD5.0000.0001)

확장 rowed 포맷

• 오라클 8 이후 버전
• 데이터 오브젝트 번호(6자리) : 세그먼트를 식별하기 위해 사용되는 데이터 오브젝트 번호
• 데이터파일 번호(3자리) : 로우가 속한 데이터파일 번호, 테이블스페이스 내에서의 상대적인 파일 번호
• 블록번호(6자리) : 로우가 저장된 데이터 블록 번호, 데이터파일 내에서의 상대적 번호
• 로우번호(3자리) : 블록 내에서 각 로우에 붙여진 일련번호, 0부터 시작
• 6 바이트든 10 바이트든 출력되는 포맷은 별도 구분 없이 연속된 18자리 문자열(AAAM6PAAEAAAE2cAAA)
• 순서는 데이터 오브젝트, 데이터파일, 블록, 로우
• rowid를 자릿수만큼 잘라서 디코딩(Decoding)하면 각 구성요소에 대한 정보 출력.
• dbms_rowid 패키지 사용

select rowid extended_format
       , dbms_rowid.rowid_to_restricted(rowid, 0) restricted_format
       , dbms_rowid.rowid_object(rowid) object
       , dbms_rowid.rowid_relative_fno(rowid) file_no
       , dbms_rowid.rowid_block_number(rowid) block_no
       , dbms_rowid.rowid_row_number(rowid) row_number
  from   emp e
  where  empno = 7369;

EXTENDED_FORMAT    RESTRICTED_FORMAT      OBJECT    FILE_NO   BLOCK_NO ROW_NUMBER
------------------ ------------------ ---------- ---------- ---------- ----------
AAAMgzAAEAAAAAgAAA 00000020.0000.0004      51251          4         32          0

select dbms_rowid.rowid_type('AAAM6PAAEAAAE2cAAA') extended_format
       , dbms_rowid.rowid_type('00004D9C.0000.0004') restricted_format
  from   dual;

EXTENDED_FORMAT RESTRICTED_FORMAT
--------------- -----------------
              1                 0

- 브랜치 블록의 엔트리에 키 값을 저장시에는 압축 알고리즘 적용
- 모든 키값이 다 같을 경우는 하위 노드에 저장된 rowid 값까지 저장

begin
for i in 1..1000
loop
insert into t values (i, i);
end loop ;
commit;
end ;

Branch block dump
=================
header address 116152908=0x6ec5a4c
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 3
kdxcosdc 1
kdxconro 66
kdxcofbo 160=0xa0
kdxcofeo 7472=0x1d30
kdxcoavs 7312
kdxbrlmc 25165847=0x1800017
kdxbrsno 65
kdxbrbksz 8060 
kdxbr2urrc 0
row#0[8052] dba: 25165848=0x1800018
col 0; len 2; (2):  c1 11
col 1; TERM
row#1[8044] dba: 25165845=0x1800015
col 0; len 2; (2):  c1 20
col 1; TERM
...

==============================================

begin
for i in 1..1000
loop
insert into t values (1, i);
end loop ;
commit;
end ;

Branch block dump
=================
header address 116152908=0x6ec5a4c
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 3
kdxcosdc 1
kdxconro 89
kdxcofbo 206=0xce
kdxcofeo 7055=0x1b8f
kdxcoavs 6849
kdxbrlmc 25165847=0x1800017
kdxbrsno 88
kdxbrbksz 8060 
kdxbr2urrc 0
row#0[7956] dba: 25165849=0x1800019
col 0; len 2; (2):  c1 02
col 1; len 3; (3):  31 30 39
col 2; TERM
row#1[7944] dba: 25165850=0x180001a
col 0; len 2; (2):  c1 02
col 1; len 3; (3):  31 31 39
col 2; TERM
...

==============================================

begin
for i in 1..1000
loop
insert into t values (1, 1);
end loop ;
commit;
end ;

Branch block dump
=================
header address 116152908=0x6ec5a4c
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 3
kdxcosdc 1
kdxconro 10
kdxcofbo 48=0x30
kdxcofeo 2902=0xb56
kdxcoavs 2854
kdxbrlmc 25165847=0x1800017
kdxbrsno 7070
kdxbrbksz 8060 
kdxbr2urrc 7
row#0[2902] dba: 25165852=0x180001c
col 0; len 2; (2):  c1 02
col 1; len 500; (500): 
 31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
col 2; len 6; (6):  01 80 00 0c 00 0b
row#1[3418] dba: 25165853=0x180001d
col 0; len 2; (2):  c1 02
col 1; len 500; (500): 
 31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
col 2; len 6; (6):  01 80 00 0d 00 08
...

문서에 대하여

• 최초작성자 : 김종원
• 최초작성일 : 2010년 03월 04일
• 이 문서는 오라클클럽 코어 오라클 데이터베이스 스터디 모임에서 작성하였습니다.
• {*}이 문서의 내용은 (주)비투엔컬설팅에서 출간한 '오라클 성능 고도화 원리와 해법II'를 참고하였습니다.*