[CMU 15-445 Intro to DB Sys] Lec11 Join Algorithms

Operator Output

Data

• Early Materialization: inner table과 outer table에서 attribute의 값들을 복사하여 새로운 output tuple들로 만들어 줌. 이렇게 하면 이후에 다시 base table로 돌아갈 필요가 없다는 장점이 있음.

• Late Materialization: join key들과 함께, 해당되는 tuple들의 record ID들만을 복사함. 이는 이후에 다시 base table로 와서 attribute 값들을 찾아야 함. 불필요한 데이터를 복사하지 않기 때문에 column store에 있어서 이상적임.

  • 하지만 이렇게 하면 최종 output을 얻기 전에는 cost가 어느 정도 들지 예상하기 어렵고, 오늘날 storage와 computing이 더욱 분리되면서 나중에 다시 I/O로 오가는 것이 더 어려워서, early materialization을 더 많이 쓰는 편임.

    Cost Analysis Criteria

• join 계산에 드는 I/O 비용만을 기준으로 계산한다(결과를 출력하는 데 드는 비용은 고려하지 않음. 그 이유는 결과 출력 비용은 데이터에 따라 달라지며, 어떤 join algorithm을 사용하더라도 같기 때문임)
  

Nested Loop Join

Naive Nested Loop Join

• 단순히 outer, inner table에 대한 nested loop를 사용하여 key가 일치할 때 포함. outer의 매 tuple에 대해서 inner의 모든 tuple을 돌아야 하므로 좋지 못하다.
• 비용은 $M + m \cdot N$이다.

Blocked Nested Loop Join

• locality를 활용하기 위해 page를 block size로 하여, outer의 각 page에 대해 Inner의 모든 tuple을 확인한다. 비용은 $M + M \cdot N$이 된다.
• 더 작은 테이블을 outer로 두어야 한다.
• 만약 $B$ buffer를 사용할 수 있다면, outer의 block을 위해 $B-2$를 사용하고, 1개는 inner, 1개는 output 저장에 사용한다. 이 때 비용은 $M + \lceil M/(B-2) \rceil \cdot N$다.

Index Nested Loop Join

• inner table에서 전체를 순회하는 대신 index를 사용한다. index probe의 비용이 constant $C$라고 할 때 비용은 $M + m \cdot C$가 된다.
• 이때 Inner table이 index를 가지고 있어야 함에 유의한다.

Takeaways

• outer table은 크기가 작은 것으로 선택하라
• outer table의 가능한 많은 양을 메모리에 buffer하라
• inner table은 그냥 순회한다(혹은 index를 사용)

Sort-Merge Join

• sort phase: 두 테이블을 각각의 key에 대해 sort한다.
• merge phase: cursor를 놓고 두 테이블을 따라서 가면서 match하는 경우를 선택한다.
• $B$ buffer를 사용한다고 할 때, sort cost는 각각 $2M + (1 + \lceil \log_{B-1} \lceil M/B \rceil)$, $2N + (1 + \lceil \log_{B-1} \lceil N/B \rceil)$ 이 되고, merge cost는 $M + N$이다(극단적인 경우 $M \cdot N$이 될 수 있다)
• 이미 테이블들이 join key로 정렬되어 있거나, 결과물이 반드시 정렬되어야 하는 경우 유용하다.

Hash Join

Basic Hash Join

• 먼저 outer에 대해 해쉬테이블을 만들고, inner의 각 tuple에 대해 해쉬값을 계산하여 bucket으로 간 뒤 matching tuple이 있는지 찾는다.
• hash table의 key로는 join key값을 넣는다. hash collision이 발생할 수도 있기 때문에 이를 체크하기 위해 key값도 테이블에 함께 포함시켜야 한다. value값은 구현에 따라 tuple id만 넣거나 Tuple 전체를 다 넣을 수 있다.
• bloom filter를 사용하면 특정 key가 해쉬테이블에 있는지를 미리 빠르게 체크할 수 있다. 즉 build phase에서 bloom filter를 만들어두고, 이후 inner table의 tuple을 체크할 때 사용하는 것이다. bloom filter는 CPU cache에 들어가기 때문에 빠르다.

Grace Hash Join(Partitioned Hash Join)

• 그러나 해쉬테이블이 메모리에 다 들어가지 않는 경우가 있을 수 있다.
• partition phase: outer와 Inner table을 둘 다 같은 해쉬 함수를 이용하여 각각 $k$개의 bucket으로 나누어 준다(필요한 경우 bucket을 disk에 write해준다).
• probe phase: 각 partition을 메모리에 한 쌍씩 불러들여와서 hash join해준다.
• 만약 partition이 메모리에 다 들어오지 않는다면 다른 해쉬 함수를 이용하여 메모리에 들어올 때까지 recursively partition해 준다.
• 비용은 만약 recursive partitioning을 하지 않았다면 $3(M+N)$이 된다.
  • partition phase: read and write both tables $2(M+N)$
  • probe phase: read both tables $M+N$
• hybrid hash join에서는 key들이 skew된 경우, partition을 디스크에 저장하는 대신 즉시 비교를 수행하지만, 제대로 구현하기 어렵다.

Observation

• inner table의 크기는 무관하며, outer table 내지 그 partition이 메모리에 들어올 수 있으면 된다.
• size를 안다면 static hash table을 사용할 수 있으며, 모를 경우 dynamic hash table을 사용해야 한다.

Conclusion

• hashing is almost always better than sorting
• 하지만 non-uniform data거나, 결과물이 정렬되어야 하는 경우에는 sorting이 좋다.