B-Tree index

Created

March 9, 2024

Created by

DaEun Kim

인덱스

큰 테이블에서 소량의 데이터를 조회하는 OLTP(On Line Transaction Processing) 시스템에서 필요하다.

→ 많은 데이터를 조회할 때는 인덱스 탐색 없이 풀 스캔하는 게 오히려 유리할 때도 있다.

B-Tree

Balanced Tree ( ≠ Binary Tree)
DBMS 에서 인덱스를 관리하는 자료구조 중 가장 일반적이고 가장 오랫동안 활용되어왔다.
1개의 노드는 1개의 페이지로 구성되어 있다.
페이지 안에는 여러개의 인덱스 레코드 [인덱스 키, 자식노드의 주소] 가 인덱스 키를 기준으로 정렬되어 있다.

💡

페이지(Page)

버퍼 풀(캐시메모리) 또는 디스크에 데이터를 읽고 쓸 때 여러 데이터를 블럭 단위로 묶어서 읽고 쓰는데, 이 블럭 단위를 페이지라고 한다.

B-Tree 구조

Root Node	B-Tree 내에서 최상위 노드. 자식 노드의 주소를 가지고 있다.
Branch Node	Root, Leaf 가 아닌 중간에 위치한 노드. 자식 노드의 주소를 가지고 있다.
Leaf Node	최하위 노드. 디스크 파일에 있는 실제 데이터 레코드의 주소가 있다.

예)

SELECT * FROM employee WHERE name = '김사랑';

위 쿼리를 수행하면 인덱스 탐색은 Root → Node2 → Node7 순서로 수행됨

💡

인덱스 키는 항상 정렬되어 있지만 디스크에 있는 데이터 레코드는 순서가 보장되지 않는다.

secondary index 으로 레코드를 찾는 경우

예)

name 컬럼은 유니크하지 않음 (name = '김사랑' 조건에 맞는 레코드가 2개 이상)
emp_no 컬럼 = PK

InnoDB 테이블에서 secondary 인덱스를 관리하는 B-Tree 내에 Leaf 노드가 가지고 있는 레코드 주소는 아래 순서로 결정된다.

테이블 내에 PK 가 있으면 PK
PK 가 없으나 NOT NULL 제약조건이 붙은 유니크 키가 있으면 유니크 키
PK, 유니크 키 둘 다 없으면 InnoDB 엔진이 각 레코드에 부여한 rowID (디스크 블록 주소 + InnoDB 엔진이 부여한 번호)

[참고] 위와 같이 결정되는 이유는 클러스터 인덱스랑 연관이 있다. (클러스터 인덱스가 PK → not null unique key → rowID 순서로 결정됨)

위 예시의 경우 name = '김사랑' 조건에 맞는 레코드를 찾기 위해서는 name 컬럼에 붙은 인덱스로는 데이터 레코드에 접근하지 못하고,

name 컬럼을 통해 찾은 레코드 주소(PK)를 가지고 PRIMARY 인덱스를 한번 더 검색해야 한다.

→ InnoDB 엔진에서는 secondary 인덱스로 레코드를 검색하면 PK / 유니크 컬럼 / rowID 인덱스도 검색한다.

위 예시의 경우 A1234567, A4029343 을 가지고 아래 PRIMARY 인덱스 트리를 탐색한다.

[참고] 아래는 클러스터 인덱스 트리가 아니고 일반적인 인덱스 트리를 나타냄.

💡

rowID 는 데이터 블록 주소와 InnoDB 엔진이 부여한 row 번호로 구성되어 있으므로 rowID 를 알면 디스크에 저장된 데이터 레코드를 찾을 수 있다.

B-Tree 인덱스 성능에 영향을 주는 요소

인덱스 레코드의 용량이 클수록 성능을 떨어트린다.

B-Tree 가 자식 노드를 몇 개까지 가질 수 있는지는 페이지에 저장하는 인덱스 레코드의 크기에 따라 결정된다.
페이지 내에 인덱스 레코드 1개 당 용량이 클수록 페이지에는 레코드가 적게 들어간다. → 페이지(노드) 1개가 가지고 있는 자식 페이지(노드)의 주소 갯수는 적어지게 된다.
노드 하나 당 가지고 있는 자식 노드 주소 갯수가 적으면 트리의 깊이(depth)가 커진다. → 탐색해야하는 페이지가 많아진다.

