조인 연산, 집합 연산

# 조인 연산
- 중포-반복 조인(Nested-loop join)
- 블록 중포-반복 조인(Block nested-loop join)
- 색인된 중포-반복 조인(Indexed nested-loop join)
- 합병 조인(Merge-join)
- 혼합 합병 조인(Hybrid merge-join)
- 해시 조인(Hash-join)
- 어떤 알고리즘을 선택할 것인가: 비용 기반 선택

 

 

# 중포 반복 조인
- r ⋈θ s : r외부, s내부
for each tuple tr in r do begin
  for each tuple ts in s do begin
       test pair (tr,ts) to see if they satisfy the join condition 
       if they do, add tr • ts to the result.
  end
end
- 인덱스를 필요로 하지 않음
- 모든 형태의 조인 조건에 사용 가능함
- 두 릴레이션의 모든 튜플에 대한 pair를 검사함 => 많은 비용 소요

1. 최악의 경우 : 각 릴레이션의 1 블록 만 버퍼에 담을 수 있음
- tT : nr * bs + br
- nr * bs : r 릴레이션의 각 튜플마다 s 릴레이션의 전체 내용을 가져와야 함
- br : r 릴레이션의 전체 내용(nr 개 튜플)을 가져와야 함
- tS : nr + br
- nr : r 릴레이션의 각 튜플마다 s 릴레이션 내용을 가져오기 위하여 탐색
- s 릴레이션은 순차적으로 읽히므로 최초 탐색만 필요함
- br : r 릴레이션 전체 내용을 가져오기 위하여 탐색

2. 최선의 경우 : 릴레이션들을 모두 버퍼에 담을 수 있을 경우
- tS : br + bs
- tT : 2 => 각 릴레이션은 순차적으로 읽히므로 최초 탐색만 필요함
- r 와 s 릴레이션이 모두 순차적으로 저장되어 있는 경우에 한함
- 외부 릴레이션의 각 튜플마다 (버퍼에 있는) 내부 릴레이션 전체를 처리 => 성능 향상
- 크기가 작은 릴레이션이 외부 릴레이션으로 적합함

 

 

# 블록 중포 반복 조인
- 내부 릴레이션의 모든 블록이 외부 릴레이션의 모든 블록과 짝을 이룸
for each block Br of r do begin
  for each block Bs of s do begin
    for each tuple tr in Br do begin
      for each tuple ts in Bs do begin 
        Check if (tr,ts) satisfy the join condition
        if they do, add tr • ts to the result.
      end
    end
  end
end

 

1. 최악의 경우 

- tT : bs * br + br

- tS : 2 * br

- br * bs : 내부 릴레이션의 각 블록은 외부 릴레이션의 각 블록당 1번씩만 읽힘

- 2 * br : s 릴레이션(내부 릴레이션) 순차적으로 저장됨을 전제함

- 외부 릴레이션 블록 1개 읽을 때 내부 릴레이션은 첫 번째 레코드로만 헤더를 이동 

- 이후 내부 릴레이션은 순차적이므로 추가 탐색이 없음

- 외부 릴레이션은 매 블록을 읽을 때마다 헤더를 움직여야 함

- 작은 릴레이션을 외부 릴레이션으로 하는 것이 유리

 

2. 최선의 경우

- 외부 및 내부 릴레이션도 버퍼에 모두 load 할 수 있는 상황

- tT : br + bs

- tS : 2

 

 

# 색인된 중포 반복 조인
- 중포 반복 조인의 내부 릴레이션의 조인 속성에 대해 인덱스가 구축되어 있는 경우
- 내부 릴레이션에 파일 scan하는 대신 인덱스를 사용
- Equi-join 이나 자연 조인에 적용
- 조인을 위하여 인덱스가 임시로 만들어 질 수도 있음
- 외부릴레이션 r의 튜플 tr 에 대하여 조인 조건을 만족하는 ts 를 찾기 위해 인덱스를 사용

1. 최악의 경우 : 버퍼가 r의 1개 블록과 인덱스 1개 블록만 저장할 수 있을 때
- 릴레이션 r을 읽기 위하여 br 블록을 읽음  br 번의 탐색도 발생
- br 블록 입력으로 nr 튜플을 읽음  각 튜블마다 B+ 트리 인덱스를 통하여 조인
- 조건을 만족하는 ts를 구함(각 ts를 구하는데 c 만큼의 블록 접근 필요)
- 비용 : br (tT + tS) + nr * c (트리높이 + 1)
- c : 인덱스 순회 + 최종 ts 를 가져오는 비용
- 인덱스가 외부, 내부 릴레이션 모두 구축되어 있을 경우 튜플 수가 적은 릴레이션이 외부 
- 색인된 중포 반복 조인의 탐색비용이 블록 중포 반복 조인보다 훨씬 많음
- student 의 대상 튜플 개수를 현격하게 줄이면 전체적으로 블록 중포 반복 조인보다 훨씬 좋은 성능을 보일 것임

 

