[MySql] 인덱스

B-Tree 인덱스, 인덱스의 필요성

B-Tree 구조
일반적인 이진트리(자식 2개만을 가지) 형태

 

일반적으로 인덱스를 저장하는 방식(또는 알고리즘)에 따라 B-Tree 인덱스, Hash 인덱스, Fractal 인덱스 등으로 나눌 수 있으며, 일반적으로는 B-Tree 구조가 사용된다.

좌우 자식 간의 균형이 맞지 않을 경우에는 매우 비효율적이라, 항상 균형을 맞춘다는 의미에서 균형 트리(Balanced Tree)라고 불린다.

구조자체는 루트노드에서 부터 브랜치 노드 부터 리프노드까지 존재한다.

페이지

페이지란, 디스크와 메모리에 데이터를 쓰고 읽는 최소 작업 단위이다.
일반적인 인덱스를 포함하여 PK와 테이블등은 모두 페이지 단위로 관리된다.

 

따라서 만약 쿼리를 통해 1개의 레코드를 읽고 싶더라도 결국은 하나의 블록을 읽어야 하는 것이다.

 

페이지에 저장되는 개별 데이터의 크기를 최대한 작게 하여, 1개의 페이지에 많은 데이터들을 저장할 수 있도록 하는 것이 상당히 중요함

가장 중요한 부분은 페이지에 저장되는 데이터의 크기가 클 수록 디스크 I/O가 많아지고, 메모리 캐싱할 수 있는 페이징에 수가 줄어듬

 

추가 페이지를 읽는 작업은 디스크 I/O 과정을 거치기에 최대한 1개의 페이지안에 많은양의 데이터를 담는것이 중요하고, 메모리 효율성 문제와도 직결된다.

 

디스크 I/O를 통해 페이지를 읽어오면 버퍼풀이라는 메모리에 캐싱하는데, 캐시 용량은 한계가 있기에 (데이터크기 = 페이지크기) DB 성능 개선 혹은 쿼리 튜닝은 디스크 I/O 자체를 줄이는 것이 핵심인 경우가 많다.

B-Tree Index 구조

B-Tree 인덱스는 인덱스의 가장 기본적인 형태로서 B-Tree 구조를 사용하는 인덱스이다.

 

인덱스는 페이지 단위로 저장되며, 인덱스 키를 바탕으로 항상 정렬된 상태를 유지한다.정렬된 인덱스 키를 따라서 리프 노드에 도달하면 (인덱스 키, PK) 쌍으로 저장되어 있다.

EX) B-Tree Index 구조

 

CREATE TABLE employee (
    emp_no INT NOT NULL AUTO_INCREMENT,
    name VARCHAR(64),
    PRIMARY KEY(emp_no),
    INDEX idx_name (name)
) ENGINE=InnoDB;

 

 

위의 그림에서 그림은 왼쪽의 B-Tree 인덱스 영역과 오른쪽의 프라이커리 키 인덱스(클러스터 인덱스) 영역 또는 테이블 영역으로 나뉘어져, 키값을 기준으로 정렬되어 있다.

 

인덱스는 테이블과 독립적인 저장 공간이므로 인덱스를 통해 데이터를 조회하려면 먼저 PK를 찾아야한다.

 

PK로 레코드를 조회할 때는(인덱스 영역에서 테이블 영역으로 넘어가는 경우) PK가 어느 페이지에 저장되어 있는지 알 수 없으므로 랜덤 I/O가 발생한다. 이후에는 PK를 따라 리프노드에서 실제 레코드를 읽어온다

 

참고로 연속된 데이터를 조회하는 경우에는 순차 I/O가 발생하는데, 랜덤 I/O는 임의의 장소에서 데이터를 가져오지만 순차 I/O는 다음 장소에서 데이터를 가져오므로 훨씬 빠르다.

인덱스의 필요성

