Index&Hint.md

Inde & Hint

순차 I/O, 랜덤 I/O

인덱스 레인지 스캔, 인덱스 풀 스캔

클러스터링 인덱스, 논 클러스터링 인덱스

B-Tree Index, Hash Index

Hint

랜덤 I/O와 순차 I/O

기본적으로 디스크 드라이브는 데이터를 읽을 때 원판 플래터를 회전하며 데이터를 찾는다.

• 순차 I/O는 논리적/물리적 순서를 따라 차례대로 데이터를 읽어 나가는 방식
• 랜덤 I/O는 논리적/물리적 순서를 따르지 않고 한 건의 데이터를 읽기 위해 한 블록씩 접근하는 방식

디스크에 데이터를 쓰고 읽는 데 걸리는 시간은 디스크 헤더를 움직여서 읽고 쓸 위치로 옮기는 단계에서 결정된다. 따라서 보통 순차 I/O 가 랜덤 I/O 보다 빠르다고 볼 수 있다.

일반적으로 쿼리 튜닝은 쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선하여 랜덤 I/O 작업을 줄이는 것이 목적이다. 순차 I/O로 바꿔서 실행할 방법이 적기 때문이다.

• 인덱스 레인지 스캔은 랜덤 I/O를 사용
• 풀 테이블 스캔은 순차 I/O를 사용
  • 매우 큰 테이블의 레코드를 읽을 때는 풀 테이블 스캔을 사용한다. (ex. 데이터 웨어 하우스, 통계 작업)

인덱스

인덱스는 DBMS의 저장 성능을 희생하고 검색 성능을 높이기 위해 만들어진 자료 구조이다.

인덱스의 목적 RDBMS의 검색 속도를 높이는데 있다.

Index의 원리

Index를 해당 컬러에 주게 되면 초기 Table 생성시, FRM,MYD,MYI 3개의 파일이 만들어진다.

• FRKM: 테이블 구조가 저장되어 있는 파일
• MYD: 실제 데이터가 있는 파일
• MYI: Index 정보가 들어있는 파일

index를 사용하지 않는 경우, MYI 파일은 비어져 있다. 그러나 index를 해당 컬럼에 만들게 되면 해당 컬럼을 따로 인덱싱하여 MYI 파일에 입력한다.

이후에 사용자가 SELECT 쿼리로 index를 사용하는 쿼리를 사용 시 해당 Table을 검색하는 것이 아니라 MYI 파일의 내용을 검색한다.

Index의 장점

• 키 값을 기초로 하여 테이블에서 검색과 정렬 속도를 향상시킨다.
• 인덱스를 사용하면 테이블 행의 고유성을 강화시킬 수 있다.
• 전반적인 시스템의 부하를 줄일 수 있다.

Index의 단점

• 사용자가 한 페이지를 동시에 수정할 수 있는 병행성이 줄어든다.
• 인덱스된 필드에서 데이터를 업데이트(UPDATE)하거나 레코드를 추가(INSERT) 또는 삭제(DELETE) 할 때 성능이 떨어진다. (DML에 취약)
  • Insert
    • indext split : 인덱스의 Block들이 하나에서 두개로 나누어지는 현상.
    • 인덱스는 데이터가 순서대로 정렬되어야 한다. 기존 블록에 여유 공간이 없는 상황에서 그 블록에 새로운 데이터가 입력되어야 할 경우, 오라클이 기존 블록의 내용 중 일부를 새 블록에다가 기록한 후, 기존 블록에 빈 공간을 만들어서 새로운 데이터를 추가하게 된다.
    • Index split은 새로운 블록을 할당받고 Key를 옮기는 복잡한 작업을 수행한다. 모든 수행 과정이 Redo에 기록되고 많은 양의 Redo를 유발한다.
    • Index split이 이루어지는 동안 해당 블록에 대해 키 값이 변경되면 안되므로 DML이 블로킹된다.
  • Delete
    • ndex에서 데이터가 delete될 경우, 데이터가 지워지지 않고 사용 안됨 표시만 해둔다.
    • 즉, 테이블에 데이터가 1만건 있는 경우, 인덱스에는 2만건이 있을 수 있다는 뜻이다.
  • Update
    • 테이블에 update가 발생할 경우, 인덱스에서는 delete가 먼저 발생한 후 새로운 작업의 insert 작업이 발생한다.
    • delete와 insert 두 개의 작업이 인덱스에서 동시에 일어나 다른 DML보다 더 큰 부하를 주게 된다
• 인덱스가 데이터베이스 공간을 차지해 추가적인 공간이 필요해진다. (데이터베이스의 10% 내외의 공간이 추가로 필요)
• 인덱스를 생성하는데 시간이 많이 소요될 수 있다.
• 데이터 변경 작업이 자주 일어날 경우에 인덱스를 재작성해야 할 필요가 있기에 성능에 영향을 끼칠 수 있다.

인덱스 레인지 스캔 vs 인덱스 풀 스캔

