인덱스

디스크 읽기 방식

  1. 랜덤 I/O
  2. 순차 I/O

데이터 베이스의 성능 튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건

디스크의 헤더를 움직이지 않고 한 번에 많은 데이터를 읽는 순차I/O에서는 SSD가 하드 디스크 드라이브보다 조금 빠르거나 거의 비슷한 성능을 보인다. 하지만 SSD의 장점은 하드 디스크보다 랜덤 I/O가 훨씬 빠르다는 것이다.

DB 서버에서 순차 I/O 작업은 그다지 비중이 크지 않고 랜덤 I/O를 통해 작은 데이터를 읽고 쓰는 작업이 대부분이므로 SSD의 장점은 DBMS용 스토리지에 최적이다.

랜덤 I/O와 순차 I/O

랜덤 I/O라는 표현은 하드 디스크 드라이브의 원판을 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것

순차 I/O는 3개의 페이지를 디스크에 기록하기 위해 1번 시스템 콜을 요청했지만, 랜덤 I/O는 3번의 시스템 콜을 요청했다. 즉 디스크를 각각 1번, 3번 움직인 셈이다.

쿼리 튜닝 = 랜덤 I/O 자체를 줄인다.

인덱스 레인지 스캔은 주로 랜덤 I/O를 사용하며, 풀 테이블 스캔은 순차 I/O를 사용한다. 그래서 큰 테이블의 레코드 대부분을 읽는 작업에서는 인덱스를 사용하지 않고 풀 테이블 스캔을 사용하도록 유도할 때도 있다.

인덱스란?

책의 맨 끝에 있는 찾아보기(또는 “색인”)로 설명한다. 책의 마지막에 있는 “찾아보기가 인덱스에 비유된다면 책의 내용은 데이터 파일에 해당한다고 볼 수 있다. 찾아보기를 통해 알아낼 수 있는 페이지 번호는 데이터 파일에 저장된 레코드의 주소로 비유된다.

컬럼(또는 컬럼들)의 값과 해당 레코드가 저장된 주소를 키와 값이 쌍(key-value pair)으로 삼아 인덱스를 만들어둔다. SortedList와 ArryaList는 데이터 파일과 같은 자료구조이다. SortedList는 DBMS의 인덱스와 같은 자료구조이며, ArryaList는 데이터 파일과 같이 저장되는 순서를 그대로 유지하는 자료구조이다.

SortedList는 값이 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느림. 하지만 조회시 빠름. 이는 인덱스에서도 동일하게 적용됨.

DBMS에서 인덱스는 저장(INSERT, UPDATE, DELETE) 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능이다. select 쿼리 문의 where 절에 사용되는 컬럼이라고 해서 전부 인덱스로 생성하면 데이터 저장 성능이 떨어지고 인덱스의 크기가 비대해져 오히려 역효과 발생.

  • 프라이머리 키(Primary Key) - Null 허용X, 중복 허용X
  • 보조 키(Secondary Key) - 프라이머리 제외 모든 인덱스를 보조 키로 분류

B-Tree 알고리즘: 가장 일반적으로 사용되는 인덱스 알고리즘으로 원래의 값을 변형하지 않고 인덱싱하는 알고리즘.

Hash 알고리즘: 칼럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원. Prefix의 일치와 같이 값의 일부나 범위 검색 시에는 사용할 수 없음.

B-Tree 인덱스

범용적인 인덱스 알고리즘. 주의할 점으로는 “B”가 바이너리(이진) 트리가 아니다. “B”는 Balanced를 의미한다. B 트리는 트리 구조의 최상위 하나의 “루트 노드”가 존재하고 그 하위에 자식 노드가 붙어 있는 형태다. 트리 구조의 가장 하위에 있는 노드를 “리프 노드”라 하고, 트리 구조에서 루트나 리프 노드가 아닌 중간의 노드를 “브랜치 노드”라고 한다. 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.

데이터 파일의 레코드는 Insert된 순서대로 저장되지 않는다 만약 실제로 그렇게 동작한다면 빈자리를 채우기 위해서 데이터를 끌고오거나 보내는 과정에 많은 비용이 들기 때문에 어느 빈 구멍이라도 들어갈 수 있는 방식이다.

인덱스는 테이블의 키 컬럼만 가지고 있으므로 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야하는데 이때 인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가진다.

MyISAM 테이블의 인덱스와 데이터 파일의 관계를 보자면 “레코드 주소”는 테이블 생성 옵션에 따라 레코드가 테이블에 Insert된 순번이거나 데이터 파일 내의 위치다.

InnoDB 테이블의 인덱스 데이터 파일의 관계를 보자면 이 엔진에서 사용하는 테이블에서는 프라이머리 키가 ROWID 역할을 수행한다. MyISAM과 InnoDB의 차이점으로는 세컨더리 인덱스가 MyISAM은 데이터의 물리적 주소를 가지지만 InnoDB는 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가진다.

InnoDB 테이블에서는 MyISAM처럼 한번에 데이터를 찾아서 가지 못하지만 인덱스에 저장돼 있는 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽는다. 이를 DoubleLookup이라 한다.

