Index

책의 마지막에 있는 "찾아보기"가 인덱스에 비유된다면 책의 내용은 데이터 파일에 저장된 레코드 주소에 비유된다. DBMS도 데이터베이스 테이블의 모든 데이터를 검색해서 결과를 가져오려면 시간이 오래 걸린다. 그래서 칼럼의 값과 해당 레코드가 저장된 주소를 key-value 쌍으로 삼아 인덱스를 만들어준다. 책의 찾아보기도 ㄱ, ㄴ, ㄷ, ... 순으로 정렬되어 있는데 DBMS의 인덱스도 칼럼의 값을 주어진 순서로 미리 정렬해서 보관한다.

분류

• 역할별
  • Primary Key
    • 레코드를 대표하는 칼럼의 값으로 만들어진 인덱스. 테이블에서 레코드를 식별하는 기준값이 되기 때문에 식별자라고도 부른다. PK는 NULL 값, 중복을 허용하지 않는다.
  • Secondary Index
    • UNIQUE INDEX는 PK와 성격이 비슷하고 PK를 대체할 수 있다 해서 대체키라고도 하는데 별도로 분류하기도 하고 그냥 세컨더리 인덱스로 분류하기도 한다.
• 데이터 저장 알고리즘별
  • B-Tree Index
    • B-Tree 알고리즘은 가장 일반적으로 사용되는 인덱스 알고리즘.
  • Hash Index
    • 칼럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원
    • 값을 변형해서 인덱싱하므로 Prefix 일치와 같이 값의 일부만 검색하거나 범위를 검색할 때는 해시 인덱스를 사용할 수 없다.
    • 주로 메모리 기반의 데이터베이스에서 많이 사용한다.
• 데이터의 중복 허용 여부
  • UNIQUE 인덱스
  • NON-UNIQUE 인덱스
  • 실제 DBMS 쿼리를 실행해야 하는 옵티마이저에게는 상당히 중요한 문제다. 유니크 인덱스에 대해 동등 조건(Equal, =)으로 검색하는 것은 항상 1건의 레코드만 찾으면 더 찾지 않아도 된다는 것을 옵티마이저에게 알려주는 효과를 낸다.

B-Tree 인덱스

B-Tree는 칼럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태로 유지한다.

구조 및 특성

인덱스의 리프 노드는 항상 실제 데이터 레코드의 주소값을 가진다.

데이터 파일의 레코드는 INSERT된 순서로 저장되어 있지 않다. 레코드가 삭제되어 빈 공간이 생기면 가능한 한 삭제된 공간을 재활용하도록 DBMS가 설계되기 때문에 항상 INSERT된 순서로 저장되지는 않는다.

인덱스는 테이블의 키 칼럼만 가지고 있으므로 나머지 칼럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 한다. 이를 위해 인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가진다.

인덱스 키 추가 및 삭제

[인덱스 키 추가]

새로운 키 값을 B-Tree에 저장할 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다. 리프 노드가 꽉 차서 저장할 수 없을 때는 리프 노드가 Split(분리)되어야 하는데, 이는 상위 브랜치 노드까지 처리 범위가 넓어진다. 따라서 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 든다.

WARNING

대부분의 RDBMS의 데이터 파일에서 레코드는 특정 기준으로 정렬되지 않고 임의 순서로 저장된다. 하지만 InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되므로 기본적으로 PK 순서로 정렬되어 저장된다. 이는 오라클의 IOT(Index Organized Table)나 MS-SQL의 클러스터 테이블과 같은 구조를 말한다. InnoDB에서는 사용자가 별도의 명령이나 옵션을 선택하지 않아도 디폴트로 클러스터링 테이블이 생성된다.

[인덱스 키 삭제]

해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료된다. 삭제 마킹된 공간은 재활용할 수 있다. 인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 디스크 I/O가 필요한 작업이다. MySQL 5.5 이상 버전의 InnoDB 스토리지 엔진에서는 버퍼링되어 지연 처리될 수 있다. (서버가 내부적으로 처리하므로 특별히 걱정할 것은 없다.)

[인덱스 키 변경]

인덱스의 키 값은 그 값에 따라 저장될 리프 노드의 위치가 결정되므로 단순히 인덱스 상의 키 값만 변경하는 것은 불가하다. 먼저 키 값을 삭제한 후 다시 새로운 키 값을 추가하는 방식으로 처리된다. InnoDB 스토리지 엔진을 사용하는 테이블에 대해서는 이 작업 모두 체인지 버퍼를 이용해 지연 처리될 수 있다.

[인덱스 키 검색]

인덱스를 검색하는 작업은 B-Tree 루트 노드부터 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행하는데 이 과정을 '트리 탐색'이라 한다. 이 작업은 SELECT 뿐만 아니라 UPDATE, DELETE를 처리하기 위해 항상 레코드를 먼저 검색해야 할 때도 수행된다.

B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있다. 부등호 비교 조건에서도 인덱스를 활용할 수 있지만 인덱스를 구성하는 키 값의 뒷부분만 검색하는 용도로는 인덱스를 사용할 수 없다. 또한 인덱스 키 값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree의 빠른 검색 기능을 사용할 수 없다. 이미 변형된 값은 B-Tree 인덱스에 존재하는 값이 아니다. 따라서 함수나 연산을 수행한 결과로 정렬, 검색하는 작업은 B-Tree의 장점을 이용할 수 없으므로 주의해야 한다.

인덱스 사용에 영향을 미치는 요소

[인덱스 키 값의 크기]

페이지(Page) 또는 블록(Block)
InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(Page) 또는 블록(Block)이라 하며, 디스크의 모든 읽기/쓰기 작업의 최소 단위가 된다. 또한 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이다.

DBMS의 B-Tree는 자식 노드의 개수가 가변적인 구조다. 자식 노드의 개수는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다. MySQL 5.7 버전부터 InnoDB 스토리지 엔진의 페이지 크기를 innodb_page_size 시스템 변수를 이용해 4KB ~ 64KB 사이 값을 선택할 수 있지만 기본값은 16KB다.

그림 8.7의 경우 하나의 인덱스 페이지(16KB)에 저장할 수 있는 키의 개수는 16 * 1024 / (16 + 12) = 585개 저장할 수 있다. -> 자식 노드를 585개 가질 수 있다.

인덱스 키 값이 커지면 (키 값의 크기가 두 배인 32Byte 로) 16 * 1024 / (32 + 12) = 372개 저장할 수 있다.

SELECT 쿼리가 레코드 500개를 읽어야 한다면 전자는 인덱스 페이지 한 번으로 해결될 수 있지만, 후자는 적어도 최소한 2번 이상 디스크로부터 읽어야 한다. 결국 인덱스를 구성하는 키 값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고 그만큼 느려짐을 의미한다.

또한 인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스 크기가 커진다는 것을 의미한다. 하지만 인덱스를 캐시해 두는 InnoDB의 버퍼 풀이나 MyISAM의 키 캐시 영역은 크기가 제한적이기 때문에 메모리에 캐시해둘 수 있는 레코드의 수는 줄어든다. 자연히 메모리 효율이 떨어지는 결과를 가져온다.

[B-Tree 깊이]

깊이는 상당히 중요하지만 직접 제어할 수 없다. 인덱스 키 값의 평균 크기가 늘어나면

인덱스 B-Tree 깊이가 3, 키 값이 16바이트인 경우에는 최대 2억 (585 * 585 * 585)개 정도 키 값을 담을 수 있지만, 키 값이 32바이트로 늘어나면 5천만(372 * 372 * 372) 개로 줄어든다.

B-Tree의 깊이는 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결된다. 결론적으로 인덱스 키 값의 크기가 커지면 커질수록 한 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어지고, 같은 레코드 건수라 하더라도 B-Tree 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 됨을 의미한다.

