Featured image of post 8. 인덱스 (2) - B-Tree 인덱스
Real MySQL

8. 인덱스 (2) - B-Tree 인덱스

Real MySQL 8.0

B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 가장 먼저 도입되었지만 아직까지도 가장 범용적으로 사용되는 인덱스 알고리즘이다.

B-Tree에는 여러 변형된 형대의 알고리즘이 있는데, 일반적으로 DMBS에서는 B+-Tree, B*-Tree가 사용된다.

B-Tree는 컬럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태로 유지한다. 전문 검색같은 특수한 요건이 아닌 경우, 대부분 인덱스는 B-Tree를 사용한다.

구조 및 특성

B-Tree 인덱스의 구조

B-Tree는 트리 구조의 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식 노드가 붙어있는 형태이다. 트리 구조의 가장 하위에 있는 노드를 리프 노드라 하고, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간 노드를 브랜치 노드라고 한다.

데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가진다.

인덱스의 키 값은 모두 정렬돼 있지만, 데이터 파일릐 레코드는 정렬돼 있지 않고 임의의 순서로 저장돼 있다. 레코드가 삭제되어 빈 공간이 생기면 그다음 INSERT는 가능한 한 삭제된 공간을 재활용 하도록 DBMS가 설계되기 때문에, 항상 INSERT순서대로 저장되는 것은 아니다.

B-Tree의 리프 노드와 테이블 데이터 레코드(MyISAM) B-Tree의 리프 노드와 테이블 데이터 레코드(InnoDB)

인덱스는 테이블의 키 컬럼만 가지고 있으므로 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 한다. 이를 위해 인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가진다.

  • MyISAM
    • 레코드 주소는 MyISAM 테이블 생성 옵션에 따라 레코드가 테이블에 INSERT된 순번이거나 데이터 파일 내의 위치다. (ROWID)
    • 세컨더리 인덱스가 물리적인 주소를 가진다.
  • InnoDB
    • 프라이머리 키가 ROWID 역할을 한다
    • 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가진다고 볼 수 있다.
    • 따라서 인덱스를 통해 레코드를 읽을때는 데이터 파일을 바로 찾아가지 못하고, 인덱스에 저장되어있는 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한번 검색해야 한다.

이러한 특징으로 인해 InnoDB 스토리지 엔진을 사용하는 테이블의 성능이 떨어질 것 처럼 보이지만 각각 장단점을 가지고 있다.

B-Tree 인덱스 키 추가 및 삭제

테이블의 레코드를 저장하거나 변경하는 경우 인덱스 키 추가나 삭제 작업이 발생한다. 이에따라 주의해야 할 사항이 있다.

인덱스 키 추가

새로운 키 값이 B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다.

리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리돼야 하는데, 이는 상위 브랜치 노드까지 처리 범위가 넓어진다. 이러한 작업 탓이 B-Tree는 상대적으로 쓰기 작업(새로운 키를 추가)에 비용이 많이 드는 것으로 알려졌다.

인덱스 추가로 인해 INSERT, UPDATE 문장이 어떤 영향을 받을지 예상해보려면 테이블의 컬럼 수, 컬럼 크기, 인덱스 컬럼의 특성 등을 확인해야 한다. 대략적으로 테이블의 레코드를 추가하는 작업 비용을 1이라고 가정하면, 해당 테이블의 인덱스에 키를 추가하는 작업 비용을 1.5 정도로 예측한다. 테이블에 인덱스가 3개가 있다면 5.5(1.5 * 3 + 1) 정도로 예측한다. 중요한 것은 이 비용의 대부분이 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야해서 걸리는 시간이다.

MyISAM이나 MEMORY 스토리지 엔진을 사용하는 테이블에서는 INSERT 문장이 실행되면 즉시 새로운 키 값을 B-Tree 인덱스에 변경하지만, InnoDB 스토리지 엔진은 필요하다면 인덱스 키 추가 작업을 지연시켜 나중에 처리할 수 있다. 하지만 프라이머리 키나 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 즉시 B-Tree에 추가하거나 삭제한다.

인덱스 키 삭제

B-Tree의 키 값이 삭제되는 경우는 상당히 간단하다. 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료된다. 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재사용할 수 있다.

인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하며, MySQL 5.5 이상 버전의 InnoDB 스토리지 엔진에서는 버퍼링 되어 지연 처리될 수 있다. 처리가 지연된 인덱스 키 삭제 또한 사용자에게는 특별한 악영향 없이 MySQL 서버가 내부적으로 처리하므로 특별히 걱정할 것은 없다.

