DB Join algorithm

Introduction to Join Evaluation

• Join 명령어는 데이터베이스에서 두 테이블을 연결하여 구체화 시키거나 (중간 단계 테이블로 저장) 즉석에서 사용 (이번에는 후자의 경우만 고려한다) 할 수 있게 만들어준다.
• 가장 많이 사용되는 명령어 중 하나로 최적화가 잘 돼있다.
• 조인 알고리즘의 목표는 이러한 연결을 더 효율적으로 잘 하는 것이다.

Simple Nested Loops Join

For each tuple r in R do
     For each tuple s in S do
        If r and s satisfy the join condition
           Then output the tuple <r,s>

Block Nested Loops Join

• 기존의 SNLJ에서 |R| < |S| 라고 가정한다면, S는 R의 모든 튜플에 대하여 한 번씩 스캔이 될 것이다. 만약 조건을 만족하는 R 튜플이 많다면, 그리고 S에 조인을 위한 인덱스가 없다면 이 비용은 배우 비쌀 것이다.

• BNLJ는 R 튜플의 "묶음" 당 한 번의 S 스캔을 실행함으로 효율을 높인다.

• 예를 들면 BNLJ의 방식 중 하나는 R 튜플의 모든 페이지를 메모리로 읽고 hash table 으로 로드한다. 그리고 S를 스캔할 때 hash table을 이용하여 현재 로드된 R의 페이지의 어떤 튜플이라도 매치하는 S의 튜플을 찾는다. 이렇게 하여 S의 스캔 횟수를 줄일 수 있다.
• DB에서 성능에 중요한 부분은 디스크 I/O가 일어나는 횟수인데 이가 줄어든다.

• 또 다른 변형은 R의 페이지를 가능한 많이 메모리에 로드하여 모두 hash table화 하는 것이다. 그리고 반복적으로 S를 스캔한다. 이렇게 하면 S의 스캔 횟수를 더 줄일 수 있다. 
• 사실 이러한 알고리즘은 따로 분류되어 hash join 알고리즘이라 불린다.

Index Nested Loops Join

• 기존의 접근 방법은 R x S 을 항상 실행하고 존재하는 인덱스를 사용하지 않는 문제가 있다.
• 만약 한 릴레이션 (S라고 하자)의 join 열에 인덱스가 있다면 이 릴레이션을 inner로 만들고 이 인덱스를 사용하지 않을 이유가 없다.
• outer 릴레이션 R을 스캔 한다 (한 번에 한 페이지씩).
• R의 각 튜플 r에 대해 인덱스를 이용하여 S에서 일치하는 튜플을 찾아낸다.
• eqi-join 인 경우에 사용한다. 다른 경우에도 사용할 수는 있지만 매우 효율이 좋지 않음.
• Nested Loop Join과 같은 방식으로 읽어오고 비교한다.
• Cost of Indexed-Nested Loop
• worst cast (r 테이블의 한 개 블록만 메모리에 수용)
• C = bi + nr * c
• c는 r의 튜플과 조인조건을 만족하는 s의 튜플을 찾는 비용이며, 접근한 인덱스의 노드 블록의 수가 비용이 됨.
• 만약 r과 s 두 개 릴레이션 모두에 조인 애트리뷰트에 대한 인덱스가 사용 가능하다면?
• 큰 릴레이션을 inner로(인덱스를 사용하는 쪽으로) 보낸다.
• 비용 c의 높이는 인덱스 트리의 높이에 비례해서 급격하게 줄어든다.
• 트리에서 찾는 비용은 O(lg n) 이니까..

Sort-Merge Join

• R x S의 생성을 피하는 또 다른 방법으로 SMJ가 있다.

• 인덱스가 없을 때 SNLJ 보다 좋은 성능을 내기 위해 사용.

• 동등 조인 조건에 대해서만 수행이 가능하다.
• 동등 조인이란: Equi 조인이라고도 하며, 공통 컬럼의 동등 비교만을 한다.
• 즉 <, > 등의 부등호는 사용하지 않고 ON a.col1 = b.col2 처럼 동등한 경우만을 고려한다.

• SMJ는 두 단계로 나뉜다.
• 정렬 단계
• external sort 알고리즘을 사용하여 R과 S를 조인 속성을 기준으로 정렬한다.
• 병합 단계
• 두 릴레이션을 병합하며 R과 S에 속해있는 튜플을 찾아낸다.
• 병합 단계는 SNLJ과 비슷하지만 차이는 정렬되어 있다는 것이고, 동등 조인 조건에서만 가능하므로 동등 조건이 아니면 병합을 시도하지 않는 것이다.

Hash Join

• 비용이 가장 많이 들어가는 조인 방법이지만 대용량 데이터 조인 시 Sorted 나 Nested Loop 보다 좋은 성능을 나타낸다.

• 조인에 참여한 두 집합 중 작은 집합 (Build input) 의 해쉬 테이블을 메모리상에 만들고  큰 집합 (Probe Input) 은 조인을 위해 해쉬 테이블을 검색한다.

• 따라서 조인 과정에서 발생하는 부하가 없으나, hash table 생성 비용이 크다. 따라서 Build Input이 작을 때라야 효과적이다.

• 이용 가능한 hash area의 크기에 따라 성능에 영향을 받는다.

• 이용 가능한 메모리가 작은 집합을 유지할 정도로 충분히 크지 않다면 두 집합을 좀 더 작은 단위로 나누게 되는데, 이를 파티션이라고 한다.

