[Real MySQL 8.0 1] 08 인덱스 - 1. 디스크 읽기 방식 / 2. 인덱스란? / 3. B-Tree 인덱스

8.0 버전부터: MyISAM 스토리지 엔진에서만 제공하던 전문 검색 or 위치 기반 검색 기능도 모두 InnoDB에서 사용 O

But, MySQL 서버의 옵티마이저가 발전하고 성능이 개선돼도 관리자의 역할 중요

 

1. 디스크 읽기 방식

어떻게 디스크 I/O를 줄이느냐 -> 데이터베이스의 성능 튜닝

1) 하드 디스크 드라이브(HDD)와 솔리드 스테이트 드라이브(SDD)

컴퓨터에서 CPU or 메모리 같은 주요 장치는 대부분 전자식 장치

But, 하드 디스크 드라이브는 기계식 장치 -> 서버에서 항상 병목이 됨

=> 기계식 하드 디스크 드라이브 대체: 전자식 저장 매체인 SSD(Solid State Drive)

• 같은 인터페이스(SATA/SAS) 지원 -> 내장 디스크 DAS or SAN에 그대로 사용할 수 있음
• 기존 하드 디스크 드라이브에서 데이터 저장용 플래터(원판) 제거, 플래시 메모리 장착
  • 디스크 원판을 기계적으로 회전시킬 필요 X -> 아주 빨리 데이터 읽기/쓰기
• 전원 공급되지 않아도 데이터 삭제 X
• 속도: 컴퓨터의 메모리(D-RAM) > SSD > 기계식 하드 디스크 드라이브
  • CPU > DRAM > SSD > HDD

---

2) (Random)랜덤 I/O와 (Sequential)순차 I/O

랜덤 I/O: 하드 디스크 드라이브의 플래터(원판) 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더 이동시킨 다음 읽는 것

-> 순차 I/O도 작업 과정 같음

3개의 페이지(3*16KB)를 디스크에 기록 
순차 I/O: 1번 시스템 콜 요청 = 디스크에 기록해야 할 위치 찾기 -> 헤드 1번 움직임
랜덤 I/O: 3번 시스템 콜 요청 = 디스크에 기록해야 할 위치 찾기 -> 헤드 3번 움직임

디스크에 데이터 쓰기/읽기 걸리는 시간: 디스크 헤더 움직여서 읽고 쓸 위치로 옮기는 단계에서 결정
=> 순차 I/O는 랜덤 I/O보다 약 3배 빠름

 

디스크의 성능: 디스크 헤더의 위치 이동 X 얼마나 많은 데이터를 한 번에 기록하느냐
-> 여러 번 쓰기/읽기 요청하는 랜덤 I/O 작업 부하 ↑

 

데이터베이스 대부분의 작업은 작은 데이터를 빈번히 읽기/쓰기

-> 서버) 그룹 커밋 or 바이너리 로그 버퍼 or InnoDB 로그 버퍼 등 기능 내장

Q. 디스크 원판 가지지 않는 SSD는 랜덤 I/O와 순차 I/O 차이 X?
A. X
랜덤 I/O는 순차 I/O보다 전체 스루풋(Throughput) 떨어짐 => 성능 비교를 구분해서 명시해야 함

 

참고

• 파일에 쓰기 실행 -> 반드시 동기화(`fsync` or `flush` 작업) 필요
• 순차 I/O: 파일 동기화 작업 빈번히 발생 -> 랜덤 I/O와 같이 비효율적인 형태로 처리될 때 ↑
• 캐시 메모리가 장착된 RAID 컨트롤러 일반적으로 사용
  • 아주 빈번한 파일 동기화 작업이 호출되는 순차 I/O를 효율적으로 처리될 수 있게 변환하는 역할
  • 하드 디스크 드라이브뿐만 아니라 SSD를 사용하는 경우에도 RAID 컨트롤러 중요한 역할

 

쿼리 튜닝 -> (랜덤 I/O -> 순차 I/O) 실행할 방법 많지 X

=> 쿼리를 튜닝하는 것의 목적: 랜덤 I/O 자체를 줄여주는 것

쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것

 

참고

• 인덱스 레인지 스캔: 데이터를 읽기 위해 주로 랜덤 I/O를 사용
• 풀 테이블 스캔: 순차 I/O 사용

=> 큰 테이블의 레코드 대부분을 읽는 작업에서는 인덱스 사용 X, 풀 테이블 스캔 사용하도록 유도할 때도 있음

-> 순차 I/O > 랜덤 I/O 훨씬 빨리 많은 레코드 읽어오기 때문

OLTP(On-Line Transaction Processing) 성격의 웹 서비스보다 데이터 웨어하우스나 통계 작업에서 자주 사용

---

2. 인덱스란?

인덱스 - 책의 맨 끝에 있는 찾아보기(or 색인)
책의 내용 - 데이터 파일
책의 찾아보기 ~> 알아낼 수 있는 페이지 번호: 데이터 파일에 저장된 레코드의 주소

 

데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과 가져오려면 시간 ↑

-> 컬럼의 값과 해당 레코드가 저장된 주소 -> 키와 값의 쌍(key-Value pair)으로 삼아 인덱스 만들어 두는 것

컬럼의 값을 주어진 순서로 미리 정렬해서 보관

 

• SortedList: DBMS의 인덱스와 같은 자료 구조
  • 저장된 값을 항상 정렬된 상태로 유지
  • 데이터가 저장될 때마다 항상 값 정렬
    • 저장하는 과정 복잡, 느림 
    • 이미 정렬돼 있어 아주 빨리 원하는 값 찾아올 수 있음
