[CS186] Introduction to Database Systems - Week 6

⛅ Joins ⛅

• final write cost는 조인 모델 비용을 계산하는데 포함하지 않는다. 즉, 조인된 테이블을 디스크에 기록하는 비용을 무시하는데, 조인된 테이블이 메모리에서 다른 연산자에 의해 사용될 것이라고 생각되기 때문이다

 

Simple Nested Loop Join

• 가장 단순한 방법은 두개의 중첩된 for loop를 사용하는 것과 비슷하다
• 예를 들어, R 테이블의 각 레코드를 가져와서 S 테이블에서 일치하는 모든 레코드를 검색하는 것이다
• I/O cost = [R]+|R|[S]     [R]은 R 테이블의 페이지 수이고 |R|는 R의 레코드 수이다

pseudocode for SNLJ

 

Page Nested Loop Join

• R의 각 페이지마다 S의 모든 페이지를 읽는다
• I/O cost = [R] + [R][S]  -> R과 S 중에서 더 작은 테이블을 외부로 두면 최적화 할 수 있다

pseudocode for PNLJ

 

Block Nested Loop Join

I/O cost

• Page Nested Loop Join도 좋지만 아직 버퍼를 잘 활용하고 있지 않다
• S를 읽는 것이 적을 수록 I/O 비용을 줄일 수 있으므로, B 버퍼 페이지가 있을 때 B-2 페이지를 R에 사용하고, 1 페이지를 S에, 나머지 1페이지를 아웃풋 버퍼에 사용하는 것을 Block Nested Loop Join (or Chunk Nested Loop Join) 이라고 한다

pseudocode for BNLJ

 

Index Nested Loop Join

• S에 인덱스가 있는 경우
• I/O cost = [R] + |R|∗(cost to look up matching records in S)

pseudocode for Index Nested Loop Join

 

Hash Join

• Naive Hash Join과 Grace Hash Join이 있다
• Grace Hash Join은 key skew에 민감하다. 
• Key skew는 해시하려고 하는데 상당 수의 키가 똑같은 곳에 가는 경우, 즉 많은 양의 레고드가 똑같은 키를 가지고 있는 경우에 발생한다

 

Sort-Merge Join

• R과 S를 먼저 정렬하는 것이  도움이 될 때가 있다 (예를 들어, 쿼리에 ORDER BY가 있는 경우)

 

 

// TODO

해시 조인 좀 더 찾아보기

전체적으로 완전히 이해하진 못한 것 같다

 

 

 

 

 

참고자료

https://cs186berkeley.net/