[DB] JOIN의 내부

주재완·2026년 7월 29일

Database

목록 보기

8/9

1. SQL은 JOIN을 어떻게 표현하는가

SQL에서 JOIN은 FROM 절에 작성합니다. 먼저 기준이 되는 테이블을 적고, 그 뒤에 결합할 테이블과 JOIN 조건을 이어 붙입니다.

SELECT *
FROM A
JOIN B ON A.id = B.a_id
JOIN C ON B.id = C.b_id;

이 쿼리는 A에서 시작해 B를 JOIN하고, 이어서 C를 JOIN하는 형태로 읽힙니다. SQL 문법만 보면 기준 테이블 하나와 그 뒤에 나열된 JOIN List로 볼 수 있습니다.

기준 테이블 A
├── JOIN B
└── JOIN C

SQL 파서도 이와 비슷하게 기준 테이블과 JOIN List로 AST를 구성할 수 있습니다. A를 기준 테이블로 두고, B와 C에 대한 JOIN 정보를 작성된 순서대로 목록에 저장하는 방식입니다. 각 항목에는 JOIN 종류와 대상 테이블, ON 또는 USING으로 작성된 조건이 포함됩니다.

이 방식은 사용자가 작성한 SQL을 보존하기에 편리합니다. 어떤 테이블이 먼저 등장했는지, 어떤 JOIN을 사용했는지, 각각의 조건이 어느 JOIN에 속하는지 쉽게 확인할 수 있습니다.

하지만 SQL의 JOIN을 항상 하나의 목록으로만 표현할 수 있는 것은 아닙니다. JOIN의 대상에는 일반 테이블뿐 아니라 서브쿼리나 다른 JOIN의 결과도 올 수 있습니다. 괄호를 사용하면 사용자가 JOIN의 결합 순서를 직접 나타낼 수도 있습니다.

SELECT *
FROM A
JOIN (
    B JOIN C ON B.id = C.b_id
) ON A.id = B.a_id;

여기서는 B와 C를 먼저 JOIN한 뒤, 그 결과를 A와 JOIN합니다. 앞의 쿼리와 똑같이 A, B, C가 등장하지만 JOIN의 결합 구조는 다릅니다. 이런 차이를 보존하려면 괄호 안의 JOIN을 다시 하나의 테이블 참조로 다룰 수 있어야 합니다.

따라서 기준 테이블과 JOIN List는 단순한 JOIN 문장을 표현하기에는 편리하지만, 중첩된 JOIN까지 다루려면 별도 구조가 필요합니다. 모든 JOIN을 하나의 JOIN List에 저장하더라도 어디에서 괄호가 시작되고 끝나는지, 어느 JOIN의 output이 다음 JOIN의 input이 되는지는 따로 보존해야 합니다.

SQL에 작성된 테이블 순서가 실제 실행 순서를 뜻하는 것도 아닙니다. SQL 파서는 사용자가 작성한 순서를 AST에 남기지만, 옵티마이저는 같은 결과를 보장할 수 있는 범위에서 JOIN 순서를 바꿀 수 있습니다. 여러 INNER JOIN은 다른 순서로 실행될 수 있지만, OUTER JOIN처럼 input 순서가 결과에 영향을 주는 경우에는 변경할 수 있는 범위가 제한됩니다.

2. 관계대수에서 JOIN

관계대수에서 JOIN은 두 relation을 input으로 받아 새로운 relation을 output으로 만드는 이항 연산자입니다. 하나의 JOIN에는 left input과 right input이 있으며, 두 input의 행을 JOIN 조건에 따라 결합합니다.

A ⋈ B

여기서 A와 B는 데이터베이스에 저장된 테이블일 수도 있고, 다른 연산을 거쳐 만들어진 결과일 수도 있습니다. 관계대수는 원본 테이블과 연산 결과를 모두 relation이라는 같은 대상으로 취급합니다.

JOIN의 output 역시 하나의 relation입니다. A와 B를 JOIN한 output은 다시 C와 JOIN할 수 있습니다.

(A ⋈ B) ⋈ C

첫 번째 JOIN은 A와 B를 input으로 받습니다. 두 번째 JOIN은 첫 번째 JOIN의 output과 C를 input으로 받습니다. 테이블 수가 늘어나더라도 각 JOIN은 항상 두 input을 처리하고, 그 output을 다음 연산에 넘깁니다.

이처럼 relation을 input으로 받은 연산이 다시 relation을 output으로 만드는 성질을 폐쇄성이라고 합니다. 폐쇄성 덕분에 복잡한 쿼리도 몇 가지 관계 연산을 반복해서 적용하는 방식으로 표현할 수 있습니다. JOIN뿐 아니라 필터링, 프로젝션, 집계의 output도 다시 다른 관계 연산의 input이 될 수 있습니다.

여러 테이블을 한 번에 결합하는 연산을 별도로 정의할 수도 있겠지만 반드시 필요하지는 않습니다. 세 테이블의 JOIN은 두 번의 이항 JOIN으로 표현할 수 있고, 네 테이블의 JOIN은 세 번의 이항 JOIN으로 표현할 수 있습니다. 더 많은 테이블이 등장하더라도 같은 방식으로 확장할 수 있습니다.

이항 연산으로 표현하면 어느 relation을 먼저 결합했는지도 분명해집니다.

(A ⋈ B) ⋈ C
A ⋈ (B ⋈ C)

첫 번째 식은 A와 B를 먼저 JOIN하고, 두 번째 식은 B와 C를 먼저 JOIN합니다. 최종적으로 같은 테이블을 사용하더라도 두 식에서 만들어지는 중간 결과는 서로 다릅니다. 각 중간 결과의 cardinality가 다르면 이후 JOIN에서 처리해야 할 데이터의 양도 달라질 수 있습니다.

