18.4 Benchmark Queries

   

---

In creating the data set above, we make it possible to tease apart data with different characteristics and to issue queries with well-controlled yet vastly differing data access patterns. We are more interested in evaluating the cost of individual pieces of core query functionality than in evaluating the composite performance of application-level queries. Knowing the costs of individual basic operations, we can estimate the cost of any complex query by just adding up relevant piecewise costs (keeping in mind the pipelined nature of evaluation, and the changes in sizes of intermediate results when operators are pipelined).

One clean way to decompose complex queries is by means of algebra. While the benchmark is not tied to any particular algebra, we find it useful to refer to queries as "selection queries," "join queries," and the like, to clearly indicate the functionality of each query. A complex query that involves many of these simple operations can take time that varies monotonically with the time required for these simple components.

In the following sections, we describe each of these different types of queries in detail. In these queries, the types of the nodes are assumed to be BaseType (eNest nodes) unless specified otherwise.

18.4.1 Selection

Relational selection identifies the tuples that satisfy a given predicate over its attri-butes. XML selection is both more complex and more important because of the tree structure. Consider a query, against a popular bibliographic database, that seeks books, published in the year 2002, by an author with name including the string "Bernstein". This apparently straightforward selection query involves matches in the database to a four-node "query pattern," with predicates associated with each of these four (namely book, year, author, and name). Once a match has been found for this pattern, we may be interested in returning only the book element, all the nodes that participated in the match, or various other possibilities. We attempt to orga-nize the various sources of complexity in the following sections.

Returned Structure

In a relation, once a tuple is selected, the tuple is returned. In XML, as we saw in the example above, once an element is selected, one may return the element, as well as some structure related to the element, such as the subtree rooted at the element. Query performance can be significantly affected by how the data are stored and when the returned result is materialized.

To understand the role of returned structure in query performance, we use the query, selecting all elements with aSixtyFour = 2. The selectivity of this query is 1/64 (1.6%).

This query is run in the following cases:

• QR1: Return only the elements in question, not including any subelements

• QR2: Return the elements and all their immediate children

• QR3: Return the entire subtree rooted at the elements

• QR4: Return the elements and their selected descendants with aFour = 1

The remaining queries in the benchmark simply return the unique identifier attributes of the selected nodes (aUnique1 for eNest and aRef for eOccasional), except when explicitly specified otherwise. This design choice ensures that the cost of producing the final result is a small portion of the query execution cost.

Simple Selection

Even XML queries involving only one element and a single predicate can show considerable diversity. We examine the effect of this single selection predicate in this set of queries.

Exact Match Attribute Value Selection

Selection based on the value of a string attribute.

QS1. Low selectivity: Select nodes with aString = "Sing a song of oneB4". Selectivity is 0.8%.

QS2. High selectivity: Select nodes with aString = "Sing a song of oneB1". Selectivity is 6.3%.

Selection based on the value of an integer attribute.

We reproduce the same selectivities as in the string attribute case.

QS3. Low selectivity: Select nodes with aLevel = 10. Selectivity is 0.7%.

QS4. High selectivity: Select nodes with aLevel = 13. Selectivity is 6.0%.

Selection on range values.

QS5: Select nodes with aSixtyFour between 5 and 8. Selectivity is 6.3%.

Selection with sorting.

QS6: Select nodes with aLevel = 13 and have the returned nodes sorted by aSixtyFour attribute. Selectivity is 6.0%.

Multiple-attribute selection.

QS7: Select nodes with attributes aSixteen = 1 and aFour = 1. Selectivity is 1.6%.

Element Name Selection

QS8: Select nodes with the element name eOccasional. Selectivity is 1.6%.

Order-Based Selection

QS9: Select the second child of every node with aLevel = 7. Selectivity is 0.4%.

QS10: Select the second child of every node with aLevel = 9. Selectivity is 0.4%.

Since the fraction of nodes in these two queries is the same, the performance difference between queries QS9 and QS10 is likely to be on account of fanout.

Element Content Selection

QS11: Select OccasionalType nodes that have "oneB4" in the element content. Selectivity is 0.2%.

QS12: Select nodes that have "oneB4" as a substring of element content. Selectivity is 12.5%.

String Distance Selection

