순차 IO / 랜덤 IO

기본적으로 하드는 데이터를 읽을때 원판 플래터를 회전시키며 데이터를 찾는다.
순차 IO란 시작위치에 간 뒤 쭉 읽어서 데이터를 찾는 것을 말하고,
랜덤 IO란 여러 위치를 탐색해서 최종적으로 데이터를 찾는 것을 말한다.

인덱스 레인지 스캔의 경우 랜덤 IO, 테이블 풀 스캔의 경우 순차 IO를 사용한다.
보다시피 당연히 랜덤 IO가 순차 IO 보다 성능이 떨어진다.
하지만 여기서 SSD를 사용하면 얘기가 달라진다.
SSD는 HDD와 달리 플래터에 데이터를 기록하지 않고, 플래시 메모리라는 것에 데이터를 저장한다.
이는 원판을 기계적으로 회전시킬 필요가 없으므로 데이터를 매우 빠르게 찾을 수 있다.
그러므로 DBMS용 스토리지에는 SSD가 최적이라고 볼 수 있다.

인덱스란

책을 데이터에 비유한다면, 인덱스는 색인에 비유할 수 있다.
색인에서 키워드와 페이지 번호를 쌍으로 연결해놓았듯이, 인덱스 또한 인덱스 컬럼 값들과 레코드 주소를 키,벨류 형태의 쌍으로 저장해놓은 것을 말한다.
즉 데이터를 검색 할 때 인덱스를 통하는 방식으로 원하는 레코드에 빠르게 접근 할 수 있다.

자료구조로 비교해봤을 때
- 인덱스는 SortedList, 데이터 파일은 ArrayList 이다.
- 인덱스는 항상 정렬된 상태로 유지되고, 데이터 파일은 들어온 순서대로 저장된다.(앞이 비어져있을 경우 앞부터 채운다)
- 이미 정렬된 상태이므로 검색에는 매우 빠르나, 데이터가 추가되거나 삭제될 경우 다시 정렬해줘야 한다.
- 즉 데이터 조작의 성능을 희생하고 검색의 속도를 높이고자 할 경우 사용하는 것이 좋다.
- 인덱스가 많으면 많을수록 데이터 조작에서 발생하는 오버헤드가 많으므로, 적절하게 생성해야 한다.
인덱스를 역할로 분류했을 때,
- primary key와 secondary key로 분류할 수 있다.
- primary key는 지정과 동시에 바로 인덱스가 생성된다.
- secondary key는 primary key가 아닌 인덱스들을 얘기한다. unique key의 경우 primary key와 거의 비슷하므로 대체키 라고도 한다.
인덱스 저장 방식으로 분류했을 때,
- B-Tree 방식(가장 일반적으로 많이 쓰임), 해시 방식, Fractal 방식 등이 있다.
인덱스를 중복 여부로 구분했을 때,
- 값이 고유한 데이터들에 대한 인덱스와 중복된 값에 대한 인덱스 둘 다 생성할 수 있다.
- DBMS 입장에서 값이 고유하다는 것은 그 데이터를 찾았을 경우 더이상 탐색하지 않아도 된다는 것을 의미하므로, 성능 부분에서 매우 유리하다.

B-Tree 인덱스

가장 일반적으로 사용되는 인덱스 저장 자료구조.
컬럼의 값을 아무런 변형없이 저장한다.
B-Tree 생김새(대충)

구조

최상단의 루트 노드, 최하단의 리프 노드, 그 둘을 잇는 여러개의 브런치 노드들이 있다.(저장된 데이터가 작을 경우 브런치 노드는 없을 수 있다. 루트랑 리프노드는 항상 존재한다.)
루트 노드들은 각각 자식 노드들의 주소를 가지고, 최하단 리프노드는 저장된 레코드의 주소를 가진다.

인덱스 키 추가 및 삭제

추가

테이블에 레코드를 추가하게 되면 키 값을 이용해 들어갈 리프노드의 위치를 찾고, 추가한다.
만약 리프노드에 더 이상 들어갈 공간이 없으면 리프노드를 하나 더 추가하게 되는데, 여기서 상위 리프노드 또한 조정되어야 한다.
이러한 이유 때문에 B-Tree 인덱스에서는 데이터의 추가 작업 비용이 높다.

