Learning response time for WebSources using query feedback and application in query optimization

This paper explores the space of real delay at a WebSource, versus the WebPT prediction of this delay, with respect to critical points of delay in specific plans, and identifies those cases where WebPT overestimation or underestimation of the real delay results in a penalty in the scrambling enabled optimizer, andThose cases where there is no penalty.

Abstract

The rapid growth of the Internet and support for interoperability \nprotocols has increased the number of Web accessible sources, WebSources.\nCurrent optimization technology for wrapper mediator architectures\nneeds to be extended to estimate the response time (delays) to access\nWebSources and to use this delay in query optimization.\nIn this paper, we present a Multi-Dimensional Table (MDT), a tool that \nis based on learning using query feedback from WebSources.\nWe describe the MDT learning algorithms, and report on the MDT learning for\nWebSources. The MDT uses dimensions Time of day, Day, and Quantity of data, to learn\nresponse times from a particular WebSource, and to predict the expected \nresponse time (delay), and a confidence in this prediction, for some query.\nExperiment data was collected from several WebSources and analyzed, to \ndetermine those dimensions that were significant in estimating the response time\nfor particular WebSources. Our research shows that we can improve the quality of learning by \ntuning the MDT features, e.g., including significant dimensions in the MDT,\nor changing the ordering of dimensions. We then demonstrate how the MDT \nprediction of delay may be used by a scrambling enabled optimizer. \nA scrambling algorithm identifies some critical points of delay, where it makes \na decision to scramble (modify) a plan, to attempt to hide the expected delay \nby computing some other part of the plan that is unaffected by the delay.\nWe explore the space of real delay at a WebSource, versus the MDT prediction of\nthis delay, with respect to critical points of delay in specific plans.\nWe identify those cases where MDT overestimation or underestimation of the\nreal delay results in a penalty in the scrambling enabled optimizer, and \nthose cases where there is no penalty. Using the experimental\ndata and MDT learning, we test how good the MDT is in minimizing these penalties.\nAlso cross-referenced as UMIACS TR #98-64