[PostgreSQL] NL Join과 Hash Join은 어떻게 선택된걸까

Table

우선 식당(restaurants)과 게시글(articles) 테이블을 가지고 여러 가지 테스트를 해볼 것이다. 식당 테이블에는 약 34만개, 게시글에는 1000개의 데이터가 존재한다.

 

PK인 id만을 가지고 테스트를 해볼 것이기 때문에 스키마는 생략한다. 단, 추가로 articles의 restaurant_id를 가지는 인덱스 restaurant_idx를 생성했다.

NL Join & Index Scan

select  *  
from restaurants r , articles a  
where r.id < 10  
    and r.id = a.restaurant_id;

Nested Loop  (cost=0.70..71.30 rows=1 width=855) (actual time=0.047..0.049 rows=0 loops=1)
  ->  Index Scan using restaurants_pkey on restaurants r  (cost=0.42..8.58 rows=9 width=340) (actual time=0.006..0.009 rows=9 loops=1)
        Index Cond: (id < 10)
  ->  Index Scan using restaurant_idx on articles a  (cost=0.28..6.96 rows=1 width=515) (actual time=0.004..0.004 rows=0 loops=9)
        Index Cond: (restaurant_id = r.id)
Planning Time: 0.315 ms
Execution Time: 0.086 ms

 

위와 같이 식당 테이블(r)을 조회하는 조건을 id < 10로 지정할 경우, NL Join과 Index Scan이 일어나는 것을 확인할 수 있다.

1. id < 10인 식당 9개 조회
2. 조회한 각 식당의 id를 가지고 restaurant_idx 인덱스 테이블에서 Scan
3. Scan된 인덱스에 해당하는 데이터 조회 (2 - 3 반복)

Hash Join & Seq/Index Scan

select  *  
from restaurants r , articles a  
where r.id < 100  
    and r.id = a.restaurant_id;

Hash Join  (cost=15.45..95.08 rows=1 width=855) (actual time=0.819..0.825 rows=0 loops=1)
  Hash Cond: (a.restaurant_id = r.id)
  ->  Seq Scan on articles a  (cost=0.00..77.00 rows=1000 width=515) (actual time=0.012..0.461 rows=1000 loops=1)
  ->  Hash  (cost=14.19..14.19 rows=101 width=340) (actual time=0.087..0.088 rows=99 loops=1)
        Buckets: 1024  Batches: 1  Memory Usage: 45kB
        ->  Index Scan using restaurants_pkey on restaurants r  (cost=0.42..14.19 rows=101 width=340) (actual time=0.011..0.051 rows=99 loops=1)
              Index Cond: (id < 100)
Planning Time: 0.581 ms
Execution Time: 0.909 ms

id < 100으로 변경하고 다시 쿼리를 실행하면, 위 처럼 Hash Join을 적용한다.

 

Hash Join의 경우 Query Plan에서 Hash 부분부터 읽으면 된다. id < 100에 해당하는 99개의 식당 데이터를 Index Scan으로 조회하고 해시 테이블을 생성한다. 이때 In-memory 해시 조인이 일어난다. (Build 단계) 이후 Probe Input에 해당하는 게시글 게이터를 Seq Scan을 통해 해시 맵을 탐색한다. (Probe 단계)

1. id < 100에 해당하는 99개의 식당 데이터를 Index Scan
2. 식당 해시 테이블 생성
3. 게시글 데이터를 Seq Scan하며 해시 맵 탐색

NOTE

• Bucket: 해시 테이블 내에서 각 고유 해시 값을 저장하는데 사용되는 슬롯
• Batch: 값이 1일 경우 In-memory, 2 이상일 경우 Temp 테이블 또는 디스크에 나누어서 처리

NL Join을 적용한다면?

위에서 이상한 점은 왜 NL Join이 아니라 Hash Join이 적용되었는가 하는 점이다. 99개의 식당 데이터를 Index Scan하고 해당 식당 id로 restaurant_idx 인덱스 테이블에 탐색하는 것이 더 효율적이지 않을까?

 

굳이 해시 테이블을 생성하고 모든 게시글 데이터를 Seq Scan하여 탐색하는 것이 맞을까?

 

일단 pg_hint_plan extension을 사용하여 NL Join으로 적용하여 확인해보았다.

select /*+ nestloop(r a) */ *  
from restaurants r , articles a  
where r.id < 100  
    and r.id = a.restaurant_id;

Nested Loop  (cost=0.70..300.74 rows=1 width=855) (actual time=0.131..0.132 rows=0 loops=1)
  ->  Index Scan using restaurants_pkey on restaurants r  (cost=0.42..14.19 rows=101 width=340) (actual time=0.010..0.036 rows=99 loops=1)
        Index Cond: (id < 100)
  ->  Index Scan using restaurant_idx on articles a  (cost=0.28..2.83 rows=1 width=515) (actual time=0.001..0.001 rows=0 loops=99)
        Index Cond: (restaurant_id = r.id)
Planning Time: 0.282 ms
Execution Time: 0.168 ms

평균적으로 Execution Time이 비교적 NL Join을 적용하였을 때 더 작은 값이 출력되었다. (NL Join이 더 빠름)

 

하지만 cost는 NL이 300.74, Hash가 95.08로 계산되어 3배가량 차이가나는 것을 확인할 수 있다.

