고유 개수 및 카디널리티 추정 함수

고유 개수 및 카디널리티 추정 함수 (Unique Count and Cardinality Estimation Functions)

고유 개수(distinct count)

카디널리티 추정은 고전적인 문제예요. Pinot은 정확도와 지연 시간 사이의 트레이드오프가 각각 다른 여러 방식으로 이를 해결합니다.

출처: 문서

본문

정확한 결과 (Exact Results)

함수:

  • DistinctCount(x) -> LONG

컬럼의 모든 고유 값에 대한 정확한 개수를 반환해요.

기반 구현은 it.unimi.dsi:fastutil:8.2.3 라이브러리의 IntOpenHashSet을 사용해 모든 고유 값을 보관합니다.

근사 결과 (Approximate Results)

대규모 데이터셋에 대한 고유 개수의 정확한 결과를 계산하는 데는 보통 많은 리소스와 시간이 소요됩니다. 어떤 상황에서는 특정 오차율을 허용할 수 있는데, 그 경우 근사 함수를 사용해 이 문제를 해결할 수 있어요.

HyperLogLog

HyperLogLog는 고유 개수를 위한 근사 알고리즘이에요. 고정된 비트 수를 사용해 주어진 데이터셋의 카디널리티를 추정합니다.

Pinot은 com.clearspring.analytics:stream:2.7.0 라이브러리의 HyperLogLog Class를 중간 결과 보관 데이터 구조로 활용해요.

함수:

  • DistinctCountHLL(x) -> LONG_

INT/LONG/FLOAT/DOUBLE/STRING 컬럼 타입의 경우 Pinot은 각 값을 HyperLogLog 객체에 추가할 개별 항목으로 취급한 뒤 _cardinality() 메서드를 호출해 근사치를 계산합니다.

BYTES 컬럼 타입의 경우 Pinot은 각 값을 내부에 사전 집계된 값이 있는 직렬화된 HyperLogLog 객체로 취급합니다. bytes 값은 org.apache.pinot.core.common.ObjectSerDeUtils.HYPER_LOG_LOG_SER_DE.serialize(hyperLogLog)로 생성됩니다.

역직렬화된 모든 HyperLogLog 객체는 하나로 병합된 뒤 _cardinality() 메서드를 호출해 근사 고유 개수를 얻습니다.

HyperLogLogPlusPlus

HyperLogLog++ 알고리즘은 메모리 요구량을 줄이고 특정 카디널리티 범위에서 정확도를 높이기 위해 HyperLogLog 알고리즘에 몇 가지 개선을 제안해요.

  • 원래 논문에서 사용한 32비트 대신 64비트 해시 함수를 사용합니다. 이는 대규모 카디널리티에서 해시 충돌을 줄여 대역폭 보정을 제거할 수 있게 해줍니다.
  • 선형 카운팅에서 HLL 카운팅으로 전환할 때 작은 카디널리티에서 약간의 편향이 발견됩니다. 이 문제를 완화하기 위해 경험적 편향 보정이 제안되었습니다.
  • 작은 카디널리티의 메모리 요구량을 줄이기 위해 레지스터의 희소 표현이 구현되며, 카디널리티가 커지면 나중에 조밀 표현으로 변환될 수 있습니다.

Pinot은 com.clearspring.analytics:stream:2.7.0 라이브러리의 HyperLogLogPlus Class를 중간 결과 보관 데이터 구조로 활용해요.

