Vijayshankar Raman, Bhaskaran Raman and Joseph M. Hellerstein

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-99-1043
1999

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1043.pdf

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.

In this paper 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.

BibTeX citation:

@techreport{Raman:CSD-99-1043,
    Author = {Raman, Vijayshankar and Raman, Bhaskaran and Hellerstein, Joseph M.},
    Title = {Online Dynamic Reordering for Interactive Data Processing},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1999},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5565.html},
    Number = {UCB/CSD-99-1043},
    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. <p>In this paper 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.}
}

EndNote citation:

%0 Report
%A Raman, Vijayshankar
%A Raman, Bhaskaran
%A Hellerstein, Joseph M.
%T Online Dynamic Reordering for Interactive Data Processing
%I EECS Department, University of California, Berkeley
%D 1999
%@ UCB/CSD-99-1043
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5565.html
%F Raman:CSD-99-1043