데이터베이스 질의 최적화

Query Optimization

같은 결과를 내는 여러 실행 방법 가운데 비용이 가장 적은 것을 고르는 과정

SQL 은 선언적이어서 '무엇을' 구할지만 적는다. '어떻게' 구할지는 DBMS 가 정하며 그 판단을 맡는 것이 질의 최적화기다.

질의 처리 단계

• 파싱 : SQL 문법과 권한을 검사해 파스 트리를 만든다.
• 변환 : 파스 트리를 관계 대수식으로 바꾼다.
• 최적화 : 관계 대수식에 대응하는 질의 트리를 만들고 더 싼 형태로 바꾼다.
• 코드 생성·실행 : 실행 계획을 만들어 수행한다.

질의의 표현

• 질의 트리(query tree) : 관계 대수식을 트리로 나타낸 것. 잎은 릴레이션, 내부 노드는 연산이며 연산 순서를 담는다
• 질의 그래프(query graph) : 릴레이션과 조인 조건을 노드·간선으로 나타낸 것. 연산 순서를 담지 않는다
• 동등한 질의를 서로 다른 여러 개의 질의 트리로 나타낼 수 있다. 그중 싼 것을 고르는 것이 최적화다
• 반면 질의 그래프는 하나의 질의에 대해 하나로 정해진다. 순서 정보가 없기 때문이다

동등 변환 규칙

질의 트리를 바꿀 수 있는 근거는 결과가 같은 관계 대수식 사이의 동등 규칙이다.

• AND 로 이은 실렉트는 차례로 나눌 수 있다. σ_{c1 AND c2}(E) ≡ σ_c1(σ_c2(E))
• 실렉트끼리는 순서를 바꿀 수 있다. σ_c1(σ_c2(E)) ≡ σ_c2(σ_c1(E))
• 조건이 한쪽 릴레이션의 속성만 쓰면 조인 안쪽으로 내릴 수 있다. σ_{c1 AND c2}(R ⋈ S) ≡ (σ_c1R) ⋈ (σ_c2S) (c1 은 R 의 속성만, c2 는 S 의 속성만 쓸 때)
• 조인과 자연 조인은 교환·결합 법칙이 성립한다.
• 실렉트와 카티전 곱은 세타 조인으로 합칠 수 있다. σ_c(R × S) ≡ R ⋈_c S
• 조인 위의 실렉트 조건은 조인 조건에 AND 로 합칠 수 있다. σ_c1(R ⋈_c2 S) ≡ R ⋈_{c1 AND c2} S
• 실렉트는 차집합 안으로 내릴 수 있다. σ_c(R − S) ≡ σ_c(R) − σ_c(S) ≡ σ_c(R) − S. 빼는 쪽 S 에 실렉트를 하지 않아도 결과가 같다. 교집합도 σ_c(R ∩ S) ≡ σ_c(R) ∩ S 이지만, 합집합은 σ_c(R) ∪ σ_c(S) 처럼 양쪽에 모두 해야 한다
• 프로젝트는 합집합에 분배된다. π_L(R ∪ S) ≡ π_L(R) ∪ π_L(S). 차집합과 교집합에는 일반적으로 분배되지 않는다. 투영으로 속성을 버리면 서로 달랐던 튜플이 같아질 수 있기 때문이다

OR 로 이은 조건은 이렇게 나눌 수 없다. σ_{A=3 OR F=9}(R ⋈ S) 는 A=3 인 행과 F=9 인 행을 모두 남기지만, (σ_A=3R) ⋈ (σ_F=9S) 나 σ_A=3(σ_F=9(R ⋈ S)) 는 두 조건을 모두 만족하는 행만 남긴다. 그래서 σ_{A=3 AND F=9}(R ⋈ S), (σ_A=3R) ⋈ (σ_F=9S), σ_A=3(σ_F=9(R ⋈ S)) 셋은 서로 동등하고, OR 를 쓴 식만 다르다.

경험적 최적화

휴리스틱 규칙으로 질의 트리를 바꾼다. 핵심은 중간 결과를 최대한 작게 만드는 것이다.

• 실렉트(σ)를 가능한 한 잎 쪽으로 내린다. 행을 먼저 줄인다.
• 프로젝트(π)도 가능한 한 아래로 내린다. 열을 먼저 줄인다.
• 실렉트 조건 c 의 애트리뷰트가 프로젝트 리스트에 모두 들어 있으면 두 연산의 순서를 바꿀 수 있다.
• 카티전 곱과 실렉트가 이어지면 조인으로 묶는다.
• 선택도가 낮은(결과가 작은) 연산을 먼저 수행한다.

비용 기반 최적화

• 카탈로그의 통계 정보(튜플 수, 블록 수, 인덱스 유무, 값의 분포)로 실행 계획마다 비용을 추정해 비교한다.
• 비용은 주로 디스크 접근 횟수로 잰다. 계산·메모리·통신 비용도 고려한다.
• 조인 방법(중첩 루프, 정렬 합병, 해시)과 접근 경로(전체 스캔, 인덱스 스캔)를 조합해 견준다.

같이 보기

• 관계 대수
• SQL 인덱스 관리
• 데이터베이스 병행제어