8.3 B-Tree 인덱스
B-Tree 인덱스는 데이터베이스의 인덱싱 알고리즘 중 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다. 하지만 아직도 가장 범용적인 목적으로 사용되는 알고리즘이다.
B는 Binary의 약자가 아니라 Balanced를 의미한다.
B-Tree는 컬럼의 원래 값을 변형시키지 않고 (물론 값의 앞부분만 잘라서 관리하지만) 인덱스 구조체 내에서는 항상 정렬된 상태로 유지한다.
8.3.1 구조 및 특성
B-Tree는 트리 구조의 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식 노드가 붙어 있는 형태이다. 트리 구조의 가장 하위에 있는 노드를 리프 노드라고 하며, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간의 노드를 브랜치 노드라고 한다.
데이터 베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리하는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있다.
아래 사진 처럼 인덱스의 키 값은 모두 정렬되어 있지만 데이터 파일의 레코드는 정렬되어 있지 않고 임의의 순서로 저장되어 있다. 많은 사람들이 데이터 파일의 레코드는 INSERT된 순서대로 저장되는 것으로 생각하지만 그렇지 않다. 레코드를 삭제하거나 변경하지 않고 INSERT만을 수행한다면 그럴 수도 있지만 레코드가 삭제되어 빈 공간이 생기면 그 다음의 INSERT는 가능한 삭제된 공간을 재사용하도록 DBMS가 설계되어 있기 때문에 항상 INSERT된 순서대로 저장되는 것은 아니다.
B-Tree 인덱스의 구조
대부분의 RDBMS의 데이터 파일에서 레코드는 특정 기준으로 정렬되지 않고 임의의 순서로 저장된다.
하지만 InnoDB 테이블에서 레코드는 클러스터링 되어 디스크에 저장되므로 기본적으로 프라이머리 키 순서로 정렬되어 저장된다.
B-Tree의 리프 노드와 테이블 데이터 레코드(InnoDB)
MyISAM 스토리지 엔진에서 인덱스의 구조는 프라이머리 키에 의한 클러스터링 없이 데이터 파일이 힙(Heap) 공간처럼 활용된다. 즉 MyISAM 테이블에 레코드는 프라이머리 키 값과 무관하게 INSERT되는 순서대로 데이터 파일에 저장된다. 그리고 MyISAM 테이블에 저장되는 레코드는 모두 ROWID라는 물리적인 주솟값을 가지는데, 프라이머리 키와 세컨더리 인덱스는 모두 데이터 파일에 저장된 레코드의 ROWID 값을 포인터로 가진다. InnoDB 스토리지 엔진을 사용하는 테이블에서는 프라이머리 키가 ROWID의 역할을 한다.
4.3.3 참조
→ 두 스토리지 엔진의 인덱스에서 가장 큰 차이점은 세컨더리 인덱스를 통해 데이터 파일의 레코드를 찾아가는 방법이다.
1.
MyISAM 테이블은 세컨더리 인덱스가 물리적인 주소를 가진다.
2.
InnoDB 테이블은 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가진다.
위의 이유 때문에 InnoDB는 인덱스에 저장되어 있는 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 저장되어 있는 레코드를 읽는다.
→ 즉, InnoDB 스토리지 엔진에서는 모든 세컨더리 인덱스 검색에서 데이터 코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한 번 검색해야 한다.
8.3.2 B-Tree 인덱스 키 추가 및 삭제
인덱스 키 추가
새로운 키 값이 B-Tree에 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다. B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree 리프 노드에 저장한다. 리프 노드가 꽉 차서 더는 저장할 수 없는 경우에는 리프 노드가 분리되어야 하는데 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다.
MyISAM이나 MEMORY 스토리지 엔진을 사용하는 테이블에서는 INSERT 문장이 실행되면 즉시 새로운 키 값을 B-Tree 인덱스에 반영한다. 하지만 InnoDB 스토리지 엔진은 이 작업을 조금 더 지능적으로 처리하는데 필요하다면 인덱스 키 추가 작업을 지연시켜 나중에 처리할 수 있다. 하지만 프라이머리 키나 유니크 인덱스의 경우에는 중복 체크가 필요하기 때문에 즉시 B-Tree에 추가되거나 삭제한다.
4.2.10 체인지 버퍼 참조
인덱스 키 삭제
삭제는 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아 그냥 삭제 마크만 하면 작업이 완료된다. 이렇게 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재활용할 수 있다. 인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 이 작업 역시 디스크 I/O가 필요한 작업이다.
MySQL 5.5버전 이상의 InnoDB 스토리지 엔진에서는 이 작업 또한 버퍼링되어 지연 처리될 수 있다. 이때 지연된 인덱스 키를 삭제 또한 사용자에게는 악영향을 끼치지 않고 MySQL 서버가 내부적으로 처리한다.
인덱스 키 변경
인덱스의 키 값은 그 값에 따라 저장될 리프 노드의 위치가 결정되므로 B-Tree의 키 값이 변경되는 경우에는 단순히 인덱스상의 키 값만 변경되는게 아니라 기존 키 값을 삭제한 후 다시 새로운 키 값을 추가하는 형태로 처리된다.
인덱스 키 검색
인덱스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행하는데 이 과정을 트리 탐색이라고 한다. B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있다. 부등호 비교 조건에서는 인덱스를 활용할 수 있지만 인덱스를 구성하는 키 값의 뒷부분만을 검색하는 용도로는 인덱스를 사용할 수 없다.
인덱스를 이용한 검색에서 중요한 사실은 인덱스의 키 값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree의 빠른 검색 기능을 사용할 수 없다. 이미 변형된 값은 B-Tree 인덱스에 존재하는 값이 아니다. 따라서 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree의 장점을 이용할 수 없다.
InnoDB 스토리지 엔진에서 지원하는 레코드 잠금이나 넥스트 키락(갭락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현되어 있다. 때문에 UPDATE나 DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠근다. 그만큼 InnoDB에서는 인덱스의 설계가 중요하다.
8.3.3 B-Tree 인덱스 사용에 영향을 미치는 요소
인덱스 키 값의 크기
InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(Page) or 블록(Block)이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다. Page는 InnoDB의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위기도 하다.
이진트리는 각 노드가 자식 노드를 2개만 가지는데, DBMS의 B-Tree가 이진 트리라면 인덱스 검색이 상당히 비효율적일 것이다. 일반적으로 DBMS의 B-Tree는 자식 노드의 개수가 가변적인 구조이다. 그리고 B-Tree의 자식노드의 개수는 인덱스 페이지 크기와 키 값의 크기에 따라 결정된다.
InnoDB의 페이지 크기 기본값은 16KB, 인덱스의 키가 16바이트, 자식 노드의 주소 영역이 12바이트로
구성된다고 가정하면 다음의 인덱스 페이지가 구성된다.
이 경우, 하나의 인덱스 페이지에는 16*1024/(16+12) = 585개의 키를 저장할 수 있다.
키 값의 크기가 두 배인 32바이트로 늘어났다고 가정하면,
하나의 인덱스 페이지에는 16*1024/(32+12) = 372개의 키를 저장할 수 있다.
인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미한다. 인덱스를 캐시해 두는 InnoDB의 버퍼 풀이나 MyISAM의 키 캐시 영역은 크기가 제한적이기 때문에 하나의 레코드를 위한 인덱스 크기가 커지면 커질수록 메모리에 캐시해 둘 수 있는 레코드 수는 줄어든다. 이는 메모리의 효율이 떨어지는 결과를 가져온다.
B-Tree 깊이
B-Tree의 깊이는 MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제이다.
B-Tree 깊이가 3인 경우 최대 몇 개의 키 값을 가질 수 있는가
•
키 값이 16바이트인 경우 : 최대 2억(585 * 585 * 585)개 정도
•
키 값이 32바이트인 경우 : 5천만(372 * 372 * 372)개 정도
인덱스 키 값의 크기가 커질수록 하나의 인덱스 페이지에서 담을 수 있는 인덱스 키 값의 개수는 적어지고 그로 인해 노드들이 쪼개어지며 B-Tree의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다.
선택도(기수성)
인덱스에서 선택도(Selectivity) 또는 기수성(Cardinality)은 거의 같은 의미로 사용되는데 모든 인덱스 키 값 가운데 유니크한 값의 수를 말한다. 전체 인덱스 키 값은 100개인데 그중에서 유니크한 값의 개수가 10개라면 기수성은 10이된다.
키 값 가운데 중복된 값이 많아지면 많아질수록 기수성은 낮아지며 동시에 선택도 또한 떨어지게 된다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리될 수 있다.
읽어야 하는 레코드의 건수
인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 발생한다.
만약 테이블에 레코드가 100만건이라는 가정하에 50만건을 읽어야 한다면 인덱스를 통해 읽을 것인지 인덱스를 거치지 않고 읽을 것인지 정해야한다. 이때 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도의 비용을 발생시킨다고 예측한다.
인덱스를 통해 읽어야할 레코드의 수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 통해 읽지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 가져오게 하는것이 효율적이다.
만약 이렇게 많은 레코드를 읽을 때 강제로 인덱스를 사용하도록 힌트를 추가해도 성능상 이점을 얻을 수 없다. 물론 이러한 작업은 MySQL의 옵티마이저가 기본적으로 힌트를 무시하고 테이블을 직접 읽는 방식으로 처리하게 된다.
8.3.4 B-Tree 인덱스를 통한 데이터 읽기
인덱스 레인지 스캔
인덱스 레인지 스캔은 범위가 결정된 인덱스를 읽는 방식으로, 정해진 범위만 접근하면 되므로 이 방식은 다른 방식들보다 빠르다. 일반적으로 인덱스를 탄다고 하면 인덱스 레인지 스캔으로 데이터를 조회하는 것을 의미한다.
예를 들어 다음의 쿼리를 실행했다고 하자.
mysql> SELECT * FROM employee WHERE name BETWEEN 'Lemon' AND 'Mango';
SQL
복사
해당 테이블의 name 컬럼에 인덱스가 걸려있다고 할 때, 쿼리의 실행 순서를 정리하면 다음과 같다.
1.
(인덱스 탐색) 인덱스의 조건을 만족하는 값이 저장된 위치를 찾는다.
2.
(인덱스 스캔) 시작 위치부터 필요한 만큼 인덱스를 순서대로 읽는다.
3.
(랜덤 I/O) 읽어들인 인덱스와 PK를 이용해 최종 레코드를 읽어온다.
먼저 루트 노드에서 시작해서 브랜치 노드를 거쳐 원하는 인덱스가 저장된 리프 노드(페이지8)로 이동한다. 읽고 쓰는 단위는 페이지이므로 원하는 인덱스를 찾기 위해서는 8번 페이지의 처음부터 시작해서 시작점(Lemon)을 찾는데, 이를 탐색이라고 한다.
시작점을 찾았으면 이후에는 순서대로 검색 범위의 마지막 인덱스(Mango)까지 읽으면 되는데, 이를 스캔이라고 한다. 이것이 가능한 이유는 인덱스가 정렬되어 있기 때문이며, 스캔을 하다가 페이지의 끝에 도달하면 페이지 간의 링크를 이용해 다음 페이지(9)로 넘어간다. 그리고 계속해서 스캔하다가 마지막 인덱스를 찾으면 지금까지 읽은 레코드를 반환하고 쿼리를 종료한다.
만약 쿼리가 인덱스나 PK 외의가 아닌 레코드의 다른 값을 필요로 한다면 테이블로부터 레코드를 조회해와야 하며, 이때는 PK를 이용해 랜덤 I/O를 통해 레코드들을 조회해야 한다. 만약 인덱스나 PK만 필요로 한다면 해당 작업은 실행되지 않는데, 이를 커버링 인덱스라고 한다. 커버링 인덱스는 디스크 랜덤 I/O 작업을 줄일 수 있어서 성능이 훨씬 뛰어나다.
다시 한번 설명하지만, 인덱스에 PK가 저장되는 것은 MySQL의 InnoDB가 클러스터 테이블이기 때문에 이러한 구조를 갖는 것이다. 다른 DBMS의 경우에는 다를 수 있음을 참고하자.
인덱스 풀 스캔
인덱스 풀 스캔은 처음부터 끝까지 페이지를 이동하며 모든 인덱스를 읽는 방식이다. 쿼리가 인덱스나 PK 만 필요로 한다면 해당 방식이 주로 사용되고, 그 외의 컬럼이 필요하다면 절대 이 방식으로 처리되지 않는다. 또한 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우에 사용된다.
예를 들어 인덱스는 (A, B, C) 순서로 되어 있지만, 조건절은 B 또는 C 컬럼으로 검색되는 경우이다.
또는 SELECT COUNT(*) FROM employee의 경우에도 풀 테이블 스캔이 아닌 풀 인덱스 스캔이 사용된다.
인덱스 풀 스캔이 사용되는 이유는 테이블에는 다른 레코드들도 포함되어 있으니 비효율적이기 때문이다. 해당 방식이 아주 빠르지는 않지만 테이블 풀 스캔보다는 적은 디스크 I/O로 쿼리를 처리할 수 있다.
그렇다고 하여 인덱스 풀 스캔을 위해서 인덱스를 생성해서는 안되며, 인덱스 풀 스캔은 일반적으로 “인덱스를 사용한다”고 하지도 않는다.
루스 인덱스 스캔
루스 인덱스 스캔은 말 그대로 인덱스를 듬성듬성 읽는 방식이다. 일반적으로 GROUP BY나 MIN() 또는 MAX()와 같은 집합 함수를 사용하는 쿼리를 최적화할 때 사용되며, 중간에 불필요한 인덱스는 무시하고 넘어간다.
예를 들어 (dept_no, emp_no)로 인덱스가 생성되어 있는 테이블에 아래와 같은 쿼리를 실행한다고 하자.
mysql> SELECT dept_no, MIN(emp_no)
FROM dept_emp
WHERE dept_no BETWEEN 'D002' AND 'D004'
GROUP BY dept_no;
SQL
복사
위의 쿼리에서 emp_no는 dept_no에 의존하여 정렬되므로, dept_no 그룹 별로 가장 처음의 emp_no값만 읽으면 된다. 옵티마이저는 이러한 부분을 알고 있기 때문에, 처음이 아닌 emp_no는 무시하고 넘어간다.
이러한 부분은 인덱스의 정렬 특성 때문이므로, 인덱스를 구성하는 컬럼의 순서는 상당히 중요한 것이다.
앞선 인덱스 레인지 스캔과 인덱스 풀 스캔은 모든 인덱스를 스캔하므로 타이트 인덱스 스캔으로 묶이는데, 이와 반대되는 스캔 방식이다.
인덱스 스킵 스캔
인덱스 스킵 스캔은 MySQL 8.0부터 추가된 기능으로, 인덱스의 뒷 컬럼만으로 검색하는 경우에 옵티마이저가 자동으로 쿼리를 최적화하여 인덱스를 타도록 하는 읽기 방식이다.
예를 들어 아래와 같은 employee 테이블에 다음과 같은 인덱스를 생성했다고 하자.
mysql> ALTER TABLE employee
ADD INDEX ix_gender_birthdate (gender, birth_date);
SQL
복사
이 인덱스를 사용하려면 WHERE 절에 gender에 대한 비교 조건이 반드시 있어야 한다. birth_date만으로 검색하는 경우라면 인덱스를 새롭게 만들어줘야 했다.
# 인덱스를 사용하지 못하는 쿼리
mysql> SELECT gender, birth_date
FROM employee
WHERE birth_date >= '1994-12-26';
SQL
복사
하지만 MySQL 8.0부터는 옵티마이저가 인덱스를 타지 못하는 쿼리를 최적화하는데,
아래와 같은 쿼리는 다음과 같이 실행된다.
mysql> SELECT gender, birth_date
FROM employee
WHERE gender = 'M' AND birth_date >= '1994-12-26';
mysql> SELECT gender, birth_date
FROM employee
WHERE gender = 'F' AND birth_date >= '1994-12-26';
SQL
복사
인덱스 스킵 스캔이 실행되기 위해서는 다음의 조건들을 모두 만족시켜줘야만 한다.
•
조회되는 컬럼은 인덱스 만으로 처리 가능해야 함(커버링 인덱스)
•
인덱스의 선행 컬럼은 WHERE 절에 없어야 함
•
인덱스 선행 컬럼의 카디날리티가 낮아야 함(유니크한 값이 적어야 함)
먼저 조회되는 컬럼이 인덱스 만으로 처리 가능해야 한다. 만약 모든 컬럼을 조회하는 쿼리라면 풀 테이블 스캔을 타게 된다. 인덱스 스킵 스캔은 MySQL 8.0부터 추가된 기능이라 아직 최적화가 되지 못한 부분이 많은데, 이 부분이 그 중 하나이다.
그 다음으로는 인덱스 선행 컬럼이 WHERE 절에 없으며, 선행 컬럼이 갖는 값이 유니크한 개수가 적을 때에만 최적화가 가능하다는 것이다. 일반적으로는 유니크한 값의 개수가 많을수록 좋다. 하지만 인덱스 스킵 스캔의 경우에는 유니크한 값의 개수가 많다면 인덱스의 스캔 시작 지점을 검색하는 작업이 많아진다. 그래서 쿼리 최적화를 하려다가 오히려 느려질 수 있다.
인덱스를 사용하지 않는 경우
풀 테이블 스캔은 인덱스를 사용하지 않고 테이블의 데이터를 처음부터 끝까지 읽는 방식이다. 옵티마이저는 아래의 경우에 주로 풀 테이블 스캔을 이용한다.
•
WHERE 절이나 ON 절에 인덱스를 이용할 수 있는 적절한 조건이 없는 경우
•
테이블의 레코드 건수가 너무 적어서 인덱스를 통해 읽는 것보다 풀 테이블 스캔을 하는 것이 더 빠른 경우
(일반적으로 테이블이 1개의 페이지 만으로 구성되는 경우)
•
인덱스 레인지 스캔을 사용할 수 있더라도 일치되는 레코드 건수가 너무 많은 경우
일반적으로 전체 테이블의 크기는 인덱스보다 훨씬 크기 때문에 풀 테이블 스캔은 상당히 많은 디스크 읽기를 필요로한다. 그래서 MySQL은 특정 테이블의 연속된 페이지가 읽히면 백그라운드 쓰레드를 통해 다음 페이지의 작업을 미리 읽어 메모리(버퍼풀)에 넣어두는 리드 어헤드(Read ahead) 기능을 갖고 있다. 리드 어헤드 작업은 4개 또는 8개의 페이지부터 시작하여 최대 64개의 페이지까지 읽어오도록 증가된다. 참고로 이는 풀 인덱스 스캔에도 동일하게 적용된다.
8.3.5 다중 컬럼(Multi-column) 인덱스 - 복합 키
지금까지 살펴본 인덱스들은 모두 1개의 칼럼만 포함된 인덱스이다. 하지만 실제 서비스용 데이터베이스에서는 2개 이상의 칼럼을 포함하는 인덱스가 더 많이 사용된다.
두 개 이상의 칼럼으로 구성된 인덱스를 다중 칼럼 인덱스라고 하며, 또한 2개 이상의 칼럼이 연결됐다고 해서 Concatenated Index라고도 한다.
아래 그림에서 중요한 것은 인덱스의 두 번째 컬럼은 첫 번째 컬럼에 의존해서 정렬되어 있다는 것이다. 즉 두 번째 컬럼의 정렬은 첫 번째 컬럼이 똑같은 레코드에서만 의미가 있다는 것이다. 그림에서는 컬럼이 2개 뿐이지만, 만약 컬럼이 4개인 인덱스를 생성한다면 세 번째 컬럼은 두 번째 컬럼에 의존해서 정렬되고, 네 번째 컬럼은 세 번째 컬럼에 의존해 정렬된다.
다중 컬럼 인덱스에서는 인덱스 내에서 각 컬럼의 위치(순서)는 상당히 중요하며 아주 신중히 결정해야 한다.
8.3.6 B-Tree 인덱스의 정렬 및 스캔 방향
인덱스를 생성할 때 설정한 정렬 규칙에 따라 인덱스의 키 값은 항상 오름차순이거나 내림차순으로 정렬되어 저장된다.
But, 인덱스가 오름차순으로 생성되었다고 하더라도 오름차순으로만 읽을 수 있는건 아니다.
인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 만드는 실행계획에 의해 결정된다.
인덱스의 정렬
일반적 사용 DBMS에서는 인덱스를 생성하는 시점에 인덱스를 구성하는 각 칼럼의 정렬을 오름/내림 차순으로 설정할 수 있다.
MySQL 5.7 버전까지는 칼럼 단위로 정렬 순서를 혼합(ASC/DESC)해서 생성할 수 없었고, 이런 문제 해결을 위해 숫자 칼럼의 경우 -1을 곱해 저장하는 우회방법을 사용했었다. MySQL 8.0 부터는 다음과 같은 형태의 정렬 순서를 혼합한 인덱스도 생성할 수 있게 되었다.
mysql> CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC);
SQL
복사
인덱스 스캔 방향
first_name 칼럼에 대한 인덱스가 포함된 employees 테이블에 대해 아래 쿼리를 실행할 때,
mysql> SELECT * FROM employees ORDER BY first_name DESC LIMIT 1;
SQL
복사
인덱스는 항상 오름차순으로만 정렬돼 있지만 인덱스를 최솟값부터 읽으면 오름차순으로 값을 가져올 수 있고, 최대값부터 거꾸로 읽으면 내림차순으로 값을 가져올 수 있다는 것을 MySQL 옵티마이저는 이미 알고있다.
그래서 위의 쿼리는 인덱스를 역순으로 접근해 첫 번째 레코드만 읽으면 된다.
즉, 인덱스 생성 시점에 오름차순 또는 내림차순으로 정렬이 결정되지만 쿼리가 인덱스를 사용하는 시점에 인덱스를 읽는 방향에 따라 오름차순(ASC) 또는 내림차순(DESC) 정렬 효과를 얻을 수 있다.
내림차순 인덱스
복합 인덱스에서 내림차순, 오름차순이 혼합되어 있다면 ‘내림차순 인덱스’의 사용도 고려해야 한다.
소량의 레코드를 대상으로 한다면 그냥 그대로 사용해도 되지만, 대량의 레코드를 대상으로 한다면 내림차순 인덱스가 더 효율적일 수 있다.
오름차순 인덱스 : 작은 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
내림차순 인덱스 : 큰 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
인덱스 정방향 스캔 : 인덱스 키의 크고 작음에 관계없이 인덱스 리프 노드의 왼쪽 페이지부터 오른쪽으로 스캔
인덱스 역방향 스캔 : 인덱스 키의 크고 작음에 관계없이 인덱스 리프 노드의 오른쪽 페이지부터 왼쪽으로 스캔
SELECT * FROM MEMBER ORDER BY NUMBER ASC LIMIT 12619775, 1;
1 row in set (4.15 sec)
SELECT * FROM MEMBER ORDER BY NUMBER DESC LIMIT 12619775, 1;
1 row in set (5.35 sec)
SQL
복사
위의 예제를 보면 DESC를 사용한 결과가 조금 더 느리다는 것을 알 수 있다. MySQL 서버의 InnoDB 스토리지 엔진에서 정방향 스캔과 역방향 스캔은 페이지간의 양방향 연결 고리를 통해 전진이냐 후진이냐의 차이만 있지만 실제 내부적으로는 보통 인덱스 정방향 스캔이 좀 더 빠르게 이루어진다.
이는 페이지 잠금이 인덱스 정방향 스캔에 좀 더 적합하게 설계되었으며, 페이지 내의 인덱스 레코드가 단방향으로만 연결되어 있기 때문이다.
InnoDB 페이지 내에서 레코드들의 연결
8.3.7 B-Tree 인덱스의 가용성과 효율성
쿼리의 WHERE 조건이나 GROUP BY, 또는 ORDER BY 절이 어떤 경우에 인덱스를 사용할 수 있고 어떤 방식으로 사용할 수 있는지 식별할 수 있어야 한다.
비교 조건의 종류와 효율성
다중 칼럼 인덱스에서 각 칼럼의 순서와 그 칼럼에 사용된 조건이 동등(=) 비교, 아니면 크다(>) 또는 작다(<) 같은 범위 조건인지에 따라 각 인덱스 칼럼의 활용 형태가 달라지면 그 효율 또한 달라진다.
mysql> SELECT * FROM dept_emp WHERE dept_no='d002' AND emp_no >= 10114;
SQL
복사
해당 쿼리를 처리하기 위해 두 가지 케이스의 인덱스를 비교해보자
A : INDEX (dept_no, emp_no)
dept_no='d002' AND emp_no>=10114 인 레코드를 찾는다
이후 dept_no 가 d002가 아닐때 까지 쭉 읽는다.
B : INDEX (emp_no, dept_no)
emp_no>=10144 AND depth_no='d002' 인 레코드를 찾는다.
이후 모든 레코드에 대해 dept_no가 d002인이 비교하는 과정을 거친다.
인덱스를 통해 읽은 레코드가 나머지 조건에 맞는지 비교하면서 선택하는 작업 = 필터링
•
A와 B의 인덱스 비교가 다른 이유
◦
다중 칼럼 인덱스의 정렬 방식 때문이다.
▪
인덱스의 N번째 키 값은 N-1번째 키 값에 대해서 다시 정렬된다.
◦
A인덱스의 경우 2번째 컬럼인 emp_no는 비교작업의 범위를 좁히는 데 도움을 준다.
▪
작업 범위 결정 조건
◦
B인덱스의 경우 2번째 칼럼인 dept_no는 비교 작업의 범위를 좁히는 데 아무런 도움 X
▪
범위를 줄이지 못하고 단순히 거름종이 역할만 하는 조건
•
필터링 조건 또는 체크 조건
인덱스의 가용성
B-Tree 인덱스의 특징은 왼쪽 값에 기준해서 오른쪽 값이 정렬돼 있다는 것
•
왼쪽이란 하나의 칼럼 내에서뿐만 아니라 다중 칼럼 인덱스의 칼럼에 대해서도 함께 적용된다.
•
인덱스 키 값의 이런 정렬 특성은 빠른 검색의 전제 조건
•
하나의 칼럼으로 검색해도 값의 왼쪽 부분이 없으면 인덱스 레인지 스캔 방식의 검색이 불가하다.
•
케이스 A : INDEX(first_name)
SELECT * FROM employees WHERE first_name LIKE '%mer';
SQL
복사
위 쿼리는 인덱스 레인지 스캔 방식으로 인덱스를 이용할 수 없다. 그 이유는 first_name 칼럼의 왼쪽부터 비교해야하는데, 해당 쿼리는 왼쪽값이 고정되어 있지 않기 때문이다.
정렬 우선순위가 낮은 뒷부분의 값만으로는 왼쪽 기준 정렬 기반의 인덱스인 B-tree에서는 인덱스의 효과를 얻을 수 없다.
•
케이스 B : INDEX(dept_no, emp_no)
SELECT * FROM dept_emp WHERE emp_no >= 10144;
SQL
복사
인덱스의 선행 칼럼인 dept_no 조건 없이 emp_no 값으로만 검색하면 인덱스를 효율적으로 사용할 수 없다.
dept_no 칼럼에 대해 먼저 정렬 후 다시 emp_no 칼럼으로 정렬되기 때문이다.
간단히 WHERE 조건절에 대한 내용만 언급했지만 인덱스의 왼쪽 값 기준 규칙은 GROUP BY 절이 나 ORDER BY 절에도 동일 적용된다.
가용성과 효율성 판단
기본적으로 B-Tree 인덱스의 특성상 다음 조건에서는 사용 불가하다. 사용할 수 없다는 것은 작업 범위 결정 조건으로 사용할 수 없다는 것을 의미하며, 경우에 따라서는 체크 조건으로 인덱스를 사용 가능하다.
•
NOT-EQUAL로 비교된 경우 (<>, NOT IN, NOT BETWEEN, IS NOT NULL)
.. WHERE column <> 'N'
.. WHERE column NOT IN (10, 11, 12)
.. WHERE column IS NOT NULL
SQL
복사
•
LIKE '%??' 앞부분이 나닌 뒷부분 일치 형태로 문자열 패턴이 비교된 경우
.. WHERE column LIKE '%승환'
SQL
복사
•
스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우
.. WHERE SUBSTRING(column, 1, 1) = 'X'
SQL
복사
•
NOT-DEERMINISTIC 속성의 스토어드 함수가 비교 조건으로 사용된 경우
.. WHERE column = deterministic_function()
SQL
복사
•
데이터 타입이 서로 다른 비교 (인덱스 칼럼의 타입을 변환해야 비교가 가능한 경우)
.. WHERE char_column = 10
SQL
복사
•
문자열 데이터 타입의 콜레이션이 다른 경우
.. WHERE utf_bin_char_column = euckr_bin_char_column
SQL
복사
다른 일반적 DBMS에서는 NULL 값이 인덱스에 저장되지 않지만,
MySQL에서는 NULL 값도 인덱스에 저장된다.
다음과 같은 WHERE 조건도 작업 범위 결정 조건으로 인덱스를 사용한다.
.. WHERE column IS NULL ..
SQL
복사
다중 컬럼으로 만들어진 인덱스는 어떤 조건에서 사용될 수 있고, 어떤 경우에 절대 사용할 수 없는지 살펴보자.
INDEX ix_test (column_1, column_2, column_3 ..., column_n)
SQL
복사
•
작업 범위 결정 조건으로 인덱스를 사용하지 못하는 경우
◦
column_1 칼럼에 대한 조건이 없는 경우
◦
column_1 칼럼의 비교 조건이 위의 인덱스 사용 불가 조건 중 하나일 경우
•
작업 범위 결정 조건으로 인덱스 사용이 가능한 경우
◦
column_1 ~ column_(i-1) 칼럼까지 동등 비교 형태로 비교
◦
column_1 칼럼에 대해 다음 연산자 중 하나로 비교
▪
동등 비교(=), 크다 작다 형태(>, <), LIKE로 좌측 일치 패턴(%)
위의 두 가지 조건을 모두 만족하는 쿼리는 column_1부터 column_i까지는 작업 범위 결정 조건으로 사용되고, column_(i+1)부터 column_n까지의 조건은 체크 조건으로 사용된다.
