[PostgreSQL] Join 알고리즘에 대해...

PostgreSQL은 테이블 간의 JOIN 작업을 수행하기 위해 주로 세 가지 알고리즘을 사용한다. 

이 세 가지 알고리즘은 Nested Loop, Hash Join, 그리고 Merge Join이다.

 

간혹 join에 대해 질문을 하면 inner, outer 조인에 대해 얘기하는 경우가 많이 있는데. 

좀 더 자세히 질문을 하자면 join 알고리즘에 대해 라고 질문을 줘야겠다.

Nested Loop

이 알고리즘은 한 테이블의 각 행에 대해 다른 테이블의 모든 행을 순회하며 일치하는 행을 찾는다.

이는 특히 작은 데이터 세트에 대해 효율적이며, 또한 인덱스가 적절하게 사용될 수 있을 때 매우 유용하다.

하지만 큰 데이터 세트에 대해 이 방식은 비효율적일 수 있다

Hash Join

이 알고리즘은 먼저 작은 쪽 테이블을 메모리에 해시 테이블로 읽어들인다. 

그 다음, 큰 쪽 테이블을 순회하면서 해시 테이블에서 일치하는 행을 찾는다. 

이 방식은 메모리에 충분한 공간이 있고, 동등 조인(equal join)을 수행할 때 효율적이다.

Merge Join

이 알고리즘은 먼저 두 테이블을 조인 조건에 따라 정렬하고, 두 테이블을 동시에 순회하면서 일치하는 행을 찾는다.

이 방법은 주로 대규모 데이터에 대해 효율적이며, 테이블이 이미 (또는 쉽게) 정렬될 수 있고, 조인 조건이 "같다", "크다", "작다"와 같은 비교 연산자일 때 유용하다.

PostgreSQL의 옵티마이저는 위의 각 JOIN 알고리즘의 비용을 계산하고, 가장 비용이 적은 방법을 선택한다.

이 비용 계산은 테이블의 크기, 조인 조건, 인덱스 사용 가능성, 데이터 분포 등 다양한 요소를 고려한다.

따라서 같은 쿼리라도 데이터베이스의 상황에 따라 다른 JOIN 알고리즘이 선택될 수 있다.

 

PostgreSQL도 hint가 있기는 하나 Oracle 처럼 자유롭게 사용하지는 않는것으로 보인다.

hint를 이용해 실행계획을 제어 할 수 있는데 이 방법은 리스크를 가지고 있기는 하다.

잘 못된 힌트를 사용하거나 플랜이 변경되는 특히 업그레이드등이 있을시에는 큰 영향을 주기도 한다.

 

 

 

여기서 추가로 join에 대해 또 하나 알아둬야 할것이 "Driving Table"과 "Inner Table" 이다.

 

PostgreSQL에서 JOIN 연산을 수행할 때 "Driving Table"과 "Inner Table"이라는 용어를 사용한다.

Driving Table

이는 주로 JOIN 연산의 왼쪽 테이블을 가리키는 용어로, JOIN 연산을 시작하는 데 사용되는 테이블이다.

이 테이블은 Nested Loop Join에서 먼저 순회되는 테이블이며, 쿼리의 최적화 과정에서 이 테이블의 크기와 인덱스 구조 등이 중요한 역할을 한다.

Inner Table

이는 주로 JOIN 연산의 오른쪽 테이블을 가리키는 용어로, JOIN 연산을 수행하는 데 이용되는 두 번째 테이블이다.

이 테이블은 Nested Loop Join에서 두 번째로 순회되며, 또한 Hash Join이나 Merge Join에서 주요 연산이 수행되는 테이블이다.

데이터베이스 쿼리 플래너는 여러 요인을 고려하여 어떤 테이블을 Driving Table로, 어떤 테이블을 Inner Table로 사용할지 결정한다.

이는 테이블의 크기, 인덱스의 존재 여부, 데이터 분포, 테이블 간의 관계 등을 고려하여 최적의 실행 계획을 만드는 데 중요한 역할을 한다.

따라서 이들 용어는 데이터베이스 성능 튜닝과 쿼리 최적화에 있어 중요한 개념이다.

 

여튼 위에 있는 내용이 종합되어 결국 옵티마이저가 수행하게 된다.

그럼 옵티마이저가 드라이빙 테이블과 이너 테이블은 어떻게 구분하는 걸까?

 

PostgreSQL에서 쿼리 최적화기(Query Optimizer)는 Driving Table과 Inner Table을 결정할 때 여러 가지 요소를 고려한다.

이는 복잡한 프로세스로, 다양한 통계 정보, 인덱스 정보, 테이블 크기, JOIN 조건 등을 포함된다고 한다.

테이블의 크기

일반적으로, 작은 테이블이 Driving Table로 선택되며, 큰 테이블이 Inner Table로 선택된다.

작은 테이블을 먼저 순회하면 필터링이 더 효과적이기 때문이다.

인덱스

테이블에 존재하는 인덱스는 테이블을 Driving Table로 선택할지 여부에 큰 영향을 미치게 된다.

만약 테이블에 효율적인 인덱스가 존재하고, 그 인덱스가 JOIN 조건에 활용될 수 있다면, PostgreSQL은 해당 테이블을 Driving Table로 선택할 가능성이 높다.

조인 타입

JOIN의 종류(Inner, Outer, Semi, Anti 등)도 테이블 선택에 영향을 미친다.

예를 들어, LEFT OUTER JOIN의 경우 LEFT 테이블(즉, 쿼리의 왼쪽에 있는 테이블)이 Driving Table이 된다.

통계 정보 

PostgreSQL은 테이블의 통계 정보를 유지하고, 이 정보를 사용하여 쿼리를 최적화한다.

이 통계 정보는 테이블의 크기, 행의 수, 열의 분포 등을 포함하며, 이러한 정보는 테이블을 Driving Table 또는 Inner Table로 결정하는 데 사용된다.

이러한 요소들은 쿼리 최적화기가 실행 계획을 생성하고, 어떤 테이블을 먼저 접근할지, 어떤 조인 알고리즘을 사용할지 결정하는 데 중요한 역할을 한다.

이러한 선택은 전반적인 쿼리 성능에 큰 영향을 미치므로, 이해하고 있어야 한다.

 

요즘은 ORM을 많이 사용해서 그런지 쿼리에 대한 관심이 예전같지 않아 보인다.

다만 여기서 언급된 내요은 꼭 알아둘 필요가 있는거니깐 잊지는 말자.