데이터베이스 조인 알고리즘, 성능을 획기적으로 개선하는 4가지 방법!
Yannakakis 알고리즘은 이론적으로는 완벽하지만, 실제 구현 시 Hash Join보다 느린 단점이 존재함.
Bloom filter를 활용하여 Semijoin 연산의 오버헤드를 줄이고, Aggregate pushdown을 통해 여러 단계를 하나의 패스로 통합하여 성능을 향상시킴.
Join on the way up 기법은 중간 결과의 확장을 지연시켜 메모리 사용량을 줄이고, On-the-fly semijoin을 통해 불필요한 튜플을 제거하여 조인 속도를 개선함.
Bloom Filter를 활용한 Semijoin 최적화
Bloom filter는 확률적 자료구조로, Semijoin 결과를 저장하여 메모리 접근을 최소화한다. 구체적으로, Hash table 대신 Bloom filter를 사용하여 Lookup 및 Insert 연산 속도를 향상시킨다. 따라서, 캐시 적중률을 높여 전반적인 조인 성능을 개선하고, 불필요한 튜플 제거를 통해 최종 조인 단계의 속도를 높인다.
Aggregate Pushdown 기법의 장단점
Aggregate pushdown은 GROUP BY 연산을 활용하여 Yannakakis 알고리즘의 여러 단계를 단일 패스로 통합한다. 구체적으로, 각 관계에 대한 Hash table을 구축하면서 집계 연산을 수행하여 쿼리 실행 시간을 단축한다. 반면, SELECT * 쿼리에는 적용할 수 없으며, GROUP BY 속성이 동일한 관계에서 나와야 하는 제약 조건이 존재한다. 따라서, 특정 쿼리 유형에만 적용 가능하다.
On-the-fly Semijoin과 TreeTracker Join
On-the-fly semijoin은 Left-deep plan에서 Semijoin을 런타임에 수행하여 불필요한 튜플을 제거한다. 구체적으로, Hash probe 실패 시 해당 튜플을 삭제하여 메모리 사용량을 줄이고, 조인 연산의 효율성을 높인다. 따라서, O(|IN|+|OUT|)의 시간 복잡도를 가지며, TreeTracker Join은 루프를 건너뛰는 추가적인 최적화를 제공한다.
