Database - Mysql 기반으로 Index 에 대해 Deep Dive 해보자

Index 자주 사용하지만.. 잘 알고 있으신가요?

안녕하세요 ㅎㅎ 

회사에 입사해서 비즈니스 통계 데이터를 추출하다 보니, 문득 그런 생각이 들었습니다.

Index를 이용한 select query 를 만들고 plan 을 해보고 있지만, 정말 나는 Index 에 대해 완벽히 알고 있을까?

Index 를 사용하는 방법은 알지만, 어떻게 하면 효율적인 query 를 작성하고, 어떻게 하면 올바르게 Index 를 설계하는지 알고 있는걸까?

 

개발하다 보니 너무 궁금해져서 본격적으로 Deep Dive 를 하고 싶게 되어 준비하게 되었습니다.

 

Index 란 무엇일까?

그럼 우리는 Index 가 무엇인지를 알아야 합니다.

Index

Index 란 본래 Table 에 저장되어 있는 데이터를 쉽게 찾기 위한 색인 이라고 정의합니다.

따라서 별도의 메모리로 Index 기반의 실제 저장되어 있는 데이터의 물리적 주소를 저장한다고 보면 될 것 같아요.

 

별도의 메모리로 운영하기 때문에, Insert / Update / Delete 와 같은 데이터 변경시에 DB 에도

더 많은 변경이 있어서 성능이 조금 느려지지만, Select 성능은 그만큼 많이 올리게 되는 것이죠.

주의해야 할 것은 데이터 변경에 대한 행위만 느려질 뿐 검색은 향상 됩니다.

Index 가 무엇인지 이해하였죠? 그러면 어떻게 Index 는 데이터를 빠르게 탐색할까요?

Index 는 어떻게 데이터를 빠르게 탐색할까?

우리가 알고 있는 DBMS 는 B-Tree 의 자료 구조이다.

B-Tree 자료구조

Index 기반으로 하는 B-Tree 의 자료구조는 크게 3가지 레벨로 구성되어 있습니다

Root -> Branch(Internal) -> Leaf

위 구조에서 가장 눈여겨 볼 것은, 상위 레벨에서는 하위 레벨에 대한 key 값의 range 정보를 가지고 있다는 것입니다.

 

결국에 이 구조를 이해한 것만으로도 select query 를 작성할 때  range scan 이 어떻게 되는지를 이해할 수 있습니다.

range scan(범위 스캔) 이라는 것은 특정 key 값의 범위에 대해서만 검색을 할 수 있습니다.

 

어쨌든 다시 돌아와서 ㅎㅎ

그러면 Leaf Node 에 있는 데이터가 실질적으로 데이터가 저장되어 있는 위치인가요? 

하고 물어보신다면 아닙니다.

 

Leaf Node 에 있는 데이터는 테이블 레코드를 가리키는 주소값 즉, ROWID 값을 가지게 됩니다.

최종적으로 데이터를 탐색해본 다는 것은 데이터가 담겨져 있는 주소값을 탐색한다는 의미이고, 우리는 이 주소값을 빠르게 찾기 위한 query 를 작성해야 됩니다.

Index 탐색 과정

Index 는 총 2가지 탐색 과정에 의해서 탐색하게 됩니다.

• 수직적 탐색: 인덱스 스캔 시작지점을 찾는 과정
• 수평적 탐색: 데이터를 찾는 과정

어려우니까 바로 그림으로 가보죠 ㅎㅎ

Index 탐색 방법

그림으로 보면서 쉽게 이해를 해보자면..

 

수직적 탐색 은 Root -> Branch -> Leaf 로 탐색하여 검색조건을 만족하는 첫 번째 레코드를 찾는 것을 목표로 합니다.

예를 들면, 12~40 번을 검색한다고 했을 때 Root 1 -> Branch 2 -> Leaf 5 순으로 탐색하는 것이죠.

