B-Tree 인덱스(3)

B-Tree 인덱스(3)

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

인덱스 키값은 항상 오름차순으로만 정렬되지만 사실 그 인덱스를 거꾸로 끝에서부터 읽으면 내림차순으로 정렬된 인덱스로도 사용될 수 있다. 인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 실시간으로 만들어 내는 실행 계획에 따라 결정된다.

인덱스의 정렬

일반적인 상용 DBMS에서는 인덱스를 생성하는 시점에 인덱스를 구성하는 각 칼럼의 정렬을 오름차순으로 또는 내림차순을 설정할 수 있다. 안타깝게도 MySQL은 다음 예제와 같이 인덱스를 구성하는 칼럼 단위로 정렬 방식(ASC와 DESC)을 혼합해서 생성하는 기능을 아직까지 지원하지 않는다.

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

MySQL에서는 위와 같은 명령으로 인덱스를 생성하면 아무 문제 없이 인덱스 생성은 가능하지만, 실제로는 ASC나 DESC 키워드를 무시하고 모든 칼럼이 오름차순(정순)으로만 정렬된다. MySQL에서 ASC 또는 DESC 키워드는 앞으로 만들어질 버전에 대한 호환성을 위해 문법상으로만 제공하는 것이다. 인덱스의 모든 칼럼을 오름차순(ASC)으로만 또는 내림차순(DESC)으로만 생성하는 것은 (인덱스를 앞으로 읽을지 뒤로 읽을지에 따라 해결되기 때문에) 아무런 문제가 되지 않는다. 하지만 가끔 인덱스를 구성하는 칼럼 가운데 오름차순(ASC)과 내림차순(DESC)을 혼합해서 만들어야 할 때가 있다. MySQL에서는 칼럼의 값을 역으로 변환해서 구현하는 것이 유일한 방법이다. 한 예로 다음 테이블을 살펴보자.

CREATE TABLE ranking (
  team_name VARCHAR(20),
  user_name VARCHAR(20),
  user_score INT,
  ...
  INDEX ix_teamname_userscore(team_name, user_score)
);

ranking 테이블에서 team_name 칼럼은 오름차순(ASC)으로 정렬하고 user_score는 높은 점수 순서(내림차순)대로 정렬해서 사용자를 조회하려면 어떻게 할까?

SELECT team_name, user_name
FROM ranking
ORDER BY team_name ASC, user_score DESC;

위와 같이 쿼리를 사용하면 원하는 결과는 조회할 수 있다. 하지만 이 쿼리는 실행의 최종 단계에서 레코드를 정렬하는 것이 필요하므로 절대로 빠르게 처리할 수 없다. 그래서 이럴 때는 user_score의 값을 역으로 변환해서 저장하는 것이 현재로서는 유일한 방법이다. 즉 user_score 값을 그대로 음수로 만들어서 저장하는 것이다. 그러면 다음과 같이 ORDER BY의 정렬 조건을 모두 오름차순(ASC)으로 사용할 수 있게 되므로 별도의 정렬 작업 없이 인덱스를 읽기만 해도 정렬되어 출력되는 것이다.

SELECT team_name, user_name
FROM ranking ORDER BY team_name, user_score;

참고로 ORDER BY의 칼럼에 별도로 ASC나 DESC가 명시되지 않으면 기본적으로 "ASC"가 생략된 것으로 판단하고 오름차순으로 정렬한다.

인덱스 스캔 방향

first_name 칼럼에 인덱스가 포함된 employees 테이블에 대해 다음 쿼리를 실행하는 과정을 한번 살펴보자. MySQL은 이 쿼리를 실행하기 위해 인덱스를 처음부터 오름차순으로 끝까지 읽어 first_name이 가장 큰(오름차순으로 읽었을 때 가장 마지막 레코드) 값 하나를 가져오는 걸까?

SELECT *
FROM employees ORDER BY first_name DESC LIMIT 1;

그렇지 않다. 인덱스는 항상 오름차순으로만 정렬돼 있지만 인덱스를 최소값부터 읽으면 오름차순으로 값을 가져올 수 있고, 최댓값부터 거꾸로 읽으면 내림차순으로 값을 가져올 수 있다는 것을 MySQL 옵티마이저는 이미 알고 있다. 그래서 위의 쿼리는 인덱스를 역순으로 접근해 첫 번째 레코드만 읽으면 된다. 아래 그림은 인덱스를 정순으로 읽는 경우와 역순으로 읽는 경우를 보여준다.

즉, 인덱스를 역순으로 정렬되게 할 수는 없지만 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬 효과를 얻을 수 있다. 인덱스를 오름차순으로 읽으면 최종적으로 출력되는 결과 레코드는 자동으로 오름차순으로 정렬된 결과이며, 내림차순으로 읽으면 그 결과는 내림차순으로 정렬된 상태가 되는 것이다.

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 칼럼에 정의된 인덱스를 역순으로 읽으면서 처음 다섯 개의 레코드만 가져오게 되는 것이다. 쿼리의 ORDER BY 처리나 MIN() 또는 MAX() 함수 등의 최적화가 필요한 경우, MySQL 옵티마이저는 인덱스의 읽기 방향을 전환해서 사용하도록 실행 계획을 만들어 낸다.

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

