[Database] Index

데이터베이스의 성능을 좌우하는 주요 요소인 인덱스에 대해 알아보자.

 

데이터베이스의 크기가 충분히 크지 않을 때(테이블 하나에 10000개정도?)는

인덱스를 걸지 않아도 딱히 눈에 띌만한 성능 저하가 나타나지는 않지만

10만개, 100만개처럼 늘어나다보면 문제가 두드러진다.

 

예를 들어, 위 쿼리 결과는 800만개의 행이 저장된 테이블에 대해 무지성 쿼리를 날린 결과인데,

실행 시간이 5초나 걸렸다.

 

엥? 5초면 괜찮은거 아니냐? 할 수도 있는데,

우리가 데이터베이스를 주로 사용하는 환경은 단일 사용자가 아닌 다중 사용자 대상이므로

여러 명의 사용자가 저런 쿼리를 날리게 되면 걸리는 시간은 더욱 늘어난다.

 

게다가, 느리기만 하면 그나마 다행이지... 컴퓨팅 자원도 엄청나게 소모한다.

https://satisfactoryplace.tistory.com/182?category=907962 

[MongoDB] CPU Spike(frequently high load) 문제

 

만약 이 상태에서 다른 테이블과 조인과 같이 복잡한 연산이 들어갈 경우 분단위까지 넘어갈 수 있기 때문에

반드시 문제점을 찾아 진단 및 수정한다.

 

Index

데이터베이스에서 인덱스는 색인을 의미한다.

 

우리가 도서관이나 서점에 가서 원하는 책을 찾을때를 생각해 보자.

 

그러면 우리는 정보 검색을 통해 책 위치를 코드값으로 알 수 있다.

I304라는 값을 받으면 I섹션으로 간 다음 그 섹션에서 304를 찾는다.

 

여기서 정보 검색기도 없고, 섹션별로 도서를 정리해두지 않으면 어떻게 될까?

 

우리는 원하는 책을 찾기 위해 모든 책을 뒤져보아야 한다.

 

데이터베이스도 마찬가지다.

 

수만개의 데이터 중 원하는 row를 찾을 때 적은 비용으로 찾아내기 위해

각 row마다 어떤 대표값들을 지정해 두고, 나중에 그 row를 찾기 위해 대표값으로 검색한다.

 

여기에서의 대표값이 Database Index이다.

 

인덱스가 없다면?

도서관에서 책을 찾기 위해 모든 책을 뒤지듯이, 데이터베이스도 값을 찾기 위해 테이블에 존재하는 모든 데이터를 탐색한다.

 

이는 Full scan을 유발하며 막대한 컴퓨팅 자원을 오랜 시간 소모한다.

 

Clustered Index vs Non-Clustered Index

Clustered Index는 테이블 당 하나 존재하는 인덱스로,

PK를 기준으로 B+ Tree를 만들고 해당 트리의 리프 노드에 실제 데이터가 존재한다.

 

이 때, 리프 노드는 여러개의 row에 대해 순차적으로 정렬된 상태로 데이터를 가지고 있으며,

하나의 데이터를 읽더라도, 해당 리프 노드에 존재하는 모든 데이터를 읽는다.

 

따라서 단일 검색 또는, 범위 검색(Range Search)를 할 때 매우 빠른 속도를 자랑한다.

(Binary Search의 압도적인 검색 속도를 상상해보자; O(log n))

 

Clustered Index는 테이블당 하나만 존재할 수 있기 때문에 다른 값에 대한 인덱스(ex: unique key)는 Non Clustered Index로 적용된다.

 

Non-Clustered Index의 Node들도 B+ Tree형태로 저장되지만,

Leaf Node가 데이터를 포함하지 않고 대신 Clustered Index의 Leaf Node의 한 부분을 포인팅한다.

 

따라서 단일 검색에서는 큰 차이가 없지만 Range Search를 하게 되면

Disk IO횟수가 기하급수적으로 늘어나 성능에 악영향을 끼친다.

(Non-Clustered Index의 Leaf Node에 포함된 포인터들은 실제 디스크에서는 순차적으로 존재하지 않기 때문이다)

 

B+ tree

 

B+ tree는 이진 트리와 비슷한데 조금 다르다.

 

1. 리프 노드들 끼리 양방향으로 연결되어 있어, 하나의 leaf node에 대한 스캔을 마치고 나서 바로 다음 리프 노드로 이동할 수 있다.

 

2. 항상 리프 노드들 끼리는 같은 depth에 존재한다. B+ tree의 depth는 한 노드의 child 갯수를 f(fanout)라 했을 때 LogN/LogF 값이다(단 N은 전체 레코드 갯수; f=100, N= 1,000,000,000일 때 depth는 5가 된다)

 

3. 트리 깊이의 확장과 축소가 가능하며, 확장하기 전 최대한 모든 노드의 child 갯수를  fanout/2<= count <= fanout을 유지하도록 하여 가능한 모든 노드를 채우도록 되어 있다.

 