빨간색으로 표시를 해두었지만 검색조건을 만족하는 모든 레코드를 찾는 것이 아닌 것을 유의해주세요!

 

수평적 탐색 은 수직적 탐색에서 찾은 첫 번째 레코드를 바탕으로, 찾고자 하는 데이터가 더 안나올때 까지 Leaf Block 을 수평적으로 스캔합니다.

예를 들어서, 12 ~ 40을 검색한다고 했을 때 수직적 탐색을 통해 12 번을 찾았으면 Leaf Block 에서 40번까지 다 찾는 과정을 의미합니다.

여기서는 획득한 ROWID 기반으로 실제 테이블을 액세스하게 됩니다.

 

그러면 우리는 한번 생각해볼 수 있는 것이.. 이 탐색 기반으로 어떻게 인덱스를 설계하는 것이 올바를까요?

수직적 탐색을 통해, 최대한 빠르게 첫번째 레코드 시작점을 찾고.. 수평적 탐색에 해당하는 범위 검색 대상의 레코드 수를 줄이는 것이 중요해지게 되는 것입니다.

 

그럼 어떻게 하면 검색 대상의 레코드 수를 효과적으로 빠르게 줄일 수 있을까요?

Index 를 효율적으로 어떻게 사용할까?

수평적 탐색에 대한 범위 검색 대상의 레코드 수를 줄이기 위해서는, 첫번째는 카디널라티가 높아야 합니다.

카디널라티가 무엇일까요?

카디널리티란 데이터 고유 값이 존재하는 정도 입니다.
카디널리티가 높다는 것은 데이터 중복이 거의 없다는 것이며, 카디널리티가 낮다는 것은 데이터 중복이 많다는 것입니다

뒤에 예시에서 나타낼 것이니까 이정도만 하고 넘어가겠습니다.

 

두번째는 선택도가 높아야 합니다.

선택도가 높다는 것은 조건절에 자주 사용되거나, '=' 조건으로 자주 조회되는 컬럼을 의미합니다.

 

대표적으로 varchar 타입의 like query 의 '%' 검색은 Index 로 지정해주어봤자 아무런 의미가 없다는 말과 일치합니다.

사실상 많은 수의 데이터를 탐색한다는 것과 일치하니까요.

 

카디널리티를 높게 하고, 선택도를 높게 하기 위해서 대부분의 경우에는 결합 Index 를 생성하고는 합니다.

이 결합 Index 에 대한 이해와 우리가 지금껏 배운 Index 에 대한 개념을 정리하기 위해 예제를 통해 알아보도록 할게요 

 

결합 Index 예시

아래와 같은 Table 을 만들고, 데이터는 대략적으로 100만건을 미리 삽입을 해놓았습니다.

import org.springframework.data.annotation.CreatedDate
import java.math.BigDecimal
import java.time.ZonedDateTime
import javax.persistence.*

@Entity
@Table(name = "order_table")
class OrderTable(
    @Id
    @GeneratedValue
    val id: Long? = null,

    @Column(name = "purchaser_id", nullable = false)
    val purchaser: Long,

    @Column(name = "seller_id", nullable = false)
    val seller: Long,

    @Column(name = "gift", nullable = false)
    val isGift: Boolean,

    @Column(name = "service_location", length = 20)
    val serviceLocation: String?,

    @Column(name = "pay_amount", scale = 2)
    val payAmount: BigDecimal,
) {
    @CreatedDate
    @Column(name = "created_at", nullable = false)
    var createdAt: ZonedDateTime = ZonedDateTime.now()

    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (other !is OrderTable) return false

        if (id != other.id) return false

        return true
    }

    override fun hashCode(): Int {
        return id.hashCode()
    }
}

JPA 를 사용하여 위 테이블에 대한 DDL 을 만들게 되면 아래와 같습니다.

