Star-Tree 인덱스

Star-Tree 인덱스

Apache Pinot에서 사용 가능한 인덱싱 기법을 설명해요. 이 페이지에서 star-tree 인덱스가 무엇인지, 그리고 어떻게 동작하는지에 대한 개념적 이해를 얻게 돼요.

출처: 문서

본문

단일 컬럼에 대해 동작하는 다른 인덱스 기법과 달리 star-tree 인덱스는 여러 컬럼에 구축되며 사전 집계된 결과를 활용해 처리해야 할 값의 수를 크게 줄여 쿼리 성능을 향상시켜요.

실시간 OLAP 시스템의 가장 큰 과제 중 하나는 대규모 데이터셋에서 대기 시간과 처리량에 대한 엄격한 SLA를 달성하고 유지하는 거예요. sorted index나 inverted index 같은 기존 기법은 쿼리 대기 시간을 개선하는 데 도움이 되지만, 결과를 계산하기 위해 처리해야 하는 문서 수에 의해 속도 향상이 여전히 제한돼요. 반면 결과를 사전 집계하면 쿼리 대기 시간에 일정한 상한을 보장하지만 저장 공간이 폭발적으로 늘어날 수 있어요.

집계 및 group-by 쿼리를 위해 사전 집계된 문서를 활용해 낮은 쿼리 대기 시간과 효율적인 저장 공간 사용을 모두 달성하려면 star-tree 인덱스를 사용하세요.

언제 사용할까

다음과 같은 경우 star-tree 인덱스를 사용하세요.

  • 워크로드가 알려진 dimension 및 metric 컬럼 집합에 대한 집계 및 group-by 쿼리에 의해 지배되는 경우.
  • 데이터 볼륨과 관계없이 쿼리 대기 시간 요구 사항이 1초 미만의 응답 시간을 요구하는 경우.
  • dimension 분할 순서와 집계 함수를 구성하기 위해 가장 일반적인 쿼리 패턴을 사전에 식별할 수 있는 경우.

star-tree 인덱스는 다음 경우에 적합하지 않아요.

  • 쿼리가 임시(ad-hoc)적이고 예측 불가능한 경우 — 필터 조건자, group-by 컬럼, 집계 함수가 star-tree 구성과 일치하는 쿼리만 혜택을 받아요.
  • dimension 컬럼이 매우 높은 카디널리티를 가져 사전 집계된 데이터의 크기를 늘리는 경우.

기존 해결책

다음 데이터셋을 이러한 인덱스를 논의하는 예시로 사용해요.

Country Browser Locale Impressions
CA Chrome en 400
CA Firefox fr 200
MX Safari es 300
MX Safari en 100
USA Chrome en 600
USA Firefox es 200
USA Firefox en 400

Sorted index

이 방식에서 데이터는 쿼리 집합에서 대부분의 쿼리에 필터로 나타날 가능성이 높은 기본 키(primary key)로 정렬돼요.

이렇게 하면 주어진 기본 키 값에 대해 문서를 검색하는 시간이 선형 스캔 *O(n)*에서 이진 검색 *O(logn)*으로 줄고, 선택된 문서의 지역성(locality)도 좋게 유지돼요.

이는 선형 스캔에 비해 상당한 개선이지만 여전히 몇 가지 문제가 있어요.

  • 한 컬럼에 정렬은 추가 공간이 필요 없지만, 추가 컬럼에 정렬하려면 다양한 정렬 순서에 대해 레코드를 다시 인덱싱하므로 추가 저장 공간이 필요해요.
  • 검색 시간이 *O(n)*에서 *O(logn)*으로 줄었지만 전반적 대기 시간은 여전히 쿼리를 답하기 위해 처리해야 하는 총 문서 수의 함수예요.

Inverted index

이 방식에서 주어진 컬럼의 각 값에 대해 그 값이 나타나는 문서 ID 목록을 유지해요.

다음은 예시 데이터셋의 'Browser'와 'Locale' 컬럼에 대한 inverted index예요.

Browser Doc Id
Firefox 1,5,6
Chrome 0,4
Safari 2,3
Locale Doc Id
en 0,3,4,6
es 2,5
fr 1

예를 들어 'Browser'가 'Firefox'인 모든 문서를 얻으려면 'Browser'에 대한 inverted index를 조회해 문서 [1, 5, 6]에 나타난다는 것을 식별할 수 있어요.

Inverted index를 사용하면 검색 시간을 상수 시간 *O(1)*으로 줄일 수 있어요. 하지만 쿼리 대기 시간은 여전히 쿼리의 선택도(selectivity)의 함수예요. 쿼리를 답하기 위해 처리해야 하는 문서 수에 따라 증가해요.

사전 집계 (Pre-aggregation)

이 기법에서 주어진 쿼리 집합에 대한 답을 미리 계산해요.

아래 예시에서 각 country에 대한 총 impressions를 사전 집계했어요.

Country Impressions
CA 600
MX 400
USA 1200

이 방식으로 country의 총 impressions에 대한 쿼리에 답하는 것은 값 조회이며, 많은 문서를 처리할 필요가 없어졌기 때문이에요. 그러나 여러 조건자를 가진 쿼리에 답하려면 다양한 dimension 조합에 대해 사전 집계해야 하므로 저장 공간이 기하급수적으로 늘어나요.

Star-tree 해결책

한쪽 끝에는 제한된 공간 증가로 검색 시간을 개선하지만 쿼리 대기 시간에 엄격한 상한을 보장하지 않는 인덱싱 기법이 있고, 다른 쪽 끝에는 쿼리 대기 시간에 엄격한 상한을 제공하지만 저장 공간이 기하급수적으로 폭발하는 사전 집계 기법이 있어요.

Star-tree 데이터 구조는 공간과 시간 사이의 구성 가능한 절충안을 제공하며 주어진 사용 사례에 대해 쿼리 대기 시간의 엄격한 상한을 달성할 수 있게 해요. 다음 섹션은 star-tree 데이터 구조를 다루고 Pinot가 이 구조를 사용해 낮은 대기 시간과 높은 처리량을 어떻게 달성하는지 설명해요.

정의

트리 구조

Star-tree 인덱스는 다음 속성으로 구성된 구조에 데이터를 저장해요.

  • 루트 노드 (주황): 나머지 트리를 탐색할 수 있는 단일 루트 노드.
  • 리프 노드 (파랑): 리프 노드는 최대 T개 레코드를 포함할 수 있으며, T는 구성 가능.
  • 비리프 노드 (초록): T개보다 많은 레코드를 가진 노드는 자식 노드로 더 분할됨.
  • Star 노드 (노랑): 비리프 노드는 star 노드라는 특수 자식 노드를 가질 수도 있음. 이 노드는 이 레벨에 대해 데이터가 분할된 dimension을 제거한 후 사전 집계된 레코드를 포함함.
  • Dimensions split order ([D1, D2]): 트리의 주어진 레벨에 있는 노드는 특정 dimension의 모든 값에 대해 자식 노드로 분할됨. dimensions split order는 트리의 주어진 레벨에서 분할할 dimension을 결정하는 데 사용되는 정렬된 dimension 목록임.

노드 속성

각 노드에 저장된 속성은 다음과 같아요.

  • Dimension: 노드가 분할되는 dimension
  • Start/End Document Id: 이 노드가 가리키는 문서의 범위
  • Aggregated Document Id: 이 노드가 가리키는 모든 문서의 집계 결과인 단일 문서

인덱스 생성

