6종 JOIN 알고리즘 및 CBO 도입을 통한 TPC-H 1,450배 성능 향상

Context

2020년 이전 ClickHouse는 단일 Hash Join 알고리즘 의존으로 인해 RAM 용량을 초과하는 우측 테이블 처리 시 OOM Crash가 빈번했던 구조. 쿼리 최적화 도구의 부재로 인해 쿼리 구문 순서대로 JOIN이 실행되어 비효율적인 실행 계획이 강제되었으며, 이를 피하기 위해 극단적인 Denormalization이 권장되었음.

Technical Solution

• Grace Hash Join 도입을 통한 메모리 초과 데이터의 Disk Spilling 처리로 OOM Crash 근본적 해결
• Equivalence-Set Predicate Pushdown 적용으로 필터 조건을 JOIN 이전 단계로 전이시켜 스캔 데이터양 최소화
• Greedy 및 DPsize 알고리즘 기반의 Cost-Based Optimizer(CBO) 구축을 통한 최적의 JOIN 순서 자동 결정
• Runtime Bloom Filter를 통한 Fact Table 스캔 시 불필요한 행을 Storage Layer에서 즉시 제거하는 Pruning 구현
• OUTER JOIN의 세만틱 분석을 통한 INNER JOIN 자동 변환으로 Predicate Pushdown 및 Reordering 최적화 가능성 확보
• Correlated Subquery의 Decorrelation 처리를 통한 JOIN 구조 자동 변환으로 복잡한 서브쿼리 성능 최적화