Digital Symposium Collection 2000

Online Feedback for Nested Aggregate Queries with Multi-Threading Kian-Lee Tan, Cheng Hian Goh, and Beng Chin Ooi   View Paper (PDF)   Return to Aggregation, Approximation & Explanation Note: The quality of the PDF contained herein reflects that of the material supplied to the DiSC'00 Production Team. Abstract In the paper, we study the progressive evaluation of nested queries with aggregates (i.e., the inner query block is an aggregate query), where users are provided progressively with (approximate) answers as the inner block is evaluated. We propose an incremental evaluation strategy to present answers that are certainly in the final answer space first, before presenting those whose validity may be affected as the inner query aggregates are refined. We also propose a multithreaded model in evaluating such queries: the outer query is assigned to a thread, and the inner query is assigned to another thread. The time-sliced across the two subqueries is nondeterministic in the sense that the user controls the relative rate at which these subqueries are being evaluated. We implemented a prototype system using JAVA, and evaluated our system. Our results show the effectiveness of the proposed mechanisms in providing online feedback that reduce the initial waiting time of users significantly without sacrificing on the quality of the answers. References Note: References link to DBLP on the Web. [1] Roberto J. Bayardo Jr. , Daniel P. Miranker : Processing Queries for First Few Answers. CIKM 1996 : 45-52 [2] Umeshwar Dayal : Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987 : 197-208 [3] Richard A. Ganski , Harry K. T. Wong : Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987 : 23-33 [4] Peter J. Haas : Large-Sample and Deterministic Confidence Intervals for Online Aggregation. SSDBM 1997 : 51-63 [5] Peter J. Haas , Joseph M. Hellerstein : Ripple Joins for Online Aggregation. SIGMOD Conference 1999 : 287-298 [6] Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami : Selectivity and Cost Estimation for Joins Based on Random Sampling. JCSS 52(3) : 550-569(1996) [7] Joseph M. Hellerstein , Peter J. Haas , Helen Wang : Online Aggregation. SIGMOD Conference 1997 : 171-182 [8] Wen-Chi Hou , Gultekin Özsoyoglu , Baldeo K. Taneja : Statistical Estimators for Relational Algebra Expressions. PODS 1988 : 276-287 [9] Wen-Chi Hou , Gultekin Özsoyoglu , Baldeo K. Taneja : Processing Aggregate Relational Queries with Hard Time Constraints. SIGMOD Conference 1989 : 68-77 [10] Won Kim : On Optimizing an SQL-like Nested Query. TODS 7(3) : 443-469(1982) [11] Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider , S. Seshadri : Efficient Sampling Strategies for Relational Database Operations. TCS 116(1&2) : 195-226(1993) [12] Guy M. Lohman , Dean Daniels , Laura M. Haas , Ruth Kistler , Patricia G. Selinger : Optimization of Nested Queries in a Distributed Relational Database. VLDB 1984 : 403-415 [13] Frank Olken : Random Sampling from Databases. Ph.D. thesis, University of California at Berkeley LBL Technical Report 1993 [14] Kian-Lee Tan , Cheng Hian Goh , Beng Chin Ooi : On Getting Some Answers Quickly, and Perhaps More Later. ICDE 1999 : 32-39 [15] Annita N. Wilschut , Peter M. G. Apers : Dataflow Query Execution in a Parallel Main-Memory Environment. PDIS 1991 : 68-77 BIBTEX @inproceedings{DBLP:conf/vldb/TanGO99,   author    = {Kian-Lee Tan and                 Cheng Hian Goh and                 Beng Chin Ooi},    editor    = {Malcolm P. Atkinson and                 Maria E. Orlowska and                 Patrick Valduriez and                 Stanley B. Zdonik and                 Michael L. Brodie},    title     = {Online Feedback for Nested Aggregate Queries with Multi-Threading},    booktitle = {VLDB'99, Proceedings of 25th International Conference on Very                 Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,                 UK},    publisher = {Morgan Kaufmann},    year      = {1999},    isbn      = {1-55860-615-5},    pages     = {18-29},    crossref  = {DBLP:conf/vldb/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM