[SQLP] 2-1. 인덱스 구조

🧷 인덱스 구조

🖇️ 인덱스 튜닝

온라인 트랜잭션 처리(OLTP) 시스템에서는 소량의 데이터를 빠르게 검색하는 것이 중요하다. 따라서 대규모 테이블에서 소량의 데이터를 효율적으로 검색할 수 있도록 인덱스를 최적화하는 튜닝이 필수적이다. 인덱스 스캔 과정에서 성능을 결정하는 요소는 여러 가지가 있지만, 핵심적으로 고려해야 할 두 가지 요소는 다음과 같다.

 

✔️ 핵심 요소

• 인덱스 스캔 효율화 튜닝
  • 인덱스 스캔 과정에서 불필요한 연산을 최소화하는 것이 중요하다.
  • 인덱스 정렬 방식과 접근 방식을 최적화하여 스캔 횟수를 줄이는 것이 핵심이다.
• 랜덤 액세스 최소화 튜닝
  • 인덱스 스캔 후 테이블 데이터를 가져올 때 랜덤 I/O를 최소화해야 한다.
  • 테이블 접근 횟수를 줄이면 디스크 I/O 부담을 줄일 수 있어 성능 향상에 직접적인 영향을 미친다.

✔️ 랜덤 액세스 최소화가 중요한가?

 

데이터베이스 성능이 저하되는 주요 원인은 디스크 I/O 때문이다. 특히 OLTP 시스템에서는 인덱스를 활용한 검색이 많으므로, 랜덤 I/O가 성능 저하의 주요 요인이 된다. 즉, SQL튜닝의 핵심은 랜덤 액세스 최소화 하는 것 이라고 할 수 있다.

 

따라서 인덱스 튜닝을 통해 불필요한 테이블 액세스를 줄이고 랜덤 I/O를 최소화하는 것이 성능 최적화의 핵심 전략이다.

 

🖇️ 인덱스 구조

인덱스는 대용량 테이블에서 필요한 데이터만 빠르고 효율적으로 액세스 하기 위해 사용하는 객체(Object)이다.

1. 인덱스 기본 구조

여러 종류의 인덱스 중 가장 일반적으로 사용되는 B * Tree 인덱스 구조는 루트(Root), 브랜치(Branch), 그리고 리프(Leaf) 블록으로 구성된다.

• 루트 및 브랜치 블록
  • 하위 노드 블록을 접근하기 위한 주소 정보 (DBA, Data Block Address) 정보를 갖고 있다.
  • 특별한 엔트리인 Leftmost Child (LMC)가 존재하는데, 가장 왼쪽 첫 번째 레코드이고 자식 노드 중에 가장 왼쪽 끝에 위치한 블록을 가리킨다. LMC는 명시적인 키 값을 갖지 않더라도 키 값을 가진 첫번째 엔트리보다 작은 값의 의미를 갖는다.
• 리프 블록
  • 인덱스 키 컬럼 값과 해당 값을 가진 테이블 레코드를 찾기 위한 ROWID 정보를 저장한다.
  • 리프 블록은 항상 키 컬럼 순으로 정렬되어 있어, 특정 범위 내에서 연속된 값을 빠르게 검색할 수 있는 범위 스캔(Range Scan) 이 가능하다. 인덱스 키값이 같을때는 ROWID 순으로 정렬되어 있다.

✔️ 범위 스캔

 

테이블은 처음부터 끝까지 모든 레코드를 읽어야 완전한 결과집합을 얻을 수 있지만, 인덱스는 키 값이 정렬되어 있기 때문에 특정 범위 내에서 연속된 값을 효율적으로 검색할 수 있다. 특정 위치에서 스캔을 시작해 검색 조건에 일치하지 않는 값을 만나는 순간 멈출 수 있기 때문에 인덱스를 통해서는 범위 스캔이 가능하다.

 

반면, 일반적인 힙 구조 테이블은 데이터가 물리적으로 정렬되어 있지 않으므로 범위 스캔이 어렵다. 정렬 상태가 유지되도록 사용자가 데이터를 입력한다 하여도, 옵티마이저가 이를 그것을 신뢰해 테이블에서 범위 스캔이 일어나도록 실행계획을 수립하지 않는다. 단, IOT(index-organized table)는 특정 컬럼 순으로 데이터를 저장하기 때문에 범위 스캔이 가능하다.

 

2. 인덱스와 테이블 간의 관계

일부 DBMS에서는 값이 NULL 여부와 관계없이 인덱스에 저장하는 반면, Oracle은 인덱스 구성 컬럼의 값이 모두 NULL인 레코드는 저장하지 않는다. 즉, 인덱스 구성 컬럼의 값이 전부 NULL이 아닐 경우, 인덱스와 테이블 레코드는 1:1 대응관계를 갖는다. (단, 클러스터 인덱스는 1:M 관계) 또한, 브랜치에 저장된 레코드 수는 해당 브랜치의 하위 블록 수와 일치한다.

 

위에서 언급했듯이 인덱스 리프의 레코드와 테이블 레코드는 1:1 관계이며, 이들의 키 값도 동일하다. 따라서 테이블 레코드에서 값이 갱신되면, 대응하는 인덱스 키 값도 함께 갱신(delete & insert)된다.

 

반면, 리프 노드의 엔트리 키 값이 갱신되더라도 브랜치 노드까지 값이 변경되지 않는다. 브랜치 블록에 위치한 엔트리는 하위 노드 블록 중 자신의 키 값과 같거나 큰 값을 가진 영역을 포인팅 하는데, 그 키 값은 자식 노드 전체가 포함하는 값의 범위를 나타내기 때문이다. 따라서, 하위 노드의 첫 번째 레코드와 정확히 일치하지 않을 수 있다. 참고로, 브랜치 노드의 갱신은 인덱스 분할 과정에서 새로운 블록이 추가되거나 삭제될 때만 발생한다.

 

• 리프 노드
  • 리프 노드상의 인덱스 레코드와 테이블 레코드 간에는 1:1 관계
  • 리프 노드상의 키 값과 테이블 레코드 키 값은 서로 일치
• 브랜치 노드
  • 브랜치 노드상의 레코드 개수는 하위 블록 개수와 일치
  • 브랜치 노드상의 키 값은 하위 노드가 갖는 값의 범위를 의미

이러한 인덱스 구조와 특징을 명확히 이해하면 인덱스 탐색 과정을 보다 쉽게 파악할 수 있다.

 

3. ROWID

ROWID는 테이블 레코드의 물리적 위치 정보를 나타내는 pseudo 컬럼으로, 실제 테이블에 저장되는 값이 아니라, 인덱스와 데이터 블록 헤더에 존재하는 정보를 기반으로 동적으로 생성된다.

 

① 구성 요소

• ROWID = 데이터 블록 주소 + 로우 번호
• 데이터 블록 주소 (DBA) = 데이터 파일 번호 + 블록 번호
• 블록 번호 : 데이터 파일 내에서 부여한 상대적 순번
• 로우 번호 : 블록 내 레코드 순번

이처럼 ROWID에는 데이터 파일 번호, 블록 번호, 로우 번호 등 테이블 레코드의 물리적 위치 정보가 포함되며, 이 정보는 테이블 자체에 저장되는 것이 아니라 인덱스에 저장된다. 따라서 ROWID를 출력할 수는 있지만, 실제 테이블 데이터로 존재하지 않는다.

 

인덱스를 사용하지 않는 쿼리에서 ROWID가 요구될 경우, 데이터 블록 헤더에 저장된 오브젝트 및 데이터 파일 번호, 상대적 블록 번호와 레코드의 슬롯 번호를 활용하여 동적으로 가공해 출력할 수 있다.

 

② Oracle 버전에 따른 ROWID 포맷 변화

 

Oracle 7 이전 (제한 ROWID 포맷)까지의 ROWID는 6바이트 크기를 가지며, 데이터 파일 번호, 블록 번호, 로우 번호의 3개 구성요소로 이루어진다.

 

Oracle 8 이후 (확장 ROWID 포맷)부터는 데이터의 양 증가와 더 많은 데이터 파일 관리, 파티셔닝 기능 도입 등의 이유로 오브젝트 번호까지 저장할 필요가 생겼기 때문에 ROWID 크기가 10바이트로 확대되었다. 기존 3개의 구성요소에 데이터 오브젝트 번호가 추가되어 총 4개의 구성요소로 구성된다.

 

