[Database] 인덱스 (Index) 5장 : Multiple-key Access (다중 키)

https://kghworks.tistory.com/152

[Database] 인덱스 (Index) 4장 : Hash Index

 

4장까지 인덱스의 종류와 그 특징을 알아보았다. Ordered index와 Hash index가 있으며 Oredered index에서 B+-Tree index는 양이 많아 3장에 별도로 분리해서 설명했다.

 

지금까지 하나의 search key 로 인덱스를 탐색하는 걸 설명했지만, 실제  query 할 때 1가지 속성으로만 질의하기보다는 2가지 이상의 속성을 이용해 질의한다. 이를테면 아래처럼 2가지 속성을 이용한다.

 

select ID
from idol
where group_name = 'AESPA'
  and age = 23;

 

 relation idol에 group_name 속성과 age 속성을 조건을 주어 질의했다. 이때도 인덱스를 이용해 빠르게 찾으려는 record에 접근할 수 있어야 한다. 이번 포스팅에서는 2가지 이상의 속성으로 질의할 때 인덱스를 활용하는 방법을 알아본다. 간단히 다중키로 접근한다고 한다.

 

목차

• Multiple Single-key index
• Multiple-key index (Composite key index)
• Covering index
• Bitmap index

 

---

Multiple Single-key index

 속성마다 index가 있어서 2가지 이상의 인덱스를 활용하는 방법이다.

 

select ID
from idol
where group_name = 'AESPA'
  and age = 23;

 

 크게 두가지 전략이 있다. 첫 번째 전략은 둘 중에 group_name 인덱스를 통해 tuple을 찾고, 해당 tuple 중 age 조건이 맞는 tuple을 찾는 방법이다. 즉 하나의 인덱스만 활용하는 방법이다. age 인덱스를 활용한 다음 group_name 을 검사해도 된다. 

 

 다른 방법으로는 두 인덱스를 모두 사용하는 방법이다. group_name 인덱스를 사용하여 tuple을 추려내고, age 인덱스를 활용해 tuple을 추려낸다. 이렇데 2개의 tuple을 가지고 교집합에 해당하는 tuple을 결과로 생성한다. 이는 Bitmap index에서 매우 효과적인 방법이다. (Bitmap index는 추후 설명)

 다만 이 전략은 각 인덱스 결과 tuple이 매우 많고, 그 교집합은 상대적으로 매우 적을 때 성능이 떨어진다. 예를 들어 relation idol에서 group_name이 'AESPA'인 비율이 매우 많고, age가 23인 비율도 매우 많은데, 'AESPA'이면서 23인 비율은 매우 적은 경우다.

 

---

Multiple-key index (Composite key index)

 2가지 이상의 속성으로 인덱스를 생성하는 것을 말한다. 복합 인덱스라고도 한다. 위 경우 복합 인덱스를 사용하면 인덱스의 search key는  <group_name, age>가 된다. B+-Tree index에서 사용가능하고, range query도 가능해진다. 둘 중 하나의 속성으로만 조회할 때도 인덱스를 사용할 수 있다. 아래 경우 모두 인덱스를 사용하여 검색할 수 있다.

 

select ID
from idol
where group_name = 'AESPA'
  and age = 23;

-- range query
select ID
from idol
where group_name = 'AESPA'
  and age > 20;

-- 하나의 속성만
select ID
from idol
where group_name = 'AESPA';

 

그러나 아래 query는 인덱스를 사용할 수 없다.

 

-- 1개 이상의 비교연산자
select ID
from idol
where group_name < 'AESPA'
  and age < 23;

 

group_name이 'AESPA'보다 작은 인덱스 엔트리는 빨리 탐색할 수 있지만 그중에 age가 23보다 작은 엔트리는 서로 다른 disk block에 있기 때문에 많은 I/O Operation이 추가로 수행된다. 이 때는 그 대안으로 Btimap index, R-tree index와 같은 것들을 사용할 수 있다.

 

---

Covering index

인덱스 엔트리에 pointer와 함께 특정 속성의 값 (value)을 저장하는 방법이다. Secondary index (보조 인덱스)에서 유용한데 다음과 같은 경우를 보자.

 

select idol_name
from idol
where id = 'idol0001'

 

 위처럼 질의할 때 속성 id로 인덱스를 생성하고, idol_name 값을 인덱스에 저장하는 Covering index를 생성한다면 위 쿼리에서는 인덱스를 조회하는 것만으로 query가 끝난다. (Disk에 가서 record 읽을 필요 없음)

 

vs Multiple-key index

 복합 인덱스로 <id, idol_name>을 생성하는 것과, Covering index로 <id>로 생성하는 것은 어떤 차이가 있을까. query 성능은 비슷한 효과를 가져올 수 있지만 인덱스의 search key 가 Covering index의 사이즈가 더 작다. (space overhead) 따라서 더 B+-Tree의 단말노드에 큰 fanout을 보장할 수 있고, 그에 따라 전체 트리의 높이가 더 낮아질 수 있다. (access time)

 

---

Bitmap index

Bitmap index 예시 (속성 gender, income_level)

 

 single key 기반의 인덱스지만, 2가지 이상의 속성으로 query하는 것에 특화되어 있는 인덱스이다. 

 

bitmap은 bit로 이루어진 배열을 의미한다. 모든 record에 대해 각 record별로 숫자를 순차적으로 할당한다. (위 그림에서 record number)

 만약 relation r의 속성 A에 대해 Bitmap index를 생성했다면, 속성 A의 모든 고유 값에 대해 Bitmap index를 생성한다. 위 그림을 보면 gender 속성에 대해 Bitmap index를 생성했고, 해당 인덱스에는 값 m, f에 대해 Bitmap이 생성된 것을 볼 수 있다. 

 각 Bitmap의 임의의 bit i의 값이 1이면, record number i가 긍정 0이면, 부정을 뜻한다. 위 그림에서 속성 gender의 Bitmap index의 m bitmap을 보면 10010이 들어있다. record number 1, 3만 gender의 값이 'm'임을 볼 수 있다.

 

실제 동작

select *
from instructor_info
where gender = 'f'
  and income_level = 'L2';

 

 이런 query가 있다. 2가지 이상의 key로 query했고, 위 그림을 보면 각 속성마다 Bitmap index를 생성해 두었다. 이 query는 이렇게 진행된다.

 

1. 속성 gender가 'f'인 bitmap을 가져옴 (01101) 
2. 속성 income_level이 'L2'인 bitmap 가져옴 (01000)
3. 두 bitmap에 대해 논리곱 연산 (01000)
4. 결과 : record number = 1