Covering Index, 성능 테스트

 

 

 

MySQL에서 성능 개선을 위해 Covering Index가 무엇인지, 추가로 그 배경 지식인 Index와 관련된 내용을 살피는 것이 해당 포스팅의 목표입니다.

 

안녕하세요. 이번 포스팅에서는 MySQL의 Covering Index에 대해 다루고자 합니다.

Covering Index를 이해하기 위해서는 MySQL의 Index 구조와 Execution Plan 지식이 요구됩니다.

 

Execution Plan에 대한 이해는 'SQL Execution Plan, 제대로 이해하기'을 참고하실 수 있고,

Index와 관련된 내용은 'MySQL Index, 제대로 알아보기'을 참고하실 수 있습니다.

 

 

 

---

 

B-Tree

 

MySQL의 InnoDB는 기본적으로 인덱스를 B$^+$-Tree의 자료구조로 생성합니다.

B$^+$-Tree는 Binary Tree 👉🏻 B-Tree👉🏻B+Tree 순으로 확장되어진 자료구조로 이해할 수 있습니다.

 

엄밀히 말하면 Binary Search Tree (균형 이진 검색 트리, 이하 BST)의 확장 구조인데요.

BST는 각 노드가 두 개의 자식 노드만을 갖는 데이터가 정렬되도록 구성하는 트리입니다.

여기서 데이터 블록 한 개를 노드(Node) 혹은 페이지(Page)라고 부릅니다.

더 자세한 설명은 본 포스팅의 주제와 벗어나기 때문에 여기서 마치겠습니다.

갑자기 생각났는데 교수님께서 BST 설명하실 때 BTS 랑 헷갈리지 말라고 하시면서 본인 드립에 뿌듯해 하셨던 기억이 있네요

...여러분은 그러지 마세요

 

 

📌 B-Tree

B-Tree

 

언급했다시피 BST(Binary Search Tree)의 확장이 바로 B-tree 인데요.

 

BST를 확장한 B-tree는 균형 트리로 각 노드 당 자식 노드가 2개 이상이라는 점에서 확장되었습니다.

그림을 보면 가장 상단 노드 아래에 [10], [30, 33], [50, 60] 의 자식 노드가 3개 있는 것처럼 말이죠.

이때, B-tree는 정렬을 통한 구조로 검색이 항상 동일한 시간을 갖게끔 만들어 줍니다.

 

다른 Self-balancing Binary Search Tree들과는 다르게 B-tree는 데이터베이스나 파일 시스템과 같이 비교적 큰 데이터 블록을 읽고 쓰는 스토리지 시스템에 적합합니다.

 

FYI 1. B-tree라는 이름이 'Balanced'를 의미하는 ‘B’가 아닐까라는 추측하는 여론이  있는데요.

개인적으로 합리적인 추측같아 보입니다.

 

 

 

📌 B$^+$-Tree

 

 

B$^+$-Tree는 B-tree의 확장개념으로 B-Tree와의 대표적인 차이점은 두 가지가 있습니다.

✔️ Leaf Node에만 Key + Data를 저장

B-Tree 는 모든 노드마다 데이터를 가지고 있는 반면,

B$^+$-Tree는 Branch 혹은 상위 블록들Internal Node에는 Key만 저장이 되고, 

최하위 노드Leaf Node에만 Key와 Data를 함께 저장합니다.

 

아래의 이미지로 구조를 확인하면서 다시 언급하겠습니다.

 

✔️  각 Node끼리 Linked list로 연결

B$^+$-Tree는 각 Node끼리 Linked list로 연결되어있습니다.

덕분에 풀 스캔 시 선형 탐색을 할 수 있기 때문에 기본 B-Tree가 모든 노드를 탐색하는 것보다 빠릅니다.

 

FYI 2. MySQL의 InnoDB의 공식문서를 보면 B-Tree로 생성한다고 작성되어 있는데요. 

MySQL은 B$^+$-Tree를 B-Tree 로 소개하고 있는데, 아마 확장 개념이라 그런 것 아닐까 하는 추측을 해봅니다.

아이폰 6+ 같은 느낌 아닐까요. 아이폰 6+도 아이폰 6 계열이긴 하니까요 ~.~

궁금해서 찾아봤는데 Stackoverflow에 글이 조금 도움이 되어서 링크 참고하시길 바랍니다.

 

 

 

 

 

용어를 정리하면 아래와 같습니다.

 

✔ Root Node      : 최상단 노드

✔ Internal Node : 중간 노드들 = Branch Node

✔ Leaf Node       : 가장 아래 노드들

 

