Merge Join vs Nested Loop Join

인덱스 생성 전 실행 계획

      ->  Merge Left Join  (cost=8192.75..441426.93 rows=4386 width=150) (actual time=102.871..9919.006 rows=4154 loops=1)
            Merge Cond: ((order.user_id)::text = (user.id)::text)
            ... 생략
            ->  Materialize  (cost=2798.21..425278.44 rows=4075321 width=119) (actual time=79.025..8708.221 rows=4093777 loops=1)
                  ->  Merge Left Join  (cost=2798.21..415090.14 rows=4075321 width=119) (actual time=79.017..7425.337 rows=4092797 loops=1)
                        Merge Cond: ((user.id)::text = (mapper.user_id)::text)
                        ->  Index Scan using user_pkey on user  (cost=0.56..401692.55 rows=4075321 width=82) (actual time=0.048..5698.219 rows=4092797 loops=1)
                        ->  Sort  (cost=2797.64..2866.25 rows=27444 width=37) (actual time=78.961..89.021 rows=27371 loops=1)
                              Sort Key: mapper.user_id
                              Sort Method: quicksort  Memory: 2907kB
                              ->  Seq Scan on mapper  (cost=0.00..774.44 rows=27444 width=37) (actual time=0.008..4.203 rows=27376 loops=1)
...
Planning Time: 0.749 ms
Execution Time: 11816.214 ms

 

인덱스 생성 후 실행 계획

      ->  Nested Loop Left Join  (cost=5400.54..44078.17 rows=4430 width=150) (actual time=27.505..111.089 rows=4155 loops=1)
            ->  Nested Loop Left Join  (cost=5400.13..42127.69 rows=4430 width=150) (actual time=27.486..85.159 rows=4155 loops=1)
                  ...생략
                  ->  Index Scan using user_pkey on user  (cost=0.56..8.17 rows=1 width=82) (actual time=0.011..0.011 rows=1 loops=4155)
                        Index Cond: ((id)::text = (order.user_id)::text)
            ->  Index Only Scan using mapper_user_id_index on mapper  (cost=0.41..0.43 rows=1 width=37) (actual time=0.005..0.005 rows=1 loops=4155)
                  Index Cond: (user_id = (user.id)::text)
                  Heap Fetches: 423
...
Planning Time: 1.613 ms
Execution Time: 2148.665 ms

• mapper_user_id_index 인덱스 생성 후 실행 시간이 단축되었다.

 

인덱스 하나를 생성했을 뿐인데 실행 계획이 Merge Left Join 방식에서 Nested Loop Left Join 방식으로 바뀐 걸 알 수 있다.
어떻게 된 걸까? 그전에 Merge Left Join과 Nested Loop Left Join에 대해서 간단하게 알아보자.

Merge Left Join
- 두 테이블을 정렬한 뒤 병합하여 조인을 수행

Nested Loop Left Join
- 중첩 반복문을 사용하여 조인을 수행

 

변화된 부분1

before

->  Materialize  (cost=2798.21..425278.44 rows=4075321 width=119) (actual time=79.025..8708.221 rows=4093777 loops=1)
                  ->  Merge Left Join  (cost=2798.21..415090.14 rows=4075321 width=119) (actual time=79.017..7425.337 rows=4092797 loops=1)
                        Merge Cond: ((user.id)::text = (mapper.user_id)::text)
                        ->  Index Scan using user_pkey on user  (cost=0.56..401692.55 rows=4075321 width=82) (actual time=0.048..5698.219 rows=4092797 loops=1)
                        ->  Sort  (cost=2797.64..2866.25 rows=27444 width=37) (actual time=78.961..89.021 rows=27371 loops=1)
                              Sort Key: mapper.user_id
                              Sort Method: quicksort  Memory: 2907kB
                              ->  Seq Scan on mapper  (cost=0.00..774.44 rows=27444 width=37) (actual time=0.008..4.203 rows=27376 loops=1)

