[Real MySQL] 인덱스 (1)

8.1 디스크 읽기 방식

Random I/O

• 3개의 페이지를 디스크에 기록 하기 위해 3번의 시스템 콜 요청 → 디스크 헤더 3번 움직임
• 인덱스 레인지 스캔에서 Random I/O 사용
• OLTP (On-Line Transaction Processing) 성격의 웹 서비스에서 자주 사용
• 일반적으로 쿼리를 튜닝한다 함은 Random I/O → Sequential I/O 가 아닌 Random I/O 를 줄이는 것

Sequencial I/O

• 3개의 페이지를 디스크에 기록하기 위해 1번의 시스템 콜 요청 → 디스크 헤더 1번 움직임
• 풀 테이블 스캔에서 Sequential I/O 사용
• 데이터웨어하우스나 통계 작업에서 자주 사용 (많은 레코드를 더 빨리 읽어올 수 있으므로)

8.2 인덱스

데이터가 저장 될 때 마다 정렬이 이뤄진다.

데이터의 저장 (INSERT, UPDATE, DELETE) 성능을 희생하고 테이터의 읽기 속도 (SELECT)를 높이는 기능이다.

인덱스 종류

• Primary Index
  레코드를 대표하는 칼럼의 값으로 만들어진 인덱스
• Secondary Index
  Primary Index를 제외한 나머지 인덱스

인덱스 알고리즘

• B-Tree
• Hash

8.3 B-Tree 인덱스

가장 범용적으로 사용되는 알고리즘이다.

8.3.1 구조 및 특성

루트노드, 브랜치 노드, 리프노드로 이뤄져있다.

INSERT 수행시 레코드는 삭제된 공간이 있다면 삭제된 공간에 저장된다. 아니라면 순차적으로 저장된다.

InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되므로 프라이머리 키 순서로 정렬되어 저장된다.

InnoDB 테이블에서는 프라이머리 키가 ROWID 역할을 한다. 세컨더리 인덱스를 통해 레코드를 찾아갈 때, 프라이머리 키를 주소처럼 사용한다. 논리적인 주소를 가진다. 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 있는 레코드를 읽게 된다.

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

B-Tree 인덱스를 이용한 검색은

• 100% 일치
• Left-most part 일치
• 부등호 비교 조건

경우에 사용된다.

• 뒷부분 검색
• 인덱스 키 값에 변형이 가해진 후 비교

의 경우에는 사용될 수 없다.

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

1. 인덱스 키 값의 크기
   B-Tree가 가질 수 있는 최대 자식 노드 수는 인덱스 페이지 크기와 키 값의 크기에 따라 결정된다.
   InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라고 한다. 인덱스도 페이지 단위로 관리된다.
   페이지의 크기를 16KB, 인덱스 키가 16 Byte, 자식 노드 수가 12 Byte라고 하자. 하나의 인덱스 페이지에 저장할 수 있는 키의 갯수는 16*1024/(16+12) = 585 개 이다. 이는 곧 최대 자식 노드 수가 된다.
   키의 크기가 커지면, 저장할 수 있는 최대 자식 노드의 수는 작이진다.
   SELECT 쿼리가 한번에 500개를 읽어야 할 때, 최대 자식 노드 수가 500보다 작다면, 예를 들어 372개라면, 디스크로 부터 2번 이상 읽어야 한다. 따라서 최대 자식 노드 수가 작아지면, 키의 크기가 커지면, 느려진다.
2. B-Tree Depth
   키의 크기가 커지면, 같은 데이터를 담기 위해 필요한 depth가 늘어난다. depth는 값을 검색할 때 랜덤하게 디스크를 읽어야 하는 수와 관련이 있다. 따라서 depth가 늘어나면 디스크 읽기 수가 커지고 탐색 시간이 늘어나게 된다.
3. Selectivity (선택도) Cardinality (기수성)
   모든 인덱스 키 값 가운데 유니크한 값의 수이다. 인덱스의 키 값 가운데 중복된 값이 많아질수록 기수성은 낮아지고 선택도가 떨어진다.
   유니크한 값의 수가 작으면, 레코드 한 건을 읽기 위해 불필요하게 많은 레코드를 읽어야 한다.
4. 읽어야 하는 레코드 건수
   인덱스를 통해 레코드를 읽는 것은 인덱스를 거치지 않고 바로 레코드를 읽는 것 보다 높은 비용이 든다. 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면, 인덱스를 이용하지 않고 테이블을 직접 읽어서 필요한 레코드만 가려내는 (필터링) 방식으로 처리하는 것이 효율적이다. (옵티마이저가 알아서 처리한다.)

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

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

인덱스 레인지 스캔

1. 인덱스 탐색 (Index Seek): 인덱스에서 조건을 만족하는 값이 저장도니 위치를 찾는다.
2. 인덱스 스캔 (Index Scan): 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 읽는다.
3. 2번에서 읽어들인 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽는다.

인덱스 풀 스캔

인덱스 레인지 스캔과 마찬가지로 인덱스를 사용하지만, 인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 읽는 방식이다. 인덱스는 (A, B, C) 칼럼의 순서로 만들어져 있지만 쿼리의 조건절이 B 칼럼이나 C 칼럼으로 검색하는 경우에 인덱스 풀 스캔이 사용된다.

쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있는 경우 사용된다. 인덱스의 크기가 테이블의 크기보다 작으므로, 적은 디스크 I/O로 처리가 가능하다.

Loose 인덱스 스캔

앞의 두 방식은, Loose 인덱스 스캔과 상반된 의미에서 Tight 인덱스 스캔으로 분류한다. 인덱스 레인지 스캔과 비슷하게 작동하지만, 중간에 필요하지 않은 인덱스 키 값은 SKIP 하고 넘어가는 형태로 처리된다. GROUP BY 또는 집합 함수 중 MAX(), MIN() 함수에 대해 최적화를 하는 경우에 사용된다.

인덱스 스킵 스캔

(gender, birth_date) 인덱스가 있는 테이블에 다음과 같은 쿼리로 조회를 해보자.

SELECT gender, birth_date
FROM employees
WHERE birth_date >= '1965-02-01';

MySQL 옵티마이저는 gender 칼럼에서 유니크한 값을 조회해, 주어진 쿼리에 gender 칼럼의 조건을 추가해서 쿼리를 실행한다.

SELECT gender, birth_date
FROM employees
WHERE gender = 'M' AND birth_date >= '1965-02-01';

SELECT gender, birth_date
FROM employees
WHERE gender = 'F' AND birth_date >= '1965-02-01';

gender 칼럼을 건너 뛰고 인덱스를 검색이 가능하게 해서 인덱스 스킵 스캔이라 한다.

 

인덱스 스킵 스캔은 MySQL 8.0 버전에서 새로 도입된 기능이어서 아직 다음과 같은 단점이 있다.

• WHERE 조건절에 조건이 없는 인덱스의 선행 칼럼의 유니크한 값의 개수가 적어야 한다.
• 쿼리가 인덱스에 존재하는 칼럼만으로 처리가 가능해야 한다. (커버링 인덱스)

8.3.5 Multi-Column 인덱스

두 개 이상의 칼럼으로 구성된 인덱스를 다중 칼럼 인덱스라고 한다. 두개 이상의 칼럼이 연결됐다고 해서 Concatenated Index라고도 한다.

인덱스의 두 번째 칼럼은 첫 번째 칼럼에 의존해서 정렬되어 있다.

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

인덱스를 생성할 때 설정한 정렬 규칙에 따라 인덱스의 키 값은 오름차순 또는 내림차순으로 정렬되어 저장된다. 인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 실시간으로 만들어내는 실행 계획에 따라 결정된다.

인덱스 정순(Forward) 스캔이 인덱스 역순(Backware) 스캔보다 빠른 이유는 다음과 같다.

• 페이지 락이 정순 스캔에 적합한 구조
• 인덱스 레코드가 단방향으로만 연결된 구조