[MySQL] B-Tree 인덱스

인덱스는 데이터베이스 쿼리의 성능을 언급하면서 빼놓을 수 없는 부분입니다. MySQL에서 사용 가능한 인덱스의 종류 및 특성에서 각 특성의 차이는 상당히 중요하며, 물리 수준의 모델링을 할 때도 중요한 요소가 될 것입니다. 다른 RDBMS에서 제공하는 모든 기능을 제공하지는 않지만, MySQL에서는 인덱싱이나 검색 방식에 따라 다른 스토리지 엔진을 선택해야 할 수도 있기 때문에 여전히 인덱스에 대한 기본 지식은 중요하며, 쿼리 튜닝의 기본이 될 것입니다. 또한 인덱스에만 의존적인 용어는 아니지만, 자주 언급되는 "랜덤(Random) I/O"와 "순차(Sequential) I/O"와 같은 디스크 읽기 방식도 알아두는 것이 좋습니다.

디스크 읽기 방식

---

컴퓨터의 CPU나 메모리와 같은 전기적 특성을 띤 장치의 성능은 짧은 시간 동안 매우 빠른 속도로 발전했지만 디스크와 같은 기계식 장치의 성능은 상당히 제한적으로 발전했습니다. 데이터베이스나 쿼리 튜닝에 어느정도 지식을 갖춘 사용자가 많이 절감하고 있듯이, 데이터베이스의 성능 튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건인 것들이 상당히 많습니다.

저장 매체

디스크의 읽기 방식을 살펴보기 전에 간단히 데이터를 저장할 수 있는 매체(Media)에 대해 살펴보면, 일바적으로 서버에 사용되는 저장 매체는 크게 3가지로 나뉩니다.

내장 디스크(Internal Disk)

DAS(Direct Attached Storage)

NAS(Network Attached Storage)

SAN(Storage Area Network)

내장 디스크는 개인용 PC의 본체 내에 장착된 디스크와 같은 매체입니다. 물론 서버용으로 사용되는 디스크는 개인 PC에 장착되는 것보다는 빠르고 안정적인 것들입니다. 그리고 개인 PC와는 달리 데이터베이스 서버용으로 사용되는 장비는 일반적으로 4~6개 정도의 내장 디스크를 장착합니다. 하지만 컴퓨터의 본체 내부 공간은 제한적이어서 장착할 수 있는 디스크의 개수가 적고 용량도 부족할 때가 많습니다.

내장 디스크의 용량 문제를 해결하기 위해 주로 사용하는 것이 DAS인데, DAS는 컴퓨터의 본체와는 달리 디스크만 있는 것이 특징입니다. DAS 장치는 독자적으로 사용할 수 없으며, 컴퓨터 본체에 연결해서만 사용할 수 있습니다. DAS나 내장 디스크는 모두 SATA나 SAS와 같은 케이블로 연결되기 때문에 실제 사용자에게는 거의 같은 방식으로 사용되며, 성능 또한 내장 디스크와 거의 비슷합니다. 최근의 DAS는 디스크를 최대 200개까지 장착할 수 있는 것들도 있기 때문에 대용량의 디스크가 필요한 경우에는 DAS가 적합합니다. 하지만 DAS는 반드시 하나의 컴퓨터 본체에 연결해서 사용할 수 있기 때문에 디스크의 정보를 여러 컴퓨터가 동시에 공유하는 것이 불가능 합니다.

내장 디스크와 DAS의 문제점을 동시에 해결하기 위해 주로 NAS와 SAN을 사용합니다. DAS와 NAS의 가장 큰 차이는 여러 컴퓨터에서 동시에 사용할 수 있는지와 컴퓨터 본체와 연결되는 방식입니다. 위에서도 살펴봤지만 DAS는 내장 디스크와 같이 컴퓨터 본체와 SATA나 SAS 또는 SCSI 케이블로 연결되지만, NAS는 TCP/IP를 통해 연결됩니다. NAS는 동시에 여러 컴퓨터에서 공유해서 사용할 수 있는 저장매체이지만 SATA나 SAS 방식의 직접 연결보다는 속도가 매우 느립니다.

SAN은 DAS로는 구축할 수 없는 아주 대용량의 스토리지 공간을 제공하는 장치입니다. SAN은 여러 컴퓨터에서 동시에 사용할 수 있을뿐더러 컴퓨터 본체와 광케이블로 연결되기 때문에 상당히 빠르고 안정적인 데이터 처리(읽고 쓰기)를 보장해줍니다. 하지만 그만큼 고가의 구축 비용이 들기 때문에 각 기업에서는 중요 데이터를 보관할 경우에만 일반적으로 사용합니다.

NAS는 TCP/IP로 데이터가 전송되기 때문에 빈번한 데이터 읽고 쓰기가 필요한 데이터베이스 서버용으로는 거의 사용되지 않습니다. 내장 디스크 → DAS → SAN 순으로, 뒤로 갈수록 고사양 고성능이며, 구축 비용도 올라갑니다. 각 장치가 얼마나 많은 디스크 드라이브를 장착할 수 있는지, 그리고 어떤 방식으로 컴퓨터 본체에 연결되는지에 따른 구분일 뿐, 여기에 언급된 모든 저장 매체는 내부적으로 1개 이상의 디스크 드라이브를 장착하고 있다는 점은 같습니다. 대부분의 저장 매체는 디스크 드라이브의 플래터(Platter, 디스크 드라이브 내부의 데이터 저장용 원판)를 회전시켜서 데이터를 읽고 쓰는 기계적인 방식을 사용합니다.

디스크 드라이브와 솔리드 스테이트 드라이브

컴퓨터에서 CPU나 메모리와 같은 주요 장치는 대부분 전자식 장치지만 디스크 드라이브는 기계식 장치입니다. 그래서 데이터베이스 서버에서는 항상 디스크 장치가 병목 지점이 됩니다. 이러한 기계식 디스크 드라이브를 대체하기 위해 전자식 저장 매체인 SSD(Solid State Drive)가 많이 출시되고 있씁니다. SSD도 기존 디스크 드라이브와 같은 인터페이스(SATA나 SAS)를 지원하므로 내장 디스크나 DAS 또는 SAN에 그대로 사용 가능합니다.

SSD는 기존의 디스크 드라이브에서 데이터 저장용 플래터를 제거하고 대신 플래시 메모리를 장착하고 있습니다. 그래서 디스크 원판을 기계적으로 회전시킬 필요가 없으므로 아주 빨리 데이터를 읽고 쓸 수 있습니다. 플래시 메모리는 전원이 공급되지 않아도 데이터가 삭제되지 않습니다. 그리고 컴퓨터 메모리보다는 느리지만 기계식 디스크 드라이브보다는 훨씬 빠릅니다.

디스크의 헤더를 움직이지 않고 한번에 많은 데이터를 읽는 순차 I/O에서는 SSD가 디스크 드라이브보다 조금 빠르거나 거의 비슷한 성능을 보이기도 합니다. 하지만 SSD의 장점은 기존의 디스크 드라이브보다 랜덤 I/O가 훨씬 빠르다는 것입니다.  데이터베이스 서버에 순차 I/O 작업은 그다지 비중이 크지 않고 랜덤 I/O를 통해 작은 데이터를 읽고 쓰는 작업이 대부분이므로 SSD의 장점은 DBMS용 스토리지에 최적이라고 볼 수 있씁니다. 

