[DB] 인덱스 머지 (Index Merge)

0. 학습 목적

• 인덱스 머지가 무엇인지 이해한다.
• 인덱스 머지의 종류인 교집합, 합집합, 정렬 후 합집합을 이해한다.

1. 인덱스 머지란?

Index Merge 란 하나의 테이블에서 두 개 이상의 인덱스를 활용하여 데이터를 선별하고 그 결과를 병합하여 쿼리를 처리하는 최적화 전략이다.

만약 해당 옵션을 켜두지 않았다면, 옵티마이저는 쿼리를 처리할 때, 하나의 테이블에서는 오로지 하나의 인덱스를 활용한다.

2. 사용되는 조건

1. 쿼리에 사용된 각각의 조건이 하나의 테이블 내의 서로 다른 인덱스를 활용할 수 있다.
2. 하나의 인덱스로만 처리했을 경우 범위 필터링 효과가 미미하다.

3. 종류

1. intersection
   : 각기 다른 인덱스로 필터링한 데이터들 사이의 교집합만 반환
2. union
   : 각기 다른 인덱스로 필터링한 데이터들 사이에 합집합만 반환 (중복 제거를 위한 추가 정렬 작업 필요 x)
3. sort union
   : 2번과 같으나 중복 제거를 위해 인덱스를 활용하지 못해서 추가 정렬 작업이 필요함.

(1) 교집합 (index_merge_intersection)

1. 하나의 테이블에서 2개 이상의 인덱스로 각각 유효한 데이터를 필터링한다.
2. 필터링한 데이터들 중 교집합만 본 테이블 읽어서 추가 데이터를 얻고 사용자에게 반환한다.

만약 다음과 같이 테이블이 존재한다고 하자.

CREATE TABLE emplyoees (
    emp_no int (PRIMARY),
    last_name VARCHAR(20),
    first_name VARCHAR(20),
    hire_date DATE
    INDEX idx_first_name (first_name);
    INDEX idx_hire_date (hire_date);
)engine='innodb'

이후 다음 쿼리문을 실행한다.

explain
select * from employees
where first_name = 'Georgi'
and emp_no between 10000 and 20000;

테이블을 확인해보면 first_name에게는 보조 인덱스가 존재하고, emp_no는 PK라 클러스터링 인덱스가 있다.
만약 옵티마이저가 둘 중 하나만 써도 쿼리문을 효율적으로 처리할 수 있다면, 그 방법을 선택했을 것이다.
하지만 만약 실행 계획에 Using Intersect 라고 나온다면 다음과 같이 처리 된 것이다.

1. first_name = Georgi 조건은 idx_first_name으로 필터링
2. emp_no between 10000 and 20000 은 클러스터링 인덱스로 필터링
3. 둘의 교집합만 결과 데이터로 반환

A. Index-merge-교집합이 더 효율적인 경우는 언제일까?

위의 쿼리문 처리를 위해 하나의 인덱스만 사용했다고 가정해보자.

경우 1. 보조 인덱스만 활용

1. idx_first_name 보조 인덱스로 이름이 Georgi인 사람을 range-scan 하니 10만 명 중 253명이었다.
2. 해당 253명 중 사번이 10,000 에서 20,000인 사람을 찾기 위해, 하나의 레코드마다 본 테이블과 접근하여 일일히 비교한다. -> 본 테이블 읽기 작업 (253번 필요)

경우 2. PK만 활용

1. PK인 사번으로 range-scan 해보니 사번이 10,000 - 20,000 인 사람은 만 명이다.
2. 이 만 명에 대해 각각 이름이 Geogi인지 확인한다. (만 번의 Where 조건 비교 작업 필요)

경우 3. 인덱스 머지 활용

1. idx_first_name과 PK 모두 range-scan 해서 유효한 데이터를 가져온다.
2. 양쪽 모두 PK로 정렬되어 있다. 따라서 병합 정렬 알고리즘으로 추가 데이터 비교 작업 없이 교집합을 찾아 반환한다.

만약 최종적으로 이름이 Georgi이고 사번이 만 번대인 사람이 14명이면 경우1은 239번의 데이터 읽기가 불필요한 작업이고 경우 2는 9,986 건이 불필요한 작업이었다.

[!hint] 실행 계획 상 표시
Using intersect(사용한 모든 인덱스 이름 나열됨)

