공부/데이터 2026. 4. 10. 16:16

0. 개요

Apache DataSketches는 확률적 알고리즘(Probabilistic Algorithms) 기반의 스트리밍 데이터 집계 라이브러리입니다. 빅데이터 환경에서 정확한 계산이 수십 분~수 시간 걸리는 고유값 카운팅, 분위수 추정, 빈발 항목 탐지 같은 연산을 수 밀리초에 처리하며, 수학적으로 오차 범위를 보장합니다.

2011년 Yahoo 내부 프로젝트로 시작 → 2015년 오픈소스 공개 → 2019년 Apache Software Foundation Top-Level Project 승격.

항목	내용
공식 사이트	https://datasketches.apache.org/
GitHub	https://github.com/apache/datasketches-python
라이선스	Apache License 2.0
지원 언어	Java, C++, Python, Go, Rust
통합 플랫폼	Apache Druid, Spark, Hive, BigQuery, Snowflake, Databricks

1. Apache DataSketches란?

한 줄 정의

수학적으로 증명된 오차 범위를 보장하면서, 빅데이터 스트림을 단일 패스로 처리해 카디널리티·분위수·빈도 등을 근사 추정하는 확률적 스트리밍 알고리즘 라이브러리

등장 배경

Yahoo, Google, Facebook 같은 기업들은 매일 수백억 건의 이벤트 로그를 생성합니다. 여기서 다음 같은 쿼리들이 빈번하게 요구됩니다.

COUNT DISTINCT: "이번 주 앱을 방문한 고유 사용자 수는?" → 10억 유저 = HashSet에 수 GB 메모리
PERCENTILE: "응답시간의 P99는?" → 전체 데이터 정렬 필요 = O(N log N) 시간
Set Intersection: "캠페인 A와 B 모두 접촉한 사용자는?" → 수십 대 노드 간 전체 데이터 셔플

DataSketches의 핵심 통찰: "근사값으로도 충분하다면, 수학적으로 보장된 오차 범위 내에서 수천~수십만 배 빠르고 메모리 효율적인 알고리즘을 쓸 수 있습니다."

핵심 스케치 종류

HLL 스케치 (HyperLogLog) — 카디널리티 추정

용도: 고유값 개수 추정 (COUNT DISTINCT)
정확도: 표준 오차 ≈ 1.04 / sqrt(k) (lgK=12 기준 ~0.8%)
메모리: lgK=12 기준 ~2.5KB로 수십억 개 항목 처리
알고리즘: 입력값을 해시하여 최대 선행 0비트 수를 k개 레지스터에 기록 → HarmonicMean 보정

CPC 스케치 (Compressed Probabilistic Counting)

용도: 카디널리티 추정 (HLL보다 더 작은 크기)
특징: 동일 정확도에서 HLL보다 2~16배 작은 직렬화 크기
이론: 이론적 엔트로피 하한 달성 — 어떤 HLL 구현도 CPC를 이길 수 없습니다

Theta 스케치 — 카디널리티 + 집합 연산

용도: 카디널리티 추정 + 합집합/교집합/차집합
정확도: RSE ≈ 1 / sqrt(k) (lgK=12 기준 ~1.56%)
메모리: k × 8바이트 (기본 k=4096 → ~32KB)
핵심 강점: 집합 연산 결과도 스케치 → 복잡한 퍼널 분석 가능

KLL 스케치 (Karnin-Lang-Liberty) — 분위수 추정

용도: 분위수 추정 (중앙값, 백분위수, 히스토그램)
정확도: 순위 오차 ≤ ε (설정 가능), 입력 분포에 무관
메모리: 이론적 최적 공간 (Space-Optimal) 수학적 증명
알고리즘: 계층적 압축(Hierarchical Compaction) — 버퍼가 가득 차면 절반만 상위 레벨로 승격

Frequent Items 스케치 — 빈발 항목 탐지

용도: Heavy Hitters 탐지 (최고 빈도 항목)
정확도: 결정론적 상한/하한 보장 (100% 확률로 실제 빈도는 [LowerBound, UpperBound] 사이)
알고리즘: Misra-Gries / Space-Saving 기반

Tuple 스케치 — 연관 데이터 포함 집합 연산

용도: Theta Sketch + 연관 Summary 데이터 (클릭 수, 매출 등) 동시 집계
특징: 고유 ID별 임프레션 수, 클릭 수, 매출 등 복합 집계

메모리 효율성 비교

문제 유형	정확한 방법	DataSketches 근사	절감 비율
1억 고유 ID 카운트	~800MB (HashSet)	~2.5KB (HLL)	~320,000배
10억 항목 분위수	~8GB (전체 저장)	~수십KB (KLL)	~수십만 배
빈도 상위 100개	전체 카운트 맵	~수KB (Frequent Items)	데이터 크기 무관
집합 교집합 카디널리티	두 집합 전체 교차	~32KB (Theta Sketch)	수만 배

핵심 설계 원칙

단일 패스(Single Pass): 스트리밍 데이터를 한 번만 읽음 — 재처리 불필요
병합 가능(Mergeable): 여러 스케치를 나중에 합칠 수 있음 → 분산 시스템 친화적
수학적 오차 보장: 확률적 오차 경계를 수식으로 증명 — 신뢰 구간 제공
언어 간 바이너리 호환: Java, C++, Python 직렬화 형식 동일

2. 기존 SQL 호출과의 차이점

COUNT DISTINCT vs HLL 스케치

-- 기존 SQL: 정확하지만 느림
SELECT COUNT(DISTINCT user_id) FROM events;
-- 10억 레코드 → 45분 소요, 수십 GB 메모리

-- HLL 스케치: 빠르고 메모리 효율적
SELECT APPROX_COUNT_DISTINCT(user_id) FROM events;
-- 동일 데이터 → 100ms 소요, ~6KB 메모리 (오차 ±1~2%)

항목	SQL COUNT DISTINCT	HLL 스케치
정확도	100%	~~99% (오차 ±1~~2%)
메모리	O(n) — 모든 고유값 저장	고정 크기 (6KB~수십KB)
속도	매우 느림	매우 빠름 (단일 패스)
분산 병합	불가능 (전체 집합 필요)	가능 (스케치 병합)
10억 건 예시	45분	100ms

PERCENTILE vs KLL 스케치

-- 기존 SQL: 전체 데이터 정렬 필요 O(n log n)
SELECT PERCENTILE_CONT(0.99) WITHIN GROUP (ORDER BY response_ms) AS p99
FROM request_logs;

-- KLL 스케치: O(log log n) 공간, 스트리밍 처리 가능
SELECT kll_sketch_get_quantile(sketch, 0.99) AS p99
FROM sketched_table;

항목	SQL PERCENTILE	KLL 스케치
공간	O(n)	O(log log n)
오차	없음	순위 기준 ±0.1%
스트리밍	불가	가능
병합	불가	가능

집합 연산 (GROUP BY INTERSECT) vs Theta 스케치

-- 기존 SQL: 전체 테이블 스캔 2회, 대용량 조인 필요
SELECT COUNT(*) FROM (
    SELECT user_id FROM events WHERE campaign = 'A'
    INTERSECT
    SELECT user_id FROM events WHERE campaign = 'B'
) t;

-- Theta 스케치: 미리 집계된 스케치 간 연산 → 수 ms
SELECT THETA_SKETCH_ESTIMATE(
    THETA_SKETCH_INTERSECT(sketch_A, sketch_B)
) AS intersect_users
FROM pre_aggregated_sketches;

성능 종합 비교

지표	정확한 SQL	스케치 근사
속도 (10억 건)	분~시간	밀리초
메모리 사용량	수십 GB	수 KB~수십 KB
분산 병합	전체 데이터 재전송	스케치만 전송 (수 KB)
정확도	100%	97~99%+ (오차 수학적 보장)
스트리밍 처리	제한적	완전 지원
사전 집계 재사용	불가	가능 (스케치 직렬화 저장)

SQL로 충분한 경우 vs 스케치가 필요한 경우

SQL로 충분한 경우

데이터 크기가 수백만 건 이하
100% 정확도가 비즈니스 요건 (금융, 법적 집계)
쿼리가 가끔 실행되어 지연 허용 가능

스케치가 필요한 경우

수억~수천억 건 대용량 데이터
실시간/준실시간 분석 대시보드 (초 단위 응답 필요)
Spark/Flink 분산 환경에서 노드 간 집계 병합
여러 세그먼트 간 중복 제거 (교집합/합집합)

3. Python 사용법

설치

pip install datasketches
# 최신 버전: 5.2.0 (Python 3.11~3.13 지원)

HLL 스케치 — 카디널리티 추정

from datasketches import hll_sketch, hll_union

# lg_config_k: 정밀도 설정 (4~21, 클수록 정확하지만 메모리 증가)
# lg_k=12 → ~2.3KB 메모리, 오차율 ~0.8%
sketch = hll_sketch(lg_config_k=12)

for user_id in range(1_000_000):
    sketch.update(f"user_{user_id}")

print(f"추정 고유 사용자 수: {sketch.get_estimate():,.0f}")

# 95% 신뢰 구간 확인
lower = sketch.get_lower_bound(num_std_devs=2)
upper = sketch.get_upper_bound(num_std_devs=2)
print(f"95% 신뢰 구간: [{lower:,.0f} ~ {upper:,.0f}]")

# 직렬화 (분산 시스템 저장/전송용)
compact_bytes = sketch.serialize_compact()
print(f"직렬화 크기: {len(compact_bytes)} bytes")

# 복원
restored = hll_sketch.deserialize(compact_bytes)

# 스케치 병합 (핵심 기능: 전체 데이터 없이 스케치만 병합)
sketch_a = hll_sketch(12)
sketch_b = hll_sketch(12)
for uid in range(500_000): sketch_a.update(f"user_{uid}")
for uid in range(300_000, 800_000): sketch_b.update(f"user_{uid}")

union = hll_union(lg_max_k=12)
union.update(sketch_a)
union.update(sketch_b)
merged = union.get_result()
print(f"병합 후 고유 사용자 수: {merged.get_estimate():,.0f}")
# 실제 고유: 800,000명

KLL 스케치 — 분위수/백분위수 추정

from datasketches import kll_floats_sketch
import numpy as np

sketch = kll_floats_sketch(k=200)  # k=200: 오차율 ~1.33%

# 웹 서비스 응답 시간 시뮬레이션 (1,000만 건)
response_times = np.random.lognormal(mean=3.0, sigma=1.2, size=10_000_000)
sketch.update(response_times.astype(np.float32))  # numpy 배열 직접 입력

print(f"처리: {sketch.n:,}건 → 보관 샘플: {sketch.num_retained:,}건")
# 처리 10,000,000건 → 보관 ~1,700건 (0.017%!)

# 분위수 조회
print(f"P50 (중앙값): {sketch.get_quantile(0.5):.1f}ms")
print(f"P90:          {sketch.get_quantile(0.90):.1f}ms")
print(f"P99:          {sketch.get_quantile(0.99):.1f}ms")
print(f"P99.9:        {sketch.get_quantile(0.999):.1f}ms")

# 역방향: 특정 값의 순위 조회
rank_200ms = sketch.get_rank(200.0)
print(f"200ms 이하인 비율: {rank_200ms:.1%}")

# SLA 체크: P95 ≤ 200ms 충족 여부
sla_ok = sketch.get_rank(200.0) >= 0.95
print(f"SLA 충족: {sla_ok}")

# 병합 (분산 노드에서 수집 후 합치기)
sketch_node1 = kll_floats_sketch(200)
sketch_node2 = kll_floats_sketch(200)
# ... 각 노드에서 데이터 처리 ...
sketch_node1.merge(sketch_node2)

Theta 스케치 — 집합 연산

from datasketches import update_theta_sketch, theta_union, theta_intersection, theta_a_not_b

# 세 개 캠페인의 사용자 중복 분석
sketch_a = update_theta_sketch()
sketch_b = update_theta_sketch()
sketch_c = update_theta_sketch()

for uid in range(700_000): sketch_a.update(f"user_{uid}")         # 캠페인 A: 0~70만
for uid in range(300_000, 1_000_000): sketch_b.update(f"user_{uid}")  # 캠페인 B: 30~100만
for uid in range(600_000, 1_200_000): sketch_c.update(f"user_{uid}")  # 캠페인 C: 60~120만

# 합집합 (A OR B)
union_op = theta_union()
union_op.update(sketch_a)
union_op.update(sketch_b)
result_union = union_op.get_result()
print(f"A ∪ B 고유 사용자: {result_union.get_estimate():,.0f}")

# 교집합 (A AND B)
intersect_op = theta_intersection()
intersect_op.update(sketch_a)
intersect_op.update(sketch_b)
result_intersect = intersect_op.get_result()
print(f"A ∩ B 중복 사용자: {result_intersect.get_estimate():,.0f}")
# 실제: 400,000명

# 차집합 (A만 방문)
a_not_b_op = theta_a_not_b()
result_diff = a_not_b_op.compute(sketch_a, sketch_b)
print(f"A만 방문 (A\\B): {result_diff.get_estimate():,.0f}")

# 직렬화
compact_a = sketch_a.compact()
serialized = compact_a.serialize()
print(f"직렬화 크기: {len(serialized)} bytes")

Frequent Items 스케치 — 빈발 항목 탐지

from datasketches import frequent_strings_sketch, frequent_items_error_type
import random

sketch = frequent_strings_sketch(max_map_size=32)

products = ["iPhone", "MacBook", "iPad", "AirPods", "AppleWatch"]
weights  = [40, 25, 20, 10, 5]

for _ in range(1_000_000):
    sketch.update(random.choices(products, weights=weights)[0])

# NO_FALSE_POSITIVES: 확실한 빈발 항목만 (보수적)
print("=== 확실한 빈발 항목 ===")
for item in sketch.get_frequent_items(frequent_items_error_type.NO_FALSE_POSITIVES):
    print(f"  {item.get_item():12s}: {item.get_estimate():>10,} "
          f"[{item.get_lower_bound():>10,} ~ {item.get_upper_bound():>10,}]")

# NO_FALSE_NEGATIVES: 빈발 가능성 있는 것 모두 (포괄적)
print("\n=== 빈발 가능 항목 ===")
for item in sketch.get_frequent_items(frequent_items_error_type.NO_FALSE_NEGATIVES):
    print(f"  {item.get_item():12s}: {item.get_estimate():>10,}")

분산 시스템에서의 병합 패턴

from datasketches import hll_sketch, hll_union, kll_floats_sketch

def worker_process(shard_id: int, data_range: range) -> dict:
    """각 분산 워커에서 실행: 스케치 생성 후 직렬화하여 반환"""
    hll = hll_sketch(lg_config_k=12)
    kll = kll_floats_sketch(k=200)

    for user_id in data_range:
        hll.update(f"user_{user_id}")
        kll.update(float(user_id % 1000))

    return {
        "hll_bytes": hll.serialize_compact(),  # 수 KB만 전송
        "kll_bytes": kll.serialize(),
    }

def driver_aggregate(worker_results: list) -> None:
    """드라이버 노드: 모든 스케치 병합"""
    hll_union_op = hll_union(lg_max_k=12)
    kll_merged = kll_floats_sketch(k=200)

    for result in worker_results:
        hll_shard = hll_sketch.deserialize(result["hll_bytes"])
        kll_shard = kll_floats_sketch.deserialize(result["kll_bytes"])
        hll_union_op.update(hll_shard)
        kll_merged.merge(kll_shard)

    final_hll = hll_union_op.get_result()
    print(f"전체 고유 사용자: {final_hll.get_estimate():,.0f}")
    print(f"전체 P99:        {kll_merged.get_quantile(0.99):.1f}")

# 10개 워커 × 100만 명 = 1,000만 명 처리
results = [worker_process(i, range(i*1_000_000, (i+1)*1_000_000)) for i in range(10)]

total_bytes = sum(len(r["hll_bytes"]) + len(r["kll_bytes"]) for r in results)
print(f"전송된 총 데이터: {total_bytes/1024:.1f} KB")
# 전통 방식: 1,000만 user_id → 수십 MB~수 GB
# 스케치 방식: 수십 KB만 전송!

driver_aggregate(results)

4. BigQuery / Databricks / Snowflake 예시

BigQuery

내장 근사 집계 함수

-- APPROX_COUNT_DISTINCT: 고유 사용자 수 근사 (정확도 ~98%)
SELECT
  date,
  APPROX_COUNT_DISTINCT(user_id) AS approx_unique_users
FROM `myproject.analytics.events`
GROUP BY date;

-- APPROX_QUANTILES: 응답 시간 분위수
SELECT
  APPROX_QUANTILES(response_time_ms, 100)[OFFSET(50)] AS p50_ms,
  APPROX_QUANTILES(response_time_ms, 100)[OFFSET(95)] AS p95_ms,
  APPROX_QUANTILES(response_time_ms, 100)[OFFSET(99)] AS p99_ms
FROM `myproject.monitoring.api_logs`;

-- APPROX_TOP_COUNT: 상위 빈도 페이지
SELECT approx_top.*
FROM (
  SELECT APPROX_TOP_COUNT(page_url, 10) AS top_pages
  FROM `myproject.analytics.pageviews`
),
UNNEST(top_pages) AS approx_top
ORDER BY approx_top.count DESC;

HLL++ 스케치 함수 (증분 집계 + 저장)

-- 1단계: 파티션별 HLL 스케치 생성 및 저장
CREATE OR REPLACE TABLE `myproject.analytics.daily_user_sketches` AS
SELECT
  DATE(event_timestamp) AS event_date,
  country,
  HLL_COUNT.INIT(user_id, 15) AS user_hll_sketch
  -- precision 15: 오차율 ~0.4%, 메모리 ~32KB
FROM `myproject.analytics.events`
GROUP BY event_date, country;

-- 2단계: 여러 날의 스케치를 병합하여 월간 고유 사용자 계산
-- (전체 데이터 재스캔 불필요!)
SELECT
  DATE_TRUNC(event_date, MONTH) AS month,
  country,
  HLL_COUNT.MERGE(user_hll_sketch) AS monthly_unique_users
FROM `myproject.analytics.daily_user_sketches`
GROUP BY month, country;

-- 롤링 30일 윈도우 고유 사용자 (재계산 없이)
WITH daily_sketches AS (
  SELECT event_date, HLL_COUNT.INIT(user_id) AS sketch
  FROM `myproject.analytics.events`
  GROUP BY event_date
)
SELECT
  d1.event_date,
  HLL_COUNT.MERGE(d2.sketch) AS rolling_30d_unique_users
FROM daily_sketches d1
JOIN daily_sketches d2
  ON d2.event_date BETWEEN DATE_SUB(d1.event_date, INTERVAL 29 DAY) AND d1.event_date
GROUP BY d1.event_date;

Apache DataSketches for BigQuery (bqutil)

-- Theta Sketch: A/B 테스트 집합 연산
WITH group_sketches AS (
  SELECT
    experiment_group,
    bqutil.datasketches.theta_sketch_agg_int64(user_id) AS sketch
  FROM `myproject.experiments.user_assignments`
  GROUP BY experiment_group
)
SELECT
  bqutil.datasketches.theta_sketch_get_estimate(
    bqutil.datasketches.theta_sketch_a_not_b(
      (SELECT sketch FROM group_sketches WHERE experiment_group = 'treatment'),
      (SELECT sketch FROM group_sketches WHERE experiment_group = 'control')
    )
  ) AS exclusive_treatment_users;

-- KLL Sketch: 서비스별 응답 시간 분포
WITH kll_sketches AS (
  SELECT
    service_name,
    bqutil.datasketches.kll_sketch_float_build_k(
      CAST(response_time_ms AS FLOAT64), 250
    ) AS sketch
  FROM `myproject.monitoring.api_logs`
  GROUP BY service_name
)
SELECT
  service_name,
  bqutil.datasketches.kll_sketch_float_get_quantile(sketch, 0.5, true)  AS p50_ms,
  bqutil.datasketches.kll_sketch_float_get_quantile(sketch, 0.95, true) AS p95_ms,
  bqutil.datasketches.kll_sketch_float_get_quantile(sketch, 0.99, true) AS p99_ms
FROM kll_sketches;

Databricks (Spark 3.5+ / Databricks Runtime 13.0+)

네이티브 SQL 함수

-- HLL 스케치 생성 및 추정
SELECT
  DATE(event_time) AS event_date,
  hll_sketch_estimate(hll_sketch_agg(user_id, 12)) AS approx_unique_users
FROM events
GROUP BY event_date;

-- 스케치 저장 후 주간 롤업 (재계산 없이)
CREATE OR REPLACE TABLE daily_user_sketches AS
SELECT event_date, platform, hll_sketch_agg(user_id, 14) AS user_sketch
FROM events
GROUP BY event_date, platform;

SELECT
  DATE_TRUNC('week', event_date) AS week_start,
  platform,
  hll_sketch_estimate(hll_union_agg(user_sketch)) AS weekly_unique_users
FROM daily_user_sketches
GROUP BY week_start, platform;

-- Theta 스케치: 마케팅 채널 중복 분석
WITH channel_sketches AS (
  SELECT channel, theta_sketch_agg(user_id, 20) AS sketch
  FROM user_acquisitions
  GROUP BY channel
)
SELECT
  theta_sketch_estimate(theta_intersect_agg(sketch)) AS overlap_user_count
FROM channel_sketches
WHERE channel IN ('email', 'push_notification');

-- KLL 스케치: 주문 금액 분위수
SELECT
  product_category,
  kll_sketch_get_quantile(sketch, 0.25) AS q1_price,
  kll_sketch_get_quantile(sketch, 0.50) AS median_price,
  kll_sketch_get_quantile(sketch, 0.75) AS q3_price,
  kll_sketch_get_quantile(sketch, 0.99) AS p99_price
FROM (
  SELECT product_category, kll_sketch_agg_double(order_amount) AS sketch
  FROM orders
  GROUP BY product_category
);

PySpark + Python datasketches 라이브러리

from pyspark.sql.functions import pandas_udf, col
from pyspark.sql.types import BinaryType, LongType
import pandas as pd
import datasketches

# HLL 스케치 생성 UDF
@pandas_udf(BinaryType())
def create_hll_sketch(values: pd.Series) -> bytes:
    sketch = datasketches.hll_sketch(12)
    for v in values.dropna():
        sketch.update(str(v))
    return sketch.serialize_compact()

# HLL 스케치 추정 UDF
@pandas_udf(LongType())
def estimate_hll(sketches: pd.Series) -> pd.Series:
    results = []
    for s in sketches:
        if s is None:
            results.append(0)
        else:
            sketch = datasketches.hll_sketch.deserialize(bytes(s))
            results.append(int(sketch.get_estimate()))
    return pd.Series(results)

# 네이티브 SQL 사용 (권장)
spark.sql("""
    SELECT
        DATE(event_time) AS event_date,
        hll_sketch_estimate(hll_sketch_agg(user_id, 12)) AS approx_uniq_users
    FROM events_view
    GROUP BY DATE(event_time)
""")

Snowflake

내장 근사 집계 함수

-- APPROX_COUNT_DISTINCT (= HLL): 평균 오차율 1.62%
SELECT
  event_date,
  APPROX_COUNT_DISTINCT(user_id) AS approx_daily_users,
  HLL(user_id)                   AS hll_daily_users,    -- APPROX_COUNT_DISTINCT의 별칭
  COUNT(DISTINCT user_id)        AS exact_daily_users   -- 비교용
FROM events
GROUP BY event_date;

HLL 스케치 함수 (증분 집계)

-- 스케치 생성 및 저장
CREATE OR REPLACE TABLE daily_user_hll_sketches AS
SELECT
  event_date, market_segment,
  HLL_ACCUMULATE(user_id) AS hll_sketch  -- BINARY 타입으로 저장
FROM events
GROUP BY event_date, market_segment;

-- 저장된 스케치를 병합하여 월간 집계 (전체 데이터 재스캔 불필요)
SELECT
  DATE_TRUNC('month', event_date) AS month,
  market_segment,
  HLL_ESTIMATE(HLL_COMBINE(hll_sketch)) AS monthly_unique_users
FROM daily_user_hll_sketches
GROUP BY month, market_segment;

Apache DataSketches HLL (외부 시스템 호환)

-- DATASKETCHES_HLL_*: Apache DataSketches 형식으로 저장/병합 → Spark·BigQuery와 교환 가능
CREATE OR REPLACE TEMP TABLE segment_sketches AS
SELECT
  c_mktsegment,
  DATASKETCHES_HLL_ACCUMULATE(c_custkey) AS hll_sketch
FROM SNOWFLAKE_SAMPLE_DATA.TPCH_SF100.CUSTOMER
GROUP BY c_mktsegment;

SELECT
  c_mktsegment,
  DATASKETCHES_HLL_ESTIMATE(hll_sketch) AS approx_customer_count
FROM segment_sketches
ORDER BY approx_customer_count DESC;

-- 여러 세그먼트 병합
SELECT
  DATASKETCHES_HLL_ESTIMATE(DATASKETCHES_HLL_COMBINE(hll_sketch)) AS total_unique_customers
FROM segment_sketches
WHERE c_mktsegment IN ('AUTOMOBILE', 'MACHINERY');

MinHash — 유사도 추정

-- 두 고객 세그먼트의 상품 구매 패턴 유사도
WITH segment_minhash AS (
  SELECT customer_segment, MINHASH(100, product_id) AS minhash_state
  FROM purchases
  GROUP BY customer_segment
)
SELECT
  a.customer_segment AS segment_a,
  b.customer_segment AS segment_b,
  APPROXIMATE_SIMILARITY(a.minhash_state, b.minhash_state) AS jaccard_similarity
FROM segment_minhash a
CROSS JOIN segment_minhash b
WHERE a.customer_segment < b.customer_segment
ORDER BY jaccard_similarity DESC;

플랫폼 비교 요약

기능	BigQuery	Databricks	Snowflake
기본 고유값 근사	`APPROX_COUNT_DISTINCT`	`hll_sketch_estimate(hll_sketch_agg(...))`	`APPROX_COUNT_DISTINCT` / `HLL`
HLL 스케치 생성	`HLL_COUNT.INIT`	`hll_sketch_agg`	`HLL_ACCUMULATE`
HLL 스케치 병합	`HLL_COUNT.MERGE`	`hll_union_agg`	`HLL_COMBINE`
Theta 스케치	`bqutil.datasketches.*`	`theta_sketch_agg`	미지원 (네이티브)
분위수 스케치	`bqutil.datasketches.kll_*`	`kll_sketch_agg_*`	`APPROX_QUANTILES`
유사도 추정	Theta 교집합/차집합	`theta_intersect_agg`	`MINHASH`
DataSketches 호환	`bqutil.datasketches.*` (별도)	네이티브 (Spark 3.5+)	`DATASKETCHES_HLL_*`

5. 적합한 상황 / 부적합한 상황

적합한 상황 (Good Use Cases)

1. DAU/MAU 대규모 집계

Yahoo가 10년 이상 내부 프로덕션에서 수백억 건의 이벤트에서 일/월간 순방문자 수를 수초 내에 집계합니다. mParticle은 HLL 하나에 사용자 ID를 저장하고 여러 날짜의 DAU를 병합하여 MAU를 추정합니다.

2. 실시간 스트리밍 분석 대시보드

Spark Streaming + DataSketches 조합으로 단일 패스 스트림 처리합니다. Apache Druid, Apache Pinot이 DataSketches를 네이티브 통합으로 내장합니다.

3. 네트워크 트래픽 분석 (고유 IP 카운팅)

초당 수백만 패킷 처리하며 고유 IP 수 추정합니다. 전체 데이터 저장이 불필요하며, 수 KB 메모리로 수십억 개의 IP 처리가 가능합니다.

4. 광고 기술 (Ad Tech)

고유 사용자 도달 수(unique reach) 및 빈도 캡핑(frequency capping)
캠페인별 고유 노출 사용자 수 실시간 집계
A/B 테스트 메트릭 계산

5. 이커머스

상품별 고유 조회 수, 카테고리별 순방문자 집계
퍼널 분석에서 세그먼트별 중복 제거

6. 대규모 로그 분석

BigQuery, Presto, Hive와 연동하여 수백 TB 데이터를 수 초 안에 쿼리합니다.

7. 분산 시스템 집계 병합

각 노드에서 스케치를 독립 생성 후 중앙에서 병합 — exact counting 대비 핵심 차별점입니다.

부적합한 상황 (Bad Use Cases)

1. 법적/규제 요구사항이 있는 집계

"약 12억 달러"는 감사인이 수락하지 않습니다. 과금(billing), 재무 정산, 컴플라이언스 보고서에는 절대 사용할 수 없습니다.

2. 소규모 데이터셋

100만 건 미만의 데이터 → 정확한 집계가 1초 미만으로 완료됩니다. 고유 항목 수가 200개 미만 → 오차 범위가 실제 값 자체보다 클 수 있습니다.

3. 정확한 집합 구성원 정보가 필요한 경우

"약 5만 명의 고유 사용자" 추정은 가능하지만, 어떤 사용자들인지는 알 수 없습니다. 개인별 중복 제거 목록이 필요한 경우 부적합합니다.

4. 복잡한 연쇄 집합 연산

A ∩ B ∩ C ∩ D처럼 여러 세트 교집합 연산 시 오차가 누적됩니다. 세트 교집합은 합집합보다 오차가 크게 증가합니다.

"스케치가 세그먼트 간 중복 제거에 좋다"는 것은 합집합(Union) 기반 연산을 말하는 것이지, 다중 교집합(Intersection)과는 별개의 문제입니다.

왜 교집합은 오차가 커지는가?

Theta Sketch는 내부적으로 고정 크기의 샘플(예: k=4096개의 해시값)을 유지합니다.

합집합(Union): 각 스케치에서 최소 theta 값을 취하고, 그 이하의 해시값들을 합치는 "lossless" 연산입니다. A ∪ B ∪ C ∪ D를 해도 결과 스케치의 오차 범위가 개별 스케치와 동일하게 유지됩니다.
교집합(Intersection): 결과 집합이 작아질수록, 4096개 샘플 중 교집합에 해당하는 샘플이 극소수가 되어 추정이 불안정해집니다. 연쇄 교집합은 결과를 계속 줄이므로 각 단계마다 상대 오차가 증가합니다.

또한 교집합은 내부적으로 포함-배제 원리(|A∩B| = |A| + |B| - |A∪B|)로 계산되는데, 큰 수에서 큰 수를 빼는 연산이라 오차가 증폭됩니다.

연산별 오차 비교

연산	오차 특성	적합성
A ∪ B ∪ C ∪ D	오차 누적 안 됨	✅ 적합
A ∩ B (2개 교집합)	결과가 크면 괜찮을 수 있음	⚠️ 조건부 적합
A ∩ B ∩ C ∩ D (다중 교집합)	오차 누적되어 폭증	❌ 부적합

구체적 예시

시나리오: 4개 캠페인 세그먼트, 각각 100만 명
스케치 설정: k=4096 (lgK=12)

[합집합 — 오차 안정적]
A ∪ B ∪ C ∪ D = 약 350만 명
→ 4096개 샘플로 350만 명 추정 → 상대 오차 ~1.56%
→ 결과: 350만 ± 5.5만 명 (쓸 만함)

[2개 교집합 — 주의 필요]
A ∩ B = 약 20만 명
→ 4096개 샘플 중 교집합 해당 샘플: ~230개
→ 상대 오차: ~6.6%
→ 결과: 20만 ± 1.3만 명 (상황에 따라 허용 가능)

[4개 교집합 — 부적합]
A ∩ B ∩ C ∩ D = 약 1,000명
→ 4096개 샘플 중 교집합 해당 샘플: ~1개
→ 상대 오차: ~100%+
→ 결과: 1,000 ± 1,000명 이상 (사실상 무의미)

핵심: 교집합 결과의 크기가 전체 대비 작아질수록, 추정에 쓸 수 있는 유효 샘플이 줄어들어 오차가 급격히 커집니다. 합집합은 이 문제가 없습니다.

5. 재현성이 필요한 시스템

동일 데이터에 대해 연속 실행 시 결과가 다를 수 있습니다 (오차 범위 내). 재현 가능한 결과가 필요한 단위 테스트, 멱등성 요구 시스템에서 주의가 필요합니다.

6. 유사 오픈소스

비교 요약표

라이브러리	언어	카디널리티	분위수	빈도	병합 지원	특이점
Apache DataSketches	Java/C++/Python/Go	HLL, CPC (최고 정확도)	KLL, REQ	Frequent Items	네이티브 병합	올인원, Druid/Spark 통합
stream-lib	Java	HLL, LinearCount	-	CMS	가능	가볍고 단독 의존성 없음
Google HLL++ (ZetaSketch)	BigQuery/Dataflow	HLL++	-	-	제한적	Google 에코시스템 전용
Redis HyperLogLog	Redis 내장	HLL (0.81% 오차)	-	-	PFMERGE	추가 설치 없이 즉시 사용
T-Digest	Java/C++/Go/Python	-	꼬리 특화	-	병합 가능	p99+ 정확도 최고
Twitter Algebird	Scala	HLL, BloomFilter	QTree	CMS	Monoid 병합	Scala 함수형 설계
datasketch (Python)	Python	HLL, HLL++	-	-	제한적	MinHash LSH 유사도 검색 강점

각 라이브러리 상세

stream-lib (Java) — AddThis

GitHub: github.com/addthis/stream-lib
HyperLogLog, Count-Min Sketch, Bloom Filter, Top-K 포함
가볍고 단독 의존성이 없습니다
단점: DataSketches 대비 정확도가 낮고, 최근 업데이트가 드뭅니다 (사실상 유지보수 모드)

Google HLL++ / ZetaSketch

BigQuery HLL_COUNT.*, Cloud Dataflow ZetaSketch
64비트 해시 + sparse 표현으로 원본 HLL 개선
단점: Google 에코시스템에 의존하며, standalone 라이브러리로 사용하기 어렵습니다

Redis HyperLogLog

명령어: PFADD, PFCOUNT, PFMERGE
최악의 경우 12KB 메모리, 표준 오차 0.81%
장점: 기존 Redis에서 즉시 사용 가능하며, 명령어가 단순합니다
단점: 카디널리티 추정만 지원하며, 분위수/빈도 기능이 없습니다

T-Digest — Ted Dunning

GitHub: github.com/tdunning/t-digest
꼬리 분위수(p99, p99.9) 정확도에 특화되어 있습니다
Netflix, Microsoft 내부 모니터링, Elasticsearch 등에서 사용됩니다
DataSketches KLL vs T-Digest: T-Digest는 양쪽 꼬리 정확도가 높고 중간값 정확도는 낮습니다 / KLL은 균등한 정확도를 제공합니다

Twitter Algebird (Scala)

GitHub: github.com/twitter/algebird
추상대수(Monoid/Semigroup) 기반으로 설계되었습니다
HyperLogLog, Count-Min Sketch, Bloom Filter, QTree를 포함합니다
Twitter 광고 타겟팅, 그래프 PageRank, 트윗 트렌드 분석에 사용됩니다
단점: Scala/JVM 전용으로, Python/Go 환경에서는 사용할 수 없습니다

datasketch (Python)

GitHub: github.com/ekzhu/datasketch
MinHash LSH (Locality Sensitive Hashing) 유사도 검색에 특화되어 있습니다
단점: 분위수/빈도 스케치가 포함되어 있지 않습니다

DataSketches를 선택하는 이유

다언어 지원: Java, C++, Python, Go — 동일 직렬화 포맷으로 언어 간 병합이 가능합니다
알고리즘 다양성: 카디널리티(HLL/CPC), 분위수(KLL/REQ), 빈도(Frequent Items), Theta, Tuple — 한 라이브러리에서 지원됩니다
정확도 우위: Clearspring HLL++ 대비 오차 특성이 우수합니다
엔터프라이즈 통합: Apache Druid, Spark, Hive, BigQuery, Impala, PostgreSQL 어댑터가 공식으로 제공됩니다
이론적 검증: 알고리즘별 오차 하한 보장이 공식 문서화되어 있습니다

다른 라이브러리를 선택하는 경우

Redis HLL → 기존 Redis 인프라에서 즉시, 추가 라이브러리 없이 고유 카운팅만 필요
T-Digest → p99/p99.9 꼬리 레이턴시 모니터링 전용
Twitter Algebird → Scala/Scalding 기반 파이프라인에서 Monoid 추상화 활용
stream-lib → 레거시 Java 프로젝트에서 가벼운 단독 라이브러리 필요

7. 실전 예시: 테이블 A에 DataSketches 적용

테이블 스키마

-- 테이블 A: 이커머스 사용자 행동 로그
CREATE TABLE A (
  category         STRING,     -- 상품 카테고리 (예: 'electronics', 'fashion')
  user_id          STRING,     -- 고유 사용자 식별자
  insert_timestamp TIMESTAMP,  -- 이벤트 발생 시각
  page_path        STRING,     -- 방문 페이지 경로 (예: '/product/123')
  goods_no         STRING,     -- 상품 번호
  platform         STRING      -- 접속 플랫폼 ('mobile', 'web', 'app')
);

카디널리티 설정 기준

대상 컬럼	예상 고유값 수	lgK (HLL)	오차율	메모리
`user_id`	수백만~수천만	12	~0.8%	~2.5KB
`goods_no`	수만~수십만	10	~1.6%	~0.6KB
`page_path`	수천~수만	10	~1.6%	~0.6KB
`category`	수십~수백 (소규모)	8	~3.2%	~0.2KB

lgK가 클수록 정확하지만 메모리가 늘어납니다. user_id처럼 고유값이 수천만에 달하는 경우 lgK=12를 사용하고, goods_no·page_path처럼 상대적으로 적은 경우 lgK=10으로 설정합니다.

Python 예시

1. HLL 스케치 — 카디널리티 추정

import pandas as pd
from datasketches import hll_sketch, hll_union
from collections import defaultdict

df = pd.read_parquet("table_a.parquet")

# ── 1-1. 일별 고유 사용자 수 (DAU) ──────────────────────────
daily_user_sketches = defaultdict(lambda: hll_sketch(lg_config_k=12))

for _, row in df.iterrows():
    date_key = row["insert_timestamp"].date().isoformat()  # 'YYYY-MM-DD'
    daily_user_sketches[date_key].update(row["user_id"])

print("=== 일별 DAU (고유 사용자 수) ===")
for date, sketch in sorted(daily_user_sketches.items()):
    lower = sketch.get_lower_bound(num_std_devs=2)
    upper = sketch.get_upper_bound(num_std_devs=2)
    print(f"  {date}: {sketch.get_estimate():>10,.0f}명  [95% CI: {lower:,.0f} ~ {upper:,.0f}]")

# ── 1-2. 카테고리별 고유 사용자 수 ──────────────────────────
category_user_sketches = defaultdict(lambda: hll_sketch(lg_config_k=12))

for _, row in df.iterrows():
    category_user_sketches[row["category"]].update(row["user_id"])

print("\n=== 카테고리별 고유 사용자 수 ===")
for cat, sketch in sorted(category_user_sketches.items()):
    print(f"  {cat:20s}: {sketch.get_estimate():>8,.0f}명")

# ── 1-3. 플랫폼별 고유 상품 조회 수 (goods_no 기준) ─────────
platform_goods_sketches = defaultdict(lambda: hll_sketch(lg_config_k=10))

for _, row in df.iterrows():
    if pd.notna(row["goods_no"]):
        platform_goods_sketches[row["platform"]].update(row["goods_no"])

print("\n=== 플랫폼별 고유 상품 조회 수 ===")
for platform, sketch in sorted(platform_goods_sketches.items()):
    print(f"  {platform:8s}: {sketch.get_estimate():>8,.0f}개")

# ── 1-4. MAU 계산: 일별 스케치를 병합 (전체 데이터 재스캔 없이) ──
union = hll_union(lg_max_k=12)
for sketch in daily_user_sketches.values():
    union.update(sketch)

print(f"\n=== 월간 고유 사용자 수 (MAU) ===")
print(f"  전체 기간 MAU: {union.get_result().get_estimate():,.0f}명")

2. Theta 스케치 — 플랫폼 / 카테고리 간 집합 연산

from datasketches import update_theta_sketch, theta_union, theta_intersection, theta_a_not_b

# ── 2-1. 플랫폼 간 중복 사용자 분석 ─────────────────────────
platform_sketches = {}
for platform in df["platform"].unique():
    sketch = update_theta_sketch(lg_k=12)
    for uid in df[df["platform"] == platform]["user_id"]:
        sketch.update(uid)
    platform_sketches[platform] = sketch

# mobile과 web 모두 사용한 사용자 (교집합)
intersect_op = theta_intersection()
intersect_op.update(platform_sketches["mobile"])
intersect_op.update(platform_sketches["web"])
mobile_and_web = intersect_op.get_result().get_estimate()

# mobile만 사용한 사용자 (차집합)
a_not_b_op = theta_a_not_b()
mobile_only = a_not_b_op.compute(
    platform_sketches["mobile"],
    platform_sketches["web"]
).get_estimate()

# 전체 고유 사용자 (합집합)
union_op = theta_union()
for sketch in platform_sketches.values():
    union_op.update(sketch)
total_unique = union_op.get_result().get_estimate()

print("=== 플랫폼 중복 사용자 분석 ===")
print(f"  mobile ∩ web (크로스 플랫폼 사용자): {mobile_and_web:>8,.0f}명")
print(f"  mobile only (mobile 전용 사용자):   {mobile_only:>8,.0f}명")
print(f"  전체 고유 사용자 (합집합):            {total_unique:>8,.0f}명")

# ── 2-2. 카테고리 간 교차 방문 사용자 분석 ──────────────────
category_sketches = {}
for cat in df["category"].unique():
    sketch = update_theta_sketch(lg_k=12)
    for uid in df[df["category"] == cat]["user_id"]:
        sketch.update(uid)
    category_sketches[cat] = sketch

categories = list(category_sketches.keys())
print("\n=== 카테고리 간 교차 방문 사용자 수 ===")
for i in range(len(categories)):
    for j in range(i + 1, len(categories)):
        cat_a, cat_b = categories[i], categories[j]
        intersect = theta_intersection()
        intersect.update(category_sketches[cat_a])
        intersect.update(category_sketches[cat_b])
        overlap = intersect.get_result().get_estimate()
        print(f"  {cat_a} ∩ {cat_b}: {overlap:>8,.0f}명")

3. Frequent Items 스케치 — 인기 상품 / 페이지 탐지

from datasketches import frequent_strings_sketch, frequent_items_error_type

# ── 3-1. 가장 많이 조회된 상품 (goods_no) ────────────────────
goods_sketch = frequent_strings_sketch(max_map_size=64)
for goods_no in df["goods_no"].dropna():
    goods_sketch.update(goods_no)

print("=== 인기 상품 Top-10 ===")
for item in goods_sketch.get_frequent_items(
    frequent_items_error_type.NO_FALSE_POSITIVES
)[:10]:
    print(f"  goods_no={item.get_item():15s}: "
          f"추정 {item.get_estimate():>8,}회 "
          f"[{item.get_lower_bound():,} ~ {item.get_upper_bound():,}]")

# ── 3-2. 가장 많이 방문된 페이지 경로 (page_path) ────────────
page_sketch = frequent_strings_sketch(max_map_size=64)
for path in df["page_path"]:
    page_sketch.update(path)

print("\n=== 인기 페이지 Top-10 ===")
for item in page_sketch.get_frequent_items(
    frequent_items_error_type.NO_FALSE_POSITIVES
)[:10]:
    print(f"  {item.get_item():35s}: {item.get_estimate():>8,}회")

# ── 3-3. 카테고리별 인기 상품 분리 집계 ─────────────────────
category_goods_sketches = defaultdict(lambda: frequent_strings_sketch(64))
for _, row in df.iterrows():
    if pd.notna(row["goods_no"]):
        category_goods_sketches[row["category"]].update(row["goods_no"])

print("\n=== 카테고리별 인기 상품 1위 ===")
for cat, sketch in sorted(category_goods_sketches.items()):
    items = sketch.get_frequent_items(frequent_items_error_type.NO_FALSE_POSITIVES)
    if items:
        top1 = items[0]
        print(f"  [{cat}] 1위: goods_no={top1.get_item()} ({top1.get_estimate():,}회)")

4. KLL 스케치 — 시간대별 트래픽 분포 분석

from datasketches import kll_ints_sketch

# insert_timestamp의 시간(hour) 분포로 피크 시간대 파악
hour_sketch = kll_ints_sketch(k=200)
for ts in df["insert_timestamp"]:
    hour_sketch.update(int(ts.hour))

print("=== 트래픽 시간대 분포 ===")
print(f"  Q1 (25th): {hour_sketch.get_quantile(0.25):.0f}시")
print(f"  중앙값:    {hour_sketch.get_quantile(0.50):.0f}시")
print(f"  Q3 (75th): {hour_sketch.get_quantile(0.75):.0f}시")

