8장 인덱스

8.1 디스크 읽기 방식

• 데이터베이스 성능 튜닝은 디스크 I/O를 줄이는게 관건

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

• HDD(DB 서버 병목 초래) 대체를 위한 SSD
• HDD와 같은 인터페이스(SATA, SAS) 지원 → 내장디스크, DAS, SAN에 사용 가능
  • 참고: https://cheershennah.tistory.com/168
• SSD는 랜덤 I/O 작업이 HDD보다 훨씬 빠르기 때문에 DBMS용 스토리지에 좋음

8.1.2 랜덤 I/O와 순차 I/O

• 랜덤 I/O: HDD 플래터를 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것
  • 순차 I/O와 다르게 페이지 당 시스템 콜 요청
  • 부하가 큼 → MySQL 서버에는 그룹커밋, 바이너리 로그 버퍼, InnoDB 로그 버퍼 등 기능 내장
  • 실제는 RAID 컨트롤러 캐시 메모리가 효율적 I/O 처리 도움
    • https://12bme.tistory.com/286
• 쿼리 튜닝으로 랜덤 I/O → 순차 I/O 하기는 쉽지 않음, 일반적으로 쿼리 튜닝하는 것은 랜덤 I/O 자체를 줄여주는 것이 목적(쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선)

8.2 인덱스란?

• 찾아보기: 인덱스 / 책 내용: 데이터 파일
• 인덱스를 통해 데이터 파일에 저장된 레코드 주소를 알아낼 수 있음
  • 칼럼 값(key) - 레코드 저장된 주소(value)로 인덱스 만들기
• 책처럼 DBMS의 인덱스도 컬럼 값을 미리 정렬해서 보관
• SortedList: 저장되는 값을 항상 정렬된 상태로 유지하는 자료구조 - 인덱스
  • 데이터가 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리지만, 이미 정렬돼 있어서 아주 빨리 원하는 값을 찾아올 수 있음 → SELECT는 빠르지만 인덱스가 많은 테이블은 INSERT나 UPDATE 그리고 DELETE 문장의 처리가 느려짐
  • SELECT WHERE 조건절에 사용된다고 다 인덱스 걸면 저장 성능 망함
• ArrayList: 값을 저장되는 순서대로 그대로 유지하는 자료구조 - 데이터 파일
• Primary Key: 레코드를 대표하는 컬럼 값으로 만들어진 인덱스
• Secondary key: primary 제외한 모든 인덱스
• B-Tree 알고리즘: 가장 많이씀, 컬럼의 값을 변형하지 않고, 원래의 값을 이용해 인덱싱하는 알고리즘
• Hash 인덱스 알고리즘: 컬럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘, 매우 빠른 검색을 지원, 값을 변형해서 인덱싱하므로, 전방(Prefix) 일치와 같이 값의 일부만 검색하고자 할 때는 해시 인덱스를 사용할 수 없음, 메모리 기반 DB에서 많이 사용
• Unique: 레코드 1건 찾으면 더 안 찾아도 되는 걸 옵티마이저에게 알려줌

8.3 B-Tree 인덱스

• 일반적으로 DBMS에서는 주로 B+-Tree 또는 B*-Tree 사용
  • B(Balanced)
• 컬럼의 원래 값을 변형시키지 않고, 인덱스 구조체 내에서는 항상 정렬된 상태로 유지

8.3.1 구조 및 특성

• root node + branch node + leaf node
• leaf node: 실제 데이터 레코드를 찾아가기 위한 주솟값 보유
• 인덱스의 키값은 정렬돼 있지만 데이터 파일의 레코드는 임의의 순서대로 저장
  • 레코드가 중간에 삭제되어 빈 공간이 생기면 다음 INSERT는 빈 공간 활용하기 때문에 데이터 파일의 레코드 != INSERT된 순서임
  • InnoDB 레코드는 클러스터되어 디스크에 저장되기 때문에 PK 순서로 저장됨
    • https://dev.mysql.com/doc/refman/5.7/en/innodb-index-types.html
    • 다른 db는 선택인데 이노 친구는 디폴트로 클러스터링 테이블 생성함
• 인덱스는 테이블의 키 컬럼만 가지고 있으므로 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 함 → 리프 노드가 데이터 파일에 저장된 레코드의 주소 갖는 이유
• 8.5(MyISAM): PK값과 무관하게 insert 순서대로 레코드가 데이터 파일에 저장 → ROWID라는 물리적 주솟값 가짐 → 인덱스가 데이터 파일에 저장된 레코드의 ROWID 값을 포인터로 가짐 (ROWID=secondary index)
• 8.6(InnoDB): PK=ROWID 역할=논리적 주소 → 인덱스에 저장된 PK(11800)로 프라이머리 키 루트노드 인덱스 키에 맵핑된 자식노드 주소를 타고타고 가 리프 노드에 있는 레코드를 읽는다.
  • secondary index(Aamer)가 PK(11800)를 바라보고 있음
  • PK 저장하고 있는 B-Tree 다시 위에서부터 보면서 11800번 찾음
    • 1번 시나리오
      • 11800어딨을까~
      • 11043? 나 너보다 큰데~ 브랜치 노드로 감
      • 11800? 오~ 찾음~ 레코드로 감
    • 2번 시나리오
      • 10128 어딨을까~
      • 루트노드 봤더니 없네~ 10057 보단 큰데 11043보다는 작네~
      • 또 10057이네~ 내가 이것보단 큰데~ 10418보다는 작네~
      • 오 리프노드 10128 드디어있네~
  • 즉 Inno에서는 PK 검색 아니면 PK B-Tree 인덱스 다시 타줘야 한다.
  • http://www.btechsmartclass.com/data_structures/b-trees.html

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

8.3.2.1 인덱스 키 추가

• 바로 저장 → B-Tree상의 적절한 위치를 검색
• 저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장
• 리프노드 꽉차면 분리해야되는데 비용 많이 든다 → B-Tree 쓰기 작업 비용 많이 드는 이유
  • 비용 계산? 대충 레코드 추가:인덱스에 키 추가=1:1.5
  • 요 작업 MyISAM/Memory 스토리지 엔진은 INSERT와 동시에 하는데, InnoDB는 똑똑해서 지연시킬 수 있음(PK, UK는 중복체크해야해서 즉시 반영)

8.3.2.2 인덱스 키 삭제

• 키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 표시
• 요것도 InnoDB는 체인지 버퍼로 지연 처리 가능

8.3.2.3 인덱스 키 변경

• Balanced Tree라 했지? → 변경하고 싶으면 바꿔치기 안되고 키 값 삭제한 후 새로 추가해야함(키 값으로 리프노드 위치 발란싱하니까)
• 요것도 InnoDB는 체인지 버퍼로 지연 처리 가능

8.3.2.4 인덱스 키 검색

• 인덱스 검색 = 빠른 검색을 위함 = 트리 탐색이라고 함
• SELECT에서만 사용하는 것이 아니라 UPDATE, DELETE 처리하기 위해 레코드를 먼저 검색해야 할 경우에도 사용
• B-Tree 인덱스는 100% 일치 또는 값의 앞부분만 일치하는 경우에만 사용 가능
• 인덱스 키 값 변형된 이후 비교하면 빠른 검색 사용 불가 (B-Tree에 변한건 없으니까 당연)
• InnoDB 테이블에서 지원하는 레코드 잠금 & 넥스트 키 락(갭 락) → 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그기 때문에 불필요하게 많은 레코드가 잠길 수 있음

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

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

8.3.3.1 인덱스 키 값의 크기

• 페이지/블록: InnoDB 스토리지 엔진에서 디스크에 데이터를 저장하는 가장 기본 단위
  • 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 함
  • 루트/브랜치/리프 노드 애들도 결국 다 페이지임
