NiagaraCQ: a scalable continuous query system for Internet databases

ABSTRACT

Continuous queries are persistent queries that allow users to receive new results when they become available. While continuous query systems can transform a passive web into an active environment, they need to be able to support millions of queries due to the scale of the Internet. No existing systems have achieved this level of scalability. NiagaraCQ addresses this problem by grouping continuous queries based on the observation that many web queries share similar structures. Grouped queries can share the common computation, tend to fit in memory and can reduce the I/O cost significantly. Furthermore, grouping on selection predicates can eliminate a large number of unnecessary query invocations. Our grouping technique is distinguished from previous group optimization approaches in the following ways. First, we use an incremental group optimization strategy with dynamic re-grouping. New queries are added to existing query groups, without having to regroup already installed queries. Second, we use a query-split scheme that requires minimal changes to a general-purpose query engine. Third, NiagaraCQ groups both change-based and timer-based queries in a uniform way. To insure that NiagaraCQ is scalable, we have also employed other techniques including incremental evaluation of continuous queries, use of both pull and push models for detecting heterogeneous data source changes, and memory caching. This paper presents the design of NiagaraCQ system and gives some experimental results on the system's performance and scalability.

REFERENCES

• CM86: Upen S. Chakravarthy , Jack Minker, Multiple Query Processing in Deductive Databases using Query Graphs, Proceedings of the 12th International Conference on Very Large Data Bases, p.384-391, August 25-28, 1986
• DFF+98: A. Deutsch, M. Fernandez, D. Florescu, A. Levy, D. Suciu. XML-QL: A Query Langaage for XML. http://www.w3.org/TR/NOTE-xml-ql.
• HCH+99: Chris Carnes , J. B. Park , Albert Vernon, Scalable Trigger Processing, Proceedings of the 15th International Conference on Data Engineering, p.266, March 23-26, 1999
• HJ94: E. N. Hanson and T. Johnson. Selection Predicate Indexing for Active Databases Using Interval Skip List. TR94-017. CIS department, University of Florida, 1994.
• LPBZ96: Differential evaluation of continual queries, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.458, May 27-30, 1996
• LPT99: Ling Liu , Calton Pu , Wei Tang, Continual Queries for Internet Scale Event-Driven Information Delivery, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.610-628, July 1999 [doi>10.1109/69.790816]
• MD89: Dennis McCarthy , Umeshwar Dayal, The architecture of an active database management system, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.215-224, June 1989, Portland, Oregon, United States
• RC88: Arnon Rosenthal , Upen S. Chakravarthy, Anatomy of a Mudular Multiple Query Optimizer, Proceedings of the 14th International Conference on Very Large Data Bases, p.230-239, August 29-September 01, 1988
• Sel86: T. Sellis. Multiple query optimization. ACM Transactions on Database Systems, 10(3), 1986.
• SJGP90: Michael Stonebraker , Anant Jhingran , Jeffrey Goh , Spyros Potamianos, On rules, procedure, caching and views in data base systems, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.281-290, May 23-26, 1990, Atlantic City, New Jersey, United States
• SK95: Eric Simon , Angelika Kotz Dittrich, Promises and Realities of Active Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.642-653, September 11-15, 1995
• SPAM91: Ulf Schreier , Hamid Pirahesh , Rakesh Agrawal , C. Mohan, Alert: An Architecture for Transforming a Passive DBMS into an Active DBMS, Proceedings of the 17th International Conference on Very Large Data Bases, p.469-478, September 03-06, 1991
• TGNO92: Douglas Terry , David Goldberg , David Nichols , Brian Oki, Continuous queries over append-only databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.321-330, June 02-05, 1992, San Diego, California, United States
• WF89: Jennifer Widom , S. J. Finkelstein, Set-oriented production rules in relational database systems, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.259-270, May 23-26, 1990, Atlantic City, New Jersey, United States
• ZDNS98: Yihong Zhao , Prasad M. Deshpande , Jeffrey F. Naughton , Amit Shukla, Simultaneous optimization and evaluation of multiple dimensional queries, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.271-282, June 01-04, 1998, Seattle, Washington, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Experimentation, Management