-- auto-generated definition
create table order_table
(
    id               bigint         not null
        primary key,
    created_at       datetime       not null,
    gift             bit            not null,
    pay_amount       decimal(19, 2) null,
    purchaser_id     bigint         not null,
    seller_id        bigint         not null,
    service_location varchar(20)    null
)

그리고 나서 임의로 데이터를 insert 해놓고, 전체적인 카디널리티를 아래와 같이 설정하였습니다.

select
    count(distinct id) 'id',
    count(distinct purchaser_id) 'purchaser',
    count(distinct seller_id) 'seller',
    count(distinct gift) 'gift',
    count(distinct pay_amount) 'pay_amount',
    count(distinct service_location) 'service_location'
from order_table
;

간단하게 테스트 할 수 있는 데이터를 준비하였습니다. 

저는 총 2가지 검증대한 테스트를 진행할 것인데요.

 

1. 카디널리티에 따라서 정말 성능차이가 있을까?
2. 복합 Index 를 사용하는 경우 인덱스 조건에 대한 누락이 있으면 어떻게 될까?

한번 진행해보겠습니다.

카디널리티에 따른 성능 차이가 있을까?

주문 데이터를 찾아보고 싶은데, 요구사항은 구매유형(buy/gift), 샐러(seller_id), 결제금액(pay_amount) 기준으로 집계를 하고 싶습니다.

 

2가지 Index 를 만들어보겠습니다.

첫번째는 카디널리티가 낮은 순서에서 높은 순서대로 진행해보고, 

두번째는 카디널리티가 높은 순서에서 낮은 순서대로 진행해볼게요.

create index order_table__gift_index
    on order_table (gift, seller_id, pay_amount);

create index order_table__pay_amount_index
    on order_table (pay_amount, seller_id, gift);

그러면 한번 결과를 살펴보러 갈까요? ㅎㅎ

test_db> select * from order_table
         use index(order_table__gift_index)
         where
             pay_amount between 200000 and 300000
         and seller_id = 5000
         and gift is true
[2022-06-26 18:58:06] 9 rows retrieved starting from 1 in 1 s 882 ms (execution: 1 s 863 ms, fetching: 19 ms)

첫번째 Index 의 경우에는 9 개의 row 를 가져오는데에 1초 882ms 가 소요되었습니다.

test_db> select * from order_table
         use index(order_table__pay_amount_index)
         where
             pay_amount between 200000 and 300000
         and seller_id = 5000
         and gift is true
[2022-06-26 18:58:32] 9 rows retrieved starting from 1 in 76 ms (execution: 55 ms, fetching: 21 ms)

반대로 두번째 Index 의 경우에는 9 개의 row 를 가져오는데 76ms 가 소요되었습니다.

놀라운 결과죠? 카디널리티에 따라서 쿼리 성능은 확연하게 차이가 납니다.

 

한번 쿼리 Plan 까지 확인해볼까요? 

쿼리 Plan 을 해석하는 방법에 대해서는 아래 게시글을 참조해주세요 :)

https://huisam.tistory.com/entry/mysql-plan-query?category=689280 

Mysql Query Plan - Intellij 를 활용하여 Plan query 를 해보자

첫번째 Index 에 대한 쿼리 plan 입니다. 

type 이 ALL 이라는 것은 Full scan 을 의미합니다.

사실상 Index 가 아무런 효용도 얻지 못하고 있습니다. 차이가 없는 것이죠

반대로 두번째 Index 대한 쿼리 plan 은 type 이 range 입니다. 범위에 대한 scan 이 이루어진다는 것을 의미합니다.

결과적으로 비교 연산에 대한 횟수를 줄이기 위해서라도 카디널리티는 Index 설계에 아주 중요한 요소를 하게 됩니다.

 

복합 Index 에서 조건절에 일부 누락되면 어떻게 될까?

새로운 Index 를 만들어서 한번 테스트해보겠습니다. 

이번에는 샐러(seller_id), 구매자(purchaser_id) 기반으로 복합 Index 를 만들어볼게요.

