목차

I. DB Index : 구조와 작동 방식

II. 현행 서비스 내 최적화 필요 Query 특정

III. Indexing 적용 전/후 성능 비교를 위한 실험 계획(?) 세우기

IV. Indexing 적용 전/후 비교를 위한 실험 환경 설정

V. 비교 실험 결과

아래에서 기술할 내용들은 현재 프로젝트의 DB에 Indexing 을 적용하는 과정에서 공부한 것들을 기록한 것입니다.

그렇기 때문에 Bender-specific한 정보(ex. DB 에서 실제로 Index 를 구조화 / 활용 하는 방식) 등은 현 프로젝트에서 사용하는 다음 제품에 관한 것으로 한정함을 미리 알려드립니다.

• DBMS : MySQL 9.1.0
• Storage Engine : Inno DB

DB Index의 구조와 작동 방식에 관해 기술해보려합니다.

하지만 그 전에 Index 가 무엇인지 한 번 살펴보려합니다.

그리고 보다 Index 를 쉽게 이해할 수 있도록 연관된 다른 개념들도 소개하고자 합니다.

Index 라는 단어는 한글로 색인 입니다.

색인의 사전적 의미는 다음과 같습니다.

책 속의 내용 중에서 중요한 단어나 항목, 인명 따위를 쉽게 찾아볼 수 있도록 일정한 순서에 따라 별도로 배열하여 놓은 목록.

사전적 의미 자체도 복잡하지 않고, 실제로 데이터베이스 시스템 영역에서 사용되는 Index 도 다르지 않습니다.

위의 사전적 의미 내에 등장하는 개념을 추려 DBMS 의 인덱스를 설명하기 위해 필요한 개념과 대응시켜보면 다음과 같이 이해할 수 있습니다.

책 ➡️ 데이터베이스 혹은 테이블

중요한 ➡️ 찾고자 하는

단어, 항목, 인명 ➡️ 행(Row)

찾기 쉽도록 일정한 순서에 따라 별도로 배열하여 놓은 목록 ➡️ Index

거의 다 왔지만, 조금 더 생각해보겠습니다.

색인으로 원하는 정보가 담긴 페이지를 찾아가 정보를 찾는 과정을 한 번 그려보도록 하겠습니다.

Source : FingerReader

책의 색인은 통상 '어떤 용어/개념/단어/사건 - 기록된 페이지 식별자(쪽 번호)' 형태로 작성됩니다.

색인에 개념 별로 본문에 등장하는 전체 내용을 담아두진 않는다는 것이죠.

또한, 우리가 통상적으로 생각하는 책은 낱장의 정보 모음 형태가 아닙니다.

어떤 정보, 단어 등을 담은 장(Page) 가 있고 이 장들이 여러 개 묶여 하나의 책을 이룬다는 점을 알고 계실 것입니다.

그러면 우리가 "호연반점" 이라는 중국집에 관해 알고싶어 전화번호부를 살펴는 과정을 상상해보겠습니다.

우선 우리 지역의 가게들 정보를 담은 전화번호부의 색인은 일반적으로 해당 가게의 "이름"을 기준으로 작성됩니다.

'ㄱ, ㄴ, ㄷ, ㄹ...' 와 같은 자음으로 시작하는 가게들의 목록이 오름차순으로 각각의 가게 정보가 담긴 페이지 정보와 함께 담겨있을 겁니다.

'ㅎ' 위치로 찾아가 순서대로 다음과 같은 가게들 - 한성경꽃집, 한결상회, ... - 를 지나 호연반점에 드디어 도달합니다.

아마 이렇게 표현되어있을 겁니다.

"호연반점 - 48 페이지"

우리는 신나게 48페이지로 달려갑니다.

하지만 48페이지엔 호연반점의 정보만 대문짝만한 글자 크기로 적혀있지 않습니다.

'호식이두마리치킨' 과 같은 가게들의 정보와 함께 같은 페이지를 차지하고 있을 것입니다.

우리는 천천히 손가락으로 페이지의 가장 왼쪽 위에서 시작해 가장 오른쪽 아래를 향해 훑음과 동시에 읽어가며 호연반점의 정보를 찾을 것입니다.

지루한 비유를 읽으시느라 고생 많으셨습니다.

데이터베이스 시스템도 위와 아주 유사한 과정으로 데이터베이스/테이블을 읽어나가며 원하는 정보(행)를 찾아갑니다.

위의 이야기에서 등장한 각각의 개념과 데이터베이스 시스템의 구성요소 간 대응관계를 정리해보면 다음과 같습니다.

독자 ➡️ DBMS

책 ➡️ 데이터베이스 / 테이블

색인 ➡️ 인덱스

쪽 ➡️ 페이지

단위정보(Ex. 가게이름-주소-전화번호-업종으로 표현되는 가게 정보) ➡️ 행(Row / Entry)

손가락 / 시선 ➡️ Disk를 읽는 헤드

의외로 상당히 정확하게 대응하는 것을 알 수 있습니다.

위의 개념들은 앞으로 등장할 모든 내용을 수월하게 이해하기 위해선 반드시 필요한 친구들이라 지루한 과정을 통해서라도 소개해보았습니다.

이제 진짜로 Index 와 그 정의에 대해 살펴보겠습니다.

Index 란, 데이터베이스 탐색이 효율적으로 이루어질 수 있도록 고안된 자료구조 혹은 *이러한 자료구조로 구조화된 데이터(파일)*을 의미합니다.

Indexing 이란, 이러한 Index 를 생성하는 행위 를 말합니다.

다시 전화번호부의 예를 떠올려보겠습니다.

만약 100만 개의 가게 정보가 담긴 전화번호부에서 호연반점을 찾아야 한다고 생각해보겠습니다.

