[DB] 3. 질의 수행(Query Evaluation)

이번 글에서는 질의 수행 개요 즉, 질의를 어떻게 처리하는지에 대해 설명할 것이다.

1. 시스템 카탈로그(System Catalog)

관계형 DBMS는 파일의 메타데이터(metadata)를 시스템 카탈로그라는 테이블 집합에 저장 및 관리한다. 

파일은 크게 테이블 파일과 인덱스 파일의 두 가지 유형이 존재한다.

- 테이블 파일의 메타데이터: 테이블의 스키마와 튜플의 통계 정보(튜플 수, 분포)

- 인덱스 파일의 메타데이터: 인덱스의 구조, 탐색 키, 인덱스 통계 정보(인덱스 크기, 높이, 범위)

 

시스템  카탈로그에는 계정 및 권한 정보와 같은 사용자 정보도 포함하고 있다.

카탈로그 테이블에는 자신에 대한 정보도 기술하고 있다. (아래 표 1~4번 행 참고)

 2. 연산자 수행(Operation Evaluation)

관계 연산자(relational operation)에 대한 다양한 알고리즘이 존재한다. 

테이블 크기, 인덱스 유무, 버퍼 풀 크기 및 교체 정책 등 여러 요인에 따라 최적 알고리즘이 달라진다. 

 

2.1. Common Technique

관계 연산자 알고리즘에 자주 사용되는 기법 3가지가 있다.

1. 인덱싱(indexing): 인덱스로 조건에 만족하는 테이블 튜플을 찾는다. (hash, tree)

2. 반복(iteration): 스캔으로 테이블 튜플을 하나씩 차례로 검사한다. (table scan, index data entry scan)

3. 분할(partitioning): 테이블 튜플을 특정 기준(정렬 키값 or 헤시값)에 따라 나누어 하나의 연산을 여러 독립적인 연산으로 분해하는 기법이다. (sorting or hashing)

 

2.2. Access Path

접근 경로(access path)는 테이블의 튜플을 검색하는 방법으로, 파일 스캔 혹은 조건에 부합(match)하는 인덱스로 구성되어 있다.

attr op value(e.g., rname > 4) 조건의 논리곱으로 이루어진 선택 조건을 논리곱 정규형(Conjunctive Normal Form=CNF)라 부르며, 각 조건을 논리곱(conjunct)이라 한다.

인덱스가 선택 조건을 만족하는 튜플을 찾는데 사용될 수 있다면, 해당 인덱스는 선택 조건에 부합한다(match)라고 표현한다.

- hash index: 탐색 키의 모든 필드에 대해 attr = value 조건이 있는 경우에만 CNF 조건에 부합한다.

- tree index: 탐색 키의 prefix 필드에 대해 attr op value 조건이 있는 경우, CNF 조건에 부합한다.

 

인덱스가 선택 조건의 전체가 아니라 일부에만 부합할 경우, 부합한 일부 조건을 기본 논리곱(primary conjunct)라 부른다.

 

- 접근 경로의 선택도(selectivity): 접근 경로를 사용 시 검색하는 페이지 수

- 가장 선택적인 접근 경로(most selectivity access path):  가장 적은 수의 페이지를 검색하는 접근 경로

3. 관계 연산자 알고리즘

1. 셀렉션(selection): file scan, cluster indexing

2. 프로젝션(projection): 중복 제거 시 partitioning(sorting, hashing)

3. 조인(join): nested loop(tuple, page, block) hash index, sort-merge

4. 쿼리 옵티마이저(Query Optimizer)

아래 그림처럼, 질의를 파싱 후 쿼리 옵티마이저에 넘기면, 쿼리 옵티마이저는 다양한 쿼리 처리 계획(Query Evaluation Plan)들을 생성하고 이들 중 추정 비용이 가장 적은 계획을 선택한다.

SQL 질의는 기본적으로 $\sigma-\pi-\bowtie$ 형태의 "확장된 관계 대수(extended form of relational algebra)"으로 표현할 수 있다.

 

쿼리 옵티마이저 수행 단계:

- 관계대수 변형규칙(relational algebra equivalence)으로 질의에 대한 여러 동치 관계대수 표현식을 찾는다. 

- 표현식마다 관계 연산자의 구현 방식을 고려해 여러 계획을 선별한다.

- 선별된 여러 질의 수행 계획 중 가장 비용이 적게 드는 계획을 선택한다.

 

4.1. 쿼리 처리 계획(Query Evaluation Plan)

쿼리 처리 계획은 관계대수 트리로 구성되며, 각 노드는 테이블 접근 방식 혹은 관계 연산자 구현 방법을 포함하고 있다.

앞으로, 쿼리 처리 계획에서 조인 연산의 왼쪽 자식을 외부 테이블(기준 테이블)으로 두겠다.

SQL

관계 대수

쿼리 처리 계획

4.2. 파이프라인식 처리(Multi-operator Queries: Pipelined Evaluation)

질의 수행 도중 중간 결과 저장을 위해 임시 테이블을 생성하지 않고 바로 다음 연산을 수행하는 것을 파이프라인되었다(piplelined)라고 표현한다. 연산 결과를 바로 다음 연산으로 파이프라인하면, 중간 결과를 디스크에 쓰고 읽는 작업을 생략해 상당한 비용을 절감할 수 있다.

반대로, 다음 연산을 위해 임시 테이블을 생성하는 경우는 튜플이 실체화(materialized)되었다라고 표현한다.

단항 연산자의 입력 테이블이 파이프라인될 경우, 연산자가 즉시(on-the-fly) 적용되었다라고 표현한다.

 

4.3. 쿼리 옵티마이저가 검토할 만한 요소

특정 테이블에 대해 두 관계대수가 항상 같은 결과를 내는 경우, 이 두 대수는 동등하다(equivalent)라고 표현한다.

대표적으로 다음과 같은 방식으로 동등한 관계대수를 만들 수 있다.

- 셀랙션과 크로스-프로덕트를 합쳐 조인으로 변경

- 조인의 순서 변경

- 입력 크기를 줄이기 위해, 셀랙션과 프로젝션을 조인 앞으로 이동

 

쿼리 옵티마이저가 좌심(left-deep) 트리 계획만 고려하는데 이유는 2가지가 있다.

1. 조인 개수가 늘어남에 따라 질의 수행 계획 경우의 수가 급격히 늘어나 가지치기가 필요하다.

2. 좌심 트리는 완전 파이프라인식의 생성을 가능케 한다.

맨 오른쪽 그래프가 좌심 트리다

 

4.4. 계획 비용 추정(estimating the Cost of a Plan)

질의 수행 계획 비용은 해당 계획 내 모든 연산의 비용의 합계다.

입출력 비용만 고려한다면, 계획의 비용은 크게 3가지로 나눌 수 있다: 1. 테이블 읽기, 2. 임시 테이블 쓰기, 3. 최종 결과 정렬

이 중 최종 결과 정렬은 모든 계획에 해당되므로 고려 대상이 아니다.

완전 파이프라인 계획의 경우 임시 테이블 쓰기 비용도 고려 대상이 아니기 때문에, 입력 테이블 접근 경로에 의해 총 비용이 주로 결정된다. 그 중 특히 조인 접근 경로가 중요하다.

완전 파이프라인 계획이 아닌 경우, 임시 테이블 실체화에 많은 비용이 발생할 수 있다. 해당 비용은 임시 테이블 크기에 좌우된다. 뿐만 아니라, 임시 테이블을 입력 테이블로 사용하는 연산자의 비용에도 영향을 준다.