[데이터베이스 개론] 8. 쿼리 실행(Query Execution)

15장과 16장은 쿼리 처리를 다룬다. SQL은 쿼리를 매우 높은 수준에서 표현하기 때문에, 쿼리 프로세서는 쿼리를 단순히 실행만 하기 보다, 어떻게 실행할지 고민하여 실행 효율을 높여야 한다. 15장에서는 쿼리 실행, 16장에서는 쿼리 컴파일에 집중한다.

쿼리 컴파일 단계는 세 가지 단계로 나뉜다.

1. 파싱(parsing): 쿼리로부터 맥락 트리(parse treee)를 만듦
2. 논리적 계획 생성(Logical Plan Generation): 맥락 트리로부터 논리적 계획(보통 대수적 표현)을 생성한다. 실행시간을 최소화 하기 위해, 동등하지만 더 효율적인 계획으로 변경한다.
3. 물리적 계획 생성(Phyisical Plan Generation): 논리적 계획을 물리적 계획으로 변경한다.

2번과 3번 단계를 흔히 쿼리 옵티마이저(optimizier)라고 하며, 가장 어려운 부분이다. 최적의 쿼리 계획을 선택하려면 아래의 고민이 필요하다.

1. 실행할 쿼리와 대수적으로 동등한 여려 형태 중 어떤것이 가장 효율적인가?
2. 선택된 형태의 각 연산을 어떻게 알고리즘으로 구현할 것인가?
3. 연산 간 데이터 전달을 어떻게 할 것인가? (파이프라인, 메인 메모리 버퍼, 디스크 등)

SQL은 bag 모델을 사용하기 때문에, bag 연산자 버전의 관계 대수를 이용한다. 위의 고민들은 데이터베이스의 메타데이터들을 통해 결정된다.

15.1 Introduction to Physical-Query-Plan Operators

물리적 계획은 연산자들로 구성된다. 연산자들은 특정 관계 대수를 위한 연산자도 있지만, 직접 관련없는 scan() 같은 연산자도 있다. 이 절에서는 물리적 계획을 구성하는 기본 블럭들을 다루고, 이후에는 관계 대수 연산은 효율적으로 구현하는 알고리즘을 다룬다.

물리적 계획의 기본은 릴레이션 R의 전체 내용을 읽는 것이다. 기본적으로 두가지 방법이 있다.

1. 디스크에 블럭 단위로 저장된 릴레이션들을 블럭 단위로 하나씩 가져오는 테이블 스캔(table-scan)
2. 인덱스를 사용해 모든 튜플을 가져오는 인덱스 스캔(index-scan)

그리고 데이터를 가져옴과 동시에, 정렬된 릴레이션이 필요하다면 소트 스캔(sort-scan)을 사용할 수 있다.

어떤 쿼리가 좋은 쿼리인지 선택하려면, 쿼리의 비용을 추산해야 한다. 이 때 비용의 척도로는, 디스크 I/O 횟수가 사용된다. 이 비용을 추산하기 위한 파라미터들도 소개한다.

• M: 연산에 사용가능한 메모리의 블럭 수. 보통 M은 실행중인 다른 프로세스 등에 의해 실행중에 결정되므로, 정확한 값보다는 추정값이다.
• B(R): R의 모든 튜플을 저장하는데 필요한 블럭 수. R은 B개의 블럭에 저장된다.
• T(R): R의 튜플 개수
• V(R,a): R의 a컬럼에 나타나는 서로 다른 값의 개수

파라미터를 적용해보자. 릴레이션 R이 클러스터링 되어있다면, 테이블 스캔 연산자의 디스크 I/O 횟수는 B이다. R이 메인메모리에 들어가는데에 문제가 없다면 소트 스캔도 마찬가지다. 하지만 클러스터링 되어있지 않다면, 튜플 횟수만큼 I/O를 해야하므로 테이블 스캔과 소트 스캔 비용은 T가 된다. 인덱스 스캔도 인덱스를 미리 살펴봐야하기는 하나, 인덱스의 크기는 B(R)보다 훨씬 작은 수이므로 동일하게 클러스터링 유무 각각 B와 T로 비용을 추산한다.

많은 물리적 연산자는 이터레이터(Iterator)로 구현된다. 연산자의 결과를 한번에 생성하는 물질화(materization) 전략에 비해 이터레이터 방식은 저장공간 관리에 유리하다. 물리적 연산자의 결과를 한 튜플씩 소비자에게 전달하는 구현은 세 가지 메소드로 구성된다.

1. Open(): 튜플을 가져오는 과정을 시작함. 필요한 데이터구조들을 초기화한다.
2. GetNext(): 결과에서 다음 튜플을 반환하고, 다음 튜플을 준비한다.
3. Close(): 소비자가 원하는 모든 튜플을 얻은 후, 반복을 종료한다.

이제 각 연산자마다 구현할 알고리즘을 정할것이다. 방법에 따라 세 가지로 나눌 수 있다.

1. 정렬 기반
2. 해시 기반
3. 인덱스 기반

난이도와 비용에 따라서도 세 단계로 나눌 수 있다.

1. 데이터를 디스크에서 한 번만 읽는 one-pass
2. 데이터를 디스크에서 두 번 읽는 two-pass, 큰 데이터의 크기 때문에 한 번에 메모리 크기 M안에 올릴 수 없기 때문이다.
3. Two-pass의 확장 개념으로, 재귀적으로 계속 디스크를 읽는 multi-pass

연산자의 종류도 세 가지로 분류할 수 있다.

1. 튜플 단위, 단항 연산
   1. 종류: 선택(selection), 사영(projection)
   2. 블록 단위로 읽고, 메모리 버퍼 하나만으로 연산 가능하다.
2. 릴레이션 단위, 단항 연산
   1. 종류: 중복제거(duplicate-elimination), 그룹화(grouping)
   2. 릴레이션 크기가 M보다 작으면 one-pass로도 가능
3. 릴레이션 단위, 이항 연산
   1. 종류: 집합연산, 곱연산(union, intersection, difference, join, production)
   2. 적어도 하나의 릴레이션 크기가 M보다 작으면 one-pass로도 가능

15.2는 one-pass 알고리즘을 다룬다. 15.3~15.6은 two-pass 알고리즘을 다루며, 각각 iteration-based, sort-based, hash-based, index-based 알고리즘이다. 15.8은 multi-pass 알고리즘을 다루지만 이 글에서는 생략한다.

15.2... 이후로는 언젠가 작성됩니다