[MySQL] B-Tree 인덱스

기존의 Real MySQL (5.0, 5.1 버전) 책을 너무 유익하게 봤는데, Real MySQL 8.0이 전면 개정판이 나와서... 설레는 마음에 보면서 개인적인 공부용으로 정리하고 있습니다.
역시 믿고 보는 Real MySQL... 👍 한번 사서 보시는 것을 강력 추천드립니다!

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

---

스토리지 엔진이 어떻게 인덱스를 이용해서 실제 레코드를 읽어 내는지에 대한 내용. (MySQL이 인덱스를 이용하는 대표적인 방법)

인덱스 레인지 스캔

대표적인 세 가지 방법 중 가장 빠른 방법

SELECT * FROM employees WHERE first_name BETWEEN 'AAA' AND 'BBB';

인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식. (레코드의 건수와 상관없이)

스캔 과정

• 루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 찾아 들어가야만 비로소 필요한 레코드의 시작 지점을 찾을 수 있다.
• 시작해야 할 위치를 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 된다.
  • 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔한다.
  • 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다.

레코드를 읽어오는 과정

인덱스의 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다.

• 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 레코드 한 건 한 건 단위로 랜덤 I/O가 한 번씩 일어난다.
• 인덱스를 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 작업으로 분류돼, 인덱스를 통해 읽어야 할 데이터 레코드가 20~25%를 넘으면 인덱스를 통한 읽기보다 테이블의 데이터를 직접 읽는 것이 더 효율적인 접근 방식이다.

인덱스 레인지 스캔 과정 정리

1. 인덱스 탐색: 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다.

2. 인덱스 스캔: 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 쭉 읽는다.

3. 2번에서 읽어 들인 인덱스 키와 레코드 주소를 이용해서 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽어온다.

커버링 인덱스

상황에 따라 3번 과정은 필요하지 않을 수도 있는데, 커버링 인덱스라고 한다.

• 커버링 인덱스로 처리되는 쿼리는 디스크의 레코드를 읽지 않아도 되기 때문에 랜덤 읽기가 상당히 줄어들고 성능은 그만큼 빨라진다.

인덱스 풀 스캔

인덱스의 처음부터 끝까지 모두 읽는 방식

• 일반적으로 인덱스의 크기는 테이블의 크기보다 작으므로 직접 테이블을 처음부터 끝까지 읽는 것보다는 인덱스만 읽는 것이 효율적이다.
• 인덱스 풀 스캔은 테이블 전체를 읽는 것보다는 적은 디스크 I/O로 쿼리를 처리할 수 있다.
  • 인덱스의 전체 크기는 테이블 자체의 크기보다는 훨씬 작기 때문에
• 쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용된다. (인덱스뿐만 아니라 데이터 레코드까지 모두 읽어야 한다면 절대 이 방식으로 처리되지 않는다)

인덱스 풀 스캔 처리 방식

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

루스 인덱스 스캔

듬성듬성하게 인덱스를 읽는 것.

• MySQL 5.7 버전까지는 MySQL의 루스 인덱스 스캔 기능이 많이 제한적이었지만, MySQL 8.0 버전부터는 다른 사용 DBMS에서 지원하는 인덱스 스킵 스캔과 같은 최적화를 조금씩 지원하기 시작했다.

인덱스 레인지 스캔과 비슷하게 작동하지만 중간에 필요하지 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리한다.

• 일반적으로 GROUP BY 또는 MAX(), MIN() 함수에 대해 최적화를 하는 경우 사용된다.

인덱스 스킵 스캔

# 인덱스가 (gender, birth_date)로 생성되어 있는 경우

SELECT * FROM employees WHERE birth_date >= '1998-02-12';

• 다음과 같은 경우 MySQL 8.0 이전에는 인덱스를 사용할 수 없었다. (주로 이런 경우에는 birth_date 칼럼부터 시작하는 인덱스를 새로 생성해야만 했음)
• MySQL 8.0 버전부터는 옵티마이저가 gender 칼럼을 건너뛰어서 birth_date 칼럼만으로도 인덱스 검색이 가능하게 해주는 인덱스 스킵 스캔 최적화 기능이 도입됐다.
  • MySQL 8.0 이전 버전에도 인덱스 스킵 스캔과 비슷한 최적화를 수행하는 루스 인덱스 스캔이라는 기능이 있었지만, 루스 인덱스 스캔은 GROUP BY 작업을 처리하기 위해 인덱스를 사용하는 경우에만 적용할 수 있었는데, MySQL 8.0 버전부터 WHERE 조건절의 검색을 위해 사용 가능하도록 용도가 훨씬 넓어진 것이다.

다중 칼럼 인덱스

---

두 개 이상의 칼럼으로 구성된 인덱스로, Concatenated Index라고도 한다.

• 인덱스의 두 번째 칼럼은 첫 번째 칼럼에 의존해서 정렬돼 있다. (두 번째 칼럼의 정렬은 첫 번째 칼럼이 똑같은 레코드에서만 의미가 있다는 것)
• 이러한 이유로 다중 칼럼 인덱스에서는 인덱스 내에서 각 칼럼의 위치가 상당히 중요하다.

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

---