인덱스 키 값의 크기는 가능하면 작게 만드는 것이 좋다.

[선택도]

인덱스에서 선택도(Selectivity)와 기수성(Cardinality)는 거의 같은 의미로 사용되며, 모든 키 값 가운데 유니크한 값의 수를 의미한다. 전체 인덱스 키 값은 100개인데 그 중 유니크한 값의 수는 10개라면 기수성은 10이다. 인덱스 키 값 가운데 중복 값이 많아지면 많아질 수록 기수성은 낮아지고 선택도도 떨어진다. 인덱스는 선택도가 높을 수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

country, city 칼럼이 포함된 tb_city 테이블을 예로 들자. tb_city 테이블의 전체 레코드 건수는 1만 건이며 country 칼럼으로만 인덱스가 생성되어 있다. tb_city 테이블에는 국가와 도시가 중복해서 저장되어 있지 않다.

CREATE TABLE tb_city(
	country VARCHAR(10),
	city VARCHAR(10),
	INDEX ix_country(country)
);

다음 쿼리를 실행했을 때 내부적인 쿼리와 인덱스의 효율성을 살펴보자

SELECT * FROM tb_test WHERE country = 'KOREA' AND city = 'SEOUL';

• country 칼럼의 유니크한 값의 개수가 10개
  유니크 값이 10개이므로 10개의 country의 city 정보가 저장되어 있다. 전체 레코드 건수를 유니크한 값의 개수로 나누면 하나의 키 값으로 검색했을 때 대략 몇 건의 레코드가 일치할 지 예측할 수 있다.
  country = 'KOREA' 조건으로 인덱스를 검색하면 1,000건 (10,000 / 10)이 일치한다 예상할 수 있다. 1,000건 가운데 city = 'SEOUL'인 레코드는 1건이므로 999건은 불필요하게 읽은 것이다.

• country 칼럼의 유니크한 값의 개수가 1,000개
  유니크 값이 1,000개이므로 1,000개 country의 city 정보가 저장되어 있다. 전체 레코드 건수를 유니크 값의 개수로 나누면 대략 한 국가당 10개의 도시 정보가 저장되어 있을 것이라 예측할 수 있다.
  country = 'KOREA' 조건으로 인덱스를 검색하면 10건 (10,000 / 1,000)이 일치할 것이며 그 10건 중에서 city = 'SEOUL'인 레코드는 1건이므로 9건만 불필요하게 읽은 것이다.

이처럼 인덱스에서 유니크한 값의 개수는 인덱스나 쿼리의 효율성에 큰 영향을 미친다.

[읽어야 하는 레코드 건수]
인덱스를 통해 테이블의 레코드를 읽는 것은 바로 테이블 레코드를 읽는 것보다 높은 비용이 드는 작업이다. 테이블에 레코드가 100만 건 있는데 그 중 50만 건을 읽어야 하는 쿼리가 있다고 하자. 전체 테이블을 모두 읽어서 필요 없는 50만 건을 버리는 것이 효율적일지, 인덱스를 통해 필요한 50만 건만 읽어 오는 것이 효율적일지 판단해야 한다.

인덱스를 통해 읽어야 할 레코드 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 가려내는 방식으로 처리하는 것이 효율적이다. (일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드를 1건 읽는 것이 직접 레코드 1건을 읽는 것보다 4~5배 정도 비용이 더 많이 드는 작업으로 예측한다.)

전체 100만 건 레코드 가운데 50만 건을 읽어야 하는 작업은 인덱스 손익 분기점인 20~25%보다 훨씬 크기 때문에 MySQL 옵티마이저는 인덱스를 사용하지 않고 직접 테이블을 처음부터 끝까지 읽어서 처리할 것이다.

데이터 읽기

인덱스 레인지 스캔

SELECT * FROM EMPLOYEES WHERE first_name BETWEEN 'Ebbe' AND 'Gad'

