Index (기본 / 인덱스 스캔 방향)

1. 인덱스란

• 책의 목차가 인덱스에 많이 비유된다.
• 목차를 통해 알아낼 수 있는 페이지 번호는 데이터 파일에 저장된 레코드의 주소에 비유된다.
• DBMS도 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 오래 걸린다.

컬럼의 값과 해당 레코드가 저장된 주소를 Key-Value 형태로 삼아 인덱스를 만들어 둔다.

레코드는 최대한 빠르게 찾아갈 수 있게 컬럼의 값을 주어진 순서대로 미리 정렬해서 보관한다.

SortedList & Array List

SortedList는 인덱스와 같은 자료 구조이며, ArrayList는 데이터 파일과 같은 자료 구조를 사용한다.

• SortedList는 저장되는 값을 항상 정렬된 상태로 유지하는 자료 구조
• ArrayList는 값을 저장되는 순서 그대로 유지하는 자료 구조

Index - SortedList와 마찬가지로 저장되는 칼럼의 값을 이용해 항상 정렬된 상태를 유지한다.

Data File - ArrayList와 같이 저장된 순서대로 별도의 정렬 없이 그대로 저장한다.

• SortedList는 데이터가 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리지만, 이미 정렬돼 있어서 아주 빨리 원하는 값을 찾아 올 수 있다.
• 인덱스가 많은 테이블은 당연히 INSERT나 UPDATE, DELETE 문장의 처리가 느리다.
• 다만, 빠른 SELECT가 가능하다.

인덱스를 하나 더 추가할지 말지는 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하느냐에 따라 결정해야 한다.

2. B-Tree Index

• B-Tree의 B는 Binary가 아닌 Balanced 이다.
• 원래 값을 변형시키지 않고, 인덱스 구조체 내에서는 항상 정렬된 상태를 유지한다.

구조 및 특성

• 트리 구조의 최상위에 하나의 루트노드가 존재하고 그 하위에 자식 노드가 붙어 있는 형태
• 가장 하위에 있는 노드를 리프 노드(Leaf Node)
• 루트 노드도 아니고 리프 노드도 아닌 중간의 노드를 브랜치 노드(Branch Node)라고 한다.
• 인덱스와 실제 데이터가 저장된 데이터는 따로 보관된다.
• 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.
• 인덱스의 키 값은 모두 정렬돼 있지만, 데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서로 저장돼 있다.
• INSERT된 순서로 저장되는건 아님 → DELETE된 공간을 재활용하도록 설계되어 있기 때문

데이터 파일에서 레코드는 특정 기준으로 정렬되지 않고 임의의 순서로 저장된다. 하지만 InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되므로 기본적으로 PK 순서로 정렬된다.

Index 추가

• B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree 상의 적절한 위치를 검색해야 한다.
• 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다.
• 리프 노드가 꽉 찼을 때는 Split 돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다.
• 따라서 B-Tree는 쓰기 작업에 비용이 많이 드는 것으로 알려졌다.

대략적인 성능 계산 법

• 추가 작업 비용을 1이라고 가정
• 인덱스 키 추가하는 작업 비용 = 1.5
• 인덱스가 3개인 경우 (1.5*3 + 1) = 5.5
• 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 해서 걸리는 시간이다.

Index 제거

• 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 된다.
• 삭제 마킹된 인덱스 키 공간은 방치하거나 재활용할 수 있다.

Index 변경

• B-Tree의 키 값이 변경되는 경우에는 단순히 인덱스상의 키 값만 변경하는 것은 불가능하다.
• B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다.

Index 검색

• B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행한다.
• B-Tree인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있다.
• 부등호 비교 조건에서도 인덱스를 활용할 수 있지만, 인덱스를 구성하는 키 값의 뒷부분만 검색하는 용도로는 사용할 수 없다.
• 변형된 경우는 인덱스 사용 불가능
• InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키락이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현되어 있다.
• 따라서 UPDATE나 DELETE 문장이 실행될 때 적절한 인덱스가 없으면, 불필요하게 많은 레코드를 잠근다.

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

• 인덱스를 구성하는 칼럼의 크기, 레코드의 건수, 유니크한 인덱스 키값의 개수 등에 의해 성능에 영향을 받는다.

Index 값의 크기

• 디스크에 데이터를 저장하는 가장 기본 단위를 Page라고 부름
• 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위
• 페이지는 버퍼 풀에서 데이터를 버퍼링하는 기본 단위
• 인덱스도 결국 Page단위로 관리되며, 루트와 브랜치 그리고 리프 노드를 구분한 기준이 바로 Page 단위
• B-Tree는 자식 노드의 개수가 가변적인 구조다.
• 인덱스의 페이지 크기와 키 값의 크기에 따라 자식 노드의 갯수가 결정된다.

SELECT 쿼리가 레코드 500개를 읽어야 한다면 인덱스 페이지 한 번으로 해결될 수도 있지만, 최소한 2번 이상 디스크로부터 읽어야 할 수 있다.

인덱스를 구성하는 키 값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 느려진다.

• 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미
• 버퍼풀의 크기는 제한적이기 때문에 메모리에 캐시해 둘 수 있는 레코드 수가 줄어들고, 메모리의 효율이 떨어진다.

