MySQL vs PostgreSQL, 조인의 불확실성과 엔진별 한계

ORM이 보편화되면서 백엔드 개발자들은 select_related나 joinedload(JPA에서는 JOIN FETCH)를 통해 손쉽게 두 테이블을 INNER JOIN으로 엮어냅니다. 그리고 "옵티마이저가 알아서 쿼리를 최적화하여 필요한 데이터만 조인하겠지"라고 기대합니다. 하지만 데이터베이스가 감당해야 할 데이터가 수백만 건을 넘어가고, 넓은(Wide) 테이블에 깊은 페이지네이션(Deep Pagination)이 결합하는 순간 이 기대는 처참히 무너집니다.

이 글에서는 PostgreSQL과 MySQL(InnoDB)의 내부 아키텍처를 바탕으로, RDBMS 조인이 태생적으로 안고 있는 구조적 한계와 알고리즘의 맹점을 이론적으로 분석해 봅니다.

---

관계 대수의 제약과 의미론적 장벽(Semantic Barrier)

Pagination을 LIMIT&OFFSET으로 구현해야하는 경우가 있습니다. 해당 Pagination 쿼리에서 JOIN까지 수행해야하는 경우 우리는 RDBMS가 JOIN을 수행하기 전에 데이터를 먼저 추려서(LIMIT&OFFSET기준으로) JOIN을 할거라고 기대하기도 합니다. 하지만 이것은 큰 착각인데, SQL 표준의 엄격한 의미론적 장벽(Semantic Barrier)때문에 이는 수학적으로 불가능하기 때문입니다.

 

의미론적 장벽(Semantic Barrier)은 바로 SQL 표준이 규정하는 논리적 실행 순서(Logical Execution Order)와 관계 대수의 결과 무결성을 지키기 위해 옵티마이저가 넘지 못하는 선을 뜻합니다. SQL은 우리가 쿼리를 작성한 순서대로 실행되지 않습니다. RDBMS는 SQL을 파싱한 뒤, 수학적인 관계대수의 규칙에 따라 논리적 실행 순서를 밟습니다. 일반적으로 FROM -> JOIN -> WHERE -> SELECT -> ORDER BY -> LIMIT/OFFSET 순서를 따릅니다.

 

아래와 같은 쿼리가 있다고 해봅시다.

SELECT review.*, product.*
FROM review
INNER JOIN product ON review.product_id = product.id
WHERE 
    review.client_id = 1 
    AND review.review_type = 1 
    AND review_status = 1
LIMIT 100 OFFSET 200
ORDER BY review.sort_order DESC

 

의미론적 장벽을 알지 못하면 이렇게 생각할 수 있습니다. "어차피 100개만 볼 건데, review 테이블에서 인덱스 타서 조건에 맞는 100건만 먼저 쏙 빼낸(LIMIT) 다음에, 그 100개만 product 테이블이랑 JOIN 하면 메모리도 덜 먹고 엄청 빠르지 않을까?" 이처럼 연산의 순서를 논리적 순서보다 앞당겨서 처리하는 것을 푸시다운(Pushdown)이라고 합니다. 하지만 여기서 옵티마이저를 가로막는 것이 바로 의미론적 장벽(Semantic Barrier)입니다.

 

옵티마이저가 쿼리의 의미(Semantic)와 결과의 정합성을 보장하려면 다음 상황을 반드시 고려해야 합니다.

1. 만약 review 테이블에서 먼저 100건을 추려냈다고 가정해 봅시다.
2. 그런데 이 100건을 product 테이블과 INNER JOIN 하거나 WHERE 조건을 검사하는 과정에서, 조건에 맞지 않는 데이터가 20건 탈락(Elimination)해 버렸습니다.
3. 결국 최종 결과는 80건이 되어버리고, 이는 사용자가 요청한 LIMIT 100이라는 결과의 무결성(Deterministic Guarantee)을 정면으로 위반하게 됩니다.

이러한 관계 대수의 제약 때문에, PostgreSQL과 MySQL의 옵티마이저는 완벽한 1:1 카디널리티(100% 매칭 보장)가 수학적으로 증명되지 않는 이상 LIMIT 연산을 조인 아래로 밀어 넣지(Pushdown) 못합니다.

 

결과적으로 옵티마이저는 쿼리의 의미(Semantic)를 안전하게 지키기 위해, 두 테이블을 완전히 조인하여 SELECT 절에 명시된 모든 '넓은 컬럼'들을 포함한 거대한 중간 결과셋을 메모리에 전부 생성한 뒤에야 비로소 ORDER BY와 LIMIT을 시도하는 보수적인 실행 계획을 강제받게 됩니다.

---

정렬의 알고리즘 복잡도와 메모리 스필 (Disk Spill)

의미론적 장벽에 의해 거대한 중간 결과셋이 만들어지면, DB는 ORDER BY를 수행하기 위해 정렬 알고리즘을 가동합니다. 여기서 대표적인 두 DB엔진인 MySQL 과 PostgreSQL의 물리적 메모리 한계가 적나라하게 드러납니다.

 

처리해야 할 데이터의 크기가 할당된 인메모리 버퍼를 초과하여 디스크 공간을 임시로 빌려 쓰는 현상을 메모리 스필(Memory Spill)이라고 합니다. 정렬의 시간 복잡도는 O(logN)인데, 넓은 튜플 전체가 메모리에 적재되는 순간 RAM 속도로 동작하던 연산이 느린 디스크 I/O 속도로 추락하게 됩니다.

