Overview of PostgreSQL Internals(PG14 기준)

https://www.postgresql.org/docs/14/overview.html

Chapter

1. The Path of a Query

1. How Connections Are Established
2. The Parser Stage 3.1. Parser 3.2. Transformation Process
3. The PostgreSQL Rule System
4. Planner/Optimizer 5.1. Generating Possible Plans
5. Executor

1. The Path of a Query

쿼리 경로가 생성되기 위해서는, 우선 애플리케이션 프로그램에서 PostgreSQL 서버로의 연결이 설정되어야 한다. 애플리케이션 프로그램은 서버에 쿼리를 전송하고 서버에서 다시 보낸 결과를 받을 때까지 기다린다.

Parser Stage에서는 애플리케이션으로부터 전송 받은 쿼리가 정확한 구문으로 왔는지 체크한 후에 Query Tree를 생성한다.

Rewrite System은 Parser Stage로부터 만들어진 Query Tree를 가지고 와서 Query Tree에 적용할 Rule을 저장된 System Catalog에서 탐색한다.

Rewrite System 중 하나의 애플리케이션은 View를 실현한다. View(가상 테이블)에 대한 쿼리가 만들어 질 경우, Rewrite System은 사용자의 쿼리를 View 정의에 제공된 기본 테이블에 액세스하는 쿼리로 Rewrite 한다.

Planner/Optimizer는 (재작성된) Query Tree를 가지고 와서 Executor에 대한 입력이 될 Query Plan을 생성한다.

2. How Connections Are Established

PostgreSQL은 ‘process per user(사용자 당 Process)’ Client 및 Server model을 구현한다. 이 모델에서, 모든 Client Process는 정확히 Backend Process에 연결된다.

이 때 얼마나 많은 Connection이 만들어질지는 미리 알 수 없으므로, Connection이 요청될 때마다 새로운 Backend Process를 생성하는 ‘supervisor process’ 를 사용해야 한다.

이 supervisor process는 postmaster라고도 불리며, 지정된 TCP/IP port에서 들어오는 연결을 수신 받기 위해 대기한다. Connection 요청을 감지할 때마다 새로운 Backend Process를 생성한다.

이 Backend Process는 동시 데이터 액세스 전체에서 데이터 무결성을 보장하기 위해 Semaphore 및 공유 메모리를 사용하여 동일 프로세스 혹은 Instance의 다른 Process와 통신한다.

3. The Parser Stage

Parser Stage는 다음 두 가지 파트로 이루어져 있다.

• Parser는 bison과 flex라는 Unit Tool로 build된 gram.y와 scan.l에 의해 정의된다.
• Transformation Process는 Parser에서 Return된 Data Structure를 수정하고 확장한다.

3.1 Parser

Parser는 (일반적인 텍스트로 온) 유효한 구문에 대한 Query String을 체크해야 한다. 구문이 올바를 경우 Parse Tree가 만들어지고 이를 다시 전달한다. Parser와 lexer는 bison과 flex를 통해 구현된다.

lexer는 scan.l 파일에 정의되어 있고, 식별자와 SQL Keyword 등을 인식하는 역할을 한다. 발견된 모든 Keyword 및 식별자에 대해 Token이 생성되어 Parser에 전달된다.

Parser는 gram.y에 정의되어 있고, rule이 실행될 때마다 실행되는 일종의 문법 규칙과 관련 action으로 구성된다. action code(C Code) Parse Tree를 구축하는 데에 사용된다.

scan.l 파일은 flex를 사용하여 C Source 파일인 scan.c 파일로 변환되며, gram.y는 bison을 통해 gram.c로 변환된다. 이후 일반적인 C Compiler를 통해 Parser를 만들 수 있다. 차후 변경 사항이 생기면(flex 및 bison이 호출될 때) 기존에 생성된 C 파일을 덮어쓰게 되므로, 변경해야 할 내용이 있다면 scan.l과 gram.y를 직접 제어해야 한다.

상기 연관된 파일들은 일반적으로 PostgreSQL 소스 배포와 함께 제공되는 makefile을 사용하여 자동으로 수행된다.

3.2. Transformation Process

Parser Stage는 SQL의 구문 구조에 대한 고정된 rule만을 사용하여 Parse Tree를 생성한다. 이는 System Catalog에서 탐색하지 않으므로, 요청 작업에 대한 상세한 의미를 알기가 힘들다. Parser가 완료되면, Transformation Process는 Parser가 반환한 Tree를 입력으로 사용하고, Query에서 참조하는 Table이나 Function 및 연산자를 이해하는 데에 필요한 의미가 담긴 해석(Semantic Analysis)을 수행한다. 이 정보를 나타내기 위해 작성된 데이터 구조가 Query Tree이다.

Semantic Analysis에서 Raw Parsing을 분리하는 이유는 시스템 카탈로그는 Transaction 내에서만 조회를 수행할 수 있고, Query String을 수신하는 즉시 Transaction을 시작하지 않기 때문이다.

Raw Parsing Stage는 Transaction Control Command(BEGIN, ROLLBACK, and so on)를 충분히 식별할 수 있으며, 추가적인 Analysis 없이 해당 작업을 제대로 수행할 수 있다. Actual Query(SELECT, UPDATE 등등)를 처리하고 있음을 인지하게 되면, 아직 Transaction이 없는 경우 Transaction을 시작할 수 있고, 이 과정이 있어야 Transformation Process를 호출할 수 있다.

Transformation Process를 통해 생성된 Query Tree는 대부분 구조적으로 Raw Parse Tree와 유사하지만, 세세하게 따지면 많은 차이점이 존재한다. 예를 들어, Parse Tree 내부에 있는 FuncCall node는 구문적으로는 Function Call처럼 보이지만, Reference name이 일반적인 함수인지, 집계 함수인지를 따라 FuncExpr이나 Aggref node로 변환될 수 있다. 또한, Column의 실제 데이터 타입과 expression 결과에 대한 정보가 Query Tree에 추가된다.

4. The PostgreSQL Rule System

PostgreSQL은 View의 사양이나 애매한 View Update를 위한 Rule System을 지원한다.

이러한 Rule System은 두 가지 구현으로 구성되어 있다.

• Row level Processing을 활용하여 기동되고, 이는 Executor의 내부 깊숙한 곳에 구현되어 있다. Rule System은 개별적인 Row에 엑세스 할 때마다 호출된다. 개별 Row에 액세스할 때마다 Rule System이 호출되었지만, 이 기능은 Berkeley Postgres 프로젝트의 마지막 공식 릴리스가 Postgres95로 변환된 1995년에 제거되었다.
• Rule System의 두 번째 구현은 query rewriting이라 불리는 기술이다. rewrite system은 Parser Stage와 Planner/Optimizer 사이에 존재하는 모듈이다. 상기 기술은 사실상 폐기이고, 현재느 ㄴ이 기능이 유일하다.

5. Planner/Optimizer

Planner/Optimizer의 역할은 최적의 Execution Plan을 만드는 것이다. 주어진 SQL Query(Query Tree)는 실제로 다양한 방식으로 실행될 수 있으며 각 방식은 동일한 result set을 생성한다. 계산이 가능한 경우 Query Optimizer는은 이러한 가능한 각 Execution Plan을 검사하여 그 중 가장 빠르게 실행될 것으로 예상되는 Execution Plan을 선택한다.

경우에 따라 Query를 실행할 수 있는 각 가능한 방법을 검사하는 데 필요 이상의 시간과 메모리가 소요된다. Join이 많이 걸려있는 Query를 실행할 때 발생하는데, 합리적인 시간 내에 합리적인(최적일 필요는 없는) Query Plan을 결정하기 위해 PostgreSQL은 Join 수가 임계값(geqo_threshold)을 초과할 때 Genetic Query Optimizer를 사용한다.

Planner의 검색 절차는 Path라고 하는 데이터 구조와 함께 동작한다. Path는 Planner가 결정을 내리는 데 필요한 만큼의 정보만 포함하는 계획의 간략한 표현이다. 가장 비용이 낮은 Path라고 판단되면 본격적인 Plan Tree가 구축되어 실행자에게 전달된다. 이는 실행자가 실행할 수 있도록 원하는 Execution Plan을 충분할 정도로 자세하게 나타낸다.

5.1 Generating Possible Plans

