8.2.1.10 Nested Loop 조인 알고리즘

MySQL은 Nested Loop 알고리즘 또는 변형을 사용하여 테이블 간의 조인을 수행합니다.

Nested Loop 조인 알고리즘

간단한 Nested Loop Join (NLJ) 알고리즘은 루프의 첫 번째 테이블에서 행을 한 번에 하나씩 읽고 각 행을 조인 다음 테이블을 처리하는 중첩 루프에 전달합니다. 이 프로세스는 결합하는 테이블이 남아있는만큼 반복됩니다.

3 개의 테이블 t1 , t2 및 t3 사이의 결합이 다음 결합 형을 사용하여 실행합니다.

 Table Join Type
 t1 range
 t2 ref
 t3 ALL

간단한 NLJ 알고리즘을 사용하면 결합은 다음과 같이 처리됩니다.

 for each row in t1 matching range {
   for each row in t2 matching reference key {
     for each row in t3 {
       if row satisfies join conditions,
       send to client
     }
   }
 }

NLJ 알고리즘은 외부 루프에서 내부 루프에 한 번에 한 행씩 전달하므로 일반적으로 내부 루프에서 처리되는 테이블을 여러 번 읽습니다.

Block Nested Loop 조인 알고리즘

Block Nested-Loop (BNL) 결합 알고리즘은 외부 루프에서 읽은 행 버퍼링을 사용하여 내부 루프에서 테이블을 읽어야하는 횟수가 줄어 듭니다. 예를 들어, 버퍼에 10 행이 읽혀이 버퍼가 다음 내부 루프에 전달되면 내부 루프에서 읽을 각 행을 버퍼에있는 모든 10 행과 비교할 수 있습니다. 이렇게하면 내부 테이블을 읽어야하는 횟수가 크게 감소합니다.

MySQL은 다음의 조건에서 결합 버퍼링을 사용합니다.

NLJ 알고리즘 (버퍼링 없음)의 앞부분에 결합의 예에서는 결합은 결합 버퍼링을 사용하면 다음과 같이 실행됩니다.

 for each row in t1 matching range {
   for each row in t2 matching reference key {
     store used columns from t1, t2 in join buffer
     if buffer is full {
       for each row in t3 {
         for each t1, t2 combination in join buffer {
           if row satisfies join conditions,
           send to client
         }
       }
       empty buffer
     }
   }
 }

 if buffer is not empty {
   for each row in t3 {
     for each t1, t2 combination in join buffer {
       if row satisfies join conditions,
       send to client
     }
   }
 }

S 가 결합 버퍼에 저장되는 각 t1 , t2 조합의 크기이며, C 가 버퍼의 조합의 수인 경우 테이블 t3 가 스캔되는 횟수는 :

 ( S * C ) / join_buffer_size +1

join_buffer_size 전에 모든 행의 조합을 유지하기에 충분한 크기가 될 때까지 join_buffer_size 값이 클수록 t3 스캔 횟수는 줄어 듭니다. 그 시점에서는 더욱 크게해도 속도는 향상되지 않습니다.