QS13. Low selectivity: Select all nodes with element content that the distance between keyword"oneB5" and keyword "twenty" is not more than four. Selectivity is 0.8%.

QS14. High selectivity: Select all nodes with element content that the distance between keyword "oneB2" and keyword "twenty" is not more than four. Selectivity is 6.3%.

Structural Selection

Selection in XML is often based on patterns. Queries should be constructed to consider multinode patterns of various sorts and selectivities. These patterns often have "conditional selectivity." Consider a simple two-node selection pattern. Given that one of the nodes has been identified, the selectivity of the second node in the pattern can differ from its selectivity in the database as a whole. Similar dependencies between different attributes in a relation could exist, thereby affecting the selectivity of a multiattribute predicate. Conditional selectivity is complicated in XML because different attributes may not be in the same element, but rather in different elements that are structurally related.

In this section, all queries return only the root of the selection pattern, unless otherwise specified.

Parent-Child Selection

QS15. Medium selectivity of both parent and child: Select nodes with aLevel = 13 that have a child with aSixteen = 3. Selectivity is approximately 0.7%.

QS16. High selectivity of parent and low selectivity of child: Select nodes with aLevel = 15 that have a child with aSixtyFour = 3. Selectivity is approximately 0.7%.

QS17. Low selectivity of parent and high selectivity of child: Select nodes with aLevel = 11 that have a child with aFour = 3. Selectivity is approximately 0.7%.

Order-Sensitive Parent-Child Selection

QS18. Local ordering: Select the second element below each element with aFour = 1 if that second element also has aFour = 1. Selectivity is 3.1%.

QS19. Global ordering: Select the second element with aFour = 1 below any element with aSixtyFour = 1. This query returns at most one element, whereas the previous query returns one for each parent.

QS20. Reverse ordering: Among the children with aSixteen = 1 of the parent element with aLevel = 13, select the last child. Selectivity is 0.7%.

Ancestor-Descendant Selection

QS21. Medium selectivity of both ancestor and descendant: Select nodes with aLevel = 13 that have a descendant with aSixteen = 3. Selectivity is 3.5%.

QS22. High selectivity of ancestor and low selectivity of descendant: Select nodes with aLevel = 15 that have a descendant with aSixtyFour = 3.Selectivity is 0.7%.

QS23. Low selectivity of ancestor and high selectivity of descendant: Select nodes with aLevel = 11 that have a descendant with aFour = 3. Selectivity is 1.5%.

Ancestor Nesting in Ancestor-Descendant Selection

In the ancestor-descendant queries above (QS21?QS23), ancestors are never nested below other ancestors. To test the performance of queries when ancestors are recursively nested below other ancestors, we have three other ancestor-descendant queries. These queries are variants of QS21?QS23.

QS24. Medium selectivity of both ancestor and descendant: Select nodes with aSixteen = 3 that have a descendant with aSixteen = 5.

QS25. High selectivity of ancestor and low selectivity of descendant: Select nodes with aFour = 3 that have a descendant with aSixtyFour = 3.

QS26. Low selectivity of ancestor and high selectivity of descendant: Select nodes with aSixtyFour = 9 that have a descendant with aFour = 3.

The overall selectivities of these queries (QS24?QS26) cannot be the same as that of the "equivalent" unnested queries (QS21?QS23) for two situations. First, the same descendants can now have multiple ancestors they match, and second, the number of candidate descendants is different (fewer) since the ancestor predicate can be satisfied by nodes at any level. These two situations may not necessarily cancel each other out. We focus on the local predicate selectivities and keep these the same for all of these queries (as well as for the parent-child queries considered before).

QS27: Similar to query QS26, but return both the root node and the descendant node of the selection pattern. Thus, the returned structure is a pair of nodes with an inclusion relationship between them.

Complex Pattern Selection

Complex pattern matches are common in XML databases, and in this section, we introduce a number of chain and twig queries that we use in this benchmark. Figure 18.1 shows an example of each of these types of queries.

Figure 18.1. Samples of Chain and Twig Queries