Planner/Optimizer는 우선 Query에 사용된 각 개별 Releation(Table)을 Scan하기 위한 Plan을 생성한다. 가능한 Plan은 각 Relation에서 사용할 수 있는 Index에 의해 결정된다. 항상 Relation에 대한 순차적인 스캔을 수행할 수 있으므로 이 때 항시 Sequential Plan Plan이 생성된다.

Index가 관계(예: B-트리 색인)에 정의되어 있고 쿼리에 Re relation.attribute OPR 상수가 포함되어 있다고 가정할 때, relation.attribute가 B-Tree index의 Key와 일치하고 OPR이 Index의 연산자 클래스에 나열된 연산자 중 하나인 경우 B-Tree Index를 사용하여 관계를 스캔하는 또 다른 Plan이 생성된다.

추가 Index가 있고 Query의 제한 사항이 Index의 Key와 일치하는 경우 추가 Plan이 고려된다. Query의 ORDER BY 절(있는 경우)과 일치할 수 있는 정렬 순서 또는 병합 Join에 유용할 수 있는 정렬 순서가 있는 Index에 대해서도 Inddex Scan Plan이 생성된다.

Query가 두 개 이상의 Relation을 Join해야 할 경우, 단일 관계를 Scan하기 위한 모든 Plan을 탐색한 후, Relation Scan Plan을 고려한다. 이 때 사용할 수 있는 전략은 다음 세 가지가 대표적이다.

• nested loop join : 왼쪽 Relation에서 찾은 모든 Row에 대해 오른쪽 Relation을 한 번 Scan한다. 구현은 쉽지만 시간이 많이 소요될 수 있다. 만일 Index Scan으로 오른쪽 Relation을 Scan할 수 있다면 이는 어느 정도 해소될 수 있다.
• merge join : Join이 시작되기 전 Join의 속성에 따라 각 Relation이 결정된다. 그 후 두 Relation을 병렬로 Scan하고 일치하는 Row를 결합하여 Join Row를 생성한다. 이런 유형의 Join은 각 Relation을 한 번만 Scan하는 장점이 있다. 필요한 정렬은 명시적인 정렬 단계 혹은 Join Key의 Index를 사용하여 적절한 순서로 Relation을 Scan하여 수행할 수 있다.
• hash join : 우측 Relation을 Hash Key로 사용하여 정확한 Relation을 먼저 Scan 한 후 Hash Table에 불러온다. 그 후 왼쪽 Relation이 Scan되고 찾아낸 모든 Row의 적절한 값이 Hash Key로 활용, Table에서 일치하는 Row를 찾는다.

Query가 세 개 이상의 Relation에 포함되어 있을 경우, 마지막 결과는 두 가지 입력 형태를 가진 Join 단계의 Tree로 만들어져야 한다. Planner는 가능한 여러 Join Sequence를 조사하여 가장 값싼 것을 찾는다.

Query가 geqo_thjreshold Relation보다 적은 Relation을 사용할 경우, 가장 이상적인 Join Sequence를 찾기 위해 거의 포괄적인 Scan을 수행한다. Planner는 WHERE 절에 대해 해당 JOIN이 있는 경우(where rel1.attr1 = rel2.attr 같은 유형) 두 Relation간의 Join을 우선적으로 고려한다. Join절이 없는 Join 쌍은 다른 대안이 없을 경우, 즉 특정 Relation에 다른 Relation에 사용할 수 있는 JOIN이 없는 경우)에만 고려된다. Planner가 고려한 모든 JOIN pair에 가능한 모든 Plan이 생성되며, 그 중 가장 cost가 낮다고 판단되는 것이 선택된다.

geqo_threshold가 초과되면, JOIN Sequence는 heuristics에 의해 결정된다. 그렇지 않을 경우의 Process는 동일하다.

완성된 Plan Tree는 기본 Relation의 순차 혹은 Index Scan과 필요시 nested-loop, merge, hash join node, 정렬 노드 또는 집계 함수 계산 노드와 같은 필요한 보조 단계로 구성된다. 이러한 Plan node의 대부분의 유형은 선택(지정된 Boolean 조건을 충족하지 않는 Row 삭제) 및 Projection(주어진 Row value를 기반으로 파생된 Column Set의 계산, 즉 필요한 경우 Scalar식 평가)을 수행할 수 있는 추가 기능이 있다. Planner가 지녀야 할 소임 중 하나는 WHERE 절의 선택 조건과 필요한 출력 표현식의 계산을 Plan Tree의 가장 적절한 노드에 연결하는 것이다.

