Digital Symposium Collection 2000  

 
 
 
 
 
 

 



















Online Dynamic Reordering for Interactive Data Processing

Vijayshankar Raman, Bhaskaran Raman, and Joseph M. Hellerstein

  View Paper (PDF)  

Return to Query Systems

Abstract
We present a pipelining, dynamically user-controllable reorder operator, for use in data-intensive applications. Allowing the user to reorder the data delivery on the fly increases the interactivity in several contexts such as online aggregation and large-scale spreadsheets; it allows the user to control the processing of data by dynamically specifying preferences for different data items based on prior feedback, so that data of interest is prioritized for early processing. We describe an efficient, non-blocking mechanism for reordering, which can be used over arbitrary data streams from files, indexes, and continuous data feeds. We also investigate several policies for the reordering based on the performance goals of various typical applications. We present results from an implementation used in Online Aggregation in the Informix Dynamic Server with Universal Data Option, and in sorting and scrolling in a large-scale spreadsheet. Our experiments demonstrate that for a variety of data distributions and applications, reordering is responsive to dynamic preference changes, imposes minimal overheads in overall completion time, and provides dramatic improvements in the quality of the feedback over time. Surprisingly, preliminary experiments indicate that online reordering can also be useful in traditional batch query processing, because it can serve as a form of pipelined, approximate sorting.


References

Note: References link to DBLP on the Web.

[A+96]
Alexander Aiken , Jolly Chen , Michael Stonebraker , Allison Woodruff : Tioga-2: A Direct Manipulation Database Visualization Environment. ICDE 1996 : 208-217
[A+97]
Swarup Acharya , Michael J. Franklin , Stanley B. Zdonik : Balancing Push and Pull for Data Broadcast. SIGMOD Conference 1997 : 183-194
[AZ96]
Gennady Antoshenkov , Mohamed Ziauddin : Query Processing and Optimization in Oracle Rdb. VLDB Journal 5(4) : 229-237(1996)
[Bat79]
...
[Bat90]
...
[BM85]
David C. Blair , M. E. Maron : An Evaluation of Retrieval Effectiveness for a Full-Text Document-Retrieval System. CACM 28(3) : 289-299(1985)
[C+98]
Surajit Chaudhuri , Rajeev Motwani , Vivek R. Narasayya : Random Sampling for Histogram Construction: How much is enough? SIGMOD Conference 1998 : 436-447
[CD97]
Surajit Chaudhuri , Umeshwar Dayal : Data Warehousing and OLAP for Decision Support (Tutorial). SIGMOD Conference 1997 : 507-508
[CK97]
Michael J. Carey , Donald Kossmann : On Saying "Enough Already!" in SQL. SIGMOD Conference 1997 : 219-230
[Exc]
...
[G+96]
Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh : Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total. ICDE 1996 : 152-159
[GM98]
Phillip B. Gibbons , Yossi Matias : New Sampling-Based Summary Statistics for Improving Approximate Query Answers. SIGMOD Conference 1998 : 331-342
[Gra93]
Goetz Graefe : Query Evaluation Techniques for Large Databases. Computing Surveys 25(2) : 73-170(1993)
[H+]
...
[Haa97]
Peter J. Haas : Large-Sample and Deterministic Confidence Intervals for Online Aggregation. SSDBM 1997 : 51-63
[HH99]
Peter J. Haas , Joseph M. Hellerstein : Ripple Joins for Online Aggregation. SIGMOD Conference 1999 : 287-298
[H+97]
Joseph M. Hellerstein , Peter J. Haas , Helen Wang : Online Aggregation. SIGMOD Conference 1997 : 171-182
[H+98]
Joseph M. Hellerstein , Ron Avnur , Andy Chou , Christian Hidber , Chris Olston , Vijayshankar Raman , Tali Roth , Peter J. Haas : Interactive data Analysis: The Control Project. IEEE Computer 32(8) : 51-59(1999)
[HN96]
Joseph M. Hellerstein , Jeffrey F. Naughton : Query Execution Techniques for Caching Expensive Methods. SIGMOD Conf. 1996 : 423-434
[OJ93]
...
[S+96]
Praveen Seshadri , Joseph M. Hellerstein , Hamid Pirahesh , T. Y. Cliff Leung , Raghu Ramakrishnan , Divesh Srivastava , Peter J. Stuckey , S. Sudarshan : Cost-Based Optimization for Magic: Algebra and Implementation. SIGMOD Conf. 1996 : 435-446
[SS]
...
[Sto89]
Michael Stonebraker : The Case for Partial Indexes. SIGMOD Record 18(4) : 4-11(1989)
[vR75]
C. J. van Rijsbergen : Information Retrieval. Butterworth 1979, ISBN 0-408-70929-4
[Z+]
Yihong Zhao , Prasad Deshpande , Jeffrey F. Naughton : An Array-Based Algorithm for Simultaneous Multidimensional Aggregates. SIGMOD Conference 1997 : 159-170

Referenced by

  1. Peter J. Haas : Techniques for Online Exploration of Large Object-Relational Datasets. SSDBM 1999 : 4-12

BIBTEX

@inproceedings{DBLP:conf/vldb/RamanRH99,
  author    = {Vijayshankar Raman and
                Bhaskaran Raman and
                Joseph M. Hellerstein},
   editor    = {Malcolm P. Atkinson and
                Maria E. Orlowska and
                Patrick Valduriez and
                Stanley B. Zdonik and
                Michael L. Brodie},
   title     = {Online Dynamic Reordering for Interactive Data Processing},
   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     = {709-720},
   crossref  = {DBLP:conf/vldb/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM