[DB] CBO는 JOIN 순서를 어떻게 찾는가

주재완·2026년 7월 29일

Database

목록 보기

9/9

1. JOIN 순서 탐색의 입력

이전 포스팅에서는 SQL의 JOIN List가 Binary Join Tree로 바뀌고, CBO(Cost-Based Optimizer)가 Join Graph, Join Hypergraph, Memo와 같은 구조를 이용해 여러 후보를 관리하는 과정을 살펴봤습니다. 이번에 다루는 영역은 다음과 같습니다.

CBO는 가능한 JOIN 순서 중에서 무엇을 실제로 탐색하고, 그중 하나를 어떻게 선택하는가

JOIN 순서 탐색은 테이블 이름의 순열을 만드는 작업과 다릅니다. CBO가 다루는 입력에는 적어도 다음 정보가 들어 있습니다.

JOIN에 참여하는 relation
relation 사이의 predicate
OUTER JOIN과 SEMI JOIN이 만드는 순서 제약
각 relation의 access path
cardinality와 데이터 분포에 대한 통계
Hash Join, Nested Loop Join, Merge Join과 같은 물리 연산
ordering과 distribution 같은 physical property

예를 들어 A, B, C의 순서를 정했다고 해서 실행 계획 후보가 단 하나인 것은 아닙니다. A를 Table Scan으로 읽을 수도 있고 Index Scan으로 읽을 수도 있습니다. A와 B를 Hash Join으로 결합할 수도 있고 Nested Loop Join으로 결합할 수도 있습니다. 같은 Join Tree라도 build side, probe side, ordering에 따라 서로 다른 물리 계획이 됩니다.

따라서 JOIN 최적화에는 다음과 같은 여러 문제가 있습니다.

어떤 relation끼리 먼저 결합할 것인가
각 relation을 어떤 access path로 읽을 것인가
각 JOIN을 어떤 물리 연산으로 실행할 것인가

이번 글은 첫 번째 문제인 JOIN 순서 탐색을 중심에 두되, 나머지 두 문제가 탐색 공간을 어떻게 키우는지도 함께 살펴봅니다.

2. JOIN 순서의 수

JOIN 순서의 수를 계산하려면 먼저 무엇을 서로 다른 후보로 볼지 정해야 합니다. 이 글에서는 INNER JOIN의 교환 법칙이 성립하고, logical Join Tree의 한 node에서 left input과 right input을 맞바꾼 경우는 같은 순서로 봅니다.

A JOIN B = B JOIN A

이 기준은 logical Join Tree의 수를 셀 때만 적용합니다. 실제 물리 계획에서는 left input과 right input의 역할이 다를 수 있습니다. Hash Join의 build side와 probe side, Nested Loop Join의 outer input과 inner input은 서로 바꿨을 때 cost가 달라집니다. OUTER JOIN처럼 교환 법칙이 성립하지 않는 연산도 별도로 다뤄야 합니다.

Left-Deep Join Tree

$n$ 개의 relation으로 Left-Deep Join Tree를 만든다고 가정해 보겠습니다. 처음 JOIN할 두 relation은 순서를 구분하지 않으므로 ${n \choose 2}$ 가지입니다. 남은 $n-2$ 개의 relation은 Join Tree에 추가되는 순서가 중요하므로 $(n-2)!$ 가지입니다.

N_{left}(n) = {n \choose 2}(n-2)! = \frac{n!}{2}

relation이 10개라면 Left-Deep Join Tree만 고려해도 후보는 다음과 같습니다.

N_{left}(10)=\frac{10!}{2}=1,814,400

여기에는 access path와 JOIN 방식이 아직 포함되지 않았습니다.

전체 Binary Join Tree

Bushy Join Tree까지 허용하면 relation을 배치하는 순서뿐 아니라 Join Tree의 모양도 달라집니다. 좌우 교환을 같은 logical Join Tree로 보는 경우, $n$ 개의 이름 있는 relation으로 만들 수 있는 전체 Binary Join Tree의 수는 다음과 같습니다.

N_{binary}(n) =(2n-3)!! =\frac{(2n-2)!}{2^{n-1}(n-1)!}

여기서 이중 계승(Double Factorial)은 다음과 같은 곱을 뜻합니다.

(2n-3)!!=(2n-3)(2n-5)\cdots3\times1

