Published on

8장. 인덱스

8장. 인덱스

디스크 읽기 방식

데이터 저장 매체는 컴퓨터에서 가장 느립니다. 그렇기 때문에 DB의 성능 튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건입니다.

하드 디스크 드라이브(HDD)와 솔리드 스테이트 드라이브(SSD)

1초당 처리 비율

  • CPUL 1,000,000,000
  • DRAM: 100,000,000
  • SSD: 100,000
  • HDD: 200

SSD와 HDD의 성능차이는 굉장합니다.

이런 차이가 나는 이유는 SSD는 기존 HDD에서 데이터 저장용 플래터(원판)를 제거하고 그 대신 플래시 메모리를 장착했기 때문에 디스크원판을 기계적으로 회전시킬 필요가 없어 아주 빨리 데이터를 읽을 수 있기 때문입니다.

요즘은 DBMS용으로 사용할 서버에는 대부분 SSD를 채택하고 있습니다.

디스크 헤더를 움직이지 않고 한 번에 많은 데이터를 읽는 순차/IO에서는 SSD가 HDD보다 조금 빠르거나 비슷하지만 랜덤 I/O의 경우 SSD가 훨씬 빠릅니다.

순차 I/O 작업은 그다지 비중이 크지는 않습니다.

랜덤 I/O와 순차 I/O

두 개 다 HDD 디스크 원판을 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것을 의미합니다.

여기서 차이는 3개의 페이지를 디스크에 기록한다고 했을 때, 순차 I/O의 경우 1번만 쓰는 반면 랜덤 I/O의 경우 페이지 별로 쓰기 때문에 3번을 기록하게 됩니다.

이런 경우 순차 I/O가 랜덤 I/O에 비해 3배 빠르다고 볼 수 있습니다.

디스크의 성능은 디스크 헤더의 위치 이동 없이 얼마나많은 데이터를 한 번에 기록하느냐에 의해 결정 됩니다.

디스크 원판을 가지지 않는 SSD 또한 랜덤 I/O는 순차 I/O보다 전체 스루풋이 떨어집니다.

쿼리를 튜닝해서 랜덤 I/O를 순차 I/O로 바꿔서 실행할 방법은 많지 않습니다.

일반적으로 쿼리를 튜닝하는 것은 꼭 필요한 데이터만 읽도록 쿼리를 개선하여 랜덤 I/O 자체를 줄여 주는것이 목적입니다.

인덱스란?

인덱스는 책의 목차와 비슷합니다.

책의 내용이 많아지면 한 번에 찾아가기 쉽도록 목차에 챕터와 페이지를 적어 두고 정렬이 되어 있습니다.

이렇게 목차를 만드는 일은 당연히 책을 작성할 때 조금 더 수고가 들어가게 됩니다. 대신 빠르게 원하는 내용을 볼수가 있죠.

DBMS의 인덱스도 동일합니다.

조금 더 데이터를 빠르게 읽어오기 위해 저장 성능(INSERT, UPDATE, DELETE)을 희생하여 정렬된 상태로 값을 저장해두고 값을 읽어 오도록 설정하는 것입니다.

  • 프라이머리 키 인덱스
    • 프라이머리 키는 그 레코드를 대표하는 컬럼의 값으로 만들어진 인덱스를 의미
    • 이 컬럼은 테이블에서 해당 레코드를 식별할 수 있는 기준값이 되기 때문에 식별자라고도 부름
    • NULL과 중복을 허용하지 않음
  • 세컨더리 인덱스
    • 프라이머리 키를 제외한 모든 인덱스
    • 유니크 인덱스는 프라이머리 키와 성격이 비슷하고 프라이머리 키를 대체해서 사용할 수 있다고 해서 대체 키라도고 함