• B-Tree 자식노드 수는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정
  • 페이지 당 저장할 수 있는 인덱스 키 수만큼 레코드 가져올 수 있음
  • 키 값의 크기가 커지면 디스크로부터 여러번 읽어야하고 느려짐

8.3.3.2 B-Tree 깊이

• 인덱스 키 값이 증가 → 페이지에 당 인덱스 키 수 감소 → b-tree 깊이 증가 → 디스크 읽기 횟수 증가

8.3.3.3 선택도(기수성)

• Cardinality = the number of cardinal (basic) members in a set
• Selectivity = Cardinality / Total Number Of Records
• 인덱스의 유니크한 값의 수 → 인덱스나 쿼리의 성능을 결정(교재 country index 예시 참고)

8.3.3.4 읽어야하는 레코드의 건수

• 손익분기점 잘 판단해야
  • 전체 테이블의 모두 읽어서 필요 없는 50만 건을 버리는 것이 효율적일지, 인덱스를 통해 필요한 50건만 읽어 오는 것이 효율적인지 판단
  • (DBMS 옵티마이저 왈) 인덱스 1건 = 직접 * 4~5
  • 인덱스 타는 레코드 수가 전체의 20~25% 넘으면 직접 가져와서 필터링하는게 더 효율적

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

8.3.4.1 인덱스 레인지 스캔

• 제일 빠름
• 검색해야할 인덱스의 범위가 결정됐을 때 사용하는 방식
• 시작 위치(인덱스 탐색) 찾은 후 리프노드 간 링크를 통해 다음 리프노드를 찾아 스캔(인덱스 스캔)
• 최종 범위(Gad)에 다다르면 멈추고 결과 반환
• 어떤 방식으로 스캔하든 관계 없이, 해당 인덱스를 수정하는 칼럼의 정순 또는 역순으로 정렬된 상태로 레코드를 가져옴
• 인덱스의 리프 노드에서 검색 조건에 맞는 것들을 데이터 파일에서 레코드를 읽어오는 과정이 필요
  • 데이터 레코드 당 랜덤 I/O 한 번씩 발생
  • 커버링 인덱스(쿼리를 충족하는데 필요한 모든 데이터를 갖는 인덱스) 사용 시 디스크 레코드 안 읽어도 된다.
    • https://tecoble.techcourse.co.kr/post/2021-10-12-covering-index/

8.3.4.2 인덱스 풀 스캔

• 인덱스의 처음부터 끝까지 모두 읽는 방식
• 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 발생
  • 인덱스는 (A,B,C) 칼럼의 순서대로 만들어져 있지만 쿼리의 조건절에 B 칼럼이나 C 칼럼으로 검색하는 경우
• 과정
  • 인덱스 리프 노드의 처음 또는 끝으로 이동한 후 리프노드를 연결하는 LinkedList 탐색(인덱스 레인지 스캔보단 느리지만 테이블 풀스캔보단 빠름)

8.3.4.3 루스 인덱스 스캔

• 느슨하게 또는 듬성듬성 하게 인덱스를 읽는 것
• 인덱스 레인지 스캔과 비슷하게 동작하지만, 중간마다 필요치 않은 인덱스 키 값은 스킵
• GROUP BY 또는 집합 함수 가운데 MAX(), MIN() 함수에 대해 최적화에 사용

8.3.4.4 인덱스 스킵 스캔

• MySQL 8.0부터 옵티마이저가 인덱스 두번째 칼럼으로도 인덱스 타게 해줌
• 이게 바로 인덱스 스킵 스캔
• 이전에는 두 번째 칼럼만 where 조건 걸면 인덱스 풀스캔했음(type=index)
• EXPLAIN 찍어보면 지금은 type=range + Extra에 스킵 스캔 나옴
• 제약 사항
  • where 조건절에 안 써준 인덱스 앞에 걸린 컬럼의 유니크한 수가 적어야 함
  • 커버링 인덱스여야함(인덱스 존재하는 컬럼만으로 쿼리 완성)

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

