데이터베이스 - 인덱스

인덱스(Index)

---

엄청나게 큰 규모의 데이터에서 원하는 데이터를 찾는다는 것은 쉽지 않다.

실제로 몇 GB의 데이터에서 원하는 데이터를 select 쿼리문을 통해 조회하게 되면 엄청 느린 속도로 조회되거나 혹은 아예 동작을 안 할 수도 있다.

그렇다면 어떻게 하면 요청된 데이터를 빠르게 조회할 수 있을까?

이럴때 사용되는 도구가 바로 인덱스(Index)이다.

인덱스라고 하면 가장 많이 나오는 예시가 바로 책이다.

책을 한 번이라도 읽어본 사람은 책의 앞부분에 목차가 있다는 것을 알 것이다.

이러한 목차는 내가 원하는 정보를 바로 찾을 수 있게 해 주는데 만약 목차가 없었다면 내가 원하는 정보를 페이지 하나씩 넘겨보며 찾아야 될 것이다.

또 다른 예시를 들어보면 만약 자바를 공부하기 위해 자바 언어에 대한 책을 구입했다고 가정해 보자.

연산자랑 조건문, 반복문 등은 이미 알고 있어서 바로 객체에 대해서 공부를 하고 싶다.

책의 목차가 있다면 객체의 설명이 몇 페이지에 나와있는지 확인하고 해당 부분을 바로 펼쳐보면 되지만, 목차가 없는 책이라면 자바의 역사부터 시작해서 찾아야 되는 아주아주 귀찮은 일이 생긴다.

이처럼 인덱스는 내가 원하는 정보를 빨리 찾아주는 것도 있지만, 다른 의미에서는 쓸데없는 조회를 줄이는 것이다.

그리고 또 하나 알 수 있는 것은 특정 조건을 만족하는 데이터들을 빠르게 조회하기 위해 인덱스가 사용된다는 것을 알 수 있다.

그럼 인덱스가 어떻게 성능을 높여주는 것일까?

인덱스는 쿼리 속도를 높이기 위해 사용되는 강력한 도구로 실제 물리적인 디스크 방문 횟수를 최소화하여 데이터베이스 성능을 향상한다.

다시 책을 가지고 예시를 들어보면 책의 내용은 이미 적혀있는 상태로 바뀌지 않는다.

단순히 목차 페이지를 만들어서 기존의 책에서 맨 앞 페이지에 끼워주면 된다. 이러한 목차에는 간단한 책의 주제와 해당 주제가 적혀있는 페이지 번호가 담겨있게 된다.

인덱스도 똑같다고 생각하면 된다.

인덱스를 만들면 기존의 테이블 내용이 바뀌는 것이 아니라 인덱스라는 테이블이 하나 생기게 되고, 해당 인덱스에는 기존의 테이블의 속성 값과 해당 값이 어디에 위치하는지를 알려주는 포인터 값이 저장된다.

이를 통해서 인덱스 없이 테이블에서 데이터를 조회하게 되면 평균적으로 O(N) 시간복잡도를 가지게 되지만, 인덱스(B 트리 기반)라면 데이터를 조회하는데 O(logn)의 시간복잡도를 가진다.

이처럼 인덱스의 개념을 살펴보면 상당히 좋아 보이지만 만능이 되지는 못한다. 이에 대한 얘기는 인덱스의 단점에서 알아보자.

 

SQL을 통해서 인덱스 알아보기

---

인덱스를 어떻게 생성하는지 직접 SQL문을 통해서 살펴보자.

MySQL을 기준으로 작성했기 때문에 다른 DBMS에서는 조금씩 다를 수 있다.

대부분의 MySQL 인덱스(PRIMARY KEY, UNIQUE, INDEX, 및 FULLTEXT)는 B-트리에 저장됩니다

MySQL의 공식 문서를 살펴보면 인덱스의 내부 구조가 어떻게 이루어져 있는지 알 수 있다.

