Computer Science/Database Systems

[Database Systems] Query Processing and Optimization

__K.Jun__ 2025. 2. 15. 18:32

Query Processing

High-Level 쿼리 -> 스캔, 파싱, 유효성 검사 후, 쿼리의 중간 형태 -> 쿼리 최적화 후 실행 계획 -> 쿼리 코드 생성기가 쿼리 코드 생성 -> runtime DB processor가 쿼리의 결과 도출

 

Translating SQL Queries into Relational Algebra

SELECT-FROM-WHERE(-GROUP BY-HAVING)으로 이루어진 Basic Unit이 Algebraic operator로 변환된 후 최적화 된다.

 

External Sorting

DB환경상에서 Disk에서 Main Memory에 한번에 로드할 수 없는 대용량 데이터를 정렬하기 위한 알고리즘으로 보통 JOIN, ORDER BY, 또는 DISTINCT를 수행하기 위해 사용한다.

  • Sort-Merge strategy:
    • Main file을 Small subfiles(Runs) 단위로 정렬
    • 정렬된 Run들을 Merge하여 전체 정렬 완료

 

Algorithms for SELECT Operations

1. Linear search (brute force):

  • 모든 레코드를 순차적으로 검색
  • 가장 느리지만 인덱스가 없는 경우 사용 가능

2. Binary search:

  • 정렬된 데이터에서 사용
  • 키 값에 대해 빠른 검색이 가능

3. Using a primary index or hash key to retrieve a single record:

  • 인덱스를 사용하여 빠르게 검색

4. Using a primary index to retrieve multiple records:

  • 인덱스와 비교 조건 (>, >=, <, <=)을 사용하여 다중 레코드를 빠르게 검색

5. Using a clustering index to retrieve multiple records:

  • 동일한 키 값을 갖는 여러 레코드를 검색할 때 유용

6. Conjunctive selection:

  • 여러 조건을 조합하여 검색
  • 인덱스가 있는 조건을 우선적으로 처리 하여 레코드를 가져오고, 인덱스가 없는 나머지 조건을 처리 해야 검색 속도가 빠르다.

7. Conjunctive selection by intersection of record pointers:

  • 각 조건에 Record pointer가 존재할 때, 두 Record pointer의 교집합을 구하는 방식

 

Algorithms for JOIN Operations

1. Nested-Loop Join (brute force):

  • 모든 조합을 Join condition과 일치하는지 검사

2. Single-Loop Join:

  • 한 쪽에 인덱스가 있을 경우, 없는 쪽에서 하나 선택 후, 이와 동일한 것을 인덱스 서치로 찾기

3. Sort-Merge Join:

  • 양쪽 데이터를 Join Attribute에 대해 정렬하면 Join condition과 일치하는 조합을 금방 찾을 수 있다.

4. Hash Join:

  • 해시함수 결과가 같은 것들 끼리 bucket에 묶어놓으면, Join condition과 일치하는 조합을 금방 찾을 수 있다.

 

Algorithms for PROJECT Operations

  • 키가 포함된 경우: 중복 제거 필요 없음
  • 키가 없는 경우: Sorting 또는 Hashing을 사용하여 중복을 제거

Algorithms for SET Operations

  • UNION: 두 Relation을 Sorting후, merge를 하는데, 양 쪽 Tuple이 동일하면 한 쪽에서 하나만 추출, 다르면 양쪽에서 모추 추출
  • INTERSECTION: 두 Relation을 Sorting후, merge를 하는데, 양 쪽 Tuple이 동일한 경우에만 한 쪽에서 하나 추출
  • SET DIFFERENCE R-S: 두 Relation을 Sorting후, merge를 하는데, R에만 있는 Tuple만 추출

 