# 시간대별 트래픽 히스토그램
split_points = list(range(1, 24))
pmf = hour_sketch.get_pmf(split_points)
print("\n=== 시간대별 트래픽 비중 ===")
for hour, prob in enumerate(pmf):
    bar = '█' * int(prob * 150)
    print(f"  {hour:02d}시: {prob:5.1%}  {bar}")

# 플랫폼별 피크 시간 비교
print("\n=== 플랫폼별 피크 시간 (P75) ===")
for platform in df["platform"].unique():
    sketch_p = kll_ints_sketch(k=200)
    for ts in df[df["platform"] == platform]["insert_timestamp"]:
        sketch_p.update(int(ts.hour))
    peak = sketch_p.get_quantile(0.75)
    print(f"  {platform:8s}: P75 = {peak:.0f}시")

5. 일별 스케치 저장 + 월간 증분 병합 패턴

import pickle
from pathlib import Path

def save_daily_sketches(df_daily: pd.DataFrame, date_str: str, output_dir: str):
    """매일 실행: 당일 데이터로 스케치 생성 후 저장"""
    sketches = {
        "user_hll":  hll_sketch(lg_config_k=12),
        "goods_hll": hll_sketch(lg_config_k=10),
        "page_fi":   frequent_strings_sketch(64),
        "goods_fi":  frequent_strings_sketch(64),
        "hour_kll":  kll_ints_sketch(k=200),
    }
    for _, row in df_daily.iterrows():
        sketches["user_hll"].update(row["user_id"])
        if pd.notna(row["goods_no"]):
            sketches["goods_hll"].update(row["goods_no"])
            sketches["goods_fi"].update(row["goods_no"])
        sketches["page_fi"].update(row["page_path"])
        sketches["hour_kll"].update(int(row["insert_timestamp"].hour))

    output = {
        "user_hll":  sketches["user_hll"].serialize_compact(),
        "goods_hll": sketches["goods_hll"].serialize_compact(),
        "page_fi":   sketches["page_fi"].serialize(),
        "goods_fi":  sketches["goods_fi"].serialize(),
        "hour_kll":  sketches["hour_kll"].serialize(),
    }
    Path(output_dir).mkdir(parents=True, exist_ok=True)
    with open(f"{output_dir}/{date_str}.pkl", "wb") as f:
        pickle.dump(output, f)
    print(f"[{date_str}] 스케치 저장 완료")

def compute_monthly_metrics(output_dir: str) -> dict:
    """저장된 일별 스케치를 병합하여 월간 메트릭 계산 (전체 재스캔 없이)"""
    user_union  = hll_union(lg_max_k=12)
    goods_union = hll_union(lg_max_k=10)
    hour_kll    = kll_ints_sketch(k=200)

    for pkl_file in sorted(Path(output_dir).glob("*.pkl")):
        with open(pkl_file, "rb") as f:
            data = pickle.load(f)
        user_union.update(hll_sketch.deserialize(data["user_hll"]))
        goods_union.update(hll_sketch.deserialize(data["goods_hll"]))
        hour_kll.merge(kll_ints_sketch.deserialize(data["hour_kll"]))

    return {
        "monthly_unique_users":  user_union.get_result().get_estimate(),
        "monthly_unique_goods":  goods_union.get_result().get_estimate(),
        "peak_hour_p75":         hour_kll.get_quantile(0.75),
    }

# 사용 예시
# save_daily_sketches(df[df["insert_timestamp"].dt.date == today], "2026-04-07", "./sketches/2026-04")
# metrics = compute_monthly_metrics("./sketches/2026-04/")
# print(f"MAU:        {metrics['monthly_unique_users']:,.0f}명")
# print(f"고유 상품:   {metrics['monthly_unique_goods']:,.0f}개")
# print(f"피크 시간대: {metrics['peak_hour_p75']:.0f}시")

BigQuery SQL 예시

-- ── 1. 일별 × 플랫폼별 DAU 집계 ──────────────────────────────
SELECT
  DATE(insert_timestamp)          AS event_date,
  platform,
  APPROX_COUNT_DISTINCT(user_id)  AS approx_dau,
  APPROX_COUNT_DISTINCT(goods_no) AS approx_unique_goods_viewed,
  COUNT(*)                        AS total_events
FROM A
GROUP BY event_date, platform
ORDER BY event_date, platform;

-- ── 2. HLL 스케치 저장 테이블 생성 (lgK=12 ≈ precision 15 in BigQuery) ──
CREATE OR REPLACE TABLE A_daily_sketches AS
SELECT
  DATE(insert_timestamp)          AS event_date,
  category,
  platform,
  HLL_COUNT.INIT(user_id, 15)     AS user_sketch,   -- DAU용
  HLL_COUNT.INIT(goods_no, 13)    AS goods_sketch   -- 고유 상품 조회용
FROM A
GROUP BY event_date, category, platform;

-- ── 3. 저장된 스케치로 MAU 계산 (전체 데이터 재스캔 불필요) ────
SELECT
  DATE_TRUNC(event_date, MONTH)            AS month,
  category,
  HLL_COUNT.MERGE(user_sketch)             AS monthly_unique_users,
  HLL_COUNT.MERGE(goods_sketch)            AS monthly_unique_goods
FROM A_daily_sketches
GROUP BY month, category
ORDER BY month, category;

-- ── 4. Theta 스케치: mobile과 web 모두 사용한 사용자 수 ────────
SELECT
  bqutil.datasketches.theta_sketch_get_estimate(
    bqutil.datasketches.theta_sketch_intersection(
      mobile_sketch, web_sketch
    )
  ) AS mobile_and_web_users
FROM (
  SELECT
    bqutil.datasketches.theta_sketch_agg_string(
      IF(platform = 'mobile', user_id, NULL)
    ) AS mobile_sketch,
    bqutil.datasketches.theta_sketch_agg_string(
      IF(platform = 'web', user_id, NULL)
    ) AS web_sketch
  FROM A
  WHERE DATE(insert_timestamp) = CURRENT_DATE()
);

-- ── 5. 카테고리별 인기 상품 Top-10 ───────────────────────────
SELECT
  category,
  top_goods.value  AS goods_no,
  top_goods.count  AS view_count
FROM (
  SELECT
    category,
    APPROX_TOP_COUNT(goods_no, 10) AS top_goods_arr
  FROM A
  WHERE DATE(insert_timestamp) >= DATE_SUB(CURRENT_DATE(), INTERVAL 7 DAY)
    AND goods_no IS NOT NULL
  GROUP BY category
),
UNNEST(top_goods_arr) AS top_goods
ORDER BY category, top_goods.count DESC;

-- ── 6. 카테고리별 인기 페이지 Top-5 ──────────────────────────
SELECT
  category,
  top_page.value  AS page_path,
  top_page.count  AS visit_count
FROM (
  SELECT
    category,
    APPROX_TOP_COUNT(page_path, 5) AS top_pages
  FROM A
  GROUP BY category
),
UNNEST(top_pages) AS top_page
ORDER BY category, top_page.count DESC;

Databricks SQL 예시

-- ── 1. 일별 × 플랫폼별 DAU 스케치 집계 ──────────────────────
SELECT
  CAST(insert_timestamp AS DATE)                     AS event_date,
  platform,
  hll_sketch_estimate(hll_sketch_agg(user_id,  12))  AS approx_dau,
  hll_sketch_estimate(hll_sketch_agg(goods_no, 10))  AS approx_unique_goods
FROM A
GROUP BY event_date, platform
ORDER BY event_date, platform;

-- ── 2. HLL 스케치 저장 테이블 생성 ───────────────────────────
CREATE OR REPLACE TABLE A_daily_sketches AS
SELECT
  CAST(insert_timestamp AS DATE)  AS event_date,
  category,
  platform,
  hll_sketch_agg(user_id,  12)    AS user_sketch,
  hll_sketch_agg(goods_no, 10)    AS goods_sketch
