자주 나타나는 값 추정하기¶

개요¶

Snowflake는 Metwally, Agrawal 및 Abbadi가 제안한 데이터 스트림에서 빈도 및 상위 k 요소의 효율적인 계산 에서 제공되는 Space-Saving 알고리즘의 구현을 제공합니다. 이는 함수의 APPROX_TOP_K 패밀리를 통해 구현됩니다.

또한, APPROX_TOP_K_COMBINE 함수에서는 Cafaro, Pulimeno 및 Tempesta가 제안한 병렬 Space-Saving 알고리즘 도 사용됩니다.

이 알고리즘에서의 오류 비율은 데이터의 불일치 비율 및 알고리즘에서 사용된 카운터 수에 따라 크게 달라집니다. 데이터의 불일치 비율이 증가하거나 카운터가 더 많이 사용되면 출력의 정확도가 증가합니다.

SQL 함수¶

다음 집계 함수 는 Space-Saving을 사용하여 자주 나타나는 값을 추정하기 위해 제공됩니다.

• APPROX_TOP_K: 입력에서 자주 나타나는 값의 추정치를 반환합니다.

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

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

• APPROX_TOP_K_ESTIMATE: APPROX_TOP_K_ACCUMULATE 및 APPROX_TOP_K_COMBINE에 의해 생성된 Space-Saving 상태의 카디널리티 추정을 계산합니다.

구현 세부 정보¶

Snowflake 구현에서 각 카운터는 항목 및 빈도를 추적합니다. 특히, 알고리즘의 출력을 보장하는 데만 유용하고 알고리즘 자체에는 사용되지 않으므로 Snowflake 구현에서는 카운터의 엡실론 값을 추적하지 않습니다.

최대 카운터 수는 10만개로 설정되어 있습니다. 이 경우 메모리에 10만 개의 카운터가 저장되지만, 이 중 일부만 내보낸 상태로 저장됩니다.

k 의 최대 개수는 10만 개입니다. 모든 값이 출력에 적합하지 않으면 이 값이 자동으로 감소됩니다.

대부분의 경우, Snowflake 구현의 런타임은 카운터의 수에 따라 달라지지 않습니다. Snowflake 구현에서는 카운터의 수가 알고리즘의 런타임에 명시적인 효과를 주지 않습니다.

각 집계 상태의 각 카운터는 약 100바이트의 일정한 메모리 오버헤드 양을 사용합니다. 그러므로 집계에서 c 카운터를 사용하고 g 집계 그룹이 있는 경우, 집계에서는 c * g * 100B 의 메모리와 값을 저장하기 위한 메모리가 사용됩니다. 이 메모리가 총 메모리 예산을 초과하면 메모리가 디스크로 분할됩니다. 이를 통해 정확한 버전에서보다 훨씬 더 적은 메모리가 사용되며, 특히 고유 값의 수가 많은 경우에 유용합니다.