DB 기초 - 1

이 글은 포스텍 한욱신 교수님의 데이터베이스시스템(CSED421) 강의를 기반으로 재구성한 것입니다.

 

DBMS의 정의

 DBMS란 database를 관리/유지시켜주는 소프트웨어이다. 사용 이유는 data independency와 효율적 접근, 보안, 동시 접근을 위해서이다. file system에 비해서 cost는 크지만 redundancy가 없고, constraint를 유지할 수 있다는 장점이 있다.

 

 

 

Transction & ACID

transaction : DBMS의 상호작용 단위. transaction은 다음 4가지 성질을 가지고 있다.

• Atomicity : transction은 실행되거나, 실행되지 않거나 둘 중 하나의 상태만 가진다. 중간에 끊기지 않는다.
• Consistency : transaction의 실행 결과는 항상 일관성이 있다. (정해둔 규칙을 위배하지 않는다.)
• Isolation : transaction 사이에 다른 trasnaction이 낄 수 없다.
• Durability : DBMS가 꺼져도 수행된 transaction은 반영되어 있어야 한다.

 

 

 

Data Model & Schema

 data model은 data를 묘사하기 위한 개념의 collection.

 schema는 data의 특정 collection의 설명을 말한다. data의 관계, 구조, 표현 방법을 표시하는 구조이다.

 

 schema는 크게 3가지 구조가 있다.

• external schema (view) : 각 user가 접근하는 table
• conceptual schema (logical) : 어떤 종류의 data가 저장되는지
• physical schema (physical) : data가 어떻게 저장되는지

 

Data Independence

• physical data independence : physical structure를 바꾸어도 logical schema는 불변하는 특징
• logical data independence : logcial structure를 바꾸어도 external schema는 불변하는 특징

 

 

 

Buffer Pool

 OS에서 file을 byte sequence로 봤던 것처럼, DB는 file - record(tuple) - page 3개의 structure로 분리해 본다.

 DBMS는 disk에 있는 page를 memory에 frame으로 저장하는데, 이 공간을 buffer pool이라 한다. OS의 paging과 매우 유사하지만 조금은 다르다. (DB는 prefetch 예측하기 때문)

 

 

 

Index - B+ tree

• m-way balanced tree (각 node에는 최대 m-1개의 element가 들어있고 각 node는 최대 m개의 child를 가질 수 있다)
  • balanced tree인 만큼, child의 height 차이가 1 이상 나지 않는다.
• 모든 leaf node는 doubly linked list
• space utilization이 50% 이상이어야 한다. 
  • leaf node는 $\left \lfloor \frac{n+1}{2} \right \rfloor$개의 pointer가 있어야 하고,
  • non-leaf node는 $\left \lceil \frac{n+1}{2} \right \rceil$개의 pointer가 있어야 한다.

B+ tree 노드 구조

 

삽입

• simple case : 해당하는 key의 leaft node에 그냥 넣음
• leaf overflow가 발생하는 경우 : 반 쪼개어 parent에 push한다.
• non-leaf overflow가 발생하는 경우 : 쪼갬
• root overflow가 발생하는 경우 : 쪼갬

 

삭제

• simple case : 해당하는 key를 삭제해도 utilization이 50% 이상인 경우, 그냥 삭제
• coalesce with sibiling : sibiling과 합치는 방법. 이전 leat node의 largest key를 가져오거나 이후 leaf node의 smallest key를 가져온다.
• redistribute key : key를 재조정해 utilization을 맞추는 방법. sibling과 parent 사이에서 key를 재조정한다.
• non-leaf에서 coalesce나 redistribute : 같은 방법을 취한다.

 

Index 쓸 때 장/단점

• 장점 : index에 있는 정보에 대해서는 read 속도가 빨라진다.
• 단점 : insert/delete/update 속도가 느려진다. 해당 tree를 수정해야 하기 때문.
• 자주 select되고, 덜 update되는 column에 대해 쓰는 것이 좋다. + FK나 join도.
• 공통적으로 사용하는 것 - index column의 순서는 cardinality가 높은 것부터 낮은 순으로 나열하는 것이 좋다. (data의 unique 개수) 

 

 

Hash Table과의 차이점

 hash table은 하나의 entry에 대해서는 O(1)이지만, range search를 하면 전체를 탐색해야 하기 때문에 O(n)이라는 단점이 있다.

 

 

 