Star-tree 인덱스는 다음 단계로 생성돼요.

  • 데이터는 먼저 dimensionsSplitOrder대로 프로젝션돼요. split order의 dimension만 유지되고 나머지는 버려져요. 예약된 dimension의 각 고유 조합에 대해 메트릭이 구성대로 집계돼요. 집계된 문서는 파일에 쓰여지고 (원본 문서와 별개인) 초기 star-tree 문서로 제공돼요.
  • star-tree 문서를 dimensionsSplitOrder 기준으로 정렬해요. 목록의 첫 번째 dimension에 대해 기본 정렬되고 목록의 순서에 따라 나머지 dimension에 대해 2차 정렬돼요. 트리의 각 노드는 정렬된 문서의 범위를 가리켜요.
  • 트리 구조는 (루트 노드에서 시작해) 재귀적으로 다음과 같이 생성될 수 있어요.

    • 노드가 T개보다 많은 레코드를 가지면, 트리의 현재 레벨에 해당하는 split order의 dimension 각 값에 대해 하나씩 여러 자식 노드로 분할돼요.

    • 분할되는 dimension을 버리고 동일한 값을 가진 dimension이 있는 행의 메트릭을 집계해, (구성에 따라) 현재 노드에 star 노드를 생성할 수 있어요. 이 집계된 문서는 star-tree 문서의 끝에 추가돼요.

      현재 dimension에 값이 하나뿐이면 star 노드 아래 문서가 단일 노드와 동일하므로 star 노드는 생성되지 않아요.

  • 위 단계는 더 이상 분할할 노드가 없을 때까지 재귀적으로 반복돼요.
  • 서로 다른 구성(dimensionsSplitOrder, aggregations, T)을 기반으로 여러 star-tree를 생성할 수 있어요.

집계 (Aggregation)

집계는 집계 함수와 집계를 적용할 컬럼의 쌍으로 구성돼요.

경계 크기 중간 결과(bounded-sized intermediate result)를 가진 모든 유형의 집계 함수가 지원돼요.

