블록 네스티드 루프 조인

Nested Loop Join

• MySQL 서버에서 사용되는 대부분의 조인 방식이다.
• 조인의 연결 조건이 되는 칼럼에 모두 인덱스가 있는 경우 사용된다.
• 레코드를 읽어서 다른 버퍼 공간에 저장하지 않고, 즉시 드리븐 테이블의 레코드를 찾아서 반환한다.

  • 다음과 같이 프로그래밍 언어에서 마치 중첩된 반복 명령을 사용하는 것처럼 작동한다고 해서 네스티드 루프 조인(Nested Loop Join)이라고 한다.

    -- 예제 코드
    SELECT *
    FROM employees e
    	INNER JOIN salaries s ON s.emp_no = e.emp_no
    		AND s.from_date <= NOW();
    				s.to_date >= NOW();
    WHERE e.first_name = 'Amor';

    -- Nested Loop Join 의사 코드(Psuedo Code)
    for (row1 IN employees) {
    	for (row2 IN salaries) {
    		if (condition_matched)
    			return (row1, row2);
    	}
    }

Block Nested Loop Join

• 네스티드 루프 조인과의 가장 큰 차이는 다음 두 가지다.
  • 조인 버퍼가 사용되는 여부
  • 조인에서 드라이빙 테이블과 드리븐 테이블이 어떤 순서로 조인되는지

조인 버퍼

• 조인 알고리즘에서 “Block”이라는 단어가 사용되면 조인용으로 별도의 버퍼가 사용됐다는 것을 의미한다.
  • 조인 쿼리의 실행 계획에서 Extra 칼럼에 “Using Join buffer”라는 문구가 표시되면, 그 실행 계획은 조인 버퍼를 사용한다는 것이다.
• 조인은 드라이빙 테이블에서 일치하는 레코드의 건수만큼 드리븐 테이블을 검색하면서 처리된다.
  • 드라이빙 테이블에서 일치하는 레코드가 1000건일 때, 드리븐 테이블의 조인 조건이 인덱스를 이용할 수 없다면 드리븐 테이블의 풀 테이블 스캔이 1000번 일어난다.
  • 드리븐 테이블을 검색할 때 인덱스를 사용할 수 없는 쿼리는 상당히 느려진다.
  • 옵티마이저는 최대한 드리븐 테이블의 검색이 인덱스를 사용할 수 있게 실행 계획을 수립한다.
• 어떤 방식으로도 드리븐 테이블의 풀 테이블 스캔이나 인덱스 풀 스캔을 피할 수 없을 경우
  • 옵티마이저는 드라이빙 테이블에서 읽은 레코드를 메모리에 캐시한 후 드리븐 테이블과 이 메모리 캐시를 조인하는 형태로 처리한다.
  • 이때 사용되는 메모리의 캐시를 조인 버퍼(Join buffer)라고 한다.
  • 조인이 완료되면 조인 버퍼는 바로 해제된다.
• 조인 버퍼는 join_buffer_size 시스템 변수로 크기를 제한할 수 있다.

💡 실행 계획의 “Using Join Buffer(block nested loop)" 표시

MySQL 8.0.20 버전부터는 블록 네스티드 조인대신 MySQL 8.0.18 버전부터 도입된 해시 조인 알고리즘이 대체되어 사용된다.

따라서 MySQL 8.0.20 이후의 버전이라면 실행 계획의 Extra 칼럼에 더 이상 “Using Join Buffer” 메시지는 표시되지 않을 수도 있다.

Reference

참고 서적

📔 Real MySQL 8.0