만약 전화번호부가 상호명 기준 오름차순으로 정렬되어있다는 보장이 없다면, 우리는 최악의 경우 호연 반점을 찾기 위해 100만 개의 점포를 모두 뒤져야할 수 있습니다.

인덱스가 있다면 어떨까요? 인덱스는 적어도 호연반점이 몇 페이지에 있는 지 알려줍니다.

이 경우 우리는 해당하는 페이지를 펼쳐 그 페이지 안에서 호연 반점을 찾으면 됩니다.

실제 인덱스도 우리가 아는 전화번호부의 색인처럼 생긴 자료일까요?

그럴 수도 있고 아닐 수도 있습니다. DBMS 마다 본인들의 목적에 따라 다르게 만들 수 있기 때문입니다.

하지만 개략적으로라도 '찾고자 하는 정보가', '어디에' 있는지 알려주는 것이 인덱스의 역할이라는 점을 주목해본다면,

세부적인 정보는 다를지언정, 인덱스가 Key-Value 형태로 조직되는 것이 자연스러울 것이라는 생각을 할 수 있습니다.

이때 Key 로는 통상 인덱스에 수록된 탐색의 기준값(Search Key 혹은 Key), Value 로는 Page 번호 혹은 주소 가 사용됩니다.

전화번호부의 색인이 "상호명 : 쪽수" 로 구조화되어있다면, 실제 색인 페이지 내 정보가 "호연반점 - 48 페이지" 로 표현되는 것을 생각하시면 이해가 수월할 것입니다.

이제 우리는 인덱스가 무엇인지, 어떤 형태로 표현이 되는지, 언제 활용되는지 이해했습니다.

그렇다면 실제로 DBMS 가 생성하는 Index 는 어떤 형태로 구조화되는지, 어떻게 실제 탐색에 활용되는지 알아볼 시간입니다.

그 중 먼저 B-Tree, B+Tree 를 알아보려고 합니다.

그 전에 잠시 함께 살펴봐야 하는 지점이 있습니다.

바로 트리에서의 노드 및 포인터가 데이터베이스 시스템의 무엇과 대응하는가? 입니다.

결론부터 말씀드리면, 노드는 앞서 함께 살펴보았던 페이지 내부에 존재합니다.

그리고 트리와 노드 모두 논리적인 모델입니다. 실제로 트리 모양으로 배치되어있다거나, 페이지 내부에 노드처럼 생긴 녀석이 떡 자리를 잡고 있는 것이 아닌 것이죠.

Binary Heap 의 구조와 마찬가지로 실제로는 Disk 내부에 저장되어있습니다. 또한 노드 또한 해당 논리적 트리 모델에서의 '노드' 역할 - 자식의 위치를 가짐으로써 논리적으로 연결되어있도록 하는 구성체 - 을 하기 때문에 부르는 것입니다.

이 부분을 유의하여 실제 페이지의 구조를 살펴보면 다음과 같습니다.

ptr 은 다른 페이지의 논리 주소 혹은 식별자를 담고 있습니다.

이 처럼 페이지가 노드 역할에 필요한 정보를 저장함으로써 노드 역할을 하고 이 포인터들을 통해 논리적인 트리 구조를 형성하는 것입니다.

이론적으로 B-Tree, B+Tree 모두 그 구조와 성질, 자격에 대한 수학적 정의가 존재합니다.

실제 활용과 관련한 내용을 다루는 현 노트에서 다루기엔 방향이 맞지 않다고 판단하여 생략하기로 하였습니다.

이에 대해 조금 더 자세히 알고 싶은 분은 제가 자료를 참고한 다음 책을 참고해주시면 감사드리겠습니다.

데이터베이스 시스템, 이석호

B-Tree는 균형 다원 탐색 트리(Balanced Multiway Search Tree) 자료구조로, 검색, 삽입, 삭제 등의 연산이 모두 O(log n) 의 시간복잡도를 가지도록 설계되어 있습니다.

이때 많은 분들이 이미 아시겠지만 균형 잡힌 트리 는 지나치게 트리의 깊이가 깊어져 탐색 시간 복잡도가 증가하지 않도록 적절히 재배치 및 합병(Balancing) 하여 제한된 높이를 갖는 트리를 의미합니다.

바로 이 Balancing 으로 인해 삽입과 삭제가 빈번한 테이블 혹은 변경이 잦은 테이블에 대해 Indexing 을 하는 것이 항상 효율성 증대만을 가져오는 것이 아닌 이유입니다.

그 삽입, 삭제, 변경 때 탐색 및 Balancing이 수반되는 경우가 있기 때문입니다.

전통적인 B-Tree의 경우, 내부 노드와 리프 노드 모두에 실제 데이터(또는 포인터와 함께 데이터)를 저장하도록 구현됩니다.

예를 들어, concertschedule 테이블에서 reservation_start_at 컬럼을 기준으로 B-Tree 인덱스를 구성한다고 가정해봅니다.

그리고 우리는 이 인덱스를 활용해 함께 2025-05-20 에 예매 가능한 공연 일정 을 찾아보도록 하겠습니다!

우선 B-Tree의 구조는 다음과 같이 표현할 수 있습니다.

