DB 06. 물리 설계와 인덱스

6장의 핵심은 논리적으로 설계된 relation을 실제 보조 기억 장치 위에 어떻게 저장하고, 어떤 접근 방법을 통해 빠르게 검색할 것인가이다. 앞 장에서 relation, key, normalization, relational algebra를 다뤘다면, 이 장에서는 DBMS가 실제 disk block을 읽고 쓰는 관점에서 성능을 분석한다.

물리적 데이터베이스 설계는 다음 질문으로 압축할 수 있다.

주어진 workload에서 어떤 file organization과 index structure를 선택해야 disk I/O를 줄일 수 있는가?

---

1. 물리적 데이터베이스 설계의 관점

물리적 데이터베이스 설계는 논리적 데이터 구조를 보조 기억 장치상의 file, 즉 물리적 데이터 모델로 사상하는 과정이다. 단순히 데이터를 저장하는 것이 아니라, 자주 실행되는 query와 transaction의 빈도, 원하는 성능, 갱신 비용을 함께 고려한다.

주요 고려 사항은 다음과 같다.

항목	의미
Query workload	어떤 query가 자주 실행되는지
Update workload	INSERT, DELETE, UPDATE가 얼마나 자주 발생하는지
Storage structure	record를 disk block에 어떤 방식으로 배치할지
Access method	원하는 record를 어떤 방식으로 찾을지
DBMS characteristics	특정 DBMS의 optimizer, index 구현, storage engine 특성
Index strategy	어떤 relation의 어떤 attribute에 index를 둘지

예를 들어 다음 query가 매우 자주 실행된다면 EMPNO에 대한 index가 중요해질 수 있다.

SELECT *
FROM EMPLOYEE
WHERE EMPNO = 1365;

반대로 SALARY가 자주 변경되는 시스템에서 SALARY index를 많이 만들면 검색은 빨라질 수 있지만 갱신 비용이 커질 수 있다.

---

2. 보조 기억 장치와 disk I/O

DBMS는 database를 주로 disk에 저장한다. 하지만 DBMS가 실제 연산을 수행하려면 필요한 disk block을 main memory로 가져와야 한다.

Disk block → Buffer in main memory → DBMS operation

변경된 데이터는 반대로 memory에서 수정된 뒤 disk에 다시 기록된다.

Buffer update → Write back to disk

중요한 점은 DBMS가 보통 record 하나를 직접 읽는 것이 아니라 block 단위로 읽고 쓴다는 것이다.

2.1 Block

Block은 disk I/O의 기본 단위이다. 강의 예제에서는 전형적인 block size로 4,096 bytes를 사용했다.

예를 들어 record length가 200 bytes, block size가 4,096 bytes라면 한 block에 들어가는 record 수는 다음과 같다.

blocking factor = ⌊4096 / 200⌋ = 20

이 값은 뒤의 heap file, sequential file, index 예제에서 반복적으로 사용된다.

2.2 Magnetic disk 구조

Magnetic disk는 platter, track, sector, cylinder, block 등의 단위로 이해할 수 있다.

용어	의미
platter	실제 회전하는 원판
track	disk 표면의 동심원 경로
sector	track을 나눈 작은 단위
cylinder	여러 disk 면에서 같은 지름을 갖는 track들의 집합
block	하나 이상의 sector로 구성되는 입출력 단위

Disk에서 임의의 block을 읽거나 기록하는 시간은 다음 세 요소의 합이다.

Disk access time = seek time + rotational delay + transfer time

구성 요소	의미
seek time	disk head가 원하는 track으로 이동하는 시간
rotational delay	원하는 sector가 head 아래로 올 때까지 기다리는 시간
transfer time	실제 데이터를 읽거나 쓰는 시간

Disk I/O는 매우 느리기 때문에, 물리적 설계의 핵심은 결국 disk block 접근 횟수를 줄이는 것이다.

---

3. Buffer management

DBMS는 disk에 있는 데이터를 바로 처리하지 않는다. 필요한 page 또는 block을 buffer pool에 올린 뒤 처리한다.

Data must be in RAM for DBMS to operate on it.

3.1 Buffer pool과 frame

Buffer는 disk block을 저장하기 위해 main memory에 마련된 공간이다. Buffer pool은 여러 frame으로 구성되고, 각 frame은 disk page 또는 block 하나를 담을 수 있다.