버퍼 풀에는 인덱스와 레코드를 캐싱해두는데, 인덱스 레코드가 클수록 캐싱할 수 있는 데이터 레코드 수도 줄어든다.
캐싱할 수 있는 레코드가 적을수록 캐싱의 이점을 누리기 어렵다.

기수성(cardinality) 낮을수록 성능을 떨어트린다.

모든 인덱스 키들 중에서 distinct 키의 갯수가 많을수록 cardinality 가 높다.

예) employee 테이블 내 레코드 갯수는 1000건이고, gendor 컬럼에 인덱스가 붙어있다.

mysql> select count(*) from employee;
+----------+
| count(*) |
+----------+
|    1000  |
+----------+
1 rows in set (0.01 sec)

select distinct gendor from employee;
+----------+
| gendor   |
+----------+
| Male     |
| Female   |
+----------+
2 rows in set (0.01 sec)

gendor 컬럼의 distinct 값은 2개 → gendor 컬럼의 인덱스 키는 평균적으로 키 1개당 500개의 중복이 있을 수 있다. ( 1000 / 500 = 2 으로 cardinaility 가 매우 낮다.)

따라서 아래 쿼리를 실행하면

mysql> select * from employee where gendor = 'Female' and name = '김수한무거북이와두루미';

name = '김수한무거북이와두루미' 조건을 만족하는 데이터 레코드가 1건만 존재한다고 해도 499건의 불필요한 인덱스 레코드를 읽게 된다.

읽어야 할 레코드 수가 많을수록 성능을 떨어트린다.

옵티마이저는 물리적으로 N번째에 위치하는 레코드를 찾을 때 [인덱스 탐색 + disk random I/O] 하는 비용이 [테이블 스캔으로 N-1 번째 레코드에서 N번째 레코드로 순차 I/O 하는 비용] 보다 4배 정도 더 크다고 예측한다.

따라서 읽어야 할 레코드의 갯수가 테이블 내 전체 갯수 대비 20 ~ 25% 를 넘어가면 옵티마이저는 인덱스 스캔보다 테이블 풀 스캔이 더 유리하다고 판단한다. (인덱스를 탐색하지 않고 table full scan 한 뒤, 조건에 맞지 않는 레코드들은 버리는 식으로 처리한다.)

인덱스를 통해 데이터를 읽는 방식

인덱스 레인지 스캔 (index range scan)

범위 검색을 할 때 사용한다.

root 노드 ~ leaf 노드까지 수직 탐색을 한다.
leaf 노드에서 범위의 시작 지점에 해당하는 인덱스 키를 발견하면 범위의 끝 지점에 해당하는 인덱스 키가 나타날 때 까지 leaf 노드 내 레코드를 순차적으로 스캔한다.
leaf 노드를 끝까지 스캔하면 leaf 노드 간의 링크를 통해 다음 leaf 노드로 넘어가서 스캔을 계속 진행한다.

mysql> select emp_no from employee where emp_no between 'A1234567' and 'A4999999';
+----------+
| emp_no   |
+----------+
| A1234567 |
| A1299999 |
| A4000000 |
| A4029343 |
| A4999999 |
+----------+
5 rows in set (0.01 sec)

💡

검색 조건에 일치하는 레코드들을 데이터 파일에서 읽어오는 작업 (random I/O) 가 필요하다. → 검색 조건에 일치하는 레코드 수에 비례하게 random I/O 횟수가 늘어난다.

💡

데이터 레코드를 조회하면 데이터 레코드들이 정렬되어 있는데, 따로 정렬 작업을 하는 게 아니라 leaf 노드 내에 정렬되어 있는 인덱스 레코드를 순차적으로 스캔하기 때문에 데이터 레코드들이 정렬된 상태로 조회되는 것이다.

인덱스 풀 스캔 (index full can)

root 노드 ~ leaf 노드를 수직 탐색하는 과정 없이, 모든 leaf 노드들을 처음부터 끝까지 훑는 것을 인덱스 풀 스캔 이라고 한다.
인덱스 레인지 스캔보다 느리지만 테이블 풀 스캔보다 빠르다.
주로 데이터 검색을 위한 최적의 인덱스가 없을 때 옵티마이저가 차선으로 선택한다.

