Review 3. 8_인덱스 (8.3, 8.8, 8.9)

[DaehunGwak]

진도

8.3 B-Tree 인덱스 8.8 클러스터링 인덱스 8.9 유니크 인덱스

일정

• 2022.06.26.(일) 23:00

[tmxkqotnl]

다시 정리

• MySQL의 InnoDB 엔진은 Page(block)라는 단위로 레코드를 저장하며, 크기는 16KB(default)로 고정된 크기를 가짐
  • 헤더 또는 트레일러(checksum) 등의 정보 포함

B-Tree 인덱스 알고리즘

• 레코드의 인덱스 기준으로 정렬함

• InnoDB의 레코드는 클러스터링 되어 기본 키로 정렬됨(default)

  • 기본 키를 주소처럼 사용하기 때문에 이에 맞춰 정렬됨
    • 프라이머리 키를 찾기 위해 검색 과정이 요구됨
  • 그 외 대부분 데이터 파일의 순서는 임의의 순서로 저장됌
    • 삭제된 공간을 재활용하기 때문

• 인덱스 키의 크기와 한 페이지에 저장할 수 있는 키의 갯수는 반비례한다.

  • 갯수가 적어질 수록 노드의 분기가 잦아지고 디스크 I/O 가 늘어날 가능성이 커짐

• 기수성은 즉, 인덱스 컬럼의 값 중 유니크 한 값의 수

  • 전체 테이블 레코드의 20~25% 이상을 읽어야 한다면 인덱스를 사용하지 않을 것을 권장
  • 이 비율은 RDBMS 서버마다 다를 수 있음

• 인덱스 레인지 스캔이란, 검색을 통한 인덱스 범위가 정해져 있을 때 리프 노드 레코드를 찾으려는 인덱스 값의 시작부터 차례대로 읽는 것 ↔ 인덱스 풀 스캔

• 그 뒤에 스캔된 레코드를을 하나씩 데이터 파일로부터 랜덤 I/O를 통해 읽어온다.

  1. 인덱스 탐색

  2. 인덱스 스캔

  3. 인덱스 키 그리고 레코드 주소로 페이지를 가져와서 레코드를 읽음

• 인덱스 풀 스캔의 경우 인덱스만 읽는 방식(인덱스에 명시된 컬럼만으로 조건을 처리할 수 있음)

• 쿼리를 충족하는데 필요한 모든 데이터를 갖춘 인덱스를 커버링 인덱스라고 함

  • 디스크 레코드를 읽지 않아도 됌

• 인덱스 풀 스캔, 인덱스 레인지 스캔 등은 타이트(tight) 인덱스 스캔 ↔ 루스(loose) 인덱스 스캔

• 필요한 리프 노드만 스캔하는 방식의 루스 인덱스 스캔(인덱스 스킵 스캔)

  • 단, 성능 측면에서
    • 1. 커버링 인덱스이면서
    • 2. 유니크 값의 갯수가 적어야 함

• 인덱스 스캔 방향은 옵티마이저에 의해서 실시간으로 만들어지는 실행 계획에 의해 결정됨

• 인덱스의 정렬은 정렬 순서를 컬럼에 따라 혼합(오름/내림차순) 가능

• 인덱스는 생성 시점에서 정렬되지만, 쿼리로 인덱스를 사용하는 시점에서 읽는 방향에 따라 정렬 효과를 얻음

  • 즉, 비용을 최소화 할 수 있음
  • 일부 함수에 옵티마이저가 이를 적용함

• 복합 인덱스로 혼합 정렬을 하는 경우에는 내림차순 인덱스로만 해결될 수 있다.

  • 역순 스캔이 정순에 비해 더 오래 걸리기 때문(테이블 풀 스캔을 실시함)
    • 단방향 링크드 리스트로 연결된 구조이기 때문
    • 페이지 잠금이 정순 스캔에 적합한 구조이기 때문

• 그래서 B-Tree 인덱스를 사용하려면..

  • 쿼리의 where, group by, order by 절을 적절한 상황에 사용해야 함
    • 인덱스 사용 여부, 어떤 방식으로 사용할지, 비교 작업 범위를 좁히도록

클러스터링 인덱스

• InnoDB엔진에서 비슷한 값들을 동시에 조회한다는 점에서 착안한 프라이머리 키에만 적용되는 저장 방식

  • 기본 키 값에 의해 레코드 저장 위치가 결정됨
    • 검색이 빠르나, 업데이트, 삭제, 저장은 상대적으로 느려짐

• 기본 키로 검색하면 매우 빠름

• 커버링 인덱스가 되는 경우가 많음

• 단, 클러스터링 키 값이 커지면 전체적인 인덱스 크기가 커짐

• 레코드의 모든 컬럼이 리프 노드에 저장되어 있음

  • 즉, 레코드의 기본 키가 변경되면 리프 노드의 페이지가 바뀔 수 있음

• 기본 키가 없는 테이블의 경우 다음 우선순위대로 대체 컬럼을 선택함

  1. NOT NULL 옵션의 유니크 인덱스 중 첫 번째 인덱스를 클러스터링 키로 선택
  2. 자동으로 유니크한 값을 가지도록 증가되는 컬럼을 내부적으로 추가하고 이를 클러스터링 키로 선택
     • 내부 컬럼은 사용자에게 노출되지 않음
     • 그저 자동 증가하는 컬럼이 기본 키가 되므로 특별한 혜택은 없음

• InnoDB 테이블의 모든 세컨더리 인덱스는 기본 키 값을 저장하도록 구현됌

  • 기본 키를 확인하고 검색한 후 최종 레코드를 가져옴(오버헤드)
  • 기본 키가 커지면 세컨더리 인덱스도 커짐

• 자동 증가 값을 기본 키로 설정하고, 상대적으로 긴 인덱스를 세컨더리 인덱스로 둠으로써 성능 향상을 도모할 수 있음

  • 인위적인 기본 키(Surrogate Key)

유니크 인덱스

• 클러스터링 키 역할은 못함

• 읽기 및 쓰기 성능 관점에서 세컨더리 인덱스(유니크 하지 않음)는 큰 차이가 없음

  • 정확히는, 인덱스의 특성이라는 점에서 크게 차이가 없음
    • 그저 중복을 허용해 읽어야 할 레코드가 많음
  • 세컨더리 인덱스의 추가 작업인 CPU의 컬럼값 비교 작업은 크게 영향을 주지 않음
  • 서로 역할은 같음

• 중복 검사에 대한 비용이 있음

  • 읽기 잠금 그리고 쓰기 잠금 중에 데드락이 자주 발생함
  • 인덱스 키 저장 또는 변경을 위해 체인지 버퍼를 사용해 빠르지만, 유니크 검사에는 영향이 적음
    • 그래서 세컨더리 인덱스에 비해 느림

• 유니크 인덱스는 반드시 성능 향상을 가져오지는 않음

---

참고

https://dev.mysql.com/doc/internals/en/innodb-page-structure.html

[minkukjo]

B-tree

• B 트리의 B는 Binary가 아니다. Balanced임!
• B 트리는 쓰기/삭제/업데이트에 성능이 안좋고, 읽기에 성능이 좋다. 하지만 그것도 쿼리에 인덱스가 발려진 컬럼을 잘 써야 그렇고 아니면 불필요하게 많이 잠금을 걸어서 오히려 성능이 나빠질 수도 있다.
• 참고로 인덱스를 통해 읽어야하는 레코드 건수가 전체 테이블 크기의 20~25%가 넘으면 인덱스를 쓰지 않고 전체 테이블을 읽어서 가려내는 방식을 MySQL 옵티마이저가 쓴다고 한다.
• 최상위 : Root, 중간 : Branch, 끝 : Leaf로 이루어진 트리
• 인덱스의 리프는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 갖고 있음
• InnoDB에서는 인덱스의 리프노드를 본 후 프라이머리 키 인덱스를 다시 찾아간다.
• 결국 인덱스의 리프노드는 클러스터링 인덱스의 리프노드를 가르키고 있으며, 여기를 다시 순차적으로 찾아서 최종 목적지인 데이터에 다다른다.

왜 InnoDB는 인덱스를 탐색 후 다시 탐색하는 이딴 번거로운 짓을 하는가?

• 클러스터링 인덱스란 키 값이 비슷한 레코드끼리 묶어서 저장하는 것을 말한다.
• 즉, PK 값이 레코드의 저장 위치를 결정한다는 의미이므로 PK 값과 클러스터링 테이블은 강결합이 되게 된다.
• 그래서 이건 알고리즘이 아니고, 그냥 테이블 레코드의 저장방식 그 자체다.
• 때문에 클러스터링 인덱스를 사용하는 InnoDB는 검색에 매우 빠른 성능을 보이지만, 상대적으로 레코드 저장이나 PK 변경에 취약한 모습을 보인다.
• 물론 일반 인덱스 역시 키값을 기준으로 저장되어 저장되지만, 그렇다고 이걸 클러스터링 인덱스라 부르지 않는다. 왜? 클러스터링 인덱스는 PK 키 값으로 정렬되어 저장된 경우만 클러스터링 인덱스라고 부르기 때문.
• 만약 PK가 바뀌게 되면 기존 페이지에서 다른 페이지로 이동할 수도 있다. 이는 꽤 비용이 비싸다.
• PK가 없는 테이블은 InnoDB가 알아서 PK를 대체할 칼럼을 선정해서 클러스터링 키로 선정한다.
• 그래도 없으면 InnoDB가 알아서 자기가 PK 비슷한걸 만들어서 관리하며, 이는 사용자에게 노출되지 않음.

클러스터링 인덱스의 장/단점

• 장점
• PK로 검색하는 경우 검색 개빠름 특히 PK를 범위 검색하는 경우도
• 커버링 인덱스를 사용해서 인덱스만으로 처리가 가능함.
• 단점
• 모든 세컨더리 인덱스가 클러스터링 키를 가지므로, 키 값의 크기가 커질 경우 전체적인 인덱스 크기가 커짐
• 세컨더리 인덱스를 통해 검색할 때 PK로 한 번 다시 검색해야해서 처리 성능이 느림
• Insert 성능 구림
• PK 변경 성능 구림
• 일반적인 웹서비스에서는 Read가 CUD에 비해 많아서 클러스터링 인덱스가 장점이 될 수 있음.

유니크 인덱스에 대해

• 사실상 세컨더리 인덱스는 구조적으로 아무런 차이가 없다.
• 꼭 필요한 경우에만 유니크 인덱스를 걸자.

[DaehunGwak]

8.3 B-Tree 인덱스

• InnoDB 는 프라이머리 키를 기반한 클러스터링 인덱스를 통해 데이터 파일이 저장됨
  • 이는 이노디비 세컨더리 인덱스를 통해 검색하면 데이터 파일의 프라이머리 키의 B-Tree 를 한번더 거침
• InnoDB 의 쓰기작업은 스플릿 작업이 포함될 수 있기때문에 상대적으로 더 느릴 수 있음
  • 코스트 계산: 세컨더리 인덱스 수 * 1.5 + 1 (데이터 파일에 쓰는 비용)
• 변경 작업은 키 값을 먼저 제거 후 다른 새로운 키 값을 추가하는 형태로 진행 (삭제 + 쓰기)
• 기본 단위는 페이지 (4~64 kb)
  • 읽어야 하는 페이지 수만큼 io 발생
  • 인덱스 키값 length 를 줄여야하는 이유
• 선택성(기수성) - 해당 필드의 유니크한 값 수 (기수가 클 수록 빨리 처리됨)
• 인덱스 데이터 읽기
  • 인덱스 레인지 스캔
    • 뒤의 두가지 보다 빠른 방식
    • index seek → index scan (다시 상위로 안올라가고 쭉 스캔) → 인덱스 스캔으로 실제 저장된 페이지를 가져옴 (커버링 인덱스 이면 해당 과정 생략)
    • 커버링 인덱스? 인덱스에 조회에 필요한 필드가 다 있을 경우 실제 데이터파일에 페이지를 읽어오지 않고 인덱스로만 다 커버하는 것
      • https://tecoble.techcourse.co.kr/post/2021-10-12-covering-index/
  • 인덱스 풀 스캔
    • 인덱스 전체를 다 읽는 경우
    • 커버링 인덱스가 가능한 경우만 보통 씀
  • 루스 인덱스 스캔
    • 듬성듬성 읽기
    • GROUP BY, MIN, MAX 등 최적화에 사용
  • 인덱스 스킵 스캔
    • 8.0 부터 도입
    • index (gender, birth_date) 만 있는 상태에서 birth_date 조건만 사용하면 해당 인덱스를 태울 수가 없었음
    • 이젠 태울 수 있음 (range 로가능)
    • 실제론 gender=M, gender=F 를 나눠서 실행하게 됨
    • 단점
      • 조건 없는 인덱스 선행 칼럼의 기수가 적어야 함
      • 커버링 인덱스가 가능해야함
