[DB] 1. 인덱싱(Indexing)

파일 구성(File organization)은 파일 내의 데이터 레코드(data record)를 배치하는 방법을 의미한다. 파일 구성 방법마다 효율적인 연산과 비효율적인 연산이 존재한다.

 

0. 디스크에 저장되는 데이터

- 디스크의 입출력 단위는 페이지(page)다. 페이지의 I/O cost가 대부분의 DB 연산 비용을 차지하기 때문에, 해당 비용을 최소화하도록 BD를 최적화 해야 한다.

- 디스크의 임의의 페이지 접근 비용은 모두 거의 동일하다. 다만, 순차적으로 나열되어 있는 여러 페이지는 무작위로 배치되어 있는 여러 페이지보다 빠르게 접근할 수 있다.

- 각 데이터 레코드는 rid(record-id)라 불리는 식별자(identifier)를 가지고 있다. 이를 가지고 데이터 레코드를 포함하고 있는 페이지의 디스크 주소를 파악할 수 있다.

- 버퍼 관리자(Buffer Manager)는 디스크에서 페이지를 읽어오는 혹은 디스크에 페이지를 기록(저장)하는 역할을 수행한다.

- 디스크 공간 관리자(Disk Space Manager)는 디스크 공간을 관리하는 역할을 수행한다. 쉽게 말해, 디스크 공간을 할당 및 해체(반환)하는 역할을 수행한다.

1. 파일 구성 & 인덱싱

- 힙 파일(Heap files, random order files): 무작위로 데이터 레코드를 파일의 페이지에 저장(배치)한다.

저장한다.

- 정렬 파일(Sorted files): 정렬 기준에 맞게 데이터 레코드를 파일의 페이지에 저장(배치)한다.

- 인덱스 파일(Indexed files): Symbol Table의 대표적인 자료구조(Tree, Hash)를 사용해 데이터 레코드를 탐색 키 기준으로 저장(배치)한다.

 

1.1. 인덱싱(Indexing)

인덱스(Index)는 데이터 레코드에서 탐색 키에 대한 검색 연산을 효율적으로 처리하기 위해 설계된 데이터 구조이며, 대부분 트리(Tree) 혹은 해쉬(Hash) 자료구조를 사용한다.

 

인덱스는 크게 두 유형으로 나뉜다:

1. 기본 인덱스(primary index): 기본 키를 탐색 키로 갖는 인덱스, 2. 보조 인덱스(secondary index): 그 외의 키를 탐색 키로 갖는 인덱스
(기본 인덱스는 중복을 없지만, 보조 인덱스는 중복이 존재할 수 있다. 보조 인덱스에 중복 키가 존재하지 않으면 이를 고유 인덱스(unique index)라고 칭한다.)

 

인덱스 파일은 데이터 엔트리(data entry)에 데이터 레코드에 대한 정보를 저장하는데, 크게 세 가지 유형이 있다:

1. 데이터 레코드 그 자체, 2. <key, rid>, 3. <key, rid-list>

(참고로, 첫번째 방식을 적용하면 indexed file, 그 외 방식을 적용하면 index file이라 부른다.)

 

군집 인덱스(Clustered Indexes) vs 비군집 인덱스(Un-clustered Indexes)

- 군집 인덱스: 데이터 레코드의 물리적 저장 순서가 데이터 엔트리의 물리적 저장 순서와 동일하거나 거의 비슷한 인덱스

- 비군집 인덱스: 데이터 레코드의 물리적 저장 순서와 데이터 엔트리의 물리적 저장 순서가 다른 인덱스

(그렇기 때문에, 군집 인덱스는 데이터 엔트리의 첫 유형을 사용하는 인덱스로, 비군집 인덱스는 그 외의 유형을 사용하는 인덱스로 볼 수 있다.)

2. 인덱스 자료구조

2.1. 해쉬 기반 인덱스(hash-based index)

해싱(hashing) 기법을 활용한 인덱스로, 특정 탐색 키 값을 갖는 모든 데이터 엔트리를 빠르게 찾아준다.

해쉬 기반 인덱스는 데이터 엔트리를 버킷(bucket)에 저장한다 이때, 각 데이터 엔트리가 속할 버킷은 해당 데이터 엔트리의 해시 값에 따라 결정된다. 쉽게 말해, 해시 값이 같으면 동일한 버킷에 저장된다. 

각 버킷은 기본 페이지(primary page)와 경우에 따라 체인으로 연결된 부가적인 페이지(overflow page)로 구성된다. 즉, 버킷 내의 모든 페이지가 가득 차면 새로운 페이지가 추가로 할당한다.

주어진 탐색 키 값을 가지는 데이터 엔트리를 찾기 위해선 해시 함수를 적용해 그런 데이터 엔트리가 속할 수 있는 버킷을 식별한 다음, 그 버킷에 존재하는 모든 페이지를 살펴봐야 한다.

만약, 탐색 키에 해당하는 인덱스가 없을 경우 파일 내의 모든 페이지를 스캔해야 한다.

 

아래 그림은, age(기본 키) 해쉬 인덱스와 sal 해쉬 인덱스를 그림으로 표현한 것이다.

