[Real MySQL] 인덱스

👊🏻 랜덤 I/O 와 순차 I/O

인덱스의 성능에 대해서 제대로 이해하기 위해서는 랜덤 I/O 와 순차 I/O에 대해서 알아볼 필요가 있다.

랜덤 I/O 라는 표현은 디스크 드라이브의 플래터를 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것을 의미한다. 사실 순차 I/O 또한 이 작업은 같다.

디스크에 데이터를 쓰고 읽는데 걸리는 시간과 비용은 결국 디스크 헤더를 움직여서 읽고 쓸 위치로 옮기는 단계에서 결정난다.

 

책에서 나온 예제에는 3개의 페이지 블록을 디스크에 기록하기 위해 순차 I/O는 1번의 시스템 콜을 요청했지만 랜덤 I/O는 3번의 시스템 콜을 요청했다.

해당 예제의 경우 순차 I/O가 랜덤 I/O보다 3배 정도 빠르다고 볼 수 있다.

 

쿼리를 튜닝해서 랜덤 I/O 작업을 순차 I/O 작업으로 실행할 방법은 많지 않다.

때문에 쿼리를 튜닝한다는 것은 랜덤 I/O 자체를 줄이는 것이 목표이며 이는 쿼리를 처리하는데 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것을 의미한다.

 

---

 

🍏 인덱스란 ?

많은 예제에서 나오듯이 인덱스는 책의 제일 끝에 있는 찾아보기로 설명하곤 한다.

DBMS 에서도 DB 테이블의 모든 레코드를 검색해서 원하는 결과를 가져오려면 오랜 시간이 걸린다.

때문에 칼럼 (칼럼들) 의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 만들어 별도의 공간에 저장해두는걸 인덱스라고 한다.

 

책의 찾아보기와 인덱스와의 중요한 공통점은 바로 정렬이다.

최대한 원하는 데이터 값에 빠르게 찾아가기 위해 인덱스는 미리 정렬해서 보관해야한다.

인덱스의 기본 개념과 구현 자료구조에 관해서는 이전에 포스팅을 하였기 때문에 먼저 읽고 오기 바란다.

https://daisyit.tistory.com/42

 

인덱스의 구분

인덱스는 여러 가지로 나눠볼 수 있다.

 

인덱스를 역할별로 구분한다면 프라이머리 키와 보조 키로 구분해 볼 수 있다. (여기서 키란 인덱스를 의미한다)

여기서 프라이머리 키란 그 레코드를 대표하는 칼럼의 값으로 만들어진 인덱스를 의미한다. NULL 값과 중복을 허용하지 않는다.

프라이머리 키를 제외한 모든 인덱스는 보조 키로 분류한다. 대체 키라고도 한다.

 

인덱스를 알고리즘으로 분류한다면 상당히 많은 분류가 있겠지만 보통 B-Tree 인덱스와 Hash 인덱스로 구분할 수 있다.

글이 써진 시점에서 최근에 Fractal-Tree 도 추가되었다고 한다.

알고리즘에 대한 분류는 뒤에 자세히 설명해보려 한다.

 

인덱스를 데이터 중복 허용 여부로 분류한다면 유니크 인덱스와 논(non)유니크 인덱스로 구분할 수 있다.

이는 단순하게 같은 값이 1개만 존재하는지 그 이상 존재할 수 있는지를 의미하지만 실제 DBMS 쿼리를 실행하는 옵티마이저에게는 상당히 중요한 문제가 된다.

유니크 인덱스에 대해 equal 로 검색한다는 것은 1건의 레코드를 찾으면 그 이후의 인덱스 작업은 필요없다는 것을 옵티마이저에게 알려주는 효과를 내기 때문이다.

 

---

 

🍎 B-Tree 인덱스

DB 의 인덱싱 알고리즘 가운데 가장 일반적이고 먼저 도입된 알고리즘이다.

현재에는 B+-Tree 를 주로 사용하지만 이 또한 B-Tree 에서 변형된 알고리즘이다.

추가로 여기서 B 는 Binary(이진)의 뜻이 아닌 Balanced 를 의미한다고 한다. 나도 처음 알았다.

 

B-Tree 는 칼럼의 원래 값을 변형시키지 않고 (앞부분만 잘라서 관리하긴 하지만) 항상 정렬된 상태로 유지하고 있다.

B-Tree 인덱스에 관해 설명하기 위해서는, B-Tree 의 기본적인 구조는 알고 있어야한다.

