인덱스가 무엇인지, B-Tree Index, Hash Index 등에 대해 알고있다는 가정하에 작성
인덱스는 왜 쓰는가?
인덱스는 '인덱스가 검색 범위를 제한시켜주기 때문에' 빠르게 데이터를 검색할 수 있게 해준다.
인덱스가 왜 어떻게 검색 범위를 제한해주나?
인덱스는 항상 정렬이 되있기 때문에 라고 생각할 수 있지만, 그건 특정 인덱스에 한정된 이야기다. 검색범위를 제한해주는 방법은 어떤 인덱스를 사용하느냐에 따라 달라진다.
B-Tree 인덱스
- B-Tree 인덱스는 항상 정렬된 상태를 유지한다. (장점) 항상 정렬된 상태를 유지하기 위해서는 삽입과 삭제시에 정렬이 발생한다. (단점)
- 이 경우는 정렬된 상태로 검색 범위를 제한시킬 수 있는게 맞다.
Hash Index
- 해시 인덱스는 정렬되어 있다고 볼 수 없다.
- 다만 해싱된 데이터 값에 따라 저장될 버킷 위치를 정하기 때문에 빠른 속도로 검색 영역을 제한할 수 있다. 동등비교(=) 에서 효과적이다.
- 정렬할 필요가 없으니 삽입/삭제가 빠를 수 있다.
어떤 경우에 사용하면 좋을까?
B-Tree의 경우 대부분의 DBMS에서 기본적으로 사용한다. 위에서 언급한대로 항상 정렬된 상태를 유지하기 때문에 범위검색을 할때 유용하기 때문이다.
- loose 인덱스 스캔
- 다중 컬럼 인덱스를 사용할 수 있다.
해시 인덱스는 메모리기반의 테이블에 주로 사용된다. 디스크 기반 대용량 테이블용으로는 적합하지 않다. 왜냐하면 정렬된 결과를 가져올 수 없기 때문이다.
- MySQL InnoDB에서는 메모리 버퍼 풀에서 레코드 검색을 위한 어댑티브 해시 인덱스로 사용
버킷은 링크드리스트를 저장하는 배열이라고 생각하면 된다. 버킷의 위치를 정한다는 말은 데이터를 해싱해서 적절한 배열 인덱스를 구하는 것이다.
다른 자료구조도 많은데(레드 블랙 트리 등), B-Tree를 쓰는 이유
다중 컬럼 인덱스에서 선정 기준
B-Tree 인덱스의 다중 컬럼 인덱스는 컬럼 순서가 매우 중요하다. 순서에 따라 해당 인덱스를 활용하지 못 할 수도 있기 때문이다.
반드시 왼쪽에 있는 컬럼이 사용되어야 그 오른쪽의 컬럼도 사용될 수 있다.
그럼 어떤 기준으로 순서를 정하는게 좋을까? (단일 컬럼 인덱스에도 적용되는 해당되는 이야기)
Cardinality(기수성)
카디널리티는 유니크한 값의 개수를 말한다.
- cardinality(기수성)가 높은 컬럼이 앞에와야 검색 효율이 좋다.
- 기수성이 높은 컬럼이 앞에오고 컬럼이 범위를 크게 줄여주고, 낮은 컬럼이 뒤에오면 필터링 조건으로 사용된다.
남자이고 이름이 A로 시작하는 사람을 가져와보자.
예를 들어 100명 중 A로 시작하는 사람은 10명, 전체 남자는 70명이다. 그리고 A로 시작하는 남자는 5명이다.
select NAME, GENDER from EMPLOYEES where NAME like 'A%' and GENDER='male'
- (NAME, GENDER) 인덱스 A로 시작하는 사람 10명 목록을 가져온다. 그리고 그 중 남자만 필터링 하면 된다.
- (GENDER, NAME) 인덱스 성별이 남자인 사람을 70명 가져온다. 그 중 A로 시작하는 사람을 찾는다. => 성별로 가져온 70명 대부분이 버려진다.
Selectivity (선택도)
선택도란 얼마나 값을 잘 가져오냐를 말하는데, 1이면 유니크하다는 의미다. 20~25% 를 넘어서면 그 인덱스를 사용하지 않는게 좋다고 한다.
- Cardinality의 (NAME, GENDER) 인덱스는 100명중 10명만 읽고 5명을 찾아온다. 즉 전체의 10%만 읽었다. 그 중 50% 만 필터링되었다.
- (GENDER, NAME) 인덱스 예제를 보면 전체 100명중 무려 70%를 읽었다. 그 중 5명만 찾은거니 70명중에서도 35% 만 필터링에서 살아남았다. 비효율 적이다.
활용도
남자 10명을 이름 오름차순으로 가져온다고 가정했을 때
이전 예제와 차이는 여기선 이름을 오름차순으로 가져온다는 것이다. select NAME, GENDER where GENDER='male' order by NAME LIMIT 10 기수성 예와 반대로 (GENDER, NAME) 인덱스를 더 효율적으로 사용한다.
- where -> order by 순으로 진행된다.
- 그러므로 (NAME, GENDER) 의 경우 앞선 where 절에서 사용되지 못하고 order by 에서 왼쪽 컬럼 'NAME' 만 사용되기 때문이다. 반쪽짜리가 된다.
- 그러나 (GENDER, NAME) 의 경우 where 에서 성별을 -> order by에서 이름 순으로 사용하기 때문에** 지정한 인덱스의 컬럼을 모두 사용**한다. 또
SELECT NAME, GENDER이므로 커버링 인덱스가 사용되어 효율적이라고 볼 수 있다.
그러나 (GENDER, NAME) 이 인덱스가 얼마나 활용될 수 있을지 고민해봐야 한다. 이 인덱스는 이름순으로 특정 성별을 찾는 아주 특정한 케이스에만 활용될 수 있다.
인덱스는 곧 디스크 용량을 차지하고 메모리를 차지하기 때문에 크기가 큰 테이블인데 활용도가 떨어지면 굳이 이 인덱스(GENDER, NAME)을 쓸 필요는 없을 것 같다.
- NAME 만 조건으로 사용될 때도 활용되지 못하고, GENDER 만 조건으로 활용할 경우 선택도가 50% 인데, 이 경우 인덱스를 사용하지 않는 편이 낫다.
(NAME, GENDER) 각각의 케이스 생각
남자 10명을 이름 오름차순으로 가져온다고 가정했을 때
BEST
Aaaa - Male Aaab - Male Aaac - Male ... 이런 식으로 성별이 연달아 남자만 나오는 경우. 10건만 읽으면 된다.
WORST
이름순 상위 50명이 모두 여자인 경우. Aaaa - Female Aaab - Female Aaac - Female ... 옵티마이저가 인덱스를 정방향으로 읽을지 역방향으로 읽을지 결정할 수 있다.
- 그래서 만약 Z로 시작하는 남자 10명을 찾는 거라면 역순으로 읽으면 10건만 읽으면 된다.
- 그런데 이 경우는 이름은 정방향, 성별은 역방향이기 때문에 최악의 케이스다.
MySQL8 버전은 내림차순 인덱스도 지원을 해서 (NAME ASC, GENDER DESC) 같은 인덱스를 사용할 수 있다.
- 그러나 이렇게 했을 때 과연 최악의 케이스가 해결이 될까?
- 만약 남자 10명이 아니라, 이번엔 여자 10명을 찾는다면? 똑같이 최악의 케이스가 나온다.