MyISAM이나 Memory DB의 경우 레코드 추가 -> 인덱스 추가의 작업이 바로바로 이뤄지므로 인덱스에 데이터가 들어가기 전까지 사용자는 결과를 받지 못한다.
이에 비해 InnoDB는 이를 좀 더 유연하게 처리한다.
레코드가 추가되었을 때 리프노드에 들어갈 공간이 남았을 경우 바로 추가하고, 공간이 없을 경우 인서트 버퍼라는 곳에 따로 저장해둔다.
이후 백그라운드 프로세스에서 인덱스를 읽을때나 데이터베이스 서버의 자원이 여유로울 경우 인서트 버퍼 스레드에서 인서트 버퍼를 체크한 뒤 인덱스에 머지한다.
중요한 것은 사용자가 이 작업을 인지하지 않아도 되게끔 투명하게 처리된다는 것이다.

삭제

레코드가 삭제되면 그에 해당하는 인덱스에 삭제마크를 표시한다.
이후 저장되는 레코드는 마지막 리프노드 뒤에 붙을수도 있고, 삭제마크된 부분을 재활용하여 인서트 될 수도 있다.
삭제마크를 표시하는 작업도 인서트와 마찬가지로 버퍼를 이용해 지연 처리할 수 있다(MySql 5.5부터)

변경

인덱스 키 값에 따라 인덱스가 들어갈 리프노드의 위치가 정해지므로, 변경은 불가능하고 삭제 -> 추가의 작업으로 진행된다.
작업 방식은 위의 삭제, 추가 방식과 동일하다.

검색

동등연산, 범위연산, Like(검색어%) 연산에서 인덱스를 사용할 수 있다.
부정연산, Like(%검색어)에서는 인덱스를 사용할 수 없다.
또한 인덱스 키 값에 변형이 일어난 경우(연산, 형변환)에도 인덱스를 이용한 빠른 검색이 불가능하다.

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

기본적으로 MySql에서는 데이터의 저장 공간에 페이지라는 최소 단위를 사용한다.
인덱스의 각 노드들도 하나의 페이지로 볼 수 있다.
MySql에서 페이지의 기본 단위는 16KB이다. 변경하려면 소스를 수정하고 컴파일해야 한다.

인덱스 키 값의 크기

인덱스 키 값의 크기가 커지면 자연스럽게 하나의 리프 노드(페이지)에 들어갈 수 있는 데이터의 개수가 작아진다.
만약 인덱스 키 값의 크기가 16바이트이고, 저장된 주소값의 크기가 12바이트 정도라고 하자.
이럴 경우 하나의 리프 노드에 들어갈 수 있는 데이터의 개수는 (16+12)/16KB 해서 585개가 된다.
그리고 만약 인덱스 키 값의 크기가 32바이트라면 (32+12)/16KB 해서 372개가 된다.
이런 상황에서 인덱스를 500개 읽어야 한다고 가정해보면, 리프노드 하나만 읽어도 되었을 것을 리프노드를 2개에 걸쳐 읽어야 하는 상황이 발생한다.
이로 인해 추가적인 I/O가 발생하게 되고, 속도가 느려지게 된다.

노드의 깊이

만약 2억개의 인덱스를 저장해야 하는 상황이 있다고 가정해보자.
인덱스 키 값의 크기가 16바이트일 경우 한 리프당 585개의 데이터가 저장 가능하기 때문에
585^3 = 200,201,625 로 3depth로 2억개의 레코드에 대한 인덱스를 저장 가능하다.
하지만 만약 32바이트일 경우 한 리프당 372개만 저장 가능하기 때문에
372^3 = 51,478,848 밖에 안되므로 3depth로 모든 인덱스를 저장하지 못하고, depth가 깊어지는 상황이 발생한다.
당연하게도 depth가 깊어지면 그만큼 I/O가 늘어나게 되고, 속도가 느려지게 된다.

실제로 depth가 아무리 깊어져도 4-5depth라고 한다. 인덱스 키 값의 크기를 작게해야 한다는 것을 강조하기 위한 약간 극단적인 예시였다.

선택도(분포도)

인덱스에 값의 그룹이 많을 경우 분포도가 좋다고 하고, 값의 그룹이 작을 경우 분포도가 나쁘다고 한다.
예를 들어 성별 같은 경우 값의 그룹이 남,여 뿐이므로 분포도가 상당히 나쁜 편이다.

