[Architecture of a Database System] Relational Query Processor

Relational Query Processor는 declarative SQL statement (a type of SQL statement that specifies what data is required, but not how to obtain it)를 받아서 validate하고, 절차적인 데이터 플로우 execution plan으로 optimize하고, 데이터 플로우를 실행한다. 클라이언트는 결과 튜플을 한번에 하나씩, 혹은 작은 배치로 fetch (pull) 한다.

이번 장에서는 DML에 대해 공부한다. DDL은 쿼리 옵티마이저에 의해 실행되지 않는다. DDL 문은 스토리지 엔진 및 카탈로그 관리자에 대한 명시적 호출을 통해 static DBMS 로직에 의해 절차적으로 구현된다.

4.1 Query Parsing and Authorization

SQL Parser가 하는 일

1. 쿼리가 올바른지 확인한다. (check that the query is correctly specified )
2. name과 참조를 해결한다. (resolve names and references )
3. 쿼리를 옵티마이저가 사용할 내부 포맷으로 변환시킨다. (convert the query into the internal format used by the optimizer)
4. 사용자가 권한이 있는지 검증한다. (verify that the user is authorized to execute the query)

SQL 쿼리가 주어지면, 파서는 FROM 절에 있는 테이블 참조를 본다. 테이블 이름을 server.database.schema.table 의 형태로 표준화한다. 그리고 카탈로그 매니저를 호출해서 시스템 카탈로그에 테이블이 등록되어있는지 확인한다. 카탈로그를 통해 속성 참조가 올바른지 확인한다. 데이터 타입을 확인해 불명확한 논리 (함수 표현, 비교 연산자, 그리고 상수 표현)를 구동한다. 마지막으로 표준적인 SQL 문법을 확인한다.

그 다음으로 유저가 테이블에 데해 SELECT, DELETE, INSERT, UPDATE할 권한이 있는지 확인한다. security validation의 일부는 query plan execution 으로 넘겨진다.

쿼리 파싱과 validation 이 끝나면, 변환된 쿼리의 내부 포맷이 query rewrite 모듈로 넘겨진다.

4.2 Query Rewrite

Query Rewrite 모듈은 쿼리의 semantics를 바꾸지 않고 쿼리를 간단하게 만들고 표준화한다. 쿼리와 카탈로그에 있는 메타데이타만 사용할 수 있고 테이블의 데이터에는 접근할 수 없다.

Query Rewrite 모듈은 Query Parser와 Query Optimizer 사이에 존재한다. Query Parsing의 끝부분에서 실행되거나 Query Opimizer 맨 앞에서 실행된다. 여기에서는 전자로 설명한다.

Rewriter가 하는 일

1. View expansion
   뷰를 테이블로 변환한다.
2. Constant arithmetic evaluation
   ex) R.x < 10+2 + R.y → R.x > 12 + R.y
3. Logical rewriting of predicates
   WHERE 절의 상수와 술어를 기반으로 논리적 재작성을 한다.
   ex) NOT Emp.Salary > 1000000 → Emp.Salary ≤ 1000000
   Emp.Salary < 75000 AND Emp.Salary > 1000000 → False
4. Semantic Optimization
   ex) redundant join elimination
5. Subquery flattening and other heuristic rewrites

4.3 Query Optimizer

쿼리 옵티마이저는 내부 쿼리 표현을 쿼리 플랜으로 변환시킨다. 쿼리 플랜은 테이블 데이터를 쿼리 operators의 그래프로 연결시키는 데이터 다이어그램이다. 많은 시스템에서 쿼리는 SELECT-FROM-WHERE 쿼리 블록으로 나눠진다. Each query block is treated as a separate query, and the optimizer generates and evaluates possible execution plans for each block independently. The resulting optimal plans for each block are then combined to form an optimal plan for the entire query. 쿼리 옵티마이즈를 한다. 끝으로 GROUP BY, ORDER BY, HAVING, DISTINCT 절을 계산하기 위해 각 쿼리 블록의 맨 위에 operators가 추가된다. 쿼리 블락들을 하나로 붙인다. 이것이 쿼리 플랜이 된다.

대부분의 DBMS는 쿼리를 interpretable data structure로 컴파일 한다. (컴파일 언어와 인터프리터 언어 사이쯤 된다.) 쿼리 플랜은 relational algebraic expression 과 비슷하다.

대부분의 시스템이 Selinger의 논문을 확장해서 사용한다.

1. Plan space
   The System R optimizer에서는 plan space를 left-deep 쿼리 플랜에만 초점을 맞추고 Cartesian product를 조인 뒤로 연기했다. 요즘의 상업 시스템에서는, bush trees와 early Cartesian product를 사용하기도 한다.
