[ Database - Intermediate ] - Index

SELECT *
FROM customer
WHERE first_name = "Minsoo';

(인덱스가 걸려있지 않은 상황)이런식으로 Customer 테이블을 full scan(=table scan)을 통해 tuple을 찾으면 $O(N)$의 시간 복잡도가 걸릴 것입니다. 그리고 Customer 테이블의 로우 수가 많아지면 많아질 수록 이는 비효율적인 scan이 되겠죠.

 

이는 B-tree based index를 적용해서 table scan을 하게되면 $O(logN)$으로 로우를 찾을 수 있습니다. 즉 해당 쿼리문이 더 빠르게 처리될 수 있습니다. 이는 상황에 따라서 조건을 만족하는 튜플(들)을 빠르게 조회하거나 바르게 정렬, 그룹핑하기 위해 사용됩니다.

 

MySQL에서 Indexing 해보기

만약 위와같은 Player 테이블이 있다고 해보겠습니다. 우선 name을 통해 player를 조회하는 쿼리문과, team_id, backnumber를 통해 조회하는 쿼리문이 있습니다. 

 

우선 name은 중복이 가능한 attribute이고, team_id, backnumber는 unique한 attribute입니다. 이를 위해서 index를 걸어주기 위한 SQL문이 좀 다른데 위와같이 후자에만 Unique index를 적고 On 뒤에는 인덱스 대상 attributes를 적어주면 됩니다.

 

그리고 위와같이 Table을 만들때 Index를 명시해줄 수 있습니다. 그리고 team_id_backnumber_idx와 같이 여러개의 attributes로 이루어진 index를 multicolumn index, composite index라고 합니다. 또한 대부분의 RDBMS에서는 PK를 생성할 때 index를 자동생성해줍니다. 

 

B트리 기반 인덱스 동작 방식

Index(a)와 같이 a attribute를 인덱싱하는 별도의 테이블이 존재합니다. 이는 B트리 기반이며 정렬되어 있습니다. 그리고 ptr은 실제 Members테이블을 가리키는 포인터라고 할 수 있습니다. 만약 WHERE a = 9; 라는 condition이 있다면 Binary Search를 통해 인덱스를 활용해 Members의 튜플을 검색할 것입니다. ( 이 Index 테이블을 만드는 방식이 B트리 기반입니다 )

 

만약 조건에 a, b 2개가 있으면 어떻게 될까요? 

바로 똑같이 Binary Search를 하고, 실제 a=7이면 Members테이블에 가서 b의 값을 확인한 다음에 95인지를 확인합니다. 다만, 여기서 주의해야할 점은 Binary Search를 하면서 a=7이더라도 그 윗부분, 아랫부분에서 해당 로우가 있어서 배재할 수 없다는 것입니다. 

 

이를 정리해보면, a에 대해서는 인덱스를 통해 빠르게 찾을 수 있지만, b 조건에서는 실제로 하나하나 다 가보면서 full scan을 해야한다는 것입니다. 이 또한 매우 비효율적입니다.

 

그래서 실제로 이러한 쿼리를 빠르게 처리하려면 CREATE INDEX(a, b) 이렇게 둘을 묶은 인덱스가 필요로 됩니다. 그리고 또한, (a, b)이렇게 인덱스를 만들었다면 우선순위는 a가 b보다 높게 됩니다. 

즉 위와같은 상황에서, Binary Search가 앞선 상황과 똑같이 진행됩니다. 이 상황에서도 a=7, b=95를 찾았다 하더라도 끝내서는 안되고 그 앞쪽, 뒷쪽에 대해서도 scan을 해주어 만족하는 로우를 다 찾아주어야 합니다. 어차피 위 경우에서는 아래는 a=9여서 그 아래는 무시, 위는 b=80이여서 그 위는 싹 무시여서 하나만 찾을 수 있게 됩니다.

 

그리고 만약에 위 테이블에서 b 하나만을 통해 조회를 한다고 하면, b는 우선순위가 a보다 낮다고 했습니다. 즉 정렬이 되어있지 않기 때문에 실제로 값을 빠르게 찾을 수 없습니다. 즉 그냥 full scan 하는것과 같은 성능이 나옵니다. 이를 해결하기 위해서는 b에 대한 인덱스를 따로 만들어 주어야 합니다.

 

