Index

SQL 성능은 여러 가지 요소가 결합된 결과이겠지만 Disk I/O와 밀접한 연관이 있다. 특히 종류에 따라 Sequential, Random I/O의 성격도 달라지고 속도도 달라진다. 보통 쿼리 튜닝은 이 I/O를 줄이는데 큰 목적을 둔다.

인덱스는 책 뒤쪽 색인 페이지와 유사하다. 우리는 색인으로 모든 페이지를 순회하지 않고 원하는 내용을 찾을 수 있다. 물론 이 색인이 만능은 아니다. 미리 정렬하고 정리해놓는 과정이 필요하다.

DBMS에서 인덱스는 이와 같다. INSERT, UPDATE, DELETE의 성능을 조금 포기하더라도 읽기에서 성능을 높이는 기능이다. 인덱스는 관리 방식과 중복 허용 등에 따라 PrimaryKey, SecondaryKey로 구분할 수 있다.

  1. PK : 레코드를 대표하는 컬럼 값으로 만들어진 인덱스. 식별자라고 부른다.
  2. SK : PK를 제외한 나머지 모든 인덱스 (유니크는 PK를 대체할 수 있다고 해서 대체 키라고도 부른다.)

알고리즘으로 분류하면

  1. B-Tree : 일반적 알고리즘 컬럼 값 변형 없이 인덱싱한다.
  2. Hash : 컬럼 값으로 해시 값을 계산하는 알고리즘 (전방 일치등으로 검색 불가)
  3. Fractal-Tree
  4. Merge-Tree

등이 있다.

B-Tree

B 트리의 B는 Balanced라고 한다. 원래 값 변형 없이 인덱스 구조체 내에서는 항상 정렬된 상태로 유지된다.

루트 노드가 존재하고 자식 노드가 붙여있는 형태다. (브랜치 노드 + 리프 노드) 리프 노드는 실제 데이터 레코드의 주소 값을 가지고 있다. 여기서 인덱스는 정렬되어 있지만 레코드는 정렬되어 있지 않다. (InnoDB에서는 PK 순서로 정렬되어 저장된다. -> 클러스터링 영향이 있다.)

추가

TableStorageEngine에 따라 새로운 키 값이 인덱스에 저장될 수도 있고 아닐 수도 있다. B-Tree라면 적절한 위치를 찾아서 정하는 과정이 필요하다. 혹여나 리프 노드가 꽉 차면 리프 노드가 분리되고 이는 상위 노드로도 전파될 수 있다. 그렇기 때문에 인덱스 추가 작업에 비용이 크다.

InnoDB는 지연처리를 기본으로 한다. 물론 PK, UQ는 중복 체크가 필요하므로 즉시 B-Tree를 수정한다.

삭제

간단하다. 리프 노드를 찾아 삭제 마킹으로 끝낸다. 이 부분 역시 지연처리가 가능하다.

변경

변경은 불가능하다. 삭제 -> 추가 순으로 진행된다. InnoDB를 사용한다면 위 작업 모두 체인지 버퍼를 이용해서 지연 처리된다.

검색

루트 노드부터 조건에 맞는 노드로 트리 탐색을 진행한다.

중요성

InnoDB 인덱스는 꽤 중요하다. 레코드 잠금, 넥스트 키락(갭락)을 할 때 인덱스를 잠그고 레코드를 잠그는 방식으로 구현되어 있다. 따라서 Update, Delete에서도 인덱스가 없으면 심하면 모든 레코드를 잠글 수도 있다.

크기

InnoDB는 디스크에 데이터를 저장하는 기본 단위를 Page 혹은 Block으로 한다. 읽기/쓰기의 최소 단위가 된다. 또한 버퍼 풀에서 데이터 버퍼링 기본 단위가 되기도 한다. B-Tree에서 자식 노드를 가질 수 있는 수 역시 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다. 인덱스 키 값이 커지면 여러 번 인덱스 페이지를 읽게 되고 I/O 횟수가 늘면서 느려질 수 있다. 또한 인덱스 크기가 커질수록 메모리에 캐시해 둘 수 있는 레코드 수가 줄어든다.

깊이

B-Tree 깊이는 Random I/O 횟수와 직결된다. 이 역시 키 값의 크기에 따라 좌우된다.

Cardinality

Cardinality가 높으면 중복도가 낮게 되고, 검색 대상을 효율적으로 좁힐 수 있게 된다. 이는 성능에 영향을 미친다.

Scan

인덱스를 거치지 않고 레코드를 읽는 작업은 비용이 큰 작업이다. 예를 들어 100건을 다 읽고 50만 건을 버릴지 인덱스를 통해 50만건만 읽을지는 천지차이다. 물론 인덱스를 통해서 읽어야 할 레코드 건수가 전체 레코드의 20 ~ 25%를 초과하면 인덱스를 이용하지 않는게 효율적일 수도 있다.

Range

인덱스 레인지 스캔은 검색해야할 인덱스의 범위가 결정됐을 때 사용하는 방식이다. 인덱스가 정렬되어 있다는 특징을 이용해서 필요한 부분을 추려서 Disk I/O를 발생시킨다. 이 부분은 랜덤이다. 위에서 20 ~ 25%가 넘으면 비효율이라고 한 것이 풀스캔을 하면 순차 읽기가 된다. 따라서 인덱스 -> 데이터보다. 데이터 풀 스캔이 저렴할 수 있다.

여튼 레인지 스캔을 자세히 살펴보면

  1. 인덱스에서 조건메 만족하는 값이 저장된 위치를 찾는다( 인덱스 탐색 )
  2. 1에서 찾은 부분부터 필요한 만큼 읽는다.( 인덱스 탐색 )
  3. 2번에 읽은 인덱스 키-레코드 주소로 레코드가 저장된 페이지를 읽고 최종 레코드를 읽는다.

3번은 커버링 인덱스로 처리되면 디스크의 레코드를 읽지 않아도 된다.

  • 커버링 인덱스: 쿼리를 충족시키는데 필요한 모든 데이터를 갖고 있는 인덱스

FullScan

인덱스를 사용하긴하지만 처음부터 끝까지 모두 읽는 방식을 풀 스캔이라고 한다. 예를 들어 인덱스가 (A, B, C) 컬럼으로 설정됐는데 검색 조건이 (B, C)인 경우가 이 예에 해당한다.

쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우 이 방식이 채택된다. 레코드까지 읽어야 한다면 절대 이 방식으로 처리되지 않는다.

Loose Scan

인덱스 스킵 스캔과 비슷하다. 위의 두 스캔은 tight 스캔으로 분류된다. 루스 인덱스 스캔은 말 그대로 느슨하게 인덱스를 읽는 것을 의미한다. 중간에 필요치 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리된다.

예시)

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

-- 첫 번쨰 emp_no만 읽으면 되기 떄문에 between을 모두 검색할 필요가 없기에 옵티아마이저가 만족하지 않는 레코드는 무시한다.

Skip Scan

인덱스의 핵심은 값이 정렬되어 있다는 것이다. 때문에 인덱스 구성하는 컬럼 순서가 중요하다. 예를 들어 인덱스가 (A, B)로 잡혀있고 where에 B만으로 검색하면 A로 정렬 -> B로 정렬 순이기 떄문에 인덱스를 사용하지 못했다. 따라서 인덱스를 사용하려면 A, B 에 대해서 순서대로 조건이 있어야만 했다.

8.0에서는 컬럼을 건너뛰어서 B만으로 인덱스 검색이 가능하게 해주는 SkipScan이 도입됐다. 일전에는 B만으로 검색하면 Index FullScan을 동반했다. 이후에는 이를 range로 처리한다. 또한 Extra에는 Using index for skip scan이 명시된다.

내부적으로 어떻게 처리는지 보면 A가 있다고 가정하고 쿼리를 여러 번 실행해서 rangeScan을 만드는 식으로 최적화를 시도한다.

select ~ where a = 1 and b >= ...
select ~ where a = 2 and b >= ...

그러나 여기서 맹점은 A(선행 컬럼)의 값이 유니크한 개수가 많으면 쿼리 개수가 늘어나서 비효율이 된다는 점, 쿼리가 커버링 인덱스로 처리되어야 한다는 점이 있다. 만일 인덱스에 명시된 내용이 아닌 다른 부분 (* 같은)도 호출하면 결국 인덱스 스킵 스캔을 사용하지 못하고 풀 테이블 스캔을 초래하게 한다.

MultiColumn

실제 사용에서는 인덱스에 하나의 컬럼만을 잡는 경우는 드물다. 다중 컬럼 인덱스(Concatenated Index)라고 한다. 특징은 컬럼 순서에 맞춰서 뒤쪽 순서 컬럼은 앞쪽 컬럼에 의존해서 정렬되어 있다는 것이 특징이다.

스캔 방향

인덱스는 오름/ 내림 차순으로 정렬할 수 있다. 논리적으로는

  1. ASC : 작은 인덱스 키가 B-Tree 왼쪽으로 정렬
  2. DESC : 큰 인덱스 키가 B-Tree 왼쪽으로 정렬

이다. 스캔을 살펴보면

  1. FORWARD : 인덱스 리프 노드의 왼쪽 페이지부터 오른쪽으로 스캔
  2. BACKWARD : 인덱스 리프 노드의 오른쪽 페이지부터 왼쪽으로 스캔

