Skew-Aware Join Optimization for Array Databases

ABSTRACT

Science applications are accumulating an ever-increasing amount of multidimensional data. Although some of it can be processed in a relational database, much of it is better suited to array-based engines. As such, it is important to optimize the query processing of these systems. This paper focuses on efficient query processing of join operations within an array database. These engines invariably ``chunk'' their data into multidimensional tiles that they use to efficiently process spatial queries. As such, traditional relational algorithms need to be substantially modified to take advantage of array tiles. Moreover, most n-dimensional science data is unevenly distributed in array space because its underlying observations rarely follow a uniform pattern. It is crucial that the optimization of array joins be skew-aware. In addition, owing to the scale of science applications, their query processing usually spans multiple nodes. This further complicates the planning of array joins.

In this paper, we introduce a join optimization framework that is skew-aware for distributed joins. This optimization consists of two phases. In the first, a logical planner selects the query's algorithm (e.g., merge join), the granularity of the its tiles, and the reorganization operations needed to align the data. The second phase implements this logical plan by assigning tiles to cluster nodes using an analytical cost model. Our experimental results, on both synthetic and real-world data, demonstrate that this optimization framework speeds up array joins by up to 2.5X in comparison to the baseline.

References

1. M. Stonebraker et al. C-store: a column-oriented DBMS. In VLDB, 2005.
2. T. Achterberg. Scip: solving constraint integer programs. Mathematical Programming Computation, 1(1):1--41, 2009.
3. A. Ailamaki, V. Kantere, and D. Dash. Managing scientific data. Communications of the ACM, 53(6):68--78, 2010.
4. C. Balkesen, J. Teubner, G. Alonso, and T. Ozsu. Main-memory hash joins on multi-core CPUs: Tuning to the underlying Hardware. In ICDE, 2013.
5. A. Ballegooij. Ram: A multidimensional array dbms. In EDBT Workshops '05.
6. P. Baumann, A. Dehmel, P. Furtado, R. Ritsch, and N. Widmann. The multidimensional database system RasDaMan. In SIGMOD Record, 1998.
7. S. Blanas, Y. Li, and J. Patel. Design and evaluation of main memory hash join algorithms for multi-core CPUs. In SIGMOD, 2011.
8. H. Boral, W. Alexander, L. Clay, G. Copeland, S. Danforth, M. Franklin, B. Hart, M. Smith, and P. Valduriez. Prototyping bubba, a highly parallel database system. Knowledge and Data Engineering, IEEE Transactions on, 2(1):4--24, 1990.
9. P. G. Brown. Overview of SciDB: large scale array storage, processing and analysis. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pages 963--968. ACM, 2010.
10. P. Cudré-Mauroux, H. Kimura, K.-T. Lim, J. Rogers, R. Simakov, E. Soroush, P. Velikhov, D. L. Wang, M. Balazinska, J. Becla, D. J. DeWitt, B. Heath, D. Maier, S. Madden, J. M. Patel, M. Stonebraker, and S. B. Zdonik. A Demonstration of SciDB: A Science-Oriented DBMS. PVLDB, 2(2):1534--1537, 2009.
11. D. DeWitt, S. Ghandeharizadeh, D. Schneider, A. Bricker, H.-I. Hsiao, and R. Rasmussen. The gamma database machine project. Trans. on Knowledge & Data Eng., 2(1):44--62, 1990.
12. D. J. DeWitt and J. Gray. Parallel database systems: The future of database processing or a passing fad? SIGMOD Record, 19(4):104--112, 1990.
13. D. J. DeWitt, R. H. Katz, F. Olken, L. D. Shapiro, M. R. Stonebraker, and D. A. Wood. Implementation techniques for main memory database systems, volume 14. June 1984.
14. D. J. DeWitt, J. F. Naughton, D. A. Schneider, and S. Seshadri. Practical skew handling in parallel joins. In VLDB, volume 92, pages 27--40, 1992.
15. S. Englert, J. Gray, T. Kocher, and P. Shah. A benchmark of non-stop sql release 2 demonstrating near-linear speedup and scaleup on large databases. Tandem Tech Report, 1989.
16. C. Faloutsos, B. Seeger, A. Traina, and C. Traina, Jr. Spatial join selectivity using power laws. SIGMOD Rec., 29(2), May 2000.
17. S. Ganguly, W. Hasan, and R. Krishnamurthy. Query Optimization for Parallel Execution. In SIGMOD, 1992.
18. F. Glover. Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5):533--549, 1986.
19. J. Gray, D. T. Liu, M. Nieto-Santisteban, A. Szalay, D. J. DeWitt, and G. Heber. Scientific data management in the coming decade. ACM SIGMOD Record, 34(4):34--41, 2005.
20. M. Kitsuregawa and Y. Ogawa. Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer. In VLDB, 1990.
21. M. Kitsuregawa, H. Tanaka, and T. Moto-Oka. Application of hash to data base machine and its architecture. New Generation Computing, 1(1):63--74, 1983.
22. Large Synoptic Survey Telescope. http://www.lsst.org.
23. J. Li, A. Deshpande, and S. Khuller. Minimizing Communication Cost in Distributed Multi-query Processing. In ICDE, 2009.
24. M. Mehta and D. J. DeWitt. Data placement in shared-nothing parallel database systems. The VLDB Journal, 6(1):53--72, 1997.
25. NASA, MODIS Website. modis.gsfc.nasa.gov/data/.
26. National Oceanic and Atmospheric Administration. Marine Cadastre. http://marinecadastre.gov/AIS/.
27. M. E. Newman. Power laws, pareto distributions and zipf's law. Contemporary Physics, 46(5):323--351, 2005.
28. G. Planthaber, M. Stonebraker, and J. Frew. Earthdb: scalable analysis of modis data using scidb. In BigSpatial '12.
29. O. Polychroniou, R. Sen, and K. A. Ross. Track join: Distributed joins with minimal network traffic. SIGMOD '14, pages 1483--1494, New York, NY, USA, 2014. ACM.
30. W. Rödiger, T. Mühlbauer, P. Unterbrunner, A. Reiser, A. Kemper, and T. Neumann. Locality-sensitive operators for parallel main-memory database clusters. In ICDE, pages 592--603, 2014.
31. D. Schneider and D. DeWitt. A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment. In SIGMOD '89.
32. P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD international conference on Management of data, pages 23--34. ACM, 1979.
33. Sloan Digital Sky Survey. http://www.sdss.org.
34. E. Soroush, M. Balazinska, and D. L. Wang. ArrayStore: a storage manager for complex parallel array processing. In SIGMOD, 2011.
35. M. Stonebraker. The case for shared nothing. IEEE Database Eng. Bull., 1986.
36. M. Stonebraker, J. Becla, D. J. DeWitt, K.-T. Lim, D. Maier, O. Ratzesberger, and S. B. Zdonik. Requirements for science data bases. In CIDR, 2009.
37. R. Taft, M. Vartak, N. R. Satish, N. Sundaram, S. Madden, and M. Stonebraker. Genbase: a complex analytics genomics benchmark. In SIGMOD Conference, pages 177--188, 2014.
38. C. B. Walton, A. G. Dale, and R. M. Jenevein. A taxonomy and performance model of data skew effects in parallel joins. In VLDB, 1991.
39. X. Wang, R. Burns, A. Terzis, and A. Deshpande. Network - Aware Join Processing in Global Scale Database Federations. In ICDE, 2008.
40. J. Wolf, D. Dias, and P. Yu. A parallel sort merge join algorithm for managing data skew. Trans. on Parallel and Dist. Systems, 1993.
41. J. Wolf, P. Yu, J. Turek, and D. Dias. A parallel hash join algorithm for managing data skew. Trans. on Parallel and Dist. Systems, 1993.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

      • Database query processing

      • Parallel and distributed DBMSs

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)