• 인덱스 정렬 및 스캔 방향
  • 8.0 부터 혼합(ASC + DESC) 인덱스 생성 가능
  • 인덱스 역순 스캔이 정순 스캔보다 느린 이유
    • 페이지 내 인덱스 레코드가 단방향으로 연결되어 있음 → 페이지 잠금이 인덱스 정순 스캔에 적합한 구조
  • 따라서, 자주 사용되는 쿼리의 순서로 인덱스를 생성하자
• 인덱스의 가용성과 효율성
  • 얼마나 필터링 될지 안될지를 알고 채택해야됨
  • left most 정렬 기반이라는 것

8.8 클러스터링 인덱스

• InnoDB 에서 프라이머리 키 기반으로 묶어 데이터를 저장
• 프라이머리 키 기반의 데이터 추가, 변경에 조금 느린성능을가지게 되지만, 조회 성능을 빨리 가져갈 수 있음
• 프라이머리 키가 세컨더리 인덱스에 미치는 영향
  • innodb는 세컨더리 인덱스의 리프 노드를 프라이머리 키로 가져감
• 장점
  • 프라이머리 키 기반 검색이 매우 빠름
  • 커버링 인덱스
• 단점
  • 클러스터링 키의 크기가 세컨더리 인덱스의 크기에 영향을 줌
  • 세컨더리 → 프라이머리 키 구조라 두번 검색해야 함
  • 쓰기 성능이 느림
  • 프라이머리 키 변경 시 레코드를 삭제 + 쓰기 해야함

8.9 유니크 인덱스

• 세컨더리 인덱스에 쓰기 작업하는 것에 비해, 유니크 한지 검사가 한번더 필요함
  • 중복된 값 체크 시 읽기 잠금 사용 + 쓰기 시 쓰기 잠금 사용 (데드락 빈번)
  • 버퍼링도 불가
• 제약 조건이 꼭 필요하다면 사용하지만, 성능이 더 좋아질 것으로 판단하고 사용해선 안됨

[Edwin222]

B-Tree

• 삽입이 비쌈(Split때문)

• 키값의 바이트 사이즈는 작을수록 좋다.

  • 레코드 많아질수록 커지는건 필연적일것 같긴 한데..

• 키값의 바이트 사이즈는 유니크한 칼럼의 갯수(기수성)에 맞춰서 최저한으로 해두는게 좋겠다.

  • 여유분은 한 1바이트만 둬도 *256이니까 충분할 느낌..

클러스터링 인덱스

• PK를 기준으로 비슷한 것들을 묶어 정렬

  • PK를 변경하면 레코드의 물리적 저장 위치도 바뀌어야 한다. (DELETE 후 INSERT하는 동작)

  • 따라서 레코드 ID에 커플링되는 무언가가 없도록 세컨더리 인덱스는 해당되는 PK가 무엇인지로 이어진다.

    • 세컨더리 인덱스가 레코드 ID를 직접 가리킬 경우, PK의 변경에 의해 모든 세컨더리 인덱스 테이블을 정합성 맞게 바꿔야하는 오버헤드가 발생하기 때문.

  • 레코드를 조회할 수 있는 레코드 ID는 항상 PK에 의해 접근되도록 되어 있다.

  • PK 자체에 대한 의존도가 높아서 잘 정해야 한다.

• PK가 없는 경우에 클러스터링은 어떻게 하나

  • PK가 없으면 NOT NULL인 유니크 인덱스 중 첫번째 인덱스를 클러스터링 키로 고른다.

  • 그것도 없으면 유니크한 값을 가지는 칼럼을 자동 생성한 뒤 클러스터링 키로 쓴다.

  • 명시적으로 조회가 불가능하며 의미도 없는 값이므로 사실상 활용할 수 없음.

유니크 인덱스

• 유니크하지 않은 세컨더리 인덱스와 구조적 차이는 없다.

• 세컨더리 인덱스보다 편집이 느리다. 바꿀 때 마다 유니크한지에 대한 검증이 필요하기 때문

• 세컨더리 인덱스의 퍼포먼스가 유니크 인덱스에 비해 퍼포먼스가 부족한 건 겹치는 값이 적어서 비교할 레코드가 많기 때문이다.

  • 두 인덱스 처리의 실행 계획은 다르지만, 실행 계획에서 수행하는 연산 자체가 느린 건 아니라는 것.