희소 기본 인덱스

희소 기본 인덱스 (Sparse Primary Indexes)

이 가이드에서는 ClickHouse 인덱싱을 깊이 있게 다뤄 볼게요. 다음을 자세히 설명하고 논의할 거예요.

• ClickHouse의 인덱싱이 전통적인 관계형 데이터베이스 관리 시스템과 어떻게 다른지
• ClickHouse가 테이블의 희소 기본 인덱스(sparse primary index)를 어떻게 구축하고 사용하는지
• ClickHouse에서 인덱싱의 모범 사례가 무엇인지

출처: 문서

본문

이 가이드의 모든 ClickHouse SQL 문과 쿼리는 여러분 자신의 머신에서 직접 실행할 수 있어요. ClickHouse 설치와 시작 지침은 Quick Start을 참고하세요. 이 가이드는 ClickHouse 희소 기본 인덱스에 초점을 맞춰요. ClickHouse 보조 데이터 스킵 인덱스(secondary data skipping indexes)는 Tutorial을 참고하세요.

데이터셋

이 가이드 전반에서 익명화된 샘플 웹 트래픽 데이터셋을 사용할게요.

• 샘플 데이터셋에서 887만 행(이벤트)의 부분집합을 사용할게요.
• 비압축 데이터 크기는 887만 이벤트, 약 700 MB예요. ClickHouse에 저장하면 200 MB로 압축돼요.
• 부분집합의 각 행은 특정 시간(EventTime 컬럼)에 URL(URL 컬럼)을 클릭한 인터넷 사용자(UserID 컬럼)를 나타내는 세 개의 컬럼을 포함해요.

이 세 개의 컬럼으로 이미 몇 가지 전형적인 웹 분석 쿼리를 만들 수 있어요.

• "특정 사용자가 가장 많이 클릭한 상위 10개 URL은 무엇인가?"
• "특정 URL을 가장 자주 클릭한 상위 10명의 사용자는 누구인가?"
• "사용자가 특정 URL을 클릭하는 가장 인기 있는 시간(예: 요일)은 언제인가?"

테스트 머신

이 문서의 모든 런타임 수치는 Apple M1 Pro 칩과 16GB RAM이 있는 MacBook Pro에서 로컬로 ClickHouse 22.2.1을 실행한 것에 기반해요.

전체 테이블 스캔 (A full table scan)

기본 키 없이 우리 데이터셋에 대해 쿼리가 어떻게 실행되는지 보기 위해, 다음 SQL DDL 문을 실행해 (MergeTree 테이블 엔진으로) 테이블을 만들어요.

CREATE TABLE hits_NoPrimaryKey
(
    `UserID` UInt32,
    `URL` String,
    `EventTime` DateTime
)
ENGINE = MergeTree
PRIMARY KEY tuple();

다음으로 다음 SQL insert 문으로 hits 데이터셋의 부분집합을 테이블에 삽입해요. 이것은 clickhouse.com에 원격으로 호스팅된 전체 데이터셋의 부분집합을 적재하기 위해 URL 테이블 함수를 사용해요.

INSERT INTO hits_NoPrimaryKey SELECT
   intHash32(UserID) AS UserID,
   URL,
   EventTime
FROM url('https://datasets.clickhouse.com/hits/tsv/hits_v1.tsv.xz', 'TSV', 'WatchID UInt64,  JavaEnable UInt8,  Title String,  GoodEvent Int16,  EventTime DateTime,  EventDate Date,  CounterID UInt32,  ClientIP UInt32,  ClientIP6 FixedString(16),  RegionID UInt32,  UserID UInt64,  CounterClass Int8,  OS UInt8,  UserAgent UInt8,  URL String,  Referer String,  URLDomain String,  RefererDomain String,  Refresh UInt8,  IsRobot UInt8,  RefererCategories Array(UInt16),  URLCategories Array(UInt16), URLRegions Array(UInt32),  RefererRegions Array(UInt32),  ResolutionWidth UInt16,  ResolutionHeight UInt16,  ResolutionDepth UInt8,  FlashMajor UInt8, FlashMinor UInt8,  FlashMinor2 String,  NetMajor UInt8,  NetMinor UInt8, UserAgentMajor UInt16,  UserAgentMinor FixedString(2),  CookieEnable UInt8, JavascriptEnable UInt8,  IsMobile UInt8,  MobilePhone UInt8,  MobilePhoneModel String,  Params String,  IPNetworkID UInt32,  TraficSourceID Int8, SearchEngineID UInt16,  SearchPhrase String,  AdvEngineID UInt8,  IsArtifical UInt8,  WindowClientWidth UInt16,  WindowClientHeight UInt16,  ClientTimeZone Int16,  ClientEventTime DateTime,  SilverlightVersion1 UInt8, SilverlightVersion2 UInt8,  SilverlightVersion3 UInt32,  SilverlightVersion4 UInt16,  PageCharset String,  CodeVersion UInt32,  IsLink UInt8,  IsDownload UInt8,  IsNotBounce UInt8,  FUniqID UInt64,  HID UInt32,  IsOldCounter UInt8, IsEvent UInt8,  IsParameter UInt8,  DontCountHits UInt8,  WithHash UInt8, HitColor FixedString(1),  UTCEventTime DateTime,  Age UInt8,  Sex UInt8,  Income UInt8,  Interests UInt16,  Robotness UInt8,  GeneralInterests Array(UInt16), RemoteIP UInt32,  RemoteIP6 FixedString(16),  WindowName Int32,  OpenerName Int32,  HistoryLength Int16,  BrowserLanguage FixedString(2),  BrowserCountry FixedString(2),  SocialNetwork String,  SocialAction String,  HTTPError UInt16, SendTiming Int32,  DNSTiming Int32,  ConnectTiming Int32,  ResponseStartTiming Int32,  ResponseEndTiming Int32,  FetchTiming Int32,  RedirectTiming Int32, DOMInteractiveTiming Int32,  DOMContentLoadedTiming Int32,  DOMCompleteTiming Int32,  LoadEventStartTiming Int32,  LoadEventEndTiming Int32, NSToDOMContentLoadedTiming Int32,  FirstPaintTiming Int32,  RedirectCount Int8, SocialSourceNetworkID UInt8,  SocialSourcePage String,  ParamPrice Int64, ParamOrderID String,  ParamCurrency FixedString(3),  ParamCurrencyID UInt16, GoalsReached Array(UInt32),  OpenstatServiceName String,  OpenstatCampaignID String,  OpenstatAdID String,  OpenstatSourceID String,  UTMSource String, UTMMedium String,  UTMCampaign String,  UTMContent String,  UTMTerm String, FromTag String,  HasGCLID UInt8,  RefererHash UInt64,  URLHash UInt64,  CLID UInt32,  YCLID UInt64,  ShareService String,  ShareURL String,  ShareTitle String,  ParsedParams Nested(Key1 String,  Key2 String, Key3 String, Key4 String, Key5 String,  ValueDouble Float64),  IslandID FixedString(16),  RequestNum UInt32,  RequestTry UInt8')
WHERE URL != '';

응답은:

Ok.

0 rows in set. Elapsed: 145.993 sec. Processed 8.87 million rows, 18.40 GB (60.78 thousand rows/s., 126.06 MB/s.)

ClickHouse 클라이언트의 결과 출력은 위 문이 테이블에 887만 행을 삽입했음을 보여줘요. 마지막으로 가이드 후반부의 논의를 단순화하고 다이어그램과 결과를 재현 가능하게 만들기 위해 FINAL 키워드로 테이블을 optimize 해요.

OPTIMIZE TABLE hits_NoPrimaryKey FINAL;

일반적으로 데이터 적재 직후 테이블을 optimize하는 것은 필요하지도 권장되지도 않아요. 이 예시에서 왜 필요한지는 나중에 분명해질 거예요. 이제 첫 번째 웹 분석 쿼리를 실행할게요. 다음은 UserID 749927693인 인터넷 사용자의 가장 많이 클릭된 상위 10개 URL을 계산해요.

SELECT URL, count(URL) AS Count
FROM hits_NoPrimaryKey
WHERE UserID = 749927693
GROUP BY URL
ORDER BY Count DESC
LIMIT 10;

응답은:

┌─URL────────────────────────────┬─Count─┐
│ http://auto.ru/chatay-barana.. │   170 │
│ http://auto.ru/chatay-id=371...│    52 │
│ http://public_search           │    45 │
│ http://kovrik-medvedevushku-...│    36 │
│ http://forumal                 │    33 │
│ http://korablitz.ru/L_1OFFER...│    14 │
│ http://auto.ru/chatay-id=371...│    14 │
│ http://auto.ru/chatay-john-D...│    13 │
│ http://auto.ru/chatay-john-D...│    10 │
│ http://wot/html?page/23600_m...│     9 │
└────────────────────────────────┴───────┘

10 rows in set. Elapsed: 0.022 sec.
Processed 8.87 million rows,
70.45 MB (398.53 million rows/s., 3.17 GB/s.)

ClickHouse 클라이언트의 결과 출력은 ClickHouse가 전체 테이블 스캔을 실행했음을 나타내요! 테이블의 887만 행 각각이 ClickHouse로 스트리밍됐어요. 이것은 확장되지 않아요. 이것을 (훨씬) 더 효율적으로, (훨씬) 더 빠르게 만들려면 적절한 기본 키를 가진 테이블을 사용해야 해요. 그러면 ClickHouse가 (기본 키의 컬럼을 기반으로) 자동으로 희소 기본 인덱스를 만들고, 이를 사용해 예시 쿼리의 실행을 크게 가속화할 수 있어요.

ClickHouse 인덱스 설계

대규모 데이터를 위한 인덱스 설계

전통적인 관계형 데이터베이스 관리 시스템에서 기본 인덱스는 테이블 행당 하나의 항목을 포함할 거예요. 이 경우 우리 데이터셋의 기본 인덱스는 887만 개 항목을 포함하게 돼요. 이런 인덱스는 특정 행의 빠른 위치 확인을 허용해서 조회 쿼리와 지점 업데이트에 높은 효율을 제공해요. B(+)-Tree 데이터 구조에서 항목을 검색하는 것은 평균 시간 복잡도 O(log n)을 가져요. 더 정확히는 log_b n = log_2 n / log_2 b이며, 여기서 b는 B(+)-Tree의 분기 인자(branching factor), n은 인덱스된 행 수예요. b가 일반적으로 수백에서 수천 사이이므로 B(+)-Tree는 매우 얕은 구조이고, 레코드를 찾는 데 필요한 디스크 탐색이 적어요. 887만 행과 분기 인자 1000에서 평균 2.3회의 디스크 탐색이 필요해요. 이 기능에는 비용이 따르죠: 추가 디스크와 메모리 오버헤드, 테이블에 새 행과 인덱스에 항목을 추가할 때의 더 높은 삽입 비용, 때로는 B-Tree의 재균형이 필요해요. B-Tree 인덱스와 관련된 도전을 고려해, ClickHouse의 테이블 엔진은 다른 접근을 사용해요. ClickHouse MergeTree 엔진 계열은 대규모 데이터 볼륨을 처리하도록 설계되고 최적화됐어요. 이 테이블들은 초당 수백만 개의 행 삽입을 받고 매우 큰(수백 PB) 데이터 볼륨을 저장하도록 설계됐어요. 데이터는 파트별로 테이블에 빠르게 기록되며, 백그라운드에서 파트를 병합하는 규칙이 적용돼요. ClickHouse에서 각 파트는 자체 기본 인덱스를 가져요. 파트가 병합되면 병합된 파트의 기본 인덱스도 병합돼요. ClickHouse가 설계된 매우 큰 규모에서는 디스크와 메모리 효율이 매우 중요해요. 따라서 모든 행을 인덱스하는 대신, 파트의 기본 인덱스는 행 그룹(그래뉼, 'granule'이라 함)당 하나의 인덱스 항목('mark'라고 함)을 가져요. 이 기법을 희소 인덱스(sparse index) 라고 해요. 희소 인덱싱이 가능한 이유는 ClickHouse가 파트의 행을 기본 키 컬럼 순서로 디스크에 저장하기 때문이에요. (B-Tree 기반 인덱스처럼) 단일 행을 직접 찾는 대신, 희소 기본 인덱스는 (인덱스 항목에 대한 이진 탐색을 통해) 쿼리와 일치할 수 있는 행 그룹을 빠르게 식별하게 해줘요. 찾은 잠재적으로 일치하는 행 그룹(그래뉼)은 그런 다음 병렬로 ClickHouse 엔진으로 스트리밍되어 일치 항목을 찾아요. 이 인덱스 설계는 기본 인덱스를 작게 유지하며(완전히 메인 메모리에 맞아야 하고 맞을 수 있어요), 쿼리 실행 시간을 특히 데이터 분석 사용 사례에서 전형적인 범위 쿼리에서 크게 가속화해요. 아래에서 ClickHouse가 희소 기본 인덱스를 구축하고 사용하는 방법을 자세히 설명할게요. 기사의 후반부에서는 인덱스를 만드는 데 사용되는 테이블 컬럼(기본 키 컬럼)을 선택·제거·순서화하는 몇 가지 모범 사례를 논의할 거예요.