FROM A
GROUP BY event_date, category, platform;

-- ── 3. MAU: 일별 스케치를 월 단위로 병합 ─────────────────────
SELECT
  DATE_TRUNC('month', event_date)                     AS month,
  category,
  hll_sketch_estimate(hll_union_agg(user_sketch))      AS monthly_unique_users,
  hll_sketch_estimate(hll_union_agg(goods_sketch))     AS monthly_unique_goods
FROM A_daily_sketches
GROUP BY month, category
ORDER BY month, category;

-- ── 4. Theta 스케치: 카테고리 간 교차 방문 사용자 수 ──────────
WITH cat_sketches AS (
  SELECT
    category,
    theta_sketch_agg(user_id, 12) AS sketch
  FROM A
  WHERE CAST(insert_timestamp AS DATE) = CURRENT_DATE()
  GROUP BY category
)
SELECT
  a.category  AS cat_a,
  b.category  AS cat_b,
  theta_sketch_estimate(
    theta_intersect_agg(a.sketch)
  )           AS overlap_users
FROM cat_sketches a
JOIN cat_sketches b ON a.category < b.category
GROUP BY cat_a, cat_b
ORDER BY overlap_users DESC;

-- ── 5. 플랫폼별 exclusive 사용자 비중 ────────────────────────
WITH platform_sketches AS (
  SELECT platform, theta_sketch_agg(user_id, 12) AS sketch
  FROM A
  GROUP BY platform
),
union_sketch AS (
  SELECT theta_union_agg(sketch) AS all_sketch FROM platform_sketches
)
SELECT
  p.platform,
  theta_sketch_estimate(p.sketch)      AS platform_users,
  theta_sketch_estimate(u.all_sketch)  AS total_users,
  ROUND(
    theta_sketch_estimate(p.sketch) /
    theta_sketch_estimate(u.all_sketch) * 100, 1
  )                                    AS pct_of_total
FROM platform_sketches p
CROSS JOIN union_sketch u
ORDER BY platform_users DESC;

-- ── 6. 시간대별 트래픽 분포 (KLL 스케치) ─────────────────────
SELECT
  platform,
  kll_sketch_get_quantile(sketch, 0.25) AS p25_hour,
  kll_sketch_get_quantile(sketch, 0.50) AS median_hour,
  kll_sketch_get_quantile(sketch, 0.75) AS p75_hour
FROM (
  SELECT
    platform,
    kll_sketch_agg_bigint(HOUR(insert_timestamp)) AS sketch
  FROM A
  GROUP BY platform
);

8. 정리

핵심 요약

스케치 종류	해결 문제	오차 보장	메모리
HLL / CPC	COUNT DISTINCT	±0.8~2%	2~6KB
KLL	PERCENTILE / MEDIAN	순위 오차 ±0.1%	수십KB
Theta	집합 연산 (합집합/교집합/차집합)	±1.56%	~32KB
Frequent Items	Heavy Hitters (빈발 항목)	결정론적 상하한	수KB
Tuple	Theta + 연관 데이터 집계	Theta와 동일	가변

의사결정 가이드

데이터가 수억 건 이상인가? + 속도가 중요한가?
├── YES → 스케치 사용
│   ├── 고유값 카운팅 → HLL 또는 CPC 스케치
│   ├── 분위수/백분위 → KLL 스케치
│   ├── 집합 연산 → Theta 스케치
│   └── 빈발 항목 → Frequent Items 스케치
└── NO (소규모, 정확도 최우선) → 기존 SQL 사용

분산 환경인가?
├── YES → 직렬화 + 병합 패턴 활용
└── NO → 단순 업데이트 + 조회

정확도 요건
├── 법적/금융/컴플라이언스 → 사용 금지
└── 분석/모니터링/대시보드 → 스케치 적합

참고 링크

공식 사이트: https://datasketches.apache.org/
Python 라이브러리: https://github.com/apache/datasketches-python
BigQuery DataSketches: https://cloud.google.com/blog/products/data-analytics/bigquery-supports-apache-datasketches-for-approximate-analytics
Databricks 블로그: https://www.databricks.com/blog/apache-spark-3-apache-datasketches-new-sketch-based-approximate-distinct-counting

저작자표시 (새창열림)

ABOUT ME

0. 개요

1. Apache DataSketches란?

한 줄 정의

등장 배경

핵심 스케치 종류

HLL 스케치 (HyperLogLog) — 카디널리티 추정

CPC 스케치 (Compressed Probabilistic Counting)

Theta 스케치 — 카디널리티 + 집합 연산

KLL 스케치 (Karnin-Lang-Liberty) — 분위수 추정

Frequent Items 스케치 — 빈발 항목 탐지

Tuple 스케치 — 연관 데이터 포함 집합 연산

메모리 효율성 비교

핵심 설계 원칙

2. 기존 SQL 호출과의 차이점

COUNT DISTINCT vs HLL 스케치

PERCENTILE vs KLL 스케치

집합 연산 (GROUP BY INTERSECT) vs Theta 스케치

성능 종합 비교

SQL로 충분한 경우 vs 스케치가 필요한 경우

3. Python 사용법

설치

HLL 스케치 — 카디널리티 추정

KLL 스케치 — 분위수/백분위수 추정

Theta 스케치 — 집합 연산

Frequent Items 스케치 — 빈발 항목 탐지

분산 시스템에서의 병합 패턴

4. BigQuery / Databricks / Snowflake 예시

BigQuery

내장 근사 집계 함수

HLL++ 스케치 함수 (증분 집계 + 저장)

Apache DataSketches for BigQuery (bqutil)

Databricks (Spark 3.5+ / Databricks Runtime 13.0+)

네이티브 SQL 함수

PySpark + Python datasketches 라이브러리

Snowflake

내장 근사 집계 함수

HLL 스케치 함수 (증분 집계)

Apache DataSketches HLL (외부 시스템 호환)

MinHash — 유사도 추정

플랫폼 비교 요약

5. 적합한 상황 / 부적합한 상황

적합한 상황 (Good Use Cases)

1. DAU/MAU 대규모 집계

2. 실시간 스트리밍 분석 대시보드

3. 네트워크 트래픽 분석 (고유 IP 카운팅)

4. 광고 기술 (Ad Tech)

5. 이커머스

6. 대규모 로그 분석

7. 분산 시스템 집계 병합

부적합한 상황 (Bad Use Cases)

1. 법적/규제 요구사항이 있는 집계

2. 소규모 데이터셋

3. 정확한 집합 구성원 정보가 필요한 경우

4. 복잡한 연쇄 집합 연산

왜 교집합은 오차가 커지는가?

연산별 오차 비교

구체적 예시

5. 재현성이 필요한 시스템

6. 유사 오픈소스

비교 요약표

각 라이브러리 상세

stream-lib (Java) — AddThis

Google HLL++ / ZetaSketch

Redis HyperLogLog

T-Digest — Ted Dunning

Twitter Algebird (Scala)

datasketch (Python)

DataSketches를 선택하는 이유

다른 라이브러리를 선택하는 경우

7. 실전 예시: 테이블 A에 DataSketches 적용

테이블 스키마

카디널리티 설정 기준

Python 예시

1. HLL 스케치 — 카디널리티 추정

2. Theta 스케치 — 플랫폼 / 카테고리 간 집합 연산

3. Frequent Items 스케치 — 인기 상품 / 페이지 탐지

4. KLL 스케치 — 시간대별 트래픽 분포 분석

5. 일별 스케치 저장 + 월간 증분 병합 패턴

BigQuery SQL 예시