Online Dynamic Reordering for Interactive Data Processing.
Vijayshankar Raman, Bhaskaran Raman, Joseph M. Hellerstein:
Online Dynamic Reordering for Interactive Data Processing.
VLDB 1999: 709-720@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-7},
pages = {709-720},
ee = {db/conf/vldb/RamanRH99.html},
crossref = {DBLP:conf/vldb/99},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
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.
Copyright © 1999 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Malcolm P. Atkinson, Maria E. Orlowska, Patrick Valduriez, Stanley B. Zdonik, Michael L. Brodie (Eds.):
VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK.
Morgan Kaufmann 1999, ISBN 1-55860-615-7
Contents 
References
- [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 J. 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.
Commun. ACM 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.
ACM Comput. Surv. 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 J. 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 Conference 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 Conference 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
Copyright © Tue Mar 16 02:22:09 2010
by Michael Ley (ley@uni-trier.de)