Implementing Aggregate Operations

  • 사용 연산: MIN, MAX, SUM, COUNT, AVG
  • 구현 방법
    • 테이블 전체 검색
    • 인덱스 활용
  • MIN, MAX
    • 레코드를 정렬한 후, 양쪽 맨 끝 값이 MIN 또는 MAX이다. 이것을 인덱스로 찾을 수있다.
  • SUM, COUNT, AVG
    • Dense index (각 레코드가 하나의 Index 엔트리를 갖는것)의 경우 모든 레코드에 대해서 SUM, COUNT를 직접 계산할 수 있고 이를 통해 AVG까지 구할 수 있다.
    • Non-dense index (일부 레코드에만 Index 엔트리가 존재 / 블럭마다 Index 엔트리가 존재)의 경우, 각 블럭에서 SUM, COUNT를 구해서 모두 더한 후, 모든 레코드의 SUM, COUNT를 알 수 있고 이를 통해 AVG까지 구할 수 있다.
    • GROUP BY: Grouping attribute에 대해 sorting 또는 hashing을 수행하여 분할한다. 그러고 나서 각 그룹의 tuple들에 대해linear하게 aggregation을 수행한다.

 

Using Heuristics in Query Optimization

경험적 규칙을 적용하여 쿼리를 빠르게 최적화 하는 방식

1. High-level 쿼리를 파싱하여 relation algebra 형태로 만든다.

2. 1에서 만든 형태를 최적화 하기 위해 heuristic rule을 적용한다.

3. 연산 집합을 실행하기 위해 쿼리 실행 계획이 생성된다.

 

Heuristic의 주 방식은 SELECT 및 PROJECT 연산을 우선적으로 수행하여 중간 결과 크기를 축소하는 것이다. JOIN은 중간 결과의 사이즈를 증가시키기 때문에, 가장 작은 테이블 부터 JOIN하는 것이 좋다.

(a) -> (b)

SELECT를 먼저 사용하여 테이블의 사이즈를 먼저 줄인 후, CARTESIAN 연산을 한다.

(b) -> (c)

CARTESIAN -> SELECT의 결과는 테이블의 크기를 키우기 때문에, 작은 테이블을 먼저 CARTESIAN -> SELECT한다.

(c) -> (d)

CARTESIAN -> SELECT는 JOIN과 같기 때문에, JOIN으로 바꾼다.

(d) -> (e)

트리의 상위 레벨에서 사용할 것만 PROJECTION하여 테이블의 크기를 줄인다.

 

General Transformation Rules

1. 좌변 처럼 조건을 만족 하는 것을 한번에 찾는 것 보다, 우변처럼 각각 하나씩 처리하여 테이블을 줄여가면서 수행하는게 더 빠르다.

2. C1에 인덱스가 있다면 먼저 빠르게 테이블을 줄일 수 있다.

3. PROJECTION을 여러 번 해도, 결국 마지막으로 수행 한 PROJECTION만 남게된다.

4. 우변 처럼 먼저 PROJECTION으로 테이블을 줄여놓고 SELECTION하는 게 더 빠르다. 단, C에 A1, A2, ... , An이 존재해야 한다.

5. 교환법칙이 성립한다. JOIN의 경우에 한 쪽에 인덱스가 있을 경우, 없는 쪽에서 하나 선택 후, 이와 동일한 것을 인덱스 서치로 찾는 것이 성능 상 더 빠르다. CARTESIAN 연산의 경우에는 R이 메인 메모리에 한번에 올라갈 수 없을 정도로 크고 S는 메인 메모리에 한번에 올라갈 수 있을 경우, S의 한 Tuple을 기준으로 하여 R에 있는 Tuple과의 조합을 구하면 disk access가 많이 발생하지만, 반대로 R의 한 Tuple을 기준으로 S에 있는 Tuple과의 조합을 구하면 disk access가 상대적으로 조금 발생한다.

6. SELECTION으로 먼저 줄여 놓고, JOIN

7. PROJECTION으로 먼저 줄여 놓고, JOIN

8. 교환법칙

9. 결합법칙

10. SELECTION으로 먼저 줄여 놓고, 연산 가능

- PROJECTION으로 먼저 줄여 놓고, 연산 가능

- CARTESIAN -> SELECT는 JOIN과 같기 때문에, JOIN으로 바꾼다.

Using Selectivity and Cost Estimates in Query Optimization

여러가지 Plan을 세운 후, 가장 Cost가 낮은 방식을 선택하는 방식이다. 대표적으로 Cost로 여겨지는 것은 다음과 같다.

1. 디스크 접근 비용

2. 디스크 저장 비용

3. 메인 메모리에 올라온 것을 계산하는 비용

4. 메모리 사용 비용

5. 분산 환경에서 머신 간 커뮤니케이션 비용

728x90