With a growing demand of hidden insights from the large scale of data, multi-way join operations become the key of many OLAP-style data analytic tasks for not only relational data analysis, but also various scientific applications. To process OLAP-style data analytic tasks with cost-efficiency, shared-nothing distributed system, such as MapReduce, gets its popularity in both academic field and enterprises. However, due to various lacks in support of MapReduce such as processing data from multiple sources and data skew handling, join operation is inefficient operation in MapReduce. Specifically, generation of query execution plan in MapReduce does not consider the dominantly utilized resources that affect the performance of a query processing significantly. Our work is based on a counter observations from traditional wisdoms of query processing in MapReduce: reducing the number of MapReduce job does not guarantee the performance benefit, and growing intermediate data does not always triggers the performance degradation. In this work, we propose efficient resource-aware multi-way join processing method by taking not only algorithmic approach, but also systemic approach. As an algorithmic approach, we propose in-memory streaming hash join method with careful consideration of memory constraint in a computing machine and a balanced workload of each join task. As a systemic approach, we propose a generation of efficient multi-way join query execution plan. In experimental results, our method improves the performance of multi-way join query processing, especially the latest version of Apache Hive[5], and AQUA[11]. In addition, our method shows better performance even if the aggregated intermediate data is larger than other method by exploiting major resources very efficiently. ⓒ 2015 DGIST
Table Of Contents
Ⅰ. INTRODUCTION -- Ⅱ. BACKGROUND -- 2.1 MapReduce -- 2.2 SQL-on-Hadoop -- Ⅲ. JOIN PROCESSING USING MAPREDUCE -- 3.1 Basic join algorithms in MapReduce -- 3.2 Replicated join -- 3.3 1-Bucket-Theta -- Ⅳ. RESOURCE-AWARE MULTI-WAY JOIN PROCESSING -- 4.1 Problem description -- 4.2 Cost model of operator pipeline in MapReduce -- 4.3 In-memory streaming hash join -- 4.4 Finding multi-way join group -- Ⅴ. EXPERIMENTS -- Ⅵ. RELATED WORK -- Ⅶ. CONCLUSIONS -- Ⅷ. REFERENCE