인덱스 Index - (3)

1. 인덱스 키 값의 크기

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(Page) 또는 블록(Block)이라고 하며 디스크 I/O 최소 작업 단위가 된다. 또한 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 하다. 인덱스도 결국은 페이지 단위로 관리되며 루트, 브랜치, 리프 노드를 구분한 기준이 바로 페이지 단위다. 

일반적으로 DBMS의 B-Tree는 자식 노드의 개수가 가변적인 구조다. MySQL의 B-Tree는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다. MySQL 5.7 버전부터는 InnoDB 스토리지 엔진의 페이지 크기를 innodb_page_size 시스템 변수를 이용해 4KB ~ 64KB 사이의 값을 선택할 수 있으며 디폴트 값은 16KB이다. 앞으로 페이지 사이즈는 16KB 기준으로 설명하겠다. 

그림(1) 인덱스 페이지의 구성

인덱스의 키가 16 Byte라고 가정하면 그림(1)과 같이 인덱스 페이지가 구성될 것이다. 자식 노드 주소라는 것은 여러 복합적인 정보가 담긴 영역이며 페이지의 종류에 따라 6 Byte ~ 12 Byte 사이의 값을 가질 수 있다. 여기서는 편의상 12 Byte로 구성된다고 가정하자.
그림(1)의 경우 하나의 인덱스 페이지(16KB)에  585개의 키를 저장할 수 있다. 자식 노드를 585개를 가질 수 있는 B-Tree가 되는 것이다. 

(A) 케이스 585 = 16 * 1024 / (16 + 12) 16KB = 16 Byte * 1024 16 + 12 = 인덱스 키 16 Byte + 자식노드 주소 12 Byte

만약 같은 조건에서 인덱스 키 값이 32 Byte로 늘어났다고 가정하면 하나의 인덱스 페이지(16KB)에 372개의 키를 저장할 수 있다.

(B) 케이스 372 = 16 * 1024 / (32 + 12) 16KB = 16 Byte * 1024 32 + 12 = 인덱스 키 32 Byte + 자식노드 주소 12 Byte

SELECT 쿼리가 레코드 500개를 읽어야 한다면 (A)케이스는 인덱스 페이지 한 번으로 해결되지만 (B)케이스는 최소 2번 이상 디스크를 읽어야 한다. 결국 인덱스를 구성하는 키 값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고 그만큼 느려진다는 것을 의미한다.
인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미한다. 하지만 인덱스를 캐시해 두는 InnoDB의 버펄 풀은 크기가 제한적이기 때문에 하나의 레코드를 위한 인덱스 크기가 커지면 커질수록 메모리에 캐시해 둘 수 있는 레코드 수는 줄어든다. 그렇게 되면 자연히 메모리의 효율이 떨어지는 결과를 가져온다.

 

2. B-Tree 깊이

B-Tree 인덱스의 깊이(Depth)는 중요하지만 직접 제어할 방법은 없다. 인덱스의 B-Tree 깊이가 3이고 키 값이 16 Byte인 경우에는 최대 2억 (585 * 585 * 585)개 정도의 키 값을 담을 수 있다. 키 값이 32 Byte로 늘어나면 5천만(372 * 372 * 372) 개로 줄어든다. B-Tree의 깊이는 MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다. 결론적으로 인덱스 키 값의 크기가 커지면 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어지고 같은 레코드 수라 하더라도 B-Tree의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다는 것을 의미한다.
인덱스 키 값의 크기는 가능하면 작게 만드는 것이 좋다. 실제로는 아무리 대용량 데이터베이스라도 B-Tree 깊이가 5단계 이상까지 깊어지는 경우는 드물다.

 

3. 선택도(기수성)

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

country, city 컬럼을 포함하는 tb_test 테이블을 예로 들겠다. tb_test 테이브르이 전체 레코드 수는 1만이며 country 컬럼에만 인덱스가 생성된 상태에서 아래 두 케이스를 살펴보자.

• (A) 케이스: country 컬럼의 기수성 10
• (B) 케이스: country 컬럼의 기수성 1,000

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

MySQL은 인덱스의 통계 정보 (유니크한 값의 개수) 가 관리된다. 위의 쿼리를 실행하면 (A) 케이스의 경우에는 평균 1,000건 (B) 케이스의 경우네느 평균 10건이 조회될 수 있다는 것을 예측할 수 있다. (A), (B) 케이스 모두 위 쿼리문에서 만족하는 레코드는 단 1건만 있었다면 (A) 케이스 인덱스는 1건의 레코드를 위해 999건의 레코드를 더 읽게 되고 (B) 케이스 인덱스는 9건만 더 읽게 된다. 그래서 (A) 케이스의 경우 country 컬럼에 생성된 인덱스는 (B) 케이스에 비해 비효율적이게 된다. 모든 조건을 만족하는 인덱스를 생성한다는 것은 불가능에 가깝기 때문에  (A) 케이스 정도의 낭비는 무시할 수 있는 수준이다. 인덱스에서 유니크한 값의 개수(선택도, 기수성)는 인덱스나 쿼리의 효율성에 큰 영향을 미친다.

 

4. 읽어야 하는 레코드의 건수

인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 많은 비용이 드는 작업이다. 일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도 비용이 더 많이 드는 작업으로 예측한다. (RDBMS 서버 정류별로 차이가 있을 수 있으며 MySQL 서버에서는 코스트(Cost) 모델 설정에 따라 변경될 수 있다.) 그래서 읽어야 할 레코드의 건수가 테이블의 전체 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 가려내는 필터링 방식으로 처리하는 것이 효율적이다.