DBMS는 어떤 frame에 어떤 page가 올라와 있는지 관리하기 위해 다음과 같은 mapping table을 유지한다.

<frame#, pageid>

예시는 다음과 같다.

frame	pageid
1	25
2	103
3	free
4	7

필요한 page가 이미 buffer pool에 있으면 disk를 다시 읽지 않아도 된다. 반대로 없으면 disk I/O가 발생한다.

상황	의미
Buffer hit	필요한 page가 이미 memory에 있음
Buffer miss	필요한 page가 없어 disk에서 읽어와야 함

3.2 Replacement policy와 LRU

Buffer pool의 크기는 제한되어 있다. 새로운 page를 읽어와야 하는데 free frame이 없으면 기존 page 중 하나를 내보내야 한다. 이때 어떤 page를 제거할지 결정하는 기준이 replacement policy이다.

대표적인 정책은 LRU(Least Recently Used)이다.

LRU = 가장 오랫동안 사용되지 않은 page를 교체하는 방식

LRU는 일반적인 프로그램에서는 합리적인 정책이지만, database workload에서는 항상 좋은 성능을 보장하지 않는다. 예를 들어 대량 sequential scan은 한 번 읽고 다시 사용하지 않을 block들을 최근 사용 page로 남겨 자주 쓰는 page를 밀어낼 수 있다.

주의할 점은 다음과 같다.

접근 패턴	LRU의 한계
대량 sequential scan	다시 쓰지 않을 block이 buffer를 차지할 수 있음
반복적으로 사용되는 index root	일반 page보다 오래 유지하는 것이 유리할 수 있음
Join 중 반복 접근되는 page	단순 LRU보다 DBMS가 접근 패턴을 아는 것이 유리

따라서 실제 DBMS는 운영체제의 일반적인 buffer management에만 의존하지 않고, 자체적인 buffer manager를 통해 database 접근 패턴에 맞게 page를 관리한다.

---

4. Disk 상에서 file의 record 배치

Relation의 attribute는 실제 저장 단계에서 field로 표현된다. 관련 field들이 모이면 record가 되고, 같은 relation에 속한 record들의 모임이 file이 된다. File은 다시 여러 disk block에 나누어 저장된다.

Attribute → Field
Fields → Record
Records → File
File → Disk blocks

4.1 File과 block

한 file에 속하는 block들이 disk 위에서 반드시 물리적으로 인접할 필요는 없다.

EMPLOYEE block 1 → free space → DEPARTMENT block 1 → EMPLOYEE block 2

하지만 같은 file의 block들이 인접해 있으면 sequential access에서 seek time과 rotational delay를 줄일 수 있다. 따라서 전체 scan이나 range query가 많은 file은 물리적으로 가까운 block에 배치하는 것이 유리하다.

4.2 BLOB

BLOB(Binary Large Object)은 image, video와 같은 대용량 binary data를 저장하기 위한 타입이다.

예를 들어 직원 사진을 저장하는 경우 다음과 같은 schema를 생각할 수 있다.

EMPLOYEE(EMPNO, EMPNAME, PHOTO)

여기서 PHOTO가 image data 자체라면 BLOB으로 저장할 수 있다.

4.3 Fill factor

fill factor는 block을 얼마나 채울 것인지 나타내는 비율이다.

Fill factor	장점	단점
100%	공간 낭비가 적음	중간 삽입 시 record 이동 또는 block split 가능성 증가
낮은 값	삽입 여유 공간 확보	더 많은 block 필요

정렬된 file에서 중간 삽입이 자주 발생한다면 block에 여유 공간을 남겨두는 것이 유리할 수 있다.

4.4 Fixed-length record

Fixed-length record는 모든 record의 크기가 같은 구조이다. 이 경우 i번째 record의 시작 위치를 바로 계산할 수 있다.

record i 시작 위치 = n * (i - 1) + 1

여기서 n은 record length이고, i는 record number이다.

예를 들어 record length가 18 bytes라면 다음과 같다.

record number	계산	시작 위치
1	18 * (1 - 1) + 1	1
2	18 * (2 - 1) + 1	19
3	18 * (3 - 1) + 1	37
4	18 * (4 - 1) + 1	55