Relational Algebra - JOIN

 projection, selection 등 여러 가지 표기법이 있지만, 여기서는 join만 살펴보고자 한다. 제일 헷갈리니까.

• theta join (conditional join) R⋈$_c$S : 조건 c를 만족하는 tuple만 가져온다.
• equi join : theta join에서 조건 c가 equal로만 이뤄져 있는 theta join
• natrual join R⋈S : 모든 공통 field에 대한 equi join

 

 

 

Relational Operator Implement

 SQL은 logical plan인데, 이것은 physical operator로 구현된다. 크게 selection, join만 신경쓰면 된다.

 

 cost는 CPU cost, I/O cost 2종류로 나뉘는데 CPU cost는 제하고, I/O cost만 본다.

 

 |R|$_p$를 relation R에 해당하는 page 개수라고 정의하자. 그러면 I/O cost는 |R|$_p$로 나타낼 수 있다.

 

 

Selection - Sequential Scan

for each page P in R:
    for each tuple t in P:
        if theta(t) return

 pseudo code는 위와 같다. 어떤 relation R의 모든 page에 대해 조건을 만족하는 tuple만 return한다. 따라서 cost는 $|R|_p$이다.

 

 

Selection - Index Scan

 B+ tree로 구성된 index가 있고, 해당 index의 key로 검색할 수 있다면 index scan을 할 수 있다. key로 index를 탐색한 후, 그 결과에서 조건을 만족하는 tuple만 return하므로, cost는 log|R|$_p$ + fetch cost이다. log항은 B+ tree로 구성된 index 탐색에 걸리는 시간, fetch cost는 index 탐색 결과 table의 크기이다. 이 때 fetch cost는 clustered 여부에 따라 다르다.

 

Clustered vs Non-Clustered Index

 clustered index는 B+ tree의 leaf node가 가리키는 data page가 index 순서대로 정렬된 index이고, non-clustered index는 그렇지 않은 index. (data page가 index 순서대로 정렬되어 있지 않음)

 

Index Scan I/O Cost

 한 page에 b개 tuple이 있고, predicate의 실행 개수 cardinality를 card(P)로 두자.

• clustered : fetch time은 leaf node access time + card(P)개에 접근하는 시간인데, 이 때 card(P)개의 tuple은 index의 leaf node이기 때문에 연속적이다. 따라서 fetch cost는 $\left \lceil \frac{card(P)}{B} \right \rceil + 1$이다.
• non-clustered : not clustered인 경우, 각 leaf node는 key에 해당하는 data가 있는 page pointer가 있다. pointer는 worst case random이므로 fetch cost는 card(P)라 상한을 둘 수 있다.

 

 

External Sort

 page가 너무 커서 in-memory sort가 불가능한 경우 I/O cost가 어떻게 되는지 보자. 그냥 merge sort할 때 I/O cost가 얼마나 나오는지 생각하면 된다.

 

 어떤 relation R의 sequence S를 size B의 buffer pool을 사용해 정렬한다고 하자. 메모리가 부족하지 떄문에 아래와 같은 단계를 거쳐야 한다.

• buffer pool에 올릴 수 있는 만큼 S를 올린다.
• S를 정렬한다.
• S를 disk에 쓴다.

 

 merge sort를 생각하며 이해해 보자. 한 번의 pass는 아래와 같은 알고리즘으로 수행된다.

• R을 page에 담고, 정렬한 후 다시 disk에 넣는다. 이 I/O cost는 read/write를 수행하므로 cost는 $2|R|_p$이다. 한편 초기 run의 개수는 $\left \lceil \frac{|R|_p}{B} \right \rceil$개이다.
• page를 merge한다. 이 때, buffer pool에 B-1개는 정렬되지 않은 page를, 나머지 1개는 정렬한 후 disk write할 용도로 사용한다.
  • 여기서 run은 합쳐야 하는 정렬된 group의 개수라고 생각하면 되고, pass는 merge 회수라고 생각하면 된다.

 

 그러면 한 번의 pass에서 B-1개의 run이 줄어드므로 k번째 pass에서 merge할 때는 $\left \lceil \frac{|R|_p}{B(B-1)^k} \right \rceil$개의 run이 있을 것이다.

 즉, 전체 pass의 개수는 $\left \lceil log_{B-1}\left \lceil \frac{|R|_p}{B} \right \rceil \right \rceil + 1$이고, 각 pass에서 run들이 정렬될 때마다 [R을 page에 담고, 정렬한 후 다시 disk에 넣는] 연산이 수행된다.