relation 수	Left-Deep Join Tree	전체 Binary Join Tree
2	1	1
3	3	3
4	12	15
5	60	105
6	360	945
7	2,520	10,395
8	20,160	135,135
9	181,440	2,027,025
10	1,814,400	34,459,425

10개의 relation만으로도 전체 Binary Join Tree는 약 3,446만 개가 됩니다. relation이 하나 늘 때마다 기존 계획에 위치 하나만 추가되는 것이 아니라, 새로운 relation의 위치와 새로운 Join Tree의 모양이 함께 늘어납니다.

left input과 right input의 방향까지 구분하면 수는 더 커집니다. $C_{n-1}$ 을 Catalan 수라고 할 때 후보 수는 다음과 같습니다.

N_{ordered}(n)=n!C_{n-1}

C_{n-1}=\frac{1}{n}{2n-2 \choose n-1}

다만 이 값은 logical JOIN 순서와 물리적인 input 역할을 한꺼번에 셀 수 있으므로, 최적화 알고리즘을 비교할 때는 어떤 기준으로 후보를 셌는지 반드시 확인해야 합니다.

물리 계획

각 relation $R_i$ 에 $a_i$ 개의 access path가 있고, 각 JOIN node에서 $m$ 개의 물리 JOIN 방식을 모두 적용할 수 있다고 가정하면 단순 조합 수는 다음과 같이 볼 수 있습니다.

N_{physical} \approx N_{tree} \times \prod_{i=1}^{n}a_i \times m^{n-1}

이 식은 실제 DBMS의 정확한 후보 수를 계산하는 공식이 아닙니다. predicate의 종류, physical property, 구현 가능한 JOIN 방식에 따라 많은 조합이 제외됩니다. 다만 logical Join Tree의 수만으로도 큰 탐색 공간에 access path와 물리 연산이 다시 곱해진다는 점을 보여줍니다.

CBO의 문제는 가능한 순서를 만드는 데 있지 않습니다. 제한된 최적화 시간 안에 비교할 가치가 있는 순서만 만드는 데 있습니다.

3. Relation Set과 Dynamic Programming

모든 Binary Join Tree를 처음부터 끝까지 각각 만들면 같은 중간 결과를 여러 번 계산하게 됩니다.

((A JOIN B) JOIN C) JOIN D
((A JOIN B) JOIN D) JOIN C

두 계획은 모두 {A, B}를 먼저 만듭니다. {A, B}의 최적 계획을 한 번 구해 저장한다면 상위 계획에서 다시 사용할 수 있습니다. Dynamic Programming은 이 중복을 relation set 단위로 제거합니다.

최적 부분 구조

relation set $S$ 의 최적 계획이 두 하위 계획 $S_1$ , $S_2$ 를 JOIN해서 만들어졌다고 가정하겠습니다. 동일한 조건과 physical property 아래에서 $S_1$ 의 계획이 최적이 아니라면, cost가 더 낮은 $S_1$ 의 계획으로 교체해 전체 계획의 cost도 낮출 수 있습니다.

이 성질을 최적 부분 구조라고 합니다. Dynamic Programming은 작은 relation set의 최적 계획부터 구한 뒤 더 큰 relation set을 만듭니다.

base relation의 초기 상태는 다음과 같습니다.

Best(\{R_i\}) =R_i\text{를 읽는 cost가 가장 낮은 access path}

계획 $P$ 가 $P_L$ 과 $P_R$ 을 JOIN한다면 cost는 일반적으로 다음 구조를 가집니다.

C(P) =C(P_L)+C(P_R)+C_{join}(P_L,P_R)

$C_{join}$ 에는 두 input의 cardinality, JOIN 방식, 메모리 사용량, 정렬 여부, I/O 등이 반영됩니다.

Left-Deep 탐색

Left-Deep Join Tree만 탐색한다면 right input에는 항상 base relation 하나가 들어갑니다. relation set $S$ 의 최적 계획은 $S$ 에서 relation 하나를 제외한 계획에 그 relation을 추가하는 방식으로 구할 수 있습니다.

Best(S) =\min_{r\in S} Join\bigl(Best(S-\{r\}),Best(\{r\})\bigr)

계산은 relation 수에 따라 진행됩니다.