INNER JOIN은 조건이 허용하는 경우 결합 순서를 바꾸어도 같은 결과를 만들 수 있습니다. 이 성질은 옵티마이저가 여러 JOIN 순서를 비교할 수 있는 근거가 됩니다. 하지만 모든 JOIN이 자유롭게 순서를 바꿀 수 있는 것은 아닙니다. OUTER JOIN은 어느 쪽의 행을 보존하고 NULL을 채울지가 정해져 있으므로 괄호의 위치나 input 순서를 바꾸면 결과가 달라질 수 있습니다.

또한 관계대수에서 중간 결과가 존재한다는 말은 DBMS가 그 결과를 반드시 임시 테이블로 저장한다는 뜻이 아닙니다. 중간 결과는 우선 JOIN의 input과 output을 설명하기 위한 논리적인 단위입니다. 실제 실행에서는 output 행을 다음 연산으로 바로 전달할 수도 있고, 해시 테이블이나 정렬 결과처럼 필요한 형태로 보관할 수도 있습니다.

3. Binary Join Tree

앞에서 본 SQL의 JOIN List를 Binary Join Tree로 옮겨 보겠습니다. A가 기준 테이블이 되고, B와 C에 대한 JOIN이 작성된 순서대로 저장된 상태에서 시작합니다.

기준 테이블: A
JOIN List:
- JOIN B
- JOIN C

JOIN List를 왼쪽부터 처리하기

Binary Join Tree를 만들 때는 기준 테이블에서 시작해 JOIN List를 앞에서부터 처리합니다.

처음에는 A에서 시작합니다.
B를 만나면 A JOIN B를 만듭니다.
이 output을 다음 JOIN의 left input으로 사용합니다.
left input과 C를 JOIN합니다.

A + [JOIN B, JOIN C]
          ↓
        JOIN
       /    \
    JOIN     C
   /    \
  A      B

최종 결과는 (A JOIN B) JOIN C가 됩니다. JOIN List에서는 처리 과정의 상태로만 존재하던 A JOIN B의 output이 Join Tree에서는 독립된 subtree가 됩니다. 이 subtree는 상위 JOIN의 left input으로 직접 연결됩니다.

Left-Deep Join Tree

JOIN List를 작성된 순서대로 처리하면 왼쪽에 이전 JOIN의 output이 계속 누적됩니다.

          JOIN
         /    \
      JOIN     D
     /    \
  JOIN     C
 /    \
A      B

이 형태를 Left-Deep Join Tree라고 합니다. SQL에 A, B, C, D 순서로 작성했다면 초기 Join Tree도 같은 순서를 보존합니다.

이 단계에서는 어떤 JOIN 순서의 cost가 더 낮은지 판단하지 않습니다. SQL 문법으로 저장된 JOIN List를 각 JOIN의 input과 output이 드러나는 논리 구조로 옮길 뿐입니다. JOIN 순서를 바꾸는 작업은 이후 옵티마이저가 수행합니다.

JOIN 결합 구조

괄호가 사용된 JOIN은 그 결합 구조를 그대로 보존해야 합니다.

SELECT *
FROM A
JOIN (
    B JOIN C ON B.id = C.b_id
) ON A.id = B.a_id;

이 쿼리에서는 B와 C의 JOIN 결과 전체가 A와 JOIN할 input이 됩니다. 따라서 A JOIN B JOIN C처럼 모든 JOIN을 같은 JOIN List에 나열하면 원래 구조를 구분할 수 없습니다.

또한 INNER JOIN은 조건에 따라 결합 순서를 바꿀 수 있지만, OUTER JOIN은 input 순서와 결합 위치가 결과에 영향을 줄 수 있습니다. 그러므로 초기 Binary Join Tree를 만들 때는 JOIN 종류와 조건뿐 아니라 괄호로 지정된 결합 구조도 유지해야 합니다.

4. 왜 Binary Join Tree를 사용하는가

Binary Join Tree에서는 기본 테이블이 leaf node가 되고, 각 JOIN의 output이 상위 JOIN의 input이 됩니다.

        JOIN
       /    \
    JOIN     C
   /    \
  A      B

이 구조는 JOIN의 결합 순서뿐 아니라 각 단계에서 만들어지는 중간 결과를 직접 보여줍니다. DBMS는 이를 기준으로 cardinality를 추정하고, cost를 계산하며, predicate를 적용할 위치를 판단할 수 있습니다.

중간 결과

A와 B를 JOIN한 output은 C와의 JOIN에 사용되는 중간 결과입니다. 이 중간 결과는 자체 schema와 cardinality를 가지며, 상위 JOIN의 input이 됩니다.

JOIN List에서는 이 중간 결과가 목록을 처리하는 동안의 상태로만 존재합니다. Binary Join Tree에서는 A JOIN B가 독립된 subtree가 되어 상위 JOIN과 직접 연결됩니다.

다만 Join Tree에 중간 결과가 존재한다고 해서 실행 중에 결과 전체를 반드시 저장하는 것은 아닙니다. DBMS는 행을 상위 연산으로 바로 전달하거나, Hash Join을 위해 일부 데이터를 해시 테이블에 저장할 수도 있습니다.

Cardinality

옵티마이저가 JOIN 순서를 결정하려면 각 연산에서 몇 개의 행이 나올지 추정해야 합니다.

A                     1,000,000행
B                        10,000행
A JOIN B                    100행
(A JOIN B) JOIN C             5행

A와 B의 JOIN output이 작다면 이를 먼저 계산하는 계획이 유리할 수 있습니다. 반대로 중간 결과가 크게 증가하면 이후 JOIN에서 처리해야 할 데이터도 늘어납니다.

Binary Join Tree에서는 각 subtree가 하나의 cardinality 추정 단위가 됩니다. 이 추정이 부정확하면 나쁜 JOIN 순서가 선택될 수 있습니다.

Cost

cardinality는 cost 계산의 중요한 input입니다. 처리할 행이 많아지면 CPU와 메모리 사용량, 데이터 접근 비용도 증가합니다.

