[Real MySQL] 5. 인덱스

인덱스란?

색인 (찾아보기)

보통 인덱스는 책 끝에 있는 색인으로 많이 비유가 된다. 색인의 내용을 통해 실제 데이터(책의 내용)을 찾아가게 되는데, 인덱스도 이와 유사하다.
테이블 칼럼의 값을 키로, 실제 데이터가 있는 곳의 주소를 값으로 하여 인덱스를 만들어두면, 빠르게 원하는 컬럼만을 찾아가서 조회할 수 있다.

여기서 가장 중요한 것이 바로 정렬이다.
책의 색인과 마찬가지로, 인덱스도 데이터를 최대한 빠르게 찾아갈 수 있게 칼럼의 값을 주어진 순서로 미리 정렬해서 보관한다.

SortedList VS. ArrayList

프로그래밍 언어의 자료구조로 말하자면, 인덱스는 SortedList와, 일반적인 데이터 파일은 ArrayList와 유사하다고 볼 수 있다.

ArrayList는 데이터가 저장되는 순서대로 값을 보관하는 반면, SortedList는 저장된 내용을 이용해 데이터를 항상 정렬된 상태로 유지한다.
그래서 SortedList 자료구조는 데이터가 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정이 느리지만, 이미 정렬되어 있기 때문에 빠르게 원하는 값을 찾아올 수 있다.

인덱스도 결국은 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 희생하고 대신 데이터의 읽기 속도를 높이는 기능이다.
다만 과도한 인덱스의 수는 데이터 저장 성능을 떨어뜨리기 때문에 적절한 선에서 결정이 필요하다.

책에서 소개하는 인덱스에는 B-Tree 인덱스, Hash 인덱스, R-Tree 인덱스, Fractal-Tree 인덱스, 전문 검색 인덱스 등이 있지만 여기서는 B-Tree 인덱스와 Hash 인덱스만 짚으려 한다.

---

B-Tree 인덱스

B-Tree 인덱스는 이름에서 알 수 있듯이 트리 구조를 가진 인덱스이다.
B-Tree에서는 최상위에 있는 하나의 노드를 루트 노드라 하고, 중간 노드들을 브랜치 노드, 그리고 가장 하위에 있는 노드를 리프 노드라고 한다.

이 때 각 자식 노드들의 개수는 가변적으로 변할 수 있기 때문에, B-Tree의 B는 Binary가 아님을 주의하자. 이 B는 Balanced를 의미한다.

인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소 값을 가지고 있다.
그리고 리프 노드끼리는 링크로 연결되어 있어 하나의 리프 노드를 읽는 것이 끝나면 링크를 통해 다음 리프 노드로 넘어가서 작업을 계속 이어나갈 수 있다.

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

새로운 키값이 B-Tree에 저장될 때 테이블의 스토리지 엔진에 따라 바로 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다.
저장 시에는 저장될 키값을 이용해 적절한 위치를 검색한 후, 리프 노드에 키값과 레코드의 주소 정보를 저장한다.

만약 리프 노드가 꽉 차서 더는 저장할 수 없다면 리프 노드가 분리되어야 하는데, 이는 상위 노드에까지 영향을 주므로 일반적으로 쓰기 작업에 비용이 많이 든다.
보통 테이블에 레코드를 추가하는 작업을 1이라 하면, 인덱스에 키를 추가하는 비용은 1~1.5 정도로 예측한다.

인덱스 키값 삭제는 생각보다 간단하다. 해당 리프 노드를 찾아서 삭제 마크만 하면 된다.
인덱스 키값 변경은 먼저 키값을 삭제한 후, 다시 새로운 키값을 추가하는 형태로 처리된다.

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

• 인덱스 키값의 크기

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(Page) 또는 블록(Block)이라고 하는데, InnoDB의 모든 페이지 크기는 16KB로 고정돼 있다.
하나의 페이지가 고정되어 있기 때문에, 인덱스의 키값이 커지면 한 인덱스에 저장할 수 있는 인덱스 키의 개수가 적어지고, 이는 같은 분량의 내용을 읽을 때 디스크로부터 읽어야 하는 횟수가 늘어나 그만큼 느려진다는 것을 의미한다.

• B-Tree 깊이

인덱스의 깊이는 상당히 중요하지만 직접적으로 제어할 방법은 없다.
위에서와 마찬가지로 인덱스 키값의 크기가 커질수록 하나에 인덱스 페이지에 담긴 인덱스 키값의 수가 줄어들고, 이에 따라 B-Tree의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다.