Fixed-length record의 장점은 특정 record 위치를 계산으로 바로 찾을 수 있다는 점이다.

4.5 Record deletion과 free list

Fixed-length record 삭제 시 대표적인 방법은 세 가지이다.

방법	장점	단점
뒤 record들을 모두 앞으로 이동	순서 유지	이동 비용 큼
마지막 record를 삭제 위치로 이동	이동 비용 작음	순서 깨짐
free list로 빈 공간 관리	삭제 시 이동 불필요	빈 공간 목록 관리 필요

free list 방식에서는 삭제된 공간을 바로 메우지 않고, 빈 공간 목록에 등록해둔다. 이후 새 record 삽입 시 free list를 확인하여 비어 있는 위치를 재사용할 수 있다.

Before delete:
1 영업 8
2 기획 10
3 개발 9
4 총무 7

After delete with free list:
1 영업 8
[free]
3 개발 9
4 총무 7

4.6 Clustering

Clustering은 함께 검색될 가능성이 높은 record들을 물리적으로 가까운 곳에 저장하는 것이다.

구분	의미
intra-file clustering	하나의 file 안에서 관련 record를 가까이 배치
inter-file clustering	서로 다른 file의 관련 record를 가까이 배치

예를 들어 EMPLOYEE file에서 DNO = 1인 직원들을 같은 block 근처에 모아두면 다음 query가 효율적이다.

SELECT *
FROM EMPLOYEE
WHERE DNO = 1;

DEPARTMENT와 EMPLOYEE가 자주 join된다면, 특정 department record와 해당 department의 employee records를 가까이 저장하는 inter-file clustering도 고려할 수 있다.

---

5. File organization

File organization은 record를 file에 어떤 순서와 방식으로 저장할 것인지에 대한 전략이다.

유형	핵심
heap file	삽입 순서대로 비정렬 저장
sequential file	search key 순서대로 정렬 저장
indexed sequential file	sequential file에 index 결합
hash file	hash function으로 저장 위치 계산

5.1 Heap file

heap file은 가장 단순한 file organization이다. Record들이 일반적으로 삽입된 순서대로 file 끝에 저장된다.

연산	성능
Insert	효율적
Delete	대상 record를 찾아야 하므로 비용 큼
특정 record search	비효율적
조건 search	비효율적
Full scan	어차피 전체를 읽으므로 상대적으로 적합

Heap file은 다음 query처럼 전체 record를 읽고 순서가 중요하지 않은 경우에는 괜찮다.

SELECT *
FROM EMPLOYEE;

하지만 특정 record를 찾는 query에는 비효율적이다.

SELECT TITLE
FROM EMPLOYEE
WHERE EMPNO = 1365;

Heap file에 b개의 block이 있다면 원하는 record를 찾기 위해 평균적으로 다음만큼의 block을 읽어야 한다.

Average block access = b / 2

조건을 만족하는 여러 record를 찾는 경우에는 더 있는지 확인해야 하므로 마지막 block까지 읽어야 한다.

SELECT EMPNAME, TITLE
FROM EMPLOYEE
WHERE DNO = 2;

범위 조건도 마찬가지이다.

SELECT EMPNAME, TITLE
FROM EMPLOYEE
WHERE SALARY >= 3000000
  AND SALARY <= 4000000;

Heap file 계산 예제

조건은 다음과 같다.

항목	값
Record 수	10,000,000
Record length	200 bytes
Block size	4,096 bytes
Block access time	10 ms

한 block에 들어가는 record 수는 다음과 같다.

⌊4096 / 200⌋ = 20

전체 block 수는 다음과 같다.

10,000,000 / 20 = 500,000 blocks

Heap file에서 특정 record를 찾는 평균 block access 수는 다음과 같다.

500,000 / 2 = 250,000 blocks

따라서 평균 검색 시간은 다음과 같다.

250,000 * 10ms = 2,500,000ms = 2,500s ≈ 42min

5.2 Sequential file

sequential file은 record들이 하나 이상의 field 값, 일반적으로 search key 값의 순서대로 저장된 file이다.

예를 들어 EMPLOYEE file이 EMPNO 순서로 저장되어 있다면 EMPNO가 search key이다.

1003 → 1365 → 2106 → 3011 → 3426 → 3427 → 4377

Search key 기준의 특정 record 검색은 binary search를 사용할 수 있다.

SELECT TITLE
FROM EMPLOYEE
WHERE EMPNO = 1365;

비용은 대략 다음과 같다.

Search cost ≈ log2(b)

하지만 search key가 아닌 field 조건은 여전히 전체 탐색이 필요할 수 있다.

SELECT EMPNAME, TITLE
FROM EMPLOYEE
WHERE SALARY >= 3000000
  AND SALARY <= 4000000;

조건 필드	Sequential file 성능
Search key	binary search 가능
Search key가 아닌 field	full scan 필요 가능

Sequential file 계산 예제

앞의 예제에서 전체 data block 수는 500,000개였다. Search key 기준 binary search를 사용하면 필요한 block access 수는 다음과 같다.

⌈log2(500,000)⌉ = 19

Block access time이 10ms이면 검색 시간은 다음과 같다.

19 * 10ms = 190ms

Heap file의 약 42분과 비교하면 search key 기반 검색에서는 큰 차이가 난다.

5.3 Heap file과 sequential file 비교

구분	Heap file	Sequential file
저장 순서	삽입 순서	search key 순서
Insert	빠름	정렬 유지 필요로 느릴 수 있음
Delete	느림, 재조직 필요 가능	느림, 재조직 필요 가능
Full scan	적합	적합
특정 record search	평균 b/2	search key 기준 log2(b)
범위 search	대부분 full scan	search key 기준이면 유리
적합한 상황	삽입 중심, 전체 scan 중심	search key 기반 검색 중심

---

6. Single-level index

single-level index는 <search key, pointer> 쌍을 별도의 index file에 저장하여 record를 빠르게 찾는 구조이다.

<search key, record pointer>

Index는 data file과 별도의 file에 저장된다. 일반적으로 index entry는 전체 data record보다 훨씬 작기 때문에, data file 전체를 탐색하는 것보다 index를 먼저 탐색하는 것이 빠르다.

6.1 Index의 기본 성질

항목	설명
Search key	index가 정의된 field
Pointer	record 또는 block 위치를 가리키는 값
정렬 기준	index entry는 search key 오름차순 정렬
Index file 크기	data file보다 훨씬 작음
Index 개수	하나의 file에 여러 index 정의 가능

Search key는 반드시 candidate key일 필요가 없다. EMPNO처럼 unique한 값도 가능하고, DNO처럼 중복 가능한 값도 가능하다.

6.2 Primary index

primary index는 search key가 data file의 primary key인 index이다. Data file은 primary key 값에 따라 정렬되어 있어야 한다.

항목	Primary index
Search key	primary key
Data file	primary key 순서로 정렬
Index type	보통 sparse index 가능
개수	relation마다 최대 1개

Primary index는 보통 각 data block마다 하나의 index entry를 갖는 sparse index로 만들 수 있다.

10 → data block 0
30 → data block 1
50 → data block 2
70 → data block 3
90 → data block 4

Primary index 계산 예제

조건은 다음과 같다.

항목	값
Record 수	10,000,000
Record length	200 bytes
Block size	4,096 bytes
Search key length	20 bytes
Block pointer length	4 bytes
Index entry length	24 bytes
Block access time	10 ms

Data block의 blocking factor는 다음과 같다.

⌊4096 / 200⌋ = 20

전체 data block 수는 다음과 같다.

10,000,000 / 20 = 500,000 blocks

Primary index가 sparse index라면 data block마다 index entry 하나가 필요하다.

Index entry count = 500,000

Index block 하나에 들어가는 index entry 수는 다음과 같다.

⌊4096 / 24⌋ = 170

Index block 수는 다음과 같다.

⌈500,000 / 170⌉ = 2,942 blocks

Single-level index에서 binary search를 사용하면 block access 수는 다음과 같다.

⌈log2(2942)⌉ + 1 = 13

여기서 +1은 실제 data block 접근이다.

13 * 10ms = 130ms

6.3 Clustering index

clustering index는 data file이 search key 값에 따라 정렬되어 있을 때 정의되는 index이다. Search key가 반드시 primary key일 필요는 없다.

예를 들어 DNO는 primary key가 아니지만, EMPLOYEE record들이 DNO 순서로 물리적으로 모여 있다면 DNO에 대한 clustering index를 만들 수 있다.