• ArrayList: 데이터 파일과 같은 자료 구조 
  • 값을 저장되는 순서 그대로 유지하는 자료 구조

인덱스: 저장되는 컬럼의 값을 이용해 항상 정렬된 상태 유지(SortedList)

데이터 파일: 저장된 순서대로 별도의 정렬 없이 그대로 저장(ArrayList)

=> 데이터의 저장(INSERT, UPDATE, DELETE) 성능 희생 But, 데이터 읽기 속도 ↑

 

=> 테이블의 인덱스를 하나 더 추가할지 말지

-> 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하는지

---

구분

데이터를 관리하는 방식(알고리즘), 중복 값의 허용 여부 등 따라 여러 가지로 나눌 수 있음

 

역할별

• 프라이머리 키(Primary key): 레코드를 대표하는 컬럼의 값으로 만들어진 인덱스 의미
  • 컬럼(컬럼의 조합)은 테이블에서 해당 레코드를 식별할 수 있는 기준 값 => 식별자
  • NULL 허용 X, 중복 허용 X
• 보조 키(세컨더리 인덱스, Secondary key): 프라이머리 키를 제외한 나머지 모든 인덱스
  • 유니크 인덱스(대체 키): 프라이머리 키와 성격 비슷, 프라이머리 키를 대체해서 사용할 수 있음
    (별도로 분류 / 세컨더리 인덱스로 분류)

 

데이터 저장 방식(알고리즘)

• B-Tree 인덱스: 가장 일반적으로 사용되는 인덱스 알고리즘
  • 컬럼의 값 변형 X 원래의 값을 이용해 인덱싱하는 알골지므
  • R-Tree 알고리즘(MySQL 서버-위치 기반 검색 지원): B-Tree의 응용 알고리즘
• Hash 인덱스: 컬럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘, 매우 빠른 검색 지원
  • 값을 변형해서 인덱싱 -> 전방(Prefix) 일치와 같이 값의 일부만 검색 or 범위를 검색 -> 해시 인덱스 사용 X
  • 주로 메모리 기반의 데이터베이스에서 사용

 

데이터의 중복 허용 여부

• 유니크 인덱스(Unique) / 유니크하지 않은 인덱스(Non-Unique)
• 단순히 같은 값이 1개만 존재하는지 / 1개 이상 존재할 수 있는지
• 실제 DBMS의 쿼리를 실행해야 하는 옵티마이저에게 중요한 문제
  • (유니크 인덱스: 동등 조건(Equal, =)으로 검색 = 항상 1건의 레코드만 찾으면 더 찾지 않아도 됨) 알려주는 효과
  • 유니크 인덱스 -> MySQL의 처리 방식의 변화 or 차이점 ↑

 

인덱스의 기능별

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

---

3. B-Tree 인덱스

데이터베이스의 인덱싱 알고리즘 중 가장 일반적으로 사용(특수 요건(ex. 전문 검색) X), 가장 먼저 도입

But, 가장 범용적인 목적으로만 사용되는 인덱스 알고리즘

B: Binary(이진) (X) Balanced (O)

변형된 형태의 알고리즘: B+-Tree or B*-Tree

원래 값 변형 X (값의 앞부분만 자라서 관리) 인덱스 구조체 내에서 항상 정렬된 상태 유지

1) 구조 및 특성

• 최상위에 하나의 루트 노드(Root node) 존재, 하위에 자식 노드가 붙어 있는 형태
  • 리프 노드(Leaf node): 가장 하위에 있는 노드
  • 브랜치 노드(Branch node): 리프 노드 X 중간의 노드
• 인덱스와 실제 데이터 레코드는 따로 관리
  = 데이터의 위치만 저장하고 실제 내용은 별도의 저장소(데이터 파일)에 있음
  
  • 인덱스: 테이블의 키 컬럼 기준으로 생성
    
    • (키, 주소) 쌍 저장
      • 키: `WHERE` 절에서 자주 사용하는 컬럼 값
      • 주소: 그 키 값이 포함된 실제 레코드가 저장된 위치
  • 루트/브랜치 노드: 탐색용 -> 키 값만 저장 (주소 X)
  • 리프 노드: (키, 주소) 쌍 저장 / 실질적인 인덱스 데이터 저장소
    / 실제 값 저장 X 데이터 파일에 있는 레코드의 주소(포인터) 저장 
    • -> 나머지 컬럼 읽기 위해서는 리프 노드의 주소를 따라 데이터 파일로 이동해야 함

=> 데이터 조회: 인덱스 -> 리프 노드 -> 데이터 파일로 이동 -> 전체 레코드 접근

 

• 인덱스의 키 값: 정렬 O / 데이터 파일의 레코드: 정렬 X 임의의 순서로 저장
• 데이터 파일의 레코드 `INSERT` 순서대로 저장 (X)
  • IF. 테이블의 레코드 전혀 삭제 or 변경 X `INSERT`만 수행 -> (O)
  • 레코드 삭제 -> 빈 공간 => 그 다음 `INSERT` 가능한 삭제된 공간 재활용

 

참고

• 대부분 RDBMS의 데이터 파일에서 레코드: 특정 기준 정렬 X 임의의 순서로 저장
• InnoDB 테이블에서 레코드: 클러스터되어 디스크에 저장 -> (기본) 프라이머리 키 순서대로 정렬되어 저장
  • ex. 오라클의 IOT(Index organized table) or MS-SQL의 클러스터 테이블
  • 다른 DBMS: 클러스터링 기능이 선택 사항
    클러스터링: 비슷한 값을 최대한 모아서 저장하는 방식
  • InnoDB: 사용자가 별도의 명령 or 옵션 선택 X -> (default) 클러스터링 테이블 생성

 

