Parallelization of XPath queries using multi-core processors: challenges and experiences

ABSTRACT

In this study, we present experiences of parallelizing XPath queries using the Xalan XPath engine on shared-address space multi-core systems. For our evaluation, we consider a scenario where an XPath processor uses multiple threads to concurrently navigate and execute individual XPath queries on a shared XML document. Given the constraints of the XML execution and data models, we propose three strategies for parallelizing individual XPath queries: Data partitioning, Query partitioning, and Hybrid (query and data) partitioning. We experimentally evaluated these strategies on an x86 Linux multi-core system using a set of XPath queries, invoked on a variety of XML documents using the Xalan XPath APIs. Experimental results demonstrate that the proposed parallelization strategies work very effectively in practice; for a majority of XPath queries under evaluation, the execution performance scaled linearly as the number of threads was increased. Results also revealed the pros and cons of the different parallelization strategies for different XPath query patterns.

REFERENCES

• 1: DBLP XML Dataset. http://dblp.uni-trier.de/xml.
• 2: SQL/XML Standard. www.sqlx.org.
• 3: The PENN Treebank Project. http://www.cis.upenn.edu/treebank.
• 4: Web Services Activities at W3C. www.w3.org/2002/ws.
• 5: XML Schema Activities at W3C. http://www.w3.org/XML/Schema.
• 6: Peter Buneman , Gao Cong , Wenfei Fan , Anastasios Kementsietsidis, Using partial evaluation in distributed query evaluation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 7: Gao Cong , Wenfei Fan , Anastasios Kementsietsidis, Distributed query evaluation with performance guarantees, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247537]
• 8: World Wide Web Consortium (W3C), XML Path Language (XPath) 2.0, W3C Recommendation, 23 January 2007. www.w3.org.
• 9: World Wide Web Consortium (W3C), XQuery 1.0: An XML Query Language, W3C Recommendation, 23 January 2007. www.w3.org.
• 10: World Wide Web Consortium (W3C), XQuery 1.0 and XPath 2.0 Data Model (XDM), W3C Recommendation, 23 January 2007. www.w3.org.
• 11: World Wide Web Consortium (W3C), XSL Transformations (XSLT) 2.0, W3C Recommendation, 23 January 2007. www.w3.org.
• 12: Georg Gottlob , Christoph Koch , Reinhard Pichler, Efficient algorithms for processing XPath queries, ACM Transactions on Database Systems (TODS), v.30 n.2, p.444-491, June 2005 [doi>10.1145/1071610.1071614]
• 13: Herlihy, M., and Shavit, N. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008.
• 14: M. F. Khan , Ray Paul , Ishfaq Ahmed , Arif Ghafoor, Intensive Data Management in Parallel Systems: A Survey, Distributed and Parallel Databases, v.7 n.4, p.383-414, Oct. 1999 [doi>10.1023/A:1026458902456]
• 15: Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000 [doi>10.1145/371578.371598]
• 16: Hongjun Lu , K. L. Tan , Beng-Chin Ooi, Query Processing in Parallel Relational Database Systems, IEEE Computer Society Press, Los Alamitos, CA, 1994
• 17: Wei Lu , Kenneth Chiu , Yinfei Pan, A Parallel Approach to XML Parsing, Proceedings of the 7th IEEE/ACM International Conference on Grid Computing, p.223-230, September 28-29, 2006 [doi>10.1109/ICGRID.2006.311019]
• 18: Wei Lu , Dennis Gannon, Parallel XML processing by work stealing, Proceedings of the 2007 workshop on Service-oriented computing performance: aspects, issues, and approaches, p.31-38, June 25-25, 2007, Monterey, California, USA [doi>10.1145/1272457.1272462]
• 19: Yinfei Pan , Wei Lu , Ying Zhang , Kenneth Chiu, A Static Load-Balancing Scheme for Parallel XML Parsing on Multicore CPUs, Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid, p.351-362, May 14-17, 2007 [doi>10.1109/CCGRID.2007.14]
• 20: Albrecht Schmidt , Florian Waas , Martin Kersten , Daniela Florescu , Michael J. Carey , Ioana Manolescu , Ralph Busse, Why and how to benchmark XML databases, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603872]
• 21: Dan Suciu, Distributed query evaluation on semistructured data, ACM Transactions on Database Systems (TODS), v.27 n.1, p.1-62, March 2002 [doi>10.1145/507234.507235]