B-Tree 인덱스 2편

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

어떤 경우에 인덱스를 사용하게 유도할지, 또는 사용하지 못하게 할지 판단하려면 각 스토리지 엔진이 어떻게 인덱스를 이용(경유)해서

실제 레코드를 읽어 내는지 알아야 한다.

인덱스 레인지 스캔

인덱스 레인지 스캔은 인덱스의 접근 방법 가운데 가장 대표적이며, 앞으로 나올 두 가지 접근 방식보다 빠른 방법이다.

인덱스를 통해 레코드를 한 건만 읽는 경우와 한 건이상을 읽는 경우를 각각 다른 이름으로 구분하지만, 

이번에는 모두 묶어서 인덱스 레인지 스캔이라고 표현했다.

 

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

검색하려는 값의 수나 결과 레코드 건수와 관계 없이 레인지 스캔이라고 표현한다.

루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고

최종적으로 리프 노드까지 찾아 들어가야만 비로소 필요한 레코드의 시작점을 알 수 있다.

 

일단 시작해야 할 위치를 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 된다.

차례대로 쭉 읽는 것을 스캔이라고 표현했는데,

만약 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔한다.

그리고 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다.

 

인덱스 레인지 스캔은 크게 3단계를 거친다.

 

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

인덱스 풀 스캔

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

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

예를 들어 인덱스는 (A, B, C) 칼럼의 순서로 만들어져  있지만 쿼리의 조건절은 B 칼럼이나 C 칼럼으로 검색하는 경우다.

 

일반적으로 인덱스의 크기는 테이블의 크기보다 작으므로 직접 테이블을 처음부터 끝까지 읽는 것보다는 인덱스만 읽는 것이 효율적이다.

쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용된다.

데이터 레코드까지 모두 읽어야 한다면 절대 이 방식으로 처리되지 않는다.

 

인덱스 풀 스캔은

먼저 인덱스 리프 노드의 제일 앞 또는 제일 뒤로 이동한 후,

인덱스의 리프 노드를 연결하는 링크드 리스트를 따라서 처음부터 끝까지 스캔한다.

 

이 방식은 인덱스 레인지 스캔보다는 빠르지 않지만 테이블 풀 스캔보다는 효율적이다.

참고

인덱스 풀 스캔 방식 또한 인덱스를 이용하는 것이지만 효율적인 방식은 아니며, 일반적으로 인덱스를 생성하는 목적은 아니다.

루스 인덱스 스캔

루스(Loose) 인덱스 스캔은 말 그대로 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미한다.

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

일반적으로 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_emp 테이블은 dept_no와 emp_no라는  2개의 칼럼으로 인덱스가 생성돼 있다.

또한 인덱스는 (dept_no, emp_no) 조합으로 정렬까지 돼 있다.

따라서 dept_no 그룹별로 첫 번째 emp_no 값만 읽으면 된다.

인덱스에서 WHERE 조건을 만족하는 범위 전체를 다 스캔할 필요가 없다는 것을 옵티마이저는 알고 있기 때문에

조건에 만족하지 않는 레코드는 무시하고 다음 레코드로 이동한다.

인덱스 스킵 스캔

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

아래 인덱스 생성 쿼리를 살펴보자.

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

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

#인덱스를 사용하지 못하는 쿼리
SELECT * FROM employees WHERE birth_date >= '1965-02-01';
	
#인덱스를 사용할 수 있는 쿼리
SELECT * FROM employees WHERE gender='M' AND birth_date >= '1965-02-01';

MySQL 8.0 버전부터는 옵티마이저가 gender 칼럼을 건너뛰어서 birth_date 칼럼만으로도 인덱스 검색이

가능하게 해주는 인덱스 스킵 스캔 최적화 기능이 도입됐다.

물론 루스 인덱스 스캔이라느 기능이 있었지만 루스 인덱스 스캔은 GROUP BY 작업을 처리하기 위해 인덱스를 사용하는 경우에만 적용할 수 있었다.

인덱스 스킵 스캔은 WHERE 조건절의 검색을 위해 사용 가능하도록 용도가 넓어진 것이다.

 

구체적인 인덱스 스킵 스캔 예제는 책 p.238에서 확인할 수 있다.

 

인덱스 스킵은 MySQL 8.0 버전에 새로이 도입된 기능이라 아직 아래와 같은 단점이 있다고 한다.

 

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

다중 칼럼 인덱스

실제 서비스용 데이터베이스에서는 2개 이상의 칼럼을 포함하는 인덱스가 더 많이 사용된다.

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

루트 노드는 편의상 생략했다.

다중 칼럼 인덱스 (d003, 10144)는 오타. d002로 썼어야함. 추후 수정하자.

위 그림에서 중요한 것은 인덱스의 두 번째 칼럼은 첫 번째 칼럼에 의존해서 정렬돼 있다는 것이다.

즉, 두 번째 칼럼의 정렬은 첫 번째 칼럼이 똑같은 레코드에서만 의미가 있다는 것이다.

칼럼이 2개뿐이지만, 만약 칼럼이 4개인 인덱스를 생성한다면 세 번째 칼럼은 두 번째 칼럼에 의존해서 정렬되고 네 번째 칼럼은 다시 세 번째 칼럼에 의존해서 정렬된다.

다중 칼럼 인덱스에서는 인덱스 내에서 칼럼의 위치가 상당히 중요하며, 아주 신중히 결정해야 한다.

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

인덱스 정렬

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

하지만 MySQL 8.0 버전부터는 칼럼 단위로 정렬 순서를 혼합해서 인덱스를 생성할 수 있게 됐다.

인덱스 스캔 방향

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

오름차순 또는 내림차순 정렬 효과를 얻을 수 있다.

오름차순으로 생성된 인덱스를 정순으로 읽으면 출력되는 결과 레코드는 자동으로 오름차순으로 정렬된 결과가 되고,

역순으로 읽으면 그 결과는 내림차순으로 정렬된 상태가 되는 것이다.

# first_name 칼럼에 대한 인덱스가 포함된 employees 테이블

SELECT * FROM employees WHERE first_name >= 'Anneke'
ORDER BY first_name ASC LIMIT 4;

SELECT * FROM employees 
ORDER BY first_name DESC LIMIT 5;

위의 첫 번째 쿼리는 first_name 칼럼에 정의된 인덱스를 이용해 'Anneke'라는 레코드를 찾은 후,

정순으로 해당 인덱스를 읽으면서 4개의 레코드만 가져오면 아무런 비용을 들이지 않고도 원하는 정렬 효과를 얻을 수 있다.

 

두 번째 쿼리는 이와 반대로 employees 테이블의 first_name 칼럼에 정의된 인덱스를 역순으로 읽으면서

처음 다섯 개의 코드만 가져오면 된다.

 

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

내림차순 인덱스

아래와 같이 2개 이상의 칼럼으로 구성된 복합 인덱스에서 각각의 칼럼이 내림차순과 오름차순이 혼합된 경우에는

MySQL 8.0의 내림차순 인덱스로만 해결될 수 있다.

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

first_name 칼럼을 역순으로 정렬하는 요건만 있다면 다음 2개 인덱스 중에서 어떤 것을 선택하는 것이 좋을까?

아니면 두 인덱스 모두 동일한 성능을 보일까?

 

결론만 말하면 InnoDB에서는 역순 스캔이 정순 스캔보다 느리다.

이유가 무엇일까?

 

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

일반적으로 OREDER By ... DESC 하는 쿼리가 소량의 레코드에 드물게 실행되는 경우라면 내림차순 인덱스를 굳이 고려할 필요는 없어 보인다.

이제 다음 쿼리를 살펴보자.

SELECT * FROM tab
WHERE userid=?
ORDER BY score DESC
LIMIT 10;

이 쿼리의 경우 다음 두 가지 인덱스 모두 적절한 선택이 될 수 있다.

 

• 오름차순 인덱스 : INDEX (userid ASC, score ASC)
• 내림차순 인덱스 : INDEX (userid DESC, score DESC)

하지만 위 쿼리가 많은 레코드를 조회하면서 빈번하게 실행된다면 오름차순 인덱스보다 내림차순 인덱스가 더 효율적이다.

 

또한 많은 쿼리가 인덱스의 앞쪽만 뒤쪽만 집중적으로 읽어서 인덱스의 특정 페이지 잠금이 병목이 될 것으로 예상된다면

쿼리에서 자주 사용되는 정렬 순서대로 인덱스를 생성하는 것이 병목 현상을 완화하는 데 도움이 될 것이다.

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

쿼리의 WHERE 조건이나 GROUP BY, 또는 ORDER BY 절이 어떤 경우에 인덱스를 사용할 수 있고 어떤 방식으로 사용할 수 있는지

식별할 수 있어야 한다. 그래야만 쿼리의 조건을 최적화하거나, 역으로 쿼리에 맞게 인덱스를 최적으로 생성할 수 있다.

