PostgreSQL 옵티마이저

개요

• 쿼리를 효율적으로 짜기 위해서는 옵티마이저의 동작원리를 잘 알아야 된다.
• 즉, 옵티마이저의 마음을 이해하는 것이 중요하다.
• 하지만 생각보다 옵티마이저의 동작원리를 이해하는 것은 복잡하고 깊은 내용이다.
• 그렇지만 간단하게라도 옵티마이저에 대해서 정리하고 넘어가려고 한다.

 

먼저 쿼리가 어떤식으로 실행되는지 간단하게 알아보자.

 

 

쿼리 실행 흐름

 

 

Parser

• 입력받은 쿼리의 문법을 검증하고 Parse Tree를 생성한다.

 

Analyzer

• Parser로 부터 전달받은 Parse Tree를 바탕으로 Query Tree를 생성한다.
• pg_catalog에 담겨 있는 정보를 바탕으로 테이블, 칼럼, 제약조건 등에 대한 Sematic 검증을 수행한다.
• Query Tree는 테이블, 칼럼을 참조하기 위한 정보를 포함한다.

 

Rewiter

• Query Tree가 Optimizer에게 전달되기 전에 사용자가 Rule System에 저장한 규칙을 기반으로 Query Tree를 수정한다.

 

Optimizer

• Query Tree에 담긴 참조정보를 바탕으로 데이터를 찾고 아래 3단계를 거쳐서 실행계획을 생성한다.
• Query Transformer
  • 사용자에 의해 제공된 원래 쿼리를 분석하고 변환한다.
  • 쿼리는 더 효율적으로 실행될 수 있도록 재작성될 수 있다. 예를 들어, 서브쿼리는 조인으로 변환될 수 있다.
  • 또한, 필요하지 않은 칼럼을 제거하거나, 쿼리 조건을 간소화하는 등의 최적화가 이루어질 수 있다.
• Cost Estimator
  • 다양한 실행 경로의 비용을 추정한다.
  • 각각의 실행 계획에 대한 비용을 평가하기 위해 데이터베이스의 통계 정보를 사용한다.
  • 비용을 계산하는 방법은 아래에서 좀 더 자세히 살펴보자.
• Plan Generator
  • 비용 추정을 바탕으로 최적의 실행 계획을 선택한다.
  • 여러 가능한 실행 계획 중에서 비용이 가장 낮은 계획을 선정한다.
  • 여기서 결정된 실행 계획은 실제 쿼리를 실행하는 데 사용된다.
• 생성된 Plan Tree를 Executor에게 전달한다.

 

Executor

• Optimizer로 부터 전달 받은 Plan Tree안에 있는 Plan Node들을 순서에 맞시 실행하면서 필요한 Row들을 받아온다.

 

이제 본격적으로 옵티마이저에 대해서 알아보자.

 

옵티마이저란?

옵티마이저는 쿼리를 실행할 때 가장 효율적인 방법을 찾아주는 역할을 한다.

Query 가 수행될 수 있는 모든 실행 경로에 대해서 비교해보고 가장 비용이 적은 실행 경로를 실행계획으로 수립한다.

옵티마이저는 크게 2가지로 유형으로 나뉜다.

• 첫 번째는 RBO(Rule Based Optimizer)이다.
  • RBO는 사전에 정의된 규칙에 의해 실행계획이 수립되는 방식이다.
  • 장점은 실행계획을 예측하기 쉽고, 매우 직관적이다.
  • 단점은 상황에 따라서 비효율적일 수 있다. 사전에 정의된 규칙이 모든 상황에 최적일 수 없기 때문이다.
  • 이러한 단점으로 인해서 RBO 방식의 옵티마이저는 거의 사용되지 않는다.