한 가지 알고 넘어가야 될 부분으로 대부분의 RDBMS는 테이블을 생성할 때 기본 키에는 인덱스가 자동 생성된다.

create table MEMBER (
	id INT primary key auto_increment,
	first_name VARCHAR(50),
	email VARCHAR(50),
	country VARCHAR(50),
	tel VARCHAR(50)
);

직접 인덱스를 생성해 보고 테스트하기 위한 예제로 MEMBER 테이블을 생성하였고, 총 5만 개의 더미 데이터를 넣어서 진행해 보았다.

 

• 인덱스 생성

인덱스를 생성하는 방법으로 DDL의 CREATE 문을 사용하는 방법이 있다.

예시로 name을 기준으로 인덱스를 생성했는데 이처럼 중복될 수 있는 값은 중복을 허용하는 인덱스를 걸어줘야 한다.

CREATE INDEX [인덱스_명] ON [테이블_명](속성);
CREATE INDEX emp_name_idx ON MEMBER(first_name);

어떤 인덱스를 만들 것인지 이름을 명시하고, 어떤 테이블에서 어떤 속성을 기준으로 가져올지를 SQL문을 작성하면 된다.

위의 SQL문과 같이 작성하면 MySQL에서는 중복을 허용한 인덱스를 만들어준다.

 

인덱스를 생성하는 다른 방법으로는 테이블을 생성할 때 인덱스를 걸어주는 방법이다.

CREATE TABLE MEMBER (
	id INT PRIMARY KEY,
	name VARCHAR(20) NOT NULL,
	email VARCHAR(20),
	country VARCHAR(20),
	tel VARCHAR(20),
	INDEX emp_name_idx(name),
);

 

 

• 복합 인덱스 생성(Multicolumn Index = Composite Index)

조회하는 SQL문을 작성하다 보면 원하는 데이터를 찾기 위한 조건이 여러 개가 될 수 있다.

예를 들어 google 이메일을 사용하는 회원 중에 전화번호가 000으로 시작하는 회원을 찾는 SQL을 작성해 보면

SELECT * FROM MEMBER WHERE email LIKE '%google%' AND tel;

이렇게 작성할 수 있는데, 이때 email과 tel에 대해서 각각 인덱스를 생성하는 것이 아닌 두 속성들을 조합해서 조회할 수 있도록 인덱스를 만드는 것을 복합 인덱스라고 한다.

 

CREATE UNIQUE INDEX emp_email_tel ON MEMBER(email, tel);

 

복합 인덱스를 DDL 문으로 작성해 보면 위와 같이 MEMBER 테이블에서 여러 속성들을 가져올 수 있다.

여기서 UNIQUE 키워드를 확인할 수 있는데 해당 키워드는 emp_email_tel이라는 인덱스의 모든 값이 고유해야 한다는 제약조건이다.

 

CREATE TABLE MEMBER (
	id INT PRIMARY KEY,
	name VARCHAR(20) NOT NULL,
	email VARCHAR(20),
	country VARCHAR(20),
	tel VARCHAR(20),
	INDEX emp_name_idx(name),
	UNIQUE INDEX email_tel_idx(email, tel)
);

이전에 살펴봤던 중복을 허용하는 인덱스처럼 테이블을 생성할 때 복합 인덱스를 추가할 수 있다.

 

테이블이 많아지게 되면서 인덱스를 많이 생성하게 되는데 현재 어떤 인덱스가 있는지 궁금할 때 사용하는 쿼리문이 있다.

SHOW INDEX FROM MEMBER;

위의 쿼리문을 실행하면 아래와 같은 정보를 확인할 수 있다.

 

중요한 정보만 알아보면 아래와 같다.

