[Relational database] 04. 파일 조직과 인덱스

Chapter 1: 비용 모델과 파일 조직법

• 비용 모델 개요
• 파일 조직법 비교 기준 연산
• 힙 파일
• 정렬 파일
• 해시 파일
• 파일 조직 선택

Chapter 2: 인덱스

• 인덱스 개요
• 클러스터드 인덱스(Clustered Index)
• 넌 클러스터드 인덱스(Non-Clustered Index)
• 밀집 인덱스(Dense Index)와 희소 인덱스(Sparse Index)
• 기본 인덱스(Primary Index)와 보조 인덱스(Secondary Index)
• 복합 키 인덱스

실습: 인덱스 생성(MySQL)

---

Chapter 1: 비용 모델과 파일 조직법

 DB는 Query가 요청될 때 여러 실행 계획을 세우고 비교하여 최적화된 방법으로 query를 실행한다.(Query Optimizer) 그 중 가장 많이 쓰이는 방법이 Cost Model이고, 파일 조직은 파일이 디스크에 저장되어 있을 때 레코드를 파일에 배치하는 방법이다.

비용 모델 개요

• DB는 Query가 요청될 때 Query Optimizer는 여러 실행 계획을 세우고 최적화된 방법을 찾아 실행한다.
• Query Optimizer의 종류 2가지
  1. 규칙 기반 옵티마이저(Rule-Based Optimizer)
  2. 비용 기반 옵티마이저(Cost-Based Optimizer) -> 대부분의 RDBMS가 사용.
• 파일 조직별 입출력 비용만 감안하여, 파일 조직별 비용을 비교한다.
  • B: 페이지의 개수.
  • R: 페이지에 속한 레코드의 개수.
  • D: 디스크 페이지 하나를 읽는 시간.
  • C: 레코드 하나를 처리하는데 걸리는 시간.
  • H: 레코드 하나에 해시 함수를 적용하는데 걸리는 시간.

 

파일 조직법 비교 기준 연산

• 3가지 기본적인 파일조직(비정렬 파일: 힙, 정렬 파일: ISAM, B+ Tree, 해시 파일)에 대해 대표적인 DB 연산들의 비용을 비교. 
  1. Scan: 파일에 있는 모든 레코드를 가져온다. -> 파일에 있는 page들을 disk에서 Buffer Pool로 load.
  2. Equality Selection: Query에서 요구하는 검색어와 같은 문자열임을 만족하는 모든 record를 Buffer Pool로 load.
  3. Range Selection: Query에서 요구하는 범위에 해당하는 모든 record를 Buffer Pool로 load.
  4. Insertion: 주어진 record를 파일에 삽입.
  5. Deletion: RID로 명세된 record를 삭제.

 

힙 파일 (비정렬 파일)

• 정렬되지 않은 단순한 형태의 파일.
  • Scan: B(D+RC)
  • Equality Selection: Candidate Key에 대한 연산일 경우 = 0.5B(D+RC) / 정렬 필드가 아닐 경우 Scan과 동일.
  • Range Selection: B(D+RC)
  • Insertion: 항상 파일 끝에 삽입된다고 가정할 경우 = 2D+C
  • Deletion: C+D

 

정렬 파일

• 특정 필드를 기준으로 정렬된 파일.
  • Scan: B(D+RC)
  • Equality Selection: 정렬된 필드 기준으로 검색할 경우 이진 탐색 = DlogB + ClogR / 정렬 필드가 아닐 경우 Scan과 동일.
  • Range Selection: Equality Selection과 동일.
  • Insertion: 탐색 비용 + B(D+RC)
  • Deletion: 탐색 비용 + B(D+RC)

 

해시 파일

• 특정 필드를 기준으로 정렬된 파일
  • Scan: 1.25B(D+RC)
  • Equality Selection: 찾은 페이지에서 record를 찾기 위해 평균 50%의 페이지를 스캔해야 한다면 = H+D+RC / 검색 조건이 해시 파일의 탐색 키가 아니라면 Scan과 동일.
  • Range Selection: Scan과 동일.
  • Insertion: 탐색비용+C+D
  • Deletion: 탐색비용+C+D

 

