بهینه سازی پرس و جوی XML با شاخص های مسیر

ABSTRACT XML Query Optimization Using Path Indexes

Over the past few years the Extensible Markup Language (XML) has became the dominant data format for information exchange. With the proliferation of data in this format comes the motivation to query and manipulate XML documents. XQuery [28] is the predominant proposal for a native XML query language standard. Query optimization proved to be the foundation of success for Relational Database Management Systems. However, while there are many XQuery implementations, the vast majority of them lack a query optimizer. We believe that there is a significant opportunity to adapt and extend mature relational optimization techniques in XML systems. As in relational systems, we can regard XML query optimization as a combination of two stages: access method selection and join order selection (these separate stages are a simplification that applies for Select-Project-Join SQL queries with no sub-queries). In relation systems, the data access operators also incorporate selection and projection operations.

This approach can be applied to the XML model as well, with one major difference: in the XML model the selection predicates are XPath expressions. The evaluation of these path expressions by different access methods used within XML engines represents the bulk of the research in XML query evaluation.

Methods for evaluating XPath expressions have been developed with the assumption that the query processor has to apply the selection condition while streaming through the document. There is extensive work on streaming XPath processors [5, 9, 12, 15, 21, 22]. These implementations use automata in order to evaluate on the fly a number of XPath expressions. Any of these processors can be encapsulated into an access method.

When a native XML system controls the storage of the XML documents, the stream processing requirement can be relaxed. Consequently, the XML documents can be pre-parsed into special purpose data structures in order to speed up query execution. One such data structure is derived from the notation used in region algebras [7], where an inverted file like structure with the element name, the begin, start and level of the text region of each element is used. Utilizing this type of data structures evaluating path expressions is equivalent to joins between lists of element regions, referred to as containment queries [27] or structural joins [2].

In the relational model, a SQL query is translated into a relational algebra expression and then optimized. Many of the XQuery implementations use the same approach, although many of the algebras in the literature are simply an API or are based on some procedural semantics. For instance, Galax [30] translates XQuery to XQuery Core [29]. Other XQuery systems, such as Timber [16], Niagara [14], Natix [10] and ToX [3] rely on a logical XML algebra. In between are systems like BEA/SQRL [11] that translates XQuery into an internal representation and performs optimization based on heuristics. Ultimately, XQuery systems implement a set of access methods.

An XQuery expression frequently contains several XPath sub-expressions, such as the example given in Figure 1. The example query joins a supplier document and a catalog document based on supplier no, returning the name and description of items in the catalog for those suppliers located in Toronto, Ontario. The XPath expressions that occur in the query above and apply to the supplier document are: //supplier’, `//supplier/supplier_no’, ‘//supplier/city’ and `//supplier/province’. A fragment of a sample supplier document is shown in Figure 2.

Although each of the XPath expressions in an XQuery expression such as the example above can be computed separately, a much better approach is to group XPath queries. The group of XPath expressions that apply to a certain document (such as suppliers in the example above) can be computed in a single pass through the document. Most of the XPath processors as well as novel structural join algorithms support this approach [4, 15, 16]. Relational query optimization relies on schema information. In the XML data model the information given by XML Schemas (or by DTDs) specifies the conditions for validity of documents. However, an XML Schema is not necessarily very descriptive about the structures occurring in a collection of XML documents. As such, XML Schema information is not well-suited for optimization. However, there are different data structures employable as schema, namely path indexes. A path index, also known as a structural index or as a structural summary, represents a summarization of the paths that actually occur in a document. That is, for each distinct path in an XML document there is a distinct path in the path index [13, 20] or an approximation of it [18, 24]. Because, a path index reflects the existing schema of the document, it can be used for optimization in a similar fashion than a relational schema.

In this paper, we describe a comprehensive approach to XML query optimization that incorporates several novel characteristics. The description in the paper focuses on ToXop, a cost-based optimizer for ToX.

The key novel contributions showcased by ToXop are:

• An original two-level approach to cost-based optimization. The higher level consists of the traditional join order selection together with the cost-based selection of access methods. The lower level cost-based optimization is entirely performed within the access method that takes advantage of the path indexes.
• The high level cost-based selection is based on just two access methods specialized for XML query processing. The first access method supports streaming (single-pass) pattern matching in XML documents, while the second access method takes advantage of path index structures for matching patterns in pre-processed XML documents.
• The lower level cost-based optimization determines how the path index will be traversed. This choice is encapsulated in the second access method described above. This access method also encapsulates the pruning of the patterns to be matched against the path index. Incorporating the path index in this lower level optimization has the benefits of constraining the query plan search space and exploiting a cost model based on XML-specific statistics
• The two access methods used by ToXop share the same data model as the operators in the native XML logical algebra. They operate on collections of trees at both levels, which should be contrasted with XML implementations in the literature that employ structural join access methods, which operate on collections of trees at the logical level, but switch to operations on collections of nodes at the physical level.

We have to note here a similarity of the work that we present in the XML context, with earlier the work in query optimization for Object Oriented Databases (00DB) [6, 8, 19]. For instance, Access Support Relations (ASRs) provide an indexing mechanism for paths like XML path indexes. Despite the similarities, in the OODB context the schema information is known, while this is frequently not the case in the XML context. Moreover, ASRs may cover only some paths from the database instance, while in the XML context the path indexes cover all paths from the document instance. Finally, previous work on optimization that incorporates ASRs does not employ the two-level cost-based access method selection introduced in this paper. In the following section we introduce the cost-based access method selection employed by ToXop (the high level optimization). Section 3 describes the use of path indexes within an access method that performs the low-level cost-based optimization. We conclude by mentioning future research in Section 4.