# 합병 조인(Merge-Join)
- 양쪽 릴레이션을 조인 속성으로 정렬(정렬이 되어 있지 않았다면 외부 정렬 합병)
- 정렬된 릴레이션을 합병
1. 조인 과정은 정렬-합병 알고리즘과 유사하지만
2. 중복값 처리에서 차이
=> 조인 속성 값이 동일한 값을 가지는 쌍을 찾음
- Equi-join 과 자연 조인에만 사용 가능함
- 조인이 이루어진 결과 튜플들의 집합은 주기억장치에 모두 올라갈 수 있다고 전제
- tT : br + bs 
- tS : br + bs => 정렬된 릴레이션 대상
- 릴레이션이 정렬되어있지 않았다면 정렬 비용

 

# 혼합 합병 조인(Hybrid Merge-Join)
- 릴레이션 1개는 조인속성으로 정렬(주키)되어 있고 다른 릴레이션은 조인 속성에 2차 B+트리 인덱스가 구축되어 있는 경우
- 정렬된 릴레이션을 정렬되지 않은 릴레이션의 B+ 트리 인덱스의 단말노드와 합병하고 정렬되지 않은 릴레이션의 튜플 들 중 조인되어야 할 튜플들의 주소들만 얻음
- 그 결과를 정렬되지 않은 릴레이션의 튜플 주소를 기준으로 정렬
- 정렬되지 않은 릴레이션을 정렬한 튜플 주소를 기준으로 스캔(순차적인 접근)
- 조인속성으로 정렬된 결과를 읽음
- 이를 정렬되어 있던 릴레이션의 튜플과 결합
- 테이블 만들 때 FK 만들어서 B+트리 인덱스 만들어라

 

 

# 해시 조인
- Equi-join 과 자연 조인에 적용 가능함
- 해시함수 h는 양쪽 릴레이션의 튜플들을 분할하는 데 사용됨(파티션 수행)
- h 는 JoinAttrs 를 {0, 1, ..., n}로 매핑
- JoinAttrs: r and s 의 자연 조인에 사용되는 공통 속성 
- r0, r1, . . ., rn :  r 릴레이션 튜플들의 분할
- 튜플 tr은 i = h(tr [JoinAttrs])의 분할 ri 에 배정됨
- s0, s1. . ., sn :  s 릴레이션 튜플들의 분할 
- 튜플 ts는 i = h(ts [JoinAttrs]) 의 분할 si 에 배정됨
- ri에 있는 튜플은 si에 있는 튜플들과 비교 => 다른 분할에 있는 튜플들과는 비교할 필요가 없음
- 조인 조건을 만족하는 r 튜플과 s 튜플은 조인속성 값이 동일함
- 릴레이션 s : 구축입력(build input)
- 릴레이션 r : 탐색입력(probe input)
- in-memory hash index 구축 입력이 사용
- 해싱 두 번 (파티션 만듦, 빌딩, 프로빙에 다른 해시 함수 사용)
- tT : 3(br + bs) + 4 * nh
2(br + bs) : 두 릴레이션 r, s 분할을 위해 읽음, 분할된 두 릴레이션 모두 저장
1(br + bs) : 구축과 탐색 단계에서 각 분할영역들을 모두 한 번씩 읽음(building probing)
4 * nh : 파티션의 마지막 블록은 남아있음 (nh개씩)
- tS : 2(br  + bs) + 2nh
입력과 출력 버퍼 각각에 1개의 블록이 할당되는 경우
각 분할은 한번의 탐색으로 순차적으로 읽히므로 구축과 탐색을 위해서는 2nh(파티션 개수) 회 탐색 필요(building probing)
- 전체가 주기억장치에서 구축될 수 있다면: br + bs

 

 

# 중복 제거(Duplicate Elimination)
1. 정렬을 이용하여 구현
- 동일한 튜플은 정렬의 결과로 서로 인접하게 위치
- 이를 1개만 남겨두고 제거
- 외부정렬-합병 수행 시
- 런 생성 시 중복 찾아 디스크에 쓰기 전에 중복 제거 => 크기 줄임
- 다른 런들과의 중복 튜플  합병 단계에서 제거
- 런들이 합병된 최종 결과에는 중복이 등장하지 않음