6. Executor

Executor는 Planner/Optimizer가 생성한 Plan을 가져온 후 필요한 Row Set을 추출하기 위해 반복적으로 처리한다(demand-pull pipeline mechanism의 일종). Plan node가 호출될 때마다 하나 이상의 Row를 전달하거나 전달이 완료되었음을 report 해야 한다.

최상위 노드가 MergeJoin 노드라고 가정할 경우 Merge 수행 전 두 개의 Row를 각 하위 Plan에서 하나씩 가져와야 한다. 이 하위 Plan을 처리 하기 위해 재귀적으로 자신을 계속해서 호출한다(왼쪽 Tree에 연결된 하위 Plan에서 시작한다).

새로운 최상위 Note(왼쪽 하위 Plan의 최상위 Node)는 정렬 Node이며 입력 Row를 얻기 위해 다시 재귀가 필요하다고 가정했을 경우, Sort의 하위 Node는 테이블의 실제 읽기를 나타내는 SeqScan 노드일 수 있다. 이 Node를 실행하면 실행자가 테이블에서 Row를 가져와 호출 Node로 반환한다. 정렬 Node는 정렬할 모든 Row을 얻기 위해 하위 항목을 반복적으로 호출하고, 입력이 소진되면(Row 대신 NULL을 반환하는 자식 Node로 표시됨) Sort 코드는 정렬을 수행하고 최종적으로 정렬된 순서의 첫 번째 Row를 반환할 수 있다. 나중에 요청에 응답하여 정렬된 순서로 전달할 수 있도록 나머지 행을 저장된 상태로 유지한다다.

MergeJoin 노드는 마찬가지로 오른쪽 하위 Plan에서 첫 번째 행을 요구한 후 두 Row를 비교하여 JOIN할 수 있는지 확인한다. 그 후 JOIN ROW를 호출자에게 반환한다. 다음 호출에서 또는 현재 입력 쌍을 JOIN할 수 없는 경우 즉시 한 테이블 또는 다른 테이블의 다음 Row로 이동하고(비교 결과에 따라) 다시 일치하는지 확인한다. 결국 하나의 하위 Plan 또는 다른 하위 Plan이 소진되고 MergeJoin 노드가 NULL을 반환하여 더 이상 JOIN Row를 형성할 수 없음을 나타낸다.

복잡한 Query에는 여러 수준의 Plan Node가 포함될 수 있지만 일반적인 접근 방식은 동일하다. 각 Node는 호출될 때마다 다음 출력 Row를 계산하고 반환하고, 각 Node는 Planner가 할당한 선택 또는 Projection Expression을 적용하는 역할도 담당한다.

Executor 메커니즘은 SELECT, INSERT, UPDATE 및 DELETE의 네 가지 기본 SQL Query 유형을 모두 평가한다. SELECT의 경우 최상위 Executor Code는 Query Plan Tree에서 반환된 각 Row를 클라이언트로 보내기만 하면 된다. INSERT ... SELECT, UPDATE 및 DELETE는 ModifyTable이라는 특별한 최상위 Plan Node 아래의 효과적인 SELECT이다.

INSERT ... SELECT는 삽입을 위해 ModifyTable까지 Row를 공급한다. UPDATE의 경우 Planner는 각 계산된 Row에 업데이트된 모든 Column 값과 원래 대상 Row의 TID(Tuple ID or Row ID)가 포함되도록 정렬한다. 이 데이터는 이 정보를 사용하여 업데이트된 새 Row를 만들고 이전 Row를 삭제된 것으로 표시하는 ModifyTable Node에 제공된다. DELETE의 경우 Plan에서 실제로 반환되는 유일한 Column은 TID이며 ModifyTable Node는 단순히 TID를 사용하여 각 대상 Row을 방문하고 삭제된 것으로 표시한다.

간단한 INSERT ... VALUES 명령은 단 하나의 결과 Row를 계산하고 삽입을 수행하기 위해 ModifyTable에 공급하는 단일 결과 노드로 구성된 사소한 Plan Tree를 형성한다.