treecode

개념

- 디스크 읽기 방식

- 인덱스란?

- B-Tree 인덱스

- 클러스터링 인덱스

- 유니크 인덱스

- 외래키

디스크 읽기 방식

디스크를 읽는 방식에는 랜덤(Random) I/O, 순차(Sequential) I/O가 있다. 이전에 가상 메모리, 페이징을 공부하면서 디스크 I/O를 줄이는 것이 중요하다는 것을 배웠는데 일반적으로 데이터베이스도 디스크에 데이터를 읽고 저장하기 때문에 디스크 I/O가 성능에 큰 영향을 끼친다.

순차 I/O는 디스크 헤더를 움직이지 않고 한번에 많은 데이터를 읽는 작업으로 비중이 크지 않다.

랜덤 I/O는 부분적으로 작은 데이터를 읽고 쓰는 작업으로 대부분의 작업이 이에 해당한다.

디스크 원판을 가지지 않는 SSD는 HDD에 비해 랜덤 I/O 속도가 훨씬 빠른데 그래도 순차 I/O에 비하면 전체 스루풋(Throughput)이 떨어진다고 한다.

일반적으로 쿼리를 튜닝하는 것은 랜덤 I/O 자체를 줄여주는 것이 목적으로 쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것을 의미한다.

인덱스란?

인덱스에 대해 찾아보면 대부분 책 뒤에 있는 색인으로 비유를 하는데 "ㄱ", "ㄴ", "ㄷ" 와 같은 순서로 정렬을 해서 원하는 데이터를 빠르게 찾을 수 있도록 도와주는 역할을 한다. 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 희생하고 읽기 속도를 향상 시키는 것이다.

인덱스는 유니크(Unique)한 인덱스와 유니크 하지 않은 인덱스로 구분할 수 있는데 이는 실제 쿼리를 실행해야 하는 옵티마이저에게 상당히 중요한 문제이다. 유니크 인덱스에 대해 동등 조건('=')으로 검색한다는 것은 항상 1건의 코드만 찾으면 더 찾지 않아도 된다는 것을 옵티마이저에게 알려주는 효과를 낸다.

B-Tree 인덱스

인덱싱 알고리즘으로 가장 일반적으로 사용되는 B-Tree(Balanced-Tree)는 다음과 같은 구조로 되어 있다.

- 최상위 루트 노드(Root node)

- 중간 자식 노드 (Branch node)

- 최하위 자식 노드 (Leaf node)

데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데 일반적으로 인덱스의 리프 노드는 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.

데이터 파일은 일반적으로 정렬이 되지 않은 상태로 저장이 되는데 DELETE 된 공간이 다시 재활용 되기 때문에 순서가 섞인다.

InnoDB 테이블

- 레코드가 클러스터 되어 디스크에 저장 되기 때문에 기본적으로 프라이머리 키 순서로 정렬이 되어 저장

- 리프 노드가 실제 주솟값이 아닌 프라이머리 키를 논리적인 주소로 사용 (세컨더리 인덱스 검색에서 프라이머리 키를 저장하고 있는 B-Tree를 다시 한번 검색)

인덱스 키를 추가할때 리프 노드가 꽉차면 분리가 되면서 상위 브랜치 노드까지 처리의 범위가 넓어지는데 이러한 이유로 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 든다. (이 비용의 대부분이 메모리와 CPU에서 처리하는 시간이 아니라 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 해서 걸리는 시간)

아무튼 이런 비용을 감당하면서 인덱스를 사용하는 이유는 빠른 검색을 위해서이다. DB을 잘 사용하려면 얻는 것과 잃는 것에 대해 많은 경험, 고민이 필요한 것 같다.

인덱스를 이용한 검색에서 주의할 점은 인덱스의 키 값에 변형이 가해진 후 비교되는 경우 B-Tree의 빠른 검색 기능을 사용할 수 없다는 것인데 함수나 연산을 수행한 결과로 정렬, 검색을 하는 작업은 B-Tree의 장점을 이용할 수 없으므로 주의해야 한다.

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라고 하며 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다. 위의 루트, 브랜치, 리프 노드를 구분한 기준도 페이지 단위이다.

하나의 인덱스 페이지는 4KB ~ 64KB(기본값 16KB)의 크기를 가지는데 인덱스 키 값이 커지면 그만큼 하나의 페이지에 담을 수 있는 키가 줄어들고 페이지 깊이(depth)가 증가하게 된다. 이는 디스크로부터 읽어야 하는 횟수가 늘어나고 그만큼 느려질 수 있다는 것을 의미한다.