가령 벤치마크 결과를 살펴보면 SSD는 초당 436개의 트랜잭션을 처리했지만 디스크 드라이브는 초당 60개의 트랜잭션밖에 처리하지 못했씁니다. 이 벤치마크 결과는 저자가 간단히 준비한 데이터로 테스트한 내용이라서 실제 애플리케이션에서는 어느 정도의 성능 차이를 보일지 예측하기가 어렵니다. 하지만 일반적인 웹 서비스 환경의 데이터베이스에서는 SSD가 디스크 드라이브보다는 훨씬 빠릅니다. 물론 애플리케이션을 직접 벤치마킹해볼 수 있다면 더 나은 선택을 할 수 있을 것입니다.

참고 : SSD를 쓰면 DBMS가 빨라질까?

랜덤 I/O와 순차 I/O

랜덤 I/O라는 표현은 디스크 드라이브의 플래터(원판)를 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것을 의미하는데, 사실 순차 I/O 또한 이 작업은 같습니다. 그렇다면 랜덤 I/O와 순차 I/O는 어떤 차이가 있을까요?

Sequential 액세스 방식 ([그림 Ⅲ-1-13]에서 ⑤번)

Random 액세스 방식 ([그림 Ⅲ-1-13]에서 ①, ②, ③, ④, ⑥번)

순차 I/O는 연속된 3개의 페이지를 접근하게 되는 방식이라 디스크에 기록하기 위해 한번 시스템 콜을 요청하지만 랜덤 I/O는 3개의 페이지를 디스크에 기록하기 위해 3번의 시스템 콜을 하게 되는 방식이 됩니다. 즉, 디스크에 기록해야 할 위치를 찾기 위해 순차 I/O는 디스크의 헤드를 1번 움직였고, 랜덤 I/O는 디스크 헤드를 3번 움직인 것입니다. 디스크에 데이터를 쓰고 읽는 데 걸리는 시간은 디스크 헤더를 움직여서 읽고 쓸 위치로 옮기는 단계에서 결정됩니다. 결국 여기서 제시한 예에서는 순차 I/O가 랜덤 I/O보다 거의 3배 정도 빠르다고 볼 수 있습니다. 즉, 디스크의 성능은 디스크 헤더의 위치 이동 없이 얼마나 많은 데이터를 한 번에 기록하느냐에 의해 결정된다고 볼 수 있습니다.

그래서 여러번 쓰기 또는 읽기를 요청하는 랜덤 I/O 작업이 훨씬 작업의 부하가 커지게 됩니다. 데이터베이스 대부분의 작업은 이러한 작은 데이터를 빈번히 읽고 쓰기 때문에 MySQL 서버에는 그룹 커밋이나 바이너리 로그 버퍼 또는 InnoDB 로그 버퍼 등의 기능이 내장되어 있습니다.

랜덤 I/O나 순차 I/O 모두 파일에 쓰기를 실행하면, 반드시 동기화(fsync 또는 flush 작업)가 필요합니다. 그런데 순차 I/O인 경우에도 이런 파일 동기화 작업이 빈번히 발생한다면 랜덤 I/O와 같이 비효율적인 형태로 처리될 때가 많습니다. 기업용으로 사용하는 데이터베이스 서버에는 캐시 메모리가 장착된 RAID 컨트롤러가 일반적으로 사용되는데, RAID 컨트롤러의 캐시 메모리는 아주 빈번한 파일 동기화 작업이 호출되는 순차 I/O를 효율적으로 처리될 수 있게 변환하는 역할을 하게 됩니다.

사실 쿼리를 튜닝해서 랜덤 I/O를 순차 I/O로 바꿔서 실행할 방법은 그다지 많지 않습니다. 일반적으로 쿼리를 튜닝하는 것은 랜덤 I/O 자체를 줄여주는 것이 목적이라고 할 수 있습니다. 여기서 랜덤 I/O를 줄인다는 것은 쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것을 의미합니다.

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

1) OLTP: On-Line Transaction Processing (데이터 갱신위주)

네트워크 상의 여러 이용자가 실시간으로 데이터베이스의 데이터를 갱신하거나 조회하는 등의 단위 작업을 처리하는 방식을 말합니다.

2) OLAP: On-Line Analytic Processing (데이터 조회위주)

정보위주의 처리 분석을 의미합니다. 의사결정에 활용할 수 있는 정보를 얻을 수 있게 해주는 기술 입니다.

 

인덱스란?

---

많은 사람들이 인덱스를 언급할 때는 항상 책의 제일 끝에 있는 찾아보기(또는 "색인")로 설명하곤 합니다. 책의 마지막에 있는 "찾아보기"가 인덱스에 비유된다면 책의 내용은 데이터 파일에 해당한다고 볼 수 있습니다. 책의 찾아보기를 통해 알아낼 수 있는 페이지 번호는 데이터 파일에 저장된 레코드의 주소에 비유될 것입니다. DBMS도 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 오래 걸립니다. 그래서 컬럼(또는 컬럼들)의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍(key-Value pair)로 인덱스를 만들어 두는 것입니다. 그리고 책의 "착아보기"와 DBMS의 인덱스의 공통점 가운데 중요한 것이 바로 정렬입니다. 책의 찾아보기도 내용이 많아지면 우리가 원하는 검색어를 찾아내는 데 시간이 걸릴 것입니다. 그래서 최대한 빠르게 찾아갈 수 있게 "ㄱ", "ㄴ", "ㄷ", ...와 같은 순서대로 정렬돼 있는데, DBMS의 인덱스도 마찬가지로 컬럼의 값을 주어진 순서로 미리 정렬해서 보관합니다.

프로그래밍 언어의 자료구조와 인덱스와 데이터 파일을 비교해 가면서 살펴보면 다음과 같습니다. 프로그래밍 언어별로 각 자료구조의 이름이 조금씩 다르긴 하지만 SortedList와 ArrayList라는 자료구조는 익숙할 정도로 많이 들어본 적이 있을 것입니다. SortedList는 DBMS의 인덱스와 같은 자료구조이며, ArrayList는 데이터 파일과 같은 자료구조를 이용합니다. SortedList는 저장되는 값을 항상 정렬된 상태로 유지하는 자료구조이며, ArrayList는 값을 저장되는 순서대로 그대로 유지하는 자료구조입니다. DBMS의 인덱스도 SortedList와 마찬가지로 저장되는 컬럼의 값을 이용해 항상 정렬된 상태로 유지합니다. 데이터 파일은 ArrayList와 같이 저장된 순서대로 별도의 정렬없이 그대로 저장해둡니다.

SortedList 자료구조는 데이터가 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리지만, 이미 정렬돼 있어서 아주 빨리 원하는 값을 찾아올 수 있습니다. DBMS의 인덱스도 인덱스가 많은 테이블은 당연히 INSERT나 UPDATE 그리고 DELETE 문장의 처리가 느려집니다. 하지만 이미 정렬된 "찾아보기"용 표(인덱스)를 가지고 있기 때문에 SELECT 문장은 매우 빠르게 처리할 수 있습니다.

결론적으로 DBMS에서 인덱스는 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능입니다. 여기서도 알 수 있듯이 테이블의 인덱스를 하나 더 추가할지 말지는 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하는지의 여부에 따라 결정돼야 합니다. SELECT 쿼리 문장의 WHERE 조건절에 사용되는 컬럼이라고 전부 인덱스로 생성하면 데이터 저장 성능이 떨어지고 인덱스의 크기가 비대해져서 오히려 역효과만 불러올 수 있습니다.

인덱스를 역할별로 구분한다면 프라이머리 키(Primary Key)와 보조 키(Secondary Key)로 구분해 볼 수 있습니다. 데이터 저장 방식(알고리즘)별로 구분하는 것은 상당히 많은 분류가 가능하겠지만 대표적으로 B-Tree 인덱스와 Hash 인덱스로 구분할 수 있습니다. 그리고 Fractal-Tree 인덱스와 같은 알고리즘도 존재합니다. 

B-Tree 알고리즘은 가장 일반적으로 사용되는 인덱스 알고리즘으로서, 상당히 오래전에 도입된 알고리즘이며 그만큼 성숙해진 상태입니다. B-Tree 인덱스는 칼럼의 값을 변형하지 않고, 원래의 값을 이용해 인덱싱하는 알고리즘 입니다.

Hash 인덱스 알고리즘은 컬럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로, 매우 빠른 검색을 지원합니다. 하지만 값을 변형해서 인덱싱하므로, 전방(Prefix) 일치와 같이 값의 일부만 검색하고자 할 때는 해시 인덱스를 사용할 수 없습니다. Hash 인덱스는 주로 메모리 기반의 데이터베이스에서 많이 사용합니다.

Fractal-Tree 알고리즘은 B-Tree의 단점을 보완하기 위해 고안된 알고리즘입니다. 값을 변형하지 않고 인덱싱하며 범용적인 목적으로 사용할 수 있다는 측면에서 B-Tree와 거의 비슷하지만 데이터가 저장되거나 삭제될 때 처리 비용을 상당히 줄일 수 있게 설계된 것이 특징입니다. 아직 B-Tree 알고리즘만큼 안정적이고 성숙되진 않았지만 아마도 조만간 B-Tree 인덱스의 상당 부분을 대체할 수 있지 않을까 생각합니다.

데이터의 중복 허용 여부로 분류하면 유니크 인덱스(Unique)와 유니크하지 않은 인덱스(Non-Unique)로 구분할 수 있습니다. 인덱스가 유니크한지 아닌지는 단순하게 같은 값이 1개만 존재하는지 1개 이상 존재할 수 있는지를 의미하지만 실제 DBMS의 쿼리를 실행해야 하는 옵티마이저에게는 상당히 중요한 문제가 됩니다. 

B-Tree 인덱스

---

B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 또한 가장 먼저 도입된 알고리즘입니다. 하지만 아직도 가장 범용적인 목적으로 사용되는 인덱스 알고리즘입니다. B-Tree에는 여러 가지 변형된 형태의 알고리즘이 있는데, 일반적으로 DBMS에서는 주로 B+-Tree 또는 B*-Tree가 사용됩니다. 인터넷상에서 쉽게 구할 수 있는 B-Tree의 구조를 설명한 그림 때문인지 많은 사람들이 B-Tree의 "B"가 바이너리(이진) 트리라고 잘못 생각하고 있습니다. 하지만 B-Tree의 "B"는 "Binary(이진)"의 약자가 아니라 "Balanced"를 의미합니다.

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

구조 및 특성

B-Tree 인덱스를 제대로 사용하려면 B-Tree의 기본적인 구조는 알고 있어야 합니다. B-Tree는 트리 구조의 최상위에 하나의 "루트 노드"가 존재하고 그 하위에 자식 노드가 붙어 있는 형태입니다. 트리 구조의 가장 하위에 있는 노드를 "리프 노드"라 하고, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간 노드를 "브랜치 노드"라고 합니다. 데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소 값을 가지고 있습니다.

인덱스의 키값은 모두 정렬돼 있지만 데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서대로 저장돼 있습니다. 많은 사람이 데이터 파일의 레코드는 INSERT된 순서대로 저장되는 것으로 생각하지만 그렇지 않습니다. 만약 테이블의 레코드를 전혀 삭제나 변경없이 INSERT만 수행한다면 맞을 수도 있습니다. 하지만 레코드가 삭제되어 빈 공간이 생기면 그다음의 INSERT는 가능한 삭제된 공간을 재활용하도록 DBMS가 설계되기 때문에 항상 INSERT된 순서로 저장되는 것은 아닙니다.

대부분 RDBMS의 데이터 파일에서 레코드는 특정 기준으로 정렬되지 않고 임의의 순서대로 저장됩니다. 하지만 InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되므로 기본적으로 프라이머리 키 순서대로 정렬되어 저장됩니다. 이는 오라클 IOT(Index organized table)나 MS-SQL의 클러스터 테이블과 같은 구조를 말합니다. 다른 DBMS에서는 클러스터링 기능이 선택 사항이지만, InnoDB에서는 사용자가 별도의 명령이나 옵션을 선택하지 않아도 디폴트로 클러스터링 테이블이 생성됩니다. 클러스터링이란 비슷한 값들은 최대한 모아서 저장하는 방식을 의미합니다.

인덱스는 테이블의 키 컬럼만 가지고 있으므로 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 합니다. 이를 위해 인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가지게 됩니다. "레코드 주소"는 DBMS 종류나 MySQL의 스토리지 엔진에 따라 의미가 달라집니다. 오라클은 물리적인 레코드 주소가 되지만 MyISAM 테이블에서는 내부적인 레코드의 아이디(번호)를 의미합니다. 그리고 InnoDB 테이블에서는 프라이머리 키에 의해 클러스터링되기 때문에 프라이머리 키값 자체가 주소 역할을 합니다. 실제 MySQL 테이블의 인덱스는 항상 인덱스 컬럼 값과 주소 값(MyISAM의 레코드 아이디 값 또는 InnoDB의 프라이머리 키값)의 조합이 인덱스 레코드로 구성됩니다.

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

---

테이블의 레코드를 저장하거나 변경하는 경우, 인덱스 키 추가나 삭제 작업이 발생합니다. 인덱스 키 추가나 삭제가 어떻게 처리되는지 알아두면 쿼리의 성능을 쉽게 예측할 수 있을 것입니다. 또한, 인덱스를 사용하면서 주의해야 할 사항도 함께 살펴보겠습니다.

인덱스 키 추가

새로운 키값이 B-Tree에 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있습니다. B-Tree에 저장될 때는 저장될 키값을 이용해 B-Tree상의 적절한 위치를 검색해야 합니다. 저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장합니다. 만약 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리(Split)돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어집니다. 이러한 작업 탓에 B-Tree는 상대적으로 쓰기 작업(새로운 키를 추가하는 작업)에 비용이 많이 드는 것으로 알려졌습니다.

인덱스 추가로 인해 INSERT나 UPDATE 문장이 어떤 영향을 받을지 궁금해하는 사람이 많습니다. 하지만 이 질문에 명확하게 답변하려면 테이블의 컬럼 수, 컬럼의 크기, 인덱스 컬럼의 특성 등을 확인해야합니다. 대략적으로 계산하는 방법은 테이블에 레코드를 추가하는 작업 비용을 1이라고 가정하면 해당 테이블의 인덱스에 키를 추가하는 작업 비용을 1~1.5 정도로 예측하는 것이 일반적입니다. 일반적으로 테이블에 인덱스가 3개(테이블의 모든 인덱스가 B-Tree라는 가정하에)가 있다면 이때 테이블에 인덱스가 하나도 없는 경우 작업 비용이 1이고, 3개인 경우에는 5.5 정도의 비용(1.5*3 + 1) 정도로 예측해 볼 수 있씁니다. 중요한 것은 이 비용의 대부분이 메모리와 CPU에서 처리하는 시간이 아니라 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야하기 때문에 시간이 오래 걸린다는 점입니다.

MyISAM이나 Memory 스토리지 엔진을 사용하는 테이블에서는 INSERT 문장이 실행되면 즉시 새로운 키값을 B-Tree 인덱스에 반영합니다. 즉 B-Tree에 키를 추가하는 작업이 완료될 때까지 클라이언트는 쿼리의 결과를 받지 못하고 기다리게 됩니다. MyISAM 스토리지 엔진은 delay-key-write" 파라미터를 설정해 인덱스 키 추가 작업을 미뤄서(지연) 처리할 수 있는데, 이는 동시 작업 환경에서는 적합하지 않습니다. InnoDB 스토리지 엔진은 이 작업을 조금 더 지능적으로 처리하는데, 상황에 따라 적절하게 인덱스 키 추가 작업을 지연시켜 나중에 처리할지, 아니면 바로 처리할지 결정합니다.

(1) 사용자의 쿼리 실행

(2) InnoDB의 버퍼 풀에 새로운 키값이 추가해야 할 페이지(B-Tree의 리프 노드)가 존재한다면 즉시 키 추가 작업 처리

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

(4) 백그라운드 작업으로 인덱스 페이지를 읽을 때마다 인서트 버퍼에 머지해야 할 인덱스 키 값이 있는지 확인한 후, 있다면 병합함(B-Tree에 인덱스 키와 주소를 저장)

(5) 데이터베이스 서버 자원의 여유가 생기면 MySQL 서버의 인서트 버퍼 머지 스레드가 조금씩 인서트 버퍼에 임시 저장된 인덱스 키와 주소 값을 머지(B-Tree에 인덱스 키와 주소를 저장)시킴

InnoDB 스토리지 엔진의 인서트 버퍼는 MySQL 5.1 이하에서는 INSERT로 인한 인덱스 키 추가 작업만 버퍼링 및 지연 처리를 할 수 있었습니다. 하지만 MySQL 5.5 이상의 버전에서는 INSERT뿐 아니라 DELETE 등에 의한 인덱스 키의 추가 및 삭제 작업까지 버퍼링해서 지연 처리할 수 있게 기능이 확장됐습니다. 그래서 MySQL 5.1 이하 버전에서는 이 기능을 인서트 버퍼링(Insert Buffering)이라고 했지만 MySQL 5.5 이상 버전부터는 체인지 버퍼링(Change Buffering)이라는 이름으로 바뀌었습니다. MySQL 5.5 이상 버전부터는 관련 설정 파라미터로 "innodb_change_buffering"이 새롭게 도입됐습니다. 인서트 버퍼에 의해 인덱스 키 추가 작업이 지연되어 처리된다 하더라도, 이는 사용자에게 아무런 악영향 없이 투명하게 처리되므로 개발자나 DBA는 이를 전혀 신경쓰지 않아도 됩니다. MySQL 5.1 이하 버전에서는 자동으로 적용되는 기능이었지만 MySQL 5.5 이상 버전 부터는 "innodb_change_buffering" 설정값을 이용해 키 추가 작업과 키 삭제 작업 중 어느 것을 지연 처리할지 설정해야 합니다.

인덱스 키 삭제

B-Tree의 키값이 삭제되는 경우는 상당히 간단합니다. 해당 키값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료됩니다. 이렇게 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 또는 재활용할 수 있습니다. 인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 이작업 역시 디스크 I/O가 필요한 작업입니다. MySQL 5.5 이상의 버전의 InnoDB 스토리지 엔진에서는 이 작업 또한 버퍼링되어 지연처리가 될 수도 있습니다. 처리가 지연된 인덱스 키 삭제 또한 사용자에게는 특별한 악영향 없이 MySQL 서버가 내부적으로 처리하므로 특별히 걱정할 것은 없습니다. MyISAM이나 Memory 스토리지 엔진의 테이블에서는 인서트 버퍼와 같은 기능이 없으므로 인덱스 키 삭제가 완료된 후 쿼리 실행이 완료됩니다.

인덱스 키 변경

인덱스의 키값은 그 값에 따라 저장될 리프 노드의 위치가 결정되므로 B-Tree의 키값이 변경되는 경우에는 단순히 인덱상의 키값만 변경하는 것은 불가능합니다. B-Tree의 키값 변경 작업은 먼저 키값을 삭제한 후, 다시 새로운 키값을 추가하는 형태로 처리됩니다. 키 값의 변경 때문에 발생하는 B-Tree 인덱스 키값의 삭제와 추가 작업은 위에서 설명한 절차대로 처리됩니다.

인덱스 키 검색

INSERT, UPDATE, DELETE 작업을 할 때 인덱스 관리에 따르는 추가 비용을 감당하면서 인덱스를 구축하는 이유는 바로 빠른 검색을 위해서입니다. 인덱스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행하는데, 이 과정을 "트리 탐색(Tree traversal)"이라고 합니다. 인덱스 트리 탐색은 SELECT에서만 사용하는 것이 아니라 UPDATE나 DELETE를 처리하기 위해 항상 해당 레코드를 먼저 검색해야 할 경우에도 인덱스가 있으면 빠른 검색이 가능합니다. B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분(Left-most part)만 일치하는 경우에 사용할 수 있습니다. 부등호("<>") 비교나 값의 뒷부분이 일치하는 경우에는 B-Tree 인덱스를 이용한 검색이 불가능합니다. 또한 인덱스를 이용한 검색에서 중요한 사실은 인덱스의 키값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree의 빠른 검색 기능을 사용할 수 없다는 것입니다. 이미 변형된 값은 B-Tree 인덱스에 존재하는 값이 아닙니다. 따라서 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree의 장점을 이용할 수 없으므로 주의해야 합니다.

