8. Query Processing & Optimization

Basic Steps in Query Processing

1. Parsing and translation

2. Optimization

3. Evaluation

 

Detailed Steps in Query Processing

---

0. SQL query : Example

select name, title
from teaches, course, instructor
where teaches.course_id = course.course_id and
	teaches.ID = instructor.ID and
        dept_name = 'Music' and year = '2009';

 

 

1. Parsing

Query를 Parse Tree로

 

2. Translation

Parse Trees를 Logical Query Execution Plan(관계대수)으로

 

 

3. Generate equivalent expressions

Equivalence rules를 활용해서 equivalent logical execution plans를 생성

 

4. Estimate result sizes of each l.q.e.p

• 각 logical execution plan에 대한 결과를 측정
• Statistical information about relations (DB에 있는 릴레이션에 대한 통계 정보 활용)
  • 튜플의 수
  • 튜플 사이즈
  • 각 속성의 고유 값 개수
  • 속성의 최대/최소 값 등
• SES: Statistically Estimated Size

 

5. Consider physical plans of each l.q.e.p

스캔 방법, 조인 방법과 순서 등 물리적 실행 계획 검토

 

6. Physical plans of each l.q.e.p with SESs

각 물리적 계획에 SES 반영

 

7. Estimate costs

물리적 계획의 비용을 측정 -> 비용이 가장 낮은 Best Plan을 찾음

 

---

Generate equivalent expressions

Transformation of Relational Expressions

• relation algebra expressions가 equivalent하다.
  • 모든 legal 데이터베이스 인스턴스에 대해서 같은 튜플 집합을 생성
• equivalent rule : 두 expression이 equivalent하다고 말할 수 있다.

 

Equivalent Rules

 

---

 

Estimate result sizes of each logical query execution plans

Selection Size Estimation

• σ_A=v (r)
  • n_r / V(A, r) : 전체 레코드 개수를 속성 A의 distinct values의 개수로 나눔
  • key 속성에 대한 동등 조건 조회는 size estimate = 1
  • 예시: 10,000개의 레코드가 있을 때 속성 A의 값이 100개 있다면 A = 50인 레코드는 10,000 / 100 = 100개일 것이라고 추정