In the figure, each node represents a predicate such as an element tag name predicate, an attribute value predicate, or an element content match predicate. A structural parent-child relationship in the query is shown by a single line, and an ancestor-descendant relationship is represented by a double-edged line. The chain query shown in (i) finds all nodes that match the condition A, such that there is a child node that matches the condition B, such that some descendant of the child node matches the condition C. The twig query shown in (ii) matches all nodes that satisfy the condition A, and have a child node that satisfies the condition B, and also has a descendant node that satisfies the condition C.

We use the following complex queries in our benchmark.

Parent-Child Complex Pattern Selection

QS28. One chain query with three parent-child joins with the selectivity pattern: high-low-low-high: The query is to test the choice of join order in evaluating a complex query. To achieve the desired selectivities, we use the following predicates: aFour = 3, aSixteen = 3, aSixteen = 5, and aLevel = 16.

QS29. One twig query with two parent-child selection (low-high, low-low): Select parent nodes with aLevel = 11 (low selectivity) that have a child with aFour = 3 (high selectivity) and another child with aSixtyFour = 3 (low selectivity).

QS30. One twig query with two parent-child selection (high-low, high-low): Select parent nodes with aFour = 1 (high selectivity) that have a child with aLevel = 11 (low selectivity) and another child with aSixtyFour = 3 (low selectivity).

Ancestor-Descendant Complex Pattern Selection

QS31?QS33: Repeat queries QS28?QS30 but using ancestor-descendant in place of parent-child.

QS34. One twig query with one parent-child selection and one ancestor-descendant selection: Select nodes with aFour = 1 that have a child of nodes with aLevel = 11 and a descendant with aSixtyFour = 3.

Negated Selection

QS35: Find all BaseType elements below which do not contain an OccasionalType element.

18.4.2 Value-Based Join

A value-based join involves comparing values at two different nodes that need not be related structurally. In computing the value-based joins, one would naturally expect both nodes participating in the join to be returned. As such, the return structure is a tree per join-pair. Each tree has a join-node as the root, and two children, one corresponding to each element participating in the join.

QJ1. Low selectivity: Select nodes with aSixtyFour = 2 and join with themselves based on the equality of aUnique1 attribute. The selectivity of this query is approximately 1.6%.

QJ2. High selectivity: Select nodes based on aSixteen = 2 and join with themselves based on the equality of aUnique1 attribute. The selectivity of this query is approximately 6.3%.

18.4.3 Pointer-Based Join

The difference between these following queries and the join queries based on values QJ1?QJ2 is that references that can be specified in the DTD or XML Schema may be optimized with logical OIDs in some XML databases.

QJ3. Low selectivity: Select all OccasionalType nodes that point to a node with aSixtyFour = 3. Selectivity is 0.02%.

QJ4. High selectivity: Select all OccasionalType nodes that point to a node with aFour = 3. Selectivity is 0.4%.

Both of these pointer-based joins are semi-join queries. The returned elements are only the eOccasional nodes, not the nodes pointed to.

18.4.4 Aggregation

Aggregate queries are very important for data-warehousing applications. In XML, aggregation also has richer possibilities due to the structure. These are explored in the next set of queries.

QA1. Value aggregation: Compute the average value for the aSixtyFour attribute of all nodes at level 15. Note that about 1/4 of all nodes are at level 15. The number of returned nodes is 1.

QA2. Value aggregation with group by: Group nodes by level. Compute the average value of the aSixtyFour attribute of all nodes at each level. The return structure is a tree, with a dummy root and a child for each group. Each leaf (child) node has one attribute for the level and one attribute for the average value. The number of returned trees is 16.

QA3. Value aggregate selection: Select elements that have at least two occurrences of keyword "oneB1" in their content. Selectivity is 0.3%.

QA4. Structural aggregation. Among the nodes at level 11, find the node(s) with the largest fanout. 1/64 of the nodes are at level 11. Selectivity is 0.02%.

QA5. Structural aggregate selection: Select elements that have at least two children that satisfy aFour = 1. Selectivity is 3.1%.