MyISAM이나 MEMORY 스토리지 엔진의 테이블에서는 체인지 버퍼와 같은 기능이 없으므로 인덱스 키 삭제가 완료된 후 쿼리 실행이 완료된다.

인덱스 키 변경

인덱스의 키 값은 값에 따라 저장될 리프 노드의 위치가 결정되므로 B-Tree의 키 값이 변경되는 경우에는 단순히 인덱스상의 키 값만 변경하는 것은 불가능하다. 따라서 B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다.

결국 인덱스 키 값을 변경하는 작업은 기존 인덱스 키 값을 삭제한 후 새로운 인덱스 키 값을 추가하는 작업으로 처리되고 InnoDB 스토리지 엔진을 사용하는 테이블에 대해서는 이 작업 모두 체인지 버퍼를 활용해 지연 처리 될 수 있다.

인덱스 키 검색

인덱스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행하는데, 이 과정을 트리 탐색이라고 한다.

인덱스 트리 탐색은 SELECT뿐만 아니라 UPDATE, DELETE를 처리하기 위해 해당 레코드를 검색해야 할 때도 사용된다.

B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있다.

  • 부등호 비교 조건에서도 인덱스를 활용할 수 있지만, 인덱스를 구성하는 키 값의 뒷부분만 검색하는 용도로는 사용할 수 없다.
  • 인덱스를 키 값에 변형이 가해진 후 비교되는 경우 빠른 검색 기능을 활용할 수 없다.(변형된 값은 인덱스에 존재하는 값이 아니므로)
    • 함수나 연산을 수행한 결과로 정렬 또는 검색

InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키락이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼있어, UPDATE, DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠그게 된다.

B-Tree 인덱스 사용에 영향을 미치는 요소

  • 컬럼 크기
  • 레코드의 건수
  • 유니크한 인덱스 키 값의 개수

인덱스 키 값의 크기

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다. 또한 페이지는 InnoDB 스토리지 엔진의 버퍼풀에서 데이터를 버퍼링하는 기본 단위이기도 하다. 인덱스도 결국 페이지 단위로 관리되며, 루트와 브랜치 리프 노드를 구분한 기준이 페이지 단위이다.

일반적으로 DBMS의 B-Tree는 자식 노드의 개수가 가변적인 구조다. 인덱스의 페이지 크기와 키 값의 크기에 따라 자식 노드의 최대 개수가 결정된다. MySQL 5.7 버전부터는 InnoDB 스토리지 엔진의 페이지 크기를 innodb_page_size 시스템 변수를 이용해 4KB ~ 64KB 사이의 값을 결정 할 수 있으며, 기본값은 16KB 이다.

인덱스 페이지는 인덱스 키 값과 해당하는 주솟값을 인덱스 페이지에 지정하게 되며, 페이지 크기가 변하지 않았을 경우 인덱스 키 값이 커지면 하나의 페이지에 저장되는 레코드의 개수는 줄어들게 된다. 키 크기가 커서 한 페이지에 300개의 레코드가 인덱스 페이지에 저장된다고 가정하면 SELECT 쿼리를 통해 500개의 데이터를 조회해야 한다고 했을때 최소한 2번 읽기 작업이 발생하게 된다.

따라서, 인덱스를 구성하는 키 값의 크기가 커지면 디스크로 부터 읽어와야 하는 횟수가 늘어날 수 있고, 그만큼 느려질 수 있다. 또한 인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미하기 때문에, 무한정 인덱스를 캐시해둘 수 없는 InnoDB의 버퍼풀, MyISAM의 키 캐시에 저장할 수 있는 공간이 부족해져 메모리 효율이 떨어질 수 있다.

B-Tree 깊이

인덱스의 깊이는 상당히 중요하지만 제어할 방법은 없다.

B-Tree의 깊이는 MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다. 인덱스 키 값의 크기가 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어지고, 이에 따라 같은 개수의 인덱스 키값을 저장하게 되면 더 깊어지게된다. 따라서 디스크 읽기가 더 많이 필요하게 된다.

인ㄷ게스 키 값의 크기는 가능한 작게 만드는 것이 좋지만, 실제로 아무리 대용량 데이터베이스라도 B-Tree의 깊이가 5단계 이상까지 깊어지는 경우는 흔하지 않다.

선택도(기수성)

인덱스에서 선택도(Selectivity) 또는 기수성(Cardinality)은 거의 같은 의미로 사용되며, 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다.

인덱스 키 값 가운데 중복된 값이 많아질수록 기수성은 낮아지고 동시에 선택도 또한 떨어지게 된다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

선택도가 좋지 않다고 하더라도 정렬이나 그루핑과 같은 작업을 위해 인덱스를 만드는 것이 훨씬 나은 경우도 많다. 인덱스가 항상 검색에만 사용되는 것은 아니므로 여러 가지 용도를 고려해 적절히 인덱스를 설계해야한다.

선택도가 낮은 인덱스를 처리하면 MySQL 서버는 불필요한 데이터를 더 많이 읽어오게 된다.

읽어야 하는 레코드의 건수

인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것 보다 높은 비용이 드는 작업이다. 따라서 인덱스를 이용한 읽기의 손익 분기점이 얼마인지를 판단할 필요가 있다.

일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도 비용이 더 많이 드는 작업인 것으로 예측한다. 즉 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20%~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 가려내는 방식으로 처리하는 것이 효율적이다.

많은 레코드를 읽을 때는 강제로 인덱스를 사용하도록 힌트를 추가해도 성능상 얻을 수 있는 이점이 없다.

B-Tree 인덱스를 통한 데이터 읽기

어떤 경우에 인덱스를 사용하게 유도할지, 또는 사용하지 못하게 할지 판단하려면 MySQL이 어떻게 인덱스를 이용해서 레코드를 읽어 내는지 알아야 한다.

인덱스 레인지 스캔

1
2
3

SELECT *
FROM employees
WHERE first_name BETWEEN 'Ebbe' AND 'Gad';

인덱스 레인지 스캔

인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 대 사용하는 방식이다. 검색하려는 값의 수나 검색 결과 레코드 건수와 관계 없이 레인지 스캔이라고 표현한다.

루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 찾아 들어가야만 비로소 필요한 레코드의 시작 지점을 찾을 수 있다. 이처럼 차례대로 죽 읽는 것을 스캔이라고 표현하며, 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드의 구간은 실제 스캔하는 범위를 표현한다.

B-Tree 인덱스에서 루트와 브랜치 노드를 이용해 스캔 시작 위치를 검색하고, 그 지점부터 필요한 방향으로 인덱스를 읽어 나간다. 인덱스 자체 정렬 특성으로 인해 어떤 방식으로 스캔하든 관계없이, 해당 인덱스를 구성하는 컬럼의 정순 또는 역순으로 정렬된 상태로 레코드를 가져온다.

인덱스의 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다. 이때 리프노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 레코드 한 건 단위로 랜덤 I/O가 한 번 씩 일어난다. 이러한 이유 때문에 인덱스를 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 작업으로 분류된다.

  1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다.
  2. 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 쭉 읽는다.(인덱스 스캔)
  3. 읽어 들인 인덱스 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽어온다.

쿼리가 필요로 하는 데이터에 따라 3번 과정은 필요하지 않을 수도 있는데, 이를 커버링 인덱스라고 한다. 커버링 인덱스로 처리되는 쿼리는 디스크의 레코드를 읽지 않아도 되기 때문에 랜덤 읽기가 상당히 줄어들고 그만큼 빨라진다.

1

SHOW STATUS LIKE 'Handler_%';

위 쿼리를 통해 읽은 레코드 건수를 조회할 수 있으나, 실제 인덱스만 읽었는지 인덱스를 통해 테이블의 레코드를 읽었는지(3번)은 구분할 수 없다.

  • Handler_read_key: 1번 단계가 실행된 횟수
  • Handler_read_next: 인덱스 정순으로 읽은 레코드 건수
  • Handler_read_prev: 인덱스 역순으로 읽은 레코드 건수
  • Handler_read_first: 첫 번째 레코드를 읽은 횟수 (MIN)
  • Handler_read_last: 마지막 레코드를 읽은 횟수 (MAX)

인덱스 풀 스캔

인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 읽는 방식이다. 대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다.

  • 인덱스 리프 노드의 제일 앞 또는 제일 뒤로 이동한다.
  • 인덱스의 리프 노드를 연결하는 링크드 리스트를 따라서 처음부터 끝까지 스캔한다.

인덱스 풀 스캔은 인덱스에 포함된 컬럼만으로 쿼리를 처리할 수 있는 경우 테이블의 레코드를 읽을 필요가 없어 테이블 풀 스캔보다는 효율적이다. 인덱스의 전체 크기는 테이블 자체의 크기보다는 훨씬 작으므로 더 적은 디스크 I/O로 처리할 수 있다.

