Performance evaluations on inner vs. outer decomposition first parallel join algorithms for two nested loop joins

Abstract

Two popular traditional join algorithms and their parallel versions are introduced. When designing join algorithms in serial computing environment, decomposing inner relation is considered as the right direction to save disk I/Os. However, two different decomposition algorithms are compared, such as inner vs. outer decomposition first algorithms for tuple-based and block-based nested loop joins, showing that the proposed approach is 20% better than general approach. Also lemmas are proved, when we have to use the outer decomposition first parallel join algorithms.

Keywords

parallel join performance / inner decomposition / outer decomposition

References

[1] DewittD, AnughtonJ, BurgerJ. Nested loops revisited [C]. PDIS, 1993, USA, IEEE Computer Society: 230-242

[2] LiJ-z, SunW-j, LiY-shu. Parallel join algorithms based on parallel B+trees [C]. CODAS. USA, 2001205-211

[3] SpyrosB, JigneshP M, VukE, RaoJ, EugeneS J, TianY-yuan. A comparison of join algorithms for log processing in MaPreduce [C]. SIGMOD. USA, 2010975-986

[4] SpyrosB, LiY-n, JigneshP M. Design and evaluation of main memory hash join algorithms for multi-core CPUs [C]. SIGMOD. Greece, 201137-48

[5] AgrawalP, WidomJ. Confidence-aware join algorithms [C]. ICDE, China, 2009628-639

[6] HeW, ZhouM-q, GongX-q, HeX-feng. Massive parallel join in NUMA architecture [C]. BigData Congress. CA, USA, 2013219-226

[7] MarkH D, MartyR M. Amdahl’s law in the multicore era [J]. IEEE Computer, 2008, 41(7): 33-39

[8] ChaiL, GaoQ, DhabaleswarP K. Understanding the impact of multi-core architecture in cluster computing: A case study with intel dual-core system [C]. CCGRID, 2007, Brazil, IEEE Computer Society: 471-478

[9] van CraeynestK, EeckhoutL. The multi-program performance model: Debunking current practice in multi-core simulation [C]. Workload Characterization (IISWC). TX, USA, 201126-37

[10] MuresanoR, RexachsD, LuqueE. How SPMD applications could be efficiently executed on multicore environments? [C]. CLUSTER. LA, USA, 20091-4

[11] NohS-Y, YoonH, YeoI, ParkH. Decomposition-based parallel join algorithm [C]. ICCT2013. Thailand, 2013914-915

[12] NohS Y, YoonH, YeoI, ParkHyungwoo. Outer first decomposition-based parallel join algorithm for block nested loop join [J]. IJACT, 2013, 5(12): 914-915

[13] DewittJ D. The Wisconsin benchmark: Past, present, and future [M]. The Benchmark Handbook. Morgan Kaufmann, 19931-43

[14] Garcia-MolinaH, UllmanJ D, WidomJDatabase systems-the complete book [M], 2002, Upper Saddle River, NJ, USA, Prentice Hall: 733-736

[15] CoronelC, MorrisS, RobP. Database systems: Design, implementation, and management [M]. Cengage Learning, 2012270-285

[16] SiberschatzA, KorthH, SudarshanS. Database system concepts [M]. McGraw-Hill Science/Engineering, 2010542-554

[17] GroppW, Huss-LedermanS, LumsdaineA, LuskE, NitzbergB, SaphirW, SnirMMPI-The complete reference: the MPI-2 extensions [M]. Volume 2, 1998, Cambridge, MA, USA, MIT Press: 56-60

[18] LiW, DaoD, SnodgrassR. Skew handling techniques in sort-merge join [R]. Tech 65. A Time Center Technical Report, 2001

[19] ChungS M, ChatterjeeA. Adaptive parallel distributive join algorithm for skewed data [C]. Parallel and Distributed Systems (ICPADS). Kyongju, Korea, 200115-22