Outer join is a join operation in which all tuples from its argument relations are returned as the results despite those tuples don't satisfy the join condition. Outer joins are widely used in advanced database applications such as OLAP, hierarchical view, and nested query processing. Although many commercial DBMSs support outer join, detailed algorithms or implementation techniques have not been published in the literature.
In this thesis, we design and implement outer join for the ODYSSEUS object-relational DBMS that has been under development at KAIST. In order to improve the performance of outer join queries, we propose the following new method and implementation technique: (1) We propose a method that optimizes outer join queries by pipelining the output of a join operation into the input of the next join operation instead of storing the output into the temporary relation. (2) We propose an efficient implementation technique of the existing algorithm that simplifies outer join to inner join or one-sided outer join for query optimization.
외부 조인은 조인에 참여하는 릴레이션들에서 조인 조건을 만족하지 않는 한쪽 또는 양쪽 튜플들도 결과로 반환하는 조인 연산으로 OLAP 질의 처리, 계층적 뷰(hierarchical view) 처리, 중첩 질의 처리 등의 다양한 고급 데이터베이스 응용에서 널리 사용된다. 많은 상용 DBMS에서 외부 조인을 지원하고 있으나, 상세한 구현 방법은 공개되어 있지 않다. 외부 조인은 조인에 참여하는 릴레이션들에서 조인 조건을 만족하지 않는 한쪽 또는 양쪽 튜플들도 결과로 반환하는 조인 연산으로 OLAP 질의 처리, 계층적 뷰(hierarchical view) 처리, 중첩 질의 처리(nested query processing) 등의 다양한 고급 데이터베이스 응용에서 널리 사용된다. 많은 상용 DBMS에서 외부 조인을 지원하고 있으나, 상세한 구현 방법은 공개되어 있지 않다.
본 논문에서는 한국과학기술원 멀티미디어 및 데이타베이스 연구실에서 개발하고 있는 오디세우스 객체관계형 DBMS를 위한 외부 조인을 설계하고 구현한다. 본 논문에서는 외부 조인의 처리 성능을 향상시키기 위해 다음과 같은 새로운 방법 및 구현 기법을 제안한다. 첫째, 외부 조인이 포함된 질의에 대해서 조인 연산의 결과를 임시 릴레이션(temporary relation)에 저장하는 것 대신에 다음 조인 연산의 입력으로 파이프라이닝(pipelining)시킴으로써 질의를 최적화하는 방법을 제안한다. 둘째, 질의 최적화를 위해 외부 조인을 내부 조인 또는 한쪽 외부 조인(one-sided outer join)으로 간략화하는 기존 알고리즘을 효율적으로 구현하는 기법을 제안한다.