루스 인덱스 스캔

오라클 DBMS의 인덱스 스킵 스캔비슷하게 처리되는 방법으로 MySQL 5.7 버전 까지는 기능이 많이 제한적이었지만, MySQL 8.0 버전부터는 다른 상용 DBMS에서 지원하는 인덱스 스킵 스캔과 같은 최적화를 조금씩 지원하기 시작했다.

인덱스 레인지 스캔과 인덱스 풀 스캔은 루스 인덱스 스캔과는 상반된 의미로 타이트 인덱스 스캔으로 분류한다.

루스 인덱스 스캔이란 말 그대로 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미한다. 인덱스 레인지 스캔과 비슷하게 작동하지만 중간에 필요치 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리한다. 일반적으로 GROUP BY 또는 집합 함수 중 MIN(), MAX() 함수에 대해 최적화를 하는 경우 사용된다.

1
2
3
4
5
6

SELECT dept_no
     ,MIN(emp_no)
FROM dept_emp
WHERE dep_no BETWEEN 'd002' AND 'd004'
GROUP BY dept_no
;

인덱스에서 WHERE조건을 만족하는 범위 전체를 다 스캔할 필요가 없다는 것을 옵티마이저는 알고 있기 때문에 조건에 만족하지 않는 레코드는 무시하고 다음 레코드로 이동한다. 루스 인덱스 스캔을 사용하려면 여러가지 조건을 만족해야 한다.

인덱스 스킵 스캔

데이터베이스 서버에서 인덱스의 핵심은 값이 정렬돼 있다는 것이며, 이로 인해 인덱스를 구성하는 컬럼의 순서가 매우 중요하다.

1
2
3

ALTER TABLE employees
ADD INDEX ix_gender_birthdate (gender, birth_date)
;

인덱스를 사용하려면 WHERE조건절에 gender 컬럼에 대한 비교 조건이 필수이다.

1
2
3
4
5
6
7
8
9

/* 인덱스 X */
SELECT * FROM employees WHERE birth_date >= '1965-02-01';

/* 인덱스 O */
SELECT * 
FROM employees 
WHERE gender = 'M'
    AND birth_date >= '1965-02-01'
;

따라서 위 두 쿼리중 gender 컬럼과 birth_date 컬럼의 조건을 모두 가진 두 번째 쿼리는 인덱스를 효율적으로 사용할 수 있지만, gender 컬럼에 대한 비교 조건이 없는 첫 번째 쿼리는 인덱스를 사용할 수 없어 birth_date 컬럼부터 시작하는 인덱스를 생성해야만 했다.

MySQL 8.0 버전부터는 옵티마이저가 gender 컬럼을 건너 뛰어서 birth_date 컬럼만으로도 인덱스 검색이 가능하게 해주는 인덱스 스킵 스캔 최적화 기능이 도입됐다.

1
2
3
4
5
6

SET optimizer_switch='skip_scan=on';

SELECT * 
FROM employees 
WHERE birth_date >= '1965-02-01'
;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

SELECT *
FROM employees
WHERE gender = 'M'
  AND birth_date >= '1965-02-01'
;

SELECT *
FROM employees
WHERE gender = 'F'
  AND birth_date >= '1965-02-01'
;

위의 쿼리는 아래의 쿼리로 나눠 실행한 것과 비슷한 형태로 최적화를 실행한다.

인덱스 스킵 스캔은 새롭게 도입된 기능이어서 아직 다음과 같은 단점이 있다.

  • WHERE 조건절에 조건이 없는 인덱스의 선행 컬럼의 유니크한 값의 개수가 적어야함
  • 쿼리가 인덱스에 존재하는 컬럼만으로 처리 가능해야함(커버링 인덱스)

다중 컬럼 인덱스

실제 서비스용 데이터베이스에서는 2개 이상의 컬럼을 포함하는 인덱스가 더 많이 사용된다. 두개 이상의 컬럼으로 구성된 인덱스를 다중 컬럼 인덱스(복합 컬럼 인덱스, Concatenated Index)라고 한다.

인덱스의 두 번째 컬럼은 첫 번째 컬럼에 의존해서 정렬돼있다. 즉 두 번째 컬럼의 정렬은 첫 번째 컬럼이 똑같은 레코드에서만 의미가 있다. 위의 예제에서 emp_no 값의 정렬 순서가 빠르다고 하더라도 dept_no 컬럼의 정렬 순서가 늦다면 인덱스의 두쪽에 위치한다. 따라서 다중 컬럼 인덱스에서는 인덱스 내에서 각 컬럼의 위치(순서)가 상당히 중요하여 신중히 결정해야 한다.