• 두 개 이상의 칼럼으로 구성된 인덱스
• 두번째 컬럼은 첫 번째 칼럼에 의존해서 정렬
• 따라서 인덱스 내 컬럼 위치가 중요

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

• 인덱스를 어느 방향으로 읽을지는 쿼리에 따라서 옵티마이저가 실시간으로 만들어내는 실행 계획에 따라 결정

8.3.6.1 인덱스의 정렬

• MySQL 8.0부터 혼합 정렬 인덱스 사용 가능

8.3.6.1.1 인덱스 스캔 방향

• 옵티마이저가 똑똑해서 인덱스 걸어둔 컬럼에 대해서 정렬하면 가까운 곳에서부터 정순/역순 스캔함

8.3.6.1.2 내림차순 인덱스

• 복합인덱스에서 내림/올림 혼합되면 8.0이 지원하는 내림차순 인덱스만 사용 가능

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

• 만약 한 컬럼을 역순으로 정렬해야하는데 하나는 인덱스 오름차순으로 생성/나머지는 내림차순으로 생성한다면?

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

• 12619775번부터 1건 반환해야하는데 역순 정렬 쿼리가 정순 정렬 쿼리보다 28.9% 시간이 더 걸림
• 왜? InnoDB 엔진에서 페이지 잠금이 forward index scan에 더 적합한 구조를 가져서
• 페이지 내부 레코드가 단방향 링크만 가진다. (페이지 간은 doubly인데 안에가 single linked list임)
  • 물리적으로 정렬된게 아니라 페이지 구조가 Heap처럼 연결되어 있는것

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

8.3.7.1 비교 조건의 종류와 효율성

• 다중 컬럼 인덱스에서 각 컬럼의 순서 & 컬럼에 사용된 조건에 따라 인덱스 컬럼 활용 형태가 달라짐

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

• INDEX (dept_no, emp_no)
  • dept_no가 d002고 emp_no가 10144 이상인 레코드를 찾은 후 그 d002 끝까지 읽으면 된다.
  • dept_no='d002' AND emp_no >=10144: 작업 범위 결정 조건
• INDEX (emp_no, dept_no)
  • emp_no가 10144인 레코드를 찾은 후 dept_no 적합성을 전부 검증해줘야 한다. (필터링)
  • 다중컬럼인덱스 정렬방식 때문(N번째 키값은 N-1번째 키 값에 의해 다시 정렬됨
  • dept_no='d002': 필터링 조건(체크 조건), emp_no: 작업 범위 결정 조건
  • 작업범위 결정 조건은 많을수록 성능에 유리하지만 체크 조건은 많아도 쿼리 성능을 높이지 못함

8.3.7.2 인덱스의 가용성

• B-Tree 인덱스는 왼쪽값 기준으로 오른쪽값이 정렬됨
• 왼쪽 키 값이 없으면 인덱스 레인지 스캔이 불가

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

• LIKE 쿼리 왼쪽부분이 고정되지 않았기 때문에 B-tree 인덱스 효과 X

SELECT * FROM dept_emp WHERE emp_no>=10144;

• dept_no 조건이 없기 때문에 다중컬럼 인덱스 제대로 못탄다.
• Left-most 정렬 규칙은 GROUP BY, ORDER BY 절에도 동일하게 적용

8.3.7.3 가용성과 효율성 판단

• 아래 조건들일 경우 인덱스를 작업 범위 결정 조건으로 사용 불가(체크 조건으로만 사용)
  • NOT-EQUAL로 비교
  • LIKE '%??'(뒷부분 일치)
  • 스토어드 함수나 다른 연산자로 인덱스 컬럼이 변형
  • NOT-DETERMINISTIC 속성의 스토어드 함수가 비교조건에 사용
  • 데이터 타입이 서로 다른 비교
  • 문자열 데이터 타입의 콜레이션이 다를 때
• 일반적인 DBMS에서는 Null 값이 인덱스에 저장되지 않지만 MySQL에서는 저장됨
  • 작업 범위 결정 조건으로 인덱스 사용

.. WHERE column IS NULL ..