기본 키가 있는 테이블

키 컬럼 UserID와 URL을 가진 복합 기본 키(compound primary key)가 있는 테이블을 만들어요.

CREATE TABLE hits_UserID_URL
(
    `UserID` UInt32,
    `URL` String,
    `EventTime` DateTime
)
ENGINE = MergeTree
PRIMARY KEY (UserID, URL)
ORDER BY (UserID, URL, EventTime)
SETTINGS index_granularity_bytes = 0, compress_primary_key = 0;

DDL 문 상세 가이드 후반부의 논의를 단순화하고 다이어그램과 결과를 재현 가능하게 만들기 위해 DDL 문은:

• ORDER BY 절을 통해 테이블의 복합 정렬 키를 지정해요.
• 다음 설정을 통해 기본 인덱스가 가질 인덱스 항목 수를 명시적으로 제어해요.
  • index_granularity: 기본값 8192로 명시적으로 설정. 이것은 8192행마다 기본 인덱스가 하나의 인덱스 항목을 가진다는 뜻이에요. 예를 들어 테이블이 16384행을 포함하면 인덱스는 두 개의 인덱스 항목을 가져요.
  • index_granularity_bytes: 적응형 인덱스 그래뉼러리티(adaptive index granularity)를 끄기 위해 0으로 설정. 적응형 인덱스 그래뉼러리티는 다음 중 하나가 참일 때 ClickHouse가 n행 그룹에 대해 자동으로 하나의 인덱스 항목을 만든다는 뜻이에요.
    • n이 8192보다 작고 그 n행의 결합된 행 데이터 크기가 10 MB(index_granularity_bytes의 기본값)보다 크거나 같을 때.
    • n행의 결합된 행 데이터 크기가 10 MB보다 작지만 n이 8192일 때.
  • compress_primary_key: 기본 인덱스의 압축을 끄기 위해 0으로 설정. 이것은 나중에 그 내용을 선택적으로 검사할 수 있게 해줘요.

위 DDL 문의 기본 키는 지정된 두 키 컬럼을 기반으로 기본 인덱스의 생성을 일으켜요. 다음으로 데이터를 삽입해요.

INSERT INTO hits_UserID_URL SELECT
   intHash32(UserID) AS UserID,
   URL,
   EventTime
FROM url('https://datasets.clickhouse.com/hits/tsv/hits_v1.tsv.xz', 'TSV', 'WatchID UInt64,  JavaEnable UInt8,  Title String,  GoodEvent Int16,  EventTime DateTime,  EventDate Date,  CounterID UInt32,  ClientIP UInt32,  ClientIP6 FixedString(16),  RegionID UInt32,  UserID UInt64,  CounterClass Int8,  OS UInt8,  UserAgent UInt8,  URL String,  Referer String,  URLDomain String,  RefererDomain String,  Refresh UInt8,  IsRobot UInt8,  RefererCategories Array(UInt16),  URLCategories Array(UInt16), URLRegions Array(UInt32),  RefererRegions Array(UInt32),  ResolutionWidth UInt16,  ResolutionHeight UInt16,  ResolutionDepth UInt8,  FlashMajor UInt8, FlashMinor UInt8,  FlashMinor2 String,  NetMajor UInt8,  NetMinor UInt8, UserAgentMajor UInt16,  UserAgentMinor FixedString(2),  CookieEnable UInt8, JavascriptEnable UInt8,  IsMobile UInt8,  MobilePhone UInt8,  MobilePhoneModel String,  Params String,  IPNetworkID UInt32,  TraficSourceID Int8, SearchEngineID UInt16,  SearchPhrase String,  AdvEngineID UInt8,  IsArtifical UInt8,  WindowClientWidth UInt16,  WindowClientHeight UInt16,  ClientTimeZone Int16,  ClientEventTime DateTime,  SilverlightVersion1 UInt8, SilverlightVersion2 UInt8,  SilverlightVersion3 UInt32,  SilverlightVersion4 UInt16,  PageCharset String,  CodeVersion UInt32,  IsLink UInt8,  IsDownload UInt8,  IsNotBounce UInt8,  FUniqID UInt64,  HID UInt32,  IsOldCounter UInt8, IsEvent UInt8,  IsParameter UInt8,  DontCountHits UInt8,  WithHash UInt8, HitColor FixedString(1),  UTCEventTime DateTime,  Age UInt8,  Sex UInt8,  Income UInt8,  Interests UInt16,  Robotness UInt8,  GeneralInterests Array(UInt16), RemoteIP UInt32,  RemoteIP6 FixedString(16),  WindowName Int32,  OpenerName Int32,  HistoryLength Int16,  BrowserLanguage FixedString(2),  BrowserCountry FixedString(2),  SocialNetwork String,  SocialAction String,  HTTPError UInt16, SendTiming Int32,  DNSTiming Int32,  ConnectTiming Int32,  ResponseStartTiming Int32,  ResponseEndTiming Int32,  FetchTiming Int32,  RedirectTiming Int32, DOMInteractiveTiming Int32,  DOMContentLoadedTiming Int32,  DOMCompleteTiming Int32,  LoadEventStartTiming Int32,  LoadEventEndTiming Int32, NSToDOMContentLoadedTiming Int32,  FirstPaintTiming Int32,  RedirectCount Int8, SocialSourceNetworkID UInt8,  SocialSourcePage String,  ParamPrice Int64, ParamOrderID String,  ParamCurrency FixedString(3),  ParamCurrencyID UInt16, GoalsReached Array(UInt32),  OpenstatServiceName String,  OpenstatCampaignID String,  OpenstatAdID String,  OpenstatSourceID String,  UTMSource String, UTMMedium String,  UTMCampaign String,  UTMContent String,  UTMTerm String, FromTag String,  HasGCLID UInt8,  RefererHash UInt64,  URLHash UInt64,  CLID UInt32,  YCLID UInt64,  ShareService String,  ShareURL String,  ShareTitle String,  ParsedParams Nested(Key1 String,  Key2 String, Key3 String, Key4 String, Key5 String,  ValueDouble Float64),  IslandID FixedString(16),  RequestNum UInt32,  RequestTry UInt8')
WHERE URL != '';

응답은 다음과 같아요.

0 rows in set. Elapsed: 149.432 sec. Processed 8.87 million rows, 18.40 GB (59.38 thousand rows/s., 123.16 MB/s.)

그리고 테이블을 optimize해요.

OPTIMIZE TABLE hits_UserID_URL FINAL;

다음 쿼리로 테이블에 대한 메타데이터를 얻을 수 있어요.

SELECT
    part_type,
    path,
    formatReadableQuantity(rows) AS rows,
    formatReadableSize(data_uncompressed_bytes) AS data_uncompressed_bytes,
    formatReadableSize(data_compressed_bytes) AS data_compressed_bytes,
    formatReadableSize(primary_key_bytes_in_memory) AS primary_key_bytes_in_memory,
    marks,
    formatReadableSize(bytes_on_disk) AS bytes_on_disk
FROM system.parts
WHERE (table = 'hits_UserID_URL') AND (active = 1)
FORMAT Vertical;

응답은:

part_type:                   Wide
path:                        ./store/d9f/d9f36a1a-d2e6-46d4-8fb5-ffe9ad0d5aed/all_1_9_2/
rows:                        8.87 million
data_uncompressed_bytes:     733.28 MiB
data_compressed_bytes:       206.94 MiB
primary_key_bytes_in_memory: 96.93 KiB
marks:                       1083
bytes_on_disk:               207.07 MiB

1 rows in set. Elapsed: 0.003 sec.

ClickHouse 클라이언트의 출력은 다음을 보여줘요.

• 테이블의 데이터는 디스크의 특정 디렉터리에 wide 포맷으로 저장되어, 그 디렉터리 안에 테이블 컬럼마다 하나의 데이터 파일(및 하나의 mark 파일)이 있을 것임을 의미해요.
• 테이블은 887만 행을 가져요.
• 모든 행의 비압축 데이터 크기는 함께 733.28 MB예요.
• 모든 행의 디스크 압축 크기는 함께 206.94 MB예요.
• 테이블은 1083개 항목('mark'라고 함)을 가진 기본 인덱스를 가지며, 인덱스 크기는 96.93 KB예요.
• 총합적으로 테이블의 데이터·mark 파일·기본 인덱스 파일이 디스크에서 함께 207.07 MB를 차지해요.

데이터는 기본 키 컬럼 순서로 디스크에 저장된다

위에서 만든 테이블은

• 복합 기본 키 (UserID, URL)과

• 복합 정렬 키 (UserID, URL, EventTime)을 가져요.

• 정렬 키만 지정했다면 기본 키는 암시적으로 정렬 키와 동일하게 정의돼요.

• 메모리 효율을 위해 우리 쿼리가 필터링하는 컬럼만 포함하는 기본 키를 명시적으로 지정했어요. 기본 키 기반의 기본 인덱스는 완전히 메인 메모리에 적재돼요.

• 가이드 다이어그램의 일관성과 압축 비율 극대화를 위해 테이블의 모든 컬럼을 포함하는 별도의 정렬 키를 정의했어요 (컬럼에서 유사한 데이터가 예를 들어 정렬을 통해 서로 가까이 배치되면 더 잘 압축되기 때문이에요).

• 기본 키와 정렬 키를 모두 지정했다면 기본 키는 정렬 키의 접두사여야 해요.

삽입된 행은 기본 키 컬럼(및 정렬 키의 추가 EventTime 컬럼)에 의해 사전식(오름차순) 순서로 디스크에 저장돼요. ClickHouse는 동일한 기본 키 컬럼 값을 가진 여러 행의 삽입을 허용해요. 이 경우(아래 다이어그램의 행 1과 행 2 참조) 최종 순서는 지정된 정렬 키, 따라서 EventTime 컬럼의 값에 의해 결정돼요. ClickHouse는 컬럼 지향 데이터베이스 관리 시스템이에요. 아래 다이어그램에 표시된 대로

• 디스크 표현을 위해 테이블 컬럼마다 단일 데이터 파일(*.bin)이 있으며, 그 컬럼의 모든 값이 압축 포맷으로 저장되고,
• 887만 행은 기본 키 컬럼(및 추가 정렬 키 컬럼) 순서로 사전식 오름차순으로 디스크에 저장돼요. 즉 이 경우
  • 첫째로 UserID,
  • 그런 다음 URL,
  • 마지막으로 EventTime 순서로 저장돼요:

UserID.bin, URL.bin, EventTime.bin은 UserID, URL, EventTime 컬럼의 값이 저장되는 디스크의 데이터 파일이에요.

• 기본 키가 디스크의 행 사전식 순서를 정의하므로 테이블은 하나의 기본 키만 가질 수 있어요.
• 로깅 메시지에도 사용되는 ClickHouse 내부 행 번호 체계에 맞추기 위해 0부터 행 번호를 매기고 있어요.

데이터는 병렬 데이터 처리를 위해 그래뉼로 구성된다

데이터 처리 목적으로 테이블의 컬럼 값들은 논리적으로 그래뉼(granule)로 나뉘어요. 그래뉼은 데이터 처리를 위해 ClickHouse로 스트리밍되는 가장 작은 분할할 수 없는 데이터셋이에요. 이것은 개별 행을 읽는 대신, ClickHouse가 항상 (스트리밍 방식으로 그리고 병렬로) 전체 행 그룹(그래뉼)을 읽는다는 뜻이에요. 컬럼 값은 그래뉼 안에 물리적으로 저장되지 않아요. 그래뉼은 쿼리 처리를 위한 컬럼 값의 논리적 구성일 뿐이에요. 다음 다이어그램은 테이블의 887만 행(의 컬럼 값)이 어떻게 1083개의 그래뉼로 구성되는지 보여줘요. 이것은 테이블의 DDL 문에 index_granularity 설정(기본값 8192로 설정)이 포함된 결과예요. (디스크의 물리적 순서 기준) 처음 8192행(의 컬럼 값)은 논리적으로 그래뉼 0에 속하고, 그 다음 8192행(의 컬럼 값)은 그래뉼 1에 속하는 식이에요.

• 마지막 그래뉼(그래뉼 1082)은 8192행보다 적게 "포함"해요.
• 이 가이드 시작 부분의 "DDL 문 상세"에서 적응형 인덱스 그래뉼러리티를 껐다고 언급했어요 (가이드의 논의 단순화를 위해, 그리고 다이어그램과 결과를 재현 가능하게 만들기 위해요). 따라서 예시 테이블의 모든 그래뉼(마지막 것 제외)은 같은 크기를 가져요.
• 적응형 인덱스 그래뉼러리티(인덱스 그래뉼러리티는 기본으로 적응형)가 있는 테이블에서는 행 데이터 크기에 따라 일부 그래뉼의 크기가 8192행보다 작을 수 있어요.
• 기본 키 컬럼(UserID, URL)의 일부 컬럼 값을 주황색으로 표시했어요. 이 주황색 표시 컬럼 값들은 각 그래뉼의 첫 행의 기본 키 컬럼 값이에요. 아래에서 보게 되겠지만, 이 주황색 표시 컬럼 값들이 테이블의 기본 인덱스 항목이 될 거예요.
• 로깅 메시지에도 사용되는 ClickHouse 내부 번호 체계에 맞추기 위해 0부터 그래뉼을 번호 매기고 있어요.

기본 인덱스는 그래뉼마다 하나의 항목을 가진다

기본 인덱스는 위 다이어그램에 표시된 그래뉼을 기반으로 만들어져요. 이 인덱스는 0부터 시작하는 소위 숫자 인덱스 mark를 포함하는 비압축 평면 배열 파일(primary.idx)이에요. 아래 다이어그램은 인덱스가 각 그래뉼의 각 첫 행에 대한 기본 키 컬럼 값(위 다이어그램에서 주황색으로 표시된 값)을 저장함을 보여줘요. 즉 기본 인덱스는 (기본 키 컬럼이 정의한 물리적 행 순서에 기반한) 테이블의 매 8192번째 행의 기본 키 컬럼 값을 저장해요. 예를 들어

• 첫 인덱스 항목('mark 0')은 위 다이어그램의 그래뉼 0의 첫 행 키 컬럼 값을 저장하고,
• 두 번째 인덱스 항목('mark 1')은 위 다이어그램의 그래뉼 1의 첫 행 키 컬럼 값을 저장하는 식이에요.

전체적으로 인덱스는 887만 행과 1083개의 그래뉼을 가진 테이블에 대해 1083개 항목을 가져요.

• 적응형 인덱스 그래뉼러리티가 있는 테이블에는 마지막 테이블 행의 기본 키 컬럼 값을 기록하는 "최종" 추가 mark 하나가 기본 인덱스에 저장되지만, 우리는 적응형 인덱스 그래뉼러리티를 껐으므로(가이드 논의 단순화를 위해) 예시 테이블의 인덱스는 이 최종 mark를 포함하지 않아요.
• 기본 인덱스 파일은 완전히 메인 메모리에 적재돼요. 파일이 사용 가능한 자유 메모리 공간보다 크면 ClickHouse는 오류를 발생시켜요.

기본 인덱스 내용 검사하기 자체 관리형 ClickHouse 클러스터에서는 file 테이블 함수로 예시 테이블의 기본 인덱스 내용을 검사할 수 있어요. 먼저 실행 중인 클러스터의 노드 user_files_path로 기본 인덱스 파일을 복사해야 해요.

단계 1: 기본 인덱스 파일을 포함하는 part-path 가져오기

 SELECT path FROM system.parts WHERE table = 'hits_UserID_URL' AND active = 1

테스트 머신에서 /Users/tomschreiber/ClickHouse/store/85f/85f4ee68-6e28-4f08-98b1-7d8affa1d88c/all_1_9_4를 반환해요.

단계 2: user_files_path 가져오기 기본 user_files_path는 Linux에서 /var/lib/clickhouse/user_files/이고, Linux에서 변경됐는지 확인할 수 있어요: $ grep user_files_path /etc/clickhouse-server/config.xml 테스트 머신에서 경로는 /Users/tomschreiber/ClickHouse/user_files/예요.

단계 3: 기본 인덱스 파일을 user_files_path로 복사하기

 cp /Users/tomschreiber/ClickHouse/store/85f/85f4ee68-6e28-4f08-98b1-7d8affa1d88c/all_1_9_4/primary.idx /Users/tomschreiber/ClickHouse/user_files/primary-hits_UserID_URL.idx

이제 SQL로 기본 인덱스의 내용을 검사할 수 있어요.

항목 수 가져오기

 SELECT count()
FROM file('primary-hits_UserID_URL.idx', 'RowBinary', 'UserID UInt32, URL String');

1083을 반환해요.

처음 두 개의 인덱스 mark 가져오기

 SELECT UserID, URL
FROM file('primary-hits_UserID_URL.idx', 'RowBinary', 'UserID UInt32, URL String')
LIMIT 0, 2;

다음을 반환해요.

240923, http://showtopics.html%3...
4073710, http://mk.ru&pos=3_0

마지막 인덱스 mark 가져오기

 SELECT UserID, URL FROM file('primary-hits_UserID_URL.idx', 'RowBinary', 'UserID UInt32, URL String')
LIMIT 1082, 1;

다음을 반환해요.

4292714039 │ http://sosyal-mansetleri...

이것은 예시 테이블의 기본 인덱스 내용 다이어그램과 정확히 일치해요. 기본 키 항목이 인덱스 mark라고 불리는 이유는 각 인덱스 항목이 특정 데이터 범위의 시작을 표시하기 때문이에요. 구체적으로 예시 테이블의 경우:

• UserID 인덱스 mark: 기본 인덱스에 저장된 UserID 값들은 오름차순으로 정렬돼요. 위 다이어그램의 'mark 1'은 따라서 그래뉼 1의 모든 테이블 행의 UserID 값들과, 이후 모든 그래뉼의 값들이 4.073.710보다 크거나 같음이 보장됨을 나타내요.

나중에 보게 되겠지만, 이 전역 순서 덕분에 쿼리가 첫 키 컬럼을 필터링할 때 ClickHouse가 첫 키 컬럼의 인덱스 mark에 대해 이진 탐색 알고리즘을 사용할 수 있어요.

• URL 인덱스 mark: 기본 키 컬럼 UserID와 URL의 카디널리티가 상당히 유사하다는 것은, 첫 컬럼 이후의 모든 키 컬럼에 대한 인덱스 mark가 일반적으로 선행 키 컬럼 값이 적어도 현재 그래뉼 내의 모든 테이블 행에 대해 동일하게 유지되는 한에서만 데이터 범위를 나타낸다는 뜻이에요. 예를 들어 위 다이어그램에서 mark 0과 mark 1의 UserID 값이 다르기 때문에, ClickHouse는 그래뉼 0의 모든 테이블 행의 모든 URL 값이 'http://showtopics.html%3...'보다 크거나 같다고 가정할 수 없어요. 그러나 위 다이어그램에서 mark 0과 mark 1의 UserID 값이 같다면(그래뉼 0 내의 모든 테이블 행에 대해 UserID 값이 동일하게 유지된다는 뜻), ClickHouse는 그래뉼 0의 모든 테이블 행의 모든 URL 값이 'http://showtopics.html%3...'보다 크거나 같다고 가정할 수 있었을 거예요. 이것이 쿼리 실행 성능에 미치는 결과는 나중에 더 자세히 논의할게요.

기본 인덱스는 그래뉼 선택에 사용된다

이제 기본 인덱스의 지원으로 쿼리를 실행할 수 있어요. 다음은 UserID 749927693에 대한 가장 많이 클릭된 상위 10개 URL을 계산해요.

SELECT URL, count(URL) AS Count
FROM hits_UserID_URL
WHERE UserID = 749927693
GROUP BY URL
ORDER BY Count DESC
LIMIT 10;

응답은:

┌─URL────────────────────────────┬─Count─┐
│ http://auto.ru/chatay-barana.. │   170 │
│ http://auto.ru/chatay-id=371...│    52 │
│ http://public_search           │    45 │
│ http://kovrik-medvedevushku-...│    36 │
│ http://forumal                 │    33 │
│ http://korablitz.ru/L_1OFFER...│    14 │
│ http://auto.ru/chatay-id=371...│    14 │
│ http://auto.ru/chatay-john-D...│    13 │
│ http://auto.ru/chatay-john-D...│    10 │
│ http://wot/html?page/23600_m...│     9 │
└────────────────────────────────┴───────┘

10 rows in set. Elapsed: 0.005 sec.
Processed 8.19 thousand rows,
740.18 KB (1.53 million rows/s., 138.59 MB/s.)

ClickHouse 클라이언트의 출력은 이제 전체 테이블 스캔 대신 단 8.19천 행만 ClickHouse로 스트리밍됐음을 보여줘요. trace logging이 활성화되어 있다면 ClickHouse 서버 로그 파일은 ClickHouse가 749927693의 UserID 컬럼 값을 가진 행을 포함할 수 있는 그래뉼을 식별하기 위해 1083개의 UserID 인덱스 mark에 대해 이진 탐색을 실행했음을 보여줘요. 이것은 평균 시간 복잡도 O(log2 n)으로 19단계가 필요해요.

...Executor): Key condition: (column 0 in [749927693, 749927693])
...Executor): Running binary search on index range for part all_1_9_2 (1083 marks)
...Executor): Found (LEFT) boundary mark: 176
...Executor): Found (RIGHT) boundary mark: 177
...Executor): Found continuous range in 19 steps
...Executor): Selected 1/1 parts by partition key, 1 parts by primary key,
              1/1083 marks by primary key, 1 marks to read from 1 ranges
...Reading ...approx. 8192 rows starting from 1441792

최근 ClickHouse 버전에서는 Running binary search on index range, Found (LEFT) boundary mark, Found (RIGHT) boundary mark 메시지가 trace가 아니라 test 레벨(가장 높은 상세도)로 기록돼요. 보려면 로그 상세도를 test로 올리세요(예: 클라이언트에서 SET send_logs_level = 'test', 또는 서버 설정에서 <logger><level>test</level></logger>). 위에 표시된 나머지 줄들은 여전히 trace로 기록돼요. 이것은 이 가이드의 모든 이진 탐색 로그 예시에 적용돼요. 위 trace 로그에서 1083개의 기존 mark 중 하나가 쿼리를 만족했음을 볼 수 있어요.

Trace 로그 상세 mark 176이 식별됐고('찾은 왼쪽 경계 mark'는 포함, '찾은 오른쪽 경계 mark'는 배타), 따라서 그래뉼 176의 모든 8192행(행 1.441.792에서 시작 — 이 가이드에서 나중에 볼게요)이 749927693의 UserID 컬럼 값을 가진 실제 행을 찾기 위해 ClickHouse로 스트리밍돼요. 이것은 예시 쿼리에서 EXPLAIN 절을 사용해 재현할 수도 있어요.

EXPLAIN indexes = 1
SELECT URL, count(URL) AS Count
FROM hits_UserID_URL
WHERE UserID = 749927693
GROUP BY URL
ORDER BY Count DESC
LIMIT 10;

응답은 다음과 같아요.

┌─explain───────────────────────────────────────────────────────────────────────────────┐
│ Expression (Projection)                                                               │
│   Limit (preliminary LIMIT (without OFFSET))                                          │
│     Sorting (Sorting for ORDER BY)                                                    │
│       Expression (Before ORDER BY)                                                    │
│         Aggregating                                                                   │
│           Expression (Before GROUP BY)                                                │
│             Filter (WHERE)                                                            │
│               SettingQuotaAndLimits (Set limits and quota after reading from storage) │
│                 ReadFromMergeTree                                                     │
│                 Indexes:                                                              │
│                   PrimaryKey                                                          │
│                     Keys:                                                             │
│                       UserID                                                          │
│                     Condition: (UserID in [749927693, 749927693])                     │
│                     Parts: 1/1                                                        │
│                     Granules: 1/1083                                                  │
└───────────────────────────────────────────────────────────────────────────────────────┘

16 rows in set. Elapsed: 0.003 sec.

클라이언트 출력은 1083개의 그래뉼 중 하나가 749927693의 UserID 컬럼 값을 가진 행을 포함할 가능성이 있는 것으로 선택됐음을 보여줘요. 결론 쿼리가 복합 키의 일부이면서 첫 키 컬럼인 컬럼을 필터링할 때, ClickHouse는 키 컬럼의 인덱스 mark에 대해 이진 탐색 알고리즘을 실행해요.

위에서 논의했듯 ClickHouse는 희소 기본 인덱스를 사용해 (이진 탐색을 통해) 쿼리와 일치할 수 있는 행을 포함할 가능성이 있는 그래뉼을 빠르게 선택해요. 이것은 ClickHouse 쿼리 실행의 첫 번째 단계(그래뉼 선택) 예요. 두 번째 단계(데이터 읽기) 에서 ClickHouse는 선택된 그래뉼을 찾아 모든 행을 ClickHouse 엔진으로 스트리밍해 실제로 쿼리와 일치하는 행을 찾아요. 그 두 번째 단계는 다음 섹션에서 더 자세히 논의할게요.

mark 파일은 그래뉼 찾기에 사용된다

다음 다이어그램은 우리 테이블의 기본 인덱스 파일 일부를 보여줘요. 위에서 논의했듯 인덱스의 1083개 UserID mark에 대한 이진 탐색을 통해 mark 176이 식별됐어요. 그에 대응하는 그래뉼 176은 따라서 749.927.693의 UserID 컬럼 값을 가진 행을 포함할 수 있어요.

그래뉼 선택 상세 위 다이어그램은 mark 176이, 연관된 그래뉼 176의 최소 UserID 값이 749.927.693보다 작고, 다음 mark(mark 177)의 그래뉼 177의 최소 UserID 값이 이 값보다 큰, 첫 인덱스 항목임을 보여줘요. 따라서 mark 176에 대응하는 그래뉼 176만 749.927.693의 UserID 컬럼 값을 가진 행을 포함할 수 있어요. 그래뉼 176의 일부 행이 749.927.693의 UserID 컬럼 값을 포함하는지 확인(또는 부정)하려면, 이 그래뉼에 속한 모든 8192행이 ClickHouse로 스트리밍되어야 해요. 이를 위해 ClickHouse는 그래뉼 176의 물리적 위치를 알아야 해요. ClickHouse에서 우리 테이블의 모든 그래뉼의 물리적 위치는 mark 파일에 저장돼요. 데이터 파일과 유사하게 테이블 컬럼마다 하나의 mark 파일이 있어요. 다음 다이어그램은 테이블의 UserID, URL, EventTime 컬럼에 대한 그래뉼의 물리적 위치를 저장하는 UserID.mrk, URL.mrk, EventTime.mrk 세 개의 mark 파일을 보여줘요. 기본 인덱스가 0부터 시작해 번호가 매겨진 인덱스 mark를 포함하는 비압축 평면 배열 파일(primary.idx)임을 논의했어요. 마찬가지로 mark 파일도 0부터 시작해 번호가 매겨진 mark를 포함하는 비압축 평면 배열 파일(*.mrk)이에요. ClickHouse가 쿼리와 일치할 수 있는 그래뉼의 인덱스 mark를 식별하고 선택하면, 오프셋 형태로 두 위치를 저장하는 마크 파일에서 위치 배열 조회를 수행해 그래뉼의 물리적 위치를 얻을 수 있어요. 특정 컬럼에 대한 각 mark 파일 항목은 두 위치를 저장해요.

• 첫 번째 오프셋('block_offset')은 선택된 그래뉼의 압축 버전을 포함하는 압축 컬럼 데이터 파일의 블록을 찾아요. 이 압축 블록은 잠재적으로 몇 개의 압축 그래뉼을 포함할 수 있어요. 찾은 압축 파일 블록은 읽을 때 메인 메모리로 압축 해제돼요.
• mark 파일의 두 번째 오프셋('granule_offset')은 비압축 블록 데이터 안에서의 그래뉼 위치를 제공해요.

찾은 비압축 그래뉼에 속한 모든 8192행은 추가 처리 위해 ClickHouse로 스트리밍돼요.

• wide 포맷이고 적응형 인덱스 그래뉼러리티가 없는 테이블의 경우 ClickHouse는 위에서 시각화한 것처럼 .mrk mark 파일을 사용하며, 각 항목에 8바이트 길이 주소 두 개를 포함하는 항목들이 있어요. 이 항목들은 모두 같은 크기를 가진 그래뉼의 물리적 위치예요.

인덱스 그래뉼러리티는 기본적으로 적응형이지만, 예시 테이블에서는 적응형 인덱스 그래뉼러리티를 껐어요(가이드 논의 단순화를 위해). 우리 테이블은 데이터 크기가 min_bytes_for_wide_part(자체 관리형 클러스터의 기본 10 MB)보다 크기 때문에 wide 포맷을 사용해요.

• wide 포맷이고 적응형 인덱스 그래뉼러리티가 있는 테이블의 경우 ClickHouse는 .mrk2 mark 파일을 사용하며, .mrk mark 파일과 유사한 항목을 포함하지만 항목당 추가 세 번째 값(현재 항목과 연관된 그래뉼의 행 수)이 있어요.
• compact 포맷 테이블의 경우 ClickHouse는 .mrk3 mark 파일을 사용해요.

왜 mark 파일인가? 기본 인덱스가 인덱스 mark에 대응하는 그래뉼의 물리적 위치를 직접 포함하지 않는 이유는 무엇일까요? ClickHouse가 설계된 매우 큰 규모에서는 디스크와 메모리 효율이 중요하기 때문이에요. 기본 인덱스 파일은 메인 메모리에 맞아야 해요. 우리 예시 쿼리에 대해 ClickHouse는 기본 인덱스를 사용해 쿼리와 일치할 수 있는 행을 포함하는 단일 그래뉼을 선택했어요. 그 하나의 그래뉼에 대해서만 ClickHouse가 추가 처리를 위해 대응하는 행을 스트리밍하기 위해 물리적 위치가 필요해요. 게다가 이 오프셋 정보는 UserID와 URL 컬럼에 대해서만 필요해요. 쿼리에서 사용되지 않는 컬럼(예: EventTime)에는 오프셋 정보가 필요하지 않아요. 우리 샘플 쿼리에 대해 ClickHouse는 UserID 데이터 파일(UserID.bin)의 그래뉼 176에 대한 두 개의 물리적 위치 오프셋과 URL 데이터 파일(URL.bin)의 그래뉼 176에 대한 두 개의 물리적 위치 오프셋만 필요해요. mark 파일이 제공하는 간접성은 세 컬럼 모두의 1083개 그래뉼에 대한 물리적 위치 항목을 기본 인덱스에 직접 저장하는 것을 피하게 해줘요. 따라서 메인 메모리에서 불필요한(잠재적으로 사용되지 않는) 데이터를 피할 수 있어요. 다음 다이어그램과 아래 텍스트는 예시 쿼리에 대해 ClickHouse가 UserID.bin 데이터 파일에서 그래뉼 176을 찾는 방법을 보여줘요. 이 가이드 앞부분에서 ClickHouse가 기본 인덱스 mark 176, 따라서 그래뉼 176을 쿼리와 일치할 수 있는 행을 포함하는 것으로 선택했다고 논의했어요. ClickHouse는 이제 인덱스에서 선택된 mark 번호(176)를 사용해 UserID.mrk mark 파일에서 위치 배열 조회를 수행해 그래뉼 176을 찾기 위한 두 오프셋을 얻어요. 표시된 대로 첫 번째 오프셋은 UserID.bin 데이터 파일 내의 압축 파일 블록을 찾는데, 그 블록이 다시 그래뉼 176의 압축 버전을 포함해요. 찾은 파일 블록이 메인 메모리로 압축 해제되면, mark 파일의 두 번째 오프셋으로 비압축 데이터 안에서 그래뉼 176을 찾을 수 있어요. 예시 쿼리(UserID 749.927.693인 인터넷 사용자의 가장 많이 클릭된 상위 10개 URL)를 실행하려면 ClickHouse는 UserID.bin 데이터 파일과 URL.bin 데이터 파일 모두에서 그래뉼 176을 찾아(모든 값을 스트리밍해)야 해요. 위 다이어그램은 ClickHouse가 UserID.bin 데이터 파일에 대해 그래뉼을 찾는 방법을 보여줘요. 병렬로 ClickHouse는 URL.bin 데이터 파일의 그래뉼 176에 대해서도 동일하게 수행해요. 두 각각의 그래뉼은 정렬되어 ClickHouse 엔진으로 스트리밍되어 추가 처리 — 즉 UserID가 749.927.693인 모든 행에 대해 URL 값을 그룹별로 집계·카운트 — 한 다음, 마지막으로 가장 큰 10개 URL 그룹을 카운트 내림차순으로 출력해요.

