Single‐scan: a fast star‐join query processing algorithm. (16th January 2015)

• Record Type: Journal Article
• Authors: Purdilă, Vasile; Pentiuc, Ştefan‐Gheorghe
• Is Part Of: Software, practice & experience. Volume 46:Number 3(2016)
• Page Start: 319
• Page End: 339
• Publication Date: 2015-01-16
• Subjects: algorithm -- data warehouse -- dimension table -- fact table -- Hadoop -- MapReduce -- parallel processing -- Bloom filter -- star‐join; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2308
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: A data warehouse can store very large amounts of data that should be processed in parallel in order to achieve reasonable query execution times. The MapReduce programming model is a very convenient way to process large amounts of data in parallel on commodity hardware clusters. A very popular query used in data warehouses is star‐join. In this paper, we present a fast and efficient star‐join query execution algorithm built on top of a MapReduce framework called Hadoop. By using dynamic filters against dimension tables, the algorithm needs a single scan of the fact table, which means a significant reduction of input/output operations and computational complexity. Also, the algorithm requires only two MapReduce iterations in total–one to build the filters against dimension tables and one to scan the fact table. Our experiments show that the proposed algorithm performs much better than the existing solutions in terms of execution time and input/output. Copyright © 2014 John Wiley & Sons, Ltd.