크기 1: {A}, {B}, {C}, {D}
크기 2: {A,B}, {A,C}, {B,C}, ...
크기 3: {A,B,C}, {A,B,D}, ...
크기 4: {A,B,C,D}

Join Graph에 직접 연결되지 않은 relation set을 제외한다면 실제로 생성되는 상태는 이보다 적습니다.

Bushy 탐색

Bushy Join Tree에서는 $S$ 를 두 개의 비어 있지 않은 부분집합으로 나누는 모든 방법을 고려합니다.

Best(S) =\min_{\substack{A\subset S\\A\neq\varnothing}} Join\bigl(Best(A),Best(S-A)\bigr)

INNER JOIN에서 $A$ 와 $S-A$ 를 바꾼 분할은 logical Join Tree 기준으로 같습니다. 따라서 가장 작은 relation을 항상 $A$ 에 포함하는 식의 canonical rule을 적용해 대칭인 분할을 한 번만 평가할 수 있습니다.

Left-Deep 탐색은 기존 relation set에 base relation 하나만 붙입니다. Bushy 탐색은 두 중간 결과를 결합할 수 있으므로 더 많은 계획을 찾을 수 있지만, 하나의 relation set을 만드는 분할 수도 크게 늘어납니다.

Physical Property

실제 CBO는 relation set마다 계획 하나만 저장해서는 안 됩니다. {A, B}를 만드는 cost가 가장 낮은 계획이 정렬되지 않은 output을 만들고, cost가 조금 더 높은 계획이 A.id 순서로 정렬된 output을 만든다고 가정해 보겠습니다. 상위 Merge Join이나 ORDER BY가 해당 순서를 요구한다면 두 번째 계획이 전체 cost를 낮출 수 있습니다.

따라서 상태는 보통 relation set만이 아니라 필요한 physical property까지 포함합니다.

Best(S,p) =S\text{를 property }p\text{로 만드는 최적 계획}

ordering, distribution, parameterization이 다르면 현재 cost가 더 높더라도 바로 제거할 수 없습니다. 후보의 우열은 같은 logical output과 같은 required property 안에서 비교해야 합니다.

4. Cardinality와 JOIN 순서

JOIN 순서가 중요한 이유를 단순한 숫자로 살펴보겠습니다. 다음 값은 알고리즘을 설명하기 위해 만든 가상의 추정치입니다.

relation 또는 중간 결과	estimated cardinality
A	1,000,000
B	1,000,000
C	1,000
D	1,000
A JOIN B	100,000,000
C JOIN D	100
B JOIN (C JOIN D)	10,000
(A JOIN B) JOIN C	10,000
최종 결과	1,000

비교를 단순하게 하기 위해 한 번의 JOIN이 읽어야 하는 row 수만 cost로 계산하겠습니다.

W_{join}(L,R)=card(L)+card(R)

첫 번째 계획은 A와 B를 먼저 JOIN합니다.

(((A JOIN B) JOIN C) JOIN D)

\begin{aligned} W_1 &=(1{,}000{,}000+1{,}000{,}000)\\ &\quad +(100{,}000{,}000+1{,}000)\\ &\quad +(10{,}000+1{,}000)\\ &=102{,}012{,}000 \end{aligned}

두 번째 계획은 C와 D를 먼저 줄입니다.

A JOIN (B JOIN (C JOIN D))

\begin{aligned} W_2 &=(1{,}000+1{,}000)\\ &\quad +(1{,}000{,}000+100)\\ &\quad +(1{,}000{,}000+10{,}000)\\ &=2{,}012{,}100 \end{aligned}

두 계획의 차이는 약 50.7배입니다.

\frac{W_1}{W_2}\approx50.7

최종 결과의 cardinality는 두 계획 모두 1,000이지만, 최종 결과에 도달할 때까지 처리한 row 수는 크게 다릅니다. A와 B를 먼저 JOIN한 계획은 1억 row의 중간 결과를 만든 직후 C와 결합해야 합니다. C와 D를 먼저 JOIN한 계획은 100 row로 줄인 결과를 B와 결합합니다.

실제 cost model은 단순한 덧셈보다 복잡합니다. Sequential I/O와 Random I/O, CPU 연산, 메모리, spill, 병렬 처리, 캐시 효과를 함께 계산합니다. 그래도 JOIN 순서의 cost 차이는 대부분 중간 결과의 cardinality가 이후 연산에 연쇄적으로 반영되면서 커집니다.

