EXPLAIN의 access_type을 시간복잡도로 이해하기
서론
MariaDB나 MySQL에서 쿼리 튜닝을 위해 EXPLAIN을 실행하면 여러 칼럼이 나오는데, 그중 access_type(MySQL은 type)은 쿼리 성능을 결정짓는 매우 중요한 지표다.
그동안 "ALL이면 나쁘다" 정도로만 단편적으로 알고 있었고, 각 타입이 정확히 어느 정도의 비용을 소모하는지 피부에 잘 와닿지 않았다. 그래서 개발자에게 가장 익숙한 개념인 시간 복잡도를 빌려와 이 접근 방식들을 이해해보면 어떨까 싶어 내용을 정리해본다.
MySQL/MariaDB를 기반으로 했고 RealMySQL, 웹 서칭, AI 등을 통해 얻은 정보를 나름의 관점으로 Access Type을 시간복잡도 분류해 틀린 내용이 있을 수 있다. 각 설명은 레퍼런스를 참고하여 괜찮지만 시간복잡도 분류는 공식적인 레퍼런스가 따로 있는 것은 아닌 만큼, 읽는 분들은 비판적인 시각으로 참고해주시길 부탁드린다.
access_type 별 시간복잡도
가장 성능이 좋은것 부터 낮은것 순으로 기술했다.
시간복잡도: O(1)
system
레코드가 1건만 존재하는 테이블 또는 한 건도 없는 테이블 참조하는 형태의 접근 방법이다.
InnoDB 스토리지 엔진을 사용하는 테이블에선 나타나지 않고, MyISAM or MEMORY 테이블 에서만 사용되고 있다.
const
테이블 레코드 건수 관계없이, 쿼리가 PK or UNIQUE KEY 이용하는 WHERE 조건절을 가진 경우 나타나는 접근 방법이다.
Primary Key나 UNIQUE Key를 이용하고 있으니 필연적으로 1건을 반환 할 수 밖에 없다.
특이한 속성이 있는데 const의 경우, 처음 데이터를 찾으러 갈 때는 B-Tree 를 타야 하니 O(log N) 이지만, 이후 옵티마이저가 해당 쿼리와 값을 상수화 하기 때문에 O(1) 으로 최적화가 발생한다.
시간복잡도: O(log n)
eq_ref
조인에서 첫 번째 읽은 테이블의 칼럼값을 이용해 두 번째 테이블을 PK or UNIQUE KEY 로 동등 조건 검색하는 경우 나타나는 접근 방법이다.
eq_ref는 PK or UNIQUE KEY 이용한 동등 조건 검색이기 때문에 두 번째 테이블은 반드시 1건의 레코드 반환할 수 밖에 없다.
만약 PK or UNIQUE KEY가 다중 칼럼 형태라면 모든 칼럼이 비교 조건에 있어야 이 eq_ref 접근 방법이 쓰일 수 있다.
시간복잡도: O(log n + k)
ref
이 접근 방법은 크게 2가지 경우에서 발생한다.
- 인덱스의 칼럼 조합 중 일부만 동등 조건으로 사용될 때
- 비고유 인덱스(Non-Unique Index)를 사용하여 동등 조건으로 검색할 때
조건에 일치하는 레코드가 1건이 보장 안되기에 상수(k)가 붙는다.
k는 인덱스 탐색 후, 해당 위치에서 범위 탐색을 한다는 의미다.
만약 k가 전체 데이터 대비 작다면 결국 O(log n)으로 수렴될 것이다.
eq_ref와 달리 조인 순서와 관계없이 사용되고 PK or UNIQUE Key 제약도 따로 없다. 인덱스 종류에 관계없이 동등 조건으로 검색이 ref가 쓰인다.
조인의 순서와 인덱스 종류 관계없이 동등 조건으로 검색(1건의 레코드만 반환된다는 보장 없어도 됨)
ref_or_null
ref 와 접근 방법 같은데 NULL 비교가 추가된 형태(ref 방식 또는 NULL 비교 접근 방법)
range
말 그대로 '범위'로 접근 하여 검색하는 방법이다. <, >, IS NULL, BETWEEN, IN, LIKE 등 연산 시 사용된다.
이 방식도 처음에는 B-Tree 탐색에 O(log n) 만큼의 시간을 쓰고, 이후 범위 탐색에 인접 노드를 탐색해야하기에 상수(k)가 더해진다.
시간복잡도: O(n)
index
개인적으로 오해하고 있던 접근 방식. index라 표기되어 인덱스를 잘 타는 쿼리구나 하고생각했었는데 그게 아니었다.
이 index 접근 방식은 인덱스를 처음부터 끝까지 읽는 인덱스 풀 스캔을 의미한다.
이 방법은 풀 테이블 스캔과 비교해보면 결국 다루는 레코드 건수는 같다. 하지만 인덱스는 데이터 파일 전체보다 크기가 적으므로 인덱스 풀 스캔시 풀 테이블 스캔보다는 빠르다. 또한 쿼리 내용에 따라 정렬이라는 인덱스의 장점을 사용할 수 있다.
index 접근 방법은 다음 조건에서 1+2 또는 1+3 조건이 충족될 때 사용된다.
range,cosnt,ref같은 접근 방법으로 인덱스 못 쓸 때- 인덱스에 포함된 칼럼만으로 처리할 수 있는 쿼리일 때(즉, 데이터 파일 읽지 않아도 되는 경우)
- 인덱스를 이용해 정렬이나 그루핑 작업이 가능할 때(즉, 별도의 정렬 작업 피할 수 있는 경우)
ALL
풀 테이블 스캔을 의미한다. 테이블의 레코드를 모두 읽고 불필요한 레코드를 제거하고 반환시킨다. 가장 비효율적인 접근 방법.
참고로, InnoDB 스토리지 엔진에서는 풀 테이블 스캔, 인덱스 풀 스캔 같은 대량의 Disk I/O를 발생시키는 작업을 위해 한꺼번에 많은 페이지를 읽는 기능을 제공한다. 이를 Read Ahead라 한다.
DataWarehouse, Batch 프로그램 같이 대용량 레코드를 처리하는 작업에서는 이 ALL 방식이 적합하기도 하다.
쿼리 튜닝이 꼭 ALL이나 index를 못 쓰게 하는건 아니라는것 인지하자.
기타
unique_subquery
WHERE 절에서 사용될 수 있는 IN(subquery) 형태의 쿼리 위한 접근 방법.
unique_subquery 의미 그대로 서브쿼리에서 중복되지 않는 유니크한 값만 반환할 때 이 접근 방법 사용한다.
subquery 가 중복된 값을 만들지 않는다는 보장이 있는 경우에 사용 가능한 접근 방법.
index_subquery
IN 연산자 특성상 IN(subquery) or IN(상수 나열) 형태 조건은 괄호 안에 있는 값의 목록에서 중복된 값이 먼저 제거되야한다.
앞서 정리한 unique subquery 는 IN(subquery) 조건의 서브쿼리가 중복된 값 만들어내지 않는다는 보장이 있으므로 별도의 중복 제거 필요 없었다.
하지만 쿼리에 따라 IN(subquery) 에서 subquery가 중복된 값을 반환할 수 도 있다.
이때 subquery 결과의 중복된 값을 인덱스를 이용해서 제거할 수 있을때, index subquery 접근 방법이 이용된다.
unique_subquery,index_subquery비교 정리
unique_subquery- IN(subquery) 형태의 조건에서 서브쿼리의 반환 값에는 중복이 없으므로 별도의 중복 제거 작업 불필요
index_subquery- IN(subquery) 형태의 조건에서 서브쿼리의 반환 값에 중복된 값이 있을 수 있지만 인덱스를 이용해 중복된 값 제거 가능
index_merge
이건 이때까지 방법과 달리 2개 이상의 인덱스를 이용해 각각의 검색 결과 만든 후, 그 결과를 병합 해 처리하는 방식
다음과 같은 특징이 있다.
- 여러 인덱스 읽어야 하므로 일반적으로
range보다 효율성 떨어짐 - 전문 검색 인덱스 사용하는 쿼리에선
index_merge적용 안됨 index_merge방법으로 처리된 결과는 항상 2개 이상의 집합이 되기 때문에 그 두 집합의 교집합이나 합집합 또는 중복 제거와 같은 부가적인 작업이 더 필요