“쿼리 튜닝”이라는 단어가 사라질 날이 올까?

솔직히 말해보자. 우리 중 누구도 SELECT 절 안에 또 다른 SELECT가 들어가는 Correlated Subquery(상관 서브쿼리)를 좋아하지 않는다. 코드 리뷰 때 그런 쿼리가 보이면 “이거 조인으로 바꾸세요”라고 코멘트를 다는 게 시니어 엔지니어의 일상이다. 하지만 현실은 어떤가? 우리가 쓰는 Hibernate, JPA, Django ORM들은 뒤에서 끔찍한 중첩 쿼리를 쏟아낸다.

최근 CMU 데이터베이스 강의 자료 목록을 뒤적이다가 Thomas Neumann 의 2025년 BTW 컨퍼런스 논문인 “Improving Unnesting of Complex Queries” 를 발견했다. Thomas Neumann이 누구인가. HyPer와 Umbra DB를 만든, 현존하는 쿼리 옵티마이저 계의 ‘괴물’이다. 그가 또다시 Unnesting(중첩 해제) 주제를 들고 나왔다는 건, 아직도 이 분야에 쥐어짤 성능이 남았다는 뜻이다.

오늘은 이 논문의 맥락을 바탕으로, 데이터베이스가 어떻게 우리의 똥 쿼리(?)를 황금 같은 실행 계획으로 바꾸는지, 그리고 왜 시니어 엔지니어가 이 원리를 알아야 하는지 이야기해 보려 한다.

---

1. 문제는 언제나 $O(N^2)$이다

가장 기본적인 상관 서브쿼리를 생각해보자. 외부 테이블의 각 행(Row)마다 내부 쿼리가 실행되는 구조다. CS 전공자라면 본능적으로 거부감을 느낄 것이다. 이건 Nested Loop 다. 외부 테이블이 100만 건이면, 내부 쿼리도 100만 번 돈다. 인덱스가 아무리 좋아도 망하는 지름길이다.

과거의 DB 옵티마이저들은 멍청했다. 정말로 루프를 돌렸다. 그래서 우리는 “서브쿼리 절대 금지”를 십계명처럼 외우고 다녔다. 하지만 Neumann이 2015년에 발표했던 “Unnesting Arbitrary Queries” 이후, 현대적인 DB 엔진(특히 DuckDB, Umbra, 최신 PostgreSQL 등)은 상황이 달라졌다.

2. Unnesting의 마법: Apply 연산자 제거하기

이 논문과 Neumann의 접근 방식의 핵심은 ‘Apply’ 연산자의 제거 다. Apply는 프로그래밍 언어의 map 함수와 비슷하다. 각 튜플에 대해 함수(서브쿼리)를 적용하는 것이다.

옵티마이저의 목표는 이 Apply를 우리가 사랑하는 Join으로 바꾸는 것이다. 논문에서 다루는, 그리고 우리가 알아야 할 핵심 기법은 다음과 같다.

Dependent Join의 해체

상관 서브쿼리는 논리적으로 Dependent Join 이다. 오른쪽(서브쿼리)이 왼쪽(외부 쿼리)의 값에 의존한다. Neumann의 방식은 이를 수학적으로 증명된 규칙에 따라 일반적인 Outer Join이나 Semi Join으로 변환한다.

이게 왜 대단하냐면, 단순히 WHERE 절에 있는 서브쿼리뿐만 아니라, SELECT 절에 있는 스칼라 서브쿼리, 심지어 LIMIT이나 ORDER BY가 포함된 복잡한 서브쿼리까지 전부 Set-oriented(집합 기반) 연산으로 바꿔버리기 때문이다.

결과적으로 $O(N^2)$이었던 복잡도가 해시 조인을 통해 $O(N)$에 가깝게 떨어진다. 10분 걸릴 쿼리가 0.1초 만에 끝나는 마법은 여기서 일어난다.

3. 이번 논문(BTW 2025)은 무엇이 다른가?

이미 2015년에 큰 틀은 잡혔다. 이번 2025년 논문(Improving Unnesting…)은 그동안의 엣지 케이스들을 다룬다. 현업에서 쿼리 튜닝을 하다 보면 옵티마이저가 포기하고 Nested Loop로 회귀해버리는 지점들이 있다. 보통 다음과 같은 경우다:

• 서브쿼리 내부에 복잡한 집계 함수가 있을 때
• 비등가 조인(Non-equi join) 조건이 섞여 있을 때
• 윈도우 함수가 중첩되어 있을 때

Neumann은 이번 연구를 통해 이러한 복잡한 케이스에서도 ‘Apply’를 밀어내(Push down)거나, 다른 연산자와 결합하여 Unnesting 할 수 있는 일반화된 알고리즘을 제시한다. 즉, “어떤 거지 같은 쿼리를 짜도 우리는 조인으로 풀어낼 수 있다” 는 자신감의 표현이다.

4. 개발자를 위한 시사점: ORM을 미워하지 마라

나는 주니어 시절, ORM이 만들어내는 쿼리를 보며 “이건 DB에 대한 모독이야!”라고 분노하곤 했다. 하지만 시니어 레벨에 도달하고, 이런 논문들을 보며 생각이 바뀌었다.

“인간은 비즈니스 로직에 집중하고, 최적화는 기계(DB)가 하는 게 맞다.”

우리가 수동으로 쿼리를 힌트(Hint) 떡칠해가며 튜닝하는 건, 컴파일러 최적화를 믿지 못해 어셈블리어를 직접 짜는 것과 비슷해지고 있다. 물론 아직 모든 DB가 Neumann의 논문처럼 완벽하게 구현되어 있진 않다. MySQL이나 구버전 DB를 쓴다면 여전히 서브쿼리는 주의해야 한다.

하지만 트렌드는 명확하다. DuckDB나 최신 상용 데이터웨어하우스들은 이미 이런 기법을 적극 도입하고 있다. 여러분이 작성한 복잡한 중첩 쿼리가 느리다면, 쿼리를 고치기 전에 실행 계획(EXPLAIN)을 먼저 봐라. 만약 Dependent Join이나 Nested Loop가 보인다면, 그건 여러분의 잘못이라기보단 DB 옵티마이저가 아직 Neumann의 논문을 덜 읽어서일 수도 있다.

결론: 기술의 끝은 ‘추상화’다

Thomas Neumann의 연구가 우리에게 주는 메시지는 명확하다. SQL은 ‘무엇(What)‘을 원하는지 기술하는 언어지, ‘어떻게(How)’ 가져올지 기술하는 언어가 아니라는 점이다.

복잡한 Unnesting 알고리즘이 발전할수록, 우리는 더 직관적이고 유지보수하기 쉬운 SQL(혹은 ORM 코드)을 작성해도 성능 저하를 겪지 않게 될 것이다. 그러니 가끔은 머리 아픈 쿼리 튜닝 대신, 최신 DB 엔진의 릴리즈 노트를 읽어보자. 그곳에 진짜 성능 향상의 열쇠가 있을지도 모른다.