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

1. CM86 U.S. Chakravarthy and J. Minker. Multiple Query Processing in Deductive Databases using Query Graphs. VLDB Conference 1986: 384-391.
2. 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.
3. HCH+99 E. N. Hanson, C. Carnes, L. Huang, M. Konyala, L. Noronha, S. Parthasarathy, J.B.Park and A. Vernon. Scalable Trigger Processing. In proceeding of 15 th ICDE, page 266-275, Sydney, Australia, 1999.
4. 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.
5. LPBZ96 L. Liu, C. Pu, R. Barga, T. Zhou. Differential Evaluation of Continual Queries. ICDCS 1996: 458-465.
6. LPT99 L. Liu, C. Pu, W. Tang. Continual Queries for Internet Scale Event-Driven Information Delivery. TKDE 11(4): 610-628 (1999).
7. MD89 D. McCarthy and U. Dayal. The architecture of an active database management system. SIGMOD 1989: 215-224.
8. RC88 A. Rosenthal and U. S. Chakravarthy. Anatomy of a Modular Multiple Query Optimizer. VLDB 1988: 230-239.
9. Sel86 T. Sellis. Multiple query optimization. ACM Transactions on Database Systems, 10(3), 1986.
10. SJGP90 M. Stonebraker, A. Jhingran, J. Goh and S. Potamianos. On Rules, Procedures, Caching and Views in Data Base Systems. SIGMOD Conference 1990: 281-290.
11. SK95 E. Simon, A. Kotz-Dittrich. Promises and Realities of Active Database Systems. VLDB 1995: 642-653.
12. SPAM91 U. Schreier, H. Pirahesh, R. Agrawal, and C. Mohan. Alert: An architecture for transforming a passive dbms into an active dbms. VLDB 1991: 469-478.
13. TGNO92 D. Terry, D. Goldberg, D. Nichols, and B. Oki. Continuous Queries over Append-Only Databases. SIGMOD 1992: 321-330.
14. WF89 J. Widom and S.J. Finklestein. Set-Oriented Production Rules in Relational Database Systems. SIGMOD Conference 1990: 259-270.
15. ZDNS98 Y. Zhao, P. Deshpande, J. F. Naughton, A. Shukla. Simultaneous Optimization and Evaluation of Multiple Dimensional Queries. SIGMOD 1998: 271-282.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

    • Query languages

  • Information retrieval

  • Information storage systems