PostgreSQL: 동등 조건과 범위 조건의 선택도 추정 방식 분석

※ PostgreSQL: An In-Depth Analysis of Selectivity Estimation for Equality and Range Conditions.

※ Version: PostgreSQL 17.

 

안녕하세요. 듀스트림입니다.

 

오늘 포스팅은 조금 심도 있는 내용입니다.

 

PostgreSQL의 옵티마이저에 대한 이해도를 높이고 통계 기반 실행 계획 최적화 전략을 세우기 위하여 동등 조건(=)과 범위 조건(<, >, BETWEEN)에 대한 선택도 추정 방식을 알아보겠습니다.

---

1. 선택도 추정 이해를 위한 배경 지식

1.1 선택도 (Selectivity)

• 특정 조건이 전체 행에서 몇 %의 데이터를 필터링할지를 나타내는 값 (0~1 사이)

-- 공식
selectivity = 조건을 만족하는 예상 행 수 / 전체 행 수

-- 예.
전체 10000건
조건 만족 3000건
→ 선택도 = 3000 / 10000 = 0.3

• 옵티마이저는 이 값을 바탕으로 인덱스 사용 여부, Join 전략 등을 판단
• 파티션 테이블의 선택도 계산은 각 파티션 테이블의 통계를 독립적으로 사용하여 계산하고, 필요 시 프루닝을 통해 최종 row 수와 비용을 추정
  • 먼저 파티션 프루닝 수행 → 각 파티션마다 pg_statistic에 따로 저장된 통계를 사용 (대상 파티션만 선택도 계산)
  • 파티션 간 데이터 분포가 매우 다르면 옵티마이저의 오판 가능성 존재 (skew된 파티션은 개별 통계 또는 튜닝 필요)
  • 여러 파티션 접근 시, 옵티마이저는 각 파티션별 선택도를 추정한 후 합산
  • 각 파티션의 행 수 × 그 파티션에서의 선택도를 합산한 후 전체 행 수로 나눠 가중 평균 선택도를 추정

-- 단일 파티션 접근 시
selectivity_total = selectivity_partition_X

-- 여러 파티션 접근 시 (예. region IN ('KR', 'JP'))
selectivity_total = ∑ (rows_partition_i × selectivity_i) / total_partitioned_rows

---

1.2 MCV (Most Common Values) & most_common_freqs

• MCV: 해당 컬럼에서 자주 등장하는 상위 값 리스트
• most_common_freqs: 각 MCV에 대한 상대적 등장 비율
• 예. gender 컬럼의 MCV = ['M', 'F'], freq = [0.6, 0.4]
• MCV는 기본 통계 수집 대상이며, default_statistics_target에 따라 수집 개수 증가 가능

---

1.3 n_distinct

• 해당 컬럼에 대해 ANALYZE 시 수집된 고유 값의 개수(distinct values)에 대한 예측값
  (Oracle의 NDV(Number of Distinct Values)와 유사한 개념)
• PostgreSQL에서는 이를 통계 수집 및 실행 계획에 간접적으로 반영하기 위한 예측 계수값으로 저장함
• n_distinct는 양수 또는 음수로 저장됨
  
  • 양수일 경우: 실제 고유값 개수 (예: n_distinct = 42)
  • 음수일 경우: 테이블 row 수에 대한 비율로서의 NDV (예: n_distinct = -0.5 → 전체 row 수의 50%)

• PK나 UNIQUE 키의 n_distinct 값:

예시	결과
id SERIAL PRIMARY KEY	n_distinct = -1로 나옴 → row 수만큼 고유
email TEXT UNIQUE	데이터가 고르게 분포되어 있다면 역시 n_distinct = -1 또는 매우 큰 수치

---

1.4 histogram_bounds

• 연속형 데이터(숫자, 날짜 등)에 대해 값의 분포를 일정 구간(Slice)으로 나눔
• 기본적으로 최대 100개 경계값 수집 → 99개의 구간
• 범위 조건에 대한 선택도는 해당 구간을 몇 개 포함하는지를 비율로 계산함

---

1.5 null_frac

• NULL 값이 차지하는 비율
• 조건에서 IS NOT NULL 또는 = 비교시 제외되는 비율 고려 필요

---

1.6 PostgreSQL의 컬럼별 통계 수집 순서

1. null_frac: NULL 비율
2. n_distinct: 고유 값 개수
3. MCV 목록: 가장 자주 등장하는 값들 (max 100개 정도)
4. 히스토그램: MCV를 제외한 나머지 값들의 분포

---

1.7 통계 수집 주기 및 정확도 향상 방법

• 통계는 ANALYZE 또는 VACUUM ANALYZE, AUTOVACUUM로 수집됨
• DML 이후 통계를 갱신하지 않으면 옵티마이저는 부정확한 선택도로 잘못된 계획을 수립할 수 있음
• default_statistics_target을 skew가 심한 컬럼에 대해 높이면 MCV/히스토그램 정확도가 향상됨
• 고급 통계 수집을 위한 CREATE STATISTICS 명령으로 다중 컬럼 상관 통계 생성 가능

---

2. 동등 조건 선택도 추정 (=)