인덱스를 통해 데이터를 조회한다면 기본적으로 실행되는 것이 1. 인덱스를 통해 PK를 찾고 2. PK를 통해 레코드를 찾는다

 

그렇기에 인덱스는 무조건적인 장점만 있는것이 아니다. 실제로 옵티마이저는 인덱스를 통해 레코드 1건을 읽는 것이 테이블을 통해 직접 읽는 것 보다 4~5배 정도 비용이 더 많이 드는 것으로 예측한다.

 

하지만 DBMS는 우리가 원하는 레코드가 어디있는지 모르므로, 모든 테이블을 뒤져서 레코드를 찾아야한다. 이는 엄청난 디스크 읽기 작업이 필요하므로 상당히 느리다.

 

하지만, 인덱스를 사용한다면, PK를 찾고(페이지 1) PK를 통해 레코드를 찾으면 디스크 I/O가 상당히 줄어들게된다. 그렇기에 인덱스를 사용하는 주된 목표는 조회속도의 향상이다.

 

반면에 인덱스를 타지 않는 것이 효율적일 수도 있다. 인덱스를 통해 레코드 1건을 읽는 것이 4-5배 정도 비싸기 때문에, 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20-25%를 넘어서면 인덱스를 이용하지 않는 것이 효율적이다.

 

이런 경우 옵티마이저는 인덱스를 이용하지 않고 테이블 전체를 읽어서 처리하게된다.

인덱싱에 영향을 끼칠 수 있는 요소

1. PK의 크기
MySql에는 PK가 레코드의 물리적인 저장 위치를 결정하는 키라는걸 감안해야하기 때문에, 인덱스는 PK에 의존해야 함.

 

PK가 아닌 실제 레코드의 주소를 갖게 할 수도 있지만, 그러면 PK가 변경될 때 레코드의 주소가 변경되고 모든 인덱스에 저장된 레코드 주소를 변경해야 한다.

 

이러한 오버헤드를 피하기 위해 인덱스는 레코드의 주소가 아닌 PK를 저장한다.

따라서 PK 값이 클수록 인덱스에 좋지 않다.

PK가 클수록 한 페이지에 담을 수 있는 인덱스 정보도 줄어들고, 메모리도 비효율적으로 사용되기 때문이다. 또한 트리의 깊이도 지나치게 깊어지면서 되면서 읽어야 하는 페이지가 많아져서 성능에 좋지않다.

 

2. 인덱스의 컬럼 순서
인덱스는 여러 개의 컬럼으로 구성될 수 있는데, 이를 멀티 컬럼 인덱스(Multi-column Index)라고 함.

멀티 컬럼 인덱스에서 가장 중요한 점은 항상 다음 컬럼이 이전 컬럼에 의존하여 정렬된다는 것.

 

즉, 인덱스의 순서에 따라 인덱스를 타고 안타고가 결정된다.

 

3. 카디날리티
카디날리티란 특정 컬럼에 존재하는 데이터의 고유성을 의미한다. 카디날리티가 높을수록 중복도가 낮아지며, 유니크한 값이 많다는 것이다. 항상 그런 것은 아니지만 일반적으로 값이 유니크할수록 검색 대상이 줄어들어서 처리가 빠르다.

 

MySQL은 인덱스의 통계 정보를 관리하는데, 그 중에 유니크한 값의 개수가 있어, 인덱스 별로 평균적으로 몇 건의 레코드가 있는지를 계산하여 이를 쿼리 시에 활용

 

이러한, 사실로 미루어봤을때 고유성이 높을 수록 불필요한 레코드의 조회가 줄어든다.

예시로 1000개의 유니크한 값이 1000개 일경우 1개의 레코드를 위해 999개의 레코드가 추가적으로 읽히게 되기에 일반적으로 인덱스는 유니크할수록 효율적이다.

 

4. 인덱스의 정렬 및 스캔 방향
인덱스는 설정된 정렬 규칙에 따라 정렬되어 저장된다.(생성 시에 정렬 순서 지정 가능)

 

