Index 도사가 되어보자

in woowacourse on Woowacourse, Index, B-tree, Clustering

Let’s be an index master

왜 인덱스가 필요할까?

데이터베이스의 성능 튜닝은 어떻게 디스크 I/O를 줄이냐가 중요하다. 데이터베이스 서버에서 순차 I/O 작업은 그다지 비중이 크지 않고 랜덤 I/O를 통해 작은 데이터를 읽고 쓰는 작업이 대부분이다. 랜덤 I/O와 순차 I/O에는 어떤 차이가 있을까?

순차 I/O는 3개의 페이지를 디스크에 기록하기 위해 1번 시스템 콜을 요청했지만, 랜덤 I/O는 3개의 페이지를 디스크에 기록하기 위해 3번 시스템 콜을 요청했다. 즉, 디스크의 헤드를 각각 1번, 3번 움직였다. 디스크에 데이터를 쓰고 읽는데 걸리는 시간은 디스크 헤더를 움직여서 읽고 쓸 위치로 옮기는 단계에서 결정된다.

위의 그림의 경우 순차 I/O는 랜덤 I/O보다 3배 정도 빠르다. 결국 디스크의 성능은 디스크 헤더의 위치 이동 없이 얼마나 많은 데이터를 한 번에 기록하느냐에 의해 결정된다. 그래서 여러 번 쓰기 또는 읽기를 요청하는 랜덤 I/O 작업이 작업부하가 훨씬 더 크다. 일반적으로 쿼리를 튜닝하는 것은 랜덤 I/O 자체를 줄여주는 것이 목적이다.

인덱스란?

인덱스란 보통 책의 맨 끝에 있는 찾아보기(또는 “색인”)이라 할 수 있다. 찾아보기도 내용이 많아지면 우리가 원하는 검색어를 찾아내는 데 시간이 걸릴 것이다. 그래서 최대한 빠르게 찾아갈 수 있게 정렬이 돼있으며 인덱스도 마찬가지로 칼럼의 값을 주어진 순서로 미리 정렬해서 보관한다. 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 오래 걸리기 때문에 인덱스를 이용해 빠르게 찾아볼 수 있다.

DBMS에서 인덱스는 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능이다. 테이블의 인덱스를 하나 더 추가할지 말지는 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하느냐에 따라 결정해야 한다.

인덱스를 역할별로 구분해 본다면 프라이머리 키와 보조 키(세컨더리 인덱스)로 구분할 수 있다.

  • 프라이머리 키: 그 레코드를 대표하는 칼럼의 값으로 만들어진 인덱스를 의미. 프라이머리 키는 NULL 값을 허용하지 않으며 중복을 허용하지 않는 것이 특징
  • 보조 키(세컨더리 인덱스): 프라이머리 키를 제외한 나머지 모든 인덱스는 세컨더리 인덱스로 분류한다.

데이터 저장 알고리즘은 많은 분류가 있겠지만 대표적으로 B-tree 인덱스와 Hash 인덱스로 구분할 수 있다.

  • B-Tree 인덱스는 가장 일반적으로 사용되는 인덱스 알고리즘으로 칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘이다.
  • Hash 인덱스 알고리즘은 칼럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다. 하지만, 값을 변형해서 인덱싱하므로 일부만 검색하거나 범위를 검색할 때는 사용할 수 없다.

B-Tree 구조

B-Tree의 트리구조는 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식 노드가 붙어 있는 형태이다. 트리 구조의 가장 하위에 있는 노드를 리프 노드라 하고 중간 노드를 브랜치 노드라 한다. 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.

인덱스 키값은 모두 정렬돼 있지만 데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서로 저장돼 있다.

인덱스와 데이터 파일의 관계는 스토리지 엔진에 따라 달라진다. 두 스토리지 엔진(MyISAM, InnoDB)의 가장 큰 차이점은 세컨더리 인덱스를 통해 데이터 파일의 레코드를 찾아가는 방법에 있다. MyISAM 테이블은 세컨더리 인덱스가 물리적인 주소를 가지는 반면 InnoDB 테이블은 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가진다.