레코드 주소: MyISAM 테이블의 생성 옵션에 따라 레코드가 테이블에 `INSERT`된 순번 or 데이터 파일 내의 위치(Offset)

(MyISAM 스토리 엔진에서 인덱스의 구조: 4.3.3절 데이터 파일과 프라이머리 키(인덱스) 구조의 ROWID)

InnoDB 스토리지 엔진을 사용하는 테이블: 프라이머리 키 -> ROWID 역할

 

=> 차이점: 세컨더리 인덱스 ~> 데이터 파일의 레코드를 찾아가는 방법

• MyISAM 테이블: 세컨더리 인덱스 -> 물리적인 주소
• InnoDB 테이블: 프라이머리 키 -> 주소처럼 사용 => 논리적인 주소 

=> InnoDB 테이블: 인덱스 ~> 레코드 읽을 때 데이터 파일 바로 찾아가지 X

인덱스에 저장된 프라이머리 키 값 -> 프라이머리 키 인덱스 검색 -> 프라이머리 키 인덱스의 리프 페이지에 저장된 레코드 읽음

=> 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree 다시 한번 검색해야 함

---

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

인덱스 키 추가

새로운 키 값이 B-Tree에 저장: 테이블의 스토리지 엔진 -> 새로운 키 값 즉시 인덱스에 저장 OX

 

저장될 키 값 -> B-Tree상의 적절한 위치를 검색 후 결정 -> (레코드의 키 값, 대상 레코드의 주소 정보) 리프 노드에 저장

IF. 리프 노드 꽉 차서 저장 X -> 리프 노드 분리(split) -> 상위 브랜치 노드까지 처리 범위 넓어짐

=> 상대적으로 쓰기 작업(새로운 키를 추가하는 작업)에 비용 ↑

 

Q. 인덱스 추가 -> `INSERT` or `UPDATE` 문장 어떤 영향?

-> 테이블의 컬럼 수, 컬럼의 크기, 인덱스 컬럼의 특성 등 확인해야 함

• 테이블에 레코드를 추가하는 작업 비용을 1이라고 가정
• 해당 테이블의 인덱스에 키를 추가하는 작업 비용을 1.5 정도로 예측

(테이블의 모든 인덱스가 B-Tree 가정) 일반적으로 테이블에 인덱스가 3개 

IF. 테이블에 인덱스 하나도 X -> 작업 비용 1 / IF. 인덱스 3개 -> 5.5(1.5 * 3 + 1) 

=> 비용의 대부분이 메모리, CPU에서 처리하는 시간 X 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 해서 걸리는 시간 O

 

인덱스 키 삭제

해당 키 값이 저장된 B-Tree의 리프 노드 찾아 삭제 마크

-> 삭제 마킹된 인덱스 키 공간: 그대로 방치 or 재활용 O

 

인데스 키 삭제로 인한 마킹 작업: 디스크 쓰기 필요 -> 디스크 I/O 필요한 작업

• 5.5 이상 버전 InnoDB의 스토리지 엔진) 버퍼링되어 지연 처리될 수 있음
  • 처리가 지연된 인덱스 키 삭제: 사용자 악영향 X MySQL 서버가 내부적으로 처리 
• MyISAM or MEMORY 스토리지 엔진의 테이블) 체인지 버퍼와 같은 기능 X -> 인덱스 키 삭제가 완료된 후 쿼리 실행 완료

 

인덱스 키 변경

인덱스 키 값: 값에 따라 저장될 리프 노드의 위치 결정

-> B-Tree 키 값 변경 시 인덱스 키 값만 변경 X

=> 기존 인덱스 키 값 삭제 -> 새로운 인덱스 키 값 추가

InnoDB 스토리지 엔진 사용 O 테이블) 체인지 버퍼 활용 -> 지연 처리될 수 있음

 

인덱스 키 검색

빠른 검색 -> `INSERT`, `UPDATE`, `DELETE` 작업할 때 인덱스 관리에 따르는 추가 비용 감당하면서 인덱스 구축

• 인덱스 검색 작업(트리 탐색): (B-Tree의 루트 노드 -> 브랜치 노드 -> 최종 리프 노드) 이동하면서 비교 작업 수행
• `SELETE`, `UPDATE`, `DELETE` 처리를 위해 항상 해당 레코드를 먼저 검색해야 할 경우에도 사용
  • 100% 일치 or 값 앞부분(Left-most part) 일치하는 경우에만 사용 O
  • 부등호("<, >") 비교 조건에서도 활용 O
  • 인덱스를 구성하는 키 값의 뒷부분만 검색하는 용도 X
  • 인덱스의 키 값 변형 후 비교 -> B-Tree의 빠른 검색 기능 사용 X
    • B-Tree 인덱스에 존재하는 값 X
      => 함수 or 연산을 수행한 결과 -> 정렬 or 검색할 때 B-Tree 장점 이용 X

 

 InnoDB 테이블에서 지원하는 레코드 잠금 or 넥스트 키락(갭락)이 검색을 수행한 인덱스 잠금 -> 테이블의 레코드 잠금

=> `UPDATE` or `DELETE` 문장 실행 시 테이블에 적절히 사용할 수 있는 인덱스 X