인덱스를 통해 테이블의 레코드를 일는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업인데 인덱스를 통해 읽어야 할 레코드의 건수가 많다면(대략 전체 테이블 레코드의 20~25% 기준) 인덱스를 사용하지 않고 테이블을 모두 읽어서 필터링 하는 방식이 효율적이다. (MySQL의 옵티마이저는 이런 경우 예상을 해서 효율적인 방식으로 처리한다)

클러스터링 인덱스

MySQL 서버에서 클러스터링은 테이블의 레코드를 비슷한 것(프라이머리 키)들끼리 묶어서 저장하는 형태로 구현되는데 InnoDB는 프라이머리 키를 클러스터링 인덱스로 사용한다. 중요한 것은 프라이머리 키 값에 의해 레코드의 저장 위치가 결정된다는 것이다.

프라이머리 키가 세컨더리 인덱스에 미치는 영향

InnoDB 테이블의 모든 세컨더리 인덱스는 해당 레코드가 저장된 주소가 아니라 프라이머리 키(클러스터링 인덱스) 값을 저장하도록 구현이 되어 있다. 

세컨더리 인덱스가 프라이머리 키 값을 포함하고 있기 때문에 프라이머리 키의 크기가 커질 경우 세컨더리 인덱스도 자동으로 크기가 커지게 되서 위에서 말한대로 디스크 I/O가 증가하게 된다. 그래서 프라이머리 키의 크기는 가능하면 작게 사용하는 것이 효율적이다.

하지만 InnoDB의 프라이머리 키는 클러스터링 키로 사용되며 검색에 큰 이점이 있어서 해당 칼럼의 크기가 크더라도 업무적으로 해당 레코드를 대표할 수 있다면 그 칼럼을 프라이머리 키로 설정하는 것도 좋다고 한다.

유니크 인덱스

유니크 인덱스는 고유한 값으로 검색 시 1건만 찾으면 되기 때문에 유니크하지 않은 인덱스에 비해 훨씬 빠를 것 같지만 유니크하지 않은 인덱스의 경우 CPU에서 칼럼값을 비교하는 작업이 추가되는 것이라서 성능상 큰 차이는 없다고 한다.

오히려 유니크 인덱스는 주의해야 될 점이 있는데 유니크 인덱스 쓰기 작업의 경우 별도로 중복된 값이 있는지 없는지 체크를 한다. MySQL에서는 중복된 값을 체크할 때 읽기 잠금을 사용하고, 쓰기를 할 때는 쓰기 잠금을 사용하는데 이 과정에서 데드락이 빈번히 발생한다. 그리고 InnoDB 스토리지 엔진은 인덱스 키의 저장을 체인지 버퍼(Change Buffer)를 사용해서 버퍼링을 하기 때문에 인덱스의 쓰기 작업을 빨리 처리할 수 있는데 유니크 인덱스의 경우는 중복 체크를 해야 하기 때문에 작업 자체를 버퍼링하지 못한다. (= 꼭 필요할때 사용)

외래키

InnoDB의 외래키 관리

- 테이블의 변경(쓰기 잠금)이 발생하는 경우에만 잠금 경합(잠금 대기)이 발생한다.

- 외래키와 연관되지 않은 칼럼의 변경은 최대한 잠금 경합(잠금 대기)를 발생시키지 않는다.

자식 테이블의 외래 키 칼럼의 변경은 부모 테이블의 확인이 필요한데, 이 상태에서 부모 테이블의 해당 레코드가 쓰기 잠금이 걸려 있으면 해당 쓰기 잠금이 해제될 때까지 기다리게 된다. 자식 테이블의 외래키가 아닌 칼럼의 변경은 외래키로 인한 잠금 확장이 발생하지 않는다.

데이터베이스에서 외래 키를 물리적으로 생성하려면 이러한 잠금 경합을 고려해 모델링을 해야한다. 물리적으로 외래키를 생성하면 자식 테이블에 레코드가 추가되는 경우 해당 참조키가 부모 테이블에 있는지 확인하는데 이때 연관 테이블에 읽기 잠금을 걸어서 이런 잠금 확장으로 인한 영항을 신경 써야한다.

[참고]

Real MySQL 책