MySQL8 - Semi Join 과 Anti Join - 안티조인 세미조인

MySQL 8.0에서 SemiJoin 과 AntiJoin에 대해서 확인해보도록 하겠습니다.          

Contents [숨기기]

• 테스트 환경 과 샘플 데이터
• Semi Join 과 Anti Join
• Reference

테스트 환경 과 샘플 데이터

포스팅의 테스트 환경 버전 정보와 샘플 데이터 정보입니다.

• Version : MySQL 8.0.25

• Sample 데이터: dept_emp 테이블과 departments 테이블을 사용하였고 아래 github 에서 다운로드 받을 수 있습니다.

 

datacharmer/test_db: A sample MySQL database with an integrated test suite

A sample MySQL database with an integrated test suite, used to test your applications and database servers

departments 테이블에서 FK는 제거하고 생성하였으며, 테스트를 위해 아래 데이터를 한 건 더 입력하였으며, dept_emp 테이블에 인덱스를 생성하였습니다.

insert into departments(dept_no,dept_name)

values('d010','Office Facility');

 

 

alter table dept_emp add index idx_dept_no(dept_no);

               

Semi Join 과 Anti Join

세미조인은 테이블 풀아웃(table pullout), 중복 제거(duplicate weedout), first match, loose scan, materialization와 같은 multiple execution 전략을 가능하게 하는 preparation-time 변환(transformation)입니다.
옵티마이저는 세미조인 전략을 사용하여 서브 쿼리 실행 성능을 개선합니다.

두 개의 테이블 간의 Inner Join의 경우, 조인은 한 테이블에서 다른 테이블과 일치하는 만큼 행을 여러 번 반환합니다.
그러나 일부 쿼리에서는 조인 수행 시 일치 여부가 중요한 정보이지만 일치하는 횟수는 중요하지 않을 수도 있습니다.

예를 들어, department(부서 정보)와 dept_emp(사원 별 부서정보, 소속된 기간정보)이라는 두 개의 테이블이 있다고 가정할 때, 실제로 사원이 존재하는 부서를 확인하기 위해서 다음과 같이 조인을 사용할 수 있습니다

SELECT departments.dept_no, departments.dept_name

FROM departments

INNER JOIN dept_emp

ON departments.dept_no = dept_emp.dept_no;

 

< ... 출력 결과 생략.....>

| d007 | Sales |

| d007 | Sales |

+---------+--------------------+

331603 rows in set (0.00 sec)

 

explain)

+----+-------------+-------------+-------+---------------+-------------+---------+---------------------+-------+----------+-------------+

| id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra |

+----+-------------+-------------+-------+---------------+-------------+---------+---------------------+-------+----------+-------------+

| 1 | SIMPLE | departments | index | PRIMARY | dept_name | 162 | NULL | 9 | 100.00 | Using index |

| 1 | SIMPLE | dept_emp | ref | idx_dept_no | idx_dept_no | 16 | departments.dept_no | 41392 | 100.00 | Using index |

+----+-------------+-------------+-------+---------------+-------------+---------+---------------------+-------+----------+-------------+

그러나 결과는 각 사원별로 한 번씩 부서정보를 나열하게 됩니다. 쿼리를 수행할 목적에 대한 결과로서는 이는 불필요한 중복 정보입니다.

departments 테이블에서 dept_no 컬럼이 primary key 임으로, SELECT DISTINCT를 사용하여 중복을 제거할 수 있지만, 먼저 모든 일치하는 행을 찾고 나서 중복을 나중에 제거하는 작업은 비효율입니다.

위에서의 동일한 의미의 중복이 제거된 결과는 다음과 같은 서브쿼리를 사용하여 결과를 얻을 수 있습니다.

SELECT dept_no, dept_name

FROM departments

WHERE dept_no IN

(SELECT dept_no FROM dept_emp);

+---------+--------------------+

| dept_no | dept_name |

+---------+--------------------+

| d009 | Customer Service |

| d005 | Development |

| d002 | Finance |

| d003 | Human Resources |

