고유 값 개수 추정하기¶

개요¶

Snowflake는 Flajolet 외가 제안한 HyperLogLog: 최적에 가까운 카디널리티 추정 알고리즘 분석 에서 제공된 HyperLogLog 알고리즘의 편향을 수정한 구현을 제공합니다.

Snowflake는 입력이 클 수 있고 대략적인 결과가 허용되는 경우 항상 HyperLogLog를 사용하는 것을 권장합니다. HyperLogLog 구현의 평균 상대 오차는 1.62338%입니다(즉, 해당 COUNT(DISTINCT …) 결과에 대한 평균 상대 차이).

SQL 함수¶

HyperLogLog를 사용하여 카디널리티를 추정하기 위해서는 다음 집계 함수 이 제공됩니다.

• HLL: 입력의 고유 카디널리티에 대한 추정값을 반환합니다.

• HLL_ACCUMULATE: 최종 추정 단계를 건너뛰고 집계의 마지막에 HyperLogLog 상태를 반환합니다.

• HLL_COMBINE: 입력 상태를 단일 출력 상태로 결합(즉, 병합)합니다.

• HLL_ESTIMATE: HLL_ACCUMULATE 및 HLL_COMBINE에 의해 생성된 HyperLogLog 상태의 카디널리티 추정을 계산합니다.

• HLL_EXPORT: HyperLogLog 상태를 BINARY 형식에서 OBJECT 형식으로 변환합니다(이후에 인쇄하고 JSON으로 내보낼 수 있음).

• HLL_IMPORT: HyperLogLog 상태를 OBJECT 형식에서 BINARY 형식으로 변환합니다.

구현 세부 정보¶

Snowflake의 구현은 입력 행을 64비트 값으로 해시하며, 그 중 상위 12비트 또는 《전체 자릿수》(HyperLogLog 알고리즘 설명서 참조, 자세한 내용은 위 문서 링크 참조)를 사용하여 입력 값을 서브 스트림으로 분할합니다. 이를 통해 다음과 같은 평균 상대 오차가 제공됩니다.

sqrt(3\*ln(2)-1)/sqrt(2^precision) = 0.0162338 = 1.62338%

즉, COUNT(DISTINCT …) 에서 1,000,000 의 결과가 반환되는 쿼리의 경우, HyperLogLog는 일반적으로 983,767 ~ 1,016,234 범위 내의 결과를 반환합니다.

각 서브 스트림에서, HyperLogLog는 최대 선행 0 개수(최대 자릿수 = 12에서 64비트 값의 경우 0~52 사이)를 유지합니다. 이러한 상태의 가장 직접적인 표현은 단순한 바이트 배열이며 각 2^12 = 4096 서브 스트림은 1바이트입니다. Snowflake 구현에서는 집계 그룹당 최대 4096바이트(2^precision = 2^12 = 4096)의 메모리가 필요합니다. 기술적으로는 서브 스트림당 6비트(8비트 아님)만 필요하지만, 계산의 효율성을 위해 공간 효율성을 약간 희생합니다.

소규모 입력 카디널리티의 경우 대부분의 서브 스트림은 적중하지 않습니다. 그러므로 집계 그룹당 4096바이트의 전체 블록을 사전에 할당하는 대신, Snowflake 구현에서는 이 상태의 공간 최적화 《스파스》 표현이 유용할 때마다 사용됩니다. 결과적으로, HyperLogLog의 메모리 비용은 집계 그룹당 4096바이트(집계 그룹당 최저 약 32바이트)보다 상당히 낮을 수 있습니다. 이를 통해 해당 COUNT(DISTINCT …) 쿼리에 비해 훨씬 더 낮은 메모리 사용량과 CPU 시간을 사용하여 여러 집계 그룹(수백만 개 또는 수십억 개, 쿼리의 GROUP BY 또는 OVER 절에 따라)에 대한 카디널리티를 추정할 수 있습니다.

매우 큰 입력 테이블 및 여러 집계 그룹으로 인해 HyperLogLog가 총 메모리 예산을 초과하는 (드문) 경우에도 Snowflake는 기타 집계 함수에서와 마찬가지로 임시 공간으로 분할하여 재귀적 집계를 실행합니다.

