Database Management Sys3

On Supporting Containment Queries in Relational Database Management Systems Chun Zhang, Jeffrey Naughton, David DeWitt, Qiong Luo Department of Computer Sciences University of Wisconsin, Madison czhang,naughton,dewitt,[email protected] ABSTRACT Virtually all proposals for querying XML include a class of query we term “containment queries”. It is also clear that in the foreseeable future, a substantial amount of XML data will be stored in relational database systems. This raises the question of how to support these containment queries. The inverted list technology that underlies much of Information Retrieval is well-suited to these queries, but should we implement this technology (a) in a separate loosely-coupled IR engine, or (b) using the native tables and query execution machinery of the RDBMS? With option (b), more than twenty years of work on RDBMS query optimization, query execution, scalability, and concurrency control and recovery immediately extend to the queries and structures that implement these new operations. But all this will be irrelevant if the performance of option (b) lags that of (a) by too much. In this paper, we explore some performance implications of both options using native implementations in two commercial relational database systems and in a special purpose inverted list engine. Our performance study shows that while RDBMSs are generally poorly suited for such queries, under certain conditions they can outperform an inverted list engine. Our analysis further identifies two significant causes that differentiate the performance of the IR and RDBMS implementations: the join algorithms employed and the hardware cache utilization. Our results suggest that contrary to most expectations, with some modifications, a native implementation in an RDBMS can support this class of query much more efficiently.

1.

INTRODUCTION

In virtually every query language proposed for XML (including Lorel [1], YATL [33], XQL [24], XML-QL [12], Quilt [6], and even more generic SGML query languages [7, 38]), containment queries play a prominent role. By “containment query” we mean queries that are based on the containment and proximity relationships among elements, attributes, and their contents.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SIGMOD ’01 Santa Barbara, California USA Copyright 2001 ACM 0-89791-88-6/97/05 ...$5.00.

Guy Lohman IBM Almaden Research Center San Jose, California [email protected]

While there is a great deal of work being done on how to support such query languages in special purpose query engines [16, 19, 31, 23, 26, 25], it is clear that in the foreseeable future a great deal of XML data will be stored in relational database systems. (As evidence for this, notice that major DBMS vendors including IBM, Microsoft, and Oracle are investing substantial resources toward improving their system support for XML data.) Since containment queries are an important aspect of querying XML data, and RDBMSs must support the storage and querying of XML data, the question arises: how should we support containment queries in RDBMS? The inverted list technology that underlies much of Information Retrieval is well-suited to containment queries, but should we implement this technology (a) in a loosely-coupled IR engine, or (b) using the native tables and query machinery of the RDBMS? Commercial products such as the Oracle InterMedia Text and DB2 text extenders take option (a), where a special purpose IR engine is coupled with the database engine. Users employ certain operators (e.g.,“about” in Oracle InterMedia Text, “synonym form of” in DB2 Text Extender, and “contains” in both) to tell the system to route parts of the query to the IR engine. Query results from both engines are then combined before returning to the user. In this type of system, a “glue” module must be used between the IR engine and the main database engine to handle locking, concurrency control and recovery. In addition, the optimizer has no choice as to which engine should execute which part of a query, since the use of the “IR” engine is dictated by the use of special predicates when the query was framed. Option (b) directly utilizes the database storage and processing power to process containment queries. More than twenty years of work on query optimization, query execution, scalability, and concurrency control and recovery immediately extend to the queries and structures that implement the new operations. In addition, this approach has the advantage of one unified optimization and execution framework for all queries. However, all this will be irrelevant if the performance of the native implementation lags that of the “coupled” implementation by too much. In this paper we take a first step in exploring the two options. We compare the implementation of containment queries using native support in two commercial relational database systems and in a special purpose inverted list engine. We transform the inverted index into relational tables and convert containment queries into SQL queries. It turns out that a native implementation using an RDBMS can process queries that are either difficult or impossible to process

by an inverted list engine. Our performance study shows that while RDBMSs are generally poorly suited for containment queries, under certain conditions they can outperform the inverted list engine. Also, our experiments point to two significant causes that differentiate the performance of the IR and RDBMS implementations: (1) the join algorithms employed, and (2) the hardware cache utilization achieved. The inverted list engine uses a merge join that we term Multi-Predicate Merge Join (MPMGJN), as its workhorse join operator. This algorithm is different from the standard merge join and the index nested-loop join algorithms, and the difference has a significant impact on performance. To isolate algorithmic differences from other factors, we implemented the standard merge join and the index nested-loop join ourselves. We compare the join algorithms in great detail and our experimental results show that MPMGJN could out-perform the standard RDBMS join algorithms by more than an order of magnitude on containment queries. Additionally, with main memory sizes getting larger and the memory hierarchy getting deeper, many researchers have recognized the importance of hardware cache utilization on performance [2, 36, 29]. We conducted experiments to see whether there is a significant difference between the inverted list engine and the RDBMS. The answer is yes. To the best of our knowledge, this is the first paper that studies and compares a merge join using multiple predicates with standard join algorithms and shows their impact on hardware cache utilization. The rest of the paper is organized as follows: Section 2 describes containment queries, their processing using the inverted index, and the translation of the inverted index into relations and containment queries into SQL queries. Section 3 details our performance study and analysis comparing the two types of systems: an inverted list engine and the RDBMS. Section 4 discusses related work, and Section 5 concludes.

