README.md

인덱스 (5.1 ~ 5.4)

5.1 디스크 읽기 방식

데이터베이스의 성능 튜닝은 디스크 I/O를 줄이는 것과 많은 관련이 있다.

5.1.1 저장 매체

일반적으로 서버에서 사용되는 저장 매체는 아래와 같다.

• DAS(Direct Attached Storage)

• NAS(Network Attached Storage)

• SAN(Storage Area Network)

DAS는 독자적으로 사용이 불가능하고 컴퓨터 본체에 연결을 해야만 사용할 수 있다. 성능은 일반적인 PC의 내장 디스크와 비슷하고 여러 컴퓨터가 동시에 공유하는 것은 불가능하다. 이런 문제점을 해결하기 위해 주로 NAS 또는 SAN를 사용한다.

DAS는 SATA와 같은 케이블로 여러 컴퓨터와 동시에 연결 가능하고 NAS는 TCP/IP 방식으로 연결된다. NAS는 네트워크로 연결되는 만큼 SAN보다는 조금 속도가 느리다. SAN는 DAS로는 구축할 수 없는 대용량 스토리지 공간을 제공하는 장치이다. 다만 설비에 큰 비용이 드는 단점이 있다. NAS는 앞서 말한 것처럼 속도가 느리다. 그래서 데이터베이스 서버와 같이 읽기, 쓰기 작업이 잦은 용도로는 거의 사용되지 않는다. 위 저장 매체들은 대부분 디스크 드라이브의 플래터를 회전시켜 데이터를 읽고 쓰는 기계적인 방식을 사용한다.

5.1.2 디스크 드라이브와 솔리드 스테이트 드라이브

디스크 드라이브의 느린 속도를 보완하기 위해 등장한 것이 SSD(Solid State Drive)이다. 컴퓨터의 메모리(D-ram)보다는 느리지만 기계식 디스크 드라이브보다는 훨씬 빠르다.

순차 I/O에서는 SSD가 디스크 드라이브보다 조금 빠르거나 거의 비슷한 속도이다. 그러나 랜덤 I/O가 디스크 드라이브에 비해 훨씬 빠르다는 장점이 있다. 데이터베이스 서버에서는 순차 I/O 작업은 그다지 비중이 크지 않고 랜덤 I/O를 통해 작은 데이터를 읽고 쓰는 작업이 대부분이므로 SSD 장점은 DBMS용 스토리지에 최적이라고 볼 수 있다.

5.1.3 랜덤 I/O와 순차 I/O

랜덤 I/O는 디스크 드라이브의 플래터를 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것을 의미한다. 만약 순차 I/O로 3개의 페이지를 읽는 데는 1번의 시스템 콜을 요청하지만, 랜덤 I/O로 3개의 페이지를 읽는 데는 3번의 시스템 콜을 요청한다.

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

데이터베이스의 대부분의 작업은 이러한 작은 데이터를 빈번히 읽고 쓰기 때문에 MySQL 서버에는 그룹 커밋이나 바이너리 로그 버퍼 등의 기능이 내장된 것이다.

관련 질문 : [Issue #27] 바이너리 로그 버퍼와 InnoDB 로그 버퍼가 입출력 작업에 끼치는 영향

쿼리를 튜닝해서 랜덤 I/O를 순차 I/O로 바꿔서 실행할 방법은 많지 않다. 그래서 일반적으로 쿼리를 튜닝하는 것은 랜덤 I/O 자체를 줄여주는 것이 목적이라고 할 수 있다.

인덱스 레인지 스캔은 데이터를 읽기 위해 주로 랜덤 I/O를 사용하고, 풀 테이블 스캔은 순차 I/O를 사용하낟. 그래서 상황에 따라 풀 테이블 스캔을 사용하도록 유도하는 경우도 발생한다.

5.2 인덱스란?

DBMS의 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 오래 걸린다. 그래서 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍(key-value pair)으로 인덱스를 만들어 둔다. 인덱스는 또한 이러한 검색을 빠르게 하기 위해 칼럼의 값을 주어진 순서로 미리 정렬해서 보관한다.

DBMS 인덱스의 자료구조로는 SortedList를 사용한다. 데이터 파일을 보관하는 자료구조는 ArrayList를 사용한다. 인덱스의 경우 항상 정렬된 상태를 유지해야 하기 때문에 SortedList를, 데이터 파일의 경우 별도의 정렬 없이 그대로 저장해도 되므로 ArrayList를 사용한다.

이때 두 자료구조의 장단점을 한 번 살펴보면 SortedList는 데이터의 변경이 생길 때 마다 데이터 정렬이 필요하다. 하지만 정렬된 데이터에서 값을 찾는 것은 매우 빠르게 가능하다. ArrayList의 경우 데이터의 변경이 생겨도 순서가 보장될 필요가 없으니 속도에 영향을 미치지 않는다. 그러나 정렬되지 않은 데이터에서 검색을 하는 경우는 많은 시간이 소요된다.

결론적으로 DBMS에서 인덱스는 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 희생하고 대신 데이터의 읽기 속도를 높이는 기능이다. 인덱스의 추가 여부는 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하는지의 여부로 결정돼야 한다.

인덱스의 역할별로 구분해 본다면 프라이머리 키(Primary Key)와 보조 키(Secondary Key)로 구분해 볼 수 있다.

• 프라이머리 키(Primary Key) : 레코드를 대표하는 칼럼의 값으로 만들어진 인덱스를 의미한다. 이 칼럼은 통해 레코드를 식별 가능하므로 식별자라고 부르기도 한다. 프라이머리 키는 NULL과 중복을 허용하지 않는다.

• 프라이머리 키를 제외한 나머지 모든 인덱스는 보조 인덱스(Secondary Index)로 분류된다.

인덱스의 데이터 저장 방식(알고리즘)별로 구분하는 것은 많은 분류가 가능하겠지만 대표적으로 B-Tree 인덱스와 Hash 인덱스로 구분할 수 있다. 최근 새롭게 Fractal-Tree 인덱스와 같은 알고리즘도 도입됐다.

• B-Tree 알고리즘 : 가장 일반적으로 사용하는 알고리즘이다. 성숙된 상태이고 칼럼 값을 변형하지 않고 원래의 값을 이용해 인덱싱한다.
• Hash 알고리즘 : 해시 값을 계산해서 인덱싱하는 알고리즘이다. 빠른 검색이 가능하지만 값을 변형해서 인덱싱하므로 전방(Prefix) 일치와 같은 값 일부 검색을 사용할 수는 없다. 주로 메모리 기반의 데이터베이스에서 많이 사용한다.
• Fractal-Tree 알고리즘 : B-Tree 알고리즘의 단점을 보완하기 위해 나온 알고리즘이다. 값을 변형하지 않고 인덱싱는 것은 B-Tree와 비슷하지만 데이터가 저장되거나 삭제될 때 처리 비용을 줄일 수 있게 설계된 것이 특징이다. 아직은 성숙도는 떨어지지만 B-Tree 알고리즘을 대체할 수 있을 만한 알고리즘이다.

인덱스의 데이터 중복 허용 여부로 분류하면 유니크 인덱스(Unique)와 유니크 하지 않은 인덱스(Non-unique) 인덱스로 구분할 수 있다. 유니크한지 여부는 DBMS의 쿼리를 실행해야 하는 옵티마이저에게는 상당히 중요한 문제이다. 유니크 인덱스일 경우 동등 조건에 대한 검사는 항상 1건의 레코드만 검색하면 더 이상 찾지 않아도 된다는 내용을 옵티마이저에게 알려주는 효과를 낸다.

인덱스의 기능별로 분류해보면 전문 검색용 인덱스나 공간 검색용 인덱스 등이 있다.

5.3 B-Tree 인덱스

B-Tree 인덱스는 가장 범용적인 목적으로 사용되는 인덱스 알고리즘이다. 변형된 알고리즘으로는 여러 종류가 있는데, 일반적으로 DBMS에서는 주로 B+ Tree 또는 B* Tree가 사용된다. B-Tree에서 B는 Balanced를 의미한다.

B-Tree는 칼럼의 원래 값을 변형시키지 않고 항상 정렬된 상태로 유지하고 있다. 전문 검색과 같은 특수한 요건이 아닌 경우, 대부분 인덱스는 거의 B-Tree를 사용할 정도로 일반적인 용도에 적합한 알고리즘이다.

관련 질문 : [Issue #26] 전문 검색에 사용되는 인덱스

5.3.1 구조 및 특성

B-Tree의 기본적인 구조로는 트리 구조의 최상위에 하나의 "루트 노드"가, 그 하위에는 자식 노드가 붙어있다. 가장 하위에 있는 노드를 "리프 노드"라 하고 루트 노드도 아니고 리프 노드도 아닌 중간 노드를 "브랜치 노드"라고 한다. 인덱스의 리프 노드에는 항상 실제 데이터 레코드를 찾아가기 위한 주소 값을 가지고 있다.

데이터 파일은 INSERT된 순서대로 저장되지 않는다. 만약 데이터가 삭제되면 그 빈 공간을 다른 데이터가 재사용할 수 있도록 DBMS가 설계되어 있기 때문이다.

InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되므로 기본적으로 프라이머리 키 순서대로 정렬되어 저장된다.

앞서 말한 것처럼 인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가지게 된다. 그러나 이 레코드 주소는 DBMS 종류나 MySQL의 스토리지 엔진에 따라 의미가 달라진다. 오라클은 물리적인 레코드 주소가 되지만 MyISAM 테이블에서는 내부적인 레코드의 아이디를 의미한다. InnoDB 테이블에서는 프라이머리 키가 클러스터링되기 때문에 프라이므러 키값 자체가 주소 역할을 한다.

5.3.2 B-Tree 인덱스 키 추가 및 삭제

인덱스 키 추가

새로운 키값이 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다. 저장될 키값으로 저장되어야 할 위치를 검색해야 한다. 만약 리프 노드가 꽉 차서 저장할 공간이 없을 경우 리프 노드를 분리하는데 이 과정이 브랜치 노드까지 영향을 미친다. 이런 탓에 쓰기 작업에 비용이 많이 드는 것으로 알려졌다.

인덱스 추가에 대한 비용을 간단하게 비교해보면 테이블에 레코드를 추가하는 작업 비용이 1이라면 테이블의 인덱스에 키를 추가하는 작업은 1~1.5 정도 예측한다. 이는 메모리와 CPU에서 처리하는 것이 아니라 디스크로부터 인덱스 페이지를 읽고 쓰기 때문에 시간이 오래 걸린다.

• MyISAM, Memory 스토리지 엔진의 경우

  • 삽입이 실행되면 즉시 새 키 값을 인덱스에 반영
  • B-Tree에 키를 추가하는 작업이 완료될 때까지 클라이언트는 쿼리의 결과를 받지 못하고 기다리게 된다.
  • delay-key-write 파라미터로 인덱스 키 추가 작업을 (지연) 처리할 수 있다.
    • 그러나, 이는 동시 작업 환경에서는 적합하지 않다.

• InnoDB의 경우

  • 상황에 따라 적절하게 인덱스 키 추가 작업을 지연시켜 나중에 처리할 지, 아니면 바로 처리할지 결정
  1. 사용자 쿼리 실행
  2. 버퍼 풀에 새로운 키 값을 추가할 페이지(리프 노드)가 존재한다면 즉시 키 추가 작업
  3. 리프 노드가 없다면, 인서트 버퍼에 추가할 키 값과 레코드의 주소를 임시로 기록해두고 작업 완료 (사용자 쿼리는 실행 완료)
  4. 백그라운드 작업으로 인덱스 페이지를 읽을 때에만 인서트 버퍼에 머지해야할 인덱스 키 값이 있는지 확인한 후, 있다면 병합함(B-Tree에 인덱스 키과 주소를 지정)
  5. lnnoDB 서버 자원의 여유가 생기면 MySQL 서버의 인서트 버퍼 머지 스레드가 조금씩 인서트 버퍼에 임시 저장된 인덱스 키와 주소 값을 머지(B-Tree에 인덱스 키와 주소를 저장)시킴

• 위 지연 처리 기능은 INSERT, DELETE 등 인덱스 키의 추가 및 삭제 작업까지 버퍼링해서 지연 처리할 수 있게 기능이 확장

인덱스 키 삭제

• 해당 키 값이 저장된 리프 노드를 찾아 그냥 삭제 마크만 하면 작업 완료된다.
• InnoDB는 삭제도 지연 처리 가능
• MyISAM, Memory 스토리지 엔진은 테이블에서는 인서트 버퍼와 같은 기능이 없으므로 인덱스 키 삭제가 완료된 후 쿼리 실행이 완료된다.

인덱스 키 변경

• B-Tree의 키값 변경 작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리

인덱스 키 검색

• 트리 탐색

  • 인덱스 검색 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행

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

  • 부등호("<>") 비교나 값의 뒷부분이 일치하는 경우에는 B-Tree 인덱스를 이용한 검색이 불가능

• 변형된 인덱스 값은 B-Tree의 빠른 검색 기능을 사용할 수 없다.

  • 변형 ⇒ 함수나 연산

InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키 락 (갭락)이 검색을 수행한 후 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있다.

따라서 UPDATE, DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불 필요하게 많은 레코드를 잠근다. 심지어 모든 테이블을 잠글 수 있으므로 InnoDB에서는 특히나 인덱스의 설계가 중요

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

• 칼럼의 크기, 레코드의 건수, 유니크한 인덱스 키값의 개수가 검색, 변경 작업의 성능에 영향을 끼친다.

인덱스 키 값의 크기

• InnoDB 스토리지 엔진

  • 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라 한다.
  • 모든 읽, 쓰 작업의 최소 작업 단위가 된다.
  • 버퍼 풀에서 데이터를 버퍼링하는 기본 단위
  • 인덱스도 결국은 페이지 단위로 관리

• DBMS의 B-Tree는 자식 노드의 개수가 가변적 구조

• 인덱스의 페이지 크기와 키 값의 크기에 다라 자식 노드의 수가 결정

  • InnoDB의 모든 페이지 크기는 16KB로 고정
  • 자식 노드 주소는 페이지의 종류 별로 대략 6 바이트에서 12 바이트 까지 다양한 값을 가질 수 있다.
  • 

• 위 그림의 경우 (임의로 자식 노드의 주소를 12 바이트로 고정, 마찬가지로 키가 되는 인덱스 컬럼도 16 바이트로 설정) 하나의 인덱스 페이지(16KB)에 16 * 1024 / (16+12) = 585 개의 키를 저장할 수 있다.

• 인덱스 키 값이 커지면?

  • 키 값의 크기가 32바이트로 늘어났다고 가정하면 16*1024/(32+12) = 372개 저장할 수 있다.

• 만약 SELECT 쿼리가 레코드 500개를 읽어야한다면 전자는 인덱스 페이지 한번으로 해결되지만, 후자는 최소한 2번 이상 디스크로부터 읽어야한다.

• 결국, 인덱스를 구성하는 키 값의 크기가 커지면, 디스크로부터 읽어야하는 회수가 늘어나고, 그만큼 늘여진다는 것을 의미

B-Tree 깊이

• B-Tree의 깊이는 MySQL에서 값을 검색할 때 몇번이나 랜덤하게 디스크를 읽어야하는지와 직결되는 문제

  • 결론적으로 인덱스 키값의 크기가 커지면 커질 수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 작아지고, 그 때문에 같은 레코드 건수라 하더라도 B-Tree의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다는 것을 의미

• 키 사이즈 증가 ⇒ 깊이 증가 ⇒ 디스크 읽기 수 증가 ⇒ 성능 다운!

선택도(기수성)

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

• 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리

• 선택도가 좋지 않다고 하더라도 정렬이나 그룹핑과 같은 작업을 위해 인덱스를 만드는 것이 훨씬 나은 경우도 많다.

• 예를 들자면 1000개가 중복된 인덱스(기수성이 낮은 인덱스) 생성된 A 인덱스와 10개 단위로 인덱스(기수성이 높은 인덱스) 생성된 B의 경우

  • 1개의 레코드를 찾고자 한다.
  • A인덱스는 1개의 레코드를 찾기 위해 1000개를 훑어야하기 때문에 999개, B인덱스는 1개의 레코드를 찾기 위해 9개의 불필요한 레코드를 탐색

읽어야하는 레코드의 건수

• 인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 더 높은 비용이 든다.

• 일반적인 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도 더 비용이 많이 드는 작업인 것으로 예측

• 즉, 인덱스를 통해 읽어야할 레코드의 건수가 전체 테이블 레코드의 20~25퍼센트를 넘어서면 인덱스를 이용하지 않고 직접 테이블을 모두 읽어서 필요한 레코드만 가려내는 (필터링) 방식으로 처리하는 것이 효율적이다.

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

인덱스 레인지 스캔

• 가장 대표적인 방법으로 인덱스 풀 스캔, 루스 인덱스 스캔 보다 더 빠른 방법

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

• 인덱스 레인지 스캔은 검색 해야할 인덱스의 범위가 결정됐을 때 사용하는 방식이다.

• 검색하려는 값의 수나 검색 결과 레코드 건수와 관계없이 레인지 스캔이라고 표현한다.

• 일단 시작해야할 위치를 찾으면 그 때부터는 리프 노드의 레코드만 순서대로 읽으면 된다. 차례대로 쭉 읽는 것을 스캔이라고 표현한다.

• 만약 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔한다.

• 최종적으로 스캔을 멈춰야할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다.

• 위 그림에서 어떤 방식으로 스캔하든 관계 없이, 해당 인덱스를 구성하는 칼럼의 정순, 또는 역순으로 정렬된 상태로 레코드를 가져온다.

• 인덱스의 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다.

  • 이때 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 레코드 한 건 한 건 단위로, 랜덤 I/O가 한번씩 실행된다.
  • 위에서는 랜덤 I/O가 최대 3번이 필요한 것

인덱스 풀 스캔

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

  • 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 칼럼이 아닌 경우 인덱스 풀 스캔 방식이 사용
  • 예를 들어 인덱스는 (A, B, C) 칼럼의 순서로 만들어져 있찌만 쿼리의 조건절은 B 칼럼이나 C칼럼으로 검색하는 경우

• 쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용

1. 인덱스 리프 노드의 제일 앞으로 이동
2. 리프 노드를 연결하는 링크드 리스트를 따라서 처음부터 끝까지 스캔하는 방식을 인덱스 풀스캔

• 인덱스의 전체 크기는 테이블 자체의 크기보다는 훨씬 작으므로 인덱스 풀 스캔은 테이블 전체를 읽는 것보다는 적은 디스크 I/O 로 쿼리를 처리할 수 있다.

루스 인덱스 스캔

• 느슨하게 듬성 듬성하게 인덱스를 읽는 것

• 인덱스 레인지 스캔과 비슷하게 작동하지만, 중간마다 필요하지 않은 인덱스 키 같은 무시하고 다음으로 넘어가는 형태로 처리한다.
• GROUPO BY 또는 집합 함수 가운데 MAX, MIN 함수에 대한 최적화를 하는 경우에 사용된다.

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

• 이 쿼리에서 사용된 dept_emp 테이블은 dep_no와 emp_no 두 개의 칼럼으로 인덱스가 생성돼있다.
• 위 그림을 보면 인덱스 리프 노드를 스캔하면서 불필요한 부분은 그냥 무시하고 필요한 부분만 읽었음을 알 수 있다.

5.3.5 다중 칼럼 인덱스

• 실제 서비스용 DB에서는 2개 이상의 칼럼을 포함하는 인덱스가 더 많이 사용
• Concatenated INdex라고도 한다.

• 인덱스의 두 번째 칼럼은 첫 번째 칼럼에 의존해서 정렬돼 있다.

• 즉, 두번째 칼럼의 정렬은 첫 번째 칼럼이 똑같은 레코드에서만 의미가 있다.

• 다중 칼럼 인덱스에서는 인덱스 내에서 각 칼럼의 위치가 상당히 중요하다.

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

인덱스의 정렬

• 상용 DBMS는 인덱스의 오름, 내림 차순을 결정할 수 있지만 MySQL은 칼럼 단위로 정렬 방식을 혼합해서 생성하는 기능을 아직 지원하지 않는다.

• 하지만 가끔 인덱스를 구성하는 칼럼 가운데 오름,내림 차순을 혼합해서 만들어야 할 때가 있다.

• MySQL에서는 칼럼의 값을 역으로 변환해서 구현하는 것이 유일한 방법

• 내림 차순이 필요할 경우에는 해당 컬럼을 음수로 저장하여 오름 차순으로 정렬하는 꼼수가 필요함

인덱스 스캔 방향

SELECT *
FROM employees ORDER BY first_name DESC LIMIT 1;

위 쿼리를 실행하기 위해 인덱스를 처음부터 오름 차순으로 끝까지 읽어 first_name이 가장 큰 (오름차순의 마지막 레코드) 값 하나를 가져오는 걸까?

• 그렇지 않다. 옵티마이저는 최소 값은 맨 위, 최대 값은 맨 아래임을 옵티마이저는 이미 알고 있다.
• 위 쿼리는 인덱스를 역순으로 접근해 첫 레코드만 읽으면 된다.

즉, 인덱스를 역순으로 정렬되게 할 수 없지만 인덱스를 읽는 방향에 따라 오름차순 또는 내림 차순 정렬 효과를 얻을 수 있다.

쿼리의 ORDER BY 처리, MIN(), MAX 함수 등의 최적화, MySQL 옵티마이저는 인덱스의 읽기 방향을 전환해서 사용하도록 실행 계획을 만들어낸다.

5.3.7 B-Tree 인덱스의 가용성과 효율성

WHERE, GROUP BY, ORDER BY 절이 어떤 경우에 인덱스를 사용할 수 있고 어떤 방식으로 사용할 수 있는지 식별할 수 있어야 한다. 그래야만 쿼리의 조건을 최적화하거나, 쿼리에 맞게 인덱스를 최적으로 생성할 수 있다.

비교 조건의 종류와 효율성

다중 칼럼 인덱스에서 각 칼럼의 순서와 그 칼럼에 사용된 조건이 동등 조건("=")인지 아니면 크다(">") 또는 작다("<")와 같은 범위 조건인지에 따라 각 인덱스 칼럼의 활용 형태가 달라지며, 그 효율 또한 달라진다.

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

각각 컬럼의 순서만 다른 2가지 케이스로 인덱스를 생성

• 케이스 A: dept_no + emp_no
• 케이스 B: emp_no + dept_no

케이스 A는 "dept_no='d002' AND emp_no ≥ 10144"인 레코드를 찾고, 그 이후에는 dept_no가 'd002'가 아닐 때까지 인덱스를 그냥 죽 읽기만 하면 된다. 위 경우에는 읽은 레코드가 모두 사용자가 원하는 결과이다.

케이스 B는 우선"emp_no≥10144 AND dept_no='d002'" 인 레코드를 찾고, 그 이후 모든 레코드에 대해 dept_no='d002' 인지 비교하는 과정을 거쳐야한다.

**이처럼 인덱스를 통해 읽은 레코드가 나머지 조건에 맞는지 비교하면서 취사 선택하는 작업을 "필터링"**이라고 한다. 최종적으로 위의 예에서 보면 케이스 A는 5개의 값을 찾기위해 5번의 비교 연산이 실행되었고 케이스 B는 5개의 값을 찾기 위해 7개의 비교 과정을 거쳤다.

이런 현상이 발생한 이유는 다중 칼럼 인덱스의 정렬방식(인덱스의 N번째 키 값은 N-1번째 키값에 대해서 다시 정렬됨) 때문이다. 케이스 A인데스는 2번째 칼럼 emp_no는 비교 작업의 범위를 좁히는데 도움을 준다. 케이스 B인덱스에서 2번째 칼럼인 emp_no는 비교 작업의 범위를 좁히는 데 아무런 도움을 주지 못하고, 단지 쿼리의 조건에 맞는지 검사하는 용도로만 사용됐다.

• 작업의 범위를 결정하는 조건을 "작업의 범위 결정 조건"이라고 하고 비교 작업의 범위를 줄이지 못하고 단순히 거름 종이 역할만 하는 조건을 "필터링 조건", "체크 조건"이라고 표현
• 작업 범위를 결정하는 조건은 많으면 많을수록 쿼리의 처리 성능을 높이지만 체크 조건은 많다고 해서 (최종적으로 가져오는 레코드는 작게 만들지 몰라도) 쿼리의 처리 성능을 높이지는 못한다. 오히려 쿼리 실행을 더 느리게 만들 때가 많다.

인덱스의 가용성

• B-Tree 인덱스의 특징은 왼쪽 값에 기준해서 오른쪽 값이 정렬돼있다는 것
• 칼럼 내부에서도, 다중 칼럼 인덱스의 칼럼에서도

• 위 그림을 보면 하나의 칼럼으로 검색해도 값의 왼쪽 부분이 없으면 인덱스 레인지 스캔 방식의 검색이 불가능하다. 또한, 다중 칼럼 인덱스에서도 왼쪽 칼럼의 값을 모르면 인덱스 레인지 스캔을 사용할 수 없다.

• SELECT * FROM employees WHERE first_name LIKE '%mer';

  • 왼쪽 부분이 고정돼있지 않기 때문에 인덱스 사용 불가능

• SELECT * FROM dept_emp WHERE emp_no >= 10144

  • dept_no, emp_no 칼럼의 순서대로 인덱스가 생성돼 있다면, dept_no가 결정되지 않았기 때문에 위 쿼리는 인덱스 사용이 불가능

가용성과 효율성 판단

• B-Tree는 아래와 같은 조건에서 작업 범위 결정 조건으로 사용할 수 없다. 경우에 따라서는 체크 조건으로 인덱스를 사용할 수 있다.

• 또한 다른 일반적인 DBMS에서는 NULL 값은 인덱스에 저장되지 않지만 MySQL 에서는 NULL 값도 인덱스로 관리된다.

다중 칼럼으로 만들어진 인덱스가 사용될 수 있는 조건에 대해서 살펴보자.

• 작업 범위 결정 조건으로 인덱스를 사용하지 못하는 경우

  • column_1 칼럼에 대한 조건이 없는 경우
  • column_1 칼럼의 비교 조건이 위의 인덱스 사용 불가 조건 중 하나인 경우

• 작업 범위 결정 조건으로 인덱스를 사용하는 경우 (i는 2보다 크고 n보다 작은 임의의 값을 의미)

  • column_1 ~ column_(j-1) 칼럼까지 Equal 형태 ("=" 또는 "IN") 로 비교
  • column_j 칼럼에 대해 다음 연산자 중 하나로 비교
    • Equal("=" 또는 "IN")
    • 크다 작다 형태(">", "<")
    • LIKE로 좌측 일치 패턴 (LIKE '승환%')

5.4 해시 인덱스

• 해시 인덱스는 동등 비교 검색에는 최적화돼 있지만 범위를 검색한다거나 정렬된 결과를 가져오는 목적으로는 사용할 수 없다.
• 일반적인 DBMS에서 해시 인덱스는 메모리 기반의 테이블에 주로 구현돼 있으며 디스크 기반의 대용량 테이블용으로는 거의 사용되지 않는다.
• 해시 인덱스 알고리즘은 테이블의 인덱스 뿐 아니라 InnoDB의 버퍼 풀에서 빠른 레코드 검색을 위한 어댑티브 해시 인덱스로 사용되기도 하고 오라클과 같은 DBMS에서는 조인에 사용되기도 한다.

5.4.1 구조 및 특성

해시 인덱스 장점

• 실제 키값과 관계없이 인덱스 크기가 작고 검색이 빠름
  • 트리 형태의 구조가 아니므로 검색하고자 하는 값을 주면 해시 함수를 거쳐 찾고자 하는 키값이 포함된 버켓을 한번에 알아낼 수 있다.
• 그리고 그 버켓 하나만 읽어서 비교해보면 실제로 레코드가 저장된 위치를 바로 알 수 있다.
• 그래서 트리내에서 여러 노드를 읽어야하지만 레코드의 주소를 알아낼 수 있는 B-Tree보다 상당히 빨리 결과를 가져올 수 있다.
• 해시 함수를 사용하므로 인덱스 키 크기가 작다.

해시 인덱스에서 가장 중요한 것은 해시 함수로, 입력된 키 값이 어디에 저장될지를 결정하는 함수이다.

해시 함수의 결과 값의 범위가 넓으면 그만큼 버켓이 많이 필요해서 공간의 낭비가 커지고, 값의 범위가 좁으면 충돌되는 경우가 너무 많이 발생해 해시 인덱스의 장점이 사라진다.

• 검색을 위한 해시 인덱스에서는 충돌이 많이 발생하면 할수록 검색의 효율이 떨어진다.
• DBMS에서의 주된 해시 알고리즘 사용 목적
  • 인덱스
  • 테이블의 파티셔닝 용도
    • 검색의 경우와 반대로 해시 함수가 필요한 파티션의 개수만큼만 만들어내도록 설계해야하므로 해시 함수의 결과 값의 범위를 좁게 사용
    • MySQL의 파티션은 이러한 해시 알고리즘을 이용해 테이블을 파티셔닝하는 기능

5.4.2 해시 인덱스의 가용성 및 효율성

• 해시 인덱스는 빠른 검색을 제공하지만 키 값 자체가 변환되어 저장되기 때문에 범위를 검색하거나 원본값 기준으로 정렬할 수 없다.

작업 범위 제한 조건으로 해시 인덱스를 사용하는 쿼리

• 다음 패턴의 쿼리는 동등 비교 조건으로 값을 검색하고 있으므로 해시 인덱스의 빠른 장점을 그대로 이용
• IN 연산자도 결정 여러 개의 동등 비교로 풀어서 처리 하므로 사용 가능

SELECT .. FROM tb_hash WHERE column = '검색어' ;
SELECT .. FROM tb_hash WHERE column <=> '검색어' ;
SELECT .. FROM tb_hash WHERE column IN ('검색어1', '검색어2');
SELECT .. FROM tb_hash WHERE column IS NULL;
SELECT .. FROM tb_hash WHERE column IS NOT NULL;

<=> 는 "NULL Safe Equal" 연산자라고 하는데, 비교 양쪽의 값이 NULL이 있을때를 제외하고는 "=" 연산자와 똑같다.

해시 인덱스를 전혀 사용하지 못하는 쿼리

• 어떤 방법으로도 해시 인덱스를 사용 불가능

SELECT .. FROM tb_hash WHERE column >= '검색어';
SELECT .. FROM tb_hash WHERE column BETWEEN 100 AND 120;
SELECT .. FROM tb_hash WHERE column LIKE '검색어%';
SELECT .. FROM tb_hash WHERE column <> '검색어';

• 다중 칼럼으로 생성된 해시 인덱스에서도 모든 칼럼이 동등 조건으로 비교되는 경우에만 인덱스를 사용할 수 있다.

CREATE TABLE tb_session (
	session_id BIGINT NOT NULL,
	member_id CHAR(20) NOT NULL,
	...
	INDEX ix_memberid_sessionid (member_id, session_id) using HASH
) ENGINE=MEMORY;

SELECT * FROM tb_session WHERE member_id='user_nickname';