[MySQL] 인덱스 1

랜덤 I/O와 순차 I/O

---

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

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

위 그림에서 순차 I/O는 디스크에 기록해야 할 위치를 찾기 위해 디스크의 헤드를 1번 움직였고, 랜덤 I/O는 디스크 헤드를 3번 움직였는데, 이는 순차 I/O는 랜덤 I/O보다 거의 3배 정도 빠르다고 볼 수 있다. 따라서 여러 번 쓰기 또는 읽기를 요청하는 랜덤 I/O 작업이 작업 부하가 훨씬 더 크다. 대부분의 작업은 이러한 작은 데이터를 빈번히 읽고 쓰기 때문에 MySQL 서버에는 그룹 커밋이나 바이너리 로그 버퍼 또는 InnoDB 로그 버퍼 등의 기능이 내장돼있다.

쿼리를 튜닝해서 랜덤 I/O를 순차 I/O로 바꿔서 실행할 방법은 그다지 많지 않다. 일반적으로 쿼리를 튜닝하는 것은 쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것을 의미한다.

인덱스 레인지 스캔은 데이터를 읽기 위해 주로 랜덤 I/O를 사용하며, 풀 테이블 스캔은 순차 I/O를 사용한다.
그래서 큰 테이블의 레코드 대부분을 읽는 작업에서는 인덱스를 사용하지 않고 풀 테이블 스캔을 사용하도록 유도할 때도 있다. 이는 순차 I/O가 랜덤 I/O보다 훨씬 빨리 많은 레코드를 읽어올수 있기 때문인데, 이런 형태는 OLTP(On-Line Transaction Processing) 성격의 웹 서비스보다는 데이터 웨어하우스나 통계 작업에서 자주 사용된다.

인덱스

---

DBMS에서 인덱스는 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 포기하고 데이터의 읽기 속도를 높이는 기능이다.

테이블의 인덱스를 하나 더 추가할지 말지는 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하느냐에 따라 결정된다. SELECT 쿼리 문장의 WHERE 조건절에 사용되는 칼럼이라고 해서 전부 인덱스로 생성하면 데이터 저장 성능이 떨어지고 인덱스의 크기가 비대해져 오히려 역효과를 불러올 수 있다.

B-Tree 인덱스

---

B-Tree는 칼럼의 원래 값을 변형시키지 않고(물론 값의 앞 부분만 잘라서 관리하기는 하지만) 인덱스 구조체 내에서는 항상 정렬된 상태로 유지한다. 전문 검색과 같은 특수한 요건이 아닌 경우, 대부분 인덱스는 거의 B-Tree를 사용할 정도로 일반적인 용도에 적합한 알고리즘이다.

구조 및 특성

B-Tree는 트리 구조의 최상위에 하나의 "루트 노드"가 존재하고 그 하위에 자식 노드가 붙어 있는 형태다. 트리 구조의 가장 하위에 있는 노드를 "리프 노드"라 하고, 트리 구조에서 루트 노드가 아니고 리프 노드가 아닌 중간의 노드를 "브랜치 노드"라고 한다.

데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.

위 그림을 보면 인덱스의 키 값은 모두 정렬돼 있지만, 데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서로 저장돼 있다. 데이터 파일의 레코드를 전혀 삭제하거나 수정하지 않고 INSERT만 수행한다면 순서대로 저장되겠지만, 레코드가 삭제되어 빈 공간이 생기면 그다음의 INSERT는 가능한 한 삭제된 공간을 재활용하도록 설계되기 때문에 항상 INSERT된 순서로 저장되는 것은 아니다.

또한, InnoDB 테이블에서 인덱스를 통해 레코드를 읽을 때는 데이터 파일을 바로 찾아가지 않고, 인덱스에 저장돼 있는 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽는다. 즉, InnoDB 스토리지 엔진에서는 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한번 검색해야 한다.

B-Tree 인덱스 키 추가 및 삭제

인덱스 키 추가

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

MyISAM이나 MEMORY 스토리지 엔진을 사용하는 테이블에서는 INSERT 문장이 실행되면 즉시 새로운 키 값을 B-Tree 인덱스에 변경하지만, InnoDB 스토리지 엔진은 필요하다면 인덱스 키 추가 작업을 지연시켜 나중에 처리할 수도 있다.(프라이머리 키나 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 즉시 B-Tree에 추가하거나 삭제한다.)