→ 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한번 검색해야 한다.

인덱스 키 추가

새로운 키 값이 B-Tree에 저장도리 때 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장되거나 안될 수 있다. 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프노드에 저장해야하는데 꽉 찰 경우에는 리프 노드가 분리되면서 상위 브랜치 노드들까지 처리의 범위가 넓어진다. 이러한 작업 탓에 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 든다. 이 비용의 대부분이 메모리와 CPU에서 처리하는 시간이 아니라 인덱스 페이지를 읽고 쓰기를 해야 해서 걸리는 시간이다.

인덱스 키 삭제

B키 값이 저장도니 트리의 리프노드를 찾아서 삭제 마크만 하면 작업이 완료된다. 삭제 마킹된 인덱스 키 공간은 그대로 방치 or 재활용. 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하여 디스크 I/O에 해당한다.

인덱스 키 변경

키 값 변경 작업은 먼저 기존의 키 값을 삭제한 후에 새로운 키 값을 추가하는 형태로 처리된다. 결국에는 기존의 방식인 추가와 삭제 과정을 다시 한번 거친다.

인덱스 키 검색

트리 검색 방식으로서 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행. B-Tree 인덱스 검색 같은 경우에는 100% 일치 또는 값의 앞부분(Left-most part)만 일치하는 경우 사용 가능. 인덱스의 키 값에 변형이 가해진 후에는 인덱스의 기능 사용 불가. 따라서 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree의 장점을 이용 불가.

InnoDB 스토리지 엔진에서 지원하는 레코드 잠금 또는 갭락이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있다.

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

인덱스 키 값의 크기

InnoDB 스토리지 엔진

  • 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(Page) 또는 블록(Block), 디스크의 모든 읽기 및 쓰기 작업의 최소 단위
    • B-Tree는 이진 트리가 아니라 자식 노드의 개수가 가변적인 구조다.
    • 자식 노드의 개수로는 인덱스의 페이지 크기와 키 값에 따라 결정됨.
    • 키 값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 느려진다.
    • 따라서 하나의 레코드를 위한 인덱스 크기가 커지면 메모리에 캐시해 둘 수 있는 레코드 수가 줄어둠.
    • 이와 같이 인덱스의 크기에 따라서 페이지에 저장되는 인덱스 개수도 적어지고, 깊이가 깊어져 디스크 읽기 횟수가 늘어남.

선택도(기수성)

모든 인덱스 키 값 가운데 유니크한 값의 수를 의미. 전체 인덱스 키 값 100일 때 유니크한 값의 개수가 10인 경우 기수성은 10이다. 인덱스는 기수성이 높을수록 검색 대상이 줄어들어서 빠르게 처리됨.

country라는 컬럼과 city라는 컬럼이 포함된 tb_test 테이블이 주어진 경우

A. country 컬럼의 유니크 개수가 10

B. country 컬럼의 유니크 개수가 1000

위의 쿼리를 수행하면 A의 경우에는 평균 1000건이 조회되고, B의 경우에는 평균 10건이 조회됨.

만약에 1건의 레코드를 조회하는 경우에는 A는 999건의 레코드를 더 읽은 것이지만, B 케이스는 9건만 더 읽은 것이다. → A의 경우 country 컬럼에 생성된 인덱스는 비효율적이다.

반대로 만약에 10000건의 레코드를 가지고 있는 tb_city 테이블에서 country 컬럼에만 인덱스가 존재하는 경우.

📁 케이스 A: 종류가 별로 없는 경우 (비효율적)

  • 상황: 전체 1만 명인데, 나라 종류가 10개밖에 없는 경우입니다. (예: 전 세계에 나라가 10개뿐이라고 가정)
  • 검색 과정
    1. 인덱스에서 country='KOREA'를 찾습니다.
    2. 나라가 10개밖에 없으니, 1만 명을 10으로 나누면 'KOREA'인 사람이 무려 1,000명이나 됩니다.
    3. 데이터베이스는 이 1,000명의 서류를 전부 꺼내서, 그중에 city='SEOUL'인 사람이 있는지 하나하나 확인해야 합니다.
  • 결과
    • 진짜 필요한 건 1명인데, 그걸 찾으려고 엄한 사람 999명을 더 확인했습니다.
    • 평가: 매우 비효율적! (쓸데없는 고생을 많이 함)

📂 케이스 B: 종류가 아주 다양한 경우 (효율적)

  • 상황: 전체 1만 명인데, 나라 종류가 1,000개나 되는 경우입니다.
  • 검색 과정
    1. 인덱스에서 country='KOREA'를 찾습니다.
    2. 나라가 1,000개나 되니, 1만 명을 1,000으로 나누면 'KOREA'인 사람은 평균 10명밖에 안 됩니다.
    3. 데이터베이스는 딱 10명의 서류만 꺼내서, city='SEOUL'인지 확인하면 됩니다.
  • 결과
    • 진짜 필요한 1명을 찾기 위해, 나머지 9명만 더 확인하면 끝났습니다.
    • 평가: 아주 효율적! (빠르게 찾음)