2.

CONTAINMENT QUERY PROCESSING

Containment queries are a class of queries based on containment relationships among elements, attributes, and their contents. This class subsumes database path expressions (including regular path expressions) and Information Retrieval Boolean and proximity queries. In this section we first use examples to illustrate these queries and establish their importance, we then show how to use the inverted index and the relational database system to process basic containment queries. Since complex containment queries can be reduced to a sequence of more basic ones, and basic containment queries shed more light on the fundamental determinants of performance, we mostly focus on simple containment queries such as “title contains ‘galaxy’ ”.

2.1 Containment Queries Descriptions of path expressions can be found in LoreL [1] and Quilt [6]. Quilt path expressions are based on the abbreviated syntax of XPath [21]. Since Quilt is the first XML query language that satisfies the W3C XML Query Requirements [5] and XPath became a W3C recommendation in November 1999, the Quilt style of path expressions is likely to be widely used. Thus we adopt its syntax to describe the containment queries. The following is a containment query:

Q1. /doc[author=‘John Smith’]//section/title It selects titles of sections contained in the document authored by “John Smith”. In this query, the leading “/” indicates that “doc” must be a root element. “[author=‘John Smith’]” is a predicate restricting “doc” elements to those that contain “author” elements, whose content is “John Smith”. The symbols “/” and “//” represent containment, with “/” indicating direct containment (i.e., parent-child relationship), and “//” indicating indirect containment (i.e., predecessor-descendent relationship). The following is an IR Boolean and proximity query: Q2. /doc[author/(‘Smith’ NOT ‘Adams’) AND distance(‘UNIX’, ‘DOS’)≤5 ] It selects all documents whose authors include “Smith” but not “Adams”, and this document must also have the two words “UNIX” and “DOS” within a distance of five words. LoreL [1] defines a class of useful regular path expressions, which can use wildcards ‘?’, ‘+’, and ‘*’ to mean repetitions of zero or one, one or more, and zero or more, respectively. For example the expression Q3. chapter[1]/section*/title selects the titles of the first chapter, as well as the titles of sections and subsections in the chapter. Note that this expression differs from chapter[1]/section/*/title, which selects the titles of anything contained in a section of the first chapter, including the titles of captions or figures. Note that since there is no leading “/”, “chapter” can be anywhere inside a document. At the heart of these queries is a simple containment query: does one specified element or word appear within another specified element?

2.2 Containment Query Processing Using the Inverted Index The inverted index [32] is very popular in information retrieval systems as it supports Boolean, proximity, and ranking queries efficiently. The classic inverted index data structure maps a text word (or a phrase) to a list, which enumerates documents containing the word and its position within each document. In order to process structured documents such as XML, the inverted index can be extended in a simple way: text words are indexed in a T-index similar to that used in a traditional IR system, and elements are indexed in an E-index, which maps elements to inverted lists. Figure 1 illustrates the structure of the two indexes for a sample XML file. Each inverted list records the occurrences of a word or an element—here we use “term” to refer to both of them. Each occurrence is indexed by its document number, its position and its nesting depth within the document. This is denoted in Figure 1 as (docno, begin : end, level) for an element and (docno, wordno, level) for a text word. The position, begin : end or wordno, in a document can be generated by counting word numbers. Alternatively, if the document is in a parsed tree format, the position can be generated by doing a depthfirst traversal of the tree and sequentially assigning a number at each visit. Since each non-leaf node is always traversed twice, once before visiting all its children and once after, it has two numbers assigned, while leaf nodes have only one number. An inverted list is sorted in the increasing order of docno, and then in the increasing order of begin and end1 . 1

Since XML documents are strictly nested, sorting in the

<section> <section> <section> (a)

<section>

(1, 1:23, 0) (1, 8:22, 1) (1, 14:21, 2) ...

John SIGMOD99 Smith74 John99b John SIGMOD99 John97 Smith74 Smith JACM Adams69

Figure 15: Bibliograph in XML.