데이터 저장 방식별로 구분할 경우 대표적으로 B-Tree 인덱스와 Hash 인덱스로 구분할 수 있습니다.

  • B-Tree 인덱스
    • 가장 일반적으로 사용되는 인덱스 알고리즘
    • 컬럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘
    • MySQL에는 위치 기반 검색을 지원하기 위한 R-Tree 인덱스도 존재하지만, 결국 B-Tree의 응용 알고리즘으로 볼 수 있음
  • Hash 인덱스
    • 컬럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘
    • 매우 빠른 검색 지원
    • 값을 변형해서 인덱싱하므로 전방 일치와 같이 값의 일부만 검색하거나 범위를 검색할 때는 Hash 인덱스를 사용할 수 없음
    • 주로 메모리 기반의 DB에서 많이 사용

데이터의 중복 허용 여부로 분류하면 유니크 인덱스와 유니크하지 않은 인덱스로 구분할 수 있습니다.

실제 DBMS의 쿼리를 실행해야 하는 옵티마이저에게는 하나만 존재하는지 아닌지는 상당히 중요한 문제가 됩니다.

유니크 인덱스인 경우 동등 조건(Equals, =)으로 검색한다는 것은 항상 1개의 레코드만 찾으면 더 이상 찾지 않아도 된다는 것을 옵티마이저에게 아려주는 효과를 냅니다.

B-Tree 인덱스

인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘 입니다.

B-Tree의 B는 (Binary)가 아니라 Balanced를 의미합니다.

구조 및 특성

B-Tree는 트리 구조의 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식 노드가 붙어 있는 형태 입니다.

트리 구조의 제일 하단에 있는것을 리프 노드라고 하며 그 중간을 잇는 노드를 브랜치 노드라고 합니다.

  • 루트 노드
    • 브랜치 노드
      • 브랜치 노드
        • 리프 노드
    • 리프 노드

즉 위 처럼 브랜치 노드 하위에 리프 노드가 존재할 수도있고, 루트 노드 하위에 바로 리프 노드가 존재할 수도 있습니다.

인덱스의 키 값을 모두 정렬되어 저장됩니다. 하지만 데이터 파일의 레코드는 정렬되어 있지 않습니다.

순서대로 넣고 변경이나 삭제를 하지 않으면 데이터 파일도 정렬된 상태겠지만, 변경이나 삭제가 있었다면 DBMS는 조금 더 효율적으로 공간을 사용하기 위해 공간을 재활용 합니다.

인덱스는 테이블의 키 컬럼만 가지고 있으므로 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 합니다.

MyISAM의 경우 세컨더리 인덱스가 물리적인 주소를 가지는 반면 InnoDB 테이블은 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가집니다.

그래서 InnoDB는 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한번 검색해야 합니다.

단순하게 생각하면 InnoDB의 성능이 더 떨어질 것처럼 보이지만 각각 장단점이 있습니다.

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

인덱스 키 추가

새로운 키 값이 B-Tree에 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 지연 되어 저장될 수도 있습니다.

B-Tree에 저장될 때는 아래와 같은 과정을 거칩니다.

  • 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색
  • 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노트에 저장
  • 리프 노드가 꽉 찬 경우 리프 노드를 분리

리프 노드를 분리하는 것은 상위 브랜치 노드까지 처리의 범위가 넓어지기 때문에 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 드는 것으로 알려졌습니다.

💡 대략적으로 작업시간 계산하는 방법

레코드를 추가하는 작업 비용을 1이라고 가정하면 해당 테이블의 인덱스에 키를 추가하는 작업 비용을 1.5정도로 예측할수 있습니다.

이때, 인덱스가 하나도 없는 레코드의 경우 작업 비용이 1이고, 인덱스가 3개인 경우 5.5(1.5 * 3 + 1) 정도로 예측합니다.

중요한 것은 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 해서 걸리는 시간이라는 점입니다.

인덱스 키 삭제

해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 마크만 처리합니다.

이렇게 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재활용할 수 있습니다.

인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 이 작업 역시 디스크 I/O가 필요한 작업입니다.

InnoDB에서는 이 작업 또한 ㅈ버퍼링 되어 지연 처리 될 수 있습니다.

인덱스 키 변경