graph TD;
    %% 내부 노드 구성 (깊이 3)
    A["루트 노드<br>[2025-05-01 | 2025-06-15]"] -->|reservation_start_at < 2025-05-01| B["내부 노드<br>[2025-04-10 | 2025-04-20]"];
    A -->|2025-05-01 ≤ reservation_start_at < 2025-06-15| C["내부 노드<br>[2025-05-05 | 2025-05-20]"];
    A -->|reservation_start_at ≥ 2025-06-15| D["내부 노드<br>[2025-06-20 | 2025-07-01]"];

    %% 리프 노드 (데이터 저장)
    B -->|2025-04-10 ≤ reservation_start_at < 2025-04-20| B1["리프 노드<br>(2025-04-12, Row Data)"];
    B -->|reservation_start_at = 2025-04-20| B2["리프 노드<br>(2025-04-20, Row Data)"];

    C -->|reservation_start_at = 2025-05-05| C1["리프 노드<br>(2025-05-05, Row Data)"];
    C -->|reservation_start_at = 2025-05-20| C2["리프 노드<br>(2025-05-20, Row Data)"];
    C -->|reservation_start_at = 2025-06-10| C3["리프 노드<br>(2025-06-10, Row Data)"];

    D -->|reservation_start_at = 2025-06-20| D1["리프 노드<br>(2025-06-20, Row Data)"];
    D -->|reservation_start_at = 2025-07-01| D2["리프 노드<br>(2025-07-01, Row Data)"];

    %% 특정 값 탐색 과정 (예: reservation_start_at = 2025-05-20 찾기)
    style C2 fill:#ffcc00,stroke:#333,stroke-width:2px;

탐색과정은 다음과 같이 개략적으로 설명할 수 있습니다.

1. 인덱스를 이루는 각 노드의 키(Key)는 해당 테이블 행들의 인덱싱 대상 필드의 실제 값이다.
2. 탐색 키(Search Key)는 찾고자 하는 키 값이다.
3. 인덱스의 시작지점인 루트 노드의 키값과 탐색 키 값을 비교한다.
   • 이때 해당 노드가 가진 키 값 중 가장 작은 키 값보다 작으면 해당 노드의 왼쪽 서브트리로 향한다. 노드는 서브트리로 가는 포인터 내지 방법을 보관하고있다.
   • 해당 노드의 가장 작은 키 값 <= 탐색 키 값 < 그 다음으로 작은 키 값 조건을 만족하는 경우, 왼쪽에서 두 번째 서브트리로 향한다. ... ... O(log n). 탐색 키를 가진 노드를 발견한다.

B+Tree는 B-Tree의 한 종류로, 모든 실제 데이터는 오직 리프 노드에만 저장되고, 내부 노드는 검색을 위한 키와 자식 노드에 대한 포인터만을 보유합니다.
이러한 구조 덕분에 다음과 같은 장점이 있습니다.

• 일관된 데이터 저장:
  모든 실제 데이터가 리프 노드에 존재하므로, 인덱스 탐색 후 바로 데이터를 얻을 수 있습니다.

• 순차적 접근의 효율성:
  리프 노드들이 양방향 링크드 리스트로 연결되어 있어, 범위 검색이나 순차적 스캔 시 디스크 랜덤 I/O가 아닌 순차 I/O를 수행할 수 있습니다.
  → 이는 디스크 Seek time 측면에서 큰 이점을 제공합니다.

• 내부 노드의 경량화:
  내부 노드에는 키와 포인터만 저장되므로, 메모리 사용량이 줄어들고 캐시 적중률이 높아집니다.

concertschedule 테이블에서 reservation_start_at 컬럼을 기준으로 B+Tree 인덱스를 구성한 경우를 살펴보면, 구조는 다음과 같이 그려볼 수 있습니다.

graph TD;
    %% 내부 노드 구성 (깊이 3)
    A["내부 노드<br>[2025-05-01 | 2025-06-15]"] -->|reservation_start_at < 2025-05-01| B["내부 노드<br>[2025-04-10 | 2025-04-20]"];
    A -->|2025-05-01 ≤ reservation_start_at < 2025-06-15| C["내부 노드<br>[2025-05-05 | 2025-05-20]"];
    A -->|reservation_start_at ≥ 2025-06-15| D["내부 노드<br>[2025-06-20 | 2025-07-01]"];

    %% 리프 노드 (데이터 저장)
    B -->|2025-04-10 ≤ reservation_start_at < 2025-04-20| B1["리프 노드<br>(2025-04-12, Row Data)"];
    B -->|reservation_start_at = 2025-04-20| B2["리프 노드<br>(2025-04-20, Row Data)"];

    C -->|reservation_start_at = 2025-05-05| C1["리프 노드<br>(2025-05-05, Row Data)"];
    C -->|reservation_start_at = 2025-05-20| C2["리프 노드<br>(2025-05-20, Row Data)"];
    C -->|reservation_start_at = 2025-06-10| C3["리프 노드<br>(2025-06-10, Row Data)"];

    D -->|reservation_start_at = 2025-06-20| D1["리프 노드<br>(2025-06-20, Row Data)"];
    D -->|reservation_start_at = 2025-07-01| D2["리프 노드<br>(2025-07-01, Row Data)"];

    %% 특정 값 탐색 과정 (예: reservation_start_at = 2025-05-20 찾기)
    style C2 fill:#ffcc00,stroke:#333,stroke-width:2px;

이처럼 B+Tree 구조에서는 내부 노드와 리프 노드의 역할이 명확히 구분됩니다. 특히 리프 노드들이 양방향 링크드 리스트로 연결되어 있다는 점은, 순차적 데이터 읽기(예: 범위 검색)에 매우 유리하게 작용합니다. 바로 이 순차적 데이터 읽기에 유리한 구조 가 Inno DB 의 선택을 받은 큰 이유라고 생각합니다.

• 데이터 저장 위치

  • B-Tree:
    • 내부 노드와 리프 노드 모두에 실제 데이터나 포인터를 저장할 수 있습니다.
    • 이로 인해, 데이터가 여러 레벨에 분산되어 저장되며, 데이터가 어느 노드에 있는지에 따라 접근 경로가 달라집니다.
    • 즉, Table 전체를 탐색하고 싶을 때 해당 인덱스를 이용할 경우 오히려 트리 전체를 중위순회해야 한다는 점에서 효율이 떨어지는 것입니다.
    • 이러한 비효율은 실제 물리적으로도 거리가 존재하는 공간에 저장되어 분포되어있기 때문에 계속해서 Disk Seek 을 해야한다는 점에 근거합니다.
  • B+Tree:
    • 실제 데이터는 오직 리프 노드에만 저장되고, 내부 노드는 탐색을 위한 키와 자식 노드에 대한 포인터만 보유합니다.
    • 이러한 구조는 데이터 저장 위치를 일관되게 유지하여, 검색 후 데이터를 찾는 과정이 단순해집니다.