검색해야 할 인덱스 범위가 결정됬을 때 사용한다. 검색 값의 수나 검색 결과 레코드 건수와 상관없이 레인지 스캔이라고 표현한다. 루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종 리프 노드까지 찾아들어가야 필요한 레코드의 시작 지점을 알 수 있다.

시작 위치를 찾으면 그 때부터 리프 노드의 레코드만 순서대로 읽으면 된다. 이처럼 차레대로 쭉 읽는 것을 '스캔'이라고 표현한다. 만약 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔한다. 그리고 최종적으로 스캔을 멈춰야 할 위치에 도달하면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다.

두꺼운 선은 스캔해야 할 위치 검색을 위한 비교 작업을 의미하며 두꺼운 화살표가 지나가는 리프 노드의 레코드 구간은 실제 스캔 범위를 표현한다.

그림 8.8은 실제 인덱스만을 읽는 경우를 보여준다. 하지만 B-Tree 인덱스의 리프 노드를 스캔하면서 실제 데이터 파일의 레코드를 읽어와야 하는 경우는 어떨까

어떤 방식으로 스캔하든 상관없이, 해당 인덱스를 구성하는 칼럼의 정순 또는 역순으로 정렬된 상태로 레코드를 가져온다. 별도의 정렬 과정이 수반되지 않고 인덱스 자체의 정렬 특성 때문에 자동으로 그렇게 된다.

또 한 가지 중요한 것은 인덱스의 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다. 이 때 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 레코드 한 건 한 건 단위로 랜덤 I/O가 한 번씩 일어난다. 그래서 인덱스를 통해 레코드를 읽는 작업은 비용이 많이 드는 작업으로 분류된다. 그리고 인덱스를 통해 읽어야 할 데이터 레코드가 20~25%를 넘으면 인덱스를 통한 읽기보다 테이블 데이터를 직접 읽는 것이 더 효율적인 처리 방식이 된다.

[인덱스 레인지 스캔의 3단계]

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

쿼리가 필요로 하는 데이터에 따라 3번 과정은 필요 없을 수도 있다. 이를 '커버링 인덱스' 라고 한다. 커버링 인덱스로 처리되는 쿼리는 디스크 레코드를 읽지 않아도 되기 때문에 랜덤 읽기가 상당히 줄어들고 성능은 그만큼 빨라진다. MySQL 서버에는 1번과 2번 단계의 작업이 얼마나 수행됬는지 확인할 수 있게 다음과 같은 상태 값을 제공한다.

• Handler_read_key : 1번 단계(Index Seek) 실행된 횟수
• Handler_read_next, Handler_read_prev : 2번 단계(Index Scan)로 읽은 레코드 건수
  • Handler_read_next는 인덱스 정순으로 읽은 레코드 건수
  • Handler_read_prev는 인덱스 역순으로 읽은 레코드 건수
  • Handler_read_first, Handler_read_last는 인덱스의 첫 번째 레코드와 마지막 레코드를 읽은 횟수를 의미하는데, MIN(), MAX()와 같이 제일 큰/작은 값만 읽는 경우 증가하는 상태 값이다.

이 상태 값들은 읽은 레코드 건수를 의미하는데 실제 인덱스만 읽었는지 인덱스를 통해 데이터 레코드를 읽었는지(3번 단계)는 구분하지 않는다.

인덱스 풀 스캔

인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 읽는 방식이다. 대표적으로 쿼리의 조건절이 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다. 예를 들어 인덱스는 (A, B, C) 순서로 만들어져 있지만 쿼리의 조건 절은 B 칼럼이나 C 칼럼으로 검색하는 경우다.

이 방식은 인덱스 레인지 스캔보다 빠르지 않지만 테이블 풀 스캔보다는 효율적이다. 인덱스에 포함된 칼럼만으로 쿼리를 처리할 수 있는 경우 테이블의 레코드를 읽을 필요가 없기 때문이다. 인덱스의 전체 크기는 테이블 자체 크기보다 훨씬 작으므로 인덱스 풀 스캔은 테이블 전체를 읽는 것보다 적은 디스크 I/O로 쿼리를 처리할 수 있다.