- Table: 테이블 이름
- Non_unique: 유니크 여부
- Key_name: 인덱스 이름
- Seq_in_index: 복합 인덱스의 순서
- Column_name: 컬럼 이름
- Collation: 인덱스 내부의 데이터 정렬 방식(A는 오름차순, D는 내림차순, Null은 정렬되지 않음)
- Null: 인덱스를 생성할 때 걸어줬던 속성이 Null을 허용하는

인덱스에 대한 정보를 더 알고 싶으면 밑의 링크를 참고해 보자.

MySQL :: MySQL 8.4 Reference Manual :: 15.7.7.23 SHOW INDEX Statement

 

 

인덱스 동작 방식

---

• 조건이 하나일 경우

만약 name이 A로 시작하는 사람을 찾는다고 가정해 보자.

인덱스는 기본적으로 바이너리 서치로 데이터를 탐색하게 된다.

위의 예시로 설명하면 인덱스에서 name 데이터의 중간 값인 Chandler와 A를 비교해 본다.

A는 C보다 앞서기 때문에 Chandler를 기준으로 위의 데이터를 다시 탐색하게 되고 Auberta를 찾게 된다.

원하는 데이터를 찾았으면 해당 데이터의 포인터를 확인해 실제 테이블에 있는 데이터를 찾게 되고 그 후 결과를 반환해 준다.

하지만 만약 name이 A로 시작하면서 tel이 000으로 시작하는 회원을 찾으려고 하면 문제가 발생하게 된다.

A로 시작하는 name을 찾았지만 인덱스에는 tel에 대한 정보가 없기 때문에 실제 테이블에서 name이 A로 시작하는 데이터를 먼저 찾고, tel에 대해서는 full scan을 해야 되는 문제가 생기게 된다.

 

• 조건이 하나 이상일 경우

앞서 인덱스에 없는 속성을 조회하면 full scan 해야 되는 문제가 발생하였는데 이를 개선하여 복합 인덱스로 조회를 할 경우 어떻게 동작하는지 살펴보자.

먼저 name과 tel 속성으로 인덱스를 생성했다고 가정하면 위와 같이 인덱스가 생성된다.

이전에는 name으로 데이터를 찾은 다음 실제 테이블에서 tel을 full scan 했다면 복합 인덱스에서는 name을 먼저 찾고, 해당 name의 tel을 탐색하게 된다.

이때 중요한 것은 어떤 속성을 기준으로 정렬이 되는 것인지가 중요한데 밑의 SQL문과 같이 인덱스를 생성했다고 가정해 보자.

CREATE UNIQUE INDEX emp_email_tel ON MEMBER(name, tel);

이렇게 인덱스를 생성하게 되면 왼쪽 속성인 email을 기준으로 정렬되고, 그 후 같은 name일 경우 tel을 기준으로 정렬된다.

위의 그림을 보면 만약 Auberta라는 이름의 회원이 두 명 있을 경우 그 두 명에 대한 tel이 정렬된다는 뜻이다.

이처럼 인덱스를 생성할 때 왼쪽 속성을 기준으로 정렬되기 때문에 속성의 순서가 매우 중요하다. 만약 name과 tel의 순서가 달랐다면 다른 결괏값을 반환할 수도 있다.

이렇게 복합 인덱스가 동작하는 과정을 알아봤는데 복합 인덱스에서도 full scan이 되는 문제가 발생한다.

SELECT * FROM MEMBER WHERE tel LIKE '000%';

만약 위의 쿼리문을 가지고 복합 인덱스를 조회하려고 한다면 full scan이 발생하게 되는데, 그 이유는 name을 기준으로 정렬이 된 상태에서 같은 name일 때 tel을 정렬하기 때문에 tel만 기준으로 본다면 정렬된 상태라고 보기 힘들다.

따라서 원하는 tel 정보를 찾기 위해서는 full scan을 할 수밖에 없고 인덱스의 장점을 발휘하기 힘들어진다.

 

• EXPLAIN으로 결과 확인해 보기

CREATE UNIQUE INDEX emp_email_tel ON MEMBER(name, tel);
CREATE UNIQUE INDEX tel_index ON MEMBER(tel);