-> 불필요하게 많은 레코드 잠금 (모든 레코드 잠글 수 O)

=> InnoDB 스토리지 엔진에서 인덱스 설계 중요 (많은 부분에 영향 O)

---

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

인덱스를 구성하는 컬럼의 크기, 레코드 건수, 유니크한 인덱스 키 값의 개수 등에 의한 검색 or 변경 작업의 성능

 

인덱스 키 값의 크기

InnoDB 스토리지 엔진) 디스크에 데이터를 저장하는 가장 기본 단위: 페이지(Page) or 블록(Block)

-> 디스크의 모든 읽기/쓰기 작업의 최소 단위

버퍼 풀에서 데이터를 버퍼링하는 기본 단위

 

IF. DBMS의 B-Tree가 이진 트리 -> 인덱스 검색 비효율 

이진(Binary) 트리: 각 노드가 자식 노드 2개만 가짐

=> 자식 노드 개수 가변적 (인덱스의 페이지 크기, 키 값 -> 자식 노드 개수)

5.7 버전부터: `innodb_page_size` 시스템 변수 4KB ~ 64KB 사이의 값 선택 (기본 16KB)

 

인덱스 키 16바이트 + 자식 노드 주소 12바이트 (6 ~ 12바이트)

Q.  하나의 인덱스 페이지(16KB)에 몇 개의 키 저장?

A. 16*1024/(16+12) = 585개

=> 자식 노드를 585개 가질 수 있는 B-Tree

 

IF. 키 값 32바이트 -> 한 페이지에 인덱스 키를 16*1024/(32+12) = 372개 저장

=> 인덱스 구성하는 키 값 크기 ↑ -> 디스크로부터 읽어야 하는 횟수 ↑ => 느려짐

/ 인덱스 키 값 길어진다 = 전체 인덱스 크기가 커진다

 

But, 인덱스 캐시해 두는 InnoDB의 버퍼 풀 or MyISAM의 키 캐시 영역 크기 제한적

-> 하나의 레코드를 위한 인덱스 크기 ↑ -> 메모리에 캐시해 둘 수 있는 레코드 수 ↓ -> 메모리 효율 ↓

 

B-Tree 깊이

직접 제어할 방법 X 인덱스 키 값의 평균 크기 ↑ -> 발생하는 현상

ex. 인덱스의 B-Tree 깊이: 3 -> 최대 몇 개의 키 값?

키 값 16바이트 -> 최대 2억(585 *585 * 585)개 / 키 값 32 바이트 -> 5천만(372 * 372 * 372) 개

 

MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제

인덱스 키 값 크기 ↑ -> 인덱스 페이지가 담을 수 있는 인덱스의 키 값의 개수 ↓

=> 같은 레코드 건수여도 B-Tree 깊이(depth) 깊어져서 디스크  읽기 필요 ↑

 

선택도(기수성)

선택도(Selectivity) = 기수성(Cardinality): 모든 인덱스 키 값 가운데 유니크한 값의 수

ex. 전체 인덱스 키 값 100개, 유니크한 값 10개 -> 기수성 10

인덱스 키 값 중 중복된 값 ↑ -> 기수성 ↓, 선택도 ↓ (-> 검색 대상 ↑ => 느리게 처리)

 

`country`, `city` 포함된 tb_test 테이블/ 전체 레코드 건수 1만 건

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

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

MySQL) 인덱스의 통계 정보(유니크한 값의 개수) 관리 -> `city`의 기수성은 작업 범위에 영향 X

케이스 A: 평균 1,000건 / 케이스 B: 평균 10건 조회

IF. 두 케이스 모두 실제 모든 조건을 만족하는 레코드 단 1건 -> 케이스 A의 인덱스 적합 X (쓸모없는 999건 레코드 읽음)

 

각 국가의 도시 저장하는 tb_city 테이블

1만 건의 레코드 / `country`에만 인덱스 O / 국가, 도시 중복 저장 X

CREATE TABLE tb_city(
	country VARCHAR(10),
    city VARCHAR(10),
    INDEX ix_country (country)
);

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

• 케이스 A: 10개 국가의 도시 정보 저장
  • MySQL 서버) 인덱스된 `country`에 대해서는 전체 레코드의 건수 or 유니크한 값의 개수 등에 대한 통계 정보
  • 전체 레코드 건수 / 유니크한 값의 개수 = 하나의 키 값으로 검색했을 때 몇 건의 레코드 일치할지 예측
  • ex. `country=KOREA` 조건으로 인덱스 검색 -> 1,000건(10,000/10)이 일치
    • `city=SEOUL`인 레코드 1건 -> 999건 불필요하게 읽은 것 
• 케이스 B: 1,000개 국가의 도시 정보 저장
  • 전체 레코드 건수 / 유니크한 값의 개수 = 한 국가당 약 10개 정도의 도시 정보 저장
  • ex. `country=KOREA` 조건으로 인덱스 검색 -> 1,000건(10,000/1,000)이 일치
    • `city=SEOUL`인 레코드 1건 -> 9 불필요하게 읽은 것

=> 똑같은 쿼리 시행해 똑같은 결과 But, MySQL 서버가 수행한 작업 내용 ↑

-> 유니크한 값의 개수 -> 인덱스 or 쿼리의 효율성에 영향 ↑

 

읽어야 하는 레코드 건수

인덱스 ~> 테이블의 레코드를 읽는 것 > 인덱스 X 바로 테이블의 레코드 읽는 비용

 