• 디스크 I/O 최적화

  • B-Tree:
    • 내부 노드에도 데이터가 포함되어 있어, 특정 데이터를 찾기 위해 디스크에서 여러 랜덤 I/O 작업이 발생할 수 있습니다.
    • 랜덤 I/O는 디스크의 Seek time에 크게 의존하므로, 디스크 접근 속도가 저하될 수 있습니다.
  • B+Tree:
    • 리프 노드들이 양방향 링크드 리스트로 연결되어 있습니다.
    • 이로 인해 범위 검색이나 순차적 스캔 시, 인접한 리프 노드를 순차적으로 읽을 수 있어 순차 I/O가 가능해집니다.
    • 순차 I/O는 디스크의 Seek time을 최소화하므로, 대용량 데이터 처리 시 빠른 데이터 접근을 지원합니다.

• 캐시 효율성 및 메모리 사용

  • B-Tree:
    • 내부와 리프 노드에 데이터가 혼합되어 저장되므로, 캐시 메모리에 불필요한 데이터까지 로딩될 가능성이 있습니다.
  • B+Tree:
    • 내부 노드에는 키와 포인터만 존재하므로, 메모리에 더 많은 내부 노드를 적재할 수 있고, 이로 인해 탐색 효율성이 높아집니다.
    • 리프 노드의 순차적 배열 덕분에 한 번의 디스크 읽기로 여러 인접 데이터를 가져올 수 있어, 캐시 활용도가 극대화됩니다.

• 실제 시스템 적용 관점

  • InnoDB와 같은 디스크 기반 DBMS에서는 디스크 I/O가 성능의 중요한 요소입니다.
  • B+Tree의 리프 노드 연결 구조는 데이터가 순차적으로 저장되어 범위 검색 및 순차 스캔 시 디스크 접근 비용을 줄여줍니다.
  • 따라서 InnoDB는 B-Tree 대신 B+Tree를 채택하여 디스크 I/O 최적화와 범위 검색 효율성을 극대화합니다.

이러한 이유로 InnoDB는 B-Tree 구조보다 B+Tree 구조를 사용하여 인덱스를 구성하며, 이는 특히 디스크 기반 환경에서 빠른 데이터 접근과 효율적인 캐시 관리에 큰 도움이 됩니다.

그 외에도 Bendor 의 선택에 따라 목적에 맞는 동작을 보장하기만한다면 어떤 자료구조건 Index 구조화에 활용될 수 있습니다.

예를 들어 Hash Table 기반의 Adaptive Hash Index 도 있습니다.

Adaptive Hash Index의 경우 자주 사용되는 컬럼에 대해 Hash Table 기반의 Indexing 을 시행하는 방식으로써, B-Tree 의 구조적 특징에 기인한 문제점(자주 쓰는 데이터임에도 트리 구조를 쫓아 내려가야한다는 것)을 보완하기 위해 InnoDB 에서 활용합니다.

Adaptive Hash Index 는 특히 Table 을 구성하는 Row 에 대해 row-level mutex lock 이 많이 적용된 경우 자꾸만 지체되는 B-Tree 사용 시의 문제를 깔끔하게 해결해줄 수 있다는 점에서 주목할만합니다.

B+Tree 기반의 인덱스 구조

InnoDB는 주로 B+Tree 구조를 사용하여 인덱스를 구현합니다.

즉, 리프 노드들이 모두 같은 깊이에 위치함과 더불어 서로 양방향 연결리스트 구조를 이루고있기 때문에 순차 탐색에 약하다는 B-Tree의 단점을 극복한 구조를 갖는다는 것입니다.

하지만 이와 더불어 눈 여겨볼 지점은, 바로 InnoDB 는 크게 두 가지의 Index 를 생성하여 관리한다는 부분입니다.

클러스터드 인덱스 (Clustered Index or Primary Key Index)

InnoDB는 모든 테이블에 대해 PK 기준 인덱스를 자동으로 생성하는데 바로 이 인덱스를 Clusrtered Index(syn. Primary Key Index) 라고 합니다.

실제로 테스트를 위해 mock dataset 을 삽입하던 중 만든 적이 없던 PK 기준 인덱스가 있었는데 그것이 바로 이 Clustered Index 였습니다.

구조적으로도 특이한 점이 한 가지 있는데요, 바로 실제 데이터 행이 인덱스의 리프 노드에 저장 된다는 점입니다.

즉, PK 대상 검색 조건이 붙은 SELECT 쿼리 수행 시 Clustered Index 를 활용하고, 이 인덱스의 끝에 실제 목표 Row 가 담긴 Page에 도달이 가능하다는 것입니다.

이 덕분에 기본 키를 검색 조건으로 활용하는 SELECT 쿼리가 아주 효율적으로 이루어질 수 있습니다.

Clustered index와는 달리, 보조 인덱스는 실제 데이터 행을 포함하지 않고, 해당 행의 기본 키 값을 저장합니다.

따라서 보조 인덱스만으로는 완전한 데이터를 얻을 수 없으며, 기본 키를 참조해 최종 데이터를 조회하는 추가 단계가 필요할 수 있습니다.

MySQL이 인덱스를 만들어두고 정직하게 이 구조를 순회하며 데이터를 찾는다면 사실 그렇게 똑똑한 DBMS 라고 할 순 없겠습니다.