예1) employee 테이블 대상으로 복합 인덱스 idx_full_name 가 있으나 last_name 컬럼을 조건으로 검색하는 상황

mysql> select count(*) from employee;
+----------+
| count(*) |
+----------+
|   31395 |
+----------+
1 row in set (0.08 sec)

mysql> show index from employee where key_name = 'idx_full_name' ;
+----------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table    | Non_unique | Key_name      | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+----------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| employee |          1 | idx_full_name |            1 | first_name  | A         |           2 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| employee |          1 | idx_full_name |            2 | last_name   | A         |           5 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
+----------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
2 rows in set (0.03 sec)

mysql> explain analyze select * from employee where last_name = 'Park';
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                                               |
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Filter: (employee.last_name = 'Park')  (cost=299.35 rows=29633) (actual time=14.004..768.446 rows=728 loops=1)
    -> Index scan on employee  (cost=29977.35 rows=296326) (actual time=0.705..573.299 rows=313950 loops=1) -> 
 |
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.78 sec)

idx_full_name 복합인덱스의 선행 컬럼에 해당하는 first_name 이 조건절에 없으므로 index range 스캔은 불가능하다.

이 때 옵티마이저는 테이블 풀 스캔 할 지 인덱스 풀 스캔 할 지 결정한다.

조건을 충족하는 인덱스 레코드의 갯수가 많지 않으면, 인덱스 레코드를 가지고 disk random I/O 를 하는 게 테이블 풀 스캔하는 것보다 유리하기 때문에 옵티마이저는 인덱스 풀 스캔을 선택한다.

예2) 모든 레코드의 갯수를 조회하는 상황

mysql> explain select count(*) from employee;
+----+-------------+----------+------------+-------+---------------+---------+---------+------+--------+----------+-------------+
| id | select_type | table    | partitions | type  | possible_keys | key     | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+----------+------------+-------+---------------+---------+---------+------+--------+----------+-------------+
|  1 | SIMPLE      | employee | NULL       | index | NULL          | PRIMARY | 4       | NULL | 296326 |   100.00 | Using index |
+----+-------------+----------+------------+-------+---------------+---------+---------+------+--------+----------+-------------+
1 row in set, 1 warning (0.01 sec)

레코드의 갯수만을 조회하는 경우, 상대적으로 용량이 큰 테이블을 풀 스캔하는 것보다 테이블에 비해 용량이 작은 인덱스를 스캔하는 게 훨씬 빠르기 때문에 인덱스 풀 스캔을 선택한다.

하지만 아래와 같이 레코드 내 모든 필드를 조회하는 경우에는 테이블 풀 스캔을 할 가능성이 높다.

mysql> explain select * from employee;
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------+
| id | select_type | table    | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra |
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------+
|  1 | SIMPLE      | employee | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 296326 |   100.00 | NULL  |
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------+
1 row in set, 1 warning (0.00 sec)

루스 인덱스 스캔 (loose index scan)

range scan 과 비슷하게 동작하지만 필요하지 않은 인덱스 레코드를 건너뛰면서 스캔하는 방식이다.
GROUP BY, MIN(), MAX() 와 같이 집계 쿼리의 최적화에 쓰인다.

인덱스 스킵 스캔 (index skip scan)

Mysql 8.0 버전부터는 인덱스 스킵 스캔을 통해 복합인덱스 내 선행 컬럼이 쿼리 조건절에 없더라도 최적화 된 탐색을 가능한게 한다.

CREATE TABLE t1 (f1 INT NOT NULL, f2 INT NOT NULL, PRIMARY KEY(f1, f2));
INSERT INTO t1 VALUES
  (1,1), (1,2), (1,3), (1,4), (1,5),
  (2,1), (2,2), (2,3), (2,4), (2,5);
INSERT INTO t1 SELECT f1, f2 + 5 FROM t1;
INSERT INTO t1 SELECT f1, f2 + 10 FROM t1;
INSERT INTO t1 SELECT f1, f2 + 20 FROM t1;
INSERT INTO t1 SELECT f1, f2 + 40 FROM t1;