해당 포스팅은 인덱스에 관한 내용이기 때문에 해당 자료구조의 대한 설명은 링크로 첨부하고 생략한다.

https://code-lab1.tistory.com/217

[자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정

 

B-Tree 인덱스 키 추가 삭제

- B-Tree 인덱스 추가

새로운 데이터가 추가되어 키 값이 B-Tree 에 저장될 때 스토리지 엔진에 따라 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다.

저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다.

이때 리프 노드가 꽉 차서 더는 저장할 수 없을 때에 리프 노드가 분리되야 하는데, 이는 상위 브랜츠 노드까지 처리의 범위가 넓어진다.

이러한 작업 탓에 B-Tree 는 상대적으로 쓰기 작업이 비용이 많이 든다.

일반적으로 테이블에 INSERT 작업 비용을 1이라고 하면 인덱스에 키를 추가하는 작업 비용을 1~1.5 정도로 예측한다.

중요한 것은 이 비용의 대부분이 메모리와 CPU에서 처리하는 것이 아닌, 디스크로부터 인덱스 페이지를 읽고 쓰는데 드는 비용이다.

 

InnoDB 스토리지 엔진에서는 Insert 쿼리가 실행되면 즉시 새로운 키값을 B-Tree 인덱스에 반영하는 것이 아닌 지연처리가 가능하다.

 

[innoDB 에서의 인서트 버퍼 처리]

1. 사용자의 insert 쿼리 실행

2. InnoDB의 버퍼 풀에 새로운 키 값을 추가해야 할 페이지가 존재한다면 즉시 키 추가 작업 처리

3. 버퍼 풀에 B-Tree의 리프 노드가 없다면, 인서트 버퍼에 추가할 키값과 레코드의 주소를 임시로 기록해두고 작업완료 처리(사용자의 쿼리 실행 완료 반환)

4. 백그라운드 작업으로 인덱스 페이지를 읽을 때마다 인서트 버퍼에 머지해야할 인덱스 키값이 있는지 확인 후, 있다면 병합

5. DB 의 자원 여유가 없다면, MySQL 서버의 인서트 버퍼 머지 스레드가 조금씩 인서트 버퍼에 임시 저장된 인덱스 키와 주소 값을 병합

 

MySQL 5.5 버전 이상부터는 "innodb_change_buffering" 설정 파라미터가 도입됐다.

설정 값을 이용해 키 추가 작업과 키 삭제 작업 중 어느 것을 지연 처리할지 설정해야한다.

자세한 방법은 또 따로 실습해보고 포스팅 해보겠다.

 

- B-Tree 인덱스 삭제

키 값이 삭제되는 경우는 간단하다.

해당 키 값이 저장된 B-Tree 의 리프 노드를 찾아 삭제 마크만 하면 작업이 완료된다.

삭제 마킹된 인덱스 키 공간은 계속 방치하거나 재활용 할 수 있으며 이 또한 지연처리가 가능하다.

 

- B-Tree 인덱스 변경

정렬이 필수적이기 때문에 단순히 키 값만 변경하는 것은 불가능하다.

먼저 B-Tree 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다.

 

- B-Tree 인덱스 검색

빠른 검색을 위해 루트 노드로부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행한다.

이 과정을 트리 탐색 이라 부른다. 중요한 사실은 인덱스의 키 값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree 의 빠른 검색 기능을 사용할 수 없다. 때문에 연산을 수행한 결과로 정렬하거나 검색하는 것은 B-Tree 의 장점을 이용할 수 없다.

 

특히 InnoDB 에서는 레코드 잠금 혹은 넥스트 키 락이 검색을 수행한 인덱스를 잠근 후 테이블 레코드를 잠그는 방식으로 구현되어 있다.

때문에 UPDATE or DELETE 문장이 실행될 때 인덱스가 없으면 불필요하게 더 많은 레코드를 잠군다.

최악은 테이블의 모든 레코드를 잠글 수 있다.

그만큼 InnoDB 에서는 인덱스가 중요하다.

 

 

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

- 인덱스 키 값의 크기

InnoDB 스토리지 엔진은 디스크에 저장하는 데이터의 가장 기본 단위를 페이지(Page) 혹은 블록(Block) 이라고 한다.

이는 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위이며, 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이다.

인덱스도 페이지 단위로 관리되며, 루트 브랜치 리프 노드를 구분하는 기준 역시 페이지 단위이다.

 

InnoDB의 모든 페이지 크기는 16KB로 고정되어 있다. 이를 변경하기 위해서는 소스 컴파일이 필요하다고 한다.

B-Tree 의 자식 노드들의 개수는 가변적이고 이는 인덱스 키 값의 크기에 영향을 미친다.

고정적인 페이지 크기 안에서 인덱스의 키 값들이 커지게 된다면 저장할 수 있는 인덱스 키의 개수들이 줄어들게 된다.

인덱스 키의 크기가 작아 하나의 페이지에 600개의 인덱스 키를 저장할 수 있는 반면, 인덱스 키의 크기가 커져 하나의 페이지의 400개의 인덱스 키를 저장할 수 있다고 가정해보자.

어느 SELECT 쿼리가 500개의 레코드를 읽어야 한다면 전자는 인덱스 페이지 한 번으로 해결될 수 있지만, 후자는 최소 2번 이상 디스크에서 읽어야한다. 이는 성능에 직접적인 영향을 미친다.

 

또한 인덱스 키 값의 크기가 길어진다는 것은 인덱스 전체의 크기가 커지는 것을 의미하고 이는 메모리 효율에도 영향을 미친다.

 

- B-Tree 깊이

B-Tree 의 깊이가 길어지는 것 또한 상당히 중요하지만 직접적으로 제어할 방법은 없다.

B-Tree 의 깊이는 MySQL 에서 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다.

인덱스 키값의 크기를 작게 만들면 깊이도 자연스레 깊어지지 않게된다.

중요한건 인덱스 키 값의 크기는 가능하면 작게 만들어야 하며, 아무리 대용량 DB라 하더라도 B-Tree 의 깊이가 4-5 이상까지 깊어지는 경우는 거의 없다.

 

- Cardinality(기수성)

모든 인덱스 키값 가운데 유니크한 값의 개수를 의미한다.

전체 인덱스 키 값이 100개일 때, 유니크한 값의 수가 10이라면 기수성은 10이다.

기수성이 높아야 선택도도 높아져 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

해당 컬럼의 중복되는 값의 개수가 많아지면 결국 해당 인덱스는 불필요한 것과 마찬가지다.

 

- 읽어야 하는 레코드의 건수

인덱스를 통해 검색하는 것은 읽는 도중 과정 하나를 더 거치는 것이다.

만약 100만건이 저장되어 있는 테이블에 50만건의 레코드를 검색하는 쿼리를 작성한다고 가정해보자.

이는 DB에서 필요없는 50만건을 제외하는 성능과, 인덱스에서 필요한 50만건을 조회하는 성능을 비교해봐야 한다.

일반적으로 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 사용하지 않고 직접 풀스캔하는게 더 효율적이라고 한다.

 

 

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

MySQL 이 어떻게 인덱스를 이용해 실제 레코드를 읽어내는지 알아보자.

대표적으로 3가지 방법이 있다.

 

- 인덱스 레인지 스캔

가장 대표적인 접근 방식으로 밑의 2가지 방식보다는 빠른 방법이다.

인덱스를 통해 레코드 한 건만을 읽는 경우와 한 건 이상 읽는 경우를 각각 다른 이름으로 구분하지만 책에서는 두가지 모두 인덱스 레인지 스캔이라고 표현하였다.

인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다.

다음과 같은 쿼리가 실행됐다고 가정해보자.

SELECT * FROM employees WHERE first_name BETWEEN 'Ebbe' AND 'Gad';

루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 리프 노드까지 찾아 들어가야만 비로소 실제로 원하는 시작 지점을 찾을 수 있다.

시작 지점을 찾으면 그 때부터는 리프 노드의 레코드만 순서대로 읽으면 된다. => 정렬되어 있기 때문.

만약 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 통해 다음 리프 노드를 찾아서 다시 스캔한다.

결국 리프 노드를 스캔하면서 실제 DB 테이블에 저장된 값을 가져와야 하는데 이 때 레코드 한건 한건 단위로 랜덤 I/O 가 실행된다.

랜덤 I/O 는 리소스가 많이 들기 때문에 전체 레코들 중 20~25%가 넘는 레코드들을 조회할 때에는 풀스캔이 낫다.

 

 

- 인덱스 풀 스캔

인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 하며, 일반적으로 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닐 경우에 사용된다.

예를 들어 인덱스를 생성할 때 (A,B,C) 로 생성했지만 조건절에는 B 혹은 C 칼럼으로 검색하는 경우이다.

 

일반적으로 인덱스의 크기는 실제 테이블의 크기보다 작기 때문에 테이블 풀 스캔보다는 효율적이다.

때문에 쿼리에서 인덱스로 원하는 값을 모두 조회할 수 있을 때 사용하고, 절대 테이블의 추가 정보까지 필요하다면 사용해서 안된다.

 

 

- 루스 인덱스 스캔

루스 인덱스 스캔은 중간마다 필요하지 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리한다.

일반적으로 GROUP BY 혹은 집합 함수의 MAX, MIN 최적화에 사용된다.

보통 두 칼럼으로 인덱스가 생성되어 있을 때, 앞선 칼럼의 조건에 만족하지 않으면 뒤 칼람은 볼 필요 없이 스킵해서 처리하는 방식으로 진행된다.

 

 

다중 칼럼 인덱스

현업에서는 하나의 칼럼으로 구성된 인덱스들보다 2개 이상으로 구성된 인덱스가 더 많이 사용된다.

이를 다중 칼럼 인덱스라고 부른다.

여기서 중요한 것은 항상 앞선 칼럼에 의해서 정렬된다는 것이다.

두 번째 칼럼은 첫 번째 칼럼에 의존해서 정렬되어 있고, 세 번째 칼럼은 두 번째 칼럼에 의존해서 정렬되어 있다.

때문에 다중 칼럼 인덱스에서는 인덱스 내에서 각 칼럼의 위치와 순서가 중요하며 신중히 결정해야한다.

 

 

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

쿼리의 WHERE 조건과 GROUP BY, ORDER BY 절이 어떤 경우에 인덱스를 사용해야 하고 어떤 방식으로 사용해야 하는지 식별할 수 있어야 한다. 그래야지 쿼리를 최적화 하거나, 쿼리에 맞게 인덱스를 최적으로 생성할 수 있다.

 

비교 조건의 종류와 효율성

다중 칼럼 인덱스에서 각 칼럼의 순서와 그 칼럼에 사용된 조건이 동등 비교인지, 범위 조건이지에 따라 인덱스 칼럼의 활용 형태와 효율이 달라진다. 다음과 같은 쿼리가 실행된다고 가정해보자.

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

전자에서는 dept_no 가 d002 이고 emp_no 가 10144 보다 큰 레코드 시작점을 찾고, 그 이후에는 detp_no 가 d002 가 아닐 때까지 인덱스를 쭉 읽기만 하면 된다. 읽은 레코드 모두가 사용자가 원하는 결과임을 알 수 있다. 반대로 후자는 emp_no 가 10144 보다 큰 레코드를 찾고 그 이후 모든 레코드에 대해 dept_no 가 d002 인지 비교하는 필터링 과정을 걸쳐야 한다.

 

전자와 같이 작업의 범위를 좁히는데 도움을 준 조건을 작업 범위 결정 조건이라 하고, 후자 같이 범위를 줄이지 못 하고 단순히 필터링 역할만 하는 조건을 필터링 조건이라고 표현한다.

작업 범위를 결정하는 조건은 많으면 많을수록 쿼리의 처리 성능을 높이지만, 필터링 조건이 많다고 해서 쿼리의 처리 성능이 높아지지 않을 뿐더러 오히려 쿼리 실행을 느리게 만들 수도 있다.

 

 

인덱스의 가용성 (정상적으로 사용 가능한지)

두가지 Case 가 있다고 가정하자.

Case A : INDEX(first_name)

Case B : INDEX(dept_no, emp_no)

 

Case A 에서 SELECT * FROM employees WHERE first_name LIKE '%mer'; 쿼리는 인덱스의 효과를 사용할 수 없다. 앞 문자를 기준으로 정렬되기 때문이다.

Case B 에서 또한 SELECT * FROM dept_emp WHERE emp_no >= 10144; 쿼리에서 인덱스 효과를 볼 수 없다. emp_no 는 dept_no 에 의존해서 정렬되기 때문이다.

 

 

효율성과 가용성 판단

일반적으로 다음과 같은 조건문들은 작업 범위 결정 조건으로 사용할 수 없다.

다만 필터링 조건으로는 사용할 수 있다.

 

1. NOT-EQUAL로 비교된 경우

2. LIKE '%??' 형태로 문자열 패턴이 비교된 경우

3. 스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우 (ex WHERE SUBSTRING(column, 1, 1) = 'X')

4. NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우

5. 데이터 타입이 서로 다른 비교 (즉 인덱스 칼럼의 타입을 변환해야 할 경우)

6. 문자열 데이터 타입의 콜레이션이 다른 경우(utf8 vs euckr)