Real MySQL - 8장 인덱스 정리 - 1

사전 지식

쿼리 튜닝

• 랜덤 IO를 줄이는 것이 목표
• 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것을 의미한다.
• 예)
  • index 걸린 컬럼만 읽는다던가 (커버링 인덱스)
  • 인덱스 풀스캔 대신 테이블 풀 스캔 사용
    • 순차 I/O 로 테이블을 다 읽는다. 그래서 테이블 풀스캔이 더 빠를 때도 있다.

데이터 저장 매체(디스크)는 컴퓨터에서 가장 느린 부분이다. 따라서 DB 성능 튜닝은 어떻게 Disk I/O를 줄이느냐가 관건인 경우가 많다.

• 디스크 접근 방식은 랜덤 IO와 순차 IO가 있다.

랜덤 IO vs 순차 IO

• 랜덤 IO
  • 하드 디스크 드라이브의 플래터(원판)을 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것을 의미
• 순차 IO
  • 작업 과정은 동일함
  • 다음 읽을 데이터가 바로 옆에 있기에 시스템 콜(헤드 이동 요청)이 불필요하다. 헤드를 이동하는 시간을 절약할 수 있다.
• 차이점
  • 순차는 3개의 페이지를 읽을 때 1번의 시스템 콜, 랜덤은 3번의 시스템 콜
  • 디스크 헤드를 순차는 1번, 랜덤은 3번 움직였다. 이 시간 소모가 데이터를 읽고 쓰는데 영향을 준다.
  • 최소 이동으로 데이터를 한번에 얼만큼 읽고 쓰느냐에 의해 디스크 성능이 결정됨.
    • MySQL은 그룹 커밋이나 바이너리 로그 버퍼 같은 기능으로 최적화를 시도함

SSD

• SSD는 플래터 대신 플래시 메모리를 사용하기에 헤드가 물리적으로 이동하는 시간이 필요가 없다.
• HDD와 비교했을 때 비교적 매우 빠르다.
  • 순차 IO에서는 조금 빠르거나 비슷한데, 랜덤 IO가 HDD 대비 훨씬 빠르다.

---

인덱스?

정의

• 하나 이상의 열에 있는 값을 기반으로 행을 보다 효율적으로 조회할 수 있는 방법을 제공하여 테이블에서 데이터 검색 작업의 속도를 향상시키는 데이터 구조
• 행의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍(key-value pair)으로 삼아 만들어 둔 것.
  • 행의 값을 기준으로 정렬된 데이터이다.

인덱스가 정렬되어 있는 것이 데이터가 정렬되어 있는 것을 의미하지 않는다. (클러스터 인덱스만 예외)

장점

• 정렬되어 있기에 빠르게 값을 찾아올 수 있다. (SELECT)

단점

• 정렬해야 하기에 저장 과정이 느리고 복잡하다. (INSERT, UPDATE, DELETE)

사용하는 이유

• 요청의 80%는 읽기, 20% 쓰기로 이루어진다. 80%를 차지하는 읽기 성능에 초점을 맞춘다.
• 따라서 인덱스를 하나 더 추가할지 말지도 1. 저장 속도를 어디까지 희생할 수 있는지, 2. 읽기 속도가 얼마나 중요한지에 따라 고려해야 한다.

인덱스 분류

관리 방식으로 분류

• 프라이머리 키와 세컨더리 키
  • 저자의 임의 구분 방식이다. (책에서는 키와 인덱스 명칭 혼용..)
  • 프라이머리 키
    • 열을 대표하는 행(레코드를 대표하는 컬럼 값)으로 만들어진 인덱스
    • 익히 알고있는 그 프라이머리 키를 인덱스로 만든 것을 의미한다.
  • 이외 모두 세컨더리 키로 분류한다.

저장 방식(알고리즘)으로 분류

• 대표적 B-Tree, Hash 인덱스
  • B-Tree는 뒤에 설명
  • Hash 인덱스는 컬럼 값 해싱
    • → 해시 값으로 인덱싱하는 알고리즘. 빠른 검색 지원
      • 일부 일치 불가능
      • 범위 검색 불가능
• 최근에는 Fractal-Tree, 로그 기반의 Merge-Tree

중복 허용 여부로 분류

