Database Index

DB 에서 조건 검색을 하면 어떻게 될까?

SELECT * FROM my_table WHERE name = "Brian";

보통 이런식의 검색은 테이블안에 있는 모든 레코드/row 를 훑어서 찾는다. 이런식의 검색을 full scan 이라고 하고 테이블 안에 레코드의 개수가 늘어날수록 검색시간도 선형적으로 늘어난다.

검색시간을 줄이고 더 효율적으로 원하는 데이터를 DB 테이블에서 찾기 위해 인덱스를 사용할 수 있다. 글을 정리하면서 느낀점은 인덱스는 파고 팔수록 정말 다양한 디테일들이 있고 쿼리에 따른 다양한 주의점과 특징을 가지는것 같다. 되도록 대표적인 것을 담을 수 있도록 노력했다.

인덱스

위에서 보았듯이 검색은 특정한 컬럼의 값을 기반으로 이루어진다. 예를 들어 WHERE column1 = "특정한 값".

이런 검색을 효율적으로 하기 위해 인덱스는 테이블 안에서 컬럼 값들을 모아서 정렬된 상태로 보관하며 그 위에서 이분탐색의 개념을 사용하여 원하는 데이터 값을 빠르게 찾아낸다. 인덱스 안에 정렬된 값들은 해당 값을 읽어온 테이블 레코드의 위치도 함께 저장하기 때문에 다시 원본 데이터로 매핑해 탐색이 완료되면 빠르게 데이터를 읽어올 수 있다.

제일 이해하기 쉽게는 컬럼 하나를 이용해서 만든다고 생각 할 수 있지만 실질적으로는 보통 여러개의 컬럼을 혼합해서 다중컬럼 인덱스를 만든다. 그 이유는 상황에 따라 다중컬럼 인덱스는 단일 컬럼 인덱스의 역할을 동일하게 수행해줄 수 있고 주로 같이 검색되는 컬럼이 있을 경우 성능면에서나 저장공간 면에서 더 효율적이다.

물론 이것도 어떤식으로 다중컬럼 인덱스를 구성하느냐에 따라 효율성이 더 달라질수 있다.

이름	나이	데이터 포인터
김민재	28	12343
김민재	30	23439
손흥민	32	23131
이강인	23	12312

에를 들어 보면 회원 테이블의 이름 컬럼과 나이 컬럼을 가져와 인덱스를 만든다고 생각해보자. 인덱스는 가장 우선적으로 이름 컬럼대로 정렬이 되고 그 다음으로 나이 컬럼으로 정렬이 된다. 이럴 경우, 예를들어 같은 이름을 갖는 레코드가 있을 경우, 2차적으로 나이를 이용해 정렬이 될것이다.

이때 다중컬럼 인덱스를 이름으로 만든 단일 컬럼 인덱스와 동일하게 사용가능하다. 그 이유는 인덱스안에 데이터들이 완벽히 이름 값으로 정렬되어있기 때문에 이분탐색을 적용 할 수 있기 때문이다. 같은 맥락으로 이 다중컬럼 인덱스를 나이로 만든 단일 컬럼 인덱스처럼 사용하지는 못한다.

또 다른 경우로는 조건이 AND 가 아닌 OR 일 경우, 각 컬럼 마다 단일 인덱스가 없을 경우 결국 풀 스캔을 하게 된다.

따라서 인덱스는 상황에 따라서 그리고 데이터에 실행되는 쿼리를 살펴보고 적절히 설계해주고 변경해주는 작업이 필요한것 같다.

인덱스 구조

인덱스는 별도의 자료구조로 관리가 된다. 인덱스는 B-tree 또는 B+tree 로 구현이 된다. 둘은 거의 비슷하지만 B+tree 는 B-tree 의 변형형태로 몇가지 이점을 갖는 개선된 버전이다.

간략하게 정리해보자. B-tree 는 binary search tree (BST) 를 더 일반화 시킨것이다. BST 는 각 노드가 값 하나 그리고 최대 0개에서 2개의 자식 노드를 가리킨다.