파일 조직 선택

• 힙 파일: 저장 성능 우수 / 스캔, 삽입, 삭제 연산이 빠르지만, 탐색이 느리다.
• 정렬 파일: 저장 성능 우수 / 삽입, 삭제 연산이 느리지만, 탐색이 빠르다.
• 해시 파일: 저장 성능 미흡 / 삽입, 삭제 연산이 빠르지만, Range Scan을 지원하지 않고 Scan 성능이 떨어진다.

파일 조직별 cost.

 

RDBMS별 파일 조직

• My SQL: B-Tree
• MS-SQL: Heap, B+ Tree (Primary Key면 B+ Tree, 그 외는 Heap)
• Oracle: Heap, B-Tree, B+ Tree
• PostgreSQL: B+ Tree

---

Chapter 2: 인덱스

인덱스 개요

• Index: 데이터의 검색 속도를 높이기 위한 보조 자료구조.
• 데이터 엔트리(Data Entry)들의 모임 - Data Entry: Index의 키 값과 해당 키 값에 연결된 데이터의 위치 정보를 의미.
• Index는 검색을 위해 특정 column의 값과 그 값에 해당하는 record가 저장된 위치를 연결하는 구조.
• 특정 column 값(ID)을 기준으로 정렬된 상태에서, 다른 column(이름)이 들어왔을 때 찾기 어려우니 이때 Index를 사용. 

Index 구조.

 

클러스터드 인덱스(Clustered Index)

• 파일을 조직할 때, record의 순서를 파일에 대한 index 순서와 동일한 순서로 조직된 Index.
  (Data가 Index의 정렬 순서와 똑같이 정렬되어 있는 것)

Clustered Index

 

넌 클러스터드 인덱스(Non-Clustered Index)

• Clustered Index의 형태가 아닌 Index로, 하나의 데이터 파일에는 하나의 클러스터드 인덱스만 만들 수 있다.
• Index의 정렬 순서와, Data의 정렬 순서가 관계없다.

Non-Clustered Index

 

밀집 인덱스(Dense Index)와 희소 인덱스(Sparse Index)

• Dense Index: 파일에 있는 모든 Key 값(record)에 대해 Index 구성.
• Sparse Index: 하나의 Page에 하나의 Index 구성.
• 일반적으로 Clustered Index -> Sparse Index / Non-Clustered Index -> Dense Index.

Dense Index와 Sparse Index

 

기본 인덱스(Primary Index)와 보조 인덱스(Secondary Index)

• Primary Index: Primary Key를 포함하는 필드들에 대한 Index. (기본 키를 포함하는 필드)
• Secondary Index: Primary Index 이외의 Index.

 

복합 키 인덱스

• Index가 여러 개의 필드를 포함하는 경우.
• 한 파일에 들어있는 2가지 컬럼에 대해서 동시 정렬은 불가능하다. 
• 복합 인덱스 생성
  CREATE INDEX idx_product_categoryno_name ON product(categoryno, productname);

 

실습: 인덱스 생성 (MySQL)

joo@JOOui-MacBookAir ~ % mysql -u root -p
Enter password: 
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 9
Server version: 9.0.1 Homebrew

mysql> show databases;
+--------------------+
| Database           |
+--------------------+
| information_schema |
| Module02           |
| Module03           |
| Module06           |
| mysql              |
| performance_schema |
| sys                |
+--------------------+
7 rows in set (0.00 sec)

mysql> use module03;
Database changed


# Clustered Index 확인.


mysql> desc product;
+-------------+--------------+------+-----+---------+-------+
| Field       | Type         | Null | Key | Default | Extra |
+-------------+--------------+------+-----+---------+-------+
| ProductNo   | int          | NO   | PRI | NULL    |       |
| ProductName | varchar(100) | NO   |     | NULL    |       |
| UnitPrice   | int          | NO   |     | 0       |       |
| Description | text         | YES  |     | NULL    |       |
| CategoryNo  | int          | YES  | MUL | NULL    |       |
+-------------+--------------+------+-----+---------+-------+
5 rows in set (0.00 sec)

# Error: Product Table에 data 삽입하지만, CategoryNo가 Category Table에 없는 값임.
INSERT INTO Product VALUES (1, 'Fellowship of the Rings', 25000, 'Book of Legend', 1);
ERROR 1452 (23000): Cannot add or update a child row: a foreign key constraint fails (`module03`.`product`, CONSTRAINT `fk_Product_CategoryNo` FOREIGN KEY (`CategoryNo`) REFERENCES `category` (`CategoryNo`))

# Category Table에 데이터 삽입
mysql> INSERT INTO Category VALUES(1, 'Novel');
mysql> INSERT INTO Category VALUES(2, 'Science');

mysql> SELECT * FROM Category;
+------------+--------------+
| CategoryNo | CategoryName |
+------------+--------------+
|          1 | Novel        |
|          2 | Science      |
+------------+--------------+
2 rows in set (0.00 sec)

# Product Table에 데이터 삽입.
mysql> INSERT INTO Product VALUES (1, 'Fellowship of the Rings', 25000, 'Book of Legend', 1);
Query OK, 1 row affected (0.00 sec)

mysql> SELECT * FROM Product;
+-----------+-------------------------+-----------+----------------+------------+
| ProductNo | ProductName             | UnitPrice | Description    | CategoryNo |
+-----------+-------------------------+-----------+----------------+------------+
|         1 | Fellowship of the Rings |     25000 | Book of Legend |          1 |
+-----------+-------------------------+-----------+----------------+------------+
1 row in set (0.00 sec)

# Error: Product Table에 삽입할 Data의 PK가 중복됨.
INSERT INTO Product VALUES (1, 'The Two Towers', 25000, 'Book of Legend', 1);
ERROR 1062 (23000): Duplicate entry '1' for key 'Product.PRIMARY'

INSERT INTO Product VALUES (2, 'The Two Towers', 25000, 'Book of Legend', 1);
INSERT INTO Product VALUES (4, 'Science', 45000, 'Book of Legend', 2);
INSERT INTO Product VALUES (5, 'Newton', 8000, 'Science Magazine', 2);
INSERT INTO Product VALUES (3, 'Return of the King', 25000, 'Book of Legend', 1);
Query OK, 1 row affected (0.00 sec)


# Data 삽입 순서와 관계없이 Product Table의 PK인 ProductNo를 기준으로 정렬됨!
# Product Table 생성시 Primary Key를 지정했기 때문에
mysql> SELECT * FROM Product;
+-----------+-------------------------+-----------+------------------+------------+
| ProductNo | ProductName             | UnitPrice | Description      | CategoryNo |
+-----------+-------------------------+-----------+------------------+------------+
|         1 | Fellowship of the Rings |     25000 | Book of Legend   |          1 |
|         2 | The Two Towers          |     25000 | Book of Legend   |          1 |
|         3 | Return of the King      |     25000 | Book of Legend   |          1 |
|         4 | Science                 |     45000 | Book of Legend   |          2 |
|         5 | Newton                  |      8000 | Science Magazine |          2 |
+-----------+-------------------------+-----------+------------------+------------+
5 rows in set (0.00 sec)


# Non-Clustered Index 생성 및 확인.


# Product Table의 CategoryNo 컬럼에 Index를 생성.
mysql> CREATE INDEX idx_Product_CategoryNo ON Product(CategoryNo);
Query OK, 0 rows affected (0.02 sec)
Records: 0  Duplicates: 0  Warnings: 0

# Product Table의 Index 확인.
mysql> show index FROM Product;
+---------+------------+------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table   | Non_unique | Key_name               | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+---------+------------+------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Product |          0 | PRIMARY                |            1 | ProductNo   | A         |           4 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| Product |          1 | idx_Product_CategoryNo |            1 | CategoryNo  | A         |           2 |     NULL |   NULL | YES  | BTREE      |         |               | YES     | NULL       |
+---------+------------+------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
2 rows in set (0.01 sec)

INSERT INTO Product VALUES (7, 'World War Z', 20000, 'Most interesting book', 1);
INSERT INTO Product VALUES (6, 'Bourne Identity', 18000, 'Spy Novel', 1);

