맵리듀스 기반 스트리밍 세타 조인 알고리즘

Abstract

처리해야 할 데이터의 크기가 급격히 증가하면서, 맵리듀스를 이용하여 조인질의를 수행하는 다양한 연구가 이루어지고 있다. 하지만 입력 데이터의 크기가 증가하면 중간 생성 데이터의 크기가 커지고 디스크 입출력과 네트워크 트래픽이 증가하여 수행시간이 오래 걸리는 문제가 있다. 본 논문에서는 맵리듀스 프레임워크를 이용한 세타 조인에 대해 중간 생성 데이터의 크기를 최대 75%를 줄여 수행시간을 감소시킬 수 있는 향상된 세타 조인 방식을 제안한다. 또한 디스크 입출력에 대한 비용모델을 제안하고 이를 세타 조인 알고리즘에 적용하여 수행시간을 최소화하는 데이터 분할 방법을 선택하도록 한다.

As the size of data to be processed is rapidly increases, many researches have been conducted on processing join queries using MapReduce. However, when the size of input data becomes large, processing time of a join query tends to grow significantly since the disk I/O and network traffic become large due to the increase of the size of intermediate data. In this paper, an improved theta-join algorithm is proposed for process theta-join queries using a MapReduce framework. This algorithm can reduce the execution time of query processing due to the size of intermediate result is reduced by up to 75%. A cost model for disk I/O is also proposed and it is applied to the improved theta-join algorithm to select the best partitioning method to minimize the execution time.