지원 함수

  • COUNT
  • COUNTMV
  • MIN
  • MAX
  • SUM
  • SUMMV
  • ARRAYAGG
    • 예를 들어 aggregationConfigs에 {"columnName": "m", "aggregationFunction": "ARRAYAGG"}를 구성한 다음 ARRAY_AGG(m, 'LONG', true)로 쿼리. 단일 값 소스 컬럼에 대한 distinct 집계만 star-tree를 사용할 수 있어요. 소스는 BYTES를 포함한 dictionary 또는 raw 인코딩을 사용할 수 있으며, 쿼리의 요소 유형은 컬럼의 저장 유형과 일치해야 해요. Non-distinct ARRAY_AGG와 다중 값 소스 컬럼은 star-tree를 사용할 수 없어요. Distinct 결과에는 보장된 순서가 없어요. ARRAY_AGG 함수 참조를 참조하세요.
  • SUM_PRECISION
    • 최대 정밀도는 functionParameters에서 precision 키로 선택적으로 구성할 수 있어요. 예: {"precision": 20}.
  • AVG
  • AVGMV
  • MIN_MAX_RANGE
  • PERCENTILE_EST
  • PERCENTILE_RAW_EST
  • PERCENTILE_TDIGEST
    • TDigest 히스토그램의 압축 계수는 functionParameters의 compressionFactor 키로 선택적으로 구성할 수 있어요. 예: {"compressionFactor": 200}. 구성하지 않으면 기본값 100이 사용돼요. 10 미만의 값은 유효 압축 계수 10을 사용해요.
  • PERCENTILE_RAW_TDIGEST
    • TDigest 히스토그램의 압축 계수는 functionParameters의 compressionFactor 키로 선택적으로 구성할 수 있어요. 예: {"compressionFactor": 200}. 구성하지 않으면 기본값 100이 사용돼요. 10 미만의 값은 유효 압축 계수 10을 사용해요.
  • DISTINCT_COUNT_BITMAP
    • 참고: 중간 결과 RoaringBitmap은 경계 크기가 아니므로 높은 카디널리티 컬럼에서 주의해서 사용하세요.
  • DISTINCT_COUNT_HLL
    • HyperLogLog 구조의 log2m 값은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"log2m": 16}. 구성하지 않으면 기본값 8이 사용돼요. log2m 값이 클수록 정확도는 좋아지지만 메모리 사용량도 커진다는 점을 기억하세요.
  • DISTINCT_COUNT_RAW_HLL
    • HyperLogLog 구조의 log2m 값은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"log2m": 16}. 구성하지 않으면 기본값 8이 사용돼요. log2m 값이 클수록 정확도는 좋아지지만 메모리 사용량도 커진다는 점을 기억하세요.
  • DISTINCT_COUNT_HLL_PLUS
    • HyperLogLogPlus 구조의 p(정상 세트의 정밀도)와 sp(희소 세트의 정밀도) 값은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"p": 16, "sp": 32}. 구성하지 않으면 p는 기본값 14, sp는 기본값 0을 가져요.
  • DISTINCT_COUNT_RAW_HLL_PLUS
    • HyperLogLogPlus 구조의 p(정상 세트의 정밀도)와 sp(희소 세트의 정밀도) 값은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"p": 16, "sp": 32}. 구성하지 않으면 p는 기본값 14, sp는 기본값 0을 가져요.
  • DISTINCT_COUNT_THETA_SKETCH
    • Theta Sketch의 nominalEntries 값은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"nominalEntries": 4096}. 구성하지 않으면 기본값 16384가 사용돼요. 쿼리 시점에 제공된 nominalEntries는 star-tree 인덱스를 구축하는 데 사용된 값보다 작거나 같아야 한다는 점에 유의하세요. 예를 들어 {"nominalEntries": 8192}인 star-tree 인덱스는 임의의 2의 거듭제곱에 대해 nominalEntries=8192 이하의 DISTINCT_COUNT_THETA_SKETCH와 함께 사용할 수 있어요.
  • DISTINCT_COUNT_RAW_THETA_SKETCH
    • Theta Sketch의 nominalEntries 값은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"nominalEntries": 4096}. 구성하지 않으면 기본값 16384가 사용돼요. 쿼리 시점에 제공된 nominalEntries는 star-tree 인덱스를 구축하는 데 사용된 값보다 작거나 같아야 해요. 예를 들어 {"nominalEntries": 8192}인 star-tree 인덱스는 임의의 2의 거듭제곱에 대해 nominalEntries=8192 이하의 DISTINCT_COUNT_RAW_THETA_SKETCH와 함께 사용할 수 있어요.
  • DISTINCT_COUNT_TUPLE_SKETCH
    • Tuple Sketch의 nominalEntries 값은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"nominalEntries": 4096}. 구성하지 않으면 기본값 16384가 사용돼요. 쿼리 시점에 제공된 nominalEntries는 star-tree 인덱스를 구축하는 데 사용된 값보다 작거나 같아야 해요. 예를 들어 {"nominalEntries": 8192}인 star-tree 인덱스는 임의의 2의 거듭제곱에 대해 nominalEntries=8192 이하의 DISTINCT_COUNT_TUPLE_SKETCH와 함께 사용할 수 있어요.
  • DISTINCT_COUNT_RAW_INTEGER_SUM_TUPLE_SKETCH
    • Tuple Sketch의 nominalEntries 값은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"nominalEntries": 4096}. 구성하지 않으면 기본값 16384가 사용돼요. 쿼리 시점에 제공된 nominalEntries는 star-tree 인덱스를 구축하는 데 사용된 값보다 작거나 같아야 해요.
  • SUM_VALUES_INTEGER_SUM_TUPLE_SKETCH
    • Tuple Sketch의 nominalEntries 값은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"nominalEntries": 4096}. 구성하지 않으면 기본값 16384가 사용돼요.
  • AVG_VALUE_INTEGER_SUM_TUPLE_SKETCH
    • Tuple Sketch의 nominalEntries 값은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"nominalEntries": 4096}. 구성하지 않으면 기본값 16384가 사용돼요.
  • DISTINCT_COUNT_CPC_SKETCH
    • CPC Sketch의 lgK 값은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"lgK": 13}. 구성하지 않으면 기본값 12가 사용돼요. star-tree 인덱스를 사용하려면 쿼리 시점에 제공된 nominalEntries가 2 ^ lgK여야 한다는 점에 유의하세요. 예를 들어 {"lgK": 13}인 star-tree 인덱스는 nominalEntries=8192인 DISTINCTCOUNTCPCSKETCH와 함께 사용할 수 있어요.
  • DISTINCT_COUNT_RAW_CPC_SKETCH
  • DISTINCT_COUNT_ULL
    • UltraLogLog 구조의 p 값(정밀도 파라미터)은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"p": 20}. 구성하지 않으면 기본값 12가 사용돼요.
  • DISTINCT_COUNT_RAW_ULL
    • UltraLogLog 구조의 p 값(정밀도 파라미터)은 functionParameters에서 선택적으로 구성할 수 있어요. 예: {"p": 20}. 구성하지 않으면 기본값 12가 사용돼요.