아래과 같은 상황이 있다고 가정해보자

-- index : 단일 인덱스(country)

-- 실행할 쿼리
SELECT * FROM test_table WHERE country='KOREA' AND city='SEOUL';

테이블의 데이터는 10,000개라고 가정하고, country='KOREA' AND city='SEOUL'인 레코드가 1건 뿐이라고 가정해보겠다.

저장된 나라가 총 10개뿐일 경우(분포도 낮음)

country가 KOREA인 데이터 1000개를 인덱스로부터 읽어온 뒤, 데이터파일에 랜덤 액세스를 하며 city가 SEOUL인 데이터를 찾는다. 총 999건의 불필요한 검색을 하게 된다.
저장된 나라가 총 1,000개일 경우(분포도 높음)

country가 KOREA인 데이터 10개를 인덱스로부터 읽어온 뒤, 데이터파일에 랜덤 액세스를 하며 city가 SEOUL인 데이터를 찾는다. 총 9건의 불필요한 검색을 하게 된다.

보다시피 1번과 같은 인덱스는 좋지 않다고 할 수 있다.
어쩌피 모든 데이터 상황에 맞출 수 없으므로 불필요한 검색을 0건으로 만드는 것은 거의 불가능하다.
그래도 최대한 2번 인덱스처럼 검색하여 낭비를 최소화 하도록 해야 한다.

읽어야 하는 데이터의 양

일반적으로 인덱스를 이용해 레코드를 읽는 행위가 레코드를 직접 읽는 행위에 비해 3-4배 정도 비용이 크다고 산정한다.
인덱스의 리프 노드까지 가서 레코드의 주소를 찾고 이 주소로 레코드를 읽는 과정에서 랜덤 I/O가 발생하기 때문이다.
인덱스는 각자의 정렬기준으로 정렬되어 있지만 데이터 파일은 그렇지 않기 때문이다.
(인덱스를 통해 3건의 데이터를 찾았을 경우 총 3번의 랜덤 I/O가 발생하는 것이다.)

그래서 테이블 전체 레코드 개수의 20-25%를 넘는 데이터를 인덱스로부터 읽어야 할 경우에 옵티마이저는 그냥 풀 테이블 스캔을 시전한다.
(풀 테이블 스캔의 경우 그냥 순차 I/O로 읽어내리기 때문)
여기서 강제로 인덱스를 타게 해봐야 성능상 별로 효과가 없다.

인덱스를 이용해 데이터를 읽는 법

인덱스 레인지 스캔

가장 빠른 스캔 방법이다.
동일 연산자로 하나만 읽으나 범위 연산자로 여러개를 읽으나 모두 인덱스 레인지 스캔으로 분류한다.
루트 노드부터 브랜치 노드를 따라 리프 노드의 데이터(들)를 읽는 방식이다. 이를 탐색한다라고 한다.

인덱스 풀 스캔

인덱스를 처음부터 끝까지 다 읽는 방식이다.
인덱스에 저장된 데이터만으로 모든 것을 처리할 수 있는 경우이거나, 멀티인덱스의 중간 값 부터 조건을 지정하였을 경우 발생한다.
리프 노드의 첫번째 데이터 부터 순차적으로 읽어 내려가며, 하나의 리프노드가 끝났을 경우 해당 리프노드의 링크드리스트를 통해 다음 리프노드로 넘어가 끝까지 읽는 방식이다.
인덱스 풀 스캔은 좋은 방식이 아니다.

루스 인덱스 스캔

말 그대로 루~스하게, 인덱스를 다 읽지않고 듬성듬성 읽는것을 말한다.
중간마다 필요치 않은 인덱스 키 값을 무시하고 다음으로 넘어가는 형태로 처리한다.
예를 들면 아래와 같이 GROUP BY 집합 함수 가운데 MIN, MIX에 대한 최적화를 할 때 사용할 수 있다.

-- index : 복합 인덱스(dept_no, emp_no)

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

