My Books

My Slides

rss 아이콘 이미지

MySQL – Block Nested-Loop (BNL)에 대한 이해

MySQL 2017.05.10 15:51 Posted by 시연아카데미

이번 시간에 살펴볼 내용은 Block Nested-Loop (이하 BNL)입니다.

 

MySQL이 BNL을 제공하는 이유는 Nested Loop 조인만 지원하는 한계점을 보완하기 위해서입니다. 예를 들어, 조인 칼럼 인덱스가 없다고 가정해보죠. 이 경우, ORACLE과 PostgreSQL과 같은 DBMS는 해시 조인 또는 머지 조인을 사용합니다. 그런데 Nested Loop 조인만 지원하는 MySQL은 이 문제를 어떻게 처리할까요?

 

만일 BNL 방식이 없다면, Driving 테이블의 건수만큼 Inner 테이블을 스캔 (또는 Index Full Scan)해야만 합니다. 이것은 어마어마한 성능 저하를 초래합니다. 이 문제를 어느 정도 완화하기 위해서 MySQL은 BNL 방식을 고안했습니다.

 

BNL 방식은 프로세스 내에 별도의 버퍼 (이를 조인 버퍼라고 합니다)에 Driving 테이블의 레코드를 저장한 후에 Inner 테이블을 스캔하면서 조인 버퍼를 탐색하는 방식입니다. 따라서 BNL 방식을 사용하면 BNL 방식을 사용하지 않는 것에 비해서는 빠릅니다. 하지만 BNL 방식은 Nested Loop 조인의 한계를 개선하기 위한 차선책일 뿐 근본적인 해결책은 아닙니다. Sort Merge 조인이나 Hash 조인에 비해서 턱없이 느린 방식이기 때문입니다. 이 때문에 MySQL에서도 가능한 빨리 Sort Merge나 Hash 조인을 지원하면 좋겠지만, MySQL 8에서도 아직 지원 예정은 없는 것 같습니다.

 

그럼 예제를 통해 살펴보겠습니다. 참고로, Sort Merge, Hash 조인의 성능을 간접적으로 비교하기 위해서 PostgreSQL과 ORACLE에서 테스트한 결과도 첨부합니다.

 

테스트 환경 구성


 

테스트 환경은 MySQL 5.7입니다.

show variables like "version%";
+-------------------------+---------------------+
| Variable_name           | Value               |
+-------------------------+---------------------+
| version                 | 5.7.18-log          |
| version_comment         | Source distribution |
| version_compile_machine | x86_64              |
| version_compile_os      | Linux               |
+-------------------------+---------------------+

drop table t1;
drop table t2;

create table t1 (c1 integer, c2 integer, dummy char(100)) engine=InnoDB;
create table t2 (c1 integer, c2 integer, dummy char(100)) engine=InnoDB;

call generate_series(1,50000);

insert into t1 select series, series, 'dummy' from  series_tmp order by series limit 5000;
insert into t2 select mod(series,5000), series, 'dummy' from  series_tmp order by series limit 50000;

 

BNL 성능 테스트


 

아래의 Explain 결과처럼 Extra 칼럼에 “Using Join buffer (Block Nested Loop)“가 표시되면 BNL 방식으로 수행된 것입니다. BNL 방식은 조인 칼럼에 적절한 인덱스가 없을 때 수행될 수 있는 방식이므로, BNL 방식으로 수행될 때의 type은 ALL (Table Full Scan) 또는 Index (Index Full Scan)입니다.

 

그리고 Driving 테이블의 레코드를 조인 버퍼에 저장하기 때문에 조인 버퍼의 크기가 매우 중요합니다. 만일 Driving 테이블의 레코드를 조인 버퍼에 모두 저장할 수 없다면, Inner 테이블을 여러 번 스캔해야 하는 부하가 발생합니다. 참고로 아래의 예제는 모두 조인 버퍼 내에서 수행됐으므로, T2 테이블을 1회만 스캔했습니다.

 

따라서 3개의 쿼리 간의 성능 차이는 조인 버퍼를 탐색하는 시간이라고 해도 무방하며, 조인 버퍼 내에 레코드가 많을수록 선형적으로 처리 성능이 저하되는 것을 알 수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
explain
select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 50;
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+----------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows  | filtered | Extra                                              |
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+----------------------------------------------------+
|  1 | SIMPLE      | a     | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  4956 |    11.11 | Using where                                        |
|  1 | SIMPLE      | b     | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 49720 |    10.00 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+----------------------------------------------------+
 
set profiling=1;
 
select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 50;
 
select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 500;
 
select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 5000;
 
show profiles;
+----------+-------------+-------------------------------------------------------------------------------------------+
| Query_ID | Duration    | Query                                                                                     |
+----------+-------------+-------------------------------------------------------------------------------------------+
|        1 |  0.17276250 | select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 50   |
|        2 |  1.57978475 | select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 500  |
|        3 | 15.68152675 | select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 5000 |
+----------+-------------+-------------------------------------------------------------------------------------------+

 

BNL DISABLE 후의 성능 테스트


 

그렇다면 과면 BNL은 정말 효과가 있는 방식일까요?

다음과 같이, 5.7에서부터 제공하는 NO_BNL 힌트를 이용해서 수행 속도를 비교해보겠습니다. 아래의 Explain 결과를 보면 Extra 칼럼에 BNL이 나타나지 않습니다. 즉, NO_BNL 힌트의 영향때문에 BNL 방식으로 수행되지 않은 것인데요. 처리 결과를 보면 알 수 있듯이, BNL 방식에 비해서 5배 이상 느립니다. 이로써 BNL 방식은 어느 정도의 튜닝 효과가 있다고 할 수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
explain
select /*+ NO_BNL(b) */ STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 50;
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows  | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+-------------+
|  1 | SIMPLE      | a     | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  4956 |    11.11 | Using where |
|  1 | SIMPLE      | b     | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 49720 |    10.00 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+-------------+
 
set profiling=1;
 
select /*+ NO_BNL(b) */ STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 50;
 
select /*+ NO_BNL(b) */ STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 500;
 
select /*+ NO_BNL(b) */ STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 5000;
 
show profiles;
 
+----------+-------------+------------------------------------------------------------------------------------------------------------------+
| Query_ID | Duration    | Query                                                                                                            |
+----------+-------------+------------------------------------------------------------------------------------------------------------------+
|        1 |  0.83281350 | select /*+ NO_BNL(b) */ STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 50         |
|        2 |  8.31119800 | select /*+ NO_BNL(b) */ STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 500        |
|        3 | 85.36058425 | select /*+ NO_BNL(b) */ STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 5000       |
+----------+-------------+------------------------------------------------------------------------------------------------------------------+

 

인덱스 생성 후의 성능 테스트


 

그렇다면 인덱스를 생성하면 어떻게 될까요?

당연한 결과지만, 너무나도 빠르게 처리됩니다. 10초 이상 수행된 3번째 쿼리가 인덱스 생성 후에는 0.1초 만에 수행되므로 100배 이상 빨라진 것이죠. 하지만 운영 단계에서 인덱스를 생성하는 것은 매우 부담스러운 작업입니다. 입력 속도 저하, 스토리지 사용량 증가, 다른 쿼리에 대한 영향도 분석 필요 등등. 매우 많은 고려가 필요합니다. 물론 설계 상의 실수로 인해, 반드시 생성해야 할 칼럼에 인덱스를 생성하지 않았던 것이라면 이런 고민을 덜 하겠지만, NDV가 좋지 않은 칼럼에 대한 인덱스 생성은 많은 고려가 필요한 게 사실이니까요. 그렇다면 인덱스를 생성할 수 없다면 어떻게 튜닝을 해야 할까요? 이 부분은 여기를 참고하세요.

 

— 인덱스 생성

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
create index t2_c1_idx on t2(c1);
 
