[Database] 인덱스(index)에 대하여.

0. 들어가며

데이터베이스의 쿼리 성능 향상을 위해 빼놓을 수 없는 것이 바로 인덱스입니다. 무지성으로 인덱스를 where 절에 있는 컬럼에 맞춰걸지 않지 않기 위해 공부한 내용을 정리해보려 합니다. 인덱스는 어떻게 동작하고, 인덱스를 걸었더니 왜 성능이 빨라진거지에 대한 물음을 얻는 것이 목표이며, 본 글의 내용은 Real MySQL 8.0을 주로 참고한 내용입니다. 따라서 MySQL과 InnoDB 스토리지 엔진을 기반으로 된 설명임을 알립니다.

 

이 글을 읽기 전 알고 있어야할 배경지식은 다음과 같습니다.

• B-Tree가 무엇인지
• DB에 대한 간단한 지식

---

1. 데이터베이스의 디스크 읽기

HDD는 SSD에 비해 500배 느리고, SSD는 DRAM에 비해 1,000배 가량 느립니다. 또 DRAM은 CPU에 비해 10배 정도 느리죠.

이렇게 보면 컴퓨터에서 CPU나 메모리의 성능은 매우 빠른데 비해 HDD, SDD와 같은 데이터 저장 매체는 컴퓨터에서 굉장히 느린 매체임을 알 수 있습니다.

 

이렇듯 DB 성능 튜닝의 핵심은 어떻게 디스크 I/O를 줄일 것이냐가 관건일 때가 많죠. 또한 DB 서버는 랜덤 I/O를 통해 작은 데이터를 읽고 쓰는 작업이 대부분이라 이를 잘 처리하는 것이 성능에 많은 영향을 미칩니다.

---

2. 인덱스란?

인덱스는 책의 목차로도 많이 비유됩니다. 책의 목차를 통해 빠르게 내가 원하는 내용을 찾을 수 있듯 DB에서의 인덱스는 원하는 레코드(데이터)를 빠르게 찾을 수 있도록 도움을 줍니다.

 

DB에서 원하는 데이터를 찾기 위해 모든 데이터를 검색하는 것은 시간이 많이 걸리는 일입니다. 따라서 특정 컬럼(혹은 컬럼들)의 값과 해당 레코드 주소를 key-value로 저장해둡니다. 이를 인덱스라고 하는데 이 때 중요한 것은 인덱스가 정렬되어있다는 것입니다. 가나다 순으로 많은 단어를 정렬해두면 빠르게 내가 원하는 단어를 찾을 수 있는 것처럼 DBMS도 같은 원리를 사용해 인덱스를 칼럼(key)의 값을 이용해 정렬해 둡니다. 

 

그런데 정렬된 상태를 유지하려면 비용이 듭니다. 바로 insert, update, delete에서의 비용을 추가적으로 들여야하는 것이죠. 대신 앞서 말한 것처럼 정렬된 상태에서는 select의 성능이 늘어나게 됩니다. 즉 인덱스는 쓰기 성능을 희생하고, 읽기 성능을 높이는 기능인 것이죠.

 

다시 정리하면 특정 테이블에 인덱스를 추가하려는 작업은 데이터의 쓰기 속도를 얼마나 희생가능한지와 읽기 속도를 얼마나 더 빠르게 만들어야하는지에 따라 결정되어야하는 행위입니다.

---

3. B-Tree 인덱스

인덱스를 유지하기 위해서는 적절한 자료구조가 필요한데 이 때 크게 두 가지 정도를 고려해볼 수 있습니다.

 

먼저 Hash 자료구조인데요. Hash는 키-값으로 데이터를 저장하고 키를 통해 빠르게 값을 찾아낼 수 있는 자료구조입니다. 하지만 Hash 자료구조를 DB의 인덱스에 일반적으로 사용하기에는 범위 검색이나 전방일치 검색 등이 불가능하다는 단점이 있습니다.

 

다음으로 Tree 형태의 자료구조를 고려해볼 수 있습니다. Tree 구조를 사용하면 O(logN)의 빠른 탐색 시간을 가질 수 있죠. 다만 Disk I/O 자주 해야하는 DBMS에서는 트리의 높이가 자연스럽게 높아지는 이진트리보다는 자식을 더 많이 가질 수 있는 B-Tree를 일반적으로 사용합니다. (본 글에서는 B-Tree, B+Tree, B*Tree 등은 그냥 퉁쳐서 B-Tree라고 하겠습니다.)

 

