[ADV_db]Chap 4. Query-processing

---

# 질의 처리 순서

---

Parsing and Translation

• 들어온 질의문에서 문법적 오류가 없는지 확인하고, 관련 릴레이션들을 확인한다.
• DBMS내부에서 작동가능한 형태로 번역하고, relational algebra로 변환한다.
• View연산이 포함된 쿼리의 경우, View를 정의하는 모든 관계 대수 변환식으로 대체된다.

Optimizer

• 여러 relational algebra 중에서 가장 좋은 Execution plan을 고른다.
• 고르는 기준은 데이터베이스에 파일이 저장된 방식이나 인덱스의 유무에 따라 달라지는 Cost를 기준으로 가장 낮은 Cost를 가진 Execution plan을 선택한다.

Evaluation

• 연산 처리에 대한 주석이 달린 relational-algebra operation을 evaluation primitive(평가 기본 단위)라고 한다.
• 처리를 위한 기본 연산들의 일련 과정을 나타낸 걸 Query-execution plan 또는 Query-evaluation plan이라고 부른다.
• Evaluation Engine에서는 Query-execution plan을 가지고 실행한 후, 결과를 출력해준다.

---

# Query Cost 측정

---

• Time Cost에 영향을 주는 요소들
  • Disk access
  • CPU처리
  • 네트워크
• Cost를 측정하는 기준
  • Response Time
  • Resource Consumption
    • 여기서는 총 자원 소비를 기준으로 진행
    • 측정 시 마지막에 디스크로 flush 하는 과정은 포함하지 않고 진행
• Disk Cost
  • 여러 방법이 있지만, 아래의 기준을 이용 
    • Number of block transfers
      • t(T)
      • 이 때 Read와 Write속도는 같다고 가정한다.
    • Number of Seeks
      • t(S)
      • disk seek time과 rotational latency를 합쳐져 있다고 가정한다.
    • 따라서 b개의 Block Transfer과 S번의 Seek과정이 있다면 b * t(T) + S * t(S)
    • 만약 필요한 데이터가 이미 메모리에 있다면, Disk I/O는 없다.
     

---

# Selection Operation

---

Algorithm A1 Linear search

• 모든 경우에 사용할 수 있다.

• 만약 키 속성을 이용해 특정 속성을 찾는 경우라면, 평균적으로,

Index Scan

• B+tree로 이루어진 index를 활용한 탐색

Algorithm A2(clustering index, equality on key)

• index된 키에 대한 동등 비교

• h(i)는 트리의 높이를 나타낸다.

Algorithm A3(clustering index, equality on non-key)

• index된 키가 아닌 속성에 대한 동등 비교
• 여러개의 레코드를 얻게 되지만, 모두 연속적인 블록에 있을 것이다. 따라서, 첫 번째 블록을 찾은 후에 b개의 연속적인 블록을 보면 된다.

Algorithm A4(secondary index, equality on key/non-key)

• 키 속성에 대한 동등 비교인 경우, 하나의 레코드만 검색하면 된다

• 키가 아닌 속성에 대한 동등 비교인 경우, 여러 레코드가 결과로 나오는데 모두 다른 블록에 있을 수 있다.
  • n개의 레코드가 있다고 가정하면, 다음과 같다.
  • 이 경우는 사실 아주 비효율적이다.

Comparison(비교 연산)

Algorithm A5(clustering index, comparison)

• 이런 경우 첫 번째 튜플을 찾고 이후 연속으로 모두 읽으면 되기 때문에 A3와 똑같다.

Algorithm A6(secondary index, comparison)

• 이 경우 첫 번째 튜플을 찾고 이 후 연속적으로 포인터들이 가르키는 값을 읽으면 된다. 따라서, A4의 키가 아닌 속성에 대한 동등 비교와 똑같다.
• 선형 탐색하는게 더 효율적이다.

Conjunction(논리곱 연산)

Algorithm A7(하나의 인덱스를 사용한 논리곱 연산)

• 조건을 만족시키는 레코드를 알고리즘 A2~A6 중 가장 효율적인 것(Cost가 최소인 거)을 찾는다. n-1개의 조건을 만족시켜 메모리에 올린 후 n개의 레코드에 대해 검사한다.

Algorithm A8(여러(composite) 인덱스를 사용한 논리곱 연산)

• 논리곱 연산이 두 개 이상의 속성에 대한 동등 비교 조건으로 구성되고, 복합 인덱스가 있는 경우 결과를 얻어낼 수 있다.
• 인덱스의 종류에 따라 A2,A3,A4중 하나의 알고리즘을 선택해서 사용할 수 있다.

Algorithm A9(식별자나 포인터를 이용한 논리곱 연산)

• 레코드에 대한 포인터나 식별자가 있을 때 사용한다.
• 식별자나 포인터를 조건 별로 레코드를 구한다.
• 만약 몇 개의 조건에 해당하는 적절한 식별자나 포인터가 없는 경우, 다른 조건들로 가져온 레코드들을 가지고 확인하지 못했던 조건들을 검사하여 결과를 얻는다.

Disjunction(논리합 연산)

Algorithm A10(식별자나 포인터를 이용한 논리합 연산)

• 모든 조건들에 대해 가능한 인덱스가 있을 때만 가장 효율적이다.
  • 만약 하나의 조건이라도 인덱스로 접근하는 경로가 없는 경우는 선형 탐색한다.
  • 따라서, 하나라도 접근 경로가 없는 경우에는 가장 효울적인 방법은 선형 탐색이다.
• 모든 조건에 해당하는 인덱스를 사용해서 합집합 연산을 한다. 그 후 모든 레코드를 파일로부터 가져온다.

Negation(부정 연산)

• 동등 비교 연산이 있는 경우 선형 스캔을 한다.
• 만약 인덱스가 있다면, 조건에 대한 인덱스를 먼저 찾은 후에 그걸 제외한 인덱스를 가지고 레코드를 찾을 수 있다.
• 부정 연산에 해당하는 레코드가 많다면, 선형 탐색이 좋고, 그게 아니라면 인덱스를 활용하여 조건에 해당하는 인덱스를 찾는 게 좋다.