쿼리의 WHERE 조건이나 GROUP BY 또는 ORDER BY 절이 어떤 경우에 인덱스를 사용할 수 있고 어떤 방식으로 사용할 수 있는지 식별할 수 있어야 한다. 그래야만 쿼리의 조건을 최적화하거나, 역으로 쿼리에 맞게 인덱스를 최적으로 생성할 수 있다. 여기서는 어떤 조건에서 인덱스를 사용할 수 있고 어떨 때 사용할 수 없는지 살펴보겟다. 또한 인덱스를 100% 활용할 수 있는지, 일부만 이용하게 되는지도 함께 살펴보겠다.

비교 조건의 종류와 효율성

다중 칼럼 인덱스에서 각 칼럼의 순서와 그 칼럼에 사용된 조건이 동등 비교("=")인지 아니면 크다(">") 또는 작다("<")와 같은 범위 조건인지에 따라 각 인덱스 칼럼의 활용 형태가 달라지며, 그 효율 또한 달라진다. 다음 예제를 한번 살펴보자.

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

이 쿼리를 위해 dept_emp 테이블에 각각 칼럼의 순서만 다른 2가지 케이스로 인덱스를 생성햇다고 가정하자. 위의 쿼리가 처리되는 동안 각 인덱스에 어떤 차이가 있었는지 살펴보자.

• 케이스 A : dept_no + emp_no
• 케이스 B : emp_no + dept_no

케이스 A는 "dept_no='d002' AND emp_no>=10144"인 레코드를 찾고, 그 이후에는 dept_no가 'd002'가 아닐 때까지 인덱스를 그냥 쭉 읽기만 하면 된다. 이 경우에는 읽은 레코드가 모두 사용자가 원하는 결과임을 알 수 있다. 즉, 5건의 레코드를 찾는 데 꼭 필요한 5번의 비교 작업만 수행한 것이므로 상당히 효율적으로 인덱스를 이용한 것이다. 하지만 케이스 B는 우선 "emp_no>=10144 AND dept_no='d002'"인 레코드를 찾고, 그 이후 모든 레코드에 대해 dept_no='d002'인지 비교하는 과정을 거쳐야 한다. 이처럼 인덱스를 통해 읽은 레코드가 나머지 조건에 맞는지 비교하면서 취사선택하는 작업을 "필터링"이라고도 한다. 최종적으로는 dept_no='d002' 조건을 만족(필터링)하는 레코드 5건을 가져온다. 즉, 이 경우에는 5건의 레코드를 찾기 위해 7번의 비교 과정을 거친 것이다. 왜 이런 현상이 발생했을까? 그 이유는 다중 칼럼 인덱스의 정렬 방식(인덱스의 N번째 키값은 N-1번째 키값에 대해서 다시 정렬됨) 때문이다. 케이스 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 칼럼은 "필터링 조건"으로 사용된 것이다. 작업 범위를 결정하는 조건은 많으면 많을수록 쿼리의 성능을 높이지만 체크 조건은 많다고 해서 (최종적으로 가져오는 레코드는 작게 만들지 몰라도) 쿼리의 성능을 높이지는 못한다. 오히려 쿼리 실행을 더 느리게 만들 때가 많다.

인덱스의 가용성

B-Tree 인덱스의 특징은 왼쪽 값에 기준(Left-most)해서 오른쪽 값이 정렬돼 있다는 것이다. 여기서 왼쪽이라 함은 하나의 칼럼 내에서뿐만 아니라 다중 칼럼 인덱스의 칼럼에 대해서도 함께 적용된다.

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

아래 그림에서는 정렬만 표현했지만, 사실은 이 정렬이 빠른 검색의 전제 조건이다. 즉, 하나의 칼럼으로 검색해도 값의 왼쪽 부분이 없으면 인덱스 레인지 스캔 방식의 검색이 불가능하다. 또한 다중 칼럼 인덱스에서도 왼쪽 칼럼의 값을 모르면 인덱스 레인지 스캔을 사용할 수 없다.

케이스 A의 인덱스가 지정된 employees 테이블에 대해 다음과 같은 쿼리가 어떻게 실행되는지 한번 살펴보자.

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

이 쿼리는 인덱스 레인지 스캔 방식으로 인덱스를 이용할 수는 없다. 그 이유는 first_name 칼럼에 저장된 값의 왼쪽부터 한 글자씩 비교해 가면서 일치하는 레코드를 찾아야 하는데, 조건절에 주어진 상수값("%mer")에는 왼쪽 부분이 고정되지 않았기 때문이다. 따라서 정렬 우선순위가 낮은 뒷부분의 값만으로는 왼쪽 기준(Left-most) 정렬 기반의 인덱스인 B-tree에서는 인덱스의 효과를 얻을 수 없다.