사실 별 차이가 없어 보인다. InnoDB에는 페이지 블록 간의 DoubleLinekdList를 앞으로 순회하냐, 뒤로 순회하냐의 차이로 보인다. 그러나 실제로 내부적으로 역순 스캔이 정순 스캔보다 느리다.

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

효율성과 가용성

WHERE, GROUP BY, ORDER BY가 어떤 경우에 인덱스를 사용할 수 있고, 어떻게 사용하는지를 알아야 쿼리를 최적화할 수 있다. 역으로 쿼리에 맞게 인덱스를 설계할 수 있다.

예시로 동등(=)인지 크다(>)인지 작다(<)인지에 따라서 인덱스 활용 형태가 달라지며, 효율도 달라진다. 또한, WHERE의 순서에 따라서도 인덱스 활용 정도가 달라진다.

효율성

SELECT * FROM dept_emp
WHERE dept_no='d0002' AND emp_no >= 10114;

-- A (dept_no, emp_no)
-- B (emp_no, dept_no)

라고 하면 같은 쿼리라고 해도 A는 ` dept_no=’d0002’ AND emp_no >= 10114`인 레코드를 찾고 dept_no가 d0002가 아닐 때까지 읽으면 된다. emp_no가 dept_no에 의존해서 정렬되어 있으니 dept_no에서 d0002 내부에서 emp_no가 순서대로 정렬되어 있다.

B는 emp_no >= 10114 AND dept_no='d0002'로 찾고 dept_no를 매 번 비교해야 한다. emp_no가 순서대로 정렬되어 있고 emp_no가 같은 경우 dept_no가 순서대로 정렬되어 있기 때문이다.

A와 같이 인덱스가 작업 범위를 결정하는 경우 작업 범위 결정 조건이라고 한다. B의 경우 비교 작업 범위를 줄이지 못하고 필터링만 하기 때문에 필터링 조건이라고 표현한다.

가용성

B-tree는 이전 컬럼에 종속되어 다음 컬럼이 정렬되어있다는 것을 이해하는 것이 중요하다. 여러 컬럼이든 하나든 말이다. (하나면 글자 순서로 생각해도 될 것 같다.) 예를 들어 하나의 인덱스라면 %mer로 검색하면 왼쪽 부분이 고정되지 않아서 인덱스 효과를 받지 못한다. 여러 컬럼이라면 (a, b)일 때 a를 검색 조건으로 걸지 않으면 인덱스 효과가 감소한다.

판단

아래의 경우는 인덱스를 작업 범위 결정 조건이 아닌 체크 조건으로 사용하는 경우다.

  1. NOT-EQUAL( ‘<>’, ‘NOT IN’, ‘NOT BETWEEN’, ‘IS NOT NULL’ )
  2. LIKE ‘%??’
  3. STORED FUNCTION, 다른 연산자로 인덱스 변형 후 비교할 경우
  4. NOT-DETERMISTIC 속성의 STORED FUNCTION이 비교 조건일 경우( 매 번 새로 연산 )
  5. 데이터 타입이 다른 비교
  6. 문자열 데이터 콜레이션이 다른 경우

R-Tree

공간 확장(Spatial Extension)을 이용하면 필용적으로 R-Tree를 맞닥뜨리게 된다.

SpatialExtension

  • 공간 데이터를 저장할 수 있는 데이터 타입
  • 공간 인덱스 (R-Tree)
  • 공간 연산 함수

R-Tree는 MBR(Minimum Bounding Rectangle)의 포함 관계를 B-Tree 형태로 구현한 인덱스이다.

용도

ST_CONTAINS(), ST_WITHIN() 같이 포함 관계를 비교하는 함수로 검생하는 경우에만 인덱스를 사용할 수 있다.

FullText

문서의 내용 전체를 인덱스화해서 특정 키워드가 포함된 문서를 검색하는 FullText 검색에는 B-Tree를 사용할 수 없다. 이 경우를 FullTextSearch 인덱스라고 한다. 전문 검색에서는 문서 본문의 내용에서 사용자가 검색하게 될 키워드를 분석해내고, 빠른 검색용으로 사용할 수 있게 이러한 인덱스를 구축한다. 어근분석, n-gram 분석 알고리즘으로 나뉜다.

가용성

전문 검색 인덱스를 사용하려면 반드시 두 가지 조건을 갖춰야 한다.

  1. 쿼리 문장이 저눔ㄴ 검색을 위한 문법( MATCH … AGAINST …)를 사용한다.
  2. 테이블이 전문 검색 대상 컬럼에 대해서 전문 인덱스를 보유한다.

함수 기반

컬럼 값을 변형해서 만들어진 값에 대해 인덱스를 구축해야할 때도 있다.

  1. 가상 컬럼
  2. 함수를 이용한 인덱스