인덱스 키 삭제

B-Tree의 키 값 삭제는 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료된다. 이렇게 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재활용할 수 있다. 인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 이 작업 역시 디스크 I/O가 필요한 작업이다.

MySQL 5.5 이상 버전의 InnoDB 스토리지 엔진에서는 이 작업 또한 버퍼링되어 지연 처리(MySQL 서버가 내부적으로 처리)될 수도 있다.

인덱스 키 변경

인덱스 키 값을 변경하는 작업은 기존 인덱스 키 값을 삭제한 후 새로운 인덱스 키 값을 추가하는 작업으로 처리되고, InnoDB 스토리지 엔진을 사용하는 테이블에 대해서는 이 작업 모두 체인지 버퍼를 활용해 지연 처리될 수 있다.

인덱스 키 검색

인덱스 검색 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행한다.

인덱스 트리 탐색은 SELECT에서만 사용하는 것이 아니라 UPDATE나 DELETE를 처리하기 위해 항상 해당 레코드를 먼저 검색해야 할 경우에도 사용된다. 여기서 중요한 점은 인덱스의 키 값에 변경이 가해진 후 비교되는 경우에는 절대 B-Tree의 빠른 검색 기능을 사용할 수 없는데, 이는 변형된 값은 B-Tree 인덱스에 존재하는 값이 아니기 때문이다. 따라서 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree의 장점을 이용할 수 없으므로 주의해야 한다.

InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키 락(갭락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼있다. 따라서 UPDATE나 DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠그거나 전체 레코드를 잠글 수도 있다.

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

아래 쿼리를 실행했을 때, 각 스캔 방식에 따라 어떻게 이루어지는 알아보자.

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

인덱스 레인지 스캔

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

루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 찾아 들어가야만 비로소 필요한 레코드의 시작 지점을 찾을 수 있다. 시작 지점부터 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔한다. 그리고 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다.

인덱스 풀 스캔

인덱스 레인지 스캔과 마찬가지로 인덱스를 사용하지만 인덱스 체인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 한다.

먼저 인덱스 리프 노드의 제일 앞 또는 제일 뒤로 이동한 후, 인덱스의 리프 노드를 연결하는 링크드 리스트를 따라서 처음부터 끝까지 스캔하는 방식을 인덱스 풀 스캔이라고 한다. 이 방식은 인덱스 레인지 스캔보다는 빠르지 않지만, 인덱스에 포함된 칼럼만으로 쿼리를 처리할 수 있는 경우 테이블의 레코드를 읽을 필요가 없기 때문에 테이블 풀 스캔보다는 효율적이다.

요약

• I/O는 하드 디스크 드라이브의 플래터(원판)을 돌려서 데이터가 저장된 위치로 디스크 헤더를 이동시킨 뒤 데이터를 읽는다.
• 디스크에 데이터를 쓰고 읽는 데 걸리는 시간은 디스크 헤더를 해당 위치로 옮기는 단계에서 결정된다.
• 쿼리를 튜닝한다는 것은 쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것이다.
• 인덱스는 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 포기하고 데이터의 읽기 속도를 높이는 기능이다.
• B-Tree 인덱스는 칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘이다.
• 데이터 파일의 레코드는 빈 공간이 생기면 그다음의 INSERT는 가능한 삭제된 빈 공간을 재활용하기 때문에 항상 INSERT된 순서대로 저장되는 것은 아니다.
• B-Tree의 키 값 삭제는 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 마크를 한 뒤. 추후 재사용된다.
• B-Tree의 키 값 수정은 기존의 값을 변경하는 것이 아닌, 기존 인덱스를 삭제한 후 새로운 인덱스를 추가하는 방식으로 이루어진다.
• 인덱스 레인지 스캔은 검색해야할 인덱스 범위가 결정되었을 때 사용하는 방식이다.
• 인덱스 풀 스캔은 인덱스의 처음부터 끝까지 모두 읽는 방식이다. 따라서 인덱스 레인지 스캔보다는 느리지만, 테이블 풀 스캔보다는 효율적이다.

Reference
백은빈, 이성욱. 『Real MySQL 8.0』. 위키북스, 2022