지원되지 않는 함수

  • DISTINCT_COUNT
    • 중간 결과 Set은 무제한임.
  • SEGMENT_PARTITIONED_DISTINCT_COUNT:
    • 중간 결과 Set은 무제한임.
  • PERCENTILE
    • 중간 결과 List는 무제한임.

지원 예정 함수

  • ST_UNION

인덱스 생성 구성

여러 star-tree를 생성하기 위해 여러 인덱스 생성 구성을 제공할 수 있어요. 각 구성은 다음 속성을 포함해야 해요.

Property Description
dimensionsSplitOrder 분할 순서를 구성하기 위해 정렬된 dimension 이름 목록을 지정할 수 있어요. 이 목록의 dimension만 집계된 문서에 유지돼요. 노드는 이 목록의 순서에 따라 분할돼요. 예를 들어 레벨 i에서의 분할은 목록의 인덱스 i에 있는 dimension의 값에 대해 수행돼요. - star-tree dimension은 테이블의 dimension 컬럼일 필요가 없고 필요하다면 time 컬럼, date-time 컬럼, 또는 metric 컬럼이어도 됨. - star-tree dimension 컬럼은 star-tree 인덱스를 생성하기 위해 사용 가능한 dictionary 값을 가져야 함. 일반 dictionary-encoded forward index 또는 명시적 공유 dictionary를 가진 RAW forward index일 수 있음. - 쿼리의 filter 및 group-by 절에 있는 모든 컬럼은 star-tree 인덱스를 사용하려면 이 목록에 포함되어야 함.
skipStarNodeCreationForDimensions (선택, 기본값 비어 있음): Star-Node를 생성하지 않을 dimension 이름 목록.
functionColumnPairs 집계 함수와 컬럼 쌍 목록(이중 밑줄 ""로 구분). 예: SUM__Impressions (Impressions 컬럼의 SUM), **COUNT***, 또는 다중 값 메트릭 컬럼의 COUNTMV__DivLongestGTimes.
aggregationConfigs AggregationConfigs 확인
maxLeafRecords (선택, 기본값 10000): 각 노드를 더 분할할지 결정하는 임계값 T.
nullHandlingEnabled (선택, 기본값 false): null 인지 star-tree를 구축하려면 true로 설정. 인덱스는 null dimension 값을 기본값과 분리해 유지하고 null metric 값을 사전 집계에서 제외함. null 처리를 활성화한 쿼리에 대해 선택됨.

functionColumnPairs와 aggregationConfigs는 상호 교환 가능해요. 압축 같은 추가 파라미터를 지원하므로 aggregationConfigs 사용을 고려하세요.

Star-tree dimension은 여전히 dictionary 값이 필요해요. dimension이 쿼리 시간 읽기에 RAW forward index를 사용한다면 fieldConfigList에 encodingType: RAW와 indexes.dictionary를 선언해 Pinot가 star-tree 빌더를 위한 공유 dictionary를 생성하게 하세요. 그 컬럼을 레거시 tableIndexConfig.noDictionaryColumns나 tableIndexConfig.noDictionaryConfig에 두지 마세요. 그 설정은 여전히 dictionary를 비활성화하기 때문이에요.

timestamp-index 파생 컬럼을 dimensionsSplitOrder에 $<column>$<GRANULARITY> 이름(예: $OrderDate$DAY)으로 포함할 수 있어요. 일치하는 세분성은 해당 컬럼의 fieldConfigList[].timestampConfig.granularities에 선언되어야 하며, 선언되지 않은 파생 컬럼은 테이블 구성 검증 중 거부돼요. Pinot는 세그먼트 생성 시 이 dictionary-encoded single-value TIMESTAMP 컬럼을 구체화하므로 스키마에 나타날 필요가 없어요.

두 null 처리 모드를 모두 가속화하려면 각각 nullHandlingEnabled: true와 기본 false로 두 개의 동일한 star-tree를 구성하세요. Null 인지 star-tree는 null 처리가 활성화된 쿼리만 제공하고, 일반 star-tree는 null 처리가 비활성화된 쿼리 또는 null을 포함하지 않는 컬럼에 대한 활성화된 쿼리를 제공해요.

AggregationConfigs

star-tree 인덱스를 사용하려면 쿼리의 모든 집계가 aggregationConfigs 또는 functionColumnPairs에 포함되어야 해요.

Property Description
columnName (필수) 집계할 컬럼의 이름. 컬럼은 dictionary encoded 또는 raw일 수 있음.
aggregationFunction (필수) 사용할 집계 함수의 이름.
compressionCodec (선택, 기본값 PASS_THROUGH, 릴리스 1.1.0에서 도입) star-tree-index에서 활성화되는 압축을 구성하는 데 사용. 큰 값을 포함하는 컬럼을 집계할 때 유용. 예를 들어 DISTINCTCOUNTHLL을 계산하는 데 사용되는 HLL 카운터 직렬화를 포함하는 BYTES 컬럼. 이 경우 "compressionCodec": "LZ4"를 설정하면 인덱스가 사용하는 공간을 크게 줄일 수 있음. Forward Index의 compressionCodec와 동등
deriveNumDocsPerChunk (선택, 릴리스 1.2.0에서 도입) Forward Index의 deriveNumDocsPerChunk와 동등
indexVersion (선택, 릴리스 1.2.0에서 도입) Forward Index의 rawIndexWriterVersion와 동등
targetMaxChunkSize (선택, 릴리스 1.2.0에서 도입) Forward Index의 targetMaxChunkSize와 동등
targetDocsPerChunk (선택, 릴리스 1.2.0에서 도입) Forward Index의 targetDocsPerChunk와 동등
functionParameters (선택) 집계 함수에 추가 구성을 전달하는 데 사용되는 구성 맵. 예를 들어 DISTINCTCOUNTHLL에서 log2m에 대해 비기본값으로 star-tree 인덱스를 구축하려면 {"log2m": 16}처럼 보일 수 있음. 인덱스는 DISTINCTCOUNTHLL로 log2m을 같은 값을 사용하는 쿼리에만 사용된다는 점에 유의하세요.
기본 인덱스 생성 구성

tableIndexConfig 아래의 불리언 구성 enableDefaultStarTree를 사용해 기본 star-tree 인덱스를 세그먼트에 추가할 수 있어요.

기본 star-tree는 다음 구성을 가져요.

  • 카디널리티가 임계값(10000)보다 작거나 같은 모든 dictionary-encoded single-value dimension이 dimensionsSplitOrder에 포함되며, 카디널리티 내림차순으로 정렬됨.
  • 모든 dictionary-encoded Time/DateTime 컬럼이 dimension 다음에 dimensionsSplitOrder 에 추가되며, 카디널리티 내림차순으로 정렬됨. 여기에서 time 컬럼이 대부분의 쿼리에 범위 필터 컬럼 및/또는 group by 컬럼으로 포함될 것이라 가정하므로, 더 나은 성능을 위해 항상 dimensionsSplitOrder의 마지막 요소로 포함함.
  • 모든 숫자 메트릭에 대해 functionColumnPairs에 COUNT(*)와 SUM을 포함.
  • 기본 maxLeafRecords (10000) 사용.

예시

예시 데이터셋에서 다음 쿼리를 효율적으로 해결하기 위해:

SELECT SUM(Impressions) 
FROM myTable 
WHERE Country = 'USA' 
AND Browser = 'Chrome' 
GROUP BY Locale

star-tree 인덱스를 다음과 같이 구성할 수 있어요.

"tableIndexConfig": {
  "starTreeIndexConfigs": [{
    "dimensionsSplitOrder": [
      "Country",
      "Browser",
      "Locale"
    ],
    "skipStarNodeCreationForDimensions": [
    ],
    "functionColumnPairs": [
      "SUM__Impressions"
    ],
    "maxLeafRecords": 1
  }],
  ...
}

functionColumnPairs 대신 aggregationConfigs를 사용하고 집계에 압축을 활성화하려면:

"tableIndexConfig": {
  "starTreeIndexConfigs": [{
    "dimensionsSplitOrder": [
      "Country",
      "Browser",
      "Locale"
    ],
    "skipStarNodeCreationForDimensions": [
    ],
    "aggregationConfigs": [
      {
        "columnName": "Impressions",
        "aggregationFunction": "SUM",
        "compressionCodec": "LZ4"
      }
    ],
    "maxLeafRecords": 1
  }],
  ...
}

참고: 위 예시 구성에서 maxLeafRecords가 1로 설정되어 아래 시각 자료에서 명확성을 위해 모든 dimension 조합이 사전 집계된다는 점에 유의하세요.

star-tree와 문서는 다음과 같아야 해요.

트리 구조

괄호 안의 값은 노드 아래 모든 문서의 Impressions 집계 합계예요.

Star-tree 문서

Country Browser Locale SUM__Impressions
CA Chrome en 400
CA Firefox fr 200
MX Safari en 100
MX Safari es 300
USA Chrome en 600
USA Firefox en 400
USA Firefox es 200
CA * en 400
CA * fr 200
CA * * 600
MX Safari * 400
USA Firefox * 600
USA * en 1000
USA * es 200
USA * * 1200
* Chrome en 1000
* Firefox en 400
* Firefox es 200
* Firefox fr 200
* Firefox * 800
* Safari en 100
* Safari es 300
* Safari * 400
* * en 1500
* * es 500
* * fr 200
* * * 2200

쿼리 실행

쿼리 실행의 경우 먼저 메타데이터를 확인해 쿼리를 star-tree 문서로 해결할 수 있는지 결정한 다음, Star-Tree를 탐색해 모든 조건자를 만족하는 문서를 식별하는 것이 아이디어예요. 트리를 탐색하는 동안 놓친 나머지 조건자를 식별된 문서에 적용한 후, 적격한 문서에 집계/group-by를 적용해요.

트리를 탐색하는 알고리즘은 다음과 같이 설명할 수 있어요.

  • 루트 노드에서 시작.
  • 각 레벨에 대해, 어떤 자식 노드를 선택할지는 쿼리에 해당 레벨의 분할 dimension에 대한 조건자/group-by가 있는지에 따라 달라짐.
    • 분할 dimension에 조건자나 group-by가 없으면, 존재한다면 Star-Node를 선택하거나 모든 자식 노드를 선택해 더 탐색.
    • 분할 dimension에 조건자가 있으면, 조건자를 만족하는 자식 노드(들)를 선택.
    • 조건자는 없지만 분할 dimension에 group-by가 있으면, Star-Node를 제외한 모든 자식 노드를 선택.
  • 모든 리프 노드에 도달하거나 모든 조건자가 만족될 때까지 이전 단계를 재귀적으로 반복.
  • 선택된 노드가 가리키는 모든 문서를 수집.
    • 모든 조건자와 group-by가 만족되면 각 선택된 노드에서 단일 집계 문서를 선택.
    • 그렇지 않으면 각 선택된 노드의 문서 범위에 있는 모든 문서를 수집.

조건자 (Predicates)

지원 조건자

Star-tree 조건자 필터링은 dictionary-encoded forward index 또는 명시적 공유 dictionary를 가진 RAW forward index로 지원되는 dimension에 대해 동작해요. 이는 single-stage 및 multi-stage 쿼리 엔진 모두에 적용돼요. dictionary가 없는 RAW forward index는 star-tree dimension으로 사용될 수 없어요.

  • EQ (=)
  • NOT EQ (!=)
  • IN
  • NOT IN
  • RANGE (>, >=, <, <=, BETWEEN)
  • AND

지원되지 않는 조건자

  • REGEXP_LIKE: 전체 dictionary를 스캔해야 하므로 의도적으로 지원되지 않음.
  • IS NULL: 현재 NULL 값 정보는 star-tree 인덱스에 저장되지 않으며 dimension은 기본값으로 인덱싱됨. 대안은 col = <default>를 사용하는 것.
  • IS NOT NULL: IS NULL과 동일. 대안은 col != <default>를 사용하는 것.

