Index Stride
Ripple Joins
Online Reordering

Aggregation queries in relational database systems often require scanning and analyzing a significant portion of a database. In current relational systems such queries have batch behavior, requiring a long wait. The online version of the same queries reports a running estimate of the final aggregate in real time, along with a confidence measure during the processing of the query. The measure, or "confidence interval", says that with x% confidence, the current estimate is within a certain interval around the final answer. Reaching a small confidence interval quickly can allow the user to stop the query and go on to his/her next task. As a performance measure, online algorithms are designed to shrink the confidence interval faster while providing updated estimates at a satisfactory rate. To support this behavior, we developed a family of algorithms called Ripple Joins, which allow the user to dynamically control the tradeoff between the rate at which the confidence interval shrinks (accuracy of the display), and the time between successive estimations (interactivity of the display). 

Besides continually improving feedback, another important component of interactive query processing is support for dynamic user control over the processing. For instance in GROUP BY queries, we would like the user to be able to dynamically control the rates at which the estimates for different groups improve, based on how interesting the results are. We have developed amechanism to reorder the tuples within a dataflow to support this behaviour.



[ Home | Projects | News | Papers | People | Demos]


Send mail to with questions or comments about this web site.
Last modified: February 11, 1999