Clickhouse Skip Index

Understanding ClickHouse Data Skipping Indexes | ClickHouse Docs

 

전통적인 방식에서는 B-tree 구조로 데이터베이스가 행을 log(n) 시간에 찾을 수 있게 했다. 하지만 클릭하우스의 경우 개별 row 가 존재하는게 아니기 때문에 작동하지 않는다.

 

대신 클릭하우스에선 skip 인덱스라는 걸 사용해서 불필요한 데이터 chunk 를 읽지 않아도 되는 방식을 제공한다. 각 구조마다 Skip 인덱스 표시가 되어 있어서 청크 단위로 읽지 않아도 되는 데이터를 표시를 해준다. 

 

Instead, ClickHouse provides a different type of index, which in specific circumstances can significantly improve query speed. These structures are labeled "Skip" indexes because they enable ClickHouse to skip reading significant chunks of data that are guaranteed to have no matching values.

 

유저가 data skipping index 를 만들면 data part 경로에 파일이 두개가 추가된다

• skp_idx_{index_name}.idx, which contains the ordered expression values
• skp_idx_{index_name}.mrk2, which contains the corresponding offsets into the associated data column files.

where 조건문에 index 가 걸린 칼럼에 대해서 접근하면 clickhouse 에서는 index 파일 데이터를 이용해서 처리해야하는 관련된 블록을 결정하고 걸러야 할 건 bypass 한다.

 

block 의 크기는 granularity 로 관리를 하는데 모든 색인된 블록은 별도의 granularity 를 갖고 있다. 볼지 말지 결정하는 chunk 의 크기이며 granularity 가 클수록 필터링하는 단위가 커진다.

 

 

예시

CREATE TABLE skip_table
(
  my_key UInt64,
  my_value UInt64
)
ENGINE MergeTree primary key my_key
SETTINGS index_granularity=8192;

INSERT INTO skip_table SELECT number, intDiv(number,4096) FROM numbers(100000000);

 

위와 같은 테이블에서 my_value 칼럼에 대해서 데이터를 조회하려고 하면 100m 개의 데이터를 모두 스캔해야하는 문제가 있다. 그래서 0.079 초가 걸림

SELECT * FROM skip_table WHERE my_value IN (125, 700)

┌─my_key─┬─my_value─┐
│ 512000 │      125 │
│ 512001 │      125 │
│    ... |      ... |
└────────┴──────────┘

8192 rows in set. Elapsed: 0.079 sec. Processed 100.00 million rows, 800.10 MB (1.26 billion rows/s., 10.10 GB/s.

 

여기에 인덱스를 추가하고 다시 스캐닝 해보면 속도가 0.02s 단축된 것을 확인할 수 있다. 데이터가 얼마 없어서 그리 차이는 나지 않은듯

ALTER TABLE skip_table ADD INDEX vix my_value TYPE set(100) GRANULARITY 2;

SELECT * FROM skip_table WHERE my_value IN (125, 700)

┌─my_key─┬─my_value─┐
│ 512000 │      125 │
│ 512001 │      125 │
│    ... |      ... |
└────────┴──────────┘

8192 rows in set. Elapsed: 0.051 sec. Processed 32.77 thousand rows, 360.45 KB (643.75 thousand rows/s., 7.08 MB/s.)

 

skip index 종류도 여러가지가 있어서 요구사항에 맞게 사용할 수 있다.

 

minmax 의 경우 차지하는 용량도 많지 않고 가장 간단하게 구현할 수 있는 방식이라고 한다. 최소랑 최대만 확인해주면 되기 때문에 부담이 적은듯하다. 블룸필터 같은거 쓰려면 용량도 그렇고 자료구조도 복잡해질 것 같긴 하다. 

 

예시에서는 vix 타입의 skip index 를 사용했는데 문서상에는 vix 에 대한 설명은 나와있지 않아서 당황스럽다;

 

Best Practice

MySQL, PG 처럼 row 기반 DB 에서 index 는 읽어야 하는 값을 찾아주는 용도로 사용된다. 반면에 Clickhouse 는 granule 단위로 스캔하지 않아도 되는 범위를 찾는데 효과가 있다.

 

timestamp 처럼 row 별로 저장되는 값이 다른 경우 SKIP 할 수 있는 데이터가 많으나 gender 처럼 비슷한 데이터가 전반에 분포되어 있는 경우 SKIP 하는 granule 이 별로 없다 (block 단위로 male, female 값이 모두 존재할 것이기 때문에)

 

즉 데이터가 고르게 분포되어 있는 경우에는 index의 효과를 보기 어렵다고 볼 수 없다. 아래 그림처럼 대부분의 데이터에 1001 값이 존재한다면 인덱스를 걸어도 모든 granule 을 읽게 되기 때문에 효과를 보기 어렵다

 

clickhouse 속도를 올리기 위해 index 를 사용하는 유즈케이스의 경우 대부분은 잘못사용하는 경우라고 한다. 그래서 대안요소들을 먼저 조사하고 pk 를 바꿔보고 projection 이나 materialized view 까지 써본 다음에 최종적으로 사용하는게 좋다.