인덱스를 생성할 때 설정한 정렬 규칙에 따라 인덱스의 키 값은 항상 오름차순이거나 내림차순으로 정렬되어 저장된다. 하지만 어떤 인덱스가 오름차순으로 생성됐다고 해서 그 인덱스를 오름차순으로만 읽을 수 있다는 뜻은 아니다.

• 인덱스를 거꾸로 끝에서부터 읽으면 내림차순으로 정렬된 인덱스로도 사용될 수 있다.

인덱스의 정렬

MySQL 5.7 버전까지는 칼럼 단위로 정렬 순서를 혼합(ASC, DESC를 혼합)해서 인덱스를 생성할 수 없었다.

• 이런 문제를 해결하기 위해 숫자 칼럼의 경우 -1을 곱한 값을 저장하는 우회 방법을 사용했었다.

MySQL 8.0 버전부터는 정렬 순서를 혼합한 인덱스도 생성할 수 있게 됐다.

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

인덱스의 스캔 방향

인덱스 생성 시점에 오름차순 또는 내림차순으로 정렬이 결정되지만 쿼리가 그 인덱스를 사용하는 시점에 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬 효과를 얻을 수 있다.

내림차순 인덱스

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

• 다음과 같이 복합 인덱스에서 각각의 칼럼이 내림차순과 오름차순으로 혼합된 경우에는 MySQL 8.0의 내림차순 인덱스로만 해결될 수 있다.

MySQL 8.0 내림차순 인덱스 동작 방식

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

인덱스 역순 스캔이 정순 스캔에 비해 느린 이유

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

많은 쿼리가 인덱스의 앞쪽만 또는 뒤쪽만 집중적으로 읽어서 인덱스의 특정 페이지 잠금이 병목이 될 것으로 예상된다면 쿼리에서 자주 사용되는 정렬 순서대로 인덱스를 생성하는 것이 잠금 병목 현상을 완화하는 데 도움이 될 것이다.

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

---

비교 조건의 종류와 효율성

SELECT * FROM dept_emp
WHERE dept_no='d002' AND emp_no >= 10114;

# 케이스 A: INDEX (dept_no, emp_no)
# 케이스 B: INDEX (emp_no, dept_no)

다음과 같이 두 가지 인덱스를 생성하는 케이스가 있다고 가정하자.

케이스 A

• dept_no='d002' AND emp_no ≥10144인 레코드를 찾고, 그 이후에는 dept_no가 d002가 아닐 때까지 인덱스를 그냥 쭉 읽기만 하면 된다. (읽은 레코드가 모두 사용자가 원하는 결과)
  • 조건을 만족하는 레코드가 5건이라고 할 때, 5건의 레코드를 찾는 데 꼭 필요한 5번의 비교 작업만 수행한 것이므로 상당히 효율적으로 인덱스를 이용한 것.

케이스 B

• 우선 emp_no≥1044 AND dept_no='d002'인 레코드를 찾고, 그 이후 모든 레코드에 대해 dept_no가 'd002'인지 비교하는 과정을 거쳐야 한다.
• 이처럼 인덱스를 통해 읽은 레코드가 나머지 조건에 맞는지 비교하면서 취사선택하는 작업을 필터링이라고 한다.

정리

• 케이스 A처럼 작업의 범위를 결정하는 조건을 작업 범위 결정 조건이라고 한다.
• 케이스 B처럼 비교 작업의 범위를 줄이지 못하고 단순히 거름종이 역할만 하는 조건을 필터링 조건이라고 한다.
• 작업 범위를 결정하는 조건은 많으면 많을수록 쿼리의 처리 성능을 높인다.
• 반면, 필터링 조건이 많다고 해서 쿼리의 처리 성능을 높이지는 못한다. (오히려 쿼리 실행을 느리게 하는 경우가 많음)

인덱스의 가용성

B-Tree 인덱스의 특징이자 주의사항은 왼쪽 값에 기준해서 오른쪽 값이 정렬돼 있다는 것이다.

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

• 따라서 다음과 같은 쿼리는 인덱스 레인지 스캔 방식으로 인덱스를 이용할 수 없다.

SELECT * FROM dept_emp WHERE emp_no>=10144;

# INDEX (dept_no, emp_no)

• 다음과 같이 인덱스의 선행 칼럼인 dept_no 조건 없이 emp_no 값으로만 검색하면 인덱스를 효율적으로 사용할 수 없다.

가용성과 효율성 판단

B-Tree에서 다음과 같은 조건에서는 인덱스를 사용할 수 없다. (작업 범위 결정 조건으로)

• NOT-EQUAL로 비교된 경우
  • NOT IN, <>, NOT BETWEEN, IS NOT NULL
• 뒷부분 일치 형태로 문자열 패턴이 비교된 경우
  • LIKE '%??'
• 스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우
  • WHERE SUBSTRING(column, 1, 1) = 'X
• 데이터 타입이 서로 다른 비교
  • WHERE char_column = 10
• 문자열 데이터 타입의 콜레이션이 다른 경우
  • WHERE utf_bin_char_column = euckr_bin_char_column

다른 일반적인 DBMS에서는 NULL 값이 인덱스에 저장되지 않지만 MySQL에서는 NULL 값도 인덱스에 저장된다.

SELECT ... FROM WHERE column IS NULL