또한 같은 A와 B의 JOIN이라도 실행 방식에 따라 cost가 달라집니다. 사용할 인덱스와 정렬 상태, 메모리 크기도 cost에 영향을 줍니다. 따라서 논리 계획은 무엇을 JOIN할 것인가를 나타내고, 물리 계획은 어떤 방식으로 JOIN할 것인가를 나타냅니다. cost는 실행 방식까지 정해진 물리 계획 후보를 비교할 때 사용합니다.

Predicate Pushdown

Binary Join Tree는 predicate를 적용할 수 있는 위치를 판단하는 기준도 제공합니다.

        JOIN          A, B, C 조건
       /    \
    JOIN     C        A, B 조건
   /    \
  A      B            A 조건

A의 컬럼만 사용하는 조건은 A를 읽는 단계까지 내릴 수 있습니다. A와 B의 컬럼을 함께 사용하는 조건은 두 input이 만나는 JOIN에서 평가해야 합니다. C까지 필요한 조건은 C가 포함되기 전에는 계산할 수 없습니다.

predicate를 가능한 아래쪽에서 적용하면 상위 연산으로 전달되는 행을 줄일 수 있습니다. 하지만 OUTER JOIN에서는 predicate의 위치에 따라 보존되는 행과 NULL 처리 결과가 달라질 수 있으므로 무조건 아래로 내릴 수는 없습니다.

Rule-based Rewrite

Predicate Pushdown은 JOIN 전에 적용할 수 있는 rewrite 중 하나입니다. 옵티마이저는 SQL을 바로 물리 계획으로 바꾸지 않고, 같은 결과를 만드는 범위에서 논리 계획을 먼저 정리합니다.

변환 전

Filter [A.id = 1]
└─ Join [A.key = B.key]
   ├─ Scan A
   └─ Scan B

변환 후

Join [A.key = B.key]
├─ Filter [A.id = 1]
│  └─ Scan A
└─ Scan B

이외에도 JOIN 주변에서는 다음과 같은 rewrite를 적용할 수 있습니다.

Projection Pushdown은 상위 연산에서 필요하지 않은 컬럼을 JOIN 전에 제거해 row width와 메모리 사용량을 줄입니다. JOIN key와 predicate 평가에 필요한 컬럼은 유지해야 합니다.
Constant Folding은 상수 expression을 미리 계산합니다. predicate가 항상 false라면 하위 relation을 읽지 않는 계획으로 바꿀 수도 있습니다.
Transitive Predicate는 A.id = B.id와 A.id = 10으로부터 B.id = 10을 유도해 양쪽 input에 predicate를 적용할 수 있게 합니다.
Join Elimination은 JOIN한 테이블의 컬럼이 사용되지 않고 key constraint가 결과 보존을 증명할 때 불필요한 JOIN을 제거합니다.

이러한 rewrite는 항상 적용할 수 있는 규칙이 아닙니다. OUTER JOIN의 NULL 처리, column의 type과 collation, UNIQUE와 FOREIGN KEY 같은 constraint를 함께 확인해야 합니다. 논리적으로 같은 결과를 보장한 뒤에야 변환된 계획을 cost 비교 대상으로 사용할 수 있습니다.

Join Reordering

JOIN 순서를 바꾸면 Binary Join Tree의 모양도 바뀝니다.

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

두 계획은 같은 테이블을 사용하지만 중간 결과가 다릅니다. 중간 결과의 cardinality와 사용 가능한 인덱스, JOIN 방식에 따라 전체 cost도 달라집니다.

INNER JOIN은 조건이 허용하는 범위에서 결합 순서를 바꿀 수 있습니다. 반면 OUTER JOIN이나 상관 서브쿼리처럼 input 순서에 의미가 있는 연산은 가능한 변환이 제한됩니다.

5. JOIN 실행 방식

INNER JOIN, LEFT JOIN 같은 JOIN 종류가 결과의 의미를 정한다면, Nested Loop Join, Hash Join, Merge Join은 그 결과를 계산하는 물리 실행 방식입니다.

Nested Loop Join

Nested Loop Join은 먼저 읽은 input의 각 행에 대해 다른 input에서 JOIN 조건을 만족하는 행을 찾습니다. 바깥쪽 반복에서 한 행을 가져오고, 그 값을 이용해 안쪽 input을 탐색하는 과정을 반복합니다.

안쪽 input에 JOIN key로 사용할 수 있는 인덱스가 있다면 매번 전체를 읽지 않고 필요한 범위만 찾을 수 있습니다. 먼저 읽는 input의 cardinality가 작고 인덱스의 선택도가 높을수록 유리합니다. 반대로 먼저 읽는 input에서 많은 행이 나오거나 적절한 인덱스가 없다면 안쪽 input을 반복해서 읽는 cost가 크게 증가합니다.

따라서 Nested Loop Join에서는 두 input의 위치가 중요합니다. CBO는 cardinality와 access path를 바탕으로 어떤 input을 먼저 읽을지, 다른 input을 인덱스로 탐색할 수 있는지를 함께 판단합니다.

Hash Join

Hash Join은 build side를 먼저 읽어 JOIN key를 기준으로 해시 테이블을 만듭니다. 이후 probe side를 읽으면서 같은 해시 값을 가진 행을 찾고, 실제 JOIN 조건을 확인해 output을 만듭니다.

인덱스나 정렬된 input이 없어도 두 input을 순차적으로 처리할 수 있어 큰 데이터 사이의 equi-join에 유리합니다. 일반적으로 크기가 작은 input을 build side로 선택해야 해시 테이블의 메모리 사용량을 줄일 수 있습니다.

해시 테이블이 메모리에 들어가지 않으면 데이터를 partition으로 나누어 디스크에 기록한 뒤 다시 처리할 수 있습니다. 이때 추가 I/O가 발생하므로 build side의 cardinality 추정이 중요합니다. 실제 cardinality가 예상보다 크면 메모리 부족과 spill로 인해 예상한 cost와 실제 실행 시간이 크게 달라질 수 있습니다.

