SQL 조회 성능을 위한 인덱스(Index)

인덱스

인덱스(Index)는 DB에서 조회, 정렬, 그룹화 등의 연산을 빠르게 수행하기 위해 사용되는 정렬된 자료구조입니다.

특정 열 또는 열의 조합에 대한 정렬된 키와, 해당 키가 대응한 실제 데이터 레코드의 위치로 이루어져 있습니다. (key-value) 형태

 

 

예를 들어 위와 같이 주어진 `user` 테이블에서 나이가 20세 미만인 사용자를 찾는 쿼리(`select * from user where age < 20`)를 실행한다고 가정해봅시다. 해당 쿼리는 모든 데이터를 순차적으로 조회하여 조건을 만족하는 결과를 찾아낼 것입니다. 위 테이블은 데이터가 적게 담겨져 있어서 조회 시간에 큰 문제가 없지만, 만약 테이블에 데이터가 매우 많이 담기게 된다면 조회 기능의 성능은 매우 저하될 것입니다.

 

 

우리는 조회 기능의 성능을 높이기 위해 `인덱스`를 적용할 것입니다. 인덱스를 적용하면, 나이 열에 대한 정렬된 인덱스를 생성할 수 있습니다. 아래와 같이 나이 열에 대한 정렬된 데이터와 그에 대응되는 주소로 이루어진 데이터가 저장됩니다. 

 

인덱스를 사용함으로 모든 데이터를 스캔하지 않고 정렬된 나이 데이터로 조건을 만족하는 데이터를 찾고, 그에 대응하 데이터를 가져오게되어 성능이 향상됩니다. 즉, 조회 성능을 올려주는 인덱스의 핵심은 탐색 범위를 최소화해주는 것입니다.

 

 

인덱스의 자료구조

인덱스는 어떤 자료구조로 구현되어 있을까요??

 

List

우리가 가장 흔하게 생각할 수 있는 List입니다. 정렬된 리스트의 탐색은 O(logN)입니다. 정렬되지 않은 리스트의 탐색은 O(n) 입니다. 이러한 정렬되지 않은 리스트를 정렬하게 되면 정렬하는 시간 복잡도는 O(n) ~ O(n * logN)입니다. 또한 치명적인 단점으로 리스트는 insert/delete 비용 매우 높습니다.

 

HashMap

key-value 한 쌍으로 인덱스가 이루어져 있다고 했기 때문에 가장 먼저 생각할 수 있는 자료구조라 생각합니다.

HashMap은 단건의 데이터를 조회할 때는 O(1)이 걸리지만, 조건으로 범위를 설정하여 데이터를 조회(범위 탐색)하게 되면 전체 데이터를 조회하기 때문에 O(n)이 걸립니다. 때문에 HashMap은 범위 탐색이 많지 않은, 메모리 DB안에서 HashMap이 사용되기도 합니다.

 

B+ Tree

트리를 사용하게 되면 트리 높이에 따라 시간 복잡도 결정됩니다. 만약 트리가 한쪽에만 치우치게 된다면 List와 똑같이 O(n)의 시간 복잡도를 갖게 될것입니다. 때문에 트리의 높이가 치우치지 않고 균형을 이루게하는 것이 중요합니다. 또한 Tree 중에 B+ Tree는 노드에 자식 노드에 대한 포인터가 저장되어 있기 때문에, 탐색에 매우 효율적인 알고리즘 입니다.