QA6. Structural exploration: For each node at level 7 (have aLevel = 7, determine the height of the subtree rooted at this node. Selectivity is 0.4%. Other functionalities, such as casting, also can be significant performance factors for engines that need to convert data types. However, in this benchmark, we focus on testing the core functionality of the XML engines.

18.4.5 Updates

QU1. Point Insert: Insert a new node BaseType node below the node with aUnique1 = 10102. The new node has attributes identical to its parent, except for aUnique1, which is set to some new large, unique value.

QU2. Point Delete: Delete the node with aUnique1 = 10102 and transfer all its children to its parent.

QU3. Bulk Insert: Insert a new BaseType node below each node with aSixtyFour = 1. Each new node has attributes identical to its parent, except for aUnique1, which is set to some new large, unique value.

QU4. Bulk Delete: Delete all leaf nodes with aSixteen = 3.

QU5. Bulk Load: Load the original data set from a (set of) document(s).

QU6. Bulk Reconstruction: Return a set of documents, one for each subtree rooted at level 11 (have aLevel = 11) and with a child of type eOccasional.

QU7. Restructuring: For a node u of type eOccasional, let v be the parent of u, and w be the parent of v in the database. For each such node u, make u a direct child of w in the same position as v, and place v (along with the subtree rooted at v) under u.

---

Top Title TOC Preface P.1 What Is XML? P.2 XML Concepts P.3 XML-Related Technologies P.4 XML Data Management P.5 How This Book Is Organized P.6 Who Should Read This Book P.7 Resources Acknowledgments Chapter 8 Chapter 12 Chapter 13 Chapter 14 Chapter 19 Part I: What Is XML? Chapter 1. Information Modeling with XML 1.1 Introduction 1.2 XML as an Information Domain 1.3 How XML Expresses Information 1.4 Patterns in XML 1.5 Common XML Information-Modeling Pitfalls 1.6 A Very Simple Way to Design XML 1.7 Conclusion Part II: Native XML Databases Chapter 2. Tamino-Software AG's Native XML Server 2.1 Introduction 2.2 Tamino Architecture and APIs 2.3 XML Storage 2.4 Querying XML 2.5 Tools 2.6 Full Database Functionality 2.7 Conclusion Chapter 3. eXist Native XML Database 3.1 Introduction 3.2 Features 3.3 System Architecture Overview 3.4 Getting Started 3.5 Query Language Extensions 3.6 Application Development 3.7 Technical Background 3.8 Conclusion Chapter 4. Embedded XML Databases 4.1 Introduction 4.2 A Primer on Embedded Databases 4.3 Embedded XML Databases 4.4 Building Applications for Embedded XML Databases 4.5 Conclusion Part III: XML and Relational Databases Chapter 5. IBM XML-Enabled Data Management Product Architecture & Technology 5.1 Introduction 5.2 Product and Technology Offering Summaries 5.3 Current Architecture and Technology 5.4 Future Architecture and Technology 5.5 Conclusion Notices Chapter 6. Supporting XML in Oracle9i 6.1 Introduction 6.2 Storing XML as CLOB 6.3 XMLType 6.4 Using XSU for Fine-Grained Storage 6.5 Building XML Documents from Relational Data 6.6 Web Access to the Database 6.7 Special Oracle Features 6.8 Conclusion Chapter 7. XML Support in Microsoft SQL Server 2000 7.1 Introduction 7.2 XML and Relational Data 7.3 XML Access to SQL Server 7.4 Serializing SQL Query Results into XML 7.5 Providing Relational Views over XML 7.6 SQLXML Templates 7.7 Providing XML Views over Relational Data 7.8 Conclusion Chapter 8. A Generic Architecture for Storing XML Documents in a Relational Database 8.1 Introduction 8.2 System Architecture 8.3 The Data Model 8.4 Creating the Database 8.5 Connecting to the Repository 8.6 Uploading XML Documents 8.7 Querying the Repository 8.8 Further Enhancements 8.9 Conclusion Chapter 9. An Object-Relational Approach to Building a High-Performance XML Repository 9.1 Introduction 9.2 Overview of XML Use-Case Scenario 9.3 High-Level System Architecture 9.4 Detailed Design Descriptions 9.5 Conclusion Part IV: Applications of XML Chapter 10. Knowledge Management in Bioinformatics 10.1 Introduction 10.2 A Brief Molecular Biology Background 10.3 Life Sciences Are Turning to XML to Model Their Information 10.4 A Genetic Information Model 10.5 NeoCore XMS* 10.6 Integration of BLAST into NeoCore XMS Conclusion Chapter 11. Case Studies of XML Used with IBM DB2 Universal Database 11.1 Introduction 11.2 Case Study 1: "Our Most Valued Customers Come First" 11.3 Case Study 2: "Improve Cash Flow" 11.4 Conclusion Notices Chapter 12. The Design and Implementation of an Engineering Data Management System Using XML and J2EE 12.1 Introduction 12.2 Background and Requirements 12.3 Overview 12.4 Design Choices 12.5 Future Directions 12.6 Conclusion Chapter 13. Geographical Data Interchange Using XML-Enabled Technology within the GIDB System 13.1 Introduction 13.2 GIDB METOC Data Integration 13.3 GIDB Web Map Service Implementation 13.4 GIDB GML Import and Export 13.5 Conclusion Chapter 14. Space Wide Web by Adapters in Distributed Systems Configuration from Reusable Components 14.1 Introduction 14.2 Advanced Concept Description: The Research Problem 14.3 Integration of Components with Architecture 14.4 Example 14.5 Future Generation NASA Institute for Advanced Concepts, Space Wide Web Research, and Boundaries 14.6 Advanced Concept Development 14.7 Conclusion Chapter 15. XML as a Unifying Framework for Inductive Databases 15.1 Introduction 15.2 Past Work 15.3 The Proposed Data Model: XDM 15.4 Benefits of XDM 15.5 Toward Flexible and Open Systems 15.6 Related Work 15.7 Conclusion Chapter 16. Designing and Managing an XML Warehouse 16.1 Introduction 16.2 Architecture 16.3 Data Warehouse Specification 16.4 Managing the Metadata 16.5 Storage and Management of the Data Warehouse 16.6 DAWAX: A Graphic Tool for the Specification and Management of a Data Warehouse 16.7 Related Work 16.8 Conclusion Part V: Performance and Benchmarks Chapter 17. XML Management System Benchmarks 17.1 Introduction 17.2 Benchmark Specification 17.3 Benchmark Data Set 17.4 Existing Benchmarks for XML 17.5 Conclusion Chapter 18. The Michigan Benchmark: A Micro-Benchmark for XML Query Performance Diagnostics 18.1 Introduction 18.2 Related Work 18.3 Benchmark Data Set 18.4 Benchmark Queries 18.5 Using the Benchmark 18.6 Conclusion Chapter 19. A Comparison of Database Approaches for Storing XML Documents 19.1 Introduction 19.2 Data Models for XML Documents 19.3 Databases for Storing XML Documents 19.4 Benchmarking Specification 19.5 Test Results 19.6 Related Work 19.7 Summary Chapter 20. Performance Analysis between an XML-Enabled Database and a Native XML Database 20.1 Introduction 20.2 Related Work 20.3 Methodology 20.4 Database Design 20.5 Discussion 20.6 Experiment Result 20.7 Conclusion Chapter 21. Conclusion References Contributors Editors Chapter 1: Information Modeling with XML Chapter 2: Tamino-Software AG's Native XML Server Chapter 3: eXist Native XML Database Chapter 4: Embedded XML Databases Chapter 5: IBM XML-Enabled Data Management Product Architecture and Technology Chapter 6: Supporting XML in Oracle9i Chapter 7: XML Support in Microsoft SQL Server 2000 Chapter 8: A Generic Architecture for Storing XML Documents in a Relational Database Chapter 9: An Object-Relational Approach to Building a High-Performance XML Repository Chapter 10: Knowledge Management in Bioinformatics Chapter 11: Case Studies of XML Used with IBM DB2 Universal Database Chapter 12: The Design and Implementation of an Engineering Data Management System Using XML and J2EE Chapter 13: Geographical Data Interchange Using XML-Enabled Technology within the GIDB System Chapter 14: Space Wide Web by Adapters in Distributed Systems Configuration from Reusable Components Chapter 15: XML as a Unifying Framework for Inductive Databases Chapter 16: Designing and Managing an XML Warehouse Chapter 17: XML Management System Benchmarks Chapter 18: The Michigan Benchmark: A Micro-Benchmark for XML Query Performance Diagnostics Chapter 19: A Comparison of Database Approaches for Storing XML Documents Chapter 20: Performance Analysis between an XML-Enabled Database and a Native XML Database Remember the name: eTutorials.org Copyright eTutorials.org 2008-2023. All rights reserved.