explain
select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 50;
+----+-------------+-------+------------+------+---------------+-----------+---------+------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref        | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-----------+---------+------------+------+----------+-------------+
|  1 | SIMPLE      | a     | NULL       | ALL  | NULL          | NULL      | NULL    | NULL       | 4956 |    11.11 | Using where |
|  1 | SIMPLE      | b     | NULL       | ref  | t2_c1_idx     | t2_c1_idx | 5       | mysql.a.c1 |    9 |   100.00 | NULL        |
+----+-------------+-------+------------+------+---------------+-----------+---------+------------+------+----------+-------------+
 
set profiling=1;
 
select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 50;
 
select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 500;
 
select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 5000;
 
show profiles;
+----------+------------+-------------------------------------------------------------------------------------------+
| Query_ID | Duration   | Query                                                                                     |
+----------+------------+-------------------------------------------------------------------------------------------+
|        1 | 0.00297075 | select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 50   |
|        2 | 0.01187425 | select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 500  |
|        3 | 0.12604875 | select STRAIGHT_JOIN * from t1 a INNER JOIN t2 b ON a.c1=b.c1 and a.c1 between 1 and 5000 |
+----------+------------+-------------------------------------------------------------------------------------------+

 

PostgreSQL 수행 내역


 

PostgreSQL은 해시 조인과 머지 조인을 지원합니다. 따라서 해시 조인과 머지 조인의 수행 결과를 보면 모두 0.1초 이내에 수행됩니다. NL 조인의 수행 속도는 58초 정도인데요. 이 속도를 MySQL과 비교해보면 BNL 방식을 적용한 것보다는 느리고 NO BNL 방식보다는 조금 빠른 정도입니다.

 

— 해시 조인

 

1
2
3
4
5
6
7
8
9
10
11
12
explain analyze select * From t1 a, t2 b where a.c1=b.c1;
 
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
 Hash Join  (cost=122.23..5444.27 rows=121631 width=824) (actual time=1.662..26.778 rows=49990 loops=1)
   Hash Cond: (b.c1 = a.c1)
   ->  Seq Scan on t2 b  (cost=0.00..1018.34 rows=15534 width=412) (actual time=0.009..7.129 rows=50000 loops=1)
   ->  Hash  (cost=102.66..102.66 rows=1566 width=412) (actual time=1.643..1.643 rows=5000 loops=1)
         Buckets: 8192 (originally 2048)  Batches: 1 (originally 1)  Memory Usage: 753kB
         ->  Seq Scan on t1 a  (cost=0.00..102.66 rows=1566 width=412) (actual time=0.004..0.754 rows=5000 loops=1)
 Planning time: 0.073 ms
 Execution time: 30.958 ms

 

— 머지 조인

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
set enable_hashjoin=off;
explain analyze select * From t1 a, t2 b where a.c1=b.c1;
                                                     QUERY PLAN
 
-----------------------------------------------------------------------------------------------------------------------------
 Merge Join  (cost=5208.01..7079.14 rows=121631 width=824) (actual time=40.566..81.406 rows=49990 loops=1)
   Merge Cond: (a.c1 = b.c1)
   ->  Sort  (cost=185.76..189.67 rows=1566 width=412) (actual time=1.420..2.105 rows=5000 loops=1)
         Sort Key: a.c1
         Sort Method: quicksort  Memory: 896kB
         ->  Seq Scan on t1 a  (cost=0.00..102.66 rows=1566 width=412) (actual time=0.007..0.647 rows=5000 loops=1)
   ->  Materialize  (cost=5022.25..5099.92 rows=15534 width=412) (actual time=39.133..58.476 rows=50000 loops=1)
         ->  Sort  (cost=5022.25..5061.09 rows=15534 width=412) (actual time=39.130..48.962 rows=50000 loops=1)
               Sort Key: b.c1
               Sort Method: external merge  Disk: 5816kB
               ->  Seq Scan on t2 b  (cost=0.00..1018.34 rows=15534 width=412) (actual time=0.005..7.529 rows=50000 loops=1)
 Planning time: 0.095 ms
 Execution time: 88.168 ms

 