B+ Tree 이미지 (출처:https://ko.wikipedia.org/wiki/)

B+ Tree의 특징은 다음과 같습니다.

• 삽입 / 삭제 시 항상 균형을 이룹니다.
• 하나의 노드가 여러 개의 자식을 가질 수가 있습니다.
• 리프노드에만 데이터가 존재하기 때문에 연속적인 데이터를 접근할 때 유리합니다.

 

 

실제로 인덱스는 어떻게 탐색할까?

 

앞서 설명했듯이 Index는 주로 B+ Tree 자료구조를 사용합니다. 때문에 인덱스에서 데이터를 찾기 위해 B+ Tree 탐색을 수행합니다. 그리고 여기서 부터 사용하는 DBMS가 무엇이냐에 따라 플로우가 다릅니다.

 

Oracle의 경우 인덱스에 데이터의 주소가 들어있기 때문에 바로 해당 주소를 갖고 데이터를 찾을 수 있습니다. 
반면 MySQL의 경우 인덱스에 데이터의 주소가 들어있지 않고 PK가 들어있게 됩니다. 그리고 해당 PK를 가지고 PK 인덱스(클러스터 인덱스)를 통해 물리적인 주소를 얻고 그 주소로 데이터를 조회합니다.

 

클러스터 인덱스

MySQL, MariaDB에서는 테이블을 생성하면 기본적으로 PK를 `클러스터 인덱스`로 설정됩니다.

클러스터 인덱스는 데이터의 물리적인 저장 순서와 인덱스의 순서를 일치시키는 특별한 유형의 인덱스입니다.

클러스터 인덱스는 물리적인 저장 순서와 인덱스의 순서가 일치하기 때문에 클러스터 키 순서에 따라서데이터 저장 위치가 변경됩니다. 따라서 인덱스는 클리스터 키 삽입/갱신시에 성능에 이슈가 발생할 수 있습니다. 이는 기본적으로 생성되는 Auto Increment PK를 클러스터 인덱스로 사용하는 것이 유리하다는 의미입니다.

즉, MySQL에서 우리가 생성한 인덱스만으로는 우리가 조회하고자하는 데이터를 찾지 못합니다. 클러스터 인덱스인 `PK 인덱스`를 항상 검색해주어야 인덱스를 통해 데이터를 조회할 수 있습니다.

 

클러스터 인덱스 장점

1. PK 인덱스의 PK의 값에 따라 데이터가 물리적으로 정렬되어 저장되어 있습니다. 때문에 PK를 활용한 탐색이나, 특정 순서로 접근하거나, 범위 탐색 시 성능이 향상됩니다.
2. 다른 인덱스를 추가해주면 해당 인덱스들은 클러스터 인덱스의 키인 PK를 갖게됩니다. 때문에 `커버링`에 유리합니다.
   [커버링]: 인덱스 테이블 만으로도 데이터 테이블까지 가지 않고 응답을 내려줄 수 있는 것.

 

 

인덱스는 언제 적용할까?

인덱스는 조회 성능을 향상시키는 방법입니다. 인덱스는 자주 사용되는 조회 쿼리에 사용되는 조건을 파악하여 어떤 열에 인덱스를 적용해야 하는지 고려해야합니다.

 

인덱스가 자주 사용되는 경우

1. WHERE 절, ORDER BY / GROUP BY 절, JOIN:
   해당 연산들에 참여하는 열에 인덱스를 생성하면 인덱스를 통해 효율적으로 수행될 수 있습니다. 
2. 복합 인덱스 활용:
   여러 열을 조합한 복합 인덱스를 사용하면, 여러 조건에 대한 검색 성능을 향상 시킬 수 있습니다. 때문에 이런 경우 복합 인덱스를 고려해보는 것이 좋습니다. 복합 인덱스를 적용할 때 인덱스의 순서에 따라 적용되는 순서도 바뀌기 때문에, 자주 사용되는 조건을 앞에 위치시키는 것이 좋습니다.
3. 조회(읽기) 작업이 많은 테이블:
   데이터의 변경 작업보다 읽기 작업이 빈번한 경우 검색 작업을 최적화할 수 있습니다. 

 

인덱스를 적용하지 않는 경우

1. 데이터 변경 연산 고려:
   데이터의 삽입/삭제/갱신이 빈번하게 일어나는 경우 소모되는 자원이 크기 때문에 이를 고려하여 인덱스를 적용해야합니다.
2. 인덱스를 잘못 선택한 경우:
   단일 인덱스만 사용할지, 복합 인덱스를 사용할지, 또는 어떤 열을 인덱스의 기준으로 잡는지에 따라 성능에 영향을 미칠 수 있습니다. 잘못된 인덱스 선택은 오히려 성능에 안 좋은 영향을 미칠 수 있기 때문에 고려하여 사용해야 합니다.
3. 인덱스를 생성하는 것은 저장 공간이 필요하기 때문에 무분별한 인덱스 생성은 공간 소모가 크게 증가할 수 있습니다.

 

 

인덱스 사용 주의할 점 !!

1. WHERE / ORDER BY/ GROUP BY를 혼합해서 사용할 때는 인덱스를 잘 고려해주어야 합니다.
   예를 들어 WHERE 절이 실행될 때 인덱스를 타서 데이터를 가져왔지만 ORDER BY절이 인덱스를 타지 못한다면 가져온 데이터들을 다 정렬해주어야 할 수도 있습니다.
2. explain 쿼리로 항상 인덱스가 의도대로 동작하는지 확인해주는 것이 좋습니다.