인덱스 키 변경은 기존 인덱스 키 값을 삭제한 후 새로운 인덱스 키 값을 추가하는 작업으로 처리됩니다.

인덱스 키 검색

여태 쓰기(INSERT, UPDATE, DELETE)의 성능을 희생하고 인덱스를 구축한 이유는 빠른 조회를 위해서 입니다.

인덱스를 검색하는 작업은 루트 노드부터 시작해 리프 노트까지 이동하면서 비교 작업을 수행하는데, 이를 트리 탐색이라고 합니다.

  • SELECT 외에도 UPDATE나 DELETE를 처리하기 위해 항상 해당 레코드를 먼저 검색해야 하는 경우에도 사용
  • B-Tree의 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분(Left-most part)만 일치하는 경우에 사용할 수 있음
  • 부등호(<, >)에서도 사용할 수 있지만 인덱스를 구성하는 키 값의 뒷부분만 검색하는 경우에는 사용할 수 없음
  • 함수나 연산을 수행하는 등 인덱스의 키 값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree의 빠른 검색을 사용할 수 없음

InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키락(갭락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠근는 방식으로 구현되어 있기 때문에 인덱스가 없으면 불필요하게 많은 레코드를 잠그며, 심지어 테이블의 모든 레코드를 잠글 수도 있습니다.

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

  • 컬럼의 크기
  • 레코드의 개수
  • 유니크한 인덱스 키 값의 개수 등

인덱스 키 값의 크기

InnoDB는 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 됩니다.

또한 페이지는 InnoDB 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 합니다.

인덱스도 페이지 단위로 관리 됩니다.

일반적으로 B-Tree는 자식 노드의 개수가 가변적인 구조입니다.

여기서 자식 노드의 개수를 몇 개까지 가지는지는 페이지의 크기와 키 값의 크기에 따라 결정됩니다.

페이지가 16KB(기본값)이고 키 값이 16byte라고 가정하면 하나의 인덱스 페이지는 1*1024/(16+12) = 585개의 자식 노드를 가질 수 있습니다.

여기서 키 값이 32byte로 늘어난다면 1*1024/(16+12) = 372개로 줄어들게 됩니다.

만약 500개의 레코드를 읽어야 한다면 키 값이 16byte인 경우는 한번만 디스크를 읽으면 되지만, 32byte의 경우는 2번을 읽어야 한다는 의미입니다.

B-Tree 깊이

B-Tree의 인덱스의 깊이는 상당히 중요하지만 직접 제어할 방법은 없습니다.

인덱스의 키 값의 평균 크기가 늘어나면 아래와 같은 현상이 추가로 발생합니다.

B-Tree의 깊이가 3이라면 키 값이 16byte의 경우 (585 * 585 * 585)개 정도의 키 값을 담을 수 있지만, 키 값이 32byte의 경우 (372 * 372 * 372)개 정도의 키 값을 담을 수 있습니다.

2억개와 5천만개라는 엄청난 차이를 보입니다.

당연히 담을 수 있는 양이 작으므로 디스크 읽기가 많아져 성능이 안좋아집니다.

선택도(기수성)

인덱스에서 선택도(Selectivity) 또는 기수성(Cardinality)은 거의 같은 의미로 사용되며, 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미합니다.

country라는 컬럼에 인덱스를 건 테이블이 있다고 가정하고 예시를 보겠습니다.

SELECT *
FROM tb_test
WHERE country = "KO"
  AND city = "SEOUL";
  • country 컬럼의 유니크한 값의 개수가 10개
    • 평균 1000건 조회될 것으로 예측 가능
    • 조회되는 레코드가 한 건이라면 불필요한 999개의 레코드를 더 읽는 격
    • 비효율적인 인덱스
  • country 컬럼의 유니크한 값의 개수가 1000개
    • 평균 10건이 조회될 것으로 예측 가능
    • 조회되는 레코드가 한 건이라면 불필요한 9개의 레코드를 더 읽는 격
    • 효율적인 인덱스

읽어야 하는 레코드의 건수

인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 노은 비용이 드는 작업입니다.

일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드를 익는 것보다 4~5배 정도 비용이 더 많이 드는 작업인 것으로 예측합니다.

즉 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 필터링 하는 방식으로 처리하는 것이 효율적입니다.

MySQL 옵티마이저가 기본적으로 힌트를 무시하고 테이블을 직접 읽는 방식으로 처리하겠지만 기본적으로 알고 있어야 할 사항입니다.

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

인덱스 레인지 스캔

인덱스의 접근 방법 가운데 가장 대표적인 접근 방식으로, 가장 빠른 방식입니다.

한 건만 읽는 경우와 한 건 이상을 읽는 경우를 각각 다른 이름으로 구분하지만 여기서는 묶어서 인덱스 레인지 스캔이라고 하겠습니다.

인덱스 레인지 스캔은 아래 구문처럼 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식입니다.

SELECT *
FROM employee
WHERE first_name BETWEEN 'Ebbe' AND 'Gad';

루트 노드에서부터 비교를 시작해 리프 노드까지 찾아 들어가 시작해야 할 위치를 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 됩니다.

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

위 쿼리를 통해 작업이 얼마나 수행됐는지를 확인할 수 있습니다.

  • Handler_read_key: 1번 단계가 실행된 횟수
  • Handler_read_next(정순), Handler_read_prev(역순): 2번 단게로 읽은 레코드 건수
  • Handler_read_first, Handler_read_last: 인덱스의 첫 번쨰 레코드와 마지막 레코드를 읽은 횟수

인덱스 풀 스캔

인덱스 레인지 스캔과 달리 인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 합니다.

대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 인덱스 풀 스캔 방식이 일어납니다.

쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용됩니다.

인덱스뿐만 아니라 데이터 레코드까지 모두 읽어야 한다면 절대 이 방식으로 처리되지 않습니다.

루스 인덱스 스캔

인덱스 레인지 스캔, 인덱스 풀 스캔은 타이트 스캔으로 분류 됩니다.

루스 인덱스 스캔은 말 그대로 느슨하게 듬성듬성 인덱스를 읽는 것을 의미합니다.

SELECT dept_no, MIN(emp_no)
FROM dept_emp
WHERE dep_no BETWEEN 'd002' AND 'd004'
GROUP By dept_no;

INDEX dept_emp(dept_no, emp_no)로 설정 되어 있다면, 정렬까지 되어 있기 때문에 그룹 별로 첫 번째 레코만 읽으면 되기 때문에 이런경우 루스 인덱스 스캔이 일어납니다.

인덱스 스킵 스캔

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

SELECT *
FROM employees
WHERE gender = 'M'
  AND birth_date >= '1997-04-05';

위의 경우 인덱스가 잘 사용되어 쿼리가 나갑니다.

근데 조건에 gender이 없다면 인덱스는 사용되지 않습니다.

MySQL 8.0부터는 앞에 인덱스가 없어도 앞의 인덱스의 그룹만큼 여러번 쿼리가 실행하는 것과 비슷하게 처리가 됩니다.

gender의 값이 M, W 두 가지 뿐이라면 아래 쿼리와 비슷하게 실행 된 것입니다.

SELECT gender, birth_date
FROM emplotee
WHERE gender = 'M'
  AND birth_date >= '1997-04-05';

SELECT gender, birth_date
FROM emplotee
WHERE gender = 'W'
  AND birth_date >= '1997-04-05';

이렇게 조회를 하면 인덱스를 건너뛰면서 스캔하기 때문에 인덱스 스킵 스캔이라고 합니다.

MySQL 8.0에서 새로 도입된 기능이라서 아직 아래의 단점이 있습니다.

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

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

두 개 이상의 컬럼으로 구성된 인덱스를 다중 컬럼 인덱스 또는 복합 컬럼 인덱스라고 합니다.

2개 이상의 컬럼이 연결됐다고 해서 Concatenated Index라고도 합니다.

이렇게 인덱스를 구성하면 앞 인덱스에 의존해서 다음 인덱스가 정렬되어 집니다.

다중 컬럼 인덱스에서는 인덱스 내에서 각 컬럼의 위치가 상당히 중요하며, 그것을 아주 신중이 결정해야 합니다.

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

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

하지만 그렇게 생성됐다고 해서 꼭 그 정렬순서로만 읽을 수 있다는 뜻은 아닙니다.

인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 실시간으로 만들어 내는 실행 게획에 따라 결정 됩니다.

인덱스의 정렬

일반적인 상용 DBMS에서는 인덱스를 생성하는 시점에 인덱스를 구성하는 각 컬럼의 정렬을 설정할 수 있습니다.

MySQL 5.7 까지는 컬럼 단의로 정렬 순서를 혼합해서 생성할 수 없었는데, MySQL 8.0 부터는 혼합 정렬이 가능해 졌습니다.

CREATE INDEX test_db ON member (created_at ASC, updated_at DESC);
인덱스 스캔 방향

설정에 따라 정순, 역순으로 인덱스가 정렬되어 지는데 그렇다고 해서 꼭 정순 정렬 인덱스를 정순으로만 읽는 것은 아닙니다.

옵티마이저가 실행 계획을 만들 때 읽기 방향을 전환하여 읽는 등 최적화 처리를 해줍니다.

내림차순 인덱스

그럼 정렬 상관없이 최적화를 해준다면 아무거나 사용해도 상관없는걸까? 라고 생각한다면 그렇지 않습니다.

우선 인덱스 정렬에 대해 조금 더 깊이 있게 알아보겠습니다.

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

실제로 많은 데이터를 넣고 프라이머리 키 기준으로 테스트를 해보면 정순 스캔(ORDER BY 컬럼 ASC)이 역순 스캔(ORDER BY 컬럼 DESC)보다 빠르다는 것을 알 수 있습니다.

그 이유는 아래 두 가지 때문입니다.

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

B-Tree 인덱스의 가용성과 효율성

비교 조건의 종류와 효율성

다중 컬럼 인덱스에서 각 컬럼의 순서와 그 컬럼에 사용된 조건이 동등 비교인지 아니면 크다 또는 작다 같은 범위 조건인지에 따라 각 인덱스 컬럼의 활용 형태가 달라지며 그 효율 또한 달라집니다.

SELECT *
FROM dept_emp
WHERE dept_no = 'd002'
  AND emp_no >= 10114
  • 케이스 A: INDEX(dept_no, emp_no)
    • dept_no = 'd002' 스캔 후 emp_no >= 10014 스캔 하여 반환 (스캔해야 할 범위가 작음)
  • 케이스 B: INDEX(emp_no, dept_no)
    • emp_no > 10114 스캔 후 dept_no = 'd002'를 스캔 하여 반환 (스캔해야 할 범위가 더 많음)

인덱스의 가용성

B-Tree 인덱스의 특징은 왼쪽 값을 기준으로 오른쪽 값이 정렬된다는 것입니다.

즉 하나의 컬럼을 검색해도 값의 왼쪽 부분이 없으면 인덱스 레인지 스캔 방식이 사용될 수 없다는 것입니다.

이 말은 다중 컬럼 인덱스에서도 왼쪽 컬럼의 값을 모르면 인덱스 레인지 스캔을 할 수 없다는 말이기도 합니다.

가용성과 효율성 판단

기본적으로 B-Tree 인덱스의 특성상 다음 조건에서는 사용할 수 없습니다.

  • NOT-EQUALS로 비교된 경우
  • LIKE %?? (뒷 부분 일치 패턴의 경우)
  • 스토어드 함수나 다른 연산자로 인덱스 컬럼이 변형된 후 비교된 경우
  • NOT_DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우
  • 데이터 타입이 서로 다른 비교 (인덱스 컬럼의 타입을 변환해야 비교가 가능한 경우)
  • 문자열 데이터 타입의 콜레이션이 다른 경우