메모리를 벗어난 큰 규모의 쿼리는 Disk Spill 을 하게 된다.

개인적인 경험을 이야기하자면, 2021년에 온프레미스로 돌아가는 MySQL이 계속 문제를 일으켜서 점검해본결과 메모리 스필에 활용한 Disk 공간이 모두 차서 쿼리를 실행하지 못하는 경우를 겪었습니다. 원인을 파악해서 해당 Disk 영역을 일단 비우고, 공간을 확장하는걸로 버그를 해결했었습니다. 그때 처음 Disk Spill 현상을 알게 되었습니다.

MySQL: filesort와 Addon Fields

MySQL 역시 sort_buffer_size 내에서 정렬을 시도합니다. 오프셋(OFFSET)이 작을 때는 메모리 내에서 힙 정렬(Priority Queue)을 통해 효율적으로 처리합니다.

MySQL 정렬 메커니즘

하지만 깊은 페이징(예: OFFSET 10,000)이 발생하면 큐(Queue) 내부에 유지해야 할 엘리먼트 수가 10,100개로 급증합니다. 이때 넓은 테이블의 조인으로 인해 정렬 키 외의 나머지 컬럼(Addon fields) 볼륨이 너무 커지면, MySQL은 인메모리 큐 최적화를 완전히 포기해 버립니다. 그 결과 임시 파일을 디스크에 생성하고 다중 패스 병합을 수행하는 무거운 Using filesort가 발생하며 디스크 I/O 대역폭을 집어삼킵니다.

---

PostgreSQL: tuplesort.c

PostgreSQL의 실행 계획기(costsize.c)는 정렬 비용을 수학적으로 O(logN) 복잡도로 계산합니다. 정렬은 tuplesort.c 모듈에서 수행되는데, 이때 사용되는 SortTuple 구조체는 정렬 키와 함께 원본 튜플의 페이로드(데이터 본체)를 가리키는 포인터(void *tuple)를 메모리에 통째로 적재합니다.

PostgreSQL 정렬 메커니즈

조인된 테이블에 거대한 텍스트나 JSONB 컬럼이 있다면, 메모리에 적재되는 튜플의 바이트(Byte) 너비가 폭증합니다. 특히 TOAST(The Oversized-Attribute Storage Technique)로 압축된 데이터가 메모리상에 풀리면서(Detoast) 할당된 work_mem 한계치를 순식간에 돌파해 버립니다. 결국 엔진은 메모리 정렬을 포기하고, 데이터를 디스크의 논리적 테이프(logtape.c)에 썼다 지웠다 하며 병합하는 external merge Disk 상태로 추락합니다.

---

물리적 스토리지 아키텍처에 따른 I/O 병목

정렬 이전, 데이터를 디스크에서 퍼 올리는 스캔(Scan) 단계에서도 두 RDBMS는 스토리지 아키텍처의 차이로 인해 각기 다른 치명적 병목을 겪습니다.

• PostgreSQL (Append-Only Heap & MVCC의 덫): PostgreSQL의 인덱스 리프 노드는 실제 데이터가 아닌, 힙(Heap) 테이블을 가리키는 물리적 주소표인 TID(Block + Offset)만을 가집니다. 게다가 다중 버전 동시성 제어(MVCC) 때문에, 인덱스에서 찾은 튜플이 현재 트랜잭션에서 유효한지(Visibility) 확인하려면 힙 테이블의 xmin/xmax 헤더를 반드시 열어봐야 합니다. 깊은 페이징으로 10,000개의 튜플을 조회해야 한다면, 엔진은 10,000번의 인덱스 스캔과 10,000번의 무작위 힙 페이지 조회(Random Heap Fetch)를 발생시키며 디스크 I/O를 혹사시킵니다.
• MySQL (InnoDB 클러스터링 인덱스의 Double Lookup): MySQL은 기본키(PK) B+Tree 리프 노드에 전체 데이터를 직접 저장하는 클러스터링 인덱스 구조를 가집니다. 따라서 세컨더리 인덱스로 조인을 수행하면 1차로 논리적 PK를 얻어내고, 그 PK를 들고 원본 트리(Clustered Index)를 다시 수직 탐색해야 하는 더블 룩업(Double Lookup) 페널티가 발생합니다. 10,000번의 오프셋을 처리하기 위해 무거운 B+Tree를 20,000번 오르내려야 하는 구조적 한계에 부딪힙니다.

---

글을 마치며

결국, 네이티브 RDBMS 조인은 논리적으로나 물리적으로 '넓은 테이블 + 깊은 페이지네이션'이라는 안티 패턴을 방어할 수 없습니다. 그렇다면 우리는 이 거대한 디스크 I/O와 CPU 스파이크를 어떻게 막아내야 할까요? 가장 좋은건 애초에 이런 JOIN 이 발생하지 않도록 데이터베이스 설계가 최적화되어있는 것입니다. 혹은 LIMIT&OFFSET Pagination 을 사용하지 않는거죠.

하지만 실무에서는 이렇게 깔끔하게 문제를 풀어낼 수 있는 경우는 많지 않은것 같습니다. 거대한 레거시와 현실적인 기간의 제약 때문이지요. 다음 글에서는 이 구조적 한계를 '어플리케이션 레벨 조인(Application-Level Join)'으로 끊어내고 API 성능을 4배 끌어올린 실전 트러블슈팅 사례를 소개합니다.