선택도(기수성)

• 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미
• 전체 인덱스 키 값 : 100개, 유니크한 값의 수 : 10 ⇒ 기수성 = 10
• 중복된 값이 많아질수록 기수성은 낮아지고 동시에 선택도 또한 떨어진다.
• 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

읽어야 하는 레코드의 건수

• 인덱스를 통해 레코드를 읽는 것은 바로 레코드를 읽는 것 보다 높은 비용이 드는 작업이다.
• 인덱스를 통해 레코드 1건을 읽는 것이 직접 레코드 1건을 읽는 것보다 4~5배 정도 비용이 더 많이 든다.
• 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 직접 읽어서 필터링 방식으로 처리하는 것이 효율적이다.

4. Index를 이용한 데이터 읽기

Index Range Scan

• 인덱스의 접근 방법 가운데 가장 대표적인 접근 방식
• 검색해야 할 인덱스의 범위 가 결정됐을 때 사용하는 방식 ( Ex BETWEEN)
• 검색하려는 수나 검색 결과 레코드 건수와 관계없이 레인지 스캔이라 함.
• 시작해야 할 위치를 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 된다.
• 만약 스캔 중 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔한다.
• 인덱스 레인지 스캔 중 조건에 맞는 컬럼을 디스크에서 읽어 와야 하므로 랜덤 I/O가 레코드 마다 발생한다.

1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다. → 인덱스 탐색
2. 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 쭉 읽는다. → 인덱스 스캔
3. 2번에서 읽어 들인 인덱스 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽어 온다.

커버링 인덱스로 처리되는 쿼리는 디스크의 레코드를 읽지 않아도 된다. → 랜덤 I/O 발생 X

Index Full Scan

• 인덱스 레인지 스캔과 마찬가지로 인덱스를 사용하지만, 인덱스의 처음부터 끝까지 모두 읽는 방식
• 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다.
• Ex. (A, B, C) 인덱스 → Where절 B, C
• 인덱스의 크기는 테이블의 크기보다 작으므로 직접 테이블을 처음부터 끝까지 읽는 것보다는 인덱스만 읽는 것이 효율적

인덱스 리프 노드의 제일 앞 또는 제일 뒤로 이동한 후, 리프 노드를 연결하는 Linked List를 따라서 처음부터 끝까지 스캔하는 방식

인덱스 레인지 스캔보다는 빠르지 않지만, 테이블 풀 스캔보다는 효율적
→ 인덱스에 포함된 칼럼만으로 쿼리를 처리할 수 있는 경우 테이블의 레코드를 읽을 필요가 없기 때문

루스 인덱스 스캔

• 오라클 DBMS의 인덱스 스킵 스캔과 작동 방식이 비슷
• Index Range Scan, Index Full Scan은 루스 인덱스 스캔과는 상반된 의미에서 타이트 인덱스 스캔으로 분류
• 느근하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미
• 인덱스 레인지 스캔과 비슷하게 작동하지만 중간에 필요치 않은 인덱스 키 값은 무시
• GROUP BY 또는 MAX(), MIN() 함수에 대해 최적화를 하는 경우에 사용.

인덱스 스캔 방향

해당 쿼리를 실행하기 위해 인덱스를 처음부터 오름차순으로 끝까지 읽어 가장 큰 값 하나를 가져오는게 아니다.

인덱스는 항상 오름차순으로 정렬돼 있지만 인덱스를 최솟값부터 읽으면 오름차순으로 값을 가져올 수 있고, 최댓값부터 거꾸로 읽으면 내림차순으로 값을 가져올 수 있다.

인덱스를 역순으로 접근해 첫 번째 레코드만 읽는다.

mysql > SELECT * FROM employees ORDER BY first_name DESC LIMIT 1;

• 인덱스를 사용하는 시점에 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬 효과를 얻을 수 있다.

내림차순 인덱스

내림차순과 오름차순이 혼합된 경우에는 내림차순 인덱스로만 해결될 수 있다.

CREATE INDEX ix_teamnave_userscore ON employess ( team_name ASC, user_scroe DESC);

first_name 칼럼을 역순으로 정렬하는 요건만 있다면 다음 2개 인덱스 중에서 어떤 것을 선택할까?

오름차순 인덱스 : 작은 값의 인덱스 키가 B-Tree의 왼쪽에 정렬된 인덱스

내림차순 인덱스 : 큰 값의 인덱스 키가 B-Tree의 왼쪽에 정렬된 인덱스

인덱스 정순 스캔 : 인덱스 리프 노드의 왼쪽 페이지부터 오른쪽으로 스캔

인덱스 역순 스캔 : 인덱스 리프 노드의 오른쪽 페이지부터 왼쪽으로 스캔

역순 정렬 쿼리가 정순 정렬 쿼리보다 28.9% 시간이 더 걸린다.

→ 정순 스캔과 역순 스캔은 페이지 간의 Double Linked LIst를 통해 Forward하느냐 Backward하느냐의 차이만 있지만, 다음 두 가지 이유가 있다.

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

페이지 잠금과 관련된 kakao tech 블로그
-> https://tech.kakao.com/2018/06/19/mysql-ascending-index-vs-descending-index/

---

RealMySQL 8.0