5. 인덱스.md

인덱스

• 테이블의 모든 데이터를 검색해 원하는 결과를 가져오려면 많은 처리 시간이 필요하므로, 칼럼의 값과 해당 레코드가 저장된 주소를 key-value pair 로 만들어 해당 pair(index)를 참고해 빠르게 원하는 결과를 가져오도록 하는것
• 원하는 값을 빠르게 index를 참고해 찾기 위해서 index의 정렬이 중요함. 대부분의 DBMS는 index를 주어진 순서로 미리 정렬해서 보관함.
• 원하는 결과를 빠르게 select 할 수는 있지만 새로운 값을 저장할땐 해당 값에 대한 index를 정렬해주어야 하므로 SELECT는 빨라지지만, INSERT, UPDATE, DELETE 문의 처리가 느려지게 된다. 그러므로 인덱스를 추가할때는 저장속도의 희생과 얼마나 빠른 읽기 속도가 필요한지 적절히 검토 해보아야 한다.

Pre-requirement

DB는 디스크 장치가 대부분 병목이 된다. 따라서 DB를 튜닝하기 위해선 Disk I/O를 줄이는것이 목적임.

Random I/O & Sequential I/O

• Sequential I_O의 경우는 디스크에 기록할 위치를 찾기 위해 디스크의 헤드를 한번만 움직이고 순서에 따라 그대로 쌓으면 되지만 Random I_O는 기록할 위치가 랜덤이므로 기록할 데이터별로 디스크의 헤드를 움직이는 작업을 실행 시켜주어야 함.
• 대부분의 쿼리는 Random I_O이기 때문에 꼭 필요한 데이터만 읽어 Random I_O를 줄이는것이 쿼리 개선의 목표임.

인덱스의 분류

인덱스의 역할별

• Primary Key
  • 흔히들 알고 있는 그 Primary key.. 대표하는 칼럼의 값으로 만들어진 인덱스이다.
    • nullable 하지 않고, 중복을 허용하지 않음
• Secondary Key * primary key를 제외 한 나머지 index (Unique, … etc)

저장방식(알고리즘) 별

• B-Tree Index
  • 칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱 하는 알고리즘
  • 오래 되었고 제일 일반적
• Hash Index
  • 칼럼의 값으로 hash를 생성해 hash 값을 계산해서 인덱싱 하는 알고리즘 매우 빠른 검색을 지원.
  • 값을 변형하기때문에 값의 일부만 검색하고자 할때는 hash index 사용 불가능
  • 주로 메모리 기반 DB에서 사용
• Fractal-Tree Index
  • B-Tree의 단점을 보완하기 위해 고안된 알고리즘, 값을 변형하지 않아 범용적으로 사용 가능
  • 데이터가 저장 되거나 삭제 될때 처리비용을 줄일 수 있도록 설계 됨

B-Tree index

• Binary-Tree 아님 Balanced-Tree임.
• 제일 일반적이고 오래 되었고 제일 범용적임.
• 실제 값을 변형 시키지 않고( 값의 앞부분만 잘라서 관리하긴 하지만) 인덱스 구조체 내에서는 항상 정렬된 상태.

구조 및 특성

• 위와 같이 Root - Branch - Leaf 로 구성이 되어있음.
• 인덱스와 key값은 모두 정렬 되어있지만, 데이터 파일의 레코드는 정렬 되어있지 않음.
  • InnoDB의 경우, 레코드가 클러스터 되어 디스크에 저장 되므로, PK 순서대로 정렬되어 저장이 됨.
• 그림에서의 ROW ID(레코드 주소) 는 엔진마다 의미가 달라진다. 실제 MySQL 테이블 인덱스 칼럼값과 레코드 주소 값의 조합이 인덱스 레코드로 구성이 됨.
  • Oracle의 경우 물리적인 레코드 주소
  • MyISAM의 경우 테내부적인 레코드의 ID 번호를 부여함.
  • InnoDB는 PK에 의해 클러스터링 되기때문에 PK자체가 주소 역할을 함.

B-Tree Index 유의점