DNO = 1 records → nearby blocks
DNO = 2 records → nearby blocks
DNO = 3 records → nearby blocks

Clustering index는 range query에 유리하다.

SELECT *
FROM EMPLOYEE
WHERE SALARY >= 3000000
  AND SALARY <= 4000000;

Data file이 SALARY 기준으로 clustering되어 있다면, 범위 시작점을 찾은 뒤 연속적으로 block을 읽으면 된다.

구조	Range query 성능
Clustering index	관련 record가 가까워 유리
Non-clustering index	pointer가 여러 block으로 흩어질 수 있음

Clustering index 계산 예제

조건은 다음과 같다.

항목	값
Record 수	10,000,000
Distinct search key 수	800,000
Block size	4,096 bytes
Search key length	20 bytes
Block pointer length	4 bytes
Index entry length	24 bytes

Clustering index는 각각의 distinct key value마다 하나의 index entry를 가진다.

Index entry count = 800,000

Index block 하나에 들어가는 entry 수는 다음과 같다.

⌊4096 / 24⌋ = 170

Index block 수는 다음과 같다.

⌈800,000 / 170⌉ = 4,706 blocks

Binary search와 data block 접근을 합하면 다음과 같다.

⌈log2(4706)⌉ + 1 = 14

검색 시간은 다음과 같다.

14 * 10ms = 140ms

6.4 Secondary index

secondary index는 data file이 해당 search key 값에 따라 정렬되어 있지 않을 때 정의되는 index이다.

예를 들어 data file은 EMPNO 순서로 정렬되어 있지만 SALARY로도 빠르게 검색하고 싶다면 SALARY에 secondary index를 만들 수 있다.

SELECT *
FROM EMPLOYEE
WHERE SALARY = 4000000;

Secondary index는 일반적으로 dense index이다. Data file이 search key 순서로 정렬되어 있지 않기 때문에, 각 record 또는 각 search key 값에 충분한 pointer가 필요하다.

6.5 Sparse index와 dense index

구분	Sparse index	Dense index
Entry 개수	data block마다 1개	record마다 1개
크기	작음	큼
주 사용처	primary index, clustering index	secondary index
Data file 정렬	보통 필요	없어도 가능
Index 단계 수	적음	많아질 수 있음
장점	공간/갱신 비용 작음	index-only query에 유리 가능

Dense index 계산 예제는 다음과 같다.

Index entry count = 10,000,000
Entries per block = ⌊4096 / 24⌋ = 170
Index block count = ⌈10,000,000 / 170⌉ = 58,824
Block access = ⌈log2(58,824)⌉ + 1 = 17
Search time = 17 * 10ms = 170ms

Sparse index는 일반적으로 dense index보다 작고 갱신 비용도 적다. 다만 질의가 index에 정의된 attribute만 필요로 하는 경우에는 dense index가 data file을 접근하지 않고 처리할 수 있어 유리할 수 있다.

SELECT COUNT(*)
FROM EMPLOYEE
WHERE DNO = 2;

이처럼 index만으로 답을 만들 수 있는 query를 index-only query 관점으로 볼 수 있다.

---

7. Multi-level index

Index도 커지면 index 자체를 탐색하는 시간이 길어진다. multi-level index는 single-level index를 disk 상의 하나의 ordered file로 보고, 그 위에 다시 index를 정의하는 구조이다.

Master index
→ second-level index
→ first-level index
→ data file

가장 상위 단계 index를 master index라고 한다. Master index는 모든 entry가 한 block에 들어갈 때까지 index를 반복적으로 만든 결과이다. 한 block이면 main memory에 상주시킬 수 있으므로 disk I/O를 줄일 수 있다.

대부분의 실제 multi-level index는 B+ tree를 사용한다.

7.1 Multi-level index 계산 예제

앞의 primary index 예제 값을 그대로 사용한다.

항목	값
Record 수	10,000,000
Record length	200 bytes
Block size	4,096 bytes
Data block 수	500,000
Index entry length	24 bytes
Index entries per block	170

1단계 index는 data block을 직접 가리킨다.

First-level index blocks = ⌈500,000 / 170⌉ = 2,942