APPENDIX A. LEVERAGING THE POWER OF THE RDBMS By implementing containment queries using an RDBMS, we are able to process queries that are difficult or impossible to process using only an inverted list engine. We show two examples. Type 1. Joined Searching. Figure 15 shows a sample XML document with three bibliography entries. Suppose we want to find those bib entries that cite Smith’s paper. Figure 16 shows the query in SQL. Type 2. Queries on Mixed Data. Suppose we have in our database an inverted index of the DBLP XML files, and a GRADUATES table holding data about graduate students. We can find all students who have a DBLP entry using the SQL query shown in Figure 17.

B.

PERFORMANCE FOR MORE COMPLEX QUERIES

Besides simple “micro benchmark” queries, we also experimented with complex ones. Figures 18 and 19 show two such queries, and Table 5 shows their running times. Query Antonio Knuth

IR 123 235

DB2 (2col ndx) 3261 3633

DB2 (cover ndx) 1651 104

Table 5: Timings of the Antonio query (Shakespeare dataset) and the Knuth query (DBLP dataset) [msec].

From the results of these queries and others we observed that the running times do not depend on the appearance

Find those bib entries that cite Smith’s paper. select bib1.* from ELEMENTS bib1, ELEMENTS bib2, ELEMENTS au, ELEMENTS cite, ELEMENTS key, TEXTS smith, TEXTS t1, TEXTS t2 where bib1.term = ’’ and bib2.term = ’’ and au.term = ’’ and cite.term = ’’ and key.term = ’’ and smith.term = ’smith’ -- bib1 direct_contains cite and bib1.docno = cite.docno and bib1.begin < cite.begin and cite.end < bib1.end and bib1.level = cite.level - 1 -- cite tight_contains t1 and cite.docno = t1.docno and t1.wordno = cite.begin + 1 and t1.wordno = cite.end - 1 -- bib2 direct_contains key and bib2.docno = key.docno and bib2.begin < key.begin and key.end < bib2.end and bib2.level = key.level - 1 -- key tight_contains t2 and key.docno = t2.docno and t2.wordno = key.begin + 1 and t2.wordno = key.end - 1 -- bib2 direct_contains author and bib2.docno = au.docno and bib2.begin < au.begin and au.end < bib2.end and bib2.level = author.level - 1 -- author contains "smith" and au.docno = smith.docno and au.begin < smith.wordno and smith.wordno < au.end -- t1 and t2 are the same thing and t1.term = t2.term

Figure 16: Joined searching.

select g.* from GRADUATES g, ELEMENTS au, TEXTS fn, TEXTS ln where au.term = ’’ -- author contains fn and au.docno = fn.docno and au.begin < fn.wordno and fn.wordno < au.end -- author contains ln and au.docno = ln.docno and au.begin < ln.wordno and ln.wordno < au.end -- fn, ln are the graduates firstname, lastname and fn.term = g.firstname and ln.term = g.lastname Figure 17: Query on mixed data.

Antonio Query: In the speech spoken by antonio, find the line that contains "merchandise". select line.* from ELEMENTS line, ELEMENTS speaker, ELEMENTS speech, TEXTS antonio, TEXTS merchandise where line.term = ’’ and speaker.term = ’<speaker>’ and speech.term = ’<speech>’ and antonio.term = ’antonio’ and merchandise.term = ’merchandise’ -- all in the same document and line.docno = merchandise.docno and merchandise.docno = speech.docno and speech.docno = speaker.docno and speaker.docno = antonio.docno -- CONTAINS merchandise and line.begin < merchandise.wordno and merchandise.wordno < line.end -- merchandise CONTAINEDIN <speech> and speech.begin < merchandise.wordno and merchandise.wordno < speech.end -- <speech> CONTAINS <speaker> and speech.begin < speaker.begin and speaker.end < speech.end -- <speaker> IS "antonio" and antonio.wordno - speaker.begin = 1 and speaker.end - antonio.wordno = 1

Figure 18: The Antonio query.

Knuth Query: Find author containing "donald" followed by "knuth" within 2 words. select au.* from ELEMENTS au, TEXTS donald, TEXTS knuth where au.term = ’’ and donald.term = ’donald’ and knuth.term = ’knuth’ -- in the same document and au.docno = donald.docno and donald.docno = knuth.docno -- contains both "donald" and "knuth" and au.begin < donald.wordno and knuth.wordno < au.end -- "donald" followed by "knuth" within 2 words and 0 <= knuth.wordno - donald.wordno and knuth.wordno - donald.wordno <= 2

Figure 19: The Knuth query.

of the queries. In fact, complex queries may run quickly because they may contain highly selective predicates. As pointed out in section 3.3, the RDBMS can out-perform the inverted list engine when there is a join with a very selective term and a non-selective term. The Knuth query is a case in point.