| d001 | Marketing |

| d004 | Production |

| d006 | Quality Management |

| d008 | Research |

| d007 | Sales |

+---------+--------------------+

 

Explain)

*************************** 1. row ***************************

EXPLAIN: -> Nested loop semijoin (cost=43214.95 rows=413929)

-> Index scan on departments using dept_name (cost=1.25 rows=10)

-> Index lookup on dept_emp using idx_dept_no (dept_no=departments.dept_no) (cost=24670612.69 rows=41393)

여기서 옵티마이저는 IN 절이 서브쿼리에서 dept_emp 테이블의 각 dept_no를 하나의 인스턴스만 반환해야 함을 인식할 수 있습니다. 이러한 경우, 쿼리는 semijoin을 사용할 수 있습니다.

다음 문장은 EXISTS가 서브쿼리 조건절에 포함되어 있고, 이전 문장의 IN 서브쿼리 조건절과 동일하게 수행됩니다.

SELECT dept_no, dept_name

FROM departments

WHERE EXISTS

(SELECT * FROM dept_emp WHERE departments.dept_no = dept_emp.dept_no);

 

+---------+--------------------+

| dept_no | dept_name |

+---------+--------------------+

| d009 | Customer Service |

| d005 | Development |

| d002 | Finance |

| d003 | Human Resources |

| d001 | Marketing |

| d004 | Production |

| d006 | Quality Management |

| d008 | Research |

| d007 | Sales |

+---------+--------------------+

 

Explain)

*************************** 1. row ***************************

EXPLAIN: -> Nested loop semijoin (cost=43214.95 rows=413929)

-> Index scan on departments using dept_name (cost=1.25 rows=10)

-> Index lookup on dept_emp using idx_dept_no (dept_no=departments.dept_no) (cost=24670612.69 rows=41393)

이와 같이 MySQL 8.0.16 이후로는 EXISTS가 서브쿼리 조건절이 포함된 모든 문장은 IN 서브쿼리 조건절과 동등한 semijoin 변환의 영향을 받습니다.

또한 MySQL 8.0.17부터는 다음과 같은 서브쿼리가 안티조인(AntiJoin)으로 변환됩니다.

• NOT IN (SELECT ... FROM ...)
• NOT EXISTS (SELECT ... FROM ...)
• IN (SELECT ... FROM ...) IS NOT TRUE
• EXISTS (SELECT ... FROM ...) IS NOT TRUE
• IN (SELECT ... FROM ...) IS FALSE
• EXISTS (SELECT ... FROM ...) IS FALSE.

간단히 말하면, IN (SELECT ... FROM ...) 또는 EXISTS (SELECT ... FROM ...) 형태의 서브쿼리의 부정은 AntiJoin으로 변환됩니다.

안티조인은 일치하는 결과가 없는 행만 반환하는 연산입니다. 다음 쿼리와 실행계획을 살펴보도록 하겠습니다.

SELECT dept_no, dept_name

FROM departments

WHERE dept_no NOT IN

(SELECT dept_no FROM dept_emp);

 

+---------+-----------------+

| dept_no | dept_name |

+---------+-----------------+

| d010 | Office Facility |

+---------+-----------------+

 

Explain)

*************************** 1. row ***************************

EXPLAIN: -> Nested loop antijoin (cost=43214.95 rows=413929)

-> Index scan on departments using dept_name (cost=1.25 rows=10)

-> Index lookup on dept_emp using idx_dept_no (dept_no=departments.dept_no) (cost=24670612.69 rows=41393)

위의 내용과 같이 antijoin 으로 수행된 것을 확인 할 수 있습니다.

이 쿼리는 내부적으로 안티조인 다음과 같이 재작성 됩니다.

select dept_no, dept_name

from departments

antijoin dept_emp

on dept_no

대부분의 경우, 안티조인 변환은 비교되는 표현식이 null일 때 적용할 수 없습니다. 예외는 (... NOT IN (SELECT ...)) IS NOT FALSE 및 그와 동등한 (... IN (SELECT ...)) IS NOT TRUE이 안티조인으로 변환될 수 있습니다.


