Database Seminar Series (2003-2004)

This is joint work with Sihem Amer-Yahia, Mary Fernandez, and Yu Xu. 

If there is time, I will also talk about the following:

Latency Profiles: Performance Monitoring for Wide Area Applications

Recent technological advances have enabled the deployment of wide area applications against Internet accessible sources. A performance challenge to applications in such a setting is the unpredictable end-to-end latency of accessing these sources. We use passive information gathering mechanisms to learn end-to-end latency distributions and construct Latency Profiles (LPs). We hypothesize that a group of clients, within an autonomous system (AS), that are accessing a content server, in another AS, may be represented by (one or more) LPs. Related networking research on IDMaps, points of congestion, and BGP routes support such hypothesis. We develop aggregate LPs to provide coverage of groups (clusters) of client-server pairs. Using data gathered from a (limited) experiment we demonstrate the feasibility of constructing LPs and aggregate LPs.

Joint work with Avigdor Gal, Vladimir Zadorozhny and Hui-Fang Wen

Many modern applications process queries over unbounded streams of data, including intrusion detection in networks, monitoring remote sensors, and monitoring patients vital signs. These data streams arrive in real time, are unbounded in length and have unpredictable arrival patterns due to external uncontrollable factors such as network congestion or weather in the case of remote sensors. In this talk, I'll describe the recent research and system development activities we have been undergoing at Worcester Polytechnic Institute in this emerging area of stream query engines.

One, I'll describe the novel approach we are taking towards processing XQueries over XML streams. XML stream applications bring the challenge of efficiently processing queries on sequentially accessible token-based data. While the automata model is naturally suited for pattern matching on tokenized XML streams, the algebraic model in contrast is a well-established technique for set-oriented processing of self-contained tuples. However, neither automata nor algebraic models are well-equipped to handle both computation paradigms. Our Raindrop engine thus accommodates these two paradigms within one algebraic framework to take advantage of both. In our query model, both tokenized data and self-contained tuples are supported in a uniform manner. Query plans can be flexibly rewritten using equivalence rules to change what computation is done using tokenized data versus tuples. The necessity of such a uniform plan model are been illustrated using an experimental study.

Two, we have designed a novel technique for adapting the execution of stream queries that, to my knowledge, is not present in any other continuous query system to date. Namely, we note that utilizing a single scheduling algorithm to execute a continuous query, as is employed in most current continuous query systems, is not adequate because no existing scheduling algorithms can optimally meet an arbitrary set of Quality of Service (QoS) requirements. Therefore, an adaptive strategy selector guidable by QoS requirements was developed to meet arbitrary Quality of Service (QoS) requirements. The adaptive strategy selector monitors the effects of its behavior on its environment through a feedback mechanism, with the aim of exploiting previously beneficial behavior and exploring alternative behavior. The feedback mechanism is guided by qualitatively comparing how well each algorithm has met the QoS requirements. Then the next scheduling algorithm is chosen by spinning a roulette wheel where each candidate is chosen with a probability equal to its performance score. The adaptive algorithm was shown to be effective in outperforming single scheduling algorithms for many QoS combinations and stream arrival patterns.

Three, we also have been studying methods for online plan reoptimization and plan migration so to online modify the structure of the query plan. Dynamic query plan migration is concerned with the on-the-fly transition from one continuous query plan to a semantically equivalent yet more efficient query plan. In particular, we have designed two alternate online plan migration strategies for continuous queries over data streams for plans with window-based join operators. The first strategy is called "moving state strategy" and the second is called "parallel track strategy". In the moving state strategy, the query execution is paused and all tuples in intermediate queues are drained before switching to a new plan. In the parallel track strategy, the new plan is plugged and the system executes both plans in parallel until eventually disconnecting the old plan. Pros and Cons of these techniques are discussed, and an experimental study exposing the trade-offs between these techniques will be analyzed.

In this talk, I will give an overview of how our group has addressed these issues in designing algorithms and data structures for database operations. I will then explore in more depth how buffering can be
helpful, in several contexts, for avoiding cache misses. Buffering can improve throughput while still providing certain response-time guarantees.

This talk represents joint work with Jingren Zhou.