2. Selectivity estimation
   Selectivity estimation은 간단한 테이블과 인덱스 카디널리티에 기반한다. 현대의 시스템은 히스토그램과 다른 통계 자료를 통해 속성의 값을 분석한다. 이는 칼럼의 모든 값을 방문해야 하므로 비싸다. 따라서 몇몇의 시스템은 샘플링 기술을 사용한다.
3. Search Algorithm
   Microsoft와 Tandem은 Selinger의 다이나믹 프로그래밍 옵타미이제이션 접근을 버리고 top-down search를 사용한다. top-down search는 플랜의 수를 줄여주지만 옵티마이저의 메모리 사용을 늘린다. 몇몇 시스템은 휴리스틱 search 를 사용한다.
4. Parallelism (병렬처리)
   대부분은 intra-query parallelism을 제공한다. 하나의 쿼리를 여러개의 프로세서에서 실행시키는 것이다. 옵티마이저는 operators를 여러 CPU에서 어덯게 실행시킬지 결정한다. 다른 방법으로는 먼저 하나의 single-system plan을 선택하고, 이 플랜을 여러 프로세서에서 실행시키는 것이다.
5. Auto-Tuning
   쿼리 작업량을 수집한 다음 옵티마이저가 다양한 “what-if”분석을 통해 플랜의 비용을 찾는 것을 기반으로 한다. 예를 들어 다른인덱스가 존재했거나 데이터가 다르게 배치되었다면?

4.3.1 A Note on Query Compilation and Recompilation

SQL은 query를 준비할 수 있는 기능을 지원한다. 파서와 rewriter, 옵티마이저에세 전달하고, 결과 쿼리 execution plan을 저장해 다음 SQL 문을 실행할 때 사용한다. 다이나믹 쿼리에서도 마찬가지로 가능하다. 한가지 단점은 옵티마이저가 dynamic variables를 typical한 값으로 가지도록 가정되어, selectivity estimation이 올바르게 이뤄지지 않을 수 있다는 것이다.

Ruby on Rails같은 프레임워크에서는 SQL문을 다이나믹하게 만든다. 따라서 pre-compile을 할 수 없다. 이러한 경우에 쿼리 플랜 캐시를 사용한다.

인덱스가 삭제되었을 때, 캐시된 쿼리 플랜을 re-optimize할 것인지는 DBMS 마다 다르다.

4.4 Query Executor

Query Executor는 완전히 지정된 쿼리 플랜을 작동시킨다. 쿼리 플랜은 operators를 연결하는 데이터플로우 그래프이다. 몇몇 시스템에서 데이터플로우 그래프는 옵티마이저에 의해 operation 코드로 컴파일된다. 다른 시스템에서는 이 장에서는 Query Executor가 dataflow graph를 받아서 operators를 위한 프로시져를 호출한다. 이번 장에서는 후자의 시스템에 기반해서 설명한다.

대부분의 Query Executor는 다음과 같은 iterator 모델을 사용한다.

class iterator {
        iterator &inputs[];
        void init();
        tuple get_next();
        void close();
}

각각의 iterator는 edge를 정의하는 입력을 지정한다. 쿼리 플랜의 모든 operator는 iterator 클래스의 subclass로 구현되어있다.

4.4.1 Iterator Discussion

iterator는 dataflow와 control flow을 결합한다. get_next() 콜스택을 통해 call은 콜러에게 tuple reference를 리턴하는 프로시져 콜 이다. 따라서 tuple은 컨트롤이 리턴될 때 그래프의 부모에게 리턴된다.

4.4.2 Where’s the Data?

reference 되는 튜플들은 메모리의 어디에 저장돼있을까?

1. 버퍼 풀 안에 있는 경우
   BP-튜플 이라고 한다. iterator가 BP-튜플을 참조 하는 descriptor를 만든다. 튜플 페이지의 pin count를 증가시킨다. 튜플 descriptor가 clear되면 pin count를 감소시킨다.
2. iterator 구현이 힙 공간에 튜플을 위한 메모리를 할당하는 경우
   M-튜플 이라고 한다. iterator는 버퍼 풀로부터 칼럼을 복사해서 M-튜플을 만든다.

4.4.3 Data Modification Statements

지금까지는 read-only SQL 문에 대해서 공부했다. DML에는 데이터를 수정하는 INSERT, DELETE, UPDATE 문도 있다. INSERT, DELETE, UPDATE의 execution 플랜은 일반적으로 단일 access method를 소스로 하고 파이프라인 끝에 데이터 수정 연산자를 사용하는 단순한 쿼리 플랜이다.