Storing(데이터 저장)

Database in Files

• 데이터베이스는 파일의 집합으로 저장된다. 각 파일은 레코드의 연속이고, 레코드는 필드의 연속이다.
• 간단한 접근
• 레코드의 크기가 정해져 있다
• 각 파일은 한 가지 타입의 레코드로만 이루어져 있다
• 서로 다른 파일은 서로 다른 릴레이션을 위해 사용된다. 이 경우가 가장 구현하기 쉽다. 가변 길이 레코드는 나중에 살펴본다
• Fixed-Length Records (고정 길이 레코드, 크기 n)
• i 번째 레코드는 byte n * (i - 1) 에 위치한다
• 레코드의 접근은 간단하지만 레코드가 디스크 블록에 걸쳐서 나뉘어질 수 있다
• 하지만 레코드가 경계에 걸쳐있지 않게 해야 한다
• 레코드의 삭제
• 레코드를 실제로 지우는 것이 아니라 삭제할 레코드를 free list 에 링크한다

Free List

• 첫 번째로 삭제된 레코드의 주소를 파일의 헤더에 저장한다
• 이 첫 번째 레코드에 두 번째로 삭제된 레코드의 주소가 저장된다. 계속 반복한다 (linked list)
• 주소가 저장된다는 것은 해당 레코드의 주소를 가리키는 "포인터"를 저장한다는 것이다
• 공간 효율을 높이기 위해서
• 일반 값들을 저장하기 위해 있는 공간을 재사용 하여 다음 빈 레코드의 포인터를 저장한다
• 사용 중인(값이 들어있는) 레코드에는 포인터를 저장하지 않는다
• 새 레코드를 추가할 때 free list의 항목들을 사용한다

Variable-Length Records

• 가변 길이 레코드는 데이터베이스 시스템에서 몇 가지 경우에 가끔 사용된다
• 한 파일에 여러 타입의 레코드를 저장할 때
• 레코드의 타입이 한 개 이상의 필드에서 가변 길이를 허용할 때
• 가변 길이 레코드는 Slotted Page Structure를 가진다
• 파일은 페이지의 집합이다
• Slotted Page의 헤더는 다음의 정보를 포함한다
• 레코드 엔트리의 개수
• 블록의 빈 공간의 마지막의 위치
• 각 레코드의 위치와 크기
• 페이지 안에서 레코드의 위치가 옮겨질 수 있다. 이렇게 하면 각 레코드 사이에 빈 공간이 없이 유지할 수 있다. 이를 위해 헤더의 레코드에 대한 진입점이 업데이트 되어야 한다
• 포인터는 레코드를 직접적으로 가리키면 안 된다
• 대신 레코드는 헤더에 저장된 레코드에 대한 진입점을 가리켜야 한다

Organization of Records in Files

• Heap
• 레코드의 위치는 파일 안에 공간이 있다면 어디던 위치할 수 있다
• Sequential
• 각 레코드의 search-key를 기준으로 레코드를 순서대로 저장한다
• Hashing
• 각 레코드의 일부 속성에 해시 함수가 계산되어 있다
• 결과는 파일 내 어떤 블록에 레코드가 위치해야 할지 알려준다
• 각 릴레이션의 레코드는 서로 다른 파일에 저장될 수 있다. 
• multi-table clustering file organization 에서는 서로 다른 릴레이션의 레코드가 같은 파일에 저장될 수 있다
• 연관된 레코드를 같은 블록에 저장함으로써 I/O를 최소화하기 위함이다

Sequential File Organization

• 모든 파일을 순서대로 접근해야 하는 경우에 적합하다
• search-key를 기준으로 레코드 내 파일이 정렬된다
• 정렬된 파일은 효율적으로 검색이 가능하지만 유지하기가 어렵다
• 삭제
• 포인터 체인을 이용하여 삭제된 튜플을 건너뛴다
• 삽입
• 레코드가 삽입되어야 할 위치를 찾는다
• 만약 빈 공간이 있으면 그 곳에 삽입한다
• 만약 없다면, overflow block에 삽입한다
• 두 경우 모두 포인터 체인이 갱신 되어야 한다

Multi-table Clustering

• 멀티 테이블 클러스터링을 사용하여 여러 개의 관계를 한 개의 파일에 저장한다
• 여러 개의 릴레이션을 모두 조회해야 하는 쿼리에는 적합하다
• 한 개의 릴레이션만 조회해야 하는 쿼리에는 좋지 않다
• 다양한 크기의 레코드가 결과로 나온다
• 포인터 체인을 추가하여 특정 릴레이션의 레코드를 연결할 수 있다

Data Dictionary Storage

• Data Dictionary( 혹은 system catalog )는 메타데이터를 저장한다
• 릴레이션들에 대한 정보
• 릴레이션의 이름
• 각 릴레이션의 속성의 타입의 이름
• 뷰의 정의와 이름
• 제약 조건
• 사용자와 비밀번호 같은 접근 정보
• 뷰와 그 뷰의 정의
• 물리적인 파일 구조 정보
• 어떻게 릴레이션이 저장되어 있는가(sequential/hash/...)
• 릴레이션의 물리적 위치
• 인덱스
• 카탈로그식 구조
• 디스크의 관계적 표현
• 카탈로그 표현의 예
• 릴레이션의 집합