Index(인덱스)에 대해서 알아보자

Real MySQL 책을 공부하면서 정리한 내용입니다.

데이터베이스의 성능 튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건일때가 상당히 많다.

💡 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 오래 걸린다.

그래서 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 삼아 인덱스를 만들어 둔다.

그리고 칼럼의 값을 주어진 순서로 미리 정렬해서 보관한다.

💡 조회 요청 시, 데이터가 정렬되어 있기 때문에 빨리 원하는 값을 찾아올 수 있다. (SELECT)

🚨 데이터가 저장될 때 마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리다. ( INSERT · UPDATE · DELETE )

데이터 저장 방식 별로 구분하면, 대표적으로 B-Tree 인덱스와 Hash 인덱스로 구분할 수 있다.

B-Tree (Balanced-Tree) 인덱스

B-Tree는 칼럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태로 유지한다.

출처 : https://velog.io/@ddongh1122/MySQL-B-Tree-%EC%9D%B8%EB%8D%B1%EC%8A%A4#4-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EC%8A%A4%ED%82%B5-%EC%8A%A4%EC%BA%94

B-Tree는 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식 노드가 붙어있는 형태이다.

트리 구조의 가장 하위에 있는 노드를 리프 노드라 하고 중간의 노드를 브랜치 노드라고 한다.

리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.

검색하려는 인덱스와 저장되어 있는 인덱스 레코드를 비교하면서, 가리키는 하위 페이지로 계속 이동하고

루트 노드에 도달해, 검색하려는 인덱스와 일치하는 레코드를 발견하고,

해당 인덱스가 키로서 값을 갖고 있는 레코드 주소로 찾으려는 데이터에 접근하게 된다.

📌 인덱스 키 추가 및 삭제

1️⃣ 인덱스 키 추가

새로운 인덱스가 B-Tree 에 저장될 때는 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색해야 한다.

저장될 위치가 결정되면 레코드의 키값과 해당 레코드의 주소값을 리프 노드에 저장한다.

🚨 리프 노드가 꽉 찬 경우, 리프 노드가 분리되어야 한다. 이때 상위 브랜치 노드까지 처리해야 하므로 비용이 많이 발생한다.

2️⃣ 인덱스 키 삭제

삭제하려는 인덱스를 키 값으로 하는 리프 노드를 찾아 삭제한다.

삭제 된 공간은 방치하거나 재활용할 수 있다.

3️⃣ 인덱스 키 변경

인덱스를 변경하는 작업은 해당 리프 노드를 찾아서 변경하는 것으로 해결되지 않는다.

다시 인덱스를 정렬해야하기 때문이다.

따라서, 변경 과정은 변경하려는 인덱스를 키 값으로 하는 리프 노드를 찾아 삭제한 후 변경할 인덱스를 새로 추가하는 방식으로 진행된다.

4️⃣ 인덱스 키 검색

B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있다.

InnoDB 스토리지 엔진의 경우 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있다.

따라서, 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠글 수 있기 때문에 인덱스의 설계가 중요하고 많은 부분에 영향을 미친다.

📌 인덱스 사용에 영향을 미치는 요소

1️⃣ 인덱스 키 값의 크기

InnoDB 스토리지 엔진은 디스크에 페이지 단위로 관리한다.

버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 하다.

인덱스도 페이지 단위로 관리된다.

💡 따라서, 인덱스 자체의 크기는 페이지에 인덱스가 몇개 들어갈 수 있는지를 결정한다.

🚨 인덱스 키 크기가 커질 수록 한 페이지에 수용할 수 있는 인덱스의 양이 줄어들고, 이는 특정 조건에서 디스크 접근을 추가적으로 하도록 만들 수 있다.

따라서, 가능하면 인덱스 키 값의 크기는 작게 만드는 것이 좋다.

2️⃣ 선택도

선택도(Selectivity) 또는 기수성(Cardinality)는 거의 같은 의미로 사용되며,

모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다.

선택도가 높을 수록 (중복 데이터가 적을 수록) 효율적으로 처리할 수 있다.

검색하려는 인덱스와 일치하는 레코드를 모두 읽은 뒤 추가적인 조건에 만족하는 레코드를 찾으므로,

중복되는 인덱스가 많아질 수록 성능이 떨어지게 된다.

3️⃣ 레코드 건수

일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이

테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도 비용이 더 많이 드는 작업인 것으로 예측한다.

💡 따라서, 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않는 것이 효율적이다.

📌 인덱스 스캔 방식

1️⃣ 인덱스 레인지 스캔

SELECT * FROM employees WHERE first_name BETWEEN 'Ebbe' AND 'Gad';

위와 같이 first_name 이 인덱스 칼럼일 때, 범위로 검색하는 쿼리가 있을 수 있다.

이 경우 인덱스 레인지 스캔을 사용한다.

위와 같이, 시작해야 할 위치를 찾으면 레코드를 순서대로 읽는다.

순서대로 읽다가 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다.

🚨 단, 인덱스 페이지 상으로는 정렬되어 있지만, 레코드 주소는 정렬되어 있지 않다.

따라서, 지금까지 읽은 쿼리를 사용자에게 반환할때, 랜덤 디스크 I/O가 레코드 1건당 1번 발생한다.

2️⃣ 인덱스 풀 스캔

인덱스의 처음부터 끝까지 모두 읽는 방식이다.

대표적으로, 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 사용된다.

예로, 인덱스가 (A, B, C) 순서로 만들어져있을 때, 쿼리의 조건절이 B나 C 칼럼으로 검색하는 경우이다.

🚨 단, 레코드 건 수가 적은 경우 인덱스를 사용하면 오버헤드가 발생하므로, 테이블 전체를 스캔하는게 효율적일 수 있으며