어떤 조건에서 인덱스를 사용할 수 있고, 어떨 대 사용할 수 없는 지 살펴보자.

비교 조건의 종류와  효율성

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

아래 예제를 살펴보자.

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가 아닐 때까지 인덱스를 쭉 읽으면 된다. 상당히 효율적으로 인덱스를 이용한 것이다.
• 케이스 B는 우선 emp_no>=10144 AND dept_no='d002'인 레코드를 찾고, 그 이후 모든 레코드에 대해 dept_no가 'd002'인지 비교하는 과정을 거쳐야 한다.

케이스 A 인덱스에서 2 번째 칼럼인 emp_no는 비교 작업의 범위를 좁히는데 도움을 준다.

하지만 케이스 B 인덱스에서 2번째 칼럼인 dept_no는 비교 작업의 범위를 좁히는데 아무 도움도 주지 못한다.

단지 쿼리의 조건에 맞는지 검사하는 용도로만 사용됐다.

 

공식 명칭은 아니지만 케이스 A 인덱스에서의 두 조건과 같이 작업의 범위를 결정하는 조건을 '작업 범위 결정 조건'이라 한다.

케이스 B인덱스의 조건과 같이 비교 작업의 범위를 줄이지 못하고 단순히 거름종이 역할만 하는 조건을 필터링 조건 또는 체크 조건이라 한다.

작업 범위를 결정하는 조건은 많으면 많을수록 쿼리의 처리 성능을 높이지만

체크 조건은 많다고 해서 쿼리의 처리 성능을 높이지는 못하고 오히려 쿼리 실행을 더 느리게 만들 때가 많다.

인덱스의 가용성

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

여기서 왼쪽이란 하나의 칼럼 내에서뿐만 아니라 다중 칼럼 인덱스의 칼럼에 대해서도 함께 적용한다.

 

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

인덱스의 키 값의 정렬만 표현하지만 사실은 인덱스 키 값의 이런 정렬 특성은 빠른 검색의 전제 조건이다

즉 하나의 칼럼으로 검색해도 값의 왼쪽 부분이 없으면 인덱스 레인지 스캔 방시의 검색이 불가능하다.

또한 다중 칼럼에 인덱스에서도 왼쪽 칼럼의 값을 모르면 인덱스 레인지 스캔을 활용할 수 없다.

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

이 쿼리는 인덱스 레인지 스캔 방식으로 인덱스를 이용할 수는 없다.

그 이유는 first_name 칼럼에 저장된 값의 왼쪽부터 한 글자씩 비교해 가면서 일치하는 레코드를 찾아야 하는데,

조건절에 주어진 상숫값(%mer)에는 왼쪽 부분이 고정되지 않기 때문이다.

따라서 정렬 우선순위가 낮은 뒷부분의 값만으로는 왼쪽 기준 정렬 기반의 인덱스인 B-Treed에서는 인덱스의 효과를 얻을 수 없다.

 

SELECT * FROM dept_emp WHERE emp_no>=10144;

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

케이스 B의 인덱스는 다중 칼럼으로 구성된 인덱스이므로 dept_no 칼럼에 대해 먼저 정렬한 후,

다시 emp_no 칼럼으로 정렬돼 있기 때문이다.

여기서는 간단히 WHERE 조건절에 대한 내용만 언급했지만

인덱스의 왼쪽 값 기준 규칙은 GROUP BY 절이나 ORDER BY 절에도 똑같이 적용된다.

가용성과 효율성 판단

기본적으로 B-Tree 인덱스의 특성상 다음 조건에서는 사용할 수 없다. 경우에 따라서는 체크 조건으로 인덱스를 사용할 수는 있다.

작업 범위 결정 조건으로는 사용이 불가능하다.

 

• NOT-EQUAL로 비교된 경우
• Like '%??' 뒷부분 일치 형태로 문자열 패턴이 비교된 경우
• 스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우
• NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우
• 데이터 타입이 서로 다른 비교
• 문자열 데이터 타입의 콜레이션이 다른 경우

참고로 MySQL에서는 널 값도 인덱스에 저장된다.

그래서 WHERE column is null 이런 작엄 범위 결정 조건으로 인덱스를 사용할 수 있다.

 

다중 칼럼으로 만들어진 인덱스에 대한 내용도 살펴보자.

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

 

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

 

이상으로 포스팅을 마칩니다. 감사합니다.

 

참고 자료

REAL MySQL 8.0 1권