5장. 인덱스

디스크 읽기 방식

• 데이터베이스의 성능 튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건인 것들이 상당함

저장 매체

DAS

• 컴퓨터의 본체와 달리 디스크만 있음
• 모두 SATA SAS와 같은 케이블로 연결되어서 사용자에게는 같은 방식으로 사용됨
• 하지만 반드시 하나의 컴퓨터 본체에만 연결해서 사용 가능 → 컴퓨터가 동시에 공유하는 것이 불가능

NAS

• TCP/IP를 통해 연결됨
• 여러 컴퓨터에서 공유해서 사용할 수 있는 저장 매체지만 SATA/SAS 방식에 비해 속도가 느림
• 데이터 비용으로는 사용 X

SAN

• 대용량의 스토리지 공간
• 여러 컴퓨터 사용 가능, 광케이블로 연결돼서 빠름
• 하지만 고가의 구축 비용

SSD

• 원판을 제거하고 메모리를 장착 → 기계적으로 회전 X 빠르게 데이터 읽고 쓰기 가능, 전원이 공급되지 않아도 데이터가 삭제되지 않음
• 웹 서비스 환경의 데이터베이스에서는 디스크 드라이버보다 훨씬 빠름

랜덤 I/O와 순차 I/O

순차 I/O

• 3개의 페이지를 기록하기 위해 1번 시스템 콜 요청

랜덤 I/O

• 3개의 페이지를 디스크에 기록하기 위해 3번의 시스템 콜 요청

즉 디스크의 성능 - 디스크 헤더의 위치 이동 없이 얼마나 많은 데이터를 한번에 기록하느냐가 결정

랜덤 I/O가 부하가 큼

인덱스

• 책으로 비유하면 - 맨뒤의 ‘찾아보기’ 가 인덱스, 책의 내용이 데이터
• 컬럼값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어 두는 것
• 컬럼의 값을 주어진 순서로 미리 정렬해서 보관
• DBMS의 인덱스 - SortedList와 마찬가지로 정렬된 상태를 유지
  • 저장될 때마다 정렬해야하므로 복잡하고 느림 but 빨리 원하는 값을 찾음

B-Tree index

• B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 또한 가장 먼저 도입된 알고리즘
• "B"는 "Binary(이진)"의 약자가 아니라 "Balanced"를 의미
• B-Tree는 컬럼의 원래 값을 변형시키지 않고 (물론 값의 앞부분만 잘라서 관리하기는 하지만) 인덱스 구조체 내에서는 항상 정렬된 상태로 유지하고 있습니다.

구조 및 특성

B-Tree는 트리 구조의 최상위에 하나의 "루트 노드"가 존재하고 그 하위에 자식 노드가 붙어 있는 형태입니다. 트리 구조의 **가장 하위에 있는 노드를 "리프 노드"**라 하고, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 **중간 노드를 "브랜치 노드"**라고 합니다.

인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소 값을 가지고 있습니다.

레코드가 삭제되어 빈 공간이 생기면 그다음의 INSERT는 가능한 삭제된 공간을 재활용하도록 DBMS가 설계되기 때문에 항상 INSERT된 순서로 저장되는 것은 아닙니다.

대부분 RDBMS의 데이터 파일에서 레코드는 특정 기준으로 정렬되지 않고 임의의 순서대로 저장됩니다. 하지만 InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되므로 기본적으로 프라이머리 키 순서대로 정렬되어 저장됩니다. 다른 DBMS에서는 클러스터링 기능이 선택 사항이지만, InnoDB에서는 사용자가 별도의 명령이나 옵션을 선택하지 않아도 디폴트로 클러스터링 테이블이 생성됩니다. 클러스터링이란 비슷한 값들은 최대한 모아서 저장하는 방식을 의미합니다.

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

InnoDB 테이블에서는 프라이머리 키에 의해 클러스터링되기 때문에 프라이머리 키값 자체가 주소 역할을 합니다. 실제 MySQL 테이블의 인덱스는 항상 인덱스 컬럼 값과 주소 값(MyISAM의 레코드 아이디 값 또는 InnoDB의 프라이머리 키값)의 조합이 인덱스 레코드로 구성됩니다.

B-Tree 인덱스 키 추가 및 삭제

