Inverted Index를 이용한 Row-to-Column 조인 코스트모델

Abstract

최근의 연구결과들은 OLTP와 OLAP 특성 어플리케이션들을 모두 효율적으로 지원하는 방법의 하나로 하이브리드-스토어 데이터베이스 시스템을 제안하고 있다. 이러한 데이터베이스 시스템에서 성능 예측을 위한 코스트모델 수립에는 row-oriented 데이터베이스 시스템과 column-oriented 데이터베이스 시스템의 특징이 모두 고려되어야 한다. 본 논문에서는 하이브리드-스토어 데이터베이스 시스템에서 row-oriented 테이블과 column-oriented 테이블 간 조인 연산을 위해 구상된 row-to-column 조인 알고리즘의 코스트모델 수립 과정을 기술하였다. 그리고 이 과정에서 하이브리드-스토어 데이터베이스 시스템에서의 알고리즘 구현 시, 순수한 알고리즘과 실제 구현간에 차이를 발생시킬 수 있는 요인들에 대하여 설명하였다. 코스트모델의 대상이 되었던 row-to-column 조인 알고리즘의 경우, row-oriented 데이터베이스 시스템에서의 인덱스 조인과 유사한 데이터 처리 방식을 제시하였다. row-oriented 데이터베이스 시스템은 다수의 데이터에 대한 쿼리프로세싱을 위하여 이터레이팅 방식으로 각각의 데이터에 접근하고 연산을 반복하는 동작을 한다. 하지만 하이브리드-스토어 데이터베이스에서 조인 대상 테이블이 column-oriented 테이블인 경우에는 이에 대한 별도의 고려가 필요하다. Column-oriented 테이블은 각각의 칼럼이 개별적인 메모리 공간에 존재하고 딕셔너리 인코딩되어 있기 때문에 데이터 단위의 이터레이팅 연산이 아닌 일정한 블럭 단위로 데이터를 처리한다. 따라서 하이브리드-스토어 데이터베이스 시스템의 특성상 제시된 row-to-column 조인 알고리즘의 분석으로 계산한 코스트 외에 column-oriented 테이블을 고려한 추가적인 코스트가 구현 상에서 발생하였다. 논문에서는 순수한 알고리즘의 흐름만을 고려한 코스트모델과 구현 과정에서 추가적으로 발생한 코스트가 함께 고려된 모델을 각각 수립하였다. 그리고 프로토타입 쿼리 프로세서와 상용 데이터베이스 시스템을 사용한 실험 결과를 통하여 이러한 구현 코스트의 고려가 수반되어야 하이브리드-스토어 데이터베이스 시스템의 실제 성능을 예측할 수 있는 정확한 코스트모델 수립이 가능하다는 것을 확인하였다.

Recent researches suggest hybrid-store database system as a solution of simultaneous supports for OLTP and OLAP workloads. In such environment, both characteristics of row-oriented database system and column-oriented database system have to be considered to calculate cost model for performance prediction. This paper present process about calculating cost model of row-to-column join algorithm which is designed for join operation between row-oriented table and column-oriented table in hybrid-store database system. And address factors which can make difference between pure algorithm and actual implementation. In case of row-to-column join, pure algorithm suggests join operation similar to index join of row-oriented database system. Row-oriented database system iterates and operates for each record in order to process multiple records. But database system use hybrid-store and join table other side is column-oriented, specific consideration is needed for processing. Each column in column-oriented table use separated memory address and encoded with dictionary so record is processed by block iteration. Consequentially, costs are generated with considering column-oriented table besides costs calculated from pure algorithm. In paper, two cost models are calculated. First one calculated only from pure algorithm but second one considers costs from implementation issues. And need for this consideration is confirms by experiments using prototype query processor and commercial database system.