• 인덱스 레인지 스캔

  • 인덱스 루트 블록에서 리프 블록까지 수직적으로 탐색한 후에 리프 블록을 필요한 범위만 스캔하는 방식
  • B Tree 인덱스의 가장 일반적인 엑세스 방식
  • 루트 노드 -> 브랜치 노드 -> 리프 노드 순으로 탐색
    • 리프 노드에서 시작할 지점을 찾으면, 그 다음부터는 리프 노드의 레코드만 순서대로 읽으면 된다.
    • 리프 노드의 끝까지 읽으면 리프 노드간의 링크를 통해 다음 리프 노드를 찾아서 스캔한다.
  • 최종적으로 스캔 종료 지점을 찾으면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 종료한다.
    • 데이터 파일에서 레코드를 읽어올 때 레코드 한건마다 랜덤I/O가 발생한다.
    • 그래서 인덱스를 통해 데이터를 읽는 작업은 비용이 많이 든다고 하는 것이다.
    • 인덱스를 통해 읽어야 할 데이터가 전체의 20%~25%를 넘으면 인덱스를 사용하지 않고 테이블 스캔 방식이 더 효율적인 처리 방식이 된다.
  • 주로, <, >, IS NULL, BETWEEN, IN, LIKE 등의 연산을 이용하여 인덱스를 검색할 때 사용된다.

• 인덱스 풀 스캔

  • 수직적 탐색 없이 인덱스 리프 블록을 처음부터 끝까지 수평적으로 탐색하는 방식
  • 대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫번째 컬럼이 아닌 경우 인덱스 풀 스캔 방식을 사용한다.
  • 인덱스의 크기는 테이블의 크기보다 훨씬 작기 때문에 테이블 풀 스캔보다 빠른 방식이다.
  • 인덱스 선두커럼이 조건절에 없으면 옵티마이저는 우선적으로 Table Full Scan을 고려한다.
  • Table Full Scan 부담이 크다면 옵티마이저는 차선으로 Index Full Scan을 선택한다.

• Full Table Scan

  • 테이블에 존재하는 모든 데이터를 읽어가면서 조건에 맞으면 결과로 추출하고 조건에 맞지 않으면 버리는 방식이다.
  • 일반적으로 블록들은 서로 인접되어 있기 때문에, Full Table Scan은 한번은 I/O에 여러 블록을 옮겨온다.
  • 즉 한번의 I/O에 데이터를 다중 블록 단위로 메모리에 가져오기 때문에, row 당 소요되는 입출력 비용이 인덱스 스캔에 비해 적다. 메모리에 옮겨진 블록들은 순차적으로 읽힌다.

Index의 분류

역할별

Clustered Index

• 테이블의 기본키(PK)에 대해 적용되는 인덱스
  • 테이블 당 오직 한개만 존재
• 테이블에 삽입되는 순서에 상관없이 Index로 생성되어 있는 컬럼을 기준으로 정렬되어 삽입된다.
  • 중간에 새로운 데이터가 삽입된다면 이후의 모든 컬럼을 한 칸씩 이동시켜줘야한다. (index가 군집화 되어있기 때문이다. )
• 프라이머리 키 값에 의해 레코드의 저장위치가 결정되며 프라이머리 키 값이 변경되면 그 레코드의 물리적인 저장 위치 또한 변경되어야 한다.
• Clustered Index 구조
  • Leaf Level과 Data Page가 동일한 구조를 갖는다. (별도의 공간을 필요로 하지 않는다. )
  • Data Page의 데이터들이 순차적으로 정렬되어 있다.
  • Clustered Index는 물리적으로 정렬되어 있어 검색 속도가 Non-Clustered Index보다 더 빠르다.
  • 데이터의 입력/수정/삭제 시에도 정렬을 수행하여 입력/수정/삭제 속도는 더 느리다.

Non-Clustered Index

• 테이블의 기본 키 외에 다른 컬럼에 적용된 인덱스
  • 테이블 당 여러개이 인덱스 생성 가능
• 논 클러스터드 인덱스는 테이블에 저장 된 물리적인 순서에 따라 데이터를 정렬하지 않는다. 즉, 순서대로 정렬되어 있지 않다.
• 논 클러스터 형 인덱스는 테이블 데이터와 함께 테이블에 저장되는 것이 아니라 별도의 장소에 저장된다.
  • 테이블의 ID 키 값과 포인터인 Address를 통해 실제 데이터에 접근한다.
• Non-Clustered Index 구조
  • B-Tree 의 리프 노드 처럼 노드 자체가 데이터가 아니고, 리프 노드에서는 데이터가 위치하는 주소를 가지고 있는 형태.
  • Clustured 구조와는 다르게 Leaf Level과 Data Page가 구분된다. 그리고 Data Page의 데이터는 정렬 되어있지 않다.

---

저장 방식별

B -+ Tree Index

• 트리의 가장 큰 강점은 데이터 접근 퍼포먼스가 데이터 증가량에 따라서 결코 선형적으로 증가하지 않는다는 점이다.

