Object-oriented navigational applications navigate complex objects by accessing the component objects one by one using the reference and the collection attributes. The navigational characteristics of these applications make the number of round-trips increase in client/server DBMSs and causes serious performance degradation. To minimize round-trips between the client and the server, we need an efficient prefetching policy that correctly predicts the future access pattern of the applications.
In this dissertation, we propose new notions of the type-level access locality and the type-level access pattern. The type-level access locality is a phenomenon that repetitive patterns exist in the attributes referenced, and the type-level access pattern is a pattern of attributes that are referenced in accessing the objects. We also formally define the notions of capturing and prefetching to help understand the underlying mechanisms. We then develop an efficient prefetching policy based on these notions.
Therefore, we propose the notion of the access pattern view that exploits the type-level access pattern. The access pattern view is a materialized view for the objects to be accessed by a type-level access pattern captured. In an access pattern view, the objects are clustered for the corresponding type-level access pattern. Thus, in query processing, the number of disk accesses is reduced by directly accessing the access pattern view. We then propose a prefetching method that uses the access pattern view. Here, we propose a formal framework for creating access pattern views for the type-level access patterns captured during navigation. We then develop an efficient view matching method to find the access pattern views that match the type-level access pattern captured. Experimental results using various applications including an XML application show that our technique provides orders of magnitude improvement in disk accesses and in wall-clock time over the prefetching method based on the type-level access pattern that does not use the access pattern view.
These results indicate that our approach provides a new paradigm in prefetching that improves performance of navigational applications significantly and that the proposed prefetching algorithms are practical ones that can be implemented in commercial ORDBMSs.
객체지향 항해 응용에서는 복합 객체를 구성하는 컴포넌트 객체들을 참조 애트리뷰트와 컬렉션 애트리뷰트를 사용하여 한 번에 하나씩 액세스한다. 이러한 항해 특징으로 인하여 클라이언트/서버 DBMS에서는 많은 수의 라운드트립이 발생하며 이는 심각한 성능 저하를 야기시킨다. 클라이언트와 서버 사이의 라운드트립을 줄이기 위해서는, 항해 응용의 향후 액세스 패턴을 정확하게 예측하는 효과적인 선인출 방법이 필요하다.
본 논문에서는 타입수준 액세스 지역성과 타입수준 액세스 패턴이라는 새로운 개념을 제안한다. 타입수준 액세스 지역성이란 참조된 애트리뷰트들 사이에 반복되는 패턴이 나타나는 현상이며, 타입수준 액세스 패턴이란 객체를 액세스할 때 사용된 애트리뷰트들의 패턴이다. 그리고, 선인출의 메카니즘을 이해하는데 도움이 되는 캡쳐와 선인출의 개념을 정형적으로 제안한다. 다음으로, 이러한 개념에 기반하여 효율적인 선인출 방법을 제안한다.
기존의 선인출 방법은 항해 응용에서 액세스된 객체 혹은 페이지 식별자들 간의 패턴인 객체수준 혹은 페이지수준 액세스 패턴에 의거한다. 그러나, 이 방법들은 동일한 객체 혹은 페이지들이 반복적으로 액세스될 때에만 선인출 효과를 가지는 문제점이 있다. 이에 반해, 제안하는 방법은 항해 응용에서 같은 객체들이 반복적으로 액세스되지 않더라도 같은 애트리뷰트들이 반복적으로 참조되는 경우, 즉, 타입수준 액세스 지역성이 존재하는 경우 효과적인 선인출을 수행한다.s
객체관계형 DBMS(ORDBMS)의 많은 항해 응용들은 타입수준 액세스 지역성을 가진다. 따라서, 제안하는 방법을 ORDBMS에 적용하면 라운드트립의 횟수를 효과적으로 줄일 수 있고 성능을 크게 향상시킬 수 있다. 제안한 알고리즘의 효율성을 입증하기 위하여 프로토타입 ORDBMS에서 많은 실험을 수행하였다. OO7 벤치마크나 실제 GIS 응용을 사용한 성능 평가 결과, 제안하는 선인출 방법은 단순한 요구인출 방법 및 최근의 컨텍스트 기반 선인출 방법과 비교하여 라운드트립 횟수를 수십배에서 수백배까지 줄이고 수행 시간을 수배까지 향상시켰다.
제안하는 방법은 두 가지 성능 척도에서 많은 향상을 보였지만, 수행 시간의 단축 비율이 라운드트립 횟수의 감소 비율에는 크게 미치지 못한다. 이는 항해 응용의 수행 시간이 라운드트립 시간뿐 아니라 질의 처리 시간도 포함하기 때문이다. 여기서, 질의 처리 시간은 데이타베이스에서 객체들을 인출하는 디스크 액세스 시간을 포함한다. 그러므로, 선인출의 성능을 더욱 개선하기 위해서는 선인출시에 객체들을 인출할 때 발생하는 디스크 액세스 시간을 줄이는 방법이 필요하다.
이에 따라, 본 논문에서는 타입수준 액세스 패턴의 개념을 응용하여 액세스 패턴 뷰 (access pattern view)의 개념을 제안한다. 액세스 패턴 란 캡쳐된 타입수준 액세스 패턴에 의해 액세스되는 객체들을 구체화한 뷰(materialized view)이다. 액세스 패턴 뷰에는 해당 액세스 패턴에 대해 객체들이 클러스터링되어 있고, 질의 처리 과정에서 액세스 패턴 뷰를 직접 액세스함으로써 디스크 액세스 횟수를 줄일 수 있다. 다음으로, 액세스 패턴 뷰를 활용하는 선인출 방법을 제안한다. 우선, 캡쳐된 타입수준 액세스 패턴으로부터 액세스 패턴 뷰를 생성하는 정형적인 프레임워크를 제시한다. 그리고, 타입수준 액세스 패턴과 매치하는 액세스 패턴 뷰를 찾는 효과적인 뷰 매칭 방법을 제안한다. XML 응용을 포함한 다양한 응용의 성능 평가 결과, 제안하는 방법은 액세스 패턴 뷰를 사용하지 않는 타입수준 액세스 패턴 기반 선인출과 비교하여, 디스크 액세스 횟수와 수행 시간을 최대 수십배까지 향상시켰다.
이와 같은 결과로 볼 때, 제안하는 방법은 객체지향 항해 응용의 성능을 크게 향상시키는 획기적인 결과로서, 상용 ORDBMS에 구현될 수 있는 실용적인 결과라 믿는다.
