인덱스는 데이터베이스 쿼리의 성능을 언급하면서 빼놓을 수 없는 부분입니다.
MySQL에서 사용 가능한 인덱스의 종류 및 특성에서 각 특성의 차이는 상당히 중요하며, 물리 수준의 모델링을 할 때도 중요한 요소가 될 것입니다.
다른 RDBMS에서 제공하는 모든 기능을 제공하지는 않지만, MySQL에서는 인덱싱이나 검색 방식에 따라 다른 스토리지 엔진을 선택해야 할 수도 있기 때문에 여전히 인덱스에 대한 기본 지식은 중요하며, 쿼리 튜닝의 기본이 될 것입니다. 또한 인덱스에만 의존적인 용어는 아니지만, 자주 언급되는 "랜덤(Random) I/O"와 "순차(Sequential) I/O"와 같은 디스크 읽기 방식도 알아두는 것이 좋습니다.
디스크 읽기 방식
컴퓨터의 CPU나 메모리와 같은 전기적 특성을 띤 장치의 성능은 짧은 시간 동안 매우 빠른 속도로 발전했지만 디스크와 같은 기계식 장치의 성능은 상당히 제한적으로 발전했습니다. 데이터베이스나 쿼리 튜닝에 어느정도 지식을 갖춘 사용자가 많이 절감하고 있듯이, 데이터베이스의 성능 튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건인 것들이 상당히 많습니다.
I/O : IO란 Input&Output(입출력)의 줄임말입니다. 컴퓨터 및 주변장치에 대하여 데이터를 전송하는 프로그램,
운영 혹은 장치를 일컫는 말입니다.프로세서와 메모리, 확장 슬롯, 마더보드에서 일어나는 데이터 전송도 I/O에 속합니다.
저장매체
디스크의 읽기 방식을 살펴보기 전에 간단히 데이터를 저장할 수 있는 매체(Media)에 대해 살펴보면, 일반적으로 서버에 사용되는 저장 매체는 크게 네 가지로 나뉩니다.
내장 디스크(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, 디스크 드라이브 내부의 데이터 저장용 원판)를 회전시켜서 데이터를 읽고 쓰는 기계적인 방식을 사용합니다. 그리고 이런 디스크 드라이브를 하드 디스크 드라이버라고도 부르기도 합니다. 약어로는 꽤나 익숙한 HDD가 되겠네요.
디스크 드라이브와 솔리드 스테이트 드라이브
컴퓨터에서 CPU나 메모리와 같은 주요 장치는 대부분 전자식 장치지만 디스크 드라이브는 기계식 장치입니다. 그래서 데이터베이스 서버에서는 항상 디스크 장치가 병목 지점이 됩니다. 이러한 기계식 디스크 드라이브를 대체하기 위해 전자식 저장 매체인 SSD(Solid State Drive)가 많이 출시되고 있씁니다. SSD도 기존 디스크 드라이브와 같은 인터페이스(SATA나 SAS)를 지원하므로 내장 디스크나 DAS 또는 SAN에 그대로 사용 가능합니다.
SSD는 기존의 디스크 드라이브에서 데이터 저장용 플래터를 제거하고 대신 플래시 메모리를 장착하고 있습니다. 그래서 디스크 원판을 기계적으로 회전시킬 필요가 없으므로 아주 빨리 데이터를 읽고 쓸 수 있습니다. 플래시 메모리는 전원이 공급되지 않아도 데이터가 삭제되지 않습니다. 그리고 컴퓨터 메모리보다는 느리지만 기계식 디스크 드라이브보다는 훨씬 빠릅니다.
왜 HDD는 SSD느릴수 밖에 없을까?
이는 플래터로 원판을 돌려가며 물리적으로 데이터를 읽는 태생적 한계 때문입니다. 원판의 물리적 거리만큼 시간이 걸릴 수 밖에 없는 HDD의 input방식(데이터의 지점차이가 발생)은 플래시메모리를 써서 물리적제약이 없어 데이터의 지점차이가 없이 똑같이 접근하는 SSD를 이길 수 없습니다.
디스크의 헤더를 움직이지 않고 한번에 많은 데이터를 읽는 순차 I/O에서는 SSD가 디스크 드라이브보다 조금 빠르거나 거의 비슷한 성능을 보이기도 합니다. 하지만 SSD의 장점은 기존의 디스크 드라이브보다 랜덤 I/O가 훨씬 빠르다는 것입니다. 데이터베이스 서버에 순차 I/O 작업은 그다지 비중이 크지 않고 랜덤 I/O를 통해 작은 데이터를 읽고 쓰는 작업이 대부분이므로 SSD의 장점은 DBMS용 스토리지에 최적이라고 볼 수 있습니다.
랜덤I/O와 순차I/O
랜덤 I/O라는 표현은 디스크 드라이브의 플래터(원판)를 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것을 의미하는데, 사실 순차 I/O 또한 이 작업은 같습니다. 그렇다면 랜덤 I/O와 순차 I/O는 어떤 차이가 있을까요?
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의 프라이머리 키값)의 조합이 인덱스 레코드로 구성됩니다.
절대적인 참고: https://12bme.tistory.com/138 [길은 가면, 뒤에 있다.]
값진 포스팅을 보고 스스로 재정리 해 본 글입니다.