B$^+$-Tree는 같은 레벨의 모든 키 값들이 정렬되어 있고, 같은 레벨의 노드Sibiling node는 연결리스트 형태를 가집니다.

위에서 언급한 바와 같이 Root, Internal Node에는 키의 범위 값만이 저장되어 있고, Leaf Node에는 실제 데이터가 저장되어 있습니다. 

 

데이터를 찾을 때는 키의 범위 값으로 찾습니다. 

가령, 키를 통해 Page 7의 (key: 3, data: D)를 찾는 경우를 볼까요?

 

key가 3인 데이터를 찾으면 되기 때문에 Root Node에서 >= 0 → 4의 조건에 걸립니다.

Level 2의 Internal Node에서는 >=0에 부합하지 않고 >=2 → 7에 부합하기 때문에 Page 7을 조회하고, Page 7에서 3을 찾으면 되는 것이죠.

 

 

 

Clustered & Non-clustered Index

MySQL의 InnoDB에서 PK를 생성하면 Clustered Index를 생성하고,

인덱스나 Primary Key가 존재하는 테이블의 Unique 키를 생성하면 Non-Clustered Index가 생성됩니다.

그렇다면 Clustered와 Non-Clustered이 무엇인지 알아보겠습니다.

인덱스나 Primary Key가 존재하는 테이블의 Unique 키를 생성하면 Unique 키가 Clustered Index로 생성됩니다.

 

📌 Clustered Index

 

✔️ PK의 값

✔️ PK가 없다면 Unique Key로 대체하며, 둘 다 없다면 6byte의 Hidden Key(rowId)를 생성

✔️ 실제 데이터 테이블의 row 위치를 알고 있음

✔️ 테이블 당 단 1개만 존재

 

실제 데이터의 위치를 가지고 있는 인덱스입니다.

한 테이블에 하나의 Clustered 인덱스는 반드시 단 하나 존재합니다.

중요한 특징은 만약 PK가 없을 때 Unique 키로 대체하고 Unique Key 조차 없다면 Hidden Key를 생성해서 만든다는 점입니다.

 

 

📌 Non Clustered Index

✔️ 일반적인 인덱스, PK가 존재할 때 Unique 키의 값

✔️ 인덱스 컬럼의 값들을 가진 구조

✔️ 한 테이블 당 여러 개를 생성 가능

✔️ MySQL에서는 Non Clustered Key에 Clustered Key가 포함

 

Non-Clustered Key가 Clustered Key를 포함하는 이유는 Non-Clustered Key에는 데이터 블록의 위치가 없기 때문인데요.

즉, 인덱스 조건에 부합한 WHERE 조건 절이 있더라도 SELECT 중 인덱스에 포함된 컬럼 외 다른 컬럼 값이 필요한 경우에는 Clustered Key에 있는 Clustered Key 값으로 데이터 블록을 찾는 과정이 필요합니다.

 

 

 

즉, Non-Clustered 인덱스는 Clustered 인덱스와 다르게 데이터의 위치를 알지 못합니다.

대신에 클러스터드 인덱스로 참조해서 데이터를 액세스 합니다.

 

 

 

Covering Index

커버링 인덱스는 "실제 데이터 접근" 의 행위 없이 인덱스에 있는 컬럼 값들로만 쿼리를 완성하는 것을 의미합니다.

 

간단히 정의하자면 실제 데이터 블록에 접근 없이 인덱스만으로 데이터를 가져올 수 있는 경우입니다.

위에서 데이터 블록을 직접 가지고 있는 인덱스가 Clustered Index라고 했는데요.

데이터 블록에 실제 접근하는 디스크 IO없이 실행되기 때문에 굉장히 좋은 성능을 끌어낼 수 있습니다.

 

그렇다면 어느 정도의 성능을 개선시킬 수 있을지 테스트를 진행해보도록 하겠습니다.

 

 

 

Covering Index Test

인덱스가 걸린 컬럼만을 가져오는 경우와 아닌 경우로 테스트를 진행해보았습니다.

 

 

📌 Environment

먼저 실행 환경에 대한 내용입니다.

버전은 8.0.17이고, employee라는 테이블에 emp_no (PK) 와 first_name (IDX_employee_firstName)을 인덱스로 잡았습니다.

 

MySQL 8.0.17

 

Table

테이블 정보는 위와 같습니다.

 

 

 

좌측 부터 테이블 정의, 데이터 예시 10건, 데이터 개수입니다.

데이터는 총 1,900만개의 데이터를 저장했습니다.

 

아래는 인덱스 정보입니다.

 

 

