질의처리(Query Processing)와 최적화(Optimization) 박 영철 컴퓨터과학과 경북대학교

질의처리와 최적화 [그림 18.1] 고수준의 질의를 처리하는 과정 고수준 언어(SQL)로 표현된 질의 어휘 분석(Scanning), 구문 분석(Parsing), 검증(Validating) A parsed representation of a SQL query 질의 최적화기(Query Optimizer) 실행 계획(Execution Plan) 질의 코드 생성기 코드는 직접 실행되거나 (인터프리터 방식), 저장된 뒤 필요할 때마다 실행될 수 있다. (컴파일 방식). 질의를 실행하기 위한 코드 런타임 데이타베이스 처리기 질의 결과 [그림 18.1] 고수준의 질의를 처리하는 과정 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 질의처리와 최적화(cont.) SQL queries are typically translated into Relational Algebra Queries and then optimized. Algorithms for implementing relational operations. Overview of query optimization strategies Heuristic Optimization Heuristic rules for ordering the operations in a query execution strategy. The rules typically reorder the operations in a query tree. Cost Estimation Systematically estimating the cost of different execution strategies and choosing the execution plan with the lowest cost estimate. Semantic Optimization 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems SQL 질의를 관계대수로 번역하기 SQL 질의를 최적화 하기 위한 준비 단계이다. A Nested Query v.s. A Single Block Query. [예] Uncorrelated Nested Query (비상관 중첩질의) SQL 질의 : SELECT LNAME, FNAME FROM EMPLOYEE WHERE SALARY > (SELECT MAX(SALARY) FROM EMPLOYEE WHERE DNO = 5); (2) 질의 블록들로 분해: 외부질의(Outer Query)  외부블록 : SELECT LNAME, FNAME FROM EMPLOYEE WHERE SALARY > C 내부질의(Inner Query)  내부블록: SELECT MAX(SALARY) FROM EMPLOYEE WHERE DNO = 5 (3) 관계대수로 번역: 외부블록:πLNAME, FNAME(σSALARY>C(EMPLOYEE)) 내부블록:  MAX (SALARY) (σDNO=5(EMPLOYEE)) 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems SQL 질의를 관계대수로 번역하기 SQL 질의를 최적화 하기 위한 준비 단계이다. [예] Correlated Nested Query (상관 중첩질의) SQL 질의 : SELECT e.LNAME, e.FNAME FROM EMPLOYEE e WHERE e.SSN IN (SELECT ESSN FROM DEPENDENT WHERE e.FNAME = DEPENDENT_NAME AND e.SEX = SEX); (2) 변경된 SQL 질의 : SELECT e.LNAME, e.FNAME FROM EMPLOYEE e, DEPENDENT d WHERE e.SSN = d.ESSN AND e.SEX = d.SEX AND e.FNAME = d.DEPENDENT_NAME; Note. In general, a query written with nested SELECT … FROM … WHERE … blocks and using the = or IN comparison operators can always be expressed as a single block query. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 질의 연산들을 실행하기 위한 기본 알고리즘들 18.1.1 외부 정렬 18.1.2 실렉트 연산의 구현 18.1.3 조인 연산의 구현 18.1.4 프로젝트와 집합 연산의 구현 18.1.5 집단 연산의 구현 18.1.6 외부 조인의 구현 18.1.7 파이프라이닝을 사용한 연산의 결합 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 외부 정렬(External Sort) 필요성 GROUP BY 절, ORDER BY 절, SELECT 절의 DISTINCT, 조인(Sort-Merge Join) 집합 연산 (합집합 union, 교집합 intersection, 차집합 set difference) 알고리즘 정렬 단계 (sorting phase) Read RUN; Sort; Write RUN  Runs : portions or pieces 합병 단계 (merging phase) 4-way 합병 (4개의 RUN들을 합병하여 하나의 RUN을 생성) 하나의 RUN으로 될 때 까지 합병을 반복 수행한다. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 외부 정렬(External Sort) Complexity of the algorithm the number of file blocks : b the number of available buffer space : nB the number of initial runs : nR = ceiling(b /nB) the degree of merging : dM  e.g., 4 (four-way merging)  the number of runs that can be merged together in each pass the number of merging passes : ceiling(logdM(nR)) the number of block accesses for the sorting phase and the merging phase: (2 * b) + (2 * (b * logdM(b))) 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 실렉트 연산의 구현 select * from EMP where ssn = ‘123456789’; select * from DEPT where dno > 5; select * from EMP where dno = 5; select * from EMP where dno = 5 AND SALARY > 30000 AND SEX = ‘F’; select * from WORKS_ON where essn = ‘123456789’ AND pno = 10; select * from EMP where dno = 5 AND SALARY > 30000 OR SEX = ‘F’; An Exact match query v.s. A Range Query (범위 질의) 단일 선택 v.s. 다중 선택 단순 선택 (simple selection) v.s. 복합 선택(complex selection) Conjunctive Condition (논리곱 조건) v.s. Disjunctive Condition(논리합 조건) 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 실렉트 연산의 구현 단순 선택을 위한 검색 방법 (단일 레코드 검색 v.s. 레코드들을 검색) 화일 스캔 S1. 선형 탐색(linear search) S2. 이진 탐색(binary search) : Not available for DBMS 인덱스 스캔 S3. 기본 인덱스 또는 해시 키를 사용하여 단일 레코드를 검색 S4. 기본 인덱스를 사용하여 레코드들을 검색 S5. 클러스터링 인덱스를 사용하여 레코드들을 검색 S6. 보조(B+-트리) 인덱스를 사용 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 실렉트 연산의 구현 (cont.) 복합 선택을 위한 검색 방법 논리곱 조건인 경우 : 인덱스를 이용하여 RID들을 구하고 이들을 통해 레코드들을 읽어서 다른 조건들을 비교함. S7. 개별 인덱스를 사용하는 논리곱 선택(conjunctive selection) S8. 복합 인덱스를 사용하는 논리곱 선택 S9. RID들의 교집합에 의한 논리곱 선택 논리합 조건인 경우 : 각 조건을 만족하는 레코드들의 합집합 방법 1. 단순 조건들 중 어느 하나라도 접근경로를 가지지 않으면 선형 탐색 방법을 사용할 수 밖에 없다. 방법 2. 각 조건을 만족하는 RID들의 합집합을 구하여 레코드들을 읽음. Note. 선택도(Selectivity. 조건을 만족하는 투플수를 Table의 전체 투플수로 나눈 값)에 따라 인덱스를 선택함. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 조인 연산의 구현 예 select e.fname, d.dname from EMP e, DEPT d where e.dno = d.dnumber; select e.fname, d.dname from DEPT d, EMP e where d.MGRSSN = e.SSN; J1. 중첩 루프 조인(nested loop join 또는 inner-outer loop join) R(외부 loop)의 각 레코드에 대해 S(내부 loop)의 모든 레코드들을 검색하고, 두 레코드가 조인조건을 만족하는가를 테스트한다. J2. 단일 루프 조인(single loop join) R의 각 레코드에 대해 인덱스를 사용하여 S의 레코드들 중에서 조인 조건을 만족하는 모든 레코드들을 검색한다. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 조인 연산의 구현(cont.) J3. 정렬-합병 조인(Sort-Merge Join) R과 S의 모든 레코드들을 Join Attribute를 기반으로 정렬한 후, R과 S의 화일 블록들의 쌍을 순서대로 읽어서 조인 조건을 테스트한다. J4. 해시조인(Hash Join) 분할단계 : R의 레코드들을 해시 화일 버켓들로 해시한다. 조사단계: S의 각 레코드를 해시하여 동일한 해시주소를 갖는 각 버켓에 속하는 R과 S의 레코드들이 조인조건을 만족하면 결합한다 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 18.2.3 조인 연산의 구현(cont.) (a) sort the tuples in R on attribute A; /* assume R has n tuples(records) */ sort the tuples in S on attribute B; /* assume S has m tuples(records) */ set i ← 1, j←1; while(i<=n) and (j<=m) do { if R(i)[A] > S(j)[B] then set j ← j+1; elseif R(i)[A] < S(j)[B] then set i← i+1 else { /*R(i)[A] = S(j)[B], so we output a matched tuple */ output the combined tuple <R(i), S(j)> to T; /*output other tuples that match R(i), if any */ set l←j+1; while(l<=m) and (R(i)[A]=S(j)[B]) do { output the combined tuple <R(i),S(l)> to T; set l← l+1 } /* output other tuples that match S(j), if any */ set k←i+1; while(k<=n) and (R(k)[A]=S(j)[B]) do { output the combined tuple <R(k), S(j)> to T; set k← k+1; set i← k, j← l [그림 18.3] n개의 투플을 가진 릴레이션 R과 m개의 투플을 가진 릴레이션 S에 대해 정렬을 이용하여 조인, 프로젝트, 합집합, 교집합, 차집합 연산들을 구현 (a) T← R A = B S 연산의 구현 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 조인 연산의 비용 J1 방법. select e.fname, d.dname from EMP e, DEPT d where e.dno = d.dnumber; EMPLOYEE가 외부 루프로 사용되면 EMPLOYEE의 각 블록은 한 번씩 읽혀지고, 전체 DEPARTMENT 화일은 EMPLOYEE 화일에서 nB - 2개의 블록을 읽어들일 때마다 한 번씩 읽혀진다. 총 블록 접근 수= bE + (bE/(nB - 2) *bD) = 2000 + (2000/5 *10) = 6000 외부 루프에 DEPARTMENT 화일을 사용하면 총 블록 접근 수= bD + (bD/(nB - 2) *bE) = 10 + ( 10/5 *2000) = 4010 J2. select e.fname, d.dname from DEPT d, EMP e where d.MGRSSN = e.SSN; EMPLOYEE의 SSN 애트리뷰트와 DEPARTMENT의 MGRSSN 애트리뷰트 모두에 보조 인덱스가 존재하고, 각 인덱스 단계 수가 xSSN = 4이고 xMGRSSN = 2라고 가정하자. 각 EMPLOYEE 레코드를 검색하고 부합되는 DEPARTMENT 레코드를 찾기 위해서 DEPARTMENT의 MGRSSN에 대한 인덱스를 사용하는 경우. bE + (rE * (xMGRSSN + 1)) = 2000 + (5000 * 3) = 17,000번의 블록 접근 (2) 각 DEPARTMENT 레코드를 검색하고, 부합되는 EMPLOYEE 레코드를 찾기 위해서 EMPLOYEE의 SSN에 대한 인덱스를 사용하는 경우. bD + (rD * (xSSN + 1)) = 10 + (50 * 5) = 260번의 블록 접근 조인 선택 요인(join selection factor). 한 화일의 레코드들 중에서 다른 화일에 있는 레코드들과 조인되는 비율이다. 이 요인을 다른 화일과의 동등조인의 관점에서 화일의 조인 선택 요인(join selection factor)이라 한다. 조인조건 SSN = MGRSSN에 대해서 DEPARTMENT의 조인 선택 요인 = 1. EMPLOYEE의 조인 선택 요인 = 50/5000 = 0.01. J3 방법. 정렬-합병조인의 전체 비용 = (bE + bD + bE log2bE + bD log2bD) 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 프로젝트와 집합 연산의 구현 ∏<attribute list> (R) <attribute list>가 R의 키를 포함할 경우 연산의 결과가 R과 같은 수의 투플들을 가진다. <attribute list>가 R의 키를 포함하지 않을 경우 연산의 결과를 정렬한 후 중복된 투플을 제거해야 한다. 합집합, 교집합, 차집합 : 합집합 호환성 릴레이션들에만 적용 동일한 애트리뷰트들에 대해 두 릴레이션들을 정렬한 후 각 릴레이션을 한번 조사하는 것으로 결과를 산출 카티션 프로덕트(R X S) 구현 비용이 비싸므로 질의 최적화 동안 연산을 피하고 동등한 연산으로 대치 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 프로젝트와 집합 연산의 구현 (b) create a tuple t[<attribute list>] in T’ for each tuple t in R; /* T’ contains the projection result before duplicate elimination */ if <attribute list> includes a key of R then T ← T’ else { sort the tuples in T’; set i←1, j←2; while i<= n do {output the tuple T’[i] to T; while T’[i] = T’[j] do j← j+1; (* eliminate duplicates *) i←j, j←i+1 } /* T contains the projection result after duplicate elimination */ [그림 18.3] n개의 투플을 가진 릴레이션 R과 m개의 투플을 가진 릴레이션 S에 대해 정렬을 이용하여 조인, 프로젝트, 합집합, 교집합, 차집합 연산들을 구현(cont.) (b) T ← ∏<attribute list> (R) 연산의 구현 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 프로젝트와 집합 연산의 구현 (c) sort the tuples in R and S using the same unique sort attributes; set i← 1, j←1; while (i<=n) and (j<=m) do { if R(i) > S(j) then { output S(j) to T; set j← j+1 } elseif R(i) < S(j) then { output R(i) to T; set i← i+1 else set j←j+1 /* R(i) = S(j), so we skip one of the duplicate tuples */ if (i<=n) then add tuples R(i) to R(n) to T; if (j<=m) then add tuples S(j) to S(m) to T; [그림 18.3] n개의 투플을 가진 릴레이션 R과 m개의 투플을 가진 릴레이션 S에 대해 정렬을 이용하여 조인, 프로젝트, 합집합, 교집합, 차집합 연산들을 구현(cont.) (c) T← R∪S 연산의 구현 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 프로젝트와 집합 연산의 구현 (d) sort the tuples in R and S using the same unique sort attributes; set i← 1, j←1; while (i<=n) and (j<=m) do { if R(i) > S(j) then set j← j+1 elseif R(i) < S(j) then set i← i+1 else { output R(i) to T; /* R(i) = S(j), so we output the tuple */ set i←i+1, j← j+1 } [그림 18.3] n개의 투플을 가진 릴레이션 R과 m개의 투플을 가진 릴레이션 S에 대해 정렬을 이용하여 조인, 프로젝트, 합집합, 교집합, 차집합 연산들을 구현(cont.) (d) T ← R∩S 연산의 구현 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 프로젝트와 집합 연산의 구현 (e) sort the tuples in R and S using the same unique sort attributes; set i← 1, j←1; while (i<=n) and (j<=m) do { if R(i) > S(j) then set j← j+1 elseif R(i) < S(j) then { output R(i) to T; /* R(i) has no matching S(j), so output R(i) */ set i←i+1 } else set i← i+1, j←j+1 if (i<=n) then add tuples R(i) to R(n) to T; [그림 18.3] n개의 투플을 가진 릴레이션 R과 m개의 투플을 가진 릴레이션 S에 대해 정렬을 이용하여 조인, 프로젝트, 합집합, 교집합, 차집합 연산들을 구현(cont.) (e) T ← R - S 연산의 구현 2001-01 Fundamentals of Database Systems

집단 연산(Aggregate Operation)의 구현 집단 연산자 : MIN, MAX, COUNT, AVERAGE, SUM SELECT MAX(SALARY) FROM EMPLOYEE; SALARY에 대하여 인덱스가 있는 경우 그 인덱스를 이용하여 집단 연산의 결과를 구할 수 있다. SALARY에 대해 인덱스가 없는 경우 화일 스캔을 하여야 한다. SELECT DNO, AVG(SALARY) FROM EMPLOYEE GROUP BY DNO; 동일 그룹에 대하여 해슁을 이용하여 분할하는 방법 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 외부 조인(Outer Join)의 구현 조인 알고리즘을 수정하여 구현 : 조인에 참여하지 못하는 투플의 해당 칼럼 값들을 NULL 값으로 채움. 외부 조인을 위하여 조인 알고리즘의 수정이 아닌 별개의 알고리즘을 개발할 수도 있으나 이의 효율성은 낮음. Outer join (1) left outer join, (2) right outer join, (3) full outer join SELECT lname, fname, dname FROM (employee LEFT OUTER JOIN department ON dno = dnumber); E.g., employee department result lname fname dno dnumber dname lname fname dname =========== =========== ============ <kim, a, 1> < 1, cs> <kim, a, cs> <park, b, 2> < 2, ce> <park, b, ce> <lee, c, NULL> < 3, ee> <lee, c, NULL> Note: every tuple in the left must appear in the result. Algorithm extend the join algorithms. E.g., use the left relation as the outer loop or single-loop. If there are matching tuples in the other relation, the joined tuples are produced and saved in the result. However, if no matching tuple is found, the tuple is still included in the result but is padded with null value(s). The sort-merge and hash-join algorithms can also be extended to compute outer joins. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems OUTER UNION Union of tuples from two relations if the relations are not union compatible. Tuples from the component relations with the same key are represented only once in the result and have values for all attributes in the result. select result.Name, result.SSN, result.Dept, result.Advisor, result.Rank from (select Name, SSN, Dept, Advisor, NULL as Rank from STUDENT union all select Name, SSN, Dept, NULL as Advisor, Rank from FACULTY) as result E.g., STUDENT FACULTY result (Name, SSN, Dept, Advisor) (Name, SSN, Dept, Rank) (Name, SSN, Dept, Advisor, Rank) ==================== ==================== ========================== <kim, 333, a, choi> < choi, 777, c, 1> <kim, 333, a, choi, NULL> <park, 444, b, lee> < hwang, 999, a, 2> <park, 444, b, lce, NULL> <lee, 555, c, NULL> <peter, 666, b, 3> <lee, 555, c, NULL, NULL> <choi, 777, c, NULL, 1> <hwang, 999, a, NULL, 2> <peter, 666, b, NULL, 3> Notice that OUTER UNION is equivalent to a FULL OUTER JOIN if the join attributes are all the common attributes of the two relations. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 파이프라이닝을 사용한 연산의 결합 Materialization(구체화)과 Pipelining(파이프라이닝) 임시 결과 화일들의 수를 줄이는 것이 목적이다. 하나의 연산의 결과를 임시 화일에 저장하는 대신에 다음 연산의 입력으로 사용하는 것이 파이프라이닝의 기본 아이디어이다. 2001-01 Fundamentals of Database Systems

18.3 경험(Heuristics)을 사용한 질의 최적화 성능향상을 위한 경험적 규칙들 예: 조인을 수행하기 전에 실렉트 또는 프로젝트 연산을 수행한다. Selection : Late Selection (늦은 실랙션) v.s. Early Selection (조기 실렉션) Projection : Late Projection (늦은 프로젝션) v.s. Early Projection (조기 프로젝션) 경험적 규칙들의 적용대상 질의에 대하여 파서가 생성한 초기 내부 표현 : 질의 트리 또는 질의 그래프 질의 트리 : 관계대수 혹은 확장된 관계대수식을 표현하는데 사용 질의그래프: 관계해석식을 표현하는데 사용 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 질의 트리와 질의 그래프의 표시법 질의트리 (Query Tree): 관계대수식에 대응되는 트리 구조 질의트리의 구조 리프노드 : 질의의 입력 릴레이션들 내부노드 : 관계대수 연산들 질의트리의 실행 : 질의를 실행하기 위한 연산들의 특정 순서를 나타낸다. 내부노드의 연산에 대해 피연산자가 사용가능할 때마다 그 연산을 실행하고, 그 연산의 결과로 생성된 릴레이션으로 그 내부노드를 대치한다. 그 실행은 루트노드가 실행되어 질의에 대한 결과 릴레이션을 생성한 뒤 마친다. 2001-01 Fundamentals of Database Systems

질의 트리와 질의 그래프의 표시법 (cont.) 질의그래프 (Query Graph): 관계해석식을 표현하는 자료구조 질의그래프의 구조 릴레이션 노드 : 질의의 입력 릴레이션들  한겹 원으로 표시 상수 노드 : 질의의 상수값들  이중 원으로 표시 그래프 에지 : 실렉션과 조인 조건들 각 릴레이션으로 부터 검색할 애트리뷰트들 : 꺽쇠 기호 안에 표시 질의그래프의 실행 질의를 실행하기 위한 연산들의 특정 순서를 나타내지 않는다. 각 질의에 대응되는 질의그래프는 유일하다. 2001-01 Fundamentals of Database Systems

질의 트리와 질의 그래프의 표시법(cont.) 관계대수 표현 ∏ PNUMBER, DNUM,LNAME,ADDRESS,BDATE(((σ PLOCATION=‘Stafford’(PROJECT)) DNUM=DNUMBER(DEPARTMENT)) MGRSSN = SSN(EMPLOYEE)) SQL 표현 SELECT p.PNUMBER, d.DNUM, e.LNAME, e.ADDRESS, e.BDATE FROM PROJECT p, DEPARTMENT d, EMPLOYEE e WHERE p.DNUM=d.DNUMBER AND d.MGRSSN=e.SSN AND p.PLOCATION=‘Stafford’ 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems ∏ PNUMBER, DNUM,LNAME,ADDRESS,BDATE MGRSSN = SSN DNUM=DNUMBER EMPLOYEE σPLOCATION=‘Stafford’ DEPARTMENT PROJECT [그림 18.3] 질의 Q2에 대한 두 개의 질의트리 (a) Q2의 관계대수식에 대응되는 질의 트리 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems ∏ PNUMBER, DNUM,LNAME,ADDRESS,BDATE σDNUM=DNUMBER AND MGRSSN=SSN AND PLOCATION=‘Stafford’ X X EMPLOYEE PROJECT DEPARTMENT [그림 18.4] 질의 Q2에 대한 두 개의 질의트리 (cont.) (b) Q2의 SQL 질의에 대한 초기 (Initial; 규준:Canonical) 질의 트리 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems (c) [P.PNUMBER,P.DNUM] [E.LNAME,E.ADDRESS,E.BDATE] P.DNUM=D.NUMBER D.MGRSSN=E.SSN P D E P.PLOCATION=‘Stafford’ ‘Stafford’ [그림 18.4] (c) Q2의 SQL 질의에 대한 질의 그래프 2001-01 Fundamentals of Database Systems

질의트리의 경험적 최적화(Heuristic Optimization) 질의 Q: SELECT e.LNAME FROM EMPLOYEE e, WORKS_ON w, PROJECT p WHERE p.PNAME = ‘Aquarius’ AND p.PNUMBER = w.PNO AND w.ESSN = e.SSN AND e.BDATE > ‘1957-12-31’; 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 질의트리의 경험적 최적화 (a) ∏ LNAME σPNAME=‘Aquarius’ AND PNUMBER=PNO AND ESSN=SSN AND BDATE>’1957-12-31’ X X PROJECT EMPLOYEE WORKS_ON [그림 18.5] 경험적 최적화 과정에서 질의 트리를 변경하는 과정 (a) SQL 질의 Q에 대한 초기 (규준) 질의트리. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 질의트리의 경험적 최적화 ∏ LNAME (b) σPNUMBER=PNO X σESSN=SSN σPNAME=‘Aquarius’ X PROJECT σBDATE>’1957-12-31’ WORKS_ON EMPLOYEE [그림 18.5] 경험적 최적화 과정에서 질의 트리를 변경하는 과정 (b) 실렉트 연산들을 질의트리의 아래로 이동. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 질의트리의 경험적 최적화 ∏ LNAME (c) σESSN=SSN X σPNUMBER=PNO σBDATE>’1957-12-31’ X EMPLOYEE σPNAME=‘Aquarius’ WORKS_ON PROJECT [그림 18.5] 경험적 최적화 과정에서 질의 트리를 변경하는 과정 (c) 보다 제한적인 실렉트 연산을 먼저 적용. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 질의트리의 경험적 최적화 (d) ∏ LNAME ESSN = SSN σBDATE>’1957-12-31’ PNUMBER=PNO EMPLOYEE σPNAME=‘Aquarius’ WORKS_ON PROJECT [그림 18.5] 경험적 최적화 과정에서 질의 트리를 변경하는 과정 (d) 카티션 프로덕트와 실렉트를 조인 연산으로 대체. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 질의트리의 경험적 최적화 ∏ LNAME (e) ESSN = SSN ∏ ESSN ∏ SSN,LNAME σBDATE>’1957-12-31’ PNUMBER=PNO ∏ ESSN,PNO ∏ PNUMBER EMPLOYEE σPNAME=‘Aquarius’ WORKS_ON PROJECT [그림 18.5] 경험적 최적화 과정에서 질의 트리를 변경하는 과정 (e) 프로젝트 연산들을 질의트리의 아래로 이동. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 질의트리의 경험적 최적화 관계대수 연산들을 위한 일반적인 변환 규칙 규칙 1. 연속적인 σ σc1 AND c2 AND...AND cn(R) ≡ σc1(σc2(...(σcn(R))...)) 규칙 2. σ의 교환법칙 σc1(σc2(R)) ≡ σc2(σc1(R)) 규칙 3. 연속적인 ∏ ∏List1(∏List2(...(∏Listn(R))...)) ≡ ∏List1(R) 규칙 4. σ와 ∏의 교환 ∏A1,A2,...,An(σc(R)) ≡ σc(∏A1,A2,...,An(R)) 규칙 5. (혹은 X)의 교환법칙 R cS ≡ S cR 규칙 6. σ와 (혹은 X)의 교환 σc(R S) ≡ (σc(R)) S 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 18.3.2 경험을 사용한 질의 최적화(cont.) 규칙 7. ∏와 (혹은 X)의 교환 ∏L(R cS) ≡ (∏A1,...,An(R)) c(∏B1,...,Bm(S)) 규칙 8. 집합연산의 교환법칙 ∪와 ∩사이에는 교환법칙이 성립한다. 그러나 연산에는 교환법칙이 성립하지 않는다. 규칙 9. , X, ∪, ∩의 결합법칙 (R Θ S) Θ T ≡ R Θ (S Θ T) 규칙 10. σ와 집합연산의 교환 ∪, ∩, 와 σ 는 교환가능하다. 규칙 11. ∏와 ∪의 교환 ∏L(R U S) ≡ (∏L(R)) U (∏L(S)) 규칙 12. 일련의 (σ, ×) 연산을 로 변환 σc(R X S ) ≡ (R c S) 그 밖의 다른 변환들 - 드모르강의 법칙 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 경험을 사용한 질의 최적화(cont.) 경험적 대수 최적화 알고리즘의 개요 1. 논리곱 조건을 가진 실렉트 연산을 개개의 실렉트 연산들의 연속으로 분리 (규칙 1 사용) 2. 실렉트 연산을 질의트리의 가장 아래로 보낸다. (규칙 2, 4, 6, 10 사용) 3. 가장 제한적인 실렉트 연산들을 가진 리프노드 릴레이션들이 가장 먼저 실행되게 재배치한다. (규칙 5, 9 사용) 4. 카티션 프로덕트 연산을 후속 실렉트 연산과 결합하여 조인연산을 만든다. 5. 프로젝트 연산의 애트리뷰트들의 리스트를 나눠서 가능한 한 트리의 아래로 보낸다. (규칙 3, 4, 7, 11 사용) 6. 단일 알고리즘에 의해 독립적으로 실행될 수 있는 연산들의 그룹을 나타내는 서브트리들을 식별한다. 2001-01 Fundamentals of Database Systems

질의트리를 질의 실행계획(Execution Plan)으로 변경 ∏ FNAME,LNAME,ADDRESS DNUMBER=DNO σDNAME=‘Research’ EMPLOYEE DEPARTMENT [그림 18.6] 질의 Q1에 대한 질의트리 최적화기의 실행계획: (1) 실렉트 연산 : 인덱스 스캔, (2) EMPLOYEE : 테이블 스캔, (3) 조인 연산 : 중첩 루프 조인, (4) 프로젝트 : 조인 결과를 스캔 (5) 질의 실행방법 : 구체화 평가(Materialized Evaluation)방법 / 파이프라인 평가(Pipelined Evaluation)방법 2001-01 Fundamentals of Database Systems

18.4 질의 최적화에서 선택도(Selectivity)와 비용추정치(Cost Estimates) 사용 18.4.1 질의 실행을 위한 비용의 구성요소 18.4.2 비용함수에서 사용되는 카탈로그 정보 18.4.3 실렉트에 대한 비용함수의 예 18.4.4 조인에 대한 비용함수의 예 18.4.5 다중 릴레이션 질의와 조인 순서화 18.4.6 비용기반 질의 최적화 예제 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 18.4.1 질의 실행을 위한 비용의 구성요소 보조 기억장치의 접근 비용 디스크의 데이타 블록을 찾고, 읽고, 쓰는 비용 정렬, 해싱, 기본 인덱스, 보조 인덱스등에 따라 달라진다. 저장 비용 질의의 실행 전략에 따라 생성되는 중간 화일들의 저장 비용 계산 비용 질의 실행 단계에서 연산 수행 비용 레코드 탐색, 정렬, 조인을 위한 합병, 필드값 계산 메모리 사용 비용 질의를 실행하는 동안 필요한 메모리 버퍼의 수 통신 비용 질의와 질의 결과의 전송 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 18.4.2 비용 함수에서 사용되는 카탈로그 정보 r(record) : 레코드(투플)의 수 b(blocks) : 블록의 수 bfr(blocking factor) : 화일의 블록킹 인수 x : 다단계 인덱스(기본 인덱스, 보조 인덱스, 또는 클러스터링 인덱스)의 단계수 b11 : 첫 번째 단계의 인덱스 블록의 수 d : 인덱싱 애트리뷰트에 나타나는 상이한 값들의 수 한 애트리뷰트의 s(selection cardinality) 추정 s : 한 애트리뷰트에 대한 동등조건을 만족시키는 레코드의 평균 갯수 키 애트리뷰트에 대해, s = 1 키가 아닌 애트리뷰트에 대해, s = r/d 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 18.4.3 실렉트에 대한 비용함수의 예 S1. 선형탐색 CS1a = b  조건을 만족하는 레코드가 없는 경우 CS1b = b/2  조건을 만족하는 레코드가 있는 경우 S2. 이진탐색 CS2 = log2b + s/bfr -1 키 애트리뷰트에 대한 동등조건인 경우 : log2b S3. 기본 인덱스(S3a) 또는 해시 키(S3b)를 사용하여 단일 레코드를 검색 CS3a = x + 1  기본 인덱스 CS3b = 1  해시 S4. 순서화된 인덱스를 사용하여 여러 개의 레코드들을 검색 CS4 = x + b/2 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 18.4.3 실렉트에 대한 비용함수의 예 (cont.) S5. 클러스터링 인덱스를 사용하여 여러 개의 레코드들을 검색 CS5 = x + s/bfr S6. 보조(B+-트리) 인덱스 사용 CS6a = x + s  동등 비교의 경우 CS6b = x + b11/2 + r/2  범위 질의의 경우 S7. 논리곱 선택 S1을 사용하거나 S2부터 S6까지 중 한 가지 방법을 사용한다. S8. 복합 인덱스를 사용하는 논리곱 선택 인덱스의 유형에 따라 S3a, S5, 또는 S6a와 같다. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 18.4.4 조인에 대한 비용함수의 예 조인 선택도 (join selectivity, js) : 카티션 프로덕트 화일의 크기(투플 수)에 대한 조인 화일의 크기의 비율 js = |R c S| / |R × S| = |R c S| / (|R|*|S|) J1. 중첩 루프 방법 CJ1 = bR + (bR * bS) + ((js * |R| * |S|)/bfrRS) J2. 부합되는 레코드들을 검색하기 위한 접근구조 사용 CJ2a = bR + (|R| * (xB + sB)) + ((js * |R| * |S|)/bfrRS) CJ2b = bR + (|R| * (xB + sB//bfrB)) + ((js * |R| * |S|)/bfrRS) CJ2c = bR + (|R| * (xB + 1)) + (js * |R| * |S|)/bfrRS) CJ2d = bR + (|R| * h) + ((js * |R| * |S|)/bfrRS) J3. 정렬-합병 조인 CJ3a = bR + bS + ((js * |R| * |S|)/bfrRS) CJ3b = k * ((bR*log2bR) + (bS*log2bS)) + bR + bS + ((js * |R| * |S|)/bfrRS) 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 18.4.5 다중 릴레이션 질의와 조인 순서화 R1 R4 R2 R3 R1 R2 R4 R3 [그림 18.7] 두개의 좌방향 깊이(left-deep) (조인) 질의 트리 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 18.5 ORACLE에서 질의 최적화의 개요 규칙기반 질의 최적화 15개의 서열화된 접근 경로를 유지 전체 테이블 스캔(가장 비효율적인) … ROWID를 사용한 테이블 접근(가장 효율적임) 낮은 서열일수록 보다 효율적인 방식을 의미한다. 비용기반 질의 최적화 여러 접근 경로들과 연산자 알고리즘들을 조사하고 가장 작은 추정 비용을 가지는 실행 계획을 선택한다. I/O, CPU 시간, 필요한 주기억장치 등 자원의 사용 추정치를 기초로 비용을 계산한다 2001-01 Fundamentals of Database Systems

12.4 의미적 질의 최적화 (Semantic Query Optimization) 데이타베이스 스키마에 명시된 제약조건 사용 예제 SELECT E.LNAME, M.LNAME FROM EMPLOYEE E M WHERE E.SUPERSSN = M.SSN AND E.SALARY > M.SALARY 질의의 의미 : 상사보다 더 많은 봉급을 받는 사원의 이름 제약조건: 어떤 사원도 자신의 상사보다 더 많은 급여를 받을 수 없다. 결론 : 위 질의를 수행할 필요가 없다. 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 통계 자료의 변경 Update Statistics 예제 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems 바다-II에서 최적화 관련 데이타 Left-Skewed Execution Plan Tree Early Projection의 효과 Pipelining의 효과 Update Statistics의 효과 통신 버퍼의 크기 효과 Malloc과 Free의 영향 Memory Leakage의 방어 2001-01 Fundamentals of Database Systems

Fundamentals of Database Systems Oracle 9i에서 경험치 REF와 JOIN 연산의 성능 비교 VARRAY와 JOIN의 성능 비교 2001-01 Fundamentals of Database Systems