Merge Join

Merge Join은 JOIN key 순서로 정렬된 두 input을 함께 읽습니다. 양쪽의 현재 key를 비교해 값이 작은 쪽을 진행하고, 값이 같으면 일치하는 행을 output으로 만듭니다. 같은 key가 여러 번 나타나면 해당 key에 속한 행의 조합을 모두 처리해야 합니다.

두 input이 인덱스나 앞선 연산의 결과로 이미 정렬되어 있다면 별도의 정렬 없이 순차적으로 처리할 수 있습니다. 대량의 데이터를 JOIN하거나 JOIN 결과의 정렬 순서를 이후 ORDER BY, GROUP BY 같은 연산에서 다시 사용할 수 있을 때 유리합니다.

필요한 정렬 순서가 없다면 JOIN 전에 Sort가 추가됩니다. 이 경우 Merge Join 자체의 처리 cost뿐 아니라 두 input의 정렬 cost와 메모리 사용량, 정렬 중 발생할 수 있는 디스크 I/O까지 함께 비교해야 합니다.

물리 Operator Tree

실제 물리 계획에서는 access path와 JOIN 방식이 하나의 operator tree로 연결됩니다.

Hash Join [o.customer_id = c.id]
├─ Full Scan orders o
└─ Hash
   └─ Index Scan customers c [region = 'KR']

leaf node의 Full Scan과 Index Scan은 데이터를 읽는 access path입니다. Hash node는 customers의 output으로 해시 테이블을 만들고, Hash Join은 orders를 probe side로 읽어 결과를 만듭니다. 논리 계획의 JOIN 하나가 물리 계획에서는 scan과 hash table 생성, JOIN operator가 연결된 실행 구조로 구체화됩니다.

6. Left-Deep Join Tree, Right-Deep Join Tree, Bushy Join Tree

같은 테이블을 같은 조건으로 JOIN하더라도 Join Tree의 구조는 달라질 수 있습니다. 대표적인 형태가 Left-Deep Join Tree, Right-Deep Join Tree, Bushy Join Tree입니다.

Join Tree의 구조는 어떤 중간 결과를 먼저 만들지 결정합니다. 이는 중간 결과의 크기와 실행 방식, 메모리 사용량, 병렬 처리 가능성에 영향을 줍니다.

Left-Deep Join Tree

Left-Deep Join Tree는 이전 JOIN의 output이 계속 left input으로 들어가고, right input에는 새로운 테이블이 추가되는 형태입니다.

        JOIN
       /    \
    JOIN     D
   /    \
 JOIN     C
 /  \
A    B

SQL에 작성된 JOIN List를 왼쪽부터 처리하면 자연스럽게 이 구조가 만들어집니다. 이전 JOIN의 output을 다음 JOIN으로 바로 전달하기 쉬우며, 오른쪽 테이블에서 인덱스 탐색을 수행하는 Nested Loop Join과도 잘 맞습니다.

탐색해야 할 후보가 Bushy Join Tree보다 적다는 점도 중요합니다. 초기의 많은 옵티마이저가 Left-Deep Join Tree를 중심으로 JOIN 순서를 탐색한 이유입니다.

다만 Left-Deep Join Tree가 항상 중간 결과를 작게 만드는 것은 아닙니다. A와 B의 JOIN output이 매우 크다면 이후 C와 D를 처리하는 동안 큰 중간 결과가 계속 전달될 수 있습니다.

Right-Deep Join Tree

Right-Deep Join Tree는 새로운 테이블이 left input에 놓이고, 이전 JOIN의 output이 right input으로 들어가는 형태입니다.

 JOIN
 /  \
A   JOIN
    /    \
   B    JOIN
        /  \
       C    D

Hash Join에서는 여러 right input에 대한 해시 테이블을 준비한 뒤, left input을 연속해서 통과시키는 계획으로 활용할 수 있습니다. 조건이 맞으면 probe 흐름을 이어갈 수 있지만 여러 해시 테이블을 동시에 유지해야 하므로 메모리 사용량이 커질 수 있습니다.

논리적인 left input과 right input이 항상 Hash Join의 build side와 probe side를 그대로 뜻하는 것은 아닙니다. DBMS는 물리 계획을 만들면서 input을 교환하거나 별도로 build side를 선택할 수 있습니다.

Bushy Join Tree

Bushy Join Tree는 JOIN의 양쪽 input에 모두 다른 JOIN의 output이 올 수 있는 형태입니다.

       JOIN
      /    \
   JOIN    JOIN
   /  \    /  \
  A    B  C    D

A와 B의 JOIN, C와 D의 JOIN이 서로 독립적이라면 병렬로 처리할 수 있습니다. 양쪽에서 중간 결과를 충분히 줄일 수 있다면 마지막 JOIN이 처리할 데이터도 작아집니다.

반면 가능한 Join Tree 구조가 많아져 옵티마이저가 탐색해야 할 후보가 크게 늘어납니다. 양쪽 중간 결과를 모두 저장해야 하는 실행 계획이라면 메모리 사용량도 증가할 수 있습니다.

비교

형태	특징	장점	주의점
Left-Deep Join Tree	왼쪽에 JOIN output 누적	탐색이 단순하고 Nested Loop Join과 잘 맞음	큰 중간 결과가 계속 전달될 수 있음
Right-Deep Join Tree	오른쪽에 JOIN output 누적	Hash Join의 probe 흐름에 활용 가능	여러 해시 테이블을 동시에 유지할 수 있음
Bushy Join Tree	양쪽에 JOIN output 허용	병렬 처리와 다양한 결합 순서 가능	탐색 공간과 메모리 사용량이 증가할 수 있음

어떤 Join Tree가 가장 좋은지는 쿼리와 데이터 분포, 사용할 JOIN 방식에 따라 달라집니다. 또한 OUTER JOIN이나 상관 서브쿼리가 포함되면 선택할 수 있는 Join Tree 구조가 제한될 수 있습니다.