여러 기본 인덱스 사용하기

보조 키 컬럼은 (그렇지 않을 수 있지만) 비효율적일 수 있다

쿼리가 복합 키의 일부이면서 첫 키 컬럼인 컬럼을 필터링할 때 ClickHouse는 키 컬럼의 인덱스 mark에 대해 이진 탐색 알고리즘을 실행해요. 하지만 쿼리가 복합 키의 일부이지만 첫 키 컬럼이 아닌 컬럼을 필터링하면 어떻게 될까요? 쿼리가 첫 키 컬럼을 명시적으로 필터링하지 않고 보조 키 컬럼을 필터링하는 시나리오를 논의할게요. 쿼리가 첫 키 컬럼과 첫 이후의 키 컬럼들 모두를 필터링할 때 ClickHouse는 첫 키 컬럼의 인덱스 mark에 대해 이진 탐색을 실행해요.

URL "http://public_search"를 가장 자주 클릭한 상위 10명의 사용자를 계산하는 쿼리를 사용할게요.

SELECT UserID, count(UserID) AS Count
FROM hits_UserID_URL
WHERE URL = 'http://public_search'
GROUP BY UserID
ORDER BY Count DESC
LIMIT 10;

응답은:

┌─────UserID─┬─Count─┐
│ 2459550954 │  3741 │
│ 1084649151 │  2484 │
│  723361875 │   729 │
│ 3087145896 │   695 │
│ 2754931092 │   672 │
│ 1509037307 │   582 │
│ 3085460200 │   573 │
│ 2454360090 │   556 │
│ 3884990840 │   539 │
│  765730816 │   536 │
└────────────┴───────┘

10 rows in set. Elapsed: 0.086 sec.
Processed 8.81 million rows,
799.69 MB (102.11 million rows/s., 9.27 GB/s.)

클라이언트 출력은 URL 컬럼이 복합 기본 키의 일부임에도 불구하고 ClickHouse가 거의 전체 테이블 스캔을 실행했음을 나타내요! ClickHouse는 테이블의 887만 행 중 881만 행을 읽어요. trace_logging이 활성화되어 있다면 ClickHouse 서버 로그 파일은 ClickHouse가 "http://public_search"의 URL 컬럼 값을 가진 행을 포함할 수 있는 그래뉼을 식별하기 위해 1083개의 URL 인덱스 mark에 대해 일반 배제 탐색(generic exclusion search)을 사용했음을 보여줘요.

...Executor): Key condition: (column 1 in ['http://public_search',
                                           'http://public_search'])
...Executor): Used generic exclusion search over index for part all_1_9_2
              with 1537 steps
...Executor): Selected 1/1 parts by partition key, 1 parts by primary key,
              1076/1083 marks by primary key, 1076 marks to read from 5 ranges
...Executor): Reading approx. 8814592 rows with 10 streams

위 샘플 trace 로그에서 1083개 그래뉼 중 1076개((marks 통해))가 일치하는 URL 값을 포함할 가능성이 있는 것으로 선택됐음을 볼 수 있어요. 이것은 10개 스트림을 사용해 (병렬로) ClickHouse 엔진으로 881만 행이 스트리밍되어, 실제로 "http://public_search"의 URL 값이 포함된 행을 식별하도록 해요. 그러나 나중에 보게 되겠지만 선택된 1076개 그래뉼 중 단 39개만 실제로 일치하는 행을 포함해요. 복합 기본 키(UserID, URL) 기반의 기본 인덱스는 특정 UserID 값의 행을 필터링하는 쿼리를 가속화하는 데 매우 유용했지만, 특정 URL 값의 행을 필터링하는 쿼리를 가속화하는 데는 상당한 도움을 주지 못해요. 그 이유는 URL 컬럼이 첫 키 컬럼이 아니므로 ClickHouse가 URL 컬럼의 인덱스 mark에 대해 (이진 탐색 대신) 일반 배제 탐색 알고리즘을 사용하기 때문이며, 그 알고리즘의 효율성은 URL 컬럼과 그 선행 키 컬럼 UserID 사이의 카디널리티 차이에 의존하기 때문이에요. 이를 설명하기 위해 일반 배제 탐색이 어떻게 동작하는지 몇 가지 상세를 제공할게요.

일반 배제 탐색 알고리즘

다음은 선행 키 컬럼이 (더) 낮거나 (더) 높은 카디널리티를 가질 때 보조 컬럼을 통해 그래뉼이 선택될 때 ClickHouse 일반 배제 탐색 알고리즘이 어떻게 동작하는지를 보여줘요. 두 경우 모두 예시로 다음을 가정할게요.

• URL 값 = "W3"인 행을 검색하는 쿼리.
• UserID와 URL에 대해 단순화된 값이 있는 우리 hits 테이블의 추상 버전.
• 인덱스를 위한 동일한 복합 기본 키(UserID, URL). 이것은 행이 먼저 UserID 값으로 정렬됨을 의미해요. 같은 UserID 값을 가진 행은 그런 다음 URL로 정렬돼요.
• 그래뉼 크기 2, 즉 각 그래뉼은 두 개의 행을 포함해요.

아래 다이어그램에서 각 그래뉼의 첫 테이블 행에 대한 키 컬럼 값을 주황색으로 표시했어요.

. 선행 키 컬럼이 (더) 낮은 카디널리티를 가질 때 UserID가 낮은 카디널리티를 가진다고 가정해 볼게요. 이 경우 같은 UserID 값이 여러 테이블 행과 그래뉼, 따라서 인덱스 mark에 걸쳐 퍼져 있을 가능성이 높아요. 같은 UserID의 인덱스 mark에 대해 인덱스 mark의 URL 값은 오름차순으로 정렬돼요(테이블 행이 먼저 UserID로, 그런 다음 URL로 정렬되기 때문이에요). 이것은 아래와 같이 효율적인 필터링을 허용해요. 위 다이어그램의 추상 샘플 데이터에 대한 그래뉼 선택 과정에는 세 가지 다른 시나리오가 있어요.

1. URL 값이 W3보다 작고 바로 뒤따르는 인덱스 mark의 URL 값도 W3보다 작은 인덱스 mark 0은, mark 0과 1이 같은 UserID 값을 가지므로 배제될 수 있어요. 이 배제-전제조건은 그래뉼 0이 완전히 U1 UserID 값으로 구성됨을 보장해서, ClickHouse가 그래뉼 0의 최대 URL 값도 W3보다 작다고 가정하고 그래뉼을 배제할 수 있어요.
2. URL 값이 W3보다 작거나 같고, 바로 뒤따르는 인덱스 mark의 URL 값이 W3보다 크거나 같은 인덱스 mark 1은, 그래뉼 1이 URL W3의 행을 포함할 수 있음을 의미하므로 선택돼요.
3. URL 값이 W3보다 큰 인덱스 mark 2와 3은 배제될 수 있어요. 기본 인덱스의 인덱스 mark는 각 그래뉼의 첫 테이블 행에 대한 키 컬럼 값을 저장하고 테이블 행이 디스크에 키 컬럼 값으로 정렬되어 있으므로, 그래뉼 2와 3은 URL 값 W3를 포함할 수 없기 때문이에요.

선행 키 컬럼이 (더) 높은 카디널리티를 가질 때 UserID가 높은 카디널리티를 가지면 같은 UserID 값이 여러 테이블 행과 그래뉼에 걸쳐 퍼져 있을 가능성이 낮아요. 이것은 인덱스 mark의 URL 값이 단조 증가하지 않음을 의미해요. 위 다이어그램에서 볼 수 있듯, URL 값이 W3보다 작은 표시된 모든 mark가 연관 그래뉼의 행을 ClickHouse 엔진으로 스트리밍하기 위해 선택돼요. 다이어그램의 모든 인덱스 mark가 위에서 설명한 시나리오 1에 해당하지만, _바로 뒤따르는 인덱스 mark가 현재 mark와 같은 UserID 값을 가질 때_라는 언급된 배제-전제조건을 만족하지 못하므로 배제될 수 없기 때문이에요. 예를 들어 URL 값이 W3보다 작고 바로 뒤따르는 인덱스 mark의 URL 값도 W3보다 작은 인덱스 mark 0을 고려해 볼게요. 이건 배제될 수 없어요. 왜냐하면 바로 뒤따르는 인덱스 mark 1이 현재 mark 0과 같은 UserID 값을 가지지 않기 때문이에요. 이것은 궁극적으로 ClickHouse가 그래뉼 0의 최대 URL 값에 대한 가정을 하는 것을 막아요. 대신 그래뉼 0이 잠재적으로 URL 값 W3의 행을 포함한다고 가정하고 mark 0을 선택해야 해요. 같은 시나리오가 mark 1, 2, 3에도 적용돼요.

결론 쿼리가 복합 키의 일부이지만 첫 키 컬럼이 아닌 컬럼을 필터링할 때 ClickHouse가 이진 탐색 알고리즘 대신 사용하는 일반 배제 탐색 알고리즘은 선행 키 컬럼이 (더) 낮은 카디널리티를 가질 때 가장 효과적이에요. 우리 샘플 데이터셋에서 두 키 컬럼(UserID, URL)은 비슷한 높은 카디널리티를 가지며, 설명했듯 URL 컬럼의 선행 키 컬럼이 (더) 높거나 비슷한 카디널리티를 가질 때 일반 배제 탐색 알고리즘은 매우 효과적이지 않아요.

데이터 스킵 인덱스에 대한 참고

UserID와 URL의 비슷한 높은 카디널리티 때문에 복합 기본 키(UserID, URL)가 있는 테이블의 URL 컬럼에 보조 데이터 스킵 인덱스를 만드는 것도 우리의 URL 필터링 쿼리에 큰 도움이 되지 않아요. 예를 들어 이 두 문은 테이블의 URL 컬럼에 minmax 데이터 스킵 인덱스를 만들고 채워요.

ALTER TABLE hits_UserID_URL ADD INDEX url_skipping_index URL TYPE minmax GRANULARITY 4;
ALTER TABLE hits_UserID_URL MATERIALIZE INDEX url_skipping_index;

ClickHouse는 이제 4개의 연속 그래뉼 그룹마다(위 ALTER TABLE 문의 GRANULARITY 4 절을 주목하세요) 최소·최대 URL 값을 저장하는 추가 인덱스를 만들었어요. 첫 인덱스 항목('mark 0')은 테이블의 첫 4개 그래뉼에 속한 행들의 최소·최대 URL 값을 저장해요. 두 번째 인덱스 항목('mark 1')은 다음 4개 그래뉼의 행들의 최소·최대 URL 값을 저장하는 식이에요. (ClickHouse는 데이터 스킵 인덱스에 대한 특별한 mark 파일도 만들어 인덱스 mark와 연관된 그래뉼 그룹을 찾아요.) UserID와 URL의 비슷한 높은 카디널리티 때문에, 이 보조 데이터 스킵 인덱스는 우리 URL 필터링 쿼리가 실행될 때 그래뉼이 선택에서 배제되도록 도울 수 없어요. 쿼리가 찾는 특정 URL 값(즉 'http://public_search')이 매우 가능성이 높게 인덱스가 각 그래뉼 그룹에 대해 저장한 최소값과 최대값 사이에 있기 때문에, ClickHouse는 (그것들이 쿼리와 일치하는 행을 포함할 수 있으므로) 그래뉼 그룹을 선택하도록 강요돼요.

여러 기본 인덱스를 사용해야 하는 필요

결과적으로 특정 URL의 행을 필터링하는 우리 샘플 쿼리를 크게 가속화하려면 그 쿼리에 최적화된 기본 인덱스를 사용해야 해요. 게다가 특정 UserID의 행을 필터링하는 우리 샘플 쿼리의 좋은 성능을 유지하고 싶다면 여러 기본 인덱스를 사용해야 해요. 다음은 이를 달성하는 방법을 보여줘요.

추가 기본 인덱스를 만드는 옵션

두 샘플 쿼리 — 특정 UserID의 행을 필터링하는 것과 특정 URL의 행을 필터링하는 것 — 을 모두 크게 가속화하려면 다음 세 가지 옵션 중 하나를 사용해 여러 기본 인덱스를 사용해야 해요.

• 다른 기본 키를 가진 두 번째 테이블 만들기.
• 기존 테이블에 매터리얼라이즈드 뷰 만들기.
• 기존 테이블에 프로젝션(projection) 추가하기.

세 옵션 모두 테이블 기본 인덱스와 행 정렬 순서를 재구성하기 위해 샘플 데이터를 추가 테이블로 효과적으로 중복해요. 그러나 세 옵션은 쿼리와 insert 문의 라우팅 측면에서 사용자에게 그 추가 테이블이 얼마나 투명한지가 달라요. 두 번째 테이블을 다른 기본 키로 만들면 쿼리는 쿼리에 가장 적합한 테이블 버전으로 명시적으로 보내져야 하고, 테이블을 동기화 상태로 유지하려면 새 데이터가 양쪽 테이블에 명시적으로 삽입되어야 해요. 매터리얼라이즈드 뷰를 사용하면 추가 테이블이 암시적으로 만들어지고 데이터는 두 테이블 사이에 자동으로 동기화돼요. 프로젝션은 암시적으로 만들어진(그리고 숨겨진) 추가 테이블을 데이터 변경과 자동으로 동기화할 뿐 아니라, ClickHouse가 쿼리에 가장 효과적인 테이블 버전을 자동으로 선택하기 때문에 가장 투명한 옵션이에요. 다음에서 여러 기본 인덱스를 만들고 사용하는 이 세 옵션을 실제 예시와 함께 더 자세히 논의할게요.

옵션 1: 보조 테이블 (Secondary Tables)

(원본 테이블과 비교해) 기본 키에서 키 컬럼의 순서를 바꾼 새로운 추가 테이블을 만들어요.

CREATE TABLE hits_URL_UserID
(
    `UserID` UInt32,
    `URL` String,
    `EventTime` DateTime
)
ENGINE = MergeTree
PRIMARY KEY (URL, UserID)
ORDER BY (URL, UserID, EventTime)
SETTINGS index_granularity_bytes = 0, compress_primary_key = 0;

원본 테이블의 모든 887만 행을 추가 테이블에 삽입해요.

INSERT INTO hits_URL_UserID
SELECT * FROM hits_UserID_URL;

응답은 다음과 같아요.

Ok.

0 rows in set. Elapsed: 2.898 sec. Processed 8.87 million rows, 838.84 MB (3.06 million rows/s., 289.46 MB/s.)

마지막으로 테이블을 optimize해요.

OPTIMIZE TABLE hits_URL_UserID FINAL;

기본 키에서 컬럼 순서를 바꿨으므로 삽입된 행은 (원본 테이블과 비교해) 다른 사전식 순서로 디스크에 저장되고, 따라서 그 테이블의 1083개 그래뉼도 이전과 다른 값을 포함해요. 이것이 결과 기본 키예요. 이제 "http://public_search" URL을 가장 자주 클릭한 상위 10명의 사용자를 계산하기 위해 URL 컬럼을 필터링하는 우리 예시 쿼리의 실행을 크게 가속화하는 데 사용될 수 있어요.

SELECT UserID, count(UserID) AS Count
FROM hits_URL_UserID
WHERE URL = 'http://public_search'
GROUP BY UserID
ORDER BY Count DESC
LIMIT 10;

응답은:

┌─────UserID─┬─Count─┐
│ 2459550954 │  3741 │
│ 1084649151 │  2484 │
│  723361875 │   729 │
│ 3087145896 │   695 │
│ 2754931092 │   672 │
│ 1509037307 │   582 │
│ 3085460200 │   573 │
│ 2454360090 │   556 │
│ 3884990840 │   539 │
│  765730816 │   536 │
└────────────┴───────┘

10 rows in set. Elapsed: 0.017 sec.
Processed 319.49 thousand rows,
11.38 MB (18.41 million rows/s., 655.75 MB/s.)

이제 거의 전체 테이블 스캔을 하는 대신, ClickHouse는 그 쿼리를 훨씬 더 효과적으로 실행했어요. UserID가 첫 번째, URL이 두 번째 키 컬럼이었던 원본 테이블의 기본 인덱스를 사용할 때 ClickHouse는 그 쿼리를 실행하기 위해 인덱스 mark에 대해 일반 배제 탐색을 사용했고, UserID와 URL의 비슷하게 높은 카디널리티 때문에 그게 그렇게 효과적이지 않았어요. URL이 기본 인덱스의 첫 컬럼인 이제 ClickHouse는 인덱스 mark에 대해 이진 탐색을 실행해요. 대응하는 서버 로그가 그것을 확인해 줘요(최근 버전에서 이진 탐색 메시지는 test 레벨로 기록됨 — 위 참고를 보세요):

...Executor): Key condition: (column 0 in ['http://public_search',
                                           'http://public_search'])
...Executor): Running binary search on index range for part all_1_9_2 (1083 marks)
...Executor): Found (LEFT) boundary mark: 644
...Executor): Found (RIGHT) boundary mark: 683
...Executor): Found continuous range in 19 steps
...Executor): Selected 1/1 parts by partition key, 1 parts by primary key,
              39/1083 marks by primary key, 39 marks to read from 1 ranges
...Executor): Reading approx. 319488 rows with 2 streams

ClickHouse는 일반 배제 탐색이 사용됐을 때의 1076개 대신 인덱스 mark 39개만 선택했어요. 추가 테이블은 URL을 필터링하는 우리 예시 쿼리의 실행을 가속화하도록 최적화됐다는 점에 주목하세요. 원본 테이블에서 그 쿼리의 나쁜 성능과 유사하게, 이제 UserID가 그 테이블 기본 인덱스의 두 번째 키 컬럼이므로 UserID를 필터링하는 우리 예시 쿼리는 새 추가 테이블로는 효과적으로 실행되지 않을 거예요. ClickHouse는 그래뉼 선택에 일반 배제 탐색을 사용하게 되고, 그것은 UserID와 URL의 비슷하게 높은 카디널리티에 그다지 효과적이지 않기 때문이에요. 자세한 내용은 상세 상자를 여세요.

UserID 필터링 쿼리는 이제 나쁜 성능을 가진다

SELECT URL, count(URL) AS Count
FROM hits_URL_UserID
WHERE UserID = 749927693
GROUP BY URL
ORDER BY Count DESC
LIMIT 10;

응답은:

┌─URL────────────────────────────┬─Count─┐
│ http://auto.ru/chatay-barana.. │   170 │
│ http://auto.ru/chatay-id=371...│    52 │
│ http://public_search           │    45 │
│ http://kovrik-medvedevushku-...│    36 │
│ http://forumal                 │    33 │
│ http://korablitz.ru/L_1OFFER...│    14 │
│ http://auto.ru/chatay-id=371...│    14 │
│ http://auto.ru/chatay-john-D...│    13 │
│ http://auto.ru/chatay-john-D...│    10 │
│ http://wot/html?page/23600_m...│     9 │
└────────────────────────────────┴───────┘

10 rows in set. Elapsed: 0.024 sec.
Processed 8.02 million rows,
73.04 MB (340.26 million rows/s., 3.10 GB/s.)

서버 로그:

...Executor): Key condition: (column 1 in [749927693, 749927693])
...Executor): Used generic exclusion search over index for part all_1_9_2
              with 1453 steps
...Executor): Selected 1/1 parts by partition key, 1 parts by primary key,
              980/1083 marks by primary key, 980 marks to read from 23 ranges
...Executor): Reading approx. 8028160 rows with 10 streams

이제 두 테이블이 있어요. 각각 UserID를 필터링하는 쿼리와 URL을 필터링하는 쿼리를 가속화하도록 최적화되어요.

옵션 2: 매터리얼라이즈드 뷰 (Materialized Views)

기존 테이블에 매터리얼라이즈드 뷰를 만들어요.

CREATE MATERIALIZED VIEW mv_hits_URL_UserID
ENGINE = MergeTree()
PRIMARY KEY (URL, UserID)
ORDER BY (URL, UserID, EventTime)
POPULATE
AS SELECT * FROM hits_UserID_URL;

응답은 다음과 같아요.

Ok.

0 rows in set. Elapsed: 2.935 sec. Processed 8.87 million rows, 838.84 MB (3.02 million rows/s., 285.84 MB/s.)

• (원본 테이블과 비교해) 뷰의 기본 키에서 키 컬럼의 순서를 바꿨어요.
• 매터리얼라이즈드 뷰는 행 순서와 기본 인덱스가 주어진 기본 키 정의에 기반한 암시적으로 만들어진 테이블에 의해 뒷받침돼요.
• 암시적으로 만들어진 테이블은 SHOW TABLES 쿼리에 나열되며 .inner로 시작하는 이름을 가져요.
• 매터리얼라이즈드 뷰에 대한 뒷받침 테이블을 먼저 명시적으로 만들고 그런 다음 TO [db].[table] 절로 뷰가 그 테이블을 겨냥하게 하는 것도 가능해요.
• POPULATE 키워드를 사용해 암시적으로 만들어진 테이블을 소스 테이블 hits_UserID_URL의 모든 887만 행으로 즉시 채워요.
• 소스 테이블 hits_UserID_URL에 새 행이 삽입되면 그 행도 자동으로 암시적으로 만들어진 테이블에 삽입돼요.
• 효과적으로 암시적으로 만들어진 테이블은 명시적으로 만든 보조 테이블과 같은 행 순서와 기본 인덱스를 가져요.

ClickHouse는 암시적으로 만들어진 테이블의 컬럼 데이터 파일(.bin), mark 파일(.mrk2), 기본 인덱스(primary.idx)를 ClickHouse 서버 데이터 디렉터리의 특별 폴더에 저장해요. 매터리얼라이즈드 뷰를 뒷받침하는 암시적으로 만들어진 테이블(및 그 기본 인덱스)은 이제 URL 컬럼을 필터링하는 우리 예시 쿼리의 실행을 크게 가속화하는 데 사용될 수 있어요.

SELECT UserID, count(UserID) AS Count
FROM mv_hits_URL_UserID
WHERE URL = 'http://public_search'
GROUP BY UserID
ORDER BY Count DESC
LIMIT 10;

응답은:

┌─────UserID─┬─Count─┐
│ 2459550954 │  3741 │
│ 1084649151 │  2484 │
│  723361875 │   729 │
│ 3087145896 │   695 │
│ 2754931092 │   672 │
│ 1509037307 │   582 │
│ 3085460200 │   573 │
│ 2454360090 │   556 │
│ 3884990840 │   539 │
│  765730816 │   536 │
└────────────┴───────┘

10 rows in set. Elapsed: 0.026 sec.
Processed 335.87 thousand rows,
13.54 MB (12.91 million rows/s., 520.38 MB/s.)

매터리얼라이즈드 뷰를 뒷받침하는 암시적으로 만들어진 테이블(및 그 기본 인덱스)이 효과적으로 명시적으로 만든 보조 테이블과 동일하므로, 쿼리는 명시적으로 만든 테이블과 같은 방식으로 효과적으로 실행돼요. 대응하는 서버 로그는 ClickHouse가 인덱스 mark에 대해 이진 탐색을 실행함을 확인해 줘요(최근 버전에서 이진 탐색 메시지는 test 레벨로 기록됨 — 위 참고를 보세요):

...Executor): Key condition: (column 0 in ['http://public_search',
                                           'http://public_search'])
...Executor): Running binary search on index range ...
...
...Executor): Selected 4/4 parts by partition key, 4 parts by primary key,
              41/1083 marks by primary key, 41 marks to read from 4 ranges
...Executor): Reading approx. 335872 rows with 4 streams

옵션 3: 프로젝션 (Projections)

기존 테이블에 프로젝션을 만들어요.

ALTER TABLE hits_UserID_URL
    ADD PROJECTION prj_url_userid
    (
        SELECT *
        ORDER BY (URL, UserID)
    );

그리고 프로젝션을 materialize해요.

ALTER TABLE hits_UserID_URL
    MATERIALIZE PROJECTION prj_url_userid;

• 프로젝션은 행 순서와 기본 인덱스가 프로젝션의 주어진 ORDER BY 절에 기반한 숨겨진 테이블(hidden table) 을 만들어요.
• 숨겨진 테이블은 SHOW TABLES 쿼리에 나열되지 않아요.
• MATERIALIZE 키워드를 사용해 숨겨진 테이블을 소스 테이블 hits_UserID_URL의 모든 887만 행으로 즉시 채워요.
• 소스 테이블 hits_UserID_URL에 새 행이 삽입되면 그 행도 자동으로 숨겨진 테이블에 삽입돼요.
• 쿼리는 항상 (문법적으로) 소스 테이블 hits_UserID_URL을 겨냥하지만, 숨겨진 테이블의 행 순서와 기본 인덱스가 더 효과적인 쿼리 실행을 허용하면 그 숨겨진 테이블이 대신 사용돼요.
• ORDER BY가 프로젝션의 ORDER BY 문과 일치하더라도 프로젝션은 ORDER BY를 사용하는 쿼리를 더 효율적으로 만들지 않는다는 점에 주의하세요 (https://github.com/ClickHouse/ClickHouse/issues/47333 참조).
• 효과적으로 암시적으로 만들어진 숨겨진 테이블은 명시적으로 만든 보조 테이블과 같은 행 순서와 기본 인덱스를 가져요.

ClickHouse는 숨겨진 테이블의 컬럼 데이터 파일(.bin), mark 파일(.mrk2), 기본 인덱스(primary.idx)를 소스 테이블의 데이터 파일·mark 파일·기본 인덱스 파일 옆 특별 폴더(아래 스크린샷에서 주황색으로 표시)에 저장해요. 프로젝션이 만든 숨겨진 테이블(및 그 기본 인덱스)은 URL 컬럼을 필터링하는 우리 예시 쿼리의 실행을 (암시적으로) 크게 가속화하는 데 사용될 수 있어요. 쿼리는 문법적으로 프로젝션의 소스 테이블을 겨냥한다는 점에 주목하세요.

SELECT UserID, count(UserID) AS Count
FROM hits_UserID_URL
WHERE URL = 'http://public_search'
GROUP BY UserID
ORDER BY Count DESC
LIMIT 10;

응답은:

┌─────UserID─┬─Count─┐
│ 2459550954 │  3741 │
│ 1084649151 │  2484 │
│  723361875 │   729 │
│ 3087145896 │   695 │
│ 2754931092 │   672 │
│ 1509037307 │   582 │
│ 3085460200 │   573 │
│ 2454360090 │   556 │
│ 3884990840 │   539 │
│  765730816 │   536 │
└────────────┴───────┘

10 rows in set. Elapsed: 0.029 sec.
Processed 319.49 thousand rows,
11.38 MB (11.05 million rows/s., 393.58 MB/s.)

프로젝션이 만든 숨겨진 테이블(및 그 기본 인덱스)이 효과적으로 명시적으로 만든 보조 테이블과 동일하므로, 쿼리는 명시적으로 만든 테이블과 같은 방식으로 효과적으로 실행돼요. 대응하는 서버 로그는 ClickHouse가 인덱스 mark에 대해 이진 탐색을 실행함을 확인해 줘요(최근 버전에서 이진 탐색 메시지는 test 레벨로 기록됨 — 위 참고를 보세요):

...Executor): Key condition: (column 0 in ['http://public_search',
                                           'http://public_search'])
...Executor): Running binary search on index range for part prj_url_userid (1083 marks)
...Executor): ...
...Executor): Choose complete Normal projection prj_url_userid
...Executor): projection required columns: URL, UserID
...Executor): Selected 1/1 parts by partition key, 1 parts by primary key,
              39/1083 marks by primary key, 39 marks to read from 1 ranges
...Executor): Reading approx. 319488 rows with 2 streams

요약

복합 기본 키(UserID, URL)를 가진 테이블의 기본 인덱스는 UserID를 필터링하는 쿼리를 가속화하는 데 매우 유용했지만, URL 컬럼이 복합 기본 키의 일부임에도 불구하고 그 인덱스는 URL 필터링 쿼리를 가속화하는 데 상당한 도움을 주지 못했어요. 그리고 그 반대도 마찬가지예요. 복합 기본 키(URL, UserID)를 가진 테이블의 기본 인덱스는 URL 필터링 쿼리를 가속화했지만, UserID를 필터링하는 쿼리에는 많은 지원을 제공하지 않았어요. 기본 키 컬럼 UserID와 URL의 비슷하게 높은 카디널리티 때문에, 두 번째 키 컬럼을 필터링하는 쿼리는 두 번째 키 컬럼이 인덱스에 있다는 것에서 큰 혜택을 받지 못해요. 따라서 두 번째 키 컬럼을 기본 인덱스에서 제거하는 것이(인덱스 메모리 소비를 줄이는 결과) 합리적이며, 대신 여러 기본 인덱스를 사용하는 것이 좋아요. 그러나 복합 기본 키의 키 컬럼들이 카디널리티에 큰 차이가 있다면, 기본 키 컬럼을 카디널리티 오름차순으로 정렬하는 것이 쿼리에 유익해요. 키 컬럼 사이의 카디널리티 차이가 클수록 그 컬럼들의 순서가 키에서 더 중요해요. 다음 섹션에서 그것을 보여드릴게요.

정렬 키 컬럼을 효율적으로 순서화하기

복합 기본 키에서 키 컬럼의 순서는 다음 둘 모두에 상당한 영향을 줄 수 있어요.

• 쿼리에서 보조 키 컬럼 필터링의 효율.
• 테이블 데이터 파일의 압축 비율.

이를 보여주기 위해 각 행이 인터넷 '사용자'('UserID' 컬럼)의 URL('URL' 컬럼) 접근이 봇 트래픽('IsRobot' 컬럼)으로 표시됐는지 여부를 나타내는 세 컬럼을 포함하는 웹 트래픽 샘플 데이터셋 버전을 사용할게요. 다음을 계산하는 전형적인 웹 분석 쿼리를 가속화하는 데 사용될 수 있는 위 세 컬럼 모두를 포함하는 복합 기본 키를 사용할게요.

• 특정 URL로의 트래픽 중 (비율로) 얼마나 봇에서 오는지, 또는
• 특정 사용자가 (아닌) 봇임을 얼마나 확신하는지 (그 사용자의 트래픽 중 얼마나 (아닌) 봇 트래픽으로 가정되는지)

URL 테이블 함수를 사용해(로컬 테이블을 만들 필요 없이 TSV 데이터를 임시로 쿼리하기 위해) 복합 기본 키에서 키 컬럼으로 사용하려는 세 컬럼의 카디널리티를 계산하는 이 쿼리를 사용해요. 이 쿼리를 clickhouse client에서 실행하세요.

SELECT
    formatReadableQuantity(uniq(URL)) AS cardinality_URL,
    formatReadableQuantity(uniq(UserID)) AS cardinality_UserID,
    formatReadableQuantity(uniq(IsRobot)) AS cardinality_IsRobot
FROM
(
    SELECT
        c11::UInt64 AS UserID,
        c15::String AS URL,
        c20::UInt8 AS IsRobot
    FROM url('https://datasets.clickhouse.com/hits/tsv/hits_v1.tsv.xz')
    WHERE URL != ''
)

응답은:

┌─cardinality_URL─┬─cardinality_UserID─┬─cardinality_IsRobot─┐
│ 2.39 million    │ 119.08 thousand    │ 4.00                │
└─────────────────┴────────────────────┴─────────────────────┘

1 row in set. Elapsed: 118.334 sec. Processed 8.87 million rows, 15.88 GB (74.99 thousand rows/s., 134.21 MB/s.)

카디널리티 사이에, 특히 URL과 IsRobot 컬럼 사이에 큰 차이가 있음을 볼 수 있어요. 따라서 복합 기본 키에서 이 컬럼들의 순서는 그 컬럼들을 필터링하는 쿼리의 효율적인 가속화와 테이블 컬럼 데이터 파일의 최적 압축 비율 달성 모두에 중요해요. 그것을 보여주기 위해 봇 트래픽 분석 데이터에 대해 두 테이블 버전을 만들어요.

• 카디널리티 내림차순으로 키 컬럼을 정렬한 복합 기본 키 (URL, UserID, IsRobot)를 가진 테이블 hits_URL_UserID_IsRobot
• 카디널리티 오름차순으로 키 컬럼을 정렬한 복합 기본 키 (IsRobot, UserID, URL)를 가진 테이블 hits_IsRobot_UserID_URL

복합 기본 키 (URL, UserID, IsRobot)를 가진 테이블 hits_URL_UserID_IsRobot를 만들어요.

CREATE TABLE hits_URL_UserID_IsRobot
(
    `UserID` UInt32,
    `URL` String,
    `IsRobot` UInt8
)
ENGINE = MergeTree
PRIMARY KEY (URL, UserID, IsRobot);

그리고 887만 행으로 채워요.

INSERT INTO hits_URL_UserID_IsRobot SELECT
    intHash32(c11::UInt64) AS UserID,
    c15 AS URL,
    c20 AS IsRobot
FROM url('https://datasets.clickhouse.com/hits/tsv/hits_v1.tsv.xz')
WHERE URL != '';

이것이 응답이에요.

0 rows in set. Elapsed: 104.729 sec. Processed 8.87 million rows, 15.88 GB (84.73 thousand rows/s., 151.64 MB/s.)

다음으로 복합 기본 키 (IsRobot, UserID, URL)를 가진 테이블 hits_IsRobot_UserID_URL을 만들어요.

CREATE TABLE hits_IsRobot_UserID_URL
(
    `UserID` UInt32,
    `URL` String,
    `IsRobot` UInt8
)
ENGINE = MergeTree
PRIMARY KEY (IsRobot, UserID, URL);

그리고 이전 테이블을 채우는 데 사용한 것과 같은 887만 행으로 채워요.

INSERT INTO hits_IsRobot_UserID_URL SELECT
    intHash32(c11::UInt64) AS UserID,
    c15 AS URL,
    c20 AS IsRobot
