인덱스
인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조로, 내부 데이터 구조는 트리 구조로 되어 있다.
책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가하는데, 이는 마치 데이터베이스의 index와 같다
데이터베이스에서도 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕고 있다
인덱스를 활용하면, 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE의 성능이 함께 향상된다
이유는 해당 연산을 수행하려면 해당 대상을 조회해야만 작업을 할 수 있기 때문이다
UPDATE USER SET NAME='SUBIN' where NAME='KIM';
만약 index를 사용하지 않은 컬럼을 조회해야 하는 상황이라면,
전체를 탐색하는 Full Scan(전체를 비교하여 탐색)을 수행하기 때문에 처리 속도가 떨어진다.
인덱스의 관리
DBMS는 index를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다
그렇기 때문에 인덱스가 적용된 컬럼에 INSERT,UPDATE, DELETE가 수행된다면
각각 다음과 같은 연산을 추가적으로 해주어야 하며 그에 따른 오버헤드가 발생한다
- INSERT : 새로운 데이터에 대한 인덱스를 추가함
- UPDATE : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함
- DELETE : 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가함
인덱스의 장단점
장점
- 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다
- 전반적인 시스템의 부하를 줄일 수 있다
단점
- 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다
- 인덱스를 관리하기 위해 추가 작업이 필요하다
- 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다
만약 CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다. 이유 중 하나는 DELETE 와 UPDATE 연산 때문이다
앞서 설명한대로, UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고, 사용하지 않음 처리를 한다
만약 어떤 테이블에 UPDATE와 DELETE가 빈번하게 발생된다면 실제 데이터는 10만건이지만 인덱스는 훨씬 많이 존재하게 되어, SQL문 처리시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 것이다
인덱스를 사용하면 좋은 경우
- 규모가 작지 않은 테이블
- INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
- JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
- 데이터의 중복도가 낮은 컬럼
- 기타 등등
인덱스를 사용하는 것만큼이나 생성된 인덱스를 관리해주는 것도 중요하다
그러므로 사용되지 않는 인덱스는 바로 제거해주어야 한다
인덱스의 자료구조
인덱스를 구현하기 위해서는 다양한 자료구조를 사용할 수 있는데, 가장 대표적인 해시 테이블과 B+Tree에 대해 알아보도록 하자
해시 테이블(Hash Table)
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다
해시 테이블은 Key 값을 이용해 고유한 index를 생성하여 그 index에 저장된 값
을 꺼내오는 구조이다
해시 테이블 기반의 DB 인덱스는 (데이터 = 컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현한다
해시 테이블의 시간 복잡도는 O(1)이며 매우 빠른 검색을 지원한다
하지만, DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 해시가 등호 연산에만 특화되었기 때문이다
해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>,<)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다
즉, 예를 들면 “나는”으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받지 못하게 된다.
이러한 이유로 데이터베이스의 인덱스에서는 B+Tree가 일반적으로 사용된다.
B+Tree
B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조로, 하드 디스크상에 구축하기에 알맞은 데이터 구조를 가지고 있어 DB에서 많이 사용된다.
BTree에 의해 어떻게 탐색이 빨라지는가
BTree에 데이터를 삽입할 때는 일정한 규칙에 따라 삽입할 필요가 있는데, 그 규칙 덕분에 검색할 때 일부 노드를 순회하는 것만으로 자연스럽게 찾고자 하는 데이터에 도달하게 된다
B+Tree는 모든 노드에 데이터를 저장했던 BTree와 다른 특성을 가지고 있다
- 리프노드(데이터 노드)만 인덱스와 함께 데이터를 가지고 있고, 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스만 갖는다
- 리프노드들은 LinkedList로 연결되어 있다
- 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다
B+트리는 각 노드 내에 자식 노드로의 포인터만 가지고 있고 포인터 이외에 데이터로서의 실제 값 등은 제일 마지막인 잎 노드에만 가지고 있는 구조로 DB에 데이터를 저장하는데 더 최적화된 데이터 구조이다
데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다
이러한 이유로 BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화하였다
비록 B+Tree은 O(log n)의 시간 복잡도를 갖지만 해시 테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다
물론, Best Case에 대해 리프 노드까지 가지 않아도 탐색할 수 있는 BTree에 비해 무조건 리프 노드까지 가야한다는 단점도 있다
인덱스 효과의 예
대규모가 되면 될수록 인덱스를 준비해놓느냐 아니냐에 따라 차이가 나게 된다
개인적인 용도의 작은 애플리케이션 정도라면 인덱스를 전혀 사용하지 않아도 충분한 속도로 동작한다
데이터가 1000건 정도라면 오히려 트리를 먼저 순회하는 오버 헤드가 더 커서 그냥 처음부터 찾아 내려가는 편이 더 빠른 경우일 수도 있다
그러나, 크기가 커지면 인덱스 없이는 시작부터 액세스할 수 없는 상황이므로 인덱스는 중요하다
- MySQL
- MySQL은 레코드 총 건수를 보고 인덱스를 사용하지 않는 편이 더 빠르다고 판단되면, 사용하지 않는 최적화 작업을 내부에서 어느정도 수행한다
- MySQL에서는 인덱스를 걸어놓고 있는 컬럼을 대상으로 한 쿼리라도 던지는 SQL에 따라서는 인덱스가 사용되거나 사용되지 않기도 한다
- MySQL에서 alter table 명령 등으로 명시적으로 인덱스를 추가한 경우 이외에도 Primary Key, UNIQUE 제약을 건 컬럼에도 인덱스를 가지고 있다 (show index 명령으로 인덱스 내용 확인)
복수의 칼럼이 인덱스 작용의 대상이 되는 경우 하나의 칼럼만 인덱스로 사용될 것이다
select * from entry where url like ‘~~~’ order by timestampurl, timestamp 가 모두 index 걸려있을 때, 하나만 인덱스를 사용하고 나머지는 사용하지 않게 된다.
위의 경우 두개 모두 index로 태우려고 할 경우 (url, timestamp)를 쌍으로 한 복합 인덱스를 사용해야 한다
explain 명령에서 속도에 유의하라
자신이 SQL 수반하는 프로그램을 개발할 때 속도에 신경 쓰고자 할 때는 explain 명령으로 자신이 던지려고 하는 SQL에 제대로 인덱스가 작용하는지 여부를 확인하면서 개발하면 좋다
인덱스 작용법이라는 의미에서는 Extra 열도 중요하다
- where 이외에 Using filesord, Using temporary가 나올 경우가 있다.
- 각각 레코드 정렬에 외부(외부 파일을 사용한 정렬)이나 임시 테이블이 필요하다는 의미다
- 그다지 틀이 좋은 쿼리라고 할 수 없으므로 가능한 나오지 않도록 쿼리나 인덱스를 튜닝해갈 필요가 있다.
explain 명령 자체의 결과는 실제로 SQL을 던졌을 때의 평가가 아니기때문에 explain 명령어가 빠르다고 빠른 쿼리는 아니다
💡 왜 파일 정렬이나 임시 테이블을 사용하지 않는 편이 좋은가
- 임시 테이블은 내부 임시테이블 크기가 커서 디스크에 생성되면 성능 이슈가 발생하며, 임시테이블을 사용한 정렬이 FileSort에 해당되는데 이는 레코드가 많아질수록 쿼리의 응답 속도가 현저히 떨어지게 된다
마무리
인덱스에 대해 간단히 핵심만 다루고 있지만, PK, Index에 대해 자세히 알고 있는 것이 중요하다
더 알아보기
임시 테이블(Using Temporary)
MySQL 엔진이 스토리지 엔진으로부터 받아온 레코드를 정렬하거나 그룹핑 할 때는 내부적인 임시 테이블을 사용한다
MySQL 엔진이 사용하는 임시 테이블은 처음에는 메모리에 생성됐다가 테이블의 크기가 커지면 디스크로 옮겨진다
원본 테이블의 스토리지 엔진과 관계없이 임시 테이블이 메모리를 사용할 때는 MEMORY 스토리지 엔진을 사용하며,
디스크에 저장될 때는 MyISAM 스토리지 엔진을 이용한다
임시 테이블이 필요한 경우
- ORDER BY와 GROUP BY에 명시된 칼럼이 다른 쿼리
- ORDER BY나 GROUP BY에 명시된 칼럼이 조인의 순서상 첫번째 테이블이 아닌 쿼리
- DISTINCT와 ORDER BY가 동시에 존재하는 경우 또는 DISTINCT가 인덱스로 처리되지 못하는 쿼리
- UNION이나 UNION DISTICT가 사용된 쿼리
- UNION ALL이 사용된 쿼리
- 쿼리의 실행 계획에서 select_type이 DERIVED인 쿼리
해당 6가지 중 1~3번째 경우에는 Extra 칼럼에 “Using Temporary”가 표시되며, 4~6번째 경우에는 Extra 칼럼에 “Using Temporary”가 표시되지 않지만 임시테이블이 사용된다
주의 사항
내부 임시 테이블이 크기가 커서 디스크에 생성되면 성능 이슈가 발생한다
내부 임시 테이블이 디스크에 생성되었는지 여부를 파악하려면 아래의 명령어로 가능하다
SHOW SESSION STATUS LIKE 'Create_tmp%';
해당 쿼리의 결과로 생성된 임시 테이블의 상태를 파악할 수 있다
만약 처리해야하는 레코드 건수가 100만 건이라고 가정한다면, 해당 건의 데이터 디스크에 저장된다면 큰 부하가 발생하게 되므로 각별히 주의를 기울여야 한다
드라이빙 테이블 정렬(Using Filesort)
MySQL의 정렬 처리는 크게 2가지로 나뉜다
- index를 이용한 정렬
- File sort(”Using filesort”)
인덱스를 사용할 수 있는 경우
- ORDER BY에 명시된 칼럼이 제일 먼저 읽는 테이블에 속해야 한다
- ORDER BY절의 순서가 인덱스와 일치해야한다
- WHERE 절에 첫 번째 읽는 테이블에 대한 조건이 있다면, ORDER BY절도 같은 인덱스를 사용할 수 있어야 한다
인덱스를 사용하는 정렬은 완벽한 조건을 요구하는 만큼 처리가 빠르다
인덱스의 값이 정렬되어 있기때문에 해당 인덱스를 읽기만 하면 된다
MySQL은 인덱스를 통해 정렬할 수 없다면 FileSort를 사용한다
위에서의 임시 테이블을 사용한 정렬도 FileSort에 해당한다
FileSort는 레코드가 많아질수록 쿼리의 응답 속도가 현저히 떨어지게 된다
File Sort를 사용하는 경우
- 드라이빙 테이블만 정렬 (”Using filesort”)
- 임시 테이블을 이용한 정렬 (”Using temporary, Using filesort”)
드라이빙 테이블만 정렬된다는 방식은 조회하는 테이블 중 먼저 액세스되는 테이블만 SortBuffer에서 정렬해서 나머지 테이블과 조합하는 방식이다.
이 경우 SortBuffer로 테이블을 하나 옮겨서 정렬하는 작업이 필요하지만 임시 테이블을 이용하는 방법보다는 낫다
드라이빙 테이블만 정렬하는 방법을 사용할 수 없다면 임시 테이블을 사용해야 한다
임시 테이블을 이용한 정렬은 2개 이상의 테이블을 조인해서 그 결과를 전부 임시 테이블에 넣어서 정렬하는 방식이다
임시 테이블을 이용한 정렬은 모든 테이블의 결과를 임시 테이블에 넣고 정렬을 수행하므로 가장 느리다
특히, 레코드가 많아지면 임시 테이블이 디스크에 저장되면서, 대규모 서비스에서 치명적인 I/O 부하가 발생한다
이 경우 Application Layer나 Presentation Layer에서 정렬을 해서 뷰에 노출하는 것을 고려할 수 있다
🍀 참조
SQL - Using Temporary, Using Filesort 정리 (+ 임시 테이블, 파일 정렬)