2.1 MCV에 포함된 값일 경우

2.1.1 단일 조건

SELECT * FROM users WHERE city = 'Seoul';

• 'Seoul'이 MCV 목록에 있고 빈도수가 0.25라면 선택도 = 0.25

---

2.1.2 다중 조건

-- 공식
selectivity = selectivity(a = x) × selectivity(b = y)

• 기본 규칙: 독립 가정(Independence Assumption)
  → PostgreSQL은 기본적으로 조건들 간에 통계적 독립이 있다고 가정하고 선택도를 곱해서 최종 선택도를 계산

-- 예.
SELECT * FROM users WHERE a = 'x' AND b = y;

a = x 의 선택도 = 0.1
b = y 의 선택도 = 0.05
→ 최종 선택도 = 0.1 × 0.05 = 0.005 (0.5%)

 

※ 한계점

• 실제로는 a와 b가 강하게 상관되어 있을 수 있음 (예. a = 지역, b = 도시)
• 이런 경우 독립 가정은 선택도를 과소평가하거나 과대평가할 수 있음

 

※ 보완 방법

• CREATE STATISTICS statname (dependencies)로 컬럼 간 종속성을 명시적으로 반영 가능

-- 예.
CREATE STATISTICS stat_dep (dependencies) ON region, city FROM users;

---

2.2 MCV에 포함되지 않은 값일 경우

균등 분포 가정을 기반으로 다음과 같이 계산

-- 공식
선택도 = (1 - sum(most_common_freqs)) / (n_distinct - MCV 수)

• sum(most_common_freqs): MCV 목록에 포함된 값들의 전체 빈도 합계 (예. [0.1, 0.15, 0.2] → 0.45)
• 1 - sum(...): MCV에 포함되지 않은 나머지 값들이 차지하는 비율
• n_distinct: 컬럼의 고유 값 개수 (통계에서 추정된 값)
• MCV 수: MCV 목록의 값 개수
• n_distinct - MCV 수: MCV 외의 나머지 고유 값 개수
• 전체 비율 / 고유값 수 = 선택도: MCV 외 고유 값 중 하나가 선택될 확률 (균등 분포 가정)

-- 예.
n_distinct = 100, sum(most_common_freqs) = 0.4, MCV 수 = 10
→ 선택도 = (1 - 0.4) / (100 - 10) = 0.6 / 90 ≒ 0.00667

---

3. 범위 조건 선택도 추정 (<, >, BETWEEN)

• MCV와 히스토그램 존재 여부 확인 쿼리

SELECT attname,
       most_common_vals IS NOT NULL AS has_mcv,
       histogram_bounds IS NOT NULL AS has_histogram
FROM pg_stats
WHERE schemaname = 'test' AND tablename = 'users';

[그림 1] MCV, 히스토그램 체크

 

3.1 히스토그램 기반 추정

-- 공식
선택도 = (i + f) / (n - 1)

• n: histogram_bounds 배열의 길이 (즉, 구간 개수 + 1)
• i: 조건을 완전히 만족하는 구간 개수
• f: 조건 값을 포함한 마지막 구간에서의 부분 포함 비율

-- 예.
히스토그램 경계: [10, 20, 30, 40, 50]
조건: age < 35

선택도 = (2 + 0.5) / 4 = 0.625

---

3.2 히스토그램 외부 값의 처리

• 조건 값이 히스토그램 경계보다 작거나 크면 선택도는 0 또는 1에 가까움

---

 

3.3 MCV + 히스토그램 혼합 조건 처리

-- 공식
selectivity = mcv_selectivity + (1 - null_frac - sum(mcv_freqs)) × histogram_range_selectivity

• mcv_selectivity:
  MCV 목록 내에서 조건을 만족하는 값들의 선택도 (MCV 값 중 조건을 만족하는 값들의 freq를 합한 것)
• null_frac:
  컬럼 내 NULL 값의 비율 (조건절에서 NULL은 매칭되지 않으므로, 전체에서 제외됨)
• sum(mcv_freqs):
  MCV에 포함된 값들의 전체 등장 비율 (MCV에 속한 값들은 이미 선택도 계산에 포함됐기 때문에 나머지 값만 히스토그램으로 추정)
• histogram_range_selectivity:
  히스토그램 기반으로 계산된 범위 조건의 선택도 (histogram_bounds를 기준으로 조건을 만족하는 구간의 비율 (예. < 35 등))

-- 예.
mcv_selectivity = 0.12
null_frac = 0.05
sum(mcv_freqs) = 0.30
histogram_range_selectivity = 0.40
→ selectivity = 0.12 + (1 - 0.05 - 0.30) * 0.40 = 0.38

• MCV 목록 내에 있는 값들의 선택도를 합한 후 히스토그램 기반의 선택도를 곱해서 최종 선택도를 구함

---

3.4 MCV만 존재하는 경우

• 범위 조건에서 MCV만 존재하고 히스토그램이 없는 경우는 매우 제한적이지만 있을 수도 있음

 

※ 조건