함수:

  • DistinctCountHLLPlus(_ -> LONG_
  • DistinctCountHLLPlus(,

    ) -> LONG_

  • DistinctCountHLLPlus(,

    , ) -> LONG_

INT/LONG/FLOAT/DOUBLE/STRING 컬럼 타입의 경우 Pinot은 각 값을 HyperLogLogPlus 객체에 추가할 개별 항목으로 취급한 뒤 _cardinality() 메서드를 호출해 근사치를 계산합니다.

BYTES 컬럼 타입의 경우 Pinot은 각 값을 내부에 사전 집계된 값이 있는 직렬화된 HyperLogLogPlus 객체로 취급합니다. bytes 값은 org.apache.pinot.core.common.ObjectSerDeUtils.HYPER_LOG_LOG_PLUS_SER_DE.serialize(hyperLogLogPlus)로 생성됩니다.

역직렬화된 모든 HyperLogLogPlus 객체는 하나로 병합된 뒤 _cardinality() 메서드를 호출해 근사 고유 개수를 얻습니다.

Theta Sketches

Theta Sketch 프레임워크는 데이터 스트림에 대한 집합 연산을 가능하게 하며 카디널리티 추정에도 사용할 수 있어요. Pinot은 org.apache.datasketches:datasketches-java:4.2.0 라이브러리의 Sketch Class와 그 확장을 활용해 고유 개수와 집합 연산 평가를 수행합니다.

함수:

  • DistinctCountThetaSketch(, , predicate1, predicate2..., postAggregationExpressionToEvaluate**) -> LONG
    • thetaSketchColumn (필수): 집계할 컬럼 이름.
    • thetaSketchParams (필수): 중간 theta-sketches를 구성하기 위한 파라미터. 현재 지원되는 유일한 파라미터는 nominalEntries입니다.
    • predicates (선택): where 절이 선택한 행에 적용되는 lhs <op> rhs 형식의 개별 술어들. 중간 sketch 집계 중에 이 술어들을 만족하는 thetaSketchColumn의 sketch는 개별적으로 합집합됩니다. 예를 들어 country=USA와 일치하는 모든 필터링된 행은 단일 sketch로 합집합됩니다. 개별 술어의 (AND/OR) 결합으로 만들어진 복합 술어도 지원됩니다.
    • postAggregationExpressionToEvaluate (필수): 각 술어에 대한 개별 중간 sketch에 수행할 집합 연산. 현재 지원되는 연산은 SET_DIFF, SET_UNION, SET_INTERSECT이며, DIFF는 두 인자가 필요하고 UNION/INTERSECT는 두 개 이상의 인자를 허용합니다.

아래 예시 쿼리에서 where 절은 일치하는 행을 식별하는 역할을 합니다. where 절은 postAggregationExpression과 완전히 독립적일 수 있어요. 일치하는 행이 식별되면 각 서버는 개별 술어(이 경우 country='USA', device='mobile')와 일치하는 모든 sketch를 합집합합니다. 브로커가 모든 서버에서 이 개별 술어 각각에 대한 중간 sketch를 받으면 postAggregationExpression을 평가해 최종 집계를 수행하고 결과 sketch의 최종 카디널리티를 반환합니다.

select distinctCountThetaSketch(
  sketchCol, 
  'nominalEntries=1024', 
  'country'=''USA'' AND 'state'=''CA'', 'device'=''mobile'', 'SET_INTERSECT($1, $2)'
) 
from table 
where country = 'USA' or device = 'mobile...'
  • DistinctCountRawThetaSketch(, , predicate1, predicate2..., postAggregationExpressionToEvaluate**) -> HexEncoded Serialized Sketch Bytes

이전 함수와 동일하지만 카디널리티 sketch 대신 바이트 직렬화된 sketch를 반환해요. Pinot은 응답을 JSON 문자열로 반환하므로 바이트는 hex 인코딩 문자열로 반환됩니다. hex 인코딩 문자열은 org.apache.commons.codec.binary 라이브러리를 사용해 Hex.decodeHex(stringValue.toCharArray())로 sketch로 역직렬화할 수 있어요.

Tuple Sketches

Tuple Sketch는 Theta Sketch의 확장입니다. Tuple sketch는 유지되는 각 항목에 추가 요약 값을 저장하므로, 노출수나 클릭수 같은 속성을 요약하기에 이상적이에요. Tuple sketch는 Theta Sketch와 상호 운용 가능하며 데이터 스트림에 대한 집합 연산을 가능하게 하고 카디널리티 추정에도 사용할 수 있어요.

함수:

  • avgValueIntegerSumTupleSketch(, **) -> Long
    • tupleSketchColumn (필수): 집계할 컬럼 이름.
    • tupleSketchLgK (선택): sketch의 크기와 정확도를 제어하는 K의 log2인 lgK.

이 함수는 Tuple sketch에 저장된 랜덤 샘플의 요약 값을 결합해 전체 데이터셋에 적용되는 평균에 대한 추정치를 만들 수 있어요. 평균은 sketch가 추적하는 각 키에 적용되는 것으로 해석해야 하며 가장 가까운 정수로 반올림됩니다.

  • distinctCountTupleSketch(, **) -> LONG
    • tupleSketchColumn (필수): 집계할 컬럼 이름.
    • tupleSketchLgK (선택): sketch의 크기와 정확도를 제어하는 K의 log2인 lgK.

이 함수는 값이 이미 Tuple sketch로 인코딩되어 BYTES로 저장된 컬럼에 대한 카디널리티 추정치를 반환해요.

  • distinctCountRawIntegerSumTupleSketch(, **) -> HexEncoded Serialized Sketch Bytes

이전 함수와 동일하지만 카디널리티 sketch 대신 바이트 직렬화된 sketch를 반환해요. Pinot은 응답을 JSON 문자열로 반환하므로 바이트는 hex 인코딩 문자열로 반환됩니다. hex 인코딩 문자열은 org.apache.commons.codec.binary 라이브러리를 사용해 Hex.decodeHex(stringValue.toCharArray())로 sketch로 역직렬화할 수 있어요.

  • sumValuesIntegerSumTupleSketch(, **) -> Long
    • tupleSketchColumn (필수): 집계할 컬럼 이름.
    • tupleSketchLgK (선택): sketch의 크기와 정확도를 제어하는 K의 log2인 lgK.

이 함수는 Tuple sketch에 저장된 랜덤 샘플의 요약 값을 (sum을 사용해) 결합해 전체 데이터셋에 적용되는 추정치를 만들 수 있어요. 정수 요약의 평균을 추출하려면 avgValueIntegerSumTupleSketch를 참고하세요. 다른 병합 옵션이 필요하다면 raw sketch를 직접 추출하거나 이를 지원하는 새 Pinot 집계 함수를 구현하는 것이 좋습니다.

Compressed Probability Counting (CPC) Sketches

압축 확률 계수(CPC) Sketch는 매우 공간 효율적인 카디널리티 추정을 가능하게 해요. 저장된 CPC sketch는 비슷한 정확도의 HLL sketch보다 약 40% 적은 공간을 사용할 수 있습니다. Pinot은 여러 기존 CPC sketch를 함께 집계해 전체 고유 개수를 얻거나 raw 값에서 직접 추정할 수 있어요.

함수:

더 알아보기 (Learn more)