• 선택도(기수성)

선택도(Selectivity) 또는 기수성(Cardinality)은 거의 같은 의미로 사용되며, 모든 인덱스 키값 가운데 유니크한 값의 수를 의미한다.
인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

• 읽어야 하는 레코드의 건수

인덱스를 통해 테이블의 레코드를 읽는 것은 테이블의 레코드를 바로 읽는 것보다 높은 비용이 드는 작업이다.
인덱스를 통해 읽어야 할 레코드의 건수(옵티마이저가 판단한 예상 건수)가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 직접 테이블을 읽은 후 필터링 처리하는 것이 더 효율적이다.

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

• 인덱스 레인지 스캔

대표적인 접근 방식으로 아래 두 방법보다는 빠른 방법이다.
인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다.

루트 노드에서 시작해 브랜치 노드를 거쳐 최종적으로 리프 노드까지 찾아 들어가서 시작 지점을 찾은 후, 순방향 혹은 역방향으로 원하는 레코드의 끝 범위까지 스캔을 한다.
끝에 다다르면 지금까지 읽은 레코드들을 사용자에게 반환하고 쿼리를 끝낸다.

중요한 것은 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요한데, 이 과정에서 레코드 한 건 단위로 랜덤 I/O가 발생한다.
그렇기에 인덱스를 통해 데이터를 읽는 것이 바로 테이블을 읽는 것보다 비용이 많이 드는 것이다.

• 인덱스 풀 스캔

리프 노드를 처음부터 끝까지 읽는 방식을 인덱스 풀 스캔이라고 한다.
대표적으로 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다.

이는 인덱스 레인지 스캔보다는 빠르지 않지만 테이블 풀 스캔보다는 효율적이다.
하지만 보통은 인덱스 풀 스캔 방식은 일반적으로 인덱스를 생성하는 목적에 부합하지 않기 때문에 인덱스를 사용하지 못한다고 표현한다.

• 루스 인덱스 스캔

말 그대로 듬성듬성 인덱스를 읽는 것을 의미한다.
일반적으로 GROUP BY 또는 MAX(), MIN() 함수를 사용해 최적화를 하는 경우에 사용한다.
옵티마이저가 WHERE 조건 등의 범위 전체를 다 스캔할 필요가 없음을 인지하면, 조건에 만족하지 않는 레코드는 무시하고 다음 레코드로 이동한다.

다중 칼럼 인덱스

두 개 이상의 칼럼으로 구성된 인덱스를 다중 칼럼 인덱스라고 한다.

가장 중요한 것은 인덱스의 두 번째 칼럼은 첫 번째 칼럼에 의존해서 정렬돼 있다는 것이다.
마찬가지로 n개의 컬럼으로 구성된 인덱스에서, i번째 칼럼은 항상 (i-1)번째 칼럼에 의존해서 정렬돼 있다. (i>=2)

따라서 2번째 칼럼은 1번째 칼럼이 같은 레코드에 대해서만 정렬되어 있고, 1번째 칼럼이 다른 경우에는 2번째 칼럼의 정렬 순서는 보장할 수 없다.
이 특성은 인덱스의 성능 및 적용점을 파악하는 데 아주 중요한 특성이므로 잘 알아두는 것이 좋다.

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

SELECT * FROM test_table  
WHERE col_1 = 'c001' AND col_2 >= 12345;

이런 쿼리가 있다고 가정했을 때, 아래 각각 인덱스에 대해 어떤 일이 일어나는지 알아보자.

1. 인덱스 A : col_1 + col_2
2. 인덱스 B : col_2 + col_1

인덱스 A를 사용하는 경우, 먼저 "col_1 = 'c001' AND col_2 >= 12345"인 경우를 찾고, 그 이후로는 col_1이 'c001'이 아닐 때까지 인덱스를 쭉 읽기만 하면 된다.

하지만 인덱스 B를 사용하는 경우, 정렬 조건을 고려해 보면 먼저 "col_1 = 'c001' AND col_2 >= 12345"인 경우를 찾고, 그 이후로는 모든 레코드에 대해 col_1이 'c001'인지 판별하는 과정을 가져야만 한다.
결국 인덱스 B에서 col_2는 비교 작업의 범위를 좁히는 데에 아무런 도움을 주지 못했다.