제한적 지원 조건자

  • OR
    • 같은 dimension의 조건자에 적용할 수 있음. 예: WHERE d1 < 10 OR d1 > 50
    • 사전 집계 결과와 이중 계산되므로 여러 dimension의 조건자에는 적용할 수 없음.
  • NOT (1.2.0부터 추가)
    • 단순 조건자와 NOT에 적용할 수 있음.
    • 사전 집계 결과와 이중 계산되므로 AND/OR 위에는 적용할 수 없음.

dimension split order에 있는 컬럼(들)(대상 쿼리에서 조건자 또는 group by 컬럼인 모든 컬럼을 포함해야 함)에 변환이 있고 group-by에 사용되는 시나리오에서 Star-tree 인덱스가 자동으로 적용돼요. WHERE 절(조건자)에 사용되는 컬럼에 변환이 적용되면 Star-tree 인덱스는 적용되지 않아요.

예를 들어 쿼리가 round(colA,600) as roundedValue from tableA group by roundedValue를 포함하고 colA가 dimensionSplitOrder에 포함되어 있다면 Pinot는 사전 집계된 레코드를 사용해 먼저 일치하는 레코드를 스캔한 다음 변환 round()를 적용해 roundedValue를 도출해요.

제한 사항

  • 필터 컬럼, group-by 컬럼, 집계 함수가 모두 star-tree 구성과 일치하는 쿼리만 인덱스를 사용해요.
  • DISTINCT_COUNT(정확), SEGMENT_PARTITIONED_DISTINCT_COUNT, PERCENTILE(정확)은 중간 결과가 무제한이라 지원되지 않아요.
  • REGEXP_LIKE 조건자는 star-tree 쿼리에서 지원되지 않아요.
  • IS NULL과 IS NOT NULL은 null 값 정보가 star-tree 인덱스에 저장되지 않으므로 지원되지 않아요. 대안으로 col = <default> 또는 col != <default>를 사용하세요.
  • 쿼리 옵션 enableNullHandling=true가 사용될 때, 쿼리에 관련된 집계 컬럼, 필터 컬럼, group-by 컬럼이 해당 세그먼트에 실제로 null을 포함하지 않으면 Pinot는 여전히 star-tree 인덱스를 사용할 수 있어요.
  • 여러 dimension에 걸친 OR 조건자는 지원되지 않아요(사전 집계 결과와 이중 계산을 일으킴).
  • AND/OR 위의 NOT도 같은 이중 계산 이유로 지원되지 않아요.
  • 모든 star-tree dimension 컬럼은 dictionary 값을 가져야 해요. 일반 dictionary-encoded forward index 또는 fieldConfigList.indexes.dictionary에 명시적 공유 dictionary를 가진 RAW forward index를 사용하세요.

star-tree dimension을 RAW 인코딩으로 변경

기존 세그먼트에 star-tree dimension이 있고 이후 테이블 구성 변경이 그 컬럼을 noDictionaryColumns로 옮기면, 컬럼이 RAW로 변환된 후 저장된 star-tree는 더 이상 읽을 수 없을 수 있어요. 다음 세그먼트 리로드에서 Pinot는 enableDynamicStarTreeCreation=false일 때에도 세그먼트 사전 처리 중 호환되지 않는 star-tree를 제거해요. 일반 쿼리는 여전히 세그먼트를 사용할 수 있지만 그 star-tree 가속은 잃어요. 동적 star-tree 생성을 활성화하면 Pinot는 현재 구성이 허용하는 인덱스를 재구축할 수 있어요. 사전 처리를 건너뛰면 로더는 전체 세그먼트 로드를 실패시키는 대신 경고하고 읽을 수 없는 star-tree를 건너뛰어요. 이는 또한 이전 리로드가 인코딩 변경을 유지했지만 호환되지 않는 star-tree를 남긴 세그먼트도 수리해요. apache/pinot#19349 참조.

star-tree를 계속 사용하려면 모든 dimension에 대해 dictionary 값을 유지하세요: dictionary 인코딩을 유지하거나 위에서 설명한 대로 명시적 공유 dictionary를 가진 RAW forward index를 구성하세요. star-tree dimension에 일반 RAW forward index를 사용하지 마세요.

더 알아보기 (Learn more)