# 입력 순서와 상관없이 정렬된 상태로 data가 저장됨.
mysql> SELECT * From Product;
+-----------+-------------------------+-----------+-----------------------+------------+
| ProductNo | ProductName             | UnitPrice | Description           | CategoryNo |
+-----------+-------------------------+-----------+-----------------------+------------+
|         1 | Fellowship of the Rings |     25000 | Book of Legend        |          1 |
|         2 | The Two Towers          |     25000 | Book of Legend        |          1 |
|         3 | Return of the King      |     25000 | Book of Legend        |          1 |
|         4 | Science                 |     45000 | Book of Legend        |          2 |
|         5 | Newton                  |      8000 | Science Magazine      |          2 |
|         6 | Bourne Identity         |     18000 | Spy Novel             |          1 |
|         7 | World War Z             |     20000 | Most interesting book |          1 |
+-----------+-------------------------+-----------+-----------------------+------------+
7 rows in set (0.00 sec)

# CategoryNo 컬럼에 대해 생성된 Secondary Index 기준으로 정렬됨.
mysql> SELECT * FROM Product WHERE CategoryNo > 0;
+-----------+-------------------------+-----------+-----------------------+------------+
| ProductNo | ProductName             | UnitPrice | Description           | CategoryNo |
+-----------+-------------------------+-----------+-----------------------+------------+
|         1 | Fellowship of the Rings |     25000 | Book of Legend        |          1 |
|         2 | The Two Towers          |     25000 | Book of Legend        |          1 |
|         3 | Return of the King      |     25000 | Book of Legend        |          1 |
|         6 | Bourne Identity         |     18000 | Spy Novel             |          1 |
|         7 | World War Z             |     20000 | Most interesting book |          1 |
|         4 | Science                 |     45000 | Book of Legend        |          2 |
|         5 | Newton                  |      8000 | Science Magazine      |          2 |
+-----------+-------------------------+-----------+-----------------------+------------+
7 rows in set (0.00 sec)

# ORDER BY를 활용한 정렬 -> DB가 클수록 비효율적이다.
mysql> SELECT * FROM Product ORDER BY CategoryNo;
+-----------+-------------------------+-----------+-----------------------+------------+
| ProductNo | ProductName             | UnitPrice | Description           | CategoryNo |
+-----------+-------------------------+-----------+-----------------------+------------+
|         1 | Fellowship of the Rings |     25000 | Book of Legend        |          1 |
|         2 | The Two Towers          |     25000 | Book of Legend        |          1 |
|         3 | Return of the King      |     25000 | Book of Legend        |          1 |
|         6 | Bourne Identity         |     18000 | Spy Novel             |          1 |
|         7 | World War Z             |     20000 | Most interesting book |          1 |
|         4 | Science                 |     45000 | Book of Legend        |          2 |
|         5 | Newton                  |      8000 | Science Magazine      |          2 |
+-----------+-------------------------+-----------+-----------------------+------------+
7 rows in set (0.00 sec)

 

* Product Table에 ProductNo는 정렬되어 있어서 이걸로 데이터를 찾을때는 binary search or equality selection한다.

그러나 CategoryNo는 정렬되어 있지 않아서 Scan 해야 한다. 따라서 CategoryNo에 대한 Non-Clustered Index를 생성하면, 데이터를 검색할 때 Scan이 아닌 Index에서 binary search로 검색한다.

그래서 mysql> select * from product where categoryno > 0; 에서 ProductNo(PK)로 하면 Scan 해야 하니까

Query Optimizer가 Non-Clustered Index(CategoryNo)를 사용해서 정렬한 것이다.

 

* ORDER BY를 사용한 정렬은 정렬 후 그 결과를 메모리 또는 디스크에서 재정렬해야 한다. 따라서 성능이 떨어진다.
(Index는 이미 정렬된 상태로 데이터를 검색할 수 있다.)

 

* 복합 인덱스 생성

CREATE INDEX idx_product_categoryno_name ON product(categoryno, productname);

 

---

 

 

출처: https://github.com/gikpreet/class-relational_database

GitHub - gikpreet/class-relational_database