인덱스는 이미 dept_no, emp_no 의 순서로 정렬되어 있기 때문에 emp_no의 MIN값을 찾고자 할 경우
dept_no 인덱스의 첫번째 컬럼만을 읽으면 된다. 나머지 애들은 굳이 읽을 필요가 없다.
DISTINCT도 루스 인덱스 스캔을 사용한다. 처음 한건만 읽으면 되기 때문이다.

다중 컬럼 인덱스

보통 1개의 컬럼으로 인덱스를 생성하기 보단 여러개의 컬럼으로 인덱스를 생성하는 경우가 많다.
다중 컬럼으로 인덱스를 생성할 경우 인덱스의 순서를 신중하게 생각해야 하는데, 이는 인덱스의 정렬이 자신의 앞 인덱스의 정렬에 의존하기 때문이다.
예를 들어 dept_no과 emp_no 컬럼으로 다중 컬럼 인덱스를 생성했다고 가정해보자.
이때 emp_no의 값이 아무리 낮더라도, 짝지어진 dept_no의 값이 높을 경우 해당 데이터는 인덱스의 아래쪽에 쌓이게 된다.
첫번째 컬럼인 dept_no에 의존하기 때문이다.
이 때문에 다중 컬럼 인덱스를 생성할 때에는 순서에 매우 신중해야 한다.
인덱스의 효율(속도)와 연관이 있기 때문.

인덱스 정렬 및 스캔 방향

현재는 어떤지 모르곘으나… MySQL 5.대만 해도 인덱스 생성시 정렬 기준을 주는 것이 불가능했다.

1	CREATE INDEX idx_test ON test_table(col1 ASC, col2 DESC)

이렇게 작성해봐야 모두 ASC로 생성된다는 뜻이다.
한쪽 정렬이 적용된 다중 컬럼 인덱스를 가진 테이블에서 컬럼마다 정렬을 지정할 경우, 추가적인 정렬이 일어나기 때문에 절대 빠르게 처리될 수 없다.

이와 같은 상황에서 위와 같이 인덱스를 처리하는게 제일 좋긴하나… 안된다.
그래서 역 값을 줘서 위의 처리가 동작하게 하는 방식을 사용하곤 한다.(col2의 값을 전부 -로 세팅)

MySQL 옵티마이저는 기본적으로 ASC, DESC에 대한 개념이 있다.
ASC로 요청할 때에는 인덱스의 최소값(위)부터 차례로 읽으면 된다는 것을 알고,
DESC로 요청할 때에는 인덱스의 최대값(아래)부터 차례로 읽으면 된다는 것을 알고 있다.
이러한 특성 때문에 우리는 정렬을 공짜로 얻을 수 있다!

효율성 및 가용성

인덱스 레인지 스캔이 불가능한 경우
기본적으로 B-Tree는 왼쪽의 데이터에 의존하는 방식이다.
루트 노드부터 해서 여러 depth를 거쳐 리프 노드를 찾는 방식도 결국 왼쪽의 정렬 기준에 의존하는 것이고,
다중 컬럼에서 인덱스의 저장 구조를 보았을 때도 결국 왼쪽의 정렬 기준에 의존하는 것이다.(N번째 컬럼은 N-1번째 컬럼의 정렬기준에 의존한다는 정의)

이런 상황에서 왼쪽의 기준이 불명확할 경우, 인덱스 레인지 스캔이 불가능해진다.
예를 들어 아래와 같은 쿼리가 있다고 하자.
(인덱스 = firstname)

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

왼쪽 값을 기준으로 트리를 형성하는 B-Tree 인덱스인데, 위의 조건은 문자열의 왼쪽값이 정해지지 않았으므로 인덱스를 통한 탐색이 불가능한 쿼리이다.
실제로 돌려보면 테이블 풀 스캔을 한다.

이번에는 다중컬럼 인덱스이다.
(인덱스 = dept_no, emp_no)

1	SELECT * FROM dept_emp WHERE emp_no >= '11444';

이 또한 dept_no을 기준으로 인덱스가 정렬되어 있는데 emp_no 부터 조회했으므로 인덱스를 사용하지 못한다. 루트 노드로 들어갈 수 조차 없기 때문이다.
실제로 돌려보면 테이블 풀 스캔을 한다.

인덱스 사용 불가 조건

부정 연산(!=, <>, NOT IN, NOT BETWEEN, IS NOT NULL)
우측 일치 LIKE(LIKE %mer, LIKE _mer)
스토어드 프로시저로 비교할 경우(WHERE col1 = stored_procedure())
값을 강제로 변경했을 경우(WHERE SUBSTRING(col1, 1, 1) = ‘X’)
타입이 달라 컬럼에 형변환이 일어났을 경우(WHERE ch_col1=1001)

작업 결정 범위 조건, 체크 조건 가용성

dept_no, emp_no 순서의 인덱스와 emp_no, dept_no 순서의 인덱스가 있고, 아래와 같은 쿼리를 실행한다고 가정해보자.

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

첫번째 인덱스의 경우 dept_no, emp_no의 순서로 정렬되어 인덱스에 저장되어 있으므로 단계적으로 작업의 범위를 줄여나가며 스캔이 가능하다.
하지만 두번째 인덱스의 경우 emp_no, dept_no의 순서로 저장되어 있는데, emp_no에서 동등조건이 아닌 범위 조건을 하고 있다.
이러면 이후 dept_no은 범위 조건으로 검색된 결과에 대해 자신의 조건이 맞는지 안 맞는지의 필터 조건밖에 수행하지 못하게 된다.
즉, 작업의 범위를 줄여나가며 스캔을 하지 못했다.

위의 A 처럼 조건을 더 해갈수록 작업의 범위를 줄여주는 조건을 작업 결정 범위 조건이라고 하고,
오로지 가져온 데이터에서 해당 조건이 맞는지 안맞는지만을 체크하는 조건을 체크 조건 이라고 한다.

왜 범위 연산이 들어가는 순산부터 작업 범위를 좁히지 못하는 것일까? 생각해봤는데..  

a | b | c
---------
1 | 2 | 3
1 | 2 | 4
1 | 2 | 5
...

이런 형태의 인덱스가 있다고 할 때  
a,b,c 를 전부 동등조건으로 검색하면 3가지 값이 일치하는 특정 인덱스 로우를 선택할 수 있지만,  
c를 범위조건으로 검색하면 a,b 만 일치하는 인덱스를 들고온 뒤 범위로 쭉 긁어오기 때문에 특정 인덱스 로우를 선택하는 작업이 불가능해지는게 아닌가 싶다

아래의 인덱스를 보고 어떻게 하면 작업 결정 범위 조건으로 사용할 수 있는지, 어떻게하면 사용하지 못하는지 살펴보자.

1	CREATE INDEX idx_test ON test_table(col1, col2, col3, ... colN)

아래와 같이 사용할 경우 작업 결정 범위 조건으로 사용하지 못한다.

col1에 대한 조건이 없는 경우
col1에 대한 조건이 위에 인덱스 사용 불가 조건에 부합할 경우

인덱스의 첫 컬럼은 무조건 검색되어야 한다. 루트 인덱스로 들어갈 통로이기 때문이다.

아래와 같이 사용했을 경우 작업 결정 범위 조건으로 사용할 수 있다.(i = 2이상 N이하)

col1에 대한 조건부터 coli-1에 대한 조건까지 모두 동등 연산으로 연결되었을 경우
coli에 대한 조건이 범위(<,>), 좌측 일치 LIKE(문자%)일 경우

위의 두 가지 조건이 성립해야 한다. 동등 조건으로 시작해서 범위조건이나 LIKE(좌측 일치) 조건으로 들어가는 곳 까지가 작업 결정 범위 조건이다.
그 이후로는 모두 체크 조건으로 사용된다.
※ 다중 컬럼 인덱스 사용시 WHERE 조건의 순서는 상관없다.(where절의 실행순서야 옵티마이저에 의해 적절히 잘 파싱된다는걸 말하려는 듯)

1 2	SELECT * FROM test_table WHERE col1 = 'A' AND col2 = 'B' AND col3 >= 100 AND col4 = 'D' AND col5 LIKE '%test';

(WHERE 절의 순서를 바꿔도 결과는 동일하다)
인덱스 col1 부터 하나씩 타고 가다가 col3 에서 범위조건을 만남으로써, 이후의 값들은 체크 조건으로 사용되게 된다
col1 ~ col3 = 작업 결정 범위 조건, col4 ~ col5 = 체크 조건
이는 모든 B-Tree에 적용되는 조건이므로 다른 RDBMS에서도 적용할 수 있다.