[Pinot] 가볍게 Star Tree Index 정리
Pinot Star-Tree 인덱스란?
- 여러 차원 조합에 대한 집계 결과를 미리 만들어 두고, 쿼리마다 필요한 pre-aggregated record만 빠르게 골라 읽기 위한 다차원 인덱스
- pre-aggregated result를 이용해 처리해야 할 값의 수를 줄이는 구조
Star-Tree가 왜 필요한가?
예를 들어 이런 이벤트 테이블이 있다고 하자.
| row | country | device | browser | revenue |
| 1 | US | mobile | Chrome | 40 |
| 2 | US | mobile | Safari | 50 |
| 3 | US | desktop | Chrome | 80 |
| 4 | US | desktop | Firefox | 70 |
| 5 | KR | mobile | Chrome | 40 |
| 6 | KR | mobile | Safari | 20 |
| 7 | US | mobile | Chrome | 100 |
| 8 | KR | desktop | Chrome | 30 |
SELECT browser, SUM(revenue)
FROM events
WHERE country = 'US'
GROUP BY browser;
위 쿼리를 실행하는데, Star-Tree가 없다면 Pinot은 inverted index 등을 이용해 country='US'인 row를 빨리 찾을 수 있다.
하지만 결국 선택된 row들의 revenue를 읽고 browser별로 aggregation해야 한다.
즉, 검색 속도를 Inverted Index를 통해서 빠르게 해주지만, 결과적으로 aggregation 비용을 줄여주진 않는다.
그렇다고 모든 차원에 대해서 pre-aggregation을 하자니, 차원 조합이 다양해지면 저장공간이 폭발할 수 있다. Star-Tree는 이 둘 사이의 trade-off를 목표로 한다.
Star-Tree는 먼저 데이터를 집계한다.
다음 Star-Tree를 설정했다고 하자.
{
"starTreeIndexConfigs": [
{
"dimensionsSplitOrder": [
"country",
"device",
"browser"
],
"skipStarNodeCreationForDimensions": [],
"functionColumnPairs": [
"SUM__revenue"
],
"maxLeafRecords": 1
}
]
}
Pinot은 dimensionsSplitOrder에 포함된 dimension들로 데이터를 projection하고, 같은 dimension combination을 가진 record들의 metric을 설정된 aggregation function으로 합친다.
이 aggregated document들은 원본 document와 별도로 Star-Tree용 document로 저장된다.
| country | device | browser | SUM(revenue) |
| US | mobile | Chrome | 140 |
| US | mobile | Safari | 50 |
| US | desktop | Chrome | 80 |
| US | desktop | Firefox | 70 |
| KR | mobile | Chrome | 40 |
| KR | mobile | Safari | 20 |
| KR | desktop | Chrome | 30 |
여기까지는 그냥 GROUP BY country, device, browser로 미리 계산하는 것과 비슷하다.
이 다음에 설명할 내용이 Star-Tree의 차별적인 특징이다.
* Star Node가 핵심이다.
Pinot 공식 정의에서 Star Node는 현재 level에서 split하는 dimension을 제거하고 집계한 pre-aggregated records를 담는 특별한 child다.
즉, 'country = *'는 country 값을 신경 쓰지 않고 모든 country를 합친 것이다.
그러면, 데이터는 다음과 같이 만들어진다.
| country | device | browser | SUM(revenue) |
| * | mobile | Chrome | 180 |
| * | mobile | Safari | 70 |
| * | desktop | Chrome | 110 |
| * | desktop | Firefox | 70 |
그래서 'country=*' 아래에서 다시 device로 나눌 수 있다.
- US, *, Chrome, 220
- US, *, Safari, 50
- US, *, Firefox, 70
결국 위에 있던 쿼리를 다시 본다면, country = US, device=*에 해당하는 노드를 타면 바로 값을 조회할 수 있다.
SELECT browser, SUM(revenue)
FROM events
WHERE country = 'US'
GROUP BY browser;
dimensionsSplitOrder
"dimensionsSplitOrder": [
"country",
"device",
"browser"
]첫째, 어떤 dimension을 Star-Tree 안에 넣을 것인가
둘째, 어떤 순서로 tree를 split할 것인가
를 설정하게 된다. 즉, 순서가 다르면 전혀 다른 방식으로 트리를 만들게 된다. 따라서 cardinality, data distribution, query workload에 따라 index 크기와 traversal 비용이 달라질 수 있다.
skipStarNodeCreationForDimensions 설정
만일 다음과 같이 설정했다고 가정한다면, device=*에 대한 Star Node가 생성되지 않는다. 즉, Star Node가 없다면 미리 계산된게 없기 때문에 데이터 저장 공간을 줄일 수 있지만, 반대로 해당 질의에 대해서는 런타임에 계산이 필요하다.
"skipStarNodeCreationForDimensions": ["device"]
maxLeafRecords 설정
maxLeafRecords는 leaf node가 설정된 레코드보다 크면, 다음 디멘젼으로 더 split된다.
예를 들어, 50,000으로 설정했고, country = US 아래의 레코드가 4개니까 더 이상 노드를 생성하지 않는다.
현재 예시에서는 1로 설정했으니, 모든 leaf node에 대해서 생성하게 된다.