5. B-Tree 인덱스의 정렬과 스캔 방향

인덱스는 정렬되어 있다. 이제까지 보인 예시들에선 오름차순 정렬만이 존재했지만, 우리가 생성할 때 조건을 설정함에 따라 오름차순으로도, 내림차순으로도 생성할 수 있따.

거기에, 읽는 것도 조절할 수 있다. 오름차순 테이블이여도 데이터를 내림차순으로 가져와야 한다면 내림차순으로도 읽을 수 있다! 모든 것은 옵티마이저가 결정한다.

정렬 설정법

대부분의 상용 DBMS는 인덱스 생성시 정렬을 결정할 수 있게 해준다. MySQL은 8.0 버전 부터 컬럼 단위로 설정할 수 있게 해주었다.

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

위 쿼리는 team_name은 오름차순, user_score는 내림차순 정렬이 되어 있는 인덱스를 생성할 수 있게 해준다.

5.1 스캔 방향

인덱스가 스캔되는 방향에 대해 이야기해보자.

SELECT *
FROM employees
ORDER BY first_name DESC
LIMIT 3;

위 쿼리를 수행할 때, 인덱스에서 first_name이 오름차순으로 정렬 되어 있다면, 옵티마이저는 순진하게 인덱스 전체를 읽고 가장 큰 3개의 값을 반환할까?
당연히 아니다, 옵티마이저는 인덱스를 역순으로 읽어 내림차순으로 레코드를 가져온다!

그리고 내림차순 정렬된 상태로 가져온다.
그렇다고 첫 칼럼은 역순으로 읽고, 두 번째 칼럼은 정순, 세 번째 칼럼은 다시 역순.. 이런 식으로 읽을 수는 없으니, 인덱스를 설계할 때 잘 고려해보아야 한다.

5.2 그렇다면 내림차순 인덱스는 왜 필요한걸까?

애초에 역순 읽기가 있다면, 왜 내림차순 인덱스가 필요한걸까? 그냥 오름차순 인덱스만 존재하고 거꾸로 읽어내면 그게 내림차순 인덱스인것 아닐까?

다음과 같은 두 가지 이유 때문에 거꾸로 읽는 것은 조금 느리게 진행된다.

  1. 페이지 잠금은 인덱스를 정순으로 읽는 것에 적합한 구조를 가지고 있다. (Forward Index Scan)
  2. 레코드들은 단방향 링크를 가졌다.

데이터가 많을 때, (약 천건) 28.9%정도의 속도 차이가 있다. 단순히 노드들을 역순으로 탐색하는 것 뿐만이라면 속도가 비슷해야겠지만 위의 두 이유로 인해 역순 스캔은 느리게 동작한다.

6. 인덱스의 효율성과 작업 범위 결정

효율적인 인덱스를 만들고, 쿼리를 "제대로" 최적화 하기 위해선, 쿼리의 WHERE과 GROUP BY, ORDER BY 절들이 "언제", "어떻게" 인덱스를 사용하는지 알아야만 한다.

6.1 비교 조건의 종류와 효율

비교 조건에 따라 인덱스 칼럼의 활용 형태와 효율이 달라질 수 있다. 비교 조건이란 예를 들어 = 동등 비교나, >, < 등의 범위 비교 조건 등을 의미한다.

예를 들어 컬럼의 순서만 다른 두 인덱스를 보자. 부서 번호를 dept_no로, 직원 번호를 emp_no라고 표현했다.

  1. 인덱스 1 : INDEX (dept_no, emp_no)
  2. 인덱스 2 : INDEX (emp_no, dept_no)

그리고 아래와 같은 쿼리를 보자.

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

어떤 부서 안에 10114 보다 id가 높은 회원들을 찾는 쿼리이다!
인덱스 1은 순조롭게 dept_no가 d002인 값을 찾고, emp_no가 10114 이상인 첫 값을 찾은 다음 d002의 끝까지 쭉~읽어낼 것이다.
반면 인덱스 2는 emp_no로 우선 찾을 수 밖에 없기 때문에, emp_no가 10114 이상인 그 모든 값에 대해서 dept_no를 하나 하나 비교해볼 수 밖에 없다 ㅠㅠ

image