create index order_table__seller_purchaser_index
    on order_table (seller_id, purchaser_id);

여기서 구매자만 where 절에 추가하는 select 쿼리와 샐러만 where 절에 추가하는 select 쿼리를 만들어보겠습니다.

explain select * from order_table
use index(order_table__seller_purchaser_index)
where
purchaser_id between 1 and 10

아쉽게도 Index 를 타지 않고 테이블을 Full scan 하게 됩니다.

explain select * from order_table
use index(order_table__seller_purchaser_index)
where
    seller_id = 5000

반대로 샐러정보를 기반으로 검색하게 되면?

type 이 Ref 이고 Index 를 타는 것을 볼 수 있습니다.

 

결과적으로 복합 Index 에서 첫번째 column 은 항상 조건절에 있어야 된다.

라는 결론을 얻을 수 있습니다.

 

지금까지 게시글을 보았을 때 결과적으로 Index 를 사용하는 것이 효과적으로 보입니다. 하지만 정말 그럴까요?

Index 가 항상 모든 검색에 효율적일까?

Index 를 통해 검색하게 되면 항상 속도가 빠르기 때문에, 좋아보이긴 합니다.

Index 를 통해 검색한다는 것은 데이터베이스에서 데이터를 읽을 때 Single Block I/O 기반으로 읽게 됩니다.

Single Block I/O 는 한개의 block 을 I/O 로 담아서 실어나른다고 이해하면 됩니다.

그렇기 때문에 소량 데이터를 읽을 때 효과적이라고 볼 수 있겠죠

 

반대로 Table Full scan 한다는 것은 Multi Block I/O 기반으로 읽게 됩니다.

Multi Block I/O 는 여러개의 block 을 한번에 I/O 로 담아서 실어나른다고 이해하면 됩니다.

그렇기 때문에 대량의 데이터를 읽을 때 효과적이라고 볼 수 있습니다.

 

그래서 Table Full scan 이 항상 나쁘다고 볼 수 없습니다. 

많은 Query Plan 에서 Table Full scan 이 빨간색으로 강조되어 개발자들이 꺼려하는 경향이 있는데, 꼭 그게 아닙니다.

오히려 대량의 데이터를 추출하는데, Index 를 태우는 것이 더 성능이 나빠지는 경우가 많습니다.

B-Tree 자료구조에서 수백만~수천만건의 데이터 추출이 필요한 경우에는 오히려 Index 가 효율성이 떨어집니다.
왜냐하면, Branch Node 와 Leaf Node 를 왔다갔다 하면서 분산화된 Table Access 를 진행하게 되니까요.
오히려 이 경우에는 Table Full scan 을 통해 모든 block 을 읽게 하는 것이 더 효율적인 경우가 많기 때문이죠.

그래서 정리하면 아래와 같습니다.

접근 방식	사용 목적
Table Full scan	Multi Block I/O 이기 때문에 집계성 SQL / 배치 프로그램에 유용 (수백만 ~ 수천만)
Index Range scan	Single Block I/O 라서 소량의 데이터를 추출하는 비즈니스 쿼리에 유용

정리하며

Index 에 대해 정리해보고, 실험해보았네요 ㅎㅎ

물론 아주 자세하게 모든 원리에 대해 정리해보지는 못하였지만, 실무에서 이해하고 쓸 정도로 간략하게 정리해보았어요.

• Index 는 B-Tree 기반의 자료구조에서 검색을 도와주는 색인
• 수직적 탐색과 수평적 탐색 기반으로 진행되는 탐색 구조
• 카디널라티 와 선택도 에 따라서 효율적으로 설계를 진행
• 복합 Index 를 지정할 때는 비교 연산을 줄이기 위해 우선 순위에 신경 쓸 것
• 테이블을 검색할 때 Index 가 항상 효율적인 것은 아님

으로 정리할 수 있을 것 같습니다 ㅎㅎ

참고

친절한 SQL 튜닝