인덱스뿐만 아니라 데이터 레코드까지 모두 읽어야 한다면 이 방식으로 처리되지 않는다.

WARNING

인덱스 풀 스캔 방식 또한 인덱스를 사용하지만 효율적인 방식은 아니며, 일반적으로 인덱스를 생성하는 목적은 아니다. 역으로 테이블 전체를 읽거나 인덱스 풀 스캔 방식으로 인덱스를 사용하는 경우는 "인덱스를 (효율적으로) 사용하지 못한다." 라는 표현을 사용한다.

루즈 인덱스 스캔

말 그대로 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미한다. Oracle DBMS의 인덱스 스킵 스캔과 작동방식은 비슷하지만 MySQL에서는 이를 '루즈 인덱스 스캔'이라고 한다. 앞의 두 가지 접근 방법(인덱스 레인지 스캔 / 인덱스 풀 스캔)은 루즈 인덱스 스캔과 상반된 의미에서 타이트(Tight) 인덱스 스캔으로 분류한다.

루즈 인덱스 스캔은 중간에 필요치 않은 인덱스 키 값은 무시하고 다음으로 넘어간다. 일반적으로 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 두 개의 칼럼으로 인덱스가 생성되어 있다. 또한 이 인덱스는 (dept_no, emp_no) 조합으로 정렬까지 되어 있어서 그림 8.11과 같이 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-12-01';

-- 인덱스 사용 가능
SELECT * FROM employees WHERE gender = 'M' AND birth_date >= '1965-12-01';

MySQL 8.0 버전부터 옵티마이저가 gender 칼럼을 건너뛰어 birth_date 칼럼만으로 인덱스 검색이 가능하게 해 주는 인덱스 스킵 스캔 최적화 기능이 도입되었다. 물론 8.0 이전 버전에서도 비슷하게 최적화를 수행하는 루즈 인덱스 스캔 기능이 있었지만 이 기능은 GROUP BY 작업을 처리하기 위해 인덱스를 사용하는 경우에만 적용할 수 있었다. 8.0 버전에 도입된 인덱스 스킵 스캔은 WHERE 조건절의 검색을 위해 사용 가능하도록 용도가 훨씬 넓어졌다.

인덱스 스킵 스캔을 비활성화하고 8.0 이전 버전에서 어떤 실행 계획으로 처리됐는지 살펴보면

WHERE 절에 gender 조건 없이 birth_date 비교 조건만 가지기 때문에 인덱스를 효율적으로 이용할 수 없다. (꼭 필요한 부분만 접근하는 것을 의미)

• type 칼럼이 index라고 표시 → 인덱스를 처음부터 끝까지 읽었다. (풀 인덱스 스캔)
• employees 테이블의 모든 칼럼을 조회했다면 → 테이블 풀 스캔

인덱스 스킵을 활성화하면

• type 칼럼이 range으로 표시 → 인덱스에서 꼭 필요한 부분만 읽었다.
• Extra 칼럼에 'Using index for scan' 표시 → 인덱스 스킵 스캔을 활용해 데이터 조회했다.

옵티마이저는 우선 gender 칼럼에서 유니크한 값을 모두 조회해서 주어진 쿼리에 gender 칼럼의 조건을 추가해서 쿼리를 다시 실행하는 형태로 처리한다. 내부적으로 아래 2개 쿼리를 실행하는 것과 비슷한 형태의 최적화를 실행한다.

SELECT * FROM employees WHERE gender = 'M' AND birth_date >= '1965-12-01';
SELECT * FROM employees WHERE gender = 'F' AND birth_date >= '1965-12-01';

[단점]