InnoDB 스토리지 엔진에서 인덱스는 더 특별한 의미가 있습니다. InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키 락(갭 락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있습니다. 따라서 UPDATE나 DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠급니다. 심지어 테이블의 모든 레코드를 잠글 수도 있습니다. InnoDB 스토리지 엔진에서는 그만큼 인덱스의 설계가 중요하고 많은 부분에 영향을 미친다는 것입니다.

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

---

B-Tree 인덱스는 인덱스를 구성하는 컬럼의 크기와 레코드의 건수, 그리고 유니크한 인덱스 키값의 개수 등에 의해 검색이나 변경 작업의 성능이 영향을 받습니다.

인덱스 키 값의 크기

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

이진(Binary) 트리는 각 노드가 자식 노드를 2개만 가지는데, 만약 DBMS의 B-Tree가 이진 트리라면 인덱스 검색이 상당히 비효율적일 것입니다. 그래서 B-Tree의 "B"가 이진(Binary) 트리의 약자는 아니라고 강조했던 것입니다. 일반적으로 DBMS의 B-Tree는 자식 노드의 개수가 가변적인 구조입니다. 그러면 MySQL의 B-Tree는 자식 노드를 몇 개까지 가질지가 궁금할 것입니다. 그것은 바로 인덱스 페이지 크기와 키 값의 크기에 따라 결정됩니다. InnoDB의 모든 페이지 크기는 16KB로 고정돼 있습니다(이를 변경하려면 소스 컴파일이 필요함). 만약 인덱스의 키가 16바이트라고 가정하면 다음 그림과 같이 인덱스 페이지가 구성될 것입니다. 자식 노드 주소라는 것은 여러 가지 복합적인 정보가 담긴 영역이며, 페이지의 종류별로 대략 6바이트에서 12바이트까지 다양한 크기의 값을 가질 수 있습니다. 

1233____ABCD____

자식노드 주소

1233____ABCE____

자식노드 주소

1233____ABCF____

자식노드 주소

하나의 인덱스 페이지(16KB)에 몇 개의 키를 저장할 수 있을까? 계산해 보면 16*1024/(16+12) = 585개 저장할 수 있습니다. 최종적으로 이 경우는 자식 노드를 585개를 가질 수 있는 B-Tree가 되는 것입니다. 그러면 인덱스 키값이 커지면 어떤 현상이 발생할까? 위의 경우에서 키값이 크기가 두배인 32바이트로 늘어났다고 가정하면 한 페이지에 인덱스 키를 16*1024/(32+12) = 372개 저장할 수 있습니다. 만약 SELECT 쿼리가 레코드 500개를 읽어야 한다면 전자는 인덱스 페이지 한 번으로도 해결될 수도 있지만, 후자는 최소한 2번 이상 디스크로부터 읽어야 합니다. 결국 인덱스를 구성하는 키값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 느려진다는 것을 의미합니다. 

또한, 인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미합니다. 하지만 인덱스를 캐시해 두는 InnoDB의 버퍼 풀이나 MyISAM의 키 캐시 영역은 크기가 제한적이기 때문에 하나의 레코드를 위한 인덱스 크기가 커지면 커질수록 메모리(Buffer pool이나 key cache)에 캐시해 둘 수 있는 레코드 수는 줄어드는 것을 의미합니다. 자연히 메모리의 효율이 떨어지게 되는 결과를 가져옵니다.

B-Tree 깊이

B-Tree 인덱스의 깊이(Depth)는 상당히 중요하지만 직접적으로 제어할 방법이 없습니다. 여기서는 인덱스 키값의 평균 크기가 늘어나면 어떤 현상이 추가로 더 발생하는지 알아보겠습니다. 인덱스의 B-Tree의 깊이가 3인 경우 최대 몇 개의 키 값을 가질 수 있는지 한번 비교해보자. 키값이 16바이트인 경우에는 최대 2억(585*585*585)개 정도의 키값을 담을 수 있지만 키값이 32바이트로 늘어나면 5천만(372*372*372)개로 줄어듭니다. B-Tree의 깊이는 MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제입니다. 결론적으로 인덱스 키값의 크기가 커지면 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키값의 개수가 작아지고, 그 때문에 같은 레코드 건수라 하더라도 B-Tree의 깊이(Depth)가 깊어져서 디스크 읽기가 더 많이 필요하게 된다는 것을 의미합니다.

여기서 언급한 내용은 사실 인덱스 키값의 크기는 가능하면 작게 만드는 것이 좋다는 것을 강조하기 위함이고, 실제로는 아무리 대용량의 데이터베이스라도 B-Tree의 깊이(Depth)가 4~5 이상까지 깊어지는 경우는 거의 발생하지 않습니다.

선택도(기수성)

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

선택도가 좋지 않다고 하더라도 정렬이나 그룹핑과 같은 작업을 위해 인덱스를 만드는 것이 훨씬 나은 경우도 많습니다. 인덱스가 항상 검색에만 사용되는 것은 아니므로 여러 가지 용도를 고려해 적절히 인덱스를 설계할 필요가 있습니다.

tb_test 테이블의 전체 레코드 건수는 1만 건이며, country 컬럼으로만 인덱스가 생성된 상태에서 아래 두 케이스를 살펴보자.

- 케이스 A: country 컬럼의 유니크한 값의 개수가 10개

- 케이스 B: country 컬럼의 유니크한 값의 개수가 1,000개

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

MySQL에서는 인덱스의 통계 정보(유니크한 값의 개수)가 관리되기 때문에 city 컬럼의 기수성은 작업범위에 아무런 영향을 미치지 못합니다. 위의 쿼리를 실행하면 A 케이스의 경우에는 평균 1,000건, B 케이스의 경우에는 평균적으로 10건이 조회될 수 있다는 것을 인덱스의 통계 정보(유니크한 값의 개수)로 예측할 수 있습니다. 만약 A 케이스와 B 케이스 모두 실제 모든 조건을 만족하는 레코드는 단 1건만 있었다면 A 케이스의 인덱스는 적합하지 않은 것이라고 볼 수 있습니다. A 케이스는 1건의 레코드를 위해 쓸모없는 999건의 레코드를 더 읽은 것이지만, B 케이스는 9건만 더 읽은 것입니다. 그래서 A 케이스의 경우 country 컬럼에 생성된 인덱스는 비효율적입니다. 물론 필요한 만큼의 레코드만 정확하게 읽을 수 있다면 최상이겠지만, 현실적으로 모든 조건을 만족하도록 인덱스를 생성한다는 것은 불가능하므로 이 정도의 낭비는 무시할 수 없습니다.

각 국가의 도시를 저장하는 tb_city라는 테이블을 예로 들어보면, tb_city 테이블은 1만 건의 레코드를 가지고 있는데, country 컬럼에만 인덱스가 준비돼 있습니다. tb_city 테이블에는 국가와 도시가 중복해서 저장돼 있지 않다고 가정해 보겠습니다.

CREATE TALE tb_city(
    country VARCHAR(10),
    city VARCHAR(10),
    INDEX ix_country (country)
);

tb_city 테이블에 아래와 같은 쿼리를 한번 실행해 보겠습니다. tb_city 테이블의 데이터 특성을 두 가지로 나눠서 내부적인 쿼리나 인덱스의 효율성을 따져보면 다음과 같습니다.

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

country 컬럼의 유니크 값이 10개일 때

country 컬럼의 유니크 값이 10개이므로 tb_city 테이블에는 10개 국가(country)의 도시(city) 정보가 저장돼 있는 것입니다. MySQL 서버는 인덱스된 컬럼(country)에 대해서는 전체 레코드가 몇 건이며, 유니크한 값의 개수 등에 대한 통계 정보를 가지고 있씁니다. 여기서 전체 레코드 건수를 유니크한 값의 개수로 나눠보면 하나의 키 값으로 검색했을 때 대략 몇 건의 레코드가 일치할지 예측할 수 있게 됩니다. 즉 이 케이스의 tb_city 테이블에서는 "country='KOREA'"라는 조건으로 인덱스를 검색하면 1000건(10,000/10)이 일치하리라는 것을 예상할 수 있습니다. 그런데 인덱스를 통해 검색된 1000건 가운데 city="SEOUL"인 레코드는 1건이므로 999건은 불필요하게 읽은 것으로 볼 수 있습니다.

country 컬럼의 유니크 값이 1000개일 때

country 컬럼의 유니크 값이 1000개이므로 tb_city 테이블에는 1000개 국가(country)의 도시(city) 정보가 저장돼 있는 것입니다. 이 케이스에서도 전체 레코드 건수를 국가 컬럼의 유니크 값 개수로 나눠 보면 대략 한 국가당 대략 10개 정도의 도시 정보가 저장돼 있으리라는 것을 예측할 수 있습니다. 그래서 이 케이스에서는 tb_city 테이블에서 "country='KOREA'"라는 조건으로 인덱스를 검색하면 10건(10,000/1,000)이 일치할 것이며, 그 10건 중에서 city='SEOUL'인 레코드는 1건이므로 9건만 불필요하게 읽은 것이 됩니다.

위 두 케이스의 테이블에서 똑같은 쿼리를 실행해 똑같은 결과를 받았지만 사실 두 쿼리가 처리되기 위해 MySQL 서버가 수행한 작업 내용은 매우 크다는 것을 알 수 있씁니다. 이처럼 인덱스에서 유니크한 값의 개수는 인덱스나 쿼리의 효율성에 큰 영향을 미치게 됩니다.

읽어야 하는 레코드의 건수

인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업입니다. 테이블에 레코드가 100만 건이 저장돼 있는데, 그중에서 50만건을 읽어야 하는 쿼리가 있다고 가정해보겠습니다. 이 작업은 전체 테이블을 모두 읽어서 필요 없는 50만 건을 버리는 것이 효율적일지, 인덱스를 통해 필요한 50만 건만 읽어 오는 것이 효율적일지를 판단해야 합니다. 인덱스를 이용한 읽기의 손익 분기점이 얼마인지 판단할 필요가 있는데, 일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도 더 비용이 많이 드는 작업인 것으로 예측합니다. 즉, 인덱스를 통해 읽어야 할 레코드의 건수(물론 옵티마이저가 판단한 예상 건수)가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 직접 테이블을 모두 읽어서 필요한 레코드만 가려내는(필터링) 방식으로 처리하는 것이 효율적입니다.

전체 100만 건의 레코드 가운데 50만 건을 읽어야 하는 작업은 인덱스의 손익 분기점인 20~25%보다 훨씬 크기 때문에 MySQL 옵티마이저는 인덱스를 이용하지 않고 직접 테이블을 처음부터 끝까지 읽어서 처리할 것입니다. 이렇게 많은 레코드(전체 레코드의 20~25% 이상)을 읽을 때는 강제로 인덱스를 사용하도록 힌트를 추가해도 성능상 얻을 수 있는 이점이 없습니다. 물론 이러한 작업은 MySQL의 옵티마이저가 기본적으로 힌트를 무시하고 테이블을 직접 읽는 방식으로 처리하겠지만 기본적으로는 알고 있어야 할 사항입니다.

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

어떤 경우에 인덱스를 사용하도록 유도할지, 또는 사용하지 못하게 할지 판단하려면 MySQL(더 정확히는 각 스토리지 엔진)이 어떻게 인덱스를 이용(경유)해서 실제 레코드를 읽어 내는지 알고 있어야 할 것입니다.  MySQL이 인덱스를 이용하는 대표적인 방법 3가지는 아래와 같습니다

인덱스 레인지 스캔

인덱스 레인지 스캔은 인덱스의 접근 방법 가운데 가장 대표적인 접근 방식으로, 다음에 설명할 나머지 2가지 접근 방식보다는 빠른 방법입니다. 인덱스를 통해 레코드를 한 건만 읽는 경우와 한 건 이상을 읽는 경우를 각각 다른 이름으로 구분하지만, 여기에서는 "인덱스 레인지 스캔"이라고 표현합니다. B-Tree의 필요한 영역을 스캔하는 데 어떤 작업이 필요한지만 이해할 수 있으면 충분합니다.

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

인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식입니다. 검색하려는 값의 수나 검색 결과 레코드 건수와 관계없이 레인지 스캔이라고 표현합니다. 루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 찾아 들어가야만 비로소 실제로 원하는 시작 지점을 찾을 수 있습니다. 일단 시작해야 할 위치를 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 됩니다. 이처럼 차례대로 쭉 읽는 것을 스캔이라고 표현합니다. 만약 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔합니다. 그리고 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝냅니다. 

B-Tree 인덱스의 리프 노드를 스캔하면서 실제 데이터 파일의 레코드를 읽어 와야 하는 경우도 많습니다. B-Tree 인덱스에서 루트와 브랜치 노드를 이용해 특정 검색(스캔) 시작 값을 가지고 있는 리프 노드를 검색하고, 그 지점부터 필요한 방향(오름차순 또는 내림차순)으로 인덱스를 읽어 나가는 과정을 확인할 수 있습니다. 가장 중요한 것은 어떤 방식으로 스캔하든 관계없이, 해당 인덱스를 구성하는 컬럼의 정순 또는 역순으로 정렬된 상태로 레코드를 가져온다는 것입니다. 이는 별도의 정렬 과정이 수반되는 것이 아니라 인덱스 자체의 정렬 특성 때문에 자동으로 그렇게 됩니다.

인덱스의 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다는 것입니다. 이때 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 레코드 한건 한건 단위로 랜덤 I/O가 한번씩 실행됩니다. 만약 3건의 레코드가 검색 조건에 일치했다고 가정하면 데이터 레코드를 읽기 위해 랜덤 I/O가 최대 3번이 필요하게 됩니다. 그래서 인덱스를 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 작업으로 분류되는 것입니다. 그리고 인덱스를 통해 읽어야 할 데이터 레코드가 20~25%를 넘으면 인덱스를 통한 읽기보다 테이블의 데이터를 직접 읽는 것이 더 효율적인 처리 방식이 되는 것입니다.

인덱스 풀 스캔

인덱스 레인지 스캔과 마찬가지로 인덱스를 사용하지만 인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 일근 방식을 인덱스 풀스캔이라고 합니다. 대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫번째 컬럼이 아닌 경우 인덱스 풀스캔방식이 사용됩니다. 예를 들어 인덱스는 (A, B, C) 컬럼의 순서대로 만들어져 있지만 쿼리의 조건절은 B 컬럼이나 C 컬럼으로 검색하는 경우입니다.

일반적으로 인덱스의 크기는 테이블의 크기보다 작으므로 직접 테이블을 처음부터 끝까지 읽는 것보다는 인덱스만 읽는 것이 효율적입니다. 쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용됩니다. 인덱스뿐만이 아니라 데이터 레코드까지 모두 읽어야 한다면 절대 이 방식으로 처리되지 않습니다.

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

인덱스 풀 스캔 방식은 인덱스를 이용하는 것이지만 효율적인 방식은 아니며, 일반적으로 인덱스를 생성하는 목적이 아니기 때문입니다. 또한 역으로 테이블 전체를 읽거나 인덱스 풀 스캔 방식으로 인덱스를 사용하는 경우는 "인덱스를 사용하지 못한다" 또는 "인덱스를 효율적으로 사용하지 못한다"라는 표현하기도 합니다.

루스 인덱스 스캔

많은 사용자에게 루스(Loose) 인덱스 스캔이라는 단어는 상당히 생소할 것입니다. 오라클과 같은 DBMS의 "인데스 스킵 스캔"이라고 하는 기능과 작동 방식은 비슷하지만 MySQL에서는 이를 "루스 인덱스 스캔"이라고 합니다. 하지만 MySQL의 루스 인덱스 스캔 기능은 아직은 제한적입니다. 위에서 소개한 두가지 접근 방법("인덱스 레인지 스캔"과 "인덱스 풀 스캔")은 "루스 인덱스 스캔"과는 상반된 의미에서 "타이트(Tight) 인덱스 스캔"으로도 분류합니다. 루스 인덱스 스캔이란 말 그대로 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미합니다.

루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하게 동작하지만, 중간마다 필요치 않은 인덱스 키값을 무시(SKIP)하고 다음으로 넘어가는 형태로 처리합니다. 일반적으로 GROUP BY 또는 집합 함수 가운데 MAX() 또는 MIN() 함수에 대해 최적화를 하는 경우에 사용됩니다.

다음은 루스 인덱스 스캔이 실행되는 예제입니다. 해당 쿼리에서 사용된 dept_emp 테이블은 dept_no와 emp_no 두 개의 컬럼으로 인덱스가 생성돼 있습니다. 또한 이 인덱스는 dept_no + emp_no의 값으로 정렬까지 돼 있어서 dept_no 그룹별로 제일 첫번째 레코드의 emp_no값만 읽으면 되는 것입니다. 즉 인덱스에서  WHERE 조건을 만족하는 범위 전체를 다 스캔할 필요가 없다는 것을 옵티마이저는 알고 있기 때문에 조건에 만족하지 않는 레코드는 무시하고 다음 레코드로 이동합니다. 인덱스 리프 노드를 스캔하면서 불필요한 부분은 그냥 무시하고 필요한 부분만 읽었음을 알 수 있습니다. 루스 인덱스 스캔을 사용하려면 여러 가지 조건을 만족해야 하는데, 이는 실행계획에서 상세히 살펴볼 부분입니다.

다중 컬럼(Multi-column) 인덱스

---

실제 서비스용 데이터베이스에서는 2개 이상의 컬럼을 포함하는 인덱스가 더 많이 사용되곤 합니다. 두 개 이상의 컬럼으로 구성된 인덱스를 다중 컬럼 인덱스라고 하며, 또한 2개 이상의 컬럼이 연결됐다고 해서 "Concatenated Index"라고도 합니다.

만약 데이터 레코드 건수가 적은 경우에는 브랜치 노드가 없는 경우도 있을 수 있습니다. 하지만 루트 노드와 리프 노드는 항상 존재합니다. 위 그림에서 중요한 것은 인덱스의 두 번째 컬럼은 첫 번째 컬럼에 의존해서 정렬돼 있다는 것입니다. 즉, 두 번째 컬럼의 정렬은 첫 번째 컬럼이 똑같은 레코드에서만 의미가 있다는 것입니다.

만약 컬럼이 4개인 인덱스를 생성한다면 세 번째 컬럼은 두 번째 컬럼에 의존해서 정렬되고 네 번째 컬럼은 다시 세 번째 컬럼에 의존해서 정렬될 것입니다. 만약 SUBSIDIRARY_ID 값의 정렬 순서가 빠르다 하더라도 EMPLOYEE_ID 컬럼의 정렬 순서가 늦다면 인덱스의 뒤쪽에 위치하게 됩니다. 다중 컬럼 인덱스에서는 인덱스 내에서 각 컬럼의 위치(순서)가 상당히 중요하며 또한 아주 신중히 결정해야 하는 이유가 바로 여기에 있습니다.

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

---

인덱스 키값은 항상 오름차순으로만 정렬되지만 사실 그 인덱스를 거꾸로 끝에서부터 읽으면 내림차순으로 정렬된 인덱스로도 사용될 수 있습니다. 인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 실시간으로 만들어 내는 실행 계획에 따라 결정됩니다.

인덱스의 정렬

일반적인 상용 DBMS에서는 인덱스를 생성하는 시점에 인덱스를 구성하는 각 컬럼의 정렬을 오름차순 또는 내림차순으로 설정할 수 있습니다. 안타깝게도 MySQL은 다음 예제와 같이 인덱스를 구성하는 컬럼 단위 정렬 방식(ASC와 DESC)을 혼합해서 생성하는 기능을 아직 지원하고 있지 않습니다.

CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC);

MySQL에서 위와 같은 명령으로 인덱스를 생성하면 아무 문제없이 인덱스 생성은 가능하지만, 실제로는 ASC나 DESC 키워드를 무시하고 모든 컬럼이 오름차순으로만 정렬됩니다. MySQL에서 ASC 또는 DESC 키워드는 앞으로 만들어질 버전에 대한 호환성을 위해 문법상으로만 제공하는 것입니다. 인덱스의 모든 컬럼을 오름차순(ASC)으로만 또는 내림차순(DESC)으로만 생성하는 것은 (인덱스를 앞으로 읽을지 뒤로 읽을지에 따라 해결되기 때문에) 아무런 문제가 되지 않습니다. 하지만 가끔 인덱스를 구성하는 컬럼 가운데 오름차순(ASC)과 내림차순(DESC)을 혼합해서 만들어야 할 때가 있습니다. MySQL에서는 컬럼의 값을 역으로 변환해서 구현하는 것이 유일한 방법입니다.

CREATE TABLE ranking (
    team_name VARCHAR(20),
    user_name VARCHAR(20),
    user_score INT,
    ...
    INDEX ix_teamname_userscore(team_name, user_score)
);

ranking 테이블에서 team_name 컬럼은 오름차순(ASC)으로 정렬하고 user_score는 높은 점수 순서(내림차순)대로 정렬해서 사용자를 조회하려면 어떻게 해야 할까요?

