PostgreSQL Query Optimization : 더 깊은 이론 - 알고리즘

1. 알고리즘 비용 모델

효율적인 쿼리 실행을 위해 알고리즘의 실행 비용을 이해하는 것이 중요합니다. 데이터베이스는 쿼리 실행 시 다양한 알고리즘을 활용하며, 각 알고리즘은 데이터의 크기, 분포, 인덱스 사용 여부 등에 따라 성능이 크게 달라질 수 있습니다.

 

2. 데이터 접근 알고리즘
데이터베이스는 데이터를 접근하는 여러 가지 알고리즘을 제공합니다. 주요 접근 방식은 다음과 같습니다:

1. 전체 스캔(Full Scan)
   테이블의 모든 행을 읽는 방식으로, 특정 조건을 만족하는 데이터를 찾을 때 사용됩니다. 대량의 데이터가 있는 경우 비효율적일 수 있습니다.
2. 인덱스 기반 접근(Index-Based Table Access)
   테이블에 인덱스가 존재하는 경우, 조건에 맞는 데이터를 빠르게 검색할 수 있습니다.
   SELECT * FROM flight WHERE departure_airport = 'ORD';
3. 인덱스 전용 스캔(Index-Only Scan)
   쿼리가 필요한 데이터가 모두 인덱스에 포함되어 있을 때, 테이블 데이터를 읽지 않고 인덱스만으로 작업을 완료합니다.
4. 비교
   • 전체 스캔은 데이터 크기가 작을 때 효율적입니다.
   • 인덱스 스캔은 조건에 따라 데이터가 잘 분포되어 있을 때 효과적입니다.

 

3. 인덱스 구조
인덱스는 데이터 검색 속도를 높이기 위해 설계된 데이터 구조입니다. PostgreSQL에서 제공하는 주요 인덱스 유형은 다음과 같습니다:

1. B-트리(B-Tree)
   • 가장 널리 사용되는 인덱스 유형입니다.
   • 데이터가 순서대로 정렬되어 있어 범위 검색과 정렬 작업에 적합합니다.
2. 비트맵(Bitmap)
   • 대량 데이터에 적합하며, 여러 조건을 결합하여 검색할 때 유리합니다.
3. 기타 인덱스
   • Hash, GIN, GiST, SP-GiST, BRIN
     JSONB나 텍스트 검색에 활용하는 특수 목적의 인덱스도 있습니다.

        인덱스에 대해서는 상세하게 다루기 위해 별도 포스팅 하겠습니다.

 

4. 관계 결합 알고리즘(Join Algorithms)
테이블 간의 데이터를 결합하는 다양한 알고리즘이 있습니다:

1. 네스티드 루프(Nested Loops)
   • 두 테이블의 모든 행을 반복적으로 결합합니다.
   • 작은 데이터 집합에서는 효과적이나, 데이터가 많으면 성능이 저하됩니다.
2. 해시 조인(Hash Join)
   • 한 테이블에서 해시 테이블을 생성하고, 다른 테이블의 데이터를 검색합니다.
   • 대량의 데이터를 처리하는 데 적합합니다.
3. 정렬-병합 조인(Sort-Merge Join)
   • 두 테이블을 정렬한 후 병합합니다.
   • 정렬된 데이터에 효과적입니다.
4. 비교
   • 네스티드 루프는 소규모 데이터에 적합합니다.
   • 해시 조인은 대량 데이터 처리 시 유리합니다.
   • 정렬-병합은 정렬된 데이터에서 좋은 성능을 보입니다.

 

5. 알고리즘 비교와 선택
알고리즘 선택은 데이터 크기, 분포, 인덱스 존재 여부에 따라 달라집니다. PostgreSQL 옵티마이저는 이러한 조건을 기반으로 가장 효율적인 알고리즘을 자동으로 선택합니다.

 

각 알고리즘은 특정 상황에서 유리하며, PostgreSQL 옵티마이저는 이를 자동으로 최적화합니다.

개발자는 이러한 알고리즘을 이해하고 쿼리를 작성할 때 이를 고려해야 합니다.

 

Next : PostgreSQL Query Optimization : 실행 계획 이해하기

 

참고문헌 : PostgreSQL Query Optimization