mysql> select * from t1;
+----+----+
| f1 | f2 |
+----+----+
|  1 |  1 |
|  1 |  2 |
|  1 |  3 |
...
|  1 | 79 |
|  1 | 80 |
|  2 |  1 |
|  2 |  2 |
...
|  2 | 79 |
|  2 | 80 |
+----+----+
160 rows in set (0.00 sec)

인덱스 스킵 스캔은 optimizer_switch 변수를 통해 설정할 수 있다.

mysql> select @@optimizer_switch;
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| @@optimizer_switch                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=on,block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,duplicateweedout=on,subquery_materialization_cost_based=on,use_index_extensions=on,condition_fanout_filter=on,derived_merge=on,use_invisible_indexes=off,skip_scan=on,hash_join=on,subquery_to_derived=off,prefer_ordering_index=on,hypergraph_optimizer=off,derived_condition_pushdown=on |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.01 sec)

아래 쿼리는 인덱스 풀 스캔을 탈 것으로 예상되지만, 인덱스 스킵 스캔을 통해 레인지 스캔이 가능하다.

 SELECT f1, f2 FROM t1 WHERE f2 > 40;

[skip_scan=’off’]

선행 컬럼에 해당하는 f1 이 조건절에 없으므로 인덱스 풀 스캔 실행

mysql> set optimizer_switch='skip_scan=off';
Query OK, 0 rows affected (0.01 sec)

mysql> EXPLAIN SELECT f1, f2 FROM t1 WHERE f2 > 40;
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+--------------------------+
| id | select_type | table | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra                    |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+--------------------------+
|  1 | SIMPLE      | t1    | NULL       | index | NULL          | PRIMARY | 8       | NULL |  160 |    33.33 | Using where; Using index |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+--------------------------+
1 row in set, 1 warning (0.01 sec)

[skip_scan = ‘on’]

선행 컬럼에 해당하는 f1 이 조건절에 없으나 인덱스 레인지 스캔 실행
Extra 항목에 Using index for skip scan 으로 표기되었음

mysql> set optimizer_switch='skip_scan=on';
Query OK, 0 rows affected (0.01 sec)

mysql> EXPLAIN SELECT f1, f2 FROM t1 WHERE f2 > 40;
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+----------------------------------------+
| id | select_type | table | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra                                  |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+----------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | range | PRIMARY       | PRIMARY | 8       | NULL |   53 |   100.00 | Using where; Using index for skip scan |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+----------------------------------------+
1 row in set, 1 warning (0.01 sec)

인덱스 스킵 스캔 절차

f1 컬럼에서 distinct 값을 모두 조회한다. → 위 예시에서는 1, 2 2개
내부적으로 주어진 쿼리에 f1 컬럼 조건을 더한다. 조건을 더한 쿼리는 아래와 같다.

select * from t1 where f1 = 1 and f2 > 40;
select * from t1 where f1 = 2 and f2 > 40;

복합인덱스를 사용할 수 있는 쿼리이므로, 아래와 같이 레인지 스캔을 수행한다.

인덱스 스킵 스캔에는 몇 가지 제약이 있다.

💡

선행 컬럼의 distinct 값의 갯수가 적어야 한다.

선행 컬럼의 distinct 값이 많다면 그만큼 범위의 시작 지점을 찾기 위한 수직 탐색을 많이 수행해야 하므로 성능이 오히려 떨어질 수 있다.

💡

SELECT 대상이 되는 컬럼이 복합 인덱스 컬럼이어야 한다.

인덱스가 붙지 않은 컬럼을 SELECT 할 경우 인덱스 스킵 스캔을 하지 않는다.

그 외 다른 제약사항은 여기 참고.

복합 인덱스

2개 이상의 컬럼으로 구성한 인덱스
후행 컬럼은 선행 컬럼의 정렬에 의존한다. (여기 예시처럼 ORDER BY f1, f2 한 것 마냥 정렬됨.)

→ 오름차순 인덱스 트리에서 어떤 레코드가 f2 컬럼 내에서 순서 상 앞에 위치한다고 해도 f1 값이 크다면 B-Tree 내에서 오른쪽에 위치한다.

예) f1 = 2 and f2 = 1 조건을 만족하는 레코드