age 인덱스는 기본 키를 탐색 키로 갖고 있기 때문에 기본 인덱스다. 그리고, 데이터 엔트리가 데이터 레코드 그 자체이기 때문에 군집 인덱스다.

sal 인덱스는 일반 키를 탐색 키로 갖고 있기 때문에 보조 인덱스다. 그리고, 데이터 엔트리(<key, rid>)의 저장 순서와 데이터 레코드의 저장 순서가 다르기 때문에 비군집 인덱스다.

2.2. 트리 기반 인덱스(tree-based index)

트리 자료구조를 활용한 인덱스로, 특정 범위에 속하는 탐색 키 값을 가진 모든 데이터 엔트리를 빠르게 찾아준다.

트리 기반 인덱스는 데이터 엔트리를 단말 노드(leaf node)에 저장한다. 이때, 데이터 엔트리는 탐색 키 정렬 순서에 맞게 배치된다.

 

아래 그림은, age(기본 키) 트리 인덱스를 그림으로 표현한 것이다.

age 인덱스는 기본 키를 탐색 키로 갖고 있기 때문에 기본 인덱스이다. 그리고, 데이터 엔트리가 데이터 레코드 그 자체이기 때문에 군집 인덱스다. 

3. 파일 구성 간의 성능 비교

Cost Model

- $B$: # of data pages

- $R$: # of records per pages

- $D$: avg time to read or write a disk page

- $C$: avg time to process a record (e.g., 비교 연산 등)

 

	scan	equality search	range search	insert	delete
heap	$BD$	$0.5BD$	$BD$	$2D+C$	search$+D+C$
sorted file	$BD$	$D\log_2B$	$D\log_2B + $ # of matching pages	search$+BD$	search$+BD$
clustered  tree index	$1.5BD$	$D\log_F 1.5B$	$D\log_F 1.5B + $ # of matching pages	search$+D$	search$+D$
unclustered tree index	$BDR$	$D\log_F0.15B$	$D(\log_F0.15B+$ # of matching records$)$	search$+D$	search$+D$
un-clustered hash index	$BDR$	$2D$	scan	$4D$	$4D$

 

가정:

1. 모든 트리 인덱스의 인덱스 파일의 페이지(non-leaf node page)는 평균적으로 67%를 사용한다.

2. 모든 해쉬 인덱스의 인덱스 파일의 페이지는 평균적으로 80%를 사용한다.

3. 모든 비군집 인덱스의 데이터 엔트리 크기는 데이터 레코드 크기의 10%다.

4. 인덱스 성능 튜닝

4.1. 군집 인덱스 튜닝

군집 인덱스는 일반적으로 범위 쿼리(range query)와 중복 값이 많은 동등 쿼리(equality query with many duplicate)에 유용하다.

일반적으로 테이블마다 군집 인덱스는 하나만 존재하므로, 클러스터링의 이점을 충분히 활용하는 고빈도 쿼리를 제외하고는 사용을 자제해야 한다.

- 군집 인덱스의 가치는 조건의 선택도(selectivity of condition)에 따라 결정된다. 
모든 데이터 레코드가 조건을 만족하는 경우, 순차 스캔과 거의 동일한 I/O 비용이 소요된다. 반면 데이터의 10%만 조건을 만족하는 경우,  순차 스캔의 I/O 비용의 10%만 사용된다. 이때 주의해야할 점, 조건을 만족하는 데이터 레코드가 1개인 경우 군집 인덱스는 아무런 이점을 제공해주지 않는다.

- 인덱스의 탐색 키 정보만으로 쿼리를 처리할 수 있는지 살펴봐야 한다. (=index-only evaluation)
index-only evaluation이 가능하다면 클러스터링할 필요가 없다. 

 

4.2. 복합 탐색 키(Composite Search Keys)

여러 개의 필드를 포함한 탐색 키를 복합 탐색 키라 부른다.

- 복합 탐색 키 관점에서, 모든 필드의 값이 정해진 쿼리는 동등 쿼리(equality query), 일부 필드의 값이 정해지지 않은 퀴리를 범위 쿼리(range query)라 부른다.

- 복합 키 인덱스가 조건에 맞는 데이터 레코드를 검색하는데 활용될 수 있다면, 이를 "셀랙션 조건(selection condition)에 부합(match)한다."라고 표현한다. 해쉬 인덱스에서는 복합 탐색 키의 모든 필드에 동등 조건이 있어야 하며, 트리 인덱스는에서는 복합 탐색 키의 prefix 필드에 범위 혹은 동등 조건이 있어야 한다.

 

장점: 많은 셀랙션 조건에 부합하기 때문에 넓은 범위의 쿼리를 수용할 수 있으며, index-only evaluation 가능성도 증가한다.

단점: 탐색 키의 어느 필드 값이 수정되더라도 인덱스가 업데이트되므로, 업데이트 횟수가 증가하고 단일 키 인덱스보다 크다.

 

복합 탐색 키에서는 필드 간의 정렬 순서도 중요하다. 우선순위를 동등(equality), 그룹화(groupby), 범위(range) 순으로 두는게 좋다.