• 유니크 인덱스와 유니크하지 않은 인덱스로 구분
• 옵티마이저에게 상당히 중요한 문제 (equals로 하나만 읽고 더 읽지 않아도 되는 기준)

기능별로 분류

• 전문 검색용 인덱스
• 공간 검색용 인덱스

B-Tree 인덱스

가장 일반적으로 사용되고 가장 먼저 도입됨. 가장 범용 목적으로 사용.

• 변형버전으로 B+ Tree또는 B*-Tree
• B는 Binary가 아니고 Balanced 이다.
• 컬럼의 원래 값을 변형시키지 않고 정렬 상태를 유지.

구조

루트(Root), 브랜치(Branch), 리프(Leaf) 노드로 구성됨.

• 루트: 최상위 단 하나의 노드 (시작점)
• 브랜치: 루트와 리프가 아닌, 사이를 잇는 중간 노드
• 리프: 최하위에 위치한 노드. 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있다.

인덱스는 키 컬럼만 갖고 있다. 따라서 레코드 데이터를 찾기 위해서는 루트 → 브랜치 → 리프 이동(트리 탐색) 후 주소값을 보고 데이터에 접근해서 가져와야 한다.

• 트리 탐색
  • B-Tree의 루트 노드 → 브랜치 노드 → 리프 노드까지 이동하면서 비교 작업 수행하는 과정

InnoDB에서 검색하려면 세컨더리 키 인덱스 트리 탐색 → 프라이머리 키 인덱스 트리 탐색 → 리프 노드의 정보를 통해 데이터 읽기 순으로 수행된다.

프라이머리 키 인덱스를 다시 타야하기 때문에 장단점이 조금 있다.

• 설명은 떨어질것처럼 했는데 크지 않은듯.

MyISAM / InnoDB 차이

• MyISAM은 세컨더리 인덱스가 데이터의 물리적인 주소를 갖고, InnoDB 테이블은 데이터 주소 대신 PK 주소를 사용한다. (논리적인 주소를 갖는다)

인덱스 키 검색

검색?

- 조회: 이미 알고 있는 정보를 찾는 과정.
- 검색: 대상이 명확하진 않지만 찾는 행위. 여러 곳에서 수집 분석을 통해 결과를 만든다.
  - “안녕하세요” 검색을 통해 바라는 것은 문자열이 포함된 블로그 글일수도, youtube일수도, 뉴스일수도 있다.
  - retrieve(검색): 저장 위치를 알고 있음. 특정 위치나 출처에서 정보 찾기.
  - search(검색): 저장 위치를 모름. 위치나 출처가 불확실한 정보를 찾는 것.
  - 조회와 검색은 다르다. 검색이 좀 더 넓은 범위의 조회 같은 느낌이다.

저장 공간 추가 사용같은 비용을 감당하면서 인덱스를 구축하는 이유는 빠른 검색을 위해서이다.

• 트리 탐색은 INSERT/UPDATE/DELETE에서도 사용된다. (값을 변경하기 위해서는 조회해야 한다)

주의

• InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키락(갭락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있다.
• 적절한 인덱스가 없으면 최악의 경우 테이블의 모든 레코드가 잠길 수도 있다.
• 인덱스 설계가 매우 중요하다.

인덱스 키 추가

• 적절한 저장 위치 검색 → 리프 노드에 저장.
• 적절한 위치가 없으면 리프 노드가 분리돼야 한다. 트리 밸런스를 유지하기 위해 다른 분리를 만들 수 있어서 상대적으로 쓰기에 비용이 많이든다.
  • 비용은 인덱스가 없는 테이블에 쓰기를 수행하는 비용을 1로 설정(기준), 인덱스 하나당 1.5 정도로 잡는다.
    • 인덱스가 3개인 테이블에 데이터를 추가하는 경우
    1.5*3 + 1(1.5 * 인덱스 수 + 기본 쓰기 비용) = 5.5의 비용이 든다.
  • InnoDB는 버퍼를 통해 좀 더 지능적으로 처리한다.

인덱스 키 삭제

• 리프 노드를 찾아 삭제 마크만하면 끝난다.
• 마킹도 디스크 쓰기가 필요하다.
  • InnoDB 스토리지 엔진에서는 버퍼링되어 지연처리
  • MyISAM이나 MEMORY 스토리지 엔진 테이블에서는 인덱스 키 삭제가 완료된 후 쿼리 실행이 완료
    • 블로킹 된다는 의미인듯 하다

인덱스 키 변경

• 단순 변경은 불가능하다. 키에 따라 리프노드 위치가 결정됨.
• 삭제 후 추가 형태로 작업된다.

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

키 값의 크기

• 인덱스를 구성하는 컬럼의 크기와 레코드의 건수
• 유니크한 인덱스 키 값의 개수

디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라 한다. 모든 디스크 I/O 작업의 최소 작업 단위

인덱스도 결국은 페이지 단위로 관리되며, 각 노드를 구분한 기준도 페이지 단위다.

• B-Tree는 자식 노드의 개수가 가변적인 구조다. 자식 노드의 최대 개수는 인덱스 페이지 크기와 키 값의 크기에 따라 결정된다.
• 기본 페이지 크기는 16KB, innodb_page_size 변수를 사용해 4KB ~ 64KB까지 설정 가능하다.
• 페이지 크기가 기본 크기인 16KB이고, 자식 노드의 주소 영역이 12바이트이면 하나의 인덱스 페이지에
  16KB / (16B + 12B) = 585
  585개 저장 가능하다. 최종적으로 자식 노드를 585개 가질 수 있는 B-Tree가 된다.
• 인덱스 값이 커지면 노드 수가 줄어들고, 한 페이지를 읽기 위해 2번 이상 디스크 읽기를 수행해야 할 수 있다. 이는 메모리에 캐시되는 레코드 수를 줄여 메모리 효율(캐시 히트율)이 떨어지는 결과를 가져온다.

B-Tree 깊이

직접 제어 불가능하다. 깊이가 3, 키 값이 16바이트인 경우 최대 2억(585 * 585 * 585)개

깊이는 MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다. 깊이 증가는 디스크 읽기를 의미한다. 인덱스 키 값 크기는 가능하면 작아야 하고, 깊이는 5 이상으로 깊어지는 경우는 흔치 않다.

Selectivity(선택도), Cardinality (기수성)

선택도(Selectivity)와 카디널리티(Cardinality)는 거의 같은 의미로 사용된다.

• 선택도 = ( 카디널리티 / 전체 레코드 수 ) * 100%

모든 인덱스 키 값 가운데 유니크한 값의 수를 의미.

전체 레코드 수가 10개, 그중 유니크한 값의 수가 3개이면 카디널리티가 3, 선택도가 30%이다.
(예: A, A, A, A, B, B, B, C, C, C → A, B, C)

• 중복 키가 적다 → 카디널리티가 높다
• 중복 키가 많다 → 카디널리티가 낮다

카디널리티가 높을수록 검색 대상이 줄어들기 때문에 빨리처리된다. 높을수록 좋다.

예)

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

• 예1)
  • tb의 전체 row가 10000개 이고,
  • country 컬럼의 카디널리티가 10이면
  • 해당 SELECT문은 country=’KOREA’에 의해 약 1000개의 값을 읽는다.
  • 그 중 city=’SEOUL’ 값이 1개라면 999개의 값을 불필요하게 읽는다.
• 예2)
  • tb의 전체 row가 10000개 이고,
  • country 컬럼의 카디널리티가 1000이면
  • 해당 SELECT문은 country=’KOREA’에 의해 약 10개의 값을 읽는다.
  • 그 중 city=’SEOUL’ 값이 1개라면 9개의 값을 불필요하게 읽는다.
• 예 2가 불필요한 READ를 덜 했기에 효율적이다.

단, 인덱스가 검색에만 사용되는 것이 아니므로, 여러 용도를 고려해 설계해야 한다. (예: 그루핑, 정렬)

읽어야 하는 레코드의 건수

인덱스를 통해 레코드를읽는 것은 테이블을 생으로 읽는 것보다 비싸다. (트리 탐색 비용 추가 필요)

약 4배이상 비용이 더 드는 것으로 예측하기에 인덱스를 통해 읽는 레코드 수가 전체의 20~25% 이상인 경우 테이블 풀스캔 후 필터링 방식으로 처리하는게 효율적이다. (옵티마이저가 해줄 가능성이 높다)