2단계 index는 1단계 index block들을 가리킨다.

Second-level index blocks = ⌈2,942 / 170⌉ = 18

3단계 index는 2단계 index block들을 가리킨다.

Third-level index blocks = ⌈18 / 170⌉ = 1

이 3단계 index가 master index이다.

Master index는 main memory에 상주할 수 있으므로 실제 disk access는 다음과 같다.

Second-level index block access = 1
First-level index block access = 1
Data block access = 1
Total disk access = 3

Block access time이 10ms라면 다음과 같다.

3 * 10ms = 30ms

Single-level index의 130ms와 비교하면 큰 차이가 난다.

구조	Disk access	Search time
Single-level index	13	130ms
Multi-level index	3	30ms

7.2 SQL의 index 정의

PRIMARY KEY로 명시한 attribute에 대해서는 DBMS가 자동으로 primary index를 생성할 수 있다.

CREATE TABLE EMPLOYEE (
  EMPNO INTEGER PRIMARY KEY,
  EMPNAME VARCHAR(20),
  DNO INTEGER
);

UNIQUE로 명시한 attribute에 대해서는 DBMS가 자동으로 secondary index를 생성할 수 있다.

CREATE TABLE EMPLOYEE (
  EMPNO INTEGER PRIMARY KEY,
  EMAIL VARCHAR(100) UNIQUE
);

일반 attribute에 index를 추가하려면 DBMS별 CREATE INDEX 문을 사용한다.

CREATE INDEX EmpDnoIndex
ON EMPLOYEE(DNO);

7.3 Composite index

두 개 이상의 attribute 조합에 대해 하나의 index를 정의할 수 있다.

CREATE INDEX EmpIndex
ON EMPLOYEE (DNO, SALARY);

이 index는 다음 query에 활용될 수 있다.

SELECT *
FROM EMPLOYEE
WHERE DNO = 3
  AND SALARY = 4000000;

Composite index에서는 attribute 순서가 중요하다. (DNO, SALARY) index는 보통 다음 조건에 유리하다.

WHERE DNO = 3

WHERE DNO = 3 AND SALARY = 4000000

WHERE DNO = 3 AND SALARY >= 3000000

반면 SALARY만 조건에 사용하는 query는 index를 제한적으로만 활용할 수 있다.

WHERE SALARY = 4000000

구분 기준은 다음과 같다.

(DNO, SALARY) index
→ DNO 조건 있음: 유리
→ DNO + SALARY 조건 있음: 매우 유리
→ SALARY만 조건 있음: 제한적

7.4 Index의 trade-off

Index는 검색 속도를 높이지만, 저장 공간과 갱신 비용을 증가시킨다.

효과	설명
Search 성능 향상	조건에 맞는 record를 빠르게 찾음
저장 공간 증가	index file을 별도로 저장해야 함
Insert 비용 증가	data file 삽입 후 index도 갱신
Delete 비용 증가	data file 삭제 후 index entry도 삭제
Update 비용 증가	indexed attribute가 바뀌면 index도 수정

단, 소수의 record를 UPDATE 또는 DELETE하는 경우에는 index가 대상 record를 빠르게 찾도록 도와 전체 수행 시간이 개선될 수 있다.

DELETE FROM EMPLOYEE
WHERE EMPNO = 1365;

Index가 없다면 삭제 대상 record를 찾기 위해 full scan이 필요할 수 있다. Index가 있으면 대상 record를 빠르게 찾은 뒤 삭제할 수 있다. 다만 삭제 후 index 유지 비용은 별도로 발생한다.

---

8. Index selection과 database tuning

Index selection은 workload를 기준으로 수행해야 한다. 가장 중요한 query와 update, 각각의 수행 빈도, 목표 성능을 고려한다.

8.1 Query 분석 기준

각 query에 대해 다음을 확인한다.

기준	확인할 내용
접근 relation	어떤 table을 읽는가
검색 attribute	어떤 column을 조건에 사용하는가
Selection condition	WHERE 절의 selection 조건
Join condition	WHERE 또는 JOIN ON의 join 조건
Selectivity	조건이 전체 tuple 중 얼마나 적은 tuple을 선택하는가

selectivity는 다음과 같다.

selectivity = 선택된 tuple 수 / 전체 tuple 수

