Database Indexing

TL;DR

데이터베이스 column 중 중복도가 가장 낮은 컬럼에 인덱싱을 적용하면 쿼리 속도가 매우 빨라진다

언젠가부터 회사에서 리스트를 조회하는 쿼리가 매우 느려졌다. 다른 프로젝트를 담당하는 개발자분이 DB에 인덱싱을 적용해보라고 하셔서 찾아봤다.

요약하면 인덱싱은 데이터베이스 검색속도를 향상시키는 도구이다

책을 읽는다고 가정할 때 “목차”로 봐도 좋다. 몇몇 블로그에서는 인덱싱을 자료구조라고도 부르는데, 이는 인덱싱이 B+Tree 구조이기 때문이다. B+Tree 구조에 대해서는 다음에 자세히 글을 작성해보도록 하겠다.

레스토랑 예약을 예로 들어보자. 식당예약은 예약 신청한 날짜보다, 식사를 예약한 날짜를 기준으로 테이블을 조회할 가능성이 높다. 극단적으로 만약 A가 3개월 뒤의 저녁식사를 오늘 예약했고, B가 1주일 뒤의 점심 식사를 3일 뒤에 예약했다고 하자. 이런경우 auto_increment 값을 사용해서 테이블을 조회하면 매우 비효율적이다. 따라서, 인덱싱을 식사를 예약한 날짜에 적용하면, 오늘 예약을 조회할 때 더욱 효율적일 수 있다.

SELECT * FROM reservation WHERE requested_at LIKE '2022-05-16%';

인덱싱을 어떤 column에 적용할 지 고민할 때 가장 중요한 것은

최대한 중복도가 낮아야하고,
UPDATE 가 빈번하게 일어나지 않는 값이어야 한다.

많이 중복되는 값을 피해야 하는 이유는, 데이터가 충분히 걸러지지 않기 때문이다. 다시 식당예약으로 돌아가보자. 만약 모든 예약들을 점심예약/저녁예약으로만 구분한다면. 점심장사와 저녁장사를 같은 시간동안 진행한다고 할 때, 인덱싱을 한다고 하더라도 해당 테이블을 두 분류로 밖에 나누지 못한다.

UPDATE 가 빈번하게 일어나는 값들을 피해야 하는 이유는, 인덱스는 결국 포인터를 가리키게 되는데, UPDATE 가 빈번하게 일어난다면, 해당 포인터가 계속 변경되기 때문이다. 그림으로 같이 이해해보도록 하자

MySQL without index

위와 같은 테이블에서 2022년 4월 17일의 예약을 조회하는 경우, 필요없는 값들도 같이 훑어봐야 하는 문제가 있다. 인덱싱을 적용하면 이런식으로 조회가 가능하다. 따서 해당 값이 업데이트가 자주 일어난다면, 왼쪽 테이블이 자주 수정되는 문제가 발생할 수 있다.

MySQL with index

그림으로 어느정도 이해도를 쌓았으니 이제 코드에서 시간을 확인해보도록 한다.

식당 예약을 예로 들었으니 database 안에 reservation이라는 테이블을 생성한다.

CREATE TABLE reservation (
  id INT(7) AUTO_INCREEMENT PRIMARY KEY,
  requested_at DATE,
  num_customer INT(2),
  created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
  name VARCHAR(16),
  phone VARCHAR(16),
  time TIME
);

테이블을 생성하고, random data generation 을 위한 procedure를 생성한다.

DELIMITER $$
CREATE PROCEDURE generate_reservation()
BEGIN
  DECLARE i INT DEFAULT 0;
  WHILE i < 1000000 DO
    INSERT INTO `reservation` (`requested_at`, `num_customer`, `name`, `phone`, `time`) VALUES (
      FROM_UNIXTIME(ROUND(RAND() * (1651319994-1648814394) + 1648814394)),
      FLOOR(RAND()* (10)) + 1,
      SUBSTRING(MD5(RAND()) FROM 1 FOR 7),
      SUBSTRING(MD5(RAND()) FROM 1 FOR 7),
      SEC_TO_TIME(FLOOR(TIME_TO_SEC('15:00:00') + RAND() * (TIME_TO_SEC(TIMEDIFF('22:00:00', '15:00:00')))))
    );
    SET i = i + 1;
  END WHILE;