인덱스 A의 경우에서처럼 작업의 범위를 결정하는 조건을 작업 범위 결정 조건이라 하고, 인덱스 B의 col_2처럼 단순히 거름종이 역할만을 하는 조건을 필터링 조건 혹은 체크 조건이라고 표현한다.

작업 범위를 결정하는 조건은 많으면 많을수록 좋다.
반대로 체크 조건은 오히려 쿼리 실행을 더 느리게 만들 수도 있다.
인덱스를 적절하게 사용하기 위해서는 쿼리의 조건을 작업 범위 결정 조건에 알맞게 작성하던지, 아니면 쿼리에 맞게 인덱스를 생성하는 것이 좋은 방법이다.

가용성과 효율성 판단

작업 범위 결정 조건으로 사용할 수 없는 조건을 잘 알아두는 것이 중요하다.

• NOT-EQUAL로 비교된 경우 ("<>", "NOT IN", "NOT BETWEEN", "IS NOT NULL")
• LIKE '%??' (앞부분 비교가 아닌 뒷부분 일치) 형태로 문자열 패턴이 비교된 경우
• 스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우 (ex. SUBSTRING, DAYOFMONTH)
• NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우
• 데이터 타입이 서로 다른 비교(인덱스 칼럼의 타입을 변환해야 비교가 가능한 경우)
• 문자열 데이터 타입의 콜레이션이 다른 경우(UTF8, EUCKR)

그리고 MySQL에서는 다른 DBMS와 달리 NULL 값도 인덱스로 관리되기 때문에 IS NULL 조건도 작업 범위 결정 조건으로 활용될 수 있다.

다중 칼럼 인덱스의 경우는 다음과 같이 나뉜다.

INDEX idx_test ( col_1, col_2, ... , col_n)

• 작업 범위 결정 조건으로 인덱스를 사용하지 못하는 경우

  • col_1 칼럼에 대한 조건이 없거나, col_1 칼럼의 비교 조건이 위의 인덱스 사용 불가 조건 중 하나인 경우

• 작업 범위 결정 조건으로 인덱스를 사용하는 경우 (i >= 2)

  • col_1 ~ col_(i-1)까지 EQUAL 형태("=" 또는 "IN")로 비교
  • col_i 칼럼에 대해 EQUAL 형태("=" 또는 "IN"), 크다 작다 형태(">" 또는 "<"), LIKE로 좌측 일치 패턴(LIKE 'ab%') 중 하나로 비교

---

해시(Hash) 인덱스

해시 인덱스의 구조와 특성

해시 인덱스는 동등 비교 검색에는 최적화돼 있지만 범위 검색이나 정렬된 결과를 가져오는 목적으로는 사용할 수 없다.

이름에서 알 수 있듯이 해시 함수를 사용해 인덱스를 구성하는데, 보통은 메모리 기반의 테이블에 주로 구현돼 있고 디스크 기반의 대용량 테이블로는 거의 사용되지 않는다.

해시 인덱스의 큰 장점은 실제 키값과는 관계없이 해시 함수의 결과를 이용하기 때문에 인덱스 크기가 작고 검색이 빠르다는 것이다.
트리 형태의 구조가 아니라서 검색하고자 하는 값을 주면 해시 함수를 거쳐서 원하는 키값이 포함된 버켓을 알아낼 수 있다.
그리고 해당 버켓만 읽어 빠르게 실제 레코드 저장 위치를 알 수 있다.

해시 인덱스의 가용성 및 효율성

동등 비교 조건으로 값을 검색하면 해시 인덱스를 사용할 수 있다.
예를 들면 "=", "<=>", "IN", "IS NULL", "IS NOT NULL"과 같은 것들이 있다.
IN 연산자도 결국 여러 개의 동등 비교로 풀어서 처리할 수 있기 때문에 같은 효과를 얻을 수 있다.
("<=>"은 NULL-Safe EQUAL 연산자로 양쪽이 모두 NULL인 경우를 제외하고는 "="과 똑같이 작동하는 연산자이다.)

반대로 ">", "<", "BETWEEN ~ AND", "LIKE", "<>" 등의 크다 작다 기반의 검색은 해시 인덱스를 사용할 수 없다.
다중 칼럼 인덱스에서도 모든 칼럼이 동등 비교 조건으로 비교되는 경우에만 해시 인덱스를 사용할 수 있다.

---

참고

위 내용은 이성욱님의 Real MySQL (위키북스) 에서 일부 내용을 간단하게 정리한 것입니다.
세부적인 내용은 책을 직접 구입하셔서 읽어보시는 것을 추천드립니다.