[Index] Composite Index (복합 인덱스)

주로 단일 인덱스를 많이 사용해 왔고 복합인덱스를 가끔 사용하곤 한다. 최근 면접 질문에서 관련 이야기가 나왔고 제대로 대답을 하지 못했다. 복합인덱스가 어떻게 저장되는지, 복합인덱스의 순서를 어떻게 해야 효과적으로 사용할 수 있는지에 대한 것은 사용하는 입장에서 당연히 알아야 할 개념이었다. 무턱대고 설정해 놓는다면 인덱스가 소용없게 될 수도 있다. 이번에 인식한 김에 정리를 해보았다.

참고로 postgresql을 기준으로 하였다.

목차는 아래와 같다

1. 복합인덱스란?

2. 복합 인덱스의 구조, 어떻게 생겼고 어떻게 작동하나?

3. 복합인덱스는 어떻게 설계해야할까?

4. 정리

1. 복합인덱스란?

이미지출처 : https://minervadb.xyz/composite-indexes-in-postgresql/

복합인덱스는 하나 이상의 컬럼을 을 조합하여 만든 인덱스이다. 예를 들어 "name" 과 "age" 라는 두 열에 대해 검색이 자주 일어난다면, 이 두 열을 묶어서 인덱스를 만드는 것이 복합인덱스다.

복합인덱스라고 해서 복합인덱스 생성에 사용된 모든 컬럼을 조회할 때에만 적용되는 것이 아니라 특정 컬럼만 사용한 쿼리에서도 적용될 수 있다. 하지만 이는 쿼리 플랜에 의해 full sequence scan으로 진행될 가능성이 있다. 인덱스의 가장 왼쪽(첫 번째로 사용된 컬럼)이 먼저 조건에 나올수록 더욱 효율적으로 작동된다. 앞쪽 컬럼에 조건이 있을수록 범위를 좁히기 때문이다.

아래의 예시를 보자

10만 개의 데이터가 있는 employees 테이블에 아래와  department_id와 first_name으로 복합인덱스를 추가하였다.

"idx_employees_department_first_name" btree (department_id, first_name)

                                            Table "public.employees"
    Column     |          Type          | Collation | Nullable |                    Default
---------------+------------------------+-----------+----------+------------------------------------------------
 employee_id   | integer                |           | not null | nextval('employees_employee_id_seq'::regclass)
 department_id | integer                |           | not null |
 first_name    | character varying(100) |           | not null |
 last_name     | character varying(100) |           | not null |
 age           | integer                |           | not null |
Indexes:
    "employees_pkey" PRIMARY KEY, btree (employee_id)
    "idx_employees_department_first_name" btree (department_id, first_name)

1. first_name으로만 데이터를 검색하는 경우

SELECT employee_id,department_id,first_name,age
FROM employees
WHERE first_name = 'first 10';


Seq Scan on employees  (cost=0.00..2083.00 rows=1 width=23) (actual time=0.035..12.217 rows=1 loops=1)
   Filter: ((first_name)::text = 'first 10'::text)
   Rows Removed by Filter: 99999
 Planning Time: 0.163 ms
 Execution Time: 12.257 ms
(5 rows)

위의 경우 인덱스는 타지 않고 시퀀스 스켄만 하는 것을 볼 수 있다. 이유는 복합인덱스의 첫 번째 컬럼인 department_id 조건이 포함되지 않았기 때문이다. (이렇듯 복합인덱스를 설정할 때에는 순서가 중요하다. 복합인덱스 순서에 관한 내용은 아래에 추가해 놓았다)

2. department_id만 검색하는 경우

SELECT employee_id,department_id,first_name,age
FROM employees
WHERE department_id = 15;

Bitmap Heap Scan on employees  (cost=23.91..910.28 rows=967 width=23) (actual time=0.488..2.371 rows=973 loops=1)
   Recheck Cond: (department_id = 15)
   Heap Blocks: exact=575
   ->  Bitmap Index Scan on idx_employees_department_first_name  (cost=0.00..23.67 rows=967 width=0) (actual time=0.384..0.384 rows=973 loops=1)
         Index Cond: (department_id = 15)
 Planning Time: 0.274 ms
 Execution Time: 2.496 ms

이 경우 인덱스를 타긴 한다. 이유는 복합인덱스를 생성하는 첫 번째 열로 사용된 department_id로는 인덱스를 사용할 수 있기 때문이다.

Bitmap Heap Scan (조건을 만족하는 행의 위치를 인덱스에서 빠르게 찾고 해당 블록만 읽는 방식으로 동작)을 사용하여 동작함을 알 수 있다. 실행시간 또한 12.257 -> 2.496으로 20% 정도 줄었다.

3. depatrmtnr_id로만 검색하는 경우

SELECT employee_id,department_id,first_name,age
FROM employees
WHERE department_id = 15 and first_name = 'first 10';


Index Scan using idx_employees_department_first_name on employees  (cost=0.42..8.44 rows=1 width=23) (actual time=0.082..0.170 rows=1 loops=1)
   Index Cond: ((department_id = 15) AND ((first_name)::text = 'first 10'::text))
 Planning Time: 0.265 ms
 Execution Time: 0.212 ms

이 경우엔 인덱스스캔을 하였다. 조건에 department_id와 first_name 모두를 포함하고 있고 조건이 인덱스의 순서와 일치한다. 이런 조합은 복합 인덱스만으로도 두 값을 모두 찾아낼 수 있어 인덱스 스캔만으로도 찾을 수 있는 것이다.

이렇듯 복합인덱스는 다수의 컬럼을 사용하여 인덱스를 만드는 것이다. 그리고 여러 테이블에 데이터를 빠르게 결합할 수 있기 때문에 복잡한 쿼리에 사용하는 경우 효과적임을 알 수 있다.

하지만 보다시피 조건의 순서와 첫 번째 열의 유무에 따라 인덱스 사용 유무가 달라지고 여러 열을 결합하기 때문에 단일 인덱스에 비해 더 많은 데스크 공간을 필요로 하게 된다. Vaccume에 의해 관리되는 비용 또한 높아진다는 단점이 있다.

그러므로 복합 컬럼을 조회에 자주 사용되는 경우 고려해 볼 만하다

 

그렇다면 복합 인덱스는 어떻게 구성되어 있고 어떻게 작동하길래 위와 같은 특징을 갖는 것일까? 복합인덱스 구조에 대해 더 알아보자

참고문서 : postgresql 공식문서 Multicolumn Indexes

2. 복합 인덱스의 구조, 어떻게 생겼고 어떻게 작동하나?

복합 인덱스도 단일 인덱스와 비슷하게 메인테이블에 대한 포인터가 인덱스 키 값을 기준으로 정렬된 상태이다.
차이점은 복합 인덱스는 첫 번째 컬럼을 기준으로 정렬된 데이터를 저장하며, 나머지 컬럼은 리프 노드에서 추가적인 조건 필터링에 사용된다는 점이다.

• 일반적인 B-tree Index 구조
  • PostgreSQL의 일반적인 B-tree 인덱스는 각 노드에 인덱스 키와 자식 노드를 가리키는 포인터가 존재하며, 리프 노드는 인덱스 키와 테이블의 데이터 행 위치(TID)를 포함한다. 리프 노드들은 정렬된 상태로 저장되어 있어 범위 검색에 유리하며, 서로 연결되어 있어 순차 검색에도 효율적이다.

이미지 출처 : https://www.qwertee.io/blog/postgresql-b-tree-index-explained-part-1/

• B-tree 복합 인덱스 구조
  • 복합 인덱스 구조 또한 기본 인덱스 구조와 비슷하지만, 여러 열을 기준으로 데이터를 정렬하고 저장한다.
    예를 들어, department_id와 first_name으로 구성된 복합 인덱스의 내부 노드는 department_id를 기준으로 트리를 나누며, 리프 노드에는 복합 키의 모든 정보를 저장하고 각 키에 해당하는 테이블의 데이터 행 위치(TID)를 포함한다.

이미지 출처 : https://www.qwertee.io/blog/postgresql-b-tree-index-explained-part-1/

 

조금 더 설명하자면 , 복합 인덱스를 사용한 검색은 계층적으로 진행된다.

1. 쿼리 실행 시, PostgreSQL은 복합 인덱스의 첫 번째 열(department_id)을 기준으로 내부 노드에서 탐색 경로를 결정한다.
2. department_id 범위를 좁힌 후, 리프 노드에서 두 번째 열(first_name) 조건을 추가로 확인한다.
3. 최종적으로 리프 노드에 저장된 TID를 통해 실제 데이터 행을 읽어온다.

 

또 다른 예로 아래의 그림을 보면 main index인 year로 범위를 좁힌 다음 그다음 열인 make를 추가로 확인한다. 그리고 다음 열인 mode을 확인하는 과정을 거친다.

이미지 출처 : https://www.atlassian.com/data/sql/multicolumn-indexes

 

기억해야 할 점은, 위와 같은 구조를 갖고 있기 때문에 복합 인덱스는 첫 번째 열이 조건에 포함되지 않으면 사용되지 않는다. 포함하지 않고 검색하는 경우 인덱스를 전혀 타지 않을 수 있으며 이런 경우 개별 인덱스가 필요하다. 그러므로 복합인덱스는 여러 열을 함께 사용하는 조건으로 데이터를 자주 조회할 때 유용하다. 예를 들어, WHERE name = 'Alice' AND age > 25와 같은 쿼리에서 name과 age에 대한 복합인덱스를 사용하면 검색 속도가 매우 빨라진다. 또한 특정 열에 대해 정렬이나 그룹핑을 할 때도 복합인덱스가 도움이 된다. 다만, 인덱스를 너무 많이 사용하거나 잘못된 순서로 설정할 경우 오히려 성능을 저하시킬 수 있으므로 주의가 필요하다.

- 참고문서 :

- https://www.qwertee.io/blog/postgresql-b-tree-index-explained-part-1/
- https://www.atlassian.com/data/sql/multicolumn-indexes

3. 복합인덱스는 어떻게 설계해야 할까?

위에서 설명한 것처럼, 복합 인덱스는 계층적으로 작동하며 첫 번째 열을 기준으로 탐색 범위를 좁힌다고 했다. 따라서 복합 인덱스를 설계할 때는 열의 순서를 신중히 결정해야 한다. 이 과정에서 다음과 같은 요소를 고려해야 한다.

1. 쿼리 패턴 분석

복합 인덱스는 빈번히 조회되는 쿼리 패턴을 기반으로 설계해야 한다. 어떤 열이 주로 조건에 사용되는지, 어떤 순서로 조건이 적용되는지를 분석하여 설계 방향을 결정해야 한다.
예를 들어, "특정 부서에서 특정 직원"을 조회하는 쿼리가 많다면, (department_id, first_name) 순으로 인덱스를 설계할 수 있다. 반면, "특정 회사에서 특정 부서"를 조회하는 쿼리가 많다면, (company_id, department_id)로 설계하는 것이 적합하다.

2. 카디널리티(고유 값의 수) 고려

데이터의 카디널리티는 탐색 성능에 미치는 영향이 크다. 카디널리티가 높은 열(중복이 적은)은 더 작은 데이터 범위를 생성하기 때문에 탐색 비용을 크게 줄일 수 있다. 따라서 일반적으로 카디널리티가 높은 열을 첫 번째 열로 설정하는 것이 유리하다.

3. 동등 조건을 먼저, 범위 조건을 나중에

Markus Winand의 원칙에 따르면, 동등 조건(=)이 첫 번째 열에 적용되어야 탐색 범위를 효과적으로 좁힐 수 있다고 한다. 범위 조건(<, >, BETWEEN)은 리프 노드에서 추가로 처리되므로 두 번째 열 이후에 사용하는 것이 효율적이다.