위의 쿼리문을 실행하여 2개의 인덱스를 생성했다고 가정해 보자.

SELECT * FROM MEMBER WHERE tel LIKE '000%';

그런 다음 tel을 조회하는 쿼리문을 실행했을 때 2개의 인덱스 중 어떤 인덱스를 사용할까?

어떤 인덱스를 통해서 조회하고 있는지 알려면 EXPLAIN 키워드를 사용하면 된다.

EXPLAIN SELECT * FROM MEMBER WHERE tel LIKE '8%';

위의 쿼리문과 같이 EXPLAIN 키워드를 추가하면 해당 쿼리문이 어떤 인덱스를 기반으로 실행되었는지 확인할 수 있다.

실제로 해당 EXPLAIN 쿼리문을 실행하면 위의 사진과 같이 emp_tel이라는 인덱스를 기반으로 실행된 것을 확인할 수 있고, 조회를 했을 경우 어떤 값들이 반환되는지 확인할 수 있다.

그럼 딱히 어떠한 설정을 한 것도 없는데 어떻게 복합 인덱스가 아닌 인덱스를 실행할 수 있는 것일까?

DBMS의 내부 핵심 엔진으로 옵티마이저(Optimizer)라는 것이 있는데 해당 옵티마이저가 알아서 적절한 인덱스를 선택한다.

간혹 옵티마이저가 이상한 선택을 함. 그럴 때는 직접 명시해서 사용하면 된다.

테이블에 있는 데이터의 규모에 따라 어떨 때는 full scan이 더 좋은 상황도 있는데 이럴 때는 옵티마이저가 판단해서 더 좋을 것 같은 방식으로 조회를 해준다.

옵티마이저에는 규칙 기반 옵티마이저와 비용 기반 옵티마이저가 있는데 나중에 따로 정리를 할 예정이다.

 

인덱스의 단점

---

인덱스의 단점으로는 앞서 살펴봤던 그림을 통해서 알 수 있는데 바로 인덱스를 위한 부가적인 데이터가 생성된다는 것이다.

모든 속성에 대해서 인덱스를 생성하면 그만큼 부가적인 데이터가 생기는 것이므로 효율적이지 못하다.

또한 인덱스가 실제 테이블에 대해서 의존적이기 때문에 테이블에 있는 데이터가 변경되거나 추가되면 인덱스도 같이 변경이 발생하게 된다.

따라서 데이터의 변경이 자주 일어나는 테이블에 대해서 인덱스를 생성하지 말고 가급적이면 데이터의 변경이 적고, 데이터 조회 성능이 필요한 테이블에 대해서 인덱스를 생성하는 것이 좋다.

 

커버링 인덱스

---

인덱스 중에 커버링 인덱스가 있는데 사용자가 조회하려는 데이터가 인덱스 만으로 모두 커버가 가능한 것을 의미한다.

실제 조회하려고 하는 정보가 인덱스에 모두 포함되어 있기 때문에 실제 테이블까지 조회할 필요가 없어지므로 조회 성능이 더 빠르다.

 

해시 인덱스

---

인덱스 중에서 해시 인덱스도 있는데 해시 테이블을 사용해서 구현한 인덱스이다.

해시 테이블의 장점을 활용하여 O(1)의 시간복잡도로 데이터에 접근할 수 있어 상당히 빠른 성능을 보여준다.

하지만 데이터의 규모가 커지면서 해시 테이블의 크기를 늘려야 되는 리해싱 과정이 많은 부담이 된다.

또한 데이터의 동일 비교(!=, ==)만 가능하고, 범위 비교(>, <)는 불가능하다는 단점이 있다.

 

참고 자료

What is a Database Index? | Codecademy

Introduction To Database Indexes

MySQL :: MySQL 8.4 Reference Manual :: 10.3.1 How MySQL Uses Indexes