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

목차

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

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

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

 

 

 

어떤 경우에 인덱스를 사용하게 유도할지, 또는 사용하지 못하게 할지 판단하려면 MySQL이 어떻게 인덱스를 이용해서 실제 레코드를 읽어 내는지 알아야 한다. MySQL이 인덱스를 이용하는 방법들과 인덱스의 정렬, 가용성에 대해 알아본다.

 

 

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

1) 인덱스 레인지 스캔

인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다.

 

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

(1) 인덱스 레인지 스캔

루트 노드 → 브랜치 노드 → 리프 노드(n) → 리프 노드(n+1) → ... → 레코드 반환

1. 루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 리프 노드까지 찾아가 레코드의 시작 지점을 찾는다.
2. 시작 지점부터 순서대로 레코드를 읽는다.
3. 페이지의 끝까지 읽으면 리프 노드간의 링크(Linked list)를 이용해 다음 리프 노드를 찾아서 다시 스캔한다.
4. 최종적으로 레코드를 끝까지 읽으면 사용자에게 반환한다.

 

(2) 인덱스 레인지 스캔을 통한 레코드 읽기

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

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

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

 

 

(커버링 인덱스)

쿼리가 필요로 하는 데이터가 인덱스의 키로 사용되고 있는 경우 디스크의 레코드를 읽지 않을 수도 있는데 이를 커버링 인덱스라고 한다. 랜덤 읽기가 상당히 줄어들기 때문에 그만큼 성능이 빨라진다.

 

 

2) 인덱스 풀 스캔

인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 한다.

대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 사용된다.

 

쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우 이 방식이 사용되고 디스크 I/O가 적기 때문에 테이블 풀 스캔보다 빠르지만 인덱스 레인지 스캔 보다는 느리다. 인덱스 뿐만 아니라 데이터 레코드까지 모두 읽어야 한다면 이 방식으로 처리되지 않는다. 인덱스 풀 스캔은 일반적으로 인덱스를 생성하는 목적은 아니다.

 

 

3) 루스 인덱스 스캔

인덱스 레인지 스캔과 비슷하게 작동하지만 중간에 필요치 않은 인덱스 키 값은 무시(SKIP)하고 다음으로 넘어가는 형태로 처리한다. 일반적으로 GROUP BY 또는 집합 함수 가운데 MAX() 또는 MIN() 함수에 대해 최적화를 하는 경우에 사용한다.

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

dept_no 그룹별로 첫 번째 레코드의 emp_no 값만 읽으면 되기 때문에 옵티마이저는 조건에 만족하지 않는 레코드는 무시하고 다음 레코드로 이동한다.

 

 

4) 인덱스 스킵 스캔

다중 컬럼 인덱스의 선행 컬럼이 쿼리의 조건절에 없는 경우, 선행 컬럼의 유니크한 값을 비교하는 조건을 쿼리에 추가해서 다시 실행하는 형태로 동작하게 한다.

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

-- 인덱스 레인지 스캔으로 동작
SELECT * FROM employees WHERE gender = 'M' AND birth_date >= '1965-02-01';

인덱스를 효율적으로 사용하기 위해 gender 컬럼과 birth_date 컬럼의 조건을 쿼리가 모두 가져야 한다.

 

-- 인덱스 풀 스캔으로 동작
SELECT gender, birth_date FROM employees WHERE birth_date >= '1965-02-01';

인덱스의 선행 컬럼인 gender가 쿼리의 조건에 없는 경우에는 인덱스 풀 스캔 혹은 테이블 풀 스캔으로 동작하는데

MySQL 8.0 버전부터 옵티마이저가 gender 컬럼을 건너뛰어서 인덱스 검색이 가능하도록 하는 최적화 기능이 도입됐다.

우선 gender 컬럼에서 유니크한 값을 모두 조회해서 주어진 쿼리에 gender 컬럼의 조건을 추가해서 쿼리를 다시 실행한다.

 

인덱스 스킵 스캔의 제약 조건

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

 

 

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

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

 

1) 인덱스의 정렬

인덱스 생성 시점에 ASC, DESC 키워드로 인덱스의 정렬 방향을 설정할 수 있다.

CREATE INDEX ix_firstname ON employees (first_name ASC);

 

2) 인덱스 스캔 방향

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

-- ix_firstname 인덱스를 정순으로 10개 스캔
SELECT * FROM employees ORDER BY first_name ASC LIMIT 10;

-- ix_firstname 인덱스를 역순으로 10개 스캔
SELECT * FROM employees ORDER BY first_name DESC LIMIT 10;

 

3) 내림차순 인덱스

다음과 같은 이유로 InnoDB에서 인덱스 역순 스캔이 정순 스캔에 비해 느리다.

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

따라서 쿼리에서 자주 사용되는 정렬 순서대로 인덱스를 생성하는 것이 효율적이다.

 

 

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

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

 

1) 비교 조건의 종류와 효율성

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

 

(1) 케이스 A: INDEX (dept_no, emp_no)

• " dept_no = 'd002' AND emp_no >= 10114 " 인 레코드를 찾고, 그 이후에는 dept_no가 'd002'가 아닐 때까지 인덱스 스캔
• 필요한 만큼의 비교작업만 수행하므로 효율적
• 5번의 비교로 5건 반환

(2) 케이스 B: INDEX (emp_no, dept_no)

• " emp_no >= 10114 AND dept_no = 'd002' " 인 레코드를 찾고, 그 이후 모든 레코드에 대해 dept_no가 'd002'인지 비교
• dept_no가 범위를 좁히는데 도움을 주지 못하기 때문에 비효율적
• 7번의 비교로 5건 반환

 

케이스 A에서 사용된 두 조건(dept_no = 'd002' AND emp_no >= 10114)과 같이 작업 범위를 결정하는 조건은 많으면 많을수록 쿼리의 처리 성능을 높이지만 케이스 B에서 사용된 조건(dept_no = 'd002')과 같은 체크 조건은 쿼리의 성능을 높이지 못하고 오히려 더 느리게 만들 때가 많다.

 

 

2) 인덱스의 가용성

• B-Tree 인덱스는 왼쪽 값에 기준해서 오른쪽 값이 정렬돼 있기 때문에 정렬 우선순위가 낮은 뒷부분의 값만으로는 인덱스의 효과를 얻을 수 없다.

INDEX (first_name)
SELECT * FROM dept_emp WHERE first_name LIKE '%mer';

 

• 다중 컬럼 인덱스는 첫번째 컬럼으로 정렬한 후 두번째 컬럼으로 정렬돼 있기 때문에 인덱스의 선행 컬럼 조건없이 검색하면 인덱스를 효율적으로 사용할 수 없다.

INDEX (dept_no, emp_no)
SELECT * FROM dept_emp WHERE emp_no >= 10144;

 

 

3) 가용성과 효율성 판단

(1) 인덱스 사용 불가 조건

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

 

(2) 멀티 컬럼 인덱스의 가용성

INDEX ix_test ( column_1, column_2, column_3, ... , column_n)

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

 

다른 일반적인 DBMS에서는 NULL 값이 인덱스에 저장되지 않지만 MySQL에서는 NULL 값도 인덱스에 저장되기 때문에 작업 범위 결정 조건으로 인덱스를 사용한다.

WHERE column IS NULL

 

 

 

 

 

 

 

참고

Real MySQL 8.0 (1권)