예를 들어 전체 tuple이 10,000개이고 조건을 만족하는 tuple이 200개라면 다음과 같다.

selectivity = 200 / 10,000 = 0.02 = 2%

선별력이 낮을수록 index 효과가 크다.

낮은 selectivity → 적은 tuple 선택 → index 효과 큼
높은 selectivity → 많은 tuple 선택 → full scan이 나을 수 있음

8.2 Update 분석 기준

각 update에 대해 다음을 확인한다.

기준	확인할 내용
접근 relation	어떤 table이 갱신되는가
조건 attribute	갱신 대상을 찾는 조건 column
Selectivity	소수만 갱신하는가, 다수를 갱신하는가
Update type	INSERT, DELETE, UPDATE 중 무엇인가
영향 attribute	index가 걸린 column이 바뀌는가

예를 들어 다음 query는 EMPNO index가 있으면 대상 record를 빠르게 찾을 수 있다.

UPDATE EMPLOYEE
SET SALARY = 4000000
WHERE EMPNO = 1365;

하지만 SALARY에 index가 있다면 SALARY 값 변경 후 해당 index도 갱신해야 한다.

8.3 Index 선정 지침

지침	내용
1	Primary key는 clustering index의 좋은 후보
2	Foreign key도 index의 중요한 후보
3	distinct value 수가 전체 record 수와 비슷하고 equality condition에 사용되면 non-clustering index 후보
4	큰 relation에서 대부분 query가 2%~4% 미만의 tuple만 검색하면 index 생성 고려
5	자주 갱신되는 attribute에는 index를 피하는 것이 좋음
6	갱신이 빈번한 relation에는 index를 많이 만들지 않음
7	Candidate key도 index 후보
8	Index는 record들을 충분히 분할할 수 있어야 함
9	Integer attribute는 index 후보로 적합
10	강의자료 기준으로 VARCHAR attribute에는 index를 피하는 방향으로 설명됨
11	작은 file에는 index가 필요하지 않을 수 있음
12	대량 insert 시 index를 제거하고 삽입 후 다시 생성하는 것이 좋음

주의할 점은 VARCHAR index를 항상 만들면 안 된다는 의미로 일반화하면 안 된다는 것이다. 실제 DBMS에서는 email, username, code처럼 VARCHAR라도 선별력이 높고 자주 검색되면 index를 만들 수 있다. 다만 이 강의자료의 기본 지침은 integer attribute를 선호하고 variable-length string index는 신중히 선택하는 방향이다.

8.4 Index가 사용되지 않을 수 있는 경우

Index를 만들어도 DBMS optimizer가 항상 사용하는 것은 아니다.

경우	설명
System catalog가 오래됨	통계 정보가 실제 데이터 상태와 달라 optimizer 판단이 틀릴 수 있음
Relation이 작음	full scan이 index access보다 빠를 수 있음
Indexed attribute에 산술 연산 적용	원본 index 순서를 활용하기 어려움
Indexed attribute에 내장 함수 적용	모든 row에 함수 적용이 필요할 수 있음
NULL 조건	일반적으로 index 사용이 제한될 수 있음

산술 연산 예시는 다음과 같다.

SELECT *
FROM EMPLOYEE
WHERE SALARY * 12 > 40000000;

이 경우 SALARY에 index가 있어도 SALARY * 12 결과를 기준으로 비교하므로 index 사용이 어려울 수 있다. 가능한 경우 다음처럼 column 자체에 연산을 적용하지 않는 형태로 바꾸는 것이 좋다.

SELECT *
FROM EMPLOYEE
WHERE SALARY > 40000000 / 12;

내장 함수 예시는 다음과 같다.

SELECT *
FROM EMPLOYEE
WHERE SUBSTR(EMPNAME, 1, 1) = '김';

EMPNAME에 index가 있어도 SUBSTR() 결과 기준 조건이므로 일반 index를 활용하기 어려울 수 있다.

NULL 조건 예시는 다음과 같다.

SELECT *
FROM EMPLOYEE
WHERE MANAGER IS NULL;

강의자료 기준으로는 NULL 값에 대해서 일반적으로 index가 사용되지 않을 수 있다고 정리한다.

8.5 Query tuning 지침

질의 튜닝에서는 불필요한 연산과 데이터 접근을 줄이는 것이 중요하다.

