Block Nested Loop Join

Block Nested Loop Join에 대해 알아보자.

설명

(Block Nested Loop Join의 모습)

앞서, Join의 구현 방식 3가지에 대해 알아봤다. NL 조인 방식은 인덱스가 없다면 가장 느린 성능이 나타나는데 이러한 한계를 극복하기 위해 Block Nested Loop Join방식을 활용한다. (Mysql의 경우 8.0.20부터 Block Nested Loop Join 대신 Hash Join을 사용한다고 한다. :출처)

Nested Loop Join은 Drivien Table의 IO 접근을 최소화하는 것이 성능에 중요하다. (이러한 이유로 Driven Table 의 IO 접근에 영향을 주는 Driving Table의 행의 개수를 가능하면 적도록 한다.)
Block Nested Loop Join은 두 테이블을 매번 1:1로 비교하는 것이 아니라 버퍼를 두어 N:1의 비율로 비교하도록 하여 IO를 줄인다.

위 이미지를 살펴보면 N개의 Driving Table의 행들을 모아 버퍼를 만든 후, |S|개의 Driven Table과 비교하여 Join 결과를 획득한다.

이러한 경우, 일반적인 방식에서 소요되는 |R| * |S|번의 접근 대신 (|R| * |S|)/N + 1번의 접근이 일어나 더욱 효율적이다. 다만, 버퍼를 많이 유지할 경우 메모리 소모가 크다는 단점이 있다.

설계

실제 파일 입출력을 이용하여 이를 구현해보자. 실습에 사용된 데이터들은 TPC-H 라는 벤치마크를 위한 데이터를 활용하였고, 언어는 C++를 활용하였다.

Driving Table인 Part, Driven Table인 PartSupp가 있고, PARTKEY를 키로 사용한다.

(구현된 모습)

위 이미지가 실제로 구현된 모습이며, 각 객채에 대해 살펴보자.

입출력 지원 객체

• TableReader: 테이블의 데이터를 한 줄 씩 읽어와, template class를 활용해 원하는 객체로 반환해주는 객체이다.
• TableWriter: 객체를 읽어와 테이블에 저장하는 객체이다.

VO

• Part, PartSupp: 테이블에 저장된 두 데이터 모델(Part, PartSupp)를 구현한 객체이다. 테이블을 읽어 객체로 변환하기 위한 용도로만 활용한다.
• PartAndPartSupp: Join 연산의 결과를 저장한다. 내부적으로 Part, PartSupp을 유지하고, 이들의 데이터를 테이블의 행 형태로 내보내기 위해 사용한다.

버퍼

BufferManage은 내부적으로 키:PARTKEY 값:배열 을 유지하는 해시 테이블을 갖고 있는 버퍼 관리 객체이다.

배열을 유지하도록 한 까닭은

• 해시 테이블의 크기 감소
• 추가적인 조회, 배열 생성없이 반환하는 배열과 상호작용만으로 Join 결과 생성 가능
  의 효과를 보기 위함이었다.

구현

동작 방식

1. TableReader가 Part.tbl을 한 줄씩 읽는다.
2. 읽은 데이터(string)를 Part VO로 변환한다.
3. BufferManager가 유지하는 해시 테이블에 Part VO를 저장한다
4. (1) ~ (3) 과정을 버퍼의 최대 크기만큼 반복한다.
5. 이후 TableReader가 PartSupp.tbl을 한 줄씩 읽는다.
6. 읽은 데이터(string)를 PartSupp VO로 변환한다.
7. PartSupp VO를 버퍼에 조회하여 일치하는 Part VO들의 집합을 찾는다.
8. 획득한 Part와 PartSupp VO를 통해 조인 결과 PartAndPartSupp VO를 생성한다.
9. TableWriter에 의해 Output.tbl에 조인 결과인 PartAndPartSupp VO를 문자열로 변환하여 작성한다.
10. (5) ~ (9)의 과정을 PartSupp.tbl를 다 읽을 때 까지 반복한다.
11. (1) ~ (10)의 과정을 Part.tbl를 다 읽을 때 까지 반복한다.

버퍼 크기에 따른 자원 소모 예측

버퍼 크기에 따라 실행시간, 메모리 사용량(버퍼가 꽉찼을 경우의 최대) 를 비교해보자.

버퍼가 작다면

• 해시 테이블을 작게 유지하기에 메모리 사용량이 작을 것이다.
• I/O가 빈번히 일어나기에 실행시간은 클 것이다.

버퍼가 크다면

• 해시 테이블을 크게 유지하기에 메모리 사용량이 클 것이다.
• I/O가 적게 일어나기에 실행시간은 적을 것이다.

실제 결과

• Ubuntu 18.04
• Part tbl의 크기 1000
• PartSupp의 크기 4000
  에 대해 실행하였다.

(결과)

	2	10	1000
Max VM (KB)	4764	4764	5160
Max RSS (KB)	1308	1324	3284
Elapsed time (ms)	1765.09	429.3	66.925

(표로 정리한 모습)
차례대로 가상 메모리 사용량, 프로그램 최대 메모리 사용량, 프로그램 실행 시간을 의미한다.

예상대로 버퍼의 크기가 작을 수록 시간 소모가 크도 메모리 사용량이 작았으며, 클수록 시간소모는 작고 메모리 사용량이 컸다.