B-Tree 인덱스의 정렬 및 스캔 방향

인덱스를 생성할 때 설정한 정렬 규칙에 따라 인덱스의 키 값은 항상 오름차순이거나 내림차순으로 정렬되어 저장된다. 하지만 읽을때는 반대로도 가능하며, 인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 실시간으로 만들어 내는 실행 계획에 따라 결정된다.

인덱스의 정렬

MySQL 5.7 버전까지는 컬럼 단위로 정렬 순서를 혼합해서 인덱스를 생성할 수 없었지만, 8.0 버전부터는 순서를 혼합한 인덱스도 생성할 수 있게 되었다.

1

CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC);

인덱스 스캔 방향

인덱스는 항상 오름차순으로만 정렬돼 있지만 인덱스를 최솟값부터 읽으면 오름차순으로 값을 가져올 수 있고, 최댓값부터 거꾸로 읽으면 내림차순으로 값을 가져올 수 있다는 것을 MySQL 옵티마이저는 이미 알고 있다. 즉 인덱스 생성 시점에 오름차순 또는 내림차순으로 정렬이 결정되지만 쿼리가 그 인덱스를 사용하는 시점에 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬 효과를 얻을 수 있다.

ORDER BY 처리나 MIN, MAX 함수등의 최적화가 필요한 경우에도 인덱스의 읽기 방향을 전환해서 사용하도록 실행 계획을 만들어낸다.

내림차순 인덱스

MySQL 서버는 실제 내림차순인지 오름차순인지 관계없이 인덱스를 읽는 순서만 변경해서 해결할 수 있지만, 2개 이상의 컬럼으로 구성된 복합 인덱스에서 각각의 컬럼이 내림차순과 오름차순이 혼합된 경우는 내림차순 인덱스로만 해결될 수 있다.

실제 역순 정려 쿼리가 정순 정렬 쿼리보다 더 시간이 많이 걸린다. MySQL 서버의 InnoDB 스토리지 엔진에서 정순 스캔과 역순 스캔은 페이지 간의 양방향 연결 고리를 통해 전진하느냐 후진하느냐의 차이만 있지만, 실제 내부적으로는 InnoDB에서 인덱스 역순 스캔이 더 느린 이유는 2가지가 있다.

  • 페이지 잠금이 인덱스 정순 스캔에 적합한 구조
  • 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조

쿼리가 많은 레코드를 조회하면서 빈번하게 실행된다면 오름차순 인덱스보다는 내림차순 인덱스가 더 효율적이다. 또한 많은 쿼리가 인덱스의 한쪽만을 집중적으로 읽어 특정 페이지 잠금이 병목이 될 것으로 예상된다면 쿼리에서 자주 사용되는 정렬 순서대로 인덱스를 생성하는 것이 잠금 병목 현상은 완화하는 데 도움이 될 수 있다.

B-Tree 인덱스의 가용성과 효율성

쿼리의 WHERE 조건이나 GROUP BY, ORDER BY 절이 어떤 경우에 인덱스를 사용할 수 있고 어떤 방식으로 사용할 수 있는지 식별할 수 있어야 인덱스를 최적으로 생성할 수 있다.

비교 조건의 종류와 효율성

다중 컬럼 인덱스에서 각 컬럼의 순서와 그 컬럼에 사용된 조건이 동등 비교인지 아니면 범위 조건인지에 따라 인덱스 컬럼 활용 형태가 달라지며, 효율 또한 다르다.

1
2
3
4
5

SELECT *
FROM dept_emp
WHERE dept_no='d002'
    AND emp_no >= 10114
;
  • A: INDEX (dept_no, emp_no)
    • dept_no='d002' AND emp_no >=10114 인 레코드들을 찾고 dept_no가 ‘d002’가 아닐 때까지 인덱스를 읽는다.
    • 조건을 만족하는 레코드를 찾는데 필요한 비교 작업만 수행하므로 효율적으로 인덱스를 활용했다.
  • B: INDEX (emp_no, dept_no)
    • emp_no >=10114 AND dept_no='d002' 인 레코드들을 찾고 dept_no가 모든 레코드가 ‘d002’인지 비교한다.

