내포된 루프 결합

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Nested loop join" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2021년 1월) (이 템플릿 메시지 제거 방법과 시기 파악)

중첩 루프 조인은 두 개의 중첩 루프를 사용하여 두 세트를 결합하는 순진한 알고리즘이다.^[1]가입 작업은 데이터베이스 관리를 위해 중요하다.

알고리즘.

$R{\displaystyle }$ ${\displaystyle R}$ 및 $S$ ${\displaystyle S}$ 두 관계가 다음과 같이 결합된다$$.

알고리즘 중첩_loop_join은 S do의 각 튜플에 대해 R do의 각 튜플 r에 대한 것이며, r과 s가 결합 조건을 만족하면 튜플 <r,s>를 산출한다.

이 알고리즘은 n_r*b_s+b_r 블록 전송과 n_r+b_r 탐색을 포함하며, 여기서_r b와_s b는 관계 R과 S에서 각각 블록의 수이고 n은_r 관계 R에서 튜플의 수이다.

알고리즘은 $O{\displaystyle }$( ${\displaystyle R}$ ${\displaystyle S}$) ${\displaystyle O(R$S$)}$ I$$/Os로 실행되며, ${\displaystyle 여기}$서 R $displaystyle$ R $}$과 S $displaystyle$ S$}$은(는$$$$) $각각{\displaystyle }$ R$${\$displaystyle R}$과 S ${\displaystystyle S$}에 포함된 튜플의 수입니다. 수에 관계없이 쉽게 일반화할 수 있다.

블록 중첩 루프 조인 알고리즘은^[2] $추가{\displaystyle }$ 메모리를 활용하여 S ${\displaystyle S}$ 관계가$$ 스캔되는 횟수를 줄이는 단순 중첩 루프 알고리즘의 일반화다.그것은 R 관계의 큰 덩어리를 메인 메모리에 로드한다.각 청크에 대해 S를 스캔하고 현재 메모리에 있는 모든 튜플 쌍의 결합 조건을 평가한다.이렇게 하면 S가 스캔되는 횟수가 청크당 한 번으로 줄어든다.

인덱스 결합 변동

내부 관계에 조인에 사용된 속성에 대한 인덱스가 있으면 순진한 내포 루프 조인트를 인덱스 조인으로 대체할 수 있다.

알고리즘 index_join은 인덱스 조회 시 S의 각 tuple s에 대해 R do의 각 tuple r에 대한 것이다. tuple <r,s>를 산출한다.

이 변동의 시간 복잡성은 O(M * N)에서 O(M * 로그 N)로 개선된다.

참고 항목

• 해시 조인
• 정렬-머지 결합

참조