특히 점점 시간이 흐름에 따라 서비스에서 보관하고 다루어야 하는 데이터의 규모도 선형이 아닌 기하급수적으로 증가하고 있는 추세임을 고려했을 때,

이렇게 정직한 활용만 고집한다면 경쟁력 있는 DBMS 가 될 수 없을 것이 자명합니다.

그렇기 때문에 MySQL은 Index 를 좀 더 똑똑하게 활용하여 효율적인 데이터 스캔이 되도록 하는 방안을 고민하고 고안했는데요, 이를 소개해보려 합니다.

이 스캔 방식은 주로 범위 조건을 만족하는 행들을 찾을 때 사용됩니다.

쿼리 하나를 예로 들어 보겠습니다.

SELECT * FROM employees WHERE salary BETWEEN 50000 AND 70000;

이와 같이 범위 검색이 필요한 경우, MySQL은 인덱스 내의 키 값들이 정렬되어 있다는 특성을 활용하여, 시작점부터 종료점까지 순차적으로 탐색합니다.

이 과정에서 필요한 인덱스 엔트리만 빠르게 스캔하므로, 불필요한 데이터 접근을 줄일 수 있습니다.

인덱스가 유니크한 값을 보장할 때 사용되는 방식입니다.

SELECT * FROM users WHERE user_id = 12345;

이미 PK 혹은 UNIQUE 키워드가 선언된 컬럼의 값을 검색할 때 인덱스를 모두 타면 그것 또한 인덱스를 만들어두고 제대로 활용하지 못하는 것입니다.

앞서 기술하였듯, InnoDB 가 Clustered Index 를 생성하고 관리하고 있기 때문에 위와 같은 쿼리의 경우 Tree 를 타며 비교하지 않고 곧장 해당 값을 가진 Row 에 접근 가능합니다.

인덱스 전체를 순차적으로 읽어야 할 때 적용됩니다.

이는 테이블 전체를 조회하는 경우와 유사하지만, 실제 데이터 행이 아닌 인덱스 엔트리만을 읽는다는 차이가 있습니다.

만약 인덱스에 모든 필요한 컬럼(커버링 인덱스)이 포함되어 있다면, 데이터 페이지에 접근할 필요 없이 인덱스만으로 쿼리를 해결할 수 있어 전체 스캔 비용을 줄일 수 있습니다.

하지만 Index Full Scan 의 효율성을 높이자고 인덱스에 필요한 모든 컬럼을 넣어린다면 이 또한 Index 파일의 크기 자체를 키우는 일이 되므로 운영환경에서는 충분한 고민과 검토가 필요할 것입니다.

MySQL 5.6부터 도입되어 MySQL 8.0 이상에서도 중요한 역할을 하는 기술입니다.

ICP는 WHERE 절에 포함된 조건 중 일부를 인덱스 스캔 단계에서 미리 평가하여, 디스크로부터 불필요한 데이터를 읽지 않도록 도와줍니다.

이를 잘 이해하기 위해선 MySQL 5.5 에서는 어떤 방식으로 작업이 이루어졌는지 확인해볼 필요가 있습니다.

MySQL 5.5 에서, Storage 엔진으로부터 반환받은 Row들에 대해 WHERE 절로 표현된 검색 조건과 부합하는지 평가하는 것은 DBMS(MySQL)이 해야할 일이었습니다.

이렇게 할 경우 결국에 걸러져 결과로 반환되지 않을 행들에 대한 데이터까지 모두 DISK I/O 를 통해 전송됨으로써 불필요한 자원 소비가 발생합니다.

이를 줄이기 위해 MySQL 5.6 은 기똥찬 수를 하나 냅니다.

바로 인덱스를 구성하는 필드에 대한 WHERE 절 쿼리를 실행할 경우, Index 된 필드에 대한 필터를 Storage 엔진이 수행하여 한 번 걸러진 결과들을 반환해주는 것입니다.

Index 된 필드들에 대한 WHERE 절인 경우, 이에 대한 검증을 Storage 엔진에게 '미룬다' 짬처리한다 라는 점에서 Pushdown 이라는 이름이 붙게 된 것입니다.

그렇게 때문에 복합 인덱스 사용 시 특히 효과적이며, 인덱스 스캔 후 추가적인 조건 검사를 줄여 전반적인 쿼리 성능을 향상시킵니다.

즉, 작업 범위 결정 조건 을 Storage Engine 에게 제공하여 Base Table에 대한 full scan 을 방지함으로써 효율성을 챙기는 것입니다.

Index Skip Scan 이란, 복합 Index로 지정된 컬럼들 중 첫 번째 컬럼에 대한 조건이 WHERE 절에 존재하지 않고 두 번째 컬럼에 대한 조건만 주어지더라도,
두 번째 인덱스 컬럼에 근거한 Scan을 시행하는 것을 의미합니다.

지금보면 당연하다 싶지만 의외로 MySQL 8.0 버전부터 도입된 기능입니다.

그 전엔 인덱스 자체를 타지 않고 Full Scan 이 수행되었다고 합니다.

좋은 세상입니다.

어떤 컬럼에 대한 Index 를 생성해야 그 효과를 톡톡히 누릴 수 있을까요?

바로 효율적인 컬럼 선정에 대해 고민하면 머리가 아프니, 반대로 인덱스가 소용이 없어지는 상황을 생각해봅니다.

만약 두 가지 값을 갖는 필드인 gender 라는 필드에 대한 인덱스를 생성한다면 어떨까요?

해당 필드의 값으로 조건 검색을 수행하더라도, 충분히 크고 잘 분산된 모집단 데이터에 대해선 여전히 절반의 데이터가 주어질 것입니다.