7. CBO가 JOIN 순서를 정하는 방법

CBO는 Cost-Based Optimizer로, 여러 실행 계획의 cost를 추정하고 그중 가장 낮은 후보를 선택합니다. JOIN이 여러 개라면 단순히 테이블 순서만 비교하지 않습니다.

JOIN 순서
× Join Tree 구조
× 테이블 접근 경로
× JOIN 방식
× physical property

같은 JOIN 순서라도 Full Scan과 Index Scan 중 무엇을 사용하는지, Hash Join과 Nested Loop Join 중 무엇을 선택하는지에 따라 서로 다른 실행 계획이 됩니다.

탐색 공간

A, B, C를 JOIN하는 쿼리는 여러 Join Tree로 표현할 수 있습니다.

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

테이블 수가 늘어나면 가능한 JOIN 순서는 순열 수만큼 증가하고, Bushy Join Tree까지 허용하면 괄호를 배치하는 방법도 함께 증가합니다. 여기에 각 테이블의 접근 경로와 JOIN 방식까지 조합하면 모든 실행 계획을 직접 생성해 비교하기 어려워집니다.

CBO는 가능한 계획을 넓게 살펴보면서도 최적화에 사용하는 시간과 메모리를 제한해야 합니다.

Dynamic Programming

전통적인 JOIN 순서 탐색은 작은 relation set의 최적 계획을 먼저 구하고, 그 결과를 더 큰 relation set의 계획을 만드는 데 재사용합니다.

1개 relation
{A}  {B}  {C}

2개 relation
{A, B}  {A, C}  {B, C}

3개 relation
{A, B, C}

먼저 A, B, C를 각각 읽는 access path를 비교합니다. 다음으로 두 relation을 결합하는 후보를 만들고, 마지막으로 세 relation을 모두 포함하는 후보를 만듭니다.

{A, B, C}를 만드는 방법은 하나가 아닙니다.

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

각 조합은 서로 다른 중간 결과와 cost를 가집니다. Dynamic Programming은 같은 relation set에 대한 계산을 반복하지 않고 이전 단계의 결과를 재사용합니다.

System R의 고전적인 옵티마이저는 Left-Deep Join Tree를 중심으로 이러한 방식을 사용했습니다. relation set을 작은 단위부터 확장하는 방식은 오늘날 CBO에서도 널리 사용합니다.

Cardinality와 Cost

JOIN 후보의 cost를 계산하려면 먼저 output cardinality를 추정해야 합니다. 일반적으로 하위 계획의 cost와 JOIN 자체의 처리 비용을 합쳐 상위 계획의 cost를 계산합니다.

상위 계획의 cost
= left input의 cost
+ right input의 cost
+ JOIN 처리 cost

JOIN 처리 cost는 input cardinality와 JOIN 방식, 인덱스 사용 여부, 정렬 상태, 메모리 크기 등에 따라 달라집니다.

cardinality 추정이 틀리면 이후 계산도 연쇄적으로 어긋납니다. 실제로는 큰 중간 결과를 작게 추정하면 Nested Loop Join이나 잘못된 JOIN 순서가 선택될 수 있습니다. 반대로 작은 결과를 크게 추정하면 유리한 계획이 후보에서 너무 일찍 제거될 수 있습니다.

CBO에서 cardinality 추정이 JOIN 순서 탐색만큼 중요한 이유입니다.

Physical Property

같은 relation set을 만드는 후보라고 해서 cost가 가장 낮은 계획 하나만 남길 수 있는 것은 아닙니다. 현재 cost가 조금 높더라도 이후 연산에 유리한 physical property를 제공할 수 있기 때문입니다.

대표적인 예가 정렬 순서입니다. 이미 특정 컬럼으로 정렬된 계획은 이후 Merge Join이나 ORDER BY, GROUP BY에서 별도의 Sort를 피할 수 있습니다.

최저 cost 후보
정렬된 output을 제공하는 후보
특정 distribution을 제공하는 후보
parameterized scan이 가능한 후보

System R에서는 이후 연산에 유용한 정렬 순서를 interesting order로 다뤘습니다. 현대 옵티마이저는 ordering뿐 아니라 distribution, parallelism, parameterization 같은 속성도 함께 관리할 수 있습니다.

따라서 최적 후보는 relation set만으로 결정되지 않습니다. relation set과 필요한 physical property의 조합마다 다른 최적 계획이 존재할 수 있습니다.

탐색 제한

테이블 수가 많아지면 Dynamic Programming만으로도 탐색 비용이 지나치게 커질 수 있습니다. 실제 CBO는 여러 방법으로 후보를 제한합니다.

JOIN 조건으로 연결된 relation set을 우선 탐색합니다.
불필요한 Cartesian Product를 피합니다.
이미 찾은 최저 cost보다 cost가 높은 후보를 조기에 제거합니다.
동일한 결과와 physical property를 가진 후보 중 cost가 낮은 계획만 남깁니다.
탐색 시간이나 후보 수에 제한을 둡니다.
JOIN 수가 많으면 heuristic이나 genetic algorithm을 사용합니다.

OUTER JOIN, SEMI JOIN, ANTI JOIN, LATERAL과 같은 연산은 가능한 JOIN 순서에도 제약을 만듭니다. CBO는 cost가 낮다는 이유만으로 의미가 달라지는 Join Tree를 선택할 수 없습니다. 먼저 의미적으로 허용되는 변환인지 확인한 뒤 cost를 비교해야 합니다.

최종 계획

CBO가 탐색하는 동안에는 하나의 Join Tree만 존재하지 않습니다. 같은 output을 만드는 여러 논리 표현과 물리 실행 방식이 동시에 후보로 관리됩니다.

탐색이 끝나면 필요한 physical property를 만족하면서 estimated cost가 가장 낮은 후보가 선택됩니다. 선택된 결과는 실행 가능한 물리 계획으로 구성되어 executor에 전달됩니다.