— NL 조인

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
set enable_mergejoin=off;
explain (analyze, buffers) select * From t1 a, t2 b where a.c1=b.c1;
                                                     QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..366018.58 rows=121631 width=824) (actual time=0.014..58100.334 rows=49990 loops=1)
   Join Filter: (a.c1 = b.c1)
   Rows Removed by Join Filter: 249950010
   Buffers: shared hit=950
   ->  Seq Scan on t2 b  (cost=0.00..1018.34 rows=15534 width=412) (actual time=0.007..40.626 rows=50000 loops=1)
         Buffers: shared hit=863
   ->  Materialize  (cost=0.00..110.49 rows=1566 width=412) (actual time=0.000..0.477 rows=5000 loops=50000)
         Buffers: shared hit=87
         ->  Seq Scan on t1 a  (cost=0.00..102.66 rows=1566 width=412) (actual time=0.003..0.739 rows=5000 loops=1)
               Buffers: shared hit=87
 Planning time: 0.043 ms
 Execution time: 58114.032 ms

 

ORACLE 수행 내역


 

ORACLE 수행 내역을 보면 해시 조인과 머지 조인 모두 0.1초 내로 수행됩니다. 뿐만 아니라 NL 조인도 12초 정도에 수행됩니다. 이 속도는 MySQL의 BNL 방식보다 더 빠르네요.

 

— 해시 조인

 

1
2
3
4
5
6
7
8
9
10
11
select /*+ leading(a b) use_hash(b) gather_plan_statistics */ * from t1 a, t2 b where a.c1=b.c1;
 
select * from table(dbms_xplan.display_cursor(null,null,'allstats last'));
----------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |      1 |        |  49990 |00:00:00.09 |    4196 |       |       |          |
|*  1 |  HASH JOIN         |      |      1 |  48072 |  49990 |00:00:00.09 |    4196 |  1397K|  1118K| 1445K (0)|
|   2 |   TABLE ACCESS FULL| T1   |      1 |   5309 |   5000 |00:00:00.01 |      84 |       |       |          |
|   3 |   TABLE ACCESS FULL| T2   |      1 |  48070 |  50000 |00:00:00.03 |    4112 |       |       |          |
----------------------------------------------------------------------------------------------------------------

 

— 머지 조인

 

1
2
3
4
5
6
7
8
9
10
11
12
13
select /*+ leading(a b) use_merge(b) gather_plan_statistics */ * from t1 a, t2 b where a.c1=b.c1;
 
select * from table(dbms_xplan.display_cursor(null,null,'allstats last'));
-----------------------------------------------------------------------------------------------------------------
| Id  | Operation           | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
-----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |      1 |        |  49990 |00:00:00.10 |     919 |       |       |          |
|   1 |  MERGE JOIN         |      |      1 |  48072 |  49990 |00:00:00.10 |     919 |       |       |          |
|   2 |   SORT JOIN         |      |      1 |   5309 |   5000 |00:00:00.01 |      84 |   832K|   511K|  739K (0)|
|   3 |    TABLE ACCESS FULL| T1   |      1 |   5309 |   5000 |00:00:00.01 |      84 |       |       |          |
|*  4 |   SORT JOIN         |      |   5000 |  48070 |  49990 |00:00:00.04 |     835 |  7282K|  1075K| 6472K (0)|
|   5 |    TABLE ACCESS FULL| T2   |      1 |  48070 |  50000 |00:00:00.01 |     835 |       |       |          |
-----------------------------------------------------------------------------------------------------------------

 

— NL 조인

 

1
2
3
4
5
6
7
8
9
10
11
select /*+ leading(a b) use_nl(b) gather_plan_statistics */ * from t1 a, t2 b where a.c1=b.c1;
 
select * from table(dbms_xplan.display_cursor(null,null,'allstats last'));
-------------------------------------------------------------------------------------
| Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
-------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |      1 |        |  49990 |00:00:12.80 |    4181K|
|   1 |  NESTED LOOPS      |      |      1 |  48072 |  49990 |00:00:12.80 |    4181K|
|   2 |   TABLE ACCESS FULL| T1   |      1 |   5309 |   5000 |00:00:00.01 |    3339 |
|*  3 |   TABLE ACCESS FULL| T2   |   5000 |      9 |  49990 |00:00:11.89 |    4178K|
-------------------------------------------------------------------------------------

 

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License


 

티스토리 툴바