이전에 설명했듯이 전체 테이블의 25%를 넘어가는 스캔인 경우 인덱스 스캔이 비효율적일 수 있다.

3️⃣ 루스(Loose) 인덱스 스캔

느슨하게 듬성듬성 인덱스를 읽는 것을 의미한다.

주로 GROUP BY 또는 MAX() , MIN() 함수에 대해 최적화를 하는 경우에 사용된다.

위 그림의 경우, dept_no 와 emp_no 컬럼이 인덱스로 사용되는데,

SELECT dept_no, MIN(emp_no) FROM dept_emp WHERE dep_no BETWEEN 'd001' AND 'd004' GROUP BY dept_no;

위와 같은 쿼리의 경우, 각 인덱스 루트 페이지의 첫 번째 레코드만 가져오면 되므로 루스 인덱스 스캔을 할 수 있다.

위와 같이, 루스 인덱스 스캔을 사용하려면 제약 조건이 필요하다.

4️⃣ 인덱스 스킵 스캔

인덱스를 (A,B) 로 설정하면, WHERE 조건절에 B만 사용하는 쿼리는 인덱스를 사용할 수 없다.

하지만, MySQL 8.0 부터는 B 만으로도 인덱스 검색이 가능하게 해주는 인덱스 스킵 스캔 최적화 기능이 도입되었다.

// 인덱스가 (gender, birth_date) 일 때
SELECT gender, birth_date FROM employees WHERE birth_date >= '1970-01-01';

위 쿼리는 인덱스 스킵 스캔이 없다면, 인덱스 페이지 풀 스캔을 한다.

하지만, 인덱스 스킵 스캔을 하는 경우 아래와 같다.

위 처럼, 인덱스 풀 스캔을 하는 것이 아닌

SELECT gender, birth_date FROM employees WHERE gender = 'M' and birth_date >= '1905-02-01';

SELECT gender, birth_date FROM employees WHERE gender = 'F' and birth_date >= '1965-02-01';

위와 같은 쿼리 2개를 실행한 것과 비슷한 형태의 최적화를 하게 된다.

🚨 단, 선행 인덱스의 선택도가 너무 높으면 스캔 시작점을 너무 많이 검색해야해서 성능이 떨어질 수 있다. (최적화된 쿼리 갯수가 늘어난다.)

그리고 인덱스로 지정된 컬럼으로 처리 가능한 쿼리여야 최적화를 할 수 있다.

( SELECT * FROM 을 해버리면 인덱스로 지정된 컬럼 외에 다른 컬럼도 필요해지므로 인덱스 스킵 스캔을 사용할 수 없다.)

📌 B-tree 인덱스 정렬과 성능

MySQL 8.0 부터는 정렬 순서를 혼합한 인덱스를 생성할 수 있다.

CREATE INDEX ix_index ON employees (column1 ASC , column2 DESC);

위와 같이 인덱스를 설정할 칼럼에 정렬 방법을 명시하면 된다.

❓ 만약 오름차순으로 설정한 인덱스를 역순으로 정렬해서 레코드 1건을 조회하는 쿼리는 어떻게 실행될까?

💡 인덱스 생성 시, 오름차순으로 설정했기 때문에 오름차순으로 쭉 읽다가 마지막 레코드를 읽는 것이 아니라

옵티마이저는 인덱스를 역순으로 접근한 뒤, 첫번째 레코드만 읽어오도록 한다.

❓ 그렇다면 성능은 동일할까?

생각해보자.

id 칼럼이 오름차순인 인덱스라고 가정하면, 전체 레코드 조회 시 순서대로 읽으면 된다.

그리고 역순으로 조회 요청을 했을때는 옵티마이저가 인덱스를 기준으로 뒤에서부터 조회하도록 할 것이다.

실험 결과, 1천 2백여만 건을 스캔했을 때, 약 1.2초 정도 차이가 나는 것을 확인할 수 있다.

약 28.9% 더 시간이 걸리는 것이다.

이러한 성능 차이가 발생하는 이유는 다음과 같다.

위와 같이, 페이지 내에서 인덱스 레코드는 단방향으로 연결된 구조이다.

따라서, 초기에 설정한 인덱스의 방향의 반대되는 질의를 하면, 추가적인 비용이 발생하는 것이다.

전문 검색 인덱스

B-Tree 인덱스는 전체 일치 또는 좌측 일부 일치와 같은 검색만 가능하다.

문서의 내용 전체를 인덱스화해서 특정 키워드가 포함된 문서를 검색하는 전문 검색에는 사용할 수 없다.

전문 검색을 위한 인덱스는 B-Tree 인덱스가 아닌

💡 문서 전체에 대한 분석과 검색을 위한 인덱싱 알고리즘을 적용한 전문 검색 인덱스를 사용해야 한다.

📌 n-gram 알고리즘

n-gram에서 n은 인덱싱할 키워드의 최소 글자 수를 의미하고, 이 글자수를 단위로 키워드를 쪼개서 인덱싱하는 방식이다.

That is the question

위와 같은 문장이 있을 때, 2-gram 알고리즘을 사용하면

That	Th	ha	at
is	is
the	th	he
question	qu	ue	es	st	ti	io	on

위와 같이 단어 2개로 쪼개어 토큰으로 만들고, 검색에서 가치가 없는 단어들을 필터링해서 제거한다.

그리고 남은 토큰들을 인덱스로 저장한다.

📌 전문 검색 인덱스 사용 조건

전문 검색 인덱스를 사용하기 위해서는

SELECT * FROM tb WHERE MATCH(doc_body) AGAINST('애플' IN BOOLEAN MODE);

위와 같이 MATCH() .. AGAINST() 문법을 사용해야한다.

위 문접을 사용하지 않으면, 풀 테이블 스캔으로 쿼리가 처리될 수 있다.