• WHERE 절에 조건이 없는 인덱스의 선행 칼럼의 유니크한 값의 개수가 적어야 한다.
  • 만약 유니크한 값의 개수가 많다면 옵티마이저는 인덱스에서 스캔해야 할 시작점을 검색하는 작업이 많아져 쿼리의 처리 성능이 오히려 느려질 수 있다. 예를 들어 (emp_no, dept_no) 조합으로 만들어진 인덱스에서 스킵 스캔을 실행한다 가정하면 사원의 수만큼 레인지 스캔 시작점을 검색하는 작업이 필요해져 쿼리의 성능이 매우 떨어진다.
• 쿼리가 인덱스에 존재하는 칼럼만으로 처리 가능해야 함(커버링 인덱스)
  • 모든 칼럼을 조회하면 인덱스 칼럼 이외 나머지 칼럼도 필요하기 때문에 풀 테이블 스캔으로 실행 계획을 수립한다.

다중 칼럼 인덱스

실제 서비스용 데이터베이스에서는 2개 이상의 칼럼을 포함한 인덱스가 더 많이 사용된다. 두 개 이상의 칼럼으로 구성된 인덱스를 다중 칼럼 인덱스라고 하며 2개 이상의 칼럼이 연결됬다고 해서 Concatenated Index라고도 한다.

인덱스의 두 번째 칼럼은 첫 번째 칼럼에 의존해서 정렬돼 있다. 즉 두 번째 칼럼의 정렬은 첫 번째 칼럼이 똑같은 레코드에서만 의미가 있다. 그림 8.13에서는 칼럼이 2개 뿐이지만, 만약 칼럼이 4개인 인덱스를 생성한다면 세 번째 칼럼은 두 번째 칼럼에 의존해서 정렬되고, 네 번째 칼럼은 다시 세 번째 칼럼에 의존해서 정렬된다.

인덱스의 정렬 및 스캔 방향

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

[인덱스의 정렬]

DBMS는 인덱스를 생성하는 지점에 인덱스를 구성하는 각 칼럼의 정렬을 오름차순 또는 내림차순으로 정렬할 수 있다. MySQL 5.7 버전까지는 칼럼 단위로 정렬 순서를 혼합(ASC or DESC)해서 인덱스를 생성할 수 없었다. 이런 문제점을 해결하기 위해 숫자 칼럼의 경우 -1을 곱한 값을 저장하는 우회 방법을 사용했다. 하지만 MySQL 8.0 버전부터는 다음과 같은 형태의 정렬 순서를 혼합한 인덱스도 생성할 수 있게 되었다.

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

[스캔 방향]

SELECT * FROM employees
ORDER BY first_name DESC
LIMIT 1

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

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

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

[내림차순 인덱스]

• 오름차순 인덱스(Ascending Index) : 작은 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
• 내림차순 인덱스(Descending Index) : 큰 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
• 인덱스 정순 스캔(Forward Index Scan) : 인덱스 키의 크고 작음에 관계없이 인덱스 리프 노드의 왼쪽 페이지부터 오른쪽으로 스캔
• 인덱스 역순 스캔(Backward Index Scan) : 인덱스 키의 크고 작음에 관계없이 인덱스 리프 노드의 오른쪽 페이지부터 왼쪽으로 스캔

• 인덱스 역순 스캔이 정순 스캔에 비해 느릴 수 밖에 없는 이유
  • 페이지 잠금이 인덱스 정순 스캔에 적합한 구조
  • 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조

일반적으로 ORDER BY ... DESC 쿼리가 소량의 레코드에 드물게 실행된다면 내림차순 인덱스를 고려할 필요는 없다. 하지만 쿼리가 많은 레코드를 조회하면서 빈번하게 실행된다면 내림차순 인덱스가 더 효율적이라고 볼 수 있다.

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

가용성과 효율성

비교 조건의 종류와 효율성

다중 칼럼 인덱스에서 각 칼럼의 순서와 조건이 동등 비교 =인지 아니면 크다 > 또는 작다 < 같은 범위 조건인지에 따라 각 인덱스 칼럼의 활용 형태가 달라지며, 그 효율 또한 달라진다.

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