가상 컬럼

8.0부터 가상 컬럼을 추가하고 그 가상 컬럼에 인덱스를 생성할 수 있게 됐다.

ALTER TABLE ~ 
    ADD full_name VARCHAR(30) AS (CONCAT(first_name, ' ', last_name)) VIRTUAL,
    ADD INDEX ix_fullname (full_name);

함수

5.7에는 함수를 직접 인덱스 생성에서 사용할 수 없었다.

CREATE TABLE ~ (
    user_id BIGINT,
    first_name VARCHAR(10),
    last_name VARCHAR(10),
    ...,
    INDEX ix_fullname ((CONCAT(first_name, ' ', last_name)))
)

멀티 밸류

multi-value 인덱스는 하나의 데이터 레코드가 여러 개의 키를 가질 수 있는 형태의 인덱스다.

클러스터링 인덱스

클러스터링이랑 여러 개를 하나로 묶는다는 의미로 주로 사용한다. MySQL은 테이블 레코드를 비슷한 것들끼리 묶어서 저장하는 형태로 구현한다. 클러스터링 인덱스는 테이블의 프라이머리 키에 대해서만 적용되는 내용이다. 위의 설명과 같이 PK를 묶어서 저장하는 것을 클러스터링 인덱스라고 한다. PK에 따라 저장 위치가 결정된다는 것이다. 혹여나 키 값이 변경되면 그 레코드의 물리적인 저장위치가 바뀐다는 의미다. 그러면 PK가 없는 InnoDB 테이블은 어떻게 클러스터링 테이블이 될까?

  1. PK가 있으면 PK를 클러스터링 키로 선택
  2. NOT NULL 옵션의 UQ 중 첫 번째 인덱스를 클러스터링 키로 선택
  3. 내부적 PK를 추가하고 클러스터링 키로 선택

세컨더리 인덱스와의 관계

SecondaryIndex에도 영향을 미칠 수 있다. InnoDB의 모든 세컨더리 인덱스는 레코드 저장 주소가 아닌 PK 값을 저장하도록 되어 있다.

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

  1. 장점
    • PK를 범위 검색하는 경우 빠름
    • SecondaryIndex가 PK를 가지고 있기에 인덱스만으로 처리될 수 있는 경우가 많다.
  2. 단점
    • SecondaryIndex가 클러스터링 키를 갖기 때문에 클러스터링 키 값의 크기가 클 경우 전체적으로 인덱스의 크기가 커짐
    • SecondaryIndex으로 검색하면 PK로 다시 한 번 검색해야 하므로 처리 성능이 느림
    • INSERT 시 레코드 저장 위치가 결정되기에 처리 성능이 느림
    • PK를 변경할 때 DELETE -> INSERT 해야 하므로 성능이 느림

주의 사항

  1. 클러스터링 인덱스 키의 크기
    • SecondaryIndex가 PK를 포함하므로 PK크기가 커지면 SecondaryIndex도 커진다.
  2. PK는 명시할 것
    • AUTO_INCREMENT 컬럼을 이용해서라도 PK를 사용하는 것이 좋다. 그렇지 않으면 InnoDB가 내부적으로 추가하는데, 이러면 사용자가 이 컬럼에 접근할 수 없다.

Unique

유니크와 아닌 경우 인덱스 구조상 차이점이 없다.

인덱스 읽기

읽기는 별차이가 없다. 유니크하냐 아니냐는 몇 개를 더 읽어야 하는가의 차이일 뿐이다.

쓰기

중복된 값이 있는지 없는지를 체크해야 하므로 한 단계가 더 붙는다. 중복 체크시 읽기 잠금을 하고, 쓰기할 때는 쓰기 잠금을 사용한다. 떄문에 데드락이 빈번히 발생한다. 또한 InnoDB는 인덱스 키의 저장을 버퍼링하기 위해서 ChangeBuffer가 사용된다. Unique는 중복 확인이 필요하기에 작업을 버퍼링 할 수 없다.

ForeignKey

외래키 제약이 설정되면 자동으로 생성된다. InnoDB 외래키는 아래의 특징이 있다.

  1. 테이블 변경이 발생하는 경우만 잠금 경합이 발생
  2. 외래키와 연관되지 않은 컬럼의 변경은 최대한 잠금 경합을 발생시키지 않는다.

자식 테이블의 외래 키 컬럼의 변경은 부모 테이블 확인이 필요하다. 이 상태에서 부모 테이블의 해당 레코드에 쓰기 잠금이 걸려있으면 잠금 해제까지 기다린다.

반대로 부모가 삭제되면 자식에 대한 레코드 잠금이 해제될까지 기다린다.