• B-Tree는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 자식을 가질 수 있는 B Tree를 M차 B-Tree라고 한다.

• 이진 검색 트리처럼 각 key들의 왼쪽 자식들은 항상 key보다 작은 값을, 오른쪽 값은 큰 값을 가진다.

• 컬럼의 값을 변경하지 않고, 원래의 값을 이용해 인덱싱하는 알고리즘

• Root Node, Branch Node(중간 노드), Leaf Node로 구성

• Root Node와 Branch Node는 인덱스 레코드와 자식 노드 주소를 가지고 있으며 Leaf Node는 인덱스 레코드와 레코드 주소를 가지고 있다.

• Leaf Node 의 레코드 주소는 실제 테이블에 저장되어 있는 레코드를 가리키게 된다.

B+ Tree vs B-Tree

구분	B-Tree	B+Tree
데이터포인터	모든 내부적인 노드들은 데이터 포인터를 지님	리프 노드에만 데이터 포인터가 존재
시퀀셜 엑세스 탐색 방식	모든 key가 리프노드에 존재하지 않기 때문에 모든 노드를 탐색해야 함	모든 key가 리프노드에 존재하기 때문에 리프 노드 레벨에서 탐색하면 됨
키 중복여부	모든 노드는 서로 다른 key를 지님	부모 노드와 자식 노드가 같은 key를 가질 수 있음
링크드 리스트	존재하지 않음	리프 노드는 링크드 리스트로 연결되어 있음

Hash Index

• 해시 인덱스는 InnoDB 에서 어댑티브 해시 인덱스(Adaptive Hash Index)로 사용되기도 하고, 오라클에서는 조인에 사용된다.
• B-Tree 인덱스와 달리 버켓으로 구성된다.
• 사용자가 검색하고자 하는 값을 주면 해시 함수를 거쳐서 찾고자 하는 키값이 포함된 버켓(Bucket)을 알아낼 수 있다. 그리고 그 버켓 하나만 읽어서 실제 레코드가 저장된 위치를 바로 찾을 수 있다.
• Hash index 는 원래의 값을 저장하는 것이 아닌 해시 함수의 결과만을 저장하게 됨에 따라 키 컬럼 값은 4~8바이트 정도로 작은 길이로 줄어 들게 되고 B-Tree 인덱스에 비해 상당히 작은 크기 이다.
• 입력한 값이 다르지만 해시된 값이 같을 경우 해시 충돌이 발생할 수 있다.해시 함수의 결과 값의 범위가 좁으면 필요한 버켓의 개수가 적어지게 되면서 충돌할수 있는 확율이 높게 된다. Hash index 에서 충돌이 많이 발생 될 수록 검색 효율이 떨어지게 된다.
• Hash index 는 동등(equal =) 비교 검색시 사용 및 최적화 되어 있으며 범위나 FullText Search 나 정렬된 결과를 가져오는 목적으로는 사용할 수는 없습니다.
  • SELECT 질의 조건에는 부등호 연산(<>)도 포함되기 때문에 부등호 연산 사용 시 문제 발생할 수 있다.

InnoDB Adaptive Hash Index

• InnoDB 는 B-Tree 를 사용하는데, 락으로 인한 자원 사용 효율이 떨어지는 현상을 해결하기 위해서 InnoDB Adative Hash Index 기능을 도입한다.
• 자주 사용되는 자원을 해시를 통해서 직접 접근하기 때문에, 내부적인 락(이를테면 Mutex)으로 인한 지연이 줄어든다.
• 자주 사용되는 데이터 값만 내부적으로 판단하여 상황에 맞게 해시 값을 생성한다.
• 단 자주 사용되는 자원 만을 해시로 생성하기 때문에, SELECT로 인하여 반드시 해당 자원을 향한 직접적인 해시 값이 만들어지지 않는다.
• 빈번한 데이터 접근이 많은 환경에서는 대단히 효율이 좋은 결과를 나타내었다. 그러나, 주의를 해야할 점은 오래된 테이블인 경우에도 해시가 여전히 메모리에 남아있을 수 있으며, 이에 대한 제어는 불가하다.

Hint

• SQL 문장에 특별한 키워드를 지정하여 옵티마이저에게 어떻게 데이터를 읽는 것이 효과적인지 알려주는 키워드를 의미한다.
• Hint 는 옵티마이저에게 영향을 미친다. 따라서 Hint 를 잘못 사용하면 옵티마이저가 SQL 을 알아서 최적화 해주는 것을 본인이 망치는 셈이 될 수도 있다.

사용 방법

• SQL 문장의 일부로 사용하는 방식
  • SELECT * FROM member USE INDEX (PRIMARY) WHERE id = 1001;
• 주석 표기 방식
  • SELECT * FROM member /*! USE INDEX (PRIMARY) */ WHERE id = 1001;

Oracle 과 같은 다른 DBMS 들은 Hint 를 주석으로 해석하는데, MySQL 은 SQL 의 일부로 해석하기 때문에 잘 못 사용하면 에러가 발생한다.