이 상황에서 필터된 Row들에 대해 다시 한 번 이름이 일치하는 사용자를 찾는다면? 인덱스를 적용하며 우리가 기대했던 효율이 나오진 않을 것입니다.

gender 처럼 중복도가 높은 필드에 대해 우리는 해당 필드의 카디널리티가 낮다 라고 이야기합니다.

반대로 중복도가 낮다면 카디널리티가 높다 고 합니다.

선택도(Selectivity) 란, 특정 조건에 의해 선택되는 레코드가 전체 레코드 내에서 차지하는 비율을 의미합니다.

선택도가 높은 필드의 인덱스 적용 가치는 어떨까요?

극단적으로, 어떤 필드의 어떤 값을 갖는 데이터가 전체의 99%인 경우를 생각해보겠습니다.

앞에서 함께 살펴보았듯, 이러한 상황은 선택도가 높은 상황입니다.

이처럼 선택도가 높은 필드에 대해 생성한 인덱스를 통한 Scan 은 Full Table Scan 과 다를 것이 없게 됩니다.

따라서 선택도가 높은 필드 보다는 선택도가 낮은 필드에 대한 인덱스를 생성할 때 투자 대비 높은 성능 최적화 효과를 기대할 수 있습니다.

삽입과 삭제, 변경이 잦은 테이블 혹은 컬럼은 어떨까요?

우리는 이미 인덱스가 어떻게 생성되고 관리되는지 앞에서 살펴본 바 있으므로, 이러한 경우 인덱스의 성질을 유지하기 위해 요구되는 연산의 오버헤드가 인덱스 활용 효용성을 넘을 수 있음을 알 수 있습니다.

따라서 통상, 인덱스를 생성하여 활용하기에 적절한 테이블/필드를 선택할 때 다음과 같은 조건을 만족할 경우 '적절하다' 라고 판단합니다.

1. 카디널리티가 높은 필드
2. 선택도가 낮은 필드
3. 조회가 잦은 필드 / 테이블
4. 삽입/변경/삭제가 잦지 않은 테이블 혹은 필드

앞에선 현대의 DBMS 가 인덱스를 구성하기 위해 활용하는 자료구조와 그 작동방식을 살펴보았습니다.

또한 이와 함께 다음의 사항도 함께 살펴보았습니다.

• DB 의 인덱스는 어떻게 생겼고 어떻게 작동하는가?
• 어떤 원리 혹은 특성으로 인해 효율적인 탐색이 가능한가?
• 어떤 테이블 혹은 필드가 인덱스를 생성하여 활용하기에 적합한가?

이제 실제로 DB Indexing 적용하여 전/후 결과를 비교해보고 이 과정에서 학습한 것들을 정리해나가보고자 합니다.

그렇게 하기위해선 우선 현행 서비스에서 사용되는 쿼리들을 살펴보고, 인덱스를 생성하고 유지하는 비용을 감안하더라도 유용함이 이를 초과할 수 있는 쿼리 를 추려내어야 합니다.

저는 이러한 쿼리들의 특징으로 다음의 세 가지를 생각해보고 이에 부합하는 쿼리를 추려보았습니다.

1. 검색 조건이 하나 이상인 조회 쿼리(SELET)
2. 조건 검색 대상인 필드의 데이터 타입의 특성 상 비교 연산이 복잡한 쿼리

• 예를 들어, 검색 조건이 "어떤 필드의 값이 주어진 문자열과 부분 일치 혹은 완전 일치"인 경우를 생각해볼 수 있습니다.

3. 조건 검색 대상 필드가 다른 테이블과의 조인 컬럼인 경우

1. 특정 공연 일정의 예약 가능 좌석 목록 조회

SELECT s FROM SeatJpaEntity s 
	WHERE s.concertScheduleId = :concertScheduleId 
		AND s.status = 'AVAILABLE'

2. 특정 공연 일정의 이미 선점된 좌석 목록 조회

SELECT COUNT(s) FROM SeatJpaEntity s 
	WHERE s.concertScheduleId = :concertScheduleId 
		AND s.status = 'UNAVAILABLE'

1. 현재 예약 진행 중인 공연 일정 목록 조회

select cs from ConcertScheduleJpaEntity cs 
	where cs.reservationStartAt <= :presentDateTime 
		AND cs.reservationEndAt >= :presentDateTime

2. 예약 가능 공연 일정 목록 조회.

select cs from ConcertScheduleJpaEntity cs 
    where cs.reservationStartAt <= :presentDateTime
			AND cs.reservationEndAt >= :presentDateTime
			AND cs.availability = 'AVAILABLE'

1. 특정 사용자의 특정 공연 일정 예약 조회

SELECT r FROM ReservationJpaEntity r 
	WHERE r.concertScheduleId = :concertScheduleId 
		AND r.userId = :userId

2. 만료 대상 가예약 목록 조회

SELECT r FROM ReservationJpaEntity r 
	WHERE r.status = 'BOOKED' 
		AND r.expiredAt < CURRENT_TIMESTAMP

• 필수 필터 조건
  조회 쿼리에서는 반드시 공연 예매 시작 일자와 공연 예매 종료 일자를 기준으로 필터가 적용됩니다.
• 인덱스 미적용 시 문제점
  만약 해당 컬럼들에 대해 인덱스가 없다면, 모든 행을 순차적으로 탐색하며 조건을 비교해야 하므로 쿼리 성능이 크게 저하될 수 있습니다.

각각 별도의 인덱싱

• reservation_start_at과 reservation_end_at에 대해 개별 인덱스를 생성할 경우, 각 인덱스에서 조건을 만족하는 행들을 추출한 후 두 조건의 교집합을 구하는 방식(즉, Index Merge Intersection Access Algorithm)이 사용됩니다.
• 그러나 별도의 교집합 연산에 따른 추가 비용(연산 오버헤드, 양쪽 집합의 재탐색)이 발생할 수 있습니다.