• B-Tree에 저장될 때는 저장될 키값을 이용해 B-Tree상의 적절한 위치를 검색
• 저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장합니다. 만약 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리(Split)돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어짐 → 쓰기 작업에 비용이 많이 듦
• 인덱스 추가로 인해 INSERT나 UPDATE 문장이 어떤 영향을 받을지 궁금해하는 사람이 많습니다. 하지만 이 질문에 명확하게 답변하려면 테이블의 컬럼 수, 컬럼의 크기, 인덱스 컬럼의 특성 등을 확인해야합니다. 대략적으로 계산하는 방법은 테이블에 레코드를 추가하는 작업 비용을 1이라고 가정하면 해당 테이블의 인덱스에 키를 추가하는 작업 비용을 1~1.5 정도로 예측하는 것이 일반적입니다. 일반적으로 테이블에 인덱스가 3개(테이블의 모든 인덱스가 B-Tree라는 가정하에)가 있다면 이때 테이블에 인덱스가 하나도 없는 경우 작업 비용이 1이고, 3개인 경우에는 5.5 정도의 비용(1.5*3 + 1) 정도로 예측해 볼 수 있습니다. 중요한 것은 이 비용의 대부분이 메모리와 CPU에서 처리하는 시간이 아니라 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야하기 때문에 시간이 오래 걸린다는 점입니다.

1. 사용자의 쿼리 실행
2. InnoDB의 버퍼 풀에 새로운 키값이 추가해야 할 페이지(B-Tree의 리프 노드)가 존재한다면 즉시 키 추가 작업 처리
3. 버퍼 풀에 B-Tree의 리프 노드가 없다면 인서트 버퍼에 추가할 키값과 레코드의 주소를 임시로 기록해두고 작업 완료(사용자의 쿼리는 실행 완료됨)
4. 백그라운드 작업으로 인덱스 페이지를 읽을 때마다 인서트 버퍼에 머지해야 할 인덱스 키 값이 있는지 확인한 후, 있다면 병합함(B-Tree에 인덱스 키와 주소를 저장)
5. 데이터베이스 **서버 자원의 여유가 생기면 MySQL 서버의 인서트 버퍼 머지 스레드가 조금씩 인서트 버퍼에 임시 저장된 인덱스 키와 주소 값을 머지(B-Tree에 인덱스 키와 주소를 저장)**시킴

인덱스 키 삭제

• 해당 키값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료됩니다. 이렇게 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 또는 재활용할 수 있습니다.
• 인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 이작업 역시 디스크 I/O가 필요한 작업

인덱스 키 값 변경

• B-Tree의 키값 변경 작업은 먼저 키값을 삭제한 후, 다시 새로운 키값을 추가하는 형태로 처리됩니다. 키 값의 변경 때문에 발생하는 B-Tree 인덱스 키값의 삭제와 추가 작업은 위에서 설명한 절차대로 처리

인덱스 키 검색

• 트리 탐색(Tree traversal)으로 탐색
• 검색 할 때는 select 뿐만 아니라 update, delete 할 때도 검색이 빨라짐
• B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분(Left-most part)만 일치하는 경우에 사용할 수 있습니다. 부등호("<>") 비교나 값의 뒷부분이 일치하는 경우에는 B-Tree 인덱스를 이용한 검색이 불가능합니다
• 따라서 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree의 장점을 이용할 수 없으므로 주의

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

• 인덱스를 구성하는 컬럼의 크기와 레코드의 건수, 그리고 유니크한 인덱스 키값의 개수 등에 의해 검색이나 변경 작업의 성능이 영향
• 인덱스도 결국은 페이지 단위로 관리되며, 위의 B-Tree 그림에서 루트와 브랜치, 그리고 리프(Leaf) 노드를 구분한 기준이 바로 페이지 단위\
• Tree는 자식 노드의 개수가 가변적인 구조
• 인덱스 페이지 크기와 키 값의 크기에 따라 결정
• 인덱스를 구성하는 키값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 느려진다는 것을 의미합니다.
• 인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미
• 인덱스를 캐시해 두는 InnoDB의 버퍼 풀이나 MyISAM의 키 캐시 영역은 크기가 제한적이기 때문에 하나의 레코드를 위한 인덱스 크기가 커지면 커질수록 메모리(Buffer pool이나 key cache)에 캐시해 둘 수 있는 레코드 수는 줄어드는 것을 의미

B-Tree의 깊이

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

선택도(기수성)

• 전체 인덱스 키값은 100개인데, 그중에서 유니크한 값의 수는 10개라면 기수성은 10입니다. 인덱스 키값 가운데 중복된 값이 많아지면 많아질수록 기수성은 낮아지고 동시에 선택도 또한 떨어집니다.

