[ClickHouse] INDEX 구조와 동작 원리 - ②

  전통적인 RDB에서는 PK Index 외에도 "보조" Index를 Create 해서 다른 Column에 대한 Index를 지원합니다.

Click-House에서는 Skipping-indexes 라는 방법으로 이를 지원합니다. Data의 Block을 읽는 방법으로 Index를 활용하는 만큼, 일치하는 값이 없는 Data Block은 건너뛸 수(Skip) 있기 때문에 이를 통해 Skipping-indexes를 구현합니다.

  Skipping-indexes는 Skip 할 Data Block을 찾는 방법이 여러가지 있어서 상황에 맞게 방법을 바꿀 수 있습니다. 다만 이번에는 그 중에서 Min-Max Type에 한정하여 설명합니다.

  Click-House에서는 Table이 생성되면, PK의 값에 따라 데이터를 granule이라는 Data Block으로 묶어 관리합니다. ([ClickHouse] INDEX 구조와 동작 원리 - ① 참조)
Skipping-indexes는 이 granule을 다시 한번 그룹으로 묶습니다.

  위 그림은 skipping-index를 생성했을 때 생성되는 index 파일입니다. skipping-index의 index 파일에서는 granule (Data Block)을 4개 단위로 묶어 하나의 mark로 표현합니다. 그리고 4개의 granule에서 Index로 사용할 Column의 최소 (Min), 최대(Max)값을 저장합니다.

이제 특정 Column의 값을 검색할 때, 해당 Column의 값이 mark N번째가 갖는 min, max 범위 안에 있는 지를 확인 합니다. 그리고 범위 안에 들어간다면 해당하는 mark의 granule 묶음을 모두 가져온 뒤, 그 안에서 데이터를 찾아내는 방식으로 Index를 탐색합니다.

 아래는 skipping-indexes에 대한 테스트를 진행한 결과입니다.

  위 쿼리에서 사용된 Table은 PK가 'vst_dt'인 Table입니다. WHERE절에 조건으로 사용된 'cust_id'에 skipping-index가 적용되었을 때와 적용되지 않았을 때의 차이를 확인하면 아래와 같습니다.

동일한 data로 동일한 환경에서 진행하였고, 위 쿼리를 수행했을 때 결과 출력까지 걸린 응답 시간을 체크했습니다.
  1차 ) 미적용 시 1.368s // 적용 시 0.024s
  2차 ) 미적용 시 0.850s // 적용 시 0.036s

성능 적인 면에서 확연하게 차이가 나는 모습을 볼 수 있습니다.

 

Skipping-indexes를 만드는 방법은 아래와 같습니다.

  - ALTER TABLE [TABLE명] ADD INDEX [INDEX명] [COLUMN명] TYPE [TYPE명] GRANULARITY [묶을 Granule 수];

위 명령을 통해 Skipping-indexes를 만듭니다. 새로 삽입된 Data만 적용되므로 Index를 추가하는 것으로는 기존 Data를 Query하는 데에 영향을 미치지 못합니다. 이미 존재하는 Data까지 Indexing 하려면 아래의 명령문도 함께 사용해야 합니다.

  - ALTER TABLE [TABLE명] MATERIALIZE INDEX [INDEX명];

 

  테스트의 결과는 효과가 있었습니다. 다만, Skipping-index는 보조 인덱스로써 큰 단점이 있습니다. Granule 단위로 그룹을 묶은 순간, granule이 정렬된 데이터 구조에 따라 Skipping-indexes의 탐색 과정이 영향을 받는다는 것입니다. 쉽게 말해 granule 정렬의 기준이 되는 Primary key의 카디널리티가 높아 데이터가 대부분의 granule에 퍼져 있는 경우, 결국 거의 모든 Data block을 읽게 되어 index를 탐색하는 것이 오히려 성능에 악영향을 미칩니다.

  결론적으로 Skipping-index를 사용하기 위해서는 Primary key와 Indexing 하려는 column 간에 상한 상관 관계가 요구됩니다. 이 경우 granule의 정렬에 따라 indexing 하려는 column의 데이터 역시 특정 block에 모이게 되어 많은 수의 block을 건너 뛰게(skip) 되어 좋은 성능 상의 이점을 볼 수 있습니다.

 