복합 키 인덱싱

• 두 컬럼을 하나의 복합 키로 인덱싱하면, 먼저 reservation_start_at 조건에 부합하는 행들을 필터링하고, 그 결과 집합에 대해 reservation_end_at 조건을 적용할 수 있습니다.
• 복합 키 방식은 별도의 교집합 연산 없이 두 조건을 동시에 효율적으로 적용할 수 있어 오버헤드가 적습니다.

카디널리티/선택도 및 비즈니스 특성 고려

• 하루에 100만 건의 공연 예매가 동시에 이루어지는 상황은 매우 드물다고 가정할 수 있습니다.
• 인터파크 기준 하루에 가장 많은 시점(ex. 크리스마스) 기준 통상 120건 이내의 공연 예매가 이루어지는 것으로 확인했습니다. (2017년 기준 : 출처)
• 따라서 이 수치가 전체 데이터 수 대비 어느 정도의 선택도를 갖는지에 따라 (reservation_start_at, reservation_end_at)인덱싱 적절성에 대한 평가가 변할 수 있습니다.

status 컬럼

• 해당 필드는 필터 조건 에 해당합니다.
• 또한, 이미 앞의 두 필드로 대부분 필터링된 결과 집합에 대해 추가 조건으로 사용되므로, 낮은 카디널리티를 고려하여 인덱싱하지 않는 편이 유효하다고 판단합니다.

최적 전략

• reservation_start_at과 reservation_end_at을 복합 키로 구성한 인덱싱을 적용합니다.
• 두 필드 모두 작업 범위 결정 조건 에 해당합니다.
• 테스트 시엔 쿼리 효율성 변화의 폭을 증폭시켜 실험의 결과가 두드러지도록 하기 위해 충분히 많은 데이터(100만 개)를 생성하여 활용할 예정입니다.
• 그렇기 때문에 해당 필드가 유의미한 선택도와 카디널리티를 갖는다고 판단하였고, 해당 필드 대상 조건 검색시 효율적인 작업 범위 결정 조건 으로 작용할 것으로 생각했습니다.

조회 조건

• seat 테이블의 조회 쿼리는 주로 user_id, concert_schedule_id, status 세 컬럼을 대상으로 합니다.

비즈니스 정책

• concert_schedule_id를 기준으로 필터링할 경우, 각 공연 일정 당 할당된 좌석 수(현재 50개 정도)의 행만 조회됩니다.
• 한 공연에 대해 한 유저당 하나의 좌석만 예매 가능하므로, concert_schedule_id와 user_id를 복합 키로 구성할 수도 있으나…

효율적인 필터링 이 가능한 필드가 자명하다

• concert_schedule_id를 기준으로 인덱싱하면, 이미 소규모(최대 50개)의 행에 대해 빠르게 검색할 수 있어 추가 최적화가 불필요합니다.

최적 전략 seat 테이블은 concert_schedule_id 컬럼에 인덱싱을 수행하는 것이 가장 효율적입니다.

조건 분리

• reservation 테이블의 경우, status 기준 검색과 concert_schedule_id 및 user_id 기준 검색 케이스가 명확하게 구분되어 있습니다.

삽입과 조회 빈도

• 삽입과 조회가 모두 빈번하게 발생하는 테이블로, 인덱스 생성 시 삽입 성능에 미치는 영향을 고려해야 합니다.
• Scheduler 에 의해, 만료된 가예약의 삭제 혹은 예약 확정 처리와 같은 변경 작업이 짧은 주기로 서버가 실행되는 내내 발생하기 때문.
• 삽입 시 평균적으로 O(log n)의 시간 복잡도를 가지며, 리밸런싱으로 인한 추가 비용이 발생할 수 있습니다.

복합 인덱스 적용 가능성

• concert_schedule_id와 user_id를 복합 키로 구성하는 방안을 고려할 수 있으나, 삽입과 업데이트 빈도에 따른 인덱스 유지 비용을 감안해야 합니다.

삽입과 조회가 모두 빈번하므로, 추가적인 보조 인덱스를 생성하지 않습니다.

기본 설계

• 조회 쿼리 성능 조회를 위해 Mock Data 생성 후 일괄 삽입하기.
• 데이터 수 : 모두 100만 개로 설정
• 각 테이블의 성격을 고려했을 때 100만 개의 데이터 수가 비현실적인 경우도 있으나, 인덱스 유무에 따른 실험 결과가 보다 두드러지도록 하기 위함.
• MySQL Server
• Docker 환경에서 구동
• InnoDB 의 Buffer Pool 활용 Optimization에 의해 행들이 메모리 내에 캐싱되는 것을 방지하기 위해 서버 구동시 Buffer Size 를 8MB로 제한.

독립 변수

• 인덱스의 유무

종속 변수

• 쿼리 수행 속도
• EXPLAIN 키워드로 실행 시 출력되는 실행 계획 결과.

• 생성된 Mock data 에 대해, 앞서 추린 쿼리를 각각 인덱스 생성 전/후 한 번 실행한다.
• 여러 번 실행할 경우 MySQL Optimizer 의 영향이 작용할 수 있으므로 - Advanced Hash Index 와 같은 최적화 기법은 켜거나 끌 수 없다...- 한 번만 실행한다.

• 'EXPLAIN' 키워드를 통해 쿼리 실행 계획에 대한 논리적 시간 복잡도 계산 및 평가
• 실제 쿼리 실행 속도를 바탕으로 한 정량 지표 평가

1. concertschedule : (reservation_start_at, reservation_end_at)
2. seat : (concert_schedule_id)