• 추가
  • 스토리지 엔진에 따라 새로운 key가 즉시 Index에 저장이 될수도 안될수도 있다.
    • B-tree에 저장될때는 저장 될 key를 이용해 B-tree상의 적절한 위치를 찾고, Leaf 노드에 저장한다. Leaf 노드가 꽉차있을때는 리프노드를 split한다.
  • 인덱스 추가로 인한 INSERT, UPDATE 쿼리 의 영향
    • 일반적으로 테이블에 레코드를 추가하는 작업비용이 1 이면 테이블의 인덱스에 키를 추가하는 작업비용은 1~1.5로 산정을 한다, 예로 테이블에 인덱스가 3개 있다고 하면 5.5(1.5(인덱스 insert 비용) * 3 + 1 (insert 작업비용)) 정도로 예측 할 수 있다고 함.
  • MyISAM 이나 MEMORY storage engine의 경우 즉시 새 index를 B-Tree인덱스에 반영한다. 이 경우, B-tree에 인덱스를 추가하는 작업이 끝날떄까지 쿼리의 결과를 받지 못하고 기다리게 됨.
  • InnoDB의 경우 아래와 같은 순서로 동작함. * InnoDB의 버퍼풀에 새로운 키값을 추가해야할 페이지(Leaf 노드) 가 있으면 즉시 키 추가 작업 실행 * 버퍼풀에 Leaf 노드가 없다면 인서트 버퍼에 추가할 키값과 레코드의 주소를 임시로 기록해두고 작업 완료( 사용자의 쿼리는 실행 완료됨) * 백그라운드 작업으로 인덱스 페이지를 읽을 때마다 인서트 버퍼에 merge해야할 인덱스 키가 있는지 확인후 있으면 merge함. * DB 리소스에 여유가 생기면 인서트 버퍼 머지스레드가 조금씩 인서트 버퍼에 저장된 인덱스 키와 주소값을 머지함(B-Tree에 인덱스 키와 주소를 저장)
    • MySQL 5.5 부터 INSERT, DELETE에 의한 인덱스 키의 추가, 삭제 작업까지 버퍼링 하여 지연 처리 할 수 있게 함. 이를 Change buffering 이라고 함.
      • 설정 값 innodb_change_buffering 설정 값을 이용해 키 추가 작업과 삭제 작업중 어느것을 지연 처리 할지 설정 해야함.
  • 삭제
    • 삭제될 key값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업 완료 (disk I/O)
    • InnoDB 엔진 에서는 사용자에게는 특별한 악영향 없이 내부적으로 처리
    • MyISAM, MEMORY 엔진 에서는 인서트 버퍼 같은것이 없으므로 인덱스 키 삭제가 완료 된 후 쿼리 실행이 완료 됨.
  • 변경
    • 인덱스 키 값은 그 값에 다라 저장될 리프노드의 위치가 결정 되므로 불가능. 먼저 키 값을 삭제한 후 다시 추가하는 형태로 처리된다.
  • 검색
    • 인덱스의 검색 작업은 B-Tree의 Root-Branch-Leaf로 이동 하면서 비교 작업을 수행함 이를 트리 탐색(Tree-traversal)이라고 함
    • SELECT, UPDATE, DELETE에 대해 트리 탐색을 시행하는데 B-tree 인덱스를 활용한 검색은 100%일치 혹은 값의 앞부분(left-most part)이 일치하는 경우에만 사용가능 <>(부등호 비교)나 값의 뒷부분이 일치하는 경우에는 B-Tree 인덱스를 이용한 검색이 불가능. 따라서 인덱스의 키값이 이미 변형이후엔 인덱스를 활용한 검색이 불가능 하여서 함수나 연산을 수행한 결과로 정렬 하거나 검색하는 경우엔 B-Tree 인덱스 활용이 불가능하다.
    • InnoDB의 경우엔 레코드락 이나 넥스트 키 락 (갭 락)이 검색을 수행한 인덱스를 잠근후 테이블의 레코드를 잠그는 방식으로 구현이 되어있어서 UPDATE나 DELETE가 실행될떄 테이블에 적절히 사용 할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠구기 떄문에 InnoDB 인덱스의 설계에선 SELECT 외에도 UPDATEM, DELETE 상황에서의 고려도 필요함.

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

• 인덱스를 칼럼의 크기와 레코드의 건수 유니크한 키값의 개수에 의해 영향을 받는다
• 인덱스의 크기
  • InnoDB 엔진은 디스크에 저장하는 가장 기본단위를 page 혹은 Block 이라고 함. 인덱스 또한 페이지 단위로 관리된다.
  • InnoDB의 모든 페이지 크기는 16KB로 고정이 되어있다(변경하려면 소스 컴파일을 해야함) 따라서 하나의 인덱스 페이지에 저장 할 수있는 키의 개수는 정해져 있다. 따라서 인덱스 키가 클 수록 디스크로 부터 읽어야하는(페이지를 읽어야하는) 횟수가 늘어나게 된다.