ex. 테이블에 레코드 100만 건 저장, 그중 50만 건 읽어야 하는 쿼리

Q. 어느 것이 효율적? 인덱스 ~> 필요한 50만 건 읽어 오는 것 vs 전체 테이블 모두 읽어서 필요 X 50만 건 버리는 것 

 

일반적인 DBMS의 옵티마이저) 인덱스 비용 = 직접 레코드 1건 읽는 것 * 4~5배

=> 인덱스 ~> 읽어야 할 레코드 건수가 전체 테이블 레코드의 20~25% 이상 -> 인덱스 이용 X 필터링 방식 O

---

4) B-Tree 인덱스를 통한 데이터 읽기

인덱스 레인지 스캔

• 인덱스의 접근 방법 중 가장 대표적인 방식
• 인덱스 ~> 레코드 1건만 읽는 경우 / 1건 이상 읽는 경우
• 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식
  • 검색하려는 값의 수 or 검색 결과 레코드 건수 관계 X
• 필요한 레코드의 시작점: 루트 노드 -> 브랜치 노드 -> 리프 노드
  • 리프 노드의 레코드만 순서대로 읽으면 됨(스캔)
  • IF. 스캔 중 리프 노드의 끝까지 읽으면 리프 노드 간의 링크 -> 다음 리프 노드 찾아 다시 스캔
  • 최종적으로 스캔 멈춰야 할 위치 -> 지금까지 읽은 레코드 사용자에게 반환 후 쿼리 끝냄

 

SELECT * FROM employees WHERE first_name BETWEEN 'Ebbe' AND' 'Gad';

두꺼운 선: 스캔해야 할 위치 검색 위한 비교 작업 / 두꺼운 화살표 지나가는 리프노드 레코드 구간: 실제 스캔하는 범위

1. B-Tree 인덱스에서 루트, 브랜치 노드 -> 스캔 시작 위치 검색
2. 그 지점부터 필요한 방향(오름차순/내림차순)으로 인덱스를 읽어 나감

=> 어떤 방향으로 스캔 관계 X 해당 인덱스를 구성하는 컬럼의 정순/역순으로 정렬된 상태의 레코드 가져옴
(별도의 정렬 과정 수반 X 인덱스 자체의 정렬 특성 -> 자동)

인덱스의 리프 노드에서 검색 조건에 일치하는 건들 -> 데이터 파일에서 레코드를 읽어오는 과정이 필요
리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드 읽어옴
레코드 1건 단위로 랜덤 I/O 1번 씩 일어남
(그림 8.9) 레코드가 검색 조건에 일치 -> 데이터 레코드를 읽기 위해 랜덤 I/O 최대 3번 필요
=> 읽는 작업: 비용 ↑ / 인덱스 ~> 읽어야 할 데이터 20~25% 넘으면 테이블의 데이터 직접 읽는 것이 효율적

 

인덱스 스캔 3단계

1. 인덱스 탐색(Index seek): 인덱스에서 조건을 만족하는 값이 저장된 위치 찾음 
2. 인덱스 스캔(Index scan): 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 읽음
   (1, 2번 합쳐서 인덱스 스캔으로 통치하기 도 함)
3. 2번에서 읽어 들인 인덱스 키, 레코드 주소 -> 레코드가 저장된 페이지 가져옴, 최종 레코드 읽어옴
   
   • 커버링 인덱스, 쿼리가 필요로 하는 데이터에 따라 3번 과정 필요 없을 수 O
   • 디스크의 레코드 읽지 않아도 됨 -> 랜덤 읽기 ↓ 성능 ↑

=> 1, 2번 단계의 작업이 얼마나 수행됐는지 확인할 수 있는 상태 값

SHOW STATUS LIKE 'Handler_%';

읽은 레코드의 건수: 실제 인덱스만 읽었는지 or 인덱스 ~> 테이블의 레코드 읽었는지(3번 단계) 구분 X

• `Handler_read_key`: 1번이 실행된 횟수
• 2번으로 읽은 레코드 건수
  • `Handler_read_next`: 인덱스 정순으로 읽은 레코드 건수
  • `Handler_read_prev`: 인덱스 역순으로 읽은 레코드 건수
• `Handler_read_first`, `Handler_read_last`: 인덱스의 첫 번째 레코드, 마지막 레코드 읽은 횟수
  • `MIN()` or `MAX()`와 같이 제일 작은 값 or 제일 큰 값만 읽는 경우 증가하는 상태 값
  • 읽은 레코드 건수 의미/ 실제 인덱스 읽었는지 or 인덱스 ~> 테이블의 레코드 읽었는지(3번) 구분 X

 

인덱스 풀 스캔

• 인덱스의 처음~끝 모두 읽는 방식
• 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼 X인 경우 사용
  • ex. 인덱스 (A, B, C) 칼럼의 순서/ 쿼리의 조건절 B or C 칼럼으로 검색
• 쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있는 경우 사용
• 인데스 크기 < 테이블 크기 => 테이블 처음~끝 읽는 것보다 인덱스만 읽는 것이 효율적

인덱스 리프 노드의 제일 앞/뒤로 이동 -> 링크드 리스트 따라 처음부터 끝까지 스캔
(Linked list: 리프 노드 사이 연결하는 세로로 그려진 두 쌍의 화살표)

 

루스 인덱스 스캔

