Trino와 HyperLogLog 알고리즘

 

🧠 HyperLogLog

핵심 아이디어

"해시값에서 가장 긴 앞자리 0의 개수를 보면, 얼마나 많은 고유 값이 있었는지 추정할 수 있다."

• 원소들을 해시 함수로 변환하고,
• 해시값의 **이진 표현에서 가장 앞의 연속된 0의 길이(max leading zeros)**를 기록,
• 이를 여러 버킷(bucket)에 나눠서 평균/보정하면 전체 고유 수를 추정할 수 있음.

🔍 왜 효과적인가?

• 해시값은 고유하게 퍼지기 때문에, 많은 고유 값이 들어오면 더 긴 연속된 0이 나타날 확률이 높아짐.
• 이걸 통계적으로 계산하면 거의 선형적 정확도를 얻을 수 있음.

📦 장점

메모리 효율	수십억 개 데이터를 추정하는 데 수 KB만 사용
속도	입력값 처리 시 해시 → 배열 업데이트만 하면 됨
병렬 처리 용이	HLL 스케치는 쉽게 merge 가능 → 분산 시스템에 적합
추정 정확도 조절 가능	파라미터로 ±1% ~ ±5% 조절 가능

 

📉 단점

추정치	정확하지는 않음 (신뢰 구간 존재)
고유 수가 작을 때	정확도가 낮아질 수 있음 (bias 보정 기법 존재)
해시 충돌	극단적인 충돌 가능성 존재하지만 희박

 

---

⚙️ 작동 예시 (단순화 버전)

1. 각 입력값에 대해 hash(x)를 계산 → 이진수로 표현
2. 해시값을 m개의 버킷으로 나눔 (보통 2^k 개)
3. 각 버킷에 대해 leading zeros 개수를 기록
4. 전체 평균을 통해 추정치 계산:

여기서:

• R[i]: i번 버킷에 기록된 max leading zeros
• α_m: 보정 상수 (m값에 따라 다름)

 

📘 예를 들어 Trino에서

SELECT approx_distinct(user_id) FROM logs;

→ 내부적으로는 각 user_id를 해시하고, 그 해시값으로 HLL 스케치를 만들어서 최종 카디널리티를 추정합니다.

 

✅ 사용되는 곳

• Trino (approx_distinct)
• BigQuery (APPROX_COUNT_DISTINCT)
• Redis (HLL 자료구조)
• Elasticsearch (카디널리티 집계)
• Flink, Druid, ClickHouse 등 모든 대용량 분석 플랫폼

 

 

위 시뮬레이션은 HyperLogLog(HLL) 알고리즘이 어떻게 동작하는지 보여줍니다.

• 실제로는 user_0부터 user_9999까지 10,000개의 고유 값을 넣었습니다.
• 해시값을 바탕으로 64개의 버킷으로 나누고, 각 버킷마다 해시값의 앞쪽 연속된 0의 개수를 기록했습니다.
• 최종적으로 HLL이 추정한 고유 개수는 약 14,025개로, 약간 과대 추정된 것을 볼 수 있습니다.

이는 HyperLogLog의 특성상 약 ±2~5%의 오차가 있으며, 데이터 수가 많을수록 정확도가 향상됩니다.

그래프는 각 버킷이 저장한 "가장 긴 leading zeros" 값을 나타낸 것으로, 분산된 해시값들이 어떻게 카디널리티 추정에 기여하는지를 시각적으로 보여줍니다.

 

✅ Trino의 대표적인 Approximate 함수 목록

함수설명예시

approx_distinct(x [, e])	고유 개수 추정 (COUNT(DISTINCT x))	approx_distinct(user_id)
approx_percentile(x, percentage [, accuracy])	퍼센타일 추정 (e.g. 95%)	approx_percentile(duration, 0.95)
approx_percentile(x, percentages ARRAY)	여러 퍼센타일 한 번에	approx_percentile(duration, ARRAY[0.5, 0.9, 0.99])
approx_set(x)	HLL 구조 리턴 (post-aggregation 처리 가능)	approx_set(user_id)
cardinality(approx_set)	approx_set() 결과의 고유 개수 추정	cardinality(approx_set(user_id))
merge(approx_set)	여러 노드에서 나온 approx_set을 병합	cardinality(merge(sets))

 

 

🔍 함수별 상세 설명

1. approx_distinct(x [, e])

• HyperLogLog 기반
• e: 상대 오차율 (default: 0.023)
• 예: approx_distinct(user_id, 0.01) → 약 1% 오차

2. approx_percentile(x, p [, accuracy])

• 큰 데이터셋에서 퍼센타일 추정치 구할 때 사용
• 예: 평균보다 상위 95% 사용시간

SELECT approx_percentile(duration, 0.95) FROM sessions;

• 여러 퍼센타일 계산도 가능:

SELECT approx_percentile(duration, ARRAY[0.5, 0.9, 0.99]) FROM sessions;

 

3. approx_set(x)

• user_id들을 HLL 형식으로 집계 (나중에 merge 가능)

SELECT approx_set(user_id) FROM logs;

• cardinality()와 함께 쓰면 추정 고유 수 구할 수 있음

 

4. merge(approx_set)

• 분산 환경에서 approx_set들을 합칠 때 사용

SELECT cardinality(merge(sets)) FROM ( SELECT approx_set(user_id) AS sets FROM logs GROUP BY region );

 

📌 요약 표

고유 개수	COUNT(DISTINCT x)	approx_distinct(x)
퍼센타일	percentile(x, p)	approx_percentile(x, p)
유니크 값 집합	없음	approx_set(x)
집합 합치기	없음	merge(approx_set) + cardinality()