(2) 합집합

해당 인덱스 머지는 OR 연산으로 합집합을 구하는 쿼리문에 대한 최적화 전략이다. 다음과 같이 작동한다.

1. 하나의 테이블 내에 쓸 수 있는 인덱스를 전부 활용하여 유효한 데이터만 남기기
2. 데이터 집합들 사이에 중복 제거 (Union 병합 알고리즘을 활용)
3. 중복 제거된 데이터 반환

2번의 데이터 집합 사이에 중복 제거에서 병합 알고리즘을 사용하는데, 병합 알고리즘 특성 상, 데이터들이 정렬되어 있는 상태라는 게 전제되어야 한다. 왜냐하면 정렬되어 있어야만 데이터의 위치를 특정하고 중복 여부를 빠르게 파악할 수 있기 때문이다. 이제 정렬을 위한 추가 작업이 필요 없는 경우와 필요한 경우를 나눠서 설명해보자.

A. 정렬 추가 작업이 필요 없는 경우(index_merge_union)

교집합 때와 똑같은 테이블에 다음과 같은 합집합 쿼리를 실행한다고 해보자.

SELECT *
FROM employees
WHERE first_name = 'Matt' OR hire_date = '1987-03-31'

만약 idx_first_name이나 idx_hire_date를 단독 사용하는 것의 필터링 효과가 미미할 경우, 위의 index_merge_union 방식을 활용할 것이다.

이때 두 보조 인덱스 모두 동등 비교이기 때문에 유효한 레코드는 PK가 정렬된 형태로 가져올 수 있다.
이렇게 정렬된 상태의 유효한 데이터 집합은 따로 추가 정렬 작업 없이 UNION 병합 알고리즘을 활용해 데이터를 병합하면 된다.

예를 들어 이름 보조 인덱스의 경우 다음과 같다.

이름이 '사임당'으로 같은 사람들 사이에 사번은 정렬되어 있는 것을 볼 수 있다. 이는 고용일 보조 인덱스도 마찬가지이다.

[!hint] 왜 저렇게 PK가 정렬되어 있을까?
B-Tree의 저장 특성 때문이다. B-Tree는 왼쪽에 있는 컬럼일수록 정렬 우선순위가 높다.
예를 들어 (col1, col2, co3) 순이면, co1 순으로 정렬 col1이 같다면 col2 순 정렬, col2도 같다면 col3 순으로 정렬된다.

따라서 위의 쿼리문은 동등 비교이기 때문에 보조 인덱스 컬럼 키는 동일할 것이므로 후순위인 PK 값으로 정렬된 상태일 것이다.

B. 추가 정렬 작업이 필요한 경우 (index_merge_sort_union)

explain
select * from employees
where first_name = 'Matt'
and hire_date Between '2025-01-01' and '2025-02-28'

이번의 hire_date 구문은 범위 조건인 것을 볼 수 있다. 이렇게 되면 당연히 고용일 순으로 정렬되어 있지 PK 순으로는 정렬되어 있지 않다. 따라서 index_merge가 활용된다면, 합집합 시 중복 제거를 위해 인덱스에서 나온 모든 데이터 집합을 PK 순으로 정렬하는 작업을 거친다.

4. 핵심 요약

1. index_merge 전략은 하나의 테이블에서 두 개 이상의 인덱스를 활용하여 쿼리 처리를 최적화하는 전략이다.
2. 사용 조건은 쿼리 각각의 조건이 서로 다른 인덱스를 활용할 수 있으며, 하나의 인덱스를 단독 사용하여 쿼리 처리 시에는 필터링 효과가 미미한 경우이다.
3. index_merge의 종류에는 교집합(intersect), 추가 정렬 작업 없는 합집합, 추가 정렬 필요한 합집합 으로 나뉜다.
   1. 교집합은 인덱스로 필터링한 데이터 집합 사이의 교집합을 반환한다.
   2. 합집합은 인덱스로 필터링한 데이터 집합 사이의 합집합을 반환하는데 이를 위해서 정렬 작업이 필요하다.
      • 이미 PK 순으로 정렬되어 있다면 추가 정렬 작업이 필요없지만 아니라면 모든 테이블에 관해 PK 순 정렬 작업을 추가 진행한다.

---

부록

A. 모르는 단어 정리

B. 참고 문서

• real-my-sql 329p - 334p