• 컬럼의 고유 값 수가 적고 대부분이 MCV에 포함되는 경우
• 나머지 데이터가 너무 적어서 샘플링 히스토그램을 생성할 수 없는 경우

 

※ 옵티마이저의 최종 선택도 계산 방법

• MCV 값 중 조건에 해당하는 값들의 freq만 합산

-- 공식
mcv_selectivity = freq(A) + freq(B) + ... (조건을 만족하는 MCV만 합산)

• 히스토그램이 없기 때문에 나머지 값에 대한 범위 추정은 못함 (과소 추정 위험)

---

3.5 시나리오별 대응 방법

시나리오	대응 방법
고유 값 수가 적어서 히스토그램이 생략됨	MCV 기반 필터링만 적용되므로 대응 필요없음
고유 값은 많지만 통계가 부정확	ANALYZE 수동 실행 또는 default_statistics_target 증가
복합 조건 또는 skew 분포	CREATE STATISTICS ... (mcv, histogram) 추천

---

4. 예제

4.1 데이터 생성 & ANALYZE

CREATE SCHEMA test;

CREATE TABLE test.users (id SERIAL, city TEXT, age INT);

INSERT INTO test.users
SELECT i,
       CASE WHEN i % 4 = 0 THEN 'Seoul'
            WHEN i % 4 = 1 THEN 'Busan'
            WHEN i % 4 = 2 THEN 'Daegu'
            ELSE 'Incheon' END,
       (RANDOM() * 100)::INT
FROM generate_series(1, 100000) i;

ANALYZE users;

---

4.2 pg_stats 확인

SELECT * FROM pg_stats WHERE schemaname = 'test' AND tablename = 'users';

[그림 2] pg_stats 확인 예제

---

5. 요약 정리

항목	동등 조건	범위 조건
사용 통계	MCV, n_distinct	MCV, histogram_bounds
계산 방식	MCV freq 또는 MCV 외 균등 분포 추정	MCV freq + 히스토그램 구간 기반 비율 계산
히스토그램 사용	❌	✅
핵심 기준	특정 값의 등장 빈도	값의 위치 및 범위 내 비율
장점	skew가 큰 컬럼에 대해 freq 기반 정확도 높음	연속형 숫자 컬럼에서 범위 조건에 유리함
단점	MCV 외 값은 추정 시 균등 분포 가정으로 부정확	구간 수가 적으면 정밀도 낮고 과소/과대 추정 가능
보완 기법	CREATE STATISTICS (mcv, dependencies)	default_statistics_target 증가, 복합 통계 생성

---

6. 최적화 팁

• skew가 심한 컬럼은 default_statistics_target을 500 이상으로 설정
• CREATE STATISTICS로 다중 컬럼 상관 통계 생성 시 Join 조건의 선택도 추정 정확도 향상
• 빈번한 DML 이후에는 ANALYZE로 통계 최신화 필수
• EXPLAIN (ANALYZE, BUFFERS)로 실제 실행 결과와 예상 선택도 간 차이 검증 가능

---

7. CREATE STATISTICS 문법 및 예시

• 목적: 다중 컬럼 간의 상관관계, 조합 빈도, 연속성 등을 고려하여 옵티마이저가 보다 정밀하게 선택도를 추정할 수 있도록 보조하는 통계 정보를 생성.

CREATE STATISTICS 통계이름
    [ ( 종류 [, ...] ) ]
    ON 컬럼1 [, 컬럼2, ...]
    FROM 테이블;

종류	설명
ndistinct	여러 컬럼 조합의 고유 값 수
dependencies	컬럼 간 함수적 종속성 (예. 성별과 호칭)
mcv	다중 컬럼 조합에 대한 MCV 리스트
histogram	다중 컬럼 조합의 분포 히스토그램

---

7.1 예제 1: 컬럼 간 상관관계 기반 Join 선택도 향상

-- dept_id → emp_id 같은 함수적 종속성 추정 가능
CREATE STATISTICS st_dept_emp (dependencies)
ON dept_id, emp_id
FROM emp;

---

7.2 예제 2: Join + Filter 조합 조건 선택도 개선

-- WHERE region = 'KR' AND city = 'Seoul' 같은 복합 조건에서 정확도 향상
CREATE STATISTICS st_region_city (mcv, ndistinct)
ON region, city
FROM users;

-- 확인 방법
SELECT * FROM pg_statistic_ext WHERE stxname = 'st_region_city';

---

8. 히스토그램 수 증가 (default_statistics_target 조정)

• 목적: 히스토그램 구간 수를 늘려서 범위 조건 선택도 추정의 정밀도를 높임
• Default는 100이며, 최대 10000까지 설정 가능

※ 설정 후 ANALYZE 필수!

---

8.1 컬럼 단위 설정

ALTER TABLE sales ALTER COLUMN amount SET STATISTICS 500;

• 테이블 전체에 대해 SET STATISTICS를 적용하려면 각 컬럼에 대해 개별적으로 설정해야 합니다.
• 파티션 테이블은 각 파티션 별로 설정해야 합니다.

---

8.2 전체 설정 (postgresql.conf)

default_statistics_target = 200

---

유용하게 적용하시길 바랍니다~

 

오늘은 여기까지~