XML query processing: architecture and algorithms for optimization and execution

Abstract

This thesis proposes a design for XPath processing on relational back-ends and a design for a generic and modular framework for cost-based execution of XPath queries. Based on these designs two complete systems have been developed, the PPFx system and the GeCOEX system, respectively. PPFx is an XML database system based on identifying, processing and combining Primitive Path Fragments (PPFs) on XPath expressions that runs on top of a relational back-end. A set of novel techniques is presented that significantly limit the number of SQL joins required, take advantage of the strengths of modern SQL query processors and exploit XML schema information to achieve big performance gains with low implementation complexity. The PPF-based XPath-to-SQL translation algorithm leads to SQL queries that involve only the absolutely necessary relations, with the minimum number of structural joins and the maximum exploitation of root-to-node path ids for the holistic evaluation of multi-step PPFs based on optimized regular expression filtering method. Moreover, the thesis presents a very efficient technique for backwards navigation that substitutes expensive backward structural joins with simple and cheap string manipulation, yielding performance improvement of up to 35% for reversible descendant-ancestor structural joins and of orders of magnitude for general descendant-ancestor structural joins. Furthermore, the thesis describes an optimization technique for accelerating, under specific and well-defined conditions, queries that have forward predicates, yielding - when applicable - performance improvements that range from 61% up to 99.6%. An extensive experimental study confirms the performance benefits of all these novel techniques and shows that PPFx running on top of a commercial RDBMS is competitive with respect to query performance with other native and relational-based state-of-the-art XPath processing systems, commercial as well as research prototypes. The thesis also presents in detail a Generic and Extensible Cost-based Optimization and Execution system for XPath, named GeCOEX. The cost-based optimizer of GeCOEX always picks the cheapest estimated plan, among a very large number of possible plans, for a wide range of XPath queries and different datasets in a very small fraction of the time required for efficient execution. The optimizer is based on XPAlgebra, a novel navigation based logical algebra and on a comprehensive set of rewritings. Experimental evaluation of the effectiveness of the overall GeCOEX system have shown that the execution time of the chosen plan is within 12% of the optimal execution time in all but one of the queries in the tested workloads. The GeCOEX system contains a framework for XPath execution that includes physical operator implementations along with cost models, as well as the necessary infrastructure for their easy deployment. The framework can be effectively used with a variety of different storage engines. The thesis describes two novel families of algorithms, namely Lookup and Sort-Merge-based, for all the major XPath “operations”, including forward and backward navigation, and demonstrate experimentally their performance advantages compared to existing techniques. The algorithms are implemented as physical operators for the XPAlgebra algebra which, along with physical operator implementations corresponding to existing XPath processing techniques, are all plugged in the GeCOEX system. Experimental results provide strong evidence of the performance benefits of the execution framework in general and the Lookup and Sort-Merge-based physical operator in particular. Cost models for all proposed physical operators have been defined whose accuracy have been evaluated experimentally.

Τα τελευταία χρόνια η XML υιοθετήθηκε σε μία σειρά εφαρμογών ηλεκτρονικού επιχειρείν, ως μοντέλο ανταλλαγής μηνυμάτων μεταξύ εφαρμογών και υπηρεσιών ιστού, ως μοντέλο δεδομένων για εφαρμογές ολοκλήρωσης δεδομένων αλλά και ως μοντέλο αποθήκευσης και επεξεργασίας δεδομένων εφαρμογών. Το θέμα της διδακτορικής διατριβής είναι η επεξεργασία επερωτήσεων σε ημιδομημένα δεδομένα, και συγκεκριμένα σε XML έγγραφα, και χωρίζεται σε δύο ενότητες. Η πρώτη ενότητα αφορά στην επεξεργασία επερωτήσεων σε XML δεδομένα, επερωτήσεις των οποίων η αποδοτικότητα είναι υψίστης σημασίας για συστήματα ολοκλήρωσης πληροφορίας που βασίζονται σε XML. Η δεύτερη ενότητα αφορά στην ανάπτυξη ενός ολοκληρωμένου βελτιστοποιητή βάσει εκτίμησης κόστους για XPath επερωτήσεις, ο οποίος βασίζεται σε μία λογική άλγεβρα για XPath επερωτήσεις και στον σχεδιασμό και υλοποίηση αποδοτικών φυσικών τελεστών για τους λογικές τελεστές που περιλαμβάνει η συγκεκριμένη άλγεβρα. Ειδικότερα, όσον αφορά την πρώτη ενότητα της διδακτορικής διατριβής, μελετήθηκε η σχετική υπάρχουσα βιβλιογραφία και αναπτύχθηκε μία μέθοδος επεξεργασίας επερωτήσεων σε ημιδομημένα δεδομένα, και συγκεκριμένα σε XML, η οποία χρησιμοποιεί την λειτουργικότητα των Σχεσιακών Συστημάτων Διαχείρισης Βάσεων Δεδομένων (ΣΣΔΒΔ). Η συγκεκριμένη ερευνητική δουλειά χωρίζεται σε δύο φάσης: στην πρώτη φάση αναπτύχθηκαν οι βασικές μέθοδοι και αλγόριθμοι για την επεξεργασία αυτού του είδους των επερωτήσεων ενώ στην δεύτερη οι μέθοδοι αυτοί βελτιώθηκαν και επεκτάθηκαν σημαντικά, τόσο σε σχέση με την αποδοτικότητά τους όσο σε σχέση με την λειτουργικότητα τους. Η δεύτερη ενότητα της διδακτορικής διατριβής επικεντρώθηκε στην δημιουργία ενός βελτιστοποιητή XPath επερωτήσεων που βασίζεται σε εκτίμηση κόστους. Συγκεκριμένα δημιουργήθηκε ένα πλαίσιο βελτιστοποίησης βασιζόμενης σε εκτίμηση κόστους και εκτέλεσης XPath επερωτήσεων και εκτιμήθηκε πειραματικά η αποδοτικότητα και η αποτελεσματικότητα του συστήματος. Το πλαίσιο βασίζεται σε μία λογική XPath άλγεβρα με πρωτότυπα χαρακτηριστικά και τελεστές καθώς και σε ένα σύνολο κανόνων μετασχηματισμού που μαζί επιτρέπουν να εκφραστούν αλγεβρικά πολλές υπάρχοντες αλλά και πρωτότυπες στρατηγικές επεξεργασίας XPath επερωτήσεων. Ένα σημαντικό συστατικό στοιχείο του πλαισίου είναι ένας ιδιαίτερα αποδοτικός αλγόριθμος επιλογής φυσικού πλάνου για XPath επερωτήσεις. Ο βελτιστοποιητής είναι ανεξάρτητος του φυσικού μοντέλου δεδομένων και του συστήματος αποθήκευσης αλλά και των διαθέσιμων υλοποιήσεων φυσικών τελεστών. Βασίζεται σε ένα σύνολο καλά ορισμένων API. Αναπτύχθηκαν διάφορες υλοποιήσεις των συγκεκριμένων API, που περιλαμβάνουν βασικές μεθόδους πρόσβασης δεδομένων, οι οποίες αντιστοιχούν σε διαφορετικά συστήματα αποθήκευσης XML δεδομένων. Παράλληλε υλοποιήθηκε ένα μεγάλο σύνολο από φυσικούς τελεστές, εκτιμητές στατιστικών και μοντέλα κόστους.