cardinality 추정이 틀리면 이 비교도 틀립니다. 실제로는 C JOIN D가 100만 row인데 100 row로 추정했다면, CBO는 작은 중간 결과를 기대하고 잘못된 JOIN 순서나 build side를 선택할 수 있습니다. 탐색 알고리즘이 최적 후보를 정확히 찾았더라도 입력으로 사용한 추정치가 틀리면 실제 최적 계획과 멀어집니다.

5. Join Graph와 연결된 후보

Dynamic Programming의 부분집합을 모두 생성할 필요는 없습니다. JOIN predicate가 없는 두 relation set을 결합하면 Cartesian Product가 됩니다. 쿼리가 이를 요구하지 않는다면 이런 후보는 대부분 탐색할 가치가 없습니다.

다음과 같은 chain 형태의 Join Graph를 생각해 보겠습니다.

A ── B ── C ── D

{A, C}는 연결된 relation set이 아닙니다. A와 C 사이에는 B가 필요하므로 둘만 먼저 결합하면 Cartesian Product가 됩니다. 반면 {A, B}, {B, C}, {A, B, C}는 연결된 relation set입니다.

전체 {A, B, C, D}를 마지막에 결합하는 유효한 canonical 분할은 다음과 같습니다.

{A}       JOIN {B,C,D}
{A,B}     JOIN {C,D}
{A,B,C}   JOIN {D}

{A, C} JOIN {B, D} 같은 분할은 양쪽 relation set 자체가 연결되어 있지 않으므로 제외할 수 있습니다.

CSG와 CMP

Join Graph 기반 알고리즘에서는 연결된 relation set을 csg라고 부릅니다. csg와 겹치지 않고, 그 자체도 연결되어 있으며, csg와 JOIN predicate로 연결할 수 있는 relation set을 cmp라고 부릅니다.

csg: connected subgraph
cmp: connected complement

하나의 csg-cmp pair는 Cartesian Product 없이 만들 수 있는 하나의 JOIN 후보를 뜻합니다. 같은 후보를 중복 없이 열거하고, 만들 수 없는 후보를 처음부터 생성하지 않는 것이 핵심입니다.

Join Graph의 형태

필요한 csg-cmp pair의 수는 relation 수뿐 아니라 Join Graph의 형태에 따라 달라집니다. $P_n$ 을 relation $n$ 개가 일렬로 연결된 chain graph, $K_n$ 을 모든 relation이 서로 연결된 clique graph라고 하겠습니다.

chain graph의 csg-cmp pair 수는 다음과 같습니다.

\#ccp(P_n)=\frac{n(n^2-1)}{6}

clique graph의 csg-cmp pair 수는 다음과 같습니다.

\#ccp(K_n) =\frac{3^n-2^{n+1}+1}{2}

relation 수	chain graph	clique graph
10	165	28,501
15	560	7,141,686
20	1,330	1,742,343,625

relation이 20개인 chain graph에는 1,330개의 csg-cmp pair가 있지만, clique graph에는 약 17억 개가 있습니다. 연결성만으로 많은 후보를 제거할 수 있는 쿼리가 있는 반면, 거의 모든 부분집합이 연결된 쿼리에서는 연결성만으로 탐색 공간을 충분히 줄일 수 없습니다.

JOIN 순서 탐색의 난도는 relation 수만으로 설명되지 않습니다. Join Graph의 topology가 같은 수의 relation에서도 전혀 다른 탐색 비용을 만듭니다.

6. DPsize, DPsub, DPccp

Dynamic Programming으로 JOIN 순서를 찾는 알고리즘은 같은 후보를 어떤 순서로 만들고, 불필요한 조합을 언제 제거하는지에 따라 성능이 달라집니다.

DPsize

DPsize는 relation set의 크기를 기준으로 후보를 만듭니다. 크기 1의 최적 계획을 구한 뒤 크기 2, 크기 3 순으로 확장합니다.

size 1
  ↓
size 2
  ↓
size 3
  ↓
size n

각 크기에서 가능한 부분집합과 분할을 검사하므로 구현과 동작을 이해하기 쉽습니다. chain이나 cycle 형태의 Join Graph에서는 비교적 효율적이지만, 연결되지 않은 조합을 확인한 뒤 버리는 비용이 생길 수 있습니다.