이 글에서는 CBO가 여러 JOIN 후보를 관리하는 이유와 기본 구조까지만 다룹니다. JOIN 순서의 후보 수와 Dynamic Programming 점화식, DPccp와 DPhyp 같은 열거 알고리즘은 2편인 CBO는 JOIN 순서를 어떻게 찾는가에서 이어서 다룹니다.

8. 실제 DBMS는 JOIN을 어떻게 표현하는가

DBMS 내부에서 JOIN을 표현하는 구조는 하나로 고정되어 있지 않습니다. SQL을 파싱할 때는 사용자가 작성한 문법을 보존해야 하고, 최적화할 때는 여러 JOIN 순서와 실행 방식을 비교해야 하며, 실행할 때는 선택된 계획을 executor에 전달해야 합니다.

같은 DBMS 안에서도 JOIN은 처리 단계에 따라 다른 구조로 표현됩니다.

SQL
→ 파싱된 쿼리
→ 논리 계획
→ Rule-based Rewrite
→ JOIN 순서 탐색
→ 물리 계획
→ 실행

PostgreSQL

PostgreSQL은 확장성과 SQL 표준 지원을 중시하는 범용 오픈소스 관계형 DBMS입니다.

파싱과 분석을 마친 쿼리는 Query를 중심으로 표현됩니다. 명시적으로 작성된 JOIN은 JoinExpr에 JOIN 종류와 left input, right input, JOIN 조건을 보존합니다. 쉼표로 나열한 FROM 항목과 명시적 JOIN은 query tree 안에서 함께 관리됩니다.

옵티마이저는 query tree를 그대로 실행 계획으로 사용하지 않습니다. 기본 테이블과 JOIN으로 만들어지는 relation set마다 RelOptInfo를 구성하고, 같은 relation set을 만드는 여러 Path를 비교합니다. 같은 relation set이라도 Table Scan과 Index Scan, Nested Loop Join과 Hash Join, Merge Join처럼 서로 다른 후보가 존재할 수 있습니다.

각 Path에는 estimated cardinality와 cost, 정렬 순서 같은 정보가 포함됩니다. 최종적으로 가장 적합한 Path가 선택되면 executor가 사용할 Plan이 만들어집니다. PostgreSQL은 파싱 단계에서 query tree를 사용하고, 탐색 단계에서 RelOptInfo와 Path를 비교한 뒤, 선택된 Plan을 실행 단계로 넘깁니다.

Oracle Database

Oracle Database는 대규모 기업 환경에서 널리 사용되는 상용 관계형 DBMS입니다.

Oracle은 SQL을 하나 이상의 Query Block으로 나누어 최적화합니다. 각 Query Block에는 SELECT, FROM, WHERE, GROUP BY처럼 하나의 쿼리 단위를 이루는 정보가 포함됩니다. 옵티마이저는 View Merging, Subquery Unnesting, Predicate Pushing 같은 Query Transformation을 적용해 논리적으로 동등한 형태를 만듭니다.

이후 Plan Generator가 JOIN 순서와 access path, JOIN 방식을 조합해 후보 계획을 만들고 cost를 비교합니다. 최종 실행 계획에서 Table Access와 Nested Loops, Hash Join, Merge Join은 Row Source를 input으로 받아 새로운 Row Source를 output으로 만듭니다.

Oracle은 옵티마이저의 내부 자료 구조를 모두 공개하지 않습니다. 따라서 공개 문서로 확인되는 Query Block과 Query Transformation, 후보 계획 생성, Row Source 실행 구조를 넘어 특정 내부 표현을 단정하기는 어렵습니다.

MySQL

MySQL은 웹 서비스와 OLTP 환경에서 널리 사용되는 오픈소스 관계형 DBMS입니다.

파싱된 쿼리에서는 Table_ref 계열의 구조가 테이블과 JOIN 관계를 표현합니다. 전통적인 JOIN 옵티마이저는 JOIN prefix를 확장하며 실행 순서를 탐색합니다. 하나의 테이블에서 시작해 다른 테이블을 차례로 추가하면서 더 많은 테이블을 포함하는 후보를 만듭니다.

MySQL에는 JOIN 관계를 Join Hypergraph로 변환하는 Hypergraph Join Optimizer도 있습니다. 테이블은 node가 되고 JOIN 조건은 edge 또는 hyperedge가 됩니다. 옵티마이저는 의미적으로 결합할 수 있는 subplan을 작은 relation set부터 만들고, 각 후보의 cardinality와 cost를 계산합니다.

선택된 실행 방법은 AccessPath로 표현됩니다. AccessPath에는 Table Scan, Index Scan, Nested Loop Join, Hash Join, Sort와 같은 실행 방식과 estimated cardinality, cost가 포함됩니다. JOIN 순서를 탐색하는 구조와 executor에 전달하는 계획 구조가 서로 분리되어 있습니다.

DuckDB

DuckDB는 프로세스 내부에 내장해 사용하는 컬럼 기반 분석용 DBMS입니다.

파싱과 바인딩을 거친 쿼리는 LogicalOperator를 연결한 논리 계획으로 표현됩니다. JOIN은 두 child operator를 input으로 받는 논리 연산자이며, JOIN 종류와 조건을 포함합니다.

Join Order Optimizer는 논리 계획에서 JOIN에 참여하는 relation과 predicate를 추출해 Join Hypergraph를 구성합니다. 이후 가능한 relation set과 결합 방법을 열거하고, cardinality와 cost를 바탕으로 JOIN 순서를 선택합니다. 선택이 끝나면 해당 순서에 맞는 Join Tree를 다시 구성합니다.

물리 계획 단계에서는 JOIN 조건과 데이터 특성에 따라 Hash Join을 비롯한 구체적인 JOIN 방식이 선택됩니다. 논리 계획의 Join Tree와 JOIN 순서 탐색에 사용하는 Join Hypergraph, 실행에 사용하는 물리 연산자가 구분되어 있습니다.