I/O Cost

• seq_page_cost: Seq Scan 방식으로 1 블록을 읽는 비용 (default 1)
• random_page_cost: Index Scan 방식으로 1 블록을 읽는 비용 (default 4)

위 두 가지 I/O cost 값을 확인해보면 Seq와 Index Scan이 서로 4배가 차이난다. 즉, Index Scan을 4배 정도 비싸게 계산한다는 의미인데 대부분 오늘날 메모리, 디스크 성능이 좋아지면서 이러한 차이는 과한 것 같다 라는 의견이 많았다.

 

postgresql.conf에서 random_page_cost를 4.0 -> 2.0으로 수정하고 다시 쿼리를 실행해보았다.

Hash Join

select  *  
from restaurants r , articles a  
where r.id < 100  
    and r.id = a.restaurant_id;

Hash Join  (cost=11.18..90.81 rows=1 width=855) (actual time=0.833..0.838 rows=0 loops=1)
  Hash Cond: (a.restaurant_id = r.id)
  ->  Seq Scan on articles a  (cost=0.00..77.00 rows=1000 width=515) (actual time=0.012..0.420 rows=1000 loops=1)
  ->  Hash  (cost=10.03..10.03 rows=92 width=340) (actual time=0.095..0.097 rows=99 loops=1)
        Buckets: 1024  Batches: 1  Memory Usage: 45kB
        ->  Index Scan using restaurants_pkey on restaurants r  (cost=0.42..10.03 rows=92 width=340) (actual time=0.012..0.054 rows=99 loops=1)
              Index Cond: (id < 100)
Planning Time: 0.636 ms
Execution Time: 0.924 ms

NL Join

select /*+ nestloop(r a) */ *  
from restaurants r , articles a  
where r.id < 100  
    and r.id = a.restaurant_id;

Nested Loop  (cost=0.70..159.86 rows=1 width=855) (actual time=0.481..0.484 rows=0 loops=1)
  ->  Index Scan using restaurants_pkey on restaurants r  (cost=0.42..10.03 rows=92 width=340) (actual time=0.038..0.094 rows=99 loops=1)
        Index Cond: (id < 100)
  ->  Index Scan using restaurant_idx on articles a  (cost=0.28..1.62 rows=1 width=515) (actual time=0.003..0.003 rows=0 loops=99)
        Index Cond: (restaurant_id = r.id)
Planning Time: 1.250 ms
Execution Time: 0.615 ms

이번에도 cost가 Hash는 90.81, NL은 159.86으로 Hash가 더 비용이 낮았다. 하지만 그 차이가 많이 줄어든 것을 확인할 수 있었다.

 

random_page_cost를 1.1수정하고 다시 실행했을 때의 cost는 Hash 89.22, NL 107.6이 출력되었다.

 

결과적으로 대량 데이터가 아님에도 불구하고 Hash Join이 적용되는 것이 못마땅해보인다.

CPU Cost

• cpu_tuple_cost: Seq Scan 방식으로 1개의 레코드를 액세스하는 비용 (default 0.01)
• cpu_index_tuple_cost: Index Scan 방식으로 1개의 레코드를 액세스하는 비용 (default 0.005)
• cpu_operator_cost: 레코드 1개를 필터링 하는 비용 (default 0.0025)

추가로 위 설정 값 중 cpu_tuple_cost 값을 수정해보면서 테스트해보았다.

 

그 결과, 0.01 -> 0.04 로 변경했을 때 Hash Join이 아닌 NL Join으로 실행되는 것을 확인할 수 있었다.

select  *  
from restaurants r , articles a  
where r.id < 100  
    and r.id = a.restaurant_id;

Nested Loop  (cost=0.70..117.20 rows=1 width=856) (actual time=0.336..0.338 rows=0 loops=1)
  ->  Index Scan using restaurants_pkey on restaurants r  (cost=0.42..11.28 rows=98 width=341) (actual time=0.018..0.070 rows=99 loops=1)
        Index Cond: (id < 100)
  ->  Index Scan using restaurant_idx on articles a  (cost=0.28..1.04 rows=1 width=515) (actual time=0.002..0.002 rows=0 loops=99)
        Index Cond: (restaurant_id = r.id)
Planning Time: 0.609 ms
Execution Time: 0.416 ms

최종적으로 설정 값은 아래와 같다.

seq_page_cost = 1.0
random_page_cost = 1.1
cpu_tuple_cost = 0.04
cpu_index_tuple_cost = 0.005
cpu_operator_cost = 0.0025

 

하지만 이 설정 값이 올바르다고 할 수는 없다. 여러 쿼리, 여러 경우를 고려하고 테스트를 해보고 판단해야하기 때문에 쉽게 결정할 수 없다. 그럼에도 이러한 테스트 결과를 통해 튜닝하는 방향을 한 가지 얻을 수 있었고, 이를 바탕으로 여러 테스트를 쌓아가며 확립해 나아갈 수 있을 것 같다.

 

[reference]

• https://blog.ex-em.com/1911
• https://hyunwook.dev/224
• https://postgresql.kr/blog/pg_scan_cost.html
• https://www.postgresdba.com/bbs/board.php?bo_table=B12&wr_id=24#google_vignette
• https://stackoverflow.com/questions/10232258/making-postgres-query-faster-more-indexes