하지만 몇몇 케이스에서 플랜은 질의(읽기)와 수정(쓰기)을 둘 다 한다. 이 간단한 예제는 “Halloween problem”으로 알려져있다. Halloween problem은 “give everyone whose salary is under $20K a 10% raise”와 같은 execution plan에서 발생한다.

UPDATE EMP
   SET salary=salary*1.1
 WHERE salary < 20000

이 쿼리에 대한 플랜은 인덱스 스캔 iterator를 Emp.salary를 통해 update iterator로 연결한다. 이 파이프라이닝은 인덱스 스캔을 이전에 수정한 튜플을 다시 탐색하게 한다. 모든 Employee는 salary가 $20K가 넘을 때 까지 실행된다.

SQL semantics는 하나의 SQL 문에서 본인의 update를 볼 수 없게 한다.

쿼리 옵티마이저에서 업데이트된 열에서는 인덱스를 피하는 플랜을 선택한다. 또다른 방법은 read-then-write 전략을 사용하는 것이다. 이는 인덱스 스캔과 데이터 수정 연산자 사이에 RID Materialize 및 Fetching 연산자를 끼워넣는다. Materilzation 연산자는 수정할 모든 튜플의 ID를 받아서 임시 파일에 저장한다. 그리고 임시 파일을 스캔해서 RID를 통해 물리적 튜플 ID를 fetch한다. 그리고 결과 튜플을 수정 연산자에게 넘긴다.

4.5 Access Methods

Access Methods는 다양한 disk-based 자료구조에 대한 access 를 관리하는 routine이다. heap과 같은 unordered files나 B+-Tree, R-Tree .. 를 포함한다.

Access Methods가 제공하는 기본적인 API는 iterator API이다. init() 메소드는 column 연산자 상수 형태의 search argument (SARG)를 받도록 확장된다. 메소드 레이어에 SARG를 전달하는 이유 두 가지가 있다. 첫번째는 B+-Tree 와 같은 인덱스 엑세스 메소드가 SARG를 필요로한다는 것이다. 두 번째 이유는 인덱스 스캔 뿐만 아니라 힙 검색에도 적용된다. SARG가 액세서 메소드 레이어를 콜하는 루틴에 의해 확인된다고 가정하자. 그럼 엑세스 메소드가 get_next()로부터 리턴할 떄 마다, 버퍼 풀에 있는 튜플을 핸들할 수 있는 권한을 리턴하고 페이지를 pin 하거나 튜플에 대한 복사를 하게 된다. SARG가 만족되지 않았을 때 콜러는 pin count를 감소하거나 복사된 튜플을 ㅅ가제해야 한다. 그리고 get_next()를 다시 호출한다. 이 로직은 CPU 사이클을 많이 소모하고 오버헤드가 크다. 대조적으로, 모든 로직이 액세스 메소드 레이어에서 이뤄진다고 생각하보자. 한 번에 한 페이지씩 SARG를 테스트하고 get_next()호출에서 SARG를 만족시키는 튜플을 반환함으로써 반복되는 call/return과 pin/unpin 또는 copy/delete를 막을 수 있다. 따라서 많은 시스템은 풍부한 SARG를 제공한다.

모든 DBMS는 인덱스 엔트리가 row를 reference할 수 있도록 베이스 테이블의 row를 point할 수 있어야 한다.

1. 물리적 디스크 주소를 RID로 사용
   장점: 빠르다
   단점: 세컨더리 인덱스가 RID를 사용해 페이지를 reference하므로 row의 이동이 비싸진다.
   • row 사이즈가 변경되거나 변경된 row에 대해 현재 페이지에 공간이 없는 경우 row를 옮겨야 한다.
     • forwarding pointer로 해결하기도 한다.
   • B+-tree가 분할될 때 row를 옮겨야 한다.
     • B+-tree를 주요 저장소로 사용하지 않는다.
2. PK를 RID로 사용

4.8 Standard Practice

시스템 간의 주요 설계 차이는 옵티마이저 검색 전략 (top-down vs bottom-up)과 쿼리 executor control-flow 모델, 특히 shared-nothing과 shared-disk 병렬화 (iterator 및 excange operator vs aynchronous producer/consuper 전략)에서 발생한다.

PostgreSQL은 기존 비용 기반 옵티마이저, 광범위한 execution 알고리즘 및 많은 확장성 기능을 갖춘 정교한 쿼리 프로세서를 가지고 있다.

MySQL 쿼리 프로세서는 인덱스에 중첩된 루프 조인을 기반으로 구축되어 훨씬 간단하다. MySQL 쿼리 옵티마이저는 key/foreign-key join, outer-join-to-join rewrite, 결과의 처음 몇 row만 요청하는 쿼리 등이 가볍고 효율적인지 확인하기 위하 쿼리를 분석하는데 중점을 둔다.