• 두 번째는 CBO(Cost Based Optimizer)이다.
  • CBO는 말 그대로 비용을 계산하는 방식이다.
  • 이 비용은 통계정보를 바탕으로 계산된다. 따라서 상황에 따라서 가장 비용이 적은 방법을 찾는다.
  • 따라서 요즘 같이 복잡한 환경 속에서 매우 유리한 방식이다.
  • PostgreSQL의 옵티마이저도 CBO 방식이다.
  • 단점은 상황에 따라서 옵티마이저가 실행계획을 수립하기 때문에, 실행계획을 정확히 예측하기 어렵다.

통계정보는 옵티마이저가 실행계획을 세우는 기준이 된다. 따라서 통계정보에 대해서도 알고 넘어갈 필요가 있다.

통계정보

• 옵티마이저는테이블, 인덱스, 칼럼에 대한 통계정보를 바탕으로 비용을 계산한다.
• 통계정보는 pg_class와 pg_stats를 통해서 확인할 수 있다.
• 이제 pg_class와 pg_stats테이블에 있는 데이터를 자세히 살펴보자.

테이블 세팅

• 아래와 같이 employee 테이블이 있다고 가정하고, 데이터는 10000건이 들어있다.

create table employee
(
    employee_id   bigint generated by default as identity
        constraint employee_pkey
            primary key,
    begin_date    varchar(8),
    employee_name varchar(255),
    end_date      varchar(8)
);

pg_class

• pg_class 테이블에는 블록 수와 레코드 수를 확인할 수 있다.

• relpages: 블록 수 84개 (relpages는 테이블이나 인덱스가 차지하는 디스크 상의 블록 수를 말한다)
• reltuples: 튜블 수 10000개

pg_stats

• pg_stats는 PostgreSQL에서 제공하는 시스템 뷰로, 데이터베이스 내의 각 컬럼에 대한 통계 정보를 제공한다.
• pg_stats 테이블에는 NULL값의 비율, 칼럼의 평균 길이, NDV, 컬럼 정렬 상태 등을 확인할 수 있다.

null_frac

• NULL값의 비율을 의미한다.
• 모두 NULL 이면 1, 모두 NULL이 아니면 0이다.
• 만약 30%가 NULL이라면 0.3이다.
• 위 사진에서 보면 employee_id는 pk값이기 때문에 not null이다. 따라서 값이 0인 것을 확인할 수 있다.

 

avg_width

• 칼럼의 평균 길이를 의미한다.
• 이 값은 실행계획에서 width값을 계산할 때 사용된다.

 

n_distinct

• NDV (Number ofDistinct Value)를 의미한다.
• NDV값에 따라 양수 또는 음수로 표현된다.
• NDV가 테이블 건수 대비 10% 이내이면 -(NDV/레코드수)
• 따라서 pk와 같이 전부 유니크한 값이라면 -1이다. employee_id값이 -1인 것을 확인할 수 있다.
• 위 칼럼 중에서 beginDate가 900이라는 의미는 10000건 중에서 고유한 값이 900이라는 의미이다.
• 또한, end_date가 -0.2라는 건, 10000건 중에서 2000건이 고유한 값이라는 의미다. 10%가 넘었기 때문에 음수로 표현되며 소수점으로 표현되는 것이다.
• 고유의 값이 많을수록 인덱스를 효율적으로 사용할 수 있다. 중복값이 너무 많으면 인덱스가 만들어져 있다고 해도 옵티마이저가 인덱스를 사용하지 않을 수 있다.
• 즉, -1에 가까운 값일수록 인덱스의 칼럼으로 선택하기 좋은 칼럼이다.

 

correlation

• 칼럼의 정렬상태를 나타낸다.
• -1 ~ 1 사이의 값으로 표현된다.
• 완벽히 정렬되어있다면 1, 완벽히 역순으로 정렬되어 있다면 -1이다.
• 따라서 정렬이 안되어있으면 0에 가까운 값이다. (1, -1은 가장 정렬이 잘되어있는 값이다.)
• 옵티마이저가 스캔방식을 선택할 때 정렬상태가 중요한 요소로 사용된다.
  • 정렬상태가 불량하면 인덱스가 있다고 하더라도 옵티마이저는 Index Scan 대신 Bitmap Heap Scan을 선택할 확률이 크다.