B-Tree의 구조는 기본적으로 최상위 노드를 루트 노드, 가장 하위 노드를 리프 노드, 그 중간에 있는 노드들을 브랜치 노드라고 합니다. 또한 DB에서는 인덱스 테이블과 실제 데이터 테이블이 따로 관리되는데 이 때문에 인덱스 테이블의 리프 노드에는 항상 실제 데이터 레코드가 어디에 있는지에 대한 주소값을 가지고 있습니다.

 

+ InnoDB 스토리지 엔진의 경우 세컨더리 인덱스(Primary Key로 만든 인덱스를 제외한 인덱스)에서 바로 데이터 레코드 값을 찾아가지 못하고 프라이머리 인덱스 키의 위치를 포인팅하여 한 번 더 인덱스를 타고 들어가 레코드를 찾는 방식을 사용하고 있습니다.

---

4. B-Tree 인덱스에서의 키 추가 및 변경, 검색

1) 인덱스 키 추가

B-Tree에 인덱스 키를 추가하려면 대대적인 tree rebalancing이 일어나서 비용이 많이 들 수 있습니다. 인덱스 추가에 따른 insert, update 문이 어느정도의 성능 영향을 받는지는 테이블의 컬럼 수, 컬럼의 크기, 인덱스 컬럼의 특성을 확인해야하지만 비용을 대략적으로 아래 정도로 생각할 수 있습니다.

• 모든 인덱스를 B-Tree라고 가정했을 때
  • 레코드 추가 비용을 1 이라고 하면, 인덱스 하나 당 작업 비용은 1.5 정도로 예측한다.
  • 테이블의 인덱스가 3개라면 (1 + 1.5 * 3) = 5.5 정도의 비용으로 추산한다.

이 때 대부분의 비용은 메모리나 CPU에서 처리하는 시간이 아니라 디스크로부터 인덱스 페이지를 읽고 쓰는데 걸리는 시간입니다.

2) 인덱스 키 삭제 및 변경

인덱스 키 삭제는 간단합니다. 해당 키 값이 저장된 B-Tree 리프 노드를 찾아서 삭제 마킹만 하고 작업을 완료하면 됩니다. 이 때 마킹된 인덱스 키 공간은 그대로 방치하거나 재활용합니다.

 

인덱스 키 변경은 인덱스 키 삭제 + 새로 삽입 하는 과정을 거치게 됩니다.

3) 인덱스 키 검색

위에서 살펴본 것 처럼 인덱스에 키를 추가하고 삭제하고 변경하는 작업은 비용이 많이 들고, 번거로운 일입니다. 하지만 이러한 비용을 모두 지불하면서까지 인덱스를 유지하는 이유는 바로 빠른 인덱스 키 검색을 위함입니다.

 

인덱스를 사용하면 B-Tree 루트 노드부터 시작하여 최종 리프 노드까지 이동하며 비교 작업을 수행하는데 이 과정을 "트리 탐색"이라고 합니다. 이 트리 탐색은 select 뿐 아니라 udpate, delete를 처리하기 위해 해당 레코드를 먼저 검색해야하는 경우에도 사용합니다.

 

또한 B-Tree 인덱스를 이용한 검색은 등호 조건, 부등호 조건, 전방일치 조건 등에서도 사용할 수 있습니다.

---

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

B-Tree 인덱스에서의 검색이나 변경 작업 성능은 다음과 같은 항목들에 영향을 받습니다.

1. 인덱스 키 값의 크기
2. Cardinality (선택도)
3. 읽어야하는 레코드 건 수

왜 그런지 하나하나 살펴보도록 하죠.

1) 인덱스 키 값의 크기

InnoDB 스토리지 엔진에서는 디스크에 데이터를 저장하는 가장 기본 단위를 Page 혹은 Block이라고 합니다. 이는 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 되죠. 즉, 인덱스도 결국 페이지 단위로 관리됩니다.

 

B-Tree에서는 자식 노드 개수가 가변적인데 이 때 자식 노드의 개수를 결정하는 것이 바로 페이지의 크기와 키 값의 크기입니다. 페이지의 크기의 경우 설정을 할 수 있지만 키 값의 크기는 저장하려는 데이터의 성격에 따라 달라지죠.

 