인덱스 정렬

인덱스를 생성할 때 아래처럼 오름차순/내림차순 정렬 방식을 설정할 수 있다.

mysql> alter table employee add index idx_full_name (first_name ASC, last_name DESC);
Query OK, 0 rows affected (0.09 sec)
Records: 0  Duplicates: 0  Warnings: 0

인덱스 스캔 방향에 따른 성능 차이

first_name 컬럼 인덱스가 오름차순으로 정렬된 테이블에 아래와 같이 내림차순 쿼리를 하더라도, 옵티마이저는 오름차순 정렬된 인덱스를 역순으로 스캔할 줄 알기 때문에 데이터를 빠르게 찾을 수 있다.

SELECT *
FROM employee
ORDER BY first_name DESC 
LIMIT 1;

대신에 인덱스를 역순으로 스캔하는 것은 정순으로 스캔하는 것에 비해 느리다.

각 노드(페이지)는 서로 양방향 링크로 연결되어 있지만, 노드(페이지) 내 인덱스 레코드들은 단방향으로만 연결되어 있기 때문이다.

→ 페이지에서 페이지로 넘어가는 데에는 역순/정순 스캔 성능에 차이가 없지만, 페이지 내에서 인덱스 레코드들을 역순으로 스캔할 때에는 정순으로 스캔하는 것에 비해 느리다.

→ 데이터를 조회할 때 어떤 방식으로 자주 정렬하는지 (오름차순/내림차순)에 따라 인덱스의 정렬 방식도 고려해야 한다.

[참고]

인덱스를 역순으로 스캔하면 실행계획에서 Backward index scan 으로 조회됨

mysql> explain select * from employee order by first_name desc limit 3;
+----+-------------+----------+------------+-------+---------------+---------------+---------+------+------+----------+----------------------------------+
| id | select_type | table    | partitions | type  | possible_keys | key           | key_len | ref  | rows | filtered | Extra                            |
+----+-------------+----------+------------+-------+---------------+---------------+---------+------+------+----------+----------------------------------+
|  1 | SIMPLE      | employee | NULL       | index | NULL          | idx_full_name | 1028    | NULL |    3 |   100.00 | Backward index scan; Using index |
+----+-------------+----------+------------+-------+---------------+---------------+---------+------+------+----------+----------------------------------+
1 row in set, 1 warning (0.01 sec)

인덱스를 최적으로 활용하기

복합인덱스 & 컬럼의 비교 조건

복합 인덱스 내에서 각 컬럼의 순서와 쿼리 내에서 컬럼에 적용된 조건이 무엇인지에 따라 (=, >, <) 인덱스의 활용 형태가 달라지고 효율도 달라진다.

아래와 같이 employee 테이블이 있다.

mysql> show columns from employee;
+------------+-------------+------+-----+---------+----------------+
| Field      | Type        | Null | Key | Default | Extra          |
+------------+-------------+------+-----+---------+----------------+
| emp_no     | int         | NO   | PRI | NULL    | auto_increment |
| last_name  | varchar(64) | YES  |     | NULL    |                |
| first_name | varchar(64) | YES  | MUL | NULL    |                |
| dep_no     | int         | YES  |     | NULL    |                |
+------------+-------------+------+-----+---------+----------------+
4 rows in set (0.01 sec)

employee 테이블 대상으로 아래와 같은 쿼리를 수행하는 것을 가정하고

select * 
from employee 
where first_name = 'Jeong' and last_name > 'DaEun';

first_name, last_name 컬럼을 대상으로 복합인덱스를 만들어 성능을 비교해봤다.

[first_name, last_name 순서로 복합인덱스 생성한 경우]

mysql> show index from employee where key_name = 'full_name';
+----------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table    | Non_unique | Key_name  | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+----------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| employee |          1 | full_name |            1 | first_name  | A         |        1563 |     NULL |   NULL | YES  | BTREE      |         |               | YES     | NULL       |
| employee |          1 | full_name |            2 | last_name   | A         |        3436 |     NULL |   NULL | YES  | BTREE      |         |               | YES     | NULL       |
+----------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
2 rows in set (0.02 sec)

인덱스 레인지 스캔을 수행한다.

