XML data partitioning strategies to improve parallelism in parallel holistic twig joins

ABSTRACT

Parallel XML query processing systems that process numerous queries over large heterogeneous XML documents often experience under-performance due to workload imbalance and low CPU/system utilization, because conventional partitioning strategies cannot serve well for state-of-the-art query processing algorithms, such as holistic twig joins. Consequently, partitioning and distributing heterogeneous XML documents onto a parallel cluster system have lead to such an intricacy issue for maintaining good query performance. In this paper, we propose XML data partitioning strategies that are able to alleviate system performance degradation due to workload imbalance, especially for parallel holistic twig joins processing. The proposed XML data partitioning strategies aim at improving workload balance on both static data distribution and dynamic data distribution. In the first strategy we refine an XML partition having a high cost by series of XML data partition refinements with various levels of granularities from document, query, and subquery, up to node streams. The selection of the granularity level for refining a high cost partition is contextually dependent on the overall workload balance in the system. In the second strategy for dynamic data distribution, we dynamically handle low system utilization when there are many idle nodes in the system. We propose an XML data redistribution approach by partitioning XML data on the fly at the stream nodes-based granularity.

REFERENCES

• 1: Niagara query engine. http://www.cs.wisc.edu/niagara.
• 2: Stanford university infolab. http://infolab.stanford.edu/pub/movies/dtd.html.
• 3: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of the 18th International Conference on Data Engineering, p.141, February 26-March 01, 2002
• 4: Toshiyuki Amagasa , Kentarou Kido , Hiroyuki Kitagawa, Querying XML Data using PC Cluster System, Proceedings of the 18th International Conference on Database and Expert Systems Applications, p.5-9, September 03-07, 2007 [doi>10.1109/DEXA.2007.118]
• 5: J.-M. Bremer and M. Gertz. On Distributing XML Repositories. In International Workshop on the Web and Databases (WebDB), pages 73--78, 2003.
• 6: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 7: Ting Chen , Jiaheng Lu , Tok Wang Ling, On boosting holism in XML twig pattern matching using structural indexing techniques, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066209]
• 8: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 9: Gang Gou , Rada Chirkova, Efficiently Querying Large XML Data Repositories: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.19 n.10, p.1381-1403, October 2007 [doi>10.1109/TKDE.2007.1060]
• 10: Raghav Kaushik , Rajasekar Krishnamurthy , Jeffrey F. Naughton , Raghu Ramakrishnan, On the integration of structure indexes and inverted lists, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007656]
• 11: Kentarou Kido , Toshiyuki Amagasa , Hiroyuki Kitagawa, Processing XPath Queries in PC-Clusters Using XML Data Partitioning, Proceedings of the 22nd International Conference on Data Engineering Workshops, p.114, April 03-07, 2006 [doi>10.1109/ICDEW.2006.120]
• 12: Hiroto Kurita , Kenji Hatano , Jun Miyazaki , Shunsuke Uemura, Efficient Query Processing for Large XML Data in Distributed Environments, Proceedings of the 21st International Conference on Advanced Networking and Applications, p.317-322, May 21-23, 2007 [doi>10.1109/AINA.2007.64]
• 13: Ying Guang Li , Stéphane Bressan , Gillian Dobbie , Zoé Lacroix , Mong Li Lee , Ullas Nambiar , Bimlesh Wadhwa, XOO7: applying OO7 benchmark to XML query processing tool, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502614]
• 14: Jiaheng Lu , Ting Chen , Tok Wang Ling, Efficient processing of XML twig patterns with parent child edges: a look-ahead approach, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031272]
• 15: Kevin Lü , Yuanling Zhu , Wenjun Sun, Parallel Processing XML Documents, Proceedings of the 2002 International Symposium on Database Engineering & Applications, p.96-105, July 17-19, 2002
• 16: Imam Machdi , Toshiyuki Amagasa , Hiroyuki Kitagawa, GMX: an XML data partitioning scheme for holistic twig joins, Proceedings of the 10th International Conference on Information Integration and Web-based Applications & Services, November 24-26, 2008, Linz, Austria [doi>10.1145/1497308.1497338]
• 17: Rizos Sakellariou , John R. Gurd, Compile-time minimisation of load imbalance in loop nests, Proceedings of the 11th international conference on Supercomputing, p.277-284, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263811]
• 18: Albrecht Schmidt , Florian Waas , Martin Kersten , Michael J. Carey , Ioana Manolescu , Ralph Busse, XMark: a benchmark for XML data management, Proceedings of the 28th international conference on Very Large Data Bases, p.974-985, August 20-23, 2002, Hong Kong, China
• 19: Nan Tang , Guoren Wang , Jeffrey Xu Yu , Kam-Fai Wong , Ge Yu, WIN: An E.cient Data Placement Strategy for Parallel XML Databases, Proceedings of the 11th International Conference on Parallel and Distributed Systems, p.349-355, July 20-22, 2005 [doi>10.1109/ICPADS.2005.298]
• 20: Haixun Wang , Sanghyun Park , Wei Fan , Philip S. Yu, ViST: a dynamic index method for querying XML data by tree structures, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872774]
• 21: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Performance

Keywords:
XML data partition, holistic twig joins, inter query parallelism, intra query parallelism