성긴 기본 키 — 정렬 키 순서가 무엇을 건너뛰게 하나

한 줄 요약

MergeTree 의 기본 인덱스는 행마다가 아니라 그래뉼(기본 8192행)마다 첫 행의 키 값 하나만 적는다. 그래서 인덱스가 할 수 있는 일은 "이 그래뉼에는 찾는 값이 있을 수 없다" 를 가려내는 것뿐이고, 얼마나 가려내느냐는 정렬 키의 열 순서와 앞 열의 카디널리티(값의 종류 수) 가 정한다.

왜 이게 필요했나

행 지향 DB 의 B-트리는 행 하나하나를 가리킨다. 수십억 행이면 인덱스가 메모리에 들어가지 않고, 분석 쿼리는 어차피 수백만 행을 훑으니 행 하나를 콕 집는 능력은 별 쓸모가 없다. ClickHouse 는 반대로 갔다. 디스크의 행을 정렬 키 순서로 늘어놓고, 8192행 묶음마다 첫 키 값만 적는다. 200만 행 표의 인덱스가 키 값 245개 — 압축된 파일로 수백 바이트 — 라서 늘 메모리에 둘 수 있다.

대가는 정밀도다. 인덱스가 고르는 단위가 그래뉼이라, 찾는 행이 하나여도 8192행을 읽는다. 그리고 인덱스가 정렬 순서 그 자체이므로 표 하나에 정렬 순서는 하나뿐이다. 어떤 쿼리는 빨라지고 어떤 쿼리는 전혀 도움을 못 받는다. 이 모듈은 그 "어떤" 을 숫자로 가르는 법을 다룬다. 앞 모듈에서 본 "정렬 키로 거를 때만 건너뛴다" 를 한 단계 더 들어가, 두 번째 키 열로 거를 때 무슨 일이 일어나는지 본다.

어떻게 동작하나

ORDER BY (site, user_id) 인 표는 site 로 먼저 정렬하고, 같은 site 안에서 user_id 로 정렬한다. 사이트가 다섯 개라면 디스크에는 사이트 덩어리 다섯 개가 차례로 놓인다. 여기에 EXPLAIN indexes = 1 을 붙이면 PrimaryKey 단계가 몇 그래뉼을 골랐는지 알려 준다.

PrimaryKey  Keys: site  Condition: (site in ['docs.example', 'docs.example'])  Parts: 1/1  Granules: 50/245  Search Algorithm: binary search

첫 키 열로 거르면 이진 탐색이다. 인덱스가 첫 열 기준으로 정렬돼 있으니 docs 가 시작하는 마크와 끝나는 마크를 바로 찾는다. 두 번째 열 user_id 로만 거르면 이야기가 달라진다. user_id 는 사이트 덩어리마다 0부터 다시 시작하므로 전체로는 정렬돼 있지 않다. 이때 ClickHouse 는 generic exclusion search 를 쓴다. 이웃한 두 마크의 키 값을 보고, 그 사이에서 앞 열 값이 바뀌지 않는다면 뒤 열의 범위가 정해지므로 "이 구간에 4242 는 없다" 를 판정할 수 있다. 앞 열이 바뀌는 구간은 판정할 수 없어 남긴다. 공식 가이드의 결론이 이것이다 — 이 알고리즘은 앞 키 열의 카디널리티가 낮을 때 효과적이다. 실습 파드에서 user_id = 4242 는 245개 중 9개를 골랐다.

키 순서를 뒤집은 ORDER BY (user_id, site) 표에서는 결과도 뒤집힌다. user_id 는 이제 첫 열이라 1개 그래뉼로 끝난다. 그런데 site 로 거르면 245/245 — 전부 읽는다. 사용자 5만 명이 그래뉼 245개에 퍼져 있어 그래뉼 하나에 약 200명이 들어 있고, 이웃한 마크 사이에서 앞 열 user_id 가 거의 늘 바뀌므로 어느 구간도 제외하지 못한다. 앞 열의 카디널리티가 높으면 뒤 열은 인덱스로서 쓸모가 없다.

그래뉼 크기도 손잡이다. 표 설정 index_granularity = 1024 로 만들면 마크가 246개에서 1955개로 늘고, user_id = 4242 를 찾으며 읽는 행은 73,728 에서 9,216 으로 줄었다. 대신 인덱스 파일(system.parts 의 primary_key_size)이 커진다. 인덱스를 메모리에 두는 설계이므로 그래뉼을 잘게 쪼갤수록 메모리를 더 쓴다.

마지막으로 PRIMARY KEY 와 ORDER BY 는 다를 수 있다. 정렬은 (site, user_id, ts) 로 하되 인덱스에는 (site, user_id) 만 적게 할 수 있다. MergeTree 문서의 규칙은 하나 — 기본 키가 정렬 키의 앞부분이어야 한다. 앞부분이 아닌 것을 적으면 표가 만들어지지 않는다("Primary key must be a prefix of the sorting key"). 실습 파드에서 같은 정렬의 두 표를 비교하니 기본 키 파일이 1,620 바이트에서 647 바이트로 줄었다. 거를 때 쓰지 않는 뒤쪽 열은 정렬에만 참여하고 인덱스에는 들어가지 않아도 된다.

한 가지 함정. 26.8 은 쿼리 조건 캐시가 기본으로 켜져 있어, 같은 WHERE 를 두 번째로 돌리면 "지난번에 맞는 행이 없던 그래뉼" 을 건너뛴다. user_id = 4242 쿼리가 처음엔 73,728행, 두 번째엔 40,960행을 읽었다. 인덱스의 능력을 재려면 --use_query_condition_cache 0 을 주고 잰다.

현장에서 만나는 모습

"id 로 정렬했는데 왜 사이트별 보고서가 느리냐" 는 질문을 자주 받는다. 답은 대개 키 순서다. 쿼리의 WHERE 에 거의 늘 들어가는 열, 그중에서도 종류가 적은 열을 앞에 두고, 범위로 자주 자르는 시간 열을 그 뒤에 둔다. 하루치 사이트 보고서라면 (site, ts) 가 (site, user_id) 보다 읽는 행을 몇 분의 일로 줄인다 — 이 모듈 실습의 마지막 단계가 이것이다.

두 번째로 흔한 것은 "모든 쿼리를 다 빠르게" 하려고 종류가 많은 열부터 키에 늘어놓는 것이다. 뒤쪽 열일수록 앞 열들이 이웃한 마크 사이에서 같은 값으로 머물러야 쓸모가 있다 — 위의 generic exclusion search 규칙이 열마다 겹쳐진다. 거를 때 쓰지 않는 뒤쪽 열은 인덱스에서 빼 PRIMARY KEY 를 앞부분으로 줄이고, 다른 정렬이 꼭 필요한 쿼리는 뒤 모듈의 프로젝션이나 구체화 뷰로 푼다.

공식 문서(Choosing a primary key)는 정렬 키를 표를 만들 때 정해야 하고 나중에 덧붙일 수 없다고 적는다. 정렬을 바꾸려면 새 표를 만들어 옮겨야 하므로, 처음 만들 때 대표 쿼리 몇 개의 EXPLAIN 을 먼저 보는 것이 가장 싸다.

다음 실습에서 할 것

sparse.hits 를 (site, user_id) 로 만들어 200만 행을 넣고 파트를 하나로 합친다. site 로 거를 때와 user_id 로만 거를 때의 EXPLAIN 을 저장해 고른 그래뉼과 검색 방식을 옮기고, 키 순서를 뒤집은 표에서 두 쿼리의 rows_read 를 잰다. 그래뉼을 1024행으로 줄인 표의 마크 수, PRIMARY KEY 를 따로 둔 표의 인덱스 크기를 비교한 뒤, 하루치 사이트 보고서 쿼리에 맞는 정렬 키를 골라 읽는 행을 4분의 1 이하로 줄인다.