복합인덱스 트리 내에서 first_name = 'Kim' and last_name = 'DaEun' 조건을 만족하는 인덱스 레코드를 수직탐색하고,

인덱스 레코드를 발견하면 끝까지 순차적으로 읽기만 하면 된다.

→ first_name, last_name 컬럼이 스캔 작업을 줄이는 데 활용 되었다. (인덱스 스캔 작업 범위를 결정했다.)

mysql> explain select * from employee where first_name = 'Jeong' and last_name > 'DaEun';
+----+-------------+----------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+
| id | select_type | table    | partitions | type  | possible_keys | key       | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+----------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | employee | NULL       | range | full_name     | full_name | 518     | NULL | 2457 |   100.00 | Using index condition |
+----+-------------+----------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0.00 sec)

mysql> select * from employee where first_name = 'Jeong' and last_name > 'DaEun';
+--------+-----------+------------+--------+
| emp_no | last_name | first_name | dep_no |
+--------+-----------+------------+--------+
...
+--------+-----------+------------+--------+
2457 row in set (0.06 sec)

[last_name, first_name 순서로 복합인덱스 생성한 경우]

mysql> show index from employee where key_name = 'full_name';
+----------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table    | Non_unique | Key_name  | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+----------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| employee |          1 | full_name |            1 | last_name   | A         |        3436 |     NULL |   NULL | YES  | BTREE      |         |               | YES     | NULL       |
| employee |          1 | full_name |            2 | first_name  | A         |        1563 |     NULL |   NULL | YES  | BTREE      |         |               | YES     | NULL       |
+----------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
2 rows in set (0.02 sec)

테이블 풀 스캔을 한다.

복합인덱스 내에 선행 컬럼으로는 레인지 스캔이 불가하므로

last_name = DaEun 조건을 만족하는 인덱스 레코드를 찾고
해당 레코드 이후의 모든 인덱스 레코드를 스캔하면서 각 레코드가 first_name = Jeong 을 만족하는지 비교

하는 과정이 필요한데, 옵티마이저가 이렇게 하는 것보다 테이블 풀 스캔을 하는 게 낫겠다고 판단한건지.. 어쨌든 인덱스를 전혀 활용하지 않았다.

→ first_name, last_name 컬럼이 인덱스 스캔 작업 범위를 결정하지 못하고 비교 조건으로서만 활용되었다.

mysql>  explain select * from employee where first_name = 'Jeong' and last_name > 'DaEun';
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------------+
| id | select_type | table    | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------------+
|  1 | SIMPLE      | employee | NULL       | ALL  | full_name     | NULL | NULL    | NULL | 296326 |     5.00 | Using where |
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------------+
1 row in set, 1 warning (0.02 sec)

mysql> select * from employee where first_name = 'Jeong' and last_name > 'DaEun';
+--------+-----------+------------+--------+
| emp_no | last_name | first_name | dep_no |
+--------+-----------+------------+--------+
...
+--------+-----------+------------+--------+
2457 rows in set (0.67 sec)

B-Tree 인덱스 탐색을 최적화하기 위해 알아야 할 것 : 오른쪽은 왼쪽을 기준으로 정렬되어 있다

복합인덱스 뿐만 아니라 단일 컬럼으로 검색해도 왼쪽 서브값을 모르면 오른쪽 서브값을 알 수 없다.

예) last_name 컬럼에 인덱스 생성

mysql> show index from employee ;
+----------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table    | Non_unique | Key_name      | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+----------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| employee |          0 | PRIMARY       |            1 | emp_no      | A         |      296325 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| employee |          1 | idx_last_name |            1 | last_name   | A         |         315 |     NULL |   NULL | YES  | BTREE      |         |               | YES     | NULL       |
+----------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
2 rows in set (0.02 sec)

last_name 값이 Eun 으로 끝나는 레코드 조회

→ last_name 인덱스가 있어도 스캔의 작업 범위를 결정하지 못하기 때문에 (어디서부터 스캔해야 할지 알 수 없기 때문에) 테이블 풀 스캔

mysql> explain select * from employee where last_name like '%Eun';
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------------+
| id | select_type | table    | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------------+
|  1 | SIMPLE      | employee | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 296326 |    11.11 | Using where |
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------------+
1 row in set, 1 warning (0.02 sec)