인덱스를 정렬 순서대로만 읽을 수 있는 것은 아니다. 인덱스가 오름차순으로 생성되었어도 내림차순으로 읽는 것이 가능하며, 인덱스를 읽는 방향은 옵티마이저가 실시간으로 만들어내는 실행 계획에 따라 결정된다.

 

이렇듯 인덱스를 순서대로 읽는 것을 인덱스 정순 스캔(Index Forward Scan), 반대 방향으로 읽는 것을 인덱스 역순 스캔(Index Backward Scan)라고 한다.

 

 

인덱스 정순 스캔 vs 역순 스캔

 

여기서 재밌는 점은 역순 스캔은 인덱스 정순 스캔보다 느리다고 한다.

이유는 두가지가 있다.

1. 페이지 잠금이 인덱스 정순 스캔에 적합한 구조임
2. 페이지 내에서 인덱스 레코드가 단방향으로만 연결뒨 구조임

우선 왜 정순스캔이 더 적합한 구조일까?
앞서 말했듯이 기준을 통해 정렬을 시킬 수 있다. 그렇기에 처음부터 순차적으로 읽는 정순 스캔을 하는 것이 더 빠를 수밖에 없다.

 

B-Tree 구조상 리프노드의 왼쪽부터 읽는 것을 정순 스캔 반대를 역순 스캔으로 정정하며, 인덱스 생성시 정한 정렬방향과 일치하는 경우가 정순스캔이다.

 

실제로 인덱스 기준으로 오름차순한 것을 왼쪽부터 읽어들이는 것과 그 반대는 지표적으로 20~25% 정도 차이가 난다.

 

그리고 이 외에도 페이지 잠금 과정에서 데드락을 방지하기 위해 잠금을 획득하는 것이 정순에서만 가능하고, 역순은 복잡한 과정이 필요하다고 한다.구조적으로 인덱스 스캔이 정순에 적합하다.

 

그 구조에 대해서 자세히 살펴보자면
Backward index scan으로 이전 페이지로 넘어가는 과정은 총 세가지의 단계로 이루어진다.

1. 커서의 상태를 저장하고 내부 미니 트랜잭션을 커밋해서 미니 트랜잭션 버퍼를 글로벌 리두 로그 버퍼로 복사
2. 미니 트랜잭션을 재시작
3. 커서의 상태를 다시 복구 (이 과정에서 현재 블록이 이동되는 것을 막기 위해서 pinning을 하고 필요에 따라서 현재 블록과 이전 블록(Backward block)의 잠금을 획득)

 

InnoDB의 B-Tree 리프 페이지는 Double linked list로 연결되어있어 사실 방향은 상관이없으나,InnoDB 스토리지 엔진에서는 페이지 잠금 과정에서 데드락을 방지하기 위해서 B-Tree의 왼쪽에서 오른쪽 순서(Forward)로만 잠금을 획득하도록 하고 있다.

 

그럼 단방향? 이건 무슨소리?
페이지 내에서 인덱스가 단방향으로만 연결되어 있기 때문에 실제 내부는 순차적으로 4~8개 정도씩 묶어서 그룹을 만든다.

그리고 그룹의 대표키를 선정해 리스트로 관리하는데, 이를 페이지 디렉토리(Page Directory)라고 한다

 

페이지 디렉토리는 단방향 연결이기 때문에, 역방향으로 접근이 불가능하다. 그래서 역순 스캔의 경우 일부 단방향 접근이 필요하므로 역순 스캔이 정순 스캔보다 느린 것이다.

역순 정렬은 왜 필요함?

MySQL 8.0 이전 버전을 사용하면서 역순 정렬이 필요한 경우에는, 크게 성능에 대한 고려 없이 지금까지 Ascending index를 생성하고 “ORDER BY index_column DESC” 쿼리로 인덱스를 Backward scan으로 읽는 실행 계획을 사용해왔다.

 