DPsub

DPsub는 relation set을 bitset으로 표현하고 부분집합을 순회합니다. 집합 연산을 빠르게 처리할 수 있고, star나 clique 형태의 Join Graph에서 DPsize보다 유리할 수 있습니다.

다만 DPsub도 가능한 부분집합과 분할을 먼저 열거한 뒤 Join Graph 연결성을 검사합니다. 실제 csg-cmp pair의 수보다 더 많은 조합에 접근할 수 있습니다.

DPccp

DPccp는 연결된 relation set과 연결된 complement를 직접 열거합니다. 전체 부분집합 공간을 훑으면서 연결되지 않은 후보를 버리는 대신, 처음부터 csg-cmp pair만 생성합니다.

seed 선택
  ↓
연결된 csg 확장
  ↓
연결된 cmp 확장
  ↓
csg-cmp pair 평가

각 유효한 csg-cmp pair는 cost function을 적어도 한 번 호출해야 비교할 수 있습니다. DPccp는 중복 없이 이 pair를 열거하므로, 일반적인 Join Graph에 대해 이론적으로 필요한 cost function 호출 수의 하한에 도달합니다.

이 말이 전체 최적화 시간이 항상 최소라는 뜻은 아닙니다. csg-cmp를 열거하기 위한 자료 구조와 재귀 호출, cardinality 추정, 물리 계획 생성에도 cost가 듭니다. 하지만 JOIN 후보 열거 자체에서는 연결성 검사를 통과하지 못할 조합을 대량으로 만드는 일을 피합니다.

7. Join Hypergraph와 DPhyp

일반적인 Join Graph의 edge는 두 relation을 연결합니다. 그러나 SQL predicate와 JOIN 순서 제약은 항상 두 relation만으로 표현되지 않습니다.

SELECT *
FROM A, B, C
WHERE A.x + B.y = C.z;

이 predicate는 A와 B가 같은 input 쪽에 있고 C가 반대쪽에 있어야 평가할 수 있습니다. A와 C 사이의 단순한 edge나 B와 C 사이의 단순한 edge로 바꾸면 predicate가 실제보다 일찍 평가될 수 있는 것처럼 보입니다.

Join Hypergraph에서는 relation 하나가 아니라 relation set 사이를 hyperedge로 연결할 수 있습니다.

{A,B} ── {C}

DPhyp

DPhyp는 DPccp의 연결된 후보 열거 방식을 Join Hypergraph로 확장한 알고리즘입니다. seed에서 연결된 subgraph를 확장하고, 반대편에서도 연결된 complement를 확장한 뒤 둘을 연결할 수 있는 hyperedge가 있을 때 후보를 평가합니다.

hyperedge는 여러 relation을 참조하는 predicate뿐 아니라 특정 JOIN의 순서 제약을 표현하는 데도 사용할 수 있습니다. OUTER JOIN, SEMI JOIN, ANTI JOIN은 INNER JOIN처럼 자유롭게 교환하거나 결합할 수 없으므로, 허용되는 변환만 탐색 공간에 들어오도록 해야 합니다.

다만 Join Hypergraph를 사용한다고 해서 SQL의 모든 변환이 자동으로 올바르게 처리되는 것은 아닙니다. 먼저 각 JOIN 사이의 충돌과 순서 제약을 정확히 계산하고 이를 hyperedge와 eligibility rule에 반영해야 합니다. 그 표현이 정확해야 DPhyp가 올바른 후보만 완전하게 열거할 수 있습니다.

Join Hypergraph는 탐색 알고리즘이 SQL 의미를 대신 판단하는 구조가 아닙니다. SQL 의미로부터 계산된 JOIN 가능 범위를 탐색 알고리즘에 전달하는 구조입니다.

8. Memo와 Top-Down Search

지금까지의 Dynamic Programming은 작은 relation set부터 큰 relation set으로 올라가는 bottom-up 방식이었습니다. Memo 기반 optimizer는 필요한 최종 목표에서 출발해 후보를 확장하는 top-down 방식을 사용할 수 있습니다.

Goal: Best({A,B,C,D}, required property)
  ↓
가능한 logical expression 생성
  ↓
child group에 필요한 property 전달
  ↓
