[인덱스] 복합인덱스 활용, 인덱스 스캔방향에 대해
프로젝트 도중 인기여행지, 여행지 지역 카테고리에 따른 데이터 반환이 느려 이를 해결했다.
여행지 지역카테고리에 대해서는 (도,시)의 복합인덱스를 사용하였다.
복합인덱스
여러개의 컬럼을 함께 사용하여 만든 인덱스.
효과적인 이유?
다음 예를 보자
SELECT *
FROM TABLE
WHERE columnA = 1 AND columnB = 1
이때 복합인덱스가 아닌, A 혹은 B로 인덱스를 형성한다면 DB에서 카디널리티가 높은 컬럼에 대해 인덱스를 활용한다. 그 후, 나머지 조건에 대한 필터링은 서버 엔진으로 전달해서 실행하는데 이는 cpu, 메모리 리소스를 더 많이 사용한다.
A의 인덱스를 활용했고 A = 1에 관한 데이터가 1000개 라면, 1000개의 데이터를 얻고 서버엔진에서 B = 1에 대해 필터링을 한다는 것이다.
복합인덱스를 사용한다면, 트리에서 A = 1 and B = 1모두 만족하는 리프노드 들을 반환할 것이므로 더 성능이 좋아짐을 짐작할 수 있다.
파일 소트
인기여행지, 여행지 지역카테고리 모두 특정 컬럼을 기준으로 내림차순 정렬을 하여야 했다.
ORDER BY columnC DESC;
하지만 이는 인덱스 없이는 느리다.
왜 느린가?
동작방식은 테이블을 읽고 정렬에 필요하지 않은 컬럼까지 전부 읽어서 sort buffer에 담고 정렬을 수행한다.
그리고 정렬이 완료되면 정렬 버퍼의 내용을 그대로 클라리언트로 넘겨준다.
정렬알고리즘은? : std::stable_sort
MySQL서버에서 정렬을 수행할때 위의 라이브러리 함수를 사용한다. 리눅스 서버에서 사용하는 GNU C++의 stl에서는 퀵소트와 힙소트를 복합적으로 사용한다.
시간복잡도가 O(nlogn)으로 느릴것이다.
따라서 인덱스를 활용한다면 시간을 굉장히 빠르게 만들수 있다. 노드 몇번만 타면 되는 것이다.
Descending index
내가 필요한 데이터는 역순 정렬이다. 예를들어 좋아요 수가 많은 순서대로 정렬이 필요하다. 하지만 MySQL에서 인덱스를 통해 B Tree를 생성하면 오름차순으로 정렬이 되어있다.
따라서 ORDER BY DESC로 하면 Backward Index Scan이 일어난다.
Backward Index Scan이 왜 느린가?
InnoDB에서는 다음이유로 느리다.
- 페이지 잠금이 Forward Index Scan에 적합한 구조다
MySQL에서 인덱스 B Tree에 leaf node 에는 더블 링크드 리스트 구조가 있어 양항향으로 탐색할 수 있다.
하지만 데드락 방지를 위하여 잠금은 정방향으로만 가능하다. 역방향으로는 복잡한 처리과정을 거쳐 느린 것이다.
- 페이지 내에서 인덱스 레코드는 단방향으로만 연결된 구조다.
더블 링크드 리스트 구조로 되어있는 페이지 구조와는 달리 페이지 내부에 있는 레코드들은 싱글 링크드 리스트 구조로 되어있다.