Adaptive Query Processing in Data Stream Management Systems

Abstract

This thesis addresses the problem of processing continuous queries in a Data Stream Management System (DSMS) when stream characteristics and system conditions may vary unpredictably over time. We present a generic framework, called StreaMon, for adaptive query processing in a DSMS. StreaMon has three core components: <ol> <li> An Executor, which runs the current plan for each query </li> <li> A Profiler, which collects and maintains statistics about current stream characteristics and system conditions </li> <li> A Re-optimizer, which ensures the current plans are the most efficient for current stream characteristics and system conditions </li> </ol> We instantiate the generic StreaMon framework for three distinct combinations of continuous query type and adaptivity need: <ol> <li> Adaptive processing of commutative filters over a stream to maximize throughput at all points in time </li> <li> Adaptive placement of subresult caches in pipelined plans for windowed stream joins to maximize throughput at all points in time </li> <li> Detecting relaxed constraints automatically in input streams and exploiting these constraints to reduce memory requirements in plans for windowed stream joins </li> </ol> For each problem, we provide the definition and motivating examples, develop and analyze adaptive algorithms, and present implementation techniques and experimental results from the STREAM general-purpose DSMS prototype developed at Stanford.