[SolveGO #19] 정답을 찾는다는 건 - DB Index 이론, 성능 실험과 개선

 

 
 
 
 

 
인생을 살아감에 있어, 정답을 찾는다는 것은 과연 의미가 있을까? 애초에 정답은 존재하는 것일까? 그리고 설령 존재한다 하더라도, 우리는 그것을 찾을 수 있을까?
 
하지만 설령 정답이 존재하지 않더라도, 정답을 찾으려는 행위 자체는 충분한 가치가 있다. 그 과정에서 우리는 어떤 것이 자신의 정답이 아닌지를 하나씩 알아가며 결국 자기 자신을 탐색하게 되기 때문이다.
 
한때는 열정적으로 좋아했던 일에 번아웃을 겪으며 지속 가능한 열정이 아니라는 사실을 깨닫기도 하고, 과거의 자신이 옳다고 믿었던 가치관이 더 이상 자신의 정답이 아님을 뒤늦게 깨닫게 되기도 한다. 결국 인생에서 정답을 찾는다는 것은, 역설적이게도 정답을 발견하는 과정이라기보다 정답이 아닌 것들을 하나씩 제외해 나가는 과정이 아닐까.
 

 

 

탐색(Search)의 본질 역시 동일하다. 탐색은 정답을 직접 찾아내는 행위가 아니라, 정답이 존재할 수 없는 후보를 제거하는 과정이다. 즉 정답이 어떤 공간 안에 존재한다면, 탐색 알고리즘의 성능은 정답이 존재할 수 없는 공간을 얼마나 효율적으로 제거하느냐에 달려있다. 한 번의 판단으로 많은 후보를 제거할수록 성능이 높아지게 되는 것이다. 
 
 

 
 
탐색에 있어서 가장 단순한 방법은 공간을 분할하지 않고 후보를 하나씩 제거하는 선형 탐색(Linear Search)이다. 그러나 이 방법은 후보를 하나씩만 제거하므로 데이터가 많아질수록 비효율적이다(O(N)). 반면, 공간이 정렬되어 있다면 기준값 하나만으로 후보 공간의 절반을 제거할 수 있으며, 이를 이진 탐색(Binary Search)이라고 한다(O(logN)).
 
 

 

 
 
이진 탐색은 매우 효율적인 탐색 알고리즘이지만, 한 가지 중요한 전제가 있다. 데이터가 항상 정렬된 상태를 유지해야 한다는 점이다. 문제는 실제 시스템의 데이터는 끊임없이 추가되고 삭제된다는 것이다. 새로운 데이터가 삽입될 때마다 정렬을 유지하기 위해 많은 데이터를 이동시켜야 하며, 이 비용은 데이터가 많아질수록 무시할 수 없게 된다. 그렇다면 정렬된 상태를 유지하면서도, 많은 데이터를 이동시키지 않고 효율적으로 탐색할 수 있는 방법은 없을까?
 

 
이러한 고민에서 등장한 것이 Binary Search Tree(BST)이다. BST는 데이터를 연속된 배열에 저장하는 대신, 기준값을 중심으로 탐색 공간을 왼쪽과 오른쪽으로 분할하는 구조이다. 따라서 배열처럼 삽입 시 뒤의 모든 데이터를 이동시킬 필요 없이, 적절한 위치에 새로운 노드를 연결하기만 하면 된다.
 
 
하지만 BST에도 한계는 존재한다. 데이터가 균등하게 삽입된다면 탐색과 삽입 모두 효율적으로 수행할 수 있지만, 데이터가 한쪽으로만 삽입될 경우 트리의 균형이 무너지게 된다. 
 

 

 

 

 
이처럼 트리가 한쪽으로 치우치면 탐색 공간을 절반씩 줄여 나갈 수 없게 되고, 결국 선형 탐색과 다를 바 없는 O(N)의 성능을 가지게 된다. 그렇다면 트리의 균형을 유지하면서도, 트리의 높이를 더 낮출 수는 없을까?
 

 

 

AVL Tree나 Red-Black Tree와 같은 균형 이진 탐색 트리는 일반 BST가 한쪽으로 치우치는 문제를 해결한다. 트리의 균형을 유지함으로써 탐색,삽입,삭제를 일반적으로 O(log N)에 수행할 수 있다.
 

 
하지만 데이터베이스 환경에서는 단순히 시간 복잡도가 O(log N)이라는 사실만으로는 충분하지 않다. 데이터베이스의 데이터는 대부분 메모리가 아니라 디스크에 저장되며, 트리의 다음 노드로 이동할 때마다 해당 노드가 저장된 디스크 영역을 새로 읽어 와야 할 수 있기 때문이다.
 
CPU가 현재 노드 안의 값들을 비교하는 작업은 매우 빠른 반면, 디스크에서 새로운 데이터를 읽어 오는 작업은 상대적으로 훨씬 느리다. 따라서 데이터베이스에서는 비교 횟수보다 트리의 몇 개 층을 거쳐야 하는가, 즉 트리의 높이가 더욱 중요해진다.

 

이진 탐색 트리는 노드 하나에 기준값 하나를 저장하므로, 각 노드에서 탐색 공간을 두 구간으로만 나눈다.

              50
             /  \
          < 50   > 50

 

예를 들어 트리의 높이가 4라면, 루트에서 리프까지 내려가는 동안 최대 네 개의 노드에 접근해야 한다. 트리 높이가 곧 필요한 페이지 접근 횟수의 상한이기 때문이다. 따라서 각 노드가 서로 다른 디스크 영역에 저장되어 있다면 디스크 읽기는 여러 번 발생할 수 있다.

 

그렇다면 한 노드에 더 많은 기준값을 저장하면 어떨까?

        [20 | 50 | 80]
        /    |    |    \
     <20  20~50 50~80  >80

 

기준값 세 개가 들어 있는 노드는 탐색 공간을 한 번에 네 구간으로 나눈다. 목표값이 65라면 50~80 구간만 선택하고 나머지 세 구간은 한 번에 제외할 수 있다. 이처럼 한 노드가 더 많은 자식을 가지면, 같은 수의 데이터를 훨씬 적은 층에 저장할 수 있다. 트리의 높이가 낮아지면 루트에서 리프까지 이동하면서 발생하는 디스크 접근 횟수도 함께 감소한다.

 

 

이러한 아이디어를 적용한 자료구조가 B-Tree이다. B-Tree는 하나의 노드에 여러 개의 정렬된 키를 저장하고, 그 키들을 경계로 탐색 공간을 여러 구간으로 나눈다. 또한 삽입과 삭제 과정에서 노드를 분할하거나 병합하며 모든 리프 노드의 깊이를 동일하게 유지한다.

 

 
그렇다면 데이터베이스는 왜 B-Tree에서 멈추지 않고 B+Tree를 사용하는 것일까?
B-Tree는 단일 값 탐색에는 효율적이지만, 데이터베이스에서 자주 수행되는 범위 조회에는 다소 불리하다. B-Tree에서는 실제 데이터가 내부 노드와 리프 노드에 모두 저장될 수 있고, 리프 노드끼리도 직접 연결되어 있지 않다. 따라서 특정 범위의 데이터를 순서대로 읽으려면 트리의 여러 노드를 오르내려야 할 수 있다. 또한 내부 노드에 실제 데이터까지 저장하면, 크기가 정해진 하나의 페이지 안에 담을 수 있는 키와 자식 포인터의 수가 줄어든다. 이는 분기 수를 낮추고, 결과적으로 트리의 높이를 다시 키울 수 있다.
 
이러한 한계를 보완하기 위해 등장한 구조가 B+Tree이다. B+Tree는 내부 노드에는 탐색을 위한 키와 자식 포인터만 저장하고, 실제 데이터는 모두 리프 노드에만 저장한다. 덕분에 내부 노드는 실제 데이터를 저장하지 않아도 되므로, 같은 크기의 페이지 안에 더 많은 키와 자식 포인터를 저장할 수 있다. 이는 하나의 노드가 더 많은 탐색 공간을 분할할 수 있음을 의미하며, 결과적으로 트리의 높이를 더욱 낮출 수 있다.
또한 B+Tree의 모든 리프 노드는 순차적으로 연결 리스트 형태로 연결되어 있다. 따라서 특정 값 하나를 찾는 것은 물론, 범위의 시작 지점만 찾으면 이후의 데이터는 리프 노드를 따라 연속적으로 읽어 나갈 수 있다. 이런 구조 덕분에 범위 조회와 정렬된 순회가 매우 효율적으로 수행된다. 즉, B+Tree는 B-Tree의 균형성과 높은 분기 수는 그대로 유지하면서, 실제 데이터를 리프 노드에 집중시키고 리프 노드를 연결하여 데이터베이스 환경에 더욱 적합하도록 개선한 탐색 트리이다.
 
 
그렇다면 데이터베이스는 B+Tree를 실제로 어디에 사용할까?

대표적인 예가 바로 인덱스(Index)이다. 인덱스는 특정 컬럼의 값을 B+Tree 형태로 미리 정렬하여 저장하는 자료구조이다. 테이블 전체를 처음부터 끝까지 탐색하는 대신, B+Tree를 이용해 원하는 데이터가 존재할 가능성이 있는 공간만 빠르게 탐색할 수 있다.
 

 
 
MySQL의 기본 저장 엔진인 InnoDB에서는 Primary Key와 보조 인덱스를 모두 B+Tree 구조로 관리한다. 다만 두 인덱스의 리프 노드에 저장되는 내용은 서로 다르다. Primary Key 인덱스의 리프 노드에는 실제 행 전체가 저장된다. 반면 created_at과 같은 보조 인덱스의 리프 노드에는 인덱스 컬럼 값과 해당 행의 Primary Key가 저장된다.

Primary Key 인덱스

id = 6
→ 실제 Row 전체

created_at 보조 인덱스

2026-07-12 10:00:00
→ id = 6

 
 
따라서 created_at 보조 인덱스를 통해 특정 데이터를 조회할 때는 먼저 B+Tree에서 조건에 맞는 created_at 값을 찾고, 그 리프 노드에 저장된 Primary Key를 얻는다. 이후 Primary Key 인덱스를 다시 탐색하여 실제 행 전체를 가져온다. 이 과정을 PK Lookup 이라 한다.

created_at 보조 인덱스 탐색
→ PK 발견
→ Primary Key 인덱스 탐색
→ 실제 Row 조회

 
 
 
 

---

 

SolveGO 프로젝트의 성능 실험

 

Q. 인덱스가 얼마나 효과적인가

 
SolveGO 프로젝트에서도 문제 목록을 최신순으로 조회하기 위해 createdAt을 기준으로 내림차순 정렬하고 있었다.

public interface ProblemRepository extends JpaRepository<Problem, Long> {
    @Query("""
       select p
       from Problem p
       join fetch p.creator
       order by p.createdAt desc
       """)
       List<Problem> findAllWithCreatorOrderByCreatedAtDesc();
}

 

join fetch는 문제를 등록한 사용자 정보를 함께 조회하여 N+1 문제를 방지하기 위한 것이고, 이번 인덱스 성능 개선에서 주목할 부분은 order by p.createdAt desc이다. created_at 인덱스가 없다면 MySQL은 조건에 맞는 행들을 읽은 뒤 별도의 정렬 작업을 수행해야 한다. 반면 created_at을 기준으로 구성된 B+Tree 인덱스가 있다면, 리프 노드에 이미 정렬된 순서대로 접근할 수 있으므로 정렬 비용을 줄일 가능성이 생긴다.
 
물론 인덱스를 생성했다고 해서 MySQL이 항상 인덱스를 사용하는 것은 아니다. 데이터의 개수나 분포, 쿼리의 형태에 따라 옵티마이저는 전체 테이블을 읽는 것이 더 빠르다고 판단할 수도 있다. 따라서 인덱스가 실제로 사용되었는지는 실행 계획(Execution Plan)을 확인해야 한다. MySQL에서는 EXPLAIN 명령어를 통해 쿼리가 어떤 방식으로 실행되는지 확인할 수 있다.
 

mysql> EXPLAIN
    -> SELECT *
    -> FROM problems
    -> ORDER BY created_at DESC;
+----+-------------+----------+------------+------+---------------+------+---------+------+------+----------+----------------+
| id | select_type | table    | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra          |
+----+-------------+----------+------------+------+---------------+------+---------+------+------+----------+----------------+
|  1 | SIMPLE      | problems | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 1001 |   100.00 | Using filesort |
+----+-------------+----------+------------+------+---------------+------+---------+------+------+----------+----------------+
1 row in set, 1 warning (0.00 sec)

 
EXPLAIN을 실행하면 MySQL이 어떤 테이블부터 읽는지, 어떤 인덱스를 후보로 고려했는지, 실제로 어떤 인덱스를 선택했는지, 대략 몇 개의 행을 확인할 것으로 예상하는지 등을 확인할 수 있다. 특히 주목할 항목은 possible_keys, key, rows, Extra이다.
 

possible_keys : 사용할 수 있다고 판단한 인덱스 후보
key :  실제로 선택한 인덱스
rows : 확인할 것으로 예상한 행의 수
Extra : Using filesort

 
 
인덱스의 동작을 확인하기 위해 프로시저를 이용하여 Mock Problem 데이터 1,001건을 생성한 뒤 실행 계획을 비교하였다.

먼저 인덱스를 생성한다.

mysql> CREATE INDEX idx_problems_created_at
    -> ON problems (created_at DESC);
Query OK, 0 rows affected (0.14 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> SHOW INDEX FROM problems;
+----------+------------+-------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table    | Non_unique | Key_name                | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+----------+------------+-------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| problems |          0 | PRIMARY                 |            1 | id          | A         |        1001 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| problems |          1 | fk_problems_creator     |            1 | creator_id  | A         |           2 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| problems |          1 | idx_problems_created_at |            1 | created_at  | D         |        1001 |     NULL |   NULL | YES  | BTREE      |         |               | YES     | NULL       |
+----------+------------+-------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
3 rows in set (0.01 sec)

PK, FK와 더불어 방금 생성된 idx_problems_created_at 인덱스가 B+Tree로 관리되고 있는 모습을 확인할 수 있다.
 
이후에는 EXPLAIN ANALYZE를 통해 실제 실행 결과를 측정하였다.
(페이지네이션 기능을 제공한다 가정하여 LIMIT 제약을 걸어두었고, 인덱스 유무에 따른 성능 측정이 주 목표이므로 join fetch를 제거 하여 problems 테이블만 조회하도록 하였다 이는 실험 전반에 걸쳐 일관되게 유지한 SQL 문이다)

mysql> EXPLAIN ANALYZE
    -> SELECT *
    -> FROM problems
    -> ORDER BY created_at DESC
    -> LIMIT 20;
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                                                                                                                         |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Limit: 20 row(s)  (cost=105 rows=20) (actual time=1.33..1.34 rows=20 loops=1)
    -> Sort: problems.created_at DESC, limit input to 20 row(s) per chunk  (cost=105 rows=1001) (actual time=1.33..1.33 rows=20 loops=1)
        -> Table scan on problems  (cost=105 rows=1001) (actual time=0.0249..1.03 rows=1001 loops=1)
 |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

 

 

실행 결과를 보면, created_at 인덱스는 존재했지만 옵티마이저는 해당 인덱스를 선택하지 않았다. 대신 problems 테이블의 1,001개 행을 모두 읽는 Table scan을 수행한 뒤, created_at DESC 기준으로 별도의 정렬 작업을 진행하고 최종적으로 상위 20개 행만 반환하였다.
 
 
 
 

mysql> EXPLAIN ANALYZE
    -> SELECT *
    -> FROM problems FORCE INDEX (idx_problems_created_at)
    -> ORDER BY created_at DESC
    -> LIMIT 20;
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                            |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Limit: 20 row(s)  (cost=5.04 rows=20) (actual time=0.0483..0.09 rows=20 loops=1)
    -> Index scan on problems using idx_problems_created_at  (cost=5.04 rows=20) (actual time=0.0429..0.0834 rows=20 loops=1)
 |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.01 sec)

 
위와 같이 강제로 idx_problems_created_at 인덱스를 사용하도록 하자 실행 과정이 다음과 같이 바뀌었다.
Index scan -> Limit 기본 실행에서는 Table scan → Sort → Limit 순서로 처리되었지만, 강제 인덱스 적용 후에는 Sort 단계가 사라졌다. MySQL은 created_at DESC 순서로 구성된 인덱스를 그대로 따라가며 최신 데이터부터 읽었다. 이미 인덱스 내부에 정렬 순서가 유지되고 있기 때문에, 별도의 정렬 작업을 수행할 필요가 없었다. 또한 LIMIT 20이 적용되어 있으므로 전체 1,001개 행을 읽지 않고 필요한 20개 행을 찾은 시점에서 탐색을 종료하였다.

 

 
실험 결과를 정리하면 다음과 같다. 

기본 실행 (옵티마이저 선택)
Table scan → Sort → Limit
1,001개 행 확인
약 1.34ms

강제 인덱스 실행 (FORCE INDEX)
Index scan → Limit
20개 행 확인
약 0.09ms

 

 
 
이번 단일 실행에서는 강제 인덱스를 사용했을 때 약 15배 빠른 실행 시간이 측정되었다. 다만 이는 1,001건의 데이터를 대상으로 한 단일 실행 결과이므로, 이 수치만으로 인덱스가 항상 동일한 수준의 성능 향상을 제공한다고 일반화할 수는 없다. 실제 성능은 데이터의 규모와 분포, 캐시 상태, 시스템 환경 등 다양한 요인의 영향을 받는다. 따라서 이후에는 더 많은 데이터를 대상으로 반복 측정을 수행하여 인덱스 적용에 따른 성능 변화를 추가로 검증하고자 하며, 그 결과는 이 글의 후반부에서 이어서 다룬다.
 
 

 
한편, 이번 실험에서 중요한 점은 실행 시간보다 실행 과정 자체가 달라졌다는 사실이다. B+Tree 인덱스는 리프 노드가 이미 created_at 기준으로 정렬된 상태를 유지하고 있으므로, MySQL은 인덱스를 순차적으로 탐색하기만 해도 원하는 정렬 결과를 얻을 수 있다. 따라서 기존처럼 전체 테이블을 읽은 뒤 별도의 정렬을 수행할 필요가 없으며, LIMIT 20을 만족하는 순간 탐색을 종료할 수 있다. 이는 앞에서 살펴본 '탐색 공간을 효율적으로 제거한다'는 B+Tree의 아이디어가 실제 데이터베이스에서도 그대로 적용되고 있음을 보여준다.
 
 
 
또한 혹시 옵티마이저가 오래되거나 부정확한 통계 정보를 바탕으로 실행 계획을 선택한 것은 아닌지 확인하기 위해 ANALYZE TABLE을 수행하였다.

ANALYZE TABLE problems;

 

ANALYZE TABLE은 테이블과 인덱스의 통계 정보를 갱신하여, 옵티마이저가 각 실행 방식의 비용을 보다 정확하게 추정할 수 있도록 한다. 실행 결과 status = OK가 반환되었으므로 통계 정보 갱신은 정상적으로 완료되었다.
이후 동일한 쿼리를 다시 EXPLAIN ANALYZE로 실행하였다.

mysql> EXPLAIN ANALYZE
    -> SELECT *
    -> FROM problems
    -> ORDER BY created_at DESC
    -> LIMIT 20;
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                                                                                                                          |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Limit: 20 row(s)  (cost=105 rows=20) (actual time=1.18..1.18 rows=20 loops=1)
    -> Sort: problems.created_at DESC, limit input to 20 row(s) per chunk  (cost=105 rows=1001) (actual time=1.18..1.18 rows=20 loops=1)
        -> Table scan on problems  (cost=105 rows=1001) (actual time=0.0203..0.893 rows=1001 loops=1)
 |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

 

하지만 통계 정보를 갱신한 뒤에도 실행 과정은 달라지지 않았다. MySQL은 여전히 problems 테이블의 1,001개 행을 모두 읽은 뒤, created_at DESC 기준으로 정렬하고 상위 20개를 반환하였다. 실제 실행 시간은 약 1.18ms로 이전의 1.34ms보다 소폭 줄었지만, 이는 캐시 상태나 실행 환경에 따른 변동일 수 있으며 실행 계획 자체가 개선된 것은 아니다.
 
즉, 이번 결과를 통해 옵티마이저가 인덱스를 선택하지 않은 원인이 단순히 오래된 통계 정보 때문은 아니라는 점을 확인하였다. 통계 갱신 이후에도 옵티마이저는 현재 데이터 규모와 쿼리 형태에서는 인덱스 스캔보다 전체 테이블 스캔 후 정렬하는 방식이 더 적절하다고 판단하였다.
 
 

Q. 데이터 규모가 커지면 옵티마이저의 판단이 달라지는가

 
이를 확인하기 위해 problems 데이터를 기존 1,001건에서 10,001건으로 증가시킨 뒤 동일한 쿼리를 다시 실행하였다. 데이터 추가 후 ANALYZE TABLE로 통계 정보를 갱신하고, EXPLAIN ANALYZE를 통해 실행 계획의 변화를 확인하였다.

CALL insert_test_problems(9000);

SELECT COUNT(*)
FROM problems;

COUNT(*)
10,001

ANALYZE TABLE problems;

EXPLAIN ANALYZE
SELECT *
FROM problems
ORDER BY created_at DESC
LIMIT 20;

 
그 결과, 1,001건에서는 옵티마이저가 선택하지 않았던 idx_problems_created_at 인덱스를 10,001건에서는 별도의 강제 설정 없이 자동으로 선택하였다.
 
 

Limit
→ Index scan using idx_problems_created_at

 
실행 계획에는 기존의 Table scan과 Sort 단계가 사라지고, idx_problems_created_at을 이용한 Index scan만 나타났다. MySQL은 이미 created_at DESC 순서로 정렬된 인덱스를 따라 최신 데이터부터 읽은 뒤, 20개 행을 얻은 시점에서 탐색을 종료하였다.
 

1,001건
Table Scan → Sort → Limit

10,001건
Index Scan → Limit

 
즉, 옵티마이저는 단순히 인덱스의 존재 여부만 확인하는 것이 아니라, 데이터 규모와 예상 실행 비용을 함께 비교하여 실행 계획을 선택한다. 1,001건에서는 전체 테이블을 읽고 정렬하는 비용이 충분히 작다고 판단했지만, 10,001건으로 데이터가 증가하자 전체 스캔과 정렬보다 인덱스를 이용해 필요한 20개 행만 읽는 방식이 더 효율적이라고 판단한 것이다.
 
 

Q. 실행 계획의 변화는 실제 성능 향상으로 이어질까?

 
실행 계획이 Table Scan → Sort에서 Index Scan으로 변경되었다는 사실은 확인하였다. 그렇다면 이러한 변화는 실제 실행 시간에도 유의미한 차이를 만들어낼까? 이를 확인하기 위해 10,001건의 데이터를 유지한 상태에서, 동일한 쿼리를 대상으로 인덱스를 사용한 경우와 사용하지 않은 경우를 각각 반복 실행하여 성능을 비교하였다.
 
인덱스를 사용하지 않는 경우에는 IGNORE INDEX 힌트를 이용하여 옵티마이저가 idx_problems_created_at을 선택하지 못하도록 하였고, 인덱스를 사용하는 경우에는 기본 실행 계획을 그대로 사용하였다.

 

-- 인덱스 미사용
SELECT *
FROM problems IGNORE INDEX (idx_problems_created_at)
ORDER BY created_at DESC
LIMIT 20;

-- 인덱스 사용
SELECT *
FROM problems
ORDER BY created_at DESC
LIMIT 20;

 

두 쿼리를 동일한 환경에서 각각 반복 실행하여 평균 실행 시간을 비교하였다.
 
 
측정은 Python의 PyMySQL을 이용하여 하나의 데이터베이스 연결을 유지한 상태에서 수행했다. 매 실행마다 새로운 연결을 생성할 경우 연결 설정 시간이 측정값에 포함될 수 있으므로, 최초 한 번만 MySQL에 연결한 뒤 동일한 연결에서 쿼리를 반복 실행하였다. 또한 초기 디스크 접근과 버퍼 풀(Buffer Pool) 적재의 영향을 줄이기 위해 각 쿼리를 먼저 10회씩 실행하고 해당 결과는 측정에서 제외하였다. 이후 인덱스를 사용하지 않는 쿼리와 인덱스를 사용하는 쿼리를 각각 100회씩 실행하였다. 특정 쿼리가 항상 먼저 실행되어 발생할 수 있는 순서 편향을 줄이기 위해 두 쿼리의 실행 순서는 번갈아 변경하였다.
 
측정 결과는 다음과 같았다.

 
인덱스를 사용하지 않은 경우에는 MySQL이 10,001개의 행을 모두 읽은 뒤 created_at DESC 기준으로 정렬하고, 그중 상위 20개의 행을 반환하였다. 반면 인덱스를 사용한 경우에는 이미 created_at DESC 순서로 정렬된 인덱스를 따라가며 필요한 20개의 행을 찾은 시점에서 탐색을 종료하였다.
 
그 결과 인덱스를 사용한 쿼리는 인덱스를 사용하지 않은 쿼리보다 평균 기준 약 13.27배, 중앙값 기준 약 12.90배 빠르게 실행되었다.
또한 평균과 중앙값이 거의 동일하게 나타났으며, 표준편차 역시 각각 0.2499ms와 0.0868ms로 매우 작았다. 이는 일부 예외적으로 빠르거나 느린 실행이 평균을 크게 왜곡한 것이 아니라, 대부분의 반복 실행에서 유사한 성능 차이가 안정적으로 나타났음을 의미한다.
 
이번 실험은 동일한 MySQL 연결을 유지한 상태에서 수행되었으며, 두 쿼리는 동일한 데이터, 동일한 반환 행 수(LIMIT 20), 동일한 환경에서 오직 created_at 인덱스 사용 여부만 달랐다. 따라서 반복 측정을 통해 확인된 성능 차이는 실행 계획의 변화에 따른 영향으로 해석할 수 있다.
 
다만 이번 결과는 현재 EC2 인스턴스, MySQL 설정, 버퍼 캐시 상태, 10,001개의 데이터, 그리고 LIMIT 20이라는 조건에서 측정된 결과이다. 따라서 인덱스가 모든 환경에서 항상 약 13배의 성능 향상을 제공한다고 일반화할 수는 없다. 그럼에도 이번 실험을 통해 데이터 규모가 증가하자 옵티마이저가 Table Scan → Sort → Limit 대신 Index Scan → Limit 실행 계획을 선택하였고, 이러한 실행 계획의 변화가 실제 반복 성능 향상으로 이어졌음을 확인할 수 있었다. 실험 스크립트는 아래와 같다.

solvego-backend/scripts/created_at_index_benchmark.py at main · SolveGO/solvego-backend

 

---

 
 
이번 글에서는 탐색의 관점에서 B+Tree와 데이터베이스 인덱스를 살펴보고, SolveGO 프로젝트에 created_at 인덱스를 적용한 뒤 실행 계획과 반복 성능 실험을 통해 그 효과를 검증하였다.
 
인덱스는 단순히 "검색을 빠르게 해 주는 기능"이 아니다. B+Tree를 이용해 탐색 공간을 효율적으로 줄이고, 옵티마이저가 데이터 규모와 비용을 고려하여 가장 적절한 탐색 경로를 선택하도록 돕는 자료구조다.
 
흥미로운 점은 인덱스가 존재한다는 사실만으로는 충분하지 않았다는 것이다. 1,001건의 데이터에서는 옵티마이저가 전체 테이블 스캔을 선택했지만, 10,001건으로 데이터가 증가하자 인덱스 스캔을 선택하였고, 반복 측정에서도 약 13배의 성능 향상이 확인되었다. 즉, 데이터베이스는 인덱스의 존재 자체보다도 현재 상황에서 어떤 탐색 경로가 가장 효율적인지를 끊임없이 판단하고 있었다.
 
이번 실험을 통해 SolveGO 프로젝트의 문제 목록 조회 API에 created_at 인덱스를 적용하였고, 실행 계획과 반복 성능 실험을 통해 해당 인덱스가 실제 성능 향상으로 이어짐을 확인할 수 있었다. 이제는 실제 사용자들이 동시에 요청을 보내는 환경에서도 이러한 성능 향상이 유지되는지 확인해 보자.