child의 최적 계획 탐색
  ↓
cost 합산과 후보 비교

Memo의 group은 같은 logical output을 만드는 표현을 묶습니다. 같은 group 안에서도 physical property가 다르면 별도의 최적 계획이 필요합니다.

Best(Group,property)

예를 들어 Hash Join은 child에게 ordering을 요구하지 않을 수 있습니다. Merge Join은 두 child에게 JOIN key ordering을 요구할 수 있습니다. 상위 연산이 어떤 물리 구현을 선택했는지에 따라 하위 group에서 찾아야 하는 계획의 property가 달라집니다.

top-down 탐색은 현재 목표에 필요하지 않은 property나 아직 요청되지 않은 group을 최적화하지 않을 수 있습니다. 반면 transformation rule의 적용, 중복 expression 검사, group과 subset 관리를 위한 비용이 들어갑니다.

bottom-up Dynamic Programming과 Memo는 서로 완전히 다른 문제를 푸는 구조가 아닙니다. 둘 다 같은 중간 결과를 만드는 후보를 공유하고 최적 부분 구조를 이용합니다. 차이는 후보를 생성하는 방향, property를 전달하는 방식, 탐색을 중단하는 위치에 있습니다.

9. Pruning과 탐색 중단

전체 탐색 공간이 크기 때문에 CBO는 후보를 생성하는 과정과 생성한 뒤 비교하는 과정 모두에서 pruning을 사용합니다.

연결성

Join Graph나 Join Hypergraph에서 연결되지 않은 relation set의 결합은 Cartesian Product를 만듭니다. 쿼리 의미상 필요하지 않다면 처음부터 후보에서 제외합니다.

의미 제약

OUTER JOIN, SEMI JOIN, ANTI JOIN, LATERAL과 상관 서브쿼리는 가능한 JOIN 순서를 제한합니다. cost가 낮아 보이더라도 SQL 의미를 보존하지 못하는 계획은 후보가 될 수 없습니다.

지배 관계

같은 logical output과 같은 physical property를 만드는 두 계획이 있다면 cost가 더 높은 계획을 제거할 수 있습니다.

C(P_1)\le C(P_2) \Rightarrow P_2\text{ 제거}

단, $P_1$ 과 $P_2$ 의 ordering이나 distribution이 다르면 이 비교는 성립하지 않을 수 있습니다. 현재 cost가 높은 계획이 상위 연산의 Sort나 네트워크 재분배를 없앨 수 있기 때문입니다.

Cost Upper Bound

이미 완성된 계획의 cost가 $U$ 라면, 일부만 만든 후보의 cost가 $U$ 를 넘는 순간 탐색을 중단할 수 있습니다. Oracle의 공개 문서에서도 plan generator가 현재 최저 cost를 cutoff로 사용해 cost가 더 높은 JOIN 순서의 탐색을 중단한다고 설명합니다.

이 방식의 효과는 좋은 계획을 얼마나 일찍 찾는지에 따라 달라집니다. 초기에 낮은 upper bound를 얻으면 이후 많은 후보를 빠르게 제거할 수 있습니다.

탐색 예산

relation 수가 많거나 Join Graph가 조밀하면 정확한 Dynamic Programming도 감당하기 어려울 수 있습니다. 이때는 다음과 같은 제한을 둘 수 있습니다.

Left-Deep Join Tree만 탐색
후보 수나 최적화 시간 제한
일부 transformation rule 지연
greedy search나 randomized search 사용
여러 relation을 하나의 묶음으로 고정

PostgreSQL은 JOIN relation 수가 설정값을 넘으면 exhaustive search 대신 GEQO를 사용할 수 있습니다. 이는 logical equivalence 전체를 완전 탐색하기보다 주어진 시간에 좋은 순서를 찾는 쪽을 선택한 사례입니다.

여기서 exhaustive라는 표현도 범위를 분명히 해야 합니다. optimizer가 자신이 정의한 Join Tree와 물리 연산의 탐색 공간을 모두 확인했다는 뜻이지, SQL과 동등한 세상의 모든 실행 프로그램을 확인했다는 뜻은 아닙니다.

10. 실제 DBMS의 JOIN 순서 탐색

각 DBMS는 같은 JOIN 최적화 문제를 서로 다른 자료 구조와 탐색 전략으로 풉니다. 공개 문서와 소스에서 확인할 수 있는 범위에도 차이가 있습니다.