• 선택도 (기수성)
  • 인덱스에서의 선택도(cardinality)는 모든 인덱스의 키값 가운데 유니크한 값의 값의 수를 의미한다.
  • MySQL에서는 인덱스의 통계정보(유니크한 값의개수)가 관리 된다.
  • 예로 전체 row 가 1만개인 테이블이 있고, 인덱스가 걸린 칼럼이 유니크 값이 10개 이면 한개의 특정한 Row를 검색을 할 때 인덱스를 통해 찾은 (10000/10) = 1000개의 row에서 검색을 해야하지만 유니크한 값이 1000개 이면 (10000/1000) = 10 개의 row에서만 검색하면 된다. 이렇듯 유니크한 값의 갯수에 따라 처리량에 영향을 많이 받는다
• 읽어야하는 레코드의 건수
  • DBMS의 옵티마이저에서 인덱스를 통해 읽는것이 테이블에서 읽는것 보다 4~5배 정도 빠름
  • 즉 인덱스를 통해 읽어야할 row의 수가 전체 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 직접 테이블을 모두 읽는것이 더 효율적임.
  • 보통의 이런 작업은 MySQL의 옵티마이져가 인덱스를 무시하고 테이블을 직접 읽는 방식으로 처리 하도록 됨

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

• 인덱스 레인지 스캔
  • 인덱스의 접근 방법가운데 제일 대표적인 방식
  • 검색해야 할 인덱스의 범위가 결정 되어있을때 사용하는 방식
  • Root-Branch-Leaf 순으로 탐색한 후 시작 위치를 찾으면 그 이후 부턴 리프노드의 끝까지 차례대로 읽음.
  • 시작 값을 가지고 있는 리프노드로 부터 칼럼의 정순, 역순으로 정렬된 상태로 레코드를 가져옴 (인덱스의 자체적인 속성 때문, 따로 정렬 하지는 않음)
  • 실제 데이터 파일에서 레코드를 읽어올땐 한건당 Random I/O가 발생함.
    • 그래서 인덱스를 통해 읽어야할 레코드가 20~25%가 넘음녀 인덱스를 통한 읽기보다 테이블의 데이터를 직접읽는것이 효율적인것.
• 인덱스 풀 스캔
  • 인덱스의 처음부터 끝 까지 모두 읽는 방식
  • 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 칼럼이 아닐때 사용함. 예로 인덱스는 (A,B,C)의 순서이나 쿼리의 조건절은 B나 C로 검색하는 경우.
  • 인덱스에 포함한 칼럼만으로 처리 가능한 일을 할때는 유용함,
  • 일반적으로 인덱스를 생성하는 목적에는 반하는 스캔 방식
• 루스(Loose) 인덱스 스캔
  • 듬성듬성하게 인덱스를 읽는 방식, 필요하지 않은 인덱스 키값은 스킵하고 다음으로 넘어간다.
  • 주로 group by 또는 MAX, MIN 함수에 대해 최적화를 할때 사용한다
  • 예를들어 어떤 테이블의 인덱스가 걸려있는 칼럼의 MIN을 찾는 쿼리를 호출하면 인덱스는 정렬 되어있으므로 전체 범위를 스캔하지 않고 첫 레코드만 읽는 방식
  • 이와 같이 옵티마이져가 조건에 만족하지 않는 레코드는 무시하고 넘어간다.

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

* 두개 이상의 칼럼이 포함되는 인덱스
* 위 그림과 같이 인덱스를 정의한 칼럼의 순서대로 정렬이 된다.
* 따라서 인덱스를 여러 칼럼에 대해 정의할때 칼럼의 순서가 중요하다.

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

• 인덱스의 정렬
  • 일반적인 DBMS들은 인덱스를 생성하는 시점에 인덱스를 구성하는 각 컬럼의 정렬을 ASC, DESC로 정렬을 설정 할 수있지만 Mysql은 아직 지원하지 않음(5.5기준?)
  • *MySQL에서는 모든 칼럼이 오름차순으로 정렬이됨.
• 인덱스의 스캔 방향
  • 인덱스를 읽는 방향에 따라 정렬의 효과를 가져올수 있음
  • MySQL에서는 인덱스가 무조건 오름차순이지만 옵티마이져가 이를 판단해 인덱스에 접근할 순서를 정한다.
  • 예로 SELECT * From employes ORDER BY first_name DESC LIMIT 1; 이라는 쿼리가 있으면 옵티마이져가 판단하여 인덱스를 역순으로 접근해 맨 처음 레코드만 읽은후 반환한다.

Fractal-Tree index