내보낸 상태 형식¶

HyperLogLog 알고리즘의 상태는 HLL_EXPORT 및 HLL_IMPORT 함수를 사용하여 각각 내보내고 가져올 수 있습니다(또는 다시 가져오기). 내보낸 상태의 타입은 OBJECT이며 다음 필드가 포함됩니다.

예¶

환경 설정:

USE WAREHOUSE dontdrop;
USE DATABASE stressdb;
USE SCHEMA bdb_5nodes;

SELECT COUNT(*) FROM uservisits;

-----------+
 COUNT(*)  |
-----------+
 751754869 |
-----------+

Copy

1단계:

날짜(연/월/일) 및 HLL 구조가 포함된 테이블을 만듭니다. 여기에서는 HLL_EXPORT 를 사용하여 바이너리 구조를 텍스트 오브젝트로 저장합니다.

CREATE OR REPLACE TABLE daily_uniques
AS
SELECT
 visitdate,
 hll_export(hll_accumulate(sourceip)) AS hll_sourceip
FROM uservisits
GROUP BY visitdate;

Copy

2단계:

1단계에서 각 날짜의 HLL 구조를 집계하여 월별 고유 IPs를 계산할 수 있습니다. HLL_IMPORT 를 사용하여 텍스트를 바이너리 구조로 변환한 후 HLL_COMBINE 을 사용하여 여러 HLL 구조를 단일 구조로 결합한 후 HLL_ESTIMATE 를 사용하여 고유 값의 개수를 계산합니다.

SELECT
  EXTRACT(year FROM visitdate) AS visit_year,
  EXTRACT(month FROM visitdate) AS visit_month,
  hll_estimate(hll_combine(hll_import(hll_sourceip))) AS distinct_ips
FROM daily_uniques
WHERE visitdate BETWEEN '2000-01-01' AND '2000-12-31'
GROUP BY 1,2
ORDER BY 1,2;

------------+-------------+--------------+
 VISIT_YEAR | VISIT_MONTH | DISTINCT_IPS |
------------+-------------+--------------+
       2000 |           1 |      1515168 |
       2000 |           2 |      1410289 |
       2000 |           3 |      1491997 |
       2000 |           4 |      1460837 |
       2000 |           5 |      1546647 |
       2000 |           6 |      1485599 |
       2000 |           7 |      1522643 |
       2000 |           8 |      1492831 |
       2000 |           9 |      1488507 |
       2000 |          10 |      1553201 |
       2000 |          11 |      1461140 |
       2000 |          12 |      1515772 |
------------+-------------+--------------+

Elapsed 1.3s

Copy

비교:

세부 수준 데이터에서 HLL 함수를 사용한 집계와 HLL을 사용한 집계 사용을 비교해 보겠습니다. 이 경우, HLL() 은 2단계의 HLL_ESTIMATE(HLL_COMBINE(HLL_IMPORT())) 에 해당합니다.

SELECT
  EXTRACT(year FROM visitdate) AS visit_year,
  EXTRACT(month FROM visitdate) AS visit_month,
  hll(sourceip) AS distinct_ips
FROM uservisits
WHERE visitdate BETWEEN '2000-01-01' AND '2000-12-31'
GROUP BY 1,2
ORDER BY 1,2;

------------+-------------+--------------+
 VISIT_YEAR | VISIT_MONTH | DISTINCT_IPS |
------------+-------------+--------------+
       2000 |           1 |      1515168 |
       2000 |           2 |      1410289 |
       2000 |           3 |      1491997 |
       2000 |           4 |      1460837 |
       2000 |           5 |      1546647 |
       2000 |           6 |      1485599 |
       2000 |           7 |      1522643 |
       2000 |           8 |      1492831 |
       2000 |           9 |      1488507 |
       2000 |          10 |      1553201 |
       2000 |          11 |      1461140 |
       2000 |          12 |      1515772 |
------------+-------------+--------------+

Elapsed 2m 29s

Copy

보시다시피, HLL 구조의 집계는 기준 데이터에서의 집계에서 속도가 훨씬 빠르며(예: 이러한 소규모 예에서 1.3초 vs 149초), 이는 쿼리 시간이 100배 감소함을 나타냅니다.