그래서 InnoDB 테이블에서 인덱스를 통해 레코드를 읽을 때는 데이터 파일을 바로 찾아가는 게 아니고 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽는다. 즉, InnoDB 스토리지 엔진에서는 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한번 검색한다.

이 작업으로 인해 MyISAM보다 성능이 안 좋아 보일 수 있지만 각각의 스토리지 엔진은 장단점이 있다. 그 내용은 마지막에 살펴보자.

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

인덱스 키 추가

새로운 키값이 B-Tree에 저장될 때 새로운 키값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다. 저장될 키값을 이용해 B-Tree 상의 적절한 위치를 검색 후 리프 노드에 저장한다. 만약 리프 노드가 꽉 차서 더 저장할 수 없을 때는 리프 노드가 분리되어야 하는데 이때 상위 브랜치 노드까지 처리해 줘야 되기 때문에 비용이 많이 든다.

MyISAM이나 MEMORY 스토리지 엔진을 사용하는 테이블에서는 INSERT 문장이 실행되면 즉시 새로운 값을 B Tree 인덱스에 변경한다. 하지만, InnoDB 스토리지 엔진은 필요하면 인덱스 키 추가 작업을 지연시켜 나중에 처리할 수 있다. 하지만, 프라이머리 키나 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 즉시 B-tree에 추가하거나 삭제한다.

인덱스 키 삭제

삭제 같은 경우 그냥 삭제

인덱스 키 변경

변경 같은 경우 단순히 키값만 변경하는 것은 불가능하다. 먼저 키값을 삭제한 후 다시 새로운 키값을 추가하는 형태로 처리된다.

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

  1. 인덱스를 구성하는 칼럼의 크기와 레코드의 건수
  2. 유니크한 인덱스 키값의 개수

인덱스 키값의 크기

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라 하며 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위이다. 인덱스도 결국은 페이지 단위로 관리되며 리프 노드를 구분한 기준이 바로 페이지 단위다. 일반적으로 DBMS의 B-Tree의 자식 노드의 개수는 가변적인 구조로 인덱스 페이지 크기와 키값의 크기에 따라 결정된다.

예를 들어, 인덱스 키가 16바이트이고 자식 노드 주소 영역이 12바이트로 구성된다고 가정하면 하나의 인덱스 페이지(16KB)에 16*1024/(16+12)으로 585개 저장할 수 있다. 인덱스 키값이 32바이트로 커지면 몇 개를 저장할 수 있을까? 16*1024/(32+12) = 372개를 저장할 수 있다. 레코드 500개를 읽어야 하는 select 쿼리가 있다고 하면 전자의 경우는 페이지 한 번으로 해결할 수 있지만, 후자의 경우 최소 2번은 읽어야 된다.

키값의 크기는 B 트리의 깊이와도 연관 있다. 키값의 크기가 커질수록 한 인덱스 페이지에 담을 수 있는 인덱스 키값의 개수가 적어져 깊이가 깊어지고 디스크 읽기가 더 많이 필요하다.

그러므로 키값의 크기는 가능하면 작게 만드는 것이 좋다.

선택도(기수성)

선택도는 모든 인덱스 키값 가운데 유니크한 값의 수를 의미한다. 인덱스 키값 가운데 중복된 값이 많아지면(유니크 값 줄어들면) 기수성은 낮아지고 동시에 선택도 또한 떨어진다. 인덱스는 선택도가 높을수록(유니크가 많아질수록) 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

예를 들어, 다음과 같은 상황이 있을 때

  • 전체 레코드 데이터 건수는 1만 건
  • 케이스 A - country 칼럼의 유니크한 값의 개수가 10개
  • 케이스 B - country 칼럼의 유니크한 값의 개수가 1000개
SELECT *
FROM  tb_test
WHERE country = 'KOREA' AND city = 'SEOUL';