Apache Calcite

Apache Calcite는 데이터를 직접 저장하는 DBMS가 아니라 SQL 파싱과 관계 연산, 쿼리 최적화 기능을 제공하는 프레임워크입니다.

Calcite는 SQL을 파싱한 뒤 관계 연산을 RelNode로 변환합니다. Logical Join은 left input과 right input을 가지며, 두 input을 결합해 새로운 RelNode를 output으로 만듭니다.

VolcanoPlanner는 각 Join Tree를 독립된 후보로만 관리하지 않습니다. 같은 결과를 만드는 관계식을 RelSet으로 묶고, 같은 physical property를 가진 후보를 RelSubset으로 구분합니다. 하나의 relation set에 여러 JOIN 순서와 실행 방식, physical property가 함께 존재할 수 있습니다.

최적화가 끝나면 필요한 physical property를 만족하면서 cost가 가장 낮은 후보가 선택됩니다. Calcite에서 개별 JOIN은 두 input을 받는 연산자이지만, 전체 탐색 공간은 여러 동등한 표현과 물리 후보를 공유하는 Memo 구조에 가깝습니다.

비교

시스템	파싱 및 논리 표현	JOIN 탐색	선택된 계획
PostgreSQL	Query, JoinExpr	RelOptInfo, Path	Plan
Oracle Database	Query Block	후보 실행 계획	Row Source 실행 계획
MySQL	Table_ref	JOIN prefix 또는 Join Hypergraph	AccessPath
DuckDB	LogicalOperator	Join Hypergraph	논리 및 물리 operator
Apache Calcite	RelNode	RelSet, RelSubset, Memo	선택된 RelNode

9. Binary Join Tree만으로 충분한가

Binary Join Tree는 하나의 JOIN 순서와 각 연산의 input, output을 표현하기에 적합합니다. 중간 결과가 어느 단계에서 만들어지는지 명확하고, 선택된 계획을 executor가 따라가기도 쉽습니다.

하지만 CBO가 다뤄야 하는 것은 하나의 계획이 아니라 같은 결과를 만드는 여러 후보입니다. Binary Join Tree만으로 모든 후보를 관리하면 동일한 subtree가 여러 계획에 반복해서 등장하고, 논리적으로 같은 output을 만드는 표현끼리의 관계도 별도로 관리해야 합니다.

Binary Join Tree의 한계

A, B, C를 JOIN하는 다음 두 후보를 비교해 보겠습니다.

        JOIN                 JOIN
       /    \               /    \
    JOIN     C             A     JOIN
   /    \                       /    \
  A      B                     B      C

두 Join Tree는 서로 다른 JOIN 순서를 직접 보여줍니다. 그러나 후보가 늘어나면 각 Join Tree를 독립적으로 생성하고 보관해야 합니다. 같은 relation set이나 access path가 여러 Join Tree에 포함되더라도 Binary Join Tree 자체에는 이들이 같은 최적화 문제라는 정보가 없습니다.

또한 Binary Join Tree는 이미 하나의 결합 순서를 선택한 구조입니다. 아직 JOIN 순서를 정하지 않은 상태에서 어떤 테이블이 predicate로 연결되어 있는지, 어떤 조합이 의미적으로 허용되는지를 표현하기에는 적합하지 않습니다.

Join Graph

INNER JOIN 중심의 쿼리는 Join Graph로 나타낼 수 있습니다. 기본 relation은 node가 되고, 두 relation을 연결하는 JOIN predicate는 edge가 됩니다.

A ───── B
 \     /
  \   /
    C

Join Graph는 어느 JOIN을 먼저 실행할지 결정하지 않습니다. 대신 어떤 relation끼리 직접 결합할 수 있는지 보여줍니다. 옵티마이저는 이 그래프에서 연결된 relation set을 찾고, 가능한 JOIN 순서를 탐색할 수 있습니다.

Cartesian Product를 피하려는 경우에도 Join Graph가 유용합니다. 현재 relation set과 edge로 연결된 relation을 우선 추가하면 JOIN predicate가 없는 조합을 불필요하게 탐색하지 않을 수 있습니다.

Join Hypergraph

모든 predicate가 정확히 두 relation만 참조하는 것은 아닙니다.

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

이 predicate는 A, B, C를 함께 참조합니다. 일반적인 Graph의 edge는 두 node 사이의 관계를 표현하므로 이런 조건을 직접 나타내기 어렵습니다.

Join Hypergraph의 hyperedge는 하나의 node가 아니라 relation set을 연결할 수 있습니다. OUTER JOIN, SEMI JOIN, ANTI JOIN처럼 JOIN 순서에 제약이 있는 연산도 단순한 무방향 edge보다 더 많은 정보를 필요로 합니다.

Join Hypergraph는 가능한 결합과 제약을 표현하고, Binary Join Tree는 그 가운데 선택된 결합 순서를 표현합니다.

Memo

Join Graph와 Join Hypergraph가 JOIN 관계와 탐색 가능성을 표현한다면, Memo는 탐색 과정에서 생성된 동등한 후보를 저장하고 공유하는 구조입니다.

Memo에서는 같은 논리적 output을 만드는 표현을 하나의 group으로 묶을 수 있습니다.

Group {A, B, C}
├── Join(Group {A, B}, Group {C})
├── Join(Group {A, C}, Group {B})
└── Join(Group {A}, Group {B, C})

각 child group도 여러 논리 표현과 물리 실행 방식을 가질 수 있습니다. {A, B}를 만드는 결과가 여러 상위 후보에서 필요하더라도 같은 group을 참조하므로 subtree를 반복해서 만들 필요가 없습니다.

Memo는 다음 정보를 함께 관리할 수 있습니다.

논리적으로 동등한 표현
Hash Join, Nested Loop Join 같은 물리 구현
cardinality와 cost
ordering과 distribution 같은 physical property
physical property별 최적 후보