PostgreSQL

PostgreSQL은 기본 JOIN 탐색에서 relation 수에 따라 후보를 쌓아 올립니다. join_search_one_level은 이전 단계에서 만든 relation set과 base relation을 결합하거나, 더 작은 두 relation set을 결합해 다음 level의 join_rel_level을 만듭니다.

JOIN clause가 있는 relation을 우선 결합하고, 연결된 후보가 없을 때 Cartesian Product 후보를 고려합니다. 각 relation set에는 여러 Path가 존재할 수 있으며, cost와 pathkey, parameterization을 비교해 필요한 후보를 남깁니다.

relation 수가 geqo_threshold 이상이면 GEQO를 사용할 수 있습니다. 따라서 PostgreSQL의 JOIN 탐색은 항상 하나의 알고리즘으로 고정되어 있지 않습니다.

Oracle Database

Oracle Database의 공개 문서는 plan generator가 access path, JOIN 방식, JOIN 순서를 조합해 후보 계획을 만들고 cost를 비교한다고 설명합니다. 탐색 중에 얻은 현재 최저 cost가 cutoff가 되며, 이미 그보다 cost가 높아진 JOIN 순서는 더 탐색하지 않을 수 있습니다.

다만 Oracle은 optimizer의 내부 후보 표현과 JOIN 열거 알고리즘 전체를 공개하지 않습니다. 공개 문서에서 확인할 수 있는 동작과 비공개 내부 구현을 구분해서 볼 필요가 있습니다.

MySQL

MySQL의 Hypergraph Join Optimizer는 query block의 relation과 predicate를 Join Hypergraph로 변환합니다. 이후 DPhyp 방식으로 연결된 subgraph와 complement를 열거하고, 결합 가능한 각 pair에 대해 AccessPath 후보를 만듭니다.

여러 relation을 참조하는 predicate와 OUTER JOIN이 만드는 제약도 hyperedge에 반영할 수 있습니다. 같은 subplan을 만드는 후보는 cost와 property를 비교해 관리하고, 최종적으로 선택된 AccessPath가 실행 계획의 기반이 됩니다.

DuckDB

DuckDB는 분석 쿼리에 초점을 둔 in-process columnar DBMS입니다. 공식 내부 구조 문서는 Join Order Optimizer가 DPccp를 사용한다고 설명합니다.

logical plan에서 relation과 predicate를 추출한 뒤 연결된 JOIN 후보를 탐색하고, 선택한 JOIN 순서를 다시 logical plan에 반영합니다. JOIN 순서 최적화와 구체적인 물리 연산 선택은 연결되어 있지만 서로 다른 최적화 단계에서 수행될 수 있습니다.

Apache Calcite

Apache Calcite는 데이터를 직접 저장하는 DBMS가 아니라 SQL 처리와 query optimization 기능을 제공하는 framework입니다. VolcanoPlanner는 rule을 이용해 동등한 RelNode 표현을 생성하고, Memo에 해당하는 RelSet과 RelSubset으로 후보를 공유합니다.

RelSubset은 같은 logical expression 중 같은 physical property를 만족하는 후보를 묶습니다. planner는 필요한 property를 만족하는 최저 cost의 표현을 찾습니다. 이 구조에서는 JOIN reordering도 독립된 열거기 하나가 모든 순서를 만드는 방식보다 transformation rule과 Memo 탐색의 일부에 가깝습니다.

비교

시스템	JOIN 탐색의 중심 구조	탐색의 특징
PostgreSQL	relation set, `RelOptInfo`, `Path`	level 기반 탐색, 큰 JOIN에서 GEQO 사용 가능
Oracle Database	공개 문서상 plan generator	현재 최저 cost를 cutoff로 활용
MySQL	Join Hypergraph, `AccessPath`	DPhyp 기반 연결 subgraph 열거
DuckDB	Join Graph와 logical plan	DPccp 기반 JOIN 순서 탐색
Apache Calcite	`RelSet`, `RelSubset`, Memo	rule과 top-down cost 탐색

구조와 알고리즘 이름은 다르지만 공통점은 분명합니다. 중간 결과를 공유하고, 가능한 결합만 만들며, physical property가 같은 후보 안에서 cost를 비교합니다.