• 0에 가까울수록 정렬이 안되어 있기 때문에 beginDate가 가장 정렬이 안되어 있는 칼럼이다.

이제 통계정보를 바탕으로 COST를 계산하는 방법을 알아보자.

PostgreSQL의 옵티마이저가 COST를 계산하는 방법

• COST는 크게 IO비용과 CPU비용으로 구분된다.
• 비용을 계산하기 위해서는 계산에 사용되는 파라미터값을 알아야 한다.
• 각각의 파라미터값는 아래와 같다.

• 위와 같이 CPU 비용을 계산하는 파라미터와 I/O 비용을 계산하는 파라미터가 있다.

 

Seq San 비용 계산 방법

Start-Up Cost: 0 (비용 필요 없음)

Run Cost: CPU 연산비용 + 테이블 페이지 I/O 비용

 

• 위 수식은 아래와 같이 정리할 수 있다.
• 테이블 페이지I/O 비용 = repages * seq_page_cost
• CPU 연산 비용 = reltuples * cpu_tuple_cost + reltuples * cpu_operator_cost

• 위 파라미터 정보를 바탕으로 비용을 계산해 보자. 209.00은 Seq Scan으로 84개의 블록을 읽는 I/O 비용 + 10000건을 추출하는 CPU 비용을 뜻한다.

 

Index Scan 비용 계산 방법

Start-Up Cost: 인덱스 탐색 비용 + 인덱스 페이지 I/O 비용

Run Cost: CPU 연산 비용 + 테이블 페이지 I/O 비용

 

• Index Scan 방식은 블록 수와 튜플수 만으로는 계산할 수 없다.
• CPU 연산비용 아래와 같이 좀 더 디테일하게 정리할 수 있다.
  • CPU 연산비용 = 인덱스 튜플 연산 비용 + 테이블 튜플 연산 비용
  • 인덱스 튜플 연산 비용 = 선택도 * (cpu_index_tuple_cost + 조건문 계산 비용) * 인덱스 튜플 수
  • 테이블 튜플 연산 비용 = 선택도 * (cpu_tuple_cost + 조건문 계산 비용) * 테이블 튜플 수
  • 선택도는 쿼리 조건과 일치하는 튜플의 비율을 말한다.
  • 조건문 계산 비용는 쿼리의 WHERE 절 등에 사용된 조건문을 평가하는 데 드는 CPU 비용을 말한다.
• 페이지 I/O 비용도 아래와 같다.
  • 페이지 I/O 비용 = 인덱스 페이지 I/O 비용 + 테이블 페이지 I/O 비용이다.
  • 인덱스 페이지 I/O 비용 = 선택도 * 인덱스 페이지 수 * random_page_cost
  • 테이블 페이지 I/O 비용 = (상관 관계)^2 * (최저 읽기 비용 - 최대 읽기 비용)
  • 최저 읽기 비용은 한 페이지만 랜덤 I/O로 읽고 나머지 페이지는 순차적 I/O로 읽은 비용이다.
  • 최대 읽기 비용은 모든 페이지를 랜덤 I/O로 읽은 비용이다.

위 수식을 보다시피 Index Scan의 경우 비용을 계산하는 방법은 매우 복잡하다. 실제 계산하는 건 우선은 넘어가도록 하자...

 

 

References

• PostgreSQL 9.6 성능이야기, 저자 김시연, 최두원 
• https://oss.tibero.com/eeccc36a-1720-4944-862d-bc4574436ead
• https://oss.tibero.com/6c2ff524-645e-45f2-a05b-0cd409d12a78
• https://www.cybertec-postgresql.com/en/column-correlation-explained/