[MySQL]MySQL 벼락치기(2) - 인덱스(1)

이번 포스팅은 사내에서 MySQL 관련 내용 발표를 위해 Real MySQL(http://wikibook.co.kr/real-mysql/) 서적을 기반으로 학습하고 이해한 내용을 정리하는 포스팅이다. 포스팅에서는 주로 InnoDB 스토리지 엔진을 기준으로 설명할 예정이다. 

MySQL 역시 내용이 많기 때문에 시리즈로 나눠서 정리할 예정이다. 

인덱스

인덱스는 데이터의 저장(INSERT, UPDATE, DELETE) 의 성능을 희생하고 그 대신에 데이터의 읽기 속도를 높이는 기능이다. 

인덱스를 알고리즘 별로 구분하면 아래와 같다. 

1. B-Tree 알고리즘
1. 가장 일반적으로 사용되는 알고리즘으로 컬럼을 변형하지 않고, 원래의 값을 이용해 인덱싱하는 알고리즘이다. 
2. Hash 알고리즘
1. 컬럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다. 다만 값을 변형해서 인덱싱하므로 전방일치와 같이 값의 일부만 검색하고자 할때는 해시 인덱스를 사용할 수 없다.

그외에도 Fractal-Tree알고리즘(Fractal-Tree 인덱스)이 있지만 이 포스팅에서는 다루지 않겠다. (책에는 자세하게 나와있다.)

인덱스의 종류

위에서 설명한 알고리즘으로 구분한 인덱스들과 그외에 유니크여부 및 기능별로 구분한 인덱스들에서 알아보자. 

설명해야하는 내용이 많기때문에 이번포스팅에서는 B-Tree 인덱스에 대해서만 소개할 예정이다.

B-Tree 인덱스

B-Tree 인덱스는 가장 범용적인 목적으로 사용되는 인덱스로 B-Tree 의 B는 Balanced 를 의미한다고 한다. B-Tree 인덱스를 사용하려면 B-Tree 의 기본 구조를 알고 있어야 하는데 B-Tree 는 최상위에 하나의 루트노드가 존재하고 그 하위에 자식 노드가 붙어있는 형태이다. 트리 구조의 가장 하위에는 리프 노드라고 하고 트리구조에서 루트노드도 아니고 리프노드도 아닌 중간의 노드를 브랜치 노드라고 한다. 

인덱스는 테이블의 키 컬럼만 가지고 있으므로 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 한다. B-Tree 인덱스의 리프노드는 항상 실제 데이터의 레코드를 찾아가기 위한 주소값을 가지고 있고 InnoDB 스토리지 엔진을 사용하는 테이블에서는 PK에 의해 클러스터링 되기 때문에 PK값 자체가 레코드를 찾아가기 위한 주소 역할을 한다.

B-Tree 인덱스의 추가, 삭제 

테이블의 레코드를 저장하거나 변경하는 경우, 인덱스 키 추가나 삭제 작업이 발생한다. 

인덱스 키 추가

테이블의 레코드를 추가하는 작업비용을 1이라고 가정하면 테이블의 인덱스를 추가하는 작업비용은 1~1.5 정도로 예측하는게 일반적이다. 테이블에 인덱스가 하나도 없는 경우작업비용이 1일때 테이블에 인덱스가 3개 있다면 5.5 정도의 비용(1.5 * 3 + 1) 으로 예측해 볼 수 있다. 이 비용의 대부분은 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 하기때문에 시간이 오래 걸린다.

인덱스 키 삭제

인덱스 키값을 삭제할때는 해당 키 값이 저장된 리프노드를 찾아서 삭제 마크만 하면 작업이 완료된다. 이렇게 삭제마킹된 인덱스 키 공간은 버퍼링 되어 지연된 처리를 하면서 사용자에게 별다른 악영향 없이 삭제 처리를 한다. 

인덱스 키 검색

인덱스 검색은 SELECT 에서만 사용하는게 아니라 UPDATE나 DELETE를 처리하기 위해 해당 레코드를 먼저 검색해야 할 경우에도 인덱스가 있으면 빠른 검색이 가능하다. B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있다. NotEqual(<>) 비교(https://dev.mysql.com/doc/refman/8.0/en/comparison-operators.html#operator_not-equal)나 값의 뒷부분이 일치하는 경우에는 B-Tree 인덱스를 이용한 검색이 불가능 하다. 

B-Tree 인덱스 사용에 영향을 미치는 요소

인덱스 키값의 크기

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본단위를 페이지 또는 블록이라고 하며 디스크의 모든 읽기 및 쓰기 작업의 최소작업 단위가 페이지 및 블록이된다. 인덱스도 결국은 페이지 단위로 관리되며 B-Tree 인덱스에서 루트와 브랜치 그리고 리프 노드를 구분한 기준은 페이지 단위이다. 

InnoDB 의 모든 페이지 크기는 16KB로 고정돼 있다. 만약 인덱스의 키가 16바이트(10바이트 컬럼 + 6바이트 컬럼)고 자식노드 주소를 12바이트라고 가정하면 아래 그림과 같이 인덱스 페이지가 구성될 것이다. 

하나의 인덱스 페이지(16KB)에 몇 개의 키를 저장할 수 있을까? 계산해보면 16*1024/(16+12) = 585개 저장할 수 있다. 이 경우에는 585개의 자식노드를 가질 수 있는 B-Tree 가 된다. 그런데 만약 인덱스 키 값이 16바이트에서 32바이트로 늘어났다고 가정하면 한 페이지에 인덱스 키를 16*1024/(32+12) = 372개 를 저장 할 수 있다. 만약 SELECT 쿼리가 레코드 500개를 읽어야 한다면 전자는 인덱스 페이지 한번으로 해결 될 수도 있지만 후자는 최소한 2번 이상 디스크로부터 읽어야 한다. 결국 인덱스를 구성하는 키값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고 느려진다는것을 의미한다.
그리고 B-Tree 인덱스는 실제 컬럼의 값이 1MB 라도 전체 값을 인덱스 키로 사용하는것이 아니라 767 바이트까지만 잘라서 인덱스 키로 사용한다고 한다! 주의하자!

B-Tree 깊이

B-Tree 의 깊이는 직접적으로 제어할 방법이 없다. 인덱스 키값의 평균 크기가 늘어나면 어떤 현상이 추가로 발생하는지 알아보자.
키값이 16바이트이고 B-Tree 의 깊이가 3인경우 최대 2억(585 * 585 * 585) 개정도의 키값을 담을수 있지만 키 값이 32바이트로 늘어나면 5천만(372 * 372 * 372)개로 줄어든다.
 이렇듯 인덱스 키값의 크기가 커지면 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키값의 개수가 작아지고, 그 때문에 같은 레코드건수라 하더라도 B-Tree 의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다는 것을 의미한다.

선택도(기수성)

인덱스에서 선택도 또는 기수성은 거의 같은 의미로 사용되며 모든 인덱스 키값 가운데 유니크한 값의 수를 의미한다. 전체 인덱스 키값은 100개 인데 그중에서 유니크한 값의 수는 10개라면 기수성은 10이다. 키값 가운데 중복된 값이 많아지면 기수성은 낮아지고 동시에 선택도 또한 떨어진다. 인덱스는 기수성이 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

아래의 예제를 보자.

country 컬럼의 유니크한 값의 개수가 10개
country 컬럼의 유니크한 값의 개수가 1000개
다음 테이블에 데이터가 1만건 있다고 생각해보자.

mysql> SELECT * FROM  tb_test WHERE country='KOREA' AND city='SEOUL';

만약 위의 쿼리가 실행되면 A케이스는 평균 1000건 B케이스는 평균 10건의 데이터가 조회될것이다. 이 상황에서 단 한건만 위의 쿼리의 결과와 일치한다면 A케이스는 불필요한 999건의 데이터를 읽었지만 B케이스의 경우 9건의 불필요한 데이터만 읽게된다.
그렇기 때문에 A케이스의 인덱스는 B케이스의 인덱스보다 비효율적이다.  

읽어야하는 레코드의 건수

인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는것보다 높은 비용이 드는 작업이다. 
 테이블에 레코드가 100만건 있는데 그중에 50만건을 읽어야 하는 쿼리가 있다고 했을때 전체 테이블을 모두 읽어서 필요없는 50만건을 버리는것과 인덱스를 통해 필요한 50만건 읽어오는 것이 효율적인지 판단해야 한다.
 일반적인 DBMS 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는것이 테이블에서 직접 레코드 1건을 읽는것보다 4~5배 정도 더 비용이 많이 드는 작업인 것으로 예측한다. 즉 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를이용하지 않고 직접 테이블을 모두 읽어서 필요한 레코드만 가려내는 방식으로 처리하는것이 효율적이다. 

B-Tree 인덱스를 통한 데이터 읽기

MySQL 이 인덱스를 이용하는 대표적인 방법 3가지를 살펴보자.

인덱스 레인지 스캔

인덱스 레인지 스캔은 검색해야할 인덱스의 범위가 결정됐을때 사용하는 방식이다. 인덱스의 범위를 결정하려면 시작지점을 알아야하는데 시작지점을 알려면 루트노드에서부터 비교를 시작해 브랜치 노드를 거치고 리프노드까지 찾아 들어가야지만 알 수 있다. 시작지점을 찾으면 리프노드의 레코드만 순서대로 쭉 읽는다.(스캔이라고 표현한다)
만약 스캔하다가 리프노드의 끝까지 읽으면 리프노드간의 링크를 이용해 다음 리프노드를 찾아서 다시 스캔한다. 그리고 최종적으로 스캔을 멈춰야할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다. 

이때 중요한것은 리프 노드에 저장된 레코드 주소로 데이터파일의 레코드를 읽어오는데 레코드 한건 한건 단위로 랜덤I/O가 한번씩 실행된다. 만약 3건의 레코드가 검색조건에 일치했다고 가정하면 데이터 레코드를 읽기위해 랜덤 I/O가 최대 3번이 필요한 것이다. 그래서 인덱스를 통해 데이터 레코드를 읽는 작업이 비용이 많이드는 작업으로 분류된다. 

인덱스 풀 스캔

인덱스 풀 스캔은 인덱스의 처음부터 끝까지 모두 읽는 방식을 의미한다. 대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫번째 컬럼이 아닌 경우 인덱스 풀 스캔 방식을 사용한다. 예를 들어 인덱스는 (A,B,C) 컬럼의 순서대로 만들어져 있지만 쿼리의 조건절은 B컬럼이나 C컬럼으로 검색하는 경우이다.  또한 쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리 할 수 있는 경우에도 이 방식이 사용된다. 인덱스뿐만 아니라 데이터 레코드까지 읽어야한다면 절대 이방식으로 처리되지 않는다.

이 방식은 인덱스 레인지 스캔보다는 빠르지 않지만 테이블 풀 스캔보다는 효율적이다.  인덱스에 포함된 컬럼만으로 쿼리를 처리할 수 있는 경우 테이블의 레코드를 읽을 필요가 없기 때문이다.  

루스 인덱스 스캔

루스 인덱스 스캔이란 말 그대로 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미한다. 루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하게 작동하지만 중간마다 필요치 않은 인덱스 키값은 무시하고 다음으로 넘어가는 형태로 처리한다 일반적으로 GROUP BY 또는 집합 함수 가운데 MAX 또는 MIN 함수에 대해 최적화를 하는 경우에 사용된다. 

SELECT dept_no, MIN(emp_no)
FROM dept_emp
WHERE dep_no BETWEEN 'd002' AND 'd004'
GROUP BY dept_no;

위 쿼리에서 사용된 dept_emp 테이블은 dept_no 와 emp_no 두개의 컬럼으로 인덱스가 생성돼있다. 또한 인덱스는 dept_no + emp_no 값으로 정렬돼 있어서 dept_no 그룹별로 제일 첫번째 레코드의 emp_no 값만 읽으면 된다. 즉 인덱스에서 WHERER 조건을 만족하는 범위 전체를 다 스캔할 필요가 없다는 것을 옵티마이저는 알고 있기 때문에 조건에 만족하지 않는 레코드는 무시하고 다음 레코드로 이동한다. 

다중 컬럼 인덱스

두개이상의 컬럼으로 구성된 인덱스를 다중 컬럼 인덱스라고 한다. 

다중 컬럼 인덱스에서 중요한것은 인덱스의 두번째 컬럼은 첫번째 컬럼에 의존해서 정렬돼 있다는 것이다. 즉, 두번째 컬럼의 정렬은 첫번째 컬럼이 똑같은 레코드에서만 의미가 있다. 이렇기 때문에 다중 컬럼 인덱스에서는 인덱스 내에서 각 컬럼의 위치(순서)가 상당히 중요하며 또한 아주 신중히 결정해야 하는 이유가 바로 여기에 있다. 

B-Tree 인덱스의 정렬 및 스캔 방향

인덱스 정렬

인덱스 키값은 항상 오름차순으로만 정렬되어 있기 때문에 인덱스를 구성하는 컬럼 가운데 오른차순과 내림차순을 혼합해서 만들어야 할때는 컬럼의 값을 역으로 변환해서 구현하는것이 유일한 방법이다. 

인덱스 스캔 방향

다음과 같은 쿼리가 있을때 인덱스의 스캔방향은 어떻게 될까?

SELECT * FROM employees ORDER BY first_name DESC LIMIT 1;

MySQL은 이 쿼리를 실행하기 위해 인덱스를 처음부터 오름차순으로 끝까지 읽어 first_name이 가장 큰 (오름차순으로 읽었을때 가장 마지막 레코드) 값 하나를 가져오는 걸까? 그렇지는 않다. 인덱스를 역순으로 정렬되게 할 수는 없지만 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬 효과를 얻을수는 있다. ORDER BY 처리나 MIN또는 MAX 함수 등의 최적화가 필요한 경우인덱스의 읽기방향을 전환해서 사용하도록 실행계획을 만들어 낸다. 

SELECT * FROM employees WHERE first_name >= 'Anneke' ORDER BY first_name ASC LIMIT 4
SELECT * FROM employees ORDER BY first_name DESC LIMIT 5

B-Tree 인덱스의 가용성과 효율성

쿼리의 WHERE 조건이나 GROUP BY  또는 ORDER BY 절이 어떤 경우에 어떤 방식으로 사용할 수 있는지 확인해보자. 

비교조건의 종류와 효율성

다중 컬럼 인덱스에서 컬럼의 순서와 컬럼에 사용된 조건이 동등비교(=) 인지 크다(>) 인지 작다(<) 인지에 따라 각 인덱스의 컬럼 활용 형태가 달라지며 효율또한 달라진다. 

SELECT * FROM dept_emp WHERE dept_no = 'd002' AND emp_no >= 10114

dept_emp 테입르에 컬럼의 순서만 다른 2가지 케이스로 인덱스를 생성했다고 가정하자. 

케이스 A : dept_no+ emp_no

케이스 B : emp_no + dept_no

케이스 A는 dept_no = d002 AND emp_no >= 10144 인 레코드를 차족 그 이후에는 dept_no가 d002가 아닐때까지 인덱스를 그냥 쭉 읽기만 하면 된다. 하지만 케이스 B는 우선 emp_no> 10144 AND dept_no=d002인 레코드를 찾고 그 이후에 모든 레코드에 대해 dept_no=d002 인지 비교하는 과정을 거쳐야 한다. 

A케이스의 두 조건과 같이 작업의 범위를 결정하는 조건을 "작업 범위 결정 조건" 이라고 하고 케이스 B 의 dept_no=d002 조건과 같이 비교 작업의 범위를 줄이지 못하고 단순히 거름종이 역할만 하는 조건을 필터링 조건 혹은 체크조건 이라고 한다. 작업범위를 결정하는 조건은 많을수록 쿼리의 처리 성능을 높이지만 체크 조건은 많다고 해서 쿼리의 처리 성능을 높이지는 못한다. 

인덱스의 가용성

B-Tree 인덱스의 특징은 왼쪽값에 기준해서 오른쪽값이 정렬돼 있다는 것이다 여기서 왼쪽이라 함은 하나의 컬럼내에서뿐만 아니라 다중컬럼 인덱스의 컬럼에 대해서도 함께 적용된다. 

케이스 A 인덱스 : first_name

SELECT * FROM employees WHERE first_name LIKE '%mer';

그리고 다음과 같은 쿼리가 있을때 이 쿼리는 인덱스 레인지 스캔 방식으로 인덱스를 이용할 수 없다. 

그 이유는 first_name 컬럼에 지정된 값의 왼쪽부터 한글자씩 비교해가면서 일치하는 레코드를 찾아야 하는데 조건절에는 왼쪽 부분이 고정되어 있지 않기 때문이다. 

케이스 B에서는 다음과 같은 쿼리가 어떻게 실행될까?

케이스 B 인덱스 : dept_no + emp_no

SELECT * FROM dept_emp WHERE emp_no >= 10114;

인덱스가 컬럼 순서대로 생성돼 있다면 인덱스의 선행 컬럼인 deptp_no가 없이 emp_no값으로만 검색하면 인덱스를 효율적으로 사용할 수 없다. 

가용성과 효율성 판단

효율적인 인덱스 활용을 위해서 인덱스의 작업범위 결정조건으로 사용할 수 없는 아래의 조건들에 대해서 알아보자.
아래의 조건들은 작업범위 결정조건으로 사용되지 못할뿐 경우에 따라서 체크조건으로는 사용될 수도 있다. 

1. NOT-EQUAL로 비교되는 경우(<>, NOT IN, NOT BETWEEN, IS NOT NULL) 
2. LIKE '%??'(뒷부분 일치) 형태로 문자열 패턴이 비교된 경우
3. 스토어드 함수나 다른연산자로 인덱스 컬럼이 변형된 후 비교된 경우
   WHERE SUBSTRING(column,1,1) = 'X'
   WHERE DAYOFMONTH(column) = 1
4. 데이터 타입이 서로 다른 비교(인덱스 컬럼의 타입을 변환해야 비교가 가능한 경우
   WHERE char_column = 10

다중 컬럼 인덱스에서 작업범위 결정조건으로 사용하는 경우와 그렇지 못한경우에 대해서도 알아보자.

인덱스가 다음과 같을때 : INDEX ix_test(column_1, column_2, column_3, ... , column_N)

작업범위 결정조건으로 인덱스를 사용하지 못하는 경우 

1. column_1 컬럼에 대한 조건이 없는 경우
2. column_1 컬럼의 비교조건이 위의 인덱스 사용 불가 조건(1~4)중 하나인경우 

작업범위 결정조건으로 인덱스를 사용하는 경우

1. column_1 ~ column_(i-1) 컬럼까지 Equal 형태(= 혹은 IN)로 비교 하면서 column_i 컬럼에 대해서 다음 연산자중 하나로 비교
1. Equal(= , IN)
2. 크다 작다 형태(>, <)
3. LIKE 로 좌측이리 패턴

예제로 다시한번 확인하자.

WHERE column_1 <> 2 
-- 인덱스를 사용할 수 없음

WHERE column_1 = 1 AND column_2 > 10 
-- column_1 과 column_2 까지 범위 결정조건으로 사용됨

WHERE column_1 IN (1,2) AND column_2 = 2 AND column_3 <= 10 
-- column_1 과 column_2, column_3 까지 범위 결정조건으로 사용됨

WHERE column_1 = 1 AND column_2 = 2 AND column_3 IN (10,20,30) AND column_4 <> 100 
-- column_1, column_2 column_3 까지 범위 결정조건이고 column_4 는 체크조건으로 사용됨

WHERE column_1 = 1 AND column_2 IN(2,4) AND column_3 = 30 AND column_4 LIKE '홍길%' 
-- column_1 과 column_2, column_3,column_4 까지 범위 결정조건으로 사용됨

WHERE column_1 = 1 AND column_2 = 2 AND column_3 = 30 AND column_4 = '홍길동' AND column_5 = '서울' 
 -- column_1 과 column_2, column_3, column_4, column_5 까지 범위 결정조건으로 사용됨

오늘은 여기까지~

누군가에게 도움이 되었길 바라면서 오늘의 포스팅 끝~