11. 개인적인 생각

JOIN optimizer의 수준을 얼마나 많은 후보를 탐색하는지로만 평가하기는 어렵다고 생각합니다. 후보 수가 많아도 cardinality 추정이 틀리면 잘못된 계획을 정교하게 선택할 수 있습니다. 반대로 탐색 공간이 제한되어 있어도 workload의 특성과 잘 맞는 후보를 빠르게 찾는다면 더 안정적인 성능을 낼 수 있습니다.

중요한 것은 최적화 시간당 유효한 후보의 밀도에 가깝습니다. 연결되지 않은 부분집합을 만들었다가 버리는 cost, 같은 중간 결과를 반복해서 계산하는 cost, 상위 계획에서 쓰이지 않을 physical property를 모두 최적화하는 cost를 줄여야 합니다. DPccp와 DPhyp, Memo, pruning은 서로 모양은 다르지만 이 낭비를 줄이기 위한 장치입니다.

또한 CBO가 찾은 최적 계획이라는 표현에는 항상 전제가 붙습니다.

optimizer가 허용한 변환 범위 안에서의 최적 계획
optimizer가 구현한 물리 연산 안에서의 최적 계획
추정한 cardinality와 cost model을 기준으로 한 최적 계획
주어진 최적화 시간 안에서 찾은 최적 계획

탐색 알고리즘은 이 전제 중 첫 번째와 네 번째를 개선할 수 있습니다. 그러나 통계와 cardinality 추정이 틀리거나 cost model이 실제 하드웨어와 workload를 충분히 반영하지 못하면, 탐색 알고리즘만 정교하게 만들어서는 해결되지 않습니다.

많은 계획을 보는 optimizer가 아니라, 실제로 선택할 가치가 있는 계획을 놓치지 않으면서 나머지를 빠르게 후보에서 거를 수 있는 것이 좋은 optimizer라고 생각합니다.

References

논문

P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, T. G. Price. Access Path Selection in a Relational Database Management System. ACM SIGMOD, 1979.
Kiyoshi Ono, Guy M. Lohman. Measuring the Complexity of Join Enumeration in Query Optimization. VLDB, 1990.
Goetz Graefe. The Cascades Framework for Query Optimization. IEEE Data Engineering Bulletin, 1995.
Guido Moerkotte, Thomas Neumann. Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products. VLDB, 2006.
Guido Moerkotte, Thomas Neumann. Dynamic Programming Strikes Back. ACM SIGMOD, 2008.
Guido Moerkotte, Pit Fender, Marius Eich. On the Correct and Complete Enumeration of the Core Search Space. ACM SIGMOD, 2013.
Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, Thomas Neumann. How Good Are Query Optimizers, Really?. Proceedings of the VLDB Endowment, 2015.

공식 문서와 구현

PostgreSQL

Planner and Optimizer
Controlling the Planner with Explicit JOIN Clauses
PostgreSQL source: joinrels.c, pathnodes.h

Oracle Database

MySQL

DuckDB

Apache Calcite

주재완

데이터베이스, 트랜잭션 구조 설계에 관심이 많은 백엔드 개발자입니다.

이전 포스트

[DB] CBO는 JOIN 순서를 어떻게 찾는가

Database

1. JOIN 순서 탐색의 입력

2. JOIN 순서의 수

Left-Deep Join Tree

전체 Binary Join Tree

물리 계획

3. Relation Set과 Dynamic Programming

최적 부분 구조

Left-Deep 탐색

Bushy 탐색

Physical Property

4. Cardinality와 JOIN 순서

5. Join Graph와 연결된 후보

CSG와 CMP

Join Graph의 형태

6. DPsize, DPsub, DPccp

DPsize

DPsub

DPccp

7. Join Hypergraph와 DPhyp

DPhyp

8. Memo와 Top-Down Search

9. Pruning과 탐색 중단

연결성

의미 제약

지배 관계

Cost Upper Bound

탐색 예산

10. 실제 DBMS의 JOIN 순서 탐색

PostgreSQL

Oracle Database

MySQL

DuckDB

Apache Calcite

비교

11. 개인적인 생각

References

논문

공식 문서와 구현

PostgreSQL

Oracle Database

MySQL

DuckDB

Apache Calcite

[DB] JOIN의 내부

0개의 댓글