GPU 가속 관계형 질의 실행 엔진은 연산자들의 연속인 파이프라인의 실행을 병렬화한다. 이를 위해 엔진은 파이프라인의 첫 연산자(스캔)가 스캔할 테이블의 튜플을 균등하게 분할하고, 각 스레드는 해당 분할에 속한 튜플에 대해 파이프라인을 실행한다. 그러나 이 접근법은 연산자가 입력 튜플당 서로 다른 수의 출력 튜플을 반환하기 때문에, 특히 치우친 조인 키 값과 같은 비균일한 데이터 분포 하에서 부하 불균형을 초래한다. 이러한 부하 불균형은 1) 스레드가 워프(warp)로 묶이고 2) 단일 명령-다중 스레드(single-instruction-multiple-thread) 방식에 따라 워프 내의 모든 스레드가 입력 튜플에 대해 동일한 연산자를 동시 평가하기 때문에, 워프 내부 및 워프 간 부하 불균형(intra- and inter-warp load imbalances, intra-WLIs 및 inter-WLIs)으로 분류된다. 반면 워프가 다른 경우에는 스레드가 서로 다른 연산자를 동시에 평가할 수 있다. 부하 균형화 기법이 제안되었음에도 불구하고, 다양한 워크로드에서 이러한 부하 불균형을 해결하지 못한다. 본 논문에서는 공정성의 신을 따서 Themis로 명명한 질의 실행 엔진을 제안하며, 이는 우리의 맥락에서 균형 잡힌 워크로드를 상징한다. Themis는 다양한 워크로드에서 intra-WLIs 및 inter-WLIs를 최소화한다. 첫째, Themis는 워프 내 스레드 간에 튜플을 재분배하고, 모든 스레드가 입력을 보유한 경우에만 연산자를 평가하도록 하여 intra-WLIs를 최소화한다. 둘째, Themis는 부하가 큰 워프의 튜플을 유휴 워프로 재분배함으로써 inter-WLIs를 완화한다. 워프의 워크로드가 무거운지 확인하기 위해, 워프 워크로드의 크기를 근사하는 방법을 제안한다. 이러한 근사에 기초하여 Themis는 워프의 워크로드가 무거운 것으로 판정하기 위한 임계값을 적응적으로 조정한다. TPC-H에 치우친 조인 키 분포를 도입하는 최근 벤치마크 JCC-H에서, Themis는 inter-WLIs와 intra-WLIs를 유의하게 완화하여 2위 대비 최대 379배 더 나은 성능을 보인다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.