8.3 B-Tree 인덱스
B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다. 하지만 아직도 가장 범용적인 목적으로 사용되는 인덱스 알고리즘이다. B-Tree에는 여러 가지 변형된 형태의 알고리즘이 있는데, DBMS에서는 주로 B+-Tree 또는 B*-Tree가 사용된다.
Balanced를 의미하는 B-Tree는 칼럼의 원래 값을 변형시키지 않고 (물론 값의 앞부분만 잘라서 관리하기는 하지만) 인덱스 구조체 내에서는 항상 정렬된 상태로 유지한다. 전문 검색과 같은 특수한 요건이 아닌 경우, 대부분 인덱스는 거의 B-Tree를 사용할 정도로 일반적인 용도에 적합한 알고리즘이다.
8.3.1 구조 및 특성
B-Tree는 트리 구조의 최상위에 하나의 "루트 노드(Root node)"가 존재하고 그 하위에 자식 노드가 붙어 잇는 형태다. 가장 하위에 있는 노드를 "리프 노드(Leaf node)"라 하고, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간의 노드를 "브랜치 노드(Branch node)"라고 한다. 데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.
그림과 같이 인덱스의 키 값은 모두 정렬돼 있지만, 데이터 파일의 레코드는 임의의 순서로 저장돼 있다. 많은 사람들이 데이터 파일의 레코드는 INSERT된 순서대로 저장되는 것으로 생각하지만 그렇지 않다. 테이블의 레코드를 전혀 삭제하거나 변경하지 않는다면 맞을 수 있다. 하지만 레코드가 삭제되어 빈 공간이 생기면 그 다음 INSERT는 가능한 한 삭제된 공간을 재활용하도록 DBMS가 설계되기 때문에 항상 INSERT된 순서로 저장되는 것은 아니다.
인덱스는 테이블의 키 칼럼만 가지고 있으므로 나머지 칼럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 한다. 이를 위해 인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가진다.
위의 그림은 InnoDB 테이블의 인덱스의 데이터 파일의 관계를 보여주는데, InnoDB 스토리지 엔진을 사용하는 테이블에서는 프라이머리 키가 ROWID의 역할을 한다. InnoDB 테이블은 프라이머리 키를 주소처럼 사용하기에 논리적인 주소를 가져 데이터 파일을 바로 찾아가지 못한다.
그림과 같이 인덱스에 저장돼 있는 PK 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽는다. 즉, InnoDB 엔진에서는 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 PK를 저장하고 있는 B-Tree를 다시 한번 검색해야 한다.
8.3.2 B-Tree 인덱스 키 추가 및 삭제
테이블의 레코드를 저장하거나 변경하는 경우 인덱스 키 추가나 삭제 작업이 발생한다. 어떻게 처리되는지 알아두면 쿼리의 성능을 쉽게 예측할 수 있을 것이다.
8.3.2.1 인덱스 키 추가
새로운 키 값이 B-Tree에 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다. B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보의 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다. 리프 노드가 꽉 차서 더는 저장할 수 없다면 리프 노드가 분리돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다. 이러한 작업 탓에 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 드는 것으로 알려졌다.
MyISAM이나 MEMORY 스토리지 엔진을 사용하는 테이블에서는 INSERT 문장이 실행되면 즉시 새 키 값을 B-Tree 인덱스에 변경한다. 하지만 InnoDB 스토리지 엔진은 이 작업을 조금 더 지능적으로 처리하는데, 필요하다면 인덱스 키 추가 작업을 지연시켜 나중에 처리할 수 있다. 하지만 프라이머리 키나 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 즉시 B-Tree에 추가하거나 삭제한다.
8.3.2.2 인덱스 키 삭제
B-Tree의 키 값이 삭제되는 경우는 상당히 간단하다. 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 마크만 하면 작업이 완료되고 삭제 마킹된 키 공간은 그대로 방치하거나 재활용할 수 있다. 인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 이 역시 디스크 I/O가 필요한 작업니다. InnoDB 스토리지 엔진에서는 이 작업 또한 버퍼링되어 지연 처리될 수도 있다. 처리가 지연된 인덱스 키 삭제 또한 사용자에게는 특별한 악영향 없이 MySQL 서버가 내부적으로 처리하므로 특별히 걱정할 것은 없다.
8.3.2.3 인덱스 키 변경
인덱스의 키 값은 그 값에 따라 저장될 리프 노드의 위치가 결정되므로 B-Tree의 키 값이 변경되는 경우에는 단순히 인덱스상의 키 값만 변경하는 것은 불가능하다. B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다. 키 값의 변경 때문에 발생하는 B-Tree 인덱스 키 값의 삭제와 추가 작업은 앞에서 설명한 절차대로 처리된다. 결국 인덱스 키 값을 변경하는 작업은 기존 인덱스 키 값을 삭제한 후 새 인덱스 키 값을 추가하는 작업으로 처리되고, InnoDB 스토리지 엔진을 사용하는 테이블에 대해서는 이 작업 모두 체인지 버퍼를 활용해 지연 처리될 수 있다.
8.3.2.4 인덱스 키 검색
INSERT, UPDATE, DELETE 작업을 할 때 인덱스 관리에 따르는 추가 비용을 감당하면서 인덱스를 구축하는 이유는 바로 빠른 검색을 위해서다. 인덱스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행하는데, 이 과정을 "트리 탐색"이라고 한다. 인덱스 트리 탐색은 SELECT에서만 사용하는 것이 아니라 UPDATE나 DELETE를 처리하기 위해 항상 해당 레코드를 먼저 검색해야 할 경우에도 사용된다. B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있다. 부등호 비교 조건에서도 인덱스를 활용할 수 있지만, 인덱스를 구성하는 키 값의 뒷부분만 검색하는 용도로는 인덱스를 사용할 수 없다.
또한 인덱스의 키 값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree의 빠른 검색 기능을 사용할 수 없다는 것이다. 이미 변형된 값은 B-Tree 인덱스에 존재하는 값이 아니다. 따라서 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree의 장점을 이용할 수 없으므로 주의해야 한다.
InnoDB 스토리지 엔진에서 인덱스는 더 특별한 의미가 있다. InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키락(갭락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있다. 따라서 UPDATE나 DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠근다. 심지어 테이블의 모든 레코드를 잠글 수도 있다. InnoDB 스토리지 엔진에서는 그만큼 인덱스의 설계가 중요하고 많은 부분에 영향을 미친다.
8.3.3 B-Tree 인덱스 사용에 영향을 미치는 요소
B-Tree 인덱스는 인덱스를 구성하는 칼럼의 크기와 레코드의 건수, 그리고 유니크한 인덱스 키 값의 개수 등에 의해 검색이나 변경 작업의 성능이 영향을 받는다.
8.3.3.1 인덱스 키 값의 크기
InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다. 또한 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 한다. 인덱스도 결국은 페이지 단위로 관리되며, 앞의 그림 8.4에서 루트와 브랜치, 리프 노드를 구분한 기준이 바로 페이지 단위다.
일반적으로 DBMS의 B-Tree는 자식 노드의 개수가 가변적인 구조다. 그러면 MySQL의 B-Tree는 자식 노드를 몇 개까지 가지는지 궁금할 것이다. 그것은 바로 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다. InnoDB 스토리지 엔진의 페이지 크기의 기본값은 16KB다. 인덱스의 키가 16바이트라 가정하면 다음 그림과 같이 인덱스 페이지가 구성될 것이다. 그림 8.7에서 자식 노드 주소라는 것은 여러 가지 복합적인 정보가 담긴 영역이며, 페이지의 종류별로 대략 6바이트에서 12바이트까지 다양한 크기의 값을 가질 수 있다. 여기서는 편의상 자식 노드 주소 영역이 평균적으로 12바이트로 구성된다고 가정하자.
그림 8.7의 경우 하나의 인덱스 페이지(16KB)에 몇 개의 키를 저장할 수 있을까? 계산해 보면 16*1024/(16+12) = 585개 저장할 수 있다. 최종적으로 이 경우는 자식 노드를 585개를 가질 수 있는 B-Tree가 되는 것이다. 그러면 인덱스 키 값이 커지면 어떤 현상이 발생할까? 위의 경우에서 키 값의 크기가 두 배인 32바이트로 늘어났다고 가정하면 한 페이지에 인덱스 키를 16*1024/(32+12) = 372개 저장할 수 있다. SELECT 쿼리가 레코드 500개를 읽어야 한다면 전자는 인덱스 페이지 한 번으로 해결될 수도 있지만, 후자는 최소한 2번 이상 디스크로부터 읽어야 한다. 결국 인덱스를 구성하는 키 값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 느려진다는 것을 의미한다.
또한 인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미한다. 하지만 인덱스를 캐시해 두는 InnoDB의 버퍼 풀이나 MyISAM의 키 캐시 영역은 크기가 제한적이기 때문에 하나의 레코드를 위한 인덱스 크기가 커지면 커질수록 메모리에 캐시해 둘 수 잇는 레코드 수는 줄어든다. 그렇게 되면 자연히 메모리의 효율이 떨어지는 결과를 가져온다.
8.3.3.2 B-Tree 깊이
B-Tree 인덱스의 깊이(Depth)는 상당히 중요하지만 직접 제어할 방법은 없다. 인덱스의 B-Tree 깊이가 3인 경우 최대 몇 개의 키 값을 가질 수 있는지 한 번 비교해 보자. 키 값이 16바이트인 경우에는 최대 2억개 정도의 키 값을 담을 수 있지만, 32바이트로 늘어나면 5천만개로 줄어든다. B-Tree의 깊이는 MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다. 결론적으로 인덱스 키 값의 크기가 커지면 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어지고, 그 때문에 같은 레코드 건수라 하더라도 B-Tree의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다는 것을 의미한다.
여기서 언급한 내용은 사실 인덱스 키 값의 크기는 가능하면 작게 만드는 것이 좋다는 것을 강조하기 위함이고, 실제로는 아무리 대용량 데이터베이스라도 B-Tree의 깊이가 5단계 이상까지 깊어지는 경우는 흔치 않다.
8.3.3.3 선택도(기수성)
인덱스에서 선택도(Selectivity) 또는 기수성(Cardinality)은 거의 같은 의미로 사용되며, 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다. 인덱스 키 값 가운데 중복된 값이 많아질수록 기수성은 낮아지고 동시에 선택도 또한 떨어진다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들어 그만큼 빠르게 처리된다.
8.3.3.4 읽어야 하는 레코드의 건수
인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 든다.
인덱스를 이용한 읽기의 손익 분기점이 얼마인지 판단할 필요가 있는데, 일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배정도 비용이 더 많이 드는 작업으로 예측한다. 즉, 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블의 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 가려내는 방식으로 처리하는 것이 효율적이다.
8.3.4 B-Tree 인덱스를 통한 데이터 읽기
어떤 경우에 인덱스를 사용하게 유도할지 판단하려면 MySQL이 어떻게 인덱스를 이용(경유)해서 실제 레코드를 읽어 내는지 알아야 한다.
8.3.4.1 인덱스 레인지 스캔
인덱스 레인지 스캔은 인덱스의 접근 방법 가운데 가장 대표적인 방식으로, 나머지 두 가지 접근 방식보다는 빠르다.
mysql> SELECT * FROM employees WHERE first_name BETWEEN 'Ebbe' AND 'Gad';
인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다. 화살표에서도 알 수 있듯이 루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 찾아 들어가야만 비로소 필요한 레코드의 시작 지점을 찾을 수 있다. 일단 시작해야 할 위치를 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 된다. 이처럼 차례대로 쭉 읽는 것을 스캔이라고 표현한다.
만약 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔한다. 그리고 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다. 그림 8.8에서 두꺼운 선은 스캔해야 할 위치 검색을 위한 비교 작업을 의미하며, 두꺼운 화살표가 지나가는 리프 노드의 레코드 구간은 실제 스캔하는 범위를 표현한다.
그림은 실제 인덱스만을 읽는 경우를 보여주는데 리프 노드를 스캔하면서 실제 데이터 파일의 레코드를 읽어 와야 하는 경우도 많다. 이 과정을 좀 더 자세히 살펴보자.
B-Tree 인덱스에서 루트와 브랜치 노드를 이용해 스캔 시작 위치를 검색하고, 그 지점부터 필요한 방향(오름차순/내림차순)으로 인덱스를 읽어 나가는 과정을 그림에서 확인할 수 있다. 중요한 것은 어떤 방식으로 스캔하든, 해당 인덱스를 구성하는 칼럼의 정순/역순으로 정렬된 상태로 레코드를 가져온다는 것이다. 별도의 정렬 과정이 수반되는 것이 아니라 인덱스 자체의 정렬 특성 때문에 자동으로 그렇게 된다.
또 중요한 것은 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다는 것이다. 이때 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 레코드 한 건 한 건 단위로 랜덤 I/O가 한 번씩 일어난다. 그림처럼 3건의 레코드가 검색 조건에 일치했다고 가정하면, 데이터 레코드를 읽기 위해 랜덤 I/O가 최대 3번 필요한 것이다. 그래서 인덱스를 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 작업으로 분류된다. 만약 인덱스를 통해 읽어야 할 데이터 레코드가 20~25%를 넘으면 테이블의 데이터를 직접 읽는 것이 더 효율적인 처리 방식이 된다.
인덱스 레인지 스캔 과정
1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다. -> 인덱스 탐색
2. 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 쭉 읽는다. -> 인덱스 스캔
3. 2번에서 읽어 들인 인덱스 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽어온다.
쿼리가 필요로 하는 데이터에 따라 3번 과정은 필요하지 않을 수도 있는데, 이를 커버링 인덱스라고 한다. 커버링 인덱스로 처리되는 디스크의 레코드를 읽지 않아도 되기 때문에 랜덤 읽기가 상당히 줄어들고 성능은 그만큼 빨라진다.
8.3.4.2 인덱스 풀 스캔
인덱스 레인지 스캔과 마찬가지로 인덱스를 사용하지만 인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 한다. 대표적으로 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다. 예를 들어, 인덱스는 (A, B, C) 칼럼의 순서로 만들어져 있지만 쿼리의 조건절은 B 칼럼이나 C 칼럼으로 검색하는 경우다.
인덱스 리프 노드의 제일 앞 또는 제일 뒤로 이동한 후, 인덱스의 리프 노드를 연결하는 링크드 리스트를 따라서 처음부터 끝까지 스캔하는 방식을 인덱스 풀 스캔이라고 한다. 이 방식은 인덱스 레인지 스캔보다는 빠르지 않지만 테이블 풀 스캔보다는 효율적이다. 인덱스에 포함된 칼럼만으로 쿼리를 처리할 수 있는 경우 테이블의 레코드를 읽을 필요가 없기 때문이다.
인덱스의 전체 크기는 테이블 자체의 크기보다는 훨씬 작으므로 인덱스 풀 스캔은 테이블 전체를 읽는 것보다는 적은 디스크 I/O로 쿼리를 처리할 수 있다.
8.3.5 다중 칼럼 인덱스
지금까지 살펴본 인덱스들은 모두 1개의 칼럼만 포함된 인덱스였다. 하지만 실제 서비스용 데이터베이스에서는 2개 이상의 칼럼을 포함하는 인덱스가 더 많이 사용된다. 두 개 이상의 칼럼으로 구성된 인덱스를 다중 칼럼 인덱스라 한다.
인덱스의 두 번째 칼럼은 첫 번재 칼럼에 의존해 정렬되어 있다. 즉, 두 번째 칼럼의 정렬은 첫 번째 칼럼이 똑같은 레코드에서만 의미가 있다는 것이다. 다중 칼럼 인덱스에서는 인덱스 내에서 각 칼럼의 위치(순서)가 상당히 중요하며, 그것을 아주 신중히 결정해야 하는 이유가 바로 그것이다.
8.3.6 B-Tree 인덱스의 정렬 및 스캔 방향
인덱스를 생성할 때 설정한 정렬 규칙에 따라서 인덱스의 키 값은 항상 오름차순이거나 내림차순으로 정렬되어 저장된다. 하지만 어떤 인덱스가 오름차순으로 생성됐다고 해서 그 인덱스를 오름차순으로만 읽을 수 있는 건 아니다. 인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 실시간으로 만들어내는 실행 계획에 따라 결정된다.
8.3.6.1 인덱스의 정렬
일반적인 상용 DBMS에서는 인덱스를 생성하는 시점에 인덱스를 구성하는 각 칼럼의 정렬을 오름차순 또는 내림차순으로 설정할 수 있다.
MySQL 5.7 버전까지는 칼럼 단위로 정렬 순서를 혼합해서 인덱스를 생성할 수 없었으나 MySQL 8.0 버전부터는 다음과 같은 형태의 정렬 순서를 혼합한 인덱스도 생성할 수 있게 됐다.
mysql> CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC);
8.3.6.1.1 인덱스 스캔 방향
first_name 칼럼에 대한 인덱스가 포함된 employees 테이블에 대해 다음 쿼리를 실행하는 과정을 한 번 살펴보자. MySQL은 이 쿼리를 실행하기 위해 인덱스를 처음부터 오름차순으로 끝까지 읽어 first_name이 가장 큰(오름차순으로 읽었을 때 가장 마지막 레코드) 값 하나를 가져오는 것일까?
mysql> SELECT * FROM employees ORDER BY first_name DESC LIMIT 1;
그렇지 않다. 인덱스는 항상 오름차순으로 정렬돼 있지만 인덱스를 최솟값부터 읽으면 오름차순으로, 최댓값부터 읽으면 내림차순으로 값을 가져올 수 있다는 것을 MySQL 옵티마이저는 이미 알고 있다. 그러니 위의 쿼리는 인덱스를 역순으로 접근해 첫 번째 레코드만 읽으면 된다.
인덱스 생성 시점에 오름차순 또는 내림차순으로 정렬이 결정되지만 쿼리가 그 인덱스를 사용하는 시점에 인덱스를 읽는 방향에 따른 오름차순 또는 내림차순 정렬 효과를 얻을 수 있다. 오름차순으로 생성된 인덱스를 정순으로 읽으면 출력되는 결과 레코드는 자동으로 오름차순으로 정렬된 결과가 되고, 역순으로 읽으면 그 결과는 내림차순으로 정렬된 상태가 되는 것이다.
8.3.6.1.2 내림차순 인덱스
MySQL 서버에서 다음 두 쿼리는 실제 내림차순인지 오름차순인지와 관계없이 인덱스를 읽는 순서만 변경해서 해결할 수 있다는 것을 살펴봤다.
mysql> SELECT * FROM employees ORDER BY first_name ASC LIMIT 10;
mysql> SELECT * FROM employees ORDER BY first_name DESC LIMIT 10;
mysql> CREATE INDEX ix_firstname_asc ON employees (first_name ASC);
mysql> CREATE INDEX ix_firstname_desc ON employees (first_name DESC);
이 궁금증에 대한 답을 찾기 위해 MySQL 8.0부터 지원되는 내림차순 인덱스에 대해 조금 깊이 있게 살펴보자.
- 오름차순 인덱스(Ascending index): 작은 값의 인덱스 키가 B-Tree의 왼족으로 정렬된 인덱스
- 내림차순 인덱스(Descending index): 큰 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
- 인덱스 정순 스캔(Forward index scan): 인덱스 키의 크고 작음에 관계없이 인덱스 리프 노드의 왼쪽 페이지부터 오른쪽으로 스캔
- 인덱스 역순 스캔(Backward index scan): 인덱스 키의 크고 작음에 관계없이 인덱스 리프 노드의 오른쪽 페이지부터 왼쪽으로 스캔
이제 내림차순 인덱스의 필요성에 대해 간단한 테스트 결과를 살펴보며 알아보자. 테스트용 테이블을 생성하고 대략 1천만 건 정도의 레코드를 준비해 풀 스캔하면서 정렬만 수행하는 쿼리를 실행해보자.
mysql> SELECT * FROM t1 ORDER BY tid ASC LIMIT 12619775, 1;
1 row in set (4.15 sec)
mysql> SELECT * FROM t1 ORDER BY tid DESC LIMIT 12619775, 1;
1 row in set (5.35 sec)
결국 테이블의 프라이머리 키를 정순 또는 역순으로 스캔하면서 마지막 레코드 1건만 반환한다. 첫 번째 쿼리는 tid 칼럼의 값이 가장 큰 레코드 1건을, 두 번째 쿼리는 tid 칼럼의 값이 가장 작은 레코드 1건을 반환한다. 하지만 LIMIT ... OFFSET ... 부분의 쿼리로 인해 실제 MySQL 서버는 테이블의 모든 레코드를 스캔해야 한다.
결과를 보면 역순 정렬 쿼리가 정순 정렬 쿼리보다 28.9% 더 시간이 걸리는 것을 확인할 수 있다. MySQL 서버의 InnoDB 스토리지 엔진에서 정순 스캔과 역순 스캔은 페이지(블록) 간의 양방향 연결 고리(Double linked list)를 통해 전진(Forward)하느냐 후진(Backward)하느냐의 차이만 있지만, 실제 내부적으로는 InnoDB에서 인덱스 역순 스캔이 인덱스 정순 스캔에 비해 느릴 수밖에 없는 다음의 두 가지 이유가 있다.
- 페이지 잠금이 인덱스 정순 스캔에 적합한 구조
- 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조
- 그림에서 보다시피 InnoDB 페이지 내부에서 레코드들이 단방향으로만 링크를 가진 구조다.
일반적으로 인덱스를 ORDER BY ... DESC하는 쿼리가 소량의 레코드에 드물게 실행되는 경우라면 내림차순 인덱스를 굳이 고려할 필요는 없어 보인다. 또한 많은 쿼리가 인덱스의 앞쪽만 또는 뒤쪽만 집중적으로 읽어서 인덱스의 특정 페이지 잠금이 병목이 될 것으로 예상된다면 쿼리에서 자주 사용되는 정렬 순서대로 인덱스를 생성하는 것이 잠금 병목 현상을 완화하는 데 도움이 될 것이다.
8.3.7 B-Tree 인덱스의 가용성과 효율성
쿼리의 WHERE 조건이나 GROUP BY, ORDER BY 절이 어떤 경우에 인덱스를 사용할 수 있고 어떤 방식으로 사용할 수 있는지 식별할 수 있어야 한다. 그래야만 쿼리의 조건을 최적화하거나, 역으로 쿼리에 맞게 인덱스를 최적으로 생성할 수 있다.
8.3.7.1 비교 조건의 종류와 효율성
다중 칼럼 인덱스에서 각 칼럼의 순서와 그 칼럼에 사용된 조건이 동등 비교("=")인지 아니면 크다(">") 또는 작다("<") 같은 범위 조건에 따라 각 인덱스 칼럼의 활용 형태와 효율이 달라진다.
mysql> SELECT * FROM dept_emp WHERE dept_no='d002' AND emp_no >= 10114;이 쿼리를 위해 dept_emp 테이블에 각각 칼럼의 순서만 다른 두 가지 케이스로 인덱스를 생성했다고 가정하자.
- 케이스 A: INDEX(dept_no, emp_no)
- 케이스 B: INDEX(emp_no, dept_no)
케이스 A 인덱스는 "dept_no='d002' AND emp_no>=10144"인 레코드를 찾고, 그 이후에는 dept_no가 'd002'가 아닐 때까지 인덱스를 그냥 쭉 읽기만 하면 된다. 이 경우에는 읽은 레코드가 모두 사용자가 원하는 결과가 아님을 알 수 있다. 즉, 조건을 만족하는 레코드 수만큼 비교 작업을 수행한 것이므로 상당히 효율적으로 인덱스를 이용한 것이다. 하지만 케이스 B 인덱스는 우선 "emp_no>=10144 AND dept_no='d002'"인 레코드를 찾고, 그 이후 모든 레코드에 대해 dept_no가 'd002'인지 비교하는 과정을 거쳐야 한다.
이처럼 인덱스를 통해 읽은 레코드가 나머지 조건에 맞는지 비교하면서 취사선택하는 작업을 '필터링'이라 한다. 케이스 B 인덱스에서는 최종적으로 dept_no='d002' 조건을 만족(필터링)하는 레코드 5건을 가져온다. 즉, 이 경우에는 레코드를 찾기 위해 7번의 비교 과정을 거친 것이다.
왜 이런 현상이 발생한걸까? 바로 '다중 칼럼 인덱스'에서 설명한 다중 칼럼 인덱스의 정렬 방식때문이다. 케이스 A 인덱스에서 2번째 칼럼인 emp_no는 비교 작업의 범위를 좁히는 데 도움을 준다. 하지만 케이스 B 인덱스에서 2번째 칼럼인 dept_no는 비교 작업의 범위를 좁히는 데 아무런 도움을 주지 못하고, 단지 쿼리의 조건에 맞는지 검사하는 용도로만 사요오댔다.
이처럼 케이스 A 인덱스에서의 두 조건 (dept_no='d002' 와 emp_no>=10144)과 같이 작업의 범위를 결정하는 조건을 '작업 범위 결정 조건'이라 하고, 케이스 B 인덱스의 dept_no='d002' 조건과 같이 비교 작업의 범위를 줄이지 못하고 단순히 거름종이 역할만 하는 조건을 '필터링 조건' 또는 '체크 조건'이라고도 표현한다. 결국, 케이스 A 인덱스에서 dept_no 칼럼과 emp_no 칼럼은 모두 '작업 범위 결정 조건'에 해당하지만, 케이스 B 인덱스에서는 emp_no 칼럼만 '작업 범위 결정 조건'이고, dept_no 칼럼은 '필터링 조건'으로 사용된 것이다.
작업 범위를 결정하는 조건은 많을 수록 쿼리의 처리 성능을 높이지만 체크 조건은 많다고 해서 쿼리의 처리 성능을 높이지는 못한다. 오히려 쿼리 실행을 더 느리게 만들 때가 많다.
8.3.7.2 인덱스의 가용성
B-Tree 인덱스의 특징은 왼쪽 값에 기준해서 오른쪽 값이 정렬돼 있다는 것이다. 여기서 왼쪽은 다중 칼럼 인덱스의 칼럼에 대해서도 함께 적용된다.
- 케이스 A: INDEX (first_name)
- 케이스 B: INDEX (dept_no, emp_no)
그림 8.18에서는 인덱스 키 값의 정렬만 표현하지만 사실은 인덱스 키 값의 이런 정렬 특성은 빠른 검색의 전제 조건이다. 즉 하나의 칼럼으로 검색해도 값의 왼쪽 부분이 없으면 인덱스 레인지 스캔 방식의 검색이 불가능하다. 또한 다중 칼럼 인덱스에서도 왼쪽 칼럼의 값을 모르면 인덱스 레인지 스캔을 사용할 수 없다.
케이스 A의 인덱스가 지정된 employees 테이블에 대해 다음과 같은 쿼리가 어떻게 실행되는지 한번 살펴보자.
mysql> SELECT * FROM employees WHERE first_name LIKE '%mer';
이 쿼리는 인덱스 레인지 스캔 방식으로 인덱스를 이용할 수 없다. first_name 칼럼에 저장된 값의 왼쪽부터 한 글짜씩 비교해 가며 일치하는 레코드를 찾아야 하는데, 조건절에 주어진 상숫값('%mer')에는 왼쪽 부분이 고정되지 않았기 때문이다. 따라서 왼쪽 기준 정렬 기반의 인덱스인 B-Tree에서는 인덱스의 효과를 얻을 수 없다.
mysql> SELECT * FROM dept_emp WHERE emp_no>=10144;
케이스 B의 인덱스는 다중 칼럼으로 구성된 인덱스이므로 dept_no 칼럼에 대해 먼저 정렬한 후, 다시 emp_no 칼럼값으로 정렬돼 있어 인덱스의 선행 칼럼인 dept_no 조건 없이 emp_no 값으로만 검색하면 인덱스를 효율적으로 사용할 수 없다.
'Book > RealMySQL 8.0' 카테고리의 다른 글
| [RealMySQL 8.0] 8. 인덱스 - 기타 인덱스 (멀티 밸류 인덱스, 클러스터링 인덱스, 유니크 인덱스, 외래키) (0) | 2025.02.09 |
|---|---|
| [RealMySQL 8.0] 8. 인덱스 - 디스크 읽기 방식 / 인덱스란? (2) | 2024.12.01 |
| [RealMySQL 8.0] 5. 트랜잭션과 잠금 - MySQL의 격리 수준 (1) | 2024.11.29 |
| [RealMySQL 8.0] 5. 트랜잭션과 잠금 - InnoDB 스토리지 엔진 잠금 (0) | 2024.11.27 |
| [RealMySQL 8.0] 5. 트랜잭션과 잠금 - 트랜잭션 / MySQL 엔진의 잠금 (0) | 2024.11.04 |