InnoDB의 페이지 기본값은 16KB인데 이 때 인덱스 키가 16byte, 자식 노드 주소 크기가 12byte라고 하면 한 페이지에 저장될 수 있는 키의 값이 다음과 같이 정해질 수 있습니다.

• 16KB / (16byte + 12byte) = 585개 -> 즉, 자식 노드를 585개 가질 수 있게 되는 것

이렇게 인덱스 키 값의 크기가 커지면 자연스럽게 한 페이지에 저장될 수 있는 자식 노드 개수도 줄어들게 됩니다. 이는 곧 사용해야할 페이지가 많아진다는 뜻이며, B-Tree의 높이가 높아진다는 것이고, Disk I/O 횟수가 늘어난다는 의미입니다. 즉, 성능이 느려진다는 것이죠.

 

다만, 아무리 대용량 데이터베이스라도 B-Tree의 깊이가 5단계 이상 깊어지는 경우는 흔치 않다고 하며, 인덱스 키 값은 가능하면 작게 잡는 것이 좋다는 정도의 이야기입니다.

2) Cardinality (선택도)

Cardinality는 모든 인덱스 값 중 유니크한 값의 개수를 의미합니다. 예로 100개의 인덱스 키가 있는데 유니크한 키가 15라면 Cardinality는 15가 됩니다.

 

인덱스는 Cardinality가 높을수록 검색 대상을 줄일 수 있다는 것이고, 그만큼 빠르게 처리된다는 의미입니다.

 

예시로 table에 1만 건의 레코드가 있고 country라는 컬럼에만 인덱스가 있다고 가정해봅시다.

• 케이스 1 : 인덱스의 Cardinality가 10인 경우
• 케이스 2 : 인덱스의 Cardinality가 1000인 경우

여기서 아래 쿼리를 실행하면 어떻게 될까요?

SELECT *
FROM tb_test
WHERE contry = "KOREA" AND city = "SEOUL";

 

(contry, city) 쌍은 중복이 없다고 가정했을 때 케이스 1의 경우는 country로 인덱스를 탈 시 평균적으로 1,000개의 레코드를 살펴봐야합니다. 즉 999개의 불필요한 레코드를 검색하게 되는 것이죠. 반면 케이스 2의 경우는 평균적으로 10개의 레코드를 살펴봐야합니다. 이 때는 9개의 불필요한 레코드만 검색하게 되죠.

 

따라서 인덱스의 Cardinality에 따라 같은 결과를 보이는 쿼리도 실제 살펴본 레코드의 양이 다르며, 이 때문에 성능 또한 달라질 수 있습니다.

3) 읽어야하는 레코드 건 수

인덱스를 통해 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업입니다. 예시로 100만건의 레코드 중 50만 건의 레코드를 읽어야하는 쿼리가 있다고 가정해봅시다.

 

이 때 테이블을 풀 스캔하는게 효율적일지 인덱스를 통해 필요한 50만건만 읽는 것이 효율적일지를 알아야합니다. 즉, 인덱스를 이용한 읽기의 손익분기점을 알아야합니다.

 

일반적으로는 인덱스를 통해 1건을 읽는 것은 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도의 비용이 드는 것으로 계산할 수 있습니다. 따라서 인덱스를 통해 읽는 레코드의 건수가 전체 테이블 레코드 건수의 20% 정도를 넘어서면 인덱스를 이용하지 않는 것이 더 효율적일 수 있습니다.

---

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

B-Tree 인덱스를 통해 데이터를 읽는 방법을 알아보겠습니다. 크게 다음과 같이 세 가지 방식이 있습니다.

1. 인덱스 레인지 스캔
2. 인덱스 풀 스캔
3. 루스 인덱스 스캔

여기서는 1번과 2번 스캔에 대해서 알아보도록 하겠습니다.

1) 인덱스 레인지 스캔 (Index Range Scan)

인덱스 레인지 스캔은 가장 대표적인 인덱스 접근 방법입니다.

Select * FROM employees WHERE first_name BETWEEN “Anna” AND “Gad”

 

위와 같은 쿼리문이 있고, first_name 컬럼으로 된 인덱스가 있다고 가정해봅시다.

 

이 때 다음과 같은 순서로 데이터를 찾아가게 됩니다.

1. 인덱스에서 조건에 만족하는 값이 저장된 위치를 찾는다. (Index Seek)
   • B-Tree를 따라가며 리프 노드에서 "Anna"의 위치를 찾는다.