FROM url('https://datasets.clickhouse.com/hits/tsv/hits_v1.tsv.xz')
WHERE URL != '';

응답은:

0 rows in set. Elapsed: 95.959 sec. Processed 8.87 million rows, 15.88 GB (92.48 thousand rows/s., 165.50 MB/s.)

보조 키 컬럼의 효율적인 필터링

쿼리가 복합 키의 일부이면서 첫 키 컬럼인 적어도 하나의 컬럼을 필터링할 때 ClickHouse는 키 컬럼의 인덱스 mark에 대해 이진 탐색 알고리즘을 실행해요. 쿼리가 복합 키의 일부이지만 첫 키 컬럼이 아닌 (오직) 하나의 컬럼을 필터링할 때는 ClickHouse가 키 컬럼의 인덱스 mark에 대해 일반 배제 탐색 알고리즘을 사용해요. 두 번째 경우 복합 기본 키의 키 컬럼 순서는 일반 배제 탐색 알고리즘의 효율성에 중요해요. 이것은 카디널리티 내림차순으로 키 컬럼 (URL, UserID, IsRobot)을 정렬한 테이블의 UserID 컬럼을 필터링하는 쿼리예요.

SELECT count(*)
FROM hits_URL_UserID_IsRobot
WHERE UserID = 112304

응답은:

┌─count()─┐
│      73 │
└─────────┘

1 row in set. Elapsed: 0.026 sec.
Processed 7.92 million rows,
31.67 MB (306.90 million rows/s., 1.23 GB/s.)

이것은 카디널리티 오름차순으로 키 컬럼 (IsRobot, UserID, URL)을 정렬한 테이블에 대한 같은 쿼리예요.

SELECT count(*)
FROM hits_IsRobot_UserID_URL
WHERE UserID = 112304

응답은:

┌─count()─┐
│      73 │
└─────────┘

1 row in set. Elapsed: 0.003 sec.
Processed 20.32 thousand rows,
81.28 KB (6.61 million rows/s., 26.44 MB/s.)

카디널리티 오름차순으로 키 컬럼을 정렬한 테이블에서 쿼리 실행이 상당히 더 효과적이고 빠른 것을 볼 수 있어요. 그 이유는 일반 배제 탐색 알고리즘이 선행 키 컬럼이 더 낮은 카디널리티를 가진 보조 키 컬럼을 통해 그래뉼이 선택될 때 가장 효과적으로 동작하기 때문이에요. 그것은 이 가이드의 이전 섹션에서 자세히 설명했어요.

데이터 파일의 최적 압축 비율

이 쿼리는 위에서 만든 두 테이블 사이의 UserID 컬럼 압축 비율을 비교해요.

SELECT
    table AS Table,
    name AS Column,
    formatReadableSize(data_uncompressed_bytes) AS Uncompressed,
    formatReadableSize(data_compressed_bytes) AS Compressed,
    round(data_uncompressed_bytes / data_compressed_bytes, 0) AS Ratio
FROM system.columns
WHERE (table = 'hits_URL_UserID_IsRobot' OR table = 'hits_IsRobot_UserID_URL') AND (name = 'UserID')
ORDER BY Ratio ASC

이것이 응답이에요.

┌─Table───────────────────┬─Column─┬─Uncompressed─┬─Compressed─┬─Ratio─┐
│ hits_URL_UserID_IsRobot │ UserID │ 33.83 MiB    │ 11.24 MiB  │     3 │
│ hits_IsRobot_UserID_URL │ UserID │ 33.83 MiB    │ 877.47 KiB │    39 │
└─────────────────────────┴────────┴──────────────┴────────────┴───────┘

2 rows in set. Elapsed: 0.006 sec.

카디널리티 오름차순으로 키 컬럼 (IsRobot, UserID, URL)을 정렬한 테이블에서 UserID 컬럼의 압축 비율이 상당히 더 높은 것을 볼 수 있어요. 두 테이블 모두 정확히 같은 데이터가 저장되어 있음에도(둘 다 같은 887만 행을 삽입했어요), 복합 기본 키의 키 컬럼 순서가 테이블 컬럼 데이터 파일의 압축 데이터가 필요한 디스크 공간에 상당한 영향을 줘요.

• 카디널리티 내림차순으로 키 컬럼을 정렬한 복합 기본 키 (URL, UserID, IsRobot)를 가진 테이블 hits_URL_UserID_IsRobot에서 UserID.bin 데이터 파일은 디스크 11.24 MiB를 차지해요.
• 카디널리티 오름차순으로 키 컬럼을 정렬한 복합 기본 키 (IsRobot, UserID, URL)를 가진 테이블 hits_IsRobot_UserID_URL에서 UserID.bin 데이터 파일은 디스크 877.47 KiB만 차지해요.

테이블 컬럼에 대한 디스크의 좋은 압축 비율을 가지는 것은 디스크 공간을 절약할 뿐 아니라, 그 컬럼에서 데이터 읽기를 필요로 하는 쿼리(특히 분석적 쿼리)를 더 빠르게 만들어요. 왜냐하면 컬럼 데이터를 디스크에서 메인 메모리(운영체제의 파일 캐시)로 옮기는 데 필요한 I/O가 더 적기 때문이에요. 다음에서 기본 키 컬럼을 카디널리티 오름차순으로 정렬하는 것이 테이블 컬럼의 압축 비율에 유익한 이유를 설명할게요. 아래 다이어그램은 키 컬럼들이 카디널리티 오름차순으로 정렬된 기본 키에 대한 디스크상의 행 순서를 스케치해요. 테이블의 행 데이터가 기본 키 컬럼 순서로 디스크에 저장된다는 것을 논의했어요. 위 다이어그램에서 테이블의 행(디스크상의 컬럼 값)은 먼저 cl 값으로, 그리고 같은 cl 값을 가진 행들은 ch 값으로 정렬돼요. 그리고 첫 키 컬럼 cl이 낮은 카디널리티를 가지므로 같은 cl 값을 가진 행이 있을 가능성이 높아요. 그리고 그 때문에 ch 값들이 (같은 cl 값을 가진 행들에 대해 국소적으로) 정렬되어 있을 가능성도 높아요. 컬럼에서 유사한 데이터가 서로 가까이 배치되면, 예를 들어 정렬을 통해, 그 데이터는 더 잘 압축돼요. 일반적으로 압축 알고리즘은 데이터의 런 길이(더 많은 데이터를 볼수록 압축에 좋음)와 국소성(데이터가 더 유사할수록 압축 비율이 더 좋음)의 혜택을 받아요. 위 다이어그램과 대조적으로, 아래 다이어그램은 키 컬럼들이 카디널리티 내림차순으로 정렬된 기본 키에 대한 디스크상의 행 순서를 스케치해요. 이제 테이블의 행이 먼저 ch 값으로, 그리고 같은 ch 값을 가진 행들은 cl 값으로 정렬돼요. 하지만 첫 키 컬럼 ch가 높은 카디널리티를 가지므로 같은 ch 값을 가진 행이 있을 가능성이 낮아요. 그리고 그 때문에 cl 값들이 (같은 ch 값을 가진 행들에 대해 국소적으로) 정렬되어 있을 가능성도 낮아요.

요약

쿼리에서 보조 키 컬럼의 효율적인 필터링과 테이블 컬럼 데이터 파일의 압축 비율 모두에서, 기본 키의 컬럼을 카디널리티 오름차순으로 정렬하는 것이 유익해요.

단일 행을 효율적으로 식별하기

일반적으로 ClickHouse의 가장 좋은 사용 사례는 아니지만, 때로는 ClickHouse 위에 구축된 애플리케이션이 ClickHouse 테이블의 단일 행을 식별해야 해요. 직관적인 해결책은 행마다 고유한 값의 UUID 컬럼을 사용하고, 행의 빠른 검색을 위해 그 컬럼을 기본 키 컬럼으로 사용하는 것일 수 있어요. 가장 빠른 검색을 위해 UUID 컬럼은 첫 키 컬럼이어야 해요. ClickHouse 테이블의 행 데이터가 기본 키 컬럼 순서로 디스크에 저장되기 때문에, 매우 높은 카디널리티 컬럼(UUID 컬럼 같은)을 기본 키나 복합 기본 키에서 더 낮은 카디널리티 컬럼보다 앞에 두는 것은 다른 테이블 컬럼의 압축 비율에 해롭다고 논의했어요. 가장 빠른 검색과 최적의 데이터 압축 사이의 절충은, UUID가 더 낮은 카디널리티이고 테이블의 일부 컬럼에 대한 좋은 압축 비율을 보장하는 데 사용되는 키 컬럼들 다음의 마지막 키 컬럼인 복합 기본 키를 사용하는 거예요.

구체적인 예시

구체적인 예시는 Alexey Milovidov가 개발하고 블로그에 쓴 일반 텍스트 붙여넣기 서비스 https://pastila.nl이에요. 텍스트 영역의 변경마다 데이터가 자동으로 ClickHouse 테이블 행에 저장돼요(변경마다 한 행). 그리고 붙여넣은 내용의 (특정 버전을) 식별하고 검색하는 한 가지 방법은 내용의 해시를 그 내용을 포함하는 테이블 행의 UUID로 사용하는 거예요. 다음 다이어그램은

• 내용이 변경될 때(예: 텍스트 영역에 텍스트를 입력하는 키 입력 때문에) 행의 삽입 순서와
• PRIMARY KEY (hash)가 사용될 때 삽입된 행 데이터의 디스크상 순서를 보여줘요.

hash 컬럼이 기본 키 컬럼으로 사용되므로

• 특정 행은 매우 빠르게 검색될 수 있지만,
• 테이블의 행(그 컬럼 데이터)은 (고유하고 임의의) hash 값 오름차순으로 디스크에 저장돼요. 따라서 내용 컬럼의 값도 데이터 국소성이 없이 임의의 순서로 저장되어 내용 컬럼 데이터 파일의 최적이 아닌 압축 비율을 초래해요.

내용 컬럼의 압축 비율을 크게 개선하면서 특정 행의 빠른 검색을 유지하기 위해, pastila.nl은 특정 행을 식별하는 데 두 개의 해시(그리고 복합 기본 키)를 사용해요.

• 위에서 논의한, 서로 다른 데이터에 대해 구별되는 내용의 해시.
• 데이터의 작은 변경에 변하지 않는 국소성 민감 해시(지문).

다음 다이어그램은

• 내용이 변경될 때 행의 삽입 순서와
• 복합 PRIMARY KEY (fingerprint, hash)가 사용될 때 삽입된 행 데이터의 디스크상 순서를 보여줘요.

이제 디스크의 행은 먼저 fingerprint로 정렬되고, 같은 fingerprint 값을 가진 행들에 대해 hash 값이 최종 순서를 결정해요. 작은 변경만 다른 데이터는 같은 fingerprint 값을 얻으므로, 유사한 데이터가 이제 내용 컬럼에서 디스크에 서로 가까이 저장돼요. 그리고 그것은 압축 알고리즘이 일반적으로 데이터 국소성의 혜택을 받으므로(데이터가 더 유사할수록 압축 비율이 더 좋음) 내용 컬럼의 압축 비율에 매우 좋아요. 절충은 복합 PRIMARY KEY (fingerprint, hash)에서 생기는 기본 인덱스를 최적으로 활용하기 위해 특정 행의 검색에 두 필드(fingerprint와 hash)가 필요하다는 거예요.

더 알아보기 (Learn more)

• 스키마 설계
• 데이터 비정규화
• 데이터 압축