따라서 전체 I/O cost는 $2|R|_p \times (\left \lceil log_{B-1}\left \lceil \frac{|R|_p}{B} \right \rceil \right \rceil +  1)$이다.

 

 

Join - Nested Loop Join

 R join S라고 가정하자.

for tuple r in R:
    for tuple s in S:
        if r == s then add (r, s) to result

 nested loop인 만큼 for문의 중첩으로 join하는 방식이다. 일단 R의 모든 page를 읽어야 하고, 이후 R의 모든 page에 대해 S의 page를 가져온다. I/O cost는 worst case로, I/O cost는 $|R|_p + |R|_p \times |S|_p$이다.

 참고로 outer relation size에 의존하기 때문에 nested loop join의 경우 outer loop에 더 작은 relation을 두면 좋다.

 

 

Join - Blocked Nested Join

 size B의 buffer pool을 사용해 join한다고 하자.

• 일단 R의 모든 page를 읽어야 한다.
• 이후 R의 page 중 B-2개를 먼저 buffer pool에 가져온다.
  • 남는 2개의 공간 중 하나는 S의 page를, 나머지 하나는 join result를 위해 output page로 사용할 것이다.
• 가져온 B-2개의 page에 대해 S의 모든 page에 대해 검사를 수행한다.

 따라서 I/O cost는 $|R|_p + \left \lceil \frac{|R|_p}{B-2} \right \rceil \times |S|_p$이다.

 

 

Join - Sort Merge Join

 sort는 앞에서 다뤘으니 넘어가고, merge만 보자. (보통 정렬되어 있는 것을 sort merge join으로 많이 쓴다.)

 merge sort의 merge에 해당하는 시간복잡도가 O(n)인 것처럼, 여기서 R과 S는 정렬되어 있으므로 같은 방식으로 R의 모든 page와 S의 모든 page를 1번씩만 읽으면 된다. 따라서 I/O cost는 $|R|_p + |S|_p$이다. 

 

 

Join - Grace Hash Join

 grace hash join 이외에도 simple hash join, hybrid hash join 등이 있지만 여기서는 grace hash join만 보겠다.

 

partition

 R과 S의 모든 page를 B-2개의 page로 hashing하고, 그 결과를 buffer pool에 쓴다. 읽고 쓰기 때문에 partition cost는 $2|R|_p + 2|S|_p$이다.

 

hash join

 R의 page 하나, S의 page 하나를 buffer pool에 올리고 hashing된 page B-2개와 비교한다. 이 때 $R_i ⋈ S_j$에서 i != j면 empty이다. hash(k1) != hash(k2)면 k1 != k2이기 때문이다.

 이렇게 R의 모든 page, S의 모든 page를 buffer pool에 쓰므로 이 과정의 cost는 $|R|_p + |S|_p$이다.

 

 총계 $3|R|_p + 3|S|_p$이다.

 

 

 

Query Optimization

 query optimizer는 SQL을 효율적으로 실행할 수 있는 plan을 세운다. 여기서 plan은 다음과 같은 과정을 거쳐 실행될 plan으로 바뀐다.

1. query를 logical operator들의 tree로 표현하고, logical equivalent rule을 적용해 tree를 바꾼다.
2. 앞서 살펴본 physical operator를 적용해 physical plan으로 바꾼다.
3. query optimizer는 plan의 실행 시간을 유추해서 best plan을 도출한다.

logical join에 대해 physical로 바꾸면 nested loop join, sort merge join, hash join로 표기될 수 있다.
logical selection에 대해 physical로 바꾸면 seq scan이나 index scan으로 표기될 수 있다.

 

 실행 순서에 따라 실행 시간이 꽤 많이 바뀌는데,  실행 시간을 유추할 때는 CPU cost와 I/O cost 2가지를 보며, cardinality 예측과 통계 활용 등의 방식을 사용한다. 물론 cardinality 예측이 틀렸거나 통계가 잘못된 경우 등 여러 경우의 수에 의해 좋지 않은 plan이 결정될 수도 있다. query optimizer는 이를 개선하기 위해 query optimizer는 query executor로부터 실행 결과를 feedback받아 cost 추정과 통계를 갱신한다.

 

 

 

잘못된 내용이나 오탈자에 대한 지적, 질문 등은 언제나 환영합니다.