인덱스란
인덱스란 추가적인 쓰기 작업과 저장 공간을 활용해 검색 속도를 향상시키기 위한 자료구조입니다.
테이블의 인덱스를 추가할지 말지는 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 빠르게 만들어야 하는지에 따라 결정합니다.
데이터 저장 방식
인덱스는 크게 B-TREE, Hash 를 활용해 데이터를 저장학 있습니다. 일반적으로 NoSQL에서는 Hash를 활용하게 되고 RDBMS는 B-TREE를 활용합니다.
해시를 활용한 인덱싱
매우 빠른 검색을 지원하지만, 값의 일부만 검색하거나 범위 검색을 할 수 없습니다.
트리를 활용한 인덱싱
범위 검색이 가능하지만, 해시보다 등가 검색이 느립니다.
인덱스가 필요한 이유
빠른 탐색을 위해서
찾고자 하는 데이터가 저장된 테이블이 데이터가 정렬되어 있다면 일부분만 탐색해서 데이터를 찾을 수 있습니다.
배열과 이진 탐색 트리만 생각해도 O(n)과 O(logn)이라는 탐색 시간 복잡도 차이만 봐도 정렬된 상태에서 데이터를 찾는 것이 빠르다는 것을 알 수 있습니다.
병목 현상을 해결하기 위해서
인덱스로 설정 되지 않은 데이터를 찾아 수정하게 된다면 전체 테이블에 락이 걸리게 되고 성능에 영향을 줄 수 있습니다.
데드락을 피하기 위해서
데이터를 가져올 때, 인덱스 범위 만큼 락이 걸리기 때문에 범위를 줄여 데드락 영향을 최소화할 수 있습니다.
인덱스를 학습하는 이유
인덱스를 설정한다는 것은 공간 리소스를 포기하고 시간 리소스를 줄이기 위해 사용한다는 의미인데, 시간 리소스가 줄지 않는다면 의미가 없습니다.
조각화를 조심해야 한다.
MySQL 8.0 - Defragmenting a Table
- 페이지 분할 - 배열과 이진 탐색 트리에서 삽입 시간 복잡도는 배열이 빠르다는 것을 알 수 있듯이 정렬된 상태를 유지하기 위해서 인덱스를 재정렬하는 추가적인 리소스가 발생합니다.
- 삭제 마크- 인덱스가 삭제되면 삭제 마크를 설정하는데, 이러한 마킹이 많아지면 공간만 차지하고, 탐색에도 불리한 상황이 발생할 수 있습니다. (인덱스를 수정하는 경우도 인덱스를 삭제하고 추가하기 때문에 같은 문제가 발생합니다.)
페이지 분할과 사용하지 않는 데이터로 인해 인덱스의 조각화가 심해져 성능이 저하되게 됩니다.
인덱스 크기에 따라 메모리 효율 차이가 발생한다.
- 페이지 크기가 16KB라 가정할 때, 인덱스의 키 값의 크기가 28(16+12) 바이트라면 대략 하나의 페이지에 585개를 가지는 것이고, 읽을 때, 페이지 단위로 읽으니 585 개의 데이터를 가져와 탐색이 가능합니다.
- 만약 인덱스 기 값의 크기가 32(16+16) 바이트로 늘어났다면 372 개만 가져와 탐색하기 때문에 데이터가 히트될 확률이 적어져 IO가 더 발생할 가능성이 높습니다.
인덱스의 크기에 따라 페이지에 저장된 인덱스의 개수가 정해지고, 인덱스 전체 용량 크기가 정해집니다.
데이터 중복에 따라 효율 차이가 발생한다.
Table Full Scan은 Multi Block I/O 방식으로 순차적 접근(Sequential Access)하는데 반해, Index Range Scan은 Single Block I/O 방식으로 임의 접근(Random Access)합니다.
레코드를 하나 읽기 위해 매번 I/O가 발생하는 데, 읽을 데이터가 일정량을 I/O 빈도수가 Table Full Scan보다 늘어나게 됩니다.
인덱스 스캔보다 테이블 전체 스캔이 효율적일 수 있습니다.
데이터를 조회할 때, 테이블 전체 탐색에서 사용하는 Sequential IO가 인덱스 탐색에서 사용하는 Random IO 보다 빠르게 탐색하는 상황이 발생할 수 있습니다.
실제 OLTP(Online Transcation Proccessing) 성격의 시스템에서는 읽는 작업에서 인덱스를 사용하지 않고 풀 테이블 스캔을 사용하도록 유도할 때가 있습니다.
디스크 접근 방법
결론부터 말하자면 DBMS는 Sequential IO와 Random IO 두 가지 접근 방법이 있고, Sequential IO가 Random IO보다 효율적입니다.
2020년 기준 데이터를 읽기 위해 SSD에서 Random Access한다면 1,6000ns, 1MB 데이터를 Sequential Access한다면 4,9000ns가 걸립니다. 3 개 데이터를 읽기 위해 3 번의 Random Access 하는 시간과 1MB를 통째로 읽는 시간이 비슷하다는 의미입니다.
DBMS는 전체 테이블을 탐색할 때, Sequential IO가 발생하고, 인덱스를 활용해 테이블을 탐색할 때, Random IO가 발생하기 때문에 인덱스로 탐색하는 방법이 마냥 좋은 방법은 아닙니다.
- 순차 접근(Sequential Access)
- 물리적인 페이지에 저장된 데이터를 순차적으로 접근해 일정량 읽어 버퍼 풀에 적재합니다.
- 한 번의 IO 발생으로 일정량의 데이터를 많이 가져오기 때문에 효율적인 방식입니다.
- 임의 접근(Random Access)
- 필요한 데이터를 찾고 읽기 위해 한 번의 IO를 실행하게 됩니다.
- 한 번의 IO 발생으로 하나의 데이터만 읽기 때문에 비효율적인 방식입니다.
스토리지에 더 효율적으로 접근하기 위해
InnoDB에서는 캐시 히트를 활용해 속도를 높이기 위해 접근 방법마다 설정 값을 기준으로 레코드를 프리패칭해서 IO 비용을 줄이고 있습니다. 프리패칭하는 방식은 Linear read-ahead와 Random read-ahead가 있습니다.
- Linear read-ahead인 경우에는 MySQL에 설정된 값(
innodb_read_ahead_threshold)만큼 디스크에서 익스텐트 내부에 저장된 페이지를 순차적으로 읽게 된다면 다음 익스텐트를 프리패칭합니다. - Random read-ahead인 경우에는 MySQL에
Innodb_buffer_pool_read_ahead가 설정된다면 버퍼 풀에서 동일한 익스텐트의 13개의 연속된 페이지를 발견하면 익스텐트의 남은 페이지를 프리패칭합니다.
페이지 : DBMS에서 데이터를 읽고 작업하는 가장 기본 단위. 기본 값 16 KB로 설정되어 있습니다.
익스텐트 : 16KB 페이지 기준 1MB 크기로 페이지를 그룹화하는 단위를 말합니다. (페이지 크기에 따라 익스텐트가 조정됩니다.)
정리하자면
마지막으로
- 인덱스는 테이블 외부에 공간을 할당받아 저장되고, 항상 최신의 정렬 상태를 유지합니다. 이런 특성 덕분에 검색은 빠르지만 갱신 작업은 느립니다.
- 인덱스를 사용할 때, 제약조건이 많습니다. 제약조건을 잘 파악하고 사용할 수 있어야 합니다.
- DBMS는 Sequential IO와 Random IO 두 가지 접근 방법이 있고, Sequential IO가 Random IO보다 효율적입니다. 데이터베이스의 성능 개선 핵심은 Random IO를 최대한 줄이는 것입니다.
- MySQL에서는 IO 비용을 더 줄이기 위해 연관된 데이터를 익스텐트 단위로 프리패칭합니다.
참고 자료