SELECT team_name, user_name
FROM ranking
ORDER BY team_name ASC, user_score DESC;

위와 같이 쿼리를 사용하면 원하는 결과를 조회할 수 있습니다. 하지만 이 쿼리는 실행의 최종 단계에서 레코드를 정렬하는 과정이 필요하므로 절대로 빠르게 처리할 수 없습니다. 그래서 이럴 때는 user_score의 값을 역으로 변환해서 저장하는 것이 현재로서는 유일한 방법입니다. 즉 user_score 값을 그대로 음수로 만들어서 저장하는 것입니다. 그러면 다음과 같이 ORDER BY의 정렬 조건을 모두 오름차순(ASC)으로 사용할 수 있게 되므로 별도의 정렬 작업 없이 인덱스를 읽기만 해도 정렬되어 출력되는 것입니다.

SELECT team_name, user_name
FROM ranking ORDER BY team_name, user_score;

참고로 ORDER BY의 컬럼에 별도로 ASC나 DESC가 명시되지 않으면 기본적으로 "ASC"가 생략된 것으로 판단하고 오름차순으로 정렬합니다.

인덱스 스캔 방향

first_name 컬럼에 인덱스가 포함된 employees 테이블에 대해 다음 쿼리를 실행하는 과정을 한번 살펴보면, MySQL은 아래 쿼리를 실행하기 위해 인덱스를 처음부터 오름차순으로 끝까지 읽어 first_name이 가장 큰(오름차순으로 읽었을 때 가장 마지막 레코드) 값 하나를 가져오는 것일까요?

SELECT *
FROM employees ORDER BY first_name DESC LIMIT 1;

