[SQL] MySLQ에서 median 구현 + 대규모, 스트리밍 환경에서 전략

MySQL에서의 mdeian() 구현

MEDIAN을 구하는 건 사실상 정렬 기반 연산이라서, 데이터가 커질수록 비용이 크게 올라가는 작업이다.
대규모 데이터 환경에서는 "정확한 중앙값"을 그대로 구하는 것보다 효율적인 근사치(approximation) 또는 분산 처리 전략을 많이 쓴다.

---

1. SQL 레벨에서의 정확한 계산

ROW_NUMBER()기반 중앙 위치 찾는 방법

WITH numbered AS (
    SELECT 
        class_id,
        score,
        ROW_NUMBER() OVER (PARTITION BY class_id ORDER BY score) AS rn,
        COUNT(*) OVER (PARTITION BY class_id) AS cnt
    FROM students
)
SELECT 
    class_id,
    AVG(score) AS median
FROM numbered
WHERE rn IN (FLOOR((cnt + 1)/2), CEIL((cnt + 1)/2))
GROUP BY class_id;

문제점: Median은 정렬(ORDER BY)이 필수 → O(N log N) 비용.

MySQL에서 ROW_NUMBER() + COUNT() 방식은 정확하지만, 테이블 풀스캔 + 정렬이 필요 → 수억 건 데이터에서는 비효율적.

사용 경우: 그룹별 데이터 크기가 수십만 행 이하일 때 적합하다.

분산 처리 환경 (Spark, Hive, BigQuery)

대규모 데이터에서는 보통 분산 프레임워크가 필요하다.

핵심 원리: approximate percentile 계산 과정

1. 데이터를 모두 정렬하지 않음

   • 전체 데이터를 정렬하면 비용이 O(NlogN) → 대규모 환경에서 비효율적
   • 대신 스트림처럼 데이터를 한 번 훑으면서 요약(summary) 구조를 만듦

2. 분포 요약(histogram / t-digest / GK 구조)

   • 각 데이터 값을 여러 개의 버킷(bucket) 혹은 클러스터(cluster)로 압축
   • 각 버킷에는 범위(range)와 빈도(frequency) 정보를 기록
   • 즉, 데이터 전체를 저장하지 않고 분포를 대표할 수 있는 요약 구조만 유지

3. 누적 빈도로 percentile 계산

   • 예: 50% percentile(중앙값) → 전체 누적 빈도에서 중간 위치를 가진 버킷 선택
   • 필요하면 버킷 내 선형 보간(linear interpolation)으로 정확도를 조금 더 높임

이렇게 하면 정렬 비용 없이 대규모 데이터에서도 근사 percentile을 빠르게 계산할 수 있다.

1. Spark SQL

• percentile_approx(col, 0.5) 함수 제공 → median 근사치를 빠르게 계산.
• approx_percentile 알고리즘은 t-digest나 histogram binning 기반 → 큰 데이터셋에서도 스케일링 가능.

SELECT 
    class_id,
    percentile_approx(score, 0.5) AS median
FROM students
GROUP BY class_id;

2. Hive

percentile_approx(col, p) 함수 사용 (Spark와 동일한 원리).

3. BigQuery

APPROX_QUANTILES(col, 100)[OFFSET(50)] 로 중앙값 근사치 계산 가능.

공통적으로 approximate percentile 함수를 쓰는 게 정석이라고 보면 됨.

스트리밍 & 온라인 환경

실시간 데이터 스트림(예: Kafka → Flink → Sink)에서 중앙값을 구해야 할 때는 데이터를 다 저장하고 정렬하는 게 불가능하므로, 스트리밍 알고리즘을 사용한다.

1. t-digest

• 구글에서 제안한 확률 분포 압축 알고리즘.
• 스트리밍 데이터에서도 median, percentile 계산 가능.
• Spark, Flink, Elasticsearch 등에서 이미 구현돼 있음.

2. GK 알고리즘 (Greenwald-Khanna)

• 스트리밍 데이터에서 ε-approximate quantile 추정.
• 메모리 사용량:$O\Big(\frac{1}{\varepsilon} \cdot \log(\varepsilon N)\Big)$
  → 허용 오차 ε에 따라 메모리 조정 가능, 데이터량 N이 커져도 로그 스케일로 증가 → 대규모 환경에서 효율적.

전략별 비교

접근 방식	장점	단점	적용 환경
ROW_NUMBER() 기반 정확 median	정확	정렬 비용 큼, 느림	소규모~중규모
NTILE(2) 기반	구현 쉬움, 근사치 가능	홀수일 때 오차 발생	빠른 근사 필요 시
percentile_approx / approx_quantiles	매우 빠름, 대규모 분산 환경 적합	근사치 (하지만 오차 작음)	Spark, Hive, BigQuery
t-digest, GK 알고리즘	스트리밍/실시간 처리 가능	구현 난이도 있음	실시간 데이터 파이프라인