• 다른 DBMS(ex. 오라클): 인덱스 스킵 스캔
• MySQL: 루스(Loose) 인덱스 스캔
  • 느슨하게 or 듬성듬성하게 인덱스를 읽는 것
    • 중간에 필요 X 인덱스 키 값 무시(SKIP)하고 다음으로 넘어가는 형태로 처리
    • `GROUP BY` or  집합 함수(`MAX()` or `MIN()`) 최적화하는 경우
  • vs 타이트(Tight) 인덱스 스캔: 인덱스 레인지 스캔 / 인덱스 풀 스캔

 

`(dept_no, emp_no)`로 인덱스 생성 및 정렬

SELECT dept_no MIN(emp_no)
FROM dept_emp
WEHRE dept_no BETWEEN 'd002' AND 'd004'
GROUP BY dept_no;

`dept_no` 그룹별로 첫 번째 레코드의 `emp_no` 값만 읽으면 됨

=> 옵티마이저) 인덱스에서 `WHERE` 조건을 만족하는 범위 전체를 다시 스캔할 필요 X 

-> 조건 만족 X 레코드 무시 후 다음 레코드로 이동

 

인덱스 스킵 스캔

인덱스는 값이 정렬 돼 있음 -> 인덱스를 구성하는 칼럼의 순서 중요

 

ex. employees 테이블에 인덱스 생성

ALTER TABLE employees
ADD INDEX ix_gender_birthdate (gender, birth_date);

 

인덱스 사용하려면 `WHERE` 조건절에 `gender`에 대한 비교 필수

-- // 인덱스 사용 못하는 쿼리
SELECT * FROM employees WEHRE birth_date>='1965-02-01';

-- // 인덱스 사용할 수 있는 쿼리
SELECT * FROM employees WHERE gender='M' AND birth_date>='1965-02-01';

• 인덱스 사용 X: `gender`에 대한 비교 조건 X 쿼리
  • `birth_date`부터 시작하는 인덱스를 새로 생성해야만 함
• 인덱스 사용 O: `gender`, `birth_date` 조건 모두 가진 쿼리

 

8.0 버전부터: 옵티마이저) 인덱스 스킵 스캔(Index skip scan) 최적화 기능 도입/ `WHERE` 조건절 검색 위해 사용 O

-> `gender` 건너뛰고 `birth_date`만으로 인덱스 검색 가능하게 해줌

~= 루스 인덱스 스캔(Loose index scan): `GROUP BY` 처리하기 위해 인덱스 사용하는 경우에만 적용

 

인덱스 스킵 스캔 비활성화 (-> 8.0 이전 버전 실행 계획 확인)

SET optimizer_switch='skip_scan=off';

EXPLAIN
SELECT gender, birth_date
FROM employees
WEHRE birth_date>='1965-92-01';

• `WHERE` 조건절에 `gender`에 대한 조건 X `birth_date` 비교 조건만 O
  -> `ix_gender_birthdate` 인덱스 효율적으로 이용 X
• `type`: index -> 풀 인덱스 스캔(인덱스 처음~끝 모두 읽음)

 

인덱스 스킵 스캔 활성화

SET optimizer_switch='skip_scan=on';

EXPLAIN
SELECT gender, birth_date
FROM employees
WEHRE birth_date>='1965-92-01';

• `type`: range -> 인덱스에서 꼭 필요한 부분만 읽음
• `Extra`: Using index for skip scan -> `ix_gender_birthdate` 인덱스에 대해 인덱스 스킵 스캔 활용해 데이터 조회
  • MySQL 옵티마이저) `gender` 칼럼에서 유니크한 값 모두 조회해서 주어진 쿼리에 `gender` 조건 추가해서 쿼리 다시 실행

 

 

옵티마이저) 내부적으로 아래 2개 쿼리 실행하는 것과 비슷한 형태의 최적화 실행

SELECT gender birth_date FROM employees WHERE gender='M' AND birth_date>='1965-02-01';
SELECT gender birth_date FROM employees WHERE gender='F' AND birth_date>='1965-02-01';

 

단점

① `WEHRE` 조건절에 조건 X 인덱스의 선행 칼럼의 유니크한 값의 개수 적어야 함

• 쿼리 실행 계획의 비용과 관련
• IF. 유니크한 값의 개수 매우 ↑ -> MySQL 옵티마이저) 인덱스에서 스캔해야 할 시작 지점 검색하는 작업 ↑ => 처리 성능 ↓
• ex. `(emp_no, dept_no)` 조합으로 만들어진 인덱스에서 스킵 스캔 실행
  • 사원의 수만큼 레인지 스캔 시작 지점 검색하는 작업 필요 => 쿼리 성능 ↓

② 쿼리가 인덱스에 존재하는 칼럼만으로 처리 가능해야 함 (커버링 인덱스)

ex. `WHERE` 조건절 동일 But, `SELECT` 절에서 employees 테이블의 모든 칼럼 조회하도록 변경

EXPLAIN
SELECT * 
FROM employees
WEHRE birth_date>='1965-02-01';

`ix_gender_birthdate` 인덱스에 포함된 `gender`, `birth_date` 외의 나머지 칼럼 필요

-> 인덱스 스킵 스캔 사용 X 풀 테이블 스캔으로 실행 계획 수립

(MySQL 서버의 옵티마이저 개선 시 해결 가능)

---

5) 다중 칼럼(Multi-column) 인덱스

다중 칼럼 인덱스 = 복합 칼럼 인덱스 = Concatenated Index

• 인덱스 내에서 각 칼럼의 위치(순서) 중요
• 인덱스의 첫 번째 칼럼에 의존 -> 두 번째 칼럼 정렬
  = 첫 번째 칼럼이 똑같은 레코드에서만 두 번째 칼람의 정렬 의미 O

