SQL 조인 순서 하나 잘못 고르면 연산량 100배 폭증하는 이유

요약 데이터베이스 쿼리 최적화의 핵심 분야 중 하나인 조인 순서 결정(Join Ordering)과 탐색 공간의 크기를 다룬 해외 개발자의 기술 분석 글이 공유되었습니다. 글쓴이는 카네기 멜런 대학교(CMU)의 쿼리 최적화 강좌와 뮌헨 공대(TUM) 학파의 연구를 바탕으로, SQL 엔진 내부에서 여러 테이블을 결합할 때 발생하는 비용 최적화 문제를 깊이 파고듭니다. 작성자에 따르면 SQL 표준이나 교재에는 결과 형태만 정의되어 있을 뿐, 내부적으로 조인이 어떤 순서로 실행되어야 하는지는 쿼리 플래너의 몫으로 남겨집니다. 가령 100만 건짜리 두 테이블과 10건짜리 한 테이블을 조인할 때, 어떤 순서로 묶느냐에 따라 1조 개의 튜플을 생성하는 비효율적인 카테시안 곱이 발생할 수도 있고, 작은 테이블을 먼저 처리해 극도로 저렴하게 끝낼 수도 있어 실행 시간이 100배 이상 벌어지기도 합니다. 하지만 모든 조인 순서를 전수 조사하는 것은 불가능에 가깝습니다. N개의 릴레이션에 대한 조인 트리 조합의 수는 카탈랑 수를 활용한 계산식에 따라 4개일 때는 120개에 불과하지만 15개만 되어도 약 3.5×10^18개로 기하급수적으로 폭증하기 때문입니다. 작성자는 이러한 거대한 탐색 공간을 효율적으로 다루기 위해 DPccp, DPhyp 등 독일 뮌헨 학파 중심의 동적 계획법(DP) 연구 논문 4편을 심층 분석하는 시리즈를 연재하겠다고 밝혔습니다.