Mysql - 인덱스

랜덤 I/O와 순차 I/O

---

랜덤 IO

• 랜덤 I/O라는 표현은 하드 디스크 드라이브(HDD)의 플래터(원판)를 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것을 의미합니다.
• 순차 I/O는 3개의 페이지를 디스크에 기록하기 위해 1번 시스템 콜을 요청했지만 랜덤 I/O는 3개의 페이지를 디스크에 기록하기 위해 3번 시스템 콜을 요청합니다. 즉 디스크에 기록해야 할 위치를 찾기 위해 순차 I/O는 디스크의 헤드를 1번 움직였고, 랜덤 I/O는 디스크 헤드를 3번 움직였습니다. 디스크에 데이터를 읽고 쓰는데 걸리는 시간은 디스크 헤더를 움직여서 읽고 쓸 위치로 옮기는 단계에서 결정됩니다.
• 즉 쉽게 말하면 디스크의 성능은 디스크 헤더의 위치 이동 없이 얼마나 많은 데이터를 한번에 기록하느냐에 의해 결정됩니다. 
• 랜덤 I/O나 순차 I/O 모두 파일에 쓰기를 실행하면 반드시 동기화 또는 플러시 작업이 필요합니다.
• 인덱스 레인지 스캔은 데이터를 읽기 위해 주로 랜덤 I/O를 사용하며, 풀 데이터 스캔은 순차 I/O를 사용합니다.

인덱스

---

• 컬럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 삼아 인덱스를 만듭니다.
• SortedList는 DBMS의 인덱스와 같은 자료 구조이며, ArrayList는 데이터 파일과 같은 자료구조 입니다.
• DBMS에서의 인덱스는 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 희생하고 그 대신 데이터의 읽기(SELECT) 속도를 높이는 기능입니다.
• 인덱스를 역할별로 구분한다면 프라이머리 키와 세컨더리 키로 구분할 수 있습니다.

💡 프라이머리 키

• 프라이머리 키는 테이블에서 해당 레코드를 식별할 수 있는 기준값이 되기 때문에 우리는 이를 식별자라고 부르며, 프라이머리 키는 NULL 값을 허용하지 않으며 중복을 허용하지 않습니다.

💡 세컨더리 키

• 프라이머리 키를 제외한 나머지 모든 인덱스는 세컨더리 인덱스로 분류합니다. 유니크 인덱스는 프라이머리 키와 성격이 비슷하고 프라이머리 키를 대체해서 사용할 수도 있다고 해서 대체키라고도 합니다.

 

B-Tree 인덱스

---

• B-Tree 인덱스는 컬럼의 값을 변경하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘입니다. 많은 사람들이 B가 바이너리(이진) 트리라고 생각하는 사람들이 많은데 이는 바이너리(이진)의 약자가 아닌 Balanced를 의미합니다.

구조 및 특성

• B-Tree는 트리 구조의 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식 노드가 붙어 있는 형태입니다. 트리 구조의 가장 하위에 있는 노드를 리프 노드라고 하며, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간의 노드를 브랜치 노드라고 합니다. 데이터 베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리하는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있습니다.
• 아래 사진 처럼 인덱스의 키 값은 모두 정렬되어 있지만 데이터 파일의 레코드는 정렬되어 있지 않고 임의의 순서로 저장되어 있습니다. 많은 사람들이 데이터 파일의 레코드는 INSERT된 순서대로 저장되는 것으로 생각하지만 그렇지 않고 레코드를 삭제하거나 변경하지 않고 INSERT만을 수행한다면 그럴 수도 있지만 레코드가 삭제되어 빈 공간이 생기면 그 다음의 INSERT는 가능한 삭제된 공간을 재사용하도록 DBMS가 설계되어 있기 때문에 항상 INSERT된 순서대로 저장되는 것은 아닙니다.
• 대부분의 RDBMS의 데이터 파일에서 레코드는 특정 기준으로 정렬되지 않고 임의의 순서로 저장됩니다. 하지만 InnoDB 테이블에서레코드는 클러스터되어 디스크에 저장되므로 기본적으로 프라이머리 키 순서로 정렬되어 저장됩니다.

인덱스 키 추가

• 새로운 키 값이 B-Tree에 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있습니다. B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색해야 합니다. 저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree 리프 노드에 저장합니다. 리프 노드가 꽉 차서 더는 저장할 수 없는 경우에는 리프 노드가 분리되어야 하는데 이는 상위 브랜치 노드까지 처리의 범위가 넓어집니다.
• MyISAM이나 MEMORY 스토리지 엔진을 사용하는 테이블에서는 INSERT 문장이 실행되면 즉시 새로운 키 값을 B-Tree 인덱스에 반영합니다. 하지만 InnoDB 스토리지 엔진은 이 작업을 조금 더 지능적으로 처리하는데 필요하다면 인덱스 키 추가 작업을 지연시켜 나중에 처리할 수 있습니다. 하지만 프라이머리 키나 유니크 인덱스의 경우에는 중복 체크가 필요하기 때문에 즉시 B-Tree에 추가되거나 삭제합니다.

인덱스 키 삭제

• 삭제는 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아 그냥 삭제 마크만 하면 작업이 완료됩니다. 이렇게 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재활용할 수 있습니다. 인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 이 작업 역시
  디스크 I/O가 필요한 작업입니다. MySQL 5.5버전 이상의 InnoDB 스토리지 엔진에서는 이 작업 또한 버퍼링되어 지연 처리될 수 있습니다. 이때 지연된 인덱스 키를 삭제 또한 사용자에게는 악영향을 끼치지 않고 MySQL 서버가 내부적으로 처리합니다.

인덱스 키 변경

• 인덱스의 키 값은 그 값에 따라 저장될 리프 노드의 위치가 결정되므로 B-Tree의 키 값이 변경되는 경우에는 단순히 인덱스상의 키 값만 변경되는게 아니라 기존 키 값을 삭제한 후 다시 새로운 키 값을 추가하는 형태로 처리됩니다.

인덱스 키 검색

• 인덱스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행하는데 이 과정을 트리 탐색이라고 합니다.
• B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있습니다. 부등호 비교 조건에서는 인덱스를 활용할 수 있지만 인덱스를 구성하는 키 값의 뒷부분만을 검색하는 용도로는 인덱스를 사용할 수 없습니다.
• 인덱스를 이용한 검색에서 중요한 사실은 인덱스의 키 값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree의 빠른 검색 기능을 사용할 수 없습니다. 이미 변형된 값은 B-Tree 인덱스에 존재하는 값이 아닙니다. 따라서 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree의 장점을 이용할 수 없습니다. 

 

 

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

---

인덱스 키 값의 크기

• InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블럭이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 됩니다. 또한 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 합니다.
• 인덱스를 구성하는 키 값의 크기가 커지면 B-Tree는 자식 노드를 쪼깨어 새로운 자식 노드를 만들게 됩니다.이렇게 되면 디스크로 읽어 들어가야하는 깊이가 늘어나게 되고 그만큼 느려지게 됩니다.
• 인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미하며 인덱스를 캐시해 두는 InnoDB의 버퍼 풀이나 MyISAM의 키 캐시 영역은 크기가 제한적이기 때문에 하나의 레코드를 위한 인덱스 크기가 커질수록 메모리에 캐시해 둘 수 있는 레코드 수는 줄어들기 때문에 메모리 효율이 떨어지게 됩니다.

B-Tree의 깊이

• 인덱스 키 값의 크기가 커질수록 하나의 인덱스 페이지에서 담을 수 있는 인덱스 키 값의 개수는 적어지고 그로 인해 노드들이 쪼개어지며 B-Tree의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 됩니다.

선택도(기수성)

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

읽어야 하는 레코드의 수

• 인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 발생합니다.
• 만약 테이블에 레코드가 100만건이라는 가정하에 50만건을 읽어야 한다면 인덱스를 통해 읽을 것인지 인덱스를 거치지 않고 읽을 것인지 정해야합니다. 이때 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도의 비용을 발생시킵니다. 인덱스를 통해 읽어야할 레코드의 수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 통해 읽지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 가져오게 하는것이 효율적입니다.
• 만약 이렇게 많은 레코드를 읽을 때 강제로 인덱스를 사용하도록 힌트를 추가해도 성능상 이점을 얻을 수 없습니다. 물론 이러한 작업은 MySQL의 옵티마이저가 기본적으로 힌트를 무시하고 테이블을 직접 읽는 방식으로 처리하게 됩니다.

 

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

---

인덱스 레인지 스캔

• 인덱스 레인지 스캔은 검색해야할 인덱스의 범위가 결정됐을 때 사용하는 방식입니다. 
• 루트 노드 > 브랜치 노드 > 리프 노드 순으로 검색이 진행되며 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요한데 이때 리프 노드에 저장된 각 레코드의 주소로 데이터 파일의 레코드를 읽어오는데 레코드 한건 단위로 랜덤I/O가 발생하며 만약 10건이라면 10번의 랜덤 I/O가 발생하게 됩니다.

인덱스 풀 스캔

• 인덱스를 사용하지만 인덱스 레인지 스캔과는 달리 인덱스를 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 합니다.
• 대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 인덱스 풀 스캔 방식이 사용됩니다.

루스 인덱스 스캔 (인덱스 스킵 스캔)

• 루스 인덱스 스캔이란 말 그대로 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미합니다.
• 루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하게 작동하지만 중간에 필요치 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리됩니다.
• 루스 인덱스 스캔은 인덱스의 선행 컬럼이 가진 유니크한 값의 개수가 소량일 때 적용해야 최적화하기 좋습니다.

다중 컬럼 인덱스 (복합 키)

• 아래 그림에서 중요한 것은 인덱스의 두 번째 컬럼은 첫 번째 컬럼에 의존해서 정렬되어 있다는 것입니다. 즉 두번째 컬럼의 정렬은 첫 번째 컬럼이 똑같은 레코드에서만 의미가 있다는 것입니다. 만약 컬럼이 4개인 인덱스를 생성한다면 세번째 컬럼은 두번째 컬럼에 의존해서 정렬되고 네번째 컬럼은 세번재 컬럼에 의존해 정렬됩니다.
• 다중 컬럼 인덱스에서는 인덱스 내에서 각 컬럼의 위치(순서)는 상당히 중요하며 아주 신중히 결정해야 합니다.

 

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

---

인덱스를 생성할 때 설정한 정렬 규칙에 따라 인덱스의 키 값은 항상 오름차순이거나 내림차순으로 정렬되어 있습니다.

인덱스의 정렬

• 인덱스 생성 시점에 오름차순 또는 내림차순으로 정렬이 결정되지만 쿼리가 인덱스를 사용하는 시점에 인덱스를 읽는 방향에 따라 오름차순(ASC) 또는 내림차순(DESC) 정렬 효과를 얻을 수 있습니다.

내림차순 인덱스

• 오름차순 인덱스 : 작은 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
• 내림차순 인덱스 : 큰 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
• 인덱스 정순 스캔 : 인덱스 키의 크고 작음에 관계없이 인덱스 리프 노드의 왼쪽 페이지부터 오른쪽으로 스캔
• 인덱스 역순 스캔 : 인덱스 키의 크고 작음에 관계없이 인덱스 리프 노드의 오른쪽 페이지부터 왼쪽으로 스캔

SELECT * FROM MEMBER ORDER BY NUMBER ASC LIMIT 12619775, 1;
1 row in set (4.15 sec)

SELECT * FROM MEMBER ORDER BY NUMBER DESC LIMIT 12619775, 1;
1 row in set (5.35 sec)

• 위의 예제를 보면 DESC를 사용한 결과가 조금 더 느리다는 것을 알 수 있습니다. MySQL 서버의 InnoDB 스토리지 엔진에서 정순 스캔과 역순 스캔은 페이지간의 양방향 연결 고리를 통해 전진이냐 후진이냐의 차리만 있지만 실제 내부적으로는 InnoDB에서 인덱스 역순 스캔이 인덱스 정순 스캔에 비해 느릴 수 밖에 없는 이유가 있습니다.

💡 이유 1

• 페이지 잠금이 인덱스 정순 스캔에 적합한 구조입니다.

💡 이유 2

• 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조입니다.

 

R-Tree 인덱스

---

공간 인덱스는 R-Tree 인덱스 알고리즘을 이용해 2차원의 데이터를 인덱싱하고 검색하는 목적의 인덱스 입니다. B-Tree는 인덱스를 구성하는 컬럼의 값이 1차원의 스칼라 값이라면 R-Tree 인덱스는 2차원 공간 개념 값입니다. 

구조 및 특성

• GEOMETRY 타입은 나머지 3개 타입의 슈퍼 타입입니다.

• 공간 정보의 검색을 위한 R-Tree 알고리즘을 이해하려면 MBR이라는 개념을 알고 있어야 하는데 MBR이란 Minimum Bounding Rectangle의 약자로 해당 도형을 감싸는 최소 크기의 사각형을 의미합니다.

R-Tree 인덱스의 용도

• R-Tree는 앞에서 언급한 MBR의 정보를 이용해 B-Tree 형태로 인덱스를 구축하므로 Rectangle의 R과 B-Tree의 Tree를 섞어서 R-Tree라는 이름이 붙여졌으며, 공간 인덱스라고도 합니다.
• 대표적으로 현재 사용자의 위치로부터 5km 이내의 음식점 검색등과 같은 검색에 사용할 수 있습니다.



함수 기반 인덱스

---

일반적인 인덱스는 컬럼의 값 일부(또는 앞부분) 또는 전체에 대해서만 인덱스 생성이 허용되는데 하지만 때로는 컬럼의 값을 변형해서 만들어진 값에 대해 인덱스를 구축해야 하는 경우도 발생하는데 이러한 경우에는 함수 기반의 인덱스를 사용하면 됩니다.

가상 컬럼을 이용한 인덱스

• 가상 컬럼은 테이블에 새로운 컬럼을 추가하는 것과 같은 효과를 내기 때문에 실제 테이블의 구조가 변경된다는 단점이 있습니다.

mysql > CREATE TANLE user (
	id INT,
    first_name VARCHAR(10),
    liast_name VARCHAR(10),
    PRIMARY KEY (id)
);

# 가상 컬럼 생생 및 인덱스 등록
mysql > ALTER TABLE user
	ADD full_name VARCHAR(30) AS (CONCAT(first_name, ' ', liast_name)) VIRTUAL,
    ADD INDEX ix_fullname (full_name);

 

함수를 이용한 인덱스

• 함수 기반 인덱스를 제대로 활용할려면 반드시 조건절에 함수 기반 인덱스에 명시된 표현식이 그래도 사용되어야 합니다. 함수 생성 시 명시된 표현과 쿼리의 조건절에서 사용된 표현식이 다르다면(설령 결과는 같더라도) MySQL 옵티마이저는 다른 표현식으로 간주해서 함수 기반 인덱스를 사용하지 못합니다.

mysql > CREATE TANLE user (
	id INT,
    first_name VARCHAR(10),
    liast_name VARCHAR(10),
    PRIMARY KEY (id),
    INDEX ix_fullname ((CONCAT(first_name, ' ', liast_name))) 
);

# 함수 기반 인덱스 사용
SELECT * FROM user WHERE CONCAT(first_name, ' ', liast_name) = 'K DG';

 

멀티 밸류 인덱스

---

• 전문 검색 인덱스를 제외한 모든 인덱스는 레코드 1건이 1개의 인덱스 키 값을 가집니다. 즉 인덱스 키와 데이터 레코드는 1:1의 관계를 가집니다. 하지만 멀티 밸류 인덱스는 하나의 데이터 레코드가 여러개의 키 값을 가질 수 있는 형태의 인덱스 입니다.
• json 타입에 주로 사용이 됩니다.

 

클러스터링  인덱스

---