ex. `emp_no` 값의 정렬 순서가 빨라도 `dept_no`의 정렬 순서 늦으면 인덱스 뒤쪽 위치
-> `emp_no`값이 10003인 레코드가 인덱스 리프 노드의 하단에 위치

---

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

인덱스의 정렬

• 5.7 버전까지: 칼럼 단위로 정렬 순서 혼합해서 인덱스 생성 X -> -1 곱한 값 저장하는 방법(우회) 사용
• 8.0 버전부터: 정렬 순서 혼합한 인덱스 생성 O

CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC);

 

인덱스 스캔 방향

`first_name`에 대한 인덱스가 포함된 employees 테이블

SELECT * FROM employees ORDER BY first_name DESC LIMIT 1;

Q. 쿼리 실행하기 위해 인덱스 처음~끝 오름차순으로 읽어 `first_name`이 가장 큰(가장 마지막 레코드) 값 하나 가져옴?

A. X
옵티마이저) 최솟값부터 읽으면 오름차순으로 값 가져옴 / 최댓값부터 거꾸로 읽으면 내림차순으로 값 가져옴

=> 인덱스 역순으로 접근해 첫 번째 레코드만 읽음

 

인덱스 생성 시점에 오름차순/내림차순으로 정렬 결정 

But, 쿼리가 인덱스 사용하는 시점에 인덱스 읽는 방향에 따라 오름차순/내림차순 정렬 효과 O

오름차순으로 정렬된 인덱스 -> 정순으로 읽으면 오름차순 / 역순으로 읽으면 내림차순

SELECT * FROM employees WHERE first_name >= 'Aneeke' 
ORDER BY first_name ASC LIMIT 4;

SELECT * FROM employees 
ORDER BY first_name DESC LIMIT 5;

• `first_name`에 정의된 인덱스 이용해 Anneke 레코드 찾음
  -> 정순으로 해당 인덱스 읽으며 4개의 레코드만 가져오면 비용 X 정렬 효과 O
• `first_name`에 정의된 인덱스 역순으로 읽으면서 처음 5개만 가져오면 됨

 

`ORDER BY` or `MIN()`/`MAX()` 함수 등의 최적화 필요한 경우에도 인덱스 읽기 방향 전환해서 사용 O

 

내림차순 인덱스 

실제 내림차순/오름차순 관계 X 인덱스 읽는 순서만 변경해서 해결

SELECT * FROM employees ORDER BY first_name ASC LIMIT 10;
SELECT * FROM employees ORDER BY first_name DESC LIMIT 10;

CREATE INDEX ix_firstname_asc ON employees (first_name ASC);
CREATE INDEX ix_firstname_desc ON employees (first_name DESC);

 

• 오름차순 인덱스(Ascending index): 작은 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
• 내림차순 인덱스(Descending index): 큰 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
• 인덱스 정순 스캔(Forward index scan): 인덱스 키의 크고 작음 관계 X 인덱스 리프 노드의 왼쪽 -> 오른쪽 페이지로 스캔
• 인덱스 역순 스캔(Backward index scan): 인덱스 키의 크고 작음 관계 X 인덱스 리프 노드의 오른쪽 -> 왼쪽 페이지로 스캔

 

내림차순 인덱스의 필요성

CREATE TALBE t1 (
	tid INT NOT NULL AUTO_INCREMENT,
    TABLE_NAME VARCHAR(64),
    COLUMN_NAME VARCHAR(64),
    ORDINAL_POSITION INT,
    PRIMARY KEY(tid)
) ENGINE=InnoDB;

INSERT INTO t1
SELECT NULL, TABLE_NAME, COLUMN_NAME, ORDINAL_POSITION
FROM information_schema.COLUMNS;

INSERT INTO t1
SELECT NULL, TABLE_NAME, COLUMN_NAME, ORDINAL_POSITION
FOROM t1;

SELET COUNT(*) FROM t1;

 

테이블의 프라이머리 키 정순/역순 스캔하면서 마지막 레코드 1건 반환 (`tid` 값 가장 큰/작은 레코드)

But, 실제 MySQL 서버) `LIMIT ... OFFSET ...` 부분 쿼리 -> 테이블의 모든 레코드 스캔

SELECT * FROM t1 ORDER BY tid ASC LIMIT 12619775,1;

SELECT * FROM t1 ORDER BY tid DESC LIMIT 12619775,1;

 

내부적으로 InnoDB에서 인덱스 역순 스캔이 느린 이유

• 페이지 잠금이 인덱스 정순 스캔(forward index scan)에 적합한 구조
• 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조

 

일반적으로 `ORDER BY ... DESC` 쿼리가 소량의 레코드에 드물게 실행되는 경우 -> 내림차순 인덱스 굳이 고려 X

SELECT * FROM tab
WEHRE userid=?
ORDER BY score DESC
LIMIT 10;

• 오름차순 인덱스: `INDEX (userid ASC, score ASC)`
• 내림차순 인덱스: `INDEX (userid DESC, score DESC)`

쿼리가 많은 레코드를 조회하면서 빈번하게 실행 -> 내림차순 인덱스가 효율적

인덱스의 앞/뒤쪽만 집중적으로 읽어서 인덱스의 특정 페이지 잠금이 병목 될 것으로 예상

-> 쿼리에서 자주 사용되는 정렬 순서대로 인덱스 생성 => 병목 현상 완화

---

7) B-Tree 인덱스의 가용성과 효율성