• 데이터 오브젝트 번호: 데이터베이스 세그먼트를 식별하기 위해 사용되는 데이터 오브젝트 번호
• 데이터 파일 번호: 테이블스페이스 내에서의 상대적 번호(버전 7까지는 데이터베이스 내에서 유일한 값)
• 블록 번호: 데이터 파일 내에서의 상대적 블록 번호
• 로우 번호: 해당 블록 내 레코드 순번

이와 같이 ROWID의 구조를 이해하는 것은 Oracle에서 테이블 레코드의 물리적 접근 방식 및 인덱스와의 관계를 파악하는 데 매우 중요하다.

🖇️ 인덱스 탐색

1. 인덱스 탐색

인덱스 탐색은 크게 수직적 탐색과 수평적 탐색으로 나눌 수 있다.

(1) 인덱스 수직적 탐색

정렬된 인덱스 레코드 중에서 조건을 만족하는 첫 번째 레코드를 찾는 과정, 인덱스 시작 지점을 찾는 과정

 

수직적 탐색은 수평적 탐색을 위한 시작 지점을 찾는 과정이라고 할 수 있으며, 인덱스 트리의 루트에서 리프 블록까지 내려가는 방식으로 진행되므로 ‘수직적’이라고 부른다

 

✔️ 탐색과정

1. 탐색은 루트 블록에서 시작하여, 각 노드에 저장된 하위 블록에 대한 주소값을 이용하여 리프 블록까지 진행된다.
2. 찾고자 하는 값보다 크거나 같은 값을 만나면 바로 직전 레코드가 가리키는 하위 블록으로 이동한다.

이 과정은 조건을 만족하는 레코드를 찾아가는 과정이 아니라 조건을 만족하는 첫번째 레코드를 찾는 과정이다. 또한, 조건을 만족하는 시작점을 빠르게 찾기 위한 것으로, 이후의 수평적 탐색 준비 단계라고 볼 수 있다.

 

(2) 인덱스 수평적 탐색

인덱스에서 본격적으로 데이터를 찾는 과정

 

수평적 탐색은 범위 스캔(range scan)이라고 할 수 있으며, 인덱스의 리프 블록에 저장된 레코드들이 논리적 순서대로 배열되어 있어 좌에서 우 또는 우에서 좌로 순차적으로 스캔하게 된다.

 

✔️ 탐색과정

1. 수직적 탐색을 통해 스캔 시작점(첫 번째 레코드)을 찾았으면 리프 블록을 수평적으로 탐색을 진행한다.
   • 인덱스 리프 블록은 양방향 연결 리스트 구조로 되어 있어, 시작 레코드에서 좌우로 순차적(수평적) 스캔이 가능하다.
2. 이 과정을 통해 조건에 부합하는 레코드들의 ROWID를 획득한다.
3. 만약 인덱스만으로 필요한 모든 컬럼 정보를 제공할 수 있다면 탐색은 여기서 종료되지만, 그렇지 않은 경우 획득한 ROWID를 이용하여 테이블 데이터를 추가로 조회한다.

수직적 탐색과 수평적 탐색을 모두 수행하는 이유는, 조건에 부합하는 모든 데이터를 찾아내고 그에 해당하는 ROWID를 확보하기 위함이다. 만약 필요한 컬럼이 인덱스에 모두 포함되어 있다면 이 과정을 통해 검색을 완료할 수 있으나, 그렇지 않은 경우 테이블 접근이 필요하기 때문이다.

2. 결합 인덱스 구조와 탐색

두 개 이상의 컬럼을 결합하여 인덱스를 생성할 수 있다. 결합 인덱스의 경우, 인덱스 내의 컬럼 순서에 관계없이 "=" 조건으로 검색할 때 읽는 인덱스 블록 수는 동일하다.
즉, 인덱스 컬럼 순서와 상관없이, 모든 경로가 B * Tree의 균형 구조를 따르기 때문에 루트부터 리프까지의 높이는 항상 동일하며, 이에 따라 블록 I/O 횟수도 같으므로 성능도 똑같다.

 

단, "=" 조건 검색에 한정된 이야기이며, 범위 조건이나 결합 조건에 따라서는 접근 방식에 차이가 발생할 수 있다.