Index 예제

위 와같이 인덱스가 걸려있는 상황에서 쿼리문을 평가해보도록 하겠습니다. 우선 위 2개는 (team_id, backnumber)에 대해 인덱싱 되어 있으므로 매우 바르게 검색될 겁니다. 하지만 3번째는 backnumber를 condition으로 가지는데 이는 위에서 말 한것처럼 우선순위가 낮기 아서 정렬이 안되어 있으므로 fullscan을 하는 것과 같은 성능이 나올 것입니다. 그 아래는 team_id=110는 빠르게 찾을 것이지만 backnumber = 7이 OR로 연결되어 있으므로 이 또한 fullscan을 하는 것과 같은 성능이 나올 것입니다. 이를 빠르게 인덱싱하려면 backnumber에 대한 인덱스를 붙혀주어야 겠죠??

 

그리고 위와같은 상황에서 쿼리가 어떤 인덱스를 사용할지 궁금하면, EXPLAIN 을 써주면 됩니다. 그럼 실제로 사용된 인덱스를 표시해주게 됩니다. 이는 DBMS에 있는 optimizer가 알아서 적절하게 index를 선택합니다. 하지만 optimizer가 잘못된 index를 사용하고 있어서 쿼리의 성능이 안좋게 나올 수 있습니다. 따라서 USER INDEX (backnumber_idx)나 FORCE INDEX (backnumber_idx) 이렇게 직접 사용될 idx를 지정 혹은 강제할 수 있게됩니다.

 

Index는 막 만들어도 괜찮을까?

index를 위와같이 사용하면 총 4개의 인덱스용 테이블이 존재하게 됩니다. 그리고 유의해야할 점이 table에 write할 때마다 index에도 변경이 발생한다는 점에 유의해야 합니다. 즉 오버헤드가 발생할 수 있습니다. 그리고 추가적인 저장공간을 인덱스 테이블이 차지하게 됩니다. 

 

즉 불필요한 index는 만들면 오히려 오버헤드와 저장공간 낭비로 이어지게 됩니다. 위 상황에서 INDEX(team_id)를 추가적으로 만들면 이

는 오히려 비효율적인 것이겠죠??

 

Covering Index

그리고 위와같이 team_id로 team_id, backnumber를 player 테이블에서 가져오는 SQL문을 보겠습니다. 이는 tema_id를 Binary Search로 찾아서 실제 player 테이블에 가서 backnumber를 확인할 것입니다. 하지만 이는 (team_id, backnumber)를 톻애 인덱싱 되어있으므로 실제 player 테이블까지 가지 않아도 됩니다. 이는 오히려 성능 저하로 이어지게 되겠죠??

 

이처럼 조회하는 attrubute(s)를 index가 모두 cover할 때 조회 성능이 더 빨라지게 됩니다. 이는 어떻게 보면 하나의 기술 stack입니다.

 

Hash Index

B-tree 인덱스방식보다 Hash index는 O(1)의 시간 복잡도로 데이터를 조회할 수 있게 됩니다. 하지만 이는 rehashing즉 해시 테이블을 증가시켜주는 작업이 트래픽이 몰릴 때 매우 까다로운 작업이 됩니다. 그리고 이는 equiality 비교만 가능하고 range에 대한 비교는 불가능합니다. 이는 해시 기반이기 때문에 당연합니다. 또한 hash index로 multicolumn index의 경우 전체 attributes에 대한 조회만 가능하다는 한계점이 존재하기도 합니다. 그래서 보통은 B-tree 기반의 index를 많이 사용한다고 합니다.

 

Full scan 이 더 좋은 경우

만약 조회하려는 데이터가 테이블의 상당 부분을 차지할 때 오히려 Full scan이 더 빠릅니다. 이 또한 RDBMS의 optimizer가 이를 결정합니다. 

 

그 외에도 order by나 group by에도 index가 활용될 수 있습니다. 또한 foregin key에는 index가 자동으로 생성되지 않을 수 있습니다. 그 이유는 join과 관련된 성능이슈 때문입니다. 또한 이미 데이터가 몇 백만건 이상 있는 테이블에 인덱스를 생성하는 경우 시간이 몇 분 이상 소요될 수 있고 DB 선응이 안좋은 영향을 줄 수 있게 됩니다.