클러스터링이란 여러 개를 하나로 묶는다는 의미로 주로 사용되는데 MySQL 서버에서 클러스터링은 테이블의 레코드를 비슷한 것(프라이머리 키를 기준)들끼리 묶어서 저장하는 형태로 구현되는데 이는 주로 비슷한 값들을 동시에 조회하는 경우가 많다는 점에서 착안한 것입니다. MySQL에서 클러스터링 인덱스는 InnoDB 스토리지 엔진에서만 지원하며, 나머지 스토리지 엔진에서는 지원되지 않습니다.

 

클러스터링 인덱스

• 클러스터링 인덱스는ㄴ 테이블의 프라이머리 키에 대해서만 적용이 되는 내용입니다. 즉 프라이머리 키 값이 비슷한 레코드끼리 묶어서 저장하는 것을 클러스터링 인덱스라고 표현합니다. 여기서 중요한 것은 프라이머리 키 값에 의해 레코드의 저장 위치가 결정된다는 것 입니다. 
• 프라이머리 키 값이 변경된다면 그 레코드의 물리적인 저장 위치가 바뀌어야 한다는 것을 의미하기도 합니다.
• 클러스터링 인덱스는 프라이머리 키 값에 의해 레코드 저장 위치가 결정되므로 사실 인덱스 알고리즘이라기 보다는 레코드의 저장 방식이라고 볼 수 있습니다.

💡 일반적으로 B-Tree 인덱스도 인덱스 키 값으로 정렬이 되는데 어떻게 보면 인덱스 키 값으로 클러스터링된 것으로 생각할 수 있습니다. 하지만 클러스터링 인덱스라고 부르지 않습니다. 테이블의 레코드가 프라이머리 키 값으로 정렬되어 저장된 경우에만 클러스터링 인덱스라고 부릅니다.

 

💡 클러스터링 인덱스 구조를 보면 클러스터링 테이블의 구조 자체가 일반 B-Tree와 비슷하지만 세컨더리 인덱스를 위한 B-Tree의 리프 노드와는 다릅니다. 클러스터링 인덱스의 리프 노드에는 레코드의 모든 컬럼이 같이 저장된 것을 알 수 있습니다. 즉 클러스터링 테이블은 그 자체가 하나의 거대한 인덱스 구조로 관리됩니다.

 

💡 InnoDB 스토리지 엔진이 적절한 클러스터링 키 후보를 찾지 못한다면 내부적으로 레코드의 일련번호 컬럼을 생성하게 되는데 이렇게 자동으로 생성된 프라이머리 키는 사용자에게 노출되지 않으며, 쿼리에 명시적으로 사용할 수 없습니다. 즉 프라이머리 키나 유니크 인덱스가 전혀 없는 InnoDB 테이블에서는 아무 의미 없는 숫자 값으로 클러스터링 되는 것이며 우리에게 아무런 혜택을 주지 않습니다.

 

유니크  인덱스

---

• 유니크 인덱스에서 NULL도 저장될 수 있는데 NULLdms 특정 값이 아니므로 2개 이상 저장될 수 있습니다. MySQL에서 프라이머리 키는 기본적으로 NULL을 허용하지 않는 유니크 속성이 자동으로 부여됩니다.
• 하나의 테이블에서 같은 컬럼에 유니크 인덱스와 일반 인덱스를 중복해서 사용하는 경우가 있는데 이는 MySQL의 유니크 인덱스는 ㅣ일반 다른 인덱스와 같은 역할을 하므로 중복해서 인덱스를 생성할 필요는 없습니다. 
• 새로운 레코드가 INSERT되거나 인덱스 컬럼의 값이 변경되는 경우 인덱스 쓰기 작업이 필요합니다. 그런데 유니크 인덱스의 키 값을 쓸 때는 중복된 값이 없는지 체크하는 과정이 한 단계 더 필요한데 그래서 유니크하지 않은 세컨더리 인덱스의 쓰기보다 느립니다. 
• 또한 InnoDB 스토리지 엔진에는 인덱스 키의 저장을 버퍼링하기 위해 체인지 버퍼가 사용되는데 유니크 인덱스는 반드시 중복 체크를 해야 하기 때문에 작업 자체를 버퍼링할 수 없습니다.

 

 

---

해당 내용은 Real Mysql 8.0 책을 바탕으로 작성되었습니다.