위의 쿼리를 실행하면 A 케이스의 경우 평균 1000건(10000/10), B 케이스의 경우 평균 10(10000/1000) 건이 조회될 수 있다는 것을 예측할 수 있다. A, B 케이스 모두 실제 모든 조건을 만족하는 레코드가 단 1건만 있었다고 하면 A 케이스의 경우 999건의 레코드를 더 읽었고 B 케이스의 경우 9건만 더 읽었기 때문에 A 케이스의 경우(중복도가 많은 경우) 비효율적이라 할 수 있다.

인덱스를 탄다고 무조건 좋을까?

인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업이다. 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 가려내는 방식으로 처리하는 것이 효율적이다.

MySQL이 인덱스를 이용하는 대표적인 방법 세 가지

인덱스 레인지 스캔

검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식으로 루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 들어가면 그때부터 리프 노드의 레코드만 순서대로 읽으면 된다.

  1. 인덱스 탐색 - 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다.
  2. 인덱스 스캔 - 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 쭉 읽는다.
  3. 2번에서 읽어들인 인덱스 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드 읽음
    • 데이터가 인덱스 안에 다 있으면 커버링 인덱스로 3번 과정이 일어나지 않음

인덱스 풀 스캔

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

루스 인덱스 스캔

인덱스 레인지 스캔과 비슷하게 작동하지만 중간에 필요치 않은 인덱스 키값은 무시하고 다음으로 넘어가는 방식이다. GROUP BY 작업을 처리하기 위해 인덱스를 사용하는 경우에만 적용할 수 있다.

인덱스 스킵 스캔

MYSQL 8.0부터 옵티마이저가 앞 칼럼을 뛰어넘어서 뒤 칼럼만으로도 인덱스 검색이 가능하게 해주는 최적화 기능이다. 데이터베이스에서 인덱스의 핵심은 값이 정렬돼 있다는 것이고 이로 인해 인덱스를 구성하는 칼럼의 순서가 매우 중요하다. 예를 들어, 다음과 같은 인덱스를 생성되어 있다.

ALTER table employees ADD INDEX ix_gender_birthdate (gender, birth_date);

위 인덱스를 사용하려면 WHERE 조건절에 gender 칼럼에 대한 비교 조건이 있어야 한다.

-- 인덱스 사용X
SELECT * FROM employees WHERE birth_date >= '1965-02-01';

-- 인덱스 사용O
SELECT * FROM employees WHERE gender='M' AND birth_date >= '1965-02-01';

첫 번째 쿼리의 경우 인덱스를 사용할 수 없어서 인덱스를 새로 생성했어야 했다. 하지만 MYSQL8.0 부터는 인덱스 스킵 스캔으로 처리가 가능하게 되었다.

하지만, 새로 도입된 기능이라 아직 다음과 같은 단점이 있다.

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

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

두 개 이상의 칼럼으로 구성된 인덱스로 실제 서비스에서는 다중 칼럼 인덱스가 더 많이 사용된다. 뒤에 칼럼은 앞의 칼럼에 의존해서 정렬되어 있기 때문에 각 칼럼의 위치가 상당히 중요하다.

클러스터링 인덱스

프라이머리 키값이 비슷한 레코드끼리 묶어서 저장하는 것을 클러스터링 인덱스라 하며 InnoDB 스토리지 엔진에서만 지원한다. 클러스터링 인덱스는 프라이머리 키값에 의해 레코드의 저장 위치가 결정된다. 즉, 키값이 변경된다면 그 레코드의 물리적인 저장 위치가 바뀌어야 한다는 것을 의미하므로 신중히 프라이머리 키를 결정해야 한다. 클러스터링 인덱스로 저장되는 테이블은 프라이머리 키 기반의 검색이 매우 빠르며, 대신 레코드의 저장이나 프라이머리 키의 변경이 상대적으로 느리다.

클러스터링 인덱스 구조를 보면 테이블의 구조 자체는 B-Tree와 비슷하다. 하지만, B-Tree의 리프 노드와는 달리 클러스터링 인덱스의 리프 노드에는 레코드의 모든 칼럼이 같이 저장되어 있다.

프라이머리 키가 없는 InnoDB 테이블은 어떻게 클러스터링 테이블로 구성될까? 프라이머리 키가 없는 경우에는 InnoDB 스토리지 엔진이 다음 우선순위대로 프라이머리 키를 선택한다.

  1. 프라이머리 키가 있으면 기본적으로 프라이머리 키를 클러스터링 키로 선택
  2. NOT NULL 옵션의 유니크 인덱스 중에서 첫 번째 인덱스를 클러스터링 키로 선택
  3. 자동으로 유니크한 값을 가지도록 증가되는 칼럼을 내부적으로 추가한 후, 클러스터링 키로 선택

InnoDB 테이블에서 클러스터링 인덱스는 테이블당 단 하나만 가질 수 있는 엄청난 혜택이므로 가능하다면 프라이머리 키를 명시적으로 생성하자.

세컨더리 인덱스에 미치는 영향

MyISAM이나 MEMORY 테이블 같은 클러스터링 되지 않은 테이블은 INSERT 될 때 처음 저장된 공간에서 절대 이동하지 않는다. 데이터 레코드가 저장된 주소는 내부적인 레코드 아이디(ROWID) 역할을 한다. 프라이머리 키나 세컨더리 인덱스의 각 키는 그 주소를 이용해 실제 데이터 레코드를 찾아온다. 그래서 MyISam 테이블이나 MEMORY 테이블에서는 프라이머리 키와 세컨더리 인덱스는 구조적으로 아무런 차이가 없다.

ROWID: 테이블 각 레코드(행)이 가지고 있는 고유의 주소

그렇다면 InnoDB 테이블에서 세컨더리 인덱스가 실제 레코드가 저장된 주소를 가지고 있다면 어떻게 될까? 클러스터링 키값이 변경될 때마다 데이터 레코드의 주소가 변경되고 그때마다 해당 테이블의 모든 인덱스에 저장된 주솟값을 변경해야 된다.

검색하는 과정에서 MyISAM과 InnoDB와 어떤 차이가 있는지 한번 살펴보자

  • MyISAM: 인덱스를 검색해서 레코드의 주소를 확인한 후, 레코드의 주소를 이용해 최종 레코드를 가져옴
  • InnoDB: 인덱스를 검색해 레코드의 프라이머리 키값을 확인한 후, 프라이머리 키 인덱스를 검색해서 최종 레코드를 가져옴

클러스터링 인덱스의 장점과 단점

마지막으로 MyISAM과 같은 클러스터링 되지 않은 일반 프라이머리 키와 클러스터링 인덱스를 비교했을 때 장단점을 보자.

장점

  • 프라이머리 키(클러스터링 키)로 검색할 때 처리 성능이 매우 빠르다.
  • 테이블의 모든 세컨더리 인덱스가 프라이머리 키를 가지고 있기 때문에 인덱스만으로 처리될 수 있는 경우가 많다(커버링 인덱스)

단점

  • 테이블의 모든 세컨더리 인덱스가 클러스터링 키를 갖기 때문에 클러스터링 키값의 크기가 클 경우 전체적으로 인덱스의 크기가 커진다.
  • 세컨더리 인덱스를 통해 검색할 때 프라이머리 키로 다시 한번 검색해야 하므로 처리 성능이 느리다.
  • INSERT 할 때 프라이머리 키에 의해 레코드의 저장 위치가 결정되기 때문에 처리 성능이 느리다.
  • 프라이머리 키를 변경할 때 레코드를 DELETE 하고 INSERT 하는 작업이 필요하기 때문에 처리 성능이 느리다.

참고: Real MySQL 8.0

*틀린 부분이 있으면 언제든지 말씀해 주시면 공부해서 수정하겠습니다.

© 2022. All rights reserved.

Powered by 애송이