이 쿼리를 위해 dept_emp 테이블에 각 칼럼의 순서만 다른 두 가지 케이스로 인덱스를 생성했다고 가정하자. 위의 쿼리가 처리되는 동안 각 인덱스에 어떤 차이가 있을까?

• 케이스 A: INDEX (dept_no, emp_no)
  dept_no='d002' AND emp_no >= 10114 인 레코드를 찾고 그 이후에는 dept_no가 'd002' 아닐 때까지 인덱스를 쭉 읽기만 하면 된다. 조건을 만족하는 레코드가 5개라고 할 때 5건의 레코드를 찾는데 꼭 필요한 5번의 비교 작업만 수행한 것이므로 상당히 효율적으로 인덱스를 이용했다.

• 케이스 B: INDEX (emp_no, dept_no)
  emp_no >= 10114 AND dept_no='d002'인 레코드를 찾고 그 이후에는 dept_no가 'd002'인지 비교하는 과정을 거쳐야 한다.

  최종적으로 dept_no='d002' 조건을 만족하는 레코드 5건을 찾기 위해 7번의 비교 과정을 거쳤다. 그 이유는 다중 칼럼 인덱스의 정렬 방식 때문이다. (인덱스의 N번째 키 값은 N-1 번째 키 값에 대해서 다시 정렬됨) 케이스 A 인덱스에서 2번째 칼럼인 emp_no는 비교 작업의 범위를 좁히는 데 도움을 준다. 하지만 케이스 B 인덱스에서 2번째 칼럼인 dept_no는 비교 작업의 범위를 좁히는 데 도움을 주지 못하고 단지 쿼리 조건이 맞는지 검사하는 용도로만 사용했다.

공식적인 명칭은 아니지만 케이스 A 인덱스에서 두 조건(dept_no='d002' AND emp_no >= 10114)과 같이 작업의 범위를 결정하는 조건을 '작업 범위 결정 조건' 이라 하고, 케이스 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)

하나의 칼럼으로 검색해도 왼쪽 부분이 없으면 인덱스 레인지 스캔 방식의 검색이 불가하다. 또한 다중 칼럼 인덱스에서도 왼쪽 칼럼의 값을 모르면 인덱스 레인지 스캔을 사용할 수 없다.

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

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

SELECT * FROM employees WHERE emp_no >= 10144;

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

가용성과 효율성 판단

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

• NOT-EQUAL로 비교된 경우("<>", "NOT IN", "NOT BETWEEN", "IS NOT NULL")
• LIKE '%??' (앞부분이 아닌 뒷부분 일치) 형태로 문자열 패턴이 비교된 경우
  • `.. WHERE column LIKE '%ABC'
  • `.. WHERE column LIKE '_ABC'
  • `.. WHERE column LIKE '%A%'
• 스토어드 함수나 다른 연산자로 인덱스 컬럼이 변형된 후 비교된 경우
  • `.. WHERE SUBSTRING(column,1,1) = 'X'
  • .. WHERE DAYOFMONTH(column) = 1
• NON-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우
  • .. WHERE column = deterministic_function()
• 데이터 타입이 서로 다른 비교(인덱스 칼럼의 타입을 변환해야 비교 가능한 경우)
  • .. WHERE char_column = 10
• 문자열 데이터 타입의 콜레이션이 다른 경우
  • .. WHERE utf8_bin_char_column = euckr_bin_char_column

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

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

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

-- 다음 쿼리는 인덱스 사용 불가
.. WHERE column1 <> 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 = 1 AND column_2 = 2 AND column_3 IN (10,20,30) AND column_4 <> 100

-- 다음 쿼리는 column_1, column_2, column_3, column_4까지 범위 결정 조건
-- 좌측 패턴 일치 LIKE 비교는 크다 또는 작다 비교와 동급으로 생각하면 됨
.. WHERE column_1 = 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 = '서울'

References

• Real MySQL 8.0.1 / 백은빈.이성욱 저