PK 의 선행 키가 있는 보조 키 column의 Index

  Primary Index를 사용해서 Block 단위로 Data를 찾아가는 Sparse Index의 경우, Data가 이미 PK 순서로 정렬된 채로 저장이 되어 있기 때문에 가능하다고 했습니다. ([ClickHouse] 공유 - ClickHouse Index에 관한 자료 - ① 참조)

  Primary Key가 복합 키인 경우, 앞에 기재된 Column부터 오름차순으로 정렬됩니다.
그 결과 아래와 같은 데이터 구조와 Index 구조를 갖게 됩니다.
[복합 Primary Key (UserID, URL) (선행 키:UserID//보조 키:URL)]

  위와 같은 구조에서는 UserID 컬럼을 기반으로 먼저 데이터 정렬한 뒤, URL 컬럼 기반 정렬이 이루어집니다. 이 말은 특정 UserID 의 Index를 통해 Data를 필터링 한 뒤에야 URL Index가 의미가 있다는 이야기가 됩니다.

  따라서 UserID 없이 URL 값 만을 통해서 Index를 탐색하려 하면, 1번에서 말한 Skipping-index와 같은 문제가 발생할 가능성이 생깁니다. UserID와 URL과의 상관 관계가 낮은 경우, 두 column의 카디널리티가 비슷하게 높은 경우 Index를 통해 granule을 skip하지 못하고 대부분의 data block을 읽게 됩니다.

  이는 skipping-index를 사용하든, Primary Index를 통하든 Primary Key의 순서와 선행 키 Column의 카디널리티에 영향을 받는다는 말이 됩니다.

  아래의 그림은 PK 선행 키의 카디널리티에 따라 보조 키 Index 검색이 영향을 받는 예시입니다.

  예시 1) 선행 키의 카디널리티가 낮은 경우입니다. 선행 키의 카디널리티가 낮음으로 인해 granule의 정렬이 보조 키의 정렬 순서와 근접한 구조를 갖게 됩니다. 이 경우 보조 키의 Index를 탐색할 때 선행 키(UserID)에 크게 영향을 받지 않고, 특정 granule에 원하는 값이 집중되어 모이게 됩니다.

  이는 Index를 탐색하면서 많은 data block을 건너 뛰고, 최소한의 block만을 가져올 수 있게 되어 성능이 빨라집니다.

  예시 2) 선행 키의 카디널리티가 높은 경우입니다. 선행 키의 카디널리티가 높아 granule이 선행 키에 의해 먼저 정렬되고, 이미 정렬된 data block 안에서 보조 키(URL)가 정렬됩니다. 이 경우 보조 키의 데이터가 서로 같은 값을 가져도 선행 키(UserID)의 정렬에 따라, 다른 granule에 들어가 있을 가능성이 높습니다.

  이는 보조 키의 Index를 탐색하면서, 여러 granule에 분산 되어있는 값을 찾아 많은 수의 Data block을 탐색하고 가져오게 됩니다.

  결국 Click House의 Index란 Primary Key의 선행 키가 갖는 카디널리티에 영향을 받습니다. 결론적으로 Index에 의한 성능 향상은 'Index를 얼마나 어떻게 잘 쓰는지'가 아니라 'Primary Key에 따른 Data의 구조가 얼마나 쿼리에 최적화 되어 있느냐'가 결정하게 됩니다. 따라서 특정 column를 필터링하는 (Index를 탐색하게 되는) 쿼리의 속도를 높이려면 해당 쿼리에 맞는 Primary Index를 사용해야 하며, 이 말은 곧 쿼리에 따라 Primary Key가 달라져야 한다는 말이 됩니다. (여러 Primary Index의 필요성)

  Click-House는 이를 충족할 수 있는 세 가지 방법을 제시합니다.
    - Primary Key가 다른 Copy Table 생성
    - Primary Key가 다른 Materialize View 생성
    - 기존 Table에 Primary Key가 다른 Projection을 추가

다음번 자료 공유에는 위 세 가지 방법에 대해 다루도록 하겠습니다.

 

 

 

참조 ) https://clickhouse.com/docs/en/optimize/sparse-primary-indexes#secondary-key-columns-can-not-be-inefficient

참조 ) https://clickhouse.com/docs/en/optimize/skipping-indexes

참조 ) https://clickhouse.com/blog/clickhouse-faster-queries-with-projections-and-primary-indexes