END$$

phone 은 regex 를 사용하면 형식을 맞출 수 있을 것 같긴한데, database index테스트 목적에 크게 의미없을 것 같아서 찾아보지 않았다. for loop이라 오래 걸리는 건지는 모르지만 1,000,000 row를 생성하는데 14분 58.65초 소요됐다. 이제 쿼리를 해보자.

SELECT * FROM reservation WHERE name LIKE '2b%' AND time LIKE '20:00%';

+--------+--------------+--------------+---------------------+---------+---------+----------+
| id     | requested_at | num_customer | created_at          | name    | phone   | time     |
+--------+--------------+--------------+---------------------+---------+---------+----------+
|  75402 | 2022-04-30   |            1 | 2022-05-16 21:11:50 | 2b48129 | e4205d8 | 20:00:41 |
| 173141 | 2022-04-29   |            5 | 2022-05-16 21:13:17 | 2b2e1b4 | 9df3407 | 20:00:01 |
| 207430 | 2022-04-28   |            2 | 2022-05-16 21:13:47 | 2b31924 | 256b363 | 20:00:50 |
| 412796 | 2022-04-10   |            8 | 2022-05-16 21:16:51 | 2b6c98c | af6dd3a | 20:00:43 |
| 492708 | 2022-04-07   |            2 | 2022-05-16 21:18:02 | 2b14a6b | 274ab3d | 20:00:03 |
| 610563 | 2022-04-04   |            7 | 2022-05-16 21:19:46 | 2b6ccba | 53e06ac | 20:00:32 |
| 646019 | 2022-04-09   |            3 | 2022-05-16 21:20:19 | 2b43c53 | 0d3dd41 | 20:00:59 |
| 702301 | 2022-04-21   |            6 | 2022-05-16 21:21:15 | 2b57afe | 8549b1b | 20:00:25 |
| 798381 | 2022-04-23   |            8 | 2022-05-16 21:22:43 | 2b4bf39 | cde432b | 20:00:15 |
| 839637 | 2022-04-24   |            4 | 2022-05-16 21:23:20 | 2b8adfc | 366a865 | 20:00:24 |
| 999538 | 2022-04-24   |            7 | 2022-05-16 21:25:42 | 2bf2434 | f91cefd | 20:00:27 |
+--------+--------------+--------------+---------------------+---------+---------+----------+
11 rows in set (0.45 sec)

인덱싱 없이 쿼리를 하니 0.45초 소요됐다. 인덱스를 추가하기 위해 중복값이 제일 적은 컬럼을 찾아보도록 한다.

SELECT
  COUNT(DISTINCT(requested_at)) requested_at,
  COUNT(DISTINCT(num_customer)) num_customer,
  COUNT(DISTINCT(name)) name,
  COUNT(DISTINCT(created_at)) created_at,
  COUNT(DISTINCT(phone)) phone,
  COUNT(DISTINCT(time)) time,
FROM reservation;

+--------------+--------------+--------+------------+--------+-------+
| requested_at | num_customer | name   | created_at | phone  | time  |
+--------------+--------------+--------+------------+--------+-------+
|           30 |           10 | 853470 |        901 | 853378 | 25201 |
+--------------+--------------+--------+------------+--------+-------+

phone과 name을 둘 다 random한 varchar로 생성했으니 어쩔 수 없는 것 같다. 둘 중에 하나는 범위를 줄일걸 싶다. 그럼 일단 중복도가 제일 낮은 name 에 인덱스를 걸도록 하겠다.

CREATE INDEX name_index ON reservation (name);

인덱스 생성도 3.28초 소요된다. 그럼 이제 인덱스를 사용해서 쿼리 해보도록 하겠다.

