Optimal splitters for database partitioning with size bounds

ABSTRACT

Partitioning is an important step in several database algorithms, including sorting, aggregation, and joins. Partitioning is also fundamental for dividing work into equal-sized (or balanced) parallel subtasks. In this paper, we aim to find, materialize and maintain a set of partitioning elements (splitters) for a data set. Unlike traditional partitioning elements, our splitters define both inequality and equality partitions, which allows us to bound the size of the inequality partitions. We provide an algorithm for determining an optimal set of splitters from a sorted data set and show that it has time complexity O(k lg² N), where k is the number of splitters requested and N is the size of the data set. We show how the algorithm can be extended to pairs of tables, so that joins can be partitioned into work units that have balanced cost. We demonstrate experimentally (a) that finding the optimal set of splitters can be done efficiently, and (b) that using the precomputed splitters can improve the time to sort a data set by up to 76%, with particular benefits in the presence of a few heavy hitters.

REFERENCES

• 1: R. Agrawal and A. Swami. A one-pass space-efficient algorithm for finding quantiles. In COMAD, 1995.
• 2: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 3: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider, Parallel sorting on a shared-nothing architecture using probabilistic splitting, Proceedings of the first international conference on Parallel and distributed information systems, p.280-291, December 1991, Miami, Florida, United States
• 4: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider , S. Seshadri, Practical Skew Handling in Parallel Joins, Proceedings of the 18th International Conference on Very Large Data Bases, p.27-40, August 23-27, 1992
• 5: J. Doweck. Inside intel core microarchitecture. In Hot Chips, August 2006.
• 6: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 7: Shahram Ghandeharizadeh , David J. DeWitt, Hybrid-Range Partitioning Strategy: A New Declustering Strategy for Multiprocessor Database Machines, Proceedings of the 16th International Conference on Very Large Data Bases, p.481-492, August 13-16, 1990
• 8: Jim Gray , Prakash Sundaresan , Susanne Englert , Ken Baclawski , Peter J. Weinberger, Quickly generating billion-record synthetic databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.243-252, May 24-27, 1994, Minneapolis, Minnesota, United States
• 9: A. P. Gurajada and J. Srivastava. Equidepth partitioning of a data set based on finding its medians. In Applied Computing, pages 92--101, 1991.
• 10: Peter J. Haas , Arun N. Swami, Sampling-Based Selectivity Estimation for Joins Using Augmented Frequent Value Statistics, Proceedings of the Eleventh International Conference on Data Engineering, p.522-531, March 06-10, 1995
• 11: Kien A. Hua , Chiang Lee, Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning, Proceedings of the 17th International Conference on Very Large Data Bases, p.525-535, September 03-06, 1991
• 12: J. Huang and Y. Chow. Parallel sorting and data partitioning by sampling. In Proc. of Symposium on Parallel Algorithms and Architectures, pages 627--631, 1983.
• 13: Yannis Ioannidis, The history of histograms (abridged), Proceedings of the 29th international conference on Very large data bases, p.19-30, September 09-12, 2003, Berlin, Germany
• 14: Yannis E. Ioannidis , Viswanath Poosala, Balancing histogram optimality and practicality for query result size estimation, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.233-244, May 22-25, 1995, San Jose, California, United States
• 15: Yannis E. Ioannidis , Viswanath Poosala, Histogram-Based Approximation of Set-Valued Query-Answers, Proceedings of the 25th International Conference on Very Large Data Bases, p.174-185, September 07-10, 1999
• 16: B. R. Iyer , G. R. Ricard , P. J. Varman, Percentile finding algorithm for multiple sorted runs, Proceedings of the 15th international conference on Very large data bases, p.135-144, July 1989, Amsterdam, The Netherlands
• 17: H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel, Optimal Histograms with Quality Guarantees, Proceedings of the 24rd International Conference on Very Large Data Bases, p.275-286, August 24-27, 1998
• 18: Sanjeev Khanna , S. Muthukrishnan , Steven Skiena, Efficient Array Partitioning, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.616-626, July 07-11, 1997
• 19: Masaru Kitsuregawa , Yasushi Ogawa, Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC), Proceedings of the 16th International Conference on Very Large Data Bases, p.210-221, August 13-16, 1990
• 20: Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Approximate medians and other quantiles in one pass and with limited memory, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.426-435, June 01-04, 1998, Seattle, Washington, United States
• 21: Conrado Martínez , Salvador Roura, Optimal Sampling Strategies in Quicksort and Quickselect, SIAM Journal on Computing, v.31 n.3, p.683-705, 2001 [doi>10.1137/S0097539700382108]
• 22: David R. Musser, Introspective sorting and selection algorithms, Software—Practice & Experience, v.27 n.8, p.983-993, Aug. 1997 [doi>10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#]
• 23: S. Muthukrishnan , Viswanath Poosala , Torsten Suel, On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications, Proceedings of the 7th International Conference on Database Theory, p.236-256, January 10-12, 1999
• 24: Viswanath Poosala , Yannis E. Ioannidis, Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing, Proceedings of the 22th International Conference on Very Large Data Bases, p.448-459, September 03-06, 1996
• 25: Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.294-305, June 04-06, 1996, Montreal, Quebec, Canada
• 26: P. Sanders and S. Winkel. Super scalar sample sort. In European Symposium on Algorithms, pages 784--796, 2004.
• 27: Mike Stonebraker , Daniel J. Abadi , Adam Batkin , Xuedong Chen , Mitch Cherniack , Miguel Ferreira , Edmond Lau , Amerson Lin , Sam Madden , Elizabeth O'Neil , Pat O'Neil , Alex Rasin , Nga Tran , Stan Zdonik, C-store: a column-oriented DBMS, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway