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}
}
BibTeX
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 ...
BibTeX
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 BibTeX
References
- [A+96]
- Alexander Aiken, Jolly Chen, Michael Stonebraker, Allison Woodruff:
Tioga-2: A Direct Manipulation Database Visualization Environment.
ICDE 1996: 208-217 BibTeX
- [A+97]
- Swarup Acharya, Michael J. Franklin, Stanley B. Zdonik:
Balancing Push and Pull for Data Broadcast.
SIGMOD Conference 1997: 183-194 BibTeX
- [AZ96]
- Gennady Antoshenkov, Mohamed Ziauddin:
Query Processing and Optimization in Oracle Rdb.
VLDB J. 5(4): 229-237(1996) BibTeX
- [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) BibTeX
- [C+98]
- Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya:
Random Sampling for Histogram Construction: How much is enough?
SIGMOD Conference 1998: 436-447 BibTeX
- [CD97]
- Surajit Chaudhuri, Umeshwar Dayal:
Data Warehousing and OLAP for Decision Support (Tutorial).
SIGMOD Conference 1997: 507-508 BibTeX
- [CK97]
- Michael J. Carey, Donald Kossmann:
On Saying "Enough Already!" in SQL.
SIGMOD Conference 1997: 219-230 BibTeX
- [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 BibTeX
- [GM98]
- Phillip B. Gibbons, Yossi Matias:
New Sampling-Based Summary Statistics for Improving Approximate Query Answers.
SIGMOD Conference 1998: 331-342 BibTeX
- [Gra93]
- Goetz Graefe:
Query Evaluation Techniques for Large Databases.
ACM Comput. Surv. 25(2): 73-170(1993) BibTeX
- [H+]
- ...
- [Haa97]
- Peter J. Haas:
Large-Sample and Deterministic Confidence Intervals for Online Aggregation.
SSDBM 1997: 51-63 BibTeX
- [HH99]
- Peter J. Haas, Joseph M. Hellerstein:
Ripple Joins for Online Aggregation.
SIGMOD Conference 1999: 287-298 BibTeX
- [H+97]
- Joseph M. Hellerstein, Peter J. Haas, Helen J. Wang:
Online Aggregation.
SIGMOD Conference 1997: 171-182 BibTeX
- [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) BibTeX
- [HN96]
- Joseph M. Hellerstein, Jeffrey F. Naughton:
Query Execution Techniques for Caching Expensive Methods.
SIGMOD Conference 1996: 423-434 BibTeX
- [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 BibTeX
- [SS]
- ...
- [Sto89]
- Michael Stonebraker:
The Case for Partial Indexes.
SIGMOD Record 18(4): 4-11(1989) BibTeX
- [vR75]
- C. J. van Rijsbergen:
Information Retrieval.
Butterworth 1979, ISBN 0-408-70929-4
BibTeX
- [Z+]
- Yihong Zhao, Prasad Deshpande, Jeffrey F. Naughton:
An Array-Based Algorithm for Simultaneous Multidimensional Aggregates.
SIGMOD Conference 1997: 159-170 BibTeX
Referenced by
- Ron Avnur, Joseph M. Hellerstein:
Eddies: Continuously Adaptive Query Processing.
SIGMOD Conference 2000: 261-272
- Peter J. Haas:
Techniques for Online Exploration of Large Object-Relational Datasets.
SSDBM 1999: 4-12
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:30 2009