• σ_A<=v (r) 
  • c를 조건에 해당하는 추정 튜플 개수라고 할 때
  • c = 0 if v < min(A, r)
  • c = n_r * (v - min(A, r) / (max(A,r) - min(A,r))
    • 예시: 10,000개의 레코드가 있을 때 age <= 30인 레코드 수
    • min(age, r) = 20, max(age, r) = 60이면 10,000 * (10 / 40) = 2500개라고 추정

---

Join Operation

예시 상황

• student ⋈ takes
  • n_student = 5,000
  • f_student = 50 -> b_student (블록 개수) = 5,000 / 50 = 100
    • f_r : Blocking factor - 하나의 블록에 들어가는 튜플 개수
  • n_takes = 10,000
  • f_takes = 25 -> b_takes = 10,000 / 25 = 400
  • V(ID, takes) = 2,500 -> 학생들이 평균적으로 4 courses 수강
  • V(ID, students) = 5,000 -> primary key

 

Estimation of the Size of Joins

• Cartesian product r x s : (n_r * n_s) tuples이고 각 튜플은 (l_r + l_s) bytes
• 만약 R ∩ S = ∅
  • r ⋈ s 는 r x s와 동일
• 만약 R ∩ S is a key for R
  • s의 튜플이 r로부터 최대 한 개의 튜플과 조인
  • s의 튜플 개수보다 많지 않음
• 만약 R ∩ S in S is a foreign key referencing R
  • S의 외래키가 R을 참조함
  • S의 튜플 수와 일치
  • takes의 ID가 student를 참조하는 외래키인 경우 결과는 10,000

 

• 만약 R ∩ S = {A} is not a key for R or S
  • n_r * n_s / V(A, r)
  • n_r * n_s / V(A, s)
  • 둘 중 더 적은 값으로 예상치로 사용

---

Estimate costs

Measures of Query Cost

• time cost에 영향을 미치는 요소들: disk accesses, CPU, network
• disk accesses가 큰 영향을 미치고 상대적으로 추정하기 쉬움
  • Number of seeks(=accesses)
  • Number of block read
  • Number of block written
  • write가 read보다 더 큰 비용이 든다. 
• 디스크에서의 block transfers의 개수와 seeks의 개수를 비용 추정에 사용
  • t_T : time to transfer one block
  • t_S : time for one seek
  • b개의 block을 transfer하고 S seeks를 수행: b * t_T + S * t_S
• CPU costs를 무시, disk에 writing output하는 비용을 포함하지 않음

 

Statistical Information for Cost Estimation

• b_r : r의 튜플을 가지고 있는 block의 수
  • n_r / f_r : 레코드의 수를 한 블록에 들어갈 수 있는 튜플 수로 나눈 값의 올림

---

Selection Operation

• File scan
  • linear search(=full table scan): 모든 파일 블록을 스캔하여 모든 레코드에 대해 조건에 해당하는지 검사
    • Cost estimate = b_r + 1 seek
    • key attribute에 해당하면 레코드 찾는 것을 멈춤
      • cost = (b_r / 2) + 1 seek
    • 선택 조건이나 레코드 순서, 인덱스와 상관없이 사용 가능
  • binary search: 파일이 정렬되어 있는 경우
• index scan
  • 인덱스를 사용하는 search algorithm 사용
  • 선택 조건이 인덱스의 search-key에 대한 것이어야 함
  • equality on key or nonkey
    • h_i : 인덱스 트리 높이
    • search-key is a candidate key
      • cost = (h_i + 1) * (t_T + t_S)
      • 인덱스 트리 탐색에  h_i * (t_T + t_S), 레코드가 있는 데이터 탐색에 t_T + t_S
    • search-key is not a candidate key
      • 인접한 블록에 저장된 경우: cost = h_i * (t_T + t_S) + b * t_T + t_S
      • 인접하지 않은 블록에 저장된 경우: cost = (h_i + n) * (t_T + t_S)

 

---

Joint Operation

• join 알고리즘
  • Nested-loop join
  • Block nested-loop join
  • Indexed nested-loop join
  • Merge-join
  • Hash-join
  • 비용 추정을 바탕으로 선택
• 예시 정보
  • student - 5000 records, 100 blocks
  • takes - 10000 records, 400 blocks

최악의 경우 버퍼에 한 블록씩만 가질 수 있다.

Nested-Loop Join

• r ⋈_θ s
  • r: outer relation, s: inner relation
  • 인덱스가 필요없고 join condition 상관없이 사용 가능
  • 두 테이블 간의 모든 튜플 쌍을 검사하므로 비용이 매우 비쌈

for each tuple t_r in r do begin
    for each tuple t_s in s do begin
        test pair (t_r, t_s) to see if they satisfy the join condition θ
        if they do, add t_r * t_s to the result
    end
end

 

• takes의 블록을 메인 메모리에 옮김: b_r transfer + b_r seeks
• takes의 모든 레코드에 대해서 student의 모든 블록을 가져와 비교: n_r * b_s transfer + n_r seeks
• 따라서, b_r + n_r * b_s transfers + b_r + n_r seeks

 

• student가 outer relation인 경우: (5000 * 400 + 100) transfers + (5000 + 100) seeks
• takes가 outer relation인 경우: (10000 * 100 + 400) transfers + (10000 + 400) seeks
• 작은 릴레이션을 모두 메모리에 올릴 수 있으면 비용이 줄어들게 됨
• 따라서 작은 릴레이션을 inner로

 

Block Nested-Loop Join

• inner relation의 모든 블록과 outer relation의 모든 블록을 쌍으로 만드는 것

for each block B_r of r do begin
    for each block B_s of s do begin
        for each tuple t_r in B_r do begin
            for each tuple t_s in B_s do begin
                Check if(t_r, t_s) satisfy the join condition
                if they do, add t_r * t_s to the result
            end
        end
    end
end

• Worst case: (b_r * b_s + b_r) block transfers + (2 * b_r) seeks
  • r의 블록을 올림: b_r transfers + b_r seeks
  • r의 블록마다 s의 블록을 올림: b_s * b_r transfers + b_r seeks
• Best case: (b_r + b_s) block transfers + 2 seeks
  • inner relation이 메모리 크기에 맞을 때
  • 각 릴레이션에 대해서 한 번씩 찾으면 됨

 

Indexed Nested-Loop Join

• index lookup을 file scan을 대신할 수 있는 경우
  • equi-join 이거나 natural join일 때
  • index가 inner realtion's join attribute일 때 -> 조인에 맞게 인덱스 설계 가능
• Outer relation r의 각 튜플에 대해 inner relation s에 있는 인덱스를 사용해 튜플을 찾아오는 방식
• Cost of the join: b_r * (t_T + t_S) + n_r * c
  • r의 블록을 읽음 : b_r * (t_T + t_S)
  • r 튜플마다 s 인덱스로 튜플을 찾음 : n_r * c
• 인덱스가 r과 s에서 모두 사용 가능하다면 튜플 수가 더 적은 릴레이션을 outer로 사용

---

Evaluation of Expressions

• 전체 표현식 트리를 평가하는 것의 대안
  • Materialization: 수행된 expression의 결과를 디스크에 저장해서 재사용
  • Pipelining: 연산이 수행 중이더라도 튜플을 부모 연산으로 넘김

 

Materialization

• Materialized evaluation: 연산 트리의 아래 단계부터 연산을 수행하고 결과를 저장한 후 이를 사용해서 다음 단계의 연산을 수행

 

Pipelining

• Pipelined evaluation: 여러 연산을 동시에 평가하며 한 연산의 결과를 바로 다음 연산으로 전달
  • 임시 릴레이션을 디스크에 저장할 필요가 없어 더 저렴
  • sort나 hash-join에서는 사용 불가능
  • 실행 방식
    1. demand driven: 상위 연산자가 데이터를 요청하면 하위 연산자가 생성
    2. producer driven: 하위 연산자가 데이터를 생성하면 즉시 상위 연산자로

 

 

Heuristic Optimization

• Cost-based optimizationd은 비용이 비쌈
• 선택의 수를 줄이고자 heuristics를 사용할 수 있음
• 대부분의 경우 실행을 향상시키는 규칙을 사용:
  • selection 먼저 수행
  • projection 먼저 수행
  • 다른 연산보다 제한적인 selection이나 join을 먼저 수행

 

Choice of Evaluation Plans

• 단순히 각 연산에서 가장 저렴한 알고리즘을 선택하다고 해도 결과적으로 비효율일 수 있다.
  • Merge Join vs Hash Join -> Merge가 더 비쌀 수 있지만 정렬된 결과를 반환하므로 이후 집계 비용 감소 가능
  • Nested Loop Join: 느릴 수 있지만 파이프라이닝 가능
• 쿼리 최적화를 위한 접근법
  • 모든 계획을 탐색하고 비용 기반 최고의 계획을 선택
  • 계획 선택을 위해 휴리스틱 사용