• 인덱스 생성 전의 실행 계획을 보면 user와 mapper를 조인하기 위해 Merge Left Join 방식으로 수행되고,
  Merge Cond: ((user.id)::text = (mapper.user_id)::text) 조건으로 Merge 하기 위해 user 테이블은 4,092,797건을 접근했으며, mapper 테이블은 user_id를 기준으로 정렬 후 접근했다.
• 해당 과정에서 7초 정도의 시간이 소요된 것을 알 수 있다.

 

after

      ->  Nested Loop Left Join  (cost=5400.54..44078.17 rows=4430 width=150) (actual time=27.505..111.089 rows=4155 loops=1)
           	... 
            ->  Index Only Scan using mapper_user_id_index on mapper  (cost=0.41..0.43 rows=1 width=37) (actual time=0.005..0.005 rows=1 loops=4155)
                  Index Cond: (user_id = (user.id)::text)
                  Heap Fetches: 423

• 인덱스 생성 후에는 Nested Loop Left Join으로 수행되고,  이때 새로 만든 인덱스가 사용되었다.
• (actual time=0.005..0.005 rows=1 loops=4155) 이 부분을 보면 조건에 맞는 데이터는 4155건 임을 알 수 있는데, 이를 통해 개선 전에는 4,092,797건에 불필요하게 접근한 것을 알 수 있다.

 

변화된 부분2

before

      ->  Merge Left Join  (cost=8192.75..441426.93 rows=4386 width=150) (actual time=102.871..9919.006 rows=4154 loops=1)
            Merge Cond: ((order.user_id)::text = (user.id)::text)

• order와 user를 조인하기 위해 Merge Left Join이 사용되었다.

 

after

            ->  Nested Loop Left Join  (cost=5400.13..42127.69 rows=4430 width=150) (actual time=27.486..85.159 rows=4155 loops=1)
                  ...생략
                  ->  Index Scan using user_pkey on user  (cost=0.56..8.17 rows=1 width=82) (actual time=0.011..0.011 rows=1 loops=4155)
                        Index Cond: ((id)::text = (order.user_id)::text)

• order와 user를 조인하기 위한 방식이 Merge Left Join에서 Nested Loop Left Join으로 변경되었다.

 

추가적으로 다음과 같이 궁금한 점이 생겼다.
- mapper 테이블의 인덱스를 생성했는데 왜 order와 user를 조인하는 방식도 같이 바뀐걸까?
- 처음부터 order와 user를 조인할 때에만 Nested Loop Join을 사용했으면 되지 않았을까?

 

처음부터 order와 user를 Nested Loop로 조인하지 않은 이유는, 인덱스 생성 전 단계에서 planner가 해당 방식을 선택할 경우 비용이 더 높게 나왔기 때문이다. 

mapper 인덱스 추가 전에는 user와 mapper 조인을 효율적으로 처리할 수단이 없었기 때문에, order와 user 조인 역시 Merge Join으로 이어지는 연쇄적인 선택을 통해 총 비용을 최소화하려 했다. 그러나 mapper_user_id_index 인덱스 추가 후, mapper 조인이 저렴해짐에 따라 user 테이블에 대한 접근 비용이 전체적으로 낮아졌고, 그 결과 order와 user 조인 역시 Nested Loop Join으로 전환해 전체 쿼리 비용을 절감하는 실행 계획이 선택된 것이다.

정리하자면, 쿼리 최적화 과정은 각 조인 단계를 개별적으로 고정하는 것이 아니라, 모든 조건(인덱스 유무, 통계 정보, 예상 행 수, 비용 등)을 종합적으로 고려하여 전체 계획을 수립한다. mapper 테이블 인덱스가 추가된 결과로, user 테이블 접근 시 전체 비용 구조가 변하면서, 결국 order와 user 간에도 Nested Loop Join이 더 효율적인 전략으로 판단되었기 때문에 실행 계획이 변화한 것이다.

 

*참고
Materialize
중간 결과를 메모리에 캐싱하여 반복적으로 접근해야 할 때 성능을 최적화하기 위해 사용된다. 실행 계획의 하위 노드 결과를 캐싱함으로써 같은 데이터를 반복적으로 읽는 비용을 줄이는 역할을 한다.