아닙니다. 인덱스는 항상 오름차순으로만 정렬돼 있지만 인덱스를 최소값부터 읽으면 오름차순으로 값을 가져올 수 있고, 최댓값부터 거꾸로 읽으면 내림차순으로 값을 가져올 수 있다는 것을 MySQL 옵티마이저느 이미 알고 있습니다.

즉, 인덱스를 역순으로 정렬되게 할 수는 없지만 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬 효과를 얻을 수 있습니다. 인덱스를 오름차순으로 읽으면 최종적으로 출력되는 결과 레코드는 자동으로 오름차순으로 정렬된 결과이며, 내림차순으로 읽으면 그 결과는 내림차순으로 정렬된 상태가 되는 것입니다.

쿼리의 ORDER BY 처리나 MIN() 또는 MAX() 함수 등의 최적화가 필요한 경우, MySQL 옵티마이저는 인덱스의 읽기 방향을 전환해서 사용하도록 실행 계획을 만들어냅니다.

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의 인덱스가 지정된 employees 테이블에 대해 다음과 같은 쿼리가 어떻게 실행되는지 한번 살펴 보겠습니다.

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

이 쿼리는 인덱스 레인지 스캔 방식으로 인덱스를 이용할 수는 없습니다. 그 이유는 first_name 컬럼에 저장된 값의 왼쪽부터 한글자씩 비교해 가면서 일치하는 레코드를 찾아야 하는데, 조건절에서 주어진 상수값("%mer")에는 왼쪽 부분이 고정되지 않았기 때문입니다. 따라서 정렬 우선순위가 낮은 뒷부분의 값으로는 왼쪽 기준(Left-most) 정렬 기반의 인덱스인 B-tree에서는 인덱스의 효과를 얻을 수 없습니다.

케이스 B의 인덱스가 지정된 dept_emp 테이블에 대해 다음 쿼리가 어떻게 실행되는지 살펴 보겠습니다.

SELECT * FROM dept_emp WHERE emp_no<=10144;

인덱스가 (dept_no, emp_no) 컬럼 순서대로 생성돼 있다면 인덱스의 선행 컬럼인 dept_no 값 없이 emp_no 값으로만 검색하면 인덱스를 효율적으로 사용할 수 없습니다. 케이스 B의 인덱스는 다중 컬럼으로 인덱스가 만들어졌기 때문에 dept_no에 대해 먼저 정렬한 후, 다시 emp_no 컬럼값으로 정렬돼있기 때문입니다. 여기서는 간단히 WHERE 조건절에 대한 내용만 언급했지만 인덱스의 왼쪽 값 기준 규칙은 GROUP BY 절이나 ORDER BY 절에도 똑같이 적용됩니다. GROUP BY나 ORDER BY에 대해서는 나중에 다시 자세히 살펴보겠습니다.

가용성과 효율성 판단

기본적으로 B-Tree 인덱스의 특성상 다음 조건에서는 사용할 수 없습니다. 여기서 사용할 수 없다는 것은 작업 범위 결정 조건으로 사용할 수 없다는 것을 의미하며, 경우에 따라서는 체크 조건으로 인덱스를 사용할 수는 있습니다.

NOT-EQUAL로 비교된 경우 ("<>", "NOT IN", "NOT BETWEEN", "IS NOT NULL")

... WHERE column <> 'N'

... WHERE column NOT IN (10, 11, 12)

... WHERE column IS NOT NULL

LIKE '%??' (앞부분이 아닌 뒷부분 일치) 형태로 문자열 패턴이 비교된 경우

... WHERE column LIKE '%승환'

... WHERE column LIKE '_승환'

... WHERE column LIKE '%승%'

스토어드 함수나 다른 연산자로 인덱스 컬럼이 변형된 후 비교된 경우

... WHERE SUBSTRING(column, , 1) = 'X'

... WHERE DAYOFMONTH(column) = 1

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

... WHERE column = deterministic_function()

데이터 타입이 서로 다른 비교(인덱스 컬럼의 타입을 변환해야 비교가 가능한 경우)

... WHERE char_column = 10

문자열 데이터 타입의 콜레이션이 다른 경우

... WHERE utf8_bin_char_column = euckr_bin_char_column

다른 일반적은 DBMS에서는 NULL 값은 인덱스에 저장되지 않지만 MySQL에서는 NULL 값도 인덱스로 관리됩니다. 다음과 같은 WHERE 조건도 작업 범위 결정 조건으로 인덱스를 사용하게 됩니다.

... WHERE column IS NULL ...

다중 컬럼으로 만들어진 인덱스는 어떤 조건에서 사용될 수 있고, 어떤 경우에는 절대 사용될 수 없는지 살펴보겠습니다. 다음과 같은 인덱스가 있다고 가정해 보겠습니다.

INDEX ix_test ( column_1, column_2, column_3, ..., column_n )

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

column_1 컬럼에 대한 조건이 없는 경우

column_1 컬럼의 비교 조건이 위의 인덱스 사용 불가 조건 중 하나인 경우

작업 범위 결정 조건으로 인덱스를 사용하는 경우(i는 2보다 크고 n보다 작은 임의의 값을 의미)

column_1 ~ column_(i-1) 컬럼까지 Equal 형태("=" 또는 "IN")로 비교

column_i 컬럼에 대해 다음 연산자 중 하나로 비교

Equal("=" 또는 "IN")

크다 작다 형태(">" 또는 "<")

LIKE로 좌측 일치 패턴(LIKE '승환%')

위의 2가지 조건을 모두 만족하는 쿼리는 column_1부터 column_i까지는 범위 결정 조건으로 사용되고, column_i부터 column_n까지의 조건은 체크 조건으로 사용됩니다. 인덱스를 사용하는 경우와 그렇지 않은 상황에 해당하는 쿼리의 조건 몇 가지를 예제로 살펴보면 다음과 같습니다.

-- // 다음 쿼리는 인덱스를 사용할 수 없음
... WHERE column_1 <> 2

-- // 다음 쿼리는 column_1과 column_2까지 범위 결정 조건으로 사용됨
... WHERE column_1 = 1 AND column_2 > 10

-- // 다음 쿼리는 column_1, column_2, column_3까지 범위 결정 조검으로 사용됨
... WHERE column_1 IN (1,2) AND column_2 = 2 AND column_3 <= 10

-- // 다음 쿼리는 column_1, column_2, column_3까지 범위 결정 조건으로,
-- // column_4는 체크 조건으로 사용됨
... 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까지 범위 결정 조건으로 사용됨
-- // 좌측 패턴 일치 LIKE 비교는 크다 또는 작다 비교와 동급으로 생각하면 된다.
... 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, column_5 컬럼까지
-- // 모두 범위 결정 조건으로 사용됨
... WHERE column_1 = 1 AND column_2 = 2 AND column_3 = 30
        AND column_4 = '김승환' AND column_5 = '서울'

작업 범위 결정 조건으로 인덱스를 사용하는 쿼리 패턴은 이 밖에도 상당히 많이 존재합니다. 대표적인 것들을 기억해 두면 좀 더 효율적인 쿼리를 쉽게 작성할 수 있을 것입니다. 또한 여기서 설명하는 내용은 모두 B-Tree 인덱스의 특징이므로 MySQL뿐 아니라 대부분의 RDBMS에도 동일하게 적용됩니다.

출처: https://12bme.tistory.com/138?category=682920 [길은 가면, 뒤에 있다.]