Real MySQL 1권 (p.223 ~ 247)
B-Tree 인덱스
인덱스는 쓰기 성능을 희생해서 조회 성능을 높인다.
-
테이블에 레코드를 추가하는 작업 비용이 1이라고 가정하면, 해당 테이블 인덱스에 키를 추가하는 작업 비용은 1.5 정도로 예측할 수 있다. 이때 비용의 대부분은 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 해서 발생한다.
-
InnoDB 스토리지 엔진은 체인지 버퍼를 사용해서 이 작업을 지연시켜 좀 더 효율적으로 처리할 수 있지만, 프라이머리 키나 유니크 인덱스의 경우 중복 체크가 필요해서 즉시 처리해야 한다.
인덱스 사용에 영향을 미치는 요소
-
인덱스 키 값의 크기, B-Tree 깊이, 카디널리티, 읽어야 하는 레코드의 건수가 있다.
-
인덱스 키 값이 커지면 하나의 인덱스 페이지에 저장할 수 있는 키의 개수가 적어진다. 따라서 전체적인 인덱스 크기가 커지고 B-Tree의 깊이가 깊어진다. 결국 메모리에 캐시해 둘 수 있는 레코드 개수가 적어지고, 인덱스를 사용하기 위해 디스크를 더 많이 읽어야 한다.
-
일반적으로 옵티마이저는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도 비용이 더 많이 드는 작업으로 예측한다. 따라서 인덱스를 통해 읽어야 할 레코드 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블 풀 스캔 방식으로 처리하는 것이 효율적이라고 판단한다.
인덱스 풀 스캔
-
인덱스의 처음부터 끝까지 모두 읽는 방식으로, 효율적으로 인덱스를 사용하는 방식은 아니다.
-
인덱스에 포함된 칼럼만으로 쿼리를 처리할 수 있는 경우, 테이블의 레코드를 읽을 필요가 없다.
-
인덱스의 전체 크기는 테이블 자체의 크기보다는 훨씬 작으므로 인덱스 풀 스캔을 사용하면 테이블 풀 스캔을 사용하는 것보다 디스크 I/O가 적다.
인덱스 스캔 방향
-
MySQL 8.0부터는 인덱스 구성 칼럼의 정렬을 오름차순, 내림차순 혼합해서 인덱스를 생성할 수 있다. 이는 정렬 방향을 혼합한 조회 쿼리를 최적화하는 용도로 사용할 수 있다.
-
옵티마이저는 정렬된 인덱스를 역순으로 읽을 수도 있다. 즉, 필요에 따라 인덱스 읽기 방향을 전환한다.
-
InnoDB에서 인덱스 역순 스캔이 정순 스캔보다 오래 걸리는데, 그 이유는 다음과 같다.
- 페이지 잠금이 인덱스 정순 스캔에 적합한 구조이다. 인덱스 역순 스캔의 경우 페이지 잠금 및 해제 처리에 추가적인 오버헤드가 발생한다.
- 페이지 내에서 인덱스 레코드가 단방향으로 연결된 구조이다. 따라서, 페이지 내부 레코드를 역순으로 조회할 때 추가적인 오버헤드가 발생한다.
- 참고 링크
CSAPP (p.567 ~ 577)
5.8 Loop Unrolling
개념
각 iteration에서 계산되는 element의 개수를 늘림으로써 전체 iteration 수를 줄이는 program transformation
왜 사용하는가
성능 향상을 위해 사용
- 프로그램 실행 결과에 직접 영향을 주지 않는 loop overhead를 줄여줌 (loop indexing, conditional branch)
- 전체 computation의 critical path를 구성하는 연산 개수를 줄이는 방법 제공
한계
단순히 k * 1 loop unrolling만 적용하면 critical path를 구성하는 연산 개수가 동일하기 때문에 latency bound보다 낮은 CPE를 달성할 수 없음
5.9 Enhancing Parallelism
Multiple Accumulator를 두는 방법 적용
- 이를 통해 iteration 내부 연산들 간 data dependency가 사라지고 latency bound보다 낮은 CPE 달성
- unrolling loop by a factor of k and accumulate k values in parallel ->
k * k loop unrolling - 일반적으로 프로그램이 특정 연산의 throughput bound를 달성하기 위해 해당 연산을 수행하는 모든 functional unit의 pipeline을 가득 채운 채로 유지해야 함
- 따라서
(throughput bound를 달성하기 위한 k 값) >= Latency (해당 연산을 수행하기 위한 사이클 수) * Capacity (해당 연산을 수행할 수 있는 functional unit 개수)임
한계
- floating-point multiplication, addition은 결합법칙이 성립하지 않음 (not associative)
- 따라서 특정 데이터에 대해서는 최적화 적용 전후 결과가 다를 수 있고, 컴파일러는
k * k loop unrolling을 시도하지 않을 것이므로 프로그래머가 코드를 변경해줘야 함
