데이터베이스 질의 최적화
IT 위키
- Query Optimization
- 같은 결과를 내는 여러 실행 방법 가운데 비용이 가장 적은 것을 고르는 과정
SQL 은 선언적이어서 '무엇을' 구할지만 적는다. '어떻게' 구할지는 DBMS 가 정하며 그 판단을 맡는 것이 질의 최적화기다.
- 파싱 : SQL 문법과 권한을 검사해 파스 트리를 만든다.
- 변환 : 파스 트리를 관계 대수식으로 바꾼다.
- 최적화 : 관계 대수식에 대응하는 질의 트리를 만들고 더 싼 형태로 바꾼다.
- 코드 생성·실행 : 실행 계획을 만들어 수행한다.
- 질의 트리(query tree) : 관계 대수식을 트리로 나타낸 것. 잎은 릴레이션, 내부 노드는 연산이며 연산 순서를 담는다
- 질의 그래프(query graph) : 릴레이션과 조인 조건을 노드·간선으로 나타낸 것. 연산 순서를 담지 않는다
- 동등한 질의를 서로 다른 여러 개의 질의 트리로 나타낼 수 있다. 그중 싼 것을 고르는 것이 최적화다
- 반면 질의 그래프는 하나의 질의에 대해 하나로 정해진다. 순서 정보가 없기 때문이다
휴리스틱 규칙으로 질의 트리를 바꾼다. 핵심은 중간 결과를 최대한 작게 만드는 것이다.
- 실렉트(σ)를 가능한 한 잎 쪽으로 내린다. 행을 먼저 줄인다.
- 프로젝트(π)도 가능한 한 아래로 내린다. 열을 먼저 줄인다.
- 실렉트 조건 c 의 애트리뷰트가 프로젝트 리스트에 모두 들어 있으면 두 연산의 순서를 바꿀 수 있다.
- 카티전 곱과 실렉트가 이어지면 조인으로 묶는다.
- 선택도가 낮은(결과가 작은) 연산을 먼저 수행한다.
- 카탈로그의 통계 정보(튜플 수, 블록 수, 인덱스 유무, 값의 분포)로 실행 계획마다 비용을 추정해 비교한다.
- 비용은 주로 디스크 접근 횟수로 잰다. 계산·메모리·통신 비용도 고려한다.
- 조인 방법(중첩 루프, 정렬 합병, 해시)과 접근 경로(전체 스캔, 인덱스 스캔)를 조합해 견준다.