인덱스를 통해 읽은 레코드가 나머지 조건에 맞는지 비교하면서 취사선택하는 작업을 필터링이라고 하며, 케이스 B 인덱스에서는 다중 컬럼 인덱스의 정렬 방식으로 인해 최종적인 조건을 만족하는 레코드를 찾기 위해 더 큰 범위의 데이터를 가져와 비교했다.

공식적인 명칭은 아니지만 케이스 A 인덱스에서의 도 조건과 같이 작업의 범위를 결정하는 조건을 작업 범위 결정 조건이라 하고 케이스 B 인덱스같이 비교 작업의 범위를 줄이지 못하고 거름종이 역할만 하는 조건을 필터링 조건, 체크 조건이라고 표현한다.

작업 범위를 결정하는 조건은 많으면 많을수록 쿼리의 처리 성능을 높이지만 체크 조건은 많다고 해서 쿼리의 처리 성능을 높히지는 못한다.

인덱스의 가용성

B-Tree 인덱스의 특징은 왼쪽 값에 기준해서 오른쪽 값이 정렬된다. 하나의 컬럼 내에서 뿐만 아니라 다우 컬럼 인덱스의 컬럼에 대해서도 함께 적용된다.

  • A: INDEX (first_name)
  • B: INDEX (dept_no, emp_no)

인덱스 키 값의 이런 정렬 특성은 빠른 검색의 전제 조건이다. 즉 하나의 컬럼으로 검색해도 값의 왼쪽 부분이 없으면 인덱스 레인지 스캔 방식의 검색이 불가능하다. 또한 다중 컬럼 인덱스에서도 왼쪽 컬럼의 값을 모르면 인덱스 레인지 스캔을 사용할 수 없다.

1
2
3
4

SELECT *
FROM employees
WHERE first_name LIKE '%mer'
;

first_name 컬럼에 저장된 값의 왼쪽부터 한 글자씩 비교해 가면서 일치하는 레코드를 찾아야 하는데, LIKE 조건으로 왼쪽 부분이 고정되지 않았기 때문에 인덱스 레인지 스캔 방식으로 인덱스를 사용할 수 없다.

1
2
3
4

SELECT *
FROM dept_emp
WHERE emp_no >= 10144
;

인덱스가 dept_no 기준으로 생성되었기 때문에 dept_no 조건 없이 검색하면 인덱스를 효율적으로 사용할 수 없다.

가용성과 효율성 판단

기본적으로 B-Tree 인덱스의 특성상 다음 조건에서는 사용할 수 없다. (작업 범위 결정 조거능로 사용할 수 없다.)

  • NOT-EQUAL로 비교된 경우(<>,NOT IN, NOT BETWEEN, IS NOT NULL)
  • LIKE '%??' 형태로 문자열 패턴이 비교된 경우
  • 스토어드 함수나 다른 연산자로 인덱스 컬럼이변형된 후 비교된 경우
    • WHERE SUBSTRING(column, 1, 1) = 'X
    • WHERE DAYOFMONTH(column) = 1
  • NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우
    • WHERE column = deterministic_function()
  • 데이터 타입이 서로 다른 비교(인덱스 컬럼의 타입을 변환해야 비교가 가능한 경우)
  • 문자열 데이터 타입의 콜레이션이 다른 경우

다른 일반적은 DBMS에서는 NULL 값이 인덱스에 저장되지 않지만 MySQL 에서는 NULL 값도 인덱스에 저장된다. 다음과 같은 WHERE 조건도 작업 범위 결정 조건으로 인덱스를 사용한다. (WHERE column IS NULL)

다중 컬럼 인덱스

1

INDEX ix_test ( column_1, .. column_n )
  • 작업 범위 결정 조건으로 인덱스를 사용하지 못하는 경우
    • column_1 컬럼에 대한 조건이 없는 경우
    • column_1 컬럼의 비교 조건이 위의 인덱스 사용 불가 조건 중 하나인 경우
  • 작업 범위 결정 조건으로 사용하는 경우
    • column_1 ~ column_(i-1)컬럼까지 동등 비교 형태(=, IN)
    • column_i 컬럼에 대해 다음 연산자 중 하나로 비교
      • 동등 비교
      • 크다 작다 형태
      • LIKE로 좌특 일치 패턴

적업 범위 결정 조건으로 인덱스를 사용하는 쿼리 패턴은 이 밖에도 상당히 많지만, 대표적인 것을 기억해 두면 좀 더 효율적인 쿼리를 쉽게 작성할 수 있다.