Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 제 12 장 질의 처리 개요 비용 산정을 위한 카타로그 정보 질의 비용산정 선택 연산 정렬 죠인 연산 기타 연산 표현식의 평가 관계형 표현식의 변환 평가 계획의 선택 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 질의 처리의 기본 절차 1. 구문 분석 및 변환 2. 최적화 3. 평가 질의 출력 구문 분석기 및 변환기 관계형 대수 표현식 평가 엔진 최적기 실행 계획 데이터 데이터에 관한 통계 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 질의 처리의 기본 절차 (계속) 구문 분석 및 변환 질의를 내부 형식으로 변환한다. 그리고 이것 은 관계형 대수로 변환된다. 구문 분석기는 문법을 체크하고 릴레이션을 검사한다. 평가 질의 실행 엔진은 질의 평가 계획을 취해, 그 계획을 실행하고 결과를 돌려준다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 질의 처리의 기본 절차 (계속) 최적화 - 질의에 대한 가장 비용이 적게 드는 평가 계획을 찾는다. 주어진 관계형 대수 표현식은 동등한 많은 표현식을 가질 수 있다. 예. balance < 2500(balance(account))는 다음과 동등하다 balance(balance < 2500(account)) 어떤 관계형 대수 표현식은 많은 방법으로 평가될 수 있다. 상세한 평가 전략을 명시하고 있는 주석이 붙은 표현식을 평가 계획이라 한다. 예를 들어, 잔고가 2500불보다 적은 계좌를 찾기 위해 balance 인덱스를 사용하거나 릴레이션 전체를 검색해 잔고가 2500불 이상인 계좌는 고려하지 않을 수 있다. 모든 동등한 표현식 중에서 가장 비용이 적게 드는 평가 계획을 선택하도록 한다. 계획의 비용 산정은 DBMS 카타로그내의 통계 정보에 의거한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 비용 산정을 위한 카타로그 정보 nr : 릴레이션 r내의 튜플의 수 br : r의 튜플들을 내포하고 있는 블록의 수 sr : r의 한 튜플의 바이트 단위의 크기 fr : r의 블록킹 요인 – 즉, 한 블록에 들어가는 r의 튜플 수 V(A, r) : 애트리뷰트 A에 대해 r에 나타나는 서로 다른 값의 수 ; A(r)의 크기와 같다. SC(A, r) : 릴레이션 r의 애트리뷰트 A의 선택 수 ; A와 같은 조건을 만족하는 레코드의 평균수. r의 튜플들이 파일내에 물리적으로 함께 저장되면, 다음과 같다. br = fr — nr Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 인덱스에 관한 카타로그 정보 fi : B+ - 트리와 같은 트리 구조 인덱스에 있어, 인덱스 i의 내부 노드의 평균 전개 HTi : 인덱스 i내 계층 수 – 즉, i의 높이이다. - 릴레이션 r의 애트리뷰트 A의 균형 트리 (B+ - 트리 같은) 인덱스에 있어, HTi = logfi(V(A, r)) 이다. - 해쉬 인덱스에 있어 HTi는 1이다. LBi : i내 최하위 계층 인덱스 블록의 수 – 즉, 인덱스의 잎 계층 블록의 수이다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 질의 비용 산정 비용 산정을 하는 데는 많은 가능한 방법이 있는데, 그 예로는 디스크 액세스, CPU 시간 및 분산 또는 병렬 시스템에서의 통신 비용 등이 있다. 디스크 액세스가 일반적으로 가장 유력한 비용이며, 또한 산정하기가 비교적 쉽다. 그러므로, 디스크로부터의 블록 전송 수가 평가의 실질적인 비용산정으로 사용된다. 블록들의 모든 전송은 같은 비용을 가진다고 가정한다. 알고리즘의 비용은 많은 메모리를 가지면 디스크 액세스를 줄일 수 있으므로, 메인 메모리 내 버퍼의 크기에 따른다. 따라서, 비용을 산정할 때 메모리의 크기가 패러미터가 되어야 한다 ; 흔히 최악의 경우의 산정을 사용한다. 알고리즘 A의 비용 산정을 EA로 한다. 디스크에 되 쓰는 비용은 포함하지 않는다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 선택 연산 파일 스캔 – 선택 조건을 충족하는 레코드를 찾아 검색하는 검색 알고리즘 알고리즘 A1 (선형 검색). 각 파일 블록을 스캔해 모든 레코드가 선택 조건을 만족하는지 여부를 테스트 한다. - 비용산정(스캔할 디스크 블록의 수) EA1 = br - 선택이 키 애트리뷰트상에 행해지면, EA1 = (br / 2) (레코드를 찾으면 중단) - 선형 검색은 다음에 관계없이 적용될 수 있다. * 선택 조건, 또는 * 파일 내 레코드의 순서, 또는 * 인덱스의 유무 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 선택 연산 (계속) A2 (이진 검색). 선택이 정렬된 파일상의 애트리뷰트에 동등 비교이면 적용 가능하다. - 릴레이션의 블록들이 연속해 저장되었다고 가정한다. - 비용 산정 (스캔할 디스크 블록의 수) : EA2 = log2(br) + – 1 * log2(br) – 블록들에 이진 검색을 해 첫 번째 튜플에 도달 하는 비용 * SC(A, r) – 선택을 만족할 레코드의 수 * SC(A, r) / fr – 이들 레코드가 점유할 블록의 수 - 키 애트리뷰트의 동등 조건 : SC(A, r) = 1 ; 비용 산정 EA2 = log2(br) 로 감소한다. fr ———— SC(A, r) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 통계 정보의 예제 faccount = 20 (account의 20튜플이 한 블록에 들어간다) V(branch-name, account) = 50 (50개 지점) V(balance, account) = 500 (500개의 서로 다른 잔고 값) naccount = 10000 (account에는 10,000개의 튜플이 있다) account에 다음과 같은 인덱스가 존재한다고 가정 - 애트리뷰트 branch-name에 대해 주 B+ - 트리 인덱스 - 애트리뷰트 balance에 대해 2차 B+ - 트리 인덱스 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 선택 비용 산정 예제 branch-name = “Perryridge” (account) 블록의 수 baccount = 500 : 릴레이션에 10,000개의 튜플이 있고 각 블록에는 20개의 튜플을 가지므로 account는 branch-name으로 정렬되었다고 가정한다. - V(branch-name, account)는 50이다. - account 릴레이션의 10000/50 = 200개의 튜플이 Perryridge 지점 에 속한다. - 이들 튜플에는 200/20 = 10개의 블록이 필요하다. -이진 검색으로 첫 번째 레코드를 찾으려면 log2(500) = 9 블록 액세스가 필요하다. 이진 검색의 총 비용은 9 + 10 – 1 = 18 블록 액세스이다 (선형 검색에서는 500) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 인덱스를 사용한 선택 인덱스 스캔 – 인덱스를 사용하는 검색 알고리즘 ; 조건은 인덱스의 검색 키상에 있다. A3 (후보 키상의 주 인덱스, 동등). 상응하는 조건을 만족하는 하나의 레코드를 검색한다. EA3 = HTi + 1 A4 (비 키상의 주 인덱스, 동등). 여러 레코드를 검색한다. 검색 키 애트리뷰트를 A라 하자. EA4 = HTi + A5 (2차 인덱스의 검색 키상의 동등). - 검색 키가 후보 키이면 하나의 레코드를 검색한다. EA5 = HTi + 1 - 검색 키가 후보 키가 아니면 여러 레코드를 검색한다 (각각은 서로 다른 블록에 있을 수 있다). EA5 = HTi + SC(A, r) f r ———— SC(A, r) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 비용 산정 예제 (인덱스) branch-name에 대해 주 인덱스를 가진 질의 branch-name = “Perryridge” (account)를 고려해 보자. V(branch-name, account) = 50 이므로, account 릴레이션 중에 10000/50 = 200개의 튜플이 Perryridge 지점에 속한다고 추정한다. 인덱스가 군집 인덱스이므로, account 튜플을 읽는데 200/20 = 10개의 블록 읽기가 필요하다. 몇 개의 인덱스 블록을 또한 읽어야 한다. B+ - 트리 인덱스가 노드당 20개의 포인터를 저장한다면, B+ - 트리 인덱스는 3 ~ 5 사이의 잎 노드를 가져야 하며 전체 트리의 깊이는 2이다. 그러므로, 2개의 인덱스 블록을 읽어야 한다. 이 전략으로는 12개의 블록 읽기가 필요하다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 비교를 내포한 선택 A  v(r) 또는 A  v(r) 형태의 선택을 선형 검색, 이진 검색을 사용 하 거나 다음과 같은 방식의 인덱스를 사용해 수행한다. A6 (주 인덱스, 비교). 비용 산정은 다음과 같다 : EA6 = HTi + 위에서 c는 조건을 만족하는 튜플의 추정 수이다. 통계 정보 c가 없으면, nr /2로 가정한다. A7 (2차 인덱스, 비교). 비용 산정은 다음과 같다. EA7 = HTi + + c 위에서 c는 이전과 같이 정의된다. (c가 크다면, 선형 검색이 비용이 적게 들 수 있다!) fr — c nr ———— LBi • c Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 복합 선택의 수행 조건 i의 선택도는 릴레이션 r의 한 튜플이 i를 만족하는 확률이다. Si가 r내의 만족하는 튜플 수라면, i의 선택도는 Si/nr이다. 논리곱 :   1   2  …   n(r). 산정 튜플 수는 다음과 같다 : nr * 논리합 : 1  2  …  n(r). 산정 튜플 수는 다음과 같다 : nr * 1 – ( 1 – ) * ( 1 – ) * ... * ( 1 – ) 부정 : (r). 산정 튜플 수는 다음과 같다. nr – size((r)) n ——————— S1 * S2 * … * S n n r ( nr — S1 S2 Sn ) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 복합 선택 알고리즘 A8 (하나의 인덱스를 사용한 논리곱 선택). i 와 i(r)에 대해 최소의 비용이 드는 A1~A7 알고리즘들 중 하나의 결합을 선택한다. 다른 조건들은 메모리 버퍼에서 테스트한다. A9 (다중 키 인덱스를 사용한 논리곱 선택). 사용 가능하다면 적절한 혼합(다중 키) 인덱스를 사용한다. A10 (식별자들의 공통 집합에 의한 논리곱 선택). 레코드 포인터를 가진 인덱스가 필요하다. 각 조건에 상응하는 인덱스를 상용하여 구해진 모든 레코드 포인터 집합의 공통 집합을 구한다. 그리고 파일을 읽는다. 몇 몇 조건이 적절한 인덱스를 갖지 않으면, 메모리 내에서 테스트를 한다. A11 (식별자들의 합집합에 의한 논리합 선택). 모든 조건들이 적절한 인덱스를 가진 경우에 적용한다. 그렇지 않으면 선형 검색을 사용한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 복합 선택에 대한 비용 산정의 예 아래와 같은 조건을 가진 account에서의 선택을 고려해 보자 : 알고리즘 A8을 사용해 보자 : - branch-name 인덱스가 군집이고 A8을 사용하면, 비용 산정은 12 개의 블록 읽기 이다(전에 이미 보았다). - balance 인덱스가 비군집이고 V(balance, account) = 50이므로 선 택은 10000/500 = 20개의 계좌를 검색한다. 인덱스 블록 읽기를 추가하면 비용 산정은 22개의 블록 읽기 이다. - 따라서, 그 조건이 보다 덜 선택하더라도 branch-name 인덱스를 사용하는 것이 더 낫다. - 양쪽 인덱스가 비군집이라면, balance 인덱스를 사용하는 것이 더 낫다. where branch-name = “Perryridge” and balance = 1200 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 예제 (계속) 알고리즘 A10을 사용해 보자 : - balance 인덱스를 사용해 balance = 1200인 레코드 포인터의 집합 S1을 검색한다. - branch-name 인덱스를 사용해 branch-name = “Perryridge”인 레코 드 포인터의 집합 S2를 검색한다. - S1  S2는 branch-name = “Perryridge”이고 balance = 1200인 레코 드 포인터의 집합이다. - 검색한 포인터의 수(20과 200)는 단일 잎 페이지에 들어간다 ; 두 포인터의 집합을 검색하기 위해 4개의 인덱스 블록을 읽어 그들 의 공통 집합을 계산한다. - 50*500 중의 한 튜플이 두 개의 조건을 만족한다고 추정한다. naccount = 10000이므로, S1  S2에 하나의 포인터를 포함한다고 어림잡아 과대 산정한다. - 이 전략의 총 비용 산정은 5개의 블록 읽기 이다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 정렬 릴레이션에 인덱스를 구축하여 정렬된 순서로 릴레이션을 읽는데 인덱스를 사용한다. 각 튜플마다 하나의 디스크 블록 액세스가 야기될 수 있다. 메모리에 수용되는 릴레이션에 대해서는 퀵 정렬같은 기법이 사용될 수 있다. 메모리에 수용되지 않는 릴레이션에 대해서는 외부 정렬-합병이 좋은 방법이다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 외부 정렬 - 합병 M을 페이지 단위의 메모리 크기라 하자. 1. 다음과 같이 정렬된 실행 파일을 생성한다. 처음에 i를 0으로 하자. 릴레이션의 끝까지 다음을 반복해 수행한다. (a) 릴레이션의 M블록을 메모리에 읽어 들인다. (b) 메모리내 블록을 정렬한다. (c) 정렬된 데이터를 실행 파일 Ri에 기록하고 i를 증가 시킨다. 2. 실행 파일을 합병한다 ; i < M이라 하자. 단일 합병 절차에서는 입력 실행 파일을 버퍼링하는데 i개의 메모리 블록과 출력을 버 퍼링하는데 i개의 블록을 사용한다. 모든 입력 버퍼 페이지가 빌 때까지 다음을 반복해 수행한다 : (a) 각 버퍼에서 정렬된 순으로 첫 번째 레코드를 선택한다. (b) 그 레코드를 출력에 기록한다. (c) 버퍼 페이지에서 그 레코드를 삭제한다 ; 버퍼 페이지가 비 면, 실행 파일의 다음 블록(있으면)을 버퍼에 읽어 들인다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 예제 : 정렬 - 합병을 사용한 외부 정렬 g 24 a 19 d 31 c 33 b 14 e 16 r 16 d 21 m 3 p 2 d 7 a 14 d 7 m 3 p 2 초기 릴레이션 실행파일 생성 합병 패스 - 1 패스 - 2 정렬 결과 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 외부 정렬 - 합병 (계속) i  M 이면, 여러 개의 합병 패스가 필요하다. - 각 패스에서, M – 1개의 실행 파일의 연속 그룹이 합병된다. - 패스는 M – 1로 실행 파일의 수를 감소시키고 똑 같은 요인에 의해 보다 긴 실행 파일을 생성한다. - 모든 실행 파일이 하나로 합병될 때까지 반복 패스가 수행된다. 비용 분석 : - 각 패스를 포함해 초기 실행 파일 생성을 위한 디스크 액세스는 2b r이다 (마지막 패스는 예외인데, 결과를 디스크에 출력하지 않는다). - 필요한 합병 패스의 총 수 : logM-1(br / M) 따라서, 외부 정렬을 위한 디스크 액세스의 총 수는 : br(2logM-1(br / M) + 1) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 죠인 연산 죠인을 실행하기 위한 알고리즘들은 다음과 같다 - 내포 – 루프 죠인 - 블록 내포 – 루프 죠인 - 인덱스 내포 – 루프 죠인 - 합병 – 죠인 - 해쉬 – 죠인 비용 산정에 따라 선택 관계형 대수 표현식에서 특히 외부 계층 연산에 대한 비용 산정을 위해 죠인 크기 산정이 필요하다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 죠인 연산 : 실행 예제 실행 예제 : depositor customer 죠인 예제에 대한 카타로그 정보 : ncustomer = 10,000. fcustomer = 25, 이것은 다음을 내포한다 bcustomer = 10000/25 = 400. ndepositor = 5000. fdepositor = 50, 이것은 다음을 내포한다 bdepositor = 5000/50 = 100. V(customer-name, depositor) = 2500, 이것은 각 고객이 평균 2개의 계좌를 가지고 있음을 의미한다. 또한 depositor내의 customer-name이 customer에 외래 키라고 가정한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 죠인 크기의 산정 카티전 곱 r  s는 n rn s 튜플을 내포하며, 각 튜플의 크기는 sr + ss 바이트이다. R  S = 이면, r s는 r  s와 같다. R  S가 R의 키이면, s의 한 튜플은 r의 기껏해야 한 튜플과 죠인 될 것이다. 그러므로, r s의 튜플의 수는 s내 튜플 수 보다 크지 않다. R  S가 R을 참조하는 S내의 외래 키이면, r s의 튜플의 수는 s내 튜플 수와 정확히 같다. R  S가 S를 참조하는 외래 키인 경우는 대칭적이다. 예제 질의 depositor customer 에서, depositor내의 customer-name은 customer의 외래 키이므로, 결과는 정확히 ndepositor의 튜플 수인 5000이다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 죠인 크기의 산정 (계속) R  S = {A}가 R 또는 S의 키가 아닌 경우. R내의 각 튜플 t가 R S 내의 튜플들을 생성한다고 가정하면, R S내 튜플의 수는 다음과 같이 산정된다. 그 역이 참이라면, 산정 값은 다음과 같을 것이다. 위의 두 산정 값 중에서 적은 것이 보다 정확한 값이 된다. nr * ns V(A, s) nr * ns ––––––– V(A, r) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 죠인 크기의 산정 (계속) 외래 키에 관한 정보를 사용하지 않고 depositor customer의 크기 산정을 계산해 보자 : - V(customer-name, depositor) = 2500, 이고 V(customer-name, customer) = 10000 - 두 산정 값은 5000 * 10000/2500 = 20,000 과 5000 * 10000/10000 = 5000 이다. - 이 경우에 적은 산정 값을 선택하는데, 이것은 외래 키를 사용해 앞에서 계산한 것과 같다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 내포 - 루프 죠인 세타 죠인 r s를 계산하자. r을 죠인의 외부 릴레이션이라 하고 s를 내부 릴레이션이라 한다. 어떤 인덱스도 필요로 하지 않고 어떤 종류의 죠인 조건에도 사용될 수 있다. 두 릴레이션내 각 튜플의 쌍을 조사해야 하므로 비용이 많이 든다. 보다 작은 릴레이션 전체가 메인 메모리에 들어가면, 그 릴레이션을 내부 릴레이션으로 사용한다. for each tuple tr in r do begin for each tuple ts in s do begin test pair (tr ,ts) to see if they satisfy the join condition  if they do, add tr • ts to the result. end Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 내포 - 루프 죠인 (계속) 최악의 겨우, 메모리에 각 릴레이션의 한 블록만을 수용할 수 있다면, 산정 비용은 nr * bs + br 디스크 액세스이다. 보다 작은 릴레이션 전체가 메모리에 들어 간다면, 그것을 내부 릴레이션으로 사용한다. 그렇게 하면 비용 산정은 bs + br 디스크 액세스로 줄어든다. 이용 가능한 메모리가 최악의 경우라 가정했을 때, depositor를 외부 릴레이션으로 하면 비용 산정은 5000 * 400 + 100 = 2,000,100 디스크 액세스이고, customer를 외부 릴레이션으로 하면 10000 * 100 + 400 = 1,000,400 디스크 액세스이다. 보다 작은 릴레이션(depositor) 전체가 메모리에 들어가면, 비용 산정은 500 디스크 액세스가 된다. 블록 내포 - 루프 알고리즘 (다음 장)이 더 낫다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 블록 내포 - 루프 죠인 내부 릴레이션의 각 블록이 외부 릴레이션의 각 블록과 쌍을 이루는 내포 - 루프 죠인의 변형이다. 최악의 경우 : 내부 릴레이션 s내 각 블록은 외부 릴레이션 각 블록마다 한번씩만 읽힌다 (외부 릴레이션내 각 튜플마다 한번씩 읽히는 대신). for each block Br of r do begin for each block Bs of s do begin for each tuple tr in Br do begin for each tuple ts in Bs do begin test pair (tr, ts) for satisfying the join condition if they do, add tr • ts to the result. end Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 블록 내포 - 루프 죠인 (계속) 최악의 경우의 산정 : br * bs + br 블록 액세스 최상의 경우의 산정 : br + bs 블록 액세스 내포 - 루프와 블록 내포 루프 알고리즘의 개선 : - 동등 – 죠인 애트리뷰트가 내부 릴레이션의 키이면, 부합이 처음 이루어지는 순간 내부 루프를 중단. - 블록 내포 – 루프에서는 외부 릴레이션을 위한 블록킹 단위로 M – 2 디스크 블록을 사용한다 (M은 블록 단위의 메모리 크기). 나머지 두 블록은 내부 릴레이션과 출력을 버퍼링하는데 사용한 다. 내부 릴레이션의 검색 수를 크게 줄인다. - 버퍼내에 남아 있는 블록을 사용하기 위해 내부 루프를 앞뒤로 교대로 스캔한다 (LRU 대치 전략으로). - 이용 가능하다면 내부 릴레이션의 인덱스를 사용한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 인덱스 내포 - 루프 죠인 내부 루프의 죠인 애트리뷰트에 인덱스가 있고 죠인이 동등 – 죠인 또는 자연 죠인이면, 보다 효율적인 인덱스 탐색이 파일 스캔을 대치할 수 있다. 죠인을 계산하기 위해서만 인덱스를 구축할 수도 있다. 외부 릴레이션 r내의 각 튜플 tr에 대해, 인덱스를 사용해 튜플 tr과 죠인 조건을 만족하는 s내의 튜플을 탐색한다. 최악의 경우 : 버퍼에 r의 한 페이지와 인덱스의 한 페이지만을 위한 공간을 가진다. - 릴레이션 r을 읽는데 br 디스크 액세스가 필요하고, r내의 각 튜 플에 대해 s상의 인덱스 탐색을 수행한다. - 죠인 비용 : br + nr * c (c는 죠인 조건을 사용하고 있는 s상의 단 일 선택 비용이다). r과 s 모두에 인덱스가 있다면, 보다 적은 튜플을 가진 것을 외부 릴레이션으로 사용한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 인덱스 내포 - 루프 죠인의 예 depositor를 외부 릴레이션으로 한 depositor customer를 계산 한다. customer에 죠인 애트리뷰트 customer-name상의 주 B+ - 트리 인덱 스를 가지고, 각 인덱스 노드에는 20개의 엔트리를 내포한다 하자. Customer에는 10,000개의 튜플이 있으므로, 트리의 높이는 4이고 실제 데이터를 찾으려면 한 번의 액세스가 더 필요하다. ndepositor는 5000이므로, 총 비용은 100 + 5000 * 5 = 25,100 디스크 액세스이다. 이 비용은 블록 내포 - 루프 죠인에서 필요했던 40,100 액세스보다 적다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 합병 - 죠인 1. 먼저 양 릴레이션을 그들의 죠인 애트리뷰트에 따라 정렬한다 (정렬되어 있지 않으면). 2. 죠인 절차는 정렬 – 합병 알고리즘의 합병 단계와 유사하다. 주된 차이점은 죠인 애트리뷰트 내의 중복 값을 처리하는 것이다 – 죠인 애트리뷰트상에 같은 값을 가진 각 쌍이 부합하는 것이다. a 3 b 1 d 8 d 13 f 7 m 5 q 6 a A b G c L d N m B pr a1 a2 ps a3 r s Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 합병 - 죠인 (계속) 각 튜플이 한번씩만 읽힐 필요가 있으면, 그 결과 각 블록 또한 한 번만 읽힌다. 따라서, 블록 액세스의 수는 br + bs이고, 릴레이션이 정렬되어 있지 않으면 정렬 비용이 추가 된다. 동등 – 죠인과 자연 죠인에만 사용될 수 있다. 한 릴레이션은 정렬되어 있고 다른 릴레이션에 죠인 애트리뷰트 의 2차 B+ - 트리 인덱스를 가지고 있으면, 하이브리드 합병 – 죠인 이 가능하다. 정렬된 릴레이션은 B+ - 트리의 잎 엔트리에 합병된 다. 결과는 정렬되지 않은 릴레이션의 튜플들의 주소로 정렬되고, 주소는 실제 튜플로 효율적으로 대치될 수 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 해쉬 - 죠인 동등 – 죠인과 자연 죠인에 적용 가능하다. 양쪽 릴레이션의 튜플들을 죠인 애트리뷰트에 같은 해쉬 값을 가지는 집합으로 분할하기 위해 해쉬 함수 h를 사용하며, 다음과 같다 : - h는 JoinAttrs 값들을 {0, 1, …, max}로 대응시킨다 (JoinAttrs는 자연 죠인에 사용되는 r과 s의 공통 애트리뷰트를 나타낸다). - Hr0, Hr1, …, Hrmax는 r 튜플들의 분할을 나타내며, 각각이 처음에 는 비어 있다. t r  r인 각 튜플은 분할 Hri에 들어가며, i = h(tr[JoinAttrs])이다. - Hs0, Hs1, …, Hsmax는 s 튜플들의 분할을 나타내며, 각각이 처음에 는 비어 있다. ts  s인 각 튜플은 분할 Hsi 에 들어가며, i = h(ts[JoinAttrs]) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 해쉬 - 죠인 (계속) Hri내의 r 튜플들은 Hsi내의 s 튜플들과만 비교될 필요가 있다 ; 다른 분할 내의 s 튜플과는 다음과 같은 이유로 비교될 필요가 없다 : - 죠인 조건을 만족하는 하나의 r 튜플과 s 튜플 은 죠인 애트리뷰트에 대해 같은 값을 갖는다. - 그 값이 어떤 값 i로 해쉬되면, r 튜플은 Hri내 에 있어야 하고 s 튜플은 Hsi내에 있어야 한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 해쉬 - 죠인 (계속) • 1 2 3 4 r의 분할들 s의 분할들 s Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 해쉬 - 죠인 알고리즘 r과 s의 해쉬 죠인은 다음과 같이 계산된다. 1. 해쉬 함수 h를 사용해 릴레이션 s를 분할한다. 릴레이션을 분할할 때, 메모리의 한 블록은 각 분할의 출력 버퍼로 남겨둔다. 2. 위와 유사하게 r을 분할한다. 3. 각 i에 대해 : (a) Hsi를 메모리에 넣고 죠인 애트리뷰트를 사용해 그에 메모리내 해쉬 인덱스를 구축한다. 이 해쉬 인덱스는 앞의 h와는 다른 해 쉬 함수를 사용한다. (b) 디스크에서 하나씩 Hri내의 튜플들을 읽는다. 각 튜플 tr에 대 해 메모리내 해쉬 인덱스를 사용해 Hsi 내의 부합하는 각 튜플 ts를 찾는다. 릴레이션 s를 구축 입력이라 하고 r을 탐색 입력이라 한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 해쉬 - 죠인 알고리즘 (계속) max 값과 해쉬 함수 h는 각 Hsi가 메모리에 들어가는 것으로 선택한다. 반복 분할. 분할의 수 max가 메모리의 M 페이지 수보다 크면, 반복 분할이 필요하다. - max 방향으로 분할하는 대신, s를 M – 1 방향으로 분할한다. - M – 1 분할들을 다른 해쉬 함수를 사용해 더욱 분할한다. - r에도 똑 같은 분할 방법을 사용한다. - 희귀한 경우 : 예를 들어, 블록의 크기가 4KB일 때 1GB 또는 메 모리 크기가 2MB보다 작은 릴레이션에는 반복 분할이 필요치 않다. 해쉬 테이블 오버플로. Hsi 가 메모리에 들어가지 않으면, 분할 Hsi 내에 해쉬 테이블 오버플로가 발생한다. 다른 해쉬 함수를 사용해 Hsi 를 더욱 분할해 해결할 수 있다. Hri 도 유사하게 분할되어야 한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 해쉬 - 죠인의 비용 반복 분할이 요구되지 않으면, 3(br + bs) + 2 * max. 반복 분할이 요구되면, s를 분할하는데 필요한 패스의 수는 logM-1(bs) - 1 이다. 이것은 s의 각 마지막 분할은 메모리에 있어야 하기 때문이다. 탐색 릴레이션 r의 분할의 수는 구축 릴레이션 s와 같다. r은 분할하는데 필요한 패스의 수는 또한 s와 같다. 그러므로, 구축 릴레이션으로 보다 작은 릴레이션을 선택하는 것이 좋다. 총 비용 산정은 다음과 같다 : 2( br +bs) logM-1(bs) - 1 + br +bs 구축 입력 전체가 메인 메모리에 들어갈 수 있으면, max는 0으로 설정될 수 있고 알고리즘은 릴레이션들을 임시 파일로 분할하지 않는다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 해쉬 - 죠인 비용의 예제 customer depositor bdepositor = 100이고 bcustomer = 400. depositor가 구축 입력으로 사용될 것이다. 그것은 각각의 크기가 20블록짜리 다섯 개의 분할로 분할된다. 이 분할은 한 패스로 이루어질 수 있다. 이와 유사하게, customer는 80블록짜리 5개의 분할로 분할되며, 이 또한 한 패스로 이루어질 수 있다. 그러므로, 총 비용은 3(100 + 400) = 1500 블록 전송이 된다 (부분적으로 들어찬 블록 쓰기 비용은 무시한다). Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 하이브리드 해쉬 - 죠인 메모리 크기가 비교적 크고 구축 입력이 메모리보다 클 때 유용하다. 메모리 크기가 25블록인 경우, depositor는 각각의 크기가 20블록짜리 다섯 개의 분할로 분할될 수 있다. 구축 입력 분할 중 첫 번째 것을 메모리에 저장한다. 그것은 20개의 블록을 차지한다 ; 하나의 블록은 입력으로 사용되고 하나의 블록 각각은 다른 4개 분할을 버퍼링하는데 사용된다. customer도 이와 유사하게 각각의 크기가 80블록인 5개의 분할로 분할된다. 첫 번째 분할은 출력되고 되 읽는 대신 곧바로 탐색에 사용된다. 부분적으로 들어찬 블록의 출력 비용을 무시하면, 평범한 해쉬 – 죠인으로는 1500블록 전송이던 비용이 하이브리드 해쉬 – 죠인으로는 3(80 + 320) + 20 + 80 = 1300블록 전송이 된다. M >>  bs 일 때 하이브리드 해쉬 – 죠인이 가장 유용하다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 복합 죠인 다음과 같은 논리곱 조건을 가진 죠인 : r 1  2  …  n s - 보다 단순한 죠인들 r i s 중 하나의 결과를 계산한다. - 마지막 결과에는 다음과 같은 나머지 조건을 만족하는 중간 결 과 내의 튜플들을 포함한다. 1  …  i-1  i+1  …  n - 이들 조건은 r i s 내의 튜플들이 생성될 때 테스트한다. 다음과 같은 논리합 조건을 가진 죠인 : r 1  2  …  n s 개별 죠인들 r i s 내 레코드들의 합집합으로서 계산한다 : (r 1 s)  (r 2 s)  …  (r n s) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 복합 죠인 (계속) 3개의 릴레이션을 내포한 죠인 : loan depositor customer 전략 1. depositor customer를 계산한다 ; 그 결과를 사용해 loan (depositor customer)를 계산한다. 전략 2. loan depositor를 먼저 계산하고, 그 결과와 customer를 죠인한다. 전략 3. 죠인들의 쌍을 동시에 수행한다. loan에 loan-number로, customer에 customer-name으로 인덱스를 구축한다. - depositor내 각 튜플 t에 대해, customer와 loan내의 상응하는 튜플 들을 탐색한다. - depositor의 각 튜플은 정확히 한 번만 검사된다. 전략 3은 두 연산을 두 릴레이션의 두 죠인을 수행하는 것보다 더 효율적인 하나의 특수 목적 연산으로 결합한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 기타 연산 중복 제거는 해슁 또는 정렬을 통해 수행될 수 있다. - 정렬시 중복은 서로 인접해 있을 것이고, 중복 집합중의 하나만 제외하고는 삭제될 수 있다. 최적화 : 중복은 외부 정렬 – 합병에서의 중간 합병 단계에서와 함께 실행 파일 생성시 삭제될 수 있다. - 해슁도 유사하다 – 중복은 같은 버켓에 있게 될 것이다. 추출은 각 튜플에 추출을 수행한 후 중복을 제거함으로써 구현된다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 기타 연산 (계산) 집성 연산은 중복 제거와 유사한 방법으로 수행할 수 있다. - 정렬 또는 해슁이 튜플들을 같은 그룹에 함께 넣는데 사용될 수 있으며, 집성 함수는 각 그룹에 적용될 수 있다. - 최적화 : 부분적인 집성 값을 계산함으로써 실행 파일 을 생성하고 중간 합병하는 동안 튜플들은 같은 그룹 으로 묶는다. 집합 연산 (,  및 –) : 정렬한 후 합병 – 죠인의 변형을 사용하거나 해쉬 – 죠인의 변형을 사용할 수 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 기타 연산 (계속) 예를 들어, 해슁을 사용한 집합 연산 1. 같은 해쉬 함수를 양쪽 릴레이션을 분할해 Hr0, … , Hrmax 와 Hs0, … Hsmax를 생성한다. 2. 각 분할 i를 다음과 같이 처리한다. 다른 해쉬 함수를 사용해 메모리에 넣은 후 Hri 상에 메모리내 해쉬 인덱스를 구축한다. 3. - r  s : 존재하지 않으면 Hsi내의 튜플들을 해쉬 인덱스에 추가 한다. 그리고 해쉬 인덱스 내의 튜플들을 결과에 추가 한다. - r  s : 해쉬 인덱스 내에 이미 존재하면 Hsi 내의 튜플들을 결 과에 출력한다. - r – s : Hsi 내의 각 튜플에 대해, 해쉬 인덱스 내에 있으면 인덱 스로부터 삭제한다. 해쉬 인덱스 내의 나머지 튜플들을 결과에 추가한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 기타 연산 (계속) 외부 죠인은 다음 중 하나로 계산할 수 있다. - 참가하지 않는 튜플들에 널을 채워 추가한 후 죠인. - 죠인 알고리즘을 수정함으로써 예 : - r s에서, 참가하지 않는 튜플들은 r – R(r s)내의 것들이다. - 합병 – 죠인을 수정하여 r s를 계산한다 : 합병하는 동안, s 내 의 어떤 튜플과 부합하지 않는 r의 각 튜플 tr에 대해 널로 채워 출 력한다. - 우측 외부 죠인과 완전 외부 죠인도 이와 유사하게 계산될 수 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 표현식의 평가 구체화 : 최하위 단계에서 시작해 한 번에 하나의 연산을 평가한다. 구체화된 결과를 임시 릴레이션 내에서 사용해 다음 단계 연산을 평가한다. 아래 그림의 예에서, balance < 2500(account)를 계산하고 저장한다 ; 그리고 customer와 죠인하고 저장하고, 최종적으로 customer-name 추출을 계산한다. customer-name balance < 2500 customer account Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 표현식의 평가 (계속) 파이프라이닝 : 한 연산의 결과를 다음으로 넘기면서 여러 연산을 동시에 평가한다. 앞 장 표현식의 예에서, balance < 2500(account)의 결과를 저장하지 않고 튜플들을 직접 죠인으로 넘긴다. 이와 유사하게, 죠인 결과를 저장하지 않고 튜플들을 직접 추출로 넘긴다. 구체화보다 비용이 덜 든다 : 디스크에 임시 릴레이션을 저장할 필요가 없다. 파이프라이닝이 항상 가능한 것은 아니다 – 예를 들어, 정렬과 해쉬 – 죠인 파이프라이닝을 효과적으로 하기 위해, 연산에 입력으로 도달되는 튜플들 조차 출력 튜플을 생성하는 평가 알고리즘을 사용한다. 파이프라인은 두 가지 방법으로 실행될 수 있다 : 요구불 구동과 생성자 구동. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 관계형 표현식의 변환 표현식을 위한 질의 평가 계획의 생성에는 두 가지 절차를 내포한다 : 1. 논리적으로 동등한 표현식을 생성 2. 결과 표현식에 주석을 달아 대안의 질의 계획 얻기 표현식을 동등한 것으로 변환하기 위해 동등성 규칙을 사용한다. 산정 비용에 근거해 가장 비용이 싼 계획을 선택한다. 이러한 처리를 비용 기반 최적화라 한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 표현식의 동등성 두 개의 동등한 표현식으로 생성되는 릴레이션들은 애트리뷰트들이 다른 순서로 되어 있더라도, 같은 애트리뷰트의 집합을 가지고 같은 튜플의 집합을 내포한다. customer-name branch-city=Brooklyn branch account depositor (a) 초기 표현식 트리 (b) 변환된 표현식 트리 동등한 표현식 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 동등성 규칙 1. 논리곱 선택 연산은 일련의 개별 선택으로 분리될 수 있다. 2. 선택 연산은 교환 법칙이 성립한다. 3. 일련의 추출 연산들중 마지막 것만이 필요하고, 다른 것들은 생략 될 수 있다. 4. 선택은 카티전 곱과 세타 죠인으로 결합될 수 있다. (a) (b) 1  2 (E) = 1 (2(E)) 1(2(E)) = 2 (1(E)) L1(L2(…(Ln (E)) …)) = L1(E)  (E1  E2) = E1  E2 1 (E1 2 E2) = E1 1  2 E2 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 동등성 규칙 (계속) 5. 세타 죠인 연산 (및 자연 죠인)은 교환 법칙이 성립한다. 6. (a) 자연 죠인 연산은 결합 법칙이 성립한다 : (b) 세타 죠인은 다음과 같은 방식의 결합 법칙이 성립한다 : 위에서 2는 E2와 E3로부터의 애트리뷰트만을 내포한다. E1  E2 = E2  E1 (E1 E2) E3 = E1 (E2 E3) (E1 1 E2) 2  3 E3 = E1 1  3 (E2 2 E3) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 동등성 규칙 (계속) 7. 선택 연산은 다음과 같은 두 조건하에서 세타 죠인 연산에 걸쳐 분 배된다. (a) 0내 모든 애트리뷰트가 죠인되고 있는 표현식 중의 하나(E1)의 애트리뷰트만을 내포할 때. (b) 1은 E1의 애트리뷰트만을 내포하고 2는 E2의 애트리뷰트만을 내포할 때 0(E1  E2) = (0(E1))  E2 1  2(E1  E2) = (1(E1))  (2(E2)) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 동등성 규칙 (계속) 8. 추출 연산은 다음과 같이 세타 죠인 연산에 걸쳐 분배된다. (a) 가 L1  L2의 애트리뷰트만을 내포하면 : (b) E1  E2 죠인을 고려해 보자. L1과 L2를 각각 E1과 E2의 애트리 뷰트 집합이라 하자. L3는 죠인 조건 에 내포되지만 L1  L2에 는 없는 E1의 애트리뷰트라 하고, L4는 죠인 조건 에 내포되지 만 L1  L2에는 없는 E2의 애트리뷰트라 하자.  L1  L2(E1  E2) = ( L1 (E1))  ( L2 (E2))  L1  L2(E1  E2) =  L1  L2 (( L1  L3 (E1))  ( L2  L4 (E2))) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 동등성 규칙 (계속) 9. 합집합과 공통 집합 연산은 교환 법칙이 성립한다 (차집합 연산은 교환 법칙이 성립하지 않는다). 10. 합집합과 공통 집합은 결합 법칙이 성립한다. 11. 선택 연산은 ,  및 – 에 걸쳐 분배된다. 예를 들어 : 차집합과 공통 집합에 대해서는 다음이 성립한다. 12. 추출 연산은 합집합 연산에 걸쳐 분배된다. E1  E2 = E2  E1 E1  E2 = E2  E1 P(E1 - E2) = P (E1) – P(E2) P(E1 - E2) = P (E1) – E2 L(E1  E2) = (L(E1))  (L(E2)) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 선택 연산 예제 질의 : Brooklyn에 위치한 어떤 지점에 계좌를 가진 모든 고객명을 찾아라. 규칙 7a를 사용한 변환 선택을 가능한 먼저 수행하면 죠인될 릴레이션의 크기를 줄인다. customer-name(branch-city = “Brooklyn” (branch (account depositor))) customer-name((branch-city = “Brooklyn” (branch)) (account depositor)) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 선택 연산 예제 (계속) 질의 : 예금 잔고가 1,000불을 초과하는 Brooklyn에 계좌를 가진 모든 고객명을 찾아라. 죠인의 결합 법칙을 사용한 변환 (규칙 6a) : 두번째 형식에 “가능한 먼저 선택” 규칙을 적용해 다음과 같은 부 표현식을 얻는다 따라서, 일련의 변환이 사용 가능할 수 있다. customer-name(branch-city = “Brooklyn”  balance > 1000 (branch (account depositor))) customer-name((branch-city = “Brooklyn”  balance > 1000 (branch account)) depositor) branch-city = “Brooklyn” (branch) balance > 1000 (account) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