간단한 예시를 보자, 첫 번째 열을 범위조건으로 검색을 했을 때는 3.127 ms이고 동등검색의 경우 실행시간이 0.106ms로 차이가 난다. 

동등검색을 함으로써 범위를 바로 좁힐 수 있기 때문에 훨씬 검색에 유리하다.

- 범위조건 검색

testdb=# explain analyze
SELECT employee_id,department_id,first_name,age
FROM employees
WHERE department_id < 50  and first_name = 'first 10';
                                                                    QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using idx_employees_department_first_name on employees  (cost=0.42..1279.36 rows=1 width=23) (actual time=1.014..3.074 rows=1 loops=1)
   Index Cond: ((department_id < 50) AND ((first_name)::text = 'first 10'::text))
 Planning Time: 0.273 ms
 Execution Time: 3.127 ms
(4 rows)

- 동등조건 검색

testdb=# explain analyze
SELECT employee_id,department_id,first_name,age
FROM employees
WHERE department_id = 15 and first_name = 'first 10';
                                                                   QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using idx_employees_department_first_name on employees  (cost=0.42..8.44 rows=1 width=23) (actual time=0.065..0.068 rows=1 loops=1)
   Index Cond: ((department_id = 15) AND ((first_name)::text = 'first 10'::text))
 Planning Time: 0.214 ms
 Execution Time: 0.106 ms
(4 rows)

 

4. 리프 노드에서 데이터 범위를 점진적으로 좁힐 수 있도록 설계(계층적인 구조 고려)

일반적으로 필터링의 범위를 좁히는 조건을 먼저 두는 것이 유리하다.

예를 들어, 전화번호부가 last_name → first_name 순으로 정렬되어 있다고 가정해 보자. last_name(성) 없이 first_name만으로 검색하려면 모든 데이터를 순차적으로 읽어야 하므로 비효율적이다. 그러나 성을 먼저 찾아 해당 범위로 이동한 후 이름을 검색한다면 더욱 효율적일 것이다.

계층적인 구조에서도 같은 원칙이 적용된다.
예를 들어,  company_id → department_id → employee_id와 같은 계층적 데이터 구조에서는, 상위 계층 데이터(company_id)를 기준으로 먼저 범위를 좁히고, 이후 하위 데이터를 탐색하는 방식이 적합하다.

즉, 복합인덱스 설계 시 순서는 위의 4가지 기준을 고려하여 설계해야 한다.

4. 정리

간단하게 복합인덱스의 개념과 구조, 그리고 설계 방법에 대해 알아보았다.

복합인덱스 설계 시 고려해야 할 점을 다시 정리해 보면 아래와 같다.

• 쿼리 패턴 분석
• 카디널리티(고유 값의 수)
• 동등 조건 우선, 범위 조건 나중
• 리프 노드에서 점진적으로 데이터 범위 좁히기(계층적 구조 고려)

위의 예시를 RDB인 Postgresql로만 했는데 참고로 NoSQL 에도 복합 인덱스가 있다. RDB와는 구조가 다르지만 복합 인덱스를 통해 여러 필드를 동시에 인덱싱하여 쿼리 성능을 최적화할 수 있다고 한다.

MongoDB의 경우 아래와 같이 복합인덱스를 구성할 수 있다. 

db.collection.createIndex({ category: 1, price: -1 });
db.collection.find({ category: "books", price: { $lt: 50 } });

위 인덱스는 category로 먼저 범위를 좁히고 해당 범위 내에서 price를 역순으로 정렬하며 검색한다.

ElasticSearch 또한 인덱스를 다중 필드로 설정하여 복합인덱스와 유사한 방식으로 동작할 수 있다고 한다. 아래의 참고문서를 확인해 보자

- 참고문서 : [ElasticSearch 다중 필드]

여기까지 복합인덱스에 간단하게 알아보았다.