1. 서론: 왜 내가 만든 인덱스는 실행 계획에서 무시될까?
데이터베이스 기반의 웹 애플리케이션을 개발하고 운영하다 보면 필연적으로 트래픽 증가에 따른 쿼리 지연(Slow Query) 문제와 마주하게 됩니다.
이때 많은 개발자가 직관적으로 쿼리의 WHERE 조건절에 등장하는 컬럼에 색인(Index)을 추가하여 문제를 해결하고자 합니다. 하지만 성능 개선을 위해 인덱스를 추가했음에도 불구하고, 데이터베이스의 실행 계획(Execution Plan)을 분석해보면 쿼리 옵티마이저가 기껏 만든 색인을 무시하고 여전히 전체 테이블 스캔(Full Table Scan)을 수행하는 경우를 흔히 볼 수 있습니다.
"인덱스를 생성하면 무조건 검색이 빨라질 것이다"라는 막연한 기대에 의존하기 전에, 우리는 왜 데이터베이스가 특정 상황에서 색인 사용을 포기하는지 그 근본적인 원리를 파악해야 합니다.
이 문제를 해결하려면 RDBMS(관계형 데이터베이스 관리 시스템)가 내부적으로 어떻게 실행 비용을 수학적으로 계산하고, 가장 효율적인 데이터 접근 경로를 선택하는지 이해해야 합니다 [1, 2].
특히 쿼리에 정렬 조건이 포함되어 있을 때, 잘못된 인덱스 설계는 ORDER BY 성능을 극도로 저하시키며 메모리 버퍼를 초과하여 디스크에서 정렬을 수행하는 비효율적인 상황을 초래합니다.
이 블로그 포스트에서는 MySQL 성능 최적화를 위해 색인을 어떻게 구성해야 하는지, 그리고 그 판단의 핵심 기준이 되는 '선택도(Selectivity)'의 개념과 B-Tree 구조에 수반되는 디스크 I/O 비용 분석을 수학적이고 전문적인 관점에서 상세히 알아보겠습니다.
2. 디스크 I/O와 보조 인덱스의 물리적 한계
데이터베이스 시스템의 전체 성능을 좌우하는 가장 큰 병목 지점은 메인 메모리나 CPU의 연산 속도가 아니라, 데이터를 영구적으로 저장하는 물리적 스토리지와의 통신 과정에서 발생하는 디스크 I/O에 있습니다 [3, 4].
데이터를 찾기 위해 디스크의 암(Arm)을 물리적으로 움직이는 탐색 시간(Seek Time, )과 회전하는 원판에서 데이터를 읽어 메모리로 전송하는 시간(Transfer Time, )은 컴퓨터 아키텍처에서 가장 비용이 비싼 연산에 속합니다 [5].
이러한 디스크 접근 횟수를 최소화하기 위해, MySQL의 InnoDB를 비롯한 대부분의 RDBMS는 데이터 검색 속도를 비약적으로 높이는 데 B+-Tree(Balanced Tree) 자료구조를 핵심적으로 활용합니다 [6, 7].
는 루트(Root) 노드에서 리프(Leaf) 노드까지 모든 경로의 길이가 동일한 균형 잡힌 트리 구조를 유지하며, 탐색에 소요되는 시간을 예측 가능하게 만들어 줍니다 [6, 8].
하지만 쿼리에 보조 색인(Secondary Index)이 적용된다고 해서 항상 더 빠른 데이터 조회가 보장되는 것은 아닙니다. 쿼리 최적화기(Query Optimizer)가 인덱스 사용 시 소요되는 수학적 비용을 계산하는 공식을 살펴보면 그 이유가 자명해집니다. 기본 키(Clustered Index)가 아닌 보조 색인(Secondary B+-tree Index)을 사용하여 데이터를 조회할 때 발생하는 예상 비용 산출 공식은 다음과 같습니다 [5].
여기서 각 변수는 다음을 의미합니다.
•
: 인덱스 트리의 높이 (Height of the index)
•
: 조건에 일치하여 실제로 디스크에서 가져와야 하는 레코드의 수
•
: 디스크 블록 전송 시간 (Block transfer time)
•
: 디스크 탐색 시간 (Disk seek time)
위 수학 공식에서 시스템 성능에 가장 치명적이고 결정적인 영향을 미치는 변수는 바로 $n$ (가져올 레코드 수)입니다. 보조 색인을 통해 원하는 데이터를 찾으면, 그 트리의 리프 노드에는 실제 데이터가 저장된 디스크 블록의 주소(또는 기본 키 값)가 들어 있습니다 [9, 10]. 조건에 맞는 레코드를 하나 읽어올 때마다 매번 디스크의 각기 다른 위치로 헤드를 움직여야 하는 랜덤 I/O(Random I/O)가 번만큼 발생하게 됩니다.
따라서 일치하는 레코드 수 이 전체 데이터의 일정 비율을 넘어서게 되면, 수많은 랜덤 I/O로 인해 수학적 탐색 비용이 기하급수적으로 폭증합니다. 이 경우에는 차라리 디스크 헤드를 한 방향으로만 연속적으로 움직이며 데이터를 덩어리째 읽어 들이는 전체 테이블 순차 스캔(Sequential Scan) 비용이 훨씬 저렴해집니다. 이것이 바로 옵티마이저가 여러분이 공들여 만든 인덱스를 무시하는 정확한 원리입니다.
3. 핵심 개념: 인덱스 선택도(Selectivity)란 무엇인가?
앞서 설명한 공식에서 보았듯, 옵티마이저가 랜덤 I/O의 비용을 평가하고 인덱스 탑승 여부를 결정하는 절대적인 잣대가 바로 '선택도(Selectivity)'입니다.
선택도란 전체 레코드 수 대비 특정 조건에 의해 필터링되는 고유한(Unique) 값의 비율을 나타내는 통계적 지표입니다. 이를 수식으로 표현하면 다음과 같습니다.
이 값이 1에 가까울수록(즉, 대부분의 값이 고유할수록) 선택도가 높다고 표현하며, 반대로 0에 가까울수록 선택도가 낮다고 말합니다.
•
선택도가 높은 경우 (Good): 주민등록번호, 이메일 주소, 사원 번호 등은 거의 모든 레코드가 고유한 값을 가집니다. 예를 들어 100만 건의 데이터 중 특정 이메일로 검색을 수행하면 디스크에서 퍼올려야 하는 데이터 건수()가 1건 혹은 극소수에 불과합니다. 따라서 비용이 최소화되어 B-Tree 탐색의 효율이 극대화됩니다.
•
선택도가 낮은 경우 (Bad): 성별(남/여)이나 쇼핑몰의 주문 상태(결제대기/배송중/완료) 같은 컬럼은 고유 값이 몇 개 존재하지 않습니다. 만약 100만 건의 데이터가 있는 테이블에서 '주문 상태=결제대기'라는 조건으로 색인을 생성하면, 이론상 테이블의 약 20~30만 건을 조회해야 할 수도 있습니다. 이 경우 수십만 번의 디스크 탐색 비용이 누적되므로, 옵티마이저는 색인을 타는 것이 논리적인 손해라고 판단하게 됩니다.
실무 데이터베이스 튜닝 전문가들은 일반적으로 조건절에 의해 반환되는 데이터가 전체 레코드의 약 5% ~ 10% 미만일 때만 해당 컬럼에 보조 색인을 생성하는 것이 성능상 유리하다고 판단합니다. 이 지점을 넘어서면 인덱스가 오히려 성능을 저하시키는 '티핑 포인트(Tipping Point)'가 발생하게 됩니다.
4. 다중 컬럼 인덱스(Composite Index)의 수학적 최적화 전략
실제 비즈니스 환경에서는 단일 컬럼 하나만으로 데이터의 5% 미만을 걸러낼 만큼 충분한 선택도를 확보하기 어려운 경우가 많습니다. 이럴 때 우리는 여러 컬럼을 하나로 결합하여 다중 컬럼 인덱스(Composite Index)를 생성합니다 [11]. 여기서 쿼리 성능을 좌우하는 가장 중요한 핵심은 "어떤 컬럼을 인덱스의 선두에 둘 것인가?"를 결정하는 것입니다.
4.1. 선택도가 높은 컬럼을 선두에 배치하라
결합 색인은 구성된 컬럼의 순서에 따라 사전식 정렬(Lexicographic ordering)을 수행하여 의 노드에 데이터를 저장합니다 [12]. 예를 들어 (부서명, 급여) 순으로 색인을 생성하면, 트리는 먼저 부서명을 기준으로 데이터를 정렬하고, 부서명이 완전히 동일한 경우에만 내부적으로 급여 순으로 데이터를 다시 정렬합니다 [11].
따라서, 검색 조건에 매칭되는 데이터의 양을 탐색 초기 단계에서 대폭 줄이려면 선택도가 높은(유니크한 값이 많은) 속성을 인덱스의 첫 번째 컬럼으로 두어야 합니다. 첫 관문에서 탐색해야 할 노드의 범위를 최소화해야만 최종적으로 디스크 블록에 접근하는 의 횟수를 기하급수적으로 줄일 수 있기 때문입니다.
4.2. 점 조건(Equality)을 범위 검색(Range) 조건보다 앞세워라
다중 컬럼 인덱스를 설계할 때 반드시 고려해야 할 또 다른 수학적 최적화 원칙은 조건 연산자의 종류에 따른 배치입니다. =이나 IN과 같이 하나의 점으로 떨어지는 동등 비교(Equality) 조건 컬럼을 복합 색인의 앞쪽에 배치하고, >, <, BETWEEN, LIKE와 같은 범위 검색(Range) 컬럼을 반드시 뒤쪽에 배치해야 합니다.
그 원리는 사전식 정렬 구조의 근본적인 한계에 있습니다. B-Tree 특성상 선행 컬럼이 범위 검색으로 사용되는 순간, 그 범위 내에 포함된 수많은 데이터들에 대해 후행 컬럼은 더 이상 정렬된 트리의 이점을 살리지 못하고 단순 필터링 용도로 스캔되어 버립니다 [13, 14]. 디스크 탐색 비용을 최소화하려면 동등 조건 컬럼을 통해 탐색 공간을 한 점(Point)으로 좁힌 뒤, 그 제한된 좁은 공간 안에서만 범위 조건으로 연속된 데이터를 순차적으로 스캔해 나가야 합니다.
5. 정렬(Sorting) 연산 최적화와 filesort의 회피
데이터베이스에서 조회를 수행할 때 개발자들을 가장 괴롭히는 요소 중 하나는 데이터를 정렬하여 가져오는 과정입니다. 쿼리에 ORDER BY 절이 포함되어 있을 때, 해당 정렬 기준이 인덱스의 구조와 일치한다면 데이터베이스는 이미 정렬된 B-Tree를 순서대로 읽기만 하면 되므로 추가적인 연산 비용이 전혀 발생하지 않습니다. 이를 인덱스를 활용한 정렬이라고 합니다.
하지만 인덱스가 없거나, 다중 컬럼 인덱스의 순서와 ORDER BY의 순서가 어긋나는 경우 데이터베이스는 데이터를 모두 메모리로 가져와서 별도의 정렬 작업을 수행해야 합니다. 이때 데이터베이스는 메모리 내에 정렬을 위한 전용 공간을 할당하는데, MySQL에서는 이 공간의 크기를 sort_buffer_size라는 파라미터로 제어합니다.
문제는 조회하고 정렬해야 할 데이터의 크기가 할당된 메모리 버퍼 용량을 초과할 때 발생합니다. 메모리 공간이 부족해지면 데이터베이스는 어쩔 수 없이 임시 파일(디스크)에 데이터를 나누어 기록하고 병합(Merge)하는 무거운 외부 정렬(External Sort) 과정을 거쳐야 합니다 [15, 16]. 실행 계획을 조회했을 때 엑스트라(Extra) 항목에 filesort라는 경고성 키워드가 나타난다면, 바로 이처럼 디스크를 동반한 값비싼 정렬 연산이 발생하고 있다는 징후입니다.
이러한 성능 저하를 피하려면 쿼리의 WHERE 조건뿐만 아니라 ORDER BY에 사용되는 컬럼의 순서까지 고려하여 인덱스를 설계해야 합니다. 인덱스의 정렬된 물리적 특성을 그대로 쿼리 결과로 활용할 수 있도록 구성하는 것이 튜닝의 핵심입니다.
6. 커버링 인덱스(Covering Index)를 통한 랜덤 디스크 I/O의 완전 제거
데이터베이스 성능 튜닝의 꽃이자 궁극적인 목표는, 앞선 공식에서 가장 비용이 큰 작업인 '실제 테이블의 디스크 블록에 접근하여 데이터를 가져오는 작업' 자체를 시스템에서 아예 제거하는 것입니다. 이를 가능하게 하는 고급 설계 기법을 커버링 인덱스(Covering Index)라고 부릅니다 [17, 18].
앞서 설명한 일반적인 보조 인덱스 스캔 과정은 B+-Tree에서 조건에 맞는 키를 찾고, 리프 노드에 있는 포인터(또는 기본 키)를 사용해 실제 데이터 레코드가 저장된 블록으로 다시 찾아가 나머지 컬럼 값을 읽어오는 두 단계를 거칩니다.
하지만, 만약 우리가 SELECT 절에서 조회하고자 하는 모든 컬럼이 이미 하나의 결합 색인 내에 모두 포함되어 있다면 어떻게 될까요?
예를 들어 SELECT ID, salary FROM instructor WHERE dept_name = 'Finance'; 라는 쿼리를 실행할 때, 만약 데이터베이스에 (dept_name, salary, ID)로 구성된 복합 색인이 존재한다고 가정해 봅시다 [17].
이 상황에서는 데이터베이스 엔진이 굳이 실제 테이블 데이터 블록까지 내려가서 데이터를 읽어올 필요가 없습니다. B+-Tree 내부의 리프 노드만 순회하더라도 쿼리 결과에 필요한 모든 속성을 이미 획득할 수 있기 때문입니다. 결과적으로 가장 무거운 수학적 비용이었던 (가져와야 할 레코드 수 랜덤 디스크 탐색 시간) 항목이 완전히 0으로 소멸하며, 쿼리의 응답 속도는 비약적으로 향상됩니다. (이러한 쿼리 계획을 Index-only plan이라고 부르기도 합니다 [19]).
7. 요약 및 결론
지금까지 살펴본 바와 같이, 데이터베이스의 색인은 무작정 테이블에 생성한다고 해서 쿼리 속도를 즉각적으로 향상시켜 주는 마법의 도구가 결코 아닙니다. 반대로, 새로운 데이터가 삽입(Insert), 수정(Update), 삭제(Delete)될 때마다 B+-Tree의 균형을 엄격하게 유지하기 위해 노드가 분할(Node split)되거나 병합(Coalesce)되며 막대한 쓰기 오버헤드(Overhead)를 초래하게 됩니다 [20, 21].
성능 최적화 관점에서의 성공적인 데이터베이스 시스템 설계란 다음의 수학적이고 논리적인 과정들을 반드시 거쳐야만 합니다.
1.
테이블의 데이터 분포를 세밀하게 파악해 선택도(Selectivity)를 수학적으로 계산하여 인덱스를 생성할 컬럼을 신중하게 선별합니다.
2.
검색 쿼리의 패턴에 맞추어 점-조건(Equality)과 선택도가 높은 컬럼을 복합 인덱스의 선두에 배치하여 탐색 범위를 즉각적으로 축소합니다.
3.
정렬 오버헤드를 막기 위해 인덱스 순서를 쿼리와 일치시키고, 잦은 조회가 일어나는 쿼리에 대해서는 디스크 탐색 비용을 0으로 만드는 커버링 인덱스 구성을 적극 고려합니다.
만약 여러분의 쿼리 실행 계획에서 여전히 느린 스캔이 일어나고 있다면, 이 글에서 다룬 B-Tree의 탐색 비용 공식인 를 떠올려 보십시오. 데이터를 디스크에서 어떻게 퍼올리는지에 대한 논리적이고 수학적인 구조를 깊이 이해할 때, 비로소 진정한 대용량 데이터베이스 성능 튜닝의 길로 들어설 수 있습니다.
참고문헌
[1] Database-System-Concepts-7th-Edition — [Manning et al. (2008)] C. D. Manning, P. Raghavan, and H. Schütze, Introduction to Infor-mation Retrieval, Cambridge University Press (2008). [Samet (2006)] H. Samet, Foundations of Multidimensional and Metric Data Structures, Mor-gan Kaufmann (2006). [Shekhar and Chawla (2003)] S. Shekhar and S. C…
[2] Database-System-Concepts-7th-Edition — Regardless of the way the query is written, it is the job of the optimizer to find the least-cost plan for the query. To find the least costly query-evaluation plan, the optimizer needs to generate al-ternative plans that produce the same result as the given expression and to choose the least costly…
[3] Database-System-Concepts-7th-Edition — Several techniques have been developed to optimize disk block access, such as read ahead, buffering, disk arm scheduling, prefetching, and non-volatile write buffers. Review Terms 581 Review Terms Physical storage media ° Cache ° Main memory ° Flash memory ° Magnetic disk ° Optical storage ° Tape st…
[4] designing-data-intensive-applications — Other fuzzy search techniques go in the direction of document classification and machine learning. See an information retrieval textbook for more detail [e.g., 40]. Keeping everything in memory The data structures discussed so far in this chapter have all been answers to the limi‐ tations of disks. …
[5] Database-System-Concepts-7th-Edition — A2 Clustering B+-tree Index, Equality on Key (hi + 1) ∗ (tT + tS) (Where hi denotes the height of the in-dex.) Index lookup traverses the height of the tree plus one I/O to fetch the record; each of these I/O operations requires a seek and a block transfer. A3 Clustering B+-tree Index, Equality on N…
[6] Database-System-Concepts-7th-Edition — Index-sequential files are one of the oldest index schemes used in database systems. To permit fast retrieval of records in search-key order, records are stored sequen-tially, and out-of-order records are chained together. To allow fast random access, we use an index structure. The primary disadvant…
[7] designing-data-intensive-applications — Data Structures That Power Your Database | 77 Constructing and maintaining SSTables Fine so far—but how do you get your data to be sorted by key in the first place? Our incoming writes can occur in any order. Maintaining a sorted structure on disk is possible (see “B-Trees” on page 79), but maintain…
[8] Database-System-Concepts-7th-Edition — Brandt CrickCalifieri Einstein El Said Gold Katz Kim Mozart Singh Srinivasan Wu El Said Mozart Figure 14.10 B+-tree for instructor file with n = 6. 14.3 B+-Tree Index Files 637 These examples of B+-trees are all balanced. That is, the length of every path from the root to a leaf node is the same. Th…
[9] Database-System-Concepts-7th-Edition — 626 Chapter 14 Indexing 14.2.1 Dense and Sparse Indices An index entry, or index record, consists of a search-key value and pointers to one or more records with that value as their search-key value. The pointer to a record consists of the identifier of a disk block and an offset within the disk bloc…
[10] Database-System-Concepts-7th-Edition — Figure 14.7 shows a typical node of a B+-tree. It contains up to n − 1 search-key values K1, K2,… , Kn− 1, and n pointers P1, P2,… , Pn. The search-key values within a node are kept in sorted order; thus, if i < j, then Ki < Kj. P1 K1 P2 Pn 1 Kn 1 Pn… Figure 14.7 Typical node of a B+-tree. 14.3 B+-T…
[11] Database-System-Concepts-7th-Edition — 14.6.2 Indices on Multiple Keys An alternative strategy for this case is to create and use an index on a composite search key (dept name, salary)—that is, the search key consisting of the department name concatenated with the instructor salary. We can use an ordered (B+-tree) index on the preceding …
[12] Database-System-Concepts-7th-Edition — 634 Chapter 14 Indexing The ordering of search-key values is the lexicographic ordering. For example, for the case of two attribute search keys, (a1, a2) < (b1, b2) if either a1 < b1 or a1 = b1 and a2 < b2. Lexicographic ordering is basically the same as alphabetic ordering of words. As an example, …
[13] Database-System-Concepts-7th-Edition — select ID from instructor where dept name = 'Finance' and salary < 80000; We can even use an ordered index on the search key (dept name, salary) to answer the following query on only one attribute efficiently: 14.6 Multiple-Key Access 663 select ID from instructor where dept name = 'Finance'; An equ…
[14] Database-System-Concepts-7th-Edition — The use of an ordered-index structure on a composite search key, however, has a few shortcomings. As an illustration, consider the query select ID from instructor where dept name < 'Finance' and salary < 80000; We can answer this query by using an ordered index on the search key (dept name, salary):…
[15] Database-System-Concepts-7th-Edition — Intersection of identifiers External sorting External sort–merge Runs N -way merge Equi-join Nested-loop join Block nested-loop join Indexed nested-loop join Merge join Sort-merge join Hybrid merge join 736 Chapter 15 Query Processing Hash-join ° Build ° Probe ° Build input ° Probe input ° Recursive…
[16] Database-System-Concepts-7th-Edition — Exercises 15.17 Suppose you need to sort a relation of 40 gigabytes, with 4-kilobyte blocks, using a memory size of 40 megabytes. Suppose the cost of a seek is 5 millisec-onds, while the disk transfer rate is 40 megabytes per second. a. Find the cost of sorting the relation, in seconds, with bb = 1 …
[17] Database-System-Concepts-7th-Edition — The same effect could be obtained by creating an index on the search key (ID, salary), but a covering index reduces the size of the search key, allowing a larger fanout in the nonleaf nodes, and potentially reducing the height of the index. 664 Chapter 14 Indexing 14.7 Creation of Indices Although t…
[18] designing-data-intensive-applications — [31] MySQL 5.7 Reference Manual. Oracle, 2014. [32] Books Online for SQL Server 2012. Microsoft, 2012. [33] Joe Webb: “Using Covering Indexes to Improve Query Performance,” simple-talk.com, 29 September 2008. [34] Frank Ramsak, Volker Markl, Robert Fenk, et al.: “Integrating the UB-Tree into a Datab…
[19] Database-System-Concepts-7th-Edition — 794 Chapter 16 Query Optimization 16.25 Suppose you want to get answers to r ⋈ s sorted on an attribute of r, and want only the top K answers for some relatively small K . Give a good way of evaluating the query: a. When the join is on a foreign key of r referencing s, where the foreign key attribut…
[20] Database-System-Concepts-7th-Edition — 678 Chapter 14 Indexing Hashing is a widely used technique for building indices in main memory as well as in disk-based systems. Ordered indices such as B+-trees can be used for selections based on equality con-ditions involving single attributes. When multiple attributes are involved in a selec-tio…
[21] Database-System-Concepts-7th-Edition — Practice Exercises 679 ° Nonleaf nodes ° Internal nodes ° Range queries ° Node split ° Node coalesce ° Redistribute of pointers ° Uniquifier B+-tree extensions ° Prefix compression ° Bulk loading ° Bottom-up B+-tree construction B-tree indices Hash file organization ° Hash function ° Bucket ° Overfl…