추출 연산 예제 customer-name((branch-city = “Brooklyn” (branch) 다음을 계산하면 아래와 같은 스키마를 가진 릴레이션을 얻는다 : 동등성 규칙 8a와 8b를 사용해 추출을 앞으로 밀어내 얻어지는 중간 결과에서 불필요한 애트리뷰트를 제거한다. customer-name((branch-city = “Brooklyn” (branch) account) depositor) (branch-city = “Brooklyn” (branch) account) (branch-name, branch-city, assets, account-number, balance) customer-name((account-number ( (branch-city = “Brooklyn” (branch)) account)) depositor) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 죠인 순서화 예제 모든 릴레이션 r1, r2 및 r3에 대해 r2 r3 가 매우 크고 r1 r2 가 작다면, 다음과 같이 선택하여 보다 작은 임시 릴레이션을 계산하고 저장하도록 한다. (r1 r2) r3 = r1 (r2 r3) (r1 r2) r3 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 죠인 순서화 예제 (계속) 다음 표현식을 고려해 보자 account depositor를 먼저 계산하여 아래와 죠인할 수 있다. 그러나, account depositor는 큰 릴레이션일 가능성이 있다. 은행 고객중 소수만이 Brooklyn에 위치한 지점에 계좌를 가지고 있을 가능성이 보다 크므로, 다음을 먼저 계산하는 것이 보다 낫다. customer-name((branch-city = “Brooklyn” (branch)) account depositor) branch-city = “Brooklyn” (branch) branch-city = “Brooklyn” (branch) account Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 평가 계획 평가 계획은 각 연산에 어떤 알고리즘이 사용되고 연산들 의 실행이 어떻게 협력하는지를 정확히 정의한다. customer-name(중복 제거를 위해 정렬한다. ) (해쉬-죠인) (합병-죠인) depositor 파이프라인 파이프라인 branch-city=Brooklyn balance < 1000 (인덱스 1을 사용) (선형 검색을 사용) branch account 평가 계획 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 평가 계획의 선택 평가 계획을 선택할 때는 평가 기법의 상호 작용을 고려해야 한다 : 각 연산에 대해 독립적으로 가장 비용이 적은 알고리즘을 선택하는 것이 전체적으로 최상의 알고리즘을 생성하지 못할 수도 있다. 예를 들어, - 합병–죠인이 해쉬–죠인보다 비용이 더 들 수 있지만, 외부 단계 의 집성 연산에 대해서는 비용을 줄이는 정렬된 출력을 제공할 수도 있다. - 내포 –루프 죠인은 파이프라이닝을 위한 기회를 제공한다. 실제 질의 최적기는 다음과 같은 두 가지 넓은 방법들의 요소를 결합한다 : 1. 모든 계획을 검색해 비용기반 유형에서 최상의 계획을 선택한다. 2. 경험을 사용해 계획을 선택한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 비용 기반 최적화 r1 r2 … rn에 대한 최상의 죠인 순서를 찾아 보자. 위의 표현식에 대해 (2(n - 1))! / (n - 1)!의 죠인 순서가 존재한다. n = 7이면 그 수는 665280이고, n = 10이면 그 수는 1760억 보다 크다. 모든 죠인 순서를 생성할 필요가 없다. 동적 프로그래밍을 사용하면, {r1, r2, … , rn}의 어떤 부분 집합에 대한 최소 비용의 죠인 순서는 한 번만 계산되고 미래의 사용을 위해 저장된다. 이것은 시간 복잡성을 대략 O(3n)으로 줄인다. n = 10이면, 이 수는 59000이다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 비용 기반 최적화 (계속) 왼쪽-깊이 죠인 트리에서, 각 죠인에 대한 오른쪽 편의 입력은 중간 죠인의 결과가 아닌 릴레이션이다. 왼쪽-깊이 죠인 트리만이 고려된다면, 최상의 죠인 순서 비용은 O(2n)이 된다. r3 r4 r5 r2 r1 r1 r2 r3 r4 r5 (a)왼쪽-깊이 죠인 트리 (b)비왼쪽-깊이 죠인 트리 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 최적화에서의 동적 프로그래밍 n 릴레이션 집합에 대한 최상의 왼쪽–깊이 죠인 트리를 찾으려면 : - 하나의 릴레이션을 오른쪽 편 입력으로 하고 다른 릴레이션들은 왼쪽 편 입력으로 한 n개의 대안을 고려한다. - 왼쪽 편의 각 대안에 대해 최소 비용 죠인 순서를 사용해 (반복해 계산하고 저장함), n개 대안중 가장 비용이 적은 것을 선택한다. n 릴레이션 집합에 대한 최상의 죠인 트리를 찾으려면 : - n 릴레이션중 집합 S에 대한 최상의 계획을 찾기 위해, 다음과 같 은 형식의 모든 가능한 계획을 고려한다 : S1 (S – S1), 여기서 S1은 S의 어떤 공집합이 아닌 부분 집합. - 이전처럼 각 계획의 비용을 찾기 위해 S의 부분 집합에 대해 반 복적으로 계산하고 저장된 비용을 사용한다. 2n – 1 대안중 가장 비용이 적은 것을 찾는다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 비용 기반 최적화에서 흥미있는 순서 표현식 를 고려해 보자. 흥미있는 정렬 순서란 이후의 연산에 사용될 수 있는 튜플들의 특정 정렬 순서이다. - r4 또는 r5에 공통인 애트리뷰트로 정렬된 의 결과 를 생성하는 것은 유용하지만, r1과 r2에 공통인 애트리뷰트로 생 성하는 것은 유용하지 않다. - 합병–죠인을 사용해 를 계산하는 것이 비용이 더 들지만, 흥미있는 순서로 정렬된 출력을 제공한다. 주어진 n 릴레이션 집합 각 부분 집합에 대해 최상의 죠인 순서를 찾는 것으로는 불충분하다 ; 그 부분 집합을 위한 죠인 결과의 각 흥미있는 정렬 순서에 대해 각 부분 집합에 대한 최상의 죠인 순서를 찾아야 한다. 앞의 동적 프로그래밍 알고리즘을 단순히 확장하면 된다. (r1 r2 r3 ) r4 r5 r1 r2 r3 r1 r2 r3 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 경험적 최적화 동적 프로그래밍을 가진다 하더라도 비용 기반 최적화는 경비가 많이 든다. 시스템은 비용 기반 유형으로 이루어져야 하는 선택의 수를 줄이는데 경험을 사용할 수 있다. 경험적 최적화는 일반적으로 실행 성능을 향상시키는 (모든 경우는 아니지만) 규칙의 집합을 사용해 질의 트리를 변환한다. - 가능한 먼저 선택을 수행한다 (튜플의 수를 줄인다). - 가능한 먼저 추출을 수행한다 (애트리뷰트의 수를 줄인다). - 다른 유사한 연산 이전에 가장 제한적인 선택과 죠인 연산을 수 행한다. 어떤 시스템에서는 경험만을 사용하고, 다른 시스템에서는 경험과 부분적인 비용 기반 최적화를 결합한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 전형적인 최적화 절차 1. 논리곱 선택을 일련의 단일 선택 연산으로 분해한다 (규칙 1). 2. 가장 먼저 실행이 되도록 선택 연산을 질의 트리 아래로 이동시 킨다 (규칙 2, 7a, 7b, 11). 3. 가장 작은 릴레이션을 생성할 선택과 죠인 연산을 먼저 실행한다 (규칙 6). 4. 선택 조건이 뒤에 나오는 카티전 곱 연산을 죠인 연산으로 대치 한다 (규칙 4a) 5. 필요한 곳에 새로운 추출을 생성하면서 추출 애트리뷰트 리스트를 분해해 가능한 트리의 아래로 이동시킨다 (규칙 3, 8a, 8b, 12) 6. 연산들이 파이프라인될 수 있는 부 트리를 인지하여 파이프라이닝 을 사용해 실행한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 질의 최적기의 구조 System R 최적기는 왼쪽-깊이 죠인 순서만을 고려한다. 이것은 최적화 복잡성을 줄이고 파이프라인 평가에 따르는 계획을 생성한다. System R은 또한 경험을 사용해 선택과 추출을 질의 트리 아래로 보낸다. 2차 인덱스를 사용한 검색에 대해, Sybase 최적기는 튜플을 포함하고 있는 페이지가 버퍼에 있을 확률을 고려한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 질의 최적기의 구조 (계속) 어떤 질의 최적기는 경험적 선택과 대안의 액세스 계획의 생성을 통합한다. - System R과 Starburst는 SQL의 내포 블록 개념에 근거한 경험적 프로시저를 사용한다 : 비용 기반 죠인 순서 최적화가 뒤따르는 경험적 되쓰기. - Oracle7 최적기는 사용 가능한 액세스 경로에 근거한 경험을 지 원한다. 경험을 사용한다 하더라도, 비용 기반 질의 최적화는 실질적인 비용을 부과한다. 이 비용은 일반적으로 특히 저속의 디스크 액세스 수를 감소시킴으로써 질의 실행시 얻는 절약으로 상쇄되고 남는다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수