인덱스가 없는 상태에서는 전체 테이블(약 1,107,879개의 행)을 스캔하며, 상태(status)에 따라 약 780ms ~ 860ms의 실행 시간이 소요되었습니다.

또한 쿼리 실행 계획 상, seat 테이블의 쿼리 실행 계획은 type이 ALL로 나타나며 1,107,879개의 행을 전수 스캔하는 모습을 보여주었습니다.

(인덱스 생성 소요 시간: 약 2초)

인덱스 생성 후에는 seat_schedule_pk 인덱스를 활용하여, 조건에 맞는 50개의 행만 대상으로 조회하므로 실행 시간이 극적으로 단축되었습니다.

이러한 단축의 배경은 EXPLAIN 키워드로 알아본 쿼리 실행 계획에서 파악해볼 수 있습니다.

인덱스 생성 후에는 type이 ref로 변경되어, 인덱스 seat_schedule_pk를 통해 concert_schedule_id를 기반으로 50개의 행만을 대상으로 효율적으로 조회하는 것을 확인할 수 있습니다.

또한 "Using where"와 함께 제시된 결과는 인덱스가 조건에 부합하는 소규모 행 집합만을 대상으로 작동함을 의미합니다.

• 실행 시간 비교: 인덱스 적용 전 평균 800ms에서 인덱스 적용 후 2.2~3.5ms로, 약 99% 이상의 시간 단축(200배 이상의 성능 향상)을 달성하였습니다.
• 평가: 인덱스가 매우 효과적으로 작동하여 불필요한 전체 스캔을 제거하고, 소규모 행 집합만을 대상으로 처리함을 확인할 수 있습니다.

인덱스가 없을 경우 전체 테이블 스캔이 이루어지며, 단순 조회 시 약 11ms ~ 14ms의 실행 시간이 소요되었습니다.

(인덱스 생성 소요 시간: 약 1.105초)

복합 인덱스 (reservation_start_at, reservation_end_at) 적용 후, 범위 스캔(range)과 인덱스 조건 필터링이 가능해져 실행 시간이 약 8.4ms ~ 9ms로 단축되었습니다.

• 실행 시간 비교: 15%~25%의 성능 향상을 달성하였습니다.
• 평가: 비록 절대 실행 시간이 밀리초 단위로 차이가 나지만, 고부하 환경에서는 누적 효과가 크며, 인덱스를 통한 범위 스캔 및 인덱스 조건 필터링이 효율적으로 작동함을 확인할 수 있습니다.

• 초기 인덱스 생성 비용:

  • concertschedule의 경우 1.105초, seat의 경우 2초 정도의 초기 인덱스 생성 비용이 발생하지만, 장기적으로 조회 성능 향상 효과가 이를 상쇄합니다.

• 실행 시간 단축 효과:

  • seat 테이블은 전체 스캔에서 인덱스 활용으로 약 200배 이상의 성능 향상이 나타났으며,
  • concertschedule 테이블은 고부하 상황에서 약 15%~25%의 향상이 관찰되었습니다.
  • 하지만 seat 대상 쿼리에 비해 향상이 도드라지지 않은 부분에 대한 고민이 필요했습니다.
  • 이는 이미 reservation_start_at 과 reservation_end_at 필드의 선택도가 이미 충분히 높아 인덱스가 적용되지 않아도 효율적으로 처리가 되고 있었기 때문이라고 생각합니다.

• 인덱스 유효성:

  • 두 테이블 모두 인덱스 적용으로 불필요한 전체 스캔을 피하고, 필요한 행만을 빠르게 조회할 수 있게 되어 인덱스의 유효성이 입증되었습니다.

• 데이터 10만 개 대상 실험 시 지나치게 빠른 쿼리 실행 속도를 보여 당황했습니다.
• 심지어 인덱스 적용 전/후의 차이가 거의 없었습니다.

이러한 현상의 원인으로 크게 다음의 네 가지를 고려해보았습니다.

• 실험 환경 원인 : MySQL 서버가 결국 내 컴퓨터의 로컬 자원에 근거하여 동작하고 있기 때문에 실제로는 SSD I/O 발생 -> 아주 빠를 것. (HDD 기반의 I/O => 1/100)
• 모수 데이터 크기 원인 : MySQL Optimizer 및 설계자들이 바라보고 자신들의 프로덕트가 활용되길 기대하는 환경에 비해 턱없이 모자란 100,000 개의 데이터.
• 가설 수립 근거가 충분하지 않음 : 논리적으로도 이미 해당 쿼리가 충분히 빠를 수 있다.
• 내가 파악하지 못한 MySQL 의 최적화

• 알고보니 INSERT & Import From Data 하는 과정에서 InnoDB 의 Buffer Pool 에 바로 써버리는 최적화가 존재이걸 당했다.

InnoDB의 Buffer Pool 이란, 빠른 Data fetch 를 위해 InnoDB에게 할당된 메모리 영역 중 Schema 별 Row를 복사해두기 위해 일부 할애한 영역.

읽기 지연 시간 단축을 위함.

• 이 부분이 작용하여 쿼리의 처리 속도가 비정상적으로 빨라 10만 건의 데이터 조회 실험에서 신뢰할 수 있는 실험 결과가 도출되지 않았던 것이었습니다.
• 이를 해결하기 위해 Buffer Pool 을 8MB 로 제한하여 실행하였더니 통상적인 상황에서의 결과라고 생각할 수 있는 수치가 도출되었고 인덱스 적용 전후의 차이도 발견했습니다.

실제로는 위의 가설 모두 비율의 차이일뿐 해당 현상에 영향을 주었다고 생각합니다. 하지만 가장 도드라진 기여도를 차지한 것은 역시 MySQL Buffer Pool 활용 최적화로 인해 Table 의 Row 대부분이 메모리에 적재되어 아주 빠르게 처리되었기 때문을 확인하였습니다!