지침	이유
DISTINCT 사용 최소화	중복 제거를 위한 sort 또는 hash 비용 발생 가능
GROUP BY, HAVING 사용 최소화	grouping, aggregation, filtering 비용 발생
임시 relation 사용 피하기	중간 결과 저장과 재읽기로 I/O 증가 가능
SELECT * 대신 필요한 attribute 명시	불필요한 column 읽기와 전송 비용 감소

예를 들어 다음보다,

SELECT *
FROM EMPLOYEE;

필요한 column만 명시하는 것이 좋다.

SELECT EMPNAME, TITLE
FROM EMPLOYEE;

특히 BLOB이나 큰 text column이 포함된 table에서 SELECT *는 불필요한 I/O를 크게 증가시킬 수 있다.

---

9. 자칫 실수하기 쉬운 구분 기준

9.1 Search key와 primary key

search key는 index가 정의된 field이다. 반드시 primary key일 필요는 없다.

용어	의미
Primary key	tuple을 유일하게 식별하는 key
Search key	index 검색 기준으로 사용하는 field

DNO, SALARY처럼 중복 가능한 attribute도 search key가 될 수 있다.

9.2 Primary index와 clustering index

구분	Primary index	Clustering index
Search key	primary key	primary key가 아닐 수도 있음
Data file 정렬	primary key 순서	search key 순서
Entry	보통 block당 하나 가능	distinct search key value마다 하나
장점	특정 tuple 검색	range query, 관련 record 연속 접근

9.3 Secondary index와 dense index

Secondary index는 data file이 search key 기준으로 정렬되어 있지 않은 경우의 index이다. 일반적으로 dense index가 된다.

Secondary index → usually dense index

하지만 dense index 자체는 “record마다 index entry가 있는 구조”를 뜻하는 더 일반적인 개념이다.

9.4 Sparse index와 dense index

구분	Sparse index	Dense index
기준	data block마다 entry	record마다 entry
크기	작음	큼
전제	data file 정렬 필요	정렬 없어도 가능
대표 사용	primary, clustering	secondary

9.5 Index가 많을수록 항상 좋은가?

아니다. Index는 search를 빠르게 하지만 write workload에는 비용을 추가한다.

Index 추가
→ SELECT 성능 개선 가능
→ INSERT/DELETE/UPDATE 비용 증가
→ 저장 공간 증가

따라서 workload에서 read와 write의 비율, query selectivity, update frequency를 함께 봐야 한다.

---

10. 핵심 요약

• 물리적 데이터베이스 설계는 relation을 실제 disk file 구조로 사상하고, workload에 맞는 storage structure와 access method를 선택하는 과정이다.
• DBMS는 데이터를 disk에서 block 단위로 읽어 buffer에 올린 뒤 처리한다.
• Disk I/O 비용은 seek time, rotational delay, transfer time으로 구성되며, 성능 최적화의 핵심은 block access 수를 줄이는 것이다.
• heap file은 insert가 빠르지만 특정 record 검색과 조건 검색에 약하다.
• sequential file은 search key 기준 검색과 range access에 유리하지만 insert/delete 비용이 커질 수 있다.
• single-level index는 <search key, pointer> entry를 통해 data file 접근을 빠르게 한다.
• primary index는 primary key 기준, clustering index는 search key 기준으로 정렬된 data file에 대해 정의된다.
• secondary index는 data file이 search key 순서로 정렬되지 않은 경우에 사용되며, 일반적으로 dense index이다.
• sparse index는 block마다 entry를 두고, dense index는 record마다 entry를 둔다.
• Index가 커지면 index 자체에 다시 index를 두는 multi-level index가 필요하며, 실제 DBMS에서는 대개 B+ tree를 사용한다.
• Index 선정은 query/update workload와 selectivity를 기준으로 해야 한다.
• selectivity = 선택된 tuple 수 / 전체 tuple 수이며, 낮은 selectivity일수록 index 효과가 크다.
• Index가 있어도 산술 연산, 내장 함수, NULL 조건, 작은 relation, 오래된 통계 정보 때문에 사용되지 않을 수 있다.
• Query tuning에서는 DISTINCT, GROUP BY, HAVING, 임시 relation, SELECT * 사용을 신중히 줄인다.