SELECT * FROM reservation USE INDEX (name_index) WHERE name LIKE '2b%' AND time LIKE '20:00%';
+--------+--------------+--------------+---------------------+---------+---------+----------+
| id     | requested_at | num_customer | created_at          | name    | phone   | time     |
+--------+--------------+--------------+---------------------+---------+---------+----------+
| 492708 | 2022-04-07   |            2 | 2022-05-16 21:18:02 | 2b14a6b | 274ab3d | 20:00:03 |
| 173141 | 2022-04-29   |            5 | 2022-05-16 21:13:17 | 2b2e1b4 | 9df3407 | 20:00:01 |
| 207430 | 2022-04-28   |            2 | 2022-05-16 21:13:47 | 2b31924 | 256b363 | 20:00:50 |
| 646019 | 2022-04-09   |            3 | 2022-05-16 21:20:19 | 2b43c53 | 0d3dd41 | 20:00:59 |
|  75402 | 2022-04-30   |            1 | 2022-05-16 21:11:50 | 2b48129 | e4205d8 | 20:00:41 |
| 798381 | 2022-04-23   |            8 | 2022-05-16 21:22:43 | 2b4bf39 | cde432b | 20:00:15 |
| 702301 | 2022-04-21   |            6 | 2022-05-16 21:21:15 | 2b57afe | 8549b1b | 20:00:25 |
| 412796 | 2022-04-10   |            8 | 2022-05-16 21:16:51 | 2b6c98c | af6dd3a | 20:00:43 |
| 610563 | 2022-04-04   |            7 | 2022-05-16 21:19:46 | 2b6ccba | 53e06ac | 20:00:32 |
| 839637 | 2022-04-24   |            4 | 2022-05-16 21:23:20 | 2b8adfc | 366a865 | 20:00:24 |
| 999538 | 2022-04-24   |            7 | 2022-05-16 21:25:42 | 2bf2434 | f91cefd | 20:00:27 |
+--------+--------------+--------------+---------------------+---------+---------+----------+
11 rows in set (0.02 sec)

중복도가 제일 낮은 값에 인덱싱을 적용하니 0.02초 소요된다. 중복성이 적은 column에 인덱싱을 하는 것이 유리하다는 것을 증명하기 위해 time에도 인덱싱을 적용해보겠다.

CREATE INDEX time_index ON reservation (time);

SELECT * FROM reservation USE INDEX (time_index) WHERE name LIKE '2b%' AND time LIKE '20:00%';
+--------+--------------+--------------+---------------------+---------+---------+----------+
| id     | requested_at | num_customer | created_at          | name    | phone   | time     |
+--------+--------------+--------------+---------------------+---------+---------+----------+
|  75402 | 2022-04-30   |            1 | 2022-05-16 21:11:50 | 2b48129 | e4205d8 | 20:00:41 |
| 173141 | 2022-04-29   |            5 | 2022-05-16 21:13:17 | 2b2e1b4 | 9df3407 | 20:00:01 |
| 207430 | 2022-04-28   |            2 | 2022-05-16 21:13:47 | 2b31924 | 256b363 | 20:00:50 |
| 412796 | 2022-04-10   |            8 | 2022-05-16 21:16:51 | 2b6c98c | af6dd3a | 20:00:43 |
| 492708 | 2022-04-07   |            2 | 2022-05-16 21:18:02 | 2b14a6b | 274ab3d | 20:00:03 |
| 610563 | 2022-04-04   |            7 | 2022-05-16 21:19:46 | 2b6ccba | 53e06ac | 20:00:32 |
| 646019 | 2022-04-09   |            3 | 2022-05-16 21:20:19 | 2b43c53 | 0d3dd41 | 20:00:59 |
| 702301 | 2022-04-21   |            6 | 2022-05-16 21:21:15 | 2b57afe | 8549b1b | 20:00:25 |
| 798381 | 2022-04-23   |            8 | 2022-05-16 21:22:43 | 2b4bf39 | cde432b | 20:00:15 |
| 839637 | 2022-04-24   |            4 | 2022-05-16 21:23:20 | 2b8adfc | 366a865 | 20:00:24 |
| 999538 | 2022-04-24   |            7 | 2022-05-16 21:25:42 | 2bf2434 | f91cefd | 20:00:27 |
+--------+--------------+--------------+---------------------+---------+---------+----------+
11 rows in set (0.45 sec)

중복도가 높은 쪽에 인덱싱을 적용하니 인덱싱을 사용하지 않는 쿼리와같이 0.45초가 소요된다 이렇게되면 인덱싱을 적용한 것이 의미가 없어진다. 데이터를 100만개가 아니라 1000만개 생성했다면 차이가 더 극명했을 것 같다. 다음 포스트에서는 B+ Tree에 대해 알아보도록 하겠다.

May 17, 2022

Database

AI Enthusiast and a Software EngineerJason Kang on LinkedIn