위 테이블은 몇 항목을 제거한 편집본입니다.

추후에 진행될 대부분의 테스트를 first_name condition을 걸어서 진행할 예정입니다.

 

 

 

📌  SELECT Non-Index VS Index

해당 테스트를 진행하기 전에 가설을 먼저 설정해보도록 하겠습니다.

 

SELECT 절에서 불러오는 데이터가 Index 값으로 제한되어 있을 때, 성능(속도)이 굉장히 좋을 것이다.

 

위 가설을 검증하기 위해서 아래의 두 가지 쿼리를 실행합니다.

 

 

SESSION #1. Index가 아닌 데이터 조회 쿼리

SELECT last_name FROM employee WHERE first_name = ‘Parto’ LIMIT 13000, 1000;

 

 

SESSION #2. Index 조회 - Covering Index

SELECT emp_no FROM employee WHERE first_name = ‘Parto’ LIMIT 13000, 1000;

 

 

참고로, LIMIT 조건을 건 것을 확인할 수 있는데요.

 

 

이 때 어느정도 성능이 필요한 상황을 구현하고자 LIMIT 조건을 달았고,

동일한 표본 크기(1,000건)를 위해 OFFSET을 13,000으로 잡았습니다.

 

그럼 이제 테스트 결과를 확인해보겠습니다.

 

 

✔️  SESSION #1. Index가 아닌 데이터 조회 쿼리

 

 

✔️  SESSION #2. Index 조회 - Covering Index

 

두 쿼리는 서로 다른 세션에서 진행을 했습니다.

생각보다 속도 차이가 크네요.

 

 

📌  EXECUTION EXPLAIN 비교

 

Index가 아닌 데이터 조회 시에는 실제 데이터를 접근해야 하기 때문에

실제 데이터가 저장된 Storage Engine에 접근합니다.

 

 

가장 중요하게 봐야할 건 쿼리 플랜 내용입니다.

여기서 Extra에 Using Index가 보이면 커버링 인덱스를 사용했다는 의미입니다.

 

Index 조회 (Covering Index) 에는 인덱스 자체를 이미 들고 있는 B$^+$-Tree에만 저장되어 있기 때문에 인덱스가 메모리에 이미 올라온 상태에서는 Storage Engine에 접근할 필요가 없습니다.

 

여기서 주의하실 점은 Using Index과 Using Index Condition을 구분하셔야 한다는 것입니다.

Using Index과 Using Index Condition의 차이는 아래와 같습니다.

 

 

 

Index Condition Pushdown

Using Index VS Using Index Pushdown

 

Using Index condition는 인덱스 조건을 스토리지 엔진에 넘겨서 최대한 필터링을 한 상태를 말하는데요.

MySQL 5.6 이전까지는 인덱스가 포함되어도 범위 조건을 사용 못하면 인덱스 조건을 전달 못했는데

이후(MySQL 5.6 ~)부터는 인덱스 조건을 같이 전달해서 필터링을 최대한 많이 하게끔 만들었습니다.

 

 

공식문서의 내용을 정리해보면 아래와 같습니다.

ICP(Index Condition Pushdown)는 MySQL이 Index를 사용하여 테이블에서 행을 검색하는 경우에 대한 최적화입니다.

 

ICP가 없으면 스토리지 엔진은 인덱스 트리로 데이터 테이블에서 행을 찾은 다음,

WHERE 조건으로 필터링하는 MySQL 서버로 반환합니다. 

 

반면, ICP가 활성화된 상태이고 인덱스의 열만 사용하여 WHERE 조건의 일부를 평가할 수 있는 경우라면,

MySQL 서버는 WHERE 조건의 이 부분을 스토리지 엔진으로 푸시합니다.

 

스토리지 엔진은 인덱스 항목을 사용하여 푸시된 인덱스 조건을 평가하며,

이 조건이 충족하는 테이블 행을 평가(필터링)합니다.

 

ICP를 사용하면 스토리지 엔진이 기본 테이블에 액세스해야 하는 횟수와 MySQL 서버가 스토리지 엔진에 액세스해야 하는 횟수를 줄일 수 있습니다.

 

 

 

 

 

이상으로 Covering Index에 대해서 다뤘습니다.

다음 포스팅으로는 Paging 을 할 때 Covering Index로 성능을 개선하는 방법에 대하해 다루겠습니다 🙏🏻

오타나 잘못된 내용은 댓글 부탁드립니다.

감사합니다 ☺️

 

 

 

 

 

| 참고 |

https://www.programiz.com/dsa/b-tree