쿼리의 `WEHRE`, `GROUP BY`, `ORDER BY`: 어떤 경우에 인덱스 사용, 어떤 방식으로 사용할 수 잇는지 식별할 수 있어야 함

-> 쿼리 조적 최적화 or 쿼리에 맞게 인덱스 최적으로 생성

 

비교 조건의 종류와 효율성

SELECT * FROM dept_emp
WHERE dept_no='d002' AND emp_no >= 10114;

• 케이스 A: `INDEX(dept_no, emp_no)`
• 케이스 B: `INDEX(emp_no, dept_no)`

 

인덱스의 가용성

B-Tree 인덱스 특징: 왼쪽 값에 기준해서(Left-most) 오른쪽 값이 정렬돼 있음

-> 하나의 칼럼 + 다중 칼럼 인덱스의 칼럼 모두 적용

 

• 케이스 A: `INDEX(dept_no, emp_no)`
• 케이스 B: `INDEX(emp_no, dept_no)`

값의 왼쪽 부분 X or 왼쪽 칼럼의 값 모름 -> 인덱스 레인지 스캔 방식의 검색 X

 

케이스 A의 인덱스가 지정된 employees 테이블

SELECT * FROM employees WHERE first_name LIKE '%mer';

인덱스 레인지 스캔 방식으로 인덱스 이용 X

`first_name` 에 저장된 값의 왼쪽부터 한 글자씩 비교해 가면서 일치하는 레코드를 찾아야 함

-> 조건절에 주어진 상숫값('%mer')에는 왼쪽 부분이 고정 X

=> 정렬 우선순위가 낮은 뒷부분의 값만으로는 왼쪽 기준(Left-most) 정렬 기반의 인덱스인 B-tree에서는 인덱스 효과 X

 

케이스 B의 인덱스가 지정된 dept_emp 테이블

SELECT * FROM dept_emp WHERE emp_no >= 10144;

인덱스가 `(dept_no, emp_no)` 칼럼 순서대로 생성 O

-> 인덱스의 선행 `dept_no` 조건 X `emp_no` 값으로만 검색하면 인덱스 효율적으로 사용 X

=> 케이스 B의 인덱스는 다중 칼럼으로 구성된 인덱스 -> (`dept_no` 대해 정렬 -> 다시 `emp_no`값으로 정렬)

 

가용성과 효율성 판단

• NOT-EQUAL로 비교된 경우
  • `.. WHERE column <> 'N'`
  • `.. WHERE column NOT IN (10,11,12)`
  • `.. WHERE column IS NOT NULL`
• LIKE'%??'(앞부분이 아닌 뒷부분 일치) 형태로 문자열 패턴이 비교된 경우
  •  `.. WHERE column LIKE '%승환'`
  •  `.. WHERE column LIKE '_승환'`
  •  `.. WHERE column LIKE '%승%'`
• 스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우
  •  `.. WHERE SUBSTRING(column, 1, 1) = 'X'`
  •  `.. WHERE DAYOFMONTH(column) = 1`
• NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우
  •  `.. WHERE column = deterministic_function()`
• 데이터 타입이 서로 다른 비교(인덱스 칼럼의 타입을 변환해야 비교가 가능한 경우)
  • `WHERE char_column = 10`
• 문자열 데이터 타입의 콜레이션이 다른 경우
  • `.. WHERE utf8_bin_char_column = euckr_bin_char_column`

 

일반적인 DBMS) `NULL` 값이 인덱스에 저장 X / MySQL) `NULL` 값도 인덱스에 저장 O

.. WHERE column IS NULL ..

 

INDEX ix_test ( column_1, column_2, column_3, ..., column_n)

• 작업 범위 결정 조건으로 인덱스 사용 X
  • `column_1` 대한 조건 X
  • `column_1` 비교 조건이 위의 인덱스 사용 불가 조건 중 하나인 경우
• 작업 범위 결정 조건으로 인덱스 사용 O (2 < i < n)
  •  `column_1 ~ column(i-1)`까지 동등 비교 형태("=" or "IN")로 비교
  • `column_i` 다음 연산자 중 하나로 비교
    • 동등 비교("=" or "IN")
    • 크다 작다 형태(">" or "<")
    • `LIKE`로 좌측 일치 패턴(`LIKE '승황%')

-- // 다음 쿼리는 인덱스 사용 X
.. WHERE column_1 <> 2

-- // column_1, 2까지 범위 결정 조건으로 사용
.. WHERE column_1 = 1 AND column_2 > 10

-- // column_1, 2, 3까지 범위 결정 조건으로 사용
.. WHERE column_1 IN (1, 2) AND column_2 = 2 AND column_3 <= 10

-- // column_1, 2, 3까지 범위 결정 조건, column_4는 체크 조건으로 사용
.. WHERE column_1 = 1 AND column_2 = 2 AND column_3 IN (10,20,30) AND column_4 <> 100

-- // column_1, 2, 3, 4까지 범위 결정 조건
-- // 좌측 패턴 일치 LIKE 비교: 크다 or 작다 비교와 동급
.. WHERE column_1 = 1 AND column_2 IN (2,4) AND column_3 = 30 AND column_4 LIKE '김승%'

-- // 쿼리 column_1 ~ 5까지 모두 범위 결정 조건으로 사용됨
.. WHERE column_1 = 1 AND column_2 = 2 AND column_3 = 30
	AND column_4 = '김승환' AND column_5 = '서울'

---

출처

GitHub - wikibook/realmysql80: 《Real MySQL 8.0》 예제 파일