B+는 범위 탐색에 특히 강하며, 단일 검색에 대해서도 높은 성능을 보인다.

 

시간복잡도는 O(log N/Log F)이다.

 

Database Index에서 타입을 Index로 설정하면 B+ tree를 사용한 인덱싱을 한다.

 

Hash Index

해쉬인덱스는, 인덱스로 사용한 키값을 해쉬 함수에 돌려 해쉬 버켓을 찾는다.

해쉬 버켓은 N개의 record를 포함하고 있다.

(H(x)= Hash Bucket[x]= {row[x1], row[x2] ... }; x= index value)

 

단일 검색을 할 때 시간 복잡도는, 해쉬 함수에 입력하고 버켓에 접근해 출력하는게 전부이므로 O(1)이 된다.

 

그렇다면 Hash Index는 B+ tree에 비해 항상 더 우수할까?

 

아니다, 범위 탐색을 할 때를 생각해 보자.

 

Hash Bucket은 Hash Function의 결과에 따라 버켓에 값이 저장될 뿐,

어떤 값에 대해 오름차순/내림차순으로 정렬되는 것이 아니다.

(육안으로 보기엔 전혀 다른 여러 값들이 동일한 해쉬 버켓에 들어간다)

 

따라서 범위 탐색을 할 때는 해쉬 인덱스가 전혀 도움되지 않는다.

 

또한 전체 탐색(테이블 내 모든 데이터 출력)의 경우에도,

모든 값에 대해 해쉬 함수에 대입하여 해쉬 버켓에 접근해야 하므로 역시 도움되지 않는다.

 

해쉬 인덱스는 단일 값 검색에 대해서만 압도적으로 빠르다.

 

Index vs Non-Index

 

위에서 무지성 쿼리를 날려 5초가 걸렸던 테이블을 최적화해보자.

 

WHERE에서 endYear를 비교했으니, endYear에 INDEX(B+tree)를 걸어주자.

 

같은 쿼리인데도, 인덱스가 걸려 있으면 검색 시간이 0.041초로 100배 이상 빨라진 모습을 볼 수 있다.

 

이처럼 대용량의 데이터베이스를 다룰 때는 인덱스가 매우 중요하다.

 

어디에 인덱스를 적용해야 할까?

주요 대상은 JOIN에서 사용되는 외래키들과, WHERE에서 사용되는 애트리뷰트들이다.

 

예를 들어 위처럼

SELECT * FROM movie WHERE endYear>1800 AND endYear<1950;

쿼리에서는 endYear에 대해 인덱스를 걸어줘서 endYear에 대한 범위 검색을 할 때 속도를 높일 수 있다.

 

또한 문자열에 대해서도 인덱스를 적용할 수 있지만, 이 경우 일부 사용에서는 B+tree가 아닌 Fulltext인덱스를 걸어 주어야 한다.

 

SELECT * FROM movie WHERE primaryTitle LIKE 'Para%';

위처럼 데이터가 정렬된 상태를 이용할 수 있는 문자열 비교에는 B+tree로 이득을 볼 수 있지만,

SELECT * FROM movie WHERE primaryTitle LIKE '%rasi%';

처럼 정렬이 의미가 없는 검색은 모든 문자열을 전부 비교해야 하므로 B+tree로 이득을 볼 수 없다.

(문자열의 어느 위치에서 rasi패턴이 발견될지 모르기 때문이다)

 

또한 원본 값을 훼손시키는 경우에도 B+tree로 이득을 볼 수 없다.

SELECT * FROM movie WHERE UPPER(primaryTitle)='PARASITE';
SELECT * FROM movie WHERE ABS(endYear+2)>1800;

값을 새로 계산해야 하므로, 계산하기 전 만들어진 B+tree는 쓸모가 없어진다.

 

그렇다면 모든 애트리뷰트에 모든 종류의 인덱스를 만들어두면 되지 않을까?

그렇지 않다.

 

해쉬 인덱스건, 비트리건 간에 인덱스를 만드는 행위는 한 테이블의 값들에 대해 어떤 새로운 자료구조를 만드는 것이다.

 

따라서 인덱스를 만들 때 마다 테이블의 크기에 비례한 저장공간이 필요하게 된다.

 

또한 인덱스가 적용된 테이블에 데이터를 추가하거나 업데이트할 때, B+Tree나 해쉬 버켓도 업데이트되야 하므로 입력 속도에 Overhead가 발생한다.

 

일반적으로 인덱스를 사용할 때, 대용량의 데이터베이스를 최적화하기 위해 사용한다는 점을 생각하면

모든 애트리뷰트에 인덱스를 건다는 것은 매우 비효율적인 방법이다.

 

따라서 자주 사용되고, 시간이 오래 걸리는 비교/조인 연산에 사용되는 애트리뷰트를 찾아 적절히 인덱스를 걸어주는 것이 적절하다.