따라서 Memo는 하나의 Join Tree라기보다 동등한 표현과 대안을 공유하는 AND-OR Graph에 가깝습니다. Group은 같은 output을 만드는 대안을 나타내고, 각 표현은 필요한 child group을 조합하는 방법을 나타냅니다.

선택된 계획

Join Graph, Join Hypergraph, Memo를 사용하더라도 실행 단계에서는 하나의 계획을 선택해야 합니다. 탐색이 끝나면 각 group과 physical property에서 선택된 후보를 따라 실행 가능한 물리 계획을 구성합니다.

Join Graph 또는 Join Hypergraph
→ 후보 생성과 Memo 탐색
→ 선택된 Binary Join Tree
→ 물리 실행 계획

구조	주된 역할
JOIN List	SQL에 작성된 JOIN 순서 보존
Binary Join Tree	하나의 JOIN 순서와 중간 결과 표현
Join Graph	두 relation 사이의 JOIN 가능성 표현
Join Hypergraph	relation set 사이의 predicate와 제약 표현
Memo	동등한 논리 표현과 물리 후보 공유

10. 개인적인 생각

JOIN을 하나의 자료 구조로 모두 표현할 필요는 없다고 생각합니다. SQL을 보존하는 표현, JOIN 순서를 탐색하는 표현, 후보를 공유하는 표현, 실행할 계획을 전달하는 표현은 목적이 다릅니다. Binary Join Tree는 하나의 후보와 선택된 계획을 표현하기에 적합하지만, 여러 후보를 비교하기 시작하면 relation set과 Join Graph, Join Hypergraph, Memo 같은 별도의 구조가 필요할 수 있습니다.

그렇다고 모든 DBMS가 처음부터 Join Hypergraph와 Memo를 갖춰야 하는 것은 아닙니다. 최적화 범위가 작고 JOIN 수가 제한적이라면 Binary Join Tree와 간단한 동적 계획법만으로도 충분할 수 있습니다. 복잡한 표현은 탐색 공간이 실제로 커지고, OUTER JOIN 같은 순서 제약이나 physical property를 함께 다뤄야 할 때 필요해집니다. 표현 구조의 복잡도 역시 옵티마이저가 감당해야 하는 비용입니다.

구현 순서도 같은 관점에서 보는 편이 좋습니다. 먼저 SQL에 명시된 JOIN 종류, 조건, 순서와 괄호를 정확히 보존해야 합니다. 그다음 Binary Join Tree로 중간 결과와 실행 단위를 분명하게 만들고, cardinality와 cost를 비교할 필요가 생겼을 때 Join Graph나 Memo 같은 탐색 구조를 추가하는 편이 자연스럽습니다. 정확한 의미 보존 없이 JOIN reordering부터 시작하면 잘못된 계획을 더 빠르게 찾는 옵티마이저가 될 수 있습니다.

결국 JOIN을 어떤 하나의 구조로 표현해야 하는가라는 질문에는 유일한 정답이 없습니다. SQL 단계에서는 JOIN List가 필요하고, 하나의 계획을 나타낼 때는 Binary Join Tree가 적합하며, CBO의 탐색에는 Join Graph, Join Hypergraph, Memo가 필요할 수 있습니다. 좋은 표현은 가장 정교한 표현이 아니라, 현재 단계에서 필요한 정보와 허용되는 변환을 가장 분명하게 드러내는 표현이라고 생각합니다.

References

논문

E. F. Codd. A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, 1970.
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.
Goetz Graefe, William J. McKenna. The Volcano Optimizer Generator: Extensibility and Efficient Search. IEEE ICDE, 1993.
Goetz Graefe. The Cascades Framework for Query Optimization. IEEE Data Engineering Bulletin, 1995.
Surajit Chaudhuri. An Overview of Query Optimization in Relational Systems. ACM PODS, 1998.
Guido Moerkotte, Thomas Neumann. Dynamic Programming Strikes Back. ACM SIGMOD, 2008.
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

Table Expressions
Planner and Optimizer
Controlling the Planner with Explicit JOIN Clauses
PostgreSQL source: parsenodes.h, pathnodes.h, plannodes.h

Oracle Database

MySQL

DuckDB

Apache Calcite

주재완

https://sprout6626.tistory.com

이전 포스트

[GlueSQL] Todo 앱으로 살펴본 GlueSQL: SQL 엔진과 Storage Adapter 구조

다음 포스트

[DB] JOIN의 내부

Database

1. SQL은 JOIN을 어떻게 표현하는가

2. 관계대수에서 JOIN

3. Binary Join Tree

JOIN List를 왼쪽부터 처리하기

Left-Deep Join Tree

JOIN 결합 구조

4. 왜 Binary Join Tree를 사용하는가

중간 결과

Cardinality

Cost

Predicate Pushdown

Rule-based Rewrite

Join Reordering

5. JOIN 실행 방식

Nested Loop Join

Hash Join

Merge Join

물리 Operator Tree

6. Left-Deep Join Tree, Right-Deep Join Tree, Bushy Join Tree

Left-Deep Join Tree

Right-Deep Join Tree

Bushy Join Tree

비교

7. CBO가 JOIN 순서를 정하는 방법

탐색 공간

Dynamic Programming

Cardinality와 Cost

Physical Property

탐색 제한

최종 계획

8. 실제 DBMS는 JOIN을 어떻게 표현하는가

PostgreSQL

Oracle Database

MySQL

DuckDB

Apache Calcite

비교

9. Binary Join Tree만으로 충분한가

Binary Join Tree의 한계

Join Graph

Join Hypergraph

Memo

선택된 계획

10. 개인적인 생각

References

논문

공식 문서 및 구현

PostgreSQL

Oracle Database

MySQL

DuckDB

Apache Calcite

[GlueSQL] Todo 앱으로 살펴본 GlueSQL: SQL 엔진과 Storage Adapter 구조

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

0개의 댓글