2. 1번에서 탐색된 위치부터 필요한 만큼 리프 노드에서 인덱스를 차례대로 쭉 읽는다. (Index Scan)
   • "Anna" 에서부터 시작하여 리프노드를 따라 "Gad" 까지 쭉 읽기 (리프 노드는 링크드리스트 형태로 되어있어 따라가며 Scan 할 수 있다.)
3. 2번에서 읽어들인 인덱스 키와 레코드 주소를 이용해서 레코드가 저장된 페이지를 가져오고 최종 레코드를 읽어온다.
   • 이 과정에서 레코드 한건 한건 단위로 랜덤 I/O가 일어난다. -> 인덱스를 통한 데이터 읽기가 테이블을 통해 읽는 읽기보다 성능이 안좋은 이유
   • 커버링 인덱스(쿼리가 인덱스에 존재하는 칼럼만으로 처리가 가능한 경우)를 사용하면 디스크의 레코드를 읽지 않아도 돼서 랜덤 I/O가 발생하지 않고 성능은 그만큼 빨라진다.

2) 인덱스 풀 스캔 (Index Full Scan)

인덱스 풀 스캔은 인덱스를 처음부터 끝까지 전부 읽는 것을 말합니다. 위에서 살펴본 인덱스 레인지 스캔과는 조금 다른 사용 방식인데요. 풀 스캔은 다음과 같은 상황에서 사용됩니다.

• (column1, column2, column3) 으로 인덱스가 있을 때, 쿼리의 조건이 column2 혹은 column3 으로 검색하는 경우 + 인덱스에 포함된 컬럼만으로 쿼리를 처리할 수 있는 경우에만 사용됩니다.

이 경우는 인덱스의 일반적인 생성 목적과 다르게 사용하는 방식이지만, 테이블의 레코드를 읽을 필요가 없고, 일반적으로 인덱스의 전체 크기가 전체 데이터 테이블에 비해 훨씬 작기 때문에 보다 적은 디스크 I/O로 쿼리를 처리할 수 있다는 장점이 있습니다. 

---

7. 인덱스를 사용할 때 주의할 점

인덱스를 사용할 때 주의할 점은 많이 있겠지만 몇 가지만 소개하면 다음과 같습니다.

1) 다중 컬럼 인덱스를 사용하는 경우

다중 컬럼 인덱스에서는 정렬 순서가 앞선 인덱스 컬럼부터 기준으로 정렬되기 때문에 인덱스 내의 각 컬럼의 위치(순서)가 매우 중요합니다. 즉 (c1, c2, c3) 처럼 다중 컬럼 인덱스를 구성하면 c1을 우선적으로 정렬하고 그 후 c2에 대해서 정렬하고, 마지막으로 c3에 대해서 정렬됩니다. 따라서, 만약 c2만 where 절에 썼을 때 인덱스는 c1 순으로 정렬되어 있기 때문에 인덱스를 효과적으로 탈 수 없습니다.

2) <> 조건을 사용하는 경우

where 절에서 <> (not equal) 조건을 사용하는 경우에도 B-Tree 인덱스에서는 정렬된 성질을 활용할 수 없으므로 인덱스를 사용해 봐야할 데이터 수를 줄일 수 없습니다.

3) 후방 일치 조건을 사용하는 경우

where, like 문을 사용할 때 전방이 아닌 후방 일치 형태의 문자열 패턴 비교가 일어난 경우에도 B-Tree 인덱스의 정렬된 성질을 활용하여 데이터 수를 줄일 수 없습니다.

4) 인덱스 컬럼을 변형한 후 비교하는 경우

아래와 같은 쿼리문처럼 키 값을 변형하여 사용하는 경우에도 age * 10은 B-Tree에 있는 키 값이 아니므로 인덱스를 적절히 사용할 수 없습니다.

SELECT * FROM Member WHERE age * 10 = 100

 

 

정리하면 결국 B-Tree 인덱스는 키가 정렬되어있다는 점을 이용해 조건에 맞는 데이터를 빠르게 찾거나, 찾아야하는 데이터 범위를 줄임으로써 성능 향상을 만들어냅니다. 만약 정렬된 상태를 활용할 수 없는 조건을 준다면 인덱스의 의미가 없어지는 것이죠.

 

끝.