Optimizer?
사용자의 Query가 요구하는 결과물을 가공하는 데에는 여러 방법이 존재할 수 있습니다. 예를 들어, 조건문을 사용하여 테이블로부터 필터링 된 결과만 읽으려고 할 때 테이블의 모든 Row를 읽어서 필터링을 할 수도 있고 아니면 인덱스를 활용하여 필요한 Row만 읽어올 수도 있습니다. 둘 중 어떤 선택이 더 효율적일 지는 조건문의 성격에 따라, 데이터의 특성에 따라, 그리고 장비의 스펙에 따라 달라질 수 있습니다.
사용자 Query 수행을 최적화하기 위해 가능한 모든 수행 방법의 조합을 비교하고 최선의 실행 경로를 결정하는 것이 Optimizer가 맡은 임무입니다. PostgreSQL의 Optimizer는 Query 수행을 최적화하기 위해 비용 기반 최적화(Cost-based Optimization) 방법을 사용합니다. 비용이란 Query 수행에 필요한 자원을 수치화한 것이며 대표적인 예로 로우를 읽고 값 비교를 하는 데 발생하는 CPU 비용, 임의의 페이지(Page)를 읽을 때 발생하는 I/O 비용 등이 있습니다. Optimizer는 Query 수행이 가능한 모든 실행 경로에 대해 비용을 계산하고 제일 적은 비용을 갖는 경로를 실행 계획(Execution Plan) 형태로 수립하는 일을 합니다.
실행 계획 수립 과정 ️
데이터베이스에 요구하는 Query 복잡도가 높아질수록 실행 계획을 수립하는 과정은 더 복잡해질 수밖에 없습니다. 따라서 해당 글에서는 실행 계획이 수립되는 과정의 전반적인 이해를 높이는 차원에서 간단한 Query에 대한 예로 설명하겠습니다. SQL 형태로 들어온 사용자 Query를 Parsing하면 그 결과는 Query Tree 의 형태로 Optimizer에게 전달됩니다.
Query Tree에는 Query에 포함된 컬럼이나 테이블과 같은 데이터 객체의 MetaData와 연산자, 기호와 같이 데이터 값을 얻기 위해 계산해야 하는 표현식이 상호관계에 알맞게 트리 형태로 저장되어 있습니다. Optimizer는 Query Tree에 있는 정보를 사용하여 결과값을 얻을 수 있는 실행 경로를 모두 구하고, 각각의 비용을 계산 및 비교하여 최적의 실행 계획을 선택합니다.
실행 계획 수립 과정은 크게 3개의 과정으로 나뉩니다.
- Query Tree 간소화 작업
- 최저 비용의 실행 경로를 찾는 작업
- 최저 비용의 실행 경로를 실행 계획으로 변환하는 작업
각 과정에 대해 살펴보도록 하겠습니다.
Query Tree 간소화 작업
실행 경로를 만들기에 앞서 Query Tree 내부에 미리 할 수 있거나 불필요한 표현식에 대해서 간소화를 수행합니다. 간소화 작업은 실행 경로의 변주 개수를 줄이는 역할을 하기 때문에 Query 최적화 작업 시간을 줄이고 메모리와 CPU 사용량도 줄여주는 효과를 가져옵니다.
Query Tree 간소화 작업은 다양한 부분에 대해 이뤄지는데 아래 간단한 예제들을 소개합니다.
SELECT 절에 포함된 표현식 간소화
예를 들어 ‘1 + 1’과 같은 표현식을 ‘2’로 변경하는 등 미리 SQL 컴파일 시에 계산할 수 있는 정적 표현식에 대해 간소화합니다.
불리언(Boolean) 연산자에 대한 간소화
예를 들어 ‘NOT(NOT CONDITION_A)’와 같은 표현식을 ‘CONDITION_A’로 변경하는 등 이중 부정 형식으로 이뤄진 불리언 표현식을 상쇄합니다.
AND/OR 표현식 평탄화
PostgreSQL은 AND/OR 표현식을 N항 연산자 형태로 효율적이게 처리할 수 있습니다. Query Tree에 AND/OR 표현식을 이항 연산자 형태로 만들면 실행 경로 그리고 실행 계획에서도 한 번에 처리할 수 있는 표현식을 여러 표현식 계산 단계를 거쳐 계산해야 하기 때문에 비효율적일 수 있습니다. 따라서 AND/OR 표현식에 대해 평탄화를 하여 보다 효율적인 실행 경로가 만들어지도록 유도합니다.
최저 비용의 실행 경로 찾기
간소화를 끝낸 Query Tree는 실행 경로를 만드는 데 사용됩니다. 실행 경로는 Query가 요구하는 표현식에 따라 다양하게 생기는데 종류로는 데이터를 스캔할 방식인 Access Path, 테이블을 조인할 방식인 Join Path, 데이터를 그룹 함수를 사용하여 집계할 때 사용할 방식인 Grouping Path 등이 있습니다.
Access Path의 예로는 데이터를 디스크에 저장된 순서대로 읽어오는 Sequential Scan, 인덱스를 활용하여 특정 로우를 읽어오는 Index Scan 등이 있습니다.
Join Path의 예로는 Hash Table을 사용하는 Hash Join, 인덱스를 사용하는 Index Join, 그리고 카테시안 곱처럼 모든 로우의 조합을 검사하는 Nested Loop Join이 있습니다.
마지막으로 Grouping Path의 예로는 해시 테이블을 사용하여 집계하는 Hash Aggregate와 이미 그룹키로 정렬된 데이터를 집계하는 Group Aggregate가 있습니다.
위와 같이 다양한 방법론을 조합하여 Query가 요구하는 결과값을 도출할 수 있는 실행 경로들을 생성하고 각 경로에 대한 비용을 계산하게 됩니다. 비용을 계산할 때 변수와 공식은 아래 Cost-based Optimization 항목에서 자세히 살펴보고 지금은 생략하도록 하겠습니다.
실행 경로를 실행 계획으로 변환
실행 계획은 Plan Tree 라고 불리는 트리 형태의 자료구조에 저장하여 실행 엔진에 전달됩니다. Plan Tree에는 실행 엔진이 실행 계획을 수행하는 논리적 단위인 Plan Node의 이진 트리 형태로 되어 있는데, 노드의 순서는 수행이 완료되어야 하는 순의 역순으로 되어 있습니다. 즉, 마지막으로 수행이 완료되는 노드가 부모 노드에 위치해 있으며 먼저 수행이 완료되어야 하는 노드가 자식 노드에 위치해 있습니다.
간단한 예로 아래 Query에 대해 어떻게 플랜 트리가 생성되는지 확인해보겠습니다.
postgres=$ d students
Table “public.students”
Column | Type | Collation | Nullable | Default
———–+———————+———————+—————–+—————-
id | integer | | |
name | character(20) | | |
postgres=$ explain verbose select id, name from students where id < 300 order by name;
QUERY PLAN
—————————————————————————————————–
Sort (cost=27.91..28.49 rows=233 width=88)
Output: id, name
Sort Key: students.name
-> Seq Scan on public.students (cost=0.00..18.75 rows=233 width=88)
Output: id, name
Filter: (students.id < 300)
(6 rows)
생성된 실행 계획에서도 볼 수 있듯이 Plan Tree의 첫 번째 엔트리는 SortNode, 즉 정렬에 필요한 동작이, 그리고 그 뒤에는 SeqScan, 즉 Sequential Scan을 위한 동작이 위치해 있는 것을 볼 수 있습니다. 그 이유는 Sequential Scan을 모두 끝내야 결과값을 정렬할 수 있게 되는데, 만약 SortNode가 플랜 트리의 상단이 아닌 곳에 위치해 있다면 불필요하게 트리를 탐색하는 비용이 추가되었을 것입니다.
데이터를 가공하고 사용자에게 결과값을 전달할 때 결국 마지막까지 반복적으로 수행해야 하는 노드가 트리 상단에 위치해 있는 것이 탐색의 효율성을 최대화할 수 있습니다. 그것이 PostgreSQL 뿐만 아니라 여러 DBMS가 이와 같은 형태의 실행 계획을 선택한 이유입니다.
비용 기반 최적화
앞서 설명했듯이 PostgreSQL의 Optimizer는 실행 경로 중 제일 최적의 경로를 찾아 실행 계획을 생성하는 것에 Cost-based Optimization이라는 방법을 사용합니다. 각 Executor Operation 별로 정의된 함수에 의해서 비용이 계산되며 해당 함수들은 costsize.c 파일에 정의되어 있습니다. 예를 들어 Sequential Scan과 Index Scan의 비용은 각각 cost_seqscan, cost_index 함수를 사용하여 계산됩니다.
비용은 Start-up Cost와 Run Cost로 나눠집니다. Start-up Cost는 하나의 Row를 읽기까지 소요되는 비용입니다. 예를 들어 Index Scan의 Start-up Cost 첫 번째 인덱스 튜플을 읽기 위해 소요되는 트리 탐색 비용입니다. 반면 Run Cost는 첫 번째 Row를 읽은 후 모든 Row를 읽기까지 소요되는 비용입니다. Query에 EXPLAIN 커맨드를 붙여 결과물을 출력해보면 Start-up Cost와 Run Cost를 확인해 볼 수 있습니다.
아래 간단한 예제를 통해 살펴보겠습니다.
postgres=$ EXPLAIN SELECT * FROM TEST;
QUERY PLAN
——————————————————–
Seq Scan on test (cost=0.00..35.50 rows=2550 width=4)
(1 row)
실행 계획에 출력되는 “cost” 값은 각각 Start-up Cost와 Total Cost입니다. 따라서 위와 같은 Sequential Scan의 경우 Start-up Cost는 0, Run Cost는 35.5으로 측정된 것을 볼 수 있습니다.
이제 Sequential Scan, Index Scan 그리고 정렬 오퍼레이션의 비용 계산 방법을 보면서 PostgreSQL의 Optimizer가 어떤 부분을 비용으로서 고려하고 계산하는지 알아보도록 하겠습니다.
Sequential Scan 비용 계산법
Sequential Scan의 경우 Start-up Cost는 항상 0으로 계산되고 Run Cost가 전체 비용을 차지하게 됩니다. Sequential Scan의 Run Cost는 아래 수식에 의해 정의됩니다.
Run Cost = CPU 연산비용 + 페이지 읽기 비용
text{Run Cost} = text{CPU 연산 비용} + text{페이지 읽기 비용}
CPU 연산 비용을 예측하는 데에는 cpu_tuple_cost와 cpu_operator_cost 파라미터가 사용되고, 페이지 읽기 비용을 예측하는 데에는 seq_page_cost 파라미터가 사용됩니다. 각 파라미터의 설명은 링크를 따라가 보시면 볼 수 있습니다.
Index Scan 비용 계산법
Sequential Scan과 다르게 Index Scan의 경우 Start-up Cost 발생합니다. Start-up Cost에 대한 대략적인 공식은 아래와 같이 정의할 수 있습니다.
text{Start-up Cost} = text{인덱스
탐색 비용} + text{인덱스 페이지 읽기 비용}
인덱스 탐색 비용은 Index Leaf Page 중 스캔을 시작한 위치를 찾기 위해 소요되는 비용입니다. 인덱스 페이지 읽기 비용은 탐색 후 찾아낸 Leaf Page를 읽는 비용입니다. PostgreSQL의 버전이 바뀌면서 Start-up Cost 계산하는 데 영향을 주는 요소들이 지속적으로 변경되었지만 큰 틀에서의 계산 방식은 위 공식 대로 수행됩니다.
Index Scan의 Run Cost를 구하는 공식은 큰 틀에서 Sequential Scan의 것과 동일합니다.
text{Run Cost} = text{CPU 연산 비용} +text{페이지 읽기 비용}
다만 Index Scan Run Cost 경우 각 항을 구성하는 요소에 인덱스 페이지와 튜플을 처리하는 비용이 추가됩니다.
begin{align}
text{CPU 연산 비용} &= text{인덱스 튜플 연산 비용}
newline
&+ text{테이블 튜플 연산 비용}
newline
text{페이지 읽기 비용} &= text{인덱스 페이지 읽기 비용} newline &+ text{테이블 페이지 읽기 비용} end{align}
인덱스와 테이블 튜플을 연산할 때는 선택도(Selectivity)와 조건문(Predicate) 계산 비용이 요소로 들어가게 됩니다. 선택도는 데이터 전체 범위 중 조건문에 의해 선택될 범위의 비율 대한 예측 값이며 미리 수집된 통계정보를 통해 값을 예측하게 됩니다. 조건문 계산 비용의 경우 인덱스 튜플을 연산할 때는 인덱스 키 계산에 대한 비용이 들어가며 테이블 튜플을 연산할 때는 필터링 조건문 계산에 대한 비용이 들어가게 됩니다. 연산 비용을 계산할 때는 cpu_index_tuple_cost와 cpu_tuple_cost 파라미터를 사용합니다.
begin{aligned}
text{(1)}&= text{선택도}times
(text{cpu_index_tuple_cost} + text{조건문 계산 비용}) timestext{인덱스 튜플 수}
newline
text{(2)}&= text{선택도}times
(text{cpu_tuple_cost} + text{조건문 계산 비용}) timestext{테이블 튜플 수}
end{aligned}
마지막으로 페이지 읽기 비용에는 Sequential Scan과는 다르게 Random I/O에 대한 고려가 들어가게 됩니다. 인덱스 페이지의 접근은 항상 임의적으로 이뤄진다고 가정하며 테이블 페이지의 경우 인덱스와의 상관 관계(Correlation)에 따라 Random I/O의 비율이 정해진다고 가정합니다. Random I/O에 대한 비용은 random_page_cost 파라미터로 조절할 수 있습니다.
begin{aligned}
text{(3)} &= text{선택도} times text{인덱스 페이지 수} times
text{random_page_cost}
newline
text{(4)} &= text{최대 읽기 비용} + (text{상관 관계})^{2} times (text{최저 읽기 비용} – text{최대 읽기 비용})
end{aligned}
여기서 최대 읽기 비용은 모든 페이지에 대해 Random I/O가 발생했을 때의 비용이고, 최저 읽기 비용은 한 페이지에 대해서만 Random I/O가 발생하고 나머지 페이지는 순차 읽기가 발생할 때의 비용으로 계산됩니다. 따라서 인덱스 튜플이 정렬되어 있는 순서와 테이블 튜플의 저장 위치 순서와의 상관 관계가 좋을수록 (즉, 1에 가까울수록) 읽기 비용은 최저 읽기 비용에 가까워지며, 상관 관계가 나쁠수록 최대 읽기 비용에 가까워지게 됩니다.
인덱스와 테이블 사이의 상관 관계는 pg_stats 카탈로그를 통해 확인할 수 있습니다.
postgres=# select attname, correlation from pg_stats where tablename=’tbl_corr’;
attname | correlation
———-+——————–
col_asc | 1
col_rand | 0.0022713623
col_desc | -1
(3 rows)
인덱스 튜플과 테이블 튜플의 저장 순서가 동일한 경우 상관 관계의 값은 1, 순서가 역순인 경우 상관 관계의 값은 -1, 순서가 무작위한 경우 0에 가까운 값을 갖게 됩니다.
정렬 비용 계산법
마지막으로 정렬 오퍼레이션의 비용 계산법을 살펴보겠습니다. 우선 정렬 오퍼레이션은 Query 처리 도중 정렬이 필요할 때 사용됩니다. 대표적인 예로는 사용자가 ORDER BY 구문을 사용했을 때이고, 그 외에도 머지 조인(Merge Join)을 수행하거나 그룹핑(Grouping) 함수를 계산해야 할 때도 내부적으로 정렬 오퍼레이션이 사용되게 됩니다.
정렬 오퍼레이션 수행 시 정렬 대상 데이터의 크기가 work_mem 파라미터가 허용하는 메모리 크기보다 작으면 단순히 퀵 정렬(Quick Sort)을 사용하여 정렬을 수행하게 됩니다. 반대의 경우에는 임시 파일을 생성하여 부분 정렬 결과를 저장해야 하게 되어 임시 파일에 대해 합병 정렬(Merge Sort)을 사용해 정렬을 수행하게 됩니다.
정렬 대상 데이터의 크기가 work_mem 보다 작은 경우 Start-up Cost와 Run Cost는 각각 퀵 정렬에 소요되는 비용, 정렬된 튜플을 읽을 때 소요되는 비용이 됩니다. 정렬 대상 튜플 수를 $N$이라고 했을 때 Start-up Cost Run Cost는 아래와 같으며 CPU 연산 비용에는 cpu_operator_cost 파라미터가 사용됩니다.
begin{aligned}
text{Start-up Cost} &= text{비교 비용}
times N log(N)
newline
&= (2 times text{cpu_operator_cost})
times N log(N)
newline
text{Run Cost} &=
text{cpu_operator_cost} times N
end{aligned}
정렬 대상 데이터의 크기가 work_mem 보다 작을 경우 다상 병합 정렬(Polyphase Merge Sort)을 사용합니다. 다상 병합 정렬을 사용하더라도 키 비교 횟수는 퀵 정렬 시와 동일하기 때문에 Run Cost는 퀵 정렬 시와 동일합니다. 다만 파일을 병합하면서 튜플을 읽고 쓰는 디스크 트래픽 비용이 발생하기 때문에 Start-up Cost 디스크 트래픽 비용을 더하여 계산해줍니다. 병합 정렬 시 동시에 사용되는 테이프 수를 M, 초기에 만들어진 테이프 수를 r이라고 했을 때 디스크 트래픽 비용은 아래와 같이 정의됩니다.
text{디스크 트래픽 비용} = 2 times text{정렬 대상 페이지 수} times log_{M} r
Reference.
https://www.interdb.jp/pg/pgsql03.html
https://github.com/postgres/postgres/blob/master/src/backend/optimizer/path/costsize.c
지금까지 PostgreSQL의 쿼리 엔진_ Optimizer에 관해 알아보았습니다
‘PostgreSQL의 쿼리 엔진_ Executor’편을 바로 이어서 확인해보세요!