MySQL 8.0.17 이상에서는, 서브쿼리는 NOT, IS [NOT] TRUE, 또는 IS [NOT] FALSE로 수정된 표현식의 인수로 사용될 수도 있습니다.
이와 같이 동작되기 위해서는 아래의 기준 조건이 요구됩니다.

• 서브쿼리는 UNION 구조를 포함하지 않아야 합니다.
• HAVING 절이 없어야 합니다.
• 집계 함수를 포함해서는 안 됩니다(명시적으로든 묵시적으로든 그룹화되었는지 여부에 상관없이)
• LIMIT 절이 없어야 합니다.
• 문장에서 STRAIGHT_JOIN 조인 유형을 사용해서는 안 됩니다.
• 수정된 쿼리에서 STRAIGHT_JOIN 존재해서는 안 됩니다.
• 외부 및 내부 테이블의 총 개수는 조인에서 허용되는 최대 테이블 개수보다 작아야 합니다.
• 서브쿼리는 상관 관계(Correlated)를 가질 수도 있고 가지지 않을 수도 있습니다.
• MySQL 8.0.16 이후에는 EXISTS의 인자로 사용되는 서브쿼리의 WHERE 절에 있는 단순 상관관계를 살펴보고,
  이를 IN (SELECT b FROM ...) 내에서 사용한 것과 같이 최적화할 수 있도록 합니다.
  trivially correlated라는 용어는 predicate 가 equality(동등) predicate, WHERE 절(또는 AND와 결합됨)의 유일한 predicate이며,하나의 피연산자는 하위 쿼리에서 참조되는 테이블에서, 다른 피연산자는 외부 쿼리 블록에서 온 것임을 의미합니다.
• DISTINCT 키워드는 허용되지만 무시됩니다. Semijoin 전략은 중복 제거를 자동으로 처리합니다.
• GROUP BY 절은 허용되지만 무시됩니다. 단, 서브쿼리에 하나 이상의 집계 함수가 포함되어 있는 경우에는 예외입니다.
• ORDER BY 절은 허용되지만 무시됩니다. Semijoin 전략의 평가에는 정렬이 관련이 없기 때문입니다.

만약 서브쿼리가 위에서 언급된 기준을 충족한다면, MySQL은 해당 서브쿼리를 세미조인으로 변환하고, cost-based로 다음과 같은 전략 중 하나를 선택합니다.

1. 조인으로 서브쿼리를 변환하거나, 테이블 풀아웃(table pullout)을 사용하여 서브쿼리 테이블과 외부 테이블 간의 내부 조인으로 실행합니다. 테이블 풀아웃은 서브쿼리에서 테이블을 외부 쿼리로 빼내는 작업입니다.

2. 중복 제거(Duplicate Weedout): 세미조인을 조인으로 실행하고, 임시 테이블을 사용하여 중복 레코드를 제거합니다.

3. 첫 번째 일치(FirstMatch): 내부 테이블을 행 조합을 스캔할 때 특정 값 그룹의 여러 인스턴스가 있는 경우, 모두 반환하는 대신 하나를 선택합니다. 이렇게 하면 "shortcuts(단축)" 스캔이 이루어지며 불필요한 행들이 생성되지 않습니다.

4. LooseScan: 인덱스를 사용하여 서브쿼리 테이블을 스캔하고, 각 서브쿼리의 값 그룹에서 하나의 값만 선택합니다.

5. 서브쿼리를 인덱스화된 임시 테이블로 변환하고, 중복을 제거하기 위해 인덱스를 사용하여 조인을 수행합니다.
인덱스는 임시 테이블과 외부 테이블 간의 조인 시 조회를 위해 나중에도 사용될 수 있습니다. 그렇지 않을 경우, 테이블이 스캔됩니다.

optimizer_switch 시스템 변수의 플래그를 사용하여 옵티마이저 플랜을 활성화 또는 비활성화할 수 있습니다.