인덱스를 통해 읽은 레코드가 나머지 조건에 맞는지 비교하며 취사선택하는 작업을 "필터링"이라고 부른다. 위 그림의 오른쪽 인덱스가 인덱스 2인데, 여기서는 어쩔 수 없이 7개의 레코드를 가져온 다음에 맨 아래 d001 두개를 필터링 하여 버렸다.
결국 두 번째 인덱스에서 WHERE절 앞에 나온 dept_no = 'd002' 조건은 전혀 작업 범위를 줄이지 못했다.
앞서 다중 컬럼 인덱스에서 언급한 것과 같이, 작업의 범위를 좁히기 위해선 인덱스 순서를 신중하게 결정해야 한다.

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

6.2.1 B-Tree 인덱스를 사용할 수 없는 곳

B-Tree 인덱스의 특성상 아래 조건들은 인덱스의 범위를 결정하는데 사용될 수 없다.

  1. NOT-EQUAL 비교
    • <>
    • NOT IN
    • NOT BETWEEN
    • IS NOT NULL
  2. LIKE 절을 사용할 때, 뒷 부분 일치 패턴을 사용하는 경우!
    • 예를 들어 이름 칼럼에 인덱싱 걸려 있다고 생각해보자. 만약 이름이 3글자라고 가정하면, 첫 번째 글자 부터 ㄱ, ㄴ, ㄷ..순으로 비교해 나갈 것이다.
      앞에서 부터 비교하기 때문에, 앞 부분에 패턴이 걸려있다면, ex) LIKE '이%' 범위 검색이 아주 아주 쉽다.
      "이"씨 이전임 김씨 곽씨 등은 싹 넘어가고, "이"씨만 체크하면 되기 때문이다. 하지만 뒷 부분에 걸려있는 경우.. -> LIKE '%진호'와 같이 검색하는 경우, 이름의 뒷부분만을 비교해야 하기 때문에, 제대로 된 검색을 할 수 없게 되는 것이다.
  3. 데이터 타입이 서로 다른데 비교하는 경우
    -> 인덱스 칼럼의 타입을 변환해야 비교가 가능한 경우 인덱스 사용이 불가능하다. ex) char column인데 숫자를 사용하는 경우.. 보통의 프로그래밍 언어라면 아스키 코드로 치환해주겠지만, DB에서 인덱싱은 사용할 수 없다.
  4. 스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교되는 경우
    • 예를 들어 column에 인덱스가 걸려 있을 떄 DAYOFMONTH(column) 과 같은 연산을 통하면 당연히 사용할 수 없다.
  5. 문자열 데이터 타입의 콜레이션이 다른 경우.
    -> 같은 utf8이어도 utf8_bin, utf8_general_ci 등은 내부적으로 정렬 방법이 내부적으로 다르다.
    image
  6. NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용되는 경우

6.2.2 MySQL은 인덱스에 NULL을 쓸 수 있다!

B-Tree 인덱스를 사용 가능한 곳

  1. NULL : NULL 값이 인덱스에 저장되지 않는 상용 DBMS가 많지만, MySQL에서는 NULL 값도 인덱스에 저장된다! 아래 쿼리의 WHERE 조건도 작업 범위를 결정할 때 인덱스를 사용! 
...
WHERE name IS NULL;

image

Postgresql에서는 특이하게도 Unique 인덱스에도 Null값을 여러개 넣을 수 있다; -> 공식 문서 (opens in a new tab)

6.2.3 다중 칼럼으로 만들어진 인덱스가 작업 범위를 결정하지 못하는 경우

예를 들어 아래와 같은 인덱스가 있다.
INDEX ix_test (col_1, col_2, col_3 ... )

  1. col_1에 대한 조건이 없는 경우 작업 범위를 결정할 수 없음
  2. col_1 칼럼의 비교 조건이 6.2.1에서 언급한 인덱스 사용 불가 조건들 중 하나인 경우!

6.2.4 다중 칼럼으로 만들어진 인덱스가 작업 범위를 결정할 수 있는 경우!

  1. col_1 ~ col_(i - 1) 칼럼까지 동등 비교 하는 경우 (=, IN)
    -> 말을 복잡하게 해두었는데, 인덱싱이 걸린 앞 부분 부터 특정 칼럼까지 동등 비교가 되어 있는 쿼리를 뜻한다!
  2. 1번 조건 && col_i를 아래의 연산자중 하나로 비교하는 경우
    • 동등 비교 : =, IN
    • 대소 비교 : >, <
    • LIKE 왼쪽 비교 패턴 : LIKE '진호%'