B-tree 는 노드 안에 값의 개수와 자식 노드의 개수를 매개변수로 만든것이다. 예를 들어 노드 안에 3 개의 값 [3, 6, 9] 를 저장하고 총 4개의 자식 노드로 연결 될 수 있다. 이때 가장 왼쪽 자식 노드와 그 밑에 있는 서브트리에는 모두 3보다 작은 값을 가지고 그 다음은 3 에서 6 사이의 값 그 다음은 6 에서 9 그 다음은 9 보다 큰 값으로 구성이된다. 더 나아가 B-tree 는 self-balancing 트리라고 해서 데이터가 추가되고 삭제되면서 트리의 모양이 변화하면 내부적으로 노드를 rotation 하는 작업을 통해 높이를 이븐하게 맞춰준다. (트리의 높이는 효율적인 데이터 탐색과 연결된다.)

그러면 B-tree 와 B+tree 차이는 무엇일까? 간단히 차이점을 정리해보면 다음과 같다:

B-tree

• 각 노드는 데이터와 포인터 둘다 가질 수 있다.

B+tree

• 데이터는 리프 노드에만 있고 내부노드에는 포인터만 가진다.
• 각 리프노드는 서로 연결되어 있다.
• range query 가 더 쉽고 효율적이다.
• linear read 가 쉽다.

따라서 전반적으로 B+tree 는 컬렉션 형태의 여러 데이터를 읽어오기가 더 편리하다.

관리

그렇다면 모든 컬럼에 대해 인덱스를 만들면 문제 해결 아닐까? 생각해보자 만약 특정 컬럼에 대해 인덱스를 만들었다면 새로운 데이터가 추가되거나 기존 데이터가 변경되면 어떻게 될까? 위에서 보았듯이 인덱스는 정렬된 상태로 관리가 되고 정렬된 상태이어야지 효율적으로 데이터를 찾아낼 수 있다. 이분탐색을 떠올려보면 이해가 쉬울 것이다.

따라서 데이터가 추가되고 변경됨에 따라 인덱스 역시 변경되고 데이터 상태를 정확히 반영해야한다. 따라서 데이터 쓰기에 대해 오버헤드가 생긴다. 심지어 만약 해당 컬럼에 관련된 인덱스가 여러개라면 모든 인덱스에 대해 추가적으로 업데이트가 필요하게 되는 것이다.

그러면 어떤 특징을 염두해두고 인덱스를 관리하고 효율적인지 비효율적인지 판단해줄 수 있을까?

간단하게 살펴보자.

먼저 테이블에 연결되어있는 인덱스 보기

SHOW INDEX FROM my_table;

해당 쿼리가 사용하는 인덱스 살펴보기: 쿼리 앞에 EXPLAIN 붙어주기

EXPLAIN SELECT * FROM my_table where column1 = "값";

여기에 나오는 출력물은 해당 쿼리가 사용 할 수 있는 인덱스와 실제 사용된 인덱스 등 유용한 정보가 있다. 인덱스는 DB 자체에서 optimizer 라는 기능이 자동으로 적절하게 골라준다. 따라서 상황에 따라 내가 의도하지 않은대로 인덱스가 사용되거나 사용되지 않을 수 있다.

인덱스 사용도 변경 법 USE INDEX FORCE INDEX IGNORE INDEX

하지만 이건 쿼리문 자체를 수정하고 쿼리문 자체에 사용법을 명시하게 된다. 따라서 쿼리자체를 분석해서 왜 optimizer 가 특정 인덱스를 사용하거나 사용하지 않는지 분석하고 쿼리나 인덱스를 적절히 수정하는 방향도 도움이 된다.

좋은 인덱스를 설계시 고려할 만한 것들

• 자주 검색되는 컬럼 위주
• 인덱스로 사용되는 값들을 최대한 작게 한다 (즉 데이터 값 크기 자체가 작을수록 좋다)
• 높은 카디널리티를 갖는 컬럼 값 (high uniqueness; 높은 데이터 분포도를 갖는 컬럼 값들)
• 데이터 변경이 잦은 컬럼은 피하자
• 단일 컬럼 인덱스보다는 다중컬럼 인덱스를 고려해보자
• 인덱스를 사용하지 않는 검색 조건에 주의
  1. 인덱스 컬럼을 변경하는 조건절
     1. where substring()
     2. where concat()
  2. 부정형 비교
     1. not in
     2. !=
  3. 와일드 카드 like 문장의 전체 범위 지정
     1. where column1 like ‘%search%’
  4. 인덱스 컬럼의 형변환
  5. 검색범위가 너무 큰 쿼리 (optimizer 가 자동으로 full scan 을 택할 수 있다.)