예시

tb_test 테이블의 전체 레코드 건수는 1만 건이며, country 컬럼으로만 인덱스가 생성된 상태에서 아래 두 케이스를 살펴보자.

• 케이스 A: country 컬럼의 유니크한 값의 개수가 10개
• 케이스 B: country 컬럼의 유니크한 값의 개수가 1,000개

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

위의 쿼리를 실행하면 A 케이스의 경우에는 평균 1,000건(10000/10), B 케이스의 경우에는 평균적으로 10건(10000/1000)이 조회될 수 있다는 것을 인덱스의 통계 정보(유니크한 값의 개수)로 예측

A 케이스는 1건의 레코드를 위해 쓸모없는 999건의 레코드를 더 읽은 것이지만, B 케이스는 9건만 더 읽음

일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도 더 비용이 많이 드는 작업인 것으로 예측

⇒ 인덱스를 통해 읽어야 할 레코드의 건수(물론 옵티마이저가 판단한 예상 건수)가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 직접 테이블을 모두 읽어서 필요한 레코드만 가려내는(필터링) 방식으로 처리하는 것이 효율적

인덱스 레인지 스캔

• 인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식
• 만약 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔합니다. 그리고 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝냅니다.
• 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 레코드 한건 한건 단위로 랜덤 I/O가 한번씩 실행
• 인덱스를 통해 읽어야 할 데이터 레코드가 20~25%를 넘으면 인덱스를 통한 읽기보다 테이블의 데이터를 직접 읽는 것이 더 효율적인 처리 방식이 되는 것

인덱스 풀 스캔

• 인덱스를 사용하지만 인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 일근 방식을 인덱스 풀스캔
• 쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용됩니다. 인덱스뿐만이 아니라 데이터 레코드까지 모두 읽어야 한다면 절대 이 방식으로 처리되지 않습니다.
• 이 방식은 인덱스 레인지 스캔보다는 빠르지 않지만 테이블 풀 스캔보다는 효율적입니다. 인덱스에 포함된 컬럼만으로 쿼리를 처리할 수 있는 경우 테이블의 레코드를 읽을 필요가 없기 때문입니다.

루스 인덱스 스캔

• 중간마다 필요치 않은 인덱스 키값을 무시(SKIP)하고 다음으로 넘어가는 형태로 처리
• 일반적으로 GROUP BY 또는 집합 함수 가운데 MAX() 또는 MIN() 함수에 대해 최적화를 하는 경우에 사용

다중 컬럼(Multi-column) 인덱스

• 두 개 이상의 컬럼으로 구성된 인덱스를 다중 컬럼 인덱스라고 하며, 또한 2개 이상의 컬럼이 연결됐다고 해서 "Concatenated Index"라고도 합니다
• 인덱스의 두 번째 컬럼은 첫 번째 컬럼에 의존해서 정렬돼 있다는 것
• 두 번째 컬럼의 정렬은 첫 번째 컬럼이 똑같은 레코드에서만 의미가 있다는 것입니다.
• 다중 컬럼 인덱스에서는 인덱스 내에서 각 컬럼의 위치(순서)가 상당히 중요하며 또한 아주 신중히 결정

B-Tree 인덱스의 정렬 및 스캔 방향

• 인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 실시간으로 만들어 내는 실행 계획에 따라 결정
• MySQL에서 인덱스를 생성하는 시점에 인덱스를 구성하는 각 칼럼의 정렬을 오름차순 혹은 내림차순을 설정할 수 없다.
• 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬 효과를 얻을 수 있다.

B-Tree 인덱스 특성 상 사용할 수 없는 조건 목록

• NOT-EQUAL로 비교된 경우 (<>, NOT IN, NOT BETWEEN, IS NOT NULL)
• Like '%??' (앞부분이 아닌 뒷부분 일치) 형태로 문자열 패턴 비교
• 스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우 (WHERE SUBSTRING(id)='A')
• NOT-DETERMINISTIC 속성이 스토어드 함수가 비교 조건에 사용된 경우
• 데이터 타입이 서로 다른 비교
• 문자열 데이터 타입의 콜레이션이 다른 경우

MySQL에서는 다른 일반적인 DBMS와 다르게 NULL 값도 인덱스로 관리된다.

따라서 **"WHERE column is NULL"**과 같은 WHERE 조건도 작업 범위 결정 조건으로 인덱스를 사용한다.