[데이터베이스 설계] 쿼리 처리(Query Processing) - 비용 측정부터 선택 연산(A1-A3)

쿼리 처리의 3가지 기본 단계

- 쿼리 처리는 크게 구문 분석 및 변환, 최적화, 그리고 평가의 세 단계로 이루어짐

 

1. 구문 분석 및 변환 (Parsing and Translation)
   • 사용자가 작성한 SQL 쿼리의 문법이 맞는지 확인하고, 관계들이 유효한지 검증
   • 사람이 사용하기 좋은 비절차적 언어인 SQL을 시스템이 이해하기 쉬운 내부 표현(주로 절차적인 확장 관계 대수)으로 변환
2. 최적화 (Optimization)
   • 변환된 관계 대수 표현은 여러 가지 동등한 표현으로 바뀔 수 있음
   • 예를 들어, salary < 75000인 교수의 salary를 찾는 것은 두 가지 동등한 표현이 가능
     • σ_salary < 75000(Π_salary(instructor))
     • Π_salary(σ_salary < 75000(instructor))
   • 쿼리 최적화 프로그램(Optimizer)은 이러한 여러 동등한 실행 계획(Evaluation Plan) 중에서 가장 비용이 적게 드는 계획을 선택
   • 비용은 데이터베이스 카탈로그에 저장된 통계 정보(예: 릴레이션의 튜플 수, 튜플의 크기 등)를 사용하여 추정
   • 최적화 단계가 끝나면, 구체적인 실행 전략이 담긴 '실행 계획(Evaluation Plan)'이 생성
   • "salary < 75000" 조건을 처리할 때 특정 인덱스를 사용하라는 식의 상세한 지침이 포함될 수 있음
3. 평가 (Evaluation)
   • 최적화 프로그램을 통해 만들어진 실행 계획을 받아 그대로 실행하고, 그 결과를 사용자에게 반환

---

쿼리 비용은 어떻게 측정할까?

- 쿼리 최적화에서 '비용'은 곧 실행 시간을 의미

- 여기에는 디스크 접근, CPU 사용, 네트워크 통신 등 여러 요소가 포함

- 이 중에서도 디스크 접근(disk access)이 가장 지배적인 비용이며 예측하기도 비교적 쉬움

- 디스크 접근 비용은 주로 다음 두 가지로 측정

• 탐색 횟수 (Number of seeks): 디스크 헤드가 원하는 트랙으로 이동하는 횟수
• 블록 전송 횟수 (Number of block transfers): 디스크에서 메모리로 데이터를 읽거나, 메모리에서 디스크로 데이터를 쓰는 블록의 수

이를 수식으로 표현하면 다음과 같음

• b: 전송된 블록의 수
• t_T: 블록 하나를 전송하는 데 걸리는 시간
• S: 탐색(seek) 횟수
• t_S: 한 번 탐색하는 데 걸리는 시간

계산의 편의를 위해 CPU나 네트워크 비용은 무시하고, 디스크 접근 비용에 초점을 맞춤

---

선택(Selection) 연산 알고리즘과 비용( A1 ~ A6 )

- 선택(σ) 연산은 특정 조건을 만족하는 튜플을 찾는 가장 기본적인 연산

- 이 연산을 수행하는 몇 가지 알고리즘과 각각의 비용을 확인

 

A1: 선형 탐색 (Linear Search)

- 가장 간단한 방법으로, 파일의 모든 블록을 순서대로 읽어서 각 레코드가 조건을 만족하는지 검사하는 방식

- 인덱스의 존재 여부나 데이터 정렬 상태와 관계없이 항상 적용할 수 있지만, 다른 알고리즘에 비해 느릴 수 있음

• 비용: b_r개의 블록 전송과 1번의 탐색이 필요(b_r은 릴레이션 r이 차지하는 블록의 수).
  • Cost = t_S + b_r * t_T
• 만약 선택 조건이 기본 키(Key)에 대한 것이라면, 레코드를 찾는 즉시 멈출 수 있으므로 평균적으로 절반만 탐색
  • 평균 비용:
    • Cost = t_S + (b_r / 2) * t_T

인덱스를 이용한 선택 (Index Scan)

- 인덱스를 사용하면 파일 전체를 읽지 않고 필요한 데이터에 더 빠르게 접근할 수 있음

- 인덱스는 크게 기본 인덱스(Primary Index) 와 보조 인덱스 (Secondary Index) 로 나뉨

• 기본 인덱스 (Primary Index): 데이터 파일이 인덱스의 검색 키 순서에 따라 물리적으로 정렬되어 있는 인덱스
  
  • 밀집 인덱스 (Dense Index): 모든 검색 키 값에 대한 인덱스 레코드를 가짐
    
  • 희소 인덱스 (Sparse Index):
    - 일부 검색 키 값에 대해서만 인덱스 레코드를 가짐
    - 데이터가 검색 키에 대해 순차적으로 정렬된 경우에만 사용할 수 있음

Dense Index

• 보조 인덱스 (Secondary Index):
  - 데이터 파일이 물리적으로 정렬되어 있지 않은 인덱스
  - 보조 인덱스는 항상 밀집 인덱스여야 함.

---

B+-트리 인덱스

- 가장 널리 사용되는 인덱스 구조 중 하나

- 루트 노드에서 리프 노드까지 균형 잡힌 트리 형태를 유지하여 데이터 탐색 시간을 예측 가능하게 만듬

- 높이가 3인 B+트리의 경우 어떠한 경우에도 3번만에 Leaf 노드에 접근하고, 4번만에 데이터에 접근함

B+-트리를 이용한 선택 연산 비용

 

• A2 (기본 인덱스, 키에 대한 동등 조건): 고유한 레코드 하나를 찾는 경우
  
  • 비용: 인덱스 트리의 높이(h_i)만큼 탐색하고, 마지막으로 실제 데이터 블록을 한 번 더 접근
  • Cost = (h_i + 1) * (t_T + t_S)
• A3 (기본 인덱스, 키가 아닌 속성에 대한 동등 조건): 여러 레코드가 결과로 나올 수 있는 경우
  
  • 비용: 리프 노드까지 h_i번 접근한 후, 첫 데이터 블록을 찾아 순차적으로 읽음
  • 데이터가 물리적으로 정렬되어 있어 추가 탐색이 필요 없음
  • b: 조건을 만족하는 레코드들이 포함된 블록의 수
  • Cost = h_i * (t_T + t_S) + t_S + b * t_T