• semijoin 플래그는 세미조인 사용 여부를 제어합니다. MySQL 8.0.17부터는 이것이 antijoins 에도 적용됩니다.
• semijoin이 활성화되어 있다면, firstmatch, loosescan, duplicateweedout, materialization 플래그를 통해 허용되는 세미조인 전략을 더 세밀하게 제어할 수 있습니다.

optimizer_switch 정보는 SELECT @@optimizer_switch\G 또는 show variables like 'optimizer_switch'\G 으로 조회할 수 있습니다.

show variables like 'optimizer_switch'\G

*************************** 1. row ***************************

Variable_name: optimizer_switch

Value: index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,

engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=on,block_nested_loop=on,

batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,duplicateweedout=on,

subquery_materialization_cost_based=on,use_index_extensions=on,condition_fanout_filter=on,derived_merge=on,

use_invisible_indexes=off,skip_scan=on,hash_join=on,subquery_to_derived=off,prefer_ordering_index=on,

hypergraph_optimizer=off,derived_condition_pushdown=on

위에서 SemiJoin 및 AntiJoin으로 수행된 쿼리에 대해서 위의 설명과 같이 optimizer_switch 에서 semijoin의 flag 값을 변경함에 따라서 실행 계획이 변경됨을 확인 할 수 있습니다.

SET SESSION optimizer_switch='semijoin=off';

• Semijoin 으로 수행되었던 쿼리에 대해서 off 로 지정 후 실행계획

explain format=tree

SELECT dept_no, dept_name

FROM departments

WHERE dept_no NOT IN

(SELECT dept_no FROM dept_emp)\G

 

EXPLAIN: -> Filter: exists(select #2) (cost=1.25 rows=10)

-> Index scan on departments using dept_name (cost=1.25 rows=10)

-> Select #2 (subquery in condition; dependent)

-> Limit: 1 row(s) (cost=4321.37 rows=1)

-> Index lookup on dept_emp using idx_dept_no (dept_no=departments.dept_no) (cost=4321.37 rows=41393)

• AntiJoin 으로 수행되었던 쿼리에 대해서 off 로 지정 후 실행계획

explain format=tree

SELECT dept_no, dept_name

FROM departments

WHERE dept_no NOT IN

(SELECT dept_no FROM dept_emp)\G

 

*************************** 1. row ***************************

EXPLAIN: -> Filter: <in_optimizer>(departments.dept_no,<exists>(select #2) is false) (cost=1.25 rows=10)

-> Index scan on departments using dept_name (cost=1.25 rows=10)

-> Select #2 (subquery in condition; dependent)

-> Limit: 1 row(s)

-> Index lookup on dept_emp using idx_dept_no (dept_no=<cache>(departments.dept_no))

이와 같이 semijoin의 플래그에 따라서 Semijoin 및 Antijoin 사용 여부를 제어할 수 있습니다.(기본값 on)


MySQL 8.0.21 이상에서는, [NOT] IN 또는 [NOT] EXISTS 서브쿼리 조건을 사용하는 단일 테이블 UPDATE 또는 DELETE 문에도 세미조인 변환을 적용할 수 있습니다.

단, 해당 문장은 ORDER BY나 LIMIT을 사용하지 않고, 옵티마이저 힌트나 optimizer_switch 설정에 의해 세미조인 변환을 허용해야 합니다.

explain format=tree

delete from departments

where dept_no NOT IN

(SELECT dept_no FROM dept_emp)\G

 

*************************** 1. row ***************************

EXPLAIN: -> Delete from departments (immediate)

-> Nested loop antijoin (cost=43214.95 rows=413929)

-> Table scan on departments (cost=1.25 rows=10)

-> Index lookup on dept_emp using idx_dept_no (dept_no=departments.dept_no) (cost=24670612.69 rows=41393)

이번 글은 MySQL 8.0 에서의 SemiJoin 과 AntiJoin에 대해서 간략하게 살펴보았고, 포스팅 글은 여기에서 마무리하도록 하겠습니다.
            

Reference

Reference URL
• mysql.com/8.0/semijoins