2. 해시 조인을 이용하여 구현
- 해시를 이용하여 릴레이션을 분할하고
- 각 분할을 읽어 들여 메모리에서 해시 인덱스를 구축
- 해시 인덱스를 구축하는 동안 중복을 제거
- 분할 내의 중복을 모두 제거한 후 해시 인덱스 내에 있는 튜플을 디스크에 쓰면 중복이 제거된 결과만 남게 됨

 

 

# 추출(Projection)
- 각 튜플에 추출을 수행
- 만약 추출에 사용된 속성이 후보키일 경우에는 별도 중복 제거를 할 필요 없음

 

# 집합연산(Set Operations) : 정렬로 구현
- 호환성 : 칼럼의 도메인, 개수 같아야 함
- 두 릴레이션을 정렬한 후 각 릴레이션을 스캔
- r ∪ s: 두 릴레이션을 동시에 스캔하면서 동일한 튜플 중 하나만 결과에 추가
- r ∩ s: 두 릴레이션을 동시에 스캔하면서 동시에 나타나는 튜플만을 결과에 추가
- r - s: 두 릴레이션을 동시에 스캔하면서 s에는 없고 r에만 있는 튜플만을 결과에 추가
- 각 릴레이션을 한 번 스캔함으로써 구현 
- tT : br + bs 
- tS : br + bs 
- 릴레이션이 정렬되어 있지 않은 경우 정렬비용이 추가되어야 함

 

# 집합연산(Set Operations): 해시로 구현
- 동일한 해시 함수를 이용하여 두 릴레이션 r과 s를 분할

- r ∪ s :
- 분할 시와 다른 해시함수를 이용하여 분할 영역 ri 에 대하여 해시 인덱스를 구축
- 분할영역 si에 있는 튜플 중 ri 의 해시인덱스에 존재하지 않는 튜플을 ri 의 해시인덱스에 추가
- ri 의 해시인덱스에 있는 튜플을 결과에 추가

- r ∩ s :
- 분할 시와 다른 해시함수를 이용하여 분할 영역 ri 에 대하여 해시 인덱스를 구축
- 분할영역 si에 있는 튜플 중 ri 의 해시인덱스에 존재하는 튜플을 결과에 추가

- r – s :
- 분할 시와 다른 해시함수를 이용하여 분할영역 ri 에 대하여 해시 인덱스를 구축
- 분할영역 si에 있는 각 튜플에 대하여 ri 의 해시인덱스에 존재하는지 검사하고 존재할 경우 그 튜플을 ri 의 해시인덱스에서 제거
- ri 의 해시인덱스에 있는 튜플을 결과에 추가

 

# 외부 조인(Outer Join)
- r ⟕ s 를 처리하기 위하여 정렬-합병 조인을 수정 :
- r ⟕ s 에는 r의 튜플 중 r ⋈ s 에 참여하지 않았던 r – πR(r ⋈ s) 가 추가됨
- 합병과정에서 s와 매칭 되지 않는 튜플 tr을 널을 추가하여 결과에 포함시킴
- Right outer-join 도 유사하게 처리

- r ⟕ s 를 처리하기 위하여 해시 조인을 수정 :
- 만약 r이 탐색 입력 릴레이션이면 매칭 되지 않는 r의 튜플을 널을 추가 하여 결과에 포함
- 만약 r이 구축입력 릴레이션이면
- 탐색하는 동안 r의 어떤 튜플이 s와 매칭 되지 않은 r 튜플들을 널을 추가 하여 결과에 포함

 

 

# 집계연산(Aggregation) : group by
- 그룹에 튜플을 모두 모은 후 집계연산 적용
- 동일한 그룹에 튜플들을 가져오기 위하여 정렬이나 해싱을 사용
- 중복제거와 유사하게 처리
- 해당 그룹에 집계연산을 적용
- min, max, sum, count, avg 비용은 중복제거 연산의 비용과 동일

- 그룹에 튜플을 모으면서 동시에 집계 연산 적용을 진행하는 방식
- sum, min, max 경우 그룹을 진행하는 동안 1개 투플만을 유지하는 것이 가능
- count 경우 각 그룹의 튜플을 찾을 때마다 카운트를 갱신
- avg 경우 sum과 count를 계산한 후 구함
- 비용: 정렬트리 구조나 해시인덱스를 주기억장치 내에서 유지될 수 있다고 전제
- 그룹에 모두 모은 후 집계연산 적용 : 3 * br 블록 전송, 최대 2 * br 탐색
- 그룹에 모으면서 집계연산 적용 : 1 * br 블록 전송, 1회 탐색