2022-10-12 @이영훈
1. 디스크 읽기 방식
CPU나 메모리처럼 전기적 특성을 띤 장치의 성능은 짧은 시간 동안 매우 빠른 속도로 발전했지만 디스크 같은 기계식 장치의 성능은 상당히 제한적으로 발전했다.
데이터베이스의 성능 튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건이다.
1. 하드 디스크 드라이브(HDD)와 솔리드 스테이트 드라이브(SSD)
디스크의 헤더를 움직이지 않고 한 번에 많은 데이터를 읽는 순차 I/O에서는 SSD가 하드 디스크 드라이브보다 조금 빠르거나 거의 비슷한 성능을 보이기도 한다.
하지만 랜덤 I/O는 SSD가 훨씬 빠르다.
데이터베이스 서버에서 순차 I/O 작업은 그다지 비중이 크지 않고 랜덤 I/O를 통해 작은 데이터를 읽고 쓰는 작입이 대부분이므로 SSD의 장점은 DBMS용 스토리지에 최적이라고 볼 수 있다.
2. 랜덤 I/O와 순차 I/O
디스크에 데이터를 읽고 쓰는 데 걸리는 시간은 디스크 헤더를 움직여서 읽고 쓸 위치로 옮기는 단계에서 결정된다.
예를 들어, 3개의 데이터를 읽는 순차 I/O와 3개의 데이터를 읽는 랜덤 I/O 요청이 있다.
순차 I/O는 3개의 페이지(3 x 16KB)를 디스크에 기록하기 위해 1번 시스템 콜을 요청(1번 디스크 헤더를 움직임)했지만 랜덤 I/O는 3개의 페이지를 디스크에 기록하기 위해 3번 시스템 콜을 요청(3번 디스크 헤더를 움직임)했다.
디스크 원판을 가지지 않는 SSD도 순차 I/O가 랜덤 I/O보다 더 빠르다.
쿼리를 튜닝해서 랜덤 I/O를 순차 I/O로 바꿔서 실행할 방법은 많지 않다.
일반적으로 쿼리를 튜닝하는 것은 랜덤 I/O 자체를 줄여주는 것이 목적이라고 할 수 있다. 랜덤 I/O를 줄인다는 것은 쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것을 의미한다.
2. 인덱스란?
DBMS가 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 빨리 가져오기 위해서 인덱스를 만든다.
칼럼(또는 칼럼들)의 값과 해당 레코드가 레코드가 저장된 주소를 키와 값의 쌍(key-value pair)로 삼아 인덱스를 만들어두는 것이다.
DBMS의 인덱스도 칼럼의 값을 주어진 순서로 미리 정렬해서 보관한다.
SortedList는 DBMS의 인덱스와 같은 자료 구조이며, ArrayList는 데이터 파일과 같은 자료 구조이다.
SortedList 자료 구조는 데이터가 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리지만 이미 정렬돼 있어 아주 빨리 원하는 값을 찾아올 수 있다.
DBMS에서 인덱스는 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능이다.
테이블의 인덱스를 하나 더 추가할지 말지는 데이터의 저장 속도를 어디까지 희생할 수 있는 지, 읽기 속도를 얼마나 더 빠르게 만들어야 하느냐에 따라 결정해야 한다.
이 책에서는 키(Key)라는 말과 인덱스(Index)는 같은 의미로 사용하겠다.
(1) 인덱스를 역할별로 구분해본다면 프라이머리 키 (Primary Key)와 보조 키(Secondary Key)로 구분할 수 있다.
•
Primary Key(PK)는 레코드를 대표하는 칼럼의 값으로 만들어진 인덱스를 의미한다.
NULL 값을 허용하지 않으며, 중복을 허용하지 않는 특성이 있다.
•
Secondary Index는 PK를 제외한 모든 인덱스이다.
(2) 데이터 저장 방식(알고리즘)별로 구분할 경우, 대표적으로 B-Tree 인덱스와 Hash 인덱스로 구분할 수 있다.
•
B-Tree 알고리즘은 칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘이다.
위치 기반 검새을 지원하는 R-Tree 알고리즘도 있지만 B-Tree의 응용 알고리즘으로 볼 수 있다.
•
Hash 인덱스 알고리즘은 해시값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다.
하지만 값을 변형해서 인덱싱하므로 값의 일부만 검색하거나 범위를 검색할 때는 해시 인덱스를 사용할 수 없다.
주로 메모리 기반의 데이터베이스에서 많이 사용된다.
(3) 데이터의 중복 여부로 분류하면, Unique와 Non-Unique한 인덱스로 구분할 수 있다
•
단순히 같은 값이 1개만 존재하는지 1개 이상 존재할 수 있는지를 의미하지만, 실제 DBMS의 쿼리를 실행해야하는 옵티마이저에게는 상당히 중요한 문제가 된다.
•
동등 조건 (=)으로 검색하는 것은 항상 1건의 레코드만 찾으면 더 찾지 않아도 된다는 것을 옵티마이저에게 알려주는 효과를 낸다.
(4) 인덱스의 기능별로 분류해보면, 전문 검색용 인덱스나 공간 검색용 인덱스 등을 예로 들 수 있다.
3. B-Tree 인덱스
B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다.
B는 Binary가 아니라 Balanced이다!!
일반적으로 DBMS에서는 주로 B⁺-Tree 또는 B*-Tree가 사용된다.
B-Tree는 칼럼의 원래 값을 변형시키지 않고 (물론 값의 앞부분만 잘라서 관리하기는 하지만) 인덱스 구조체 내에서는 항상 정렬된 상태로 유지한다.
1. 구조 및 특성
B-Tree 는 트리 구조의 최상위 위에 하나의 루트 노드(Root node)가 존재하고 그 하위에 자식 노드가 붙어 있는 형태다.
트리 구조의 가장 하위에 있는 노드를 리프 노드(Leaf node)라 하고, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간의 노드를 브랜치 노드(Branch node)라고 한다.
데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있다.
인덱스의 값은 모두 정렬되어 있지만, 데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서로 저장돼 있다.
•
데이터 파일의 레코드는 INSERT 순으로 저장되는 것은 아니다.
•
테이블의 레코드를 전혀 삭제하거나 변경하지 않고 INSERT만 수행한다면 맞을 수도 있다.
•
하지만 레코드가 삭제되어 빈 공간이 생기면 그다음의 INSERT는 가능한 한 삭제된 공간을 재활용하도록 DBMS가 설계되기 때문에 항상 INSERT된 순서로 저장되는 것은 아니다.
MyISAM에서 레코드 주소는 테이블의 생성 옵션에 따라 레코드가 테이블에 INSERT된 순번이거나 데이터 파일 내의 위치(Offset)다.
MyISAM 테이블은 세컨더리 인덱스가 물리적인 주소를 가진다.
InnoDB 스토리지 엔진에서는 프라이머리 키가 ROWID 역할을 한다.
인덱스에 저장돼 있는 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후, 데이터 파일(프라이머리 키 인덱스)의 리프 페이지에 저장돼 있는 레코드를 읽는다.
즉, InnoDB 스토리지 엔진에서는 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한번 검색해야 한다.
2. B-Tree 인덱스 키 추가 및 삭제
2.1 인덱스 키 추가
B-Tree에 저장될 때 키 값을 이용해 B-Tree상의 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 B-Tree의 리프 노드에 저장한다.
리프 노드가 꽉 차서 저장할 수 없을 때, 리프 노드가 분리(Split)돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다. 그래서 B-Tree는 상대적으로 쓰기 작업(새로운 키를 추가하는 작업)에 비용이 많이 든다.
인덱스 추가로 인해 INSERT나 UPDATE 문장이 어떤 영향을 받을지 대략적인 비용 계산은 다음과 같다.
테이블에 레코드를 추가하는 작업 비용을 1이라고 가정하면, 해당 테이블의 인덱스에 키를 추가하는 작업 비용을 1.5 정도로 예측하는 것이다. (B-Tree에 정렬해서 넣는 것이 정렬없이 데이터 파일을 넣는것보다 더 크게 비용이 계산되는 것을 알 수 있다)
•
일반적으로 테이블에 인덱스가 3개가 있다면, 5.5 (1 + 1.5 x 3)의 비용을 예측한다.
•
이 비용의 대부분이 메모리와 CPU에서 처리하는 시간이 아니라 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 해서 걸리는 시간이다.
MyISAM이나 MEMORY 스토리지 엔진을 사용하는 테이블에서는 INSERT 문장이 실행되면 즉시 새로운 키 값을 B-Tree 인덱스에 변경한다.
InnoDB 스토리지 엔진은 필요하다면 인덱스 키 추가 적업을 지연시켜 나중에 처리할 수 있다. 하지만 PK, Unique 인덱스 경우 중복 체크가 필요하기 때문에 즉시 B-Tree에 추가하거나 삭제한다.
2.2 인덱스 키 삭제
해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료된다.
삭제 마킹된 인덱스 키 공간은 그대로 방치하거나 재활용할 수 있다.
삭제 마킹 작업 또한 디스크 쓰기가 필요하므로 디스크 I/O가 필요한 작업이다.
InnoDB 스토리지 엔진에서는 이 작업 또한 버퍼링되어 지연 처리될 수도 있다.
MyISAM이나 MEMORY 스토리지 엔진의 테이블에서는 체인지 버퍼와 같은 기능이 없으므로 인덱스 키 삭제가 완료된 후 쿼리 실행이 완료된다.
2.3 인덱스 키 변경
인덱스의 키 값은 그 값에 따라 저장될 리프 노드의 위치가 결정되므로 인덱스상의 키 값만 변경하는 것은 불가능하다.
B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다.
B-Tree 인덱스 키 값의 삭제와 추가는 앞에서 설명한 절차대로 처리된다.
InnoDB 스토리지 엔진을 사용하는 테이블에 대해서는 이 작업 모두 체인지 버퍼를 활용해 지연 처리될 수 있다.
2.4 인덱스 키 검색
B-Tree 인덱스를 이용한 검색 가능한 경우
•
100% 일치
•
값의 앞부분(Left-most part)만 일치하는 경우
•
부등호(<, >) 비교 조건
B-Tree 인덱스를 이용한 검색이 불가능한 경우
•
함수나 연산을 수행한 결과로 검색하는 경우 (B-Tree 인덱스에 없는 값이기 때문)
3. B-Tree 인덱스 사용에 영향을 미치는 요소
3.1 인덱스 키 값의 크기
InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(Page)라고 하며, 디스크 읽기의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다.
버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 하다. 인덱스도 결국은 페이지 단위로 관리된다.
루트와 브랜치, 리프 노드를 구분한 기준이 바로 페이지 단위이다.
인덱스 페이지 크기와 키 값의 크기에 따라 B-Tree의 자식 노드를 몇 개까지 가지는 지 결정된다.
InnoDB 스토리지 엔진의 페이지 크기는 innodb_page_size 시스템 변수를 이용해 4KB~64KB 사이의 값을 선택할 수 있지만 페이지의 기본값은 16KB이다.
인덱스의 키가 16바이트라고 가정하자.
그리고 자식 노드 주소라는 것은 여러 가지 복합적인 정보가 담긴 영역이며, 페이지 종류별로 대략 6바이트에서 12바이트까지 다양한 크기를 가질 수 있다. 평균 12바이트라고 가정하자.
이 경우 하나의 인덱스 페이지(16KB)에서 몇 개의 키를 저장할 수 있을까?
•
16 x 1024 / (16+12) = 585개를 저장할 수 있다.
만약 키 값의 크기가 두 배인 32바이트로 늘어났다고 가정하면 한 페이지에 인덱스 키를
•
16 x 1024 / (32 + 12) = 372개 저장할 수 있다.
결국 인덱스를 구성하는 키 값의 크기가 커진다면
•
디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 느려진다는 것을 의미한다.
•
전체적인 인덱스의 크기가 커진다는 것을 의미한다.
•
인덱스를 캐시해 두는 InnoDB 버퍼 풀이나 MyISAM의 키 캐시 영역은 크기가 제한적이기 때문에 하나의 레코드를 위한 인덱스 크기가 커지면 메모리에 캐시해 둘 수 있는 레코드 수는 줄어든다.
3.2 B-Tree 깊이
인덱스의 B-Tree 깊이가 3인 경우 최대 몇 개의 키 값을 가질 수 있는지 한 번 비교해보자.
키 값이 16바이트인 경우에는 최대 2억(585 x 585 x585)개 정도의 키값을 담을 수 있지만,
키 값이 32바이트로 늘어나면 5천만(372 x 372 x 372)개로 줄어든다.
B-Tree의 깊이는 MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다.
결론적으로 인덱스 키 값의 크기가 커지면 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어지고, 그 때문에 같은 레코드 건수라 하더라도 B-Tree의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다는 것을 의미한다.
인덱스 키 값의 크기는 가능하면 작게 만드는 것이 좋다는 것을 강조하기 위함이고, 실제로는 아무리 대용량 데이터베이스라도 B-Tree의 깊이가 5단계 이상까지 깊어지는 경우는 흔치 않다.
3.3 선택도(기수성)
인덱스에서 선택도(Selectivity) 또는 기수성(Cardinality)은 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다.
전체 인덱스 키 값(전체 row)은 100개인데, 그중에서 유니크한 값의 수(row)는 10개라면 기수성은 10이다.
인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.
선택도가 좋지 않다고 하더라도 정렬이나 grouping과 같은 작업을 위해 인덱스를 만드는 것이 훨씬 나은 경우도 많다. 인덱스가 항상 검색에만 사용되는 것은 아니므로 여러 가지 용도를 고려해 적절히 인덱스를 설계할 필요가 있다.
country 칼럼과 city라는 칼럼이 포함된 tb_test 테이블을 예로 들겠다.
tb_test 테이블의 전체 레코드 건수는 1만 건이며, country 칼럼만 인덱스가 생성된 상태에서 아래의 두 케이스를 살펴보자
•
caseA: country 칼럼의 유니크한 값의 개수가 10개
•
caseB: country 칼럼의 유니크한 값의 개수가 1,000개
SELECT *
FROM tb_test
WHERE countr='KOREA' AND city='SEOUL';
SQL
복사
MySQL에서는 인덱스의 통계 정보(유니크한 값의 개수)가 관리되기 때문에 city 칼럼의 기수성은 작업 범위에 아무런 영향을 미치지 못한다.
A 케이스의 경우에는 평균 1,000건, B 케이스의 경우에는 평균 10건이 조회될 수 있다는 것을 인덱스의 통계 정보(유니크한 값의 개수)로 예측할 수 있다.
A 케이스와 B 케이스 모두 조건을 만족하는 레코드가 단 1건만 있었다면,
•
A 케이스는 1건을 위해 999건을 더 읽은 것이고,
•
B 케이스는 1건을 위해 9건을 더 읽은 것이다.
그래서 A 케이스의 경우 country 칼럼에 생성된 인덱스는 비효율적이다.
기수성이 높을수록 쿼리의 효율성에 더 좋은 영향을 미친다.
3.4 읽어야 하는 레코드의 건수
️ 인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업이다. (인덱스를 통해 읽으면 랜덤 I/O가 발생하고 반면에 테이블 레코드를 바로 읽으면 순차 I/O가 발생하기 때문에)테이블에 레코드가 100만 건이 저장돼 있는데, 그중에서 50만 건을 읽어야 하는 쿼리가 있다고 가정해보자.
이 작업은 전체 테이블을 모두 읽어서 필요 없는 50만 건을 버리는 것이 효율적일지, 인덱스를 통해 필요한 50만 건만 읽어 오는 것이 효율적일지 판단해야 한다.
일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도 비용이 더 많이 드는 작업인 것으로 예측한다.
즉, 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 가려내는(필터링) 방식으로 처리하는 것이 효율적이다.
4. B-Tree 인덱스를 통한 데이터 읽기
어떤 경우에 인덱스를 사용하게 유도할지 또는 사용하지 못하게 할지 판단하려면 MySQL이 어떻게 인덱스를 이용해서 실제 레코드를 읽어 내는지 알아야 한다.
4.1 인덱스 레인지 스캔
인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다.
인덱스만 읽는 경우 위의 그림처럼 동작한다.
루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 찾아 들어가야만 비로소 필요한 레코드의 시작 지점을 찾을 수 있다.
시작해야 할 위치를 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 된다. 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아가서 다시 스캔한다. 그리고 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다.
B-Tree 인덱스의 리프 노드를 스캔하면서 실제 데이터 파일의 레코드를 읽어오는 경우 다음과 같이 동작한다.
B-Tree 인덱스에서 루트와 브랜치 노드를 이용해 스캔 시작 위치를 검색하고, 그 지점부터 필요한 방향(오름차순 또는 내림차순)으로 인덱스를 읽어 나가는 과정을 위의 그림과 같이 거친다.
해당 인덱스를 구성하는 칼럼의 정순 또는 역순으로 정렬된 상태로 레코드를 가져온다는 것이다. 이는 별도의 정렬 과정이 수반되는 것이 아니라 인덱스 자체의 정렬 특성 때문에 자동으로 그렇게 된다.
인덱스의 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다. 이 때 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 레코드 한 건 한 건 단위로 랜덤 I/O가 한 번씩 일어난다. 그래서 인덱스틀 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 작업으로 분류된다.
인덱스 레인지 스캔은 다음과 같이 크게 3단계를 거친다.
1.
[인덱스 탐색, Index Seek] 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다.
2.
[인덱스 스캔, Index Scan] 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 쭉 읽는다.
3.
2번에서 읽어 들인 인덱스 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽어온다.