• TokuDB에만 적용이 되어있는 인덱싱 알고리즘
• B-Tree의 단점인 많은 Random I_O를 순차 I_O로 변환해서 처리 할 수 있음.
• (벤치마크는 책 참고)
• 구조가 유사해서 B-Tree의 장점을 Fractal-Tree도 그대로 가지고있으므로 그대로 migration이 가능함

Full Text Search Index

• B-Tree는 앞 1000바이트(myIsam) 혹은 767바이트(Innodb) 까지만 잘라서 사용하기 때문에 전문검색(full-text search)에는 사용 할수 없음
• 문서 전체의 검색과 분석을 위한 인덱싱 알고리즘, 알고리즘의 이름은 아니고 기능의 명칭임.
• 문서 본문에서 사용자가 검색하게될 키워드를 분석해내고 빠른 검색용으로 사용할 수 있게 이런 키워드로 인덱스를 구축한다.

구분자 기법(stop word)

• 전문의 내용을 공백, 탭, 마침표, 사용자정의 문자 열을 구분자로 등록하면 등록된 구분자를 기반으로 키워드를 분석하고 이 분석된 키워드로 인덱스를 생성해둠
• 키워드를 추출해내는 작업이 필요할뿐 내부적으론 B-Tree인덱스를 그대로 사용함
• Mysql에서 기본적으로 제공하는 방식임

N-Gram 기법

• 지정된 규칙이 없이 없는 전문도 분석을 가능하게 하는 방식
• 본문을 무조건 적으로 몇글자 씩 잘라서 인덱싱 하는 방식 주로 2글자 단위로 키워드를 쪼개서 분석함 (N이 쪼개지는 글자수를 의미)
• 첫단계로 문서의 본문을 2글자보다 큰 크기의 블록으로 잘라서 백엔드 인덱스를 생성
• 두번째 단계로 생성된 백엔드 인덱스 키워드들을 2글자 단위로 자르는 프론트엔드 인덱스를 생성
• 잘린 프론트엔드 인덱스를 통해 검색함. 그후 백엔드 인덱스를 통해 최종 검증함.
• 구분자와의 차이는 책을 참고
• 구분자 방식은 구분자를 기준으로 삼아 왼쪽 기준으로 비교 검색을 실행
• 검색어의 길이가 길어질 수록 많은 성능 저하
• 써드 파티 에서 제공함 5.0 이후 버전에선 플러그인 형태
• 전문 검색 인덱스를 사용하려면 Match Against … 하는 문법을 사용해야함

클러스터링 인덱스

• 인덱스를 비슷한것들은 묶어서 저장함
• 저장 방식임.
• InnoDb TokuDB에서만 지원
• 테이블의 프라이머리 키에 대해 적용됨
• 프라이머리 키가 없으면 NOT NULL Unique, 없으면 자동으로 유니크한 값을 가지는 내부적으로 추가함
• 프라이머리의 키값이 바뀌면 물리적인 저장 위치도 변경 되므로 프라이머리 키에 대한 의존도가 상당히 높으므로 프라이머리 키를 신중히 결정행야함
• 프라이머리 키 기반의 검색이 매우 빠르며 변경은 상대적으로 느림
• 클러스터링 인덱스의 리프노드에는 레코드의 모든 칼럼이 같이 저장되어있음, 클러스터링 테이블은 그 자체가 거대한 인덱스 구조로 관리됨
• 보조인덱스는 레코드가 저장된 주소가 아닌 프라이머리 키값을 저장하게 되어있음
• InnoDB같이 클러스터링된 것들은 인덱스 검색할때 프라이머리 키를 한번 더 조회하여서 최종 레코드를 가져옴.

주의사항

• 클러스터 테이블의 경우 보조인덱스가 프라이머리키를 포함하기 때문에 프라이머리 키의 크기가 커지면 같이 보조인덱스도 커짐 -> 프라이머리 키의 크기를 많이 크게 관리하는것이 중요

Unique Index

• Index 보단 제약 사항에 더 가까움, Mysql에서는 한 테이블에 중복된 로우를 막을수 없는 방법이 없다.

---

코멘트

• InnoDB의 클러스터링
• InnoDB에서 주기적으로 optimize table 해줘야 하는 이유
  • 통계테이블을 기반으로 쿼리 플랜을 짜는데,
• 인덱스 생성시 인덱스의 정렬 순서를 구성 할 수 있는지 mysql 최신버전에서
• B-Tree Index 추가시 full-scan이 일어날 수 있음
• Hash Index, unique, forienkey
• 클러스터링 인덱스에 관한 명시적 설명 ->