케이스 B의 인덱스가 지정된 dept_emp 테이블에 대해 다음 쿼리가 어떻게 실행되는지 한번 살펴보자.

SELECT * FROM dept_emp WHERE emp_no>=10144;

인덱스가 (dept_no, emp_no) 칼럼 순서대로 생성돼 있다면 인덱스의 선행 칼럼인 dept_no 값 없이 emp_no 값으로만 검색하면 인덱스를 효율적으로 사용할 수 없다. 케이스 B의 인덱스는 다중 칼럼으로 인덱스가 만들어졌기 때문에 dept_no에 대해 먼저 정렬한 후, 다시 emp_no 칼럼값으로 정렬돼 있기 때문이다. 여기서는 간단히 WHERE 조건절에 대한 내용만 언급했지만 인덱스의 왼쪽 값 기준 규칙은 GROUP BY 절이나 ORDER BY 절에도 똑같이 적용된다.

가용성과 효율성 판단

기본적으로 B-Tree 인덱스의 특성상 다음 조건에서는 사용할 수 없다. 여기서 사용할 수 없다는 것은 작업 범위 결정 조건으로 사용할 수 없다는 것을 의미하며, 경우에 따라서는 체크 조건으로 인덱스를 사용할 수는 있다.

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

2.LIKE '%??'(앞부분이 아닌 뒷부분 일치) 형태로 문자열 패턴이 비교된 경우

• WHERE column LIKE '%승환'
• WHERE column LIKE '_승환'
• WHERE column LIKE '%승%'

3.스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우

• WHERE SUBSTRING(column, 1, 1)='X'
• WHERE DAYOFMONTH(column)=1

4.NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우

• WHERE column=deterministic_function()

5.데이터 타입이 서로 다른 비교(인덱스 칼럼의 타입을 변환해야 비교가 가능한 경우)

• WHERE char_column = 10

6.문자열 데이터 타입의 콜레이션이 다른 경우

• WHERE utf8_bin_char_column=euckr_bin_char_column

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

..WHERE column IS NULL..

다중 칼럼으로 만들어진 인덱스는 어떤 조건에서 사용될 수 있고, 어떤 경우에는 절대 사용될 수 없는지 살펴보자. 다음과 같은 인덱스가 있다고 가정해보자.

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

작업 범위 결정 조건으로 인덱스를 사용하지 못하는 경우

column_1 칼럼에 대한 조건이 없는 경우
column_1 칼럼의 비교 조건이 위의 인덱스 사용 불가 조건 중 하나인 경우

작업 범위 결정 조건으로 인덱스를 사용하는 경우(i는 2보다 크고 n보다 작은 임의의 값을 의미)

column_1 ~ column_(i-1) 칼럼까지 Equal 형태("=" 또는 "IN")로 비교
column_i 칼럼에 대해 다음 연산자 중 하나로 비교

• Equal("=" 또는 "IN")
• 크다 작다 형태(">" 또는 "<")
• LIKE로 좌측 일치 패턴(LIKE '승환%')

위의 2가지 조건을 모두 만족하는 쿼리는 column_1부터 column_i까지는 범위 결정 조건으로 사용되고, column_i부터 column_n까지의 조건은 체크 조건으로 사용된다. 인덱스를 사용하는 경우와 그렇지 않은 상황에 해당하는 쿼리의 조건 몇 가지를 예제로 살펴보자.

-- // 다음 쿼리는 인덱스를 사용할 수 없음
.. WHERE column_1 <> 2

-- // 다음 쿼리는 column_1과 column_2까지 범위 결정 조건으로 사용됨
.. WHERE column_1=1 AND column_2 > 10

-- // 다음 쿼리는 column_1, column_2, column_3까지 범위 결정 조건으로 사용됨
.. WHERE column_1 IN (1,2) AND column_2=2 AND column_3 <= 10

-- // 다음 쿼리는 column_1, column_2, column_3까지 범위 결정 조건으로,
-- // column_4는 체크 조건으로 사용됨
.. WHERE column_1 AND column_2 AND column_3 IN (10,20,30) AND column_4 <> 100

-- // 다음 쿼리는 column_1, column_2, column_3, column_4까지 범위 결정 조건으로 사용됨
-- // 좌측 패턴 일치 LIKE 비교는 크다 또는 작다 비교와 동급으로 생각하면 될 듯하다.
.. WHERE column_1 AND column_2 IN (2,4) AND column_3=30 AND column_4 LIKE '김승%'

-- // 다음 쿼리는 column_1, column_2, column_3, column_4, column_5 칼럼까지
-- // 모두 범위 결정 조건으로 사용됨
.. WHERE column_1=1 AND column_2=2 AND column_3=30 AND column_4='김승환' AND column_5='서울'

참고

• Real MySQL