하지만 해당 성능차이는 심하게 나는데 1천2백만건 기준으로 마지막 레코드 1건만 반환한다고 가정해보자.

대략 28%정도 성능차이가 난다고 한다. 정확한 쿼리 실행계획과 시나리오는 카카오블로그에 잘나와있다.

 

그래서 이를 해결하고자 역순 정렬이 지원되기 시작했다.

레코드의 CUD(Create, Update, Delete)

레코드 추가

레코드 추가시 인덱스까지 추가되어야 하며, 항상 정렬된 상태를 유지해야하므로 적절한 위치 탐색 후 저장된다.

 

비용자체는 기본 추가비용을 1로 정산할때, 인덱스 추가비용은 1.5정도로 계산한다. 인덱스가 없다면 작업 비용이 1이고, B-Tree 인덱스가 3개 있다면 작업 비용을 5.5 정도(1+ 1.5*3)로 예측한다. 참고로 이때의 작업 비용은 디스크 I/O 비용이기 때문에 상당히 비싸다.

 

그래서 인덱스 추가 작업을 즉시 처리하지 않고, 메모리에 모아서 한 번에 쓰도록 지연시킬 수도 있다
그러면 디스크 쓰기 횟수를 줄일 수도 있고, 요청 시에 메모리에서 바로 결과를 반환하는 등의 장점이 존재한다.

 

하지만, 유니크 인덱스 같이 사전에 유효성 검사를 거쳐야하는 인덱스들은 즉각 반영되며, 읽기 잠금을 쓰기를 할 때는 쓰기 잠검을 사용하는데 이 과정에서 데드락 빈도수가 높다.

 

레코드를 추가하다가 페이지가 꽉찼다면 추가 디스크 작업이 필요하다.
인덱스의 리프 노드 페이지가 가득 찼다면 리프 노드를 분리해야 하는데, 그러면 상위 노드(루트 또는 브랜치 노드)에 저장된 자식 노드의 값까지 갱신하는 작업이 필요하다.

레코드 삭제

레코드를 삭제하면 인덱스도 삭제돼야 하는데, 이는 인덱스의 리프 노드에 삭제 마킹만 하면 된다. 삭제 마킹 역시 디스크 쓰기 작업이므로 이 작업도 지연 처리될 수 있다.

 

삭제 마킹된 공간은 계속해서 방치시킬 수도 있고, 재활용할 수도 있다.

 

레코드를 삭제하는 작업이 PK나 인덱스가 사용되는 쿼리라면 이를 활용해서 처리되며, 이는 레코드 수정에서도 동일하다.

 

MySQL의 잠금 중 일부(레코드 잠금, 넥스트 키락 또는 갭락)는 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있다.

따라서 UPDATE나 DELETE를 실행 시에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠그며, 심지어 테이블의 모든 레코드를 잠글 수도 있기 때문이다.

레코드 수정

레코드 수정의 수정대상은 크게 PK, 인덱스, 일반 값이 있다.
우선, PK 수정시에는 최소 2번(DELETE, INSERT)의 쓰기 작업이 필요하다.

 

해당 테이블에 인덱스가 있다면 인덱스에도 추가 작업이 필요하므로 상당히 비용이 많이 든다.

 

인덱스가 수정되는 경우에는 테이블 뿐만 아니라 인덱스에 추가 작업이 반드시 필요하므로, 해당 작업도 비용이 많이든다.
따라서 인덱스와 PK는 최대한 변경을 피해야 한다.(인덱싱 설계 시점에서 고려해야할 문제)

읽기 방식에 따른 인덱스의 분류

인덱스 레인지 스캔

인덱스 레인지 스캔은 범위가 결정된 인덱스를 읽는 방식으로, 정해진 범위만 접근하면 되므로 이 방식은 다른 방식들보다 빠르다. 일반적으로 인덱스를 탄다고 하면 인덱스 레인지 스캔으로 데이터를 조회하는 것을 의미한다.

 

Flow

1. 인덱스 탐색) 인덱스의 조건을 만족하는 값이 저장된 위치를 찾는다.
2. (인덱스 스캔) 시작 위치부터 필요한 만큼 인덱스를 순서대로 읽는다.
3. (랜덤 I/O) 읽어들인 인덱스와 PK를 이용해 최종 레코드를 읽어온다.

 

 

만약 쿼리가 인덱스나 PK 외의가 아닌 레코드의 다른 값을 필요로 한다면 테이블로부터 레코드를 조회해와야 하며, 이때는 PK를 이용해 랜덤 I/O를 통해 레코드들을 조회해야 한다.

 

만약 인덱스나 PK만 필요로 한다면 해당 작업은 실행되지 않는데, 이를 커버링 인덱스라고 한다. 커버링 인덱스는 디스크 랜덤 I/O 작업을 줄일 수 있어서 성능이 훨씬 뛰어나다.

 

물론, 이는 Mysql innodb가 클러스터 테이블 구조이기에 가능한 것.(인덱스에 pk가 저장되는 구조)

 

인덱스 풀스캔

처음부터 끝까지 모든 페이지를 순회하며 인덱스를 읽어들이는 방식이다.

주로 pk 또는 인덱스만을 조회 결과로 필요로될때 사용된다.

 

루스 인덱스 스캔

인덱스를 듬성듬성 읽는 방식이며, 일반적으로 GROUP BY나 MIN() 또는 MAX()와 같은 집합 함수를 사용하는 쿼리를 최적화할 때 사용한다. 불필요한 인덱스는 무시하고 넘어간다.

 

인덱스 스킵 스캔

인덱스 스킵 스캔은 MySQL 8.0부터 추가된 기능으로, 인덱스의 뒷 컬럼만으로 검색하는 경우에 옵티마이저가 자동으로 쿼리를 최적화하여 인덱스를 타도록 하는 읽기 방식이다.

 

인덱스 스킵 스캔이 실행되기 위해서는 다음의 조건들을 모두 만족시켜줘야만 한다.

1. 조회되는 컬럼은 인덱스 만으로 처리 가능해야 함(커버링 인덱스)
2. 인덱스의 선행 컬럼은 WHERE 절에 없어야 함
3. 인덱스 선행 컬럼의 카디날리티가 낮아야 함(유니크한 값이 적어야 함)

먼저 조회되는 컬럼이 인덱스 만으로 처리 가능해야 한다. 만약 모든 컬럼을 조회하는 쿼리라면 풀 테이블 스캔을 타게 된다

인덱스 정리

1. 인덱스를 통해 필요한 레코드만 조회하면 효율적일 수 있음
2. 인덱스는 SELECT 외에 UPDATE, DELETE 등에도 사용될 수 있음
3. 인덱스는 값이 변형되는 경우에 사용될 수 없음
4. 인덱스는 정순으로 검색하는 것이 효율적임
5. 인덱스를 무조건적으로 생성하는 것은 좋지 않음

인덱스를 무조건적으로 생성하는 것은 좋지 않다. WHERE 절에 사용되는 속성이라고 전부 인덱스를 생성하면 데이터의 저장 성능은 떨어지고 인덱스는 비대해져 오히려 역효과만 불러올 수 있다.

 

정렬된 상태를 유지하기 위해서는 데이터를 저장할 때 정렬된 위치를 찾고 넣어줘야 한다.
값이 수정된다면 추가적인 작업이 수반되기도 한다.

 

즉, 인덱스는 저장(INSERT, UPDATE, DELETE)의 성능을 희생하고 데이터의 읽기 속도를 높이는 기능이다. 인덱스가 필요한 이유는 쓰기 작업이 조금 느리더라도